Content deleted Content added
improved lead |
|||
| (21 intermediate revisions by 18 users not shown) | |||
Line 2:
{{infobox code
| name = Expander codes
| image = [[File:
| image_caption = bipartite expander graph
| namesake =
Line 14:
}}
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 [[
In fact, the alphabet contains only two elements, so expander codes belong to the class of [[
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 [[
==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''.
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==
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
==Distance==
Suppose <math>\varepsilon < \tfrac{1}{2}\,</math>. Then the distance of a <math>(n, m, d, \gamma, 1-\varepsilon)\,</math> expander code <math>C\,</math> is at least <math>2(1-\varepsilon)\gamma n\,</math>.
===Proof===
Note that we can consider every codeword <math>c\,</math> in <math>C\,</math> as a subset of vertices <math>S \subset L\,</math>, by saying that vertex <math>v_i \in S\,</math> if and only if the <math>i\,</math>th index of the codeword is a 1. Then <math>c\,</math> is a codeword iff every vertex <math>v \in R\,</math> is adjacent to an even number of vertices in <math>S\,</math>. (In order to be a codeword, <math>cP = 0\,</math>, where <math>P\,</math> is the parity check matrix. Then, each vertex in <math>R\,</math> corresponds to each column of <math>P\,</math>. Matrix multiplication over <math>\text{GF}(2) = \{0,1\}\,</math> then gives the desired result.) So, if a vertex <math>v \in R\,</math> is adjacent to a single vertex in <math>S\,</math>, we know immediately that <math>c\,</math> is not a codeword. Let <math>N(S)\,</math> denote the neighbors in <math>R\,</math> of <math>S\,</math>, and <math>U(S)\,</math> denote those neighbors of <math>S\,</math> which are unique, i.e., adjacent to a single vertex of <math>S\,</math>.
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
==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
----
'''Input:''' received
▲ intialize y' to y
while there is a v in R adjacent to an odd number of vertices in V(y')
if there is an i such that o(i) > e(i)
flip entry i in y'
else
fail
'''Output:''' fail, or modified codeword <math>y'\,</math>.
----
Line 114 ⟶ 115:
==Notes==
This article is based on Dr. Venkatesan Guruswami's course notes.<ref>{{cite web |first=V.
{{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==
| |||