The most common way to generate a rate-compatible family of codes is puncturing. In this method, one starts with a low-rate mother code and then selectively discards some of the coded bits to arrive at higher-rate codes. This approach is simple, but is not free of problems. Specifically, the mother code is optimally designed for low rates, so higher-rate punctured codes have a wider gap to capacity, and the optimal low-rate code structure and puncturing patterns are designed separately, which is suboptimal. Even though it has been shown that puncturing can theoretically achieve the same gap to capacity as the mother code, in existing codes puncturing has in creased the gap significantly.

A rate-compatible family of low density parity check (LDPC) codes was designed using code extension based on protographs. Code extension starts with a high-rate code (a daughter code), then lower-rate codes are obtained by lengthening and expurgating the parity check matrix of the daughter code.

Hybrid automatic repeat request (HARQ) is an error control method. In standard ARQ error detection, symbols such as cyclic redundancy check (CRC) are added to the information data. In HARQ, forward error correction code, such as LDPC code symbols, are also added to the existing error detection symbols, such that small random errors are corrected without retransmission, and major errors are corrected via a request for retransmission. The hybrid scheme performs better than standard ARQ in poor signal conditions. Many current and future NASA missions include ARQ or HARQ protocol schemes.

In many applications, such as HARQ, a rate-compatible family in the usual sense must have the same information block size; otherwise it is not useful for such applications. To create a code that satisfies this property, code extension was used, starting with a high-rate code. The idea of code extension for designing rate-compatible codes is not entirely new and has appeared in literature in the context of irregular LDPC codes, but its application to protographs is novel, and the quality of the codes that has been produced in this way is superior to other known results.

A simple method was provided to design a rate-compatible coding scheme for adaptive coding and HARQ applications based on protographs with a wide range of rates. These codes have thresholds within 0.1 dB of capacity, and the linear minimum distance property holds. As a byproduct of the main results, several high-rate protograph codes were produced that do not have uniform information size. The rates of these codes range from 1/2 to 5/6, have thresholds within 0.12 dB of capacity, and can be used for other applications. Although the protograph designs are constrained within a nested structure, the resulting protograph codes still perform close to capacity, and have the lowest iterative decoding thresholds among structured codes with linear minimum distance property reported in the literature.

This work was done by Dariush Divsalar of Caltech, and Thuy V. Nguyen and Aria Nosratinia of the University of Texas at Dallas for NASA’s Jet Propulsion Laboratory. For more information, contact This email address is being protected from spambots. You need JavaScript enabled to view it..

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
Mail Stop 321-123
4800 Oak Grove Drive
Pasadena, CA 91109-8099
E-mail: This email address is being protected from spambots. You need JavaScript enabled to view it.

Refer to NPO-47586.

NASA Tech Briefs Magazine

This article first appeared in the October, 2014 issue of NASA Tech Briefs Magazine.

Read more articles from this issue here.

Read more articles from the archives here.