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

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

12.2 Nonbinary and asymmetric discrete channels 237

…

(

y x

) = 1/3

Originator

source

Recipient

source

Figure 12.4 Noisy typewriter, 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 X, Y ={A, B, C,...,Z}.

1211

(

y x

) 0.5

(

y x

)

Originator

source

Noisy channel

Recipient

source













0 1

1 0

(

Y X

)

(

y x

) 0.5

(

y x

)

× × =

(

) 0

Figure 12.5 Asymmetric channel with nonoverlapping outputs, 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 X ={x

, x

} and Y ={y

, y

238 Channel entropy

, y

} has only one corresponding input {x

, x

}. While the output symbols are

random, the input symbols are deterministic, which represents a special case of noisy

channel where uncertainty does not increase, as discussed later in this chapter. It is easily

established that the corresponding transition matrix is:

P(Y |X) =













. (12.8)

The four above examples of asymmetric, nonbinary channels will be used again in

Chapter 13 to illustrate the concept of channel capacity.

12.3 Channel entropy and mutual information

With the examples of the previous section, we can now make a practical use of the abstract

deﬁnitions introduced in Chapter 5 concerning conditional entropy (also called equiv-

ocation), H (Y |X), joint entropy, H (X, Y ), and mutual information, H (Y ; X ), between

two sources X, Y . It is useful to recall here the corresponding deﬁnitions and their

relations:

H(Y |X ) =−



p(x

, y

)logp(y

), (12.9)

H(X, Y ) = H (Y, X )

=−



p(x

, y

)logp(x

, y

)

= H (X) + H (Y |X )

= H (Y ) + H (X|Y ),

(12.10)

H(X ; Y ) = H(Y ) − H(Y |X )

= H (X) − H (X |Y )

= H (X) + H (Y ) − H(X, Y ).

(12.11)

We consider ﬁrst the elementary case of the symmetric binary channel, which was

previously analyzed and illustrated in Fig. 12.1. The input probability distribution is,

thus, deﬁned by p(x

) = q and p(x

) = 1 −q, where q is a nonnegative real num-

ber such that 0 ≤ q ≤ 1. According to deﬁnition, the entropy of the input source is

H(X ) =−p(x

)logp(x

) − p(x

)logp(x

) ≡ f (q), where

f (q) =−q log q − (1 −q)log(1− q). (12.12)

The function f (q), which was ﬁrst introduced in Chapter 4, is plotted in Fig. 4.7. It is seen

from the ﬁgure that it has a maximum of f (q) = 1forq = 0.5, which corresponds to

the case of maximal uncertainty in the source X . The output probabilities are calculated

12.3 Channel entropy and mutual information 239

as follows:

p(y

) = p(y

)p(x

) + p(y

)p(x

)

= (1 − ε)q + ε(1 −q)

= q + ε − 2εq

≡ r

p(y

) = 1 −r.

(12.13)

We ﬁnd, thus, the entropy of the output source:

H(Y ) = f (q + ε − 2εq). (12.14)

Using next the transition matrix P(Y |X) deﬁned in Eq. (12.4) and Bayes’s theorem,

p(x, y) = p(y|x)p(x), we ﬁnd the joint probabilities p(y

, x

) = (1 − ε)q, p(y

, x

) =

(1 − q)ε, p(y

, x

) = εq and p(y

, x

) = (1 − ε)(1 −q). Replacing these results into

Eq. (12.9), it is easily found that

H(Y |X ) =−ε log ε − (1 −ε)log(1− ε) ≡ f (ε), (12.15)

and, hence,

H(X, Y ) = H(X) + H (Y |X) (12.16)

= f (q) + f (ε),

H(X ; Y ) = H (Y ) − H (Y |X)

= f (q + ε − 2εq) − f (ε). (12.17)

These results can be commented on as follows.

First, we observe that the entropy of the output source H(Y ) = f (q + ε − 2εq)is

different from that of the input source H(X ) = f (q). Both reach the same maximum of

H = 1forq = 0.5. Furthermore, for any values of the noise parameter ε,

the output

source entropy satisﬁes

H(Y ) = f (q + ε − 2εq) ≥ f (q) = H (X), (12.18)

which is illustrated by the family of curves shown in Fig. 12.6,forε = 0toε = 0.35

(noting that the same curves are obtained with ε ↔ 1 −ε). As seen from the ﬁgure, the

uncertainty introduced by channel noise (ε) increases the output source entropy H (Y ),

which was expected. In the cases q = 0orq = 1, which correspond to a deterministic

source X ( p(x

) = 0 and p(x

) = 1, or p(x

) = 1 and p(x

) = 0), the output source

entropy is nonzero, or H (Y ) = f (ε) = f (1 −ε). The corresponding entropy can, thus,

be seen as representing the exact measure of the channel’s noise. It is inferred from

the family of curves in Fig. 12.6 that in the limit ε → 0.5, the output source entropy

The parameter ε deﬁnes the amount of noise in the binary symmetrical communications channel through

the conditional probabilities p(y

). However, it should be noted that because of the symmetry of the

transition matrix, the same amount of noise is associated with both ε and 1 −ε. Thus, noise increases

for increasing values of ε in the interval [0, 1/2], and decreases for increasing values of ε in the interval

[1/2, 1].

240 Channel entropy

0.2

0.4

0.6

0.8

0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

Probability

Entropy

(X),

(Y)

0.00

0.10

0.15

0.05

0.20

0.25

0.30

0.35=

(

)

(

)

Figure 12.6 Input H (X ) and output H (Y ) source entropies of binary symmetric channel, as

functions of the probability q = p(x

) and channel noise parameter ε.

reaches the uniform limit H(Y ) = 1, regardless of the input probability (q). The case

ε = 0.5 corresponds to a maximum uncertainty in the output symbols, i.e., according

to Eq. (12.13): p(y

) = q + ε − 2εq ≡ 0.5 = p(y

), which is independent of the input

probability distribution. It is correct to call this communication channel useless, because

the output symbols are 100% uncorrelated with the input symbols.

Second, we observe from the result in Eq. (12.15) that the equivocation H (Y |X ) =

f (ε) is independent of the input probability distribution. This was expected, since

equivocation deﬁnes the uncertainty of Y given the knowledge of X . It represents a

measure of the channel’s noise, i.e., H(Y |X ) = f (ε). In the limit ε → 0, we have

H(Y |X ) → 0, which means that the communication channel (CC) is ideal or noiseless.

The transition matrix of the ideal or noiseless channel is deﬁned in Eq. (12.3). In this case,

Eqs. (12.14)–(12.17) show that all entropy measures are equal, i.e., H(X ) = H(Y ) =

H(X, Y ) = H (X; Y ) = f (q).

Third, we consider the mutual information H (X; Y ) of the binary symmetric channel,

which is deﬁned in Eq. (12.17). Figure 12.7 shows plots of H(Y ; X)asafunctionofthe

input probability parameter q and the channel noise parameter ε for ε = 0toε = 0.35

(noting that the same curves are obtained with ε ↔ 1 −ε). The input source entropy

H(X ) is also shown for reference.

We observe from Fig. 12.7 that the mutual information H(X ; Y ) is never greater

than the input source entropy H (X). This is expected, since, by deﬁnition, H(X ; Y ) =

H(X ) − H(X |Y ) ≤ H (X ), Eq. (12.11), with the upper bound a result of the fact that

H(X |Y ) ≥ 0. When the channel is noiseless or ideal (ε = 0), the mutual information

equals the source entropy and, as we have seen earlier, all entropy measures are equal:

12.3 Channel entropy and mutual information 241

0.2

0.4

0.6

0.8

0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

Probability

Mutual information

(X;

)

0.00

0.10

0.15

0.05

0.20

0.25

0.30

(

)

0.35

Figure 12.7 Mutual information H (X; Y ) of binary symmetric channel, as a function of the

probability q = p(x

) and channel noise parameter ε. The input source entropy H (X ) is also

shown.

H(X ) = H(Y ) = H(X, Y ) = H (X; Y ) = f (q). As the channel noise (ε) increases, the

mutual information is seen to decrease with 0 ≤ H(X ; Y ) < H (X ). When the chan-

nel noise reaches the limit ε → 0.5, the mutual information uniformly vanishes or

H(X ; Y ) → 0, regardless of the input probability (q). This is the case of the useless

channel.

Finally, we observe from Fig. 12.7 that the mutual information is always maximum

for q = 0.5, regardless of the channel noise ε. The conclusion is that for noisy binary

symmetric channels, the probability distribution that maximizes mutual information is

the uniform distribution.

The above demonstration, based on the example of the binary symmetric channel,

illustrates that in noisy channels the entropy of the output source H (Y )isnot a correct

measure of the information obtained from the recipient’s side. This is because H(Y )

also measures the uncertainty introduced by the channel noise, which is not information.

Thus, noise enhances the output source uncertainty without contributing any supple-

mental information according to the deﬁnition in Chapter 3. The right measure of the

information available to the recipient is mutual information, i.e., the uncertainty of the

output source H(Y ) minus the equivocation H (Y |X). As we have seen, equivocation

is the absolute measure of channel noise, and it is independent of the input probability

distribution. The second important conclusion we have reached is that mutual informa-

tion depends on the input probability distribution. Hence, given a noisy channel, there

must exist an input probability distribution for which the channel’s mutual information

is maximized, meaning that the information obtained by the recipient is maximized. This

242 Channel entropy

conclusion anticipates Shannon’s deﬁnition of channel capacity, which will be described

in Chapter 13.

12.4 Symbol error rate

In this last section, we consider channels with sources X, Y having equal sizes (i.e.,

numbers of symbol events), and analyze the effect of channel noise in the transmission

of information from originator to recipient.

As previously established, the effect of channel noise is to increase the uncertainty in

the recipient source Y , as translated by the entropy inequality H (Y ) ≥ H (X) with respect

to the input source entropy H (X ). As also observed, this increase of uncertainty does

not correspond to additional information. Rather, it corresponds to an uncertainty in the

effective transmission of information from originator to recipient. In noisy symmetric

channels, the transition matrix P(Y |X) is different from identity, which means that there

is no deterministic (or one-to-one) correspondence between the input symbols x

and

the output symbols y

. Short of this unique correspondence between input and output

symbols, any received message (i.e., sequence of symbols) is likely to be corrupted by

a ﬁnite amount of symbol errors.

Given x

as input, a symbol error is deﬁned as any discrepancy between the recipient

output symbol y

, which would have been expected with certainty in a noiseless channel,

and the symbol y

∗

actually output by the recipient. For messages of sufﬁcient size (or

number of symbols), the mean error count is called the symbol error rate (SER).

Let us now formalize the SER concept. Given the fact that the two sources X, Y have

equal size N , there exists a one-to-one symbol correspondence x

↔ y

between them.

To each input message or input symbol sequence x

,..., thus, corresponds a unique

output message or output symbol sequence y

,...,of matching size, in which each

symbol is the faithful counterpart of the symbol of same rank in the input sequence.

With the noisy channel, any error concerning the received symbol y

corresponds to

the joint event (y

, x

i=j

). The probability associated with this speciﬁc symbol error is

p(y

, x

i=j

The total channel SER is given by the sum of all possible symbol error probabilities

according to:

SER =



j=1

p(y

, x

i=j

)



j=1

p(y

i=j

)p(x

)

= 1 −



i=1

p(y

)p(x

)

= 1 −



i=1

p(y

, x

(12.19)

12.4 Symbol error rate 243

The second line in Eq. (12.19) expresses the fact that the SER is the probability of

the event complementary to that of the “absolutely zero error” event, the latter being

deﬁned as the sum of all possible “no error” events (y

, x

) of associated probability

p(y

, x

According to Eq. (12.19), the SER of the binary symmetric channel is deﬁned as

SER = p(y

)p(x

) + p(y

)p(x

)

= εp(x

) + εp(x

)

= ε



p(x

) + p(x

)



= ε.

(12.20)

The noise parameter ε, which we used in the earlier section to characterize the binary

symmetric CC noise, thus, corresponds to the channel SER. Given any string of

N input symbols x

,...,x

and the corresponding string of N output symbols

,...,y

, the SER gives the probability of any count of errors. For with N suf-

ﬁciently large, the average error count effectively measured is close to the SER. For

instance, SER = 0.001 = 10

−3

corresponds to an average of one error in 1000 trans-

mitted symbols, two errors in 2000 transmitted symbols, etc. This estimation becomes

accurate for sufﬁciently long sequences, such that N  1/SER.

More accurately, the SER should refer to a “mean error ratio” rather than an “error

rate.” The term comes from communication systems where symbols are transmitted at

a certain symbol rate, i.e., the number of symbols transmitted per unit time. Given a

symbol transmission rate of N symbols per unit time, the corresponding channel error

rate (or mean error count per unit time) is, thus, N × SER.

In binary channels, the SER is referred to as bit error rate or BER. For sufﬁciently

long and random bit sequences, the bit probabilities become very nearly equal, i.e.,

p(x

= “0”) ≈ p(x

= “1”) = 1/2. According to Eq. (12.20), we have, in this case,

BER ≈



p(y

) + p(y

)



≡

[

p(0|1) + p(1|0)

]

(12.21)

Most real-life binary channels are asymmetric, meaning that usually, p(0|1) = p(1|0).

Then the smallest BER is achieved when the sum p(0|1) + p(1|0) is minimized.

As an easy illustration of SER (or BER) minimization, consider the case of the “Z

channel,” which was described earlier. To recall for convenience, the Z channel has the

transition matrix

P(Y |X) =



1 ε

01− ε



. (12.22)

According to Eq. (12.19), the corresponding symbol error rate is SER = εp(x

) + 0 ×

p(x

) = εp(x

). The SER, thus, only depends on the probability p(x

). Minimizing

the SER is, therefore, a matter of using an input probability distribution such that

p(x

)  p(x

) < 1. In terms of coding, this means that the message sequences to be

transmitted through the communications channel should contain the smallest possible

244 Channel entropy

number of symbols x

, or a number that should not exceed some critical threshold. For

instance, given the constraint ε = p(y

) = 0.25 and a target error rate of SER = 10

−2

we should impose for the code p(x

) ≤ SER/ε = 10

−2

/0.25 = 0.04. The corresponding

code should not have more than 4% of x

symbols in any input codeword sequence.

Such a code has no reason to be optimal in terms of the efﬁcient use of bits to transmit

information. The point here is simply to illustrate that given a noisy communication

channel, the SER can be made arbitrarily small through an adequate choice of input

source coding. This conclusion anticipates Shannon’s deﬁnition of channel capacity,

which is described in Chapter 13.

Through the above example, we have seen that the channel SER can be minimized

by the adequate choice of source code. The issue of SER minimization should not be

confused with the principle of error-correction codes (ECC), which were described in

Chapter 11. The principle of ECC codes is to reduce the channel SER to an arbitrarily

small or negligibly small level. As we have learnt, error detection and correction are

performed by means of extra redundancy or parity bits, which are included in block

codewords. Such bits represent overhead information, which is meant to detect and cor-

rect errors automatically (up to some maximum), and which is removed once these tasks

are accomplished. Error-correction codes, thus, make it possible to achieve transition

matrices effectively approaching the identity matrix in Eq. (12.3)orEq.(12.4) with ε

being made arbitrarily small.

12.5 Exercises

12.1 (B): Show that any binary symmetric channel with X, Y as input and output

sources has an invariant probability vector P(X) such that P(Y ) = P(X).

12.2 (B): Determine the transition matrix of a channel obtained by cascading two

identical binary symmetric channels, and show that the result is also a binary

symmetric channel.

12.3 (B): A binary channel successfully transmits bit 0 with a probability of 0.6 and

bit 1 with a probability of 0.9. Assuming an input distribution P(X) = (q, 1 −q)

with q = 0.2, determine the output source entropy H(Y ).

12.4 (M): A binary symmetric channel with noise parameter ε is used to transmit code-

words of ﬁve-bit length. Determine the probabilities of transmitting codewords

with:

(a) One error;

(b) Tw o e r r o r s ;

(d) One burst of two successive errors.

Application: provide in each case the numerical result, assuming that ε = 0.1.

13 Channel capacity and coding theorem

This relatively short but mathematically intense chapter brings us to the core of

Shannon’s information theory, with the deﬁnition of channel capacity and the subse-

quent, most famous channel coding theorem (CCT), the second most important theorem

from Shannon (next to the source coding theorem, described in Chapter 8). The formal

proof of the channel coding theorem is a bit tedious, and, therefore, does not lend itself

to much oversimpliﬁcation. I have sought, however, to guide the reader in as many steps

as is necessary to reach the proof without hurdles. After deﬁning channel capacity,we

will consider the notion of typical sequences and typical sets (of such sequences) in

codebooks, which will make it possible to tackle the said CCT. We will ﬁrst proceed

through a formal proof, as inspired from the original Shannon paper (but consistently

with our notation, and with more explanation, where warranted); then with different,

more intuitive or less formal approaches.

13.1 Channel capacity

In Chapter 12, I have shown that in a noisy channel, the mutual information,

H(X ; Y ) = H (Y ) − H(Y |X ), represents the measure of the true information contents

in the output or recipient source Y ,giventheequivocation H (Y |X), which measures the

informationless channel noise. We have also shown that mutual information depends

on the input probability distribution, p(x). Shannon deﬁnes the channel capacity C as

representing the maximum achievable mutual information, as taken over all possible

input probability distributions p(x):

C = max

p(x)

H(X ; Y ). (13.1)

As an illustrative example, consider ﬁrst the case of the binary symmetric channel with

noise parameter ε. As we have seen, the corresponding mutual information is given by

Eq. (12.17), which I reproduce here for convenience:

H(X ; Y ) = f (q + ε − 2εq) − f (ε), (13.2)

where q = p(x

) = 1 − p(x

), and f (q) =−q log q − (1 −q)log(1− q). According

to Shannon’s deﬁnition, the capacity of this channel corresponds to the maximum of

246 Channel capacity and coding theorem

H(X ; Y ) as deﬁned above. It is straightforward to ﬁnd this maximum by differentiating

this deﬁnition with respect to the variable q and ﬁnding the root:

dH (X; Y )

[

f (q + ε − 2εq) − f (ε)

]

= 0,

(13.3)

which, with u = q + ε − 2εq and the deﬁnition of the function f (q) leads to

f (q + ε − 2εq) = (1 −2ε)

d f (u)

= (1 −2ε)log

1 − u

, (13.4)

= 0,

or u = 1/2 and, hence, q = 1/2 = p(x

) = p(x

This ﬁrst result shows that the mutual information of a binary symmetric channel is

maximized with the uniform input distribution. We have previously reached the same

conclusion in Chapter 12, when plotting the mutual information H (X ; Y )asafunctionof

the parameter q,seeFig. 12.7. With q = 1/2 we obtain f (q + ε − 2εq) = f (1/2) = 1

and ﬁnally the capacity of the noisy binary channel:

C = 1 − f (ε)

= 1 +ε log ε + (1 −ε)log(1− ε).

(13.5)

With the binary symmetric channel, the “maximization problem” involved in the deﬁni-

tion of channel capacity, Eq. (13.1), is seen to be relatively trivial. But in the general case,

the maximization problem is less trivial, as I shall illustrate through a basic example.

Consider next the class of binary channels whose transition matrix is deﬁned as:

P(Y |X) =



a 1 −b

1 − ab



, (13.6)

where a, b are real numbers belonging to the interval [0, 1]. Such a transition matrix

corresponds to any binary channel, including the asymmetrical case, where a = b.Ithas

been shown,

albeit without demonstration, that the channel capacity takes the form

C = log(2

+ 2

), (13.7)

where











U =

(1 − a) f (b) − bf(a)

a + b − 1

V =

(1 − b) f (a) − af(b)

a + b − 1

(13.8)

A. A. Bruen and M. A. Forcinito, Cryptography, Information Theory and Error-Correction (New York: John

Wiley & Sons, 2005). Note that in this reference, the transition matrix is the transposed version of the one

used here.