Low complexity finite precision decoders and apparatus for LDPC codes
In this invention, a new class of finite precision multilevel decoders for low-density parity-check (LDPC) codes is presented. 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. A general methodology is provided to obtain the multilevel decoders, which is based on reducing failures due to trapping sets and improving the guaranteed error-correction capability of a code. Hence 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. The description and apparatus of 3-bit decoders for column-weight three LDPC codes is also presented.
1. A message passing decoder for low-density parity check (LDPC) codes, in which messages passed between check nodes and variable nodes are from a finite multilevel message set (MMS), and in which a message update function at a variable node calculates a message update value from the MMS by applying a quantization function to a value computed by a preliminary function, wherein the preliminary function has inputs from the MMS and a channel output set.
2. The message passing decoder of claim 1 , wherein the LDPC codes have a fixed column-weight.
3. The message passing decoder of claim 1 wherein the preliminary function is a linear function.
4. The message passing decoder of claim 1 wherein the preliminary function is a non-linear function.
5. The message passing decoder of claim 1 wherein 3-bits are used for representation of the messages in the MMS.
6. The message passing decoder of claim 1 further comprising a channel output set that is quantized.
7. The message passing decoder of claim 1 wherein the message update function is implemented by a look-up table.
8. A message passing decoder for low-density parity check (LDPC) codes, in which messages passed between check nodes and variable nodes are from a finite multilevel message set (MMS), and in which a plurality of message update functions at the variable nodes calculate message update values from the MMS by applying quantization functions to values computed by preliminary functions, wherein the preliminary functions have inputs from the MMS and a channel output set.
9. The message passing decoder of claim 8 , wherein the LDPC codes have a fixed column-weight.
10. The message passing decoder of claim 8 wherein the preliminary functions comprise a plurality of linear functions.
11. The message passing decoder of claim 8 wherein the preliminary functions comprise a plurality of non-linear functions.
12. The message passing decoder of claim 8 wherein the preliminary functions comprise a plurality of either linear or non-linear functions.
13. The message passing decoder of claim 8 wherein 3-bits are used for representation of the messages in the MMS.
14. The message passing decoder of claim 8 in which the plurality of message update functions is the same for all variable nodes, and the message update functions may change from one iteration to another.
15. The message passing decoder of claim 8 in which the plurality of message update functions is the same for all iterations, and the message update functions may be different for different variable nodes.
16. The message passing decoder of claim 8 in which the plurality of the message update functions are combined.
17. The message passing decoder of claim 8 further comprising a channel output set that is guantized.
18. The message passing decoder of claim 8 wherein the message update functions are implemented by look-up tables.
19. A message passing decoding method comprising:
using a finite multilevel message set (MMS) for the messages passed between variable nodes and check nodes;
using a specifically defined message update at a variable node which calculates a message update value from the MMS by applying a quantization function to a value computed by a preliminary function, wherein the preliminary function has inputs from the MMS and a channel output set, and wherein the specifically defined message update function is is determined by generating a database of all possible subgraphs that are potentially trapping sets, performing decoding on the isolated subgraphs using different update tables under different error patterns and choosing for the message update function the table which has the best error correcting capabilities; and
using a min operation with a modulo 2 sum of signs operation to update messages at the check node.
20. The method of claim 19 , where the specifically defined message update function is chosen to decode isolated subgraphs that could potentially lead to decoding failures.
21. The method of claim 19 further comprising:
using a plurality of specifically defined message update functions to update messages at the variable nodes.
22. The method of claim 21 , where the plurality of specifically defined message update functions are chosen to decode isolated subgraphs that could potentially lead to decoding failures.