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

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

3 Measuring information

In effect, the concept of information is obvious to anyone in life. Yet the word captures so

much that we may doubt that any real deﬁnition satisfactory to a large majority of either

educated or lay people may ever exist. Etymology may then help to give the word some

skeleton. Information comes from the Latin informatio and the related verb informare

meaning: to conceive, to explain, to sketch, to make something understood or known,

to get someone knowledgeable about something. Thus, informatio is the action and art

of shaping or packaging this piece of knowledge into some sensible form, hopefully

complete, intelligible, and unambiguous to the recipient.

With this background in mind, we can conceive of information as taking different

forms: a sensory input, an identiﬁcation pattern, a game or process rule, a set of facts or

instructions meant to guide choices or actions, a record for future reference, a message

for immediate feedback. So information is diversiﬁed and conceptually intractable. Let

us clarify here from the inception and quite frankly: a theory of information is unable

to tell what information actually is or may represent in terms of objective value to

any of its recipients! As we shall learn through this series of chapters, however, it

is possible to measure information scientiﬁcally. The information measure does not

concern value or usefulness of information, which remains the ultimate recipient’s

paradigm. Rather, information theory provides mathematical methods for informatio,

in the ancestral Latin sense, but, since the twentieth century, using powerful computer

technologies, which make it possible to handle phenomenal amounts of raw information

messages.

This chapter will help us to conceive the “measure of information” in the Shannon

or “classical” deﬁnition, which represents the central axiom in information theory. We

will do this in two steps. First, we will analyze in what ways information might “make

sense,” but without any philosophical pretence. It is important in our view to go through

this preliminary reﬂection before approaching information theory. No doubt, it has

the potential to open up many interesting discussions and stimulate a brainstorming

session, which could eventually get everyone lost in the class. However, the beneﬁt of

the reﬂection is to acquire the right focus, and safely engage us on the information-theory

journey, which is a more practical and useful goal than that of philosophically mastering

the information concept.

38 Measuring information

3.1 Making sense of information

In ordinary life and circumstances, information represents any piece of knowledge

concerning facts, data, descriptions, characterizations, rules, or means to perform tasks,

which can be transmitted, exchanged,oracquired in many ways. Such information can be

transmitted through sounds, images, signals, notices, messages, announcements, voice,

mails, memos, documents, books, encyclopedias, tutorials, chapters, training, and news

media. There exist a seemingly boundless number of possible channels for information.

According to the above description, information has no intrinsic meaning in itself.

The notion of meaningfulness is tangible only to the person or the entity to which the

information is destined. For instance, long-band radio stations or foreign newspapers

are meaningful only to those who speak the tongue. Within such channels, information

makes sense only to the populations who have an interest in the acquisition or the use of

the corresponding information.

What one usually calls intelligence is the faculty to relate together separate pieces of

information,

to make sense of them in a speciﬁc context or with respect to a higher

level of information knowledge. One may refer to intelligence as the means coherently

to integrate information into a vital, self-preserving, or self-evolving way.

Another (but somewhat very speciﬁc) deﬁnition of intelligence is the systematic

collection of information on target subjects by states, agencies, or private consultants.

This activity is made in the purpose of gaining some strategic or economic advantage,

of gaining a higher perspective on a business, a market, a competitor, or a country. The

goal is to acquire or to maintain a competitive edge, for reasons of security and superior

decision-making. The collected information can also represent a product for sale, as in

the proliferating consultancy businesses.

Most people are concerned with the ﬁrst type of intelligence, a skill whose acquisition

and development begins in early school through the apprenticeship of language, then

writing, math, literature, geography, history, and other knowledge. At a later stage,

we eventually specialize into some form of integrated knowledge, which deﬁnes our

situation, responsibility, wealth, and fate in society. Yet, the intelligent acquisition and

processing of information never ceases, whether in private or in professional life. It

is a commonplace to say that we are controlled by information. From a materialistic

viewpoint, the primary goal of life is to collect the information that is useful for various

personal reasons, such as societal compliance, mind growth, satisfaction, self-image,

empowerment, standard of living, or material survival.

Fortunately, intelligence does act as an information ﬁlter. It is able to control the

ﬂow of information and to select what is relevant to any of the above needs. The rest

represents “useless” information, like spam mail. Its fate is to vanish into oblivion. On

the other hand, “useful” information is what intelligence looks after, with various degrees

of expectation and priorities. The last notion of priority implies a personal investment to

acquire and integrate information. If information must guide decisions and actions and,

overall, future growth, this effort is of vital importance. The need to deploy effort in the

The word intelligence comes from the Latin inter-ligere, literally meaning “linking things together.”

3.1 Making sense of information 39

acquisition and integration of information is too often overlooked, because of the fallacy

that one could get informed through the news media, or just by browsing the Internet

from a cell phone. To get informed is not only to access raw information, but also to

make sense of it; this is where the effort comes. Intelligence may be a gift, but it takes

some effort to make intelligent use of information.

As we all know, the principle of so-called computers is to process information,

as reduced into data.

Computers perform this data processing at higher speeds and

with larger amounts than the human brain can handle, which reﬂects a man-made

form of higher intelligence. But this intelligence is not that of a machine. It is that of

the designers who have conceived the machine and developed the code that is operated

by the machine. Hence, the old-fashioned appellation of artiﬁcial intelligence, which,

despite its phenomenal information-processing power, only emulates human intelligence.

The man–machine intelligence challenge is well illustrated by chess contests, where the

latter often wins but only for reasons of memory (having registered all champions’

strategies in chess history) and computing power (having the possibility to analyze

several moves in advance). The chances to win over the machine are higher if the

player adopts some tactics that the machine has not prerecorded or cannot ﬁgure out the

rationale thereof. One may recall Arthur C. Clarke’s 2001: A Space Odyssey (of which

S. Kubrick made the famous movie), in which HAL,

the mightiest supercomputer ever

designed in history, is eventually defeated by Dave, the more intelligent astronaut. For

those who do not know the story, HAL could not compute the possibility that Dave

would take a life chance by forcing his way back to the space station without wearing a

helmet. The computer’s intelligence may be virtually unbounded, but it is also exposed

to some gaps in which human beings may easily compete. Computer hackers are here to

illustrate that the most sophisticated ﬁrewalls can be broken into by means of exploiting

such gaps. But that is another debate.

Since information is not about intelligence, what would be the use of an information

theory? Could information theory ever be a science, as information science is to com-

puters? Let us look at this question more closely. In accurate terminology, information

science (or informatics), is a branch of computer science. Corresponding deﬁnitions go

as follows:

Information science is primarily concerned with the structure, creation, management,

storage, retrieval, dissemination, and transfer of information. It also includes study-

ing the application of information in organizations, on its usage and the interaction

between people, organizations, and information systems.

Computer science encompasses a variety of topics that relate to computation, such

as abstract analysis of algorithms, ( . . . ) programming languages, program design,

software and computer hardware. It is knowledge accumulated through scientiﬁc

methodology by computation or by the use of a computer.

The word compute comes from the Latin com (together) and putare (to root, reckon, number, appraise,

estimate).

The name HAL stems from a one-letter shift of the IBM (Information Business Machines) company acronym.

http://en.wikipedia.org/wiki/information_science, http://en.wikipedia.org/wiki/Computer_science.

40 Measuring information

We observe from the above deﬁnitions that information science, a branch of computer

science, is not concerned in assessing the value within information, other than taking

care of it for some user beneﬁt (acquiring, storing, transferring, retrieving, sharing . . .).

In this view, the Internet is a perfect application of information science. It is left to the

user to ﬁnd the value and derive the beneﬁts of information through intelligent use.

In contrast with the above, information theory is a branch of applied mathematics.

It is concerned with the issues of coding, transmitting, and retrieving information.The

three key applications of information theory are the transmission of data through special

codes that enable error correction (transmission accuracy), compression (transmission

and storage conciseness), and encryption (secrecy and security of transmission). Again,

we observe that information theory is not meant to assess the value of information,

or its relevance in terms of intelligent use. Internet communications depend heavily

on these three applications: error correction, to preserve data integrity after multiple

switching or routing and global transport; data compression, to accelerate uploading

and downloading of web pages, text, and image ﬁles; and cryptography, to secure

transactions or to protect privacy. Yet the intelligent use of the Internet information is left

to the end users, discussion groups, web-content managers, and developers of websites.

In this respect, information theory could be viewed as a misnomer, just like information

science, because there is neither theory nor science that can assess how one can properly

deal with information and its contents, in the broadest sense of the recipient’s beneﬁt.

The future may reveal new theories of information, which could empower the user with

some automatic assessment of the information usefulness or value in terms of scientiﬁc,

societal, personal, and global impact. Without a shadow of a doubt, this would lead to a

worrisome information computer, with Internet pervasiveness in both professional and

private areas, taking care of everything in order for us not to worry about anything, just

like the space companion HAL. This might also change the face of the Internet, with

more and more intelligent browsers and search engines to present us the information the

way we may appreciate it the most. Maybe we are not that far from such a frightening

reality. Nevertheless, this only remains a matter of philosophical debate and speculation.

To close this preliminary discussion, we may simply conclude that information theory

is neutral about information content and its subjective value. Its purpose is to derive

mathematical algorithms for measuring, coding, and processing information, as reduced

to immaterial data. The rest of this chapter is dedicated to the issue of measuring

information, which is central to information theory. The nice and exciting thing indeed,

is that information can be measured, and this will be our starting point in the information-

theory journey.

3.2 Measuring information

Haven’t we experienced rushing to the mailbox, the newsstand, or the TV? This excep-

tional interest in the mail or the news has many possible reasons: appointment conﬁr-

mation, contract signature, conclusion of litigation, events of nationwide impact, such

as disasters, elections, sports, but also house hunting, job classiﬁeds, favorite rubrics,

3.2 Measuring information 41

or, for children, Sunday cartoons! We have all also noticed that the value attributed to

the mail or the newspaper decreases relatively quickly. Once read, both usually go to the

recycling bin. This indicates that the information in these types of news has a special

meaning in terms of being new or unexpected, which sharpens our interest.

In a scale of information interest, unexpected facts are what give information its

highest scores. In contrast, there is decreasing interest in hearing or reading again the

same news, except for the purpose of memorizing the information details. Jokes provide

a good example here. The real information hidden in the joke is not the story but the

conclusion or punch line. The joke may be a good one for various complex reasons, but

an important common element is that the meaning of the punch line must be completely

unexpected. A joke for which everyone in the audience already knows the conclusion

is of little interest. This observation leads to a sense that the interest of information

is the highest when it is fully unexpected to the recipient. The intrinsic importance of

information is thus intimately associated with some degree of uncertainty. If an event is

very likely, we gain little information in learning that it ﬁnally occurred. The converse

is also true: unlikely or surprising events are those containing the highest information

potential. Thus, information and event probabilities are connected, which bring us on

track towards a measure deﬁnition. Consider next a practical example.

A lotto surprise

Assume that I play the lotto, and the information I am looking after is the lotto’s results.

The ofﬁcial information ﬁnally comes as the following message:

x = The winning combination is 7, 13, 17, 18.

The meaningful part of this information is the four-number set. After I compare these

numbers with the ones printed on my ticket, the information reduces to either x =Ihave

won, or x = I have lost. Concisely expressed, the two possible information events are

x = W or x = L, respectively, with X =

{

W, L

}

representing the event set. To each of

these events (x = W or x = L) is associated a probability, noted p(x). For simplicity,

we shall note p(x = W ) = p(W ) and p(x = L) = p(L).

To recall from Chapter 1, a probability is a positive number taking any value between

0 (impossible event) and 1 (absolutely certain event). The sum of all probabilities, which

represent the combined likelihood of all possible events in X, is equal to unity.

With the lotto, we know from experience that the odds of winning are quite

small, and the odds of losing are, therefore, substantially high. For instance, we may

assume:

p(W ) = 0.000001, (3.1)

p(L) = 1 − p(W ) = 0.999999, (3.2)

meaning that the odds of winning are 1/1 000 000 or 1 in a million.

How much information do I get when hearing the lotto result? Obviously, my expec-

tations of winning being not very high, I won’t learn much upon realizing that I have,

indeed, lost. But in the contrary case, if I win, this is quite a phenomenal surprise! There

42 Measuring information

is a lot of information in the winning event, to the same extent there is little information

in the losing event.

Now we are looking for a formal way of deﬁning the amount of information, which

we could use as an objective measure reference I (x) for each possible event x.We

may postulate that I (x) should approach zero for events close to absolute certainty

(p(x) → 1), and inﬁnity for events reaching impossibility ( p(x) → 0). We must also

require that for two events x

, x

such that p(x

) < p(x

), we have I (x

) > I (x

meaning that the less likely event is associated with greater information. An information

measure I (x) that satisﬁes all these properties is the following:

I (x) = log



p(x)



=−log[p(x)]. (3.3)

In the above, the function log represents the natural logarithm, with the unit of I (x)

being called a nat. Note the minus sign in the deﬁnition’s right-hand side, which ensures

that the measure of information I (x) is a positive number. This deﬁnition only applies

to events of nonzero probability (p(x) > 0), meaning that the deﬁnition does not apply

to impossible events ( p(x) = 0), or only in the sense of a limit.

In our lotto example, we have

I (W ) =−log(0.000001) = 13.8 nats, (3.4)

I (L) =−log(0.999999) = 0.000001 nat. (3.5)

Thus, to win this lotto game represents some 14 nats of information, while losing means

negligible information, namely, orders of magnitude below (10

−6

nat).

In the deﬁnition of I (x), it is also possible to choose base-two or base-ten logarithms.

This changes the information scale, but the qualitative result remains the same: infor-

mation continuously increases as the likelihood of events decrease. I will come back to

this issue later.

Next, let us explore some more properties of the proposed information measure.

Consider two unrelated or independent events A and B, with probabilities p( A) and

p(B). We deﬁne the joint probability p(A, B) as the probability that both events A

and B occur. As we have seen in Chapter 1,ifA and B are independent events, then

p(A, B) = p(A) p(B). The information associated with the joint events is, therefore,

I ( A, B) =−log[p( A, B)]

=−log[ p(A) p(B)]

=−log[ p(A)] −log[p(B)] (3.6)

≡ I (A) + I (B).

The result shows that the information measure of the joint event is the sum of the

information measures associated with each event considered separately. Information is,

thus, an additive quantity. Such a property holds true only if the events are independent.

The more complex case where events are not independent will be addressed later on.

Using the rule for logarithms: log(XY) = log X + log Y (X and Y being positive).

3.3 Information bits 43

In the following, I will refer to information measure simply as information, in the IT

meaning of the word.

What if the two events A and B are not independent? Then we know from Bayes’s the-

orem that p(A, B) = p(A

B ) p(B) = p(B

A )p(A). The information associated with

the joint event is, therefore,

I ( A, B) =−log[p( A, B)]

=−log[ p(A) p(B

A )]

=−log[ p(A)] −log[p(B

A )] (3.7)

≡ I (A) + I [p(B

A )].

The result shows that the information of the joint event is the sum of the information

concerning event A and the information concerning event B – knowing that event A

occurred. The term I [p(B

A )] is referred to as conditional information.

3.3 Information bits

Since we have established that information can be measured according to its degree of

surprise, it is interesting to ﬁnd the minimal information measurement one can make.

This concept is encapsulated in the familiar coin-tossing game.

Since a coin has two sides (heads and tails), the probabilities that it falls on either

side are equal (overlooking here any other material possibility). This feature is translated

mathematically into the relation p(x = heads) = p(x = tails) = 1/2. Consistent with

the deﬁnition in Eq. (3.3), the information that one gets from tossing a coin is I (x) =

−log[ p(x)] or, in this case, I (heads) = I (tails) =−log(1/2) = 0.693 nat. We may

choose logarithms in base 2 to make this information value an integer, namely, deﬁning

I (x) =−log

p(x), (3.8)

which gives I (heads) = I (tails) =−log

−1

) =−(−1) log

(2) = 1. The unit of this

new measure of information is the bit, as short for binary digit.

What a bit represents is, thus, the exact amount of elementary information necessary

to describe the outcome of a coin tossing. The property I = 1bitmeans that the message

used to transmit the information only requires a single symbol, out of a source of 2

= 2

possible symbols. We can thus use any character pair, for instance, tails =0 and heads =

1, for simplicity. The conclusion is that the smallest information message is a bit, namely,

containing either 0 or 1 as a symbol.

The information regarding the outcome of the

coin tossing can thus be communicated through a single message bit, which represents

the minimum amount of measurable information.

The conversion between natural and base-2 logarithms is given by the relation log

x = log x/ log 2 ≈

1.442 log x.

We could also have used base-3 or base-4 logarithms, deﬁning the “trit” or the “quad,” as representing

three-valued or four-valued units of information. But the bit is the most elementary unit that cannot be sliced

down into a smaller dimension.

44 Measuring information

If we toss the coin several times in a row, the information concerning the succession

of outcomes is described by a string of as many single bits. For instance, the message

consisting in the string 1101001101 . . . means that the ﬁrst two outcomes are heads, the

third is tails, and so on.

To illustrate the concept of minimal information measure further, consider the case of

a die. As we know, a die is a cube with six spotted faces, corresponding to the event source

X =

{

1, 2, 3, 4, 5, 6

}

. The faces have equal probabilities of showing up as the die rolls

out and stops (assuming no other physical possibility). The equiprobability translates into

the relation p(x = 1) = p(x = 2) = ... = p(x = 6) = 1/6. The information contained

in any die-roll measurement is, therefore,

I (X) =−log

(1/6) = log

(6) ≈ 2.584 bits. (3.9)

The above result is puzzling because it shows that the bit information can be a noninteger,

i.e., any positive real number. But how can one form a message string with 2.584 bits?

The explanation is not to confuse between the information measure (the bit) and the

number n of 1/0 symbols that is actually required to form the message. What the above

result tells us is that the die-roll information can be coded by any string of n symbols,

satisfying n ≥ 2.584. This means that the minimum string length is n = 3. It does,

indeed, take three binary bits to represent all numbers from one to six, using the same

symbol or block length.

Next, we are going to show that binary coding is not the only way to encapsulate this

information. Indeed, the full information of a single die roll can also be coded through

a block of three YES or NO symbols, which provide the answer to three independent

questions Q1, Q2, and Q3. Here is an example of the three questions:

Q1: Is the result x even?

If YES, then x ∈{2, 4, 6}=U

, if NO, then x ∈{1, 3, 5}=U

Q2: Is the result x strictly greater than 3?

If YES, then x ∈{4, 5, 6}=V

; if NO, then x ∈{1, 2, 3}=V

Q3: Is the result x divided by 3?

If YES, then x ∈{3, 6}=W

; if NO, then x ∈{1, 2, 4, 5}=W

The combined answers to the three questions yield the value of x (in ensemble language,

one writes x = U

∩ V

∩ W

, with i, j, k = 1 or 2). For instance, we have 5 = U

∩

∩ W

. It is straightforward to verify that the code correspondence is:

1 = NO/NO/NO,

2 = YES/NO/NO,

The choice of code being arbitrary; we can use the binary representation, 1 = 001, 2 = 010, 3 = 011, 4 =

100, 5 = 101, 6 = 110, noting that the blocks 000 and 111 are unused.

3.4 R

enyi’s fake coin 45

3 = NO/NO/YES,

4 = YES/YES/NO,

5 = NO/YES/NO,

6 = YES/YES/YES,

while the two messages YES/NO/YES and NO/YES/YES are unused (in ensemble lan-

guage, U

∩ V

∩ W

= U

∩ V

∩ W

=∅, meaning that these ensembles are empty).

Regardless of the code, we see that the symbol blocks require three symbols of

binary value bits (YES/NO or 1/0), while the information carried by the message is

only 2.584 bits. Why do we have an extra 0.416 bit of information in the message?

The explanation for this mystery is in fact quite simple. Assume a source that has

eight equiprobable symbols, i.e., Y ={1, 2, 3, 4, 5, 6, 7, 8}, which can also be written

Y = X ∪{7, 8}. The information of Y is I (Y ) =−log

(1/8) = log

= 3log

2 =

3 bits. Since our previous messages describe the outcome of a die roll, the symbols

(7, 8), which have a probability of zero, are never used. The consequence of never using

these two symbols is that the actual probabilities of the six other symbols are raised by a

factor of 8/6. This increase in likelihood corresponds to a relative information decrease

(or less surprise!) of I =−log(8/6) =−0.416 bit. Thus, the net information in the

message is I

net

= I (Y ) +I = 3 −0.416 = 2.584 bits.

One may justly argue that we get noninteger information because of the arbitrary

choice of a base-2 logarithm. For the die roll, we could equally well choose a base-

6 logarithm, i.e., I

(

)

=−log

(x) = log

(6) = 1 sit (for “six-ary digit”). Then the

information of the die roll can be given by a single sit symbol, instead of three bits.

However, the sit is six-valued, which requires six different symbols per elementary

information, as opposed to the two-valued bit, which only requires two symbols. Which

of the two message blocks is better: one made of a single six-valued symbol, or one made

of three two-valued symbols (bits)? Obviously, the ﬁrst type is the shortest possible, but

the symbol is more complex to identify. The second type is longer, but the symbol

interpretation the most straightforward. Actually, the choice of symbol representation,

by the use of multivalued symbol alphabets, is fully arbitrary. However, for computer

implementation, the bit remains the most practical way of coding information.

The lesson learnt is that information messages always require an integer number of

symbols, the 1/0 bit being the simplest or most elementary type. The bit-measure of

information (I ), however, is any real positive number. Since the number of required

message bits n cannot be less than the information I to be conveyed (n ≥ I ); it is,

therefore, given by the integer equal to or immediately greater than I .

3.4 R

enyi’s fake coin

The “fake-coin” determination problem was originally described by the mathematician

A. R

enyi.

It brilliantly illustrates for the purposes of this entry-level chapter how

A. R

enyi, A Diary on Information Theory (New York: John Wiley & Sons, 1984), p. 10.

46 Measuring information

the information measure can be applied to ﬁnd the solution of complex optimization

problems, in particular, where the outcomes are ternary or multivalued. Let’s move

directly onto the fun stuff.

Assume that a medieval jeweler was presented with 27 gold coins, all looking strictly

identical, but with one of them being fake, being made of a lighter metal. The jeweler

only has a scale with two pans. What is the minimum number of weight measurements

needed for the jeweler to ﬁgure out which coin is the fake?

Answer: A ﬁrst hunch comes from realizing that the problem is wholly similar to the

2-faced coin or the 6-faced die examples. All coins presented have equal probabilities,

p(1/27), of being the fake one. According to our information-theory knowledge, we

conclude that the number of information bits required to identify one out of 27 coins

is I = log

27 = log

= 3log

3 bit. We just need to ﬁnd a technique to acquire the

information I through a minimum number of trials or weighting measurements.

A painstaking approach but not the smartest, as we shall see, consists in comparing

the weights of all coins with respect to a same reference coin, which the jeweler would

initially pick up at random. If he happens to pick up for reference the fake coin, he

gets the answer right away with the ﬁrst measurement. The probability for this lucky

conclusion is 1/27, or 3.7%. In the worst case, where all of his successive measurements

balance out, it would take 25 operations to conclude the test.

Yet, we may observe that

this is not a bad method if the scale is too delicate and cannot take more than one coin in

each pan. Let us assume that the scale is robust and sufﬁciently accurate to weigh groups

of ten coins or so. Consider then the outcome of any scale measurement with groups of

several coins with equal numbers, as selected at random. There are three possible, and

equiprobable outcomes:

(a) Left pan heavier;

(b) Right pan heavier;

The outcome is a ternary answer (YES/NO/NEUTRAL) with equiprobable outcomes.

Each of these single measurements (a), (b), (c), thus, yields an information of I

−log

(1/3) = log

3 bit, and n such independent measurements yield the information

= n log

3 ≡ nI/3. This result shows that the minimum number of measurements

required to sort the fake coin from the group is n = 3, since 3I

= I . This is a second

hunch towards the problem solution. However, we don’t know anything yet about how

to proceed, in order to get the answer through this “theoretical” minimum of three

operations.

The solution provided by R

enyi is illustrated in Fig. 3.1. It consists in making a

succession of selective measurements, ﬁrst with two groups of nine coins, then two

groups of three coins, then with two groups of one coin, each one identifying where the

fake coin is located. This solution proves that three measurements indeed are sufﬁcient

to get the answer!

Indeed, if the ﬁrst 25 measurements with coin numbers 2–26 balance out, the reference coin (number 1)

cannot be fake, so coin number 27 is the fake one.