Main principles

2.1. Definition and description of convolution codes. As is known, in the case of block codes the sequence of information symbols (in future bits) is divided on separate blocks which in future are encoded independent of each other. Thus, the coded sequence is the sequence of independent code words of equal length.

For convolution codes a principle is other. The coding process is continuous and symbols on the encoder output (so-called code symbols) are one semi-infinite code word.

Convolution codes (CC) are the special case of continuous codes. They got the name through its property. The sequence of code symbols on the encoder output is calculated as mathematical operation of digital convolution of information bits on the input with encoder pulse response.

The structure of convolution code encoder and process of coding (decoding) are set by the generator polynomials g ^{( i )}, where i = 1, 2, …, n; D is delay. As a rule, polynomials are written down briefly, three binary coefficients of polynomial designated as one octal number. For example:

g ⁽¹⁾ = 7 means g ⁽¹⁾ = 111, i.e. g ⁽¹⁾ = D ² + D + 1 or 1 + D + D ²;

g ⁽²⁾ = 21 means g ⁽²⁾ = 010101, i.e. g ⁽²⁾ = D ⁴ + D ² + 1 or 1 + D ² + D ⁴.

2.2 Main parameters of convolution codes. Code rate is determined as R _code = k / n, where k is the number of encoder inputs, n is number of encoder outputs. Code rate shows that on k input information bits encoder gives out n code symbols.

Constraint length n characterizes encoder memory and equals the number of memory cells which encoder contains.

Encoder pulse response is the response of CC encoder on one information bit as “1”, which passes through encoder from the i -th input to the j -th output, encoder has kn pulse responses.

Free distance of code d _f is the minimum Hamming distance between the sequence of zero code symbols and all other sequences of code symbols. Free distance d _f characterizes the correcting ability of CC, i.e. number of errors q _corr, which are corrected by CC on length of the accepted code symbols sequence N = (5–6)×n. Connection between d _f and q _corr is the same, as for code distance of block error-control code:

d _f ≥ 2 q _corr + 1. (1)

2.3. Convolution codes encoder. Convolution code encoder contains the clocked memory register for saving of certain number of information symbols and transformer of input information sequence to output code sequence. Block diagram of CC (7, 5) encoder (code rate R _code = 1/2) is shown on the figure 1. Encoder contains a shift register with the three memory cells D, modulo-two adder Å and multiplexer MX. Inputs of modulo-two adders connected with those cells of register, in which the coefficients of generator polynomials equal to unit.

Information bits а on the input of register. In every clock interval on the adders outputs code symbols b ⁽¹⁾ and b ⁽²⁾ appear, i.e. on one information bit there will be two code symbols on output.

For mathematical description of convolution encoding, calculation of digital convolution, a few methods is used: state diagram, tree graph and trellis diagram. The trellis diagram which is considered below is most evident.

2.4. Trellis diagram of CC. The trellis diagram of CC called the directed graph with structure of "cells" which repeat periodically. Every cell consists of columns with the identical number of nodes connected by graph branches (figure 2, a). Between procedure of the СС encoding and trellis diagram there is univocal correspondence which is prescribed by such rules:

- every node corresponds to the encoder internal state, as a rule, it is content of two last memory cells in shift register;

- every branch represents encoder transition from one state to other after new information symbol reception in encoder: upper branch correspond to 0, and lower to 1;

- when encoder passes from one state to other, on every branch links this states initial code symbols which appear on encoder output are written down;

- the sequence of branches which is determined by the sequence of information bits and identically gives the code symbols sequence proper to it is called a path on a trellis;

So, for CC (7, 5) encoder represented on a figure 1, a trellis will have four states (00, 10, 01 and 11) and it is shown on the figure 2. The evident rule of calculation of initial code symbols on branches showed on figure 3 for the encoder initial state 00 and information bits 0 and 1 on the input. The calculation of initial code symbols of other branches is similar as for other encoder states.

Using trellis diagram code free distance d _f is calculated as weight (quantity of units) of shortest nonzero path which begins and ends in zero state (on a figure 2 for CC (7, 5) it is the dotted path).

Example 1. For CC (7, 5) encoder represented on a figure 1, find the sequence of code symbols, if sequence of information bits a = 01101000. Accept that in the initial state a register contains zeros.

Solution. Coding sequence is given in table 1, on its base on figure 4 represented trellis diagram with coding path, under coding path understand the sequence of branches which passes during coding process.

Table 1 – Coding process of information bits sequence 01101000, CC (7, 5)

k	Information bit ak	Encoder contains	Encoder state in moment tk – 1	Encoder state in moment tk	Output code symbols in moment tk

2.5. Decoding of convolution codes. Typical decoding algorithm, based on the probabilistic characteristic of the received signals, is the Viterbi algorithm [9–12], that uses the structure of certain trellis diagram of CC.

On any k time interval the Viterbi algorithm provides decoding stages given below.

1) Calculation of distance between received symbols and possible symbols, which correspond to all branches of trellis, trellis branches are included in every state in the moment t_k. This distance is called the metric of branch.

2) Construction of decoder trellis diagram, which similar to encoder trellis diagram, on which represent all possible branches with their metrics. The number of branches and correspond path on a trellis increases at the increase of trellis cells number, which are in point (the decoding depth, which depends on the capacity of decoder memory and takes value less then 10 constraint lengths).

3) Collapsing of trellis diagram on every step of its construction. Collapsing of trellis diagram it is procedure of exclusion of one from two paths which are included in every decoder state, according to the rule: a path with a greater metrics is excluding, a path with a less metrics stays (if metrics are identical, any path is excluding). Metric of path (or metric of state of trellis М_ij, where ij is number of decoder state) represents total metric of branches which a concrete path in the moment t_k passes to the concrete state. Collapsing of trellis diagram is necessary for decreasing of decoder paths number and decreasing of memory capacity.

4) Finding of optimum path on trellis after ending of decoding and making decision about transmitted information bits. A path with the less metric is optimum is called as surviving path. Decoding is carrying out on a surviving path: if it passes on the upper trellis branch, information bit is "0", lower – "1".

On the Viterbi algorithm we will consider procedure of decoding on a concrete example for a binary symmetric channel, demodulator gives out the "hard" decision as the sequence of code symbols with errors .

Example 2. Decode using Viterbi algorithm, sequence of the received code symbols: = 00 11 00 01 00 10. Convolution code (7, 5). Take, that at the beginning of decoding the decoder register is in the zero state.

Note. The received sequence is the fragment of sequence of encoder code symbols from example 1.

Solution. Procedures of decoding 1) and 2) on the Viterbi algorithm, combine into one during construction of decoder trellis diagram, resulted on figure 5 for the time moments t ₀ – t ₄. The metric of branches on any moment k is calculated as Hemming distance between a pair of received code symbols and code symbols of trellis branches. The calculated distance (0, 1 or 2) is shown near every branch on the figure 5. From figure 5 it is visible that from the moment t ₂ the number of branches is equal to eight in every trellis cell, and the number of possible paths increases exponentially with the increase of decoding depth.

Procedure 3) collapsing of trellis diagram resulted on a figure 6 for the time moments t ₃ and t ₄.

Notes. 1. For moments t ₁ and t ₂ there no collapsing of trellis diagram, because in any node which are taken up, one branch enters only.

2. It is obvious, that in errors absence the metric of one path will be zero, because this path repeats the path of encoding.

On a figure 6, a for the moments t ₂ and t ₃ shown all branches and paths, and on a figure 6, b only with a less metric. As none from the metrics of paths (states) equals to zero, it means that in the received sequence of code symbols error is present. Making decision about a surviving path is impossible, as two paths (states) have identical metrics.

The process of decoding in a trellis must be continued. For moments t ₃ and t ₄ collapsing of trellis diagram is shown on a figure 6, d. Again in nodes in the moment t ₄ paths with less metric are chosen. For the node 11 there are two paths with the metric М ₁₁ = 3, one is chosen arbitrarily.

If to complete decoding on trellis, a path with the metric М ₀₁ = 1 is optimum, shown on a figure 6, d by bold dotted line, and the decoded sequence will be = 011010, which coincides with the sequence of information bits in example 1. Conclusion: the error is corrected.

2.6 Soft decoding. It is simple modification of the just expounded procedure. At the soft decoding samples from the output of the demodulator matched filter act on the input of decoder. On the first stage of decoding it is needed to replace the Hamming metric on the Euclid metric. All other stages of decoding do not change. So complication of decoder realization with the soft decision not strongly differs from complication of decoder realization with the hard decision. It is one of important advantages of Viterbi decoding algorithm.