Error Detection and Correction
Cyclic Redundancy Check Codes
CRCCode Features
Cyclic redundancy check (CRC) coding is an errorcontrol coding technique for detecting errors that occur when a message is transmitted. Unlike block or convolutional codes, CRC codes do not have a builtin errorcorrection capability. Instead, when a communications system detects an error in a received message word, the receiver requests the sender to retransmit the message word.
In CRC coding, the transmitter applies a rule to each message word to create extra bits, called the checksum, or syndrome, and then appends the checksum to the message word. After receiving a transmitted word, the receiver applies the same rule to the received word. If the resulting checksum is nonzero, an error has occurred, and the transmitter should resend the message word.
Open the Error Detection and Correction library by doubleclicking its icon in the main Communications Toolbox™ block library. Open the CRC sublibrary by doubleclicking on its icon in the Error Detection and Correction library.
Communications Toolbox supports CRC Coding using Simulink^{®} blocks, System objects, or MATLAB^{®} objects. These CRC coding features are listed in Error Detection and Correction.
CRC NonDirect Algorithm
The CRC nondirect algorithm accepts a binary data vector, corresponding to a
polynomial M, and appends a checksum of r bits, corresponding to a polynomial C.
The concatenation of the input vector and the checksum then corresponds to the
polynomial T =
M*
x^{r}
+ C, since multiplying by
x^{r} corresponds to shifting
the input vector r bits to the left. The algorithm chooses
the checksum C so that T is divisible by a
predefined polynomial P of degree r,
called the generator polynomial.
The algorithm divides T by P, and sets
the checksum equal to the binary vector corresponding to the remainder. That is,
if T =
Q*
P +
R, where R is a polynomial of degree
less than r, the checksum is the binary vector corresponding
to R. If necessary, the algorithm prepends zeros to the
checksum so that it has length r.
The CRC generation feature, which implements the transmission phase of the CRC algorithm, does the following:
Left shifts the input data vector by r bits and divides the corresponding polynomial by P.
Sets the checksum equal to the binary vector of length r, corresponding to the remainder from step 1.
Appends the checksum to the input data vector. The result is the output vector.
The CRC detection feature computes the checksum for its entire input vector, as described above.
The CRC algorithm uses binary vectors to represent binary polynomials, in
descending order of powers. For example, the vector [1 1 0 1]
represents the polynomial x^{3 }+
x^{2 }+ 1.
Note
The implementation described in this section is one of many valid implementations of the CRC algorithm. Different implementations can yield different numerical results.
Bits enter the linear feedback shift register (LFSR) from the lowest index bit to the highest index bit. The sequence of input message bits represents the coefficients of a message polynomial in order of decreasing powers. The message vector is augmented with r zeros to flush out the LFSR, where r is the degree of the generator polynomial. If the output from the leftmost register stage d(1) is a 1, then the bits in the shift register are XORed with the coefficients of the generator polynomial. When the augmented message sequence is completely sent through the LFSR, the register contains the checksum [d(1) d(2) . . . d(r)]. This is an implementation of binary long division, in which the message sequence is the divisor (numerator) and the polynomial is the dividend (denominator). The CRC checksum is the remainder of the division operation.
Example Using CRC NonDirect Algorithm
Suppose the input frame is [1 1 0 0 1 1 0]'
, corresponding
to the polynomial M = x^{6
}+x
^{5 }+ x^{2
}+ x, and the generator polynomial is P =
x^{3} +
x^{2} + 1, of degree
r = 3. By polynomial division,
M*
x^{3} =
(x^{6} +
x^{3} +
x)*
P + x. The
remainder is R = x, so that the checksum is then
[0 1 0]'
. An extra 0 is added on the left to make the
checksum have length 3.
CRC Direct Algorithm
where
Message Block Input is $${m}_{0},\text{\hspace{0.17em}}{m}_{1},\text{\hspace{0.17em}}\mathrm{...}\text{\hspace{0.17em}},\text{\hspace{0.17em}}{m}_{k1}$$
Code Word Output is $${c}_{0},\text{\hspace{0.17em}}{c}_{1},\mathrm{...}\text{}\text{}\text{\hspace{0.17em}},\text{}\text{\hspace{0.17em}}{c}_{n1}=\underset{X}{\underbrace{{m}_{0},\text{\hspace{0.17em}}{m}_{1},\mathrm{...}\text{}\text{}\text{\hspace{0.17em}},{m}_{k1},}}\underset{Y}{\underbrace{{d}_{0},{d}_{1},\text{\hspace{0.17em}}\mathrm{...}\text{\hspace{0.17em}},\text{\hspace{0.17em}}{d}_{nk1}}}$$
The initial step of the direct CRC encoding occurs with the three switches in position X. The algorithm feeds k message bits to the encoder. These bits are the first k bits of the code word output. Simultaneously, the algorithm sends k bits to the linear feedback shift register (LFSR). When the system completely feeds the kth message bit to the LFSR, the switches move to position Y. Here, the LFSR contains the mathematical remainder from the polynomial division. These bits are shifted out of the LFSR and they are the remaining bits (checksum) of the code word output.
Selected Bibliography for CRC Coding
[1] Sklar, Bernard., Digital Communications: Fundamentals and Applications, Englewood Cliffs, NJ, Prentice Hall, 1988.
[2] Wicker, Stephen B., Error Control Systems for Digital Communication and Storage, Upper Saddle River, NJ, Prentice Hall, 1995.
Block Codes
BlockCoding Features
Errorcontrol coding techniques detect, and possibly correct, errors that occur when messages are transmitted in a digital communication system. To accomplish this, the encoder transmits not only the information symbols but also extra redundant symbols. The decoder interprets what it receives, using the redundant symbols to detect and possibly correct whatever errors occurred during transmission. You might use errorcontrol coding if your transmission channel is very noisy or if your data is very sensitive to noise. Depending on the nature of the data or noise, you might choose a specific type of errorcontrol coding.
Block coding is a special case of errorcontrol coding. Blockcoding 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. Communications Toolbox contains blockcoding capabilities by providing Simulink blocks, System objects, and MATLAB functions.
The class of blockcoding techniques includes categories shown in the diagram below.
Communications Toolbox supports general linear block codes. It also process cyclic, BCH, Hamming, and ReedSolomon codes (which are all special kinds of linear block codes). Blocks in the product can encode or decode a message using one of the previously mentioned techniques. The ReedSolomon and BCH decoders indicate how many errors they detected while decoding. The ReedSolomon coding blocks also let you decide whether to use symbols or bits as your data.
Note
The blocks and functions in Communications Toolbox are designed for errorcontrol codes that use an alphabet having 2 or 2^{m} symbols.
Communications Toolbox Support Functions. Functions in Communications Toolbox can support simulation blocks by
Determining characteristics of a technique, such as errorcorrection capability or possible message lengths
Performing lowerlevel computations associated with a technique, such as
Computing a truth table
Computing a generator or paritycheck matrix
Converting between generator and paritycheck matrices
Computing a generator polynomial
For more information about errorcontrol coding capabilities, see Block Codes.
Terminology
Throughout this section, the information to be encoded consists of message symbols and the code that is produced consists of codewords.
Each block of K message symbols is encoded into a codeword that consists of N message symbols. K is called the message length, N is called the codeword length, and the code is called an [N,K] code.
Data Formats for Block Coding
Each message or codeword is an ordered grouping of symbols. Each block in the Block Coding sublibrary processes one word in each time step, as described in the following section, Binary Format (All Coding Methods). ReedSolomon coding blocks also let you choose between binary and integer data, as described in Integer Format (ReedSolomon Only).
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 fourbit message and producing a fivebit codeword at time 0. It repeats this process with a new message at time 1.
For all coding techniques except ReedSolomon using binary input, the message vector must have length K and the corresponding code vector has length N. For ReedSolomon codes with binary input, the symbols for the code are binary sequences of length M, corresponding to elements of the Galois field GF(2^{M}). In this case, the message vector must have length M*K and the corresponding code vector has length M*N. The BinaryInput RS Encoder block and the BinaryOutput RS Decoder block use this format for messages and codewords.
If the input to a blockcoding block is a framebased vector, it must be a column vector instead of a row vector.
To produce samplebased 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 framebased 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 codingbuffering 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 (ReedSolomon Only). A message word for an [N,K] ReedSolomon 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 ReedSolomon codes lets you structure messages and codewords as integer signals instead of binary signals. (The input must be a framebased column vector.)
Note
In this context, Simulink expects the first bit to be the most significant bit in the symbol. “First” means the smallest index in a vector or the smallest time for a series of scalars.
The following figure illustrates the equivalence between binary and integer signals for a ReedSolomon encoder. The case for the decoder is similar.
To produce samplebased messages in the integer format, you can configure the Random Integer Generator block so that Mary number and Initial seed parameters are vectors of the desired length and all entries of the Mary number vector are 2^{M}. To produce framebased messages in the integer format, you can configure the same block so that its Mary number and Initial seed parameters are scalars and its Samples per frame parameter is the length of the signal you want to create.
Using Block Encoders and Decoders Within a Model
Once you have configured the coding blocks, a few tips can help you place them correctly within your model:
If a block has multiple outputs, the first one is always the stream of coding data.
The ReedSolomon and BCH blocks have an error counter as a second output.
Be sure that the signal sizes are appropriate for the mask parameters. For example, if you use the Binary Cyclic Encoder block and set Message length K to
4
, the input signal must be a vector of length 4.You can display the size of signals in your model. On the Debug tab, expand Information Overlays. In the Signals section, select Signal Dimensions.
Examples of Block Coding
Example: ReedSolomon Code in Integer Format. This example uses a ReedSolomon code in integer format. It illustrates the appropriate vector lengths of the code and message signals for the coding blocks. It also exhibits error correction, using a simple way of introducing errors into each codeword.
Open the model by typing doc_rscoding
at the MATLAB
command line. To build the model, gather and configure these blocks:
Random Integer Generator, in the Comm Sources library
Set Mary number to
15
.Set Initial seed to a positive number,
randn
is chosen here.Check the Framebased outputs check box.
Set Samples per frame to
5
.
Set Codeword length N to
15
.Set Message length K to
5
.
Gain (Simulink), in the Simulink Math Operations library
Set Gain to
[0; 0; 0; 0; 0; ones(10,1)]
.
Set Codeword length N to
15
.Set Message length K to
5
.
Scope (Simulink), in the Simulink Sinks library. Get two copies of this block.
Add (Simulink), in the Simulink Math Operations library
Set List of signs to
+
Connect the blocks as shown in the preceding figure. On the
Simulation tab, in the
Simulate section, set Stop
time to 500
. The
Simulate section appears on multiple
tabs.
You can display the vector length of signals in your model. On the Debug tab, expand Information Overlays. In the Signals section, select Signal Dimensions.
The encoder accepts a vector of length 5 (which is K in this case) and produces a vector of length 15 (which is N in this case). The decoder does the opposite.
Running the model produces the following scope images. The plotted error count will vary based on the Initial Seed value used in the Random Integer Generator block. You can adjust the axis range exactly match that of the first scope. Rightclick the plot area in the second scope and select Configuration Properties. On the Display tab, adjust the axes limits.
Number of Errors Before Correction
The second plot is the number of errors that the decoder detected while trying to recover the message. Often the number is five because the Gain block replaces the first five symbols in each codeword with zeros. However, the number of errors is less than five whenever a correct codeword contains one or more zeros in the first five places.
The first plot is the difference between the original message and the recovered message; since the decoder was able to correct all errors that occurred, each of the five data streams in the plot is zero.
Notes on Specific BlockCoding Techniques
Although the Block Coding sublibrary is somewhat uniform in its look and feel, the various coding techniques are not identical. This section describes special options and restrictions that apply to parameters and signals for the coding technique categories in this sublibrary. Coding techniques discussed below include  Generic Linear Block code, Cyclic code, Hamming code, BCH code, and ReedSolomon code.
Generic Linear Block Codes
Encoding a message using a generic linear block code requires a generator matrix. Decoding the code requires the generator matrix and possibly a truth table. To use the Binary Linear Encoder and Binary Linear Decoder blocks, you must understand the Generator matrix and Errorcorrection truth table parameters.
Generator Matrix  The process of encoding a message into an [N,K] linear block code is determined by a KbyN generator matrix G. Specifically, a 1byK message vector v is encoded into the 1byN codeword vector vG. If G has the form [I_{k}, P] or [P, I_{k}], where P is some Kby(NK) matrix and I_{k} is the KbyK identity matrix, G is said to be in standard form. (Some authors, such as Clark and Cain [2], use the first standard form, while others, such as Lin and Costello [3], use the second.) The linear blockcoding blocks in this product require the Generator matrix mask parameter to be in standard form.
Decoding Table  A decoding table tells a decoder how to correct errors that may have corrupted the code during transmission. Hamming codes can correct any singlesymbol error in any codeword. Other codes can correct, or partially correct, errors that corrupt more than one symbol in a given codeword.
The Binary Linear Decoder block allows you to specify a decoding table in the Errorcorrection truth table parameter. Represent a decoding table as a matrix with N columns and 2^{NK} rows. Each row gives a correction vector for one received codeword vector.
You can avoid specifying a decoding table explicitly, by setting the
Errorcorrection truth table parameter to
0
. When Errorcorrection truth table
is 0
, the block computes a decoding table using the syndtable
function.
Cyclic Codes
For cyclic codes, the codeword length N must have the form 2^{M}1, where M is an integer greater than or equal to 3.
Generator Polynomials  Cyclic codes have special algebraic properties that allow a polynomial to determine the coding process completely. This socalled generator polynomial is a degree(NK) divisor of the polynomial x^{N}1. Van Lint [5] explains how a generator polynomial determines a cyclic code.
The Binary Cyclic Encoder and Binary Cyclic Decoder blocks allow
you to specify a generator polynomial as the second mask parameter, instead of
specifying K there. The blocks represent a generator polynomial using a vector
that lists the coefficients of the polynomial in order of
ascending powers of the variable. You can find
generator polynomials for cyclic codes using the cyclpoly
function.
If you do not want to specify a generator polynomial, set the second mask parameter to the value of K.
Hamming Codes
For Hamming codes, the codeword length N must have the form 2^{M}1, where M is an integer greater than or equal to 3. The message length K must equal NM.
Primitive Polynomials  Hamming codes rely on algebraic
fields that have 2^{M} elements (or, more generally,
p^{M} elements for a prime
number p). Elements of such fields are named
relative to a distinguished element of the field that
is called a primitive element. The minimal polynomial of a
primitive element is called a primitive polynomial. The
Hamming Encoder and Hamming Decoder blocks allow you to
specify a primitive polynomial for the finite field that they use for
computations. If you want to specify this polynomial, do so in the second mask
parameter field. The blocks represent a primitive polynomial using a vector that
lists the coefficients of the polynomial in order of
ascending powers of the variable. You can find
generator polynomials for Galois fields using the gfprimfd
function.
If you do not want to specify a primitive polynomial, set the second mask parameter to the value of K.
BCH Codes
BCH codes are cyclic errorcorrecting codes that are constructed using finite
fields. For these codes, the codeword length N must have the form
2^{M}1, where M is an integer from 3 to 9. The
message length K is restricted to particular values that depend on N. To see
which values of K are valid for a given N, see the comm.BCHEncoder
System object™ reference page. No known analytic formula describes the
relationship among the codeword length, message length, and errorcorrection
capability for BCH codes.
NarrowSense BCH Codes
The narrowsense generator polynomial is LCM[m_1(x), m_2(x), ..., m_2t(x)], where:
LCM represents the least common multiple,
m_i(x) represents the minimum polynomial corresponding to α^{i}, α is a root of the default primitive polynomial for the field GF(
n+1
),and t represents the errorcorrecting capability of the code.
ReedSolomon Codes
ReedSolomon codes are useful for correcting errors that occur in bursts. In
the simplest case, the length of codewords in a ReedSolomon code is of the form
N= 2^{M}1, where the 2^{M }is
the number of symbols for the code. The errorcorrection capability of a
ReedSolomon code is floor((NK)/2)
, where K is the length of
message words. The difference NK must be even.
It is sometimes convenient to use a shortened ReedSolomon code in which N is
less than 2^{M}1. In this case, the encoder appends
2^{M}1N zero symbols to each message word and
codeword. The errorcorrection capability of a shortened ReedSolomon code is
also floor((NK)/2)
. The Communications Toolbox ReedSolomon blocks can implement shortened ReedSolomon
codes.
Effect of Nonbinary Symbols  One difference between ReedSolomon codes and the other codes supported in this product is that ReedSolomon codes process symbols in GF(2^{M}) instead of GF(2). M bits specify each symbol. The nonbinary nature of the ReedSolomon code symbols causes the ReedSolomon blocks to differ from other coding blocks in these ways:
You can use the integer format, via the IntegerInput RS Encoder and IntegerOutput RS Decoder blocks.
The binary format expects the vector lengths to be an integer multiple of M*K (not K) for messages and the same integer M*N (not N) for codewords.
Error Information  The ReedSolomon decoding blocks (BinaryOutput RS Decoder and IntegerOutput RS Decoder) return errorrelated information during the simulation. The second output signal indicates the number of errors that the block detected in the input codeword. A 1 in the second output indicates that the block detected more errors than it could correct using the coding scheme.
Shortening, Puncturing, and Erasures
Many standards utilize punctured codes, and digital receivers can easily output erasures. BCH and RS performance improves significantly in fading channels where the receiver generates erasures.
A punctured codeword has only parity symbols removed, and a shortened codeword has only information symbols removed. A codeword with erasures can have those erasures in either information symbols or parity symbols.
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_{1}I_{2}. (For a BCH example, the symbols are binary bits.) Because the code is a shortened (7,3) code, a zero must be added ahead of the information symbols, yielding a threesymbol message of 0I_{1}I_{2}. The modified message sequence is RS encoded, and the added information zero is then removed, which yields a result of I_{1}I_{2}P_{1}P_{2}P_{3}P_{4}. (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_{1}I_{2}P_{1}P_{3}P_{4}.
Decoder Example with Shortening and Puncturing
The following figure shows how the RS decoder 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 erasurecorrecting capability of the code, which can correct four erasures. The decoding operation results in the threesymbol message DI_{1}I_{2}. The first symbol is truncated, as in the preceding figure, yielding a final output of I_{1}I_{2}.
Decoder 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_{1}I_{2}P_{1}P_{3}P_{4} 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_{1}EP_{1}P_{3}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_{1} and P_{3}, yielding a codeword vector of I_{1}EP_{1}EP_{3}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_{1}EP_{1}EP_{3}E, such that a (7,3) codeword is sent to the Berlekamp algorithm.
This codeword is decoded, yielding a threesymbol message of DI_{1}I_{2} (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_{1}I_{2} vector.
For additional information, see the ReedSolomon Coding with Erasures, Punctures, and Shortening MATLAB example or the ReedSolomon Coding with Erasures, Punctures, and Shortening in Simulink example.
ReedSolomon Code in Integer Format
To open an example model that uses a ReedSolomon code in integer format, type
doc_rscoding
at the MATLAB command line. For more information about the model, see Example: ReedSolomon Code in Integer Format
Find a Generator Polynomial
To find a generator polynomial for a cyclic, BCH, or ReedSolomon 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
andrsgenpoly
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  A^{b})(X  A^{b+1})...(X  A^{b+2t1}),
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.
Performing Other Block Code Tasks
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.
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}_{\mathrm{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.
Finding the ErrorCorrection Capability
The
bchgenpoly
andrsgenpoly
functions can return an optional second output argument that indicates the errorcorrection capability of a BCH or ReedSolomon 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.
Finding Generator and ParityCheck Matrices
To find a paritycheck and generator matrix for a Hamming code with codeword length
2^m1
, use thehammgen
function as below.m
must be at least three.[parmat,genmat] = hammgen(m); % Hamming
To find a paritycheck 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 thecyclpoly
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
Converting Between ParityCheck and Generator Matrices
The
gen2par
function converts a generator matrix into a paritycheck matrix, and vice versa. The reference page forgen2par
contains examples to illustrate this.
Selected Bibliography for Block Coding
[1] Berlekamp, Elwyn R., Algebraic Coding Theory, New York, McGrawHill, 1968.
[2] Clark, George C. Jr., and J. Bibb Cain, ErrorCorrection 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, PrenticeHall, 1983.
[4] Peterson, W. Wesley, and E. J. Weldon, Jr., ErrorCorrecting Codes, 2nd ed., Cambridge, MA, MIT Press, 1972.
[5] van Lint, J. H., Introduction to Coding Theory, New York, SpringerVerlag, 1982.
[6] Wicker, Stephen B., Error Control Systems for Digital Communication and Storage, Upper Saddle River, NJ, Prentice Hall, 1995.
[7] Gallager, Robert G., LowDensity ParityCheck 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.
Convolutional Codes
Convolutional Code Features
Convolutional coding is a special case of errorcontrol coding. Unlike a block coder, a convolutional coder is not a memoryless device. Even though a convolutional coder accepts a fixed number of message symbols and produces a fixed number of code symbols, its computations depend not only on the current set of input symbols but on some of the previous input symbols.
Communications Toolbox provides convolutional coding capabilities as Simulink blocks, System objects, and MATLAB functions. This product supports feedforward and feedback convolutional codes that can be described by a trellis structure or a set of generator polynomials. It uses the Viterbi algorithm to implement harddecision and softdecision decoding.
The product also includes an a posteriori probability decoder, which can be used for soft output decoding of convolutional codes.
For background information about convolutional coding, see the works listed in Selected Bibliography for Convolutional Coding.
Block Parameters for Convolutional Coding
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 modulo2 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 Design a Rate 2/3 Feedforward Encoder Using Simulink.If you design your encoder using a trellis diagram, you can construct the trellis structure in MATLAB and use it as the mask parameter.
For more information about these representations, see Polynomial Description of a Convolutional Code and Trellis Description of a Convolutional Code.
Using the Polynomial Description in Blocks
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 convolutionalcoding blocks, simply place
a poly2trellis
command such as
poly2trellis(5,[35 31]);
in the Trellis structure parameter field.
Polynomial Description of a Convolutional Code
A polynomial description of a convolutional encoder describes the connections among shift registers and modulo 2 adders. For example, the figure below depicts a feedforward convolutional encoder that has one input, two outputs, and two shift registers.
A polynomial description of a convolutional encoder has either two or three components, depending on whether the encoder is a feedforward or feedback type:
Feedback connection polynomials (for feedback encoders only)
Constraint Lengths. The constraint lengths of the encoder form a vector whose length is the number of inputs in the encoder diagram. The elements of this vector indicate the number of bits stored in each shift register, including the current input bits.
In the figure above, the constraint length is three. It is a scalar because the encoder has one input stream, and its value is one plus the number of shift registers for that input.
Generator Polynomials. If the encoder diagram has k inputs and n outputs, the code generator matrix is a kbyn matrix. The element in the ith row and jth column indicates how the ith input contributes to the jth output.
For systematic bits of a systematic feedback encoder, match the entry in the code generator matrix with the corresponding element of the feedback connection vector. See Feedback Connection Polynomials below for details.
In other situations, you can determine the (i,j) entry in the matrix as follows:
Build a binary number representation by placing a 1 in each spot where a connection line from the shift register feeds into the adder, and a 0 elsewhere. The leftmost spot in the binary number represents the current input, while the rightmost spot represents the oldest input that still remains in the shift register.
Convert this binary representation into an octal representation by considering consecutive triplets of bits, starting from the rightmost bit. The rightmost bit in each triplet is the least significant. If the number of bits is not a multiple of three, place zero bits at the left end as necessary. (For example, interpret 1101010 as 001 101 010 and convert it to 152.)
For example, the binary numbers corresponding to the upper and lower adders in the figure above are 110 and 111, respectively. These binary numbers are equivalent to the octal numbers 6 and 7, respectively, so the generator polynomial matrix is [6 7].
Note
You can perform the binarytooctal conversion in MATLAB by using code like
str2num(dec2base(bin2dec('110'),8))
.
For a table of some good convolutional code generators, refer to [2] in the section Selected Bibliography for Block Coding, especially that book's appendices.
Feedback Connection Polynomials. If you are representing a feedback encoder, you need a vector of feedback connection polynomials. The length of this vector is the number of inputs in the encoder diagram. The elements of this vector indicate the feedback connection for each input, using an octal format. First build a binary number representation as in step 1 above. Then convert the binary representation into an octal representation as in step 2 above.
If the encoder has a feedback configuration and is also systematic, the code generator and feedback connection parameters corresponding to the systematic bits must have the same values.
Use Trellis Structure for Rate 1/2 Feedback Convolutional Encoder
Create a trellis structure to represent the rate 1/2 systematic convolutional encoder with feedback shown in this diagram.
This encoder has 5 for its constraint length, [37 33] as its generator polynomial matrix, and 37 for its feedback connection polynomial.
The first generator polynomial is octal 37. The second generator polynomial is octal 33. The feedback polynomial is octal 37. The first generator polynomial matches the feedback connection polynomial because the first output corresponds to the systematic bits.
The binary vector [1 1 1 1 1] represents octal 37 and corresponds to the upper row of binary digits in the diagram. The binary vector [1 1 0 1 1] represents octal 33 and corresponds to the lower row of binary digits in the diagram. These binary digits indicate connections from the outputs of the registers to the two adders in the diagram. The initial 1 corresponds to the input bit.
Convert the polynomial to a trellis structure by using the poly2trellis
function. When used with a feedback polynomial, poly2trellis
makes a feedback connection to the input of the trellis.
trellis = poly2trellis(5,[37 33],37)
trellis = struct with fields:
numInputSymbols: 2
numOutputSymbols: 4
numStates: 16
nextStates: [16x2 double]
outputs: [16x2 double]
Generate random binary data. Convolutionally encode the data by using the specified trellis structure. Decode the coded data by using the Viterbi algorithm with the specified trellis structure, 34 for its traceback depth, truncated operation mode, and hard decisions.
data = randi([0 1],70,1); codedData = convenc(data,trellis); tbdepth = 34; % Traceback depth for Viterbi decoder decodedData = vitdec(codedData,trellis,tbdepth,'trunc','hard');
Verify the decoded data has zero bit errors.
biterr(data,decodedData)
ans = 0
Using the Polynomial Description in MATLAB. To use the polynomial description with the functions
convenc
and vitdec
, first
convert it into a trellis description using the
poly2trellis
function. For example, the command
below computes the trellis description of the encoder pictured in the
section Polynomial
Description of a Convolutional Code.
trellis = poly2trellis(3,[6 7]);
The MATLAB structure trellis
is a suitable input
argument for convenc
and
vitdec
.
Trellis Description of a Convolutional Code
A trellis description of a convolutional encoder shows how each possible input to the encoder influences both the output and the state transitions of the encoder. This section describes trellises, and how to represent trellises in MATLAB, and gives an example of a MATLAB trellis.
The figure below depicts a trellis for the convolutional encoder from the previous section. The encoder has four states (numbered in binary from 00 to 11), a onebit input, and a twobit output. (The ratio of input bits to output bits makes this encoder a rate1/2 encoder.) Each solid arrow shows how the encoder changes its state if the current input is zero, and each dashed arrow shows how the encoder changes its state if the current input is one. The octal numbers above each arrow indicate the current output of the encoder.
As an example of interpreting this trellis diagram, if the encoder is in the 10 state and receives an input of zero, it outputs the code symbol 3 and changes to the 01 state. If it is in the 10 state and receives an input of one, it outputs the code symbol 0 and changes to the 11 state.
Note that any polynomial description of a convolutional encoder is equivalent to some trellis description, although some trellises have no corresponding polynomial descriptions.
Specifying a Trellis in MATLAB. To specify a trellis in MATLAB, use a specific form of a MATLAB structure called a trellis structure. A trellis structure must have five fields, as in the table below.
Fields of a Trellis Structure for a Rate k/n Code
Field in Trellis Structure  Dimensions  Meaning 

numInputSymbols
 Scalar  Number of input symbols to the encoder: 2^{k} 
numOutputsymbols
 Scalar  Number of output symbols from the encoder: 2^{n} 
numStates
 Scalar  Number of states in the encoder 
nextStates
 numStates by2^{k}
matrix  Next states for all combinations of current state and current input 
outputs
 numStates by2^{k}
matrix  Outputs (in octal) for all combinations of current state and current input 
Note
While your trellis structure can have any name, its fields must have the exact names as in the table. Field names are case sensitive.
In the nextStates
matrix, each entry is an integer
between 0 and numStates
1. The element in the ith row and
jth column denotes the next state when the starting state is i1 and the
input bits have decimal representation j1. To convert the input bits to a
decimal value, use the first input bit as the most significant bit (MSB).
For example, the second column of the nextStates
matrix
stores the next states when the current set of input values is {0,...,0,1}.
To learn how to assign numbers to states, see the reference page for
istrellis
.
In the outputs
matrix, the element in the ith row and
jth column denotes the encoder's output when the starting state is i1 and
the input bits have decimal representation j1. To convert to decimal value,
use the first output bit as the MSB.
How to Create a MATLAB Trellis Structure. Once you know what information you want to put into each field, you can create a trellis structure in any of these ways:
Define each of the five fields individually, using
structurename.fieldname
notation. For example, set the first field of a structure calleds
using the command below. Use additional commands to define the other fields.s.numInputSymbols = 2;
The reference page for the
istrellis
function illustrates this approach.Collect all field names and their values in a single
struct
command. For example:s = struct('numInputSymbols',2,'numOutputSymbols',2,... 'numStates',2,'nextStates',[0 1;0 1],'outputs',[0 0;1 1]);
Start with a polynomial description of the encoder and use the
poly2trellis
function to convert it to a valid trellis structure. For more information , see Polynomial Description of a Convolutional Code.
To check whether your structure is a valid trellis structure, use the
istrellis
function.
Example: A MATLAB Trellis Structure. Consider the trellis shown below.
To build a trellis structure that describes it, use the command below.
trellis = struct('numInputSymbols',2,'numOutputSymbols',4,... 'numStates',4,'nextStates',[0 2;0 2;1 3;1 3],... 'outputs',[0 3;1 2;3 0;2 1]);
The number of input symbols is 2 because the trellis diagram has two types of input path: the solid arrow and the dashed arrow. The number of output symbols is 4 because the numbers above the arrows can be either 0, 1, 2, or 3. The number of states is 4 because there are four bullets on the left side of the trellis diagram (equivalently, four on the right side). To compute the matrix of next states, create a matrix whose rows correspond to the four current states on the left side of the trellis, whose columns correspond to the inputs of 0 and 1, and whose elements give the next states at the end of the arrows on the right side of the trellis. To compute the matrix of outputs, create a matrix whose rows and columns are as in the next states matrix, but whose elements give the octal outputs shown above the arrows in the trellis.
Create and Decode Convolutional Codes
The functions for encoding and decoding convolutional codes are
convenc
and vitdec
. This section
discusses using these functions to create and decode convolutional codes.
Encoding. A simple way to use convenc
to create a convolutional
code is shown in the commands below.
% Define a trellis. t = poly2trellis([4 3],[4 5 17;7 4 2]); % Encode a vector of ones. x = ones(100,1); code = convenc(x,t);
The first command converts a polynomial description of a feedforward
convolutional encoder to the corresponding trellis description. The second
command encodes 100 bits, or 50 twobit symbols. Because the code rate in
this example is 2/3, the output vector code
contains 150
bits (that is, 100 input bits times 3/2).
To check whether your trellis corresponds to a catastrophic convolutional
code, use the iscatastrophic
function.
HardDecision Decoding. To decode using hard decisions, use the vitdec
function with the flag 'hard'
and with
binary input data. Because the output of
convenc
is binary, harddecision decoding can use
the output of convenc
directly, without additional
processing. This example extends the previous example and implements
harddecision decoding.
Define a trellis. t = poly2trellis([4 3],[4 5 17;7 4 2]); Encode a vector of ones. code = convenc(ones(100,1),t); Set the traceback length for decoding and decode using vitdec. tb = 2; decoded = vitdec(code,t,tb,'trunc','hard'); Verify that the decoded data is a vector of 100 ones. isequal(decoded,ones(100,1))
ans = logical 1
SoftDecision Decoding. To decode using soft decisions, use the vitdec
function with the flag 'soft'
. Specify the number,
nsdec
, of softdecision bits and use input data
consisting of integers between 0 and 2^nsdec1
.
An input of 0 represents the most confident 0, while an input of
2^nsdec1
represents the most confident 1. Other
values represent less confident decisions. For example, the table below
lists interpretations of values for 3bit soft decisions.
Input Values for 3bit Soft Decisions
Input Value  Interpretation 

0  Most confident 0 
1  Second most confident 0 
2  Third most confident 0 
3  Least confident 0 
4  Least confident 1 
5  Third most confident 1 
6  Second most confident 1 
7  Most confident 1 
Implement SoftDecision Decoding Using MATLAB
The script below illustrates decoding with 3bit soft decisions. First it
creates a convolutional code with convenc
and adds
white Gaussian noise to the code with awgn
. Then, to
prepare for softdecision decoding, the example uses
quantiz
to map the noisy data values to appropriate
decisionvalue integers between 0 and 7. The second argument in
quantiz
is a partition vector that determines which
data values map to 0, 1, 2, etc. The partition is chosen so that values near
0 map to 0, and values near 1 map to 7. (You can refine the partition to
obtain better decoding performance if your application requires it.)
Finally, the example decodes the code and computes the bit error rate. When
comparing the decoded data with the original message, the example must take
the decoding delay into account. The continuous operation mode of
vitdec
causes a delay equal to the traceback
length, so msg(1)
corresponds to
decoded(tblen+1)
rather than to
decoded(1)
.
s = RandStream.create('mt19937ar', 'seed',94384); prevStream = RandStream.setGlobalStream(s); msg = randi([0 1],4000,1); % Random data t = poly2trellis(7,[171 133]); % Define trellis. % Create a ConvolutionalEncoder System object hConvEnc = comm.ConvolutionalEncoder(t); % Create an AWGNChannel System object. hChan = comm.AWGNChannel('NoiseMethod', 'Signal to noise ratio (SNR)',... 'SNR', 6); % Create a ViterbiDecoder System object hVitDec = comm.ViterbiDecoder(t, 'InputFormat', 'Soft', ... 'SoftInputWordLength', 3, 'TracebackDepth', 48, ... 'TerminationMethod', 'Continuous'); % Create a ErrorRate Calculator System object. Account for the receive % delay caused by the traceback length of the viterbi decoder. hErrorCalc = comm.ErrorRate('ReceiveDelay', 48); ber = zeros(3,1); % Store BER values code = step(hConvEnc,msg); % Encode the data. hChan.SignalPower = (code'*code)/length(code); ncode = step(hChan,code); % Add noise. % Quantize to prepare for softdecision decoding. qcode = quantiz(ncode,[0.001,.1,.3,.5,.7,.9,.999]); tblen = 48; delay = tblen; % Traceback length decoded = step(hVitDec,qcode); % Decode. % Compute bit error rate. ber = step(hErrorCalc, msg, decoded); ratio = ber(1) number = ber(2) RandStream.setGlobalStream(prevStream);
The output is below.
number = 5 ratio = 0.0013
Implement SoftDecision Decoding Using Simulink. This example creates a rate 1/2 convolutional code. It uses a quantizer
and the Viterbi Decoder block to perform softdecision decoding. To open the
model, enter doc_softdecision
at the MATLAB command line. For a description of the model, see Overview
of the Simulation.
Defining the Convolutional Code
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 1by2 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 modulo2 sum of the rightmost and the four leftmost elements in the diagram's array of input values. The sevendigit 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.
Mapping the Received Data
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, doubleclick the icon labeled SoftOutput BPSK Demodulator.
Decoding the Convolutional Code
After the received data is properly mapped to length2 vectors of 3bit
decision values, the Viterbi Decoder block decodes it. The block uses a
softdecision algorithm with 2^{3} different input
values because the Decision type parameter is
Soft Decision
and the Number of
soft decision bits parameter is 3
.
SoftDecision Interpretation of Data
When the Decision type parameter is set to
Soft Decision
, the Viterbi Decoder block
requires input values between 0 and 2^{b}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
2^{b}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 influences the decoding delay. The decoding delay is the number of zero symbols that precede the first decoded symbol in the output.
For the continuous operating mode, the decoding delay is equal to the number of traceback depth symbols.
For the truncated or terminated operating mode, the decoding delay is zero. In this case, the traceback depth must be less than or equal to the number of symbols in each input.
Traceback Depth Estimate
As a general estimate, a typical traceback depth value is approximately two
to three times (ConstraintLength – 1) / (1 –
coderate). The constraint length of the code, ConstraintLength,
is equal to (log2(trellis
.numStates
) +
1). The coderate is equal to (K / N) ×
(length(PuncturePattern) /
sum(PuncturePattern).
K is the number of input symbols, N is the number of output symbols, and PuncturePattern is the puncture pattern vector.
For example, applying this general estimate, results in these approximate traceback depths.
A rate 1/2 code has a traceback depth of 5(ConstraintLength – 1).
A rate 2/3 code has a traceback depth of 7.5(ConstraintLength – 1).
A rate 3/4 code has a traceback depth of 10(ConstraintLength – 1).
A rate 5/6 code has a traceback depth of 15(ConstraintLength – 1).
The Traceback depth parameter in the Viterbi Decoder block represents the length of the decoding delay. Some hardware implementations offer options of 48 and 96. This example chooses 48 because that is closer to the estimated target for a rate ½ code with a constraint length of 7.
Delay in Received Data
The Receive delay parameter of the Error Rate Calculation block 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 (48).
Comparing Simulation Results with Theoretical Results
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 these steps
Computing Theoretical Bounds for the Bit Error Rate
To calculate theoretical bounds for the bit error rate P_{b} of the convolutional code in this model, you can use this estimate based on unquantizeddecision decoding:
$${P}_{b}<{\displaystyle \sum _{d=f}^{\infty}{c}_{d}{P}_{d}}$$
In this estimate, c_{d} is the sum of bit errors for error events of distance d, and f is the free distance of the code. The quantity P_{d} is the pairwise error probability, given by
$${P}_{d}=\frac{1}{2}\mathrm{erfc}\left(\sqrt{dR\frac{{E}_{b}}{{N}_{0}}}\right)$$
where R is the code rate of 1/2, and
erfc
is the MATLAB complementary error function, defined by$$\mathrm{erfc}(x)=\frac{2}{\sqrt{\pi}}{\displaystyle \underset{x}{\overset{\infty}{\int}}{e}^{{t}^{2}}dt}$$
Values for the coefficients c_{d} and the free distance f are in published articles such as "Convolutional Codes with Optimum Distance Spectrum" [3]. The free distance for this code is f = 10.
The following commands calculate the values of P_{b} for E_{b}/N_{0} values in the range from 1 to 4, 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(d9,:) = (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
(Simulink) function to run the simulation from the MATLAB command line. For example, the following code calculates the bit error rate at bit energytonoise 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 matrixBERVec
. It also plots the bit error rates in a figure window along with the theoretical bounds computed in the preceding code fragment.Note
To model the model, enter
doc_softdecision
at the MATLAB command line. 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 1e5 1]); hold on; BERVec = []; % 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); BERVec(n,:) = BER_Data; semilogy(EbNoVec(n),BERVec(n,1),'r*'); % Plot point. drawnow; end hold off;
Note
The estimate for P_{b} assumes that the decoder uses unquantized data, that is, an infinitely fine quantization. By contrast, the simulation in this example uses 8level (3bit) quantization. Because of this quantization, the simulated bit error rate is not quite as low as the bound when the signaltonoise ratio is high.
The plot of bit error rate against signaltonoise ratio follows. The locations of your actual BER points might vary because the simulation involves random numbers.
Design a Rate2/3 Feedforward Encoder Using MATLAB
The example below uses the rate 2/3 feedforward encoder depicted in this schematic. The accompanying description explains how to determine the trellis structure parameter from a schematic of the encoder and then how to perform coding using this encoder.
Determining Coding Parameters. The convenc
and vitdec
functions
can implement this code if their parameters have the appropriate
values.
The encoder's constraint length is a vector of length 2 because the encoder has two inputs. The elements of this vector indicate the number of bits stored in each shift register, including the current input bits. Counting memory spaces in each shift register in the diagram and adding one for the current inputs leads to a constraint length of [5 4].
To determine the code generator parameter as a 2by3 matrix of octal numbers, use the element in the ith row and jth column to indicate how the ith input contributes to the jth output. For example, to compute the element in the second row and third column, the leftmost and two rightmost elements in the second shift register of the diagram feed into the sum that forms the third output. Capture this information as the binary number 1011, which is equivalent to the octal number 13. The full value of the code generator matrix is [23 35 0; 0 5 13].
To use the constraint length and code generator parameters in the
convenc
and vitdec
functions,
use the poly2trellis
function to convert those
parameters into a trellis structure. The command to do this is below.
trel = poly2trellis([5 4],[23 35 0;0 5 13]); % Define trellis.
Using the Encoder. Below is a script that uses this encoder.
len = 1000; msg = randi([0 1],2*len,1); % Random binary message of 2bit symbols trel = poly2trellis([5 4],[23 35 0;0 5 13]); % Trellis % Create a ConvolutionalEncoder System object hConvEnc = comm.ConvolutionalEncoder(trel); % Create a ViterbiDecoder System object hVitDec = comm.ViterbiDecoder(trel, 'InputFormat', 'hard', ... 'TracebackDepth', 34, 'TerminationMethod', 'Continuous'); % Create a ErrorRate Calculator System object. Since each symbol represents % two bits, the receive delay for this object is twice the traceback length % of the viterbi decoder. hErrorCalc = comm.ErrorRate('ReceiveDelay', 68); ber = zeros(3,1); % Store BER values code = step(hConvEnc,msg); % Encode the message. ncode = rem(code + randerr(3*len,1,[0 1;.96 .04]),2); % Add noise. decoded = step(hVitDec, ncode); % Decode. ber = step(hErrorCalc, msg, decoded);
convenc
accepts a vector containing 2bit symbols and
produces a vector containing 3bit symbols, while
vitdec
does the opposite. Also notice that
biterr
ignores the first 68 elements of
decoded
. That is, the decoding delay is 68, which is
the number of bits per symbol (2) of the recovered message times the
traceback depth value (34) in the vitdec
function. The
first 68 elements of decoded
are 0s, while subsequent
elements represent the decoded messages.
Design a Rate 2/3 Feedforward Encoder Using Simulink
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.
How to Determine Coding Parameters. 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 2by3 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.
How to Simulate the Encoder. The following model simulates this encoder.
To open the completed model, enter doc_convcoding
at
the MATLAB command line. 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
randn
function.Set Sample time to
.5
.Check the Framebased 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
randn
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 (Simulink), 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 shown in the preceding figure. On the
Simulation tab, in the
Simulate section, set Stop
time to inf
. The
Simulate section appears on multiple
tabs.
Notes on the Model. You can display the matrix size of signals in your model. On the Debug tab, expand Information Overlays. In the Signals section, select Signal Dimensions.
The encoder accepts a 2by1 column vector and produces a 3by1 column 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.
Puncture a Convolutional Code Using MATLAB
This example processes a punctured convolutional code. It begins by generating
30,000 random bits and encoding them using a rate3/4 convolutional encoder with
a puncture pattern of [1 1 1 0 0 1]. The resulting vector contains 40,000 bits,
which are mapped to values of 1 and 1 for transmission. The punctured code,
punctcode
, passes through an additive white Gaussian
noise channel. Then vitdec
decodes the noisy vector using
the 'unquant'
decision type.
Finally, the example computes the bit error rate and the number of bit errors.
len = 30000; msg = randi([0 1], len, 1); % Random data t = poly2trellis(7, [133 171]); % Define trellis. % Create a ConvolutionalEncoder System object hConvEnc = comm.ConvolutionalEncoder(t, ... 'PuncturePatternSource', 'Property', ... 'PuncturePattern', [1;1;1;0;0;1]); % Create an AWGNChannel System object. hChan = comm.AWGNChannel('NoiseMethod', 'Signal to noise ratio (SNR)',... 'SNR', 3); % Create a ViterbiDecoder System object hVitDec = comm.ViterbiDecoder(t, 'InputFormat', 'Unquantized', ... 'TracebackDepth', 96, 'TerminationMethod', 'Truncated', ... 'PuncturePatternSource', 'Property', ... 'PuncturePattern', [1;1;1;0;0;1]); % Create a ErrorRate Calculator System object. hErrorCalc = comm.ErrorRate; berP = zeros(3,1); berPE = berP; % Store BER values punctcode = step(hConvEnc,msg); % Length is (2*len)*2/3. tcode = 12*punctcode; % Map "0" bit to 1 and "1" bit to 1 hChan.SignalPower = (tcode'*tcode)/length(tcode); ncode = step(hChan,tcode); % Add noise. % Decode the punctured code decoded = step(hVitDec,ncode); % Decode. berP = step(hErrorCalc, msg, decoded);% Bit error rate % Erase the least reliable 100 symbols, then decode release(hVitDec); reset(hErrorCalc) hVitDec.ErasuresInputPort = true; [dummy idx] = sort(abs(ncode)); erasures = zeros(size(ncode)); erasures(idx(1:100)) = 1; decoded = step(hVitDec,ncode, erasures); % Decode. berPE = step(hErrorCalc, msg, decoded);% Bit error rate fprintf('Number of errors with puncturing: %d\n', berP(2)) fprintf('Number of errors with puncturing and erasures: %d\n', berPE(2))
Implement a Systematic Encoder with Feedback Using Simulink
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 Code.
SoftDecision Decoding
This example creates a rate 1/2 convolutional code. It uses a quantizer and the Viterbi Decoder block to perform softdecision decoding. This description covers these topics:
Overview of the Simulation. The model is in the following figure. To open the model, enter
doc_softdecision
at the MATLAB command line. 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
Convolutional encoder is configured as a rate 1/2 encoder. For every 2 bits,
the encoder adds another 2 redundant bits. To accommodate this, and add the
correct amount of noise, the Eb/No (dB) parameter of
the AWGN block is in effect halved by subtracting 10*log10(2). The
simulation ends after processing 100 bit errors or
10^{7} message bits, whichever comes
first.
Defining the Convolutional Code. 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 1by2 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 modulo2 sum of the rightmost and the four leftmost elements in the diagram's array of input values. The sevendigit 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.
Mapping the Received Data. 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, doubleclick the icon labeled SoftOutput BPSK Demodulator.
Decoding the Convolutional Code. After the received data is properly mapped to length2 vectors of 3bit
decision values, the Viterbi Decoder block decodes it. The block uses a
softdecision algorithm with 2^{3} different input
values because the Decision type parameter is
Soft Decision
and the Number of
soft decision bits parameter is 3
.
SoftDecision Interpretation of Data
When the Decision type parameter is set to
Soft Decision
, the Viterbi Decoder block
requires input values between 0 and 2^{b}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
2^{b}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.
Delay in Received Data. The Receive delay parameter of the Error Rate Calculation block 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 (48).
Comparing Simulation Results with Theoretical Results. 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 P_{b} of the convolutional code in this model, you can use this estimate based on unquantizeddecision decoding:
$${P}_{b}<{\displaystyle \sum _{d=f}^{\infty}{c}_{d}{P}_{d}}$$
In this estimate, c_{d} is the sum of bit errors for error events of distance d, and f is the free distance of the code. The quantity P_{d} is the pairwise error probability, given by
$${P}_{d}=\frac{1}{2}\mathrm{erfc}\left(\sqrt{dR\frac{{E}_{b}}{{N}_{0}}}\right)$$
where R is the code rate of 1/2, and erfc
is the MATLAB complementary error function, defined by
$$\mathrm{erfc}(x)=\frac{2}{\sqrt{\pi}}{\displaystyle \underset{x}{\overset{\infty}{\int}}{e}^{{t}^{2}}dt}$$
Values for the coefficients c_{d} and the free distance f are in published articles such as "Convolutional Codes with Optimum Distance Spectrum" [3]. The free distance for this code is f = 10.
The following commands calculate the values of P_{b} for E_{b}/N_{0} values in the range from 1 to 4, 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(d9,:) = (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
(Simulink) function to run the
simulation from the MATLAB command line. For example, the following code calculates the
bit error rate at bit energytonoise 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
To open the model, enter doc_softdecision
at the
MATLAB command line. 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 1e5 1]); hold on; BERVec = []; % 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); BERVec(n,:) = BER_Data; semilogy(EbNoVec(n),BERVec(n,1),'r*'); % Plot point. drawnow; end hold off;
Note
The estimate for P_{b} assumes that the decoder uses unquantized data, that is, an infinitely fine quantization. By contrast, the simulation in this example uses 8level (3bit) quantization. Because of this quantization, the simulated bit error rate is not quite as low as the bound when the signaltonoise ratio is high.
The plot of bit error rate against signaltonoise ratio follows. The locations of your actual BER points might vary because the simulation involves random numbers.
Tailbiting Encoding Using Feedback Encoders
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 zerostate response for a given block of data. The encoder starts in the allzeros state. The whole block of data is input and the output bits are ignored. After N bits, the encoder is in a state X_{N} ^{[zs]}. From this state, we calculate the corresponding initial state X_{0} and initialize the encoder with X_{0}.
The second step is the actual encoding. The encoder starts with the initial state X_{0}, 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 X_{0} from X_{N} ^{[zs]} using statespace formulation. This is a onetime calculation which depends on the block length and in practice could be implemented as a lookup table. Here we determine this mapping table by simulating all possible entries for a chosen trellis and block length.
To open the model, enter doc_mtailbiting_wfeedback
at the
MATLAB command line.
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 zerostate response. % All possible combinations of the mappings mapStValuesTab = perms(0:trellis.numStates1); % 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'); % Check the boundary condition for each run % if ending and starting states match, choose that mapping set if unique(out)==0 return end end
Selecting the returned mapStValues
for the Table
data parameter of the Direct Lookup Table
(nD)
block in the Lookup subsystem will perform tailbiting
encoding for the chosen block length and trellis.
Selected Bibliography for Convolutional Coding
[1] Clark, George C. Jr., and J. Bibb Cain, ErrorCorrection Coding for Digital Communications, New York, Plenum Press, 1981.
[2] Gitlin, Richard D., Jeremiah F. Hayes, and Stephen B. Weinstein, Data Communications Principles, New York, Plenum Press, 1992.
[3] Frenger, P., P. Orten, and T. Ottosson. “Convolutional Codes with Optimum Distance Spectrum.” IEEE Communications Letters 3, no. 11 (November 1999): 317–19. https://doi.org/10.1109/4234.803468.
Linear Block Codes
Represent Words for Linear Block Codes
The cyclic, Hamming, and generic linear block code functionality in this product offers you multiple ways to organize bits in messages or codewords. These topics explain the available formats:
Use MATLAB to Create Messages and Codewords in Binary Vector Format
Use MATLAB to Create Messages and Codewords in Binary Matrix Format
Use MATLAB to Create Messages and Codewords in Decimal Vector Format
To learn how to represent words for BCH or ReedSolomon codes, see Represent Words for BCH Codes or Represent Words for ReedSolomon Codes.
Use MATLAB to Create Messages and Codewords in Binary Vector
Format. 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 4digit (because k
= 4)
messages. The resulting vector code
comprises three
6digit (because n
= 6) codewords, which are
concatenated to form a vector of length 18. The parity bits are at the
beginning of each codeword.
Use MATLAB to Create Messages and Codewords in Binary Matrix
Format. 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 4bit message on a distinct row in
msg
and each 6bit 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.
Use MATLAB to Create Messages and Codewords in Decimal Vector Format. 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.
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. 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 
ParityCheck Matrix  Generic linear block 
Generator Polynomial  Cyclic 
Use Decoding Table in MATLAB  Generic linear block, Hamming 
Generator Matrix. The process of encoding a message into an [n,k] linear block code is determined by a kbyn generator matrix G. Specifically, the 1byk message vector v is encoded into the 1byn codeword vector vG. If G has the form [I_{k} P] or [P I_{k}], where P is some kby(nk) matrix and I_{k} is the kbyk 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, ParityCheck Matrix.
ParityCheck Matrix. Decoding an [n,k] linear block code requires an (nk)byn paritycheck
matrix H. It satisfies
GH^{tr}
= 0 (mod
2), where H^{tr} denotes the matrix transpose of H,
G is the code's generator matrix, and this zero matrix is kby(nk). If
G = [I_{k} P] then
H = [P^{tr} I_{nk}].
Most functions in this product assume that a paritycheck matrix is in
standard form when you use it as an input argument.
The table below summarizes the standard forms of the generator and paritycheck matrices for an [n,k] binary linear block code.
Type of Matrix  Standard Form  Dimensions 

Generator  [I_{k} P] or [P I_{k}]  kbyn 
Paritycheck  [P'
I_{nk}] or
[I_{nk} P'
]  (nk)byn 
I_{k} is the identity matrix of size k and the
'
symbol indicates matrix transpose. (For
binary codes, the minus signs in the paritycheck
form listed above are irrelevant; that is, 1 = 1 in the binary
field.)
Examples
In the command below, parmat
is a paritycheck matrix
and genmat
is a generator matrix for a Hamming code in
which
[n,k] = [2^{3}1, n3] = [7,4].
genmat
has the standard form
[P I_{k}].
[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 paritycheck 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 paritycheck 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
paritycheck matrix into a generator matrix.
Generator Polynomial. Cyclic codes have algebraic properties that allow a polynomial to determine the coding process completely. This socalled generator polynomial is a degree(nk) divisor of the polynomial x^{n}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 + x^{2} + x^{3} + x^{4}.
Use Decoding Table in MATLAB
A decoding table tells a decoder how to correct errors that might have corrupted the code during transmission. Hamming codes can correct any singlesymbol 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^(nk) 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 paritycheck matrix.
This example uses a Hamming decoding table to correct an error in a received message. The hammgen
function produces the paritycheck matrix and the syndtable
function produces the decoding table. To determine the syndrome, the transpose of the paritycheck matrix is multiplied on the left 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^m1; k = nm;
Produce a paritycheck 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 value 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^(nk),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 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:
Replace the second line by
genpoly = [1 0 1]; % generator poly is 1 + x^2
In the fifth and ninth lines (
encode
anddecode
commands), replacegenmat
bygenpoly
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 Use Decoding Table in MATLAB illustrates error
correction in a Hamming code.
Hamming Codes
Create a Hamming Code in Binary Format Using Simulink
This example shows very simply how to use an encoder and decoder. It illustrates the appropriate vector lengths of the code and message signals for the coding blocks. Because the Error Rate Calculation block accepts only scalars or framebased column vectors as the transmitted and received signals, this example uses framebased column vectors throughout. (It thus avoids having to change signal attributes using a block such as Convert 1D to 2D.)
Open this model by entering doc_hamming
at the
MATLAB command line. 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
randn
function.Check the Framebased outputs check box.
Set Samples per frame to
4
.
Hamming Encoder, with default parameter values
Hamming Decoder, with default parameter values
Error Rate Calculation, in the Comm Sinks library, with default parameter values
Connect the blocks as in the preceding figure. You can display the vector length of signals in your model. On the Debug tab, expand Information Overlays. In the Signals section, select Signal Dimensions. After updating the diagram, if necessary, press Ctrl+D to compile the model and check error statistics.
The connector lines show relevant signal attributes. The connector lines are double lines to indicate framebased signals, and the annotations next to the lines show that the signals are column vectors of appropriate sizes.
Reduce the Error Rate Using a Hamming Code
This section describes how to reduce the error rate by adding an errorcorrecting code. This figure shows model that uses a Hamming code.
To open a complete version of the model, enter doc_hamming
at the MATLAB prompt.
Building the Hamming Code Model
You can build the Hamming code model by following these steps:
Type
doc_channel
at the MATLAB command line to open the channel noise model.Then save the model as
my_hamming
in the folder where you keep your work files.From the Simulink Library Browser drag the Hamming Encoder and Hamming Decoder blocks from the Error Detection and Correction/Block sublibrary into the model window.
Click the right border of the model and drag it to the right to widen the model window.
Move the Binary Symmetric Channel, Error Rate Calculation, and Display (Simulink) blocks to the right by clicking and dragging.
Create enough space between the Bernoulli Binary Generator and Binary Symmetric Channel blocks to fit the Hamming Encoder between them.
Click and drag the Hamming Encoder block on top of the line between the Bernoulli Binary Generator block and the Binary Symmetric Channel block, to the right of the branch point, as shown in the following figure. Then release the mouse button. The Hamming Encoder block should automatically connect to the line from the Bernoulli Binary Generator block to the Binary Symmetric Channel block.
Move blocks again to create enough space between the Binary Symmetric Channel and the Error Rate Calculation blocks to fit the Hamming Decoder between them.
Click and drag the Hamming Decoder block on top of the line between the Binary Symmetric Channel block and the Error Rate Calculation block.
The model should now resemble this figure.
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
Doubleclick 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:
Set Samples per frame to
4
. This converts the output of the block into frames of size 4, in order to meet the input requirement of the Hamming Encoder Block. See SampleBased and FrameBased Processing for more information about frames.Note
Many blocks, such as the Hamming Encoder block, require their input to be a vector of a specific size. If you connect a source block, such as the Bernoulli Binary Generator block, to one of these blocks, set Samples per frame to the required value. For this model the Samples per frame parameter of the Bernoulli Binary Generator block must be a multiple of the Message Length K parameter of the Hamming Encoder block.
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
1 – (0.99)^{7} – 7(0.99)^{6}(0.01) = 0.002
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:
Drag the following blocks from the Simulink Library Browser into the model window:
Relational Operator (Simulink) block, from the Simulink Logic and Bit Operations library
Scope (Simulink) block, from the Simulink Sinks library
Two copies of the Unbuffer block, from the Buffers sublibrary of the Signal Management library in DSP System Toolbox™
Doubleclick the Binary Symmetric Channel block to open its dialog box, and select Output error vector. This creates a second output port for the block, which carries the error vector.
Doubleclick the Scope block, under View > Configuration Properties, set Number of input ports to
2
. Select Layout and highlight two blocks vertically. Click OK.Connect the blocks as shown in the preceding figure.
Setting Parameters in the Expanded Model
Make the following changes to the parameters for the blocks you added to the model.
Error Rate Calculation Block – Doubleclick the Error Rate Calculation block and clear the box next to Stop simulation in the block's dialog box.
Scope Block – The Scope (Simulink) block displays the channel errors and uncorrected errors. To configure the block,
Doubleclick the Scope block, select View > Configuration Properties.
Select the Time tab and set Time span to
5000
.Select the Logging tab and set Limit data points to last to
30000
.Click OK.
The scope should now appear as shown.
To configure the axes, follow these steps:
Rightclick the vertical axis at the left side of the upper scope.
In the context menu, select Configuration Properties.
Set Ylimits (Minimum) to
1
.Set Ylimits (Maximum) to
2
, and click OK.Repeat the same steps for the vertical axis of the lower scope.
Widen the scope window until it is roughly three times as wide as it is high. You can do this by clicking the right border of the window and dragging the border to the right, while pressing the leftmouse button.
Relational Operator – Set Relational Operator to
~=
in the block's dialog box. The Relational Operator block compares the transmitted signal, coming from the Bernoulli Random Generator block, with the received signal, coming from the Hamming Decoder block. The block outputs a 0 when the two signals agree and a 1 when they disagree.
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.
BCH Codes
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.
The example below illustrates how to represent words for a [15, 11] BCH code.
msg = [1 0 0 1 0; 1 0 1 1 1]; % Messages in a Galois array
obj = comm.BCHEncoder;
c1 = step(obj, msg(1,:)');
c2 = step(obj, msg(2,:)');
cbch = [c1 c2].'
The output is
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
Parameters for BCH Codes
BCH codes use special values of n
and
k
:
n
, the codeword length, is an integer of the form 2^{m}1 for some integer m > 2.k
, the message length, is a positive integer less thann
. However, only some positive integers less thann
are valid choices fork
. See the BCH Encoder block reference page for a list of some valid values ofk
corresponding to values ofn
up to 511.
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.
The topics are
Example: BCH Coding Syntaxes. The example below illustrates how to encode and decode data using a [15, 5] BCH code.
n = 15; k = 5; % Codeword length and message length msg = randi([0 1],4*k,1); % Four random binary messages % Simplest syntax for encoding enc = comm.BCHEncoder(n,k); dec = comm.BCHDecoder(n,k); c1 = step(enc,msg); % BCH encoding d1 = step(dec,c1); % BCH decoding % Check that the decoding worked correctly. chk = isequal(d1,msg) % The following code shows how to perform the encoding and decoding % operations if one chooses to prepend the parity symbols. % Steps for converting encoded data with appended parity symbols % to encoded data with prepended parity symbols c11 = reshape(c1, n, []); c12 = circshift(c11,nk); c1_prepend = c12(:); % BCH encoded data with prepended parity symbols % Steps for converting encoded data with prepended parity symbols % to encoded data with appended parity symbols prior to decoding c21 = reshape(c1_prepend, n, []); c22 = circshift(c21,k); c1_append = c22(:); % BCH encoded data with appended parity symbols % Check that the prependtoappend conversion worked correctly. d1_append = step(dec,c1_append); chk = isequal(msg,d1_append)
The output is below.
chk = 1
Detect and Correct Errors in a BCH Code Using MATLAB. The following example illustrates the decoding results for a corrupted
code. The example encodes some data, introduces errors in each codeword, and
attempts to decode the noisy code using the BCH
Decoder
System object.
n = 15; k = 5; % Codeword length and message length [gp,t] = bchgenpoly(n,k); % t is errorcorrection capability. nw = 4; % Number of words to process msgw = randi([0 1], nw*k, 1); % Random ksymbol messages enc = comm.BCHEncoder(n,k,gp); dec = comm.BCHDecoder(n,k,gp); c = step(enc, msgw); % Encode the data. noise = randerr(nw,n,t); % t errors per codeword noisy = noise'; noisy = noisy(:); cnoisy = mod(c + noisy,2); % Add noise to the code. [dc, nerrs] = step(dec, cnoisy); % Decode cnoisy. % Check that the decoding worked correctly. chk2 = isequal(dc,msgw) nerrs % Find out how many errors have been 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 field 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 3
Excessive Noise in BCH Codewords
In the previous example, the BCH Decoder
System object corrected all the errors. However, each BCH code has a finite
errorcorrection capability. To learn more about how the BCH Decoder
System object behaves when the noise is excessive, see the analogous
discussion for ReedSolomon codes in Excessive Noise in ReedSolomon Codewords.
Algorithms for BCH and RS Errorsonly Decoding
Overview. The errorsonly 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]).
Calculate the first 2t terms of the infinite degree syndrome polynomial, $$S(z)$$.
If those 2t terms of $$S(z)$$ are all equal to 0, then the code has no errors , no correction needs to be performed, and the decoding algorithm ends.
If one or more terms of $$S(z)$$ are nonzero, calculate the error locator polynomial, Λ(z), via the Berlekamp algorithm.
Calculate the error evaluator polynomial, $$\Omega \left(z\right)$$, via
$$\Lambda \left(z\right)S\left(z\right)=\Omega \left(z\right)\mathrm{mod}{z}^{2t}$$
Correct an error in the codeword according to
$${e}_{{i}_{m}}=\frac{\Omega ({\alpha}^{{i}_{m}})}{\Lambda \text{'}({\alpha}^{{i}_{m}})}$$
where $${e}_{{i}_{m}}$$ is the error magnitude in the $${i}_{m}$$th position in the codeword, m is a value less than the errorcorrecting capability of the code, $$\Omega \left(z\right)$$ is the error magnitude polynomial, Λ'(z) is the formal derivative [5] of the error locator polynomial, Λ(z), and α is the primitive element of the Galois field of the code.
Further description of several of the steps is given in the following sections.
Syndrome Calculation. For narrowsense codes, the 2t terms of $$S(z)$$ are calculated by evaluating the received codeword at successive powers of α (the field’s primitive element) from 0 to 2t1. In other words, if we assume onebased indexing of codewords $$C(z)$$ and the syndrome polynomial $$S(z)$$, and that codewords are of the form $$[{c}_{1}\text{}{c}_{1}\text{}\mathrm{...}\text{}{c}_{N}]$$, then each term $${S}_{i}$$ of $$S(z)$$ is given as
$${S}_{i}={\displaystyle \sum _{i=1}^{N}{c}_{i}}{\alpha}^{N1i}$$
Error Locator Polynomial Calculation. The error locator polynomial, Λ(z), is found using the Berlekamp algorithm. A complete description of this algorithm is found in [2], but we summarize the algorithm as follows.
We define the following variables.
Variable  Description 

n  Iterator variable 
k  Iterator variable 
L  Length of the feedback register used to generate the first 2t terms of $$S(z)$$ 
D(z)  Correction polynomial 
d  Discrepancy 
The following diagram shows the iterative procedure (i.e., the Berlekamp algorithm) used to find Λ(z).
Error Evaluator Polynomial Calculation. The error evaluator polynomial, $$\Omega \left(z\right)$$, is simply the convolution of Λ(z) and $$S(z)$$.
ReedSolomon Codes
Represent Words for ReedSolomon Codes
This toolbox supports ReedSolomon codes that use mbit symbols instead of
bits. A message for an [n
,k
] ReedSolomon
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.
Note
For information about Galois field 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] ReedSolomon 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 ReedSolomon Codes
This section describes several integers related to ReedSolomon 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 ReedSolomon codes as supported in
this toolbox. The quantities n
and k
are input parameters for ReedSolomon 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 2^{m}1 
k  Number of symbols per message  Positive integer less than
n , such that
nk is even 
t  Errorcorrection capability of the code  (nk)/2 
Generator Polynomial. The rsgenpoly
function produces generator polynomials
for ReedSolomon 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] ReedSolomon code is X^{2} + (A^{2} + A)X + (A^{3}), 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+2t1}),
where b is an integer, A is a root of the primitive polynomial for the
Galois field, and t is (nk)/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] ReedSolomon 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 ReedSolomon Codes
The RS Encoder
and RS Decoder
System objects create and decode ReedSolomon codes,
using the data described in Represent Words for ReedSolomon Codes and Parameters for ReedSolomon Codes.
This section illustrates how to use the RS
Encoder
and RS Decoder
System
objects. The topics are
ReedSolomon Coding Syntaxes in MATLAB. The example below illustrates multiple ways to encode and decode data using a [15,13] ReedSolomon 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 the RS Encoder
and RS
Decoder
System objects use the same input arguments, except
for the first input argument.
m = 4; % Number of bits in each symbol n = 2^m1; k = 13; % Codeword length and message length msg = randi([0 m1],4*k,1); % Four random integer messages % Simplest syntax for encoding hEnc = comm.RSEncoder(n,k); hDec = comm.RSDecoder(n,k); c1 = step(hEnc, msg); d1 = step(hDec, c1); % Vary the generator polynomial for the code. release(hEnc), release(hDec) hEnc.GeneratorPolynomialSource = 'Property'; hDec.GeneratorPolynomialSource = 'Property'; hEnc.GeneratorPolynomial = rsgenpoly(n,k,19,2); hDec.GeneratorPolynomial = rsgenpoly(n,k,19,2); c2 = step(hEnc, msg); d2 = step(hDec, c2); % Vary the primitive polynomial for GF(16). release(hEnc), release(hDec) hEnc.PrimitivePolynomialSource = 'Property'; hDec.PrimitivePolynomialSource = 'Property'; hEnc.GeneratorPolynomialSource = 'Auto'; hDec.GeneratorPolynomialSource = 'Auto'; hEnc.PrimitivePolynomial = [1 1 0 0 1]; hDec.PrimitivePolynomial = [1 1 0 0 1]; c3 = step(hEnc, msg); d3 = step(hDec, c3); % Check that the decoding worked correctly. chk = isequal(d1,msg) & isequal(d2,msg) & isequal(d3,msg) % The following code shows how to perform the encoding and decoding % operations if one chooses to prepend the parity symbols. % Steps for converting encoded data with appended parity symbols % to encoded data with prepended parity symbols c31 = reshape(c3, n, []); c32 = circshift(c31,nk); c3_prepend = c32(:); % RS encoded data with prepended parity symbols % Steps for converting encoded data with prepended parity symbols % to encoded data with appended parity symbols prior to decoding c34 = reshape(c3_prepend, n, []); c35 = circshift(c34,k); c3_append = c35(:); % RS encoded data with appended parity symbols % Check that the prependtoappend conversion worked correctly. d3_append = step(hDec,c3_append); chk = isequal(msg,d3_append)
The output is
chk = 1
Detect and Correct Errors in a ReedSolomon Code Using MATLAB. The example below illustrates the decoding results for a corrupted code.
The example encodes some data, introduces errors in each codeword, and
attempts to decode the noisy code using the RS
Decoder
System object.
m = 3; % Number of bits per symbol n = 2^m1; k = 3; % Codeword length and message length t = (nk)/2; % Errorcorrection capability of the code nw = 4; % Number of words to process msgw = randi([0 n],nw*k,1); % Random ksymbol messages hEnc = comm.RSEncoder(n,k); hDec = comm.RSDecoder(n,k); c = step(hEnc, msgw); % Encode the data. noise = (1+randi([0 n1],nw,n)).*randerr(nw,n,t); % t errors per codeword noisy = noise'; noisy = noisy(:); cnoisy = gf(c,m) + noisy; % Add noise to the code under gf(m) arithmetic. [dc nerrs] = step(hDec, cnoisy.x); % Decode the noisy code. % Check that the decoding worked correctly. isequal(dc,msgw) nerrs % Find out how many errors hDec 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
field 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
Excessive Noise in ReedSolomon Codewords. In the previous example, RS Encoder
System object corrected all of the errors. However, each ReedSolomon code
has a finite errorcorrection 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 RS
Decoder
System object 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+randi([0 n1],nw,n)).*randerr(nw,n,t+1); % t+1 errors/row
Create Shortened ReedSolomon Codes. Every ReedSolomon encoder uses a codeword length that equals
2^{m}1 for an integer m. A shortened
ReedSolomon code is one in which the codeword length is not
2^{m}1. A shortened
[n
,k
] ReedSolomon code implicitly
uses an [n_{1},k_{1}] encoder, where
n_{1} = 2^{m } 1, where m is the number of bits per symbol
k_{1} = k + (n_{1}  n)
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:
Pads each message by prepending zeros
Encodes each padded message using a ReedSolomon encoder having an allowable codeword length and the desired errorcorrection capability
Removes the extra zeros from the nonparity symbols of each codeword
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^m1],3*k,1); % Random array of 3 ksymbol 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^m1; % Codeword length in the actual encoder k_pad = k+(n_padn); % 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_padn,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^m1,[]); % Each column vector represents a codeword code_eqv = cw(n_padn+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 ReedSolomon 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
andrsgenpoly
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  A^{b})(X  A^{b+1})...(X  A^{b+2t1}),
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_{1}I_{2}. (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 threesymbol message of 0I_{1}I_{2}. The modified message sequence is then RS encoded, and the added information zero is subsequently removed, which yields a result of I_{1}I_{2}P_{1}P_{2}P_{3}P_{4}. (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_{1}I_{2}P_{1}P_{3}P_{4}.
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 erasurecorrecting capability of the code, which can correct four erasures. The decoding operation results in the threesymbol message DI_{1}I_{2}. The first symbol is truncated, as in the preceding figure, yielding a final output of I_{1}I_{2}.
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_{1}I_{2}P_{1}P_{3}P_{4} 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_{1}EP_{1}P_{3}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_{1} and P_{3}, yielding a codeword vector of I_{1}EP_{1}EP_{3}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_{1}EP_{1}EP_{3}E, such that a (7,3) codeword is sent to the Berlekamp algorithm.
This codeword is decoded, yielding a threesymbol message of DI_{1}I_{2} (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_{1}I_{2} vector.
For additional information, see the ReedSolomon Coding with Erasures, Punctures, and Shortening in Simulink example.
LDPC Codes
LowDensity ParityCheck (LDPC) codes are linear error control codes with:
Sparse paritycheck matrices
Long block lengths that can attain performance near the Shannon limit (see LDPC Encoder and LDPC Decoder)
Communications Toolbox performs LDPC Coding using Simulink blocks and MATLAB objects.
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 loglikelihood 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.
Galois Field Computations
A Galois field is an algebraic field that has a finite number of members. Galois fields having 2^{m} members are used in errorcontrol coding and are denoted GF(2^{m}). This chapter describes how to work with fields that have 2^{m} members, where m is an integer between 1 and 16. The sections in this chapter are as follows.
If you need to use Galois fields having an odd number of elements, see Galois Fields of Odd Characteristic.
For more details about specific functions that process arrays of Galois field elements, see the online reference pages in the documentation for MATLAB or for Communications Toolbox software.
Note
Please note that the Galois field objects do not support the copy
method.
MATLAB functions whose generalization to Galois fields is straightforward to describe do not have reference pages in this manual because the entries would be identical to those in the MATLAB documentation.
Galois Field Terminology
The discussion of Galois fields in this document uses a few terms that are not used consistently in the literature. The definitions adopted here appear in van Lint [4]:
A primitive element of GF(2^{m}) is a cyclic generator of the group of nonzero elements of GF(2^{m}). This means that every nonzero element of the field can be expressed as the primitive element raised to some integer power.
A primitive polynomial for GF(2^{m}) is the minimal polynomial of some primitive element of GF(2^{m}). It is the binarycoefficient polynomial of smallest nonzero degree having a certain primitive element as a root in GF(2^{m}). As a consequence, a primitive polynomial has degree m and is irreducible.
The definitions imply that a primitive element is a root of a corresponding primitive polynomial.
Representing Elements of Galois Fields
Section Overview. This section describes how to create a Galois field array, which is a MATLAB expression that represents the elements of a Galois field. This section also describes how MATLAB technical computing software interprets the numbers that you use in the representation, and includes several examples.
Creating a Galois field array. To begin working with data from a Galois field GF(2^m
),
you must set the context by associating the data with crucial information
about the field. The gf
function performs this
association and creates a Galois field array in MATLAB. This function accepts as inputs
The Galois field data,
x
, which is a MATLAB array whose elements are integers between 0 and2^m1
.(Optional) An integer,
m
, that indicatesx
is in the field GF(2^m
). Valid values ofm
are between 1 and 16. The default is 1, which means that the field is GF(2).(Optional) A positive integer that indicates which primitive polynomial for GF(
2^m
) you are using in the representations inx
. If you omit this input argument,gf
uses a default primitive polynomial for GF(2^m
). For information about this argument, see Primitive Polynomials and Element Representations.
The output of the gf
function is a variable that
MATLAB recognizes as a Galois field array, rather than an array of
integers. As a result, when you manipulate the variable, MATLAB works within the Galois field you have specified. For example,
if you apply the log
function to a Galois field array,
MATLAB computes the logarithm in the Galois field and
not in the field of real or complex numbers.
When MATLAB Implicitly Creates a Galois field array
Some operations on Galois field arrays require multiple arguments. If you
specify one argument that is a Galois field array and another that is an
ordinary MATLAB array, MATLAB interprets both as Galois field arrays in the same field. It
implicitly invokes the gf
function on the ordinary
MATLAB array. This implicit invocation simplifies your syntax because
you can omit some references to the gf
function. For an
example of the simplification, see Example: Addition and Subtraction.
Example: Creating Galois Field Variables. The code below creates a row vector whose entries are in the field GF(4), and then adds the row to itself.
x = 0:3; % A row vector containing integers m = 2; % Work in the field GF(2^2), or, GF(4). a = gf(x,m) % Create a Galois array in GF(2^m). b = a + a % Add a to itself, creating b.
The output is
a = GF(2^2) array. Primitive polynomial = D^2+D+1 (7 decimal) Array elements = 0 1 2 3 b = GF(2^2) array. Primitive polynomial = D^2+D+1 (7 decimal) Array elements = 0 0 0 0
The output shows the values of the Galois field arrays named
a
and b
. Each output section
indicates
The field containing the variable, namely, GF(2^2) = GF(4).
The primitive polynomial for the field. In this case, it is the toolbox's default primitive polynomial for GF(4).
The array of Galois field values that the variable contains. In particular, the array elements in
a
are exactly the elements of the vectorx
, and the array elements inb
are four instances of the zero element in GF(4).
The command that creates b
shows how, having defined
the variable a
as a Galois field array, you can add
a
to itself by using the ordinary
+
operator. MATLAB performs the vectorized addition operation in the field GF(4).
The output shows that
Compared to
a
,b
is in the same field and uses the same primitive polynomial. It is not necessary to indicate the field when defining the sum,b
, because MATLAB remembers that information from the definition of the addends,a
.The array elements of
b
are zeros because the sum of any value with itself, in a Galois field of characteristic two, is zero. This result differs from the sumx + x
, which represents an addition operation in the infinite field of integers.
Example: Representing Elements of GF(8). To illustrate what the array elements in a Galois field array mean, the table below lists the elements of the field GF(8) as integers and as polynomials in a primitive element, A. The table should help you interpret a Galois field array like
gf8 = gf([0:7],3); % Galois vector in GF(2^3)
Integer Representation  Binary Representation  Element of GF(8) 

0  000  0 
1  001  1 
2  010  A 
3  011  A + 1 
4  100  A^{2} 
5  101  A^{2} + 1 
6  110  A^{2} + A 
7  111  A^{2} + A + 1 
How Integers Correspond to Galois Field Elements. Building on the GF(8) example
above, this section explains the interpretation of array elements
in a Galois field array in greater generality. The field
GF(2^m
) has 2^m
distinct elements,
which this toolbox labels as 0, 1, 2,..., 2^m1
. These
integer labels correspond to elements of the Galois field via a polynomial
expression involving a primitive element of the field. More specifically,
each integer between 0 and 2^m1
has a binary
representation in m
bits. Using the bits in the binary
representation as coefficients in a polynomial, where the least significant
bit is the constant term, leads to a binary polynomial whose order is at
most m1
. Evaluating the binary polynomial at a primitive
element of GF(2^m
) leads to an element of the
field.
Conversely, any element of GF(2^m
) can be expressed as
a binary polynomial of order at most m1
, evaluated at a
primitive element of the field. The m
tuple of
coefficients of the polynomial corresponds to the binary representation of
an integer between 0 and 2^m
.
Below is a symbolic illustration of the correspondence of an integer X, representable in binary form, with a Galois field element. Each b_{k} is either zero or one, while A is a primitive element.
$$\begin{array}{c}X={b}_{m1}\cdot {2}^{m1}+\cdots +{b}_{2}\cdot 4+{b}_{1}\cdot 2+{b}_{0}\\ \leftrightarrow {b}_{m1}\cdot {A}^{m1}+\cdots +{b}_{2}\cdot {A}^{2}+{b}_{1}\cdot A+{b}_{0}\end{array}$$
Example: Representing a Primitive Element. The code below defines a variable alph
that represents
a primitive element of the field GF(2^{4}).
m = 4; % Or choose any positive integer value of m. alph = gf(2,m) % Primitive element in GF(2^m)
The output is
alph = GF(2^4) array. Primitive polynomial = D^4+D+1 (19 decimal) Array elements = 2
The Galois field array alph
represents a primitive
element because of the correspondence among
The integer 2, specified in the
gf
syntaxThe binary representation of 2, which is 10 (or 0010 using four bits)
The polynomial A + 0, where A is a primitive element in this field (or 0A^{3} + 0A^{2} + A + 0 using the four lowest powers of A)
Primitive Polynomials and Element Representations. This section builds on the discussion in Creating a Galois field array by describing how to specify your own primitive polynomial when you create a Galois field array. The topics are
If you perform many computations using a nondefault primitive polynomial, see Speed and Nondefault Primitive Polynomials.
Specifying the Primitive Polynomial
The discussion in How Integers Correspond to Galois Field Elements refers to a
primitive element, which is a root of a primitive polynomial of the field.
When you use the gf
function to create a Galois field
array, the function interprets the integers in the array with respect to a
specific default primitive polynomial for that field, unless you explicitly
provide a different primitive polynomial. A list of the default primitive
polynomials is on the reference page for the gf
function.
To specify your own primitive polynomial when creating a Galois field array, use a syntax like
c = gf(5,4,25) % 25 indicates the primitive polynomial for GF(16).
instead of
c1= gf(5,4); % Use default primitive polynomial for GF(16).
The extra input argument, 25
in this case, specifies
the primitive polynomial for the field GF(2^m
) in a way
similar to the representation described in How Integers Correspond to Galois Field Elements. In this case,
the integer 25 corresponds to a binary representation of 11001, which in
turn corresponds to the polynomial
D^{4} + D^{3} + 1.
Note
When you specify the primitive polynomial, the input argument must
have a binary representation using exactly m+1
bits,
not including unnecessary leading zeros. In other words, a primitive
polynomial for GF(2^m
) always has order
m
.
When you use an input argument to specify the primitive polynomial, the output reflects your choice by showing the integer value as well as the polynomial representation.
d = gf([1 2 3],4,25)
d = GF(2^4) array. Primitive polynomial = D^4+D^3+1 (25 decimal) Array elements = 1 2 3
Note
After you have defined a Galois field array, you cannot change the primitive polynomial with respect to which MATLAB interprets the array elements.
Finding Primitive Polynomials
You can use the primpoly
function to find primitive
polynomials for GF(2^m
) and the
isprimitive
function to determine whether a
polynomial is primitive for GF(2^m
). The code below
illustrates.
m = 4; defaultprimpoly = primpoly(m) % Default primitive poly for GF(16) allprimpolys = primpoly(m,'all') % All primitive polys for GF(16) i1 = isprimitive(25) % Can 25 be the prim_poly input in gf(...)? i2 = isprimitive(21) % Can 21 be the prim_poly input in gf(...)?
The output is below.
Primitive polynomial(s) = D^4+D^1+1 defaultprimpoly = 19 Primitive polynomial(s) = D^4+D^1+1 D^4+D^3+1
allprimpolys = 19 25 i1 = 1 i2 = 0
Effect of Nondefault Primitive Polynomials on Numerical Results
Most fields offer multiple choices for the primitive polynomial that helps
define the representation of members of the field. When you use the
gf
function, changing the primitive polynomial
changes the interpretation of the array elements and, in turn, changes the
results of some subsequent operations on the Galois field array. For
example, exponentiation of a primitive element makes it easy to see how the
primitive polynomial affects the representations of field elements.
a11 = gf(2,3); % Use default primitive polynomial of 11. a13 = gf(2,3,13); % Use D^3+D^2+1 as the primitive polynomial. z = a13.^3 + a13.^2 + 1 % 0 because a13 satisfies the equation nz = a11.^3 + a11.^2 + 1 % Nonzero. a11 does not satisfy equation.
The output below shows that when the primitive polynomial has integer
representation 13
, the Galois field array satisfies a
certain equation. By contrast, when the primitive polynomial has integer
representation 11
, the Galois field array fails to
satisfy the equation.
z = GF(2^3) array. Primitive polynomial = D^3+D^2+1 (13 decimal) Array elements = 0 nz = GF(2^3) array. Primitive polynomial = D^3+D+1 (11 decimal) Array elements = 6
The output when you try this example might also include a warning about
lookup tables. This is normal if you did not use the
gftable
function to optimize computations involving
a nondefault primitive polynomial of 13.
Arithmetic in Galois Fields
Section Overview. You can perform arithmetic operations on Galois field arrays by using familiar MATLAB operators, listed in the table below. Whenever you operate on a pair of Galois field arrays, both arrays must be in the same Galois field.
Operation  Operator 

Addition  +

Subtraction  

Elementwise multiplication  .*

Matrix multiplication  *

Elementwise left division  ./

Elementwise right division  .\

Matrix left division  /

Matrix right division  \

Elementwise exponentiation  .^

Elementwise logarithm  log()

Exponentiation of a square Galois matrix by a scalar integer  ^

For multiplication and division of polynomials over a Galois field, see Addition and Subtraction of Polynomials.
Example: Addition and Subtraction. The code below adds two Galois field arrays to create an addition table
for GF(8). Addition uses the ordinary +
operator. The
code below also shows how to index into the array addtb
to find the result of adding 1 to the elements of GF(8).
m = 3; e = repmat([0:2^m1],2^m,1); f = gf(e,m); % Create a Galois array. addtb = f + f' % Add f to its own matrix transpose. addone = addtb(2,:); % Assign 2nd row to the Galois vector addone.
The output is below.
addtb = GF(2^3) array. Primitive polynomial = D^3+D+1 (11 decimal) Array elements = 0 1 2 3 4 5 6 7 1 0 3 2 5 4 7 6 2 3 0 1 6 7 4 5 3 2 1 0 7 6 5 4 4 5 6 7 0 1 2 3 5 4 7 6 1 0 3 2 6 7 4 5 2 3 0 1 7 6 5 4 3 2 1 0
As an example of reading this addition table, the (7,4) entry in the
addtb
array shows that gf(6,3)
plus gf(3,3)
equals gf(5,3)
.
Equivalently, the element A^{2}+A plus the element
A+1 equals the element A^{2}+1. The equivalence
arises from the binary representation of 6 as 110, 3 as 011, and 5 as
101.
The subtraction table, which you can obtain by replacing
+
by 
, is the same as
addtb
. This is because subtraction and addition are
identical operations in a field of characteristic two.
In fact, the zeros along the main diagonal of addtb
illustrate this fact for GF(8).
Simplifying the Syntax
The code below illustrates scalar expansion and the implicit creation of a
Galois field array from an ordinary MATLAB array. The Galois field arrays h
and
h1
are identical, but the creation of
h
uses a simpler syntax.
g = gf(ones(2,3),4); % Create a Galois array explicitly. h = g + 5; % Add gf(5,4) to each element of g. h1 = g + gf(5*ones(2,3),4) % Same as h.
The output is below.
h1 = GF(2^4) array. Primitive polynomial = D^4+D+1 (19 decimal) Array elements = 4 4 4 4 4 4
Notice that 1+5 is reported as 4 in the Galois field. This is true because the 5 represents the polynomial expression A^{2}+1, and 1+(A^{2}+1) in GF(16) is A^{2}. Furthermore, the integer that represents the polynomial expression A^{2} is 4.
Example: Multiplication. The example below multiplies individual elements in a Galois field array
using the .*
operator. It then performs matrix
multiplication using the *
operator. The elementwise
multiplication produces an array whose size matches that of the inputs. By
contrast, the matrix multiplication produces a Galois scalar because it is
the matrix product of a row vector with a column vector.
m = 5; row1 = gf([1:2:9],m); row2 = gf([2:2:10],m); col = row2'; % Transpose to create a column array. ep = row1 .* row2; % Elementwise product. mp = row1 * col; % Matrix product.
Multiplication Table for GF(8)
As another example, the code below multiplies two Galois vectors using matrix multiplication. The result is a multiplication table for GF(8).
m = 3;
els = gf([0:2^m1]',m);
multb = els * els' % Multiply els by its own matrix transpose.
The output is below.
multb = GF(2^3) array. Primitive polynomial = D^3+D+1 (11 decimal) Array elements = 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 0 2 4 6 3 1 7 5 0 3 6 5 7 4 1 2 0 4 3 7 6 2 5 1 0 5 1 4 2 7 3 6 0 6 7 1 5 3 2 4 0 7 5 2 1 6 4 3
Example: Division. The examples below illustrate the four division operators in a Galois
field by computing multiplicative inverses of individual elements and of an
array. You can also compute inverses using inv
or using
exponentiation by 1.
Elementwise Division
This example divides 1 by each of the individual elements in a Galois
field array using the ./
and .\
operators. These two operators differ only in their sequence of input
arguments. Each quotient vector lists the multiplicative inverses of the
nonzero elements of the field. In this example, MATLAB expands the scalar 1 to the size of nz
before computing; alternatively, you can use as arguments two arrays of the
same size.
m = 5; nz = gf([1:2^m1],m); % Nonzero elements of the field inv1 = 1 ./ nz; % Divide 1 by each element. inv2 = nz .\ 1; % Obtain same result using .\ operator.
Matrix Division
This example divides the identity array by the square Galois field array
mat
using the /
and
\
operators. Each quotient matrix is the
multiplicative inverse of mat
. Notice how the transpose
operator ('
) appears in the equivalent operation using
\
. For square matrices, the sequence of transpose
operations is unnecessary, but for nonsquare matrices, it is
necessary.
m = 5; mat = gf([1 2 3; 4 5 6; 7 8 9],m); minv1 = eye(3) / mat; % Compute matrix inverse. minv2 = (mat' \ eye(3)')'; % Obtain same result using \ operator.
Example: Exponentiation. The examples below illustrate how to compute integer powers of a Galois field array. To perform matrix exponentiation on a Galois field array, you must use a square Galois field array as the base and an ordinary (not Galois) integer scalar as the exponent.
Elementwise Exponentiation
This example computes powers of a primitive element, A, of a Galois field.
It then uses these separately computed powers to evaluate the default
primitive polynomial at A. The answer of zero shows that A is a root of the
primitive polynomial. The .^
operator exponentiates each
array element independently.
m = 3; av = gf(2*ones(1,m+1),m); % Row containing primitive element expa = av .^ [0:m]; % Raise element to different powers. evp = expa(4)+expa(2)+expa(1) % Evaluate D^3 + D + 1.
The output is below.
evp = GF(2^3) array. Primitive polynomial = D^3+D+1 (11 decimal) Array elements = 0
Matrix Exponentiation
This example computes the inverse of a square matrix by raising the matrix to the power 1. It also raises the square matrix to the powers 2 and 2.
m = 5; mat = gf([1 2 3; 4 5 6; 7 8 9],m); minvs = mat ^ (1); % Matrix inverse matsq = mat^2; % Same as mat * mat matinvssq = mat^(2); % Same as minvs * minvs
Example: Elementwise Logarithm. The code below computes the logarithm of the elements of a Galois field array. The output indicates how to express each nonzero element of GF(8) as a power of the primitive element. The logarithm of the zero element of the field is undefined.
gf8_nonzero = gf([1:7],3); % Vector of nonzero elements of GF(8) expformat = log(gf8_nonzero) % Logarithm of each element
The output is
expformat = 0 1 3 2 6 4 5
As an example of how to interpret the output, consider the last entry in
each vector in this example. You can infer that the element
gf(7,3)
in GF(8) can be expressed as either
A^{5}, using the last element of
expformat
A^{2}+A+1, using the binary representation of 7 as 111. See Example: Representing Elements of GF(8) for more details.
Logical Operations in Galois Fields
Section Overview. You can apply logical tests to Galois field arrays and obtain a logical array. Some important types of tests are testing for the equality of two Galois field arrays and testing for nonzero values in a Galois field array.
Testing for Equality. To compare corresponding elements of two Galois field arrays that have the
same size, use the operators ==
and
~=
. The result is a logical array, each element of which
indicates the truth or falsity of the corresponding elementwise comparison.
If you use the same operators to compare a scalar with a Galois field array,
MATLAB technical computing software compares the scalar with each
element of the array, producing a logical array of the same size.
m = 5; r1 = gf([1:3],m); r2 = 1 ./ r1; lg1 = (r1 .* r2 == [1 1 1]) % Does each element equal one? lg2 = (r1 .* r2 == 1) % Same as above, using scalar expansion lg3 = (r1 ~= r2) % Does each element differ from its inverse?
The output is below.
lg1 = 1 1 1 lg2 = 1 1 1 lg3 = 0 1 1
Comparison of isequal and ==
To compare entire arrays and obtain a logical scalar
result rather than a logical array, use the builtin
isequal
function. However,
isequal
uses strict rules for its comparison, and
returns a value of 0
(false) if you compare
A Galois field array with an ordinary MATLAB array, even if the values of the underlying array elements match
A scalar with a nonscalar array, even if all elements in the array match the scalar
The example below illustrates this difference between
==
and isequal
.
m = 5; r1 = gf([1:3],m); r2 = 1 ./ r1; lg4 = isequal(r1 .* r2, [1 1 1]); % False lg5 = isequal(r1 .* r2, gf(1,m)); % False lg6 = isequal(r1 .* r2, gf([1 1 1],m)); % True
Testing for Nonzero Values. To test for nonzero values in a Galois vector, or in the columns of a
Galois field array that has more than one row, use the
any
or all
function. These two
functions behave just like the ordinary MATLAB functions any
and
all
, except that they consider only the underlying
array elements while ignoring information about which Galois field the
elements are in. Examples are below.
m = 3; randels = gf(randi([0 2^m1],6,1),m); if all(randels) % If all elements are invertible invels = randels .\ 1; % Compute inverses of elements. else disp('At least one element was not invertible.'); end alph = gf(2,4); poly = 1 + alph + alph^3; if any(poly) % If poly contains a nonzero value disp('alph is not a root of 1 + D + D^3.'); end code = [0:4 4 0; 3:7 4 5] if all(code,2) % Is each row entirely nonzero? disp('Both codewords are entirely nonzero.'); else disp('At least one codeword contains a zero.'); end
Matrix Manipulation in Galois Fields
Basic Manipulations of Galois Field Arrays. Basic array operations on Galois field arrays are in the table below. The functionality of these operations is analogous to the MATLAB operations having the same syntax.
Operation  Syntax 

Index into array, possibly using colon operator instead of a vector of explicit indices  a(vector) or
a(vector,vector1) , where
vector and/or
vector1 can be
": " instead of a vector 
Transpose array  a'

Concatenate matrices  [a,b] or
[a;b]

Create array having specified diagonal elements  diag(vector)
or diag(vector,k)

Extract diagonal elements  diag(a) or
diag(a,k)

Extract lower triangular part  tril(a) or
tril(a,k)

Extract upper triangular part  triu(a) or
triu(a,k)

Change shape of array  reshape(a,k1,k2)

The code below uses some of these syntaxes.
m = 4; a = gf([0:15],m); a(1:2) = [13 13]; % Replace some elements of the vector a. b = reshape(a,2,8); % Create 2by8 matrix. c = [b([1 1 2],1:3); a(4:6)]; % Create 4by3 matrix. d = [c, a(1:4)']; % Create 4by4 matrix. dvec = diag(d); % Extract main diagonal of d. dmat = diag(a(5:9)); % Create 5by5 diagonal matrix dtril = tril(d); % Extract upper and lower triangular dtriu = triu(d); % parts of d.
Basic Information About Galois Field Arrays. You can determine the length of a Galois vector or the size of any Galois
field array using the length
and
size
functions. The functionality for Galois field
arrays is analogous to that of the MATLAB operations on ordinary arrays, except that the output
arguments from size
and length
are
always integers, not Galois field arrays. The code below illustrates the use
of these functions.
m = 4; e = gf([0:5],m); f = reshape(e,2,3); lne = length(e); % Vector length of e szf = size(f); % Size of f, returned as a twoelement row [nr,nc] = size(f); % Size of f, returned as two scalars nc2 = size(f,2); % Another way to compute number of columns
Positions of Nonzero Elements
Another type of information you might want to determine from a Galois
field array are the positions of nonzero elements. For an ordinary
MATLAB array, you might use the find
function.
However, for a Galois field array, you should use find
in conjunction with the ~=
operator, as
illustrated.
x = [0 1 2 1 0 2]; m = 2; g = gf(x,m); nzx = find(x); % Find nonzero values in the ordinary array x. nzg = find(g~=0); % Find nonzero values in the Galois array g.
Linear Algebra in Galois Fields
Inverting Matrices and Computing Determinants. To invert a square Galois field array, use the inv
function. Related is the det
function, which computes
the determinant of a Galois field array. Both inv
and
det
behave like their ordinary MATLAB counterparts, except that they perform computations in the
Galois field instead of in the field of complex numbers.
Note
A Galois field array is singular if and only if its determinant is exactly zero. It is not necessary to consider roundoff errors, as in the case of real and complex arrays.
The code below illustrates matrix inversion and determinant computation.
m = 4; randommatrix = gf(randi([0 2^m1],4,4),m); gfid = gf(eye(4),m); if det(randommatrix) ~= 0 invmatrix = inv(randommatrix); check1 = invmatrix * randommatrix; check2 = randommatrix * invmatrix; if (isequal(check1,gfid) & isequal(check2,gfid)) disp('inv found the correct matrix inverse.'); end else disp('The matrix is not invertible.'); end
The output from this example is either of these two messages, depending on whether the randomly generated matrix is nonsingular or singular.
inv found the correct matrix inverse. The matrix is not invertible.
Computing Ranks. To compute the rank of a Galois field array, use the
rank
function. It behaves like the ordinary
MATLAB
rank
function when given exactly one input argument.
The example below illustrates how to find the rank of square and nonsquare
Galois field arrays.
m = 3; asquare = gf([4 7 6; 4 6 5; 0 6 1],m); r1 = rank(asquare); anonsquare = gf([4 7 6 3; 4 6 5 1; 0 6 1 1],m); r2 = rank(anonsquare); [r1 r2]
The output is
ans = 2 3
The values of r1
and r2
indicate
that asquare
has less than full rank but that
anonsquare
has full rank.
Factoring Square Matrices. To express a square Galois field array (or a permutation of it) as the
product of a lower triangular Galois field array and an upper triangular
Galois field array, use the lu
function. This function
accepts one input argument and produces exactly two or three output
arguments. It behaves like the ordinary MATLAB
lu
function when given the same syntax. The example
below illustrates how to factor using lu
.
tofactor = gf([6 5 7 6; 5 6 2 5; 0 1 7 7; 1 0 5 1],3); [L,U]=lu(tofactor); % lu with two output arguments c1 = isequal(L*U, tofactor) % True tofactor2 = gf([1 2 3 4;1 2 3 0;2 5 2 1; 0 5 0 0],3); [L2,U2,P] = lu(tofactor2); % lu with three output arguments c2 = isequal(L2*U2, P*tofactor2) % True
Solving Linear Equations. To find a particular solution of a linear equation in a Galois field, use
the \
or /
operator on Galois field
arrays. The table below indicates the equation that each operator addresses,
assuming that A
and B
are previously
defined Galois field arrays.
Operator  Linear Equation  Syntax  Equivalent Syntax Using \ 

Backslash (\ )  A * x = B  x = A \ B  Not applicable 
Slash (/ )  x * A = B  x = B / A  x = (A'\B')' 
The results of the syntax in the table depend on characteristics of the
Galois field array A
:
If
A
is square and nonsingular, the outputx
is the unique solution to the linear equation.If
A
is square and singular, the syntax in the table produces an error.If
A
is not square, MATLAB attempts to find a particular solution. IfA'*A
orA*A'
is a singular array, or ifA
is a matrix, where the rows outnumber the columns, that represents an overdetermined system, the attempt might fail.
Note
An error message does not necessarily indicate that the linear
equation has no solution. You might be able to find a solution by
rephrasing the problem. For example, gf([1 2; 0 0],3) \ gf([1;
0],3)
produces an error but the mathematically equivalent
gf([1 2],3) \ gf([1],3)
does not. The first
syntax fails because gf([1 2; 0 0],3)
is a singular
square matrix.
Example: Solving Linear Equations
The examples below illustrate how to find particular solutions of linear equations over a Galois field.
m = 4; A = gf(magic(3),m); % Square nonsingular matrix Awide=[A, 2*A(:,3)]; % 3by4 matrix with redundancy on the right Atall = Awide'; % 4by3 matrix with redundancy at the bottom B = gf([0:2]',m); C = [B; 2*B(3)]; D = [B; B(3)+1]; thesolution = A \ B; % Solution of A * x = B thesolution2 = B' / A; % Solution of x * A = B' ck1 = all(A * thesolution == B) % Check validity of solutions. ck2 = all(thesolution2 * A == B') % Awide * x = B has infinitely many solutions. Find one. onesolution = Awide \ B; ck3 = all(Awide * onesolution == B) % Check validity of solution. % Atall * x = C has a solution. asolution = Atall \ C; ck4 = all(Atall * asolution == C) % Check validity of solution. % Atall * x = D has no solution. notasolution = Atall \ D; ck5 = all(Atall * notasolution == D) % It is not a valid solution.
The output from this example indicates that the validity checks are all
true (1
), except for ck5
, which is
false (0
).
Signal Processing Operations in Galois Fields
Section Overview. You can perform some signalprocessing operations on Galois field arrays, such as filtering, convolution, and the discrete Fourier transform.
This section describes how to perform these operations.
Other information about the corresponding operations for ordinary real vectors is in the Signal Processing Toolbox™ documentation.
Filtering. To filter a Galois vector, use the filter
function.
It behaves like the ordinary MATLAB
filter
function when given exactly three input
arguments.
The code and diagram below give the impulse response of a particular filter over GF(2).
m = 1; % Work in GF(2). b = gf([1 0 0 1 0 1 0 1],m); % Numerator a = gf([1 0 1 1],m); % Denominator x = gf([1,zeros(1,19)],m); y = filter(b,a,x); % Filter x. figure; stem(y.x); % Create stem plot. axis([0 20 .1 1.1])
Convolution. Communications Toolbox software offers two equivalent ways to convolve a pair of Galois vectors:
Use the
conv
function, as described in Multiplication and Division of Polynomials. This works because convolving two vectors is equivalent to multiplying the two polynomials whose coefficients are the entries of the vectors.Use the
convmtx
function to compute the convolution matrix of one of the vectors, and then multiply that matrix by the other vector. This works because convolving two vectors is equivalent to filtering one of the vectors by the other. The equivalence permits the representation of a digital filter as a convolution matrix, which you can then multiply by any Galois vector of appropriate length.
Tip
If you need to convolve large Galois vectors, multiplying by the
convolution matrix might be faster than using
conv
.
Example
Computes the convolution matrix for a vector b
in
GF(4). Represent the numerator coefficients for a digital filter, and then
illustrate the two equivalent ways to convolve b
with
x
over the Galois field.
m = 2; b = gf([1 2 3]',m); n = 3; x = gf(randi([0 2^m1],n,1),m); C = convmtx(b,n); % Compute convolution matrix. v1 = conv(b,x); % Use conv to convolve b with x v2 = C*x; % Use C to convolve b with x.
Discrete Fourier Transform. The discrete Fourier transform is an important tool in digital signal processing. This toolbox offers these tools to help you process discrete Fourier transforms:
fft
, which transforms a Galois vectorifft
, which inverts the discrete Fourier transform on a Galois vectordftmtx
, which returns a Galois field array that you can use to perform or invert the discrete Fourier transform on a Galois vector
In all cases, the vector being transformed must be a Galois vector of
length 2^{m}1 in the field
GF(2^{m}). The following example illustrates the
use of these functions. You can check, using the
isequal
function, that y
equals
y1
, z
equals
z1
, and z
equals
x
.
m = 4; x = gf(randi([0 2^m1],2^m1,1),m); % A vector to transform alph = gf(2,m); dm = dftmtx(alph); idm = dftmtx(1/alph); y = dm*x; % Transform x using the result of dftmtx. y1 = fft(x); % Transform x using fft. z = idm*y; % Recover x using the result of dftmtx(1/alph). z1 = ifft(y1); % Recover x using ifft.
Tip
If you have many vectors that you want to transform (in the same
field), it might be faster to use dftmtx
once and
matrix multiplication many times, instead of using
fft
many times.
Polynomials over Galois Fields
Section Overview. You can use Galois vectors to represent polynomials in an indeterminate quantity x, with coefficients in a Galois field. Form the representation by listing the coefficients of the polynomial in a vector in order of descending powers of x. For example, the vector
gf([2 1 0 3],4)
represents the polynomial Ax^{3} + 1x^{2} + 0x + (A+1), where
A is a primitive element in the field GF(2^{4}).
x is the indeterminate quantity in the polynomial.
You can then use such a Galois vector to perform arithmetic with, evaluate, and find roots of polynomials. You can also find minimal polynomials of elements of a Galois field.
Addition and Subtraction of Polynomials. To add and subtract polynomials, use +
and

on equallength Galois vectors that represent the
polynomials. If one polynomial has lower degree than the other, you must pad
the shorter vector with zeros at the beginning so the two vectors have the
same length. The example below shows how to add a degreeone and a
degreetwo polynomial.
lin = gf([4 2],3); % A^2 x + A, which is linear in x linpadded = gf([0 4 2],3); % The same polynomial, zeropadded quadr = gf([1 4 2],3); % x^2 + A^2 x + A, which is quadratic in x % Can't do lin + quadr because they have different vector lengths. sumpoly = [0, lin] + quadr; % Sum of the two polynomials sumpoly2 = linpadded + quadr; % The same sum
Multiplication and Division of Polynomials. To multiply and divide polynomials, use conv
and
deconv
on Galois vectors that represent the
polynomials. Multiplication and division of polynomials is equivalent to
convolution and deconvolution of vectors. The deconv
function returns the quotient of the two polynomials as well as the
remainder polynomial. Examples are below.
m = 4; apoly = gf([4 5 3],m); % A^2 x^2 + (A^2 + 1) x + (A + 1) bpoly = gf([1 1],m); % x + 1 xpoly = gf([1 0],m); % x % Product is A^2 x^3 + x^2 + (A^2 + A) x + (A + 1). cpoly = conv(apoly,bpoly); [a2,remd] = deconv(cpoly,bpoly); % a2==apoly. remd is zero. [otherpol,remd2] = deconv(cpoly,xpoly); % remd is nonzero.
The multiplication and division operators in Arithmetic in Galois Fields multiply elements or matrices, not polynomials.
Evaluating Polynomials. To evaluate a polynomial at an element of a Galois field, use
polyval
. It behaves like the ordinary MATLAB
polyval
function when given exactly two input
arguments. The example below evaluates a polynomial at several elements in a
field and checks the results using .^
and
.*
in the field.
m = 4; apoly = gf([4 5 3],m); % A^2 x^2 + (A^2 + 1) x + (A + 1) x0 = gf([0 1 2],m); % Points at which to evaluate the polynomial y = polyval(apoly,x0) a = gf(2,m); % Primitive element of the field, corresponding to A. y2 = a.^2.*x0.^2 + (a.^2+1).*x0 + (a+1) % Check the result.
The output is below.
y = GF(2^4) array. Primitive polynomial = D^4+D+1 (19 decimal) Array elements = 3 2 10 y2 = GF(2^4) array. Primitive polynomial = D^4+D+1 (19 decimal) Array elements = 3 2 10
The first element of y
evaluates the polynomial at
0
and, therefore, returns the polynomial's constant
term of 3
.
Roots of Polynomials. To find the roots of a polynomial in a Galois field, use the
roots
function on a Galois vector that represents
the polynomial. This function finds roots that are in the same field that
the Galois vector is in. The number of times an entry appears in the output
vector from roots
is exactly its multiplicity as a root
of the polynomial.
Note
If the Galois vector is in GF(2^{m}), the
polynomial it represents might have additional roots in some extension
field GF((2^{m})^{k}).
However, roots
does not find those additional roots
or indicate their existence.
The examples below find roots of cubic polynomials in GF(8).
p = 3; m = 2; field = gftuple([1:p^m2]',m,p); % List of all elements of GF(9) % Use default primitive polynomial here. polynomial = [1 0 1 1]; % 1 + x^2 + x^3 rts =gfroots(polynomial,m,p) % Find roots in exponential format % Check that each one is actually a root. for ii = 1:3 root = rts(ii); rootsquared = gfmul(root,root,field); rootcubed = gfmul(root,rootsquared,field); answer(ii)= gfadd(gfadd(0,rootsquared,field),rootcubed,field); % Recall that 1 is really alpha to the zero power. % If answer = Inf, then the variable root represents % a root of the polynomial. end answer
Roots of Binary Polynomials. In the special case of a polynomial having binary coefficients, it is also
easy to find roots that exist in an extension field. This is because the
elements 0
and 1
have the same
unambiguous representation in all fields of characteristic two. To find
roots of a binary polynomial in an extension field, apply the
roots
function to a Galois vector in the extension
field whose array elements are the binary coefficients of the
polynomial.
The example below seeks the roots of a binary polynomial in various fields.
gf2poly = gf([1 1 1],1); % x^2 + x + 1 in GF(2) noroots = roots(gf2poly); % No roots in the ground field, GF(2) gf4poly = gf([1 1 1],2); % x^2 + x + 1 in GF(4) roots4 = roots(gf4poly); % The roots are A and A+1, in GF(4). gf16poly = gf([1 1 1],4); % x^2 + x + 1 in GF(16) roots16 = roots(gf16poly); % Roots in GF(16) checkanswer4 = polyval(gf4poly,roots4); % Zero vector checkanswer16 = polyval(gf16poly,roots16); % Zero vector
The roots of the polynomial do not exist in GF(2), so
noroots
is an empty array. However, the roots of the
polynomial exist in GF(4) as well as in GF(16), so roots4
and roots16
are nonempty.
Notice that roots4
and roots16
are
not equal to each other. They differ in these ways:
roots4
is a GF(4) array, whileroots16
is a GF(16) array. MATLAB keeps track of the underlying field of a Galois field array.The array elements in
roots4
androots16
differ because they use representations with respect to different primitive polynomials. For example,2
(which represents a primitive element) is an element of the vectorroots4
because the default primitive polynomial for GF(4) is the same polynomial thatgf4poly
represents. On the other hand,2
is not an element ofroots16
because the primitive element of GF(16) is not a root of the polynomial thatgf16poly
represents.
Minimal Polynomials. The minimal polynomial of an element of GF(2^{m})
is the smallest degree nonzero binarycoefficient polynomial having that
element as a root in GF(2^{m}). To find the minimal
polynomial of an element or a column vector of elements, use the
minpol
function.
The code below finds that the minimal polynomial of
gf(6,4)
is
D^{2} + D + 1 and then checks
that gf(6,4)
is indeed among the roots of that polynomial
in the field GF(16).
m = 4; e = gf(6,4); em = minpol(e) % Find minimal polynomial of e. em is in GF(2). emr = roots(gf([0 0 1 1 1],m)) % Roots of D^2+D+1 in GF(2^m)
The output is
em = GF(2) array. Array elements = 0 0 1 1 1 emr = GF(2^4) array. Primitive polynomial = D^4+D+1 (19 decimal) Array elements = 6 7
To find out which elements of a Galois field share the same minimal
polynomial, use the cosets
function.
Manipulating Galois Variables
Section Overview. This section describes techniques for manipulating Galois variables or for transferring information between Galois field arrays and ordinary MATLAB arrays.
Note
These techniques are particularly relevant if you write MATLAB file functions that process Galois field arrays. For an
example of this type of usage, enter edit gf/conv
in
the Command Window and examine the first several lines of code in the
editor window.
Determining Whether a Variable Is a Galois Field Array. To find out whether a variable is a Galois field array rather than an
ordinary MATLAB array, use the isa
function. An
illustration is below.
mlvar = eye(3); gfvar = gf(mlvar,3); no = isa(mlvar,'gf'); % False because mlvar is not a Galois array yes = isa(gfvar,'gf'); % True because gfvar is a Galois array
Extracting Information from a Galois Field Array. To extract the array elements, field order, or primitive polynomial from a variable that is a Galois field array, append a suffix to the name of the variable. The table below lists the exact suffixes, which are independent of the name of the variable.
Information  Suffix  Output Value 

Array elements  .x  MATLAB array of type uint16 that
contains the data values from the Galois field
array. 
Field order  .m  Integer of type double that indicates
that the Galois field array is in
GF(2^m ). 
Primitive polynomial  .prim_poly  Integer of type uint32 that represents
the primitive polynomial. The representation is similar to
the description in How Integers Correspond to Galois Field Elements. 
Note
If the output value is an integer data type and you want to convert it
to double
for later manipulation, use the
double
function.
The code below illustrates the use of these suffixes. The definition of
empr
uses a vector of binary coefficients of a
polynomial to create a Galois field array in an extension field. Another
part of the example retrieves the primitive polynomial for the field and
converts it to a binary vector representation having the appropriate number
of bits.
% Check that e solves its own minimal polynomial. e = gf(6,4); % An element of GF(16) emp = minpol(e); % The minimal polynomial, emp, is in GF(2). empr = roots(gf(emp.x,e.m)); % Find roots of emp in GF(16). % Check that the primitive element gf(2,m) is % really a root of the primitive polynomial for the field. primpoly_int = double(e.prim_poly); mval = e.m; primpoly_vect = gf(de2bi(primpoly_int,mval+1,'leftmsb'),mval); containstwo = roots(primpoly_vect); % Output vector includes 2.
Converting Galois Field Array to Doubles
a = gf([1,0]) b = double(a.x) %a.x is in uint16
MATLAB returns the following:
a = GF(2) array. Array elements = 1 0 b = 1 0
Speed and Nondefault Primitive Polynomials
Primitive Polynomials and Element Representations describes how to represent elements of a Galois field with respect to a primitive polynomial of your choice. This section describes how you can increase the speed of computations involving a Galois field array that uses a primitive polynomial other than the default primitive polynomial. The technique is recommended if you perform many such computations.
The mechanism for increasing the speed is a data file,
userGftable.mat
, that some computational functions use to
avoid performing certain computations repeatedly. To take advantage of this
mechanism for your combination of field order (m
) and
primitive polynomial (prim_poly
):
Navigate in the MATLAB application to a folder to which you have write permission. You can use either the
cd
function or the Current Folder feature to navigate.Define
m
andprim_poly
as workspace variables. For example:m = 3; prim_poly = 13; % Examples of valid values
Invoke the
gftable
function:gftable(m,prim_poly); % If you previously defined m and prim_poly
The function revises or creates userGftable.mat
in your
current working folder to include data relating to your combination of field
order and primitive polynomial. After you initially invest the time to invoke
gftable
, subsequent computations using those values of
m
and prim_poly
should be
faster.
Note
If you change your current working directory after invoking
gftable
, you must place
userGftable.mat
on your MATLAB path to ensure that MATLAB can see it. Do this by using the addpath
command to prefix the directory containing
userGftable.mat
to your MATLAB path. If you have multiple copies of
userGftable.mat
on your path, use
which('userGftable.mat','all')
to find out where
they are and which one MATLAB is using.
To see how much gftable
improves the speed of your
computations, you can surround your computations with the
tic
and toc
functions. See the
gftable
reference page for an
example.
Selected Bibliography for Galois Fields
[1] Blahut, Richard E., Theory and Practice of Error Control Codes, Reading, MA, AddisonWesley, 1983, p. 105.
[2] Lang, Serge, Algebra, Third Edition, Reading, MA, AddisonWesley, 1993.
[3] Lin, Shu, and Daniel J. Costello, Jr., Error Control Coding: Fundamentals and Applications, Englewood Cliffs, NJ, PrenticeHall, 1983.
[4] van Lint, J. H., Introduction to Coding Theory, New York, SpringerVerlag, 1982.
[5] Wicker, Stephen B., Error Control Systems for Digital Communication and Storage, Upper Saddle River, NJ, Prentice Hall, 1995.
Galois Fields of Odd Characteristic
A Galois field is an algebraic field having p^{m} elements, where p is prime and m is a positive integer. This chapter describes how to work with Galois fields in which p is odd. To work with Galois fields having an even number of elements, see Galois Field Computations. The sections in this chapter are as follows.
Galois Field Terminology
Throughout this section, p is an odd prime number and m is a positive integer.
Also, this document uses a few terms that are not used consistently in the literature. The definitions adopted here appear in van Lint [5].
A primitive element of GF(p^{m}) is a cyclic generator of the group of nonzero elements of GF(p^{m}). This means that every nonzero element of the field can be expressed as the primitive element raised to some integer power. Primitive elements are called A throughout this section.
A primitive polynomial for GF(p^{m}) is the minimal polynomial of some primitive element of GF(p^{m}). As a consequence, it has degree m and is irreducible.
Representing Elements of Galois Fields
Section Overview. This section discusses how to represent Galois field elements using this toolbox's exponential format and polynomial format. It also describes a way to list all elements of the Galois field, because some functions use such a list as an input argument. Finally, it discusses the nonuniqueness of representations of Galois field elements.
The elements of GF(p) can be represented using the integers from 0 to p1.
When m is at least 2, GF(p^{m}) is called an extension field. Integers alone cannot represent the elements of GF(p^{m}) in a straightforward way. MATLAB technical computing software uses two main conventions for representing elements of GF(p^{m}): the exponential format and the polynomial format.
Note
Both the exponential format and the polynomial format are relative to your choice of a particular primitive element A of GF(p^{m}).
Exponential Format. This format uses the property that every nonzero element of GF(p^{m}) can be expressed as A^{c} for some integer c between 0 and p^{m}2. Higher exponents are not needed, because the theory of Galois fields implies that every nonzero element of GF(p^{m}) satisfies the equation x^{q1} = 1 where q = p^{m}.
The use of the exponential format is shown in the table below.
Element of GF(p^{m})  MATLAB Representation of the Element 

0  Inf 
A^{0} = 1  0

A^{1}  1

...  ... 
A^{q2} where
q = p^{m}
 q2

Although Inf
is the standard exponential
representation of the zero element, all negative integers are equivalent to
Inf
when used as input
arguments in exponential format. This equivalence can be useful; for
example, see the concise line of code at the end of the section Default Primitive Polynomials.
Note
The equivalence of all negative integers and Inf
as exponential formats means that, for example, 1 does
not represent A^{1},
the multiplicative inverse of A. Instead, 1 represents the zero element
of the field.
Polynomial Format. The polynomial format uses the property that every element of GF(p^{m}) can be expressed as a polynomial in A with exponents between 0 and m1, and coefficients in GF(p). In the polynomial format, the element
A(1)
+ A(2)
A + A(3)
A^{2} + ... + A(m)
A^{m1
}
is represented in MATLAB by the vector
[A(1) A(2) A(3) ... A(m)]
Note
The Galois field functions in this toolbox represent a polynomial as a vector that lists the coefficients in order of ascending powers of the variable. This is the opposite of the order that other MATLAB functions use.
List of All Elements of a Galois Field. Some Galois field functions in this toolbox require an argument that lists all elements of an extension field GF(p^{m}). This is again relative to a particular primitive element A of GF(p^{m}). The proper format for the list of elements is that of a matrix having p^{m} rows, one for each element of the field. The matrix has m columns, one for each coefficient of a power of A in the polynomial format shown in Polynomial Format above. The first row contains only zeros because it corresponds to the zero element in GF(p^{m}). If k is between 2 and p^{m}, then the kth row specifies the polynomial format of the element A^{k2}.
The minimal polynomial of A aids in the computation of this matrix, because it tells how to express A^{m} in terms of lower powers of A. For example, the table below lists the elements of GF(3^{2}), where A is a root of the primitive polynomial 2 + 2x + x^{2}. This polynomial allows repeated use of the substitution
A^{2} = 2  2A = 1 + A
when performing the computations in the middle column of the table.
Elements of GF(9)
Exponential Format  Polynomial Format  Row of MATLAB Matrix of Elements 

A^{Inf}  0  0 0

A^{0}  1  1 0

A^{1}  A  0 1 
A^{2}  1+A  1 1 
A^{3}  A + A^{2} = A + 1 + A = 1 + 2A  1 2 
A^{4}  A + 2A^{2} = A + 2 + 2A = 2  2 0 
A^{5}  2A  0 2 
A^{6}  2A^{2} = 2 + 2A  2 2 
A^{7}  2A + 2A^{2} = 2A + 2 + 2A = 2 + A  2 1 
Example
An automatic way to generate the matrix whose rows are in the third column of the table above is to use the code below.
p = 3; m = 2;
% Use the primitive polynomial 2 + 2x + x^2 for GF(9).
prim_poly = [2 2 1];
field = gftuple([1:p^m2]',prim_poly,p);
The gftuple
function is discussed in more detail in
Converting and Simplifying Element Formats.
Nonuniqueness of Representations. A given field has more than one primitive element. If two primitive elements have different minimal polynomials, then the corresponding matrices of elements will have their rows in a different order. If the two primitive elements share the same minimal polynomial, then the matrix of elements of the field is the same.
Note
You can use whatever primitive element you want, as long as you understand how the inputs and outputs of Galois field functions depend on the choice of some primitive polynomial. It is usually best to use the same primitive polynomial throughout a given script or function.
Other ways in which representations of elements are not unique arise from the equations that Galois field elements satisfy. For example, an exponential format of 8 in GF(9) is really the same as an exponential format of 0, because A^{8} = 1 = A^{0} in GF(9). As another example, the substitution mentioned just before the table Elements of GF(9) shows that the polynomial format [0 0 1] is really the same as the polynomial format [1 1].
Default Primitive Polynomials
This toolbox provides a default primitive polynomial for
each extension field. You can retrieve this polynomial using the
gfprimdf
function. The command
prim_poly = gfprimdf(m,p); % If m and p are already defined
produces the standard rowvector representation of the default minimal polynomial for GF(p^{m}).
For example, the command below shows that the default primitive polynomial for GF(9) is 2 + x + x^{2}, not the polynomial used in List of All Elements of a Galois Field.
poly1=gfprimdf(2,3);
poly1 = 2 1 1
To generate a list of elements of GF(p^{m}) using the default primitive polynomial, use the command
field = gftuple([1:p^m2]',m,p);
Converting and Simplifying Element Formats
Converting to Simplest Polynomial Format. The gftuple
function produces the simplest polynomial
representation of an element of GF(p^{m}), given
either an exponential representation or a polynomial representation of that
element. This can be useful for generating the list of elements of
GF(p^{m}) that other functions require.
Using gftuple
requires three arguments: one
representing an element of GF(p^{m}), one indicating
the primitive polynomial that MATLAB technical computing software should use when computing the
output, and the prime p. The table below indicates how
gftuple
behaves when given the first two arguments
in various formats.
Behavior of gftuple Depending on Format of First Two Inputs
How to Specify Element  How to Indicate Primitive Polynomial  What gftuple Produces 

Exponential format; c = any integer  Integer m > 1  Polynomial format of A^{c}, where A is a root of the default primitive polynomial for GF(p^{m}) 
Example: tp =
gftuple(6,2,3); % c = 6
here
 
Exponential format; c = any integer  Vector of coefficients of primitive polynomial  Polynomial format of A^{c}, where A is a root of the given primitive polynomial 
Example:
polynomial = gfprimdf(2,3); tp =
gftuple(6,polynomial,3); % c = 6
here
 
Polynomial format of any degree  Integer m > 1  Polynomial format of degree < m, using default primitive polynomial for GF(p^{m}) to simplify 
Example: tp =
gftuple([0 0 0 0 0 0 1],2,3);
 
Polynomial format of any degree  Vector of coefficients of primitive polynomial  Polynomial format of degree < m, using the given primitive polynomial for GF(p^{m}) to simplify 
Example:
polynomial = gfprimdf(2,3); tp = gftuple([0
0 0 0 0 0 1],polynomial,3);

The four examples that appear in the table above all produce the same
vector tp = [2, 1]
, but their different inputs to
gftuple
correspond to the lines of the table. Each
example expresses the fact that
A^{6} = 2+A, where A is a root of the
(default) primitive polynomial
2 + x+ x^{2} for
GF(3^{2}).
Example
This example shows how gfconv
and
gftuple
combine to multiply two polynomialformat
elements of GF(3^{4}). Initially,
gfconv
multiplies the two polynomials, treating the
primitive element as if it were a variable. This produces a highorder
polynomial, which gftuple
simplifies using the
polynomial equation that the primitive element satisfies. The final result
is the simplest polynomial format of the product.
p = 3; m = 4; a = [1 2 0 1]; b = [2 2 1 2]; notsimple = gfconv(a,b,p) % a times b, using high powers of alpha simple = gftuple(notsimple,m,p) %Highest exponent of alpha is m1
The output is below.
notsimple = 2 0 2 0 0 1 2 simple = 2 1 0 1
Example: Generating a List of Galois Field Elements. This example applies the conversion functionality to the task of
generating a matrix that lists all elements of a Galois field. A matrix that
lists all field elements is an input argument in functions such as
gfadd
and gfmul
. The variables
field1
and field2
below have the
format that such functions expect.
p = 5; % Or any prime number m = 4; % Or any positive integer field1 = gftuple([1:p^m2]',m,p); prim_poly = gfprimdf(m,p); % Or any primitive polynomial % for GF(p^m) field2 = gftuple([1:p^m2]',prim_poly,p);
Converting to Simplest Exponential Format. The same function gftuple
also produces the simplest
exponential representation of an element of
GF(p^{m}), given either an exponential
representation or a polynomial representation of that element. To retrieve
this output, use the syntax
[polyformat, expformat] = gftuple(...)
The input format and the output polyformat
are as in
the table Behavior of gftuple Depending on Format of First Two Inputs. In
addition, the variable expformat
contains the simplest
exponential format of the element represented in
polyformat
. It is simplest in
the sense that the exponent is either Inf
or a number
between 0 and p^{m}2.
Example
To recover the exponential format of the element 2 + A that the
previous section considered, use the commands below. In this case,
polyformat
contains redundant information, while
expformat
contains the desired result.
[polyformat, expformat] = gftuple([2 1],2,3)
polyformat = 2 1 expformat = 6
This output appears at first to contradict the information in the table Elements of GF(9) , but in fact it does not. The table uses a different primitive element; two plus that primitive element has the polynomial and exponential formats shown below.
prim_poly = [2 2 1]; [polyformat2, expformat2] = gftuple([2 1],prim_poly,3)
The output below reflects the information in the bottom line of the table.
polyformat2 = 2 1 expformat2 = 7
Arithmetic in Galois Fields
Section Overview. You can add, subtract, multiply, and divide elements of Galois fields
using the functions gfadd
, gfsub
,
gfmul
, and gfdiv
,
respectively. Each of these functions has a mode for prime fields and
a mode for extension
fields.
Arithmetic in Prime Fields. Arithmetic in GF(p) is the same as arithmetic modulo p. The functions
gfadd
, gfmul
,
gfsub
, and gfdiv
accept two
arguments that represent elements of GF(p) as integers between 0 and p1.
The third argument specifies p.
Example: Addition Table for GF(5)
The code below constructs an addition table for GF(5). If
a
and b
are between 0 and 4, then
the element gfp_add(a+1,b+1)
represents the sum
a+b
in GF(5). For example, gfp_add(3,5) =
1
because 2+4 is 1 modulo 5.
p = 5; row = 0:p1; table = ones(p,1)*row; gfp_add = gfadd(table,table',p)
The output for this example follows.
gfp_add = 0 1 2 3 4 1 2 3 4 0 2 3 4 0 1 3 4 0 1 2 4 0 1 2 3
Other values of p
produce tables for different prime
fields GF(p
). Replacing gfadd
by
gfmul
, gfsub
, or
gfdiv
produces a table for the corresponding
arithmetic operation in GF(p
).
Arithmetic in Extension Fields. The same arithmetic functions can add elements of GF(p^{m}) when m > 1, but the format of the arguments is more complicated than in the case above. In general, arithmetic in extension fields is more complicated than arithmetic in prime fields; see the works listed in Selected Bibliography for Galois Fields for details about how the arithmetic operations work.
When working in extension fields, the functions
gfadd
, gfmul
,
gfsub
, and gfdiv
use the first
two arguments to represent elements of GF(p^{m}) in
exponential format. The third argument, which is required, lists all
elements of GF(p^{m}) as described in List of All Elements of a Galois Field. The result is in
exponential format.
Example: Addition Table for GF(9)
The code below constructs an addition table for
GF(3^{2}), using exponential formats relative to
a root of the default primitive polynomial for GF(9). If
a
and b
are between 1 and 7, then
the element gfpm_add(a+2,b+2)
represents the sum of
A^{a }and A^{b }in
GF(9). For example, gfpm_add(4,6) = 5
because
A^{2} + A^{4} = A^{5 }
Using the fourth and sixth rows of the matrix field
,
you can verify that
A^{2} + A^{4} = (1 + 2A) + (2 + 0A) = 3 + 2A = 0 + 2A = A^{5} modulo 3.
p = 3; m = 2; % Work in GF(3^2). field = gftuple([1:p^m2]',m,p); % Construct list of elements. row = 1:p^m2; table = ones(p^m,1)*row; gfpm_add = gfadd(table,table',field)
The output is below.
gfpm_add = Inf 0 1 2 3 4 5 6 7 0 4 7 3 5 Inf 2 1 6 1 7 5 0 4 6 Inf 3 2 2 3 0 6 1 5 7 Inf 4 3 5 4 1 7 2 6 0 Inf 4 Inf 6 5 2 0 3 7 1 5 2 Inf 7 6 3 1 4 0 6 1 3 Inf 0 7 4 2 5 7 6 2 4 Inf 1 0 5 3
Note
If you used a different primitive polynomial, then the tables would look different. This makes sense because the ordering of the rows and columns of the tables was based on that particular choice of primitive polynomial and not on any natural ordering of the elements of GF(9).
Other values of p
and m
produce
tables for different extension fields GF(p^m
). Replacing
gfadd
by gfmul
,
gfsub
, or gfdiv
produces a
table for the corresponding arithmetic operation in
GF(p^m
).
Polynomials over Prime Fields
Section Overview. A polynomial over GF(p) is a polynomial whose coefficients are elements of GF(p). Communications Toolbox software provides functions for
Changing polynomials in cosmetic ways
Performing polynomial arithmetic
Characterizing polynomials as primitive or irreducible
Finding roots of polynomials in a Galois field
Note
The Galois field functions in this toolbox represent a polynomial over GF(p) for odd values of p as a vector that lists the coefficients in order of ascending powers of the variable. This is the opposite of the order that other MATLAB functions use.
Cosmetic Changes of Polynomials. To display the traditionally formatted polynomial that corresponds to a
row vector containing coefficients, use gfpretty
. To
truncate a polynomial by removing all zerocoefficient terms that have
exponents higher than the degree of the polynomial, use
gftrunc
. For example,
polynom = gftrunc([1 20 394 10 0 0 29 3 0 0]) gfpretty(polynom)
The output is below.
polynom = 1 20 394 10 0 0 29 3 2 3 6 7 1 + 20 X + 394 X + 10 X + 29 X + 3 X
Note
If you do not use a fixedwidth font, then the spacing in the display might not look correct.
Polynomial Arithmetic. The functions gfadd
and gfsub
add and subtract, respectively, polynomials over GF(p). The
gfconv
function multiplies polynomials over GF(p).
The gfdeconv
function divides polynomials in GF(p),
producing a quotient polynomial and a remainder polynomial. For example, the
commands below show that
2 + x + x^{2} times
1 + x over the field GF(3) is
2 + 2x^{2} + x^{3}.
a = gfconv([2 1 1],[1 1],3) [quot, remd] = gfdeconv(a,[2 1 1],3)
The output is below.
a = 2 0 2 1 quot = 1 1 remd = 0
The previously discussed functions gfadd
and
gfsub
add and subtract, respectively, polynomials.
Because it uses a vector of coefficients to represent a polynomial,
MATLAB does not distinguish between adding two polynomials and adding
two row vectors elementwise.
Characterization of Polynomials. Given a polynomial over GF(p), the gfprimck
function
determines whether it is irreducible and/or primitive. By definition, if it
is primitive then it is irreducible; however, the reverse is not necessarily
true. The gfprimdf
and gfprimfd
functions return primitive polynomials.
Given an element of GF(p^{m}), the
gfminpol
function computes its minimal polynomial
over GF(p).
Example
For example, the code below reflects the irreducibility of all minimal polynomials. However, the minimal polynomial of a nonprimitive element is not a primitive polynomial.
p = 3; m = 4; % Use default primitive polynomial here. prim_poly = gfminpol(1,m,p); ckprim = gfprimck(prim_poly,p); % ckprim = 1, since prim_poly represents a primitive polynomial. notprimpoly = gfminpol(5,m,p); cknotprim = gfprimck(notprimpoly,p); % cknotprim = 0 (irreducible but not primitive) % since alpha^5 is not a primitive element when p = 3. ckreducible = gfprimck([0 1 1],p); % ckreducible = 1 since the polynomial is reducible.
Roots of Polynomials. Given a polynomial over GF(p), the gfroots
function
finds the roots of the polynomial in a suitable extension field
GF(p^{m}). There are two ways to tell
MATLAB the degree m of the extension field
GF(p^{m}), as shown in the following table.
Formats for Second Argument of gfroots
Second Argument  Represents 

A positive integer  m as in GF(p^{m}). MATLAB uses the default primitive polynomial in its computations. 
A row vector  A primitive polynomial for GF(p^{m}). Here m is the degree of this primitive polynomial. 
Example: Roots of a Polynomial in GF(9)
The code below finds roots of the polynomial 1 + x^{2} + x^{3} in GF(9) and then checks that they are indeed roots. The exponential format of elements of GF(9) is used throughout.
p = 3; m = 2; field = gftuple([1:p^m2]',m,p); % List of all elements of GF(9) % Use default primitive polynomial here. polynomial = [1 0 1 1]; % 1 + x^2 + x^3 rts =gfroots(polynomial,m,p) % Find roots in exponential format % Check that each one is actually a root. for ii = 1:3 root = rts(ii); rootsquared = gfmul(root,root,field); rootcubed = gfmul(root,rootsquared,field); answer(ii)= gfadd(gfadd(0,rootsquared,field),rootcubed,field); % Recall that 1 is really alpha to the zero power. % If answer = Inf, then the variable root represents % a root of the polynomial. end answer
The output shows that A^{0} (which equals 1), A^{5}, and A^{7} are roots.
roots = 0 5 7 answer = Inf Inf Inf
See the reference page for gfroots
to see how
gfroots
can also provide you with the polynomial
formats of the roots and the list of all elements of the field.
Other Galois Field Functions
See the online reference pages for information about these other Galois field functions in Communications Toolbox software:
Selected Bibliography for Galois Fields
[1] Blahut, Richard E., Theory and Practice of Error Control Codes, Reading, Mass., AddisonWesley, 1983.
[2] Lang, Serge, Algebra, Third Edition, Reading, Mass., AddisonWesley, 1993.
[3] Lin, Shu, and Daniel J. Costello, Jr., Error Control Coding: Fundamentals and Applications, Englewood Cliffs, N.J., PrenticeHall, 1983.
[4] van Lint, J. H., Introduction to Coding Theory, New York, SpringerVerlag, 1982.