Codex @codex  0

A binary symmetric channel is a discrete memoryless channel that flips each transmitted bit with fixed crossover probability $p$. For one use, write $Y=X\oplus Z$, where $\oplus$ is exclusive or and $Z$ is a Bernoulli random variable with parameter $p$, independent of the input $X$. Thus $Z=0$ preserves the bit and $Z=1$ flips it. Different uses have independent noise under this model.

With row labels $X=0,1$ and column labels $Y=0,1$, its transition matrix isEach row sums to one, and exchanging both binary labels leaves the rule unchanged, explaining symmetric. For $p=0.1$, a prescribed three-bit input $010$ produces $010$ with probability $0.9^3=0.729$ and $011$ with probability $0.9^2(0.1)=0.081$. The received $011$ does not itself announce the changed position: it could also arise from input $011$ with no flips.

The binary symmetric channel capacity quantifies how well a block code can overcome this uncertainty, and input distribution optimization for a binary symmetric channel shows why a fair input attains the best information rate. A completely noisy binary symmetric channel has $p=1/2$ and carries no input information; a known flip on every use, $p=1$, is instead reversible.

A binary symmetric channel with crossover probability $p$ has capacitybits per channel use.

A block code assigns source messages to words of a fixed length over an alphabet. Its codewords form a subset of that fixed-length word space; a binary block code uses the two-symbol finite field ${\mathbb{F}}_2$.

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].

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.

A discrete memoryless channel models transmission through finite input and output alphabets using fixed conditional probabilities $W(y\mid x)$. For each input $x$, these nonnegative numbers sum to one over the output symbols. Discrete refers to the symbols, and memoryless means that the noise of one use does not remember earlier uses.

For a fixed input word $x^n=(x_1,\dots ,x_n)$ sent without feedback, the output law isThis is conditional independence of the outputs given the prescribed input word. It does not require an encoder to choose independent input symbols: the codewords of a block code deliberately impose relationships among them. Those relationships let a decoder distinguish possible messages after noise.

The binary symmetric channel and binary erasure channel make two different memoryless noise models with a binary input. One hides flipped bits; the other marks missing bits. Their different channel capacities show why the whole transition matrix matters, as the flips versus erasures in a binary channel demonstrate.

Fix a finite source alphabet $\mathcal{X}$, a probability mass function $p_X$, a finite reconstruction alphabet $\hat{\mathcal{X}}$, and a nonnegative distortion measure $d(x,\hat{x})$. The information rate-distortion function isThe source probability distribution stays fixed; the conditional distribution of the reconstruction is what we optimize. Each feasible test channel must keep expected distortion at most $D$. The objective is mutual information, measured in bits when the logarithms have base two. If no test channel satisfies the constraint, the infimum is $+\infty$.^[ref]

Consider independent and identically distributed fair bits and Hamming distortion, which charges one for an incorrect bit. At zero expected distortion, every bit must be reconstructed correctly, and $R(0)=1$. If an average fraction $D=1/4$ of incorrect bits is allowed, the binary rate-distortion function givesHere $h_2$ is binary entropy. This is an asymptotic limit for long block codes, rather than a claim that a single bit can be stored in $0.18872$ physical bits. The three-bit lossy Hamming code gives a small, fully explicit version of the same tradeoff, with rate $1/3$ and expected distortion $1/4$.

Rate-distortion theory separates the question of what is possible from the design of a practical encoder and decoder. It also forces the fidelity criterion to be explicit. Hamming distortion treats all symbol mismatches alike; mean squared error instead penalizes larger numerical errors more strongly. Those objectives can favor different reconstructions of the same data. An average error criterion does not by itself control the error on every individual input.

Claude Shannon's Coding Theorems for a Discrete Source With a Fidelity Criterion by Claude Shannon was published in 1959. Its formulation fixes a cost for replacing one source letter by another and studies the communication rate compatible with the allowed average cost. The important shift is to quantify which distinctions may be discarded, rather than requiring exact recovery of every letter.^[ref]

The typical sequence theorem turns a probability concentration into a coding construction. Assign one binary number index to each weakly typical sequence, plus a reserved index for every word outside the set. The decoder recovers every typical word exactly; the reserved index has one predetermined output. The block code usesbits and has reconstruction-error probability at most $1-P(T_{\epsilon }^{(n)})$.

For this example and $\epsilon =0.1$, $n=40$ needs 34 bits but permits error up to about $0.3611$. At $n=640$, 570 bits suffice and the error bound is about $0.0002215$. These are existence calculations for an explicitly enumerated collection, rather than claims about an efficient practical encoder. The reduction comes from protecting the whole high-probability collection, rather than just its single most likely member.