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

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

11.5 Corrected bit-error-rate 227

(dB)

Log(BER)

Figure 11.5 Bit error rate (BER) as a function of the Q-factor expressed as Q

, showing

BER = 10

−9

for Q

=+15.5 dB.

The probability of bit error (BER) is then given by the analytical expression and approx-

imation:

p(Q) =

erfc



√



≈

√

2π

−

, (11.27)

where erfc(u) is the complementary error function, and where the approximation in

the right-hand side is very accurate for Q ≥ 2. It is easily checked that for Q = 6

we have BER = p(6) ≈ 10

−9

, corresponding to one mistaken bit out of one billion

received bits. One may also use the decibel deﬁnition for the Q-factor according to

= 20 log

Q, which gives Q

=+15.5 dB for Q = 6, or BER = 10

−9

. Figure 11.5

shows a plot of BER = p(Q) = f (Q

). Long before the massive development and

ubiquitous implementation of ECC in optical telecommunications systems, the values

of BER = 10

−9

or Q

=+15.5 dB have been considered the de facto standard for

“error-free” transmission.

Having, thus, deﬁned the bit error probability, p, we can now analyze to what extent

a BER can be corrected, or reduced, by ECC, using a simple demonstration.

For

simplicity, we shall assume that the communication channel is memoryless. This means

that there is no patterning effect within the possible bit sequences, or between codewords,

namely that bit errors are uncorrelated. In a single transmission event, if m errors

occur in a block of n bits, the corresponding error probability is, therefore, given by

(1 − p)

n−m

. The number of ways the m errors can be arranged in the block is

= n!/[m!(n − m)!]. The total error probability is then C

(1 − p)

n−m

Consider now the corrected BER. To evaluate the upper bound for the corrected

BER, we must take into account all error possibilities, but include the fact that all error

patterns with a maximum of w ={(d

min

− 1)/2} have been effectively corrected. The

corresponding BER is then given by the summation over all error-pattern possibilities

Such a simpliﬁed demonstration makes no pretence of being accurate or unique.

228 Error correction

from m = w + 1tom = n, representing the minimum and maximum numbers of incor-

rect bits, respectively, i.e.,

BER

corr

≤



m=w+1

(1 − p)

n−m

. (11.28)

It is seen from Eq. (11.28) that the BER upper-bound in the right-hand side can be

expressed as the ﬁnite sum

BER

corr

≤ BER

w+1

+ BER

w+2

+···+BER

(11.29)

with

BER

= C

(1 − p)

n−m

. (11.30)

In such a sum, each term corresponds to events of increasing numbers of bit errors,

which have fast-decreasing likelihoods. It is, therefore, possible to approximate the BER

bound by the ﬁrst few terms in the sum. The accuracy of such approximation wholly

depends on the block length, the value of w and the uncorrected bit-error probability, p.

We shall consider a practical and realistic example, which also illustrates the powerful

impact of ECC in BER correction.

Assume the block code RS(n = 2

− 1 = 127, k = 119), which corresponds to the

minimum Hamming distance d

min

= (n − k)/2 = 4. We are, therefore, interested in

evaluating the BER contributions BER

, BER

, etc., in Eq. (11.29), which correspond

to over four bits of noncorrectable errors. We choose a realistic-case situation where the

bit error probability is p =10

−4

.FromEq.(11.30), we get, for the ﬁrst three uncorrected

BER contributions:







BER

= C

127

(1 − p)

122

≈ 2.5 × 10

−12

BER

= C

127

(1 − p)

121

≈ 4.9 × 10

−15

BER

= C

127

(1 − p)

120

≈ 8.5 × 10

−18

(11.31)

From the above evaluations, it is seen that the series BER

is very rapidly converging,

and that only the ﬁrst contribution BER

is actually signiﬁcant. This means that for

the corrected code, the primary source of errors is the “extra” bit error out of ﬁve

error events, which cannot be corrected by the code. It is seen, however, that the ECC

has reduced the BER from p = 10

−4

to p = 2.5 × 10

−12

, which represents quite a

substantial improvement! Figure 11.6 shows plots of the uncorrected and corrected

BER, using in the latter case the deﬁnition of BER

in Eq. (11.31). which illustrates the

BER improvement due to ECC.

Considering ON–OFF keying, and the above example, the uncorrected and corrected

BER correspond to Q

unc

≈ 3.73 (Q

unc

= 11.4 dB) and Q

corr

≈ 6.91 (Q

corr

= 16.8dB).

One can then deﬁne the coding gain as the decibel ratio γ = 20 log

corr

unc

or the decibel difference γ = Q

corr

− Q

unc

, which, in this example, yields γ =

20 log

[6.91/3.73] = 16.4 − 11.8 = 5.4 dB. This coding gain is indicated in Fig. 11.6

through the horizontal arrow. As a matter of fact, a 5.4 dB coding gain means that an

identical BER can be achieved through ECC when the signal-to-noise ratio or SNR is

decreased by 5.4 dB, as the ﬁgure illustrates. As mentioned in the previous section, the

11.5 Corrected bit-error-rate 229

20191817161514131211109

(dB)

Log(BER)

Coding gain

BER

improvement

Figure 11.6 Uncorrected BER (open circles) and corrected BER (closed circles) as a function of

, showing BER improvement from 10

−4

to 2.5 ×10

−12

, and corresponding coding gain of

5.4 dB.

BER

−2

−4

−6

−8

−10

−12

Uncorrected

RS(255,239)

+ RS(255,239)

RS(255,239)

+ RS(255,223)

Figure 11.7 Measured experimental data for uncorrected BER (open circle) and corrected BERs

using RS(255, 239) Reed–Solomon ECC (dashed line), and two concatenations RS(255, 239) +

RS(255, 239) and RS(255, 239) + RS(255, 223).

coding gain can be increased by the concatenation of two ECC codes, one serving as

a ﬁrst outer code, and the other as a second inner code. This feature is illustrated by

the experimental data

shown in Fig. 11.7, where Reed–Solomon codes RS(255, k)are

used. As the ﬁgure shows, the implementation of a single RS(255, 239) code, which

has a redundancy of 255/239 − 1 = 6.7%, provides a coding gain of about 1.5 dB at

BER = 10

−4

. The corrected BER is, however, less than BER = 10

−12

. When this RS

Experimental data from: O. Ait Sab and J. Fang, Concatenated forward error correction schemes for long-

haul DWDM optical transmission systems. In Proc. European Conference on Optical Communications,

ECOC’99, Vol. II (1999), p. 290.

230 Error correction

code is concatenated twice, i.e., using RS(255, 239) + RS(255, 239) with a redundancy

of (255/239)

− 1 = 13.8%, the coding gain is 5.4 dB at BER = 10

−5

. Alternatively,

one can increase the number of parity bits in the inner code, i.e., using RS(255, 223),

which corresponds to the concatenated code RS(255, 239) + RS(255, 223), which has

a redundancy of 255

/(239 × 223) − 1 = 22.0%. The resulting coding gain is seen to

improve with respect to the previous ECC concatenation, corresponding to 5.8 dB at

BER = 10

−5

. We also note from the ﬁgure that the BER is reduced by more than two

orders of magnitude. Such data illustrate the powerful effect of ECC on error control.

As I have mentioned earlier in this chapter, the BER is always nonzero, meaning that

there is no such thing as an absolute error correction or BER = 0.0 × 10

to inﬁnite

accuracy. Two key questions are: (a) how much a corrected BER can be made close to

zero, and (b) whether there is a SNR (or Q

) limit under which ECCs are of limited

effect in any BER correction? Such questions are answered in Chapter 13, through one

of the most famous Shannon theorems.

11.6 Exercises

11.1 (B): Tabulate the block codewords of the Hamming code (n, k) = (7, 4) deﬁned

by the following generator matrix:

G =







1000

0100

0010

0001

101

111

010

110







11.2 (B): Assuming the Hamming code (n, k) = (7, 4) with the parity-check matrix

H =





1011

1101

1110

100

010

001





determine the single errors and corrected codewords from the three received

blocks that are deﬁned as follows:

= 1010111,

= 0100001,

= 0011110.

11.3 (M): With the Hamming code (n, k) = (7, 4) described in the text, whose block

codewords are listed in Table 11.1 and syndrome vectors are listed in Table 11.2,

assume two bit errors in the received blocks. To how many possible error patterns

do each of the syndrome vectors correspond?

11.4 (M): Calculate the probability that the Hamming code (n, k) = (7, 4) described

in the text (with block codewords listed in Table 11.1) fails to detect any multiple

11.6 Exercises 231

bit errors, while assuming single-bit-error probabilities of p = 10

−2

,10

−3

,10

−4

and 10

−5

11.5 (T): Deﬁne a Hadamard code generated from a 4 × 4 matrix, then calculate the

corresponding generator and parity-check matrices.

11.6 (M): Construct a cyclic code from the generator polynomial

g(p) = p

+ p

+ 1

and tabulate the corresponding codewords.

11.7 (M): Construct the systematic nonrecursive convolutional code (n, k) = (3, 1) of

constraint length m = 3 corresponding to the encoder

i−1

i−2

(1)

(2)

+ X

i−2

(3)

+ X

i−1

+ X

i−2

Draw the corresponding coding tree for up to four input bits a, b, c, d.

12 Channel entropy

This relatively short chapter on channel entropy describes the entropy properties of

communication channels, of which I have given a generic description in Chapter 11

concerning error-correction coding. It will also serve to pave the way towards probably

the most important of all Shannon’s theorems, which concerns channel coding,as

described in the more extensive Chapter 13. Here, we shall consider the different basic

communication channels, starting with the binary symmetric channel, and continuing

with nonbinary, asymmetric channel types. In each case, we analyze the channel’s entropy

characteristics and mutual information, given a discrete source transmitting symbols and

information thereof, through the channel. This will lead us to deﬁne the symbol error

rate (SER), which corresponds to the probability that symbols will be wrongly received

or mistaken upon reception and decoding.

12.1 Binary symmetric channel

The concept of the communication channel was introduced in Chapter 11. To recall

brieﬂy, a communication channel is a transmission means for encoded information.

Its constituents are an originator source (generating message symbols), an encoder, a

transmitter, a physical transmission pipe, a receiver, a decoder, and a recipient source

(restituting message symbols). The two sources (originator and recipient) may be discrete

or continuous. The encoding and decoding scheme may include not only symbol-to-

codeword conversion and the reverse, but also data compression and error correction,

which we will not be concerned with in this chapter. Here, we shall consider binary

channels. These include two binary sources X ={x

, x

} as the originator and Y =

, y

} as the recipient, with associated probability distributions p(x

) and p(y

), i =

1, 2. The events are discrete (as opposed to continuous); hence binary channels are one

elementary variant of discrete channels.

A binary channel can be represented schematically through the diagram shown in

Fig. 12.1. Each of the four paths corresponds to the event that, given a symbol x

from

originator source X, a symbol y

is output from the recipient source Y . The conditional

probability of this event is p(y

12.1 Binary symmetric channel 233

−=1)(

xyp

=)(

xyp

=)(

xyp

−= 1)(

xyp

Originator

source

Noisy channel

Recipient

source













−

εε

)(

XYP

Figure 12.1 Binary symmetric channel showing the originator source X ={x

, x

}, the recipient

source Y ={y

, y

}, the conditional probabilities p(y

), and the corresponding transition

matrix P(Y |X).

In the ideal case of a noiseless channel, the two sources are 100% correlated,

i.e.,

p(y

) = 1fori = j,

(12.1)

p(y

) = 0fori = j,

or p(y

) = δ

, with δ

being the Kronecker symbol. In this case, the channel is ideal

indeed, since the transmission is 100% deterministic, which causes no corruption of

information.

The set of conditional probabilities p(y

) associated with the channel deﬁnes a

j × i transition matrix. This matrix, noted P(Y |X), can be written as

P(Y |X) =



p(y

) p(y

)

p(y

) p(y

)



. (12.2)

Since there is no reason to have a one-to-one correspondence between the symbols or indices, we can also

have p(y

) = 1fori = j and p(y

) = 0fori = j . Thus, a perfect binary symmetric channel can

equivalently have either of the transition matrixes (see deﬁnition in text):

(

Y |X

)





(

Y |X

)





Since in the binary system, bit parity (which of the 1 or 0 received bits represents the actual 0 in a given

code) is a matter of convention, the noiseless channel can be seen as having an identity transition matrix.

According to the transition-matrix representation, one can also deﬁne for any source Z = X, Y the prob-

ability vector P

(

)

[

(

)

, p

(

)

]

to obtain the matrix-vector relation P

(

)

= P

(

Y |X

)

(

)

, which

stems from the property of conditional probabilities: p(y

) =



p(y

(

)

234 Channel entropy

To recall from Chapter 1, the properties of the transition-matrix elements are twofold:

(a) p(y

)p(x

) + p(y

)p(x

) = p(y

);

(b) p(y

) + p(y

) = 1 (column elements add to unity).

The channel is said to be symmetric if its transition matrix P(Y |X) is symmetric, i.e.,

[P(Y |X )]

= [P(Y |X )]

, or the matrix elements are invariant by permutation of row

and column indices, i.e.,

P(Y |X) ≡ P(Y |X).

In the case of the ideal or noiseless channel, we have, according to Eqs. (12.1) and

(12.2):

P(Y |X) =





, (12.3)

which is the identity matrix. In the general, or nonideal, case, where the channel is

corrupted by noise, we have p(y

) = 1 − ε and, hence, p(y

j=i

) = ε, where ε is a

positive real number satisfying 0 ≤ ε ≤ 1. The smaller ε, the closer the channel is to

ideal or noiseless. The degree of noise “corruption” is, thus, deﬁned by the parameter ε,

which, as we shall see later in this chapter, deﬁnes the symbol error probability.

According to the deﬁnition in Eq. (4.2), in the most general case the transition matrix

of the binary symmetric channel takes the form:

P(Y |X) =



1 − εε

ε 1 − ε



. (12.4)

A limiting case is given by the parameter value ε = 0.5. In this case, the elements

of the transition matrix in Eq. (12.4) are all equal to p(y

) = 0.5. Thus, given the

knowledge of the originator symbol x

(namely, x

or x

), there is an equal probability

that the recipient will output any of the symbols y

(namely, y

or y

). It does not

matter which originator symbol is fed into the channel, the recipient symbol output

being indifferent, as in a perfect coin-ﬂipping guess. In this case, the channel is said to

be useless.

12.2 Nonbinary and asymmetric discrete channels

In this section, I provide a few illustrative examples of discrete communication channels,

which, contrary to those described in the previous section, are asymmetric, and in some

cases, nonbinary. These are referred to as the Z channel,thebinary erasure channel,the

noisy typewriter, and the asymmetric channel with nonoverlapping outputs.

Example 12.1: Z channel

This is illustrated in Fig. 12.2. The Z channel is a binary channel in which one of the

two originator symbols (say, x

) is unaffected by noise and ideally converted into a

unique recipient symbol (say, y

), which implies p(y

) = 1 and p(y

) = 0. But

the channel noise affects the other symbols, giving p(y

) = ε and p(y

) = 1 − ε.

12.2 Nonbinary and asymmetric discrete channels 235

1)(

xyp

0)(

xyp

(

xyp

−= 1)(

xyp

Originator

source

Noisy channel

Recipient

source













−

)(

XYP

Figure 12.2 Z channel showing the originator source X ={x

, x

}, the recipient source

Y ={y

, y

}, the conditional probabilities p(y

), and the corresponding transition matrix

P(Y |X).

The corresponding transition matrix is, therefore:

(

Y |X

)



1 ε

01−ε



. (12.5)

Note that stating that symbol x

is ideally transmitted through the channel and received

as symbol y

, does not mean that receiving symbol y

entails certainty of symbol x

being output by the originator.

Example 12.2: Binary erasure channel

This is illustrated in Fig. 12.3. In the erasure channel, there exists a ﬁnite probability

that the recipient source Y outputs none of the symbols from the originator source

X. This is equivalent to stating that Y includes a supplemental symbol y

= “void,”

which we shall call ∅. We, thus, deﬁne the probability of Y having y

=∅for output as

p(∅|x

) = p(∅|x

) = ε. It is easily established that the transition matrix corresponding

to input P(X) = [ p(x

), p(x

)] and output P(Y ) = [ p(y

), p(∅), p(y

)] is deﬁned as

follows:

Y ={y

, y

=∅},

P(Y |X) =





1 − ε 0

εε

01− ε





. (12.6)

236 Channel entropy

= ∅

−=1

(

y x

)

=∅=∅

)

(

)

(

y x

)

(

y x

)

−= 1

)

(

Originator

source

Noisy channel

Recipient

source













−

εε

(

Y X

)

Figure 12.3 Binary erasure channel, showing the originator source X ={x

, x

}, the recipient

source Y ={y

, y

}, the conditional probabilities p(y

), and the corresponding transition

matrix P(Y |X), with the recipient source.

Example 12.3: Noisy typewriter

This corresponds to a “typewriter” version of the binary symmetric channel, called the

noisy typewriter, which is illustrated in Fig. 12.4. As seen from the ﬁgure, the source

symbols are the characters {A, B, C,...,Z}, arranged in a linear keyboard sequence.

When a given symbol character is input to the keyboard, there are equal chances of

outputting the same character or one of its two keyboard neighbors. For instance, letter B

as the input yields either A, B, or C as the output, with p(A |B) = p(B |B) = p(C |B) =

1/3, and so on for the 26 letters (input A yielding Z, A, or B), as illustrated in the ﬁgure.

The corresponding transition matrix (reduced here for clarity to six input/output symbol

characters, is the following:

P(Y |X) =







110001

111000

011100

001110

000111

100011







. (12.7)

Example 12.4: Asymmetric channel with nonoverlapping outputs

This corresponds to an asymmetric channel with nonoverlapping outputs, which maps

source X ={x

, x

} to source Y ={y

, y

} according to the transition proba-

bilities deﬁned in Fig. 12.5. The property of this channel is that each of the outputs