A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
The capacity of a discrete memoryless channel is C = max_{p(x)} I(X;Y), the maximum mutual information between input X and output Y over all possible input distributions. Capacity represents the highest rate (in bits per channel use) at which information can be transmitted with arbitrarily low error probability. The channel's noise characteristics are fixed; the only freedom is choosing the input distribution. Shannon showed that capacity is achievable — there exist coding schemes that transmit at any rate below C with error probability approaching zero — and that rates above C are impossible. This is the channel coding theorem, the most celebrated result in information theory.
A communication channel takes an input symbol and produces an output that may be corrupted by noise. The channel is characterized by its transition probabilities p(y|x) — for each input x, the probability of receiving each output y. The fundamental question is: how fast can you communicate reliably through this noisy channel?
Shannon's answer is channel capacity: C = max over all input distributions p(x) of the mutual information I(X;Y). The mutual information I(X;Y) = H(Y) - H(Y|X) measures how much the output reveals about the input. H(Y|X) is the "noise entropy" — the uncertainty in the output that is purely due to channel noise and carries no information about the input. H(Y) is the total output uncertainty. The difference is the useful information. By choosing p(x) to maximize this difference, you find the channel's intrinsic capacity.
The conceptual beauty is that capacity separates the problem into two parts. The channel capacity C is a fixed property of the physical medium. The coding scheme is the engineering that exploits it. Shannon proved that for any rate R < C, there exist codes (sequences of input symbols) that achieve error probability approaching zero as the block length grows. Conversely, for R > C, every code has error probability bounded away from zero. The coding theorem does not tell you how to construct good codes — it is an existence proof. The quest for practical codes that approach capacity drove decades of research, leading to turbo codes, LDPC codes, and polar codes, which come within a fraction of a dB of the Shannon limit.
For the binary symmetric channel (BSC) with crossover probability p, C = 1 - H(p) bits per use, where H(p) is the binary entropy function. When p = 0 (no noise), C = 1; when p = 1/2 (random output), C = 0. For the Gaussian channel with signal power P and noise power N, C = (1/2) log2(1 + P/N) bits per use — the famous Shannon-Hartley formula. These specific results are among the most important formulas in engineering, setting the theoretical limits for everything from Wi-Fi to deep-space communication.