Desurvire E. Classical and Quantum Information Theory: An Introduction for the Telecom Scientist

Подождите немного. Документ загружается.

11.3 Cyclic codes 217

detection? It is simpler to show that the code has the capability to detect up to d

min

− 1

errors. Indeed, d

min

represents the minimum number of bit positions by which any two

codewords differ. If the distance d(X, Y ) between a received codeword Y and a message

code X is such that d(X, Y ) < d

min

, or equivalently, d(X, Y ) ≤ d

min

− 1, then Y differs

from X by fewer than d

min

positions and, hence, does not belong to the code. The

code is, thus, able to recognize that there exists a number of d(X, Y )errorsuptoa

maximum of d

min

− 1. As we have seen, the code is, however, able to correct up to

{(d

min

− 1)/2} of these errors. In the case of Hamming codes, we have seen that d

min

3. This gives for these codes an error-detection capability of up to d

min

− 1 = 2errors

and an error-correction capability of up to w = 1 errors, independently of the block-code

size.

11.3 Cyclic codes

Cyclic codes represent a subset of linear block codes that obey two essential properties:

(a) The sum of two codewords is also a block codeword;

(b) Any cyclic permutation of the block codeword is also a block codeword.

Cyclic codes corresponding to (n, k) block codes can be generated by polynomials

g(p)ofdegreen − k. Here, I shall brieﬂy describe the principle of this encoding

method.

Assume a block code Y = (y

...y

n−1

)ofn bits y

, which are now labeled from 0 to

n − 1. From this codeword, we can generate a polynomial

Y (p) = y

+ y

p + y

+···+y

n−1

, (11.15)

where p is a real variable. We multiply Y ( p)by p and perform the following term

rearrangements:

pY(p) = y

p + y

+ y

+···+y

n−1

= y

p + y

+ y

+···+y

n−1

+ 1) − y

n−1

(11.16)



n−1

+ y

p + y

+ y

+···+y

n−2

n−1

+ 1

+ y

n−1



+ 1).

To derive the above result, we have used the property that for binary numbers, subtraction

is the same as addition. Equation (11.16) can then be put in the form:

pY(p)

+ 1

= y

n−1

(p)

+ 1

, (11.17)

where

(p) = y

n−1

+ y

p + y

+ y

+···+y

n−2

n−1

(11.18)

is the reminder of the division of pY ( p)byM = p

+ 1, or

(p) = pY(p)mod[M], (11.19)

218 Error correction

where mod[M] stands for “modulo M” (the same way one writes 6:3 = 0 mod[3], or

8:3 = 2 mod[3]). It is seen from the deﬁnition in Eq. (11.17) that Y

(p) is a codeword

polynomial representing a cyclically shifted version of Y ( p)(Eq.(11.15)). Likewise, the

polynomials Y

(p) = p

Y (p)mod[M] are all cyclically shifted versions of the code

Y (p). It is then possible to use the Y (p) polynomials as a new way of encoding messages,

as I show next.

Deﬁne g( p)asagenerator polynomial of degree n − k, which divides p

+ 1. As an

example for n = 7, we have the irreducible polynomial factorization:

+ 1 = (p + 1)( p

+ p

+ 1)( p

+ p + 1)

≡ (p + 1)g

(p)g

(p),

(11.20)

showing that g

(p) = p

+ p

+ 1, g

(p) = p

+ p + 1, ( p + 1)g

(p) and

(p + 1)g

(p) are possible generator polynomials for k = 4 (ﬁrst two) and k = 3

(last two). Deﬁne next the message polynomial X ( p)ofdegreek − 1:

X(p) = x

+ x

p + x

+···x

n−1

k−1

. (11.21)

We can now construct a cyclic code for the 2

possible messages X ( p) according to the

deﬁnition:

Y (p) = X ( p)g( p), (11.22)

where g( p) is a generator polynomial. Equation (11.21) represents a polynomial version

of the previous matrix deﬁnition in Eq. (11.2), i.e.,Y = X

G. Although we will not make

use of it here, one can deﬁne the parity-check polynomial h( p) from the relation

g(p)h( p) = 1 + p

, (11.23)

or equivalently, g( p)h( p) = 0mod[1+ p

], which is the polynomial version of the

matrix Eq. (11.5), i.e., HG

= GH

= 0.

I illustrate next the polynomial encoding through the example of the (n, k) = (7, 4)

Hamming block code. From Eq. (11.20), we can choose g(p) = p

+ p + 1asthe

generator polynomial (which divides by p

+ 1). The coefﬁcients of the polynomial

Y (p), as calculated from Eq. (11.22) for all possible message polynomials X ( p), are

listed in Table 11.3.

It is seen from Table 11.3 that the obtained code representation is not systematic, i.e.,

the message bits no longer represent a separate word at the beginning or end of the code,

unlike in the linear block codes previously seen (Table 11.1). For instance, as the table

shows, the original four-bit message 0111 is encoded into 01100011.

Next, I show how error detection and correction is performed in cyclic codes. Assume

that Z( p) is the result of transmitting Y ( p) through a noisy channel. We divide the result

by g( p) and put it in the form:

Z(p) = q(p)g( p) +s( p), (11.24)

An irreducible polynomial, like a prime number, can be divided only by itself or by unity.

11.4 Error-correction code types 219

Table 11.3 Message polynomial coefﬁcients and correspond-

ing cyclic codeword polynomial coefﬁcients in the (7, 4) block

code example, as corresponding to the generator polynomial

g(p) = p

+ p + 1 .

Message word Cyclic code

X(p) x

Y ( p) y

0000 0000000

0001 0001011

0010 0010110

0011 0011101

0100 0101100

0101 0100111

0110 0111010

0111 0110001

1000 1011000

1001 1010011

1010 1001110

1011 1000101

1100 1110100

1101 1111011

1110 1100010

1111 1101001

where q( p) and s( p) are the quotient and the remainder of the division, respectively.

If there were no errors, we would have Z( p) = Y ( p) = X(p)g( p), meaning that the

quotient would be the original message, q( p) = X ( p), and the remainder would be

zero, s( p) = 0. As done previously, we call s( p)thesyndrome polynomial. A nonzero

syndrome means that errors are present in the received code. As previously shown

for the vectors E, S, it is possible to map the error polynomial e( p)intos( p), which

makes it possible to associate syndrome and error patterns. Looking at Table 11.3,

we observe that the minimum Hamming distance for this cyclic code is d

min

= 3.

According to Eq. (11.14), the Hamming weight of error patterns that can be corrected is

w ≤{(d

min

− 1)/2}=1, meaning that only single errors can be corrected. As previously

discussed, this is a general property of Hamming codes, which is not affected by the

choice of cyclic coding. The capabilities of error detection and correction of various

cyclic codes are discussed next.

11.4 Error-correction code types

So far, this chapter has provided the basic conceptual tools of ECC principles and

coding or decoding algorithms. Here, I shall complete this introduction by review-

ing different ECC types used in information technologies (data standards) and

telecommunications (packet or frame standards), as well as their error-correction

capabilities.

220 Error correction

Hamming codes

As we have seen in Section 11.2, these are linear block codes of the form (n, k) =

− 1, n − m), with m ≥ 3. The minimum distance of a Hamming code was shown to

be d

min

= 3, giving a correction capability of one-bit error.

Hadamard codes

These are linear block codes of the form (n, k) = (2

, m + 1), whose 2

m+1

codewords

are generated by Hadamard matrices.

It is left as an exercise to verify this statement and

property. The minimum distance is d

min

= n/2 = 2

m−1

, yielding a correction capability

of {(2

m−1

− 1)/2} or 3–7 bit errors for m = 4 − 5.

Cyclic redundancy check (CRC) codes

This is the generic name given to any cyclic code used for error detection. Most data

packet or framing standards include a “CRC” trailer ﬁeld, which ensures error correction

for the packet or frame payload. Binary CRC codes (n, k) can detect error bursts of

length ≤ n − k, as well as various other error-burst patterns, such as combinations of

errors up to a maximum of d

min

− 1. CRC codes can correct all error patterns of odd

Hamming weight (odd numbers of bit errors) when the generator polynomial has an

even number of nonzero coefﬁcients.

Golay code

This can be viewed equivalently as a (23, 12) linear block code, or a (23, 12) cyclic code.

In the last case, the code is generated by either of the two polynomials

g(p) = 1 + p

+ p

By deﬁnition, a Hadamard matrix M

is an nxn binary matrix (n = 2

), in which each row is different

from all the others by exactly n/2 positions. One row must contain only 0 bits, thus all other rows have n/2

zeros and n/2 ones. The smallest Hadamard matrix (out of four possibilities) is:





A property of the Hadamard matrices is that it is possible to construct M

from M

, as follows:





where

is the complementary matrix of M

(meaning that all bits values are switched). Thus, for M

obtain:





≡







0000

0101

0011

0110







The key property is that the rows of M

and

form a complete set of 2n codewords, which correspond to

a linear block code (n, k) of length n = 2

with k = m + 1 and minimum distance d

min

= n/2 = 2

m−1

11.4 Error-correction code types 221

g(p) = 1 + p + p

+ p

which are both dividers of 1 + p

. The corresponding minimum distance is d

min

= 7,

corresponding to a correction capability of three-bit errors.

Maximum-length shift-register codes

These are cyclic codes of the form (2

− 1, m) with m ≥ 3, which are generated by

polynomials of the form g( p) = (1 + p

)/ h( p), where h( p) is a primitive polynomial of

degree m (meaning an irreducible polynomial dividing 1 + p

with q = 2

− 1 being

the smallest possible integer). The minimum distance for this code is d

min

= 2

m−1

indicating the capability of correcting a maximum of w ={2

m−1

− 1/2} simultaneous

errors. For instance, the code (15, 4) has a three-bit-error correction capability. The code

rate (number of message-payload bits divided by the block length) is R = 4/15 = 26%,

which is relatively poor in terms of bandwidth use. The maximum-length code sequences

are labeled as “pseudo-noise,” owing to their auto-correlation properties, which closely

emulate white noise.

Bose–Chaudhuri–Hocquenghem (BCH) codes

These are cyclic codes of the form (2

− 1, k) with m ≥ 3, n − k ≤ mt, where m is an

arbitrary positive integer, and t is the number of errors that the code can correct (not all

m, t values being yet eligible). The BCH codes are generated by irreducible polynomials

dividing 1 + p

2m−1

. The ﬁrst of these polynomials is g( p) = 1 + p + p

, corresponding

to the block (7, 4) with t = 1. The minimum distance for BCH codes is d

min

= 2t + 1

= 3, 5, 7,...corresponding to error-correcting capabilities of t = 1, 2, 3,..., respec-

tively. For instance, the block (31, 11) with t = 5 can be corrected for a number of errors

corresponding to almost half of the 11 message bits, while the code rate is R =11/31 =

35.5%. Table 11.4 lists the possible parameter combinations (m, n, k, t) for BCH codes

up to m = 6 corresponding to block lengths 7 ≤ n ≤ 63, and their generating polyno-

mials, as expressed in octal form.

Extended lists of BCH codes and polynomials for

m ≤ 8 and m ≤ 34 can be found in.

The octal representation of a polynomial is readily understood by the following two examples, showing ﬁrst

the representation of the polynomial coefﬁcients in binary, then in decimal, then, ﬁnally, in octal:

(p) = p

+ p + 1

= 1 × p

+ 0 × p

+ 1 × p + 1 ≡ 1011

binary

≡ 19

decimal

= 2 × 8

+ 3 ×8

= 23

octal

(p) = p

+ p

+ 1 ≡ 101101001

binary

≡ 721

decimal

= 3 × 8

+ 5 ×8

+ 2 ×8

+ 1 ×8

≡ 3521

octal

J. G. Proakis, Digital Communications (New York: McGraw Hill, 2001), pp. 438–9, and other related

references, therein.

222 Error correction

Table 11.4 List of BCH codes with block lengths 7 ≤ n ≤ 63, and their generating polynomials g(p),

expressed in octal.

mn k t g(p) mn k t g(p)

3 7 4 1 13 6 63 57 1 103

4 15 11 1 23 51 2 12471

7 2 721 45 3 1701317

5 3 2467 39 4 166623567

36 5 1033500423

5 31 26 1 45 30 6 157464165547

21 2 3551 24 7 17323260404441

16 3 107657 18 10 1363026512351725

11 5 5423325 16 11 6331141367235453

6 7 313365047 10 13 472622305527250155

7 15 5231045543503271737

Reed–Solomon (RS) codes

These represent a subfamily of BCH codes based on a speciﬁc arrangement, noted

RS(N, K ). The code block is made of N symbols comprising K message symbols

and N − K parity symbols. The message or parity symbols of length m are nonbinary

(e.g., m = 8forbyte symbols). The total block length is, thus, Nm. The RS code

format is RS(N = 2

− 1, K = N − 2t). Its minimum distance is d

min

= N − K + 1,

corresponding to a symbol error-correction capability of t = (N − K )/2. The code rate

is R = (N − 2t)/N = 1 −2t/N . For instance, the RS(255, 231) code having N = 255

symbols (m = 8) and t = 12 (K = 231) corresponds to a code rate of 90% (or a

relatively small bandwidth expansion factor of N /K − 1 =10.4%. Thus, symbol errors

can be corrected up to about 1/20 of the block length with only N − K = 24 symbols,

representing an ECC overhead of nearly 10%. This example illustrates the power of RS

codes and justiﬁes their widespread use in telecommunications.

Concatenated block codes

It is possible to concatenate, or use two different ECCs successively. This is usually done

with a nonbinary ECC (outer code), which is labeled (N , K ) and a binary ECC (inner

code), which is labeled (n, k). The message coding begins with the outer code and ends

with the inner code, yielding a block of the form (nN, kK), meaning that each of the K

nonbinary symbols is encoded into k binary symbols, and similarly for the parity bits.

At the receiving end, the block successively passes through the inner decoder and then

the outer decoder. The corresponding code rate and minimum Hamming distance are

given by R



= kK/nN and d



min

= d

min

, meaning that both parameters are given

by the products of their counterparts for each code. Since the code rates k/n and K /N

are less than unity, the resulting code rate is substantially reduced. However, the error-

correction capability w ={(d

min

− 1)/2} is substantially increased, approximately

as the square of that of the individual codes. Using for instance the concatenation of

11.4 Error-correction code types 223

Figure 11.3 Two examples of rate

convolutional encoders: (a) systematic, with constraint

length m = 2; (b) nonsystematic, with constraint length m = 4.

two RS codes of the previous example, RS(255, 231), the code rate is 81% (bandwidth

expansion factor 22%) while the correction capability is 71 bit errors, representing 31%

of the initial message block length.

Convolutional codes

These are linear (n, k) block codes with rate R = k/n, using a transformation rule,

which is a function of the m last transmitted bits. The number m is called the code’s

constraint length.Them − 1 input bits are memorized into shift registers, which are

all initially set to zero. Two examples of rate

convolutional encoders are provided

in Fig. 11.3. The ﬁrst example corresponds to an encoder with constraint length m =

2. It outputs one bit, which is identical to the input (y

(1)

= x

), and a second bit,

which is the sum (modulo 2) of the last two input bits (y

(2)

= x

+ x

i−1

). Because

the input message is reproduced in the output, this convolutional code is said to be

systematic. The second example in Fig. 11.3 corresponds to a nonsystematic, m = 4

convolutional code. Another possibility is to feedback the output of one or several shift

registers to the encoder input. This is referred to as a recursive convolutional encoder.

The code examples shown in Fig. 11.3 aresaidtobenonrecursive. For relatively small

values of m, decoding is performed through the Viterbi algorithm,

which is based on

a principle of optimal decision for block error correction. It is beyond the scope of this

introduction to enter the complexities of decoding algorithms for convolutional codes.

Sufﬁce it here to state that their error-correction capabilities can be tabulated according

to their code rate k/n.

For 1/n codes with constraint length m, an upper bound for the

See, for instance: http://en.wikipedia.org/wiki/Viterbi_algorithm.

J. G. Proakis, Digital Communications (New York: McGraw Hill, 2001), pp. 492–6.

224 Error correction

Encoder 1

Encoder 2

Input

Outputs

Interleaver

Systematic

Output I

Output II

Figure 11.4 Generic layout of turbo encoder.

minimum Hamming distance d

min

is given by the following formula:

min

≤ min

p≥1



p−1

− 1

(m + p − 1)n

. (11.25)

It is easily checked that with n = 2 and m = 3, for instance, the distance is bounded

according to d

min

≤ 5, corresponding to a maximum of two-bit-error correction. Con-

volutional codes are commonly used in mobile-radio and satellite communications, and

in particular in the wireless-connection standard called Bluetooth.

Turbo codes

These high-performance codes represent a relatively recent (1993) and signiﬁcant

advance in the ﬁeld of ECC. The principle is that the turbo encoder generates three

sub-blocks, as illustrated in Fig. 11.4. As the ﬁgure shows, the ﬁrst sub-block is the k-bit

block of payload data that is output as uncoded and, thus, representing the systematic

output. The second sub-block (output I) contains m/2 parity bits for the payload, com-

puted using a convolutional code. The third sub-block (output II), also computed through

a convolutional code, contains m/2 parity bits for a known or ﬁxed pseudo-random per-

mutation of the input payload bits. Such a permutation is effected through an interleaver,

as seen in the ﬁgure. This pseudo-random interleaving makes the output I and output II

sub-blocks substantially different from each other, at least in a large majority of input

payload cases. The rationale in this approach is to ensure that one of these two sub-blocks

has a high Hamming weight, or more ones than zeros, which (as it can be shown) makes

the codeword identiﬁcation and decoding easier than in the low-weight case. Thus, hav-

ing two parallel encoders with substantially different or virtually uncorrelated outputs,

corresponds to a “divide-and-conquer” ECC strategy. Here, we will not venture into the

advanced principles of turbo decoding, but it is worth providing a high-level description

11.4 Error-correction code types 225

of the corresponding strategy. The main task of the convolutional decoder is to compute

an integer number I for each received bit. This number, called a soft bit, which is output

in the interval [−127, 127], measures the likelihood for the received bit to bea0ora1.

The likelihood is measured as follows: I =−127 means certainly 0, I =−100 means

very probably 0, I = 0 means equally likely to be either 0 or 1, I =+100 means very

likelytobe1,andI =+127 means certainly likely to be 1. In the implementation, two

parallel convolutional decoders are used to generate such likelihood measures for each of

the m/2 bit parity sub-blocks and for the k-bit payload sub-block. Using their likelihood

data, the two decoders can then construct two hypotheses for the k-bit payload pattern.

These bit-pattern hypotheses are then compared. If they do match exactly, the bit pattern

is output as representing the ﬁnal decision. In the opposite case, the decoders exchange

their likelihood measures. Each decoder includes the likelihood measure from the other

decoder, which makes it possible for each of them to generate, once again, a new payload

hypothesis. If the hypothesis comparison is not successful, the process is continued; it

may take typically up to 15 to 18 iterations to converge! For turbo code designers, the

matter and mission is to optimize the convolutional codes for efﬁcient error correction,

with maximal code rates (or minimal redundancy) and coding gains. In wireless-cellular

applications, for instance, the two convolutional encoders are typically recursive, with

a constraint length m = 4 and a code rate 1/3, yielding overheads better than 20%.

To quote some representative ﬁgures, the coding gain of turbo codes at BER = 10

−6

and after 10 iterations may be over 2 dB better than that of concatenated codes, 4.5 dB

better than that of convolutional codes, and represent a 10 dB SNR improvement with

respect to the uncoded BER case.

As two illustrative examples, sufﬁce it to mention

here the signiﬁcant applications of turbo codes in the ﬁelds of aerospace and satellite

communications

and 3G/cellular telephony (UMTS, cdma2000).

This completes our “high-level” overview of the various ECC types and families.

Since ECCs can only correct error patterns with up to w ={(d

min

− 1)/2} bit errors,

it is clear that, in the general case, the bit-error rate (BER) is never identical to zero.

Bit errors are generated when the receiver makes the “wrong decision,” namely out-

puts a 1 when the payload bit under consideration was a 0, and the reverse. Here, I

shall not describe the different types of receiver architectures and decision techniques.

Both are intimately dependent upon the type of signal modulation formats, the method

of encoding bits into actual physical signal waveforms, whether electrical, radio, or

optical. The ECC algorithms pervade all communication and information systems, and

at practically all protocol layers: in point-to-point radio links (ground, aeronautical,

satellite, and deep-space), in optical links (from ﬁber-to-the-home to metropolitan or

core networks and undersea cable systems), in mobile cellular networks (GSM, GPRS,

CDMA, UMTS/3G), in broadband wireless or wireline access (ADSL, 802.11/WiFi),

in metropolitan, regional, and global voice or data transport (Ethernet, ATM, TCP/IP, or

www.aero.org/publications/crosslink/winter2002/04.html.

See, for instance: http://users.tkk.ﬁ/∼pat/coding/essays/turbo.pdf; http://www.csee.wvu.edu/∼mvalenti/

documents/valenti01.pdf.

226 Error correction

Internet), and in global positioning systems (GPS, Galileo), to quote a few representative

examples.

11.5 Corrected bit-error-rate

As we have seen in this chapter, ECCs can only correct error patterns having up to w =

{(d

min

− 1)/2} bit errors. It is clear, then, that in the general case, the bit error rate (BER)

is always nonzero. This is despite the fact that it can be made arbitrarily close to zero

through the appropriate ECC and under certain channel limiting conditions, as will be

described in Chapter 12. Here, I will not detail the optimum receiver decision techniques,

usually referred to as hard-decision and soft-decision decoding, respectively. Sufﬁce it

to state that in the soft-decision decoding approach, the receiver decision is optimized

for each 1/0 symbol type (e.g., use of different matching ﬁlters in multilevel signaling),

which eventually minimizes symbol errors. On the other hand, hard-decision decoding

consists of making a single choice between 1 and 0 values for each of the received

symbols. Here, we shall ﬁrst derive a simple expression for the hard-decision-decoding

BER, which represents a general upper bound, regardless of the type of code used.

The uncorrected BER is deﬁned by the function p(x), which is the probability of mis-

reading 1 or 0 symbols. In the modulation and detection format referred to as intensity-

modulation/direct-detection (IM-DD) or, equivalently, ON–OFF keying (OOK), the

parameter x is the Q-factor.

Simply deﬁned, the Q-factor is a function of the mean

received signal powers, P

and P

, which are associated with the 0 and 1 bit symbols,

respectively, and of the corresponding Gaussian noise powers with standard deviations

(

, σ

(

, respectively. The Q-factor thus takes the simple form:

Q =

P

−P



+ σ

. (11.26)

See, for instance: E. Desurvire, Survival Guides Series in Global Telecommunications, Signaling Principles,

Network Protocols and Wireless Systems (New York: J. Wiley & Sons, 2004), Ch. 1; E. Desurvire, Erbium-

Doped Fiber Ampliﬁers, Device and System Developments (New York: J. Wiley & Sons, 2002), Ch. 3.

One can also deﬁne the received signal-to-noise ratio (SNR) as follows:

SNR = P

where P

≡ ( P

+ P

)/2 is the time-average signal power (assuming pseudo-random bit sequences), and

is the total additive noise power. It can be shown (E. Desurvire, Erbium-Doped Fiber Ampliﬁers, Device

and System Developments (New York: J. Wiley & Sons, 2002), Ch. 3.) that the SNR and the Q-factor are

related through

SNR =

Q(Q +

√

or, equivalently, Q = 2

√

SNR

1 +



1 +4(SNR)

For high SNR, the second formula can be approximated by SNR ≈ Q

/2. In optical communications, only

half of the noise power is taken into account, because noise exists in two electromagnetic-ﬁeld polarizations.

In this case, the above deﬁnition reduces to SNR ≈ Q