Andrew J. Viterbi - Principles of Digital Communication and Coding

PRINCIPLES OF DIGITAL
COMMUNICATION
AND CODING Andrew J. Viterbi Viterbi Group and University of Southern California Jim K. Omura The Gordon and Betty Moore Foundation DOVER PUBLICATIONS, INC. Mineola, New York Copyright Copyright 1979 by Andrew J. Viterbi and Jim K. Bibliographical Note This Dover edition, first published in 2009, is an unabridged republication of the work originally published by McGraw-Hill Book Company, New York, in 1979. Bibliographical Note This Dover edition, first published in 2009, is an unabridged republication of the work originally published by McGraw-Hill Book Company, New York, in 1979.

You can find a complete electronic version of the solutions manual on line at: http://www.archive.org/stream/princeofdigcomco00viterich/princeofdigcomco00viterich-djvu.txt International Standard Book Number
ISBN-13: 978-0-486-46901-0
ISBN-10: 0-486-46901-8 Manufactured in the United States of America Dover Publications, Inc., 31 East 2nd Street, Mineola, N.Y. 11501 CONTENTS May be omitted without loss of continuity. PREFACE TO THE DOVER EDITION Since this book was first published in 1979, there has been an almost complete worldwide transition to digital communication systems. The basic principles presented in this book still apply today; only now they are actually used in products that are embedded in our everyday lives. This transition to todays digital world was made possible by the continuous advancement of digital processing at the rate of Moores Law during the past forty years. At a worldwide systems level, the digital communications revolution since 1978 has been accelerated by the rapid expansion of high-speed worldwide fiber optic networks in the 1990s.

This coincided with the introduction of the browser, which kicked off the transition of the Internet from being mostly an e-mail system to the information network it is today. The Internet continues to evolve with social networking applications and is changing many traditional business models. Television and audio broadcast has also made this transition to digital. Most homes in the United States now have High Definition Television (HDTV) delivered by satellites, cable, and terrestrial broadcast. Digital satellite audio broadcast is now common in automobiles and digital AM and FM broadcast stations are replacing traditional analog systems. Another major change since 1978 has been the digital wireless networks that allow users to connect to the Internet and phone networks from almost anywhere.

Internet access using Wi-Fi had its origins in the FCC Part 15 ruling in 1985, which allowed unlicensed use of spread spectrum radios in the ISM bands. The cellular phone systems have gone through dramatic shifts from analog systems to todays digital systems that incorporate many of the concepts presented in this book beginning with the Code Division Multiple Access (CDMA) cellular system developed by Qualcomm, a company cofounded by Andrew Viterbi. In addition to voice communication, mobile phones today include Internet access, text messaging, Global Positioning System (GPS) based location services, digital cameras, and much more. Currently there are approximately three billion mobile phones in use worldwide. The digital revolution continues to change our world in ways we could not have imagined. PREFACE Digital communication is a much used term with many shades of meaning, widely varying and strongly dependent on the users role and requirements.

This book is directed to the communication theory student and to the designer of the channel, link, terminal, modem, or network used to transmit and receive digital messages. Within this community, digital communication theory has come to signify the body of knowledge and techniques which deal with the two-faceted problem of (1) minimizing the number of bits which must be transmitted over the communication channel so as to provide a given printed, audio, or visual record within a predetermined fidelity requirement (called source coding); and (2) ensuring that bits transmitted over the channel are received correctly despite the effects of interference of various types and origins (called channel coding). The foundations of the theory which provides the solution to this twofold problem were laid by Claude Shannon in one remarkable series of papers in 1948. In the intervening decades, the evolution and application of this so-called information theory have had ever-expanding influence on the practical implementation of digital communication systems, although their widespread application has required the evolution of electronic-device and system technology to a point which was hardly conceivable in 1948. This progress was accelerated by the development of the large-scale integrated-circuit building block and the economic incentive of communication satellite applications. We have not attempted in this book to cover peripheral topics related to digital communication theory when they involve a major deviation from the basic concepts and techniques which lead to the solution of this fundamental problem.

For this reason, constructive algebraic techniques, though valuable for developing code structures and important theoretical results of broad interest, are specifically avoided in this book. Similarly, the peripheral, though practically important, problems of carrier phase and frequency tracking, and time synchronization are not treated here. These have been covered adequately elsewhere. On the other hand, the equally practical subject of intersymbol interference in digital communication, which is fundamentally similar to the problem of convolutional coding, is covered and new insights are developed through connections with the mainstream topics of the text. This book was developed over approximately a dozen years of teaching a sequence of graduate courses at the University of California, Los Angeles, and later at the University of California, San Diego, with partial notes being distributed over the past few years. Our goal in the resulting manuscript has been to provide the most direct routes to achieve an understanding of this field for a variety of goals and needs.

All readers require some fundamental background in probability and random processes and preferably their application to communication problems; one years exposure to any of a variety of engineering or mathematics courses provides this background and the resulting maturity required to start. Given this preliminary knowledge, there are numerous approaches to utilization of this text to achieve various individual goals, as illustrated graphically by the prerequisite structure of . Figure P.1 Organisation and prequisite structure The applications-oriented engineer or student can obtain an understanding of channel coding for physical channels by tackling only . Avoiding the intricacies of ensemble-average arguments, the reader can learn how to code for noisy channels without making the additional effort to understand the complete theory. At the opposite extreme, students with some background in digital communications can be guided through the channel-coding material in on source coding in a course of similar duration. Numerous problems are provided to furnish examples, to expand on the material or indicate related results, and occasionally to guide the reader through the steps of lengthy alternate proofs and derivations.

Aside from the obvious dependence of any course in this field on Shannons work, two important textbooks have had notable effect on the development and organization of this book. These are Wozencraft and Jacobs [1965], which first emphasized the physical characteristics of digital communication channels as a basis for the development of coding theory fundamentals, and Gallager [1968], which is the most complete and expert treatment of this field to date. Collaboration with numerous university colleagues and students helped establish the framework for this book. But the academic viewpoint has been tempered in the book by the authors extensive involvement with industrial applications. A particularly strong influence has been the close association of the first author with the design team at LINKABIT Corporation, led by I. Jacobs, J. A. Heller, A. R. R.