“Expander 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, a constant positive relative distance, and a constant 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

In coding theory, an expander code is a

linear block code whose parity check matrix is the adjacency matrix of a bipartite expander graph. These codes have good relative distance

, where

and

are properties of the expander graph as defined later), rate

, and decodability (algorithms of running time

exist).

Definition

Consider a bipartite graph

, where

and

are the vertex sets and

is the set of edges connecting vertices in

to vertices of

. Suppose every vertex in

has degree

(the graph is

-regular),

, and

. Then

is a

expander graph if every small enough subset

has the property that

has at least

distinct neighbors in

. Note that this holds trivially for

. When

and

for a constant

, we say that

is a lossless expander.

Since

is a bipartite graph, we may consider its

adjacency matrix. Then the linear code

generated by viewing the transpose of this matrix as a parity check matrix is an expander code.

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

Rate

The rate of

is its dimension divided by its block length. In this case, the parity check matrix has size

, and hence

has dimension at least

Distance

Proof

Note that we can consider every codeword

as a subset of vertices

, by saying that vertex

if and only if the

th index of the codeword is a 1. Then

is a codeword iff every vertex

is adjacent to an even number of vertices in

. (In order to be a codeword,

, where

is the parity check matrix. Then, each vertex in

corresponds to each column of

. Matrix multiplication over

then gives the desired result.) So, if a vertex

is adjacent to a single vertex in

, we know immediately that

is not a codeword. Let

denote the neighbors in

, and

denote those neighbors of

which are unique, i.e., adjacent to a single vertex of

Lemma 1

Proof

Trivially,

, since

implies

follows since the degree of every vertex in

. By the expansion property of the graph, there must be a set of

edges which go to distinct vertices. The remaining

edges make at most

neighbors not unique, so

Corollary

Lemma 2

Proof

Lemma 1 proves the case

, so suppose

. Let

such that

. By Lemma 1, we know that

. Then a vertex

is in

iff

, and we know that

, so by the first part of Lemma 1, we know

. Since

, and hence

is not empty.

Corollary

Note that if a

has at least 1 unique neighbor, i.e.

, then the corresponding word

corresponding to

cannot be a codeword, as it will not multiply to the all zeros vector by the parity check matrix. By the previous argument,

. Since

is linear, we conclude that

has distance at least

Encoding

The encoding time for an expander code is upper bounded by that of a general linear code -

by matrix multiplication. A result due to Spielman shows that encoding is possible in

time.^[2]

Decoding

Decoding of expander codes is possible in

time when

using the following algorithm.

Let

be the vertex of

that corresponds to the

th index in the codewords of

. Let

be a received word, and

. Let

is even

, and

is odd

. Then consider the greedy algorithm:

Proof

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

Correctness

We must show that the algorithm terminates with the correct codeword when the received codeword is within half the code's distance of the original codeword. Let the set of corrupt variables be

, and the set of unsatisfied (adjacent to an odd number of vertices) vertices in

. The following lemma will prove useful.

Lemma 3

Proof

By Lemma 1, we know that

. So an average vertex has at least

unique neighbors (recall unique neighbors are unsatisfied and hence contribute to

), since

, and thus there is a vertex

with

So, if we have not yet reached a codeword, then there will always be some vertex to flip. Next, we show that the number of errors can never increase beyond

Lemma 4

Proof

When we flip a vertex

and

are interchanged, and since we had

, this means the number of unsatisfied vertices on the right decreases by at least one after each flip. Since

, the initial number of unsatisfied vertices is at most

, by the graph's

-regularity. If we reached a string with

errors, then by Lemma 1, there would be at least

unique neighbors, which means there would be at least

unsatisfied vertices, a contradiction.

Lemmas 3 and 4 show us that if we start with

(half the distance of

), then we will always find a vertex

to flip. Each flip reduces the number of unsatisfied vertices in

by at least 1, and hence the algorithm terminates in at most

steps, and it terminates at some codeword, by Lemma 3. (Were it not at a codeword, there would be some vertex to flip). Lemma 4 shows us that we can never be farther than

away from the correct codeword. Since the code has distance

(since

), the codeword it terminates on must be the correct codeword, since the number of bit flips is less than half the distance (so we couldn't have traveled far enough to reach any other codeword).

Complexity

We now show that the algorithm can achieve linear time decoding. Let

be constant, and

be the maximum degree of any vertex in

. Note that

is also constant for known constructions.

See also

Notes

References

1. ^{{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}}
2. ^{{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 }}
3. ^{{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 }}
{{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=http://www.cs.cmu.edu/~venkatg/teaching/codingtheory/notes/notes8.pdf }}
{{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 |url=http://dl.acm.org/citation.cfm?id=1027924}}