Welcome to EDAboard.com

Welcome to our site! EDAboard.com is an international Electronics Discussion Forum focused on EDA software, circuits, schematics, books, theory, papers, asic, pld, 8051, DSP, Network, RF, Analog Design, PCB, Service Manuals... and a whole lot more! To participate you need to register. Registration is free. Click here to register now.

Question about error correcting codes and interleaving.

Status
Not open for further replies.

lomaxe

Member level 1
Joined
Dec 9, 2010
Messages
39
Helped
3
Reputation
6
Reaction score
3
Trophy points
1,288
Location
Ukraine
Activity points
1,683
Hi guys!!!
Before posing the problem, I want to sorry for my English. I'm from Ukraine and my English is not very good.
So, I read "Digital Communication" book (by Bernard Sklar) now.And I try to solve the problems after every chapter. As I do it by myself, I have downloaded the "Solution Manual" for all the problems given in the book. I use it to control myself.
And I have a question about solving of one of the problems.
I want to give some theory from the book and the problem and the solution of the problem from the "Solution Manual".

Theory about block interleaving:
A block interleaver accepts the coded symbols in blocks from the encoder, permutes the symbols, and then feeds the rearranged symbols to the modulator. The usual permutation of the block is accomplished by filling the columns of M-row and N-column (MxN) array with the encoded sequence. After the array is completely filled, the symbols are then fed to the modulator one row at a time and transmitted over the channel. At the receiver, the deinterleaver performs the inverse operation; it accepts the symbols from the demodulator, deinterleaves them, and feeds them to the decoder. Symbols are entered into the deinterleaver array by rows and removes by columns.
The most important characteristics of such a block interleaver are as follows:
1. Any burst of less than N contiguous channel symbol errors results in isolated errors at the deinterleaver output that are separated from each other by at least M symbols.
2. Any bN burst of errors, were b>1, results in output bursts from the deinterleaver of no more than b symbols errors (here b means the smallest integer no less than b). Each output bursts is separated from the other bursts by no less than M-b symbols (here b means the largest integer no greater than b).
3. A periodic sequence of single errors spaced N symbols apart results in a single burst of errors of length M at the deinterleaver output.
4. The interleaver/deinterleaver end-to-end is approximately 2MN symbol times. To be precise, only M(N-1)+1 memory cells need to be filled before NxN array is filled transmission can begin (as soon as the first symbol of the last column of the MxN array is filled). A corresponding number needs to be filled at the receiver before decoding begins. Thus the minimum end-to-end delay is (2MN-2M+2) symbol times, not including any channel propagation delay.
5. The memory requirement is MN symbols for each location (interleaver and deinterleaver). However, since the MxN array needs to be (mostly) filled before it can be read out, a memory of 2MN symbols is generally implemented at each location to allow the emptying of one MxN array while the other is being filled, and vice versa.

The problem:

For each of the following conditions, design an interleaver for a communication system operating over a bursty noise channel at a transmission rate of 19,200 code symbols/s.
a) A contiguous noise burst typically lasts for 250 ms. The system code consists of a (127, 36) BCH code with dmin=31. The end-to-end is not to exceed 5 s.
b) A contiguous nois burst typically lasts for 20 ms. The system cod consists of a rat 1/2 convoutional code with a feedback decoding algorithm that corrects an average of 3 symbols in a sequence of 21 symbols. The end-to-end delay is not to exceed 160 ms.

Solution from the "Solution Manual"

a) (127, 36) code with dmin=31. Therefore tmax=15 (correcting capability).
bN error burst of errors results in output bursts from the deinterleaver of no more than b symbols errors (here b means the smallest integer no less than b). Each output burst is separated by at least M-b symbols (here b means the largest integer no greater than b). Channel symbol rate is 19,2 kbit/s. Burst in 250 ms results in 4800 symbol errors, bM=4800.
A code block of 127 bits can correct 15 errors. Thus let b=15; bN=4800, N=4800/15=320.
M-b=127; M=127+15=142.
Therefore the block interleaver is dimensions of (142x320) is suffice....


So, I agree with getting N=320. But I don't understand why the author of the "Solution Manual" took M-b=127. And then, respectively, M=142.
I think this way: if each output burst is separated by at least M-b symbols and (127, 36) code block is able to correct 15 errors within a 127 bits block and, for example, we can have 15 bits errors in the beginning of the block, and 15 bits errors in the beginning of the next 127 bits block, so we need to take error bursts to be separated 127-15=112 bits and 127 bits block code will cope with its task. So, in this case M-b=112. M=112+15=127.
Are my arguments valid? How do you think?
 

bulx

Full Member level 4
Joined
Aug 7, 2004
Messages
225
Helped
47
Reputation
94
Reaction score
17
Trophy points
1,298
Activity points
1,520
Nice question!

I think you are right, and the answer given in the solution manual is also right. Once a codeword is hit with error in the first 15 symbols, it cant take any more hits, that is it cant take an error in the next 127-15 = 112 symbols. However, it doesn't matter if the error burst come much later too, so any M above 127 symbols should be OK. In addition, the given 5s limit on interleaving delay works out to around 150 symbols max for M, thus any M between 127 and 150 should work.

I think the same argument will apply even if the error starts from anywhere within the codeword; not just beginning with the first symbol.

- b
 

lomaxe

Member level 1
Joined
Dec 9, 2010
Messages
39
Helped
3
Reputation
6
Reaction score
3
Trophy points
1,288
Location
Ukraine
Activity points
1,683
Nice question!

I think you are right, and the answer given in the solution manual is also right. Once a codeword is hit with error in the first 15 symbols, it cant take any more hits, that is it cant take an error in the next 127-15 = 112 symbols. However, it doesn't matter if the error burst come much later too, so any M above 127 symbols should be OK. In addition, the given 5s limit on interleaving delay works out to around 150 symbols max for M, thus any M between 127 and 150 should work.

I think the same argument will apply even if the error starts from anywhere within the codeword; not just beginning with the first symbol.

- b

Thank you very much for the answer. I just thought, that solving this problem implies a worst-case scenario.
 

Status
Not open for further replies.

Similar threads

Part and Inventory Search

Welcome to EDABoard.com

Sponsor

Top