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.

linear block code whose parity check matrix is the adjacency matrix of a bipartite expander graph.

These codes have good relative distance

are properties of the expander graph as defined later, rate

, and decodability (algorithms of running time

be an error-correcting code of block length

[1] It has been shown that nontrivial lossless expander graphs exist.

is its dimension divided by its block length.

In this case, the parity check matrix has size

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

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

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

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

A result due to Spielman shows that encoding is possible in

Then consider the greedy algorithm: Input: received word

Output: fail, or modified codeword

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

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

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

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

, the initial number of unsatisfied vertices is at most

Each flip reduces the number of unsatisfied vertices in

steps, and it terminates at some codeword, by Lemma 3.

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

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

This article is based on Dr. Venkatesan Guruswami's course notes.