Using the Communications Toolbox (Communications Toolbox)

Communications Toolbox

Trellis Description of a Convolutional Encoder

A trellis description of a convolutional encoder shows how each possible input to the encoder influences both the output and the state transitions of the encoder. This section describes trellises, describes how to represent trellises in MATLAB, and gives an example of a MATLAB trellis.

The figure below depicts a trellis for the convolutional encoder from the previous section. The encoder has four states (numbered in binary from 00 to 11), a one-bit input, and a two-bit output. (The ratio of input bits to output bits makes this encoder a rate-1/2 encoder.) Each solid arrow shows how the encoder changes its state if the current input is zero, and each dashed arrow shows how the encoder changes its state if the current input is one. The octal numbers above each arrow indicate the current output of the encoder.

As an example of interpreting this trellis diagram, if the encoder is in the 10 state and receives an input of zero, then it outputs the code symbol 3 and changes to the 01 state. If it is in the 10 state and receives an input of one, then it outputs the code symbol 0 and changes to the 11 state.

Note that any polynomial description of a convolutional encoder is equivalent to some trellis description, although some trellises have no corresponding polynomial descriptions.

Specifying a Trellis in MATLAB

To specify a trellis in MATLAB, use a specific form of a MATLAB structure called a trellis structure. A trellis structure must have five fields, as in the table below.

Fields of a Trellis Structure for a Rate k/n Code
Field in Trellis Structure
Dimensions
Meaning

numInputSymbols
Scalar
Number of input symbols to the encoder: 2^k

numOutputsymbols
Scalar
Number of output symbols from the encoder: 2ⁿ

numStates
Scalar
Number of states in the encoder

nextStates
numStates-by-2^k matrix
Next states for all combinations of current state and current input

outputs
numStates-by-2^k matrix
Outputs (in decimal) for all combinations of current state and current input

**Fields of a Trellis Structure for a Rate k/n Code**
Field in Trellis Structure	Dimensions	Meaning
`numInputSymbols`	Scalar	Number of input symbols to the encoder: 2^k
`numOutputsymbols`	Scalar	Number of output symbols from the encoder: 2ⁿ
`numStates`	Scalar	Number of states in the encoder
`nextStates`	`numStates`-by-2^k matrix	Next states for all combinations of current state and current input
`outputs`	`numStates`-by-2^k matrix	Outputs (in decimal) for all combinations of current state and current input

Note While your trellis structure can have any name, its fields must have the exact names as in the table. Field names are case sensitive.

In the nextStates matrix, each entry is an integer between 0 and numStates-1. The element in the ith row and jth column denotes the next state when the starting state is i-1 and the input bits have decimal representation j-1. To convert the input bits to a decimal value, use the first input bit as the most significant bit (MSB). For example, the second column of the nextStates matrix stores the next states when the current set of input values is {0,...,0,1}. To learn how to assign numbers to states, see the reference page for istrellis.

In the outputs matrix, the element in the ith row and jth column denotes the encoder's output when the starting state is i-1 and the input bits have decimal representation j-1. To convert to decimal value, use the first output bit as the MSB.

How to Create a MATLAB Trellis Structure

Once you know what information you want to put into each field, you can create a trellis structure in any of these ways:

Define each of the five fields individually, using structurename.fieldname notation. For example, set the first field of a structure called s using the command below. Use additional commands to define the other fields.

s.numInputSymbols = 2;

The reference page for the istrellis function illustrates this approach.

Collect all field names and their values in a single struct command. For example:

s = struct('numInputSymbols',2,'numOutputSymbols',2,...

'numStates',2,'nextStates',[0 1;0 1],'outputs',[0 0;1 1]);

Start with a polynomial description of the encoder and use the poly2trellis function to convert it to a valid trellis structure. The polynomial description of a convolutional encoder is described in Polynomial Description of a Convolutional Encoder.

To check whether your structure is a valid trellis structure, use the istrellis function.

Example: A MATLAB Trellis Structure

Consider the trellis shown below.

To build a trellis structure that describes it, use the command below.

trellis = struct('numInputSymbols',2,'numOutputSymbols',4,...
'numStates',4,'nextStates',[0 2;0 2;1 3;1 3],...
'outputs',[0 3;1 2;3 0;2 1]);

The number of input symbols is 2 because the trellis diagram has two types of input path, the solid arrow and the dashed arrow. The number of output symbols is 4 because the numbers above the arrows can be either 0, 1, 2, or 3. The number of states is 4 because there are four bullets on the left side of the trellis diagram (equivalently, four on the right side). To compute the matrix of next states, create a matrix whose rows correspond to the four current states on the left side of the trellis, whose columns correspond to the inputs of 0 and 1, and whose elements give the next states at the end of the arrows on the right side of the trellis. To compute the matrix of outputs, create a matrix whose rows and columns are as in the next states matrix, but whose elements give the octal outputs shown above the arrows in the trellis.

Polynomial Description of a Convolutional Encoder Creating and Decoding Convolutional Codes