Short-Block Protograph-Based LDPC Codes
- Created: Wednesday, 01 September 2010
Characteristics of these codes include low undetected-error rates and low latency.
Short-block low-density parity-check (LDPC) codes of a special type are intended to be especially well suited for potential applications that include transmission of command and control data, cellular telephony, data communications in wireless local area networks, and satellite data communications. [In general, LDPC codes belong to a class of error-correcting codes suitable for use in a variety of wireless data-communication systems that include noisy channels.] The codes of the present special type exhibit low error floors, low bit and frame error rates, and low latency (in comparison with related prior codes). These codes also achieve low maximum rate of undetected errors over all signal-to-noise ratios, without requiring the use of cyclic redundancy checks, which would significantly increase the overhead for short blocks. These codes have protograph representations; this is advantageous in that, for reasons that exceed the scope of this article, the applicability of protograph representations makes it possible to design high-speed iterative decoders that utilize belief-propagation algorithms.
Construction of a Code of the present special type includes elaboration of a starting protograph in a process denoted in the art as “lifting.” In this example, a starting protograph is first lifted by a factor of 4. In a subsequent step (not shown in the figure), the lifted-by-4 protograph is further lifted by a factor of 16 using circulant permutations." class="caption" align="left">The codes of the present special type are characterized mainly by rate 1/2 and input block sizes of 64, 128, and 256 bits. To simplify encoder and decoder implementations for high-data-rate transmission, the structures of the codes are based on protographs (see figure) and circulants. These codes are designed forshort blocks, the block sizes being based on maximizing minimum distances and stopping-set sizes subject to a constraint on the maximum variable node degree. In particular, these codes are designed to have variable node degrees between 3 and 5.
Short-block codes are desirable in communication systems in which frame-length constraints are imposed on the physical layers. For reasons that, once again, exceed the scope of this article, avoidance of degree-2 nodes enables construction of codes having minimum distance that grows linearly with block size. Limiting code design to the use of variable node degrees ≥3 is sufficient, but not necessary, for minimum distance to grow linearly with block size. Increasing the node degree leads to larger minimum distance, at the expense of smaller girth. Therefore, there is an engineering compromise between undetected-error-rate performance (which is improved by increasing minimum distance) and the degree of suboptimality of iterative decoders typically used (which is adversely affected by graph loops).
Codes of the present special type were found to perform well in computational simulations. For example, for a code of input block size of 64, constructed from the protograph in the figure with variable node degrees 3 and 5, the maximum undetected-error rate was found to be <3 × 10–5. This maximum was found to occur at a bit signal-to-noise ratio (SNR) of about 1.5, and the undetected-error rate was found to be smaller at SNRs both above and below 1.5, notably decreasing sharply with increasing SNR above 1.5.
This work was done by Dariush Divsalar, Samuel Dolinar, and Christopher Jones of Caltech for NASA’s Jet Propulsion Laboratory. For more information, contact iaoffice@jpl. nasa.gov. NPO-45190