Robert G. Gallager - Principles of Digital Communication

This book has evolved from lecture notes for a one-semester course on digital communication given at MIT for the past ten years. I am particularly grateful for the feedback I have received from the other faculty members, namely Professors Amos Lapidoth, Dave Forney, Greg Wornell, and Lizhong Zheng, who have used these notes in the MIT course. Their comments, on both tutorial and technical aspects, have been critically helpful. The notes in the early years were written jointly with Amos Lapidoth and Dave Forney. The notes have been rewritten and edited countless times since then, but I am very grateful for their ideas and wording, which, even after many modifications, have been an enormous help. I am doubly indebted to Dave Forney for reading the entire text a number of times and saving me from many errors, ranging from conceptual to grammatical and stylistic.

I am indebted to a number of others, including Randy Berry, Sanjoy Mitter, Baris Nakiboglu, Emre Telatar, David Tse, Edmund Yeh, and some anonymous reviewers for important help with both content and tutorial presentation.

Emre Koksal, Tengo Saengudomlert, Shan-Yuan Ho, Manish Bhardwaj, Ashish Khisti, Etty Lee, and Emmanuel Abbe have all made major contributions to the text as teaching assistants for the MIT course. They have not only suggested new exercises and prepared solutions for others, but have also given me many insights about why certain material is difficult for some students, and suggested how to explain it better to avoid this confusion. The final test for clarity, of course, comes from the three or four hundred students who have taken the course over the last ten years, and I am grateful to them for looking puzzled when my explanations have failed and asking questions when I have been almost successful.

Finally, I am particularly grateful to my wife, Marie, for making our life a delight, even during the worst moments of writing yet another book.

Communication has been one of the deepest needs of the human race throughout recorded history. It is essential to forming social unions, to educating the young, and to expressing a myriad of emotions and needs. Good communication is central to a civilized society.

The various communication disciplines in engineering have the purpose of providing technological aids to human communication. One could view the smoke signals and drum rolls of primitive societies as being technological aids to communication, but communication technology as we view it today became important with telegraphy, then telephony, then video, then computer communication, and today the amazing mixture of all of these in inexpensive, small portable devices.

Initially these technologies were developed as separate networks and were viewed as having little in common. As these networks grew, however, the fact that all parts of a given network had to work together, coupled with the fact that different components were developed at different times using different design methodologies, caused an increased focus on the underlying principles and architectural understanding required for continued system evolution.

This need for basic principles was probably best understood at American Telephone and Telegraph (AT&T), where Bell Laboratories was created as the research and development arm of AT&T. The Math Center at Bell Labs became the predominant center for communication research in the world, and held that position until quite recently. The central core of the principles of communication technology were developed at that center.

Perhaps the greatest contribution from the Math Center was the creation of Information Theory [27] by Claude Shannon (Shannon, 1948). For perhaps the first 25 years of its existence, Information Theory was regarded as a beautiful theory but not as a central guide to the architecture and design of communication systems. After that time, however, both the device technology and the engineering understanding of the theory were sufficient to enable system development to follow information theoretic principles.

A number of information theoretic ideas and how they affect communication system design will be explained carefully in subsequent chapters. One pair of ideas, however, is central to almost every topic. The first is to view all communication sources, e.g., speech waveforms, image waveforms, and text files, as being representable by binary sequences. The second is to design communication systems that first convert the source output into a binary sequence and then convert that binary sequence into a form suitable for transmission over particular physical media such as cable, twisted wire pair, optical fiber, or electromagnetic radiation through space.

Figure 1.1. Placing a binary interface between source and channel. The source encoder converts the source output to a binary sequence and the channel encoder (often called a modulator) processes the binary sequence for transmission over the channel. The channel decoder (demodulator) recreates the incoming binary sequence (hopefully reliably), and the source decoder recreates the source output.

Digital communication systems, by definition, are communication systems that use such a digital).

The idea of converting an analog source output to a binary sequence was quite revolutionary in 1948, and the notion that this should be done before channel processing was even more revolutionary. Today, with digital cameras, digital video, digital voice, etc., the idea of digitizing any kind of source is commonplace even among the most technophobic. The notion of a binary interface before channel transmission is almost as commonplace. For example, we all refer to the speed of our Internet connection in bits per second.

There are a number of reasons why communication systems now usually contain a binary interface between source and channel (i.e., why digital communication systems are now standard). These will be explained with the necessary qualifications later, but briefly they are as follows.

Digital hardware has become so cheap, reliable, and miniaturized that digital interfaces are eminently practical.

A standardized binary interface between source and channel simplifies implementation and understanding, since source coding/decoding can be done independently of the channel, and, similarly, channel coding/decoding can be done independently of the source.

A standardized binary interface between source and channel simplifies networking, which now reduces to sending binary sequences through the network.

One of the most important of Shannons information theoretic results is that if a source can be transmitted over a channel in any way at all, it can be transmitted using a binary interface between source and channel. This is known as the source/channel separation theorem.

In the remainder of this chapter, the problems of source coding and decoding and channel coding and decoding are briefly introduced. First, however, the notion of layering in a communication system is introduced. One particularly important example of layering was introduced in , where source coding and decoding are viewed as one layer and channel coding and decoding are viewed as another layer.

Large communication systems such as the Public Switched Telephone Network (PSTN) and the Internet have incredible complexity, made up of an enormous variety of equipment made by different manufacturers at different times following different design principles. Such complex networks need to be based on some simple architectural principles in order to be understood, managed, and maintained. Two such fundamental architectural principles are