page_title: Zemor's decoding algorithm
section_title: Code construction
hierarchical_section_title: Zemor's decoding algorithm / Code construction
caption_attribution_description: English: The figure shows the graph G and code C.
context_page_description: 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
context_section_description: 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 the set of 2 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 eigen value of adjacency matrix of . Here the largest eigen value is . 
  Two important claims are made:
caption: Graph G and code C
exif: {}