14 Decoding Concatenated Codes
In this chapter we study the question of decoding concatenated codes up to half their design distance. Recall that the concatenated code \(\)C_out ○C_in\( (Definition \ref{def:c10-concatenation}) consists of an outer \)[N,K,D]_Q=q^k\( code \)C_out\( and an inner \)[n,k,d]_q\( code \)C_in\(, where \)Q = O(N)\(; the resulting code has design distance \)Dd\(. We begin with a natural unique decoding algorithm that corrects up to \)Dd/4\( errors, and then develop the Generalized Minimum Distance (GMD) decoder, which decodes up to \)Dd/2\( errors. \)
14.1 A Natural Decoding Algorithm
We begin with a natural decoding algorithm for concatenated codes that “reverses” the encoding process: it first decodes the inner code (on each of the \(\)N\( blocks) and then decodes the outer code on the resulting vector of inner messages. \begin{thmenv}[Assumption for Section 14.1] \label{assumption:c14-outer-decoder} For the time being, assume that we have a polynomial time unique decoding algorithm \end{thmenv} \)D_C_out : [q^k]^N [q^k]^K\( for the outer code \)C_out\( that can correct up to \)D/2\( errors. \uses{def:c10-concatenation, def:c01-min-distance} \)
This leaves us with the task of coming up with a polynomial time decoding algorithm for the inner code. Since the running time only needs to be polynomial in the final block length, it suffices to use a decoding algorithm that runs in time singly exponential in the inner block length, as long as the inner block length is logarithmic in the outer code block length (which is the case for the codes on the Zyablov bound ). Thus we may use the Maximum Likelihood Decoder (MLD) for the inner code, which we denote \(\)D_C_in\(. \)
Input: Received word \(\)y = (y_1,…,y_N) [q^n]^N\(. \textbf{Output:} Message \)m’ [q^k]^K\(. \begin{enumerate} \item Compute \end{enumerate} \)y’ ←(y_1’,…,y_N’) [q^k]^N\( where \)C_in(y_i’) = D_C_in(y_i)\( for \)1 ≤i ≤N\( (i.e. \)y_i’\( is the message decoded by MLD on the \)i\(-th inner block). \item \)m’ ←D_C_out(y’)\(. \item Return \)m’\(. \)
Step 1 runs in time \(\)O(nq^k)\(, which, for \)k = O(N)\( and constant rate inner code, is \)(nN)^O(1)\( time; Step 2 runs in polynomial time by Assumption \ref{assumption:c14-outer-decoder}. Hence Algorithm \ref{alg:c14-natural-decoder} runs in polynomial time (in the final block length). \)
\(\)< \( many errors. \begin{proof} \uses{def:c01-hamming-distance} Let \end{proof}\)m\( be the (unique) message such that \)ΔC_out ○C_in(m), y < \(. We begin by defining a \emph{bad event} at position \)1 ≤i ≤N\(: a bad event occurs at \)i\( if \)y_i ≠C_in(C_out(m)_i)\(. More precisely, define the set of all bad events to be \[ \mathcal{B} = \{ i \mid y_i \ne C_{\mathrm{in}}(C_{\mathrm{out}}(\mathbf{m})_i) \} . \] Note that if \)|B| < D/2\(, then \)y’\( computed in Step 1 agrees with \)C_out(m)\( in more than \)N - D/2\( positions, so the decoder in Step 2 will output \)m\(. Thus, to complete the proof, we only need to show \)|B| < D/2\(. To do this, we define a superset \)B’ ⊇B\( and argue that \)|B’| < D/2\(. Note that if \)Δy_i, C_in(C_out(m)_i) < d/2\( then \)i B\( (by the proof of Proposition 1.4.2, i.e. by correctness of MLD as a unique decoder for \)C_in\() --- though the converse need not hold. We define \)B’\( by \)i B’\( if and only if \[ \Delta \big(y_i, C_{\mathrm{in}}(C_{\mathrm{out}}(\mathbf{m})_i)\big) \ge \frac{d}{2}. \] By the observation above, \)B ⊆B’\(. Now, by definition of \)B’\(, the total number of errors in \)y\( (relative to \)C_out ○C_in(m)\() is at least \)|B’| ·\(. If \)|B’| ≥D/2\( this total would be at least \) · = \(, contradicting \)ΔC_out ○C_in(m), y < \(. Thus \)|B’| < D/2\(, and hence \)|B| < D/2\(, which completes the proof. \)
Algorithm 318 (and the proof of Proposition 319) can easily be adapted to the case where the inner codes vary from block to block, e.g. for Justesen codes .
There exists an explicit linear code on the Zyablov bound that can be decoded up to a fourth of the Zyablov bound in polynomial time.
By Theorem 206 there is an explicit linear code
\(\)C_out ○C_in\( on the Zyablov bound with design distance \)Dd\(, obtained by concatenating a Reed-Solomon outer code with a suitable inner code. Theorem \ref{thm:c14-zyablov-half} already exhibits a polynomial time algorithm decoding this (or a similarly constructed) explicit Zyablov-bound code up to \)Dd/2\( errors, which in particular decodes up to \)Dd/4\( errors. Alternatively, and more directly, Proposition \ref{prop:c14-natural-decoder-correct} shows that Algorithm \ref{alg:c14-natural-decoder} run with \)D_C_out\( instantiated as the polynomial time Reed-Solomon unique decoder of Theorem \ref{thm:c14-rs-unique-decode} corrects up to \)Dd/4\( errors in polynomial time on the outer code block length, which (using \)k = O(N)\( for the inner code) is polynomial in the final block length. Either way, the claimed explicit code and decoding algorithm exist. \)
This is predicated on the existence of a polynomial time unique decoder for the outer code (Assumption 317); getting rid of this assumption (e.g. for Reed-Solomon outer codes) is answered by the material of Section 14.3 below (see Theorem 330 and Algorithm 329).
14.2 Decoding From Errors and Erasures
We digress from decoding concatenated codes to discuss decoding Reed-Solomon codes from a combination of errors and erasures; this will be used as the outer decoder in the Generalized Minimum Distance decoder of Section 14.3 (Algorithm 324).
An
\(\)[N,K]_q\( Reed-Solomon code can be corrected from \)e\( errors (or \)s\( erasures) as long as \)e < \( (or \)s < N - K + 1\() in \)O(N^3)\( time. \begin{proof} \end{proof} \)
An
\(\)[N,K]_q\( Reed-Solomon code can be corrected from \)e\( errors and \)s\( erasures in \)O(N^3)\( time as long as \begin{equation} 2e + s {\lt} N - K + 1. \label{eq:c14-ee-condition} \end{equation} \begin{proof} \uses{thm:c14-rs-unique-decode} Given a received word \end{proof}\)y (F_q ∪{?})^N\( with \)s\( erasures and \)e\( errors, let \)y’\( be the sub-vector obtained by deleting the erased positions, so \)y’ F_q^N-s\( is a valid received word for an \)[N-s,K]_q\( Reed-Solomon code (whose evaluation points are the evaluation points of the original code at the positions where an erasure did not occur). Run the error-decoding algorithm from Theorem \ref{thm:c14-rs-unique-decode} on \)y’\(. It can correct \)e\( errors as long as \[ e {\lt} \frac{(N-s) - K + 1}{2}, \] which is implied by \eqref{eq:c14-ee-condition}. Thus, we have corrected the \)e\( errors (recovering the codeword restricted to the non-erased positions). It remains to correct the \)s\( erasures under \eqref{eq:c14-ee-condition}. Let \)z’\( be the output of the error-decoding step above. Extend \)z’\( to \)z (F_q ∪{?})^N\( in the natural way, by re-inserting \)?\( at the erased positions. Finally, run the erasure-decoding algorithm from Theorem \ref{thm:c14-rs-unique-decode} on \)z\(. This succeeds as long as \)s < N - K + 1\(, which in turn holds by \eqref{eq:c14-ee-condition}. The time complexity of the overall algorithm is \)O(N^3)\(, since both algorithms invoked from Theorem \ref{thm:c14-rs-unique-decode} can be implemented in cubic time. \)
We will use this errors-and-erasures decoding algorithm to design decoding algorithms for certain concatenated codes that can be decoded up to half their design distance, i.e. up to \(\)Dd/2\(. \)
14.3 Generalized Minimum Distance Decoding
Recall the natural decoding algorithm for concatenated codes, Algorithm 318: it performs MLD on the inner code and then feeds the resulting vector to a unique decoder for the outer code. A drawback of this algorithm is that it does not exploit the extra information that MLD provides – for example, it does not distinguish between the case where a given inner received word has Hamming distance one from the closest inner codeword versus the case where it has Hamming distance (almost) \(\)d/2\( from the closest codeword. The Generalized Minimum Distance (GMD) decoder exploits precisely this extra information. \begin{thmenv}[Assumption for Section 14.3] \label{assumption:c14-gmd-setup} \uses{def:c10-concatenation, def:c01-min-distance} Throughout this section, \end{thmenv} \)C_out\( is an \)[N,K,D]_q^k\( code that can be decoded (by an algorithm \)D_C_out\() from \)e\( errors and \)s\( erasures in polynomial time whenever \)2e + s < D\(. Further, \)C_in\( is an \)[n,k,d]_q\( code with \)k = O(N)\(, equipped with a unique decoder \)D_C_in\(, which we take to be the MLD implementation. \)
We consider three versions of the GMD decoding algorithm. The first two are randomized algorithms; the last is a deterministic algorithm obtained from the second by derandomization.
14.3.1 GMD algorithm – I
Input: Received word
\(\)y = (y_1,…,y_N) [q^n]^N\(. \textbf{Output:} Message \)m’ [q^k]^K\(. \begin{enumerate} \item For \end{enumerate} \)1 ≤i ≤N\(: \begin{enumerate} \item \end{enumerate}\)y_i’ ←D_C_in(y_i)\(. \item \)w_i ← Δ(y_i’, y_i), d2 \(. \item With probability \)2w_id\(, set \)y_i” ← ?\(; otherwise set \)y_i” ←x\(, where \)y_i’ = C_in(x)\(. \)
\(\)m’ ←D_C_out(y”)\(, where \)y” = (y_1”,…,y_N”)\(. \item Return \)m’\(. \)
Let
\(\)y\( be a received word such that there exists a codeword \)C_out ○C_in(m) = (c_1,…,c_N) [q^n]^N\( with \)Δ(C_out ○C_in(m), y) < \(. Further, if \)y”\( (as computed by Algorithm \ref{alg:c14-gmd-v1}) has \)e’\( errors and \)s’\( erasures when compared with \)C_out ○C_in(m)\(, then \[ \mathbb {E}[2e' + s'] {\lt} D. \] \begin{proof} For \end{proof}\)1 ≤i ≤N\( define \)e_i = Δ(y_i, c_i)\(. Then \begin{equation} \sum _{i=1}^N e_i {\lt} \frac{Dd}{2}. \label{eq:c14-lem1-hyp} \end{equation} For \)1 ≤i ≤N\( define indicator variables \[ X_i^? = \mathbb {1}_{y_i'' = \, ?}, \qquad X_i^e = \mathbb {1}_{C_{\mathrm{in}}(y_i'') \ne c_i \text{ and } y_i'' \ne \, ?}. \] We claim it suffices to show that for every \)1 ≤i ≤N\(, \begin{equation} \mathbb {E}[2X_i^e + X_i^?] \le \frac{2e_i}{d}. \label{eq:c14-lem1-perpos} \end{equation} Indeed, by definition \)e’ = ∑_i X_i^e\( and \)s’ = ∑_i X_i^?\(, so by linearity of expectation, \[ \mathbb {E}[2e' + s'] \le \frac{2}{d} \sum _i e_i {\lt} D, \] where the last inequality follows from \eqref{eq:c14-lem1-hyp}. We now prove \eqref{eq:c14-lem1-perpos} by a case analysis. Fix \)1 ≤i ≤N\(. \textbf{Case 1} ( \)c_i = y_i’\(): If \)y_i” ≠ ?\( then, since \)c_i = y_i’\(, we have \)X_i^e = 0\(. Together with \)[y_i” = ?] = \(, this gives \[ \mathbb {E}[X_i^?] = \Pr [X_i^? = 1] = \frac{2w_i}{d}, \qquad \mathbb {E}[X_i^e] = \Pr [X_i^e = 1] = 0. \] Further, by definition, \[ w_i = \min \Big(\Delta (y_i', y_i), \frac{d}{2}\Big) \le \Delta (y_i', y_i) = \Delta (c_i, y_i) = e_i. \] These three relations give \eqref{eq:c14-lem1-perpos} in this case. \textbf{Case 2} ( \)c_i ≠y_i’\(): As in Case 1, \)E[X_i^?] = \(. If an erasure is not declared at position \)i\(, then \)X_i^e = 1\(, so \[ \mathbb {E}[X_i^e] = \Pr [X_i^e = 1] = 1 - \frac{2w_i}{d}. \] We claim \begin{equation} e_i + w_i \ge d, \label{eq:c14-lem1-case2} \end{equation} which gives \[ \mathbb {E}[2X_i^e + X_i^?] = 2 - \frac{2w_i}{d} \le \frac{2e_i}{d}, \] as desired. We prove \eqref{eq:c14-lem1-case2} by a further case split. \emph{Case 2.1} ( \)w_i = Δ(y_i’,y_i) < d/2\(): By definition of \)e_i\(, the triangle inequality, and \)Δ(c_i,y_i’) ≥d\( (since \)C_in\( has minimum distance \)d\( and \)c_i ≠y_i’\(), \[ e_i + w_i = \Delta (y_i,c_i) + \Delta (y_i',y_i) \ge \Delta (c_i,y_i') \ge d. \] \emph{Case 2.2} ( \)w_i = d/2 ≤Δ(y_i’,y_i)\(): Since \)y_i’\( is obtained from MLD, \)Δ(y_i’,y_i) ≤Δ(c_i,y_i)\(. Combined with the case hypothesis \)Δ(y_i’,y_i) ≥d/2\(, this gives \[ e_i = \Delta (c_i,y_i) \ge \Delta (y_i',y_i) \ge \frac{d}{2}, \] hence \)e_i + w_i ≥d\(, as desired. This proves \eqref{eq:c14-lem1-case2} and hence \eqref{eq:c14-lem1-perpos} in Case 2, completing the proof. \)
Note that if \(\)2e’ + s’ < D\(, then by Theorem \ref{thm:c14-rs-errors-erasures} (instantiated as \)D_C_out\( in Assumption \ref{assumption:c14-gmd-setup}), Algorithm \ref{alg:c14-gmd-v1} will output \)m\(. Lemma \ref{lem:c14-gmd-v1-expectation} says that this holds in expectation. \)
14.3.2 GMD Algorithm – II
Step 1(c) of Algorithm 324 uses fresh randomness for each \(\)i\(. We now consider a version that uses the \emph{same} randomness for every \)i\(. \begin{thmenv}[Generalized Minimum Decoder (ver 2), Algorithm 14.3.2] \label{alg:c14-gmd-v2} \uses{assumption:c14-gmd-setup} \textbf{Input:} Received word \end{thmenv} \)y = (y_1,…,y_N) [q^n]^N\(. \textbf{Output:} Message \)m’ [q^k]^K\(. \begin{enumerate} \item Pick \end{enumerate} \)θ[0,1]\( uniformly at random. \item For \)1 ≤i ≤N\(: \begin{enumerate} \item \end{enumerate}\)y_i’ ←D_C_in(y_i)\(. \item \)w_i ← Δ(y_i’, y_i), d2 \(. \item If \)θ< 2w_id\(, set \)y_i” ← ?\(; otherwise set \)y_i” ←x\(, where \)y_i’ = C_in(x)\(. \)
\(\)m’ ←D_C_out(y”)\(, where \)y” = (y_1”,…,y_N”)\(. \item Return \)m’\(. \)
Let
\(\)y\( be a received word such that there exists a codeword \)C_out ○C_in(m) = (c_1,…,c_N) [q^n]^N\( with \)Δ(C_out ○C_in(m), y) < \(. Further, if \)y”\( (as computed by Algorithm \ref{alg:c14-gmd-v2}) has \)e’\( errors and \)s’\( erasures when compared with \)C_out ○C_in(m)\(, then \[ \mathbb {E}_\theta [2e' + s'] {\lt} D. \] \begin{proof} \uses{lem:c14-gmd-v1-expectation} In the proof of Lemma \ref{lem:c14-gmd-v1-expectation}, the only property of the randomness used was \[ \Pr [y_i'' = \, ?] = \frac{2w_i}{d}. \] In Algorithm \ref{alg:c14-gmd-v2}, since \end{proof}\)θ\( is uniform on \)[0,1]\(, \[ \Pr [y_i'' = \, ?] = \Pr \Big[\theta \in \Big[0, \frac{2w_i}{d}\Big]\Big] = \frac{2w_i}{d}, \] exactly as before. Since the case analysis establishing \eqref{eq:c14-lem1-perpos} (Cases 1, 2.1, 2.2 in the proof of Lemma \ref{lem:c14-gmd-v1-expectation}) depends only on this value of \)[y_i” = ?]\(, on the definitions of \)e_i\(, \)w_i\(, \)X_i^e\(, \)X_i^?\(, and on the properties of \)C_in\( and MLD (which are unchanged), that entire argument applies verbatim here, giving \[ \mathbb {E}_\theta [2X_i^e + X_i^?] \le \frac{2e_i}{d} \] for every \)1 ≤i ≤N\(. Summing over \)i\( and using linearity of expectation as in the proof of Lemma \ref{lem:c14-gmd-v1-expectation} yields \)E_θ[2e’+s’] < D\(. \)
We next see that Algorithm 326 can be easily derandomized.
14.3.3 Derandomized GMD algorithm
Under the hypotheses of Lemma 327, there exists a value \(\)θ^* [0,1]\( such that Algorithm \ref{alg:c14-gmd-v2} run with \)θ\( fixed to \)θ^*\( in Step 1 produces \)y”\( with \)2e’ + s’ < D\( (and hence, by Theorem \ref{thm:c14-rs-errors-erasures} as instantiated for \)D_C_out\(, correctly outputs \)m\(). \begin{proof} \uses{lem:c14-gmd-v2-expectation} By Lemma \ref{lem:c14-gmd-v2-expectation}, \end{proof}\)E_θ[2e’+s’] < D\( where the expectation is over \)θ\( chosen uniformly in \)[0,1]\(. If every \)θ[0,1]\( produced \)2e’(θ) + s’(θ) ≥D\(, then the expectation would be at least \)D\(, a contradiction. Hence there exists \)θ^* [0,1]\( with \)2e’(θ^*) + s’(θ^*) < D\(. \)
Such a \(\)θ^*\( could in principle be found by exhaustive search, but there are uncountably many choices of \)θ[0,1]\(. This is resolved by the following discretization trick. Define \)Q = {0,1} ∪{ 2w_1d, …, 2w_Nd }\(. Because \)w_i = (Δ(y_i’,y_i), d/2)\( for each \)i\(, we have \)Q = {0,1} ∪{q_1,…,q_m}\( where \)q_1 < q_2 < < q_m\( for some \)m ≤d/2 \(. For every \)θ\( in a common interval \)[q_i,q_i+1)\(, Algorithm \ref{alg:c14-gmd-v2} (just before its final step) computes the same vector \)y”\(, since the erasure/non-erasure decision at position \)i\( depends only on which side of the threshold \)2w_i/d\( the value \)θ\( falls. Hence it suffices to cycle through all values \)θQ\(. \begin{thmenv}[Deterministic Generalized Minimum Decoder, Algorithm 14.3.3] \label{alg:c14-gmd-derandomized} \uses{assumption:c14-gmd-setup, cor:c14-exists-good-theta} \textbf{Input:} Received word \end{thmenv} \)y = (y_1,…,y_N) [q^n]^N\(. \textbf{Output:} Message \)m’ [q^k]^K\(. \begin{enumerate} \item For \end{enumerate} \)1 ≤i ≤N\(: \begin{enumerate} \item \end{enumerate}\)y_i’ ←D_C_in(y_i)\(. \item \)w_i ← Δ(y_i’, y_i), d2 \(. \)
\(\)Q ←{ 2w_1d, …, 2w_Nd } ∪{0,1}\(. \item For \)θQ\(: \begin{enumerate} \item For \end{enumerate}\)1 ≤i ≤N\(: if \)θ< 2w_id\(, set \)y_i” ← ?\(; otherwise set \)y_i” ←x\(, where \)y_i’ = C_in(x)\(. \item \)m_θ’ ←D_C_out(y”)\(, where \)y” = (y_1”,…,y_N”)\(. \)
Return \(\)m’_θ^*\( for \)θ^* = _θQ ΔC_out ○C_in(m’_θ), y\(. \)
Algorithm 329 is Algorithm 326 repeated \(\)|Q|\( times. Since \)|Q| = O(n)\(, this implies Algorithm \ref{alg:c14-gmd-derandomized} runs in polynomial time. \)
For every constant rate, there exists an explicit linear binary code on the Zyablov bound. Further, the code can be decoded up to half of the Zyablov bound in polynomial time.
By Theorem 206, for every constant rate there is an explicit concatenated linear code
\(\)C_out ○C_in\( on the Zyablov bound, with design distance \)Dd\(, obtained by taking \)C_out\( to be a Reed-Solomon code and \)C_in\( a (constant-rate) small-alphabet inner code with \)k = O(N)\(; this matches Assumption \ref{assumption:c14-gmd-setup}, with \)D_C_out\( the polynomial time errors-and-erasures decoder of Theorem \ref{thm:c14-rs-errors-erasures} for the Reed-Solomon outer code (correcting whenever \)2e+s < D\(). Given a received word \)y\( with \)Δ(C_out ○C_in(m), y) < \( for some message \)m\(, Corollary \ref{cor:c14-exists-good-theta} guarantees a value \)θ^* [0,1]\( (which, by the discretization argument, lies in the finite set \)Q\( used by Algorithm \ref{alg:c14-gmd-derandomized}) for which fixing \)θ= θ^*\( yields \)y”\( with \)2e’ + s’ < D\(, so that \)D_C_out(y”) = m\(. Since Algorithm \ref{alg:c14-gmd-derandomized} tries every \)θQ\( and outputs the candidate \)m_θ’\( minimizing \)Δ(C_out ○C_in(m_θ’), y)\(, and \)m\( is the unique message within distance \)Dd/2\( of \)y\( (as \)Dd\( is the design/minimum distance of \)C_out ○C_in\(), Algorithm \ref{alg:c14-gmd-derandomized} correctly outputs \)m\(. Algorithm \ref{alg:c14-gmd-derandomized} runs in polynomial time (it repeats the polynomial-time Algorithm \ref{alg:c14-gmd-v2} body \)|Q| = O(n)\( times), completing the proof. \)
This answers, in the affirmative, the question of whether concatenated codes on the Zyablov bound can be uniquely decoded up to half their design distance in polynomial time.