Introduction
Forward Error Correction
(FEC) codes can detect and correct a limited number of errors without
retransmitting the data stream. There are two basic types of FEC codes: Block
codes and Convolution codes.
The significant example of
Block code is BCH code. As other block code, BCH encodes k data bits into n
code bits by adding n-k parity checking bits for the purpose of detecting and
checking the errors. Given the
length of the codes is for any integer
m¡Ý3, we will have t (where t<
), is the bound of the error correction. That is, BCH can
correct any combination of errors (burst or separate) fewer than t in the
n-bit-codes. The number of parity checking bits is n-k¡Ümt.
An important concept for BCH
is Galois Fields (GF), which is a finite set of elements on which two binary
addition and multiplication can be defined. For any prime number p there is GF(p) and GF(is called extended field of GF(p). We often use GF(
in BCH code. A GF can be constructed over a primitive
polynomial such as
(The construction and arithmetic of GF are in ¡°Error Control
Coding¡±, by Shu Lin). Usually, GF table records all
the variables, including expressions for the elements, minimal polynomial, and
generator polynomial. By referring to the table, we can locate a proper
generator polynomial for encoder. For example, when (n, k, t)=(15,
7, 2), a possible generator is
. If we have a data stream
, the codeword would be
and have the
style of
.
The decoder of BCH is
complicated because it has to locate and correct the errors. Suppose we have a
received codeword, then
, where, v(x) is correct codeword and e(x) is the error.
First, we must compute a syndrome vector s=
, which can be achieved by calculating
, where, H is parity-check matrix and can be defined as:
.
Here,is the element of the GF field and can be located in the GF
table.
With syndrome, error-location
polynomial can be determined.
Berkekamp¡¯s iterative algorithm is one of solutions
to calculate the error-location polynomial. By finding roots of
, the location numbers for the errors will be achieved.
Usage
The program is developed with
Java applet. Basically, the implementation involves three steps: Encoder, Error
adding, Decoder.
¡¤
Encoder
m and t are available for adjusting. As mentioned
above, the codeword length will be. t is the bound of error
correction. With m and t being settled, the length of data bits is k=n-mt. Although
the program itself has no boundary for m, considering the display limitation, m
will be set between 3 and 7. The range checking for m and t are available, if m
and t are set to unreasonable values, a red color will be filled input area and
program will keep wait for proper inputs.
. User will be able to choose either to manually type
data stream in binary (user generate) or allow program to randomly generate
data stream (randomly generate). If ¡°user generate¡± is chosen, user has to type
the data stream, whose length is exact K=n-mt.
Otherwise, when ¡°user gen¡± being click, a range
checking function will fill the input area with red, indicating the data length
is incorrect. If ¡°randomly generate¡± is selected, upon m and t being settled,
the program will randomly generate a data stream and encoder it into codeword.
With
the ¡°random gen¡± or ¡°user gen¡±
button being clicked, the original signal, BCH codeword and its generator
sequence (, It comes from GF and constructs the codeword) will be
displayed. Meanwhile, the data stream and BCH codeword will be show the plot
graph underneath.
¡¤
Error Adding
In
order to evaluate the capability of BCH codes, user is allowed to decide number
of errors that will happen to codeword. Besides, two error-assignment styles
will be available to be selected:
Random: The faulty bits will be randomly selected from the
codeword;
Burst: The
faulty bits will be consecutive, and user is allowed to set start position for
burst error. In random styles, the start position will be set to ¡°-1¡±, meaning
not available for adjustment. If
the start position that user set exceeds the length of the codeword, the
program will coerce the start position back to signal range. It is well know
that burst errors are hard for normal other error correction codes to deal
with. But user will find burst or separate errors make no difference for BCH
code, which is an advantage of BCH code. When ¡°adding error¡± is clicked, the
receiving code with error bits will be displayed. Meanwhile, corresponding
receiving code will be shown in the plot graph. On the receiving curve, a red
¡°E¡± will appear on the error bit.
¡¤
Decoder
The decoder will be triggered by user clicking the
¡°decode¡±. The decoder will give the results of error corrections, including:
¡¤
decoded signal;
¡¤
sigma(x): , it is the error-location polynomial and calculated by Berkekamp¡¯s iterative algorithm, which is a quite complex
procedure;
¡¤
root: the roots
for and they are the
position number of errors;
¡¤
S(x): Syndrome,
which is essential for the decoder (details are discussed above);
¡¤
The number of
corrected errors;
¡¤
The text message,
which indicates whether all the error bits have been corrected.
The
decoded signal will also be shown in the plot graph. If the number of errors
exceeds t, the decoder will fail to correct all the errors. In that case, some
of ¡°E¡±s will be left to indicate that some errors are
still there.
Reference:
[1] Shu
Lin, ¡°Error Control Coding: Fundamentals and Applications¡±,
[2] William
Stallings, ¡°Wireless Communications and Networks¡±, Prentice Hall, 2002.