Expander code: Difference between revisions

Revision as of 21:03, 7 February 2013

Revision as of 22:04, 1 March 2013

Line 14:

}}

In [[coding theory]], '''expander codes''' form a class of [[Error detection and correction|error-correcting codes]] that are constructed from [[Bipartite graph|bipartite]] [[expander graph]]s.

Along with [[Justesen code]]s, expander codes are of particular interest since they have a constant positive [[Block_code#The_rate_R|rate]], a constant positive relative [[Block_code#The_distance_d|distance]], and a constant [[Block_code#The_alphabet_.CE.A3|alphabet size]].

In fact, the alphabet contains only two elements, so expander codes belong to the class of [[Binary code|binary codes]].

Line 24:

==Definition==

Consider a [[bipartite graph]] <math>G(L,R,E)\,</math>, where <math>L\,</math> and <math>R\,</math> are the vertex sets and <math>E\,</math> is the set of edges connecting vertices in <math>L\,</math> to vertices of <math>R\,</math>. Suppose every vertex in <math>L\,</math> has [[degree (mathematicsgraph theory)|degree]] <math>d\,</math> (the graph is <math>d\,</math>-[[Regular graph|regular]]), <math>|L|=n\,</math>, and <math>|R|=m\,</math>, <math>m < n\,</math>. Then <math>G\,</math> is a <math>(N, M, d, \gamma, \alpha)\,</math> expander graph if every small enough subset <math>S \subset L\,</math>, <math>|S| \leq \gamma n\,</math> has the property that <math>S\,</math> has at least <math>d\alpha|S|\,</math> distinct neighbors in <math>R\,</math>. Note that this holds trivially for <math>\gamma \leq \tfrac{1}{n}\,</math>. When <math>\tfrac{1}{n} < \gamma \leq 1\,</math> and <math>\alpha = 1 - \varepsilon\,</math> for a constant <math>\varepsilon\,</math>, we say that <math>G\,</math> is a lossless expander.

Since <math>G\,</math> is a bipartite graph, we may consider its <math>n \times m\,</math> adjacency matrix. Then the linear code <math>C\,</math> generated by viewing the transpose of this matrix as a parity check matrix is an expander code.