Content deleted Content added
TartarTorte (talk | contribs) m clean up, CheckWiki 26 |
Citation bot (talk | contribs) Add: s2cid, pages, issue, volume, journal, year, title, authors 1-2. Formatted dashes. | Use this bot. Report bugs. | Suggested by BrownHairedGirl | #UCB_webform 1977/3603 |
||
Line 27:
Let <math>b(i,j)</math> be a function designed so that, for each constraint <math>C_i</math>, the variables neighboring <math>C_i</math> are <math>v_{b(i,1)},\cdots,v_{b(i,d)}</math>.
Let <math>\mathcal{S}</math> be an error-correcting code of block length <math>d</math>. The '''''expander code''''' <math>\mathcal{C}(B,\mathcal{S})</math> is the code of block length <math>n</math> whose codewords are the words <math>(x_1,\cdots,x_n)</math> such that, for <math>1\leq i\leq cn/d</math>, <math>(x_{b(i,1)},\cdots,x_{b(i,d)})</math> is a codeword of <math>\mathcal{S}</math>.<ref name="definition">{{cite journal|doi=10.1109/18.556667|title=Expander codes |year=1996 |last1=Sipser |first1=M. |last2=Spielman |first2=D.A. |journal=IEEE Transactions on Information Theory |volume=42 |issue=6 |pages=1710–1722 }}</ref>
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 |chapter-url=http://dl.acm.org/citation.cfm?id=510003 |title=STOC '02 Proceedings of the thirty-fourth annual ACM symposium on Theory of computing |publisher=ACM |year=2002 |isbn=978-1-58113-495-7 |pages=659–668 |doi=10.1145/509907.510003|s2cid=1918841 }}</ref>
==Rate==
Line 117:
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 }}<br/>
{{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=https://www.cs.cmu.edu/~venkatg/teaching/codingtheory/notes/notes8.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 |s2cid=17550280 |url=http://dl.acm.org/citation.cfm?id=1027924}}</ref>
==References==
| |||