Content deleted Content added
Stevesand85 (talk | contribs) →Decoding: y is not necessarily a codeword at the beginning of the algorithm, it's just an n-dimensional word in general. |
Stevesand85 (talk | contribs) |
||
Line 23:
==Definition==
Consider a [[bipartite graph]] <math>G(L,R,E)\,</math>, where <math>L\,</math> and <math>R\,</math> are the vertex sets and <math>E\,</math> is the set of edges connecting vertices in <math>L\,</math> to vertices of <math>R\,</math>. Suppose every vertex in <math>L\,</math> has [[degree (graph theory)|degree]] <math>d\,</math> (the graph is <math>d\,</math>-left-[[Regular graph|regular]]), <math>|L|=n\,</math>, and <math>|R|=m\,</math>, <math>m < n\,</math>. Then <math>G\,</math> is a <math>(n, m, d, \gamma, \alpha)\,</math> expander graph if every small enough subset <math>S \subset L\,</math>, <math>|S| \leq \gamma n\,</math> has the property that <math>S\,</math> has at least <math>d\alpha|S|\,</math> distinct neighbors in <math>R\,</math>. Note that this holds trivially for <math>\gamma \leq \tfrac{1}{n}\,</math>. When <math>\tfrac{1}{n} < \gamma \leq 1\,</math> and <math>\alpha = 1 - \varepsilon\,</math> for a constant <math>\varepsilon\,</math>, we say that <math>G\,</math> is a lossless expander.
Since <math>G\,</math> is a bipartite graph, we may consider its <math>n \times m\,</math> adjacency matrix. Then the linear code <math>C\,</math> generated by viewing the transpose of this matrix as a parity check matrix is an expander code.
| |||