Expander code: Difference between revisions

Revision as of 16:52, 26 January 2012

Revision as of 09:27, 31 January 2012

Line 15:

In [[coding theory]], '''expander codes''' are a type of [[linear block code]] that arises by using [[bipartite]] [[expander graph]]s. Along with [[concatenated codes]], expander codes are interesting since they can construct [[Binary code|binary]] codes (codes using just 0 and 1) with constant positive [[Block_code#The_rate_R|rate]] and relative [[Block_code#The_distance_d|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.

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

==Expander codes==

Line 35:

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