Method and System for Decoding Graph-Based Codes Using Message-Passing with Difference-Map Dynamics

Abstract

A code to be decoded by message-passing is represented by a factor graph. The factor graph includes variable nodes indexed by i and constraint nodes indexed by a connected by edges for transferring messages mi→a outgoing from the variable nodes to the constraint nodes and messages ma→i incoming from the constraint nodes to the variable nodes. The messages mi→a are initialized based on beliefs bi of a received codeword. The messages ma→i are generated by overshooting the messages mi→a at the constraint nodes. The beliefs bi are updated at the variable nodes using the messages ma→i. The codeword is outputted if found, otherwise, the messages mi→a are updated using a correction for the overshooting.

Description

RELATED APPLICATION[0001]This is a Divisional Application of U.S. patent application Ser. No. 12 / 541,810, “Method and System for Decoding Graph-Based Codes Using Message-Passing with Difference-Map Dynamics,” filed by Yedidia et al. on Aug. 14, 2009, incorporated herein by reference.FIELD OF THE INVENTION[0002]This invention relates generally to decoders, and more particularly to decoding graph-based codes, including low-density parity-check (LDPC) codes, using message-passing decoders.BACKGROUND OF THE INVENTIONProblems with Standard BP Decoders of LDPC Codes[0003]Properly designed low-density parity-check (LDPC) codes, when decoded using belief propagation (BP) decoders, can achieve near Shannon limit performance in the so-called “water-fall” regime where the signal-to-noise ratio (SNR) is near the code threshold. Numerous BP decoders are known in the prior art. The U.S. Patent Database reveals over 500 hundred related patents and applications.[0004]Prior art BP decoders are insta...

AI Technical Summary

Benefits of technology

[0030]The embodiments of the invention provide belief propagation (BP) decoders for low-density parity-check (LDPC) that significantly improve the error floor compared to standard belief propagation (BP) decoders.

[0033]Another embodiment of the BP decoder uses updating rules that are similar to the standard “min-sum” or “sum-product” BP decoder but with important alterations based on the “difference map” (DM) idea from the Divide and Concur method. This “difference map belief propagation” (DMBP) decoder can dramatically improve the error floor with complexity comparable to that of standard BP decoders, on both additive white Gaussian noise, and binary symmetric channels.

Problems solved by technology

Problems with Standard BP Decoders of LDPC Codes

Unfortunately, the factor graphs for good codes invariably contain cycles, and in the presence of cycles, the min-sum BP decoder becomes sub-optimal.

Sub-optimal sum-product BP decoders nevertheless achieve near Shannon limit performance for good graph-based codes in the waterfall regime, but unfortunately, the same is not true in the high-SNR regime.

In the high-SNR regime graph-based codes paired with sum-product or min-sum BP decoders often suffer from an “error floor” phenomena, whereby the decoder error rate improves only slowly as the SNR increases.

The error floor is a significant problem for applications that require extremely high reliability for high bit densities and data rates.

It limits the applicability of current generation graph-based codes in such applications, which include magneto-optic data storage, and fiber-optic communications.

Error patterns resulting from channel transmission that strongly overlap these patterns are uncorrectable by the decoder.

However, for many applications, specified codes, or codes of specified blocklengths and rates, may be required, and this approach may not be possible to implement because there may be no way to construct codes meeting the required specifications that also have good error floor behavior when decoded using standard BP decoders.

(Note however that optimal decoders are normally too complex to be practical.)

However, for many codes the enumeration of the trapping sets is itself an extremely challenging task.

Another improved decoder is the mixed-integer linear programming (MILP) decoder, which requires no information about trapping sets and approaches ML performance, but has a large decoding complexity.

Nevertheless, the multistage decoder has considerable practical difficulties, in that it requires multiple decoders, and the worst-case throughput is as slow as the MILP decoder.

Many of those applications are NP-complete problems.

This “alternating projections” approach works well for convex constraints, but otherwise sometimes gets “stuck” in short cycles that do not correspond to correct solutions.

Of course, DM might get caught in more complicated cycles or “strange attractors” and never find an existing solution; but least it does not get caught in simple local cycles.

Images