Expander code: Difference between revisions

Revision as of 18:58, 3 May 2011

Latest revision as of 06:40, 22 July 2024

(40 intermediate revisions by 30 users not shown)

Line 1:

{{cleanup|reason=Missing definitions, and grammar requires heavy copy-editing. Blindly pointing to the references should not be the point of the article. Missing scholarly exposition.|date=July 2012}}

In [[coding theory]], expander codes are a type of [[linear code]] which arises by using [[bipartite]] [[expander graphs]]. Along with [[concatenated codes]], expander codes are interesting since they can construct [[binary]] codes (codes using just 0 and 1) with constant positive [[rate]] and relative [[distance]]. Furthermore, expander codes can be both encoded and decoded in time proportional to the block length of the code. In fact, expander codes are the only known asymptotically good codes which can be both encoded and decoded from a constant fraction of errors in polynomial time.

{{infobox code

| name = Expander codes

| image = [[File:Tanner graph example.PNG|300px]]

| image_caption = bipartite expander graph

| namesake =

| type = [[Linear block code]]

| block_length = <math>n</math>

| message_length = <math>n-m</math>

| rate = <math>1-m/n</math>

| distance = <math>2(1-\epsilon)\gamma\cdot n</math>

| alphabet_size = <math>2</math>

| notation = <math>[n,n-m,2(1-\epsilon)\gamma\cdot n]_2</math>-code

}}

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.

This article is based on Dr. Venkatesan Guruswami's course notes <ref name="vg1">[http://www.cs.washington.edu/education/courses/cse533/06au/lecnotes/lecture13.pdf Washington's course notes]</ref><ref name="vg2">[http://www.cs.cmu.edu/~venkatg/teaching/codingtheory/notes/notes8.pdf CMU's course notes]</ref><ref name="vg3">[http://portal.acm.org/citation.cfm?id=1027924 Guest column: error-correcting codes and expander graphs]</ref>.

Along with [[Justesen code]]s, expander codes are of particular interest since they have a constant positive [[Block code#The rate R|rate]], a constant positive relative [[Block code#The distance d|distance]], and a constant [[Block code#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 Codescodes==

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 code#The 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 code#The 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]] <math>d\,</math> (the graph is <math>d\,</math>-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">[http://portal.acm.org/citation.cfm?id=510003 Randomness conductors and constant-degree lossless expanders]</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 dimensionrate at least <math>(n-m)/n = 1 - \tfrac{m}{/n}\,</math>.

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

===== Lemma 1 =====

For every <math>S \subset L\,</math> of size <math>|S| \leq \gamma n\,</math>, <math>d|S| \geq |N(S)| \geq |U(S)| \geq d(1-2\varepsilon)|S|\,</math>.

===== Proof =====

Trivially, <math>|N(S)| \geq |U(S)|\,</math>, since <math>v \in U(S)\,</math> implies <math>v \in N(S)\,</math>. <math>|N(S)| \leq d|S|\,</math> follows since the degree of every vertex in <math>S\,</math> is <math>d\,</math>. By the expansion property of the graph, there must be a set of <math>d(1-\varepsilon)|S|\,</math> edges which go to distinct vertices. The remaining <math>d\varepsilon|S|\,</math> edges make at most <math>d\varepsilon|S|\,</math> neighbors not unique, so <math>U(S) \geq d(1-\varepsilon)|S| - d\varepsilon|S| = d(1-2\varepsilon)|S|\,</math>.

===== Corollary =====

Every sufficiently small <math>S\,</math> has a unique neighbor. This follows since <math>\varepsilon < \tfrac{1}{2}\,</math>.

===== Lemma 2 =====

Every subset <math>T \subset L\,</math> with \,</math>|T| < 2(1-\varepsilon)\gamma n\,</math> has a unique neighbor.

===== Proof =====

Lemma 1 proves the case <math>|T| \leq \gamma n\,</math>, so suppose <math>2(1-\varepsilon)\gamma n > |T| > \gamma n\,</math>. Let <math>S \subset T\,</math> such that <math>|S| = \gamma n\,</math>. By Lemma 1, we know that <math>|U(S)| \geq d(1-2\varepsilon)|S|\,</math>. Then a vertex <math>v \in U(S)\,</math> is in <math>U(T)\,</math> iff <math>v \notin N(T \setminus S)\,</math>, and we know that <math>|T \setminus S| \leq 2(1-\varepsilon)\gamma n - \gamma n = (1-2\varepsilon)\gamma n\,</math>, so by the first part of Lemma 1, we know <math>|N(T \setminus S)| \leq d(1-2\varepsilon)\gamma n\,</math>. Since <math>\varepsilon < \tfrac{1}{2}\,</math>, <math>|U(T)| \geq |U(S) \setminus N(T \setminus S)| \geq |U(S)| - |N(T \setminus S)| > 0\,</math>, and hence <math>U(T)\,</math> is not empty.

===== Corollary =====

Note that if a <math>T \subset L\,</math> has at least 1 unique neighbor, i.e. <math>|U(T)| > 0\,</math>, then the corresponding word <math>c\,</math> corresponding to <math>T\,</math> cannot be a codeword, as it will not multiply to the all zeros vector by the parity check matrix. By the previous argument, <math>c \in C \implies wt(c) \geq 2(1-\varepsilon)\gamma n\,</math>. Since <math>C\,</math> is linear, we conclude that <math>C\,</math> has distance at least <math>2(1-\varepsilon)\gamma n\,</math>.

==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):1723–1732, |pages=1723–31 |year=1996 |doi=10.1109/18.556668 |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 codewordword <math>y\,</math>.

intializeinitialize y' to y

<code>

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</code>

'''Output:''' fail, or modified codeword <math>y'\,</math>.

----

Line 90 ⟶ 108:

This gives a total runtime of <math>O(mdr) = O(n)\,</math> time, where <math>d\,</math> and <math>r\,</math> are constants.

==See Alsoalso==

* [[Expander graph]]

* [[Low-density parity-check code]]

* Linear time encoding and decoding of error-correcting codes

* ABNNR and AEL codes

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

<references />

[[Category:Error detection and correction]]

[[Category:Coding theory]]

[[Category:Capacity-approaching codes]]