Block Codes

Binary Format (All Coding Methods)

You can structure messages and codewords as binary vector signals, where each vector represents a message word or a codeword. At a given time, the encoder receives an entire message word, encodes it, and outputs the entire codeword. The message and code signals operate over the same sample time.

This example illustrates the encoder receiving a four-bit message and producing a five-bit codeword at time 0. It repeats this process with a new message at time 1.

For the coding techniques, the message vector must have length K and the corresponding code vector has length N.

If the input to a block-coding block is a frame-based vector, it must be a column vector instead of a row vector.

To produce sample-based messages in the binary format, you can configure the Bernoulli Binary Generator block so that its Probability of a zero parameter is a vector whose length is that of the signal you want to create. To produce frame-based messages in the binary format, you can configure the same block so that its Probability of a zero parameter is a scalar and its Samples per frame parameter is the length of the signal you want to create.

Using Serial Signals

If you prefer to structure messages and codewords as scalar signals, where several samples jointly form a message word or codeword, you can use the Buffer and Unbuffer blocks. Buffering involves latency and multirate processing. If your model computes error rates, the initial delay in the coding-buffering combination influences the Receive delay parameter in the Error Rate Calculation block.

You can display the sample times of signals in your model. On the Debug tab, expand Information Overlays. In the Sample Time section, select Colors. Alternatively, you can attach Probe (Simulink) blocks to connector lines to help evaluate sample timing, buffering, and delays.

Integer Format (Reed-Solomon Only)

A message word for an [N,K] Reed-Solomon code consists of M×K bits, which you can interpret as K symbols from 0 to 2^M. The symbols are binary sequences of length M, corresponding to elements of the Galois field GF(2^M), in descending order of powers. The integer format for Reed-Solomon codes lets you structure messages and codewords as integer signals instead of binary signals. (The input must be a frame-based column vector.)

This figure illustrates the equivalence between binary and integer signals for a Reed-Solomon encoder. The case for the decoder is similar.

To produce sample-based messages in the integer format, you can configure the Random Integer Generator block so that M-ary number and Initial seed parameters are vectors of the desired length and all entries of the M-ary number vector are 2^M. To produce frame-based messages in the integer format, you can configure the same block so that its M-ary number and Initial seed parameters are scalars and its Samples per frame parameter is the length of the signal you want to create.

Error Correction Versus Error Detection for Linear Block Codes

You can use a linear block code to detect d_min – 1 errors or to correct $$t=\left[\frac{1}{2}(d_{\min }-1)\right]$$ errors.

If you compromise the error correction capability of a code, you can detect more than t errors. For example, a code with d_min = 7 can correct t = 3 errors or it can detect up to 4 errors and correct up to 2 errors.

Find BCH and RS Code Error-Correction Capability

The bchgenpoly and rsgenpoly functions can return an optional second output argument that indicates the error-correction capability of a BCH or Reed-Solomon code.

This command shows that a [31,16] BCH code can correct up to three errors in each codeword.

[g1,t1] = bchgenpoly(31,16);
t1

t1 = 
3

This command shows that a [31,16] RS code can correct up to seven errors in each codeword.

[g2,t2] = rsgenpoly(31,16);
t2

t2 = 
7

Find Hamming and Cyclic Code Parity-Check and Generator Matrices

The hammgen and cyclgen functions return the parity-check and generator matrix for Hamming and cyclic codes, respectively.

m=3;
[parmat,genmat] = hammgen(m) % Hamming

parmat = 3×7

     1     0     0     1     0     1     1
     0     1     0     1     1     1     0
     0     0     1     0     1     1     1

genmat = 4×7

     1     1     0     1     0     0     0
     0     1     1     0     1     0     0
     1     1     1     0     0     1     0
     1     0     1     0     0     0     1

[parmat,genmat] = cyclgen(7,cyclpoly(7,4)) % Cyclic

parmat = 3×7

     1     0     0     1     1     1     0
     0     1     0     0     1     1     1
     0     0     1     1     1     0     1

genmat = 4×7

     1     0     1     1     0     0     0
     1     1     1     0     1     0     0
     1     1     0     0     0     1     0
     0     1     1     0     0     0     1

Represent Words for Linear Block Codes

Communication Toolbox® functionality for cyclic, Hamming, and generic linear block coding offers you multiple ways to organize bits in messages or codewords. This example uses the encode function to create messages and codewords in these formats:

The examples use cyclic coding. Hamming and generic linear block codes use similar formats for messages and codes.

n = 6; % Codeword length
k = 4; % Message length

msg = [1 0 0 1 1 0 1 0 1 0 1 1]';
cw = encode(msg,n,k,'cyclic');

msg'

ans = 1×12

     1     0     0     1     1     0     1     0     1     0     1     1

cw'

ans = 1×18

     1     1     1     0     0     1     0     0     1     0     1     0     0     1     1     0     1     1

n = 6; % Codeword length
k = 4; % Message length

msg = [1 0 0 1; 1 0 1 0; 1 0 1 1];
cw = encode(msg,n,k,'cyclic');
msg

msg = 3×4

     1     0     0     1
     1     0     1     0
     1     0     1     1

cw

cw = 3×6

     1     1     1     0     0     1
     0     0     1     0     1     0
     0     1     1     0     1     1

n = 6; % Codeword length
k = 4; % Message length
msg = [9;5;13];

cw = encode(msg,n,k,'cyclic/decimal')

cw = 3×1

    39
    20
    54

Configure Parameters for Linear Block Codes

This subsection describes the items that you might need in order to process [n,k] cyclic, Hamming, and generic linear block codes. This table lists the items and the coding techniques for which they are most relevant.

Generator Matrix.  The process of encoding a message into an [n,k] linear block code is determined by a k-by-n generator matrix G. Specifically, the 1-by-k message vector v is encoded into the 1-by-n codeword vector vG. If G has the form [I_k P] or [P I_k], where P is some k-by-(n-k) matrix and I_k is the k-by-k identity matrix, G is said to be in standard form. Some authors, such as Clark and Cain [2], use the first standard form. Others authors, such as Lin and Costello [3], use the second. Most functions in Communications Toolbox assume that a generator matrix is in standard form when you use it as an input argument.

The Parity-Check Matrix section shows examples of generator matrices.

Parity-Check Matrix.  Decoding an [n,k] linear block code requires an (n–k)-by-n parity-check matrix H. It satisfies GH^tr = 0 (mod 2), where H^tr denotes the matrix transpose of H, G is the generator matrix of the code, and this zero matrix is k-by-(n–k). If G = [I_kP] then H = [–P^trI_n–k]. Most functions in this product assume that a parity-check matrix is in standard form when you use it as an input argument.

This table summarizes the standard forms of generator and parity-check matrices for an [n–k] binary linear block code.

I_k is the identity matrix of size k and the ' symbol indicates matrix transpose.

Create Parity-Check and Generator Matrices

In the commands below, parmat is a parity-check matrix and genmat is a generator matrix.

This code finds parity-check and generator matrices for an $\left[n,k\right]$ Hamming code, in which $\left[n,k\right]=\left[2^3-1,n-3\right]=\left[7,4\right]$, by using the hammgen function. genmat has the standard form $\left[P{I}_k\right]$.

[parmat,genmat] = hammgen(3)

parmat = 3×7

     1     0     0     1     0     1     1
     0     1     0     1     1     1     0
     0     0     1     0     1     1     1

genmat = 4×7

     1     1     0     1     0     0     0
     0     1     1     0     1     0     0
     1     1     1     0     0     1     0
     1     0     1     0     0     0     1

This code finds parity-check and generator matrices for a [7,3] cyclic code by using the cyclpoly and cyclgen functions.

genpoly = cyclpoly(7,3); 
[parmat,genmat] = cyclgen(7,genpoly)

parmat = 4×7

     1     0     0     0     1     1     0
     0     1     0     0     0     1     1
     0     0     1     0     1     1     1
     0     0     0     1     1     0     1

genmat = 3×7

     1     0     1     1     1     0     0
     1     1     1     0     0     1     0
     0     1     1     1     0     0     1

This code converts a generator matrix for a [5,3] linear block code into the corresponding parity-check matrix by using the gen2par function. The gen2par function can also convert a parity-check matrix into a generator matrix.

genmat = [1 0 0 1 0; 0 1 0 1 1; 0 0 1 0 1];
parmat = gen2par(genmat)

parmat = 2×5

     1     1     0     1     0
     0     1     1     0     1

Generator Polynomial for Cyclic Coding

Cyclic codes have algebraic properties that allow a polynomial to determine the coding process completely. This so-called generator polynomial is a degree-(n–k) divisor of the polynomial $x^n\text{–}1$. Van Lint [5] explains how a generator polynomial determines a cyclic code.

The cyclpoly function produces generator polynomials for cyclic codes that represent the generator polynomial using a row vector containing the polynomial coefficients in order of ascending powers of the variable. For example, this command finds that one valid generator polynomial for a [7,3] cyclic code is $1+x^2+x^3+x^4$.

genpoly = cyclpoly(7,3)

genpoly = 1×5

     1     0     1     1     1

Use Decoding Table in MATLAB

A decoding table tells a decoder how to correct errors that have corrupted the code during transmission. Hamming codes can correct any single-symbol error in any codeword. Other codes can correct or partially correct errors that corrupt more than one symbol in a codeword.

The Communications toolbox represents a decoding table as a matrix with n columns and $2^{n-k}$ rows. Each row gives a correction vector for one received codeword vector. A Hamming decoding table has n+1 rows. The syndtable function generates a decoding table for a given parity-check matrix.

This example uses a Hamming decoding table to correct an error in a received message. The hammgen function produces the parity-check matrix and the syndtable function produces the decoding table. To determine the syndrome, multiply the transpose of the parity-check matrix by the received codeword. The decoding table helps determine the correction vector. The corrected codeword is the sum (modulo 2) of the correction vector and the received codeword.

Set parameters for a [7,4] Hamming code.

m = 3; 
n = 2^m-1; 
k = n-m;

Produce a parity-check matrix and decoding table.

parmat = hammgen(m);    
trt = syndtable(parmat);

Specify a vector of received data.

recd = [1 0 0 1 1 1 1]

recd = 1×7

     1     0     0     1     1     1     1

Calculate the syndrome and then display the decimal and binary values for the syndrome.

syndrome = rem(recd * parmat',2);
syndrome_int = bit2int(syndrome',m); % Convert to decimal.
disp(['Syndrome = ',num2str(syndrome_int), ...
      ' (decimal), ',num2str(syndrome),' (binary)'])

Syndrome = 3 (decimal), 0  1  1 (binary)

Determine the correction vector by using the decoding table and syndrome, and then compute the corrected codeword by using the correction vector.

corrvect = trt(1+syndrome_int,:)

corrvect = 1×7

     0     0     0     0     1     0     0

correctedcode = rem(corrvect+recd,2)

correctedcode = 1×7

     1     0     0     1     0     1     1

Create and Decode Linear Block Codes

The functions for encoding and decoding cyclic, Hamming, and generic linear block codes are encode and decode. This section discusses how to use these functions to create and decode generic linear block codes, cyclic codes, and Hamming codes.

Generic Linear Block Codes.  Encoding a message using a generic linear block code requires a generator matrix. If you have defined variables msg, n, k, and genmat, either of the commands

code = encode(msg,n,k,'linear',genmat);
code = encode(msg,n,k,'linear/decimal',genmat);

encodes the information in msg using the [n,k] code that the generator matrix genmat determines. The /decimal option, suitable when 2^n and 2^k are not very large, indicates that msg contains nonnegative decimal integers rather than their binary representations. See Represent Words for Linear Block Codes or the reference page for encode for a description of the formats of msg and code.

Decoding the code requires the generator matrix and possibly a decoding table. If you have defined variables code, n, k, genmat, and possibly also trt, then the commands

newmsg = decode(code,n,k,'linear',genmat);
newmsg = decode(code,n,k,'linear/decimal',genmat);
newmsg = decode(code,n,k,'linear',genmat,trt);
newmsg = decode(code,n,k,'linear/decimal',genmat,trt);

decode the information in code, using the [n,k] code that the generator matrix genmat determines. decode also corrects errors according to instructions in the decoding table that trt represents.

Example: Generic Linear Block Coding

The example below encodes a message, artificially adds some noise, decodes the noisy code, and keeps track of errors that the decoder detects along the way. Because the decoding table contains only zeros, the decoder does not correct any errors.

n = 4; k = 2;
genmat = [[1 1; 1 0], eye(2)]; % Generator matrix
msg = [0 1; 0 0; 1 0]; % Three messages, two bits each
% Create three codewords, four bits each.
code = encode(msg,n,k,'linear',genmat);
noisycode = rem(code + randerr(3,4,[0 1;.7 .3]),2); % Add noise.
trt = zeros(2^(n-k),n);  % No correction of errors
% Decode, keeping track of all detected errors.
[newmsg,err] = decode(noisycode,n,k,'linear',genmat,trt);
err_words = find(err~=0) % Find out which words had errors.

The output indicates that errors occurred in the first and second words. Your results might vary because this example uses random numbers as errors.

err_words =

     1
     2

Cyclic Codes.  A cyclic code is a linear block code with the property that cyclic shifts of a codeword (expressed as a series of bits) are also codewords. An alternative characterization of cyclic codes is based on its generator polynomial, as mentioned in Generator Polynomial for Cyclic Coding and discussed in [5].

Encoding a message using a cyclic code requires a generator polynomial. If you have defined variables msg, n, k, and genpoly, then either of the commands

code = encode(msg,n,k,'cyclic',genpoly);
code = encode(msg,n,k,'cyclic/decimal',genpoly);

encodes the information in msg using the [n,k] code determined by the generator polynomial genpoly. genpoly is an optional argument for encode. The default generator polynomial is cyclpoly(n,k). The /decimal option, suitable when 2^n and 2^k are not very large, indicates that msg contains nonnegative decimal integers rather than their binary representations. See Represent Words for Linear Block Codes or the reference page for encode for a description of the formats of msg and code.

Decoding the code requires the generator polynomial and possibly a decoding table. If you have defined variables code, n, k, genpoly, and trt, then the commands

newmsg = decode(code,n,k,'cyclic',genpoly);
newmsg = decode(code,n,k,'cyclic/decimal',genpoly);
newmsg = decode(code,n,k,'cyclic',genpoly,trt);
newmsg = decode(code,n,k,'cyclic/decimal',genpoly,trt);

decode the information in code, using the [n,k] code that the generator matrix genmat determines. decode also corrects errors according to instructions in the decoding table that trt represents. genpoly is an optional argument in the first two syntaxes above. The default generator polynomial is cyclpoly(n,k).

Example

You can modify the example in Generic Linear Block Codes so that it uses the cyclic coding technique, instead of the linear block code with the generator matrix genmat. Make the changes listed below:

Another example of encoding and decoding a cyclic code is on the reference page for encode.

Hamming Codes.  The reference pages for encode and decode contain examples of encoding and decoding Hamming codes. Also, the Use Decoding Table in MATLAB section illustrates error correction in a Hamming code.

Represent Words for BCH Codes

A message for an [N,K] BCH code must be a K-column binary Galois field array. The code that corresponds to that message is an N-column binary Galois field array. Each row of these Galois field arrays represents one word.

This example illustrates the representation of message and code words for a [15, 11] BCH code.

msg = [1 0 0 1 0; 1 0 1 1 1]; % Messages in a Galois array
bchenc = comm.BCHEncoder;
c1 = bchenc(msg(1,:)');
c2 = bchenc(msg(2,:)');

Concatenate and transpose the results to conveniently display the encoded output.

c = [c1 c2]'

c = 2×15

     1     0     0     1     0     0     0     1     1     1     1     0     1     0     1
     1     0     1     1     1     0     0     0     0     1     0     1     0     0     1

Parameters for BCH Codes

BCH codes use special values of n and k:

Create and Decode BCH Codes

The BCH Encoder and BCH Decoder System objects create and decode BCH codes, using the data described in Represent Words for BCH Codes and Parameters for BCH Codes.

Parity Symbol Positioning for BCH Codes

The convention used in Communications Toolbox appends parity symbols to BCH codes. This example encodes and decodes a [15,5] BCH code with parity symbols appended. It also shows you how to convert encoded data with appended parity symbols to encoded data with prepended parity symbols.

Define the codeword and message lengths, and then generate four random binary message frames in a column vector.

n = 15;                   % Codeword length
k = 5;                    % Message length
Nmsg = 4;                 % Number of frames
msg = randi([0 1],4*k,1); % Random binary messages

bchenc = comm.BCHEncoder(n,k);
bchdec = comm.BCHDecoder(n,k);
c1 = bchenc(msg);
d1 = bchdec(c1);

chk = isequal(d1,msg) 

chk = logical
   1

c11 = reshape(c1,n,[]);
c12 = circshift(c11,n-k);
c1_prepend = c12(:);

c21 = reshape(c1_prepend,n,[]);
c22 = circshift(c21,k);
c1_append = c22(:);

d1_append = bchdec(c1_append);
chk = isequal(msg,d1_append)

chk = logical
   1

Detect and Correct Errors in BCH Code Using MATLAB

This example shows the decoding results for a corrupted [15,5] BCH code. The example encodes data, introduces errors in each codeword, and attempts to decode the noisy code.

Define parameters for a [15,5] BCH code and four random K-symbol message words. Create a [15,5] BCH generator polynomial and output the error correction capability of a [15,5] BCH code as t.

N = 15;                       % Codeword length
K = 5;                        % Message length
nw = 4;                       % Number of words to process
msgw = randi([0 1], nw*K, 1); % Random k-symbol messages
[gp,t] = bchgenpoly(N,K);     % t is error-correction capability
t

t = 
3

Create [15,5] BCH encoder and decoder System objects.

bchenc = comm.BCHEncoder(N,K, ...
    GeneratorPolynomialSource='Property', ...
    GeneratorPolynomial=gp);
bchdec = comm.BCHDecoder(N,K, ...
    GeneratorPolynomialSource='Property', ...
    GeneratorPolynomial=gp);

Encode the message data.

cw = bchenc(msgw);

Generate random noise that inserts t errors per codeword. Notice that the array of noise values contains binary values, and that the adding noise to the code (cw + noise) takes place in the Galois field GF(2) because cw is a Galois field array in GF(2).

noise = randerr(nw,N,t);
noisy = noise';
noisy = noisy(:);

Add the noise vector to the binary code by using the mod function. Decode the noisy data and output the number of errors corrected in each codeword. The values in the vector nerrs indicate that the decoder corrected t errors in each codeword. Check to confirm the decoding working correctly, by using the isequal function. The nonzero value returned indicates that the decoder was able to correct the corrupted codewords and recover the original message.

cwnoisy = mod(cw + noisy,2);
[dcw, nerrs] = bchdec(cwnoisy);
nerrs

nerrs = 4×1

     3
     3
     3
     3

chk2 = isequal(dcw,msgw)

chk2 = logical
   1

Each BCH code has a finite error-correction capability. To learn more about how the comm.BCHDecoder System object™ behaves when the noise is excessive and causes more errors than the code is capable of correcting, see the analogous discussion for Reed-Solomon codes in Detect and Correct Errors in Reed-Solomon Code Using MATLAB.

Algorithms for BCH and RS Errors-only Decoding

Overview.  The errors-only decoding algorithm used for BCH and RS codes can be described by the following steps (sections 5.3.2, 5.4, and 5.6 in [2]).

Further description of several of the steps is given in the following sections.

Syndrome Calculation.  For narrow-sense codes, the 2t terms of $$S(z)$$ are calculated by evaluating the received codeword at successive powers of α (the field’s primitive element) over the range [0, (2t–1)]. In other words, if you assume one-based indexing of codewords $$C(z)$$ and the syndrome polynomial $$S(z)$$, and that codewords are of the form $$[c_1{c}_1\mathrm{...}{c}_N]$$, then each term $$S_i$$ of $$S(z)$$ is given as

Error Locator Polynomial Calculation.  The error locator polynomial, Λ(z), is found using the Berlekamp algorithm. This diagram shows an iterative procedure to find Λ(z) by using the Berlekamp algorithm.

For a detailed description of the error locator polynomial calculation algorithm, see [2].

Error Evaluator Polynomial Calculation.  The error evaluator polynomial, $$\Omega \left(z\right)$$, is simply the convolution of Λ(z) and $$S(z)$$.

Create Hamming Code in Binary Format Using Simulink

This example shows how to model a simple encoder and decoder using appropriate vector lengths for the code and message.

Reduce the Error Rate Using a Hamming Code

This section describes how to reduce the error rate by adding an error-correcting code. This figure shows a model that uses Hamming coding.

Building the Hamming Code Model

Build the Hamming code model and save the model as my_hamming in the folder where you keep your work files by following these steps:

Using the Hamming Encoder and Decoder Blocks

The Hamming Encoder block encodes the data before it is sent through the channel. The default code is the [7,4] Hamming code, which encodes message words of length 4 into codewords of length 7. As a result, the block converts frames of size 4 into frames of size 7. The code can correct one error in each transmitted codeword.

For an [n,k] code, the input to the Hamming Encoder block must consist of vectors of size k. In this example, k = 4.

The Hamming Decoder block decodes the data after it is sent through the channel. If at most one error is created in a codeword by the channel, the block decodes the word correctly. However, if more than one error occurs, the Hamming Decoder block might decode incorrectly.

To learn more about block coding features, see Block Codes.

Setting Parameters in the Hamming Code Model

Double-click the Bernoulli Binary Generator block and make the following changes to the parameter settings in the block's dialog box, as shown in the following figure:

Labeling the Display Block

You can change the label that appears below a block to make it more informative. For example, to change the label below the Display block to 'Error Rate Display', first select the label with the mouse. This causes a box to appear around the text. Enter the changes to the text in the box.

Running the Hamming Code Model

To run the model, select Simulation > Run. The model terminates after 100 errors occur. The error rate, displayed in the top window of the Display block, is approximately .001. You get slightly different results if you change the Initial seed parameters in the model or run a simulation for a different length of time.

You expect an error rate of approximately .001 for the following reason: The probability of two or more errors occurring in a codeword of length 7 is

If the codewords with two or more errors are decoded randomly, you expect about half the bits in the decoded message words to be incorrect. This indicates that .001 is a reasonable value for the bit error rate.

To obtain a lower error rate for the same probability of error, try using a Hamming code with larger parameters. To do this, change the parameters Codeword length and Message length in the Hamming Encoder and Hamming Decoder block dialog boxes. You also have to make the appropriate changes to the parameters of the Bernoulli Binary Generator block and the Binary Symmetric Channel block.

Displaying Frame Sizes

You can display the sizes of data frames in different parts in your model. On the Debug tab, expand Information Overlays. In the Signals section, select Signal Dimensions. The line leading out of the Bernoulli Binary Generator block is labeled [4x1], indicating that its output consists of column vectors of size 4. Because the Hamming Encoder block uses a [7,4] code, it converts frames of size 4 into frames of size 7, so its output is labeled [7x1].

Adding a Scope to the Model

To display the channel errors produced by the Binary Symmetric Channel block, add a Scope block to the model. This is a good way to see whether your model is functioning correctly. The example shown in the following figure shows where to insert the Scope block into the model.

To build this model from the one shown in the figure Reduce the Error Rate Using a Hamming Code, follow these steps:

Setting Parameters in the Expanded Model

Make the following changes to the parameters for the blocks you added to the model.

Observing Channel Errors with the Scope

When you run the model, the scope displays the error data. At the end of each 5000 time steps, the scope appears as shown this figure. The scope then clears the displayed data and displays the next 5000 data points.

The upper scope shows the channel errors generated by the Binary Symmetric Channel block. The lower scope shows errors that are not corrected by channel coding.

Click the Stop button on the toolbar at the top of the model window to stop the scope.

You can see individual errors by zooming in on the scope. First click the middle magnifying glass button at the top left of the Scope window. Then click one of the lines in the lower scope. This zooms in horizontally on the line. Continue clicking the lines in the lower scope until the horizontal scale is fine enough to detect individual errors. A typical example of what you might see is shown in the figure below.

The wider rectangular pulse in the middle of the upper scope represents two 1s. These two errors, which occur in a single codeword, are not corrected. This accounts for the uncorrected errors in the lower scope. The narrower rectangular pulse to the right of the upper scope represents a single error, which is corrected.

When you are done observing the errors, select Simulation > Stop.

Export Data to MATLAB explains how to send the error data to the MATLAB workspace for more detailed analysis.

Represent Words for Reed-Solomon Codes

This toolbox supports Reed-Solomon codes that use m-bit symbols instead of bits. A message for an [n,k] Reed-Solomon code must be a k-column Galois field array in the field GF(2^m). Each array entry must be an integer between 0 and 2^m-1. The code corresponding to that message is an n-column Galois field array in GF(2^m). The codeword length n must be between 3 and 2^m-1.

The example below illustrates how to represent words for a [7,3] Reed-Solomon code.

n = 7; k = 3; % Codeword length and message length
m = 3; % Number of bits in each symbol
msg = [1 6 4; 0 4 3]; % Message is a Galois array.
obj = comm.RSEncoder(n, k);
c1 = step(obj, msg(1,:)');
c2 = step(obj, msg(2,:)');
c = [c1 c2].'

The output is

C =

     1     6     4     4     3     6     3
     0     4     3     3     7     4     7

Parameters for Reed-Solomon Codes

This section describes several integers related to Reed-Solomon codes and discusses how to find generator polynomials.

Allowable Values of Integer Parameters.  The table below summarizes the meanings and allowable values of some positive integer quantities related to Reed-Solomon codes as supported in this toolbox. The quantities n and k are input parameters for Reed-Solomon functions in this toolbox.

Generator Polynomial.  The rsgenpoly function produces generator polynomials for Reed-Solomon codes. rsgenpoly represents a generator polynomial using a Galois row vector that lists the polynomial's coefficients in order of descending powers of the variable. If each symbol has m bits, the Galois row vector is in the field GF(2^m). For example, the command

r = rsgenpoly(15,13)

r = GF(2^4) array. Primitive polynomial = D^4+D+1 (19 decimal)

Array elements =

     1     6     8

finds that one generator polynomial for a [15,13] Reed-Solomon code is X² + (A² + A)X + (A³), where A is a root of the default primitive polynomial for GF(16).

Algebraic Expression for Generator Polynomials

The generator polynomials that rsgenpoly produces have the form (X - A^b)(X - A^b+1)...(X - A^b+2t-1), where b is an integer, A is a root of the primitive polynomial for the Galois field, and t is (n-k)/2. The default value of b is 1. The output from rsgenpoly is the result of multiplying the factors and collecting like powers of X. The example below checks this formula for the case of a [15,13] Reed-Solomon code, using b = 1.

n = 15;
a = gf(2,log2(n+1)); % Root of primitive polynomial
f1 = [1 a]; f2 = [1 a^2]; % Factors that form generator polynomial
f = conv(f1,f2) % Generator polynomial, same as r above.

Create and Decode Reed-Solomon Codes

The comm.RSEncoder and comm.RSDecoder System objects create and decode Reed-Solomon codes, using the data described in Represent Words for Reed-Solomon Codes and Parameters for Reed-Solomon Codes. This section illustrates how to use the System objects.

Reed-Solomon Coding Syntaxes in MATLAB

This example shows multiple ways to encode and decode data using a [15,13] Reed-Solomon code. The example shows that you can:

This example also shows that corresponding syntaxes of the comm.RSEncoder and comm.RSDecoder System objects use the same input arguments, except for the first input argument.

m = 4;                      % Number of bits in each symbol
n = 2^m-1;                  % Codeword length
k = 13;                     % Message length
msg = randi([0 m-1],4*k,1); % Four random integer messages

The simplest syntax for encoding and decoding uses the default settings System object™ properties.

rsEnc = comm.RSEncoder(n,k);
rsDec = comm.RSDecoder(n,k);
c1 = rsEnc(msg);
d1 = rsDec(c1);

release(rsEnc)
release(rsDec)
rsEnc.GeneratorPolynomialSource = 'Property';
rsDec.GeneratorPolynomialSource = 'Property';
rsEnc.GeneratorPolynomial = rsgenpoly(n,k,19,2);
rsDec.GeneratorPolynomial = rsgenpoly(n,k,19,2);
c2 = rsEnc(msg);
d2 = rsDec(c2);

release(rsEnc)
release(rsDec)
rsEnc.PrimitivePolynomialSource = 'Property';
rsDec.PrimitivePolynomialSource = 'Property';
rsEnc.GeneratorPolynomialSource = 'Auto';
rsDec.GeneratorPolynomialSource = 'Auto';
rsEnc.PrimitivePolynomial = [1 1 0 0 1];
rsDec.PrimitivePolynomial = [1 1 0 0 1];
c3 = rsEnc(msg);
d3 = rsDec(c3);

chk = isequal(d1,msg) & isequal(d2,msg) & isequal(d3,msg)

chk = logical
   1

c31 = reshape(c3,n,[]);
c32 = circshift(c31,n-k);
c3_prepend = c32(:); % RS encoded data with prepended parity symbols

c34 = reshape(c3_prepend,n,[]);
c35 = circshift(c34,k);
c3_append = c35(:); % RS encoded data with appended parity symbols

d3_append = rsDec(c3_append);
chk = isequal(msg,d3_append)

chk = logical
   1

Detect and Correct Errors in Reed-Solomon Code Using MATLAB

This example shows the decoding results for a corrupted code. The example encodes some data, introduces errors in each codeword, and then attempts to decode the noisy code by using the comm.RSDecoder System object™.

m  = 3;                     % Number of bits per symbol
n = 2^m-1;                  % Codeword length
k = 3;                      % Message length
t = (n-k)/2                 % Error-correction capability of the code

t = 
2

nw = 4;                     % Number of words to process
rsEnc = comm.RSEncoder(n,k);
rsDec = comm.RSDecoder(n,k);

msgw = randi([0 n],nw*k,1); 
c = rsEnc(msgw);            % Encode the data.

s = rng;
rng(123);
noise = (1+randi([0 n-1],nw,n)).*randerr(nw,n,t);
noisy = noise';
noisy = noisy(:);
cnoisy = gf(c,m) + noisy;
[dc nerrs] = rsDec(cnoisy.x);

isequal(dc,msgw) % Confirm decoding worked correctly

ans = logical
   1

nerrs            % Check number of errors corrected per codeword

nerrs = 4×1 int32 column vector

   2
   2
   2
   2

noise2 = (1+randi([0 n-1],nw,n)).*randerr(nw,n,t+1); % t+1 errors/row
noisy2 = noise2';
noisy2 = noisy2(:);
cnoisy2 = gf(c,m) + noisy2;
[dc2 nerrs2] = rsDec(cnoisy2.x);

isequal(dc2,msgw) % Check whether decoding worked correctly

ans = logical
   0

nerrs2            % Check number of errors corrected per codeword

nerrs2 = 4×1 int32 column vector

   -1
   -1
   -1
   -1

rng(s)

Create Shortened Reed-Solomon Codes.  Every Reed-Solomon encoder uses a codeword length that equals 2^m-1 for an integer m. A shortened Reed-Solomon code is one in which the codeword length is not 2^m-1. A shortened [n,k] Reed-Solomon code implicitly uses an [n₁,k₁] encoder, where

The RS Encoder System object supports shortened codes using the same syntaxes it uses for nonshortened codes. You do not need to indicate explicitly that you want to use a shortened code.

hEnc = comm.RSEncoder(7,5);
ordinarycode = step(hEnc,[1 1 1 1 1]');
hEnc = comm.RSEncoder(5,3);
shortenedcode = step(hEnc,[1 1 1 ]');

How the RS Encoder System Object Creates a Shortened Code

When creating a shortened code, the RS Encoder System object performs these steps:

The following example illustrates this process.

n = 12; k = 8; % Lengths for the shortened code
m = ceil(log2(n+1)); % Number of bits per symbol
msg = randi([0 2^m-1],3*k,1); % Random array of 3 k-symbol words
hEnc = comm.RSEncoder(n,k);
code = step(hEnc, msg); % Create a shortened code.

% Do the shortening manually, just to show how it works.
n_pad = 2^m-1; % Codeword length in the actual encoder
k_pad = k+(n_pad-n); % Messageword length in the actual encoder
hEnc = comm.RSEncoder(n_pad,k_pad);
mw = reshape(msg,k,[]); % Each column vector represents a messageword
msg_pad = [zeros(n_pad-n,3); mw]; % Prepend zeros to each word.
msg_pad = msg_pad(:);
code_pad = step(hEnc,msg_pad); % Encode padded words.
cw = reshape(code_pad,2^m-1,[]); % Each column vector represents a codeword
code_eqv = cw(n_pad-n+1:n_pad,:); % Remove extra zeros.
code_eqv = code_eqv(:);
ck = isequal(code_eqv,code); % Returns true (1).

Find a Generator Polynomial

To find a generator polynomial for a cyclic, BCH, or Reed-Solomon code, use the cyclpoly, bchgenpoly, or rsgenpoly function, respectively. The commands

genpolyCyclic = cyclpoly(15,5) % 1+X^5+X^10
genpolyBCH = bchgenpoly(15,5)  % x^10+x^8+x^5+x^4+x^2+x+1
genpolyRS = rsgenpoly(15,5)

find generator polynomials for block codes of different types. The output is below.

genpolyCyclic =

     1     0     0     0     0     1     0     0     0     0     1

 
genpolyBCH = GF(2) array. 
 
Array elements = 
 
     1     0     1     0     0     1     1     0     1     1     1

 
genpolyRS = GF(2^4) array. Primitive polynomial = D^4+D+1 (19 decimal)
 
Array elements = 
 
     1     4     8    10    12     9     4     2    12     2     7

The formats of these outputs vary:

Nonuniqueness of Generator Polynomials.  Some pairs of message length and codeword length do not uniquely determine the generator polynomial. The syntaxes for functions in the example above also include options for retrieving generator polynomials that satisfy certain constraints that you specify. See the functions' reference pages for details about syntax options.

Algebraic Expression for Generator Polynomials.  The generator polynomials produced by bchgenpoly and rsgenpoly have the form (X - A^b)(X - A^b+1)...(X - A^b+2t-1), where A is a primitive element for an appropriate Galois field, and b and t are integers. See the functions' reference pages for more information about this expression.

Reed Solomon Examples with Shortening, Puncturing, and Erasures

In this section, a representative example of Reed Solomon coding with shortening, puncturing, and erasures is built with increasing complexity of error correction.

Encoder Example with Shortening and Puncturing.  The following figure shows a representative example of a (7,3) Reed Solomon encoder with shortening and puncturing.

In this figure, the message source outputs two information symbols, designated by I₁I₂. (For a BCH example, the symbols are simply binary bits.) Because the code is a shortened (7,3) code, a zero must be added ahead of the information symbols, yielding a three-symbol message of 0I₁I₂. The modified message sequence is then RS encoded, and the added information zero is subsequently removed, which yields a result of I₁I₂P₁P₂P₃P₄. (In this example, the parity bits are at the end of the codeword.)

The puncturing operation is governed by the puncture vector, which, in this case, is 1011. Within the puncture vector, a 1 means that the symbol is kept, and a 0 means that the symbol is thrown away. In this example, the puncturing operation removes the second parity symbol, yielding a final vector of I₁I₂P₁P₃P₄.

Decoder Example with Shortening and Puncturing.  The following figure shows how the RS encoder operates on a shortened and punctured codeword.

This case corresponds to the encoder operations shown in the figure of the RS encoder with shortening and puncturing. As shown in the preceding figure, the encoder receives a (5,2) codeword, because it has been shortened from a (7,3) codeword by one symbol, and one symbol has also been punctured.

As a first step, the decoder adds an erasure, designated by E, in the second parity position of the codeword. This corresponds to the puncture vector 1011. Adding a zero accounts for shortening, in the same way as shown in the preceding figure. The single erasure does not exceed the erasure-correcting capability of the code, which can correct four erasures. The decoding operation results in the three-symbol message DI₁I₂. The first symbol is truncated, as in the preceding figure, yielding a final output of I₁I₂.

Encoder Example with Shortening, Puncturing, and Erasures.  The following figure shows the decoder operating on the punctured, shortened codeword, while also correcting erasures generated by the receiver.

In this figure, demodulator receives the I₁I₂P₁P₃P₄ vector that the encoder sent. The demodulator declares that two of the five received symbols are unreliable enough to be erased, such that symbols 2 and 5 are deemed to be erasures. The 01001 vector, provided by an external source, indicates these erasures. Within the erasures vector, a 1 means that the symbol is to be replaced with an erasure symbol, and a 0 means that the symbol is passed unaltered.

The decoder blocks receive the codeword and the erasure vector, and perform the erasures indicated by the vector 01001. Within the erasures vector, a 1 means that the symbol is to be replaced with an erasure symbol, and a 0 means that the symbol is passed unaltered. The resulting codeword vector is I₁EP₁P₃E, where E is an erasure symbol.

The codeword is then depunctured, according to the puncture vector used in the encoding operation (i.e., 1011). Thus, an erasure symbol is inserted between P₁ and P₃, yielding a codeword vector of I₁EP₁EP₃E.

Just prior to decoding, the addition of zeros at the beginning of the information vector accounts for the shortening. The resulting vector is 0I₁EP₁EP₃E, such that a (7,3) codeword is sent to the Berlekamp algorithm.

This codeword is decoded, yielding a three-symbol message of DI₁I₂ (where D refers to a dummy symbol). Finally, the removal of the D symbol from the message vector accounts for the shortening and yields the original I₁I₂ vector.

For additional information, see the Reed-Solomon Coding with Erasures, Punctures, and Shortening in Simulink example.

LDPC Decoding Algorithms

LDPC decoding uses one of these message-passing algorithms. The ldpcDecode function supports the belief propagation, layered belief propagation, normalized min-sum, and offset min-sum decoding algorithms. The LDPC Decoder block only supports the belief propagation decoding algorithm.

Belief Propagation Decoding.  The implementation of the belief propagation algorithm is based on the decoding algorithm presented by Gallager [2].

For transmitted LDPC-encoded codeword c = c₀, c₁, …, c_n-1, the input to the LDPC decoder is the log-likelihood ratio (LLR) value $$L(c_i)=\log \left(\frac{\mathrm{Pr}(c_i=0|\text{channel output for }{c}_i)}{\mathrm{Pr}(c_i=1|\text{channel output for }{c}_i)}\right)$$.

In each iteration, the key components of the algorithm are updated based on these equations:

$$L(r_{ji})=2\text{atanh}\left({\displaystyle \prod _{i^{\prime }\in V_j\backslash i}\tanh \left(\frac{1}{2}L(q_{i^{\prime }j})\right)}\right)$$,

$$L(q_{ij})=L(c_i)+{\displaystyle \sum _{j^{\prime }\in C_i\backslash j}L(r_{j^{\prime }i})}$$, initialized as $$L(q_{ij})=L(c_i)$$ before the first iteration, and

$$L(Q_i)=L(c_i)+{\displaystyle \sum _{j^{\prime }\in C_i}L(r_{j^{\prime }i})}$$.

At the end of each iteration, L(Q_i) contains the updated estimate of the LLR value for transmitted bit c_i. The value L(Q_i) is the soft-decision output for c_i. If L(Q_i) ≤ 0, the hard-decision output for c_i is 1. Otherwise, the hard-decision output for c_i is 0.

If decoding is configured to stop when all of the parity checks are satisfied, the algorithm verifies the parity-check equation (H c' = 0) at the end of each iteration. When all of the parity checks are satisfied, or if the maximum number of iterations is reached, decoding stops.

Index sets $$C_i\backslash j$$ and $$V_j\backslash i$$ are based on the parity-check matrix (PCM). Index sets C_i and V_j correspond to all nonzero elements in column i and row j of the PCM, respectively.

This figure shows the computation of these index sets in a given PCM for i = 5 and j = 3.

To avoid infinite numbers in the algorithm equations, atanh(1) and atanh(–1) are set to 19.07 and –19.07, respectively. Due to finite precision, MATLAB returns 1 for tanh(19.07) and –1 for tanh(-19.07).

Layered Belief Propagation Decoding.  The implementation of the layered belief propagation algorithm is based on the decoding algorithm presented in Hocevar [3], Section II.A. The decoding loop iterates over subsets of rows (layers) of the PCM. For each row, m, in a layer and each bit index, j, the implementation updates the key components of the algorithm based on these equations:

(1) $$L(q_{mj})=L(q_j)-R_{mj}$$,

(2) $$A_{mj}={\displaystyle \sum _{\begin{array}{c}n \in N\left(m\right)\\ n\ne j\end{array}}\text{ψ}(L(q_{mn}))}$$,

(3) $$s_{mj}={\displaystyle \prod _{\begin{array}{c}n \in N\left(m\right)\\ n\ne j\end{array}}\text{sign}(L(q_{mn}))}$$,

(4) $$R_{mj}=-s_{mj}\text{ψ}(A_{mj})$$, and

(5) $$L(q_j)=L(q_{mj})+R_{mj}$$.

For each layer, the decoding equation (5) works on the combined input obtained from the current LLR inputs $$L(q_{mj})$$ and the previous layer updates $$R_{mj}$$.

Because only a subset of the nodes is updated in a layer, the layered belief propagation algorithm is faster compared to the belief propagation algorithm. To achieve the same error rate as attained with belief propagation decoding, use half the number of decoding iterations when you use the layered belief propagation algorithm.

Normalized Min-Sum Decoding.  The implementation of the normalized min-sum decoding algorithm follows the layered belief propagation algorithm with equation (2) replaced by

$$A_{mj}=\underset{\begin{array}{c}n \in N\left(m\right)\\ n\ne j\end{array}}{\min }(\left|L(q_{mn}) \right|\cdot \alpha )$$,

where α is in the range (0, 1] and is the scaling factor specified by the MinSumScalingFactor input argument to the ldpcDecode function. This equation is an adaptation of equation (4) presented in Chen [4].

Offset Min-Sum Decoding.  The implementation of the offset min-sum decoding algorithm follows the layered belief propagation algorithm with equation (2) replaced by

$$A_{mj} = \max (\underset{\begin{array}{c}n \in N\left(m\right)\\ n\ne j\end{array}}{\min } (\left|L\left(q_{mn}\right)\right|- \beta ), 0)$$,

where β ≥ 0 and is the offset specified by the MinSumOffset input argument to the ldpcDecode function. This equation is an adaptation of equation (5) presented in Chen [4].

Selected Bibliography for LDPC Coding