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

ISBN 0471-49581-6

**Download**(direct link)

**:**

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

**51**> 52 53 54 55 56 57 .. 86 >> Next