Expander code: Difference between revisions

Revision as of 21:27, 23 October 2011

Revision as of 21:31, 23 October 2011

Line 13:

}}

In [[coding theory]], '''expander codes''' are a type of [[linear block code]] whichthat arises by using [[bipartite]] [[expander graph]]s. Along with [[concatenated codes]], expander codes are interesting since they can construct [[binary]] codes (codes using just 0 and 1) with constant positive [[Block_code#The_rate_R|rate]] and relative [[Block_code#The_distance_d|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 codes==

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

==Definition==