Information Theory
...ry more than 6.4 million conversations. Or it can transmit the contents of 90,000 encyclopedias in just one second. 3 Even with these high speeds, today’s communications systems don’t approach the theoretical limits of fiber, wireless, and other systems. A single optical fiber strand, in theory, might transmit up to 100 quadrillion conversations (1 followed by seventeen 0’s), each encoded at 64,000 bits per second. Nor are communications scientists and engineers happy with the current high rates. They want more, because we need more. And Shannon’s equations, 50 years later, are still showing us the way. Understanding Information Theory Understanding Shannon’s equations, the basis of Information Theory, is not an easy matter. His work is abstract and subtle, the world of mathematicians and engineers, even though we see it has everyday consequences. To get a high-level understanding of his theory, a few basic points should be made. First, words are symbols to carry information between people. If one says to an American, “Let’s go!”, the command is immediately understood. But if we give the commands in Russian, “Pustim v xod!”, we only get a quizzical look. Russian is the wrong code for an American. Second, all communication involves three steps – coding a message at its source, transmitting the message through a communications channel, and decoding the message at its destination. In the first step, the message has to be put into some kind of symbolic representation – words, musical notes, icons, mathematical equations, or bits. When we write “Hello,” we encode a greeting. When we write a musical score, it’s the same thing – only we’re encoding sounds. For any code to be useful it has to be transmitted to someone or, in a computer’s case, to something. Transmission can be by voice, a letter, a billboard, a telephone conversation, a radio or television broadcast, or the now ubiquitous e-mail. At the destination, someone or something has to receive the symbols, and then decode them by matching them against his or her own body of information to extract the data. 4 Fourth, there is a distinction between a communications channel’s designed symbol rate of so many bits per second and its actual information capacity. Shannon defines channel capacity as how many kilobits per second of user information can be transmitted over a noisy channel with as small an error rate as possible, which can be less than the channel’s “raw” symbol rate. Shannon describes the elements of communications system theory as a source--encoder--channel--decoder--destination model. What his theory does is to replace each element in the model with a mathematical model that describes that element’s behavior within the system. The Meaning of Information “Information” has a special meaning for Shannon. For years, people deliberately compressed telegraph messages by leaving certain words out, or sending key words that stood for longer messages, since costs were determined by the number of words sent. Yet people could easily read these abbreviated messages, since they supplied these predictable words, such “a” and “the.” In the same vein, for Shannon, information is symbols that contain unpredictable news, like our sentence, “only infrmatn esentil to understandn mst b tranmitd.” The predictable symbols that we can leave out, which Shannon calls redundancy, are not really news. Another example is coin flipping. Each time we flip a coin, we can transmit which way it lands, “heads” or “tails,” by transmitting a code of “zero” or “one.” But what if the coin has two “heads” and everyone knows it? Since there is no uncertainty concerning the outcome of a flip, no message need be sent at all. Although this view might seem like common sense today, it was not always so. Shannon made clear that uncertainty or unpredictability is the very commodity of communication. 5 Encoding a Message Shannon equates information with uncertainty. For Shannon, an information source is someone or something that generates messages in a statistical fashion. Think of an speaker revealing her thoughts one letter at a time. From an observer’s point of view each letter is chosen at random, although the speaker’s choice may depend on what has been uttered before, while for other letters there may be a considerable amount of latitude. The randomness of an information source can be described by its "entropy." The operational meaning of entropy is that it determines the smallest number of bits per symbol that is required to represent the total output. As an illustration, suppose we are watching cars going past on a highway. For simplicity, suppose 50% of the cars are black, 25% are white, 12.5% are red, and 12.5% are blue. Consider the flow of cars as an information source with four words: black, white, red, and blue. A simple way of encoding this source into binary symbols would be to associate each color with two bits, that is: black = 00, white = 01, red = 10, and blue = 11, an average of 2.00 bits per color. A Better Code Using Information Theory However, by properly using Information Theory, a better encoding can be constructed by allowing for the frequency of certain symbols, or words: black = 0, white = 10, red = 110, blue = 111. How is this encoding better? With this code, the average number of bits per car will be less: 0.50 black x 1 bit = .500 0.25 white x 2 bits = .500 0.125 red x 3 bits = .375 0.125 blue x 3 bits = .375 Average-- 1.750 bits per car 6 Furthermore Information Theory tells us that the entropy of this information source is 1.75 bits per car and thus no encoding scheme will do better than the scheme we just described. In general, an efficient code for a source will not represent single letters, as in our example above, but will represent strings of letters or words. If we see three black cars, followed by a white car, a red car, and a blue car, the sequence would be encoded as 00010110111, and the original sequence of cars can readily be recovered from the encoded sequence. The theory also says how complex a code needs to be for a given complexity. As a general rule, the closer one compresses a source to its entropy, the more complex the code will become. Defining a Channel’s Capacity Having compressed the source output to a sequence of bits, we must transmit them. In Information Theory the medium of transmission is called a channel, which could, for example, accept as input one of 256 symbols (i.e., 8 bits) 8,000 times per second and deliver those symbols intact to its receiver. Take, as an example, a DS0 telephone channel of 64,000 bits per second. If the output symbols are identical to the input symbols, the channel is noiseless, and its information carrying capacity is 8 bits/symbol x 8000 symbols/second = 64000 bits/second. The channel’s designed symbol rate and its capacity are the same. Matters are more complex if...