Information Theory and Reliable Communication. by R. G. Gallager Review by: S. Kullback SIAM Review, Vol. 11, No. 4 (Oct., 1969), pp. 633-634 Published by: Society for Industrial and Applied Mathematics Stable URL: http://www.jstor.org/stable/2029107 . Accessed: 15/06/2014 06:57 Your use of the JSTOR archive indicates your acceptance of the Terms & Conditions of Use, available at . http://www.jstor.org/page/info/about/policies/terms.jsp . JSTOR is a not-for-profit service that helps scholars, researchers, and students discover, use, and build upon a wide range of content in a trusted digital archive. We use information technology and tools to increase productivity and facilitate new forms of scholarship. For more information about JSTOR, please contact
[email protected]. . Society for Industrial and Applied Mathematics is collaborating with JSTOR to digitize, preserve and extend access to SIAM Review. http://www.jstor.org This content downloaded from 194.29.185.216 on Sun, 15 Jun 2014 06:57:55 AM All use subject to JSTOR Terms and Conditions http://www.jstor.org/action/showPublisher?publisherCode=siam http://www.jstor.org/stable/2029107?origin=JSTOR-pdf http://www.jstor.org/page/info/about/policies/terms.jsp http://www.jstor.org/page/info/about/policies/terms.jsp SIAM RFVIFW Vol. 1 1, No. 4, October 1969 BOOK REVIEWS EDITED BY ARTHUR WOUK Publishers are invited to send books for review to Professor Arthur Wouk, Department of Engineer- ing Sciences, The Technological Institute, Northwestern University, Evanston, Illinois 60201. Information Theory and Reliable Communication. By R. G. GALLAGER. John Wiley and Sons, Inc., New York, 1968. xiv + 588 pp. $16.95. According to the author, the book under review is designed primarily for use as a first year graduate text in information theory, suitable for both engineers and mathematicians. The author assumes that the reader has some understanding of freshman calculus, elementary probability and some introductory random process theory, but also requires a reasonable level of mathematical maturity and capability for abstract thought on the part of the reader. It is the reviewer's opinion that a reader with only the understanding assumed above will need considerable guidance and assistance from an instructor. The book consists of nine chapters covering 502 pages, Exercises and Problems in a 66 page section, nine pages of References and Selected Readings a large number of which appeared in the last six years, a two page Glossary of Symbols, and an eight page Index. Each chapter is followed by Historical Notes and References and all but the first chapter are followed by a Summary and Conclusions. An in- dication of the topics covered is given by the chapter titles and brief statement. 1. Communication Systems and Information Theory. This offers a preview to the various topics discussed in the book. 2. A Measure of Information. Mutual and self-information are defined and their properties developed. 3. Codingfor Discrete Sources. How to encode sources using the minimum average number of code letters per source letter. 4. Discrete Memoryless Channels and Capacity. The probabilistic model of a channel is developed and the converse to the coding theorem is derived. 5. The Noisy-Channel Coding Theorem. Exponential upper bounds on error probability are derived. 6. Techniquesfor Coding and Decoding. Mathematical techniques are described as well as instrumentation. 7. Memoryless Channels with Discrete Time. Channels with arbitrary input and output spaces are examined with constraints on the input channel. 8. Waveform Channels. Channels considered are those in which the transmitted signal is filtered and added to stationary Gaussian noise, and those in which the transmission medium is dispersive and time varying. 9. Source Coding with a Fidelity Criterion. The fidelity criterion used is the average distortion per letter or per time unit between source and destination. This reviewer believes that some of the notation could be improved. The use of the bar to indicate expected value, though apparently common in engineering works, is clumsy and leads to awkward combinations, as witness the expression for the characteristic function of a multivariate distribution or the autocor- relation function of the output of a linear time-invariant filter. The use of line diagrams relating input and output with the conditional probabilities can be more conveniently, and with less confusion, replaced by appropriate matrices. 633 This content downloaded from 194.29.185.216 on Sun, 15 Jun 2014 06:57:55 AM All use subject to JSTOR Terms and Conditions http://www.jstor.org/page/info/about/policies/terms.jsp 634 BOOK REVIEWS The mathematician might be surprised to find the space L2 described as that of finite energy functions. This book will be of interest to every serious worker in the field of information theory and its applications to communications. However, it seems that the use of the book for a one semester course places a financial burden as well as a tech- nical one on the student. The author has succeeded in meeting the objectives he aimed at. S. KULLBACK The George Washington University Introduction To Combinatorial Mathematics. By C. L. Liu. McGraw-Hill Book Co., New York, 1968. x + 393 pp. $13.50. The author presents an introductory text at the senior-graduate level which should be applicable to curricula in computer science, engineering, and operations research areas. The book is an ambitious undertaking, as it deals with the entire field of applied combinatorics. The author succeeds in producing a text which is rigorous and yet clear at the senior-graduate level. Therve is a proliferation of examples and applications, especially in the first four chapters. For use as a text, there are numerous problems given at the end of every chapter. The reviewer's primary objection is that the author does not assume a more algorithmic point of view. The author should present the concept of an efficient or "good" algorithm for the solution of a given combinatorial problem. If such an algorithm does not exist for a given problem, then the author should indicate the problem is open or unsolved. Chapters 1-5 deal with enumerative analysis-permutations and combin- ations, generating functions, recurrence relations, the principle of inclusion and exclusion, and Polya's theorem. An informal treatment characterizes the first four chapters, where the exposition is rather by example. Good explanations are given for the rationale behind combinatorial manipulations, and often several alternative methods are considered. Chapters 6-9 introduce basic concepts from graph theory. The presentation is mathematically formal, but well explained, and generally accompanied by a number of examples. However, in Chapter 7 which discusses trees, circuits, and cut-sets, the author develops these concepts from graph theory to the point of identifying an appropriate vector space. The author explains this very well, but Chapter 7 fails to provide an example of the application of these ideas, which are obviously very important. Chapters 10-13 deal with network flow theory, matching theory, linear and dynamic programming. Generally the theory behind each of these techniques is well explained and accompanied by many examples, providing a clear and well- motivated presentation. It is unfortunate that there is no mention of integer programming, in spite of its importance in the field of applied combinatorics. The concept of duality is only mentioned peripherally with respect to linear programming. By contrast, the reviewer feels an early and complete discussion of duality theory would have lent an essential ingredient to network flows and matching theory, as well as a sense of unity to this portion of the book. This content downloaded from 194.29.185.216 on Sun, 15 Jun 2014 06:57:55 AM All use subject to JSTOR Terms and Conditions http://www.jstor.org/page/info/about/policies/terms.jsp Article Contents p. 633 p. 634 Issue Table of Contents SIAM Review, Vol. 11, No. 4 (Oct., 1969), pp. 429-672 Volume Information [pp. ] Front Matter [pp. ] Mathematics and Psychology [pp. 429-469] Optimal Continuous-Parameter Stochastic Control [pp. 470-509] An Introduction to Lie Groups and Lie Algebras, with Applications. III: Computational Methods and Applications of Representation Theory [pp. 510-543] Complex Gaussian Processes [pp. 544-567] Range Decomposition and Generalized Inverse of Nonnegative Hermitian Matrices [pp. 568-571] Bounds on the Solution of the Lagged Optimal Inventory Equation with no Demand Backlogging and Proportional Costs [pp. 572-596] Further Relations Between Game Theory and Eigensystems [pp. 597-602] Short Notes: An Expression for the Dirac Delta Function. I [pp. 603] Short Notes: Stochastic Games With Perfect Information and Time Average Payoff [pp. 604-607] Short Notes: A Method of Solving Wave Propagation Problems in Bounded Anisotropic Media [pp. 608-611] Short Notes: On the Construction of Solutions to the Matrix Equations AX = A and YA = A [pp. 612-615] Short Notes: Solution of Ill-Conditioned Linear Two-Point Boundary Value Problems by the Riccati Transformation [pp. 616-619] Problems Problem 69-11, Ohmic Heating [pp. 620] Problem 69-12, An Elliptic Integral [pp. 620] Problem 69-13, A Polynomial with Proscribed Properties [pp. 620] Problem 69-14, Sum of Inverse Powers of Cosines [pp. 621] Problem 69-15, Existence of Binary Sequences with Prescribed Properties [pp. 621-622] Solutions Problem 66-12 [pp. 622] Problem 68-3 [pp. 622] Problem 68-6 [pp. 622-624] Problem 68 [pp. 624-625] Problem 68-8 [pp. 625-628] Problem 68-10 [pp. 628-630] Problem 68-12 [pp. 630-632] Problem 68-13 [pp. 632] Book Reviews Review: untitled [pp. 633-634] Review: untitled [pp. 634-635] Review: untitled [pp. 635-638] Other Books Received [pp. 638-640] Chronicle [pp. 641-672] Back Matter [pp. ]