Creating and Decoding Linear Block Codes :: Error-Control Coding (Communications Toolbox)

Communications Toolbox

Creating and Decoding 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, then 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 Representing 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);

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 Polynomialand 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 Representing 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 the section 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:

Replace the second line by

genpoly = [1 0 1]; % generator poly is 1 + x^2

In the fifth and ninth lines (encode and decode commands), replace genmat by genpoly and replace 'linear' by 'cyclic'.

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 section Decoding Table illustrates error correction in a Hamming code.

Parameters for Linear Block Codes

Performing Other Block Code Tasks