Expander code: Difference between revisions

Revision as of 19:33, 8 April 2019

Latest revision as of 06:40, 22 July 2024

(11 intermediate revisions by 10 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>-[[biregular graph]] between a set of <math>n</math> nodes <math>\{v_1,\cdots,v_n\}</math>, called ''variables'', and a set of <math>cn/d</math> nodes <math>\{C_1,\cdots,C_{cn/d}\}</math>, called ''constraints''.

Consider a [[bipartite graph]] <math>G(L,R,E)\,</math>, where <math>L\,</math> and <math>R\,</math> are the vertex sets and <math>E\,</math> is the set of edges connecting vertices in <math>L\,</math> to vertices of <math>R\,</math>. Suppose every vertex in <math>L\,</math> has [[degree (graph theory)|degree]] <math>d\,</math> (the graph is <math>d\,</math>-left-[[Regular graph|regular]]), <math>|L|=n\,</math>, and <math>|R|=m\,</math>, <math>m < n\,</math>. Then <math>G\,</math> is a <math>(n, m, d, \gamma, \alpha)\,</math> expander graph if every small enough subset <math>S \subset L\,</math>, <math>|S| \leq \gamma n\,</math> has the property that <math>S\,</math> has at least <math>d\alpha|S|\,</math> distinct neighbors in <math>R\,</math>. Note that this holds trivially for <math>\gamma \leq \tfrac{1}{n}\,</math>. When <math>\tfrac{1}{n} < \gamma \leq 1\,</math> and <math>\alpha = 1 - \varepsilon\,</math> for a constant <math>\varepsilon\,</math>, we say that <math>G\,</math> is a lossless expander.

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

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.

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

==Rate==

The rate of <math>C\,</math> is its dimension divided by its block length. In this case, the parity check matrix has size <math>m \times n\,</math>, and hence <math>C\,</math> has dimensionrate at least <math>(n-m)/n = 1 - \tfrac{m}{/n}\,</math>.

==Distance==

Line 57 ⟶ 59:

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

Decoding of expander codes is possible in <math>O(n)\,</math> time when <math>\varepsilon < \tfrac{1}{4}\,</math> using the following algorithm.

Let <math>v_i\,</math> be the vertex of <math>L\,</math> that corresponds to the <math>i\,</math>th index in the codewords of <math>C\,</math>. Let <math>y \in \{0,1\}^n\,</math> be a received word, and <math>V(y) = \{v_i |\mid \text{ the } i^{\text{th}} \text{ position of } y \text{ is a } 1\}\,</math>. Let <math>e(i)\,</math> be <math>|\{v \in R |\mid v_i \in N(v) \text{ and } N(v) \cap V(y) \,</math>text{ is even<math>}\}|\,</math>, and <math>o(i)\,</math> be <math>|\{v \in R |\mid v_i \in N(v) \text{ and } N(v) \cap V(y) \,</math>text{ is odd<math>}\}|\,</math>. Then consider the greedy algorithm:

----

'''Input:''' received word <math>y\,</math>.

Line 114 ⟶ 116:

==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 }}<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=httphttps://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==