Expander 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. 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. In coding theory, an expander code is a [ n , n − m ] 2 {displaystyle _{2},} linear block code whose parity check matrix is the adjacency matrix of a bipartite expander graph. These codes have good relative distance 2 ( 1 − ε ) γ {displaystyle 2(1-varepsilon )gamma ,} , where ε {displaystyle varepsilon ,} and γ {displaystyle gamma ,} are properties of the expander graph as defined later), rate ( 1 − m n ) {displaystyle left(1-{ frac {m}{n}} ight),} , and decodability (algorithms of running time O ( n ) {displaystyle O(n),} exist). Consider a bipartite graph G ( L , R , E ) {displaystyle G(L,R,E),} , where L {displaystyle L,} and R {displaystyle R,} are the vertex sets and E {displaystyle E,} is the set of edges connecting vertices in L {displaystyle L,} to vertices of R {displaystyle R,} . Suppose every vertex in L {displaystyle L,} has degree d {displaystyle d,} (the graph is d {displaystyle d,} -left-regular), | L | = n {displaystyle |L|=n,} , and | R | = m {displaystyle |R|=m,} , m < n {displaystyle m<n,} . Then G {displaystyle G,} is a ( n , m , d , γ , α ) {displaystyle (n,m,d,gamma ,alpha ),} expander graph if every small enough subset S ⊂ L {displaystyle Ssubset L,} , | S | ≤ γ n {displaystyle |S|leq gamma n,} has the property that S {displaystyle S,} has at least d α | S | {displaystyle dalpha |S|,} distinct neighbors in R {displaystyle R,} . Note that this holds trivially for γ ≤ 1 n {displaystyle gamma leq { frac {1}{n}},} . When 1 n < γ ≤ 1 {displaystyle { frac {1}{n}}<gamma leq 1,} and α = 1 − ε {displaystyle alpha =1-varepsilon ,} for a constant ε {displaystyle varepsilon ,} , we say that G {displaystyle G,} is a lossless expander. Since G {displaystyle G,} is a bipartite graph, we may consider its n × m {displaystyle n imes m,} adjacency matrix. Then the linear code C {displaystyle C,} generated by viewing the transpose of this matrix as a parity check matrix is an expander code. It has been shown that nontrivial lossless expander graphs exist. Moreover, we can explicitly construct them. The rate of C {displaystyle C,} is its dimension divided by its block length. In this case, the parity check matrix has size m × n {displaystyle m imes n,} , and hence C {displaystyle C,} has dimension at least ( n − m ) / n = 1 − m n {displaystyle (n-m)/n=1-{ frac {m}{n}},} . Suppose ε < 1 2 {displaystyle varepsilon <{ frac {1}{2}},} . Then the distance of a ( n , m , d , γ , 1 − ε ) {displaystyle (n,m,d,gamma ,1-varepsilon ),} expander code C {displaystyle C,} is at least 2 ( 1 − ε ) γ n {displaystyle 2(1-varepsilon )gamma n,} . Note that we can consider every codeword c {displaystyle c,} in C {displaystyle C,} as a subset of vertices S ⊂ L {displaystyle Ssubset L,} , by saying that vertex v i ∈ S {displaystyle v_{i}in S,} if and only if the i {displaystyle i,} th index of the codeword is a 1. Then c {displaystyle c,} is a codeword iff every vertex v ∈ R {displaystyle vin R,} is adjacent to an even number of vertices in S {displaystyle S,} . (In order to be a codeword, c P = 0 {displaystyle cP=0,} , where P {displaystyle P,} is the parity check matrix. Then, each vertex in R {displaystyle R,} corresponds to each column of P {displaystyle P,} . Matrix multiplication over GF ( 2 ) = { 0 , 1 } {displaystyle { ext{GF}}(2)={0,1},} then gives the desired result.) So, if a vertex v ∈ R {displaystyle vin R,} is adjacent to a single vertex in S {displaystyle S,} , we know immediately that c {displaystyle c,} is not a codeword. Let N ( S ) {displaystyle N(S),} denote the neighbors in R {displaystyle R,} of S {displaystyle S,} , and U ( S ) {displaystyle U(S),} denote those neighbors of S {displaystyle S,} which are unique, i.e., adjacent to a single vertex of S {displaystyle S,} . For every S ⊂ L {displaystyle Ssubset L,} of size | S | ≤ γ n {displaystyle |S|leq gamma n,} , d | S | ≥ | N ( S ) | ≥ | U ( S ) | ≥ d ( 1 − 2 ε ) | S | {displaystyle d|S|geq |N(S)|geq |U(S)|geq d(1-2varepsilon )|S|,} .