System and Method for a Message Passing Algorithm

• US 20160211867A1
• Filed: 01/15/2016
• Published: 07/21/2016
• Est. Priority Date: 01/15/2015
• Status: Active Grant

• Current Assignee: Huawei Technologies Co., Ltd. (Huawei Investment & Holding Co., Ltd.)
• Original Assignee: Huawei Technologies Co., Ltd. (Huawei Investment & Holding Co., Ltd.)
• Inventors: Guillemette, Philippe
• Granted Patent: US 9,831,895 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H03M 13/1102 Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
• CPC Class Codes: H03M 13/1111 Soft-decision decoding, e.g. by means of message passing or belief propagation algorithms
• CPC Class Codes: H03M 13/1114 Merged schedule message passing algorithm with storage of sums of check-to-bit node messages or sums of bit-to-check node messages, e.g. in order to increase the memory efficiency
• CPC Class Codes: H03M 13/1505 Golay Codes
• CPC Class Codes: H03M 13/152 Bose-Chaudhuri-Hocquenghem [BCH] codes
• CPC Class Codes: H03M 13/23 using convolutional codes, e.g. unit memory codes
• CPC Class Codes: H04L 1/0048 in conjunction with detection of multiuser or interfering signals, e.g. iteration between CDMA or MIMO detector and FEC decoder for spatial equalizer H04L25/03286
• CPC Class Codes: H04L 1/0057 Block codes H04L1/0061, H04L1/0064 take precedence

Abstract

The complexity of sparse code multiple access (SCMA) decoding can be reduced by pruning codebooks to remove unlikely codewords prior to, or while, performing an iterative message passing algorithm (MPA). The pruned codebook is then used by to perform one or more iterations of MPA processing, thereby reducing the number codeword probabilities that are calculated for the corresponding SCMA layer. The pruned codebook also reduces the computational complexity of calculating codeword probabilities associated with other SCMA layers. The pruned codebook may be “reset” by reinserting the pruned codewords into the codebook after a final hard-decision for a given set of received samples is made, so that the pruning does not affect evaluation of the next set of samples.

Claims

1. A method comprising:

receiving, by a Message Passing Algorithm (MPA) processor, a sequence of samples representative of a received signal from a device;

receiving, or otherwise generating, one or more probabilities associated codewords of a codebook assigned to a data stream in the received signal;

removing, in accordance with the probabilities, at least one of the codewords from the codebook to obtain a pruned codebook, the pruned codebook excluding the at least one codeword;

processing, by the MPA processor, the received sequence of samples according to the pruned codebook to generate soft decision values corresponding to the received signal; and

sending the soft decision values to a forward error correction (FEC) decoder.

2. The method of claim 1, wherein processing the received sequence of samples comprises:

exchanging belief propagation messages for codewords remaining in the pruned codebook between nodes of the MPA processor during the set of MPA iterations without exchanging belief propagation messages for the at least one codeword excluded from the pruned codebook; and

generating the soft decision values based on the sequence of samples and the exchanged belief propagation messages.

3. The method of claim 1, wherein the one or more probabilities indicate likelihoods that one or more codewords in the codebook are carried in the data stream.

4. The method of claim 3, wherein removing the at least one codeword from the codebook to obtain the pruned codebook comprises:

removing, from the codebook, any codewords whose likelihood of being carried in the data stream is less than a probability threshold.

5. The method of claim 4, wherein the probability threshold is predetermined.

6. The method of claim 4, wherein the probability threshold is based on the relative probabilities of codewords in the codebook.

7. The method of claim 1, wherein removing the at least one codeword from the codebook to obtain the pruned codebook comprises:

determining that a likelihood of a given bit in a given modulated symbol having a given binary value exceeds a threshold; and

removing, from the codebook, any codewords that map the given bit in the given modulated symbol to a different binary value.

8. The method of claim 7, wherein determining that the likelihood of the given bit having the given binary value exceeds the threshold comprises determining that an LLR magnitude associated with the given binary value exceeds the threshold.

9. The method of claim 8, wherein the threshold is predetermined.

10. The method of claim 8, wherein the threshold is dynamically set based on the values of other LLRs in the modulated symbol, the given layer of the received signal, or the received signal.

11. The method of claim 1, wherein the received probability is a Log Likelihood Ratio (LLR) indicative of a sign bit for a given binary bit in the data stream and a set of magnitude bits indicating a confidence level in the accuracy of the sign bit.

12. The method of claim 11, wherein the LLR is received from the FEC decoder.

13. The method of claim 1, wherein the received probability is an a priori probability (APP) value indicative of the likelihood of a given codeword having been transmitted.

14. The method of claim 1, wherein receiving the one or more probabilities comprises receiving feedback information including the one or more probabilities.

15. The method of claim 1, wherein processing the received sequence of samples according to the pruned codebook to generate soft decision values corresponding to the received signal comprises:

receiving, by a function node of the MPA processor, messages corresponding to codewords remaining in the pruned codebook from variable nodes in the MPA processor without receiving, from the variable nodes, any messages corresponding to the at least one codeword excluded from the pruned codebook; and

distributing the received messages among the virtual nodes.

16. The method of claim 1, wherein processing the received sequence of samples according to the pruned codebook to generate soft decision values corresponding to the received signal comprises:

receiving, by a variable node of the MPA processor, information about the received signal from function nodes of the MPA processor; and

calculating, based on the information, probabilities that codewords remaining in the pruned codebook were transmitted in the data stream without calculating probabilities that the at least one codeword excluded from the pruned codebook was transmitted in the data stream.

17. The method of claim 1, wherein the step of processing the received sequence of samples comprises generating a computation schedule to exclude operations associated with messages related to codewords pruned from the alphabet.

18. A decoder comprising:

a forward error correction (FEC) decoder; and

a message passing algorithm (MPA) processor coupled to the FEC decoder, the MPA processor configured to receive a sequence of samples representative of a received signal from a device, to receive, or otherwise obtain, one or more probabilities associated codewords of a codebook assigned to a data stream in the received signal, to remove, in accordance with the probabilities, at least one of the codewords from the codebook to obtain a pruned codebook, the pruned codebook excluding the at least one codeword, to process the received sequence of samples according to the pruned codebook to generate soft decision values corresponding to the received signal, and to send the soft decision values to a forward error correction (FEC) decoder.

19. The computer program product of claim 18, wherein the one or more probabilities include a codeword probability, an a priori probability (APP) value, or a log likelihood ratio (LLR).

20. A computer program product comprising a computer readable storage medium storing programming, the programming including instructions to:

receive, at a Message Passing Algorithm (MPA) processor a sequence of samples representative of a received signal from a device;

receive, or otherwise obtain, one or more probabilities associated codewords of a codebook assigned to a data stream in the received signal;

remove, in accordance with the probabilities, at least one of the codewords from the codebook to obtain a pruned codebook, the pruned codebook excluding the at least one codeword;

process, at the MPA processor, the received sequence of samples according to the pruned codebook to generate soft decision values corresponding to the received signal; and

send the soft decision values to a forward error correction (FEC) decoder.