Content deleted Content added
m wikilinks for distance, rate, and linear block code |
m Fix links to disambiguation page Binary |
||
Line 13:
}}
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.
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>.
| |||