The Practical Attainability of Capacity with Finite-Length Codes — Epoche C2
The claim under examination The claim to be examined is that low-density parity-check codes have turned Shannon's channel capacity from an asymptotic ideal into a target reachable at finite block length, and the object here is to say exactly how much of that is true: at which block lengths, against which limit the decibels are being counted, and how the residual gap divides between the block length itself and the decoder. Two numbers in the earlier version of this essay do not survive that examination, and both are corrected below with the arithmetic shown. Shannon's 1948 theorem is an asymptotic statement, and its exact form matters for everything that follows. For a discrete memoryless channel with capacity $C$, and for every rate $R 0$, there exists a block length $n$ and a code of rate $R$ whose maximal probability of error is below $\delta$. The theorem asserts the existence of such an $n$; it places no bound on it, and no bound follows from the proof, which averages over random codebooks. Its converse says that for $R > C$ the error probability cannot be driven to zero. For the bandlimited additive white Gaussian noise channel the capacity takes the closed form $$C = B \log_2\left(1 + \frac{S}{N}\right) \ \text{bits per second},$$ with $B$ the bandwidth in hertz, $S$ the average signal power and $N$ the noise power in that band. Written per channel use rather than per second, and with $P$ the signal-to-noise ratio, this is $C = \tfrac{1}{2}\log_2(1+P)$ bits. Before any code is discussed, one ambiguity in the phrase "within so many decibels of the Shannon limit" has to be removed, because the earlier version of this essay used it without saying which limit it meant, and the two candidates differ by more than the gaps being reported. Write $E_b/N_0$ for the energy per information bit divided by the noise spectral density; for a rate $R$ in bits per channel use on the real AWGN channel, $P = 2R\,E_b/N_0$. Substituting into the capacity formula, reliable transmission at rate $R$ needs $R \ln 2 = 0.693$, that is $-1.59$ dB: the ultimate limit, attainable only as the rate goes to zero. At rate $1/2$ the same relation gives $P = E_b/N_0$, and $C = 1/2$ requires $P = 1$, so the Gaussian-input limit sits at exactly $0$ dB. But practical systems impose binary signalling, and the capacity of the binary-input AWGN channel is strictly below the Gaussian-input capacity at the same power; at rate $1/2$ the binary-input limit is about $0.19$ dB. A gap quoted against one limit and read against the other is wrong by that amount, which is larger than the best reported gaps. What the sparsity of the parity-check matrix does and does not buy With the target defined, the code. Low-density parity-check codes were introduced by Robert Gallager as part of his doctoral research at MIT; the results appeared in the IRE Transactions in 1962 and as an MIT Press monograph the following year. The earlier version of this essay described them as a "doctoral thesis, published in 1962", which conflates the thesis with the journal paper. They were then largely set aside — the decoder was beyond 1960s hardware, and the field's attention went to algebraic constructions — and were rediscovered in the mid-1990s. A binary linear code of length $n$ and dimension $k$ is the null space of a parity-check matrix $\mathbf{H}$ with $n$ columns. In a $(d_v, d_c)$-regular LDPC code every column of $\mathbf{H}$ carries exactly $d_v$ ones and every row exactly $d_c$, with both held fixed as $n$ grows, so the density of ones falls as $1/n$. Counting ones two ways gives $n d_v = m d_c$ for $m$ rows, hence $m = n d_v/d_c$ and a design rate $R = 1 - d_v/d_c$, which is a lower bound on the true rate because rows of $\mathbf{H}$ may be dependent. The canonical example, $(3,6)$, has design rate $1/2$. The bipartite graph of $\mathbf{H}$ — Tanner's representation — has one variable node per codeword bit, one check node per parity equation, and an edge wherever a bit appears in an equation. For $(3,6)$ at $n = 1000$ there are $1000$ variable nodes, $500$ check nodes and $E = 3 \times 1000 = 3000$ edges. Belief propagation passes a log-likelihood ratio along each edge in each direction once per iteration, so the cost of an iteration is proportional to $E$, and with $d_v$ fixed, $E$ grows linearly in $n$; the total decoding cost is $O(nI)$ for $I$ iterations. Fifty iterations of the above code costs $3000 \times 50 = 150{,}000$ edge updates. Maximum-likelihood decoding, by contrast, compares the received word against every codeword, and there are $2^k = 2^{500} \approx 3.3 \times 10^{150}$ of them. That contrast, not any subtlety, is the whole reason sparse graphs are used. The claim in the earlier version that sparsity "facilitates efficient encoding" needs correcting, because it is false as stated and the correction is instructive. Encoding maps $k$ information bits to $n$ code bits via a generator matrix $\mathbf{G}$ spanning the null space of $\mathbf{H}$. Sparsity of $\mathbf{H}$ does not survive the Gaussian elimination that produces $\mathbf{G}$: the generator of a random sparse code is dense, and the encoding cost is the $O(n^2)$ of a dense matrix–vector product. Two real fixes exist. The general one is preprocessing: permuting $\mathbf{H}$ into approximate lower-triangular form leaves only a small residual block to be inverted, so that the dominant cost becomes linear with a quadratic term in the residual dimension rather than in $n$. The fix actually used in deployed systems is structural: standardised LDPC codes are quasi-cyclic, built by lifting a small base matrix with circulant permutation blocks, and their parity part is arranged so that the parity bits fall out of a running accumulation. Encoding is then a sequence of cyclic shifts and exclusive-ors, linear in $n$. Sparsity is necessary for cheap decoding; cheap encoding comes from structure imposed on top of it. Why belief propagation works, and under what hypotheses The decode