NIS2337 Information Theory Notes (2): Channel and Channel Capacity

The concept and properties of channels, and channel capacity.

NIS2337 Foundations of Information Theory course notes — other chapters: 1. Source and Information Entropy 2. Channel and Channel Capacity (this article) 3. Rate-Distortion Function 4. Source Coding 5. Channel Coding

Some supplementary materials can be found in Beyond 2337.

Basic Concepts of Channels

Mathematical Model of a Channel

• Channel input: , where
• Channel output: , where

The dependence between input and output is usually described by the conditional probability (transition probability) .

Noiseless Channel

; knowing the input uniquely determines the output .

Discrete Memoryless Channel with Interference

There is no deterministic relationship between channel output and input, but the transition probability satisfies . This simplifies the problem: it suffices to analyze the single-symbol transition probability .

Binary Symmetric Channel

The Binary Symmetric Channel (BSC) is the simplest discrete memoryless channel model, where both input and output are binary symbols.

• Channel input:
• Channel output:

Here, , i.e., the error probability; . The transition probability matrix is readily obtained as:

Discrete Memoryless Channel

A Discrete Memoryless Channel (DMC) refers to a memoryless channel whose input and output alphabets each have more than two symbols but are finite. The BSC is a special case of the DMC.

• Channel input: ;
• Channel output: .

The transition probability matrix is readily obtained as:

where, from the normalization condition of probabilities, .

Discrete-Input, Continuous-Output Channels

Suppose the channel input symbols are chosen from a finite discrete input alphabet, while the channel output is unquantized and can take any value on the real axis. Such a channel is defined as a discrete-time memoryless channel. Its characteristics are described by the discrete input , the continuous output , and a family of conditional probability density functions .

The most important channel of this type is the Additive White Gaussian Noise Channel (AWGN), whose mathematical expression is , where is white Gaussian noise satisfying . When is given, .

Waveform Channels

When both the input and output of a channel are random processes and , the channel is called a waveform channel. Real-world channels are all waveform channels.

We cannot directly perform probabilistic analysis on continuous-time channels. However, under practical conditions the channel bandwidth is limited, so within a finite sampling interval , the stationary random process channel can be discretized into time-discrete, stationary random sequences and , thereby converting the waveform channel into a multi-dimensional continuous channel.

The channel transition probability density function is:

The normalization condition is:

A continuous memoryless channel is a multi-dimensional continuous channel that satisfies , meaning the output variable at any given time depends only on the corresponding input variable and is independent of past inputs and outputs. If this condition is not satisfied, it is called a continuous channel with memory.

Based on how noise affects the signal in the channel, noise can be divided into two types: additive and multiplicative, i.e., noise is added to or multiplied with the input signal. We focus on single-symbol channels with additive noise, . Since is independent of :

The channel transition probability density function equals the probability density function of the noise. Now consider the conditional entropy , also called the noise entropy:

In a multi-dimensional continuous additive channel, . Similarly, and .

Definition of Channel Capacity

Information Transmission Rate per Symbol. The information transmission rate of a channel is defined as the amount of information transmitted per symbol on average:

Information Transmission Rate per Unit Time. Let be the average transmission time per symbol; define the information transmission rate per unit time as:

Channel Capacity. is a function of the input symbol probability distribution and the channel transition probabilities . For a given channel, is fixed, and is a convex-cap function of . Therefore, one can find a probability distribution that maximizes . This maximum value is the channel capacity:

If the symbol transmission period is , the channel capacity per unit time is .

For a fixed-parameter channel, the channel capacity is a constant. Whether the maximum transmission capability can be achieved in practice depends on the probability distribution at the input. For time-varying channel parameters, the channel characteristics change over time and cannot be represented by a fixed value. In such cases, average capacity and outage capacity are commonly used.

Redundancy. Absolute channel redundancy: ; relative redundancy:

Discrete Single-Symbol Channels and Their Capacity

Noiseless Discrete Channels

Assume channel input and channel output .

• Noiseless and Lossless Channel: and are in one-to-one correspondence, as shown in the figure above. In this case, the conditional probability matrix is the identity matrix, so and . When the input symbols are equally likely, is maximized:

• Noiseless but Lossy Channel: Multiple inputs map to a single output, as shown in the figure above. Under this condition, the noise entropy , but the equivocation . Consequently, .

• Noisy but Lossless Channel: A single input maps to multiple outputs. Under this condition, the equivocation , but the noise entropy . Consequently, .

Symmetric Discrete Memoryless Channels

The simplest type of DMC is the symmetric channel. For a transition probability matrix : - If every row is a permutation of the first row, the matrix is said to be input-symmetric; - If every column is a permutation of the first column, the matrix is said to be output-symmetric; - If it is both input-symmetric and output-symmetric, the matrix is said to be input-output symmetric, and the corresponding channel is called a symmetric DMC channel.

Due to symmetry:

That is, the conditional entropy of a symmetric discrete memoryless channel is independent of the input probability distribution of the source.

If the input symbols are equally likely, i.e., , then (equally likely), and attains its maximum value .

Discrete memoryless additive modulo- channel, as shown in the figure below. The input symbol set and output symbol set of this channel are both residue classes modulo , and they satisfy , where is a noise variable independent of and follows some probability distribution.

Thus, for this channel, we have:

Quasi-Symmetric Discrete Memoryless Channels

A quasi-symmetric discrete memoryless channel is a discrete memoryless channel whose transition probability matrix is input-symmetric but not output-symmetric. Since it is input-symmetric, still holds. Because the columns contain different elements, the input and output probability distributions may differ, so .

Matrix Decomposition Method. When the transition matrix can be decomposed into several symmetric sub-matrices, it can be shown that channel capacity is achieved when the input is uniformly distributed:

where is the number of input symbols, are the elements of one row, is the sum of row elements in the -th sub-matrix, is the sum of column elements in the -th sub-matrix, and is the number of sub-matrices.

General Discrete Memoryless Channels

Blahut-Arimoto Algorithm. The necessary and sufficient conditions (KKT conditions) for maximizing with respect to the input symbol probability set are: - For all , - For all ,

where .

That is, if a symbol provides more than the average mutual information about , we can more fully utilize this symbol (increase its probability of occurrence) to increase . However, doing so also changes the input distribution, reducing the average mutual information of that symbol while increasing that of other symbols. Through continuous adjustment, the outcome is that each symbol that actually occurs eventually provides the same amount of average mutual information.

The algorithm only establishes the existence of but does not provide a specific path to approach this limit. Moreover, the optimal distribution may not be unique; it need only satisfy the above conditions.

Discrete Sequence Channels and Their Capacity

• Input symbol sequence:
• Output symbol sequence:

The transition probability of a memoryless discrete sequence channel depends only on the current input. That is:

If the channel is stationary, then .

• If the channel is memoryless, then
• If the input vector components are independent, then

If the input components are independent and the channel is memoryless, the above two properties become equalities. When the input vector achieves the optimal distribution, the channel capacity is maximized:

When the channel is stationary, .

If channels are connected in parallel, with each channel output depending only on its corresponding input , we have:

Only when the input vector components are mutually independent and the channel is memoryless do we have .

Continuous Channels and Their Capacity

Continuous Single-Symbol Additive Channel

The most common continuous channel is the continuous single-symbol channel with continuous amplitude, as shown in the figure above. Both the input and output are one-dimensional random variables taking continuous values, with additive noise , i.e., . From the definition of differential entropy, the noise entropy can be computed as .

To maximize , must be Gaussian. Since and the noise power is , with the average power of the input signal being , the total power of is . When the channel input is Gaussian with zero mean and variance , the information transmission rate is maximized:

Here, is the average power of the input signal and is the average power of the noise. Therefore, we can define the signal-to-noise ratio , and the above formula simplifies to:

As mentioned in the previous section, the reason for focusing on Gaussian noise in channel analysis is that, under the constraint of average power limitation, the Gaussian distribution has the highest entropy. It is therefore commonly used as a worst-case noise model. Thus, for additive noise channels with non-Gaussian noise, the upper and lower bounds of channel capacity are:

Multi-Dimensional Memoryless Additive Continuous Channel

The mathematical model of a multi-dimensional memoryless additive continuous channel is shown in the figure above. Both the input and output are -dimensional random vectors taking continuous values, with -dimensional additive noise , i.e., .

Since the components are all statistically independent, a multi-dimensional memoryless Gaussian additive continuous channel is equivalent to one-dimensional memoryless Gaussian additive continuous channels in parallel. Let the input power of the -th one-dimensional channel be and the noise power be ; then the capacity of the -th one-dimensional channel is . Therefore, the capacity of the multi-dimensional memoryless additive continuous channel is:

If the total signal power is constrained by , how should power be allocated across channels to maximize channel capacity? Using the Lagrange multiplier method, capacity is maximized when (a constant), where . In this case, the channel capacity is . If is too large (greater than ), then the allocated power is , and power is reallocated among the remaining channels. This is known as the water-filling algorithm.

It follows that sub-channels with lower noise receive larger input power, typically have higher SNR, exhibit stronger noise immunity, can transmit more bits, and require higher-order modulation schemes to improve bandwidth efficiency.

Band-Limited, Time-Limited, and Power-Limited Additive White Gaussian Noise Channel

By the sampling theorem, under time-limited and band-limited conditions, the input process and output process of a waveform channel can be transformed into a multi-dimensional continuous channel for analysis via and .

Assume the power spectral density of the additive white Gaussian noise is , and the low-pass band-limited system has frequency bandwidth . Therefore, the average noise power is . Based on the capacity formula for the multi-dimensional memoryless additive continuous channel from the previous section, the capacity of a time-limited and band-limited AWGN channel with bandwidth is:

where is the noise power per dimension, and is the input power allocated per dimension. Assuming the average signal power per dimension is limited to , substituting these parameters into the capacity formula yields:

In the above expression, represents the average signal power, and represents the average noise power within bandwidth . Therefore, is the signal-to-noise ratio . This is Shannon’s formula.

Since Gaussian noise is the worst-case noise model, the channel capacity given by Shannon’s formula is the lower bound on the capacity of all additive noise channels with bandwidth and signal-to-noise ratio .

Source-Channel Matching

Source-channel matching is reflected in two main aspects: symbol matching and information matching. - Symbol matching requires that the symbols emitted by the source must be symbols that the channel can transmit, i.e., the source alphabet is a subset of the channel input alphabet; - Information matching requires that the information transmission rate of the source must be less than or equal to the channel capacity, i.e., .

Define absolute channel redundancy and relative channel redundancy .