2009

Rate-Compatible LDPC Codes With Linear Minimum Distance

These protograph-based codes can have fixed input or output block sizes.

A recently developed method of constructing protograph-based low-density parity-check (LDPC) codes provides for low iterative decoding thresholds and minimum distances proportional to block sizes, and can be used for various code rates. A code constructed by this method can have either fixed input block size or fixed output block size and, in either case, provides rate compatibility.

altThe method comprises two submethods: one for fixed input block size and one for fixed output block size. The first-mentioned submethod is useful for applications in which there are requirements for rate- compatible codes that have fixed input block sizes. These are codes in which only the numbers of parity bits are allowed to vary. The fixed-output-block-size submethod is useful for applications in which framing constraints are imposed on the physical layers of affected communication systems. An example of such a system is one that conforms to one of many new wireless-communication standards that involve the use of orthogonal frequency-division modulation.

Construction of a fixed-input-block-length code according to this method begins with selection of a high-rate protograph LDPC code having variable node degrees of at least 3. Lower-rate codes are obtained by splitting check nodes in the protograph and connecting them with degree-2 variable nodes. Iterative decoding thresholds are calculated for each protograph by using the reciprocal channel approximation. Thresholds are lowered by use of either precoding or one very-high-degree node in the base protograph.

It has been proven that this construction guarantees that the linear-minimum-distance property (the proportionality of minimum distance to block size) is preserved for the lower-rate codes. It has been further proven that a sufficient condition for a protograph LDPC code having only transmitted variable nodes of degree-2 and higher to have linear minimum distance is that, in each connected subgraph of degree-2 variable nodes and their attached edges and check nodes, the number of check nodes strictly exceeds the number of variable nodes.

To construct fixed-output-block-length codes, one uses degree-2 punctured nodes to merge pairs of check nodes in a low-rate base protograph, and thereby form higher-rate codes. The linear-minimum-dis tance property is preserved for higher code rates, provided that the base protograph has variable node degrees of at least 3.

The figure presents an example of such a construction, starting with a rate-1/2 base protograph and inserting three punctured degree-2 variables nodes to merge three different pairs of check nodes. The protograph resulting from these three check node mergers has rate 7/8. To achieve rate 3/4, simply force one of the inserted variable nodes (#10 in the figure) to bit value 0. To achieve rate 5/8, force two of the new variable nodes (#9, #10) to bit value 0. For rate 1/2, force all three of the new variable nodes to bit value 0. The decoder assigns (infinitely) high reliability to those punctured nodes forced to bit value 0, and zero reliability to the punctured nodes not forced to bit value 0.

Iterative decoding thresholds for the rate-compatible family of codes in the figure exceed the corresponding rate-dependent capacity limits by only 0.43 dB, 0.48 dB, 0.30 dB, and 0.21 dB, for rates 1/2, 5/8, 3/4, 7/8, respectively. Additional rate-1/2 base protographs with variable node degrees at least 3 have been designed with iterative decoding thresholds within 0.36 dB of the capacity limit, about 0.2 dB better than the thresholds achieved by the best- known unstructured irregular LDPC codes satisfying the same constraint. Rate-compatible families constructed by this method from any such base protograph will preserve the linear minimum distance property.

This work was done by Dariush Divsalar, Christopher Jones, and Samuel Dolinar of Caltech for NASA’s Jet Propulsion Laboratory.

In accordance with Public Law 96-517, the contractor has elected to retain title to this invention. Inquiries concerning rights for its commercial use should be addressed to:

Innovative Technology Assets Management
JPL
Mail Stop 202-233
4800 Oak Grove Drive
Pasadena, CA 91109-8099
(818) 354-2240
E-mail: This email address is being protected from spambots. You need JavaScript enabled to view it.

Refer to NPO-43949, volume and number of this NASA Tech Briefs issue, and the page number.