We introduce irregular product codes, a class of codes where each codeword is represented by a matrix and the entries in each row (column) of the matrix come from a component row (column) code. As opposed to standard product codes, we do not require that all component row codes nor all component column codes be the same. Relaxing this requirement can provide some additional attractive features such as allowing some regions of the codeword to be more error-resilient, providing a more refined spectrum of rates for finite lengths, and improved performance for some of these rates. We study these codes over erasure channels and prove that for any 0 <; ε <; 1, for many rate distributions on component row codes, there is a matching rate distribution on component column codes such that an irregular product code based on MDS codes with those rate distributions on the component codes has asymptotic rate 1 - ε and can decode on erasure channels having erasure probability <; ε (and having alphabet size equal to the alphabet size of the component MDS codes).

In this paper, the second moment of the ripple size during the Luby transform (LT) decoding process is analyzed. Combined with a result by Karp et al. (2004) stating that the expectation of the ripple size is of the order ofk, our study gives bounds on the error probability of the LT decoder. Furthermore, an analytic expression for the variance of the ripple size up to terms of constant order is given, and the expression of Karp et al. for the expectation of the ripple size is refined up to terms of the order of 1/k. This provides a first step toward an analytic finite-length analysis of LT decoding.

Locally testable codes, i.e., codes where membership in the code is testable with a constant number of queries, have played a central role in complexity theory. It is well known that a code must be a "low-density parity check'' (LDPC) code for it to be locally testable, but few LDPC codes are known to be locally testable, and even fewer classes of LDPC codes are known not to be locally testable. Indeed, most previous examples of codes that are not locally testable were also not LDPC. The only exception was in the work of Ben-Sasson et al. [SIAM J. Computing, 2005] who showed that random LDPC codes are not locally testable. Random codes lack "structure'' and in particular "symmetries'' motivating the possibility that "symmetric LDPC'' codes are locally testable, a question raised in the work of Alon et al. [IEEE Trans. Inf. Th., 2005]. If true such a result would capture many of the basic ingredients of known locally testable codes. In this work we rule out such a possibility by giving a highly symmetric ("2-transitive'') family of LDPC codes that are not testable with a constant number of queries. We do so by continuing the exploration of ``affine-invariant codes'' - codes where the coordinates of the words are associated with a finite field, and the code is invariant under affine transformations of the field. New to our study is the use of fields that have many subfields, and showing that such a setting allows sufficient richness to provide new obstacles to local testability, even in the presence of structure and symmetry.

We analyze the second moment of the ripple size during the LT decoding process and prove that the standard deviation of the ripple size for an LT-code with length k is of the order of radick. Together with a result by Karp et. al (2004) stating that the expectation of the ripple size is of the order of k, this gives bounds on the error probability of the LT decoder. We also give an analytic expression for the variance of the ripple size up to terms of constant order, and refine the expression of Karp et. al for the expectation of the ripple size up to terms of the order of 1/k, thus providing a first step towards an analytic finite-length analysis of LT decoding.