Books in black and white
 Books Biology Business Chemistry Computers Culture Economics Fiction Games Guide History Management Mathematical Medicine Mental Fitnes Physics Psychology Scince Sport Technics

# The art of error correcting coding - Moreloz R.H.

Moreloz R.H. The art of error correcting coding - Wiley publishing , 2002. - 232 p.
ISBN 0471-49581-6 Previous << 1 .. 43 44 45 46 47 48 < 49 > 50 51 52 53 54 55 .. 86 >> Next 2. The cyclic mapping mc(i,j) that relates the element a4J in the rectangular array of Figure 54 with a coefficient vmc^j) of a code polynomial v(x) — v0 + v% + • • • +
vnin2-i*"1"2-1 ? Cp, is such that
for mc(i,j) = 0,1, • • • ,nin2 - 1.
When these two conditions are satisfied, the generator polynomial of the cyclic code Cp is given by
mc(i,j) = [U - i) ? bri'i + *] mod n±n2
(6.20)
g(x) = GCD (<h(xbn2)g2(xani),xnir>2 + l) .
(6.21)
114
THE ART OF ERROR CORRECTING CODING
V0,0 V0,l •" V0,nrl
vl,0 vl,l ••• Vl,nrl
Vn2-1,0 Vu •“ Vn2-l,n j-1
Figure 60 Codeword of an block interleaved code of degree I = ri2-
Example 83 An example of the cyclic mapping for ů = 5 and n2 = 3 is shown in Figure 59. In this case, (-1)5 + (2)3 = 1, so that a = -1 and 6 = 2. Consequently, the mapping is given by
mc(i,j) — (6j — 5ă) mod 15.
As a check, if ł = 1 and j = 2, then mc(l, 2) = (12 — 5) mod 15 = 7; if ł = 2 and j = 1, then mc(2,1) = (6 — 10) mod 15 = —4 mod 15 = 11.
The mapping mc(i. j) indicates the order in which the digits of the array are transmitted [B W]. This is not the same as the column-by-column order of the block interleaver for a conventional product code. The mapping described by (6.20) is referred to as a cyclic interleaver. Other classes of interleavers are discussed in Section 6.2.4.
With the appearance of turbo codes [BGT] in 1993, there has been intense research activity in novel interleaver structures that perform a pseudo-random arrangement of the codewords of C\, prior to encoding with C-2. In the next section, interleaved codes are presented. Chapter 8 discusses classes of interleaver structures that are useful in iterative decoding techniques of product codes.
Block interleaved codes
A special case of product code is obtained when the second encoder is the trivial (ů, n2 ? 1) code. In this case, codewords of C\ are arranged as rows of an n2-by-ni rectangular array and transmitted column-wise, just as in a conventional product code. The value / = n2 is known as the interleaving degree [LC] or interleaving depth.
The resulting block interleaved code, henceforth denoted as c[n2\ can be decoded using the same decoding algorithm of C\, after reassembling a received word, column-by-column and decoding it row-by-row. Figure 60 shows the schematic of a codeword of an interleaved code, where (Vito vip ??? Vi,no) Ş C\, forO < ł < n2.
If the error correcting capability of C\_ is t.\ = [(di — 1)/2J, then C\"2> can correct any single error burst of length up to b = L n2. This is illustrated in Figure 61. Recall that the transmission order is column by column. If a burst occurs, but it does not affect more than hi positions per row, then it can be corrected by C\. The maximum length of such a burst of errors is n2 times b\. Moreover, if code C% can already correct (or detect) any single burst of length up to bi, then C["2) can correct (or detect) any single burst of length up to bi ri2?
If C\ is a cyclic code, then it follows from (6.21) that C[n'2) is a cyclic code with generator polynomial äł(őĎ2) [PW, LC]. This applies to shortened cyclic codes as well, and the following result holds ([PW], p. 358):
MODIFYING AND COMBINING CODES 115
Figure 61 A correctable error burst in a block interleaved codeword.
Interleaving a shortened cyclic (n. k) code to degree I produces a shortened (nl. ki) code whose burst error correcting capability is I times that of the original code.
Finally, note that the error correcting capability of a product code, tp = \_{did2 - 1)/2J, can only be achieved if a carefully designed decoding method is applied.
Most of the decoding methods for product codes use a two-stage decoding approach. In the first stage, an errors-only algebraic decoder for the row code C\ is used. Then reliability weights are assigned to the decoded symbols, based on the number of errors corrected. The more errors are corrected, the less reliable the corresponding estimated codeword e C\ is.
In the second stage, an errors-and-erasures algebraic decoder for the column code C2 is used, with an increasing number of erasures declared in the least reliable positions (those positions for which the reliability weights are the smallest), until a sufficient condition on the number of corrected errors is satisfied. This is the approach originally proposed in [RR, Wei]. The second decoding stage is usually implemented with the GMD algorithm, which is discussed in Section 7.6. More on decoding of product codes can be found in Chapter 8.
6.2.4 Concatenated codes
In 1966, Forney [Fori] introduced a clever method of combining two codes, called concatenation. The scheme is illustrated in Figure 62. Concatenated codes4 that are based on outer Reed-Solomon codes and inner convolutional codes have been to date5 perhaps the most popular choice of ECC schemes for digital communications. In general, the outer code, denoted Ci, is a nonbinary linear block (N.K.D) code over GF(2k). The codewords of Ci are stored in an interleaver memory. The output bytes read from the interleaver are then passed through an encoder for an inner code, C2. The inner code C2 can be either a block code or a convolutional code. When block codes are considered, and C2 is a binary linear block (n, k. d) code, the encoder structure is shown in Figure 62. Let C = Ci * C2 denote the concatenated code with Ci as the outer code and C2 as the inner code. Then C is a binary linear block (Nn.Kk, Dd) code. Previous << 1 .. 43 44 45 46 47 48 < 49 > 50 51 52 53 54 55 .. 86 >> Next 