Expander code

Contents
Proof
Proof
Encoding
Complexity
See also
Notes
References

n</math>"},"message_length":{"wt":"<math>n-m</math>"},"rate":{"wt":"<math>1-m/n</math>"},"distance":{"wt":"<math>2(1-\\epsilon)\\gamma\\cdot n</math>"},"alphabet_size":{"wt":"<math>2</math>"},"notation":{"wt":"<math>[n,n-m,2(1-\\epsilon)\\gamma\\cdot n]_2</math>-code"}},"i":0}}]}'>

Expander codes
bipartite expander graph
Classification
Type	Linear block code
Block length	1−m/n
Distance	[n,n−m,2(1−ϵ)γ⋅n]2-code
v t e

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.

2(1−ε)γ, where (1−mn), and decodability (algorithms of running time (c,d)-biregular graph between a set of cn/d nodes Ci, the variables neighbouring 𝒮 be an error-correcting code of block length n whose code words are the words (xb(i,1),⋯,xb(i,d)) is a code word of m×n, and hence ε<12. Then the distance of a 2(1−ε)γn.

Proof

edit

Note that we can consider every code word S⊂L, by saying that vertex c is a code word if every vertex cP=0, where P. Matrix multiplication over S, we know immediately that R of S which are unique, i.e., adjacent to a single vertex of |S|≤γn, v∈U(S) implies S is dε|S| edges make at most S has a unique neighbour. This follows since |T|<2(1−ε)γn has a unique neighbour.

Proof

edit

Lemma 1 proves the case S⊂T such that v∈U(S) is in |T∖S|≤2(1−ε)γn−γn=(1−2ε)γn, so by the first part of Lemma 1, we know |U(T)|≥|U(S)∖N(T∖S)|≥|U(S)|−|N(T∖S)|>0, and hence |U(T)|>0, then the corresponding word c∈C⟹wt(c)≥2(1−ε)γn. Since 2(1−ε)γn.

Encoding

edit

The encoding time for an expander code is upper bounded by that of a general linear code - O(n) time when L that corresponds to the y∈{0,1}n be a received word, and |{v∈R∣vi∈N(v) and N(v)∩V(y) is even}|, and 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 s=|S|, and the set of unsatisfied (adjacent to an odd number of vertices) vertices in 0<s<γn, then there is a U(S)≥d(1−2ε)s. So an average vertex has at least d/2\\,"}}'>d(1−2ε)>d/2 unique neighbours (recall unique neighbours are unsatisfied and hence contribute to vi with e(i)\\,"}}'>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 s=γn at any point in the algorithm.

Proof

edit

When we flip a vertex e(i) are interchanged, and since we had e(i)\\,"}}'>o(i)>e(i), this means the number of unsatisfied vertices on the right decreases by at least one after each flip. Since dγ(1−2ε)n unique neighbours, which means there would be at least C), then we will always find a vertex 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 ε<12), 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).