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.