Bounded-angle iterative decoding is a modified version of conventional iterative decoding, conceived as a means of reducing undetected- error rates for short low-density parity-check (LDPC) codes. For a given code, bounded- angle iterative decoding can be implemented by means of a simple modification of the decoder algorithm, without redesigning the code.

Error Rates in Iterative Decoding of a (32,16) LPDC code were computed for three test cases: one using a conventional decoding algorithm and two using the bounded-angle version of this algorithm with threshold angles of 28° and higher, and 31° and higher, respectively, varying with Eb/N0 according to the table.
Iterative decoders for well-designed LDPC codes are inherently capable of detecting as well as correcting errors. In a given instance, an error is detected if a code word is not found at the conclusion of iterations: that is, an error is detected if the estimated code symbols at the end of iterations do not constitute a valid code word. However, when this approach is followed without modification, the maximum undetectederror rates obtained for short LDPC codes are typically too high for many applications.

Bounded-angle iterative decoding is based on a representation of received words and code words as vectors in an n-dimensional Euclidean space (where n is an integer). In bounded-angle iterative decoding as in conventional iterative decoding, the estimates of the decoder are rejected (an error is detected) if a code word is not found before the maximum allowed number of iterations. Conversely, iterations may be stopped as soon as a code word is detected. The difference between bounded-angle and conventional iterative decoding manifests itself once a code word has been detected. At this point, the decoding algorithm computes the angle in the n-dimensional Euclidean space between the received word and the detected code word. If this angle is less than an arbitrarily specified threshold angle, θd, then the detected code word is accepted; if this angle exceeds θd, then the detected code word is rejected.

The undetected-error rate in bounded-angle iterative decoding is necessarily less than that in conventional iterative decoding because the modified decoding algorithm rejects at least the same code words as does the conventional decoding algorithm. By rejecting more code words, the modified algorithm reduces the undetected-error rate while increasing the overall error rate. Through judicious choice of θd, optimized as a function of signal-to-noise ratio Eb/N0 (see figure), one can reduce the decoder’s maximum undetected- error rate by orders of magnitude while increasing its overall error rate by amounts that are negligible for all values of Eb/N0 high enough to have produced a low error rate using the unmodified decoder. The main value of the modified algorithm lies in the possibility of making this favorable tradeoff between the two error rates, while not redesigning the code and only trivially modifying the decoder.

This work was done by Samuel Dolinar, Kenneth Andrews, Fabrizio Pollara, and Dariush Divsalar 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
E-mail: This email address is being protected from spambots. You need JavaScript enabled to view it.

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

Topics:
Information Technology Mathematical models Simulation and modeling Telecommunications
This Brief includes a Technical Support Package (TSP).
Document cover
Bounded-Angle Iterative Decoding of LDPC Codes

(reference NPO-46003) is currently available for download from the TSP library.

Don't have an account?

Magazine cover
NASA Tech Briefs Magazine

This article first appeared in the April, 2009 issue of NASA Tech Briefs Magazine (Vol. 33 No. 4).

Read more articles from this issue here.

Read more articles from the archives here.

Overview

The document discusses "Bounded-Angle Iterative Decoding of LDPC Codes," a novel approach to improving error detection and correction in coding systems, particularly for Low Density Parity Check (LDPC) codes. Traditional coding systems often use a combination of error-correcting codes and separate error-detecting codes, which can be inefficient, especially for short codes. The bounded-angle iterative decoding method aims to enhance the performance of LDPC codes by reducing the undetected error rate without redesigning the original code structure.

The key innovation of this method is its use of a threshold angle, denoted as theta_d, which is applied during the decoding process. In standard iterative decoding, a codeword is accepted if it satisfies the parity check equations. However, the bounded-angle method introduces an additional criterion: after detecting a codeword, the algorithm computes the Euclidean angle between the detected codeword and the received observations. If this angle exceeds the threshold theta_d, the detected codeword is rejected, and an erasure is output instead. This mechanism allows for a more stringent acceptance criterion, which can significantly lower the undetected error rate.

The document highlights that the bounded-angle iterative decoding can achieve a dramatic reduction in the maximum undetected error rate for short LDPC codes, potentially by two to three orders of magnitude, while only slightly increasing the overall error rate. This tradeoff is particularly beneficial for applications where undetected errors can have severe consequences.

The bounded-angle method is not only applicable to LDPC codes but can also be extended to generalized LDPC (GLDPC) codes, doubly generalized LDPC (DGLDPC) codes, and turbo-like codes, including turbo codes and serially concatenated codes. The document emphasizes that this approach does not require additional parity overhead from a separate error-detecting code, making it a more efficient solution.

In summary, the bounded-angle iterative decoding method represents a significant advancement in error correction technology, providing a practical solution to reduce undetected errors in coding systems while maintaining the integrity of the original code structure. This innovation is particularly relevant for aerospace applications, where reliable communication is critical.