Channel capacity

This article needs additional citations for verification . Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources:  "Channel capacity"  –  news · newspapers · books · scholar · JSTOR (May 2023) ( Learn how and when to remove this template message )

Information theory
Entropy Differential entropy Conditional entropy Joint entropy Mutual information Directed information Conditional mutual information Relative entropy Entropy rate Limiting density of discrete points
Asymptotic equipartition property Rate–distortion theory
Shannon's source coding theorem Channel capacity Noisy-channel coding theorem Shannon–Hartley theorem
v t e

Channel capacity, in electrical engineering, computer science, and information theory, is the theoretical maximum rate at which information can be reliably transmitted over a communication channel.

Contents

• Formal definition
• Additivity of channel capacity
• Shannon capacity of a graph
• Noisy-channel coding theorem
• Example application
• Channel capacity in wireless communications
• Bandlimited AWGN channel
• Frequency-selective AWGN channel
• Slow-fading channel
• Fast-fading channel
• Feedback Capacity
• Main results on feedback capacity
• Gaussian feedback capacity
• Solution techniques
• See also
• Advanced Communication Topics
• External links
• References

Following the terms of the noisy-channel coding theorem, the channel capacity of a given channel is the highest information rate (in units of information per unit time) that can be achieved with arbitrarily small error probability. ^{[1] [2]}

Information theory, developed by Claude E. Shannon in 1948, defines the notion of channel capacity and provides a mathematical model by which it may be computed. The key result states that the capacity of the channel, as defined above, is given by the maximum of the mutual information between the input and output of the channel, where the maximization is with respect to the input distribution. ^[3]

The notion of channel capacity has been central to the development of modern wireline and wireless communication systems, with the advent of novel error correction coding mechanisms that have resulted in achieving performance very close to the limits promised by channel capacity.

Formal definition

The basic mathematical model for a communication system is the following:

${\displaystyle {\xrightarrow[{\text{Message}}]{W}}{\begin{array}{|c|}\hline {\text{Encoder}}\\f_{n}\\\hline \end{array}}{\xrightarrow[{\mathrm {Encoded \atop sequence} }]{X^{n}}}{\begin{array}{|c|}\hline {\text{Channel}}\\p(y|x)\\\hline \end{array}}{\xrightarrow[{\mathrm {Received \atop sequence} }]{Y^{n}}}{\begin{array}{|c|}\hline {\text{Decoder}}\\g_{n}\\\hline \end{array}}{\xrightarrow[{\mathrm {Estimated \atop message} }]{\hat {W}}}}$

where:

• ${\displaystyle W}$ is the message to be transmitted;
• ${\displaystyle X}$ is the channel input symbol (${\displaystyle X^{n}}$ is a sequence of ${\displaystyle n}$ symbols) taken in an alphabet ${\displaystyle {\mathcal {X}}}$;
• ${\displaystyle Y}$ is the channel output symbol (${\displaystyle Y^{n}}$ is a sequence of ${\displaystyle n}$ symbols) taken in an alphabet ${\displaystyle {\mathcal {Y}}}$;
• ${\displaystyle {\hat {W}}}$ is the estimate of the transmitted message;
• ${\displaystyle f_{n}}$ is the encoding function for a block of length ${\displaystyle n}$;
• ${\displaystyle p(y|x)=p_{Y|X}(y|x)}$ is the noisy channel, which is modeled by a conditional probability distribution; and,
• ${\displaystyle g_{n}}$ is the decoding function for a block of length ${\displaystyle n}$.

Let ${\displaystyle X}$ and ${\displaystyle Y}$ be modeled as random variables. Furthermore, let ${\displaystyle p_{Y|X}(y|x)}$ be the conditional probability distribution function of ${\displaystyle Y}$ given ${\displaystyle X}$, which is an inherent fixed property of the communication channel. Then the choice of the marginal distribution ${\displaystyle p_{X}(x)}$ completely determines the joint distribution ${\displaystyle p_{X,Y}(x,y)}$ due to the identity

${\displaystyle \ p_{X,Y}(x,y)=p_{Y|X}(y|x)\,p_{X}(x)}$

which, in turn, induces a mutual information ${\displaystyle I(X;Y)}$. The channel capacity is defined as

${\displaystyle \ C=\sup _{p_{X}(x)}I(X;Y)\,}$

where the supremum is taken over all possible choices of ${\displaystyle p_{X}(x)}$.

Additivity of channel capacity

Channel capacity is additive over independent channels. ^[4] It means that using two independent channels in a combined manner provides the same theoretical capacity as using them independently. More formally, let ${\displaystyle p_{1}}$ and ${\displaystyle p_{2}}$ be two independent channels modelled as above; ${\displaystyle p_{1}}$ having an input alphabet ${\displaystyle {\mathcal {X}}_{1}}$ and an output alphabet ${\displaystyle {\mathcal {Y}}_{1}}$. Idem for ${\displaystyle p_{2}}$. We define the product channel ${\displaystyle p_{1}\times p_{2}}$ as ${\displaystyle \forall (x_{1},x_{2})\in ({\mathcal {X}}_{1},{\mathcal {X}}_{2}),\;(y_{1},y_{2})\in ({\mathcal {Y}}_{1},{\mathcal {Y}}_{2}),\;(p_{1}\times p_{2})((y_{1},y_{2})|(x_{1},x_{2}))=p_{1}(y_{1}|x_{1})p_{2}(y_{2}|x_{2})}$

This theorem states:

$${\displaystyle C(p_{1}\times p_{2})=C(p_{1})+C(p_{2})}$$

Shannon capacity of a graph

If G is an undirected graph, it can be used to define a communications channel in which the symbols are the graph vertices, and two codewords may be confused with each other if their symbols in each position are equal or adjacent. The computational complexity of finding the Shannon capacity of such a channel remains open, but it can be upper bounded by another important graph invariant, the Lovász number. ^[5]

Noisy-channel coding theorem

The noisy-channel coding theorem states that for any error probability ε > 0 and for any transmission rate R less than the channel capacity C, there is an encoding and decoding scheme transmitting data at rate R whose error probability is less than ε, for a sufficiently large block length. Also, for any rate greater than the channel capacity, the probability of error at the receiver goes to 0.5 as the block length goes to infinity.

Example application

An application of the channel capacity concept to an additive white Gaussian noise (AWGN) channel with B Hz bandwidth and signal-to-noise ratio S/N is the Shannon–Hartley theorem:

${\displaystyle C=B\log _{2}\left(1+{\frac {S}{N}}\right)\ }$

C is measured in bits per second if the logarithm is taken in base 2, or nats per second if the natural logarithm is used, assuming B is in hertz; the signal and noise powers S and N are expressed in a linear power unit (like watts or volts²). Since S/N figures are often cited in dB, a conversion may be needed. For example, a signal-to-noise ratio of 30 dB corresponds to a linear power ratio of ${\displaystyle 10^{30/10}=10^{3}=1000}$.

Channel capacity in wireless communications

This section ^[6] focuses on the single-antenna, point-to-point scenario. For channel capacity in systems with multiple antennas, see the article on MIMO.

Bandlimited AWGN channel

Main article: Shannon–Hartley theorem

If the average received power is ${\displaystyle {\bar {P}}}$ [W], the total bandwidth is ${\displaystyle W}$ in Hertz, and the noise power spectral density is ${\displaystyle N_{0}}$ [W/Hz], the AWGN channel capacity is

${\displaystyle C_{\text{AWGN}}=W\log _{2}\left(1+{\frac {\bar {P}}{N_{0}W}}\right)}$ [bits/s],

where ${\displaystyle {\frac {\bar {P}}{N_{0}W}}}$ is the received signal-to-noise ratio (SNR). This result is known as the Shannon–Hartley theorem. ^[7]

When the SNR is large (SNR ≫ 0 dB), the capacity ${\displaystyle C\approx W\log _{2}{\frac {\bar {P}}{N_{0}W}}}$ is logarithmic in power and approximately linear in bandwidth. This is called the bandwidth-limited regime.

When the SNR is small (SNR ≪ 0 dB), the capacity ${\displaystyle C\approx {\frac {\bar {P}}{N_{0}\ln 2}}}$ is linear in power but insensitive to bandwidth. This is called the power-limited regime.

The bandwidth-limited regime and power-limited regime are illustrated in the figure.

Feedback Capacity

Feedback capacity is the greatest rate at which information can be reliably transmitted, per unit time, over a point-to-point communication channel in which the receiver feeds back the channel outputs to the transmitter. Information-theoretic analysis of communication systems that incorporate feedback is more complicated and challenging than without feedback. Possibly, this was the reason C.E. Shannon chose feedback as the subject of the first Shannon Lecture, delivered at the 1973 IEEE International Symposium on Information Theory in Ashkelon, Israel.

The feedback capacity is characterized by the maximum of the directed information between the channel inputs and the channel outputs, where the maximization is with respect to the causal conditioning of the input given the output. The directed information was coined by James Massey ^[8] in 1990, who showed that its an upper bound on feedback capacity. For memoryless channels, Shannon showed ^[9] that feedback does not increase the capacity, and the feedback capacity coincides with the channel capacity characterized by the mutual information between the input and the output. The feedback capacity is known as a closed-form expression only for several examples such as: the Trapdoor channel, ^[10] Ising channel, ^{[11] [12]} the binary erasure channel with a no-consecutive-ones input constraint, NOST channels.

The basic mathematical model for a communication system is the following:

Here is the formal definition of each element (where the only difference with respect to the nonfeedback capacity is the encoder definition):

• ${\displaystyle W}$ is the message to be transmitted, taken in an alphabet ${\displaystyle {\mathcal {W}}}$;
• ${\displaystyle X}$ is the channel input symbol (${\displaystyle X^{n}}$ is a sequence of ${\displaystyle n}$ symbols) taken in an alphabet ${\displaystyle {\mathcal {X}}}$;
• ${\displaystyle Y}$ is the channel output symbol (${\displaystyle Y^{n}}$ is a sequence of ${\displaystyle n}$ symbols) taken in an alphabet ${\displaystyle {\mathcal {Y}}}$;
• ${\displaystyle {\hat {W}}}$ is the estimate of the transmitted message;
• ${\displaystyle f_{i}:{\mathcal {W}}\times {\mathcal {Y}}^{i-1}\to {\mathcal {X}}}$ is the encoding function at time ${\displaystyle i}$, for a block of length ${\displaystyle n}$;
• ${\displaystyle p(y_{i}|x^{i},y^{i-1})=p_{Y_{i}|X^{i},Y^{i-1}}(y_{i}|x^{i},y^{i-1})}$ is the noisy channel at time ${\displaystyle i}$, which is modeled by a conditional probability distribution; and,
• ${\displaystyle {\hat {w}}:{\mathcal {Y}}^{n}\to {\mathcal {W}}}$ is the decoding function for a block of length ${\displaystyle n}$.

That is, for each time ${\displaystyle i}$ there exists a feedback of the previous output ${\displaystyle Y_{i-1}}$ such that the encoder has access to all previous outputs ${\displaystyle Y^{i-1}}$. An ${\displaystyle (2^{nR},n)}$ code is a pair of encoding and decoding mappings with ${\displaystyle {\mathcal {W}}=[1,2,\dots ,2^{nR}]}$, and ${\displaystyle W}$ is uniformly distributed. A rate ${\displaystyle R}$ is said to be achievable if there exists a sequence of codes ${\displaystyle (2^{nR},n)}$ such that the average probability of error:${\displaystyle P_{e}^{(n)}\triangleq \Pr({\hat {W}}\neq W)}$ tends to zero as ${\displaystyle n\to \infty }$.

The feedback capacity is denoted by ${\displaystyle C_{\text{feedback}}}$, and is defined as the supremum over all achievable rates.

See also

• Bandwidth (computing)
• Bandwidth (signal processing)
• Bit rate
• Code rate
• Error exponent
• Nyquist rate
• Negentropy
• Redundancy
• Sender, Data compression, Receiver
• Shannon–Hartley theorem
• Spectral efficiency
• Throughput

External links

• "Transmission rate of a channel", Encyclopedia of Mathematics , EMS Press, 2001 [1994]
• AWGN Channel Capacity with various constraints on the channel input (interactive demonstration)

Related Research Articles

Information theory is the mathematical study of the quantification, storage, and communication of information. The field was originally established by the works of Harry Nyquist and Ralph Hartley, in the 1920s, and Claude Shannon in the 1940s. The field, in applied mathematics, is at the intersection of probability theory, statistics, computer science, statistical mechanics, information engineering, and electrical engineering.

In information theory, the entropy of a random variable is the average level of "information", "surprise", or "uncertainty" inherent to the variable's possible outcomes. Given a discrete random variable , which takes values in the alphabet and is distributed according to :

A random variable is a mathematical formalization of a quantity or object which depends on random events. The term 'random variable' can be misleading as its mathematical definition is not actually random nor a variable, but rather it is a function from possible outcomes in a sample space to a measurable space, often to the real numbers.

In probability and statistics, a Bernoulli process is a finite or infinite sequence of binary random variables, so it is a discrete-time stochastic process that takes only two values, canonically 0 and 1. The component Bernoulli variablesX_i are identically distributed and independent. Prosaically, a Bernoulli process is a repeated coin flipping, possibly with an unfair coin. Every variable X_i in the sequence is associated with a Bernoulli trial or experiment. They all have the same Bernoulli distribution. Much of what can be said about the Bernoulli process can also be generalized to more than two outcomes ; this generalization is known as the Bernoulli scheme.

In statistics, maximum likelihood estimation (MLE) is a method of estimating the parameters of an assumed probability distribution, given some observed data. This is achieved by maximizing a likelihood function so that, under the assumed statistical model, the observed data is most probable. The point in the parameter space that maximizes the likelihood function is called the maximum likelihood estimate. The logic of maximum likelihood is both intuitive and flexible, and as such the method has become a dominant means of statistical inference.

Additive white Gaussian noise (AWGN) is a basic noise model used in information theory to mimic the effect of many random processes that occur in nature. The modifiers denote specific characteristics:

In information theory, the typical set is a set of sequences whose probability is close to two raised to the negative power of the entropy of their source distribution. That this set has total probability close to one is a consequence of the asymptotic equipartition property (AEP) which is a kind of law of large numbers. The notion of typicality is only concerned with the probability of a sequence and not the actual sequence itself.

Vapnik–Chervonenkis theory was developed during 1960–1990 by Vladimir Vapnik and Alexey Chervonenkis. The theory is a form of computational learning theory, which attempts to explain the learning process from a statistical point of view.

In probability theory and information theory, the mutual information (MI) of two random variables is a measure of the mutual dependence between the two variables. More specifically, it quantifies the "amount of information" obtained about one random variable by observing the other random variable. The concept of mutual information is intimately linked to that of entropy of a random variable, a fundamental notion in information theory that quantifies the expected "amount of information" held in a random variable.

In information theory, the cross-entropy between two probability distributions and over the same underlying set of events measures the average number of bits needed to identify an event drawn from the set if a coding scheme used for the set is optimized for an estimated probability distribution , rather than the true distribution .

In information theory, the noisy-channel coding theorem, establishes that for any given degree of noise contamination of a communication channel, it is possible to communicate discrete data nearly error-free up to a computable maximum rate through the channel. This result was presented by Claude Shannon in 1948 and was based in part on earlier work and ideas of Harry Nyquist and Ralph Hartley.

In information theory, information dimension is an information measure for random vectors in Euclidean space, based on the normalized entropy of finely quantized versions of the random vectors. This concept was first introduced by Alfréd Rényi in 1959.

In coding theory and information theory, a Z-channel or binary asymmetric channel is a communications channel used to model the behaviour of some data storage systems.

In coding theory, list decoding is an alternative to unique decoding of error-correcting codes for large error rates. The notion was proposed by Elias in the 1950s. The main idea behind list decoding is that the decoding algorithm instead of outputting a single possible message outputs a list of possibilities one of which is correct. This allows for handling a greater number of errors than that allowed by unique decoding.

Zero-forcing precoding is a method of spatial signal processing by which a multiple antenna transmitter can null the multiuser interference in a multi-user MIMO wireless communication system. When the channel state information is perfectly known at the transmitter, the zero-forcing precoder is given by the pseudo-inverse of the channel matrix. Zero-forcing has been used in LTE mobile networks.

In the theory of quantum communication, the quantum capacity is the highest rate at which quantum information can be communicated over many independent uses of a noisy quantum channel from a sender to a receiver. It is also equal to the highest rate at which entanglement can be generated over the channel, and forward classical communication cannot improve it. The quantum capacity theorem is important for the theory of quantum error correction, and more broadly for the theory of quantum computation. The theorem giving a lower bound on the quantum capacity of any channel is colloquially known as the LSD theorem, after the authors Lloyd, Shor, and Devetak who proved it with increasing standards of rigor.

The term Blahut–Arimoto algorithm is often used to refer to a class of algorithms for computing numerically either the information theoretic capacity of a channel, the rate-distortion function of a source or a source encoding. They are iterative algorithms that eventually converge to one of the maxima of the optimization problem that is associated with these information theoretic concepts.

Fuzzy extractors are a method that allows biometric data to be used as inputs to standard cryptographic techniques, to enhance computer security. "Fuzzy", in this context, refers to the fact that the fixed values required for cryptography will be extracted from values close to but not identical to the original key, without compromising the security required. One application is to encrypt and authenticate users records, using the biometric inputs of the user as a key.

In machine learning, the kernel embedding of distributions comprises a class of nonparametric methods in which a probability distribution is represented as an element of a reproducing kernel Hilbert space (RKHS). A generalization of the individual data-point feature mapping done in classical kernel methods, the embedding of distributions into infinite-dimensional feature spaces can preserve all of the statistical features of arbitrary distributions, while allowing one to compare and manipulate distributions using Hilbert space operations such as inner products, distances, projections, linear transformations, and spectral analysis. This learning framework is very general and can be applied to distributions over any space on which a sensible kernel function may be defined. For example, various kernels have been proposed for learning from data which are: vectors in , discrete classes/categories, strings, graphs/networks, images, time series, manifolds, dynamical systems, and other structured objects. The theory behind kernel embeddings of distributions has been primarily developed by Alex Smola, Le Song , Arthur Gretton, and Bernhard Schölkopf. A review of recent works on kernel embedding of distributions can be found in.

A Stein discrepancy is a statistical divergence between two probability measures that is rooted in Stein's method. It was first formulated as a tool to assess the quality of Markov chain Monte Carlo samplers, but has since been used in diverse settings in statistics, machine learning and computer science.

References

This article needs additional citations for verification . Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources:  "Channel capacity"  –  news · newspapers · books · scholar · JSTOR (January 2008) ( Learn how and when to remove this template message )