Classification of decoding algorithms

By the receiving for purpose of optimum solution the received sequence of symbols accepted from the channel it is necessary to compare with all possible transmitted sequences. As the number of possible sequences length N for binary code is equally to 2 ⁿ by the big sequence lengths the decoder becomes inadmissible complexity (exponential decoding complexity, see section 6.3), and optimum decoding practically difficultly realizing. However by big n substantial increasing of transmission fidelity as the noise averages on a long sequence is possible. Therefore the problem of decoding algorithmscomplexity decreasing is important. Two groups of decoding methods for convolution codes are known:

1. Algebraic decoding methods are based on the use of algebraic properties of code sequences. In some cases these methods lead to a simple realisations of codec. Such algorithms are not optimal, as used algebraic decoding procedures are intended for correction concrete (and not all) configurations of channel errors. Algebraic methods are identified with «element-by-element reception» of sequences which for codes with redundancy, as is known, yields the worst results, than «reception in a whole». Most simple of algebraic algorithms is thealgebraic decoding methods. This algorithm is so far from optimum and consequently is seldom used, first of all, in systems with a high information rate. More detailed description of threshold algorithm and its modification can be discovered in the manual [2, Section 3.6.3].

2. Probability decoding methods areconsiderably is nearer to optimal “reception in a whole” as in this case decoder operates with values which proportional to a posteriori probabilities, estimates and compares probabilities of various hypotheses and on this basis carries out decision about transmitted symbols.

Algebraic algorithms operate with limited alphabet of input data for which deriving on an exit of continuous channel it is necessary to fulfil quantization of received signal with noise. Processes of elaborating of signals in an exit of the demodulator for antipodal signals are shown on figure 10.1 where are presented:

a) – forms of antipodal signals in sampling time on input of decision device of demodulator;

b) – binary quantization by hard decision;

c) – octal quantization by soft decision.

In the simple case it is made quantization of each channel symbol in sample time on two levels (named in the literature as «a hard decision »). Thus hard decision is presented by one binary symbol. It is shown on figure 10.1, b. By hard decision number of quantization levels is L = 2. By a soft decision number of quantization levels is L > 2 (figure 10.1, c). By soft decision the quantized output describes magnitude of decoded signal plus noise more precisely that raises a noise immunity.

Two basic probability algorithms for decoding of convolution codes, and also their various modifications are known.

Sequential decoding algorithm ensures arbitrarily small error probability by nonzero messages transmission rate through the channel. By sequential decoding the search of way through code lattice, corresponding to the transmitted informational sequence is made. sequential decoding is used for decoding of long convolutionаl codes. The detailed description of sequential decoding algorithm has presented in the book [4, section 13.18]. Other variety of probability algorithms is the algorithm based on a principle of dynamic programming, and known as Viterbi algorithm.

Dynamic programming principle has been formulated in 1940 by R. Bellman. it has wide application in control theory. In 1970 the dynamic programming in form of decoding algorithm for convolutional codes has been applied by A. Viterbi to solving of telecommunication problems (Viterbi algorithm). Viterbi algorithm finds wide application and realizes search of maximum probable way through code trellis with rejection of a part of least probable variants of decoded paths. Viterbi algorithm is characterized by a constant of computing work, however complexity of decoder Viterbi grows, as by all full search algorithms under the exponential law from code length. ThereforeViterbi algorithm is used for decoding of short convolutional codes.