Store 
| Products & Services | Industries | Academia | Support | User Community | Company |
 |
Download Product Updates | | |  |
Get Pricing | | | |
Trial Software |
| Documentation → Communications Toolbox |
| Products & Services | Industries | Academia | Support | User Community | Company |
|
Download Product Updates | | | |
Get Pricing | | | |
Trial Software |
| Documentation → Communications Toolbox |
| Contents | Index |
| Learn more about Communications Toolbox |
| On this page… |
|---|
Convolutional Coding Features of the Toolbox Polynomial Description of a Convolutional Encoder Trellis Description of a Convolutional Encoder Creating and Decoding Convolutional Codes |
Convolutional coding is a special case of error-control coding.
Unlike a block coder, a convolutional coder is not a memoryless device. Even though a convolutional coder accepts a fixed number of message symbols and produces a fixed number of code symbols, its computations depend not only on the current set of input symbols but on some of the previous input symbols.
Communications Toolbox supports feedforward or feedback convolutional codes that can be described by a trellis structure or a set of generator polynomials. It uses the Viterbi algorithm to implement hard-decision and soft-decision decoding.
For background information about convolutional coding, see the works listed in Selected Bibliography for Convolutional Coding.
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:
Feedback connection polynomials (for feedback encoders only)
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.
If the encoder diagram has k inputs and n outputs, 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:
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.
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, 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, so 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 [2] in the section Selected Bibliography for Block Coding, especially that book's appendices.
If you are representing a feedback encoder, 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, 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. 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.
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.
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, and 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, 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, 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.
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: 2k |
| numOutputsymbols | Scalar | Number of output symbols from the encoder: 2n |
| numStates | Scalar | Number of states in the encoder |
| nextStates | numStates-by-2k matrix | Next states for all combinations of current state and current input |
| outputs | numStates-by-2k matrix | Outputs (in octal) 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.
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.
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.
The functions for encoding and decoding convolutional codes are convenc and vitdec. This section discusses using these functions to create and decode convolutional codes.
A simple way to use convenc to create a convolutional code is shown in the commands below.
t = poly2trellis([4 3],[4 5 17;7 4 2]); % Define trellis. code = convenc(ones(100,1),t); % Encode a string of ones.
The first command converts a polynomial description of a feedforward convolutional encoder to the corresponding trellis description. The second command encodes 100 bits, or 50 two-bit symbols. Because the code rate in this example is 2/3, the output vector code contains 150 bits (that is, 100 input bits times 3/2).
To check whether your trellis corresponds to a catastrophic convolutional code, use the iscatastrophic function.
To decode using hard decisions, use the vitdec function with the flag 'hard' and with binary input data. Because the output of convenc is binary, hard-decision decoding can use the output of convenc directly, without additional processing. This example extends the previous example and implements hard-decision decoding.
t = poly2trellis([4 3],[4 5 17;7 4 2]); % Define trellis. code = convenc(ones(100,1),t); % Encode a string of ones. tb = 2; % Traceback length for decoding decoded = vitdec(code,t,tb,'trunc','hard'); % Decode.
To decode using soft decisions, use the vitdec function with the flag 'soft'. Specify the number, nsdec, of soft-decision bits and use input data consisting of integers between 0 and 2^nsdec-1.
An input of 0 represents the most confident 0, while an input of 2^nsdec-1 represents the most confident 1. Other values represent less confident decisions. For example, the table below lists interpretations of values for 3-bit soft decisions.
Input Values for 3-bit Soft Decisions
| Input Value | Interpretation |
|---|---|
| 0 | Most confident 0 |
| 1 | Second most confident 0 |
| 2 | Third most confident 0 |
| 3 | Least confident 0 |
| 4 | Least confident 1 |
| 5 | Third most confident 1 |
| 6 | Second most confident 1 |
| 7 | Most confident 1 |
Example: Soft-Decision Decoding. The script below illustrates decoding with 3-bit soft decisions. First it creates a convolutional code with convenc and adds white Gaussian noise to the code with awgn. Then, to prepare for soft-decision decoding, the example uses quantiz to map the noisy data values to appropriate decision-value integers between 0 and 7. The second argument in quantiz is a partition vector that determines which data values map to 0, 1, 2, etc. The partition is chosen so that values near 0 map to 0, and values near 1 map to 7. (You can refine the partition to obtain better decoding performance if your application requires it.) Finally, the example decodes the code and computes the bit error rate. When comparing the decoded data with the original message, the example must take the decoding delay into account. The continuous operation mode of vitdec causes a delay equal to the traceback length, so msg(1) corresponds to decoded(tblen+1) rather than to decoded(1).
msg = randint(4000,1,2,139); % Random data t = poly2trellis(7,[171 133]); % Define trellis. code = convenc(msg,t); % Encode the data. ncode = awgn(code,6,'measured',244); % Add noise. % Quantize to prepare for soft-decision decoding. qcode = quantiz(ncode,[0.001,.1,.3,.5,.7,.9,.999]); tblen = 48; delay = tblen; % Traceback length decoded = vitdec(qcode,t,tblen,'cont','soft',3); % Decode. % Compute bit error rate. [number,ratio] = biterr(decoded(delay+1:end),msg(1:end-delay))
The output is below.
number =
5
ratio =
0.0013
This section contains more examples of convolutional coding:
The first example determines the correct trellis parameter for its encoder and then uses it to process a code. The decoding process uses hard decisions and the continuous operation mode. This operation mode causes a decoding delay, which the error rate computation takes into account.
The second example processes a punctured convolutional code. The decoding process uses the unquantized decision type.
The example below uses the rate 2/3 feedforward encoder depicted in this schematic. The accompanying description explains how to determine the trellis structure parameter from a schematic of the encoder and then how to perform coding using this encoder.
Determining Coding Parameters. The convenc and vitdec functions can implement this code if their parameters have the appropriate values.
The encoder's constraint length is a vector of length 2 because the encoder has two inputs. The elements of this vector indicate the number of bits stored in each shift register, including the current input bits. Counting memory spaces in each shift register in the diagram and adding one for the current inputs leads to a constraint length of [5 4].
To determine the code generator parameter as a 2-by-3 matrix of octal numbers, use the element in the ith row and jth column to indicate how the ith input contributes to the jth output. For example, to compute the element in the second row and third column, the leftmost and two rightmost elements in the second shift register of the diagram feed into the sum that forms the third output. Capture this information as the binary number 1011, which is equivalent to the octal number 13. The full value of the code generator matrix is [23 35 0; 0 5 13].
To use the constraint length and code generator parameters in the convenc and vitdec functions, use the poly2trellis function to convert those parameters into a trellis structure. The command to do this is below.
trel = poly2trellis([5 4],[23 35 0;0 5 13]); % Define trellis.
Using the Encoder. Below is a script that uses this encoder.
len = 1000; msg = randint(2*len,1); % Random binary message of 2-bit symbols trel = poly2trellis([5 4],[23 35 0;0 5 13]); % Trellis code = convenc(msg,trel); % Encode the message. ncode = rem(code + randerr(3*len,1,[0 1;.96 .04]),2); % Add noise. decoded = vitdec(ncode,trel,34,'cont','hard'); % Decode. [number,ratio] = biterr(decoded(68+1:end),msg(1:end-68));
convenc accepts a vector containing 2-bit symbols and produces a vector containing 3-bit symbols, while vitdec does the opposite. Also notice that biterr ignores the first 68 elements of decoded. That is, the decoding delay is 68, which is the number of bits per symbol (2) of the recovered message times the traceback depth value (34) in the vitdec function. The first 68 elements of decoded are 0s, while subsequent elements represent the decoded messages.
This example processes a punctured convolutional code. It begins by generating 30,000 random bits and encoding them using a rate-3/4 convolutional encoder with a puncture pattern of [1 1 1 0 0 1]. The resulting vector contains 40,000 bits, which are mapped to values of -1 and 1 for transmission. The punctured code, punctcode, passes through an additive white Gaussian noise channel. Then vitdec decodes the noisy vector using the 'unquant' decision type.
Finally, the example computes the bit error rate and the number of bit errors.
len = 30000; msg = randi([0 1], len, 1); % Random data
t = poly2trellis(7, [133 171]); % Define trellis.
punctcode = convenc(msg, t, [1 1 1 0 0 1]); % Length is (2*len)*2/3.
tcode = 1-2*punctcode; % Map "0" bit to 1 and "1" bit to -1
ncode = awgn(tcode, 3, 'measured'); % Add noise.
% Decode the punctured code
decoded = vitdec(ncode, t, 96, 'trunc', ...
'unquant', [1 1 1 0 0 1]); % Decode.
[numErrP, berP] = biterr(decoded, msg); % Bit error rate
% Erase the least reliable 100 symbols, then decode
[dummy idx] = sort(abs(ncode));
erasures = zeros(size(ncode)); erasures(idx(1:100)) = 1;
decoded = vitdec(ncode, t, 96, 'trunc', 'unquant', ...
[1 1 1 0 0 1], erasures); % Decode.
[numErrPE, berPE] = biterr(decoded, msg); % Bit error rate
fprintf('Number of errors with puncturing: %d\n', numErrP)
fprintf('Number of errors with puncturing and erasures: %d\n', numErrPE)[1] Clark, George C. Jr., and J. Bibb Cain, Error-Correction Coding for Digital Communications, New York, Plenum Press, 1981.
[2] Gitlin, Richard D., Jeremiah F. Hayes, and Stephen B. Weinstein, Data Communications Principles, New York, Plenum Press, 1992.
 | Block Coding | Cyclic Redundancy Check Coding |  |
Learn how to apply early verification to your development process through these technical resources.
How much time do you spend on testing to ensure implementation meets system-level requirements?
| © 1984-2009- The MathWorks, Inc. - Site Help - Patents - Trademarks - Privacy Policy - Preventing Piracy - RSS |
