Viterbi decoder

A Viterbi decoder uses the Viterbi algorithm for decoding a bitstream that has been encoded using a convolutional code or trellis code. There are other algorithms for decoding a convolutionally encoded stream (for example, the Fano algorithm). The Viterbi algorithm is the most resource-consuming, but it does the maximum likelihood decoding. It is most often used for decoding convolutional codes with constraint lengths k≤3, but values up to k=15 are used in practice. Viterbi decoding was developed by Andrew J. Viterbi and published in the paper "Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm". There are both hardware (in modems) and software implementations of a Viterbi decoder. Viterbi decoding is used in the iterative Viterbi decoding algorithm.

A Viterbi decoder uses the Viterbi algorithm for decoding a bitstream that has been encoded using a convolutional code or trellis code. There are other algorithms for decoding a convolutionally encoded stream (for example, the Fano algorithm). The Viterbi algorithm is the most resource-consuming, but it does the maximum likelihood decoding. It is most often used for decoding convolutional codes with constraint lengths k≤3, but values up to k=15 are used in practice. Viterbi decoding was developed by Andrew J. Viterbi and published in the paper "Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm". There are both hardware (in modems) and software implementations of a Viterbi decoder. Viterbi decoding is used in the iterative Viterbi decoding algorithm. \,\! T = \sqrt{\frac{N_0}{2^k}}, where N_0 is a noise power spectral density, and k is a number of bits for soft decision. Each received symbol may be represented in vector form as v r = {r 0 , r 1 }, where r 0 and r 1 are soft decision values, whose magnitudes signify the joint reliability of the received vector, v r . Every symbol in the code alphabet may, likewise, be represented by the vector v i = {±1, ±1}. The actual computation of the Euclidean distance metric is: \,\!D = (\overrightarrow{v_r} - \overrightarrow{v_i})^2 = \overrightarrow{v_r}^2 - 2 \overrightarrow{v_r} \overrightarrow{v_i} + \overrightarrow{v_i}^2 Each square term is a normed distance, depicting the energy of the symbol. For ex., the energy of the symbol v i = {±1, ±1} may be computed as \,\!\overrightarrow{v_i}^2 = (\pm 1)^2 + (\pm 1)^2 = 2 Thus, the energy term of all symbols in the code alphabet is constant (at (normalized) value 2). The Add-Compare-Select (ACS) operation compares the metric distance between the received symbol ||v r || and any 2 symbols in the code alphabet whose paths merge at a node in the corresponding trellis, ||v i (0) || and ||v i (1) ||. This is equivalent to comparing \,\!D_0 = \overrightarrow{v_r}^2 - 2 \overrightarrow{v_r} \overrightarrow{v_i^0} + \overrightarrow{v_i^0}^2 and \,\!D_1 = \overrightarrow{v_r}^2 - 2 \overrightarrow{v_r} \overrightarrow{v_i^1} + \overrightarrow{v_i^1}^2 But, from above we know that the energy of v i is constant (equal to (normalized) value of 2), and the energy of v r is the same in both cases. This reduces the comparison to a minima function between the 2 (middle) dot product terms, \,\!\min(-2 \overrightarrow{v_r} \overrightarrow{v_i^0},-2 \overrightarrow{v_r} \overrightarrow{v_i^1}) = \max(\overrightarrow{v_r} \overrightarrow{v_i^0}, \overrightarrow{v_r} \overrightarrow{v_i^1}) since a operation on negative numbers may be interpreted as an equivalent operation on positive quantities. Each dot product term may be expanded as \,\! \max(\pm r_0 \pm r_1, \pm r_0 \pm r_1) where, the signs of each term depend on symbols, v i (0) and v i (1) , being compared. Thus, the squared Euclidean metric distance calculation to compute the branch metric may be performed with a simple add/subtract operation.

References

External links

Details on Viterbi decoding, as well as a bibliography. Viterbi algorithm explanation with the focus on hardware implementation issues. r=1/6 k=15 coding for the Cassini mission to Saturn. Online Generator of optimized software Viterbi decoders (GPL). GPL Viterbi decoder software for four standard codes. Description of a k=24 Viterbi decoder, believed to be the largest ever in practical use. Generic Viterbi decoder hardware (GPL).

Text derived from https://en.wikipedia.org/w/index.php?oldid=1374164456 under CC BY-SA 4.0; modifications have been made.