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

ISBN 0471-49581-6

**Download**(direct link)

**:**

**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.

BINARY CONVOLUTIONAL CODES

91

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],

92

THE ART OF ERROR CORRECTING CODING

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

BINARY CONVOLUTIONAL CODES

93

10

01

01

00

10

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)

Received

Synchronized

Reference

Figure 45 VD operation for Example 62, at i = 6.

SKIP

1

... 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:

**41**> 42 43 44 45 46 47 .. 86 >> Next