Expander code: Difference between revisions

Revision as of 08:14, 3 May 2013

Revision as of 12:24, 2 September 2013

Line 28:

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.

It has been shown that nontrivial lossless expander graphs exist. Moreover, we can explicitly construct them.<ref name="lossless">[{{cite book |first1=M. |last1=Capalbo |first2=O. |last2=Reingold |first3=S. |last3=Vadhan |first4=A. |last4=Wigderson |chapter=Randomness conductors and constant-degree lossless expanders |chapterurl=http://portaldl.acm.org/citation.cfm?id=510003 Randomness|editor= conductors|title=STOC and'02 constantProceedings of the thiry-degreefourth losslessannual expanders]ACM symposium on Theory of computing |publisher=ACM |___location= |year=2002 |isbn=1-58113-495-9 |pages=659–668 |url= |doi=10.1145/509907.510003}}</ref>

==Rate==

Line 58:

==Encoding==

The encoding time for an expander code is upper bounded by that of a general linear code - <math>O(n^2)\,</math> by matrix multiplication. A result due to Spielman shows that encoding is possible in <math>O(n)\,</math> time.<ref name="spielman">{{cite journal |first=D. |last=Spielman. |title=Linear-time encodable and decodable error-correcting codes. |journal=IEEE Transactions on Information Theory, |volume=42( |issue=6):1723–1732, |pages=1723–31 |year=1996 |doi=10.1109/18.556668 |url=}}</ref>

==Decoding==

Line 115:

==Notes==

This article is based on Dr. Venkatesan Guruswami's course notes.<ref>{{cite nameweb |first=V. |last=Guruswami |title=Lecture 13: Expander Codes |date=15 November 2006 |work=CSE 533: Error-Correcting |publisher=University of Washington |url="vg1">[http://www.cs.washington.edu/education/courses/cse533/06au/lecnotes/lecture13.pdf Washington's course notes]</ref><ref name|format="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]PDF}}<br/ref>

{{cite web |first=V. |last=Guruswami |title=Notes 8: Expander Codes and their decoding |date=March 2010 |work=Introduction to Coding Theory |publisher=Carnegie Mellon University |url=http://www.cs.cmu.edu/~venkatg/teaching/codingtheory/notes/notes8.pdf |format=PDF}}<br/>

{{cite journal |first=V. |last=Guruswami |title=Guest column: error-correcting codes and expander graphs |journal=ACM SIGACT News |volume=35 |issue=3 |pages=25–41 |date=September 2004 |doi=10.1145/1027914.1027924 |url=http://dl.acm.org/citation.cfm?id=1027924}}</ref>

==References==