Zemor's decoding algorithm

In coding theory, Zemor's algorithm, designed and developed by Gilles Zemor,[1] is a recursive low-complexity approach to code construction.

Zemor considered a typical class of Sipser–Spielman construction of expander codes, where the underlying graph is bipartite graph.

Sipser and Spielman introduced a constructive family of asymptotically good linear-error codes together with a simple parallel algorithm that will always remove a constant fraction of errors.

The article is based on Dr. Venkatesan Guruswami's course notes [2] Zemor's algorithm is based on a type of expander graphs called Tanner graph.

codes as there are different ways of ordering edges incident to a given vertex

is equal to the second largest eigenvalue of adjacency matrix of

be the rate of a linear code constructed from a bipartite graph whose digit nodes have degree

equations to parity check matrix for a total of

, then the number of edges contained in the subgraph is induced by

is odd prime, there are explicit constructions of sequences of

It is called Ramanujan graph as it satisfies the inequality

The iterative decoding algorithm written below alternates between the vertices

In fact, it doesn't matter in which order, the set of nodes

is odd) // Here the algorithm will alternate between its two vertex sets.

of vertices induces the partition of the edge set

The first iteration of the algorithm consists of applying the complete decoding for the code induced by

The next iteration consists of applying the preceding procedure to

In other words, it consists of decoding all the subvectors induced by the vertices of

The coming iterations repeat those two steps alternately applying parallel decoding to the subvectors induced by the vertices of

with itself and the above algorithm reduces to the natural hard iterative decoding of product codes].

In general, the above algorithm can correct a code word whose Hamming weight is no more than

Here, the decoding algorithm is implemented as a circuit of size

that returns the codeword given that error vector has weight less than

is a Ramanujan graph of sufficiently high degree, for any

This can be implemented in linear time on a single processor; on

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.

The set of edges which has an incorrect value while decoding is considered.

corresponds to those set of vertices that was not able to successfully decode their codeword in the

as number of unsuccessful vertices will be corrected in every iteration.