Invention:
This technology presents a new class of finite precision multilevel decoders for low-density parity-check (LDPC) codes. These decoders are much lower in complexity compared to the standard belief propagation (BP) decoder. Messages utilized by these decoders are quantized to certain levels based on the number of bits allowed for representation in hardware. A message update function specifically defined as part of the invention, is used to determine the outgoing message at the variable node, and the simple min operation along with modulo 2 sum of signs is used at the check node. These decoders improve the iterative decoding process on finite length graphs and have the potential to outperform the standard floating-point BP decoder in the error floor region.
Background:
Error-correcting codes are indispensable for any modern digital communication system which requires reliable transmission and/or storage of digital data. A class of error-correcting codes called low-density parity-check (LDPC) codes, that were originally discovered by Gallager in the 1960's and rediscovered some thirty years later, have sparked a widespread interest in the field of coding theory. The remarkable performance of LDPC codes as well as their simple and efficient high-speed implementations have made them very attractive for use in a plethora of applications ranging from wireless communication and deep-space communication systems to magnetic storage media.
In the past few years, a considerable amount of research has been dedicated towards constructing LDPC codes that have good distance properties, and finding better iterative decoders that enable simpler hardware implementations as well as have good asymptotic performance. Richardson et. al. in proposed the technique of density evolution under BP decoding in order to determine the asymptotic decoding threshold of a particular code and suggested using this analysis in order to optimize the code's profile for the best possible decoding threshold.
Applications:
- Code theory
- Low-density parity-check (LDPC) codes
Advantages:
- Improves the iterative decoding process
- More precise
- Better performance than standard belief propagation decoders
Status: issued U.S. patent # 8,458,556
