in black and white
Main menu
Home About us Share a book
Biology Business Chemistry Computers Culture Economics Fiction Games Guide History Management Mathematical Medicine Mental Fitnes Physics Psychology Scince Sport Technics

The art of error correcting coding - Moreloz R.H.

Moreloz R.H. The art of error correcting coding - Wiley publishing , 2002. - 232 p.
ISBN 0471-49581-6
Download (direct link): artoferrorcorrecting2002.pdf
Previous << 1 .. 35 36 37 38 39 40 < 41 > 42 43 44 45 46 47 .. 86 >> Next

Mmin= min {m(sP}
0<fc<2m-l I * J
is compared to a threshold T.If Mmin > T then T is subtracted from all the metrics. Clearly, this does not affect the selection process, because the metric differences remain the same. This is a method that can be easily implemented in software on a generic processor.
• Modular arithmetic method
The metrics are computed modulo N, so that they lie within the range [0. iV — 1], where N = 2Amax, and Amax is the maximum difference in survivor path metrics.
10 01 01 00
t = 4:
10 01 01 00
Figure 43 VD operation for Example 62, at i = 4.
Obviously, Amax depends on the range of values received from the channel. From the two properties of the Viterbi algorithm, it can be shown that the same MLD path is selected by the Viterbi decoder when computing path metrics with modular arithmetic. In particular, it is possible to use two’s complement arithmetic1, in such a way that overflow can occur but it does not affect the selection process. For details, see [HEK, OCC], This method is favored in hardware implementations of Viterbi decoders.
Path memory management
In a Viterbi decoder, survivor paths and their metrics need to be stored and updated. In a continuous operation mode, while updating the survivor paths at stage i, earlier portions of the survivor paths merge with high probability at stage i — L, where L is the decoding depth. The estimated information bits are taken from the (single) portion of the merged paths at stage i — L. There are different techniques to extract the information bits. Two of the most common are: (1) Register exchange and (2) Traceback memory.
• Register exchange
This method is the easiest to implement in software. All the survivor paths are updated at each iteration of the Viterbi algorithm. Therefore, the information bits can be read directly from the survivor paths. However, if this technique is implemented in hardware, the decoding speed would be low, due to an excessive number of times at which the path memory is read and written. To simplify control flow instructions, a circular pointer of length L can be used. With a circular pointer, at decoding stage i, position (i — L) in memory (to output the decoded bit) is equal to position (i + 1)
7 Arithmetic using the additive group {—2m 1,1 — 2m 1, • • ?, 2m 1 — 1} of m-bit integers [HEK],
10 01 01 00 10
t = 5:
Figure 44 VD operation for Example 62, at i = 5.
modulo L.
• Traceback
This technique is favored in implementations in hardware. The survivor paths are composed of decision values, which indicate state transitions in order to trace back the survivor paths and reconstruct a sequences of states in reverse order.
The traceback memory can be organized as a rectangular array, with rows indexed by k, for all the trellis states S-k\ k = 0,1, - 1. At decoding stage i, for each
trellis state S^\ 0 < j < 2m — 1, the traceback memory (or TB RAM) is written with the rightmost bit of the previous state sff\, t ? {1,2}, associated with the winning branch.
The traceback method trades off memory for decoding speed, since it writes only one bit per state per decoding stage, instead of L bits per state per decoding as in the register exchange method. The information bits are decoded by reading in reverse order the state transitions with an encoder replica (or looking up a state transition table). More memory (number of columns if organized in a rectangular array) is required for continuous operation because, at the same time as information bits are being read out (decoded), new decision values are being written.
Example 64 Continuing with Example 62, using the traceback technique, at the end of the i = 6 received pair of bits from the channel, the traceback memory would have the contents shown in Table 3.
The traceback memory is read starting from the last bit (e.g., use a LIFO), i = 6 (in general T — L). The row address is given by the state with the best metric. This is state S-0* in the example. Read the transition bit b& (in general, bi). The row address (ROW) at i = 5 (i = L — 1), to read the next transition bit b5, is obtained by shifting the address k at i = 6
t = 6:
> (0)
00) y 6= (11,01,01,00,10,11)
01) y 5= (10,00,01,10,10,01)
, <2>
10) y 6=(10,01,11,00,00,11) (n) y®= (10,00,01,10,10,10)
Figure 45 VD operation for Example 62, at i = 6.
... r0[i] Tjfi] r0[i+l] rj[i+l] r0[i+2] r^i+2]
' '
... r0[i] Tjli] r,[i+l] r0[i+2] r j [i+2] ...
v0[i] Vjli] V0[i+1] V,[i+1] v0[i+2] Vj [i+2]
Figure 46 Example of branch misalignment in a Viterbi decoder.
(i = L) and appending the previous decision bit b6 (bi). This can be stated in the following C language instruction:
ROW[j] = ( (ROW[j +1] << 1) && MASK) ' TB_RAM[ROW[j+1] ] [j+1] ;
(where MASK = 2m - 1.)
Continuing in this way, the following state sequence is obtained:
Previous << 1 .. 35 36 37 38 39 40 < 41 > 42 43 44 45 46 47 .. 86 >> Next