Communications Toolbox

Polynomial Description of a Convolutional Encoder

A polynomial description of a convolutional encoder describes the connections among shift registers and modulo-2 adders. For example, the figure below depicts a feedforward convolutional encoder that has one input, two outputs, and two shift registers.

A polynomial description of a convolutional encoder has either two or three components, depending on whether the encoder is a feedforward or feedback type:

• Constraint lengths
• Generator polynomials
• Feedback connection polynomials (for feedback encoders only)

Constraint Lengths

The constraint lengths of the encoder form a vector whose length is the number of inputs in the encoder diagram. The elements of this vector indicate the number of bits stored in each shift register, including the current input bits.

In the figure above, the constraint length is three. It is a scalar because the encoder has one input stream, and its value is one plus the number of shift registers for that input.

Generator Polynomials

If the encoder diagram has k inputs and n outputs, then the code generator matrix is a k-by-n matrix. The element in the ith row and jth column indicates how the ith input contributes to the jth output.

For systematic bits of a systematic feedback encoder, match the entry in the code generator matrix with the corresponding element of the feedback connection vector. See Feedback Connection Polynomials below for details.

In other situations, you can determine the (i,j) entry in the matrix as follows:

1. Build a binary number representation by placing a 1 in each spot where a connection line from the shift register feeds into the adder, and a 0 elsewhere. The leftmost spot in the binary number represents the current input, while the rightmost spot represents the oldest input that still remains in the shift register.
2. Convert this binary representation into an octal representation by considering consecutive triplets of bits, starting from the rightmost bit. The rightmost bit in each triplet is the least significant. If the number of bits is not a multiple of three, then place zero bits at the left end as necessary. (For example, interpret 1101010 as 001 101 010 and convert it to 152.)

For example, the binary numbers corresponding to the upper and lower adders in the figure above are 110 and 111, respectively. These binary numbers are equivalent to the octal numbers 6 and 7, respectively. Thus the generator polynomial matrix is [6 7].

Note    You can perform the binary-to-octal conversion in MATLAB by using code like str2num(dec2base(bin2dec('110'),8)).

For a table of some good convolutional code generators, refer to [1] in the section Selected Bibliography for Block Coding, especially that book's appendices.

Feedback Connection Polynomials

If you are representing a feedback encoder, then you need a vector of feedback connection polynomials. The length of this vector is the number of inputs in the encoder diagram. The elements of this vector indicate the feedback connection for each input, using an octal format. First build a binary number representation as in step 1 above. Then convert the binary representation into an octal representation as in step 2 above.

If the encoder has a feedback configuration and is also systematic, then the code generator and feedback connection parameters corresponding to the systematic bits must have the same values.

For example, the diagram below shows a rate 1/2 systematic encoder with feedback.

This encoder has a constraint length of 5, a generator polynomial matrix of [37 33], and a feedback connection polynomial of 37.

The first generator polynomial matches the feedback connection polynomial because the first output corresponds to the systematic bits. The feedback polynomial is represented by the binary vector [1 1 1 1 1], corresponding to the upper row of binary digits in the diagram. These digits indicate connections from the outputs of the registers to the adder. Note that the initial 1 corresponds to the input bit. The octal representation of the binary number 11111 is 37.

The second generator polynomial is represented by the binary vector [1 1 0 1 1], corresponding to the lower row of binary digits in the diagram. The octal number corresponding to the binary number 11011 is 33.

Using the Polynomial Description in MATLAB

To use the polynomial description with the functions convenc and vitdec, first convert it into a trellis description using the poly2trellis function. For example, the command below computes the trellis description of the encoder pictured in the section Polynomial Description of a Convolutional Encoder.

• trellis = poly2trellis(3,[6 7]);
  

The MATLAB structure trellis is a suitable input argument for convenc and vitdec.

Convolutional Coding Features of the Toolbox

Trellis Description of a Convolutional Encoder