XVIIContents.1928.3 The Rate-Distortion Theorem.8.4TheConverse.2002028.5Achievability of Rr(D)207Chapter Summary.208ProblemsHistorical Notes209.2119The Blahut-Arimoto Algorithms.2129.1AlternatingOptimization9.2TheAlgorithms.214.2149.2.1ChannelCapacity.2199.2.2The Rate-Distortion Function..2229.3Convergence..2229.3.1ASufficientCondition.2259.3.2Convergence to the Channel CapacityChapter Summary.226Problems.227228Historical Notes.22910DifferentialEntropy10.1 Preliminaries231.23510.2Definition10.3JointDifferentialEntropy,Conditional (Differential)Entropy,.238and Mutual Information10.4TheAEPforContinuousRandomVariables.245..24810.5InformationalDivergence.24910.6MaximumDifferentialEntropyDistributions.252Chapter SummaryProblems.255256Historical NotesContinuous-Valued Channels.25711.25711.1 Discrete-Time Channels11.2TheChannel CodingTheorem:.26011.3Proofof theChannelCodingTheorem..262.26211.3.1 The Converse11.3.2Achievability.26511.4 Memoryless Gaussian Channels.270.27211.5 Parallel Gaussian Channels..27811.6 Correlated Gaussian Channels..28011.7TheBandlimited White Gaussian Channel..28711.8TheBandlimited ColoredGaussianChannel11.9 Zero-Mean Gaussian Noise Is the Worst Additive Noise290.294Chapter SummaryProblems296Historical Notes297
Contents XVII 8.3 The Rate-Distortion Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192 8.4 The Converse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200 8.5 Achievability of RI (D) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208 Historical Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 9 The Blahut–Arimoto Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . 211 9.1 Alternating Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212 9.2 The Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214 9.2.1 Channel Capacity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214 9.2.2 The Rate-Distortion Function . . . . . . . . . . . . . . . . . . . . . . . 219 9.3 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 9.3.1 A Sufficient Condition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 9.3.2 Convergence to the Channel Capacity . . . . . . . . . . . . . . . . 225 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227 Historical Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228 10 Differential Entropy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229 10.1 Preliminaries. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 10.2 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235 10.3 Joint Differential Entropy, Conditional (Differential) Entropy, and Mutual Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238 10.4 The AEP for Continuous Random Variables . . . . . . . . . . . . . . . . 245 10.5 Informational Divergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248 10.6 Maximum Differential Entropy Distributions . . . . . . . . . . . . . . . . 249 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255 Historical Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256 11 Continuous-Valued Channels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257 11.1 Discrete-Time Channels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257 11.2 The Channel Coding Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260 11.3 Proof of the Channel Coding Theorem . . . . . . . . . . . . . . . . . . . . . 262 11.3.1 The Converse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262 11.3.2 Achievability. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265 11.4 Memoryless Gaussian Channels . . . . . . . . . . . . . . . . . . . . . . . . . . . 270 11.5 Parallel Gaussian Channels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272 11.6 Correlated Gaussian Channels . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278 11.7 The Bandlimited White Gaussian Channel. . . . . . . . . . . . . . . . . . 280 11.8 The Bandlimited Colored Gaussian Channel . . . . . . . . . . . . . . . . 287 11.9 Zero-Mean Gaussian Noise Is the Worst Additive Noise. . . . . . . 290 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296 Historical Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297
XVIIIContents12MarkovStructures299.30012.1ConditionalMutualIndependence.30912.2FullConditionalMutualIndependence.31412.3MarkoyRandomField.31712.4 Markov Chain.319Chapter Summary..320ProblemsHistorical Notes.321.32313InformationInequalities.32513.1 The Region F13.2InformationExpressions inCanonicalForm.326..32913.3AGeometricalFramework13.3.1 Unconstrained Inequalities.32913.3.2Constrained Inequalities.33013.3.3Constrained Identities..332.33313.4EquivalenceofConstrainedInequalities13.5TheImplicationProblemof ConditionalIndependence336.337Chapter Summary..338ProblemsHistorical Notes33814 Shannon-Type Inequalities.339.33914.1 The Elemental Inequalities.34114.2ALinearProgrammingApproach...34314.2.1 Unconstrained Inequalities.14.2.2Constrained Inequalities andIdentities.34414.3ADuality.345.34714.4Machine Proving-ITIP14.5TacklingtheImplicationProblem35114.6Minimalityof theElemental Inequalitie353Appendix 14.A:The Basic Inequalities and the Polymatroidal.356AxiomsChapter Summary.357..358ProblemsHistorical Notes36015Beyond Shannon-TypeInequalities.36115.1 Characterizations of F2,F3,and *.361..36915.2 A Non-Shannon-Type Unconstrained Inequality15.3ANon-Shannon-Type Constrained Inequality..374.38015.4ApplicationsChapter Summary.383Problems.383Historical Notes385
XVIII Contents 12 Markov Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299 12.1 Conditional Mutual Independence . . . . . . . . . . . . . . . . . . . . . . . . . 300 12.2 Full Conditional Mutual Independence . . . . . . . . . . . . . . . . . . . . . 309 12.3 Markov Random Field . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314 12.4 Markov Chain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320 Historical Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321 13 Information Inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323 13.1 The Region Γ∗ n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325 13.2 Information Expressions in Canonical Form . . . . . . . . . . . . . . . . . 326 13.3 A Geometrical Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329 13.3.1 Unconstrained Inequalities. . . . . . . . . . . . . . . . . . . . . . . . . . 329 13.3.2 Constrained Inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330 13.3.3 Constrained Identities. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332 13.4 Equivalence of Constrained Inequalities . . . . . . . . . . . . . . . . . . . . 333 13.5 The Implication Problem of Conditional Independence . . . . . . . 336 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338 Historical Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338 14 Shannon-Type Inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339 14.1 The Elemental Inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339 14.2 A Linear Programming Approach. . . . . . . . . . . . . . . . . . . . . . . . . . 341 14.2.1 Unconstrained Inequalities. . . . . . . . . . . . . . . . . . . . . . . . . . 343 14.2.2 Constrained Inequalities and Identities . . . . . . . . . . . . . . . 344 14.3 A Duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345 14.4 Machine Proving – ITIP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347 14.5 Tackling the Implication Problem. . . . . . . . . . . . . . . . . . . . . . . . . . 351 14.6 Minimality of the Elemental Inequalities. . . . . . . . . . . . . . . . . . . . 353 Appendix 14.A: The Basic Inequalities and the Polymatroidal Axioms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358 Historical Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 360 15 Beyond Shannon-Type Inequalities . . . . . . . . . . . . . . . . . . . . . . . . 361 15.1 Characterizations of Γ∗ 2, Γ∗ 3, and Γ∗ n . . . . . . . . . . . . . . . . . . . . . . 361 15.2 A Non-Shannon-Type Unconstrained Inequality . . . . . . . . . . . . . 369 15.3 A Non-Shannon-Type Constrained Inequality . . . . . . . . . . . . . . . 374 15.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383 Historical Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385
XIXContents.38716EntropyandGroups.38816.1GroupPreliminaries.39316.2 Group-CharacterizableEntropyFunctions16.3AGroupCharacterizationofT.398.40116.4 Information Inequalities and Group Inequalities.405Chapter Summary..406ProblemsHistorical Notes408Part IIFundamentals of Network Coding..41117Introduction.41217.1 TheButterflyNetwork.41517.2Wireless and SatelliteCommunications.41717.3SourceSeparation.418ChapterSummary.418Problems419Historical Notes18 TheMax-FlowBound42118.1 Point-to-Point Communication Networks.42118.2ExamplesAchieving the Max-FlowBound.424.42718.3AClass of Network Codes.42918.4ProofoftheMax-FlowBound..431ChapterSummary.431ProblemsHistorical Notes43419 Single-SourceLinear NetworkCoding:.435Acyclic Networks.43619.1 Acyclic Networks..43719.2LinearNetwork Codes19.3DesirablePropertiesofaLinearNetworkCode:.443..44719.3.1Transformation of a LinearNetwork Code.44819.3.2ImplementationofaLinearNetworkCode44919.4ExistenceandConstruction.46019.5GenericNetworkCodes.46819.6StaticNetworkCodes19.7RandomNetwork Coding:ACase Study.473..47419.7.1HowtheSystemWorks19.7.2 Model and Analysis..475Chapter Summary.478Problems..479482Historical Notes
Contents XIX 16 Entropy and Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 387 16.1 Group Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 388 16.2 Group-Characterizable Entropy Functions . . . . . . . . . . . . . . . . . . 393 16.3 A Group Characterization of Γ∗ n . . . . . . . . . . . . . . . . . . . . . . . . . . 398 16.4 Information Inequalities and Group Inequalities . . . . . . . . . . . . . 401 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 406 Historical Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408 Part II Fundamentals of Network Coding 17 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411 17.1 The Butterfly Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412 17.2 Wireless and Satellite Communications . . . . . . . . . . . . . . . . . . . . . 415 17.3 Source Separation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 418 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 418 Historical Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419 18 The Max-Flow Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 421 18.1 Point-to-Point Communication Networks . . . . . . . . . . . . . . . . . . . 421 18.2 Examples Achieving the Max-Flow Bound . . . . . . . . . . . . . . . . . . 424 18.3 A Class of Network Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 427 18.4 Proof of the Max-Flow Bound. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 429 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431 Historical Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434 19 Single-Source Linear Network Coding: Acyclic Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 435 19.1 Acyclic Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 436 19.2 Linear Network Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 437 19.3 Desirable Properties of a Linear Network Code . . . . . . . . . . . . . . 443 19.3.1 Transformation of a Linear Network Code . . . . . . . . . . . . 447 19.3.2 Implementation of a Linear Network Code . . . . . . . . . . . . 448 19.4 Existence and Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 449 19.5 Generic Network Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460 19.6 Static Network Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 468 19.7 Random Network Coding: A Case Study . . . . . . . . . . . . . . . . . . . 473 19.7.1 How the System Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474 19.7.2 Model and Analysis. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 475 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 478 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479 Historical Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 482
XXContents20Single-Source Linear Network Coding:Cyclic Networks..48548520.1Delay-FreeCyclicNetworks48820.2ConvolutionalNetworkCodes49820.3DecodingofConvolutionalNetworkCodes.503ChapterSummary503Problems504Historical Notes21 Multi-source Network Coding.505.50521.1 TheMax-FlowBounds.50821.2ExamplesofApplication.50821.2.1 Multilevel Diversity Coding..51021.2.2SatelliteCommunicationNetwork.51121.3ANetworkCodeforAcyclicNetworks.51221.4TheAchievableInformationRateRegion21.5ExplicitInnerandOuterBounds.51521.6 The Converse.51652121.7Achievability52421.7.1 Random Code Construction..52721.7.2PerformanceAnalysis.536Chapter SummaryProblems.537Historical Notes539Bibliography541Index561
XX Contents 20 Single-Source Linear Network Coding: Cyclic Networks . . . . 485 20.1 Delay-Free Cyclic Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485 20.2 Convolutional Network Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 488 20.3 Decoding of Convolutional Network Codes . . . . . . . . . . . . . . . . . . 498 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 503 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 503 Historical Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 504 21 Multi-source Network Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505 21.1 The Max-Flow Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505 21.2 Examples of Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 508 21.2.1 Multilevel Diversity Coding . . . . . . . . . . . . . . . . . . . . . . . . . 508 21.2.2 Satellite Communication Network . . . . . . . . . . . . . . . . . . . 510 21.3 A Network Code for Acyclic Networks . . . . . . . . . . . . . . . . . . . . . 511 21.4 The Achievable Information Rate Region . . . . . . . . . . . . . . . . . . . 512 21.5 Explicit Inner and Outer Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . 515 21.6 The Converse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 516 21.7 Achievability. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 521 21.7.1 Random Code Construction . . . . . . . . . . . . . . . . . . . . . . . . 524 21.7.2 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 527 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 536 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 537 Historical Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 539 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 541 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 561
1TheScienceofInformationIn a communication system, we try to convey information from one point toanother,very often in a noisy environment. Consider thefollowing scenario.Asecretary needs to send facsimiles regularly and she wants to convey as muchinformation as possible on each page. She has a choice of the font size,whichmeans that more characters can be squeezed onto a page if a smaller font sizeis used. In principle, she can squeeze as many characters as desired on a pageby using a small enough font size.However,therearetwofactors in the systemwhich may cause errors. First, the fax machine has a finite resolution. Second,the characters transmitted may be received incorrectly due to noise in thetelephone line. Therefore, if the font size is too small, the characters may notbe recognizable on thefacsimile.On the other hand,although some characterson thefacsimile may not be recognizable, the recipient can still figure out thewords from the context provided that the number of such characters is notexcessive.In other words, it is not necessary to choose a font size such thatall the characters on the facsimile are recognizable almost surely.Then we aremotivated to ask: What is the maximum amount of meaningful informationwhich can be conveyed on one page of facsimile?This question may not have a definite answer because it is not very wellposed. In particular, we do not have a precise measure of meaningful informa-tion. Nevertheless, this question is an illustration of the kind of fundamentalquestions we can ask about a communication system.Information, which is not a physical entity but an abstract concept, is hardto quantify in general. This is especially the case if human factors are involvedwhen the information is utilized. For example, when we play Beethoven'sviolin concertofrom an audio compact disc,wereceive themusical informationfrom the loudspeakers. We enjoy this information because it arouses certainkinds of emotion within ourselves. While we receive the same informationevery time we play the same piece of music, the kinds of emotion arousedmay be different from time to time because they depend on our mood atthat particular moment. In other words, we can derive utility from the sameinformation every time in a different way. For this reason, it is extremely
1 The Science of Information In a communication system, we try to convey information from one point to another, very often in a noisy environment. Consider the following scenario. A secretary needs to send facsimiles regularly and she wants to convey as much information as possible on each page. She has a choice of the font size, which means that more characters can be squeezed onto a page if a smaller font size is used. In principle, she can squeeze as many characters as desired on a page by using a small enough font size. However, there are two factors in the system which may cause errors. First, the fax machine has a finite resolution. Second, the characters transmitted may be received incorrectly due to noise in the telephone line. Therefore, if the font size is too small, the characters may not be recognizable on the facsimile. On the other hand, although some characters on the facsimile may not be recognizable, the recipient can still figure out the words from the context provided that the number of such characters is not excessive. In other words, it is not necessary to choose a font size such that all the characters on the facsimile are recognizable almost surely. Then we are motivated to ask: What is the maximum amount of meaningful information which can be conveyed on one page of facsimile? This question may not have a definite answer because it is not very well posed. In particular, we do not have a precise measure of meaningful information. Nevertheless, this question is an illustration of the kind of fundamental questions we can ask about a communication system. Information, which is not a physical entity but an abstract concept, is hard to quantify in general. This is especially the case if human factors are involved when the information is utilized. For example, when we play Beethoven’s violin concerto from an audio compact disc, we receive the musical information from the loudspeakers. We enjoy this information because it arouses certain kinds of emotion within ourselves. While we receive the same information every time we play the same piece of music, the kinds of emotion aroused may be different from time to time because they depend on our mood at that particular moment. In other words, we can derive utility from the same information every time in a different way. For this reason, it is extremely