6 Communications6.1 Source Model6.1.1 Kraft Inequality6.2 Source Entropy6.2.1 Gibbs Inequality6.3 Source Coding Theorem6.4 Channel Model6.5 Noiseless Channel Theorem6.6 Noisy Channel6.7 Noisy Channel Capacity Theorem6.8 Reversibility6.9 Detail: Communication System RequirementsChapter 6CommunicationsWe have been considering a model of an information handling system in which symbols from an input areencoded into bits, which are then sent across a “channel” to a receiver and get decoded back into symbols,as shown in Figure 6.1.Source EncoderCompressorChannel EncoderChannelChannel DecoderExpanderSource Decoder(Bits)(Bits)(Bits)(Bits)- - - - - - - -Input Output(Symbols) (Symbols)Figure 6.1: Communication systemIn this chapter we focus on how fast the information that identifies the symb ols c an be transferred tothe output. The symbols themselves, of course, are not transmitted, but only the information necessary toidentify them. This is what is necessary for the stream of symbols to be recreated at the output.We will model both the source and the channel in a little more detail, and then give three theoremsrelating to the source characteristics and the channel capacity.6.1 Source ModelThe source is assumed to produce symbols at a rate of R symbols per second. Each symb ol is chosenfrom a finite set of possible symbols, and the index i ranges over the possible symbols. The event of theselection of symbol i will be denoted Ai.Let us suppose that each event Ai(i.e., the selection of the symbol i) is represented by a different codewordCiwith a length Li. For fixed-length codes such as ASCII all Liare the same, whereas for variable-lengthcodes, such as Huffman codes, they are generally different. Since the codewords are patterns of bits, theAuthor: Paul Penfield, Jr.This document: http://www.mtl.mit.edu/Courses/6.050/2007/notes/chapter6 .pd fVersion 1.4, March 8, 2007. Copyrightc 2007 Massachusetts Institute of TechnologyStart of notes · back · next | 6.050J/2.110J home page | Site map | Search | About this document | Comments and inquiries696.2 Source Entropy 70number available of each length is limited. For example, there are only four distinct two-bit codewordspossible, namely 00, 01, 10, and 11.An important property of such codewords is that none can be the same as the first portion of another,longer, codeword—otherwise the same bit pattern might result from two or more different messages, andthere would be ambiguity. A code that obeys this property is called a prefix-condition code, or sometimesan instantaneous code.6.1.1 Kraft InequalitySince the number of distinct codes of short length is limited, not all codes can be short. Some must belonger, but then the prefix condition limits the available short codes even further. An important limitationon the distribution of code lengths Liwas given by L. G. Kraft, an MIT student, in his 1949 Master’s thesis.It is known as the Kraft inequality:Xi12Li≤ 1 (6.1)Any valid set of distinct codewords obeys this inequality, and conversely for any proposed Lithat obeyit, a code can be found.For example, suppose a code consists of the four distinct two-bit codewords 00, 01, 10, and 11. Theneach Li= 2 and each term in the sum in Equation 6.1 is 1/22= 1/4. In this case the equation evaluatesto an equality, and there are many different ways to assign the four codewords to four different symbols.As another example, suppose there are only three symbols, and the proposed codewords are 00 01, and 11.In this case the Kraft inequality is an inequality. However, because the sum is less than 1, the code canbe made more efficient by replacing one of the codewords with a shorter one. In particular, if the symbolrepresented by 11 is now represented by 1 the result is still a prefix-condition code but the sum would be(1/22) + (1/22) + (1/2) = 1.The Kraft inequality can be proven easily. Let Lmaxbe the length of the longest codeword of a prefix-condition code. There are exactly 2Lmaxdifferent patterns of 0 and 1 of this length. ThusXi12Lmax= 1 (6.2)where this sum is over these patterns (this is an unusual equation because the quantity being summed doesnot depend on i). At least one of these patterns is one of the codewords, but unless this happens to b ea fixed-length code there are other shorter codewords. For each shorter codeword of length k (k < Lmax)there are exactly 2Lmax−kpatterns that begin with this codeword, and none of those is a valid codeword(because this code is a prefix-condition code). In the sum of Equation 6.2 replace the terms correspondingto those patterns by a single term equal to 1/2k. The sum is unchanged. Continue this process with othershort codewords. When it is complete, there are terms in the sum corresponding to every codeword, andthe sum is still equal to 1. There may be other terms corresponding to patterns that are not c odewords—ifso, eliminate them from the sum in Equation 6.2. The result is exactly the sum in Equation 6.1 and is lessthan or equal to 1. The proof is complete.6.2 Source EntropyAs part of the source model, we assume that each symbol selection is independent of the other symbolschosen, so that the probability p(Ai) does not depend on what symbols have previously been chosen (thismodel can, of course, be generalized in many ways). The uncertainty of the identity of the next symbolchosen, H, is the average information gained when the next symbol is made known:H =Xip(Ai) log21p(Ai)(6.3)6.2 Source Entropy 71This quantity is also known as the entropy of the source, and is measured in bits per symbol. Theinformation rate, in bits per second, is H · R where R is the rate at which the source selects the symbols,measured in symbols per second.6.2.1 Gibbs InequalityHere we present the Gibbs Inequality, named after the American physicist J. Willard Gibbs (1839–1903)1,which will be use ful to us in later proofs. This inequality states that the entropy is smaller than or equal toany other average formed using the same probabilities but a different function in the logarithm. Specifically,Xip(Ai) log21p(Ai)≤Xip(Ai) log21p0(Ai)(6.4)where p(Ai) is any probability distribution (we will use it for source events and other distributions) andp0(Ai) is any other probability distribution, or more generally any set of numbers such that0 ≤ p0(Ai) ≤ 1 (6.5)andXip0(Ai) ≤ 1. (6.6)As is true for all probability distributions,Xip(Ai) = 1. (6.7)Equation 6.4 can be proven by noting that the natural