18 Fast Encoding: Linear Time Encodable Codes

18.1 Overview of the construction

Low-density parity check (LDPC) matrices lead to codes with very fast (linear-time) decoders, but the corresponding generator matrix is typically dense, so the naive encoding x ↦x ·G$ takes nearly quadratic time. This chapter constructs a code that is \emph{systematic} (the first $k$ coordinates of the codeword are the message, the rest are \emph{check bits}) and that is encodable and decodable in linear time. The construction is recursive: to encode $x F_2^k$ one first computes a low-density set of check bits $y_1$ via a low-density generator matrix; then one recursively protects $y_1$ using a smaller instance of the same construction, producing check bits $y_2$; finally one adds check bits $y_3$ that protect the pair $(y_1,y_2)$ using another low-density matrix. The key technical ingredient is an \emph{error-reduction} guarantee: if $y_3$ (and hence, inductively, $y_1,y_2$) is known up to a small number of errors, a decoding algorithm can shrink the number of errors in $(y_1,y_2)$ enough for the inductive step to recover $y_1$ completely, and this in turn lets one recover $x$ completely. We restrict attention to rate $1/4$ codes to keep the parameters simple; the resulting theorem is: \begin{thmenv}[Theorem 18.1.1] \label{thm:c18-rate-quarter} \uses{def:c18-Ck, lem:c18-encoding-time, lem:c18-decoding-time, lem:c18-linear-decode-correctness} There exist linear-time encodable and linear-time decodable binary codes of rate \end{thmenv} $1/4$. $

Theorem

Proof ▶

For each

k = 2^t$ let $C_k : F_2^k F_2^4k$ be the systematic code of Definition~ \ref{def:c18-Ck}. By construction $|C_k(x)| = 4k$ for a message of length $k$, so $C_k$ has rate $1/4$. By Lemma~ \ref{lem:c18-encoding-time} there is a constant $A$ with $T_E(k) ≤Ak$, i.e. $C_k$ is linear-time encodable. Let $β>0$ be the constant of Lemma~ \ref{lem:c18-error-reduction-guarantee}. By Lemma~ \ref{lem:c18-linear-decode-correctness}, the algorithm \textsc{Linear-Decode} corrects $βk$ errors on message length $k$, and by Lemma~ \ref{lem:c18-decoding-time} it runs in time $O(k)$. Hence $C_k$ is a linear-time decodable code (correcting the constant fraction $β/4$ of errors, since the codeword length is $4k$). Combining the three facts, ${C_k}_k=2^t$ is a family of linear-time encodable and linear-time decodable codes of rate $1/4$. $

Proof ▶

18.2 Low-density Error-Reduction Codes

As in Chapter 11, an n ×m$ matrix $G$ over $F_2$ may be viewed as a bipartite graph $B = ([n],[m],E)$ with $G_ij=1$ iff there is an edge from left vertex $i$ to right vertex $j$; under this identification, the product $x·G$ assigns to each right vertex $j$ the parity $_i N(j) x_i$ of its neighbors' labels, where $N(j) = {i [n] ∣(i,j) E}$. $

18.2.1 The Code

Construction 408 Expander graphs B_k

For integer t ≥0$ let $k = 2^t$ and $n=k$, $m=k/2$. Using the existence of good bipartite expanders with left-vertex set $[n]$, right-vertex set $[m]$, left degree $D$, and expansion parameter $ε= 1/8$, let $B_k$ denote the resulting bipartite graph: $B_k$ is a $(k,k/2,D,γ,(7/8)D)$-expander for $D=O(1)$ and $γ= Ω(1)$. We further assume that all right vertices of $B_k$ have degree $O(1)$ (this can always be arranged without loss of generality). $

Definition 409 Error-reduction code R_k

Given the graph B_k = ([k],[k/2],E)$ of Construction~ \ref{constr:c18-Bk}, define the \emph{error-reduction code} $R_k : F_2^k F_2^k/2$ by \[ R_k(\mathbf{x}) = \mathbf{y}, \qquad y_j = \bigoplus _{i \in N(j)} x_i \quad \text{for } j \in [k/2], \] where $N(j)$ denotes the neighborhood of right vertex $j$ in $B_k$. The associated systematic encoding is $R_k(x) = (x, R_k(x))$. This is a code of rate $2/3$, mapping $k$ message bits to $3k/2$ codeword bits, of which the first $k$ are the message bits and the remaining $k/2$ are check bits. $

18.2.2 Gen-Flip Algorithm

Algorithm 410 Gen-Flip, Algorithm 18.2.1

Input: a bipartite graph

B = ([n],[m],E)$ and vectors $x F_2^n$, $y F_2^m$. \textbf{Output:} $x F_2^n$. \begin{enumerate} \item \end{enumerate} $x ←x$. (We say $j [m]$ is \emph{satisfied} if $y_j = _i N(j) x_i$, and \emph{unsatisfied} otherwise.) \item While there exists $i [n]$ with more unsatisfied than satisfied neighbors in $N(i)$: flip $x_i$ and update the list of satisfied/unsatisfied vertices in $[m]$. \item Return $x$. $

Algorithm

18.2.3 Error-Reduction Guarantee

Lemma 411 Lemma 18.2.1

There exists

β>0$ such that for all $k=2^t$, for the error-reduction code $R_k$ and the algorithm \textsc{Gen-Flip}: for every $x,x F_2^k$ and $y,y F_2^k/2$ such that $y = R_k(x)$, $Δ(x,x) ≤βk$ and $Δ(y,y) ≤βk$, the output $x = Gen-Flip(B_k,x,y)$ satisfies \[ \Delta (\mathbf{x},\bar{\mathbf{x}}) \le \Delta (\mathbf{y},\hat{\mathbf{y}})/2 . \] $

Lemma

Proof ▶

Let

a = Δ(x,x)$ and $A = { i ∣x_i ≠x_i }$; let $b = Δ(y,y)$ and $B = { j ∣y_j ≠y_j }$. By hypothesis $a,b ≤βk$. Set \[ \beta = \frac{\gamma }{D+2} \] so that $a(D+1)+b ≤γk$, where $D$ is the (constant) degree of $B_k$ from Construction~ \ref{constr:c18-Bk}; we assume $D ≥8$. \textbf{Initial unsatisfied right nodes.} If $j N(A) ∪B$ then $y_j = y_j = _i N(j) x_i = _i N(j) x_i$, so $j$ is satisfied at the start of \textsc{Gen-Flip}. Hence the number of initially unsatisfied right nodes is at most $|N(A) ∪B| ≤aD + b$. \textbf{Bounding $\Delta (\mathbf{x},\bar{\mathbf{x}})$ at termination.} Initially $Δ(x,x) = a$, and each iteration of \textsc{Gen-Flip} changes at most one bit of $x$. The total number of iterations is at most the number of initially unsatisfied right nodes, since each iteration strictly decreases the number of unsatisfied right nodes by exactly one (a vertex $i$ is only flipped when strictly more than half of its neighbors are unsatisfied, and flipping it changes the status of exactly its $≤D$ neighbors, converting each formerly-unsatisfied neighbor to satisfied and vice versa, for a net decrease of at least one unsatisfied vertex). Hence at the end of the algorithm \[ \Delta (\mathbf{x},\bar{\mathbf{x}}) \le a + (aD+b) = a(D+1)+b \le \gamma k . \] \textbf{Unique-neighbor expansion argument.} Let $S = { i ∣x_i ≠x_i }$ at the end of \textsc{Gen-Flip}, so $|S| ≤a(D+1)+b ≤γk$, and let $T$ be the set of unsatisfied right vertices at termination. Let $U(S) = { j ∣|N(j) ∩S| = 1 }$ be the set of unique neighbors of $S$. By the unique-neighbor expansion property of $(k,k/2,D,γ,(7/8)D)$-expanders we have \[ |U(S)| \ge (1-2\varepsilon )D|S| = \frac{3D}{4}|S| \] (using $ε= 1/8$). Every vertex of $U(S) ∖B$ must be unsatisfied at termination, since it has a unique neighbor in $S$ (the bits $x_i$ differing from $x_i$) and $y_j = y_j$ for $j B$. Hence \[ |T| \ge |U(S) \setminus B| \ge \frac{3D}{4}|S| - b . \] On the other hand, at termination the total number of unsatisfied right vertices adjacent to $S$ must be less than $D2|S|$, or else, by averaging, some vertex of $S$ would have strictly more than $D/2$ unsatisfied neighbors among its $D$ neighbors, i.e. more unsatisfied than satisfied neighbors, contradicting that \textsc{Gen-Flip} has terminated. Thus $|T| ≤D2|S|$, and combining the two bounds, \[ \frac{3D}{4}|S| - b \le |T| \le \frac{D}{2}|S| . \] Rearranging, \[ |S| \le \frac{4b}{D} \le \frac{b}{2} \] using $D ≥8$. Since $Δ(x,x) = |S|$, this gives $Δ(x,x) ≤b/2 = Δ(y,y)/2$, as desired. $

Proof ▶

18.3 The error-correcting code: Recursive construction

Definition 412 Recursive codes C_k$, $C_k

For k=2^t$ we define codes $C_k : F_2^k F_2^3k$ inductively, with $|C_k(x)| = 4k$ (i.e. rate $1/4$). \emph{Base case.} There is a constant $k_0$ such that for all $k ≤k_0$, $C_k$ is chosen to be the check bits of an arbitrary systematic code of rate $1/4$ (of the fixed constant length $4k$). \emph{Inductive step.} Assume $C_k/2$ has been defined. For $x F_2^k$, define \[ C_k(\mathbf{x}) = (\mathbf{y}_1,\mathbf{y}_2,\mathbf{y}_3), \qquad \mathbf{y}_1 = R_k(\mathbf{x}), \quad \mathbf{y}_2 = C_{k/2}(\mathbf{y}_1), \quad \mathbf{y}_3 = R_{2k}(\mathbf{y}_1,\mathbf{y}_2). \] (Here $y_1 F_2^k/2$, $y_2 F_2^3k/2$, so $(y_1,y_2) F_2^2k$ is a valid input to $R_2k$, and $y_3 F_2^k$; thus $|C_k(x)| = k/2+3k/2+k = 3k$.) The final systematic code is $C_k(x) = (x, C_k(x))$. $

18.4 Analysis

We first analyze the encoding time, then describe and analyze the decoding algorithm; together these show the code corrects a constant fraction of errors in linear time, establishing Theorem 407.

18.4.1 Encoding Analysis

Lemma 413 R_k$ is linear-time computable$

There is a constant B$ such that for all $k$, $R_k(x)$ can be computed in time at most $Bk$ for $x F_2^k$. $

Proof ▶

By Construction 408, every right vertex of

B_k$ has degree $O(1)$, say at most $D’$. Computing $R_k(x)$ amounts to computing $y_j = _i N(j) x_i$ for each of the $k/2$ right vertices $j$, and each such computation takes $O(D’) = O(1)$ time. Hence the total time is $O(k/2) = O(k)$, i.e. at most $Bk$ for a suitable constant $B$. $

Proof ▶

Lemma 414 Linear encoding time

Let

T_E(k)$ denote the time to compute $C_k(x)$ for $x F_2^k$. There is a constant $A$ such that $T_E(k) ≤Ak$ for all $k$. $

Lemma

Proof ▶

For

k ≤k_0$ (a constant), $T_E(k)=O(1) ≤Ak$ once $A$ is chosen large enough (there are only finitely many such $k$). For the inductive step, computing $C_k(x)$ (Definition~ \ref{def:c18-Ck}) requires: computing $y_1 = R_k(x)$, which by Lemma~ \ref{lem:c18-Rk-linear-time} takes time at most $Bk$; recursively computing $y_2 = C_k/2(y_1)$, which takes time $T_E(k/2)$; and computing $y_3 = R_2k(y_1,y_2)$, which by Lemma~ \ref{lem:c18-Rk-linear-time} (applied with parameter $2k$ to the length-$2k$ input $(y_1,y_2)$) takes time at most $B(2k) = 2Bk$. Hence \[ T_E(k) \le Bk + T_E(k/2) + 2Bk = 3Bk + T_E(k/2). \tag {18.1} \] By induction on $k$, assume $T_E(k/2) ≤A(k/2)$. Then (18.1) gives \[ T_E(k) \le 3Bk + Ak/2 . \] Choosing $A ≥6B$ (so that $3Bk ≤Ak/2$) yields $T_E(k) ≤Ak/2 + Ak/2 = Ak$, completing the induction (with $A$ also chosen large enough to cover the finitely many base cases $k ≤k_0$). Hence $T_E(k) ≤Ak$ for a suitable constant $A$. $

Proof ▶

18.4.2 Decoding Algorithm

Algorithm 415 Linear-Decode, Algorithm 18.4.1

Input:

(x,y_1,y_2,y_3)$ where $x F_2^k$, $y_1 F_2^k/2$, $y_2 F_2^3k/2$ and $y_3 F_2^k$. \textbf{Output:} $x F_2^k$. \begin{enumerate} \item If \end{enumerate} $k ≤k_0$ then return $D_MLD(x,y_1,y_2,y_3)$ (the maximum-likelihood decoder for the constant-size code $C_k$). \item Set $(y_1,y_2) ←Gen-FlipB_2k, (y_1,y_2), y_3$. \item Set $(z_1,z_2) ←Linear-Decode(y_1,y_2)$ (a recursive call at message length $k/2$). \item Set $x ←Gen-Flip(B_k, x, z_1)$. \item Return $x$. $

Algorithm

18.4.3 Analysis of the decoder

Lemma 416 Gen-Flip is linear-time

For a graph

B$ on $O(k)$ vertices of maximum degree $O(1)$, $Gen-Flip(B,x,y)$ runs in time $O(k)$. $

Lemma

Proof ▶

As argued in the proof of Lemma 411, the number of iterations of the while loop of Gen-Flip is at most the number of initially unsatisfied right vertices, which is at most the number

m=O(k)$ of right vertices. Moreover each iteration can be implemented in $O(1)$ time: maintaining, for each left vertex $i$, a counter of unsatisfied neighbors (updated incrementally whenever a neighbor's satisfied/unsatisfied status flips) lets one find and process a vertex to flip in $O(1)$ amortized time, and flipping $x_i$ only changes the status of its $O(1)$ neighbors, each update taking $O(1)$ time. Hence the total running time is $O(k) ·O(1) = O(k)$. $

Proof ▶

Lemma 417 Linear decoding time

Let

T_D(k)$ denote the running time of $Linear-Decode$ on message length $k$. There is a constant $A’$ such that $T_D(k) ≤A’k$ for all $k$. $

Lemma

Proof ▶

For

k ≤k_0$ the algorithm runs $D_MLD$ on a fixed constant-size code, taking $O(1) ≤A’k$ time once $A’$ is large enough. For $k > k_0$, Step 2 runs \textsc{Gen-Flip} on the graph $B_2k$ (which by Construction~ \ref{constr:c18-Bk} has $O(1)$ maximum degree and $O(2k)$ vertices), taking time $O(2k) = O(k)$ by Lemma~ \ref{lem:c18-gen-flip-linear-time}. Step 3 makes one recursive call at message length $k/2$, taking time $T_D(k/2)$. Step 4 runs \textsc{Gen-Flip} on $B_k$, taking time $O(k)$ by Lemma~ \ref{lem:c18-gen-flip-linear-time}. Hence, mirroring the analysis of Lemma~ \ref{lem:c18-encoding-time}, \[ T_D(k) \le O(k) + T_D(k/2) + O(k) = Ck + T_D(k/2) \] for some constant $C$, and by the same inductive argument as in Lemma~ \ref{lem:c18-encoding-time} (verifying $Ck+A’k/2 ≤A’k$ whenever $A’ ≥2C$, and choosing $A’$ large enough for the base cases), we get $T_D(k) ≤A’k$ for a suitable constant $A’$. $

Proof ▶

Lemma 418 Base case of Linear-Decode

Let

β>0$ be the constant of Lemma~ \ref{lem:c18-error-reduction-guarantee}. For $k ≤k_0$, if $Δ(x,y_1,y_2,y_3),C_k(x) ≤βk$ then $Linear-Decode$ outputs $x$. $

Lemma

Proof ▶

Lemma 419 Lemma 18.4.1

Let

β> 0$ be the constant from Lemma~ \ref{lem:c18-error-reduction-guarantee}. The algorithm \textsc{Linear-Decode} corrects $βk$ errors for codes of message length $k$: specifically, on input $(x,y_1,y_2,y_3)$ such that $Δ(x,y_1,y_2,y_3),C_k(x) ≤βk$, \textsc{Linear-Decode} outputs $x$. $

Lemma

Proof ▶

We induct on

k$. The base case $k ≤k_0$ is Lemma~ \ref{lem:c18-linear-decode-base-case}. For the inductive step, let $(y_1,y_2,y_3) = C_k(x)$. Since $Δ(x,y_1,y_2,y_3),C_k(x) ≤βk$, we have in particular $Δ(y_1,y_2),(y_1,y_2) ≤βk$ and $Δ(y_3,y_3) ≤βk$. Recall $y_3 = R_2k(y_1,y_2)$, so applying Lemma~ \ref{lem:c18-error-reduction-guarantee} with parameter $2k$ (in place of $k$), the output $(y_1,y_2) = Gen-Flip(B_2k,(y_1,y_2),y_3)$ of Step 2 satisfies \[ \Delta \big((\mathbf{y}_1,\mathbf{y}_2),(\bar{\mathbf{y}}_1,\bar{\mathbf{y}}_2)\big) \le \Delta (\mathbf{y}_3,\hat{\mathbf{y}}_3)/2 \le \beta k /2 . \] Now consider Step 3. By the inductive hypothesis (applied at message length $k/2$, with error bound $β(k/2)$), since $Δ(y_1,y_2),(y_1,y_2) ≤βk /2$, the call $Linear-Decode(y_1,y_2)$ outputs $z_1,z_2$ with $z_1 = y_1$ and $z_2 = y_2$ (recalling $C_k/2(y_1) = y_2$, i.e. $(y_1,y_2)$ is a valid codeword pair for the recursive instance). Finally, in Step 4 we have $Δ(x,x) ≤βk$ (another consequence of $Δ(x,y_1,y_2,y_3),C_k(x) ≤βk$), and $y_1 = R_k(x)$, so applying Lemma~ \ref{lem:c18-error-reduction-guarantee} once more (at parameter $k$) with $y = z_1 = y_1$ exactly (so $Δ(y_1,z_1)=0$), the output $x = Gen-Flip(B_k,x,z_1)$ of Step 4 satisfies \[ \Delta (\mathbf{x},\bar{\mathbf{x}}) \le \Delta (\mathbf{y}_1,\mathbf{z}_1)/2 = 0, \] i.e. $x = x$. Hence \textsc{Linear-Decode} correctly decodes from $βk$ errors. $

Proof ▶