1
Introduction

Prologue

How does one transmit information when bandwidth is expensive? One can explore new wavelengths. One can use multiple antennas to distinguish more pathways. One can design better modulation and coding for each pathway. This book is about the last.

According to the laws of nature, sending bits of information via an electrical medium requires two main resources: energy and bandwidth. Each bit needs energy, and just as in soccer football, a certain energy is needed to hit the ball far enough. Adding bandwidth to football needs new rules. Suppose every player has a ball and all must pass through a narrow passage on the way to the goal. How difficult is it to reach the goal?

Electrical communication is a game too, played according to nature's laws. In the first half of the twentieth century, several of these became clear. First, much less energy is needed per bit if the signal bandwidth is widened. Second, a certain type of energy pulse, called "orthogonal," is easier to process. These facts were well established in 1949 when Claude Shannon published something different, a formula for the ultimate capacity of a set bandwidth and energy to carry information. The key to approaching that limit is coding, that is, imposing clever patterns on the signals. As much as 90% of signal energy can be saved compared to rudimentary methods, or the information can be sent much further. In principle, whatever configuration of energy and bandwidth was available, it could be coded.

Nonetheless, those who designed codes in the following decades thought of them, consciously or not, as trading more bandwidth for less energy. Even with a simple trade, a signal could travel much further if its bandwidth were scaled up. In this way-and only this way-signals reached Mars and even Pluto. Neither was crowded with players, so that wide bandwidth signals were practical. There will soon be rovers from several nations on Mars, so that allotting wide bandwidth to each is not quite so practical. Here on Earth the situation is more desperate. Such services as cellular wireless and digital video must share a very crowded spectrum; furthermore, governments have discovered they can force providers to pay astonishing prices for bandwidth. Today, bandwidth costs far more than energy. Everyone needs to minimize it.

In the 1970s, methods of signal coding were discovered that did not increase bandwidth; signals could travel farther and easier without scaling up bandwidth. This was clear in Shannon's 1949 formula from the first day, but the concepts took time to sink in. What his formula really says is that coding leads to large savings no matter what the combination of energy and bandwidth. Today, with bandwidth costly, we want to work at narrow bandwidth and higher energy, not the reverse. The problem is: We know little about how to design the coding. The purpose of this book is to take that next step. How should efficient signal coding work when very narrow bandwidths per bit are available?

1.1 Electrical Communication

This chapter introduces important and potentially troublesome concepts in a mostly philosophical way. Among them are bandwidth and time, pulse shapes, modulation, and coding. The needed formal communication background is Chapter 2, and Shannon's theory appears in Chapter 3. Certain concepts need some evolution to fit modern needs. The outcome of the book is that practical coding schemes exist that work well in a very narrowband world.

Communication transmits messages through time and space. In this book, the medium is electrical signals, and we will restrict ourselves to radio. For our purposes, messages are composed of symbols, and we want to transmit these accurately and efficiently through the physical world. In communication engineering, sending a symbol has three basic costs, energy, bandwidth, and implementation complexity. Each trades off against the others. Once the three costs are set the measure of good performance is most often probability of symbol error.

Even a century ago, it was clear enough that error may be reduced by spending more energy. A basic fact of communication, that first became evident with FM broadcasting, is that for the same performance, energy may be traded for bandwidth. Error-correcting codes, as first used, were thought of as a manifestation of this fact: By transmitting extra check bits, energy could be saved overall. But Claude Shannon's 1949 work [7] implied that energy or bandwidth or both could be reduced while maintaining the same error performance. Each combination of energy and bandwidth had a certain capacity to carry symbols but alas, there was no free lunch, and rapidly diverging "coding" complexity is required to approach this capacity. Today, energy, bandwidth, and complexity are a three-way trade-off.

Since 1949 there have been 60 years of progress and a rich research literature, but coding and its attendant complexity have been associated mainly with relatively low energy and wide bandwidth on a per data bit basis. Economic necessity and some changes in physical transmission paths are forcing changes in that thinking. Two examples are wireless networks and satellite digital broadcasting. Successive mobile network generations have offered more bits per second to their customers and the upcoming fifth Generation Systems will employ a variety of methods to offer even more. Among them are better antennas and shorter paths, both of which increase the symbol energy, making possible narrower bandwidth. According to theory, there is just as much to gain from coding and complexity in this narrowband/high-energy regime as we have enjoyed in wider band applications.

We move now to fundamental concepts and a sketch of the book. Knowledge of history helps make sense of a subject, and so we offer some high points, together with some important published works. The prerequisites for the book are first courses in probability, Shannon theory, signal space theory, and coding methods of the traditional type. Our own treatment of these subjects will be to extend their results to the new narrowband field.

Bandwidth and Coding. Coding, bandwidth, and their interaction lie at the heart of this book.

Coding theory is built upon abstract models, nonphysical concepts such as channel models, information, symbols, and arithmetic operations. Although it is not necessary to its mathematics, the theory can suggest physical conclusions by starting with signals and symbols that are avatars to physical channels and transmissions. In this book, the physical channel is always the white noise linear channel, wherein a white noise stochastic process with a certain power spectrum N0/2 watts/Hz (the noise) adds to a analog function of time (the signal). Something is needed to convert abstract symbols to the analog domain; this is a modulator. This last is explored in Section 1.2. A modulator-demodulator by itself has a certain probability of error. The import of Shannon's work is that another two boxes, the encoder-decoder, can be added that can in principle reduce the error rate virtually to zero, provided that the energy-bandwidth combination is sufficient. The distinction between coding and modulation is a tricky one, taken up initially in Section 1.4, and the Shannon theory tools we need are in Chapter 3. That chapter starts from the core result in the 1949 paper, which is the capacity of the additive white Gaussian noise (AWGN) channel. In this channel, an independent Gaussian-distributed noise value with mean zero and variance N0/2 is added to a real signal value. Initially, there were no analog signals; part of Shannon's genius was making the critical jump from the abstract AWGN channel to the channel with analog signals and bandwidth that we need in this book.

While it is true that the promise of narrow band/high-energy coding was already clear in 1949, we have spent most of the time since then developing techniques in the opposite regime. During its first 25 years, coded communication was primarily about parity-check codes and the binary symmetric channel. Codewords contained extra "redundant" bits, there being no other way to distinguish codeword bits from customer bits. With such codes nearly universal, one could easily fall into the belief that coding mostly exchanged extra bits (i.e., bandwidth) for coding gain (reduced energy). With the advent of coded modulation in the mid 1970s, cracks appeared in this belief. New transmission methods such as continuous-phase modulation (CPM) and set-partition coding appeared, which reduced energy without bandwidth expansion, and sometimes did this without redundant bits. By the late 1970s, it was clear that codes could even be used to reduce bandwidth, or even bandwidth and energy both.1 These new methods eventually broke through the coding equals bandwidth-expansion belief, and doubled or tripled the rate of coded communication in a given bandwidth. Today, we would like to double or triple it once more.

More changed in the 1970s and 1980s than the bandwidth/energy regime. If coding was not redundant bits, then what was it? If CPM, which seemed to be modulation, and convolutional codes both required a trellis decoder of similar size, then were they not both coding schemes? Set-partition codes contained a convolutional code within them; was that the code, or was something else? Should removal of intersymbol interference (ISI) be called decoding? It became clear that coding needed more careful definition if there...