Discrete memoryless channel ($W^n(y^n\mid x^n)={\prod }_{j=1}^{n}W(y_j\mid x_j)$)

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.

Let the input alphabet be $\{0,1,2\}$ and let the output be $Y=X+Z$, where independent noise is uniform on two distinct integers. Translating the output alphabet reduces the noise to $\{0,d\}$, $d\ge 1$. The reachable output alphabet has size $3+\min (d,3)$: it is the union of two three-element intervals shifted by $d$.

For $d=1$, every row of the transition matrix has conditional information entropy one bit, so $I(X;Y)\le {\log }_{2}4-1=1$. Input probabilities $(1/2,0,1/2)$ make the output uniform and attain one bit per use. For $d\ge 3$, the two translated input alphabets are disjoint and every output identifies its input. A uniform input then attains ${\log }_{2}3$ bits per use.

For $d=2$, reflection symmetry and concavity of information entropy permit restricting to input probabilities $(s/2,1-s,s/2)$. Conditional on output parity, outputs whose labels are even integers have probabilities $(1/4,1/2,1/4)$ and outputs whose labels are odd integers have probabilities $(1/2,1/2)$. Consequently $I(X;Y)=h_2(s)+s/2$. Its strictly negative second derivative and stationary equation ${\log }_2((1-s)/s)+1/2=0$ give $s=\sqrt{2}/(1+\sqrt{2})$ and channel capacity ${\log }_2(1+\sqrt{2})$. All three values follow from overlap of translated input alphabets, rather than from output alphabet size alone.

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

The worst message's error probability under a specified channel encoder, communication channel, and channel decoder. It upper-bounds the average error probability under every message probability distribution. In particular, a uniform bound on maximal decoding error probability remains valid after restricting to any nonempty subset of messages. This distinguishes it from an average-only error guarantee in channel coding.

A finite-alphabet erasure channel transmits the input symbol unchanged with probability $1-f$ and replaces it by a distinct erasure flag with probability $f$, independently of the symbol. Given the flag, the posterior remains the input distribution; otherwise the input is known. Thus its mutual information is $(1-f)H(X)$.

For a finite-alphabet erasure channel with $k$ input symbols, $I(X;Y)=(1-f)H(X)$. Maximizing Shannon entropy at the uniform input gives channel capacity $C=(1-f){\log }_{2}k$ bits per use, by the Shannon second coding theorem.

A binary erasure channel transmits each input bit correctly with probability $1-\epsilon$ and replaces it by an erasure symbol with probability $\epsilon$. Its channel capacity is $1-\epsilon$ bits per use.

With channel feedback, resend each message bit through a binary erasure channel until a non-erased copy arrives, then move to the next bit. The channel decoder deletes erasure symbols, giving the message without error whenever transmission completes. For $q<1$, the waiting times have an independent and identically distributed geometric distribution with expectation $1/(1-q)$, so every finite message completes almost surely. The strong law of large numbers gives forward code rate $n/{\sum }_{j=1}^n{M}_j\to 1-q$, matching channel capacity. At $q=1$, transmission never completes. Independent erasure indicators, rather than independent message bits, are the essential hypothesis.

For a deterministic length-$n$ channel code with $m>2$ messages on a binary erasure channel of erasure probability $q$, exclude the message decoded from the all-erased output. Under a uniform choice of the other $m-1$ messages, success probability is at least $1-{\epsilon }_{\max }$. Conditional on an erasure pattern with $k\ge 1$ unerased positions, there are at most $2^k$ output words, so average success is at most $\min \{1,2^k/(m-1)\}$. With no unerased positions it is zero.

Put $L={\log }_{2}m-1$. The scalar bound $\min \{1,2^k/(m-1)\}\le k/L$ is immediate for $k\ge L$. Otherwise set $r=m/2^k>2$. Since ${\log }_{2}r\le r-1$ for $r\ge 2$,The inequality ${\log }_{2}r\le r-1$ follows because equality holds at $r=2$ and the derivative of $r-1-{\log }_{2}r$ is $1-1/(r\ln 2)>0$ for $r\ge 2$. Averaging the scalar bound over the number $K$ of unerased positions, with $\mathbb{E}K=n(1-q)$, proves the displayed claim. Thus ${\epsilon }_{\max }\le \delta <1$ implies code rate $R\le (1-q)/(1-\delta )+1/n$. The cases $m\le 2$ satisfy this rate bound directly.

Deterministic decoding is essential to this version: on an always-erased channel, a randomized uniform guess has maximal decoding error probability $1-1/m$ despite receiving no information. The usual deterministic channel decoder has maximal error one when $m>1$ on that channel.

A Z-channel transmits one binary input without error while the other can change into the first. Unlike a binary symmetric channel, its errors are one-sided.