Error correcting capability

CRC-Code Features

Cyclic redundancy check (CRC) coding is an error-control coding technique for
detecting errors that occur when a message is transmitted. Unlike block or
convolutional codes, CRC codes do not have a built-in error-correction
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 double-clicking its icon in
the main Communications Toolbox™ block library. Open the CRC sublibrary by double-clicking 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 Non-Direct Algorithm

The CRC non-direct 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:

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³ +
x² + 1.

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 Non-Direct Algorithm

Suppose the input frame is [1 1 0 0 1 1 0]', corresponding
to the polynomial M = x⁶
+x
⁵ + x²
+ x, and the generator polynomial is
P = x³ +
x² + 1, of degree
r = 3. By polynomial division,
M*x³
= (x⁶ +
x³ +
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 m0, m1, … , mk−1

Code Word Output is c0, c1,…​​ ,​ cn−1=m0, m1,…​​ ,mk−1,︸Xd0,d1, … , dn−k−1︸Y

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

Block-Coding Features

Error-control 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 error-control 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 error-control
coding.

Block coding is a special case of error-control coding. Block-coding
techniques map a fixed number of message symbols to a fixed number of code
symbols. A block coder treats each block of data independently and is a
memoryless device. Communications Toolbox contains block-coding capabilities by providing Simulink blocks, System objects, and MATLAB functions.

The class of block-coding techniques includes categories shown in the diagram
below.

Communications Toolbox supports general linear block codes. It also process cyclic, BCH,
Hamming, and Reed-Solomon 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 Reed-Solomon and BCH decoders indicate how
many errors they detected while decoding. The Reed-Solomon coding blocks also
let you decide whether to use symbols or bits as your data.

Communications Toolbox Support Functions.  Functions in Communications Toolbox can support simulation blocks by

For more information about error-control 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). Reed-Solomon coding blocks also
let you choose between binary and integer data, as described in Integer Format (Reed-Solomon 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 four-bit message and
producing a five-bit codeword at time 0. It repeats this process with a new
message at time 1.

For all coding techniques except Reed-Solomon using
binary input, the message vector must have length K and the corresponding
code vector has length N. For Reed-Solomon 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 Binary-Input RS Encoder block and the
Binary-Output RS Decoder block use this format for messages and
codewords.

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

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

Using Serial Signals

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

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

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

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

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

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:

Examples of Block Coding

Example: Reed-Solomon Code in Integer Format.  This example uses a Reed-Solomon 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:

Connect the blocks as shown in the preceding figure. On the
tab, in the
section, set Stop
time to 500. The
section appears on multiple
tabs.

You can display the vector length of signals in your model. On the
tab, expand . In the
section, select .

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. Right-click the plot area in the second scope
and select . On the
tab, adjust the axes limits.

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 Block-Coding 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
Reed-Solomon 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
Error-correction truth table parameters.

Generator Matrix — The process of encoding a message into
an [N,K] linear block code is determined by a K-by-N generator matrix
G. Specifically, a 1-by-K message vector
v is encoded into the 1-by-N codeword vector
vG. If G has the form
[I_k, P] or
[P, I_k], where
P is some K-by-(N-K) matrix and
I_k is the K-by-K identity matrix,
G is said to be in standard form.
(Some authors, such as Clark and Cain [2], use the first standard form, while others, such as Lin and Costello [3], use the second.) The linear block-coding 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 single-symbol 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 Error-correction truth
table parameter. Represent a decoding table as a matrix with N
columns and 2^N-K rows. Each row gives a correction
vector for one received codeword vector.

You can avoid specifying a decoding table explicitly, by setting the
Error-correction truth table parameter to
0. When Error-correction 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 so-called generator polynomial is a degree-(N-K) 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 N-M.

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 error-correcting 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 error-correction
capability for BCH codes.

Narrow-Sense BCH Codes

The narrow-sense generator polynomial is LCM[m_1(x), m_2(x), …, m_2t(x)],
where:

Reed-Solomon Codes

Reed-Solomon codes are useful for correcting errors that occur in bursts. In
the simplest case, the length of codewords in a Reed-Solomon code is of the form
N= 2^M-1, where the 2^M is
the number of symbols for the code. The error-correction capability of a
Reed-Solomon code is floor((N-K)/2), where K is the length of
message words. The difference N-K must be even.

It is sometimes convenient to use a shortened Reed-Solomon code in which N is
less than 2^M-1. In this case, the encoder appends
2^M-1-N zero symbols to each message word and
codeword. The error-correction capability of a shortened Reed-Solomon code is
also floor((N-K)/2). The Communications Toolbox Reed-Solomon blocks can implement shortened Reed-Solomon
codes.

Effect of Nonbinary Symbols — One difference between
Reed-Solomon codes and the other codes supported in this product is that
Reed-Solomon codes process symbols in GF(2^M) instead
of GF(2). M bits specify each symbol. The nonbinary nature of the Reed-Solomon
code symbols causes the Reed-Solomon blocks to differ from other coding blocks
in these ways:

Error Information — The Reed-Solomon decoding blocks
(Binary-Output RS Decoder and Integer-Output RS Decoder) return
error-related 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₁I₂. (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 three-symbol message
of 0I₁I₂. The modified message
sequence is RS encoded, and the added information zero is then removed, which
yields a result of
I₁I₂P₁P₂P₃P₄.
(In this example, the parity bits are at the end of the codeword.)

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

Decoder Example with Shortening and
Puncturing

The following figure shows how the RS 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 erasure-correcting capability of
the code, which can correct four erasures. The decoding operation results in the
three-symbol message DI₁I₂. The
first symbol is truncated, as in the preceding figure, yielding a final output
of I₁I₂.

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

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

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

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

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

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

Reed-Solomon Code in Integer Format

To open an example model that uses a Reed-Solomon code in integer format, type
doc_rscoding at the MATLAB command line. For more information about the model, see Example: Reed-Solomon Code in Integer Format

Find a Generator Polynomial

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

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

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

genpolyCyclic =

     1     0     0     0     0     1     0     0     0     0     1


genpolyBCH = GF(2) array.

Array elements =

     1     0     1     0     0     1     1     0     1     1     1


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

Array elements =

     1     4     8    10    12     9     4     2    12     2     7

The formats of these outputs vary:

Nonuniqueness of Generator Polynomials

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

Algebraic Expression for Generator
Polynomials

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

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.

Selected Bibliography for Block Coding

Convolutional Code Features

Convolutional coding is a special case of error-control coding. Unlike a block
coder, a convolutional coder is not a memoryless device. Even though a
convolutional coder accepts a fixed number of message symbols and produces a
fixed number of code symbols, its computations depend not only on the current
set of input symbols but on some of the previous input symbols.

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 hard-decision
and soft-decision 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:

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 convolutional-coding blocks, simply place
a poly2trellis command such as

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:

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 k-by-n 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:

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].

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.

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 one-bit input, and a two-bit output. (The ratio of input bits to output
bits makes this encoder a rate-1/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.

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 i-1 and the
input bits have decimal representation j-1. 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 i-1 and
the input bits have decimal representation j-1. 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:

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 two-bit 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.

Hard-Decision 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, hard-decision decoding can use
the output of convenc directly, without additional
processing. This example extends the previous example and implements
hard-decision 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))

Soft-Decision Decoding.  To decode using soft decisions, use the vitdec
function with the flag 'soft'. Specify the number,
nsdec, of soft-decision bits and use input data
consisting of integers between 0 and 2^nsdec-1.

An input of 0 represents the most confident 0, while an input of
2^nsdec-1 represents the most confident 1. Other
values represent less confident decisions. For example, the table below
lists interpretations of values for 3-bit soft decisions.

Implement Soft-Decision Decoding Using
MATLAB

The script below illustrates decoding with 3-bit soft decisions. First it
creates a convolutional code with convenc and adds
white Gaussian noise to the code with awgn. Then, to
prepare for soft-decision decoding, the example uses
quantiz to map the noisy data values to appropriate
decision-value 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 soft-decision 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 Soft-Decision Decoding Using Simulink.  This example creates a rate 1/2 convolutional code. It uses a quantizer
and the Viterbi Decoder block to perform soft-decision 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 1-by-2 matrix of octal numbers because the encoder
has one input and two outputs. The first element in the matrix indicates
which input values contribute to the first output, and the second element in
the matrix indicates which input values contribute to the second
output.

For example, the first output in the encoder diagram is the modulo-2 sum
of the rightmost and the four leftmost elements in the diagram’s array of
input values. The seven-digit binary number 1111001 captures this
information, and is equivalent to the octal number 171. The octal number 171
thus becomes the first entry of the code generator matrix. Here, each
triplet of bits uses the leftmost bit as the most significant bit. The
second output corresponds to the binary number 1011011, which is equivalent
to the octal number 133. The code generator is therefore
[171 133].

The Trellis structure parameter in the Convolutional
Encoder block tells the block which code to use when processing data. In
this case, the poly2trellis function, in
Communications Toolbox, converts the constraint length and the pair of octal numbers
into a valid trellis structure.

While the message data entering the Convolutional Encoder block is a
scalar bit stream, the encoded data leaving the block is a stream of binary
vectors of length 2.

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

The combination of this mapping and the Viterbi Decoder block’s decision
mapping reverses the BPSK modulation that the BPSK Modulator Baseband block
performs on the transmitting side of this model. To examine the demodulator
subsystem in more detail, double-click the icon labeled Soft-Output BPSK
Demodulator.

Decoding the Convolutional Code

After the received data is properly mapped to length-2 vectors of 3-bit
decision values, the Viterbi Decoder block decodes it. The block uses a
soft-decision algorithm with 2³ different input
values because the Decision type parameter is
Soft Decision and the Number of
soft decision bits parameter is 3.

Soft-Decision Interpretation of
Data

When the Decision type parameter is set to
Soft Decision, the Viterbi Decoder block
requires input values between 0 and 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.

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.

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.

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

Design a Rate-2/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 2-by-3 matrix of octal
numbers, use the element in the ith row and jth column to indicate how the
ith input contributes to the jth output. For example, to compute the element
in the second row and third column, 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 2-bit 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 2-bit symbols and
produces a vector containing 3-bit 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 2-by-3 matrix of octal
numbers, use the element in the ith row and jth column to indicate how the
ith input contributes to the jth output. For example, to compute the element
in the second row and third column, notice that the leftmost and two
rightmost elements in the second shift register of the diagram feed into the
sum that forms the third output. Capture this information as the binary
number 1011, which is equivalent to the octal number 13. The full value of
the code generator matrix is [27 33 0; 0 5 13].

To use the constraint length and code generator parameters in the
Convolutional Encoder and Viterbi Decoder blocks, use the
poly2trellis function to convert those parameters
into a trellis structure.

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:

Connect the blocks as shown in the preceding figure. On the
tab, in the
section, set Stop
time to inf. The
section appears on multiple
tabs.

Notes on the Model.  You can display the matrix size of signals in your model. On the
tab, expand . In the
section, select .

The encoder accepts a 2-by-1 column vector and produces a 3-by-1 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 rate-3/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 = 1-2*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: %dn', berP(2))
fprintf('Number of errors with puncturing and erasures: %dn', 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

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.

Soft-Decision Decoding

This example creates a rate 1/2 convolutional code. It uses a quantizer and
the Viterbi Decoder block to perform soft-decision decoding. This description
covers these topics:

• Overview of the Simulation

• Defining the Convolutional Code

• Mapping the Received Data

• Decoding the Convolutional Code

• Delay in Received Data

• Comparing Simulation Results with Theoretical Results

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⁷ 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 1-by-2 matrix of octal numbers because the encoder
has one input and two outputs. The first element in the matrix indicates
which input values contribute to the first output, and the second element in
the matrix indicates which input values contribute to the second
output.

For example, the first output in the encoder diagram is the modulo-2 sum
of the rightmost and the four leftmost elements in the diagram’s array of
input values. The seven-digit binary number 1111001 captures this
information, and is equivalent to the octal number 171. The octal number 171
thus becomes the first entry of the code generator matrix. Here, each
triplet of bits uses the leftmost bit as the most significant bit. The
second output corresponds to the binary number 1011011, which is equivalent
to the octal number 133. The code generator is therefore
[171 133].

The Trellis structure parameter in the Convolutional
Encoder block tells the block which code to use when processing data. In
this case, the poly2trellis function, in
Communications Toolbox, converts the constraint length and the pair of octal numbers
into a valid trellis structure.

While the message data entering the Convolutional Encoder block is a
scalar bit stream, the encoded data leaving the block is a stream of binary
vectors of length 2.

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

The combination of this mapping and the Viterbi Decoder block’s decision
mapping reverses the BPSK modulation that the BPSK Modulator Baseband block
performs on the transmitting side of this model. To examine the demodulator
subsystem in more detail, double-click the icon labeled Soft-Output BPSK
Demodulator.

Decoding the Convolutional Code.  After the received data is properly mapped to length-2 vectors of 3-bit
decision values, the Viterbi Decoder block decodes it. The block uses a
soft-decision algorithm with 2³ different input
values because the Decision type parameter is
Soft Decision and the Number of
soft decision bits parameter is 3.

Soft-Decision Interpretation of
Data

When the Decision type parameter is set to
Soft Decision, the Viterbi Decoder block
requires input values between 0 and 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.

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 unquantized-decision
decoding:

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

where R is the code rate of 1/2, and erfc is the MATLAB complementary error function, defined by

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₀
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(d-9,:) = (1/2)*erfc(sqrt(d*R*10.^(EbNoVec/10)));
end
% Bounds is the vector of upper bounds for the bit error
% rate, for Eb/No values in EbNoVec.
Bounds = Errs*P;

Simulating Multiple Times to Collect Bit Error
Rates

You can efficiently vary the simulation parameters by using the sim (Simulink) function to run the
simulation from the MATLAB command line. For example, the following code calculates the
bit error rate at bit energy-to-noise ratios ranging from 1 dB to 4 dB, in
increments of 0.5 dB. It collects all bit error rates from these simulations
in the matrix BERVec. It also plots the bit error rates
in a figure window along with the theoretical bounds computed in the
preceding code fragment.

The plot of bit error rate against signal-to-noise ratio follows. The
locations of your actual BER points might vary because the simulation
involves random numbers.

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:

Refer to [8] for a theoretical calculation of the initial state
X₀ from
X_N
^[zs] using state-space formulation. This is a
one-time calculation which depends on the block length and in practice could be
implemented as a look-up table. Here we determine this mapping table by
simulating all possible entries for a chosen trellis and block length.

To open the 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 zero-state response.

% All possible combinations of the mappings
mapStValuesTab = perms(0:trellis.numStates-1);

% 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
(n-D) block in the Lookup subsystem will perform tailbiting
encoding for the chosen block length and trellis.

Selected Bibliography for Convolutional Coding

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 Reed-Solomon codes, see Represent Words for BCH Codes or Represent Words for Reed-Solomon 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 4-digit (because k = 4)
messages. The resulting vector code comprises three
6-digit (because n = 6) codewords, which are
concatenated to form a vector of length 18. The parity bits are at the
beginning of each codeword.

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 4-bit message on a distinct row in
msg and each 6-bit codeword on a distinct row in
code.

n = 6; k = 4; % Set codeword length and message length.
msg = [1 0 0 1; 1 0 1 0; 1 0 1 1]; % Message is a binary matrix.
code = encode(msg,n,k,'cyclic'); % Code will be a binary matrix.
msg
code

The output is below.

msg =

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


code =

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

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.

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.

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.

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

Some examples of generator matrices are in the next section, Parity-Check Matrix.

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

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

I_k is the identity matrix of size k and the
' symbol indicates matrix transpose. (For
binary codes, the minus signs in the parity-check
form listed above are irrelevant; that is, -1 = 1 in the binary
field.)

Examples

In the command below, parmat is a parity-check matrix
and genmat is a generator matrix for a Hamming code in
which
[n,k] = [2³-1, n-3] = [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 parity-check and generator matrices for a [7,3]
cyclic code. The cyclpoly function is mentioned below
in Generator Polynomial.

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

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

genmat =

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

The example below converts a generator matrix for a [5,3] linear block
code into the corresponding parity-check matrix.

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

parmat =

     1     1     0     1     0
     0     1     1     0     1

The same function gen2par can also convert a
parity-check matrix into a generator matrix.

Generator Polynomial.  Cyclic codes have algebraic properties that allow a polynomial to
determine the coding process completely. This so-called generator
polynomial is a degree-(n-k) divisor of the polynomial
xⁿ-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² + x³ + x⁴.

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 single-symbol error in any codeword. Other codes can correct, or partially correct, errors that corrupt more than one symbol in a given codeword.

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

This example uses a Hamming decoding table to correct an error in a received message. The hammgen function produces the parity-check matrix and the syndtable function produces the decoding table. To determine the syndrome, the transpose of the parity-check 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^m-1; 
k = n-m;

Produce a parity-check matrix and decoding table.

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

Specify a vector of received data.

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^(n-k),n);  % No correction of errors
% Decode, keeping track of all detected errors.
[newmsg,err] = decode(noisycode,n,k,'linear',genmat,trt);
err_words = find(err~=0) % Find out which words had errors.

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

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:

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.

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 frame-based column vectors as the transmitted and received
signals, this example uses frame-based column vectors throughout. (It thus
avoids having to change signal attributes using a block such as Convert 1-D to 2-D.)

Open this model by entering doc_hamming at the
MATLAB command line. To build the model, gather and configure these
blocks:

Connect the blocks as in the preceding figure. You can display the vector
length of signals in your model. On the tab,
expand . In the
section, select . 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 frame-based 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
error-correcting 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:

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

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

Labeling the Display Block

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

Running the Hamming Code Model

To run the model, select >
. 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(0.99)⁶(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 tab, expand . In the section,
select . The line leading out of the
Bernoulli Binary Generator block is labeled
[4x1], indicating that its output consists of column
vectors of size 4. Because the Hamming Encoder block uses a [7,4]
code, it converts frames of size 4 into frames of size 7, so its output is
labeled [7x1].

Adding a Scope to the Model

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

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

Setting Parameters in the Expanded
Model

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

Observing Channel Errors with the
Scope

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

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

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

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

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

When you are done observing the errors, select
>
.

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

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:

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

• Detect and Correct Errors in a BCH Code Using MATLAB

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,n-k);
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 prepend-to-append conversion worked correctly.
d1_append = step(dec,c1_append);
chk = isequal(msg,d1_append)

The output is below.

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 error-correction capability.
nw = 4; % Number of words to process
msgw = randi([0 1], nw*k, 1); % Random k-symbol 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.

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
error-correction capability. To learn more about how the BCH Decoder
System object behaves when the noise is excessive, see the analogous
discussion for Reed-Solomon codes in Excessive Noise in Reed-Solomon Codewords.

Algorithms for BCH and RS Errors-only Decoding

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

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

Syndrome Calculation.  For narrow-sense codes, the 2t terms of S(z) are calculated by evaluating the received codeword at
successive powers of α (the field’s primitive element) from 0 to
2t-1. In other words, if we assume one-based indexing
of codewords C(z) and the syndrome polynomial S(z), and that codewords are of the form [c1 c1 …  cN], then each term Si of S(z) is given as

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.

The following diagram shows the iterative procedure (i.e., the Berlekamp
algorithm) used to find Λ(z).

Error Evaluator Polynomial Calculation.  The error evaluator polynomial, Ω(z), is simply the convolution of Λ(z) and S(z).

Represent Words for Reed-Solomon Codes

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

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

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

The output is

C =

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

Parameters for Reed-Solomon Codes

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

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

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

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

Array elements =

     1     6     8

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

Algebraic Expression for Generator
Polynomials

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

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

Create and Decode Reed-Solomon Codes

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

This section illustrates how to use the RS
Encoder and RS Decoder System
objects. The topics are

• Reed-Solomon Coding Syntaxes in MATLAB

• Detect and Correct Errors in a Reed-Solomon Code Using MATLAB

• Excessive Noise in Reed-Solomon Codewords

• Create Shortened Reed-Solomon Codes

Reed-Solomon Coding Syntaxes in MATLAB.  The example below illustrates multiple ways to encode and decode data
using a [15,13] Reed-Solomon code. The example shows that you can

This example also shows that corresponding syntaxes of the 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^m-1; k = 13; % Codeword length and message length
msg = randi([0 m-1],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,n-k);
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 prepend-to-append conversion worked correctly.
d3_append = step(hDec,c3_append);
chk = isequal(msg,d3_append)

The output is

Detect and Correct Errors in a Reed-Solomon 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^m-1; k = 3; % Codeword length and message length
t = (n-k)/2; % Error-correction capability of the code
nw = 4; % Number of words to process
msgw = randi([0 n],nw*k,1); % Random k-symbol messages
hEnc = comm.RSEncoder(n,k);
hDec = comm.RSDecoder(n,k);
c = step(hEnc, msgw); % Encode the data.
noise = (1+randi([0 n-1],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.

Excessive Noise in Reed-Solomon Codewords.  In the previous example, RS Encoder
System object corrected all of the errors. However, each Reed-Solomon code
has a finite error-correction capability. If the noise is so great that the
corrupted codeword is too far in Hamming distance from the correct codeword,
that means either

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 n-1],nw,n)).*randerr(nw,n,t+1); % t+1 errors/row

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

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

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

How the RS Encoder
System Object Creates a Shortened Code

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

The following example illustrates this process.

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

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

Find a Generator Polynomial

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

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

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

genpolyCyclic =

     1     0     0     0     0     1     0     0     0     0     1

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

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

The formats of these outputs vary:

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

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

Reed Solomon Examples with Shortening, Puncturing, and Erasures

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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]:

The definitions imply that a primitive element is a root of a corresponding
primitive polynomial.

Representing Elements of Galois Fields

• Section Overview

• Creating a Galois field array

• Example: Creating Galois Field Variables

• Example: Representing Elements of GF(8)

• How Integers Correspond to Galois Field Elements

• Example: Representing a Primitive Element

• Primitive Polynomials and Element Representations

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 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 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

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)

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^m-1. 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^m-1 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 m-1. 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 m-1, 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.

Example: Representing a Primitive Element.  The code below defines a variable alph that represents
a primitive element of the field GF(2⁴).

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

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⁴ + D³ + 1.

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(2^4) array. Primitive polynomial = D^4+D^3+1 (25 decimal)

Array elements =

     1     2     3

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

• Example: Addition and Subtraction

• Example: Multiplication

• Example: Division

• Example: Exponentiation

• Example: Elementwise Logarithm

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.

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^m-1],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²+A plus the element
A+1 equals the element A²+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²+1,
and 1+(A²+1) in GF(16) is
A². Furthermore, the integer that represents
the polynomial expression A² 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^m-1]',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^m-1],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

Logical Operations in Galois Fields

• Section Overview

• Testing for Equality

• Testing for Nonzero Values

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 built-in
isequal function. However,
isequal uses strict rules for its comparison, and
returns a value of 0 (false) if you compare

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^m-1],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 Information About Galois Field Arrays

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.

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 2-by-8 matrix.
c = [b([1 1 2],1:3); a(4:6)]; % Create 4-by-3 matrix.
d = [c, a(1:4)']; % Create 4-by-4 matrix.
dvec = diag(d); % Extract main diagonal of d.
dmat = diag(a(5:9)); % Create 5-by-5 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 two-element 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

• Computing Ranks

• Factoring Square Matrices

• Solving Linear Equations

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.

The code below illustrates matrix inversion and determinant
computation.

m = 4;
randommatrix = gf(randi([0 2^m-1],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

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.

The results of the syntax in the table depend on characteristics of the
Galois field array A:

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)]; % 3-by-4 matrix with redundancy on the right
Atall = Awide'; % 4-by-3 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

• Filtering

• Convolution

• Discrete Fourier Transform

Section Overview.  You can perform some signal-processing 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.

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:

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^m-1],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:

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^m-1],2^m-1,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.

Polynomials over Galois Fields

• Section Overview

• Addition and Subtraction of Polynomials

• Multiplication and Division of Polynomials

• Evaluating Polynomials

• Roots of Polynomials

• Roots of Binary Polynomials

• Minimal Polynomials

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

represents the polynomial Ax³ +
1x² + 0x + (A+1), where

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 equal-length 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 degree-one and a
degree-two polynomial.

lin = gf([4 2],3); % A^2 x + A, which is linear in x
linpadded = gf([0 4 2],3); % The same polynomial, zero-padded
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.

The examples below find roots of cubic polynomials in GF(8).

p = 3; m = 2;
field = gftuple([-1:p^m-2]',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:

Minimal Polynomials.  The minimal polynomial of an element of GF(2^m)
is the smallest degree nonzero binary-coefficient 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² + 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

• Determining Whether a Variable Is a Galois Field Array

• Extracting Information from a Galois Field Array

• Use Field Extension Suffixes Appended to Galois Field Array Variables

Section Overview.  This section describes techniques for manipulating Galois variables or for
transferring information between Galois field arrays and ordinary
MATLAB arrays.

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.

Use Field Extension Suffixes Appended to Galois Field Array Variables

Extract information from Galois field arrays by using field extension suffixes.

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

b = double(a.x) % a.x is in uint16

e = gf(6,4);                % An element of GF(16)
emp = minpol(e);            % Minimal polynomial is in GF(2)
empr = roots(gf(emp.x,e.m)) % Find roots of emp in GF(16)

 
empr = GF(2^4) array. Primitive polynomial = D^4+D+1 (19 decimal)
 
Array elements = 
 
   6
   7

primpoly_int = double(e.prim_poly);
mval = e.m;
primpoly_vect = gf(int2bit(primpoly_int,mval+1)',mval);
containstwo = roots(primpoly_vect)

 
containstwo = GF(2^4) array. Primitive polynomial = D^4+D+1 (19 decimal)
 
Array elements = 
 
   2
   3
   4
   5

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):

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.

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

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].

Representing Elements of Galois Fields

• Section Overview

• Exponential Format

• Polynomial Format

• List of All Elements of a Galois Field

• Nonuniqueness of Representations

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
p-1.

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.

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^q-1 = 1 where
q = p^m.

The use of the exponential format is shown in the table below.

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.

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 m-1, and coefficients in GF(p). In the
polynomial format, the element

A(1) + A(2) A + A(3) A² + … + A(m) A^m-1

is represented in MATLAB by the vector

[A(1) A(2) A(3) ... A(m)]

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^k-2.

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²), where A is a root of the primitive
polynomial 2 + 2x + x². This
polynomial allows repeated use of the substitution

A² = -2 — 2A = 1 + A

when performing the computations in the middle column of the table.