viterbi decoder(5/6)
Viterbi decoding is the maximum-likelihgood decoding algorithm, mainly used in systems with Convolution(al) codes. The latter means, that it's absolutely exact, but not numerical algorithms. Due to its existense convolutional codes are very spread now. Of course, Viterbi decoding may be applied to any other type of codes, however it will be inefficient and time-consuming.
Viterbi decoding is usually performed on code grid. At every step 2 current bits are compared with the corresponding metrics of the branches of this grid. The differences are calculated and memorized. Consequently these metrics are accumulated at every step. When 2 branches are joined in one node only 1 branch remains, which has the minimum total metrics (or the maximum correlation with the received bits. This sequence of steps is repeated until all the bit stream is finally decoded.
In Hard-iterbi decoding we use Hamming metrics (that is, the bits are demodulated first and then estimated according to the minimum Hamming distance). In Soft-Viterbi decoding we avoid demodulation, but immeadiarely try to find the estimate of the transmitted bits according to the minimum of Euclidean distance.
It's also possible to substitute distance calculation for correlation one. It means that we find the correlation coefficient between the current bits (usually 2, as in convolution(al) codes) and the ones, corresponding to a certain branch, whereby we obtain the decoded bits.
Soft decoding is more sensitive, than the hard one, the energy loss is approximately 2-3 dB.
Convolutional codes are referred to a very extensive class of noise combating codes. They are capable of correcting errors in accordance with their code distance d: d>=2*t+1. In fact, Viterbi decoder may correct even more mistakes if they are not grouped (packeted).
Example: Imagine you have got 2 possible unary combinations at the input: 0 and 1. Consequently, there are 4 possible combinations after convolution(al) coding: 00, 01, 10, 11. Then the bit stream is transmitted through AWGN channel. The received bits are, for example, the following:
y = (0.5, -3, 1.5, -0.5, 1, 0, -1.5, -2.5, 6)
a) In hard decoding at first you should replace these components with 0 and 1 (or with +1 and -1). If y(i)>=0, then y(i) = 1. If y(i)<0, then y(i) = -1. Thereby we demodulate the received vector and get:
y = (1 -1 1 -1 1 1 -1 -1 1). After this we decode this observation with the use of Euclidean distance.
b) In soft thresholding we evaluate the correlation between each pair of bits with the branch of code grid, for example:
00 -> +1+1
0.5 -3 -> 0.5, -3
Correlation = 1*0.5 + 1*(-3) = -2.5. We finally choose the way with the maximum correlation.
-----------------------------------------------------------------------------------
See Bernard Sklar "Digital Communications - Fundamentals and Applications"
With respect,
Dmitrij