Store 
| Products & Services | Solutions | Academia | Support | User Community | Company |
 |
Download Product Updates | | |  |
Get Pricing | | | |
Trial Software |
| Documentation → Communications Blockset |
| Products & Services | Solutions | Academia | Support | User Community | Company |
|
Download Product Updates | | | |
Get Pricing | | | |
Trial Software |
| Documentation → Communications Blockset |
| Contents | Index |
| Learn more about Communications Blockset |
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.
Open the Error Detection and Correction library by double-clicking its icon in the main Communications Blockset library. Open the Convolutional sublibrary by double-clicking its icon in the Error Detection and Correction library.
Communications Blockset supports feedforward or feedback binary 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.
The blockset also includes an a posteriori probability decoder, which can be used for soft output decoding of convolutional codes.
To process convolutional codes, use the Convolutional Encoder, Viterbi Decoder, and/or APP Decoder blocks in the Convolutional sublibrary. If a mask parameter is required in both the encoder and the decoder, use the same value in both blocks.
The blocks in the Convolutional sublibrary assume that you use one of two different representations of a convolutional encoder:
If you design your encoder using a diagram with shift registers and modulo-2 adders, you can compute the code generator polynomial matrix and subsequently use the poly2trellis function (in Communications Toolbox) to generate the corresponding trellis structure mask parameter automatically. For an example, see Example: A Rate 2/3 Feedforward Encoder.
If you design your encoder using a trellis diagram, you can construct the trellis structure in MATLAB and use it as the mask parameter.
Details about these representations are in the sections Polynomial Description of a Convolutional Encoder and Trellis Description of a Convolutional Encoder in the Communications Toolbox User's Guide.
To use the polynomial description with the Convolutional Encoder, Viterbi Decoder, or APP Decoder blocks, use the utility function poly2trellis from Communications Toolbox. This function accepts a polynomial description and converts it into a trellis description. For example, the following command computes the trellis description of an encoder whose constraint length is 5 and whose generator polynomials are 35 and 31:
trellis = poly2trellis(5,[35 31]);
To use this encoder with one of the convolutional-coding blocks, simply place a poly2trellis command such as
poly2trellis(5,[35 31]);
in the Trellis structure parameter field.
This example uses the rate 2/3 feedforward convolutional encoder depicted in the following figure. The description explains how to determine the coding blocks' parameters from a schematic of a rate 2/3 feedforward encoder. This example also illustrates the use of the Error Rate Calculation block with a receive delay.
The Convolutional Encoder and Viterbi Decoder blocks can implement this code if their parameters have the appropriate values.
The encoder's constraint length is a vector of length 2 since 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, notice that 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 [27 33 0; 0 5 13].
To use the constraint length and code generator parameters in the Convolutional Encoder and Viterbi Decoder blocks, use the poly2trellis function to convert those parameters into a trellis structure.
The following model simulates this encoder.
To open the completed model, click here in the MATLAB Help browser. To build the model, gather and configure these blocks:
Bernoulli Binary Generator, in the Comm Sources library
Set Probability of a zero to .5.
Set Initial seed to any positive integer scalar, preferably the output of the randseed function.
Set Sample time to .5.
Check the Frame-based outputs check box.
Set Samples per frame to 2.
Set Trellis structure to poly2trellis([5 4],[23 35 0; 0 5 13]).
Binary Symmetric Channel, in the Channels library
Set Error probability to 0.02.
Set Initial seed to any positive integer scalar, preferably the output of the randseed function.
Clear the Output error vector check box.
Set Trellis structure to poly2trellis([5 4],[23 35 0; 0 5 13]).
Set Decision type to Hard Decision.
Error Rate Calculation, in the Comm Sinks library
Set Receive delay to 68.
Set Output data to Port.
Check the Stop simulation check box.
Set Target number of errors to 100.
Display, in the Simulink Sinks library
Drag the bottom edge of the icon to make the display big enough for three entries.
Connect the blocks as in the figure. From the model window's Simulation menu, select Configuration parameters. In the Configuration Parameters dialog box, set Stop time to inf.
The matrix size annotations appear on the connecting lines only if you select Signal Dimensions from the Port/Signal Displays submenu of the model's Format menu. The encoder accepts a 2-by-1 frame-based vector and produces a 3-by-1 frame-based vector, while the decoder does the opposite. The Samples per frame parameter in the Bernoulli Binary Generator block is 2 because the block must generate a message word of length 2.
The Receive delay parameter in the Error Rate Calculation block is 68, which is the vector length (2) of the recovered message times the Traceback depth value (34) in the Viterbi Decoder block. If you examine the transmitted and received signals as matrices in the MATLAB workspace, you see that the first 34 rows of the recovered message consist of zeros, while subsequent rows are the decoded messages. Thus the delay in the received signal is 34 vectors of length 2, or 68 samples.
Running the model produces display output consisting of three numbers: the error rate, the total number of errors, and the total number of comparisons that the Error Rate Calculation block makes during the simulation. (The first two numbers vary depending on your Initial seed values in the Bernoulli Binary Generator and Binary Symmetric Channel blocks.) The simulation stops after 100 errors occur, because Target number of errors is set to 100 in the Error Rate Calculation block. The error rate is much less than 0.02, the Error probability in the Binary Symmetric Channel block.
This section explains how to use the Convolutional Encoder block to implement a systematic encoder with feedback. A code is systematic if the actual message words appear as part of the codewords. The following diagram shows an example of a systematic encoder.
To implement this encoder, set the Trellis structure parameter in the Convolutional Encoder block to poly2trellis(5, [37 33], 37). This setting corresponds to
Constraint length: 5
Generator polynomial pair: [37 33]
Feedback polynomial: 37
The feedback polynomial is represented by the binary vector [1 1 1 1 1], corresponding to the upper row of binary digits. 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.
To implement a systematic code, set the first generator polynomial to be the same as the feedback polynomial in the Trellis structure parameter of the Convolutional Encoder block. In this example, both polynomials have the octal representation 37.
The second generator polynomial is represented by the binary vector [1 1 0 1 1], corresponding to the lower row of binary digits. The octal number corresponding to the binary number 11011 is 33.
For more information on setting the mask parameters for the Convolutional Encoder block, see Polynomial Description of a Convolutional Encoder in the Communications Toolbox documentation.
This example creates a rate 1/2 convolutional code. It uses a quantizer and the Viterbi Decoder block to perform soft-decision decoding. This description covers these topics:
The model is in the following figure. To open the model, click here in the MATLAB Help browser. The simulation creates a random binary message signal, encodes the message into a convolutional code, modulates the code using the binary phase shift keying (BPSK) technique, and adds white Gaussian noise to the modulated data in order to simulate a noisy channel. Then, the simulation prepares the received data for the decoding block and decodes. Finally, the simulation compares the decoded information with the original message signal in order to compute the bit error rate. The simulation ends after processing 100 bit errors or 107 message bits, whichever comes first.
The feedforward convolutional encoder in this example is depicted below.
The encoder's constraint length is a scalar since the encoder has one input. The value of the constraint length is the number of bits stored in the shift register, including the current input. There are six memory registers, and the current input is one bit. Thus the constraint length of the code is 7.
The code generator is a 1-by-2 matrix of octal numbers because the encoder has one input and two outputs. The first element in the matrix indicates which input values contribute to the first output, and the second element in the matrix indicates which input values contribute to the second output.
For example, the first output in the encoder diagram is the modulo-2 sum of the rightmost and the four leftmost elements in the diagram's array of input values. The seven-digit binary number 1111001 captures this information, and is equivalent to the octal number 171. The octal number 171 thus becomes the first entry of the code generator matrix. Here, each triplet of bits uses the leftmost bit as the most significant bit. The second output corresponds to the binary number 1011011, which is equivalent to the octal number 133. The code generator is therefore [171 133].
The Trellis structure parameter in the Convolutional Encoder block tells the block which code to use when processing data. In this case, the poly2trellis function, in Communications Toolbox, converts the constraint length and the pair of octal numbers into a valid trellis structure.
While the message data entering the Convolutional Encoder block is a scalar bit stream, the encoded data leaving the block is a stream of binary vectors of length 2.
The received data, that is, the output of the AWGN Channel block, consists of complex numbers that are close to -1 and 1. In order to reconstruct the original binary message, the receiver part of the model must decode the convolutional code. The Viterbi Decoder block in this model expects its input data to be integers between 0 and 7. The demodulator, a custom subsystem in this model, transforms the received data into a format that the Viterbi Decoder block can interpret properly. More specifically, the demodulator subsystem
Converts the received data signal to a real signal by removing its imaginary part. It is reasonable to assume that the imaginary part of the received data does not contain essential information, because the imaginary part of the transmitted data is zero (ignoring small roundoff errors) and because the channel noise is not very powerful.
Normalizes the received data by dividing by the standard deviation of the noise estimate and then multiplying by -1.
Quantizes the normalized data using three bits.
The combination of this mapping and the Viterbi Decoder block's decision mapping reverses the BPSK modulation that the BPSK Modulator Baseband block performs on the transmitting side of this model. To examine the demodulator subsystem in more detail, double-click the icon labeled Soft-Output BPSK Demodulator.
After the received data is properly mapped to length-2 vectors of 3-bit decision values, the Viterbi Decoder block decodes it. The block uses a soft-decision algorithm with 23 different input values because the Decision type parameter is Soft Decision and the Number of soft decision bits parameter is 3.
Soft-Decision Interpretation of Data. When the Decision type parameter is set to Soft Decision, the Viterbi Decoder block requires input values between 0 and 2b-1, where b is the Number of soft decision bits parameter. The block interprets 0 as the most confident decision that the codeword bit is a 0 and interprets 2b-1 as the most confident decision that the codeword bit is a 1. The values in between these extremes represent less confident decisions. The following table lists the interpretations of the eight possible input values for this example.
| Decision 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 |
Traceback and Decoding Delay. The Traceback depth parameter in the Viterbi Decoder block represents the length of the decoding delay. Typical values for a traceback depth are about five or six times the constraint length, which would be 35 or 42 in this example. However, some hardware implementations offer options of 48 and 96. This example chooses 48 because that is closer to the targets (35 and 42) than 96 is.
The Error Rate Calculation block's Receive delay parameter is nonzero because a given message bit and its corresponding recovered bit are separated in time by a nonzero amount of simulation time. The Receive delay parameter tells the block which elements of its input signals to compare when checking for errors.
In this case, the Receive delay value is equal to the Traceback depth value (49).
This section describes how to compare the bit error rate in this simulation with the bit error rate that would theoretically result from unquantized decoding. The process includes a few steps, described in these sections:
Computing Theoretical Bounds for the Bit Error Rate. To calculate theoretical bounds for the bit error rate Pb of the convolutional code in this model, you can use this estimate based on unquantized-decision decoding:
In this estimate, cd is the sum of bit errors for error events of distance d, and f is the free distance of the code. The quantity Pd is the pairwise error probability, given by
where R is the code rate of 1/2, and erfc is the MATLAB complementary error function, defined by
Values for the coefficients cd and the free distance f are in published articles such as [4]. The free distance for this code is f = 10.
The following commands calculate the values of Pb for Eb/N0 values in the range from 1 to 3.5, in increments of 0.5:
EbNoVec = [1:0.5:4.0];
R = 1/2;
% Errs is the vector of sums of bit errors for
% error events at distance d, for d from 10 to 29.
Errs = [36 0 211 0 1404 0 11633 0 77433 0 502690 0,...
3322763 0 21292910 0 134365911 0 843425871 0];
% P is the matrix of pairwise error probilities, for
% Eb/No values in EbNoVec and d from 10 to 29.
P = zeros(20,7); % Initialize.
for d = 10:29
P(d-9,:) = (1/2)*erfc(sqrt(d*R*10.^(EbNoVec/10)));
end
% Bounds is the vector of upper bounds for the bit error
% rate, for Eb/No values in EbNoVec.
Bounds = Errs*P;
Simulating Multiple Times to Collect Bit Error Rates. You can efficiently vary the simulation parameters by using the sim function to run the simulation from the MATLAB command line. For example, the following code calculates the bit error rate at bit energy-to-noise ratios ranging from 1 dB to 4 dB, in increments of 0.5 dB. It collects all bit error rates from these simulations in the matrix BERVec. It also plots the bit error rates in a figure window along with the theoretical bounds computed in the preceding code fragment.
Note First open the model by clicking here in the MATLAB Help browser. Then execute these commands, which might take a few minutes. |
% Plot theoretical bounds and set up figure.
figure;
semilogy(EbNoVec,Bounds,'bo',1,NaN,'r*');
xlabel('Eb/No (dB)'); ylabel('Bit Error Rate');
title('Bit Error Rate (BER)');
legend('Theoretical bound on BER','Actual BER');
axis([1 4 1e-5 1]);
hold on;
BERVec = [];
opts = simset('SrcWorkspace','Current',...
'DstWorkspace','Current');
% Make the noise level variable.
set_param('doc_softdecision/AWGN Channel',...
'EsNodB','EbNodB+10*log10(1/2)');
% Simulate multiple times.
for n = 1:length(EbNoVec)
EbNodB = EbNoVec(n);
sim('doc_softdecision',5000000,opts);
BERVec(n,:) = BER_Data;
semilogy(EbNoVec(n),BERVec(n,1),'r*'); % Plot point.
drawnow;
end
hold off;
Note The estimate for Pb assumes that the decoder uses unquantized data, that is, an infinitely fine quantization. By contrast, the simulation in this example uses 8-level (3-bit) quantization. Because of this quantization, the simulated bit error rate is not quite as low as the bound when the signal-to-noise ratio is high. |
The plot of bit error rate against signal-to-noise ratio follows. The locations of your actual BER points might vary because the simulation involves random numbers.
This example demonstrates Tailbiting encoding using feedback encoders. For feedback encoders, the ending state depends on the entire block of data. To accomplish tailbiting, you must calculate for a given information vector (of N bits), the initial state, that leads to the same ending state after the block of data is encoded.
This is achieved in two steps:
The first step is to determine the zero-state response for a given block of data. The encoder starts in the all-zeros state. The whole block of data is input and the output bits are ignored. After N bits, the encoder is in a state XN [zs]. From this state, we calculate the corresponding initial state X0 and initialize the encoder with X0.
The second step is the actual encoding. The encoder starts with the initial state X0, the data block is input and a valid codeword is output which conforms to the same state boundary condition.
Refer to [8] for a theoretical calculation of the initial state X0 from XN [zs] using state-space formulation. This is a one-time calculation which depends on the block length and in practice could be implemented as a look-up table. Here we determine this mapping table by simulating all possible entries for a chosen trellis and block length.
To open the completed model, click here in the MATLAB Help browser
function mapStValues = getMapping(blkLen, trellis)
% The function returns the mapping value for the given block
length and trellis to be used for determining the initial
state from the zero-state response.
% All possible combinations of the mappings
mapStValuesTab = perms(0:trellis.numStates-1);
opts = simset('SrcWorkspace', 'Current', 'DstWorkspace', 'Current');
% Loop over all the combinations of the mapping entries:
for i = 1:length(mapStValuesTab)
mapStValues = mapStValuesTab(i,:);
% Model parameterized for the Block length
sim('mtailbiting_wfeedback', [], opts);
% Check the boundary condition for each run
% if ending and starting states match, choose that mapping set
if unique(out)==0
return
end
endSelecting the returned mapStValues for the 'Table Data' parameter in the Lookup Table block will perform tailbiting encoding for the chosen block length and trellis.
[1] Benedetto, Sergio, and Guido Montorsi, "Performance of Continuous and Blockwise Decoded Turbo Codes," IEEE Communications Letters, Vol. 1, May 1997, pp.77–79.
[2] Benedetto, S., G. Montorsi, D. Divsalar, and F. Pollara, "A Soft-Input Soft-Output Maximum A Posterior (MAP) Module to Decode Parallel and Serial Concatenated Codes," JPL TDA Progress Report, Vol. 42-127, November 1996.
[3] Clark, George C., Jr., and J. Bibb Cain, Error-Correction Coding for Digital Communications, New York, Plenum Press, 1981.
[4] Frenger, P., P. Orten, and T. Ottosson, "Convolution Codes with Optimum Distance Spectrum," IEEE Communications Letters, Vol. 3, November 1999, pp. 317–319.
[5] Gitlin, Richard D., Jeremiah F. Hayes, and Stephen B. Weinstein, Data Communications Principles, New York, Plenum, 1992.
[6] Heller, Jerrold A., and Irwin Mark Jacobs, "Viterbi Decoding for Satellite and Space Communication," IEEE Transactions on Communication Technology, Vol. COM-19, October 1971, pp. 835–848.
[7] Viterbi, Andrew J., "An Intuitive Justification and a Simplified Implementation of the MAP Decoder for Convolutional Codes," IEEE Journal on Selected Areas in Communications, Vol. 16, February 1998, pp. 260–264.
[8] C. Weiss, C. Bettstetter, S. Riedel, "Code Construction and Decoding of Parallel Concatenated Tail-Biting Codes,"IEEE Transactions on Information Theory, Vol. 47, No. 1, Jan. 2001, pp. 366-386.
 | Block Coding | Cyclic Redundancy Check Coding |  |
Learn more about Simulink through this collection of videos, articles, technical literature and the Getting Started with Simulink Guide.
| © 1984-2009- The MathWorks, Inc. - Site Help - Patents - Trademarks - Privacy Policy - Preventing Piracy - RSS |
