Zemor's decoding algorithm

${\displaystyle \left({\dfrac {K}{N}}\right)\geq 2r_{o}-1}$
. Let ${\displaystyle R}$ be the rate of a linear code constructed from a bipartite graph whose digit nodes have degree ${\displaystyle m}$ and whose subcode nodes have degree ${\displaystyle n}$. If a single linear code with parameters ${\displaystyle \left(n,k\right)}$ and rate ${\displaystyle r=\left({\dfrac {k}{n}}\right)}$ is associated with each of the subcode nodes, then ${\displaystyle k\geq 1-\left(1-r\right)m}$.

Let ${\displaystyle R}$ be the rate of the linear code, which is equal to ${\displaystyle K/N}$ Let there are ${\displaystyle S}$ subcode nodes in the graph. If the degree of the subcode is ${\displaystyle n}$, then the code must have ${\displaystyle \left({\dfrac {n}{m}}\right)S}$ digits, as each digit node is connected to ${\displaystyle m}$ of the ${\displaystyle \left(n\right)S}$ edges in the graph. Each subcode node contributes ${\displaystyle (n-k)}$ equations to parity check matrix for a total of ${\displaystyle \left(n-k\right)S}$. These equations may not be linearly independent. Therefore, ${\displaystyle \left({\dfrac {K}{N}}\right)\geq \left({\dfrac {({\dfrac {n}{m}})S-(n-k)S}{({\dfrac {n}{m}})S}}\right)}$
${\displaystyle \geq 1-m\left({\dfrac {n-k}{n}}\right)}$
${\displaystyle \geq 1-m\left(1-r\right)}$, Since the value of ${\displaystyle m}$, i.e., the digit node of this bipartite graph is ${\displaystyle 2}$ and here ${\displaystyle r=r_{o}}$, we can write as:
${\displaystyle \left({\dfrac {K}{N}}\right)\geq 2r_{o}-1}$

${\displaystyle D\geq N\left({\dfrac {(\delta -({\dfrac {\lambda }{d}}))}{(1-({\dfrac {\lambda }{d}})}})\right)^{2}}$

${\displaystyle =N\left(\delta ^{2}-O\left({\dfrac {\lambda }{d}}\right)\right)}$ ${\displaystyle \rightarrow (1)}$

If ${\displaystyle S}$ is linear code of rate ${\displaystyle r}$, block code length ${\displaystyle d}$, and minimum relative distance ${\displaystyle \delta }$, and if ${\displaystyle B}$ is the edge vertex incidence graph of a ${\displaystyle d}$ – regular graph with second largest eigenvalue ${\displaystyle \lambda }$, then the code ${\displaystyle C(B,S)}$ has rate at least ${\displaystyle 2r_{o}-1}$ and minimum relative distance at least ${\displaystyle \left(\left({\dfrac {\delta -\left({\dfrac {\lambda }{d}}\right)}{1-\left({\dfrac {\lambda }{d}}\right)}}\right)\right)^{2}}$.

Let ${\displaystyle B}$ be derived from the ${\displaystyle d}$ regular graph ${\displaystyle G}$. So, the number of variables of ${\displaystyle C(B,S)}$ is ${\displaystyle \left({\dfrac {dn}{2}}\right)}$ and the number of constraints is ${\displaystyle n}$. According to Alon - Chung,[4] if ${\displaystyle X}$ is a subset of vertices of ${\displaystyle G}$ of size ${\displaystyle \gamma n}$, then the number of edges contained in the subgraph is induced by ${\displaystyle X}$ in ${\displaystyle G}$ is at most ${\displaystyle \left({\dfrac {dn}{2}}\right)\left(\gamma ^{2}+({\dfrac {\lambda }{d}})\gamma \left(1-\gamma \right)\right)}$.

As a result, any set of ${\displaystyle \left({\dfrac {dn}{2}}\right)\left(\gamma ^{2}+\left({\dfrac {\lambda }{d}}\right)\gamma \left(1-\gamma \right)\right)}$ variables will be having at least ${\displaystyle \gamma n}$ constraints as neighbours. So the average number of variables per constraint is : ${\displaystyle \left({\dfrac {({\dfrac {2nd}{2}})\left(\gamma ^{2}+({\dfrac {\lambda }{d}})\gamma \left(1-\gamma \right)\right)}{\gamma n}}\right)}$ ${\displaystyle =d\left(\gamma +({\dfrac {\lambda }{d}})\left(1-\gamma \right)\right)}$ ${\displaystyle \rightarrow (2)}$

So if ${\displaystyle d\left(\gamma +({\dfrac {\lambda }{d}})\left(1-\gamma \right)\right)<\gamma d}$, then a word of relative weight ${\displaystyle \left(\gamma ^{2}+({\dfrac {\lambda }{d}})\gamma \left(1-\gamma \right)\right)}$, cannot be a codeword of ${\displaystyle C(B,S)}$. The inequality ${\displaystyle (2)}$ is satisfied for ${\displaystyle \gamma <\left({\dfrac {1-({\dfrac {\lambda }{d}})}{\delta -({\dfrac {\lambda }{d}})}}\right)}$. Therefore, ${\displaystyle C(B,S)}$ cannot have a non zero codeword of relative weight ${\displaystyle \left({\dfrac {\delta -({\dfrac {\lambda }{d}})}{1-({\dfrac {\lambda }{d}})}}\right)^{2}}$ or less.

In matrix ${\displaystyle G}$, we can assume that ${\displaystyle \lambda /d}$ is bounded away from ${\displaystyle 1}$. For those values of ${\displaystyle d}$ in which ${\displaystyle d-1}$ is odd prime, there are explicit constructions of sequences of ${\displaystyle d}$ - regular bipartite graphs with arbitrarily large number of vertices such that each graph ${\displaystyle G}$ in the sequence is a Ramanujan graph. It is called Ramanujan graph as it satisfies the inequality ${\displaystyle \lambda (G)\leq 2{\sqrt {d-1}}}$. Certain expansion properties are visible in graph ${\displaystyle G}$ as the separation between the eigenvalues ${\displaystyle d}$ and ${\displaystyle \lambda }$. If the graph ${\displaystyle G}$ is Ramanujan graph, then that expression ${\displaystyle (1)}$ will become ${\displaystyle 0}$ eventually as ${\displaystyle d}$ becomes large.

Received word : ${\displaystyle w=(w_{e}),e\in E}$
${\displaystyle z\leftarrow w}$
For ${\displaystyle t\leftarrow 1}$ to ${\displaystyle m}$ do //${\displaystyle m}$ is the number of iterations
{ if (${\displaystyle t}$ is odd) // Here the algorithm will alternate between its two vertex sets.
${\displaystyle X\leftarrow A}$
else ${\displaystyle X\leftarrow B}$
Iteration ${\displaystyle t}$: For every ${\displaystyle v\in X}$, let ${\displaystyle (z)_{v}\leftarrow \mathbb {D} ((z)_{v})}$ // Decoding ${\displaystyle z_{v}}$ to its nearest codeword.
}
Output: ${\displaystyle z}$

Since ${\displaystyle G}$ is bipartite, the set ${\displaystyle A}$ of vertices induces the partition of the edge set ${\displaystyle E}$ = ${\displaystyle \cup _{v\in A}E_{v}}$ . The set ${\displaystyle B}$ induces another partition, ${\displaystyle E}$ = ${\displaystyle \cup _{v\in B}E_{v}}$ .

Let ${\displaystyle w\in \{0,1\}^{N}}$ be the received vector, and recall that ${\displaystyle N=dn}$. The first iteration of the algorithm consists of applying the complete decoding for the code induced by ${\displaystyle E_{v}}$ for every ${\displaystyle v\in A}$ . This means that for replacing, for every ${\displaystyle v\in A}$, the vector ${\displaystyle \left(w_{v(1)},w_{v(2)},\ldots ,w_{v(d)}\right)}$ by one of the closest codewords of ${\displaystyle C_{o}}$. Since the subsets of edges ${\displaystyle E_{v}}$ are disjoint for ${\displaystyle v\in A}$, the decoding of these ${\displaystyle n}$ subvectors of ${\displaystyle w}$ may be done in parallel.

The iteration will yield a new vector ${\displaystyle z}$. The next iteration consists of applying the preceding procedure to ${\displaystyle z}$ but with ${\displaystyle A}$ replaced by ${\displaystyle B}$. In other words, it consists of decoding all the subvectors induced by the vertices of ${\displaystyle B}$. The coming iterations repeat those two steps alternately applying parallel decoding to the subvectors induced by the vertices of ${\displaystyle A}$ and to the subvectors induced by the vertices of ${\displaystyle B}$.
Note: [If ${\displaystyle d=n}$ and ${\displaystyle G}$ is the complete bipartite graph, then ${\displaystyle C}$ is a product code of ${\displaystyle C_{o}}$ with itself and the above algorithm reduces to the natural hard iterative decoding of product codes].

Here, the number of iterations, ${\displaystyle m}$ is ${\displaystyle \left({\dfrac {(\log {n})}{\log(2-\alpha )}}\right)}$. In general, the above algorithm can correct a code word whose Hamming weight is no more than ${\displaystyle ({\dfrac {1}{2}}).\alpha N\delta \left(({\dfrac {\delta }{2}})-({\dfrac {\lambda }{d}})\right)=\left(({\dfrac {1}{4}}).\alpha N(\delta ^{2}-O({\dfrac {\lambda }{d}})\right)}$ for values of ${\displaystyle \alpha <1}$. Here, the decoding algorithm is implemented as a circuit of size ${\displaystyle O(N\log {N})}$ and depth ${\displaystyle O(\log {N})}$ that returns the codeword given that error vector has weight less than ${\displaystyle \alpha N\delta ^{2}(1-\epsilon )/4}$ .

If ${\displaystyle G}$ is a Ramanujan graph of sufficiently high degree, for any ${\displaystyle \alpha <1}$, the decoding algorithm can correct ${\displaystyle ({\dfrac {\alpha \delta _{o}^{2}}{4}})(1-\in )N}$ errors, in ${\displaystyle O(\log {n})}$ rounds ( where the big- ${\displaystyle O}$ notation hides a dependence on ${\displaystyle \alpha }$). This can be implemented in linear time on a single processor; on ${\displaystyle n}$ processors each round can be implemented in constant time.

Since the decoding algorithm is insensitive to the value of the edges and by linearity, we can assume that the transmitted codeword is the all zeros - vector. Let the received codeword be ${\displaystyle w}$. The set of edges which has an incorrect value while decoding is considered. Here by incorrect value, we mean ${\displaystyle 1}$ in any of the bits. Let ${\displaystyle w=w^{0}}$ be the initial value of the codeword, ${\displaystyle w^{1},w^{2},\ldots ,w^{t}}$ be the values after first, second . . . ${\displaystyle t}$ stages of decoding. Here, ${\displaystyle X^{i}={e\in E|x_{e}^{i}=1}}$, and ${\displaystyle S^{i}={v\in V^{i}|E_{v}\cap X^{i+1}!=\emptyset }}$. Here ${\displaystyle S^{i}}$ corresponds to those set of vertices that was not able to successfully decode their codeword in the ${\displaystyle i^{th}}$ round. From the above algorithm ${\displaystyle S^{1}<S^{0}}$ as number of unsuccessful vertices will be corrected in every iteration. We can prove that ${\displaystyle S^{0}>S^{1}>S^{2}>\cdots }$is a decreasing sequence. In fact, ${\displaystyle |S_{i+1}|<=({\dfrac {1}{2-\alpha }})|S_{i}|}$. As we are assuming, ${\displaystyle \alpha <1}$, the above equation is in a geometric decreasing sequence. So, when ${\displaystyle |S_{i}|<n}$, more than ${\displaystyle log_{2-\alpha }n}$ rounds are necessary. Furthermore, ${\displaystyle \sum |S_{i}|=n\sum ({\dfrac {1}{(2-\alpha )^{i}}})=O(n)}$, and if we implement the ${\displaystyle i^{th}}$ round in ${\displaystyle O(|S_{i}|)}$ time, then the total sequential running time will be linear.