Spectral techniques for expander codes
This paper introduces methods based on generalized Fourier analysis jor working with a class of errorcorrecting codes constructed in terms of Cayleygmphs. t%r work is motivated by the recent results of Sipser and Spielman [15] showing graph expansion to be essential for eficient decoding of certain low-density parity-check codes. They leave open the problem of sub-quadratic encoding for this class of codes, and it is this problem that we address. We show that when the codes are constructed in terms of Cayley graphs, the symmetry of the gmphs can be ezploited by using the representation theory of the underlying group to devise a sub-quadmtic encoding algorithm that, in the case where the group is PSLz(Z/qZ), requires 0(n4/3) operations, where n = 0(q3) is the block length. Our results indicate that this new class of codes may combine many of the strengths of two of the most powerful and successful, but previously dispamte areas of coding theory: the class of cyclic codes where the rich algebmic structure yields a large collection of techniques for finding and manipulating the codes, and the class of low-density paritycheck codes which have simple and eficient decoding algorithms and good asymptotic properties.