Store 
| Products & Services | Solutions | Academia | Support | User Community | Company |
 |
Download Product Updates | | |  |
Get Pricing | | | |
Trial Software |
| Documentation → Communications Toolbox |
| Products & Services | Solutions | Academia | Support | User Community | Company |
|
Download Product Updates | | | |
Get Pricing | | | |
Trial Software |
| Documentation → Communications Toolbox |
| Contents | Index |
| Learn more about Communications Toolbox |
Block coding is a special case of error-control coding. Block coding techniques map a fixed number of message symbols to a fixed number of code symbols. A block coder treats each block of data independently and is a memoryless device.
Some topics are relevant only for specific block coding techniques, while other topics apply to all supported block coding techniques. The table below suggests which topics you should read based on the coding techniques you want to use.
| Block Coding Technique | Relevant Sections |
|---|---|
| All supported block coding techniques | |
| Reed-Solomon | |
| Bose-Chaudhuri-Hocquenghem (BCH) | |
| Low-density parity-check (LDPC) | |
| Cyclic, Hamming, and generic linear block |
The class of linear block coding techniques includes categories shown below.
Communications Toolbox supports general linear block codes. It also includes functions to process cyclic, LDPC, BCH, Hamming, and Reed-Solomon codes (which are all special kinds of linear block codes). Functions in the toolbox can accomplish these tasks:
Encode or decode a message using one of the techniques mentioned above
Determine characteristics of a technique, such as error-correction capability or valid message length
Perform lower level computations associated with a technique, such as
Compute a decoding table
Compute a generator or parity-check matrix
Convert between generator and parity-check matrices
Compute a generator polynomial
Note The functions in this toolbox are designed for block codes that use an alphabet whose size is a power of 2. |
The table below lists the functions that are related to each supported block coding technique.
Throughout this section, the information to be encoded consists of a sequence of message symbols and the code that is produced consists of a sequence of codewords.
Each block of k message symbols is encoded into a codeword that consists of n symbols; in this context, k is called the message length, n is called the codeword length, and the code is called an [n,k] code.
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 array in the field GF(2m). Each array entry must be an integer between 0 and 2m-1. The code corresponding to that message is an n-column Galois array in GF(2m). The codeword length n must be between 3 and 2m-1.
Note For information about Galois arrays and how to create them, see Representing Elements of Galois Fields or the reference page for the gf function. |
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 = gf([1 6 4; 0 4 3],m); % Message is a Galois array. c = rsenc(msg,n,k) % Code will be a Galois array.
The output is
c = GF(2^3) array. Primitive polynomial = D^3+D+1 (11 decimal)
Array elements =
1 6 4 4 3 6 3
0 4 3 3 7 4 7
This section describes several integers related to Reed-Solomon codes and discusses how to find generator polynomials.
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.
| Symbol | Meaning | Value or Range |
|---|---|---|
| m | Number of bits per symbol | Integer between 3 and 16 |
| n | Number of symbols per codeword | Integer between 3 and 2m-1 |
| k | Number of symbols per message | Positive integer less than n, such that n-k is even |
| t | Error-correction capability of the code | (n-k)/2 |
The rsgenpoly function produces generator polynomials for Reed-Solomon codes. This is useful if you want to use rsenc and rsdec with a generator polynomial other than the default, or if you want to examine or manipulate a generator polynomial. 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(2m). 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 X2 + (A2 + A)X + (A3), 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 - Ab)(X - Ab+1)...(X - Ab+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.
The rsenc and rsdec functions create and decode Reed-Solomon codes, using the data described in Representing Words for Reed-Solomon Codes and Parameters for Reed-Solomon Codes.
This section illustrates how to use rsenc and rsdec. The topics are
The example below illustrates multiple ways to encode and decode data using a [15,13] Reed-Solomon code. The example shows that you can
Vary the generator polynomial for the code, using rsgenpoly to produce a different generator polynomial.
Vary the primitive polynomial for the Galois field that contains the symbols, using an input argument in gf.
Vary the position of the parity symbols within the codewords, choosing either the end (default) or beginning.
This example also shows that corresponding syntaxes of rsenc and rsdec use the same input arguments, except for the first input argument.
m = 4; % Number of bits in each symbol n = 2^m-1; k = 13; % Codeword length and message length data = randint(4,k,2^m); % Four random integer messages msg = gf(data,m); % Represent data using a Galois array. % Simplest syntax for encoding c1 = rsenc(msg,n,k); d1 = rsdec(c1,n,k); % Vary the generator polynomial for the code. c2 = rsenc(msg,n,k,rsgenpoly(n,k,19,2)); d2 = rsdec(c2,n,k,rsgenpoly(n,k,19,2)); % Vary the primitive polynomial for GF(16). msg2 = gf(data,m,25); c3 = rsenc(msg2,n,k); d3 = rsdec(c3,n,k); % Prepend the parity symbols instead of appending them. c4 = rsenc(msg,n,k,'beginning'); d4 = rsdec(c4,n,k,'beginning'); % Check that the decoding worked correctly. chk = isequal(d1,msg) & isequal(d2,msg) & isequal(d3,msg2) &... isequal(d4,msg)
The output is
chk =
1
The example below illustrates the decoding results for a corrupted code. The example encodes some data, introduces errors in each codeword, and invokes rsdec to attempt to decode the noisy code. It uses additional output arguments in rsdec to gain information about the success of the decoding process.
m = 3; % Number of bits per symbol n = 2^m-1; k = 3; % Codeword length and message length t = (n-k)/2; % Error-correction capability of the code nw = 4; % Number of words to process msgw = gf(randint(nw,k,2^m),m); % Random k-symbol messages c = rsenc(msgw,n,k); % Encode the data. noise = (1+randint(nw,n,2^m-1)).*randerr(nw,n,t); % t errors/row cnoisy = c + noise; % Add noise to the code. [dc,nerrs,corrcode] = rsdec(cnoisy,n,k); % Decode the noisy code. % Check that the decoding worked correctly. isequal(dc,msgw) & isequal(corrcode,c) nerrs % Find out how many errors rsdec corrected.
The array of noise values contains integers between 1 and 2^m, and the addition operation c + noise takes place in the Galois field GF(2^m) because c is a Galois array in GF(2^m).
The output from the example is below. The nonzero value of ans indicates that the decoder was able to correct the corrupted codewords and recover the original message. The values in the vector nerrs indicates that the decoder corrected t errors in each codeword.
ans =
1
nerrs =
2
2
2
2
In the previous example, rsdec corrected all of the errors. However, each Reed-Solomon code has a finite error-correction capability. If the noise is so great that the corrupted codeword is too far in Hamming distance from the correct codeword, that means either
The corrupted codeword is close to a valid codeword other than the correct codeword. The decoder returns the message that corresponds to the other codeword.
The corrupted codeword is not close enough to any codeword for successful decoding. This situation is called a decoding failure. The decoder removes the symbols in parity positions from the corrupted codeword and returns the remaining symbols.
In both cases, the decoder returns the wrong message. However, you can tell when a decoding failure occurs because rsdec also returns a value of -1 in its second output.
To examine cases in which codewords are too noisy for successful decoding, change the previous example so that the definition of noise is
noise = (1+randint(nw,n,n)).*randerr(nw,n,t+1); % t+1 errors/row
Every Reed-Solomon encoder uses a codeword length that equals 2m-1 for an integer m. A shortened Reed-Solomon code is one in which the codeword length is not 2m-1. A shortened [n,k] Reed-Solomon code implicitly uses an [n1,k1] encoder, where
n1 = 2m - 1, where m is the number of bits per symbol
k1 = k + (n1 - n)
The rsenc and rsdec functions support shortened codes using the same syntaxes they use for nonshortened codes. You do not need to indicate explicitly that you want to use a shortened code. For example, compare the two similar-looking commands below. The first creates a (nonshortened) [7,5] code. The second causes rsenc to create a [5,3] shortened code by implicitly using a [7,5] encoder.
m = 3; ordinarycode = rsenc(gf([1 1 1 1 1],m),7,5); m = 3; shortenedcode = rsenc(gf([1 1 1],m),5,3);
How rsenc Creates a Shortened Code. When creating a shortened code, rsenc performs these steps:
Pads each message by prepending zeros
Encodes each padded message using a Reed-Solomon encoder having an allowable codeword length and the desired error-correction capability
Removes the extra zeros from the nonparity symbols of each codeword
The example below illustrates this process. Note that forming a [12,8] Reed-Solomon code actually uses a [15,11] Reed-Solomon encoder. You do not have to indicate in the rsenc syntax that this is a shortened code or that the proper encoder to use is [15,11].
n = 12; k = 8; % Lengths for the shortened code m = ceil(log2(n+1)); % Number of bits per symbol msg = gf(randint(3,k,2^m),m); % Random array of 3 k-symbol words code = rsenc(msg,n,k); % 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); % Message length in the actual encoder msg_pad=[zeros(3, n_pad-n), msg]; % Prepend zeros to each word. code_pad = rsenc(msg_pad,n_pad,k_pad); % Encode padded words. code_eqv = code_pad(:,n_pad-n+1:n_pad); % Remove extra zeros. ck = isequal(code_eqv,code); % Returns true (1).
A message for an [n,k] BCH code must be a k-column binary Galois array. The code that corresponds to that message is an n-column binary Galois array. Each row of these Galois arrays represents one word.
The example below illustrates how to represent words for a [15, 11] BCH code.
n = 15; k = 5; % Codeword length and message length msg = gf([1 0 0 1 0; 1 0 1 1 1]); % Two messages in a Galois array cbch = bchenc(msg,n,k) % Two codewords in a Galois array.
The output is
cbch = GF(2) array.
Array elements =
Columns 1 through 5
1 0 0 1 0
1 0 1 1 1
Columns 6 through 10
0 0 1 1 1
0 0 0 0 1
Columns 11 through 15
1 0 1 0 1
0 1 0 0 1 BCH codes use special values of n and k:
n, the codeword length, is an integer of the form 2m-1 for some integer m > 2.
k, the message length, is a positive integer less than n. However, only some positive integers less than n are valid choices for k. See the bchenc reference page for a list of some valid values of k corresponding to values of n up to 511.
The bchenc and bchdec functions create and decode BCH codes, using the data described in Representing Words for BCH Codes and Parameters for BCH Codes. This section illustrates how to use bchenc and bchdec.
The topics are
The example below illustrates how to encode and decode data using a [15, 5] Reed-Solomon code. The example shows that
You can vary the position of the parity symbols within the codewords, choosing either the end (default) or beginning.
Corresponding syntaxes of bchenc and bchdec use the same input arguments, except for the first input argument.
n = 15; k = 5; % Codeword length and message length dat = randint(4,k); % Four random binary messages msg = gf(dat); % Represent data using a Galois array. % Simplest syntax for encoding c1 = bchenc(msg,n,k); d1 = bchdec(c1,n,k); % Prepend the parity symbols instead of appending them. c2 = bchenc(msg,n,k,'beginning'); d2 = bchdec(c2,n,k,'beginning'); % Check that the decoding worked correctly. chk = isequal(d1,msg) & isequal(d2,msg)
The output is below.
chk =
1
The example below illustrates the decoding results for a corrupted code. The example encodes some data, introduces errors in each codeword, and invokes bchdec to attempt to decode the noisy code. It uses additional output arguments in bchdec to gain information about the success of the decoding process.
n = 15; k = 5; % Codeword length and message length [gp,t] = bchgenpoly(n,k); % t is error-correction capability. nw = 4; % Number of words to process msgw = gf(randint(nw,k)); % Random k-symbol messages c = bchenc(msgw,n,k); % Encode the data. noise = randerr(nw,n,t); % t errors/row cnoisy = c + noise; % Add noise to the code. [dc,nerrs,corrcode] = bchdec(cnoisy,n,k); % Decode cnoisy. % Check that the decoding worked correctly. chk2 = isequal(dc,msgw) & isequal(corrcode,c) nerrs % Find out how many errors bchdec corrected.
Notice that the array of noise values contains binary values, and that the addition operation c + noise takes place in the Galois field GF(2) because c is a Galois array in GF(2).
The output from the example is below. The nonzero value of ans indicates that the decoder was able to correct the corrupted codewords and recover the original message. The values in the vector nerrs indicate that the decoder corrected t errors in each codeword.
chk2 =
1
nerrs =
3
3
3
3Excessive Noise in BCH Codewords. In the previous example, bchdec corrected all the errors. However, each BCH code has a finite error-correction capability. To learn more about how bchdec behaves when the noise is excessive, see the analogous discussion for Reed-Solomon codes in Excessive Noise in Reed-Solomon Codewords.
Low-Density Parity-Check (LDPC) codes are linear error control codes with:
Sparse parity-check matrices
Long block lengths that can attain performance near the Shannon limit (see fec.ldpcenc and fec.ldpcdec)
The decoding process is done iteratively. If the number of iterations is too small, the algorithm may not converge. You may need to experiment with the number of iterations to find an appropriate value for your model. For details on the decoding algorithm, see Decoding Algorithm.
Unlike some other codecs, you cannot connect an LDPC decoder directly to the output of an LDPC encoder, because the decoder requires log-likelihood ratios (LLR). Thus, you may use a demodulator to compute the LLRs.
Also, unlike other decoders, it is possible (although rare) that the output of the LDPC decoder does not satisfy all parity checks.
The cyclic, Hamming, and generic linear block code functionality in this toolbox offers you multiple ways to organize bits in messages or codewords. These topics explain the available formats:
To learn how to represent words for BCH or Reed-Solomon codes, see Representing Words for BCH Codes or Representing Words for Reed-Solomon Codes.
Your messages and codewords can take the form of vectors containing 0s and 1s. For example, messages and codes might look like msg and code in the lines below.
n = 6; k = 4; % Set codeword length and message length % for a [6,4] code. msg = [1 0 0 1 1 0 1 0 1 0 1 1]'; % Message is a binary column. code = encode(msg,n,k,'cyclic'); % Code will be a binary column. msg' code'
The output is below.
ans =
Columns 1 through 5
1 0 0 1 1
Columns 6 through 10
0 1 0 1 0
Columns 11 through 12
1 1
ans =
Columns 1 through 5
1 1 1 0 0
Columns 6 through 10
1 0 0 1 0
Columns 11 through 15
1 0 0 1 1
Columns 16 through 18
0 1 1 In this example, msg consists of 12 entries, which are interpreted as three 4-digit (because k = 4) messages. The resulting vector code comprises three 6-digit (because n = 6) codewords, which are concatenated to form a vector of length 18. The parity bits are at the beginning of each codeword.
You can organize coding information so as to emphasize the grouping of digits into messages and codewords. If you use this approach, each message or codeword occupies a row in a binary matrix. The example below illustrates this approach by listing each 4-bit message on a distinct row in msg and each 6-bit codeword on a distinct row in code.
n = 6; k = 4; % Set codeword length and message length. msg = [1 0 0 1; 1 0 1 0; 1 0 1 1]; % Message is a binary matrix. code = encode(msg,n,k,'cyclic'); % Code will be a binary matrix. msg code
The output is below.
msg =
1 0 0 1
1 0 1 0
1 0 1 1
code =
1 1 1 0 0 1
0 0 1 0 1 0
0 1 1 0 1 1
Note In the binary matrix format, the message matrix must have k columns. The corresponding code matrix has n columns. The parity bits are at the beginning of each row. |
Your messages and codewords can take the form of vectors containing integers. Each element of the vector gives the decimal representation of the bits in one message or one codeword.
Note If 2^n or 2^k is very large, you should use the default binary format instead of the decimal format. This is because the function uses a binary format internally, while the roundoff error associated with converting many bits to large decimal numbers and back might be substantial. |
Note When you use the decimal vector format, encode expects the leftmost bit to be the least significant bit. |
The syntax for the encode command must mention the decimal format explicitly, as in the example below. Notice that /decimal is appended to the fourth argument in the encode command.
n = 6; k = 4; % Set codeword length and message length. msg = [9;5;13]; % Message is a decimal column vector. % Code will be a decimal vector. code = encode(msg,n,k,'cyclic/decimal')
The output is below.
code =
39
20
54
Note The three examples above used cyclic coding. The formats for messages and codes are similar for Hamming and generic 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. The table below lists the items and the coding techniques for which they are most relevant.
Parameters Used in Block Coding Techniques
| Parameter | Block Coding Technique |
|---|---|
| Generator Matrix | Generic linear block |
| Parity-Check Matrix | Generic linear block |
| Generator Polynomial | Cyclic |
| Decoding Table | Generic linear block, Hamming |
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 [Ik P] or [P Ik], where P is some k-by-(n-k) matrix and Ik is the k-by-k identity matrix, G is said to be in standard form. (Some authors, e.g., Clark and Cain [2], use the first standard form, while others, e.g., Lin and Costello [3], use the second.) Most functions in this toolbox assume that a generator matrix is in standard form when you use it as an input argument.
Some examples of generator matrices are in the next section, Parity-Check Matrix.
Decoding an [n,k] linear block code requires an (n-k)-by-n parity-check matrix H. It satisfies GHtr = 0 (mod 2), where Htr denotes the matrix transpose of H, G is the code's generator matrix, and this zero matrix is k-by-(n-k). If G = [Ik P] then H = [-Ptr In-k]. Most functions in this toolbox assume that a parity-check matrix is in standard form when you use it as an input argument.
The table below summarizes the standard forms of the generator and parity-check matrices for an [n,k] binary linear block code.
| Type of Matrix | Standard Form | Dimensions |
|---|---|---|
| Generator | [Ik P] or [P Ik] | k-by-n |
| Parity-check | [-P' In-k] or [In-k -P' ] | (n-k)-by-n |
Ik is the identity matrix of size k and the ' symbol indicates matrix transpose. (For binary codes, the minus signs in the parity-check form listed above are irrelevant; that is, -1 = 1 in the binary field.)
Examples. In the command below, parmat is a parity-check matrix and genmat is a generator matrix for a Hamming code in which [n,k] = [23-1, n-3] = [7,4]. genmat has the standard form [P Ik].
[parmat,genmat] = hammgen(3)
parmat =
1 0 0 1 0 1 1
0 1 0 1 1 1 0
0 0 1 0 1 1 1
genmat =
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
The next example finds parity-check and generator matrices for a [7,3] cyclic code. The cyclpoly function is mentioned below in Generator Polynomial.
genpoly = cyclpoly(7,3);
[parmat,genmat] = cyclgen(7,genpoly)
parmat =
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 =
1 0 1 1 1 0 0
1 1 1 0 0 1 0
0 1 1 1 0 0 1
The example below converts a generator matrix for a [5,3] linear block code into the corresponding parity-check matrix.
genmat = [1 0 0 1 0; 0 1 0 1 1; 0 0 1 0 1];
parmat = gen2par(genmat)
parmat =
1 1 0 1 0
0 1 1 0 1
The same function gen2par can also convert a parity-check matrix into a generator matrix.
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 xn-1. Van Lint [5] explains how a generator polynomial determines a cyclic code.
The cyclpoly function produces generator polynomials for cyclic codes. cyclpoly represents a generator polynomial using a row vector that lists the polynomial's coefficients in order of ascending powers of the variable. For example, the command
genpoly = cyclpoly(7,3)
genpoly =
1 0 1 1 1
finds that one valid generator polynomial for a [7,3] cyclic code is 1 + x2 + x3 + x4.
A decoding table tells a decoder how to correct errors that might 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 given codeword.
This 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.
Example: Using a Decoding Table. The script below shows how to use a Hamming decoding table to correct an error in a received message. The hammgen function produces the parity-check matrix, while the syndtable function produces the decoding table. The transpose of the parity-check matrix is multiplied on the left by the received codeword, yielding the syndrome. The decoding table helps determine the correction vector. The corrected codeword is the sum (modulo 2) of the correction vector and the received codeword.
% Use a [7,4] Hamming code.
m = 3; n = 2^m-1; k = n-m;
parmat = hammgen(m); % Produce parity-check matrix.
trt = syndtable(parmat); % Produce decoding table.
recd = [1 0 0 1 1 1 1] % Suppose this is the received vector.
syndrome = rem(recd * parmat',2);
syndrome_de = bi2de(syndrome,'left-msb'); % Convert to decimal.
disp(['Syndrome = ',num2str(syndrome_de),...
' (decimal), ',num2str(syndrome),' (binary)'])
corrvect = trt(1+syndrome_de,:) % Correction vector
% Now compute the corrected codeword.
correctedcode = rem(corrvect+recd,2)The output is below.
recd =
1 0 0 1 1 1 1
Syndrome = 3 (decimal), 0 1 1 (binary)
corrvect =
0 0 0 0 1 0 0
correctedcode =
1 0 0 1 0 1 1
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.
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 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);
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
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 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 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.
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.
This section describes functions that compute typical parameters associated with linear block codes, as well as functions that convert information from one format to another. The topics are
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:
cyclpoly represents a generator polynomial using an integer row vector that lists the polynomial's coefficients in order of ascending powers of the variable.
bchgenpoly and rsgenpoly represent a generator polynomial using a Galois row vector that lists the polynomial's coefficients in order of descending powers of the variable.
rsgenpoly uses coefficients in a Galois field other than the binary field GF(2). For more information on the meaning of these coefficients, see How Integers Correspond to Galois Field Elements and Polynomials over Galois Fields.
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 - Ab)(X - Ab+1)...(X - Ab+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.
You can use a liner block code to detect dmin -1
errors or to correct t =
errors. If you compromise the
error correction capability of a code, you can detect more than t errors.
For example, a code with dmin =
7 can correct t = 3 errors or it can detect up
to 4 errors and correct up to 2 errors.
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. For example, the commands
[g,t] = bchgenpoly(31,16);
t
t =
3
find that a [31, 16] BCH code can correct up to three errors in each codeword.
To find a parity-check and generator matrix for a Hamming code with codeword length 2^m-1, use the hammgen function as below. m must be at least three.
[parmat,genmat] = hammgen(m); % Hamming
To find a parity-check and generator matrix for a cyclic code, use the cyclgen function. You must provide the codeword length and a valid generator polynomial. You can use the cyclpoly function to produce one possible generator polynomial after you provide the codeword length and message length. For example,
[parmat,genmat] = cyclgen(7,cyclpoly(7,4)); % Cyclic
The gen2par function converts a generator matrix into a parity-check matrix, and vice versa. The reference page for gen2par contains examples to illustrate this.
[1] Berlekamp, Elwyn R., Algebraic Coding Theory, New York, McGraw-Hill, 1968.
[2] Clark, George C. Jr., and J. Bibb Cain, Error-Correction Coding for Digital Communications, New York, Plenum Press, 1981.
[3] Lin, Shu, and Daniel J. Costello, Jr., Error Control Coding: Fundamentals and Applications, Englewood Cliffs, NJ, Prentice-Hall, 1983.
[4] Peterson, W. Wesley, and E. J. Weldon, Jr., Error-Correcting Codes, 2nd ed., Cambridge, MA, MIT Press, 1972.
[5] van Lint, J. H., Introduction to Coding Theory, New York, Springer-Verlag, 1982.
[6] Wicker, Stephen B., Error Control Systems for Digital Communication and Storage, Upper Saddle River, NJ, Prentice Hall, 1995.
[7] Gallager, Robert G., Low-Density Parity-Check Codes, Cambridge, MA, MIT Press, 1963.
[8] Ryan, William E., "An introduction to LDPC codes," Coding and Signal Processing for Magnetic Recoding Systems (Vasic, B., ed.), CRC Press, 2004.
 | Error Detection and Correction | Convolutional 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 |
