Expander code: Difference between revisions

Revision as of 22:06, 10 December 2021

Latest revision as of 06:40, 22 July 2024

(4 intermediate revisions by 4 users not shown)

Line 15:

In [[coding theory]], '''expander codes''' form a class of [[Error detection and correction|error-correcting codes]] that are constructed from [[Bipartite graph|bipartite]] [[expander graph]]s.

Along with [[Justesen code]]s, expander codes are of particular interest since they have a constant positive [[Block_codeBlock code#The_rate_RThe rate R|rate]], a constant positive relative [[Block_codeBlock code#The_distance_dThe distance d|distance]], and a constant [[Block_codeBlock code#The_alphabet_The alphabet .CE.A3|alphabet size]].

In fact, the alphabet contains only two elements, so expander codes belong to the class of [[binary code]]s.

Furthermore, expander codes can be both encoded and decoded in time proportional to the block length of the code.

==Expander codes==

In [[coding theory]], an expander code is a <math>[n,n-m]_2\,</math> [[linear block code]] whose parity check matrix is the adjacency matrix of a bipartite [[expander graph]]. These codes have good relative [[Block_codeBlock code#The_distance_dThe distance d|distance]] <math>2(1-\varepsilon)\gamma\,</math>, where <math>\varepsilon\,</math> and <math>\gamma\,</math> are properties of the expander graph as defined later), [[Block_codeBlock code#The_rate_RThe rate R|rate]] <math>\left(1-\tfrac{m}{n}\right)\,</math>, and decodability (algorithms of running time <math>O(n)\,</math> exist).

==Definition==

Let <math>B</math> be a <math>(c,d)</math>-regular[[biregular graph]] between a set of <math>n</math> nodes <math>\{v_1,\cdots,v_n\}</math>, called <i>''variables</i>'', and a set of <math>cn/d</math> nodes <math>\{C_1,\cdots,C_{cn/d}\}</math>, called <i>''constraints</i>''.

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 <b><i>'''''expander code</i></b>''''' <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|url-access=subscription }}</ref>

==References==