Viterbi algorithm for decoding of convolutional codes

Let's consider Viterbi algorithm on example of the code with rate R _code = 1/ n. Let, since a moment t = 0, on encoder input the information sequence of length L symbols a _L = (a ₀, a ₁, …, a_{L– 1}) moves. On encoder output there will be a sequence of symbols b _L = (b ₀, b ₁,..., b_{L –1}). encoder states at the moment t define as a set of n information symbols w_t = (a_t, a_{t –1},..., a_{t–L+ 1}). trellis diagram of code univalently connects the information sequence a_L, sequence of the encoder states w_L and the sequence of the output symbols b_L. To each branch b _t in channel there corresponds a signal, which can be presented a set of coordinates , where N – dimension of a signal space. In channel an additive noise operates. Then arriving on decoder input receiving signal sequence will be equal to X_L = S_L + n_L, where
S _L = (S ₀, S ₁,..., S_{L –1}) and n_L = (n ₀, n ₁, …, n_{L –1}), is N- dimensional vector of a noise.

Decoding consists in tracing through a code trellis of a way with maximum a posteriori probability. It is possible to specify the decoded way to one of kinds: by set of estimations of code branches S _L = (S ₀, S ₁, …, S_{L –1}) which making a way, by the sequence of estimations of the encoder states w _L = (w ₀, w ₁, …, w_{L –1}), by the sequence of estimations of information symbols on the encoder input A _L = (a ₀, …, a_{L –1}) which coincide with the first symbols of state estimations S = (s ₁, …, s_{t – ν +1}). The sequence X_L will be decoded with the minimum error probability if from all possible ways to choose estimation S _L for which a posteriori probability P (S _L / X _L) is maximum. Transmission of all variants of sequences a_L considers equiprobable. In this case decoding by criterion of a maximum a posteriori probability is equivalent to decoding by criterion of maximum of a probability when estimation S _L ensuring performance of condition P (S _L / X _L)= max gets out. In the channel without memory conditional probability P (S _L / X _L) is proportional to product of conditional densities of sum of signal and noise:

p (X_L/S_L) = .

In Gaussian channel by the white noise with an one-side power spectral density N ₀ each factor of this product looks like:

For maximum search we will take the logarithm:

By decoding choose sequence of signals S _L = (S ₁, …, S_{L –1}) and sequence of branches univalently connected with it S _L =(S ₀ S ₁ … S_{L -1}) which ensures a sum minimum

which is called as the metric of the decoded path (MP). The path metric containsthe metric of branches (MB)

In Gaussian channel the branch metric is proportional to quadrate Euclidean distances between a vector of received sum of a signal plus noise x _t and a vector of signal S _t corresponding to branch of a code a _t. In the discrete channel for an estimation of distances it is used Hamming metric. The periodic structure of trellis diagram essentially simplifies comparison and a choice of pathsaccording to decoding rules. The number of states on a trellis is limited, and two by random chosen enough long paths have, as a rule, the common state. Segments of the paths entering into such states it is necessary to compare and choose a path with the least metric. Such path is called as survived. According to Viterbi algorithm such c omparison and rejection of segments of path is made periodically, on each step of decoding.

On fig. (10.2, a, b, c, d) the development of decoding process of convolutional code (5, 7) is shown. On a decoder input symbol pairs from channel arrive (…11,10,00,11,01...) (decoding with hard decision). Figures on branches designate branch metrics, figures about states designate metric of states (MS). In an initial time it is supposed, that the decoder is in state 00 and initial metric of this state is MS (00) = 0. If the channel symbols are 11 so metrics of branches 00 and 11 going out this states will be МВ (00) = 2 and МВ (11) = 0. It is noted on the decoding first pitch. The similar picture takes place and on a following decoding step. The state metrics on this step are defined now as the sums of metrics of entering branches with previous state metrics: MS (00) = 2 + 1 = 3; MS (10) = 2 + 1 = 3; MS (01) = 0 + 0 = 0 and MS (11) = 0 + 2 = 2.

On it the development of trellis diagram for the given code comes to an end. The algorithm consists in a recurring of one basic step. On each of the subsequent diagrams figure 10.2, a, b, c, d this steps is represented explicitly. To the beginning of i -th step state metrics calculated at the previous stage are stored in memory of the decoder: МS ^{i –1}(00), МS ^{i –1} ( 10 ), МS ^{i –1} ( 01), МS ^{i –1} ( 11 ).

On the accepted channel symbols the evaluation of above branch metrics and shaping of four new states metrics is made: МS ⁱ (00), МS ⁱ (10), МS ⁱ (01) and МS ⁱ (11) by a following rule. To each new state lead two ways. For example, to state 00 conduct ways from the previous states 00 and 01. On i -th decoding step the decoder calculates metrics of paths as the sums of previous states metrics and entering branches metrics:

According to Viterbi algorithm on each decoding step ineach of trellis states the same type operations are made:

1) addition of metrics of the previous states with metrics of corresponding branches;

2) comparison of metrics of entering paths;

3) choice of paths with the least metrics which values are used as the metric of the states on the subsequent decoding step. If metrics of compared paths are identical, the choice of one of two path is made in a random way.

realisation complexity of Viterbi algorithm can be estimated by the amount of branches of the code trellis treated by the decoder at length of decoding L, taking into account complexity of each step of a trellis (see formula (9.6)). complexity of decoder Viterbi realisation can be estimated under the formula:

C = m ^{(n + k)}× L. (10.1)

On figure 10.3 the structure scheme of Viterbi decoder intended for work with the demodulator of signals QPSK is shown.

The decoder consists from analog/discrete converters (A/D C) in channels X and Y, the calculator of branch metrics and processor in which operations of addition, comparison and a choice are made, memory device of a survived paths, and majority element in which the path with the least metric gets out. The best value of a quantization levels depends on the ratio a signal/noise on input a/d C. By eight quantization levels of losses minimum is ensured at the ratio of a signal magnitude to the quantization step is equal to (4,5...5,5). More detailed description of assigning and work algorithms of the decoder Viterbi block diagram elements of are reduced in the manual [2, Section 3.8.2].