Content deleted Content added
sp |
Citation bot (talk | contribs) m Alter: isbn. Add: citeseerx. Removed parameters. | You can use this bot yourself. Report bugs here. | User-activated. |
||
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://dl.acm.org/citation.cfm?id=510003 |editor= |title=STOC '02 Proceedings of the thirty-fourth annual ACM symposium on Theory of computing |publisher=ACM |___location= |year=2002 |isbn=978-1-58113-495-
==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 |pages=1723–31 |year=1996 |doi=10.1109/18.556668 |url=|citeseerx=10.1.1.47.2736 }}</ref>
==Decoding==
Line 115:
==Notes==
This article is based on Dr. Venkatesan Guruswami's course notes.<ref>{{cite web |first=V. |last=Guruswami |title=Lecture 13: Expander Codes |date=15 November 2006 |work=CSE 533: Error-Correcting |publisher=University of Washington |url=http://www.cs.washington.edu/education/courses/cse533/06au/lecnotes/lecture13.pdf
{{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
{{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>
| |||