Expander code: Difference between revisions

Revision as of 18:59, 3 May 2011

Revision as of 03:20, 4 May 2011

Line 1:

In [[coding theory]], '''expander codes''' are a type of [[linear code]] which arises by using [[bipartite]] [[expander graphsgraph]]s. Along with [[concatenated codes]], expander codes are interesting since they can construct [[binary]] 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 <ref name="vg1">[http://www.cs.washington.edu/education/courses/cse533/06au/lecnotes/lecture13.pdf Washington's course notes]</ref><ref name="vg2">[http://www.cs.cmu.edu/~venkatg/teaching/codingtheory/notes/notes8.pdf CMU's course notes]</ref><ref name="vg3">[http://portal.acm.org/citation.cfm?id=1027924 Guest column: error-correcting codes and expander graphs]</ref>.

==Expander Codescodes==

In [[coding theory]], an expander code is a <math>[n,n-m]_2\,</math> [[linear code]] whose parity check matrix is the adjacency matrix of a bipartite [[expander graph]]. These codes have good relative [[distance]] (<math>2(1-\varepsilon)\gamma\,</math>, where <math>\varepsilon\,</math> and <math>\gamma\,</math> are properties of the expander graph as defined later), [[rate]] (<math>1-\tfrac{m}{n}\,</math>), and decodability (algorithms of running time <math>O(n)\,</math> exist).

Line 90:

This gives a total runtime of <math>O(mdr) = O(n)\,</math> time, where <math>d\,</math> and <math>r\,</math> are constants.

==See Alsoalso==

* [[Expander graph]]

* [[Low-density parity-check code]]