Content deleted Content added
dab bipartite, degree; link regular graph |
|||
Line 2:
{{infobox code
| name = Expander codes
| image = [[File:
| image_caption = bipartite expander graph
| namesake =
Line 16:
In [[coding theory]], '''expander codes''' form a class of [[Error detection and correction|error-correcting codes]] that are constructed from [[Bipartite graph|bipartite]] [[expander graph]]s.
Along with [[Justesen code]]s, expander codes are of particular interest since they have a constant positive [[Block_code#The_rate_R|rate]], a constant positive relative [[Block_code#The_distance_d|distance]], and a constant [[Block_code#The_alphabet_.CE.A3|alphabet size]].
In fact, the alphabet contains only two elements, so expander codes belong to the class of [[
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.
Line 35:
==Distance==
Suppose <math>\varepsilon < \tfrac{1}{2}\,</math>. Then the distance of a <math>(n, m, d, \gamma, 1-\varepsilon)\,</math> expander code <math>C\,</math> is at least <math>2(1-\varepsilon)\gamma n\,</math>.
===Proof===
Note that we can consider every codeword <math>c\,</math> in <math>C\,</math> as a subset of vertices <math>S \subset L\,</math>, by saying that vertex <math>v_i \in S\,</math> if and only if the <math>i\,</math>th index of the codeword is a 1. Then <math>c\,</math> is a codeword iff every vertex <math>v \in R\,</math> is adjacent to an even number of vertices in <math>S\,</math>. (In order to be a codeword, <math>cP = 0\,</math>, where <math>P\,</math> is the parity check matrix. Then, each vertex in <math>R\,</math> corresponds to each column of <math>P\,</math>. Matrix multiplication over <math>\text{GF}(2) = \{0,1\}\,</math> then gives the desired result.) So, if a vertex <math>v \in R\,</math> is adjacent to a single vertex in <math>S\,</math>, we know immediately that <math>c\,</math> is not a codeword. Let <math>N(S)\,</math> denote the neighbors in <math>R\,</math> of <math>S\,</math>, and <math>U(S)\,</math> denote those neighbors of <math>S\,</math> which are unique, i.e., adjacent to a single vertex of <math>S\,</math>.
Line 66 ⟶ 67:
'''Input:''' received codeword <math>y\,</math>.
<code>
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)
| |||