Topics
features
Publications
Issue Archive
RateCompatible LDPC Codes With Linear Minimum Distance
 Created: Tuesday, 01 September 2009
These protographbased codes can have fixed input or output block sizes.
A recently developed method of constructing protographbased lowdensity paritycheck (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.
The method comprises two submethods: one for fixed input block size and one for fixed output block size. The firstmentioned 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 fixedoutputblocksize 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 wirelesscommunication standards that involve the use of orthogonal frequencydivision modulation.Construction of a fixedinputblocklength code according to this method begins with selection of a highrate protograph LDPC code having variable node degrees of at least 3. Lowerrate codes are obtained by splitting check nodes in the protograph and connecting them with degree2 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 veryhighdegree node in the base protograph.
It has been proven that this construction guarantees that the linearminimumdistance property (the proportionality of minimum distance to block size) is preserved for the lowerrate codes. It has been further proven that a sufficient condition for a protograph LDPC code having only transmitted variable nodes of degree2 and higher to have linear minimum distance is that, in each connected subgraph of degree2 variable nodes and their attached edges and check nodes, the number of check nodes strictly exceeds the number of variable nodes.
To construct fixedoutputblocklength codes, one uses degree2 punctured nodes to merge pairs of check nodes in a lowrate base protograph, and thereby form higherrate codes. The linearminimumdis 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 rate1/2 base protograph and inserting three punctured degree2 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 ratecompatible family of codes in the figure exceed the corresponding ratedependent 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 rate1/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. Ratecompatible 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 96517, 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 202233
4800 Oak Grove Drive
Pasadena, CA 911098099
(818) 3542240
Email: This email address is being protected from spambots. You need JavaScript enabled to view it.
Refer to NPO43949, volume and number of this NASA Tech Briefs issue, and the page number.
White Papers

