System and method of belief propagation decoding

Patent metadata

Field	Value
Publication number	US-9806743-B2
Application number	US-201514941789-A
Country	US
Kind code	B2
Filing date	Nov 16, 2015
Priority date	Nov 16, 2015
Publication date	Oct 31, 2017
Grant date	Oct 31, 2017

Abstract

A method for decoding a codeword transmitted over a channel demodulates data received over the channel to produce an initial estimate of belief messages for bits of the codeword and decodes the codeword using a belief propagation (BP) decoding that iteratively passes the belief messages between a set of variable nodes representing the bits of the codeword and a set of check nodes representing parity-check constraints on the bits of the codeword until a termination condition is met. The BP decoding selects a look-up table based on a probability of the belief messages and maps, using the look-up table, values of at least two incoming belief messages to values of at least one outgoing belief message that forms an incoming belief message in a subsequent iteration of the BP decoding.

First claim

We claim:

1. A method for decoding a codeword transmitted over a channel, comprising:
demodulating data received over the channel to produce an initial estimate of belief messages for bits of the codeword; and
decoding the codeword using a belief propagation (BP) decoding that iteratively passes the belief messages between a set of variable nodes representing the bits of the codeword and a set of check nodes representing parity-check constraints on the bits of the codeword until a termination condition is met, wherein the BP decoding comprises:
determining a probability of the belief messages;
selecting a look-up table (LUT) from a set of LUTs based on the probability; and
mapping, using the LUT, values of at least two incoming belief messages to values of at least one outgoing belief message that forms an incoming belief message in a subsequent iteration of the BP decoding, wherein at least some steps of the method are performed by a processor of a BP decoder.

2. The method of claim 1 , wherein values of the belief messages are quantized, and wherein each LUT maps the quantized values of the two incoming belief messages to the quantized values of the outgoing belief messages according to a quantized function of the incoming belief messages modified based on the probability.

3. The method of claim 2 , wherein the probability is a probability mass function (PMF) that gives the probability of occurrence of the quantized values of belief messages conditioned on the bits of the codeword.

4. The method of claim 3 , further comprising:
selecting a set of PMF for the belief messages of the BP decoding; and
determining, for each PMF, a LUT that increases mutual information (MI) of the outgoing belief messages with values having a probability governed by the PMF to form the set of LUTs.

5. The method of claim 2 , wherein the BP decoding uses at least two different LUTs for at least two different iterations, wherein the two different LUTs uses different quantized function modified with different probabilities that the belief messages represent the bits of the codeword to map identical values of the incoming belief messages to different values of the outgoing belief message.

6. The method of claim 2 , wherein the quantized function is a log-likelihood function quantized to a predetermined set of values determined such that mutual information of the belief messages is increased depending on the probability of the belief messages, wherein the predetermined set of values changes between at least two iterations of the BP decoding.

7. The method of claim 1 , further comprising:
determining a signal-to-noise ratio (SNR) in the channel; and
determining the probability as a function of the SNR.

8. The method of claim 7 , further comprising:
determining an index of the iterations of the BP decoding; and
determining the probability as a function of the SNR, the index of the iterations, and a modulation format.

9. The method of claim 1 , wherein the BF decoder is a cascading decoder that uses multiple stages for propagating the belief messages, further comprising:
selecting at least two different LUTs for at least two different stages of the cascading decoder, wherein the LUT for different stages of the cascading decoder have a predetermined level of quantization.

10. The method of claim 1 , further comprising:
determining the LUT associated with the probability of the belief messages, such that at least two incoming belief messages representing the bits of the codeword with the probability are mapped by the LUT to at least one outgoing belief message that increases mutual information of the incoming belief messages.

11. The method of claim 10 , wherein the initial estimate of belief messages is quantized log-likelihood ratio (LLR) of the bits of the codeword encoded using a non-binary code, further comprising:
representing jointly the two incoming belief messages as a generalized node for an LLR vector using a vector quantization; and
determining the LUT to increase the mutual information of the LLR vector.

12. The method of claim 11 , further comprising:
determining low-density parity-check (LDPC) codes for decoding the codeword by embedding short block codes according to the generalized node.

13. The method of claim 1 , further comprising:
determining a low-density parity-check (LDPC) code for the variable nodes and the check nodes with variable degree distribution;
determining the LUTs adapted for the variable degree distribution of the variable nodes and the check nodes; and
determining a scheduling of BP decoding such that mutual information of the belief messages after predefined number of iterations is increased.

14. A system for decoding a codeword transmitted over a channel, comprising:
a demodulator to demodulate data received over the channel and to produce an initial estimate of belief messages for bits of the codeword;
a memory to store a set of look-up tables (LUTs) determined for different probabilities of the belief messages;
a belief propagation (BP) decoder to decode the codeword by iteratively passing the belief messages between a set of variable nodes representing the bits of the codeword and a set of check nodes representing parity-check constraints on the bits of the codeword until a termination condition is met, wherein the BP decoder
determines a probability of the belief messages to represent the bits of the codeword;
selects, based on the probability, a LUT from the set of LUTs stored in the memory; and
maps, using the LUT, values of at least two incoming belief messages to values of at least one outgoing belief message that forms an incoming belief message in a subsequent iteration of the BP decoder.

15. The system of claim 14 , wherein values of the belief messages are quantized, and wherein each LUT maps the quantized values of the two incoming belief messages to the quantized value of the outgoing belief message according to a quantized function of the incoming belief messages modified based on the probability, and wherein the probability is a probability mass function (PMF) that gives the probability that the quantized value of belief messages occurs conditioned on the bits of the codeword.

16. The system of claim 15 , wherein the BP decoder determines the probability as a function of a signal-to-noise ratio (SNR) in the channel.

17. The system of claim 15 , wherein the BP decoder determines the probability as a function of a signal-to-noise ratio (SNR) in the channel and an index of the iterations of the BP decoding.

18. The system of claim 14 , wherein the BP decoder determines a scheduling to propagate the belief messages, wherein a subset of the variable nodes and a subset of the check nodes propagates belief messages in parallel, wherein the subsets change for different iterations, wherein the scheduling is determined such that mutual information of the propagated belief messages is increased after predefined number of iterations.

Assignees

• Mitsubishi Electric Res Laboratories Inc

Inventors

• Koike-Akino Toshiaki
• Millar David

Classifications

• H03M13/1111 Primary

  Soft-decision decoding, e.g. by means of message passing or belief propagation algorithms · CPC title

• H03M13/033

  Theoretical methods to calculate these checking codes · CPC title

• H03M13/01 Primary

  Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes · CPC title

• H03M13/6577

  Representation or format of variables, register sizes or word-lengths and quantization · CPC title

• H03M13/1117

  using approximations for check node processing, e.g. an outgoing message is depending on the signs and the minimum over the magnitudes of all incoming messages according to the min-sum rule · CPC title