Expander code: Difference between revisions

Revision as of 04:59, 21 July 2012

Revision as of 21:03, 7 February 2013

Line 1:

{{cleanup|reason=Missing definitions, and grammar requirerequires heavy copy-editing. Blindly pointing to the references shoultshould not be the point of the article. Missing scholarly exposition.|date=July 2012}}

{{infobox code

| name = Expander codes

| image = [[File:Tanner_graph_example.PNG|300px]]

| image_caption = bipartite expander graph

| namesake =

| type = [[Linear block code]]

Line 14:

}}

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

In [[coding theory]], '''expander codes''' are a type of [[linear block code]] that arises by using [[bipartite]] [[expander graph]]s. Along with [[concatenated codes]], expander codes are interesting since they can construct [[Binary code|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. [[File:Tanner_graph_example.PNG|thumb]]

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]].

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>

Furthermore, expander codes can be both encoded and decoded in time proportional to the block length of the code.

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.

==Expander codes==

Line 110 ⟶ 112:

* Linear time encoding and decoding of error-correcting codes

* ABNNR and AEL codes

==Notes==

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>

==References==