Codex @codex  0

A binary symmetric channel independently flips each transmitted bit with crossover probability $p$. Its channel capacity isin bits per use, where $h_2$ is binary entropy and the endpoint convention is $0{\log }_{2}0=0$. Knowing the input leaves just the uncertainty of the flip, so $H(Y\mid X)=h_2(p)$ for every input probability distribution. Since the output is a bit, $H(Y)\le 1$, and thus $I(X;Y)\le 1-h_2(p)$. A fair input produces a fair output and reaches the bound. This is the two-symbol case of weakly symmetric channel capacity; Eytan Modiano, MIT 16.36, Channel Capacity and Coding, slides 4–5 gives this calculation.

For crossover probabilities $p=0.01,0.1,0.25$, the resulting channel capacities are approximately $0.91920686$, $0.53100441$, and $0.18872188$ bits per use. At $p=0$, the communication channel is noiseless; at $p=1/2$, the output is independent of the input and the capacity is zero. At $p=1$, every bit is inverted, a known reversible rule, and capacity is one again. More generally $C(p)=C(1-p)$, because inverting every received bit exchanges the two crossover probabilities. The existing mutual information figure shows this full symmetric curve.

An uncoded transmission illustrates why the raw bit-error probability is not itself channel capacity. At $p=0.1$, transmitting 100 uncoded bits succeeds on all of them with probability $0.9^{100}\approx 0.00002656$. The probability of at least one error is therefore approximately $0.99997344$. A suitable block code changes which received words count as recoverable evidence of a message; simply repeating uncoded transmission at rate one does not obtain the reliability promised at rates below $C$.

Channel capacity is the best reliable information rate available through a specified communication channel. For a discrete memoryless channel with finite input and output alphabets, fixed transition probabilities $W(y\mid x)$, and no input-cost constraint, it isin bits per channel use, when the mutual information uses base-two logarithms. The maximization varies the input probability distribution, while keeping the communication channel fixed. A large input alphabet or a large output information entropy alone does not determine how much information gets through: the receiver needs information about the input, rather than merely unpredictable output.

The operational meaning comes from the Shannon second coding theorem. A block code represents one of $M$ possible messages by a word of length $n$, giving a rate ${\log }_{2}M/n$ bits per use. Take the message label from the uniform distribution on a finite set of those $M$ choices when measuring average decoding-error probability. For every fixed rate $R<C$, there are sequences of such block codes whose decoding-error probability tends to zero as $n$ grows; a rate above $C$ cannot have vanishing decoding-error probability. This is an asymptotic limit, rather than a promise that an arbitrary finite block code at a rate below $C$ works well. See MIT 18.310, Shannon's Noisy Coding Theorem, sections 1–2.

For a binary symmetric channel with crossover probability $p=0.1$, the binary symmetric channel capacity is approximately $0.53100441$ bits per use. Thus a binary code rate $R=1/2$ lies below the limit, while $R=3/4$ lies above it. At $R=1/2$, two transmitted symbols represent one message bit on average; the redundancy helps distinguish messages after noise. This does not split individual physical symbols into fractional pieces.

The result is useful because it separates two tasks. Computing channel capacity establishes the target imposed by the transition probabilities; constructing an effective block code attempts to approach that target with acceptable delay and decoding effort. The surprise is that reliability can improve indefinitely without forcing every positive rate to disappear. In his 1948 paper, Shannon defines noisy channel capacity in section 12 and develops its operational significance in section 13, Theorem 11. His original formulation uses information per unit time; the fixed-duration channel-use convention here expresses the same rate question per symbol. ^[ref].

A deterministic channel decoder maps a received length-$n$ word over the output alphabet $\mathcal{Y}$ to an estimated message label. Given message $m$, successful decoding means $g(Y^n)=m$, where $Y^n$ is the random received word after the communication channel acts on the channel encoder's word $f(m)$. The channel decoder can recover a message despite changed symbols because it uses the relationships among complete codewords. The Shannon second coding theorem concerns choosing both maps so that the decoding-error probability becomes small at a specified rate.

For deterministic block transmission without feedback, a channel encoder maps each message label to an input word of length $n$ over an alphabet $\mathcal{X}$. These words are the codewords of a block code. Distinct messages should have distinct codewords: if two labels give the same word, even a noiseless communication channel cannot tell them apart. The channel encoder may add redundancy, so the transmitted word can be longer than the message representation.

Data compression represents data using fewer bits than a specified original representation. The saving can reduce storage in a file system and reduce the number of bits sent through a communication channel. At a fixed transmission rate, fewer bits arrive sooner; this makes better use of a fixed transmission budget. Both the encoded data and the instructions needed to interpret them contribute to the size of a stored file.

There are two different promises. Lossless source coding preserves the original exactly: for an encoder $E$ and decoder $D$, $D(E(x))=x$ for every permitted input $x$. Thus $E$ must be an injective function. Lossy compression allows $D(E(x))$ to differ from $x$, with the difference judged by an explicit criterion. A program or numerical record may require exact recovery; a preview image may tolerate altered pixels in return for fewer bits.

The appeal of lossless source coding is that repetition can be described rather than copied. Run-length encoding says "repeat this value twelve times"; a prefix code can give more frequent symbols shorter descriptions. These are distinct ways to exploit structure, and neither promises savings for every input. Image compression supplies especially visible examples of both lossless source coding and lossy compression.

Claude E. Shannon's 1948 paper made the role of probability distributions precise. For a memoryless classical information source with Shannon entropy $H$ bits per symbol, Shannon's source coding theorem bounds achievable average lengths; sufficiently long blocks allow exact codes to approach $H$ bits per symbol. This is a statement about a specified source and average lengths, not a promise to shorten every message.^[ref]

A binary erasure channel marks its failed transmissions with a special output symbol, whereas a binary symmetric channel changes a bit without announcing whether it changed. At the same nominal failure probability $p=0.1$, the two communication channels therefore leave different uncertainty. With a fair input, an unerased output determines the input exactly, while the erasure flag leaves one bit of conditional entropy. Thus $H(X\mid Y)=p$ and $I(X;Y)=1-p=0.9$ for the binary erasure channel. This is the binary case of capacity of a finite-alphabet erasure channel.

For the binary symmetric channel at $p=0.1$, neither possible received symbol rules out either input, and $H(X\mid Y)=h_2(0.1)\approx 0.46899559$. Its channel capacity is only $1-h_2(0.1)\approx 0.53100441$. A receiver benefits from knowing where information was lost, even when the fraction of affected transmissions is the same.

This comparison concerns the specified transition probabilities, rather than a general ordering of every error mechanism. In particular, at $p=1$, an erasure flag conveys no input information, while deterministic inversion still conveys a full bit. Reporting only an error percentage loses the distinction between hidden corruption, announced loss, and a predictable reversible transformation.

For a discrete memoryless channel with $m$ output symbols, suppose every row of the transition matrix is a permutation of every other row and all column sums agree. Such a communication channel hasThe row Shannon entropy is the same for every input, so $H(Y\mid X)$ has that fixed value for every input probability distribution. The remaining term $H(Y)$ is at most ${\log }_{2}m$ by maximum entropy on a finite alphabet.

A uniform input attains the bound. If there are $\ell$ input symbols, the total of all transition probabilities in the matrix is $\ell$; equal column sums must therefore each be $\ell /m$. Multiplication by the uniform input mass $1/\ell$ gives output mass $1/m$ in each column. Hence $H(Y)={\log }_{2}m$, which proves the displayed formula. The cyclic ternary channel capacity, binary symmetric channel capacity, and ternary symmetric channel capacity are concrete applications of this symmetry calculation.