Expander code: Difference between revisions

Revision as of 12:24, 2 September 2013

Revision as of 00:08, 7 August 2015

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 thirythirty-fourth annual 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==