View article

We report the empirical performance of Gallager’s low density parity check codes on Gaussian channels. We show that performance substantially better than that of standard convolutional and concatenated codes can be achieved; indeed the performance is almost as close to the Shannon limit as that of Turbo codes.

A linear code may be described in terms of a generator matrix G or in terms of a parity check matrix H, which satisfies Hx= 0 for all codewords x. In 1962, Gallager reported work on binary codes defined in terms of low density parity check matrices (abbreviated ‘GL codes’)[5, 6]. The matrix H was defined in a non-systematic form; each column of H had a small weight (eg, 3) and the weight per row was also uniform; the matrix H was constructed at random subject to these constraints. Gallager proved distance properties of these codes and described a probability-based decoding algorithm with promising empirical performance. However it appears that GL codes have been generally forgotten, the assumption perhaps being that concatenated codes [4] were superior for practical purposes (RG Gallager, personal communication). During our work on MN codes [8] we realised that it is possible to create ‘good’codes from very sparse random matrices, and to decode them (even beyond their minimum distance) using approximate probabilistic algorithms. We eventually reinvented Gallager’s decoding algorithm and GL codes. In this paper we report the empirical performance of these codes on Gaussian channels. We have proved theoretical properties of GL codes (essentially, that the channel coding theorem holds for them) elsewhere [9]. GL …