Zemor's decoding algorithm. In coding theory, Zemor's algorithm, designed and developed by Gilles Zemor, is a recursive low-complexity approach to code construction.  It is an improvement over the algorithm of Sipser and Spielman.

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

Code construction 

Zemor's algorithm is based on a type of expander graphs called Tanner graph. The construction of code was first proposed by Tanner. The codes are based on double cover , regular expander , which is a bipartite graph.  =, where  is the set of vertices and  is the set of edges and  =    and    = , where  and  denotes sets of vertices. Let  be the number of vertices in each group, i.e, . The edge set  be of size  = and every edge in  has one endpoint in both  and .  denotes the set of edges containing .

Assume an ordering on , therefore ordering will be done on every edges of  for every . Let finite field , and for a word   in , let the subword of the  word will be indexed by . Let that word be denoted by . The subset of vertices  and  induces every word  a partition into  non-overlapping sub-words , where  ranges over the elements of . 
For constructing a code , consider a linear subcode , which is a  code, where , the size of the alphabet is . For any vertex , let  be some ordering of the  vertices of  adjacent to . In this code, each bit  is linked with an edge  of .

We can define the code  to be the set of binary vectors  of  such that, for every vertex  of ,  is a code word of . In this case, we can consider a special case when every edge of  is adjacent to exactly  vertices of . It means that  and  make up, respectively, the vertex set and edge set of  regular graph .

Let us call the code  constructed in this way as  code. For a given graph  and a given code , there are several  codes as there are different ways of ordering edges incident to a given vertex , i.e., . In fact our code  consist of all codewords such that  for all . The code  is linear  in  as it is generated from a subcode , which is linear. The code  is defined as  for every .

In this figure, . It shows the graph  and code .

In matrix , let  is equal to the second largest eigenvalue of adjacency matrix of . Here the largest eigenvalue is . 
Two important claims are made:

Claim 1 

. Let  be the rate of a linear code constructed from a bipartite graph whose digit nodes have degree  and whose subcode nodes have degree . If a single linear code with parameters  and rate  is associated with each of the subcode nodes, then .

Proof 
Let  be the rate of the linear code, which is equal to 
Let there are  subcode nodes in the graph. If the degree of the subcode is , then the code must have  digits, as each digit node is connected to  of the  edges in the graph. Each subcode node contributes  equations to parity check matrix for a total of . These equations may not be linearly independent. 
Therefore, 

, Since the value of , i.e., the digit node of this bipartite graph is  and here , we can write as:

Claim 2 

 
  

If  is linear code of rate , block code length , and minimum relative distance , and if  is the edge vertex incidence graph of a  – regular graph with second largest eigenvalue , then the code  has rate at least  and minimum relative distance at least .

 Proof 
Let  be derived from the  regular graph . So, the number of variables of  is  and the number of constraints is . According to Alon - Chung, if  is a subset of vertices of  of size , then the number of edges contained in the subgraph is induced by  in  is at most .

As a result, any set of  variables will be having at least  constraints as neighbours. So the average number of variables per constraint is : 
           

So if , then a word of relative weight  , cannot be a codeword of . The inequality  is satisfied for . Therefore,  cannot have a non zero codeword of relative weight    or less.

In matrix , we can assume that  is bounded away from . For those values of  in which  is odd prime, there are explicit constructions of sequences of  - regular bipartite graphs with arbitrarily large number of vertices such that each graph  in the sequence is a  Ramanujan graph. It is called Ramanujan graph as it satisfies the inequality . Certain expansion properties are visible in graph  as the separation between the eigenvalues  and . If the graph  is Ramanujan graph, then that expression   will become  eventually as  becomes large.

 Zemor's algorithm 

The iterative decoding algorithm written below alternates between the vertices  and  in  and corrects the codeword of  in  and then it switches to correct the codeword  in . Here edges associated with a vertex on one side of a graph are not incident to other vertex on that side. In fact, it doesn't matter in which order, the set of nodes  and  are processed. The vertex processing can also be done in parallel.

The decoder  stands for a decoder for  that recovers correctly with any codewords with less than  errors.

 Decoder algorithm 

Received word :  
For   to  do         // is the number of iterations
{ if ( is odd)                                       // Here the algorithm will alternate between its two vertex sets.

else      
Iteration : For every , let  // Decoding  to its nearest codeword.
}
Output: 

 Explanation of the algorithm 

Since  is bipartite, the set  of vertices induces the partition of the edge set  =  . The set  induces another partition,  =  .

Let  be the received vector, and recall that . The first iteration of the algorithm consists of applying the complete decoding for the code induced by  for every  . This means that for replacing, for every , the vector  by one of the closest codewords of . Since the subsets of edges  are disjoint for , the decoding of these   subvectors of  may be done in parallel.

The iteration will yield a new vector . The next iteration consists of applying the preceding procedure to  but with  replaced by . 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  and to the subvectors induced by the vertices of . 
Note: [If  and  is the complete bipartite graph, then  is a product code of  with itself and the above algorithm reduces to the natural hard iterative decoding of product codes].

Here, the number of iterations,  is . 
In general, the above algorithm can correct a code word whose Hamming weight is no more than  for values of . Here, the decoding algorithm is implemented as a circuit of size  and depth  that returns the codeword given that error vector has weight less than  .

 Theorem If  is a Ramanujan graph of sufficiently high degree, for any , the decoding algorithm can correct  errors, in  rounds ( where the big-  notation hides a dependence on ). This can be implemented in linear time on a single processor; on  processors each round can be implemented in constant time.''

Proof 

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 . The set of edges which has an incorrect value while decoding is considered. Here by incorrect value, we mean  in any of the bits. Let  be the initial value of the codeword,  be the values after first, second . . .  stages of decoding. 
Here, , and  .  Here  corresponds to those set of vertices that was not able to successfully decode their codeword in the  round. From the above algorithm   as number of unsuccessful vertices will be corrected in every iteration. We can prove that  is a decreasing sequence.
In fact, . As we are assuming, , the above equation is in a geometric decreasing sequence. 
So, when , more than  rounds are necessary. Furthermore, , and if we implement the  round in  time, then the total sequential running time will be linear.

Drawbacks of Zemor's algorithm 
 It is lengthy process as the number of iterations  in decoder algorithm takes is 
 Zemor's decoding algorithm finds it difficult to decode erasures. A detailed way of how we can improve the algorithm is
given in.

See also

Expander codes
Tanner graph
Linear time encoding and decoding of error-correcting codes

References

Coding theory
Error detection and correction