Expander code
Encyclopedia
In coding theory
Coding theory
Coding theory is the study of the properties of codes and their fitness for a specific application. Codes are used for data compression, cryptography, error-correction and more recently also for network coding...

, expander codes are a type of linear block code that arises by using bipartite
Bipartite
Bipartite means having two parts, or an agreement between two parties. More specifically, it may refer to any of the following:-Mathematics:* 2 * bipartite graph* bipartite cubic, a type of cubic function-Medicine:...

 expander graph
Expander graph
In combinatorics, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion as described below...

s. Along with concatenated codes, expander codes are interesting since they can construct binary
Binary
- Mathematics :* Binary numeral system, a representation for numbers using only two digits * Binary function, a function in mathematics that takes two arguments- Computing :* Binary file, composed of something other than human-readable text...

 codes (codes using just 0 and 1) with constant positive rate and relative distance. Furthermore, expander codes can be both encoded and decoded in time proportional to the block length of the code. In fact, expander codes are the only known asymptotically good codes which can be both encoded and decoded from a constant fraction of errors in polynomial time.

This article is based on Dr. Venkatesan Guruswami's course notes .

Expander codes

In coding theory
Coding theory
Coding theory is the study of the properties of codes and their fitness for a specific application. Codes are used for data compression, cryptography, error-correction and more recently also for network coding...

, an expander code is a linear block code whose parity check matrix is the adjacency matrix of a bipartite expander graph
Expander graph
In combinatorics, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion as described below...

. These codes have good relative distance (, where and are properties of the expander graph as defined later), rate (), and decodability (algorithms of running time exist).

Definition

Consider a bipartite graph
Bipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...

 , where and are the vertex sets and is the set of edges connecting vertices in to vertices of . Suppose every vertex in has degree
Degree (mathematics)
In mathematics, there are several meanings of degree depending on the subject.- Unit of angle :A degree , usually denoted by ° , is a measurement of a plane angle, representing 1⁄360 of a turn...

(the graph is -regular), , and , . Then is a expander graph if every small enough subset , has the property that has at least distinct neighbors in . Note that this holds trivially for . When and for a constant , we say that is a lossless expander.

Since is a bipartite graph, we may consider its adjacency matrix. Then the linear code generated by viewing the transpose of this matrix as a parity check matrix is an expander code.

It has been shown that nontrivial lossless expander graphs exist. Moreover, we can explicitly construct them.

Rate

The rate of is its dimension divided by its block length. In this case, the parity check matrix has size , and hence has dimension at least .

Distance

Suppose . Then the distance of a expander code is at least .

Proof

Note that we can consider every codeword in as a subset of vertices , by saying that vertex if and only if the th index of the codeword is a 1. Then is a codeword iff every vertex is adjacent to an even number of vertices in . (In order to be a codeword, , where is the parity check matrix. Then, each vertex in corresponds to each column of . Matrix multiplication over then gives the desired result.) So, if a vertex is adjacent to a single vertex in , we know immediately that is not a codeword. Let denote the neighbors in of , and denote those neighbors of which are unique, i.e., adjacent to a single vertex of .
Lemma 1

For every of size , .
Proof

Trivially, , since implies . follows since the degree of every vertex in is . By the expansion property of the graph, there must be a set of edges which go to distinct vertices. The remaining edges make at most neighbors not unique, so .
Corollary

Every sufficiently small has a unique neighbor. This follows since .
Lemma 2

Every subset with has a unique neighbor.
Proof

Lemma 1 proves the case , so suppose . Let such that . By Lemma 1, we know that . Then a vertex is in iff , and we know that , so by the first part of Lemma 1, we know . Since , , and hence is not empty.
Corollary

Note that if a has at least 1 unique neighbor, i.e. , then the corresponding word corresponding to cannot be a codeword, as it will not multiply to the all zeros vector by the parity check matrix. By the previous argument, . Since is linear, we conclude that has distance at least .

Encoding

The encoding time for an expander code is upper bounded by that of a general linear code - by matrix multiplication. A result due to Spielman shows that encoding is possible in time.

Decoding

Decoding of expander codes is possible in time when using the following algorithm.

Let be the vertex of that corresponds to the th index in the codewords of . Let be a received word, and . Let be is even, and be is odd. Then consider the greedy algorithm:
----
Input: received codeword .

intialize y' to y
while there is a v in R adjacent to an odd number of vertices in V(y')
if there is an i such that o(i) > e(i)
flip entry i in y'
else
fail

Output: fail, or modified codeword .
----

Correctness

We must show that the algorithm terminates with the correct codeword when the received codeword is within half the code's distance of the original codeword. Let the set of corrupt variables be , , and the set of unsatisfied (adjacent to an odd number of vertices) vertices in be . The following lemma will prove useful.
Lemma 3

If , then there is a with .
Proof

By Lemma 1, we know that . So an average vertex has at least unique neighbors (recall unique neighbors are unsatisfied and hence contribute to ), since , and thus there is a vertex with .

So, if we have not yet reached a codeword, then there will always be some vertex to flip. Next, we show that the number of errors can never increase beyond .
Lemma 4

If we start with , then we never reach at any point in the algorithm.
Proof

When we flip a vertex , and are interchanged, and since we had , this means the number of unsatisfied vertices on the right decreases by at least one after each flip. Since , the initial number of unsatisfied vertices is at most , by the graph's -regularity. If we reached a string with errors, then by Lemma 1, there would be at least unique neighbors, which means there would be at least unsatisfied vertices, a contradiction.

Lemmas 3 and 4 show us that if we start with (half the distance of ), then we will always find a vertex to flip. Each flip reduces the number of unsatisfied vertices in by at least 1, and hence the algorithm terminates in at most steps, and it terminates at some codeword, by Lemma 3. (Were it not at a codeword, there would be some vertex to flip). Lemma 4 shows us that we can never be farther than away from the correct codeword. Since the code has distance (since ), the codeword it terminates on must be the correct codeword, since the number of bit flips is less than half the distance (so we couldn't have traveled far enough to reach any other codeword).

Complexity

We now show that the algorithm can achieve linear time decoding. Let be constant, and be the maximum degree of any vertex in . Note that is also constant for known constructions.
  1. Pre-processing: It takes time to compute whether each vertex in has an odd or even number of neighbors.
  2. Pre-processing 2: We take time to compute a list of vertices in which have .
  3. Each Iteration: We simply remove the first list element. To update the list of odd / even vertices in , we need only update entries, inserting / removing as necessary. We then update entries in the list of vertices in with more odd than even neighbors, inserting / removing as necessary. Thus each iteration takes time.
  4. As argued above, the total number of iterations is at most .


This gives a total runtime of time, where and are constants.
The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK