Books
in black and white
Main menu
Home About us Share a book
Books
Biology Business Chemistry Computers Culture Economics Fiction Games Guide History Management Mathematical Medicine Mental Fitnes Physics Psychology Scince Sport Technics
Ads

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
Download (direct link): artoferrorcorrecting2002.pdf
Previous << 1 .. 45 46 47 48 49 50 < 51 > 52 53 54 55 56 57 .. 86 >> Next

<Mo2 > ? ? > S^doM -, (6.24)
then codewords in correspondence with symbols over GF(q) will have an error correcting capability, [(Sidoi 1)/2j, that decreases with the level i, for 1 < < M. As a result, the messages encoded in the top (low values of i) partition levels will have enhanced error correcting capabilities, compared to those associated with the lowest partition levels. Constructions of this type are reported in [DYS, ].
A construction
Let a linear block (nj.ki.di) code C\ over GF(q) be partitioned into a chain of M (n{, ki-di) subcodes <7*, 2.3, ? ?, M + 1, such that
<7i D <72 D D CM+i,
where, for convenience, Cm+i = {0}, and +1 = oc.
Let = [Ci/Ci+i] denote a linear block (,, Si) subcode of C), which is a set of coset representatives of C*+i in Ci, of dimension ki kl+i and minimum Hamming distance Si > di. Then Ci has the following coset decomposition [For6]
ѳ = + C/2 + + C/m . (6.25)
Let denote a linear block (no-,koi-,doi) code over GF(qkli), where = dim(Cj/Cj+i) ki kl+1, = 1.2. ? . M. Then the direct sum of concatenated codes
C = Coi * C/i + C02 * C/2 + + * ѳ ?
is an (noni.k.d) linear block code of dimension and minimum Hamming distance, respectively [BZ],
M
k = -, and d > min {Sidoi}- (6.26)
*,a l<i<M
i=1 ----
MODIFYING AND COMBINING CODES
119
[i
Figure 65 Encoder structure of a generalized concatenated code with M partition levels.
Note that equality holds in (6.26) when Cn, 1 < i < M, contains the all-zero codeword.
As for the choice of component codes. Note that, since in general the dimensions of the coset representatives are distinct, the outer codes can be selected as RS codes or shortened RS codes.
Binary RM codes are good candidates as inner codes, because they have the following subcode property,
RM(r,m) C RM(r + l,m),
for 0 < r < m, and m > 2.
Example 85 Consider the r-th order RM codes of length 8, RM(r, 3). Then RM(3,3) D RM(2,3) D RM(1,3) D RM(0,3) D {0}, and it follows from (6.25) that
RM(3,3) = [RM(3,3)/RM(2,3)]+[RM(2,3) /RM(1,3)]+[RM(l, 3)/RM(0,3)]+RM(0,3).
This decomposition can be also appreciated from the generator matrix of RM(3,3), expressed as
(Gi \ ( 0 0 0 0 0 0
0 0 0 0 0 0 1 1
(*2 0 0 0 0 0 1 0 1
0 0 0 1 0 0 0 1
0 0 0 0 1 1 1 1
Gz 0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
Vg4 ) \1 1 1 1 1 1 1 l)
where Gi has been defined as the generator matrix of the set of coset representatives of RM(3 - i, 3) in RM(3 - i + 1,3), or [RM(3 - i + 1, m)/RM(3 - i, m)], for i = 1,2,3, and where G.% is the generator matrix of RM(0,3).
120
THE ART OF ERROR CORRECTING CODING
According to this partition of RM(3,3), a GC code can be designed with up to four levels. Note that the outer codes should be over GF(2), for the first and fourth partition levels, and over GF(23) for the second and third partition levels.
Also, some of the subcodes of RM(3,3) themselves can be used as inner codes to obtain a GC code with a reduced number of levels. If RM(2,3) is used as the inner code of a GC code, then the number of partition levels is three, as the generator matrix of RM(2,3) is obtained from that of RM(3,3) by removing Gy (the top row).
Let RM(2,3) be selected as the inner code, and an RS (8,1,8) code Coi over GF(23), an RS (8,5,4) code Coi over GF(23), and a binary linear SPC (8, 7,2) code C03 be selected as outer codes. This gives a binary linear GC (64,25,16) code which has one more information bit than the binary extended BCH (64,24,16) code.
It is now shown how Reed-Muller codes can be expressed as GC codes. Recall from Section 6.2.2, Equation (6.16) on page 108, that the (r + l)-th order RM code of length 2m+1 can be expressed as RM(r + l,m + 1) = |RM(r + l,m)|RM(r + 1, m) + RM(r, m)|. Let G(r, m) denote the generator matrix of RM(r, m). Then
G(r+ l,m + l) = + G(r + l,m)
V 0 G(r, m)
= G(r + l,m) ^ +G(r,m) ^ ^ . (6.27)
Figure 66 An encoder for the binary RM(r + 1, m + 1) code when viewed as a two-level
GC code.
This expression holds for each r-th order RM code, with r > 1 and m > 1, so that a recursion is obtained. From (6.27) it follows that RM(r + 1, m + 1) is a GC code with inner codes the (2,2,1) code and its partition into cosets of the repetition (2,1,2) code, and outer codes RM(r, m) and RM(r + 1, m), respectively. An encoder for RM(r + 1, m + 1) is shown in Figure 66. This recursive structure of RM codes is advantageous when designing soft-decision decoding algorithms for RM codes7, which can be based on simple repetition and parity-check codes. This is precisely what was done in [SB],
7 Soft-decision decoding is presented in Chapter 7.
The Art of Error Correcting Coding Robert H. Morelos-Zaragoza Copyright 2002 John Wiley & Sons Ltd ISBNs: 0-471-49581-6 (Hardback); 0-470-84782-4 (Electronic)
7
Soft-decision decoding
In this chapter, decoding with soft information from the channel is considered. For simplicity of exposition, binary transmission over an AWGN channel is assumed. In Chapter 9, the general case of multilevel transmission is discussed. To provide a motivation for the use of soft decision decoding, it can be argued that the noise environment in data retrieval or signal reception is continuous in nature, not discrete. This means that the received symbols are (quantized) real numbers (voltages, currents, etc.), and not binary or GF(2m) symbols.
Previous << 1 .. 45 46 47 48 49 50 < 51 > 52 53 54 55 56 57 .. 86 >> Next