Expander code: Difference between revisions

Revision as of 07:49, 28 September 2020

Revision as of 23:35, 14 December 2020

Line 27:

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 |chapterurlchapter-url=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-7 |pages=659–668 |doi=10.1145/509907.510003}}</ref>

==Rate==

Line 57:

==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==