Description methods of convolutional codes

Convolutional codes (CC) form a subclass of continuous codes. The name «convolutional code» occurs that the result of coding on encoder exit is formed as convolution of coded information sequence with pulse response of encoder. Encoder of CC contains one or several registers from delay elements and converter of information sequences into code sequences. coding process is made continuously. The scheme of simple encoder is shown on figure 9.1.

Information binary symbols a arrive on input of the register with k delay elements D. On exits of module-2 adders code symbols b ⁽¹⁾ and b ⁽²⁾ are formed. Inputs of adders are connected to certain inputs of encoder register elements. The switch K on a encoder exit establishes send sequence of code symbols to channel. During one input information symbol it is formed two output code symbols.

code rate is R _code = k/n, where k – number of the information symbols simultaneously arriving on inputs of encoder, and n – number of code symbols corresponding to them on encoder exits. code rate in this example is equal R _code = 1/2. coding with other speeds is possible. Convolutional encoder as a finite state machine with final number of states can be described by state diagram. It is considered to be state as symbol set on the inputs of register delay elements. For example, symbols (s ₁, s ₂) designate encoder state on figure 9.1. The state diagram represents the directed graph who describes all possible transitions of encoder from one state into another and also contains encoder output symbols of the which accompany these transitions.

example of the encoder state diagram is shown on figure 9.2. It contains four possible encoder states (s ₁ s ₂) = 00, 10, 11 and 01 and possible transitions.

Symbols about arrows designate symbols on a encoder output (b ⁽¹⁾ b ⁽²⁾) corresponding to the given transition. Continuous lines note the transitions made at receipt on encoder input of the information symbol 0 and dotted – by the receipt of a symbol 1. Originally the encoder is in state 00, and receipt on its input of information symbol a = 0 translates it also in state 00. Thus on an encoder output there will be symbols (b ⁽¹⁾ b ⁽²⁾) = 00. On diagram this transition is designated by loop "00" leaving a state 00 and again coming back in this state. Further, at symbol receipt a = 1 the encoder passes in state 10 thus on output there will be symbols b ⁽¹⁾ b ⁽²⁾ = 11. This transition is designated by dashed line from a state 00 into state 10. Further, receipt on an input of the coder of information symbols 0 or 1 is possible. Thus the coder passes into state 01 or 11, and symbols on output will be 10 or 01 accordingly. Process of the diagram forming comes to an end, when all possible transitions from each state in all others will be seen. The trellis diagram (trellis) is development of the state diagram in a time. On trellis the states are shown by knots. The states are connecting by lines. After each transition from one state into another there is a displacement on one step to the right. example of trellis diagram is shown on figure 9.3. trellis diagram gives evident representation of all allowed wayswhich are analogues of allowed code words of a block codes. On them the encoder can move ahead by encoding. A unique way through a trellis corresponds to each information sequence on a encoder input.

In particular by a dotted line the way on a trellis…11100001… is shown corresponding to input information sequence …1011… For description of encoder work the sequence of input and output symbols it is convenient to representing with use of delay operator D in the form of infinite series

a _{( i )}(D) = a _{( i )0} D ⁰ + a _{( i )1} D ¹ + a _{( i )2} D ² +...,

b ^{( j )}(D) = b ₀^{( j )} D ⁰ + b ₁^{( j )} D ¹ + b ₂^{( j )} D ² +...

Here indexes in brackets designate:

i – number of encoder input, 1 £ i £ k;

j – number of encoder output, 1 £ j £ n.

Indexes without brackets (0, 1, 2,...) designate discrete time moments.

For exposition of convolution coding it is used concept of the generator polynomial.

The convolution code will be completely set, if encoder scheme is known:

– An amount of encoder inputs k;

– An amount of encoder outputs n;

– Lengths of each registers K_i;

– Connections of adders with register cells are specified.

For codes with rate R = 1/ n connection of j -th adder (1 £ j £ n) with cells of shift register is described by the representationof generator polynomial:

g ^(j)(D) = g ₀^(j) + g ₁^(j) D + g ₂^(j) D ² +... + g _n^(j) D ⁿ. (9.1)

Here g_k ^(j) = 1 if connection of j- th adder with k- th register cell exists, and g_k ^(j) = 0 if such connection is absent.

coding process can be presented as multiplication of a generator polynomial on an input information sequence a _(i)(D):

. (9.2)

For example, the encoder on figure 9.1 is characterised by generator polynomials g ⁽¹⁾(D) = 1 + D + D ² and g ⁽²⁾(D) = 1 + D ² or, noting sequence of a factors g_k in the form of binary words, we receive g ⁽¹⁾ = (111) and g ⁽²⁾ = (101). For long codes it is used often the octal form. In this case generator polynomials will be presented so:

g ⁽¹⁾ = (7) and g ⁽²⁾ = (5), or G = (g ⁽¹⁾, g ⁽²⁾) = (7, 5).

coding process can be described also with using of generator matrixes (accordingly, check matrixes). It is possible to familiarise with this material under the manual [2, Section 3.4, p. 114] more in detail.