15 Efficiently Achieving the Capacity of the BSC_p
Recall (Theorem 144 and the exercise following it) that there exist linear codes of rate \(\)1-H(p)-ε\( such that maximum-likelihood decoding has error probability at most \)2^-δn\(, \)δ=Θ(ε^2)\(, on \)BSC_p\(. This left open whether the capacity of \)BSC_p\( can be achieved with \emph{efficient} encoding and decoding algorithms. In this chapter we answer this in the affirmative by using code concatenation (Definition~ \ref{def:c10-concatenation}): we pick an inner code that itself achieves the \)BSC_p\( capacity (small enough to construct by brute-force search) and an outer code that is efficiently list-... (unique-) decodable from a small constant fraction of \emph{worst-case} errors, and exploit the fact that the memoryless noise of \)BSC_p\(, combined with a concentration (Chernoff) argument, turns the outer code’s worst-case guarantee into an overall exponentially small failure probability. \)
15.1 Achieving Capacity of BSC_p
Fix
\(\)0≤p <12\( and \)0<ε<1-H(p)\(. Let \)γ>0\( be a parameter, depending only on \)ε\(, to be fixed later. We seek a linear code \)C^*=C_out○C_in\( (Definition~ \ref{def:c10-concatenation}) where: \begin{enumerate} \item[(i)]\end{enumerate}\)C_out\( is a linear \)[N,K]_2^k\( code with rate \)R≥1-ε2\(, together with a unique-decoding algorithm \)D_out\( that corrects at most a \)γ\( fraction of \emph{worst-case} errors, in time \)T_out(N)\(. \item [(ii)] \)C_in\( is a linear binary \)[n,k]_2\( code with rate \)r≥1-H(p)-ε2\(, together with a decoding algorithm \)D_in\( (returning the transmitted codeword) running in time \)T_in(k)\( and with decoding error probability at most \)γ2\( over \)BSC_p\(. \)
For the rest of the chapter we treat \(\)p\( as an absolute constant, so that \)k=Θ(n)\(; we write \)N=nN\( for the block length of \)C^*\(. \)
If
\(\)C^*=C_out○C_in\( is as in Construction~ \ref{constr:c15-concatenated-scheme}, then \[ R(C^*) \; =\; R\cdot r \; \ge \; \Big(1-\frac{\varepsilon }{2}\Big)\Big(1-H(p)-\frac{\varepsilon }{2}\Big) \; \ge \; 1-H(p)-\varepsilon . \] \begin{proof} \uses{constr:c15-concatenated-scheme} By the parameters of concatenated codes (rate of \end{proof}\)C_out○C_in\( is the product of the rates of \)C_out\( and \)C_in\(), the displayed equality holds. For the inequality, expand \[ \Big(1-\frac{\varepsilon }{2}\Big)\Big(1-H(p)-\frac{\varepsilon }{2}\Big) = 1-H(p)-\varepsilon +\frac{\varepsilon }{2}H(p)+\frac{\varepsilon ^2}{4} \ge 1-H(p)-\varepsilon , \] since \)H(p)+≥0\(. \)
We will use, for decoding, the natural decoder for concatenated codes.
Input: received word \(\)y=(y_1,…,y_N)[2]^n^N\(.\\ \textbf{Output:} message \)m’[2]^k^K\(. \begin{enumerate} \item For each \end{enumerate}\)1≤i≤N\(, let \)y_i’[2^k]\( be the (unique) symbol such that \)C_in(y_i’)=D_in(y_i)\(, and set \)y’=(y_1’,…,y_N’)\(. \item Return \)m’←D_out(y’)\(. \)
Let \(\)C^*=C_out○C_in\( be as in Construction~ \ref{constr:c15-concatenated-scheme}. Then \)C^*\( can be encoded in time \[ O(N^2k^2)+O(Nkn)\le O(N^2n^2)=O(\mathcal{N}^2), \] and Algorithm~ \ref{alg:c15-decoder} decodes \)C^*\( in time \[ N\cdot T_{in}(k)+T_{out}(N)\ \le \ \mathrm{poly}(\mathcal N), \] provided \)T_out(N)=N^O(1)\( and \)T_in(k)=2^O(k)\(. \begin{proof} \uses{constr:c15-concatenated-scheme, alg:c15-decoder} Both \end{proof}\)C_out\( and \)C_in\( are linear, so encoding \)C^*\( amounts to multiplying the message by a generator matrix for \)C_out\( (a \)K×N\( matrix over \)F_2^k\(, i.e.\ \)O(N^2)\( operations over \)F_2^k\(, each implementable with \)O(k^2)\( operations over \)F_2\(, giving \)O(N^2k^2)\() followed by, for each of the \)N\( resulting symbols, an \)O(k)×O(n)\( matrix multiplication over \)F_2\( to apply \)C_in\( (giving \)O(Nkn)\( total). Since \)k≤n\(, both terms are at most \)O(N^2n^2)=O(N^2)\(. For decoding, Algorithm~ \ref{alg:c15-decoder} runs \)D_in\( on each of the \)N\( blocks of \)y\( (total time \)N·T_in(k)\() and then runs \)D_out\( once (time \)T_out(N)\(). If \)T_out(N)=N^O(1)\( and \)T_in(k)=2^O(k)\(, both terms are \)N^O(1)\(, so the total decoding time is \)poly(N)\(. \)
15.2 Decoding Error Probability
Let \(\)C^*=C_out○C_in\( be as in Construction~ \ref{constr:c15-concatenated-scheme}, and let \)y\( be the result of transmitting a codeword of \)C^*\( over \)BSC_p\( (applied independently to each of the \)N\( inner blocks). Then Algorithm~ \ref{alg:c15-decoder} fails to recover the transmitted message with probability at most \)e^-γN/6=2^-Ω(γN/n)\(. \begin{proof} \uses{constr:c15-concatenated-scheme, alg:c15-decoder, def:c06-bsc} Fix \end{proof}\)i[N]\(. Since \)C_in\( is transmitted independently over \)BSC_p\( for each block (Definition~ \ref{def:c06-bsc}), and by the guarantee on \)D_in\( in Construction~ \ref{constr:c15-concatenated-scheme}(ii), the event \)E_i\( that \)y_i’≠C_out(m)_i\( (i.e.\ that the \)i\(-th inner decoding is wrong) has \)[E_i]≤γ/2\(; moreover the events \)E_1,…,E_N\( are mutually independent, since the \)BSC_p\( noise affecting distinct blocks is independent. Let \)X=∑_i=1^N 1[E_i]\( be the number of erroneous inner decodings; by linearity of expectation, \)E[X]≤γN/2\(. By the multiplicative Chernoff bound applied to \)X\(, a sum of \)N\( independent \){0,1}\(-valued random variables, \[ \Pr [X{\gt}\gamma N] \; =\; \Pr \big[X {\gt} 2\cdot \mathbb E[X]\big]\ \le \ \Pr \big[X{\gt}(1+1)\mathbb E[X]\big] \; \le \; e^{-\mathbb E[X]/3}\ \le \ e^{-\gamma N/6}. \] Since \)C_out\('s decoder \)D_out\( is only guaranteed to correct up to \)γ\( fraction of worst-case errors (Construction~ \ref{constr:c15-concatenated-scheme}(i)), Algorithm~ \ref{alg:c15-decoder} can only fail to recover \)m\( if \)X>γN\(, i.e.\ if the intermediate word \)y’\( has more than \)γN\( errors with respect to \)C_out(m)\(. Hence the overall decoding error probability is at most \)e^-γN/6\(, which, since \)γ\( and \)p\( are constants and \)k=Θ(n)\(, is \)2^-Ω(γN/n)\(. \)
15.3 The Inner Code
Fix
\(\)0≤p<12\( and \)0<ε<1-H(p)\(. For every large enough \)k\(, there exists a linear binary code of dimension \)k\( and rate at least \)1-H(p)-ε/2\( whose maximum-likelihood decoder has decoding error probability at most \)2^-Θ(ε^2 k)\( over \)BSC_p\(. Consequently, if \)k≥Ω\( for a parameter \)γ>0\(, there exists such a code with decoding error probability at most \)γ/2\(. \)
We find \(\)C_in\( satisfying Construction~ \ref{constr:c15-concatenated-scheme}(ii) by an exhaustive search, among all linear codes of dimension \)k\( and block length \)n\(, for one achieving the guarantee of Lemma~ \ref{lem:c15-inner-code-existence} with maximum-likelihood decoding as \)D_in\(. By Lemma~ \ref{lem:c15-inner-code-existence}, such a search succeeds as long as \[ \Omega \left(\frac{\log (1/\gamma )}{\varepsilon ^2}\right)\ \le \ k\ \le \ O(\log N), \] where the upper bound on \)k\( comes from the requirement (from Construction~ \ref{constr:c15-concatenated-scheme}(i)) that \)C_out\( have dimension \)K=Θ(N)\( over an alphabet of size \)2^k\( hence \)k=O(N)\( once we also fix \)k=Ω((1/γ)/ε^2)\(. \)
For \(\)C_in\( as in Construction~ \ref{constr:c15-inner-code}, the decoding algorithm \)D_in\( (maximum-likelihood decoding) runs in time \)T_in(k)=2^O(k)\(, and \)C_in\( can be constructed in time \)2^O(n^2)\(. \begin{proof} \uses{constr:c15-inner-code} The only known implementation of maximum-likelihood decoding for a general linear code enumerates all \end{proof}\)2^k\( codewords, taking time \)2^O(k)\(; this is \)T_in(k)\(. For the construction time: there are \)2^O(kn)\( candidate generator matrices to search over. For each candidate code, we must compute its decoding error probability, which requires checking, for each of the \)2^k\( possible transmitted codewords, whether maximum-likelihood decoding errs on each of the \)2^n\( possible received words (this takes time \)2^O(k)\( per received word by the previous paragraph, together with a polynomial-time computation of the probability with which that received word occurs given the transmitted codeword), and averaging; since \)k≤n\(, this is \)2^n+O(k)=2^O(n)\( time per codeword, hence \)2^k·2^O(n)=2^O(n)\( time per candidate code. Multiplying by the \)2^O(kn)=2^O(n^2)\( (using \)k=Θ(n)\() candidate generator matrices, the total construction time is \)2^O(n^2)·2^O(n)= 2^O(n^2)\(. \)
15.4 The Outer Code
We need an outer code \(\)C_out\( satisfying Construction~ \ref{constr:c15-concatenated-scheme}(i). Taking \)C_out\( to be a Reed--Solomon code over \)F_2^k\( decoded via error decoding gives a valid \)D_out\( running in time \)T_out(N)=O(N^3)\(; however, by Proposition~ \ref{prop:c15-inner-code-complexity}, the resulting construction time for \)C_in\( is \)2^O(n^2)\(, and since \)n=Θ(k)=Θ(N)\( this is \)2^O(^2 N)≤N^O(N)\(, which is not polynomial in \)N\(. We therefore instead take \)C_out\( to be defined over a smaller alphabet (no larger than \)2^O(N)\(), as follows. \)
15.4.1 Using a binary code as the outer code
Let \(\)C’⊆F_2^N’\( be a binary linear code with \)k∣N’\(, and suppose \)D’\( is a decoding algorithm for \)C’\( that, given any word within relative Hamming distance \)ρ\( of a codeword of \)C’\(, returns that codeword. Fix an \)F_2\(-linear bijection \)ϕ:F_2^kF_2^k\(, and let \)C_out⊆F_2^k^N\(, \)N=N’/k\(, be the code obtained from \)C’\( by grouping each consecutive block of \)k\( bits into a single symbol of \)F_2^k\( via \)ϕ\( (``folding''); \)C_out\( has the same rate as \)C’\(. Then there is a decoding algorithm \)D_out\( for \)C_out\(, running in the time of \)D’\( plus \)O(N)\(, such that, given any word within relative Hamming distance \)ρ\( (over \)F_2^k\() of a codeword of \)C_out\(, \)D_out\( returns that codeword. \begin{proof} \uses{def:c10-concatenation, def:c02-linear-code} Let \end{proof}\)yF_2^k^N\( be within relative Hamming distance \)ρ\( of some codeword \)cC_out\(, i.e.\ \)y\( and \)c\( disagree on at most \)ρN\( of their \)N\( symbols. Let \)D_out\( act by first ``unfolding'' \)y\( into \)y’F_2^N’\( (applying \)ϕ^-1\( to each symbol and concatenating the resulting \)k\(-bit strings), running \)D’\( on \)y’\( to obtain \)c’C’\(, and then folding \)c’\( back into a codeword of \)C_out\(. Let \)c’C’\( be the unfolding of \)c\(. Every symbol on which \)y\( and \)c\( agree unfolds to \)k\( bits on which the unfoldings \)y’\( and \)c’\( agree; hence each of the (at most \)ρN\() symbols on which \)y,c\( disagree contributes at most \)k\( of the bit-level disagreements between \)y’\( and \)c’\(, and every bit-level disagreement arises this way. Thus \[ \Delta (\mathbf y',\mathbf c')\ \le \ k\cdot \rho N\ =\ \rho N', \] i.e.\ \)y’\( is within relative Hamming distance \)ρ\( of \)c’C’\(. By the guarantee on \)D’\(, \)D’(y’)=c’\(, so \)D_out(y)\(, obtained by folding \)c’\(, equals \)c\(, as desired. The running time is that of \)D’\( plus the \)O(N)\( (equivalently \)O(N’)\() time to fold and unfold. \)
Let \(\)C’\( be an explicit binary linear code on the Zyablov bound (Theorem~ \ref{thm:c10-zyablov}) with outer rate \)R_1\( and inner rate \)r_1\( (in the sense of the Zyablov-bound concatenation), so that its design distance is \)δ’=(1-R_1)H^-1(1-r_1)\(, together with the GMD decoding algorithm, which corrects up to \)δ’/2\( fraction of worst-case errors in polynomial time. Set \[ k=\Theta \left(\frac{\log (1/\gamma )}{\varepsilon ^2}\right) \] (matching the requirement of Construction~ \ref{constr:c15-inner-code}), choose \)C’\( of block length \)N’=kN\(, and let \)C_out⊆F_2^k^N\( be the folding of \)C’\( given by Lemma~ \ref{lem:c15-folding}, with \)D_out\( the corresponding folded GMD decoder. We choose the parameters \)R_1,r_1\( of \)C’\( as follows: set \)1-R_1=2γ\( (so \)R_1=1-2γ\() and \)H^-1(1-r_1)= γ\(; then \)δ’=(1-R_1)H^-1(1-r_1)=2γ\(, so by Lemma~ \ref{lem:c15-folding}, \)D_out\( corrects \)δ’/2=γ\( fraction of worst-case errors over \)F_2^k\(, matching Construction~ \ref{constr:c15-concatenated-scheme}(i). \)
With \(\)γ=ε^3\(, the code \)C_out\( of Construction~ \ref{constr:c15-outer-code} has rate \[ R = R_1 r_1 = 1-O\Big(\sqrt\gamma \log \frac1\gamma \Big)\ \ge \ 1-\frac{\varepsilon }{2}, \] matching Construction~ \ref{constr:c15-concatenated-scheme}(i). \begin{proof} \uses{constr:c15-outer-code, def:c03-q-ary-entropy} Since \end{proof}\)H^-1(1-r_1)=γ\( and \)H\( is the (compositional) inverse of \)H^-1\( on the relevant range, \[ 1-r_1 = H(\sqrt\gamma ) = \sqrt\gamma \log _2\frac1{\sqrt\gamma } +(1-\sqrt\gamma )\log _2\frac1{1-\sqrt\gamma }. \] As \)γ0\(, \)_2=Θ(γ)\(, so \)(1-γ)_2=Θ(γ)\(, and \)γ_2=12γ_2\(. Hence \)1-r_1=O(γ(1/γ))\(, i.e. \)r_1=1-O(γ(1/γ))\(. Since \)R_1=1-2γ\( is also \)1-O(γ(1/γ))\(, \[ R=R_1r_1=\Big(1-O\big(\sqrt\gamma \log \tfrac 1\gamma \big)\Big)^2 =1-O\Big(\sqrt\gamma \log \frac1\gamma \Big). \] It remains to check \)O(γ(1/γ))≤ε/2\( when \)γ=ε^3\(: then \)γ=ε^3/2\( and \)(1/γ)=3(1/ε)\(, so \)γ(1/γ)=3ε^3/2(1/ε) =ε·3ε(1/ε)=o(ε)\( as \)ε0\( (since \)ε(1/ε)0\(), so this holds for small enough \)ε\(, and the hidden constant may be absorbed for all \)ε\( in range by adjusting the implicit constant in \)γ=Θ(ε^3)\(. \)
15.4.2 Wrapping Up
For every constant \(\)p\( and \)0<ε<1-H(p)\(, there exists a linear code \)C^*\( of block length \)N\( and rate at least \)1-H(p)- ε\(, such that \begin{enumerate} \item[(a)]\end{enumerate}\)C^*\( can be constructed in time \)poly(N)+ 2^O(ε^-5)\(; \item [(b)] \)C^*\( can be encoded in time \)O(N^2)\(; and \item [(c)] there exists a \)poly(N)+N·2^O(ε^-5)\( time decoding algorithm that has an error probability of at most \)2^-Ω(ε^6N)\( over the \)BSC_p\(. \)
Set
\(\)γ=ε^3\(, let \)C_in\( be as in Construction~ \ref{constr:c15-inner-code} and \)C_out\( as in Construction~ \ref{constr:c15-outer-code}, and let \)C^*=C_out○C_in\(. By Proposition~ \ref{prop:c15-rate-of-concatenation} and Proposition~ \ref{prop:c15-outer-code-rate} (which shows \)R≥1-ε/2\() together with Construction~ \ref{constr:c15-inner-code} (which shows \)r≥1-H(p)-ε/2\(), \)C^*\( has rate at least \)1-H(p)-ε\(. \emph{(a) Construction time.} With \)γ=ε^3\(, the parameter \)k\( of Construction~ \ref{constr:c15-inner-code} is \)k=Θ(1/γ)/ε^2=Θ(1/ ε)/ε^2\(, and since \)p\( is constant, \)n= Θ(k)\(. By Proposition~ \ref{prop:c15-inner-code-complexity}, \)C_in\( can be constructed in time \)2^O(n^2)=2^Oε^-4 ^2(1/ε)\(. Since for any constant \)a>0\(, \)ε^-a^O(1)(1/ε)=O(ε^-a-1)\( (applying this with \)a=4\(), this construction time is \)2^O(ε^-5)\(. The outer code \)C_out\( (Construction~ \ref{constr:c15-outer-code}) is constructed in time \)poly(N)=poly(N)\(, via Theorem~ \ref{thm:c10-zyablov} and Lemma~ \ref{lem:c15-folding}. Hence the overall construction time for \)C^*\( is \)poly(N)+ 2^O(ε^-5)\(. \emph{(b) Encoding time.} By Proposition~ \ref{prop:c15-encoding-decoding-time}, encoding \)C^*\( takes time \)O(N^2)\(. \emph{(c) Decoding time and error probability.} By Proposition~ \ref{prop:c15-inner-code-complexity}, \)T_in(k)=2^O(k)\(; since \)k≤n\(, \)2^O(k)≤2^O(n^2)=2^O(ε^-5)\( as computed above. By Proposition~ \ref{prop:c15-encoding-decoding-time} (using \)T_out(N)=poly(N)\(, which holds for the GMD-based \)D_out\( of Construction~ \ref{constr:c15-outer-code}), the decoding time is \)poly(N)+N·2^O(k)≤poly (N)+N·2^O(ε^-5)\(. For the error probability, by Proposition~ \ref{prop:c15-decoding-error-probability}, decoding fails with probability at most \)2^-Ω(γN/n)\(. Since \)γ= ε^3\( and \)n=Θε^-2(1/ε) \(, this exponent is \[ \Omega \left(\frac{\gamma N}{n}\right) = \Omega \left(\frac{\varepsilon ^3}{\varepsilon ^{-2}\log (1/\varepsilon )} \cdot \frac{N n}{n}\right) =\Omega \left(\frac{\varepsilon ^5}{\log (1/\varepsilon )}\cdot N\right) =\Omega \left(\frac{\varepsilon ^5}{\log (1/\varepsilon )}\cdot \frac{\mathcal N}{n}\right), \] and since \)ε^5/(1/ε)≥ε^6\( for all small enough \)ε\( (as \)ε(1/ε)0\(), and \)n=O(ε^-2(1/ε))=O(ε^-δ)\( for any \)δ>0\( can be absorbed into the \)Ω(·)\(, this gives a decoding error probability of at most \)2^-Ω(ε^6 N)\(. \)
15.5 Discussion
Theorem 342 resolves, in the affirmative, the question of whether the capacity of \(\)BSC_p\( can be achieved with efficient encoding and decoding algorithms However, the exponential dependence on \)1/ε\( in the decoding time complexity (part (c) of Theorem~ \ref{thm:c15-main}) is unsatisfying, raising the question of whether it can be brought down to \)poly(1/ ε)\(. We record an improvement to the outer-code component of the construction, due to Spielman, using \emph{expander codes}. \begin{thmenv}[Spielman's linear-time outer code, Theorem 15.5.1] \label{thm:c15-spielman-expander} \notready \uses{def:c11-expander-code} For every small enough \end{thmenv} \)β>0\(, there exists an explicit code \)C_out\( of rate \)\( and block length \)N\(, which can correct \)Ωβ^2()^2\( fraction of worst-case errors, and has \)O(N)\(-time encoding and decoding. \)
Using the code
\(\)C_out\( of Theorem~ \ref{thm:c15-spielman-expander} in place of the code of Construction~ \ref{constr:c15-outer-code}, with \)β=Θ(ε)\( and correspondingly \[ \gamma =\Theta \left(\frac{\varepsilon ^2}{\log ^2(1/\varepsilon )}\right), \] yields, by the same argument as in the proof of Theorem~ \ref{thm:c15-main}, a linear code \)C^*=C_out○C_in\( of rate at least \)1-H(p)-ε\( and block length \)N\(, with encoding and decoding time \)N·2^poly(1/ ε)\( and decoding error probability \)2^-Ω(γN/n)\( over \)BSC_p\(; moreover the outer-code component of the construction now has (strongly explicit) \)O(N)\(-time construction, encoding and decoding, in place of the \)poly(N)\(-, resp.\ \)O(N^3)\(-, time bounds used previously. This does not, however, remove the \)2^poly(1/ε)\(-time dependence coming from the brute-force construction and decoding of the inner code (Construction~ \ref{constr:c15-inner-code}, Proposition~ \ref{prop:c15-inner-code-complexity}), and so does not answer the question of decoding time \)poly(N,1/ε)\(. \begin{proof} \uses{thm:c15-spielman-expander, constr:c15-concatenated-scheme, constr:c15-inner-code, prop:c15-inner-code-complexity, prop:c15-decoding-error-probability, thm:c15-main} We need \end{proof}\)C_out\( to have rate \)≥1-ε/2\( (Construction~ \ref{constr:c15-concatenated-scheme}(i)); setting \)=1-ε/2\( gives \)β=Θ(ε)\(. By Theorem~ \ref{thm:c15-spielman-expander}, this \)C_out\( can then correct a \)γ=Ωβ^2/^2(1/β)= Ωε^2/^2(1/ε)\( fraction of worst-case errors in \)O(N)\( time, matching Construction~ \ref{constr:c15-concatenated-scheme}(i) with this choice of \)γ\(, and giving \)T_out(N)=O(N)\( in place of the \)poly(N)\(, resp.\ \)O(N^3)\(, bound of Construction~ \ref{constr:c15-outer-code}. Since \)(1/γ)= Θ((1/ε))\( (as \)γ=Θ(ε^2/ ^2(1/ε))\(), the required dimension \)k=Θ((1/ γ)/ε^2)=Θ((1/ε)/ε^2)\( for the inner code \)C_in\( (Construction~ \ref{constr:c15-inner-code}) is of the same asymptotic order as in the proof of Theorem~ \ref{thm:c15-main}, so by Proposition~ \ref{prop:c15-inner-code-complexity}, \)C_in\( still has construction and decoding time \)2^O(n^2)=2^poly(1/ ε)\(. Combining this \)T_in(k)=2^poly(1/ ε)\( with \)T_out(N)=O(N)\(, the overall decoding time \)N·T_in(k)+T_out(N)\( is \)N·2^poly(1/ ε)\(; the error probability \)2^-Ω(γN/n)\( follows exactly as in Proposition~ \ref{prop:c15-decoding-error-probability}. Since the exponential-in-\)1/ε\( term \)2^poly(1/ε)\( persists (it comes entirely from brute-force search for \)C_in\(, unaffected by the choice of \)C_out\(), this improvement to the outer-code time complexity does not yield \)poly(1/ ε)\( decoding time. \)