Node processors for use in parity check decoders

• US 6,938,196 B2
• Filed: 04/04/2002
• Issued: 08/30/2005
• Est. Priority Date: 06/15/2001
• Status: Expired due to Fees

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Flarion Technologies Inc (Qualcomm, Inc.)
• Inventors: Richardson, Tom, Novichkov, Vladimir
• Primary Examiner(s): DILDINE JR, R STEPHEN
• Application Number:
  US10/117,264
• Publication Number:
  US 20030023917A1
• Time in Patent Office: 1,244 Days
• Field of Search: 714/752, 714/777, 714/804
• US Class Current: 714/752
• CPC Class Codes: G06N 3/02 Neural networks
• 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/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 Class Codes: H03M 13/112 with correction functions for the min-sum rule, e.g. using an offset or a scaling factor
• CPC Class Codes: H03M 13/1125 using different domains for check node and bit node processing, wherein the different domains include probabilities, likelihood ratios, likelihood differences, log-likelihood ratios or log-likelihood difference pairs
• CPC Class Codes: H03M 13/1131 Scheduling of bit node or check node processing
• CPC Class Codes: H03M 13/1134 Full parallel processing, i.e. all bit nodes or check nodes are processed in parallel
• CPC Class Codes: H03M 13/1137 Partly parallel processing, i.e. sub-blocks or sub-groups of nodes being processed in parallel
• CPC Class Codes: H03M 13/1145 Pipelined decoding at code word level, e.g. multiple code words being decoded simultaneously
• CPC Class Codes: H03M 13/6362 by puncturing
• CPC Class Codes: H03M 13/6502 Reduction of hardware complexity or efficient processing
• CPC Class Codes: H03M 13/6577 Representation or format of variables, register sizes or word-lengths and quantization
• CPC Class Codes: H03M 13/658 Scaling by multiplication or division
• CPC Class Codes: H03M 13/6583 Normalization other than scaling, e.g. by subtraction

Abstract

Techniques for implementing message passing decoders, e.g., LDPC decoders, are described. To facilitate hardware implementation messages are quantized to integer multiples of ½ ln2. Messages are transformed between more compact variable and less compact constraint node message representation formats. The variable node message format allows variable node message operations to be performed through simple additions and subtractions while the constraint node representation allows constraint node message processing to be performed through simple additions and subtractions. Variable and constraint nodes are implemented using an accumulator module, subtractor module and delay pipeline. The accumulator module generates an accumulated message sum. The accumulated message sum for a node is stored and then delayed input messages from the delay pipeline are subtracted there from to generate output messages. The delay pipeline includes a variable delay element making it possible to sequentially perform processing operations corresponding to nodes of different degrees.

Claims

1. A decoder processing method, comprising:

receiving a value;

quantizing the received value, using quantization step sizes which are integer multiples of ½

ln 2, to produce a quantized value; and

performing one of a check node and a variable node processing operation on said quantized value to produce at least a portion of an outgoing message.

2. The method of claim 1, wherein said received value is a log-likelihood value.

3. The method of claim 2, wherein said log-likelihood value is one of a log-likelihood ratio or an approximation of a log-likelihood ratio.

4. The method of claim 1, further comprising the step of generating said received value by multiplying a detected value with a constant.

5. The decoder processing method of claim 4, wherein the received value is part of a received codeword.

6. The method of claim 1, wherein the step of quantizing the received value includes:

generating a sign bit and a magnitude value which, in combination, comprise said quantized value.

7. The method of claim 6, wherein the step of performing one of a check node and a variable node processing operation includes:

shifting a fixed number as a function of the magnitude value included in said quantized value to generate a transformed magnitude value; and

performing at least one check node processing operation on said transformed magnitude value to produce an outgoing transformed magnitude value.

8. The method of claim 7, wherein the step of performing one of a check node and a variable node processing operation further includes:

performing a second transform operation to generate a log-likelihood message magnitude value.

9. The method of claim 8, wherein the step of performing one of a check node and a variable node processing operation further includes:

performing at least one check node processing operation on the sign bit of said quantized value to produce an outgoing sign bit value.

10. The method of claim 9, wherein the step of performing one of a check node and a variable node processing operation further includes:

combining the outgoing sign bit value with the generated log-likelihood message magnitude value to produce a decoder message.

11. The method of claim 10, wherein said decoder message is a constraint node to variable node decoder message.

12. The method of claim 11, further comprising the steps of:

storing the constraint node to variable node decoder message in a memory;

supplying the stored constraint node to variable node decoder message to a variable node processor; and

operating the variable node processor to generate a variable node to constraint node message as a function of said constraint node to variable node decoder message.

13. A message passing decoder method, the method comprising the steps of:

quantizing an input value, using quantization step sizes which are integer multiples of ½

ln 2, to produce a quantized log-likelihood value; and

performing a message passing decoder processing operation using said quantized log-likelihood value as an input.

14. The method of claim 13, wherein the step of quantizing an input value:

generating a sign bit and a magnitude value which, in combination, comprise said quantized log-likelihood value.

15. The method of claim 14, wherein the step of performing a message passing decoder processing operation includes:

shifting a fixed number as a function of the magnitude value included in said quantized log-likelihood value to generate a transformed magnitude value; and

performing at least one check node processing operation on said transformed magnitude value to produce an outgoing transformed magnitude value.

16. The method of claim 13, wherein said likelihood value is a log-likelihood ratio or an approximation of a log-likelihood ratio.

17. The method of claim 13, comprising the step of:

detecting a transmitted value; and

multiplying said detected transmitted value by a constant to generate said log-likelihood value.

18. The method of claim 13, wherein said step of performing message passing decoder processing operation includes:

performing a variable node processing operation using said quantized log-likelihood value as input.

19. The method of claim 18, wherein said variable node processing operation is a low density parity check code variable node operation.

20. A device for processing detected values, the device comprising:

means for generating log-likelihood values quantized to integer multiples of ½

ln 2 to produce quantized log-likelihood values; and

a parity check decoder, coupled to said means for generating log-likelihood values, for performing parity check decoding operations using said quantized log-likelihood values as input values.

21. The device of claim 20, wherein said parity check decoder includes:

variable node processing circuitry for performing a variable node processing operation using at least some of said produced quantized log-likelihood values; and

check node processing circuitry for performing a check node processing operation on quantized log-likelihood values produced by variable node processing.

22. The device of claim 21,

wherein each generated quantized log-likelihood value includes a sign bit and a magnitude value;

and

wherein said check node processing circuitry includes a shifting circuit for shifting a fixed number as a function of the magnitude value included in at least one quantized log-likelihood value to generate a transformed magnitude value.

23. The device of claim 22, wherein said check node processing circuitry further includes:

means for performing at least one check node processing operation on said transformed magnitude value to produce an outgoing transformed magnitude value.

24. A device for performing node processing operations as part of a message passing decoding process, the device comprising:

an accumulator module for processing, in sequence, input messages corresponding to a plurality of nodes, one set of input messages being received per node, the number of messages in a set of messages corresponding to a node being equal to a degree, D, of said node, where D is a non-zero positive integer, the accumulator module including;

a summing circuit for generating a total node sum as a function of the value of each received message in a set of messages corresponding to a node, one total node sum being generated for each received set of messages;

a storage device for storing the generated total node sum;

a controllable delay unit for storing said input messages processed by said summing circuit to generate each total sum by a period of time proportional to the degree of the node to which the input messages correspond; and

a message generation module for generating output messages corresponding to a node from the total sum corresponding to the node and the delayed messages corresponding to said node, the message generation module generating one output message for each input message corresponding to a node.

25. The device of claim 24, wherein the message generation module further comprising:

a subtraction circuit coupled to said storage device and delay element for subtracting each delayed message value corresponding to a node from the total sum corresponding to said node.

26. The device of claim 25, wherein said controllable delay unit includes an input for receiving a node degree signal indicating the degree of a node corresponding to messages being received by said controllable delay unit.

27. The device of claim 26, wherein said controllable delay unit is implemented as a first-in-first out data storage device.

28. The device of claim 25, wherein said summing circuit includes:

a summer having a first input for receiving input messages;

an additional storage device coupled to said summer and to said storage device for storing a running sum generated by said summer and for outputting said stored running sum; and

a multiplexer, coupled to said additional storage device for receiving from said additional storage device the stored running sum and for outputting one of the stored running sum and a zero to a second input of said summer under control of a node clock signal.

29. The device of claim 28,

wherein said storage device further includes a control input for receiving said node clock signal, said storage device storing the stored running sum to be used as the total node sum under direction of said node clock signal.

30. The device of claim 29, further comprising:

means for asserting the node clock signal to cause the multiplexer to output a zero when a first message corresponding to a node is received by said summing circuit.

31. The device of claim 30, wherein the node clock signal causes said storage device to store the running sum as the total node sum at the same time it causes the multiplexer to output a zero.

32. A node processor for use in a message passing decoding system, the node processor including:

an accumulator module for generating a total message sum from a set of received messages corresponding to a node;

a message delay line including a variable delay element for storing the messages in each set of received messages for a period of time directly proportional to the degree of a node to which the stored message corresponds; and

a subtractor module coupled to said accumulator module and to said message delay line, the subtractor module subtracting each delayed message corresponding to a node from the total message sum generated by the accumulator module from the set of received messages corresponding to the same node as the delayed messages being subtracted.

33. The node processor of claim 32, wherein said accumulator module includes:

a latch for storing an accumulated sum corresponding to a node, for which messages are being processed, accumulated sums corresponding to different nodes being stored in said latch sequentially.

34. The node processor of claim 33, wherein said node processor further includes:

means for generating a running sum of messages corresponding to a node; and

means for resetting said running sum in response to a control signal used to store said running sum in said latch, said stored running sum being an accumulated sum.

35. The node processor of claim 34,

wherein said node processor is a variable node processor;

and

wherein said accumulator module further includes a summer for adding an input value to said running sum of messages prior to said running sum being stored in said latch.

36. The node processor of claim 34, wherein the variable delay element includes a plurality of message storage locations, the number of message storage locations in said plurality of message storage locations being at least as large as the highest degree of a node for which processing operations are to be performed by said node processor.

37. The node processor of claim 36, wherein the variable delay element further includes a control input for receiving a signal indicating the degree of the node corresponding to the messages being received by said variable delay element.

38. A method of performing node processing operations in a message passing decoder, the method comprising the steps of:

sequentially receiving messages to be processed, each message corresponding to a node, messages corresponding to the same node being part of a set of messages, sets of messages corresponding to a plurality of different nodes being received over a period of time;

generating from each set of received messages corresponding to a node, a total message sum corresponding to the same node as the set of messages used to generate the total sum;

delaying each individual received message for a period of time directly proportional to the degree of the node to which the individual received message corresponds; and

subtracting each delayed message, from the total message sum corresponding to the same node as the delayed message, to thereby generate an output message.

39. The method of claim 38, wherein said step of delaying each individual received message includes the step of:

receiving a control signal indicating the degree of the node to which a message being received for processing corresponds.

40. The method of claim 39, further comprising the step of:

adding each received message to a running sum of received messages to generate said total message sum for each set of received messages.

41. The method of claim 40, further comprising the step of:

latching the running sum into a storage device once the last message in a set of messages has been added to the running sum, the latched running sum being the total message sum.

42. The method of claim 41, further comprising:

adding an input value to said running sum prior to latching the running sum into the storage device.

43. The method of claim 41, further comprising the step of initializing the running sum to zero each time a message corresponding to a different node than the immediately preceding received message is received.

44. The method of claim 41, wherein said latching and initializing are control by the same control signal.

45. The method of claim 40, further comprising the step of outputting the generated output messages in sequence, one at a time.