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, an expander code is a linear block code whose parity check matrix is the adjacency matrix of a bipartite expander graph. These codes have good relative distance , where and are properties of the expander graph as defined later), rate , and decodability (algorithms of running time exist). Let be a -biregular graph between a set of nodes , called variables, and a set of nodes , called constraints. Let be a function designed so that, for each constraint , the variables neighboring are . Let be an error-correcting code of block length . The expander code is the code of block length whose codewords are the words such that, for , is a codeword of . It has been shown that nontrivial lossless expander graphs exist. Moreover, we can explicitly construct them. The rate of is its dimension divided by its block length. In this case, the parity check matrix has size , and hence has rate at least . Suppose . Then the distance of a expander code is at least . Note that we can consider every codeword in as a subset of vertices , by saying that vertex if and only if the th index of the codeword is a 1. Then is a codeword iff every vertex is adjacent to an even number of vertices in . (In order to be a codeword, , where is the parity check matrix. Then, each vertex in corresponds to each column of . Matrix multiplication over then gives the desired result.) So, if a vertex is adjacent to a single vertex in , we know immediately that is not a codeword. Let denote the neighbors in of , and denote those neighbors of which are unique, i.