On expander codes based on hypergraphs

Expander codes where introduced in (1996) by Sipser and Spielman. These codes are related to low-density parity-check codes (LDPC-codes) from (R.G. Gallager, 1963) and other codes described in (R.M. Tanner, 1981), but with the restriction that any code symbol is involved in only two check equations. Gallager showed in (1963) that this is not suitable for constructing LDPC-codes. Therefore we generalize expander codes by using hypergraphs. Good expander graphs are obtained by using algebraic constructions from (G.A. Margulis, 1973) and (A. Lubotzky, et al., 1988). Since such constructions are not very flexible, we present a simple probabilistic method for constructing expander codes.