1
Introduction

"Information is the resolution of uncertainty."

- Claude Shannon

Reliable communication over noisy channels is a cornerstone of modern information systems, and channel coding serves as a critical mechanism to achieve this reliability. This chapter provides the foundational knowledge necessary to understand the role of channel coding in communication systems, setting the stage for the rest of the book.

We begin by exploring the need for channel coding in ensuring reliable transmission over noisy channels and by reviewing the structure of a generic communication system. This is followed by a discussion of various channel models, including the binary symmetric channel (BSC), binary erasure channel (BEC), additive white Gaussian noise (AWGN) channel, and fading channel. These models illustrate the diverse challenges posed by different communication environments.

The fundamentals of information theory are introduced next, focusing on key concepts such as the meaning of information, discrete entropy, its properties, and mutual information. The Bhattacharyya parameter, a measure of channel reliability, is also explained to provide deeper insights into channel characteristics.

The chapter culminates with an in-depth discussion of channel capacity and the celebrated Shannon Channel Coding Theorem, which defines the theoretical limits of reliable communication. Additional topics include the block error rate for finite-length codes, the Shannon limit on power efficiency, and the computational complexity associated with coding and decoding processes.

By the end of this chapter, readers will have a comprehensive understanding of the role of channel coding in communication systems, the differences between channel models, the fundamentals of information theory, and the principles underpinning the channel coding theorem. This foundational knowledge will enable readers to appreciate the critical role of coding theory in modern communication systems and serve as a basis for exploring advanced topics in the chapters that follow.

1.1 Reliable Transmission over Noisy Channels

Digital communications and storage are essential parts of our modern lives. We rely on them for everything from sending emails to streaming videos. However, these systems are susceptible to errors that can corrupt the data and make them unusable.

Errors in data transmission and storage systems can be caused by a variety of factors, including:

• Random noise: This is caused by the inherent randomness of the physical world, such as the thermal noise of electronic devices.
• Interference: This is caused by other signals that are present in the same transmission medium, such as radio waves or electromagnetic radiation.
• Channel fading: This is caused by changes in the properties of the transmission medium, such as the attenuation of radio waves due to obstacles or the variation of the refractive index of the atmosphere.
• Physical defects: These are caused by imperfections in the physical components of the data transmission or storage system, such as scratches on a disc or defects in a memory chip.

There are two main strategies for combating errors in digital communications and storage: automatic repeat request (ARQ) and forward error correction (FEC). ARQ systems detect errors in the received data and request that the data be resent. This is a simple and effective way to ensure reliable data transmission, but it can also lead to increased latency and bandwidth usage. FEC systems, on the other hand, not only detect but also correct errors in the received data. FEC systems can achieve higher reliability than ARQ systems with lower latency, but they are also more computationally expensive. The choice of which error control strategy to use depends on the specific application. For example, FEC is often used in real-time applications where retransmission is not possible, such as live streaming. ARQ is often used in applications where latency is less important than channel bandwidth, such as file transfer over a network. In this book, our focus is on FEC, which is the subject of coding theory.

Coding theory originated in the late 1940s with the work of Claude Shannon, Marcel Golay, and Richard Hamming. Shannon's landmark paper A Mathematical Theory of Communication in 1948 laid the foundations for both information theory and coding theory. He introduced the concept of channel capacity, which is the maximum rate at which information can be transmitted over a noisy channel without errors. He also showed that arbitrarily reliable communication is possible at any rate below the channel capacity.

One way to achieve reliable communication is to use error-correcting codes. These codes add redundant bits to the data being transmitted, which can be used to detect and correct errors that occur during transmission. Hamming developed a simple but effective error-correcting code in 1947. His code is now known as the Hamming code. Other examples of communication channels include wireless communication devices and storage systems such as digital video disc (DVD)s and Blu-ray discs. Coding theory is essential for ensuring reliable communication over these channels.

Figure 1.1 illustrates a simple communication channel, ignoring the modulation and demodulation stage for the sake of simplicity. At the source of the communication (transmitter), a message represented as is intended to be transmitted. However, if this message is sent directly through the channel without any modifications, the presence of noise could distort to the extent that its accurate recovery becomes unfeasible. The fundamental concept of coding theory revolves around enhancing the message's resilience by introducing redundancy. This additional information aims to enable the recovery of the original message even in the face of noise-induced corruption during transmission. The process of adding redundancy occurs at the encoder stage, resulting in an augmented message known as a codeword, illustrated as in the figure. This codeword is then transmitted through the channel, where noise, represented as an error vector , distorts the codeword, leading to the formation of a received vector .

Subsequently, the received vector undergoes decoding, where the errors are rectified. The surplus redundancy is removed, yielding an estimation of the original message. Ideally, matches , ensuring successful recovery. Notably, there exists a direct correspondence between codewords and messages. In many instances, the primary focus shifts from the message to the codeword . From this perspective, the decoder's task involves deriving an estimate from with the hope that aligns with .

In the case of a DVD or Blu-ray disc, the message source encompasses audio, music, video, or data intended for storage on the disc. The disc itself serves as the communication channel, the DVD or Blu-ray player operates as the decoder, and the recipients consist of listeners or viewers. By refining the communication process through the introduction of redundancy and error correction, coding theory plays a vital role in maintaining the integrity of transmitted information across various contexts and communication channels.

Figure 1.1 Error correction coding over a noisy channel.

The implementation of error correction comes at a cost. The introduced redundancy functions as an additional layer that consumes transmission resources, such as channel bandwidth or transmission power. Consequently, our objective is to minimize this overhead by minimizing the required redundancy.

To quantitatively assess the amount of redundancy, we introduce the concept of coding rate, denoted as . This rate is defined as the ratio between the length of the original message and the length of the resulting codeword. For example, if a specific coding scheme produces a codeword of length from a message of length , the coding rate can be expressed as:

In this context, the coding rate reaches its highest value of 1 when no redundancy is incorporated, which basically leaves the message uncoded. The trade-off between coding performance and coding rate is pivotal. With the inclusion of more redundancy, the capability to correct errors becomes more robust, yet this comes at the expense of a reduced coding rate.

An optimal code strives to strike a balance between these factors. It aims to maximize the error correction capability while maintaining the coding rate as close to 1 as possible. This equilibrium ensures that transmission remains efficient in terms of resource utilization while effectively combating the detrimental effects of noise and errors during communication.

So far, we have established some understanding of the advantages offered by channel coding. Next, we discuss some common models for the channels, and in Section 1.4, we delve into the theoretical limit for code rate to have reliable communication.

1.2 Channel Models

There exits various channel models that are used for different applications depending on the specific characteristics of the communication channel and the requirements of the application. In the following, we review the major channel models.

1.2.1 Binary Symmetric Channel (BSC)

The BSC is a discrete memoryless channel (DMC) that has two binary symbols as inputs and outputs: 0 and 1. It is symmetric because the probability of receiving a 0 when a 1 is transmitted is the same as the probability of receiving a 1 when a 0 is...