LDPC Codes
Background
Low-density parity-check (LDPC) codes are forward error-correction codes, first proposed in the 1962 PhD thesis of Gallager at MIT, but then largely neglected for over 35 years. In the mean time the field of forward error correction was dominated by highly structured algebraic block and convolutional codes. Despite the enormous practical success of these codes, their performance fell well short of the theoretically achievable limits set down by Shannon in his seminal 1948 paper. By the late 1980s, researchers were largely resigned to this seemingly insurmountable theory--practice gap.
The situation was utterly revolutionized by turbo codes, proposed by Berrou, Glavieux and Thitimajshima in 1993, wherein all the key ingredients of successful FEC codes were replaced: turbo codes involve very little algebra, employ iterative, distributed algorithms, focus on average (rather than worst-case) performance, and rely on soft (or probabilistic) information extracted from the channel. Overnight, the gap to the Shannon limit was all but eliminated, using decoders with manageable complexity.
As researchers struggled through the 1990s to understand just why turbo codes worked as well as they did, it was recognized that the class of codes developed by Gallager shared all the essential features of turbo codes, including sparse graph-based codes and iterative message-passing decoders. Indeed turbo decoding has recently been shown to be a special case of the sum-product decoding algorithm presented by Gallager. Generalisations of Gallager's LDPC codes to irregular LDPC codes, can easily outperform the best turbo codes, as well as offering certain practical advantages and an arguably cleaner setup for theoretical results.
As their name suggests, LDPC codes are block codes with parity-check matrices that contain only a very small number of non-zero entries. It is the sparseness of the parity-check matrix which guarantees both a decoding complexity which increases only linearly with the code length and a minimum distance which also increases linearly with the code length. A graphical representation of the parity-check matrix is given by a bi-partite graph called a Tanner graph with bit nodes, one for each codeword bit, represented by circular vertices and check nodes, one for each parity-check equation in the parity-check matrix, represented by square vertices.
Aside from the requirement that the parity-check matrix be sparse, an LDPC code itself is no different to any other block code. Indeed existing block codes can be successfully used with the LDPC iterative decoding algorithms if they can be represented by a sparse parity-check matrix. Generally, however, finding a sparse parity-check matrix for an existing code is not practical. Instead LDPC codes are designed by constructing a sparse parity-check matrix first and then determining a generator matrix for the code afterwards. While Gauss-Jordan elimination can be used to put the parity-check matrix in standard form and thus define a generator matrix, the resulting generator matrix is not sparse and so encoding complexity can be quadractic in the code length. However, by using just row and column permutations an LDPC code can be put into an approximate lower triangular form while maintaining its sparsity. Then using back substitution will allow almost linear-time encoding.
The biggest difference between LDPC codes and classical block codes is how they are decoded. Classical block codes are generally decoded with ML like decoding algorithms and so are usually short and designed algebraically to make this task less complex. LDPC codes however are decoded iteratively using a graphical representation of their parity-check matrix and so are designed with the properties of the parity-check matrix as a focus.
Repeat-Accumulate Codes
Repeat-accumulate (RA) codes are a specific class of serially concatenated codes where the outer code is a repetition code and the inner code is a convolutional code with generator 1/(1+D). This convolutional code simply outputs the modulo-2 sum of the current input bit with the previous output bit, i.e. it provides a running sum of all past inputs, and so is often called an accumulator.
Importantly, RA codes are also a special type of low-density parity-check code. The parity-check equation of an RA code is the joint combiner and accumulator equations. Earlier we saw that an LDPC code can be put into an approximate lower triangular form so as to facilitate almost linear-time encoding. A repeat-accumulate (RA) code can be viewed as an LDPC code with an lower triangular form already built into the parity-check matrix during the code design. An RA code thus gains both the low encoding complexity of turbo codes and the decoding performance of LDPC codes.
Research
There are four research topics included in this project.
- Design and decoding of low-density parity-check codes
People: Steven Weller and Sarah Johnson
Funding: ARC Discovery Project DP0449627
- Repeat-accumulate codes
People: Sarah Johnson
Funding: ARC Discovery Project DP0665742
- Dynamical systems and iterative decoding of low-density parity-check codes
People: Steve Weller and Chris Kellett
Funding: ARC Discovery Project DP0771131
- Iterative coding for packet erasure networks
People: Sarah Johnson and Chris Kellett
Funding: ARC Discovery Project DP0877258
