| Communications Blockset™ | |
| On this page… |
|---|
Block-Coding Features of the Blockset Communications Toolbox Support Functions Using Block Encoders and Decoders Within a Model Notes on Specific Block-Coding Techniques |
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.
You can open the Error Detection and Correction library by double-clicking its icon in the main Communications Blockset library. Then open the Block sublibrary by double-clicking its icon in the Error Detection and Correction library.
The class of block-coding techniques includes categories shown in the diagram below.
Communications Blockset supports general linear block codes. It also includes blocks that process cyclic, BCH, Hamming, and Reed-Solomon codes (which are all special kinds of linear block codes). Blocks in the blockset can encode or decode a message using one of the techniques mentioned above. 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.
Note The blocks in this blockset are designed for error-control codes that use an alphabet having 2 or 2m symbols. |
Functions in Communications Toolbox can support the Communications Blockset simulation blocks by
Determining characteristics of a technique, such as error-correction capability or possible message lengths
Performing lower-level computations associated with a technique, such as
Computing a truth table
Computing a generator or parity-check matrix
Converting between generator and parity-check matrices
Computing a generator polynomial
For more information about error-control coding capabilities of Communications Toolbox, see Block Coding in the Communications Toolbox User's Guide.
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.
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).
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 share the same sample time.
The figure below illustrates this situation. In this example, the encoder receives a four-bit message and produces 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(2M). 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 in Signal Processing Blockset. Be aware that buffering involves latency and multirate processing. See the reference page for the Buffer block for more details. 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. If you are unsure about the sample times of signals in your model, selecting Sample time colors from the Port/signal displays submenu of the model's Format menu, or attaching Probe blocks (from the Simulink Signal Attributes library) to connector lines might help.
A message word for an [N,K] Reed-Solomon code consists of M*K bits, which you can interpret as K symbols between 0 and 2M. The symbols are binary sequences of length M, corresponding to elements of the Galois field GF(2M), 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.)
Note In this context, Simulink expects the first bit to be the most significant bit in the symbol. "First" means the smallest index in a vector or the smallest time for a series of scalars. |
The following figure illustrates the equivalence between binary and integer signals for a 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 2M. 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.
Once you have configured the coding blocks, a few tips can help you place them correctly within your model:
If a block has multiple outputs, the first one is always the stream of coding data.
The Reed-Solomon and BCH blocks have an error counter as a second output.
Be sure the signal sizes are appropriate for the mask parameters. For example, if you use the Binary Cyclic Encoder block and set Message length K to 4, the input signal must be a vector of length 4.
If you are unsure about the size of signals in your model, selecting Signal dimensions from the Port/signal displays submenu of the model's Format menu might help.
This section presents two example models. The first example processes a Hamming code using the binary format, and the second example processes a Reed-Solomon code using the integer format.
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.)
To open the completed model, click here in the MATLAB Help browser. To build the model, gather and configure these blocks:
Bernoulli Binary Generator, in the Comm Sources library
Set Probability of a zero to .5.
Set Initial seed to any positive integer scalar, preferably the output of the randseed function.
Check the Frame-based outputs check box.
Set Samples per frame to 4.
Hamming Encoder, with default parameter values
Hamming Decoder, with default parameter values
Error Rate Calculation, in the Comm Sinks library, with default parameter values
Connect the blocks as in the preceding figure. Use the Signal dimensions feature from the Port/signal displays submenu of the model window's Format menu. After updating the diagram if necessary (Update diagram from the Edit menu), 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.
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 very simple way of introducing errors into each codeword.
To open the completed model, click here in the MATLAB Help browser. To build the model, gather and configure these blocks:
Random Integer Generator, in the Comm Sources library
Set M-ary number to 15.
Set Initial seed to a positive number, randseed(0) is chosen here.
Check the Frame-based outputs check box.
Set Samples per frame to 5.
Set Codeword length N to 15.
Set Message length K to 5.
Gain, in the Simulink Math Operations library
Set Gain to [0; 0; 0; 0; 0; ones(10,1)].
Set Codeword length N to 15.
Set Message length K to 5.
Scope, in the Simulink Sinks library. Get two copies of this block.
Sum, in the Simulink Math Operations library
Set List of signs to |-+
Connect the blocks as in the preceding figure. From the model window's Simulation menu, select Configuration parameters. In the Configuration Parameters dialog box, set Stop time to 500.
The vector length numbers appear on the connecting lines only if you select Signal dimensions from the Port/signal displays submenu of the model's Format menu. 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. Your plot of the error counts might differ somewhat, depending on your Initial seed value in the Random Integer Generator block. (To make the axis range exactly match that of the first scope, right-click the plot area in the scope and select Axes properties.)
Difference Between Original Message and Recovered Message
Number of Errors Before Correction
The second plot is the number of errors that the decoder detected while trying to recover the message. Often the number is five because the Gain block replaces the first five symbols in each codeword with zeros. However, the number of errors is less than five whenever a correct codeword contains one or more zeros in the first five places.
The first plot is the difference between the original message and the recovered message; since the decoder was able to correct all errors that occurred, each of the five data streams in the plot is zero.
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. Read the part that applies to the coding technique you want to use: generic linear block code, cyclic code, Hamming code, BCH code, or Reed-Solomon code.
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. In order 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 [Ik, P] or [P, Ik], where P is some K-by-(N-K) matrix and Ik is the K-by-K identity matrix, G is said to be in standard form. (Some authors, such as Clark and Cain [1], use the first standard form, while others, such as Lin and Costello [2], use the second.) The linear block-coding blocks in this blockset require the Generator matrix mask parameter to be in standard form.
Decoding Table. 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.
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 2N-K rows. Each row gives a correction vector for one received codeword vector.
If you do not want to specify a decoding table explicitly, set that parameter to 0. This causes the block to compute a decoding table using the syndtable function in Communications Toolbox.
For cyclic codes, the codeword length N must have the form 2M-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 xN-1. Van Lint [4] 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 polynomial's coefficients in order of ascending powers of the variable. You can find generator polynomials for cyclic codes using the cyclpoly function in Communications Toolbox.
If you do not want to specify a generator polynomial, set the second mask parameter to the value of K.
For Hamming codes, the codeword length N must have the form 2M-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 2M elements (or, more generally, pM 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 polynomial's coefficients in order of ascending powers of the variable. You can find generator polynomials for Galois fields using the gfprimfd function in Communications Toolbox.
If you do not want to specify a primitive polynomial, set the second mask parameter to the value of K.
For BCH codes, the codeword length N must have the form 2M-1, where M is an integer between 3 and 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 reference page for the bchenc function in Communications Toolbox. No known analytic formula describes the relationship among the codeword length, message length, and error-correction capability for BCH codes.
Error Information. The BCH Decoder block can also return error-related information during the simulation. The optional second output signal indicates the number of errors that the block detected in the input codeword. A negative integer in the second output indicates that the block detected more errors than it could correct using the coding scheme. If you do not want the block to create a second output signal, clear Show number of errors in the block dialog box.
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= 2M-1, where the 2M 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 2M-1. In this case, the encoder appends 2M-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 Blockset 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 blockset is that Reed-Solomon codes process symbols in GF(2M) instead of GF(2). Each such symbol is specified by M bits. The nonbinary nature of the Reed-Solomon code symbols causes the Reed-Solomon blocks to differ from other coding blocks in these ways:
You can use the integer format, via the Integer-Input RS Encoder and Integer-Output RS Decoder blocks.
The binary format expects the vector lengths to be an integer multiple of M*K (not K) for messages and the same integer M*N (not N) for codewords.
Error Information. The 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.
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.
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 I1I2. (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 0I1I2. The modified message sequence is then RS encoded, and the added information zero is subsequently removed, which yields a result of I1I2P1P2P3P4. (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 I1I2P1P3P4.
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 DI1I2. The first symbol is truncated, as in the preceding figure, yielding a final output of I1I2.
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 I1I2P1P3P4 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 I1EP1P3E, 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 P1 and P3, yielding a codeword vector of I1EP1EP3E.
Just prior to decoding, the addition of zeros at the beginning of the information vector accounts for the shortening. The resulting vector is 0I1EP1EP3E, such that a (7,3) codeword is sent to the Berlekamp algorithm.
This codeword is decoded, yielding a three-symbol message of DI1I2 (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 I1I2 vector.
[1] Clark, George C., Jr., and J. Bibb Cain, Error-Correction Coding for Digital Communications, New York, Plenum Press, 1981.
[2] Lin, Shu, and Daniel J. Costello, Jr., Error Control Coding: Fundamentals and Applications, Englewood Cliffs, NJ, Prentice-Hall, 1983.
[3] Peterson, W. Wesley, and E. J. Weldon, Jr., Error-Correcting Codes, 2nd ed., Cambridge, MA, MIT Press, 1972.
[4] van Lint, J. H., Introduction to Coding Theory, New York, Springer-Verlag, 1982.
| Source Coding | Convolutional Coding | |
| © 1984-2008- The MathWorks, Inc. - Site Help - Patents - Trademarks - Privacy Policy - Preventing Piracy - RSS |