Expander code

Expander codes
bipartite expander graph
Classification
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, 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 are the only known asymptotically good codes which can be both encoded and decoded from a constant fraction of errors in polynomial time.

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