Expander code

From Quire, the open reference·Type of error-correcting codes·6 min read

Expander codes
Classification
bipartite expander graph Image: source and license
Type	Linear block code
Block length	${\displaystyle n}$
Message length	${\displaystyle n-m}$
Rate	${\displaystyle 1-m/n}$
Distance	${\displaystyle 2(1-\epsilon )\gamma \cdot n}$
Alphabet size	${\displaystyle 2}$
Notation	${\displaystyle [n,n-m,2(1-\epsilon )\gamma \cdot n]_{2$ -code

In coding theory, expander codes form a class of error-correcting codes that are constructed from bipartite expander graphs. Along with Justesen codes, expander codes are of particular interest since they have a constant positive rate, positive relative distance, and alphabet size. In fact, the alphabet contains only two elements, so expander codes belong to the class of binary codes. Furthermore, expander codes can be both encoded and decoded in time proportional to the block length of the code.

Expander codes#edit

In coding theory, an expander code is a ${\displaystyle [n,n-m]_{2}\,}$ linear block code whose parity check matrix is the adjacency matrix of a bipartite expander graph. These codes have good relative distance ${\displaystyle 2(1-\varepsilon )\gamma \,}$ , where ${\displaystyle \varepsilon \,}$ and ${\displaystyle \gamma \,}$ are properties of the expander graph as defined later, rate ${\displaystyle \left(1-{\tfrac {m}{n\right)\,}$ , and decodability (algorithms of running time ${\displaystyle O(n)\,}$ exist).

Definition#edit

Let ${\displaystyle B}$ be a ${\displaystyle (c,d)}$ -biregular graph between a set of ${\displaystyle n}$ nodes ${\displaystyle \{v_{1},\cdots ,v_{n}\$ , called variables, and a set of ${\displaystyle cn/d}$ nodes ${\displaystyle \{C_{1},\cdots ,C_{cn/d}\$ , called constraints.

Let ${\displaystyle b(i,j)}$ be a function designed so that, for each constraint ${\displaystyle C_{i$ , the variables neighbouring ${\displaystyle C_{i$ are ${\displaystyle v_{b(i,1)},\cdots ,v_{b(i,d)$ .

Let ${\displaystyle {\mathcal {S$ be an error-correcting code of block length ${\displaystyle d}$ . The expander code ${\displaystyle {\mathcal {C(B,{\mathcal {S)}$ is the code of block length ${\displaystyle n}$ whose code words are the words ${\displaystyle (x_{1},\cdots ,x_{n})}$ such that, for ${\displaystyle 1\leq i\leq cn/d}$ , ${\displaystyle (x_{b(i,1)},\cdots ,x_{b(i,d)})}$ is a code word of ${\displaystyle {\mathcal {S$ .^[1]

It has been shown that nontrivial lossless expander graphs exist. Moreover, we can explicitly construct them.^[2]

Rate#edit

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

Distance#edit

Suppose ${\displaystyle \varepsilon <{\tfrac {1}{2\,}$ . Then the distance of a ${\displaystyle (n,m,d,\gamma ,1-\varepsilon )\,}$ expander code ${\displaystyle C\,}$ is at least ${\displaystyle 2(1-\varepsilon )\gamma n\,}$ .

Proof#edit

Note that we can consider every code word ${\displaystyle c\,}$ in ${\displaystyle C\,}$ as a subset of vertices ${\displaystyle S\subset L\,}$ , by saying that vertex ${\displaystyle v_{i}\in S\,}$ if and only if the ${\displaystyle i\,}$ th index of the code word is a 1. Then ${\displaystyle c\,}$ is a code word if every vertex ${\displaystyle v\in R\,}$ is adjacent to an even number of vertices in ${\displaystyle S\,}$ . (In order to be a code word, ${\displaystyle cP=0\,}$ , where ${\displaystyle P\,}$ is the parity check matrix. Then, each vertex in ${\displaystyle R\,}$ corresponds to each column of ${\displaystyle P\,}$ . Matrix multiplication over ${\displaystyle {\text{GF(2)=\{0,1\}\,}$ then gives the desired result.) So, if a vertex ${\displaystyle v\in R\,}$ is adjacent to a single vertex in ${\displaystyle S\,}$ , we know immediately that ${\displaystyle c\,}$ is not a code word. Let ${\displaystyle N(S)\,}$ denote the neighbours in ${\displaystyle R\,}$ of ${\displaystyle S\,}$ , and ${\displaystyle U(S)\,}$ denote those neighbours of ${\displaystyle S\,}$ which are unique, i.e., adjacent to a single vertex of ${\displaystyle S\,}$ .

Lemma 1#edit

For every ${\displaystyle S\subset L\,}$ of size ${\displaystyle |S|\leq \gamma n\,}$ , ${\displaystyle d|S|\geq |N(S)|\geq |U(S)|\geq d(1-2\varepsilon )|S|\,}$ .

Proof#edit

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

Corollary#edit

Every sufficiently small ${\displaystyle S\,}$ has a unique neighbour. This follows since ${\displaystyle \varepsilon <{\tfrac {1}{2\,}$ .

Lemma 2#edit

Every subset ${\displaystyle T\subset L\,}$ with ${\displaystyle |T|<2(1-\varepsilon )\gamma n\,}$ has a unique neighbour.

Proof#edit

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

Corollary#edit

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

Encoding#edit

The encoding time for an expander code is upper bounded by that of a general linear code - ${\displaystyle O(n^{2})\,}$ by matrix multiplication. A result due to Spielman shows that encoding is possible in ${\displaystyle O(n)\,}$ time.^[3]

Decoding#edit

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

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

Input: received word ${\displaystyle y\,}$ .

initialize 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 code word ${\displaystyle y'\,}$ .

Proof#edit

We show first the correctness of the algorithm, and then examine its running time.

Correctness#edit

We must show that the algorithm terminates with the correct code word when the received code word is within half the code's distance of the original code word. Let the set of corrupt variables be ${\displaystyle S\,}$ , ${\displaystyle s=|S|\,}$ , and the set of unsatisfied (adjacent to an odd number of vertices) vertices in ${\displaystyle R\,}$ be ${\displaystyle c\,}$ . The following lemma will prove useful.

Lemma 3#edit

If ${\displaystyle 0<s<\gamma n\,}$ , then there is a ${\displaystyle v_{i}\,}$ with ${\displaystyle o(i)>e(i)\,}$ .

Proof#edit

By Lemma 1, we know that ${\displaystyle U(S)\geq d(1-2\varepsilon )s\,}$ . So an average vertex has at least ${\displaystyle d(1-2\varepsilon )>d/2\,}$ unique neighbours (recall unique neighbours are unsatisfied and hence contribute to ${\displaystyle o(i)\,}$ ), since ${\displaystyle \varepsilon <{\tfrac {1}{4\,}$ , and thus there is a vertex ${\displaystyle v_{i}\,}$ with ${\displaystyle o(i)>e(i)\,}$ .

So, if we have not yet reached a code word, then there will always be some vertex to flip. Next, we show that the number of errors can never increase beyond ${\displaystyle \gamma n\,}$ .

Lemma 4#edit

If we start with ${\displaystyle s<\gamma (1-2\varepsilon )n\,}$ , then we never reach ${\displaystyle s=\gamma n\,}$ at any point in the algorithm.

Proof#edit

When we flip a vertex ${\displaystyle v_{i}\,}$ , ${\displaystyle o(i)\,}$ and ${\displaystyle e(i)\,}$ are interchanged, and since we had ${\displaystyle o(i)>e(i)\,}$ , this means the number of unsatisfied vertices on the right decreases by at least one after each flip. Since ${\displaystyle s<\gamma (1-2\varepsilon )n\,}$ , the initial number of unsatisfied vertices is at most ${\displaystyle d\gamma (1-2\varepsilon )n\,}$ , by the graph's ${\displaystyle d\,}$ -regularity. If we reached a string with ${\displaystyle \gamma n\,}$ errors, then by Lemma 1, there would be at least ${\displaystyle d\gamma (1-2\varepsilon )n\,}$ unique neighbours, which means there would be at least ${\displaystyle d\gamma (1-2\varepsilon )n\,}$ unsatisfied vertices, a contradiction.

Lemmas 3 and 4 show us that if we start with ${\displaystyle s<\gamma (1-2\varepsilon )n\,}$ (half the distance of ${\displaystyle C\,}$ ), then we will always find a vertex ${\displaystyle v_{i}\,}$ to flip. Each flip reduces the number of unsatisfied vertices in ${\displaystyle R\,}$ by at least 1, and hence the algorithm terminates in at most ${\displaystyle m\,}$ steps, and it terminates at some code word, by Lemma 3. (Were it not at a code word, there would be some vertex to flip). Lemma 4 shows us that we can never be farther than ${\displaystyle \gamma n\,}$ away from the correct code word. Since the code has distance ${\displaystyle 2(1-\varepsilon )\gamma n>\gamma n\,}$ (since ${\displaystyle \varepsilon <{\tfrac {1}{2\,}$ ), the code word it terminates on must be the correct code word, since the number of bit flips is less than half the distance (so we couldn't have travelled far enough to reach any other code word).

Complexity#edit

We now show that the algorithm can achieve linear time decoding. Let ${\displaystyle {\tfrac {n}{m\,}$ be constant, and ${\displaystyle r\,}$ be the maximum degree of any vertex in ${\displaystyle R\,}$ . Note that ${\displaystyle r\,}$ is also constant for known constructions.

Pre-processing: It takes ${\displaystyle O(mr)\,}$ time to compute whether each vertex in ${\displaystyle R\,}$ has an odd or even number of neighbours.
Pre-processing 2: We take ${\displaystyle O(dn)=O(dmr)\,}$ time to compute a list of vertices ${\displaystyle v_{i}\,}$ in ${\displaystyle L\,}$ which have ${\displaystyle o(i)>e(i)\,}$ .
Each Iteration: We simply remove the first list element. To update the list of odd / even vertices in ${\displaystyle R\,}$ , we need only update ${\displaystyle O(d)\,}$ entries, inserting / removing as necessary. We then update ${\displaystyle O(dr)\,}$ entries in the list of vertices in ${\displaystyle L\,}$ with more odd than even neighbours, inserting / removing as necessary. Thus each iteration takes ${\displaystyle O(dr)\,}$ time.
As argued above, the total number of iterations is at most ${\displaystyle m\,}$ .

This gives a total runtime of ${\displaystyle O(mdr)=O(n)\,}$ time, where ${\displaystyle d\,}$ and ${\displaystyle r\,}$ are constants.

Notes#edit

This article is based on Dr. Venkatesan Guruswami's course notes.^[4]

References#edit

^ Sipser, M.; Spielman, D.A. (1996). "Expander codes". IEEE Transactions on Information Theory. 42 (6): 1710–1722. doi:10.1109/18.556667.
^ Capalbo, M.; Reingold, O.; Vadhan, S.; Wigderson, A. (2002). "Randomness conductors and constant-degree lossless expanders". STOC '02 Proceedings of the thirty-fourth annual ACM symposium on Theory of computing. ACM. pp. 659–668. doi:10.1145/509907.510003. ISBN 978-1-58113-495-7. S2CID 1918841.
^ Spielman, D. (1996). "Linear-time encodable and decodable error-correcting codes". IEEE Transactions on Information Theory. 42 (6): 1723–31. doi:10.1109/18.556668.
^ Guruswami, V. (15 November 2006). "Lecture 13: Expander Codes" (PDF). CSE 533: Error-Correcting. University of Washington.
Guruswami, V. (March 2010). "Notes 8: Expander Codes and their decoding" (PDF). Introduction to Coding Theory. Carnegie Mellon University.
Guruswami, V. (September 2004). "Guest column: error-correcting codes and expander graphs". ACM SIGACT News. 35 (3): 25–41. doi:10.1145/1027914.1027924. S2CID 17550280.

This article is mirrored from “Expander code” on English Wikipedia, revision 1376125949, written by Wikipedia's contributors and licensed CC BY-SA 4.0. Editing it here creates a Quire copy with its own history.

Synced with Wikipedia revision 1376125949 · just now

Expander code

Expander codes#edit

Definition#edit

Rate#edit

Distance#edit

Proof#edit

Lemma 1#edit

Proof#edit

Corollary#edit

Lemma 2#edit

Proof#edit

Corollary#edit

Encoding#edit

Decoding#edit

Proof#edit

Correctness#edit

Lemma 3#edit

Proof#edit

Lemma 4#edit

Proof#edit

Complexity#edit

See also#edit

Notes#edit

References#edit