6.441 Spring 2006 -1Paper reviewA Mathematical Theory of CommunicationJin Woo Shin, Sang Joon Kim1 IntroductionThis paper opened the new area - the information theory. Before this paper, most people believedthat the only way to make the error probability of transmission as small as desired is to reduce thedata rate (such as a long repetition scheme). However, surprisingly this paper revealed that it doesnot need to reduce the data rate for achieving that much of small errors. It proved that we can getsome positive data rate that has the same small error probability and also there is an upper boundof the data rate, which means we cannot achieve the data rate with any encoding scheme that hassmall enough error probability over the upper b ound.For reviewing this noble paper, first, we summarize the paper at our point of view and then discussseveral topics concerned with what the paper includes.2 Summary of the paperThe paper was categorized as five parts - PART I: Discrete Noiseless systems, PART II: The DiscreteChannel With Noise, PART I II: Mathematical Preliminaries, PART IV: The Continuous Channel,PART V: The Rate For A Continuous Source.We reconstruct this structure as four parts. We combine PART I and PART III to 2.1 Prelim-inary. PART I contained the important concepts for demonstrating the following parts such asentropy and ergodic source. PART III extended the concept of entropy to the continuous casefor the last parts of paper. PART II,IV,V dealt with ’discrete source and discrete channel’ case,’discrete source and continuous channel’ case and ’continuous source and continuous channel’ caserespectively. We renamed each PARTs and summarize them with this point of view.2.1 PreliminaryThere are three essential concepts which are used for developing the idea of the paper. One isentropy to measure the uncertainty of the source and another is ergodic property to apply the AEPtheorem. The last is capacity to measure how much the channel allow to transfer the information.2.1.1 EntropyTo measure the quantity of information of a discrete source, the paper defined ”entropy”. To definethe measure H(p1, p2, · · · , pn) reasonably, it should satisfy the following three requirements:1. H should b e continuous in pi.6.441 Spring 2006 -22. If all pi=1nthen, H is monotonically increasing function of n.3. H is the weighted sum of two Hs divided from the original H.And the paper proved that the only function that satisfies the above three properties is:H = −KnXi=1pilog piThe entropy easily can be extended in the continuous case as following:h = −Z∞−∞p(x) log p(x)dx**we use h for representing the entropy in continuous case to avoid confusing that with the entropyH in discrete case.2.1.2 Ergodic sourceIn the Markov process, we call the graph is ergodic if it satisfies the following properties:1. IRREDUCIBLE: the graph does not contain the case of two isolated nodes A and B, i.e. everynode can reach to every node.2. APERIODIC: the GCD of the lengths of all cycles in the graph is 1.If the source is ergodic then, with any initial conditions, Pj(N) approach the equilibrium prob-ability when N → ∞ and for ∀j. Equilibrium probability is as following:Pj=XiPipi(j)2.1.3 CapacityThe paper defined capacity as two different ways and in Theorem 12 at page 25, it proved thesetwo definitions are identical. Two different definitions are as following:1. C = limT →∞log N(T )Twhere N(T ) is the number of possible signals and T is time duration.2. C = M ax(H(x) − H(x|y))2.2 Discrete Source and Discrete ChannelDiscrete source and Discrete Channel case means that the source information is discrete value andthe received data that are sent through the channel are also discrete values. In this case the paperproved the famous theorem (Theorem 11 at the page 22) that there is a rate upper bound that wecan achieve the error-free transmission. The detail theorem is as following:Theorem 1. If the discrete source entropy H is less than or equal to the channel capacity C thenthere exists a code that can be transmitted over the channel with arbitrarily small amount of errors.If H > C then there is no method of encoding which gives equivocation less than H − C.For proving this theorem, the paper used the assumption that the source is ergodic. With thisassumption, we can use the AEP theorem and the result is the above theorem.There are several examples that make sure the result of the theorem and the last one is interestingfor us. The last example is a simple encoding function whose rate is equal to the capacity of thegiven channel, i.e. the most efficient encoding scheme in that channel. The reason why this code isinteresting is that it is [7,4,3] Hamming code - the basic linear code.6.441 Spring 2006 -32.3 Discrete Source and Continuous Channel2.3.1 The capacity of a continuous channelIn a continuous channel, the input or transmitted signals will b e continuous functions of timef(t) belonging to a certain set, and the output or received signals will be perturb ed versions ofthese.(Although the title of this section includes ’discrete source’, a continuous channel assumes acontinuous source in general.) The main difference from the discrete case is the domain size of theinput and output of a channel becomes infinite. The capacity of a continuous channel is defined ina way analogous to that for a discrete channel, namelyC = maxP (x)(h(x) − h(x|y)) = maxP (x)Z ZP (x, y) logP (x, y)P (x)P (y)dxdyOf course, h in the above definition is a differential entropy.2.3.2 The transmission rate of a discrete source using a continuous channelIf the logarithmic base used in computing h(x) and h(x|y) is two then C is the maximum numberof binary digits that can be sent per second over the channel with arbitrarily small error, just asin the discrete case. We can check this fact in two aspects. At first, this can be seen physicallyby dividing the space of signals into a large number of small cells sufficiently small so that theprobability density P (y|x) of signal x being perturbed to point y is substantially constant over acell. If the cell are considered as distinct points the situation os essentially the same as a discretechannel. Secondly, in the mathematical side, it can be shown that if u is the message, x is thesignal, y is the received signal and v is the recovered message, thenh(x) − h(x|y) ≥ H(u) − H(u|v)regardless of what operations are performed on u to obtain x or on y to