Low power low-density parity-check decoding

Patent metadata

Field	Value
Publication number	US-9590657-B2
Application number	US-201514615717-A
Country	US
Kind code	B2
Filing date	Feb 6, 2015
Priority date	Feb 6, 2015
Publication date	Mar 7, 2017
Grant date	Mar 7, 2017

Abstract

In general, a minimum determination capability, adapted for determining one or more minimum values from a set of values, is provided. The minimum determination capability may enable, for a set of values, determination of a first minimum value representing a smallest value of the set of values and a second minimum value representing an approximation of a next-smallest value of the set of values. The minimum determination capability may enable, for a set of values where each of the values is represented as a respective set of bits at a respective set of bit positions, determination of a minimum value of the set of values based on a set of bitwise comparisons performed for the respective bit positions of the values.

First claim

What is claimed is:

1. An apparatus configured to evaluate a set of values organized based on a set of bit positions, each of the values including a respective set of bits associated with the respective bit positions, the apparatus comprising:
a set of hardware modules associated with the respective bit positions, the set of hardware modules configured to determine, based on a set of bitwise comparisons performed for the respective bit positions based on the bits of the values associated with the respective bit positions, a magnitude of a minimum value of the set of values;
wherein, for each of the hardware modules associated with the respective bit positions, the respective hardware module includes a respective bit detector module configured to receive a respective set of input bits for the respective bit position and configured to generate a respective output bit indicative as to whether at least one of the input bits for the respective bit position is a first bit value;
wherein, for each of a subset of the hardware modules associated with the respective bit positions, the respective hardware module includes a respective mask generation module configured to generate, based on the respective set of bits associated with the respective bit position and based on the respective output bit generated by the respective bit detector module for the respective bit position, a respective disable signal comprising a respective set of disable bits associated with the respective values of the set of values, wherein, based on the respective output bit generated by the respective bit detector module for the respective bit position being indicative that at least one of the input bits for the respective bit position is the first bit value, each of the disable bits associated with a respective one of the values for which the bit in the respective bit position of the value is a second bit value and the bit in a next bit position of the value is the first bit value is configured to change the bit in the next bit position of the value from the first bit value to the second bit value for processing by the bit detector module associated with the next bit position.

2. The apparatus of claim 1 , wherein, for a most significant bit (MSB) position of the set of bit positions, the respective set of input bits comprises the MSBs of the values of the set of values.

3. The apparatus of claim 1 , wherein, for a given one of the bit positions of the set of bit positions other than the most significant bit (MSB) position of the set of bit positions, the respective set of input bits received by the respective bit detector module comprises a set of masked bits formed based on the respective set of bits of the given one of the bit positions and the respective disable signal associated with a next-least-significant bit position of the set of bit positions.

4. The apparatus of claim 1 , wherein, to generate the respective output bit indicative as to whether at least one of the input bits for the respective bit position is the first bit value, the respective bit detector module is configured to:
set the respective output bit to the first bit value based on a determination that at least one of the input bits for the respective bit position is the first bit value or set the respective output bit to a second bit value based on a determination that none of the input bits for the respective bit position are the first bit value.

5. The apparatus of claim 1 , wherein, to generate the respective output bit indicative as to whether at least one of the input bits for the respective bit position is the first bit value, the respective bit detector module is configured to:
perform a logical AND operation on the respective input bits at the respective bit position to provide thereby the respective output bit for the respective bit position.

6. The apparatus of claim 1 , wherein, to generate the respective output bit indicative as to whether at least one of the input bits for the respective bit position is the first bit value, the respective bit detector module is configured to:
a logical NAND operation on the respective input bits at the respective bit position to provide an intermediate bit; and
invert the intermediate bit to provide thereby the respective output bit for the respective bit position.

7. The apparatus of claim 1 , wherein the output bits are collectively indicative of the magnitude of the minimum value of the set of values.

8. The apparatus of claim 1 , wherein the set of hardware modules is configured to:
output the output bits, wherein the output bits are collectively indicative of the magnitude of the minimum value of the set of values.

9. The apparatus of claim 1 , wherein the set of hardware modules is configured to determine, based on the set of bitwise comparisons performed for the respective bit positions, an identification of one of the values of the set of values having the magnitude of the minimum value of the set of values.

10. The apparatus of claim 9 , wherein one of the hardware modules associated with a least significant bit (LSB) position of the set of bit positions is configured to:
output an indicator value providing the identification of the one of the values of the set of values having the magnitude of the minimum value of the set of values.

11. The apparatus of claim 10 , wherein, to output the indicator value, the one of the hardware modules associated with the LSB position is configured to:
generate a set of masked bits associated with the LSB position of the set of bit positions based on the respective set of LSBs of the values and the respective disable signal associated with a next-least-significant bit position of the set of bit positions; and
determine, based on the set of masked bits associated with the LSB position of the set of bit positions, the one of the values of the set of values having the magnitude of the minimum value of the set of values.

12. The apparatus of claim 11 , wherein, to determine, based on the set of masked bits associated with the LSB position of the set of bit positions, the one of the values of the set of values having the magnitude of the minimum value of the set of values, the hardware module associated with the LSB position is configured to:
perform a lookup, using the set of masked bits as a key, to determine the indicator value providing the identification of the one of the values of the set of values having the magnitude of the minimum value of the set of values.

13. The apparatus of claim 1 , wherein the subset of the hardware modules comprises the hardware modules associated with each of the bit positions except for a least significant bit (LSB) position of the set of bit positions.

14. The apparatus of claim 1 , wherein, for each of a second subset of the hardware modules associated with the respective bit positions, the respective hardware module includes a respective mask application module configured to apply the respective disable signal associated with a next-least-significant bit position of the set of bit positions to the respective set of bits of the respective bit position to provide thereby a set of masked bits for use as the respective set of input bits for the respective bit detector module of the respective bit position.

15. The apparatus of claim 14 , wherein, for at least one of the mask application modules of the second subset of hardware modules, the mask application module comprises:
a respective set of NOR gates configured to receive the respective disable bits of the respective disable signal associated with the next-least-significant bit position of the set of bit po

Assignees

• Sedighi Behnam
• Anthapadmanabhan Nagaraj Prasanth
• Suvakovic Dusan
• Alcatel Lucent Usa Inc

Inventors

• Sedighi Behnam
• Anthapadmanabhan Nagaraj Prasanth
• Suvakovic Dusan

Classifications

• H03M13/1122

  storing only the first and second minimum values per check node · CPC title

• H03M13/6572

  Implementations using a tree structure, e.g. implementations in which the complexity is reduced by a tree structure from O(n) to O (log(n)) · CPC title

• H03M13/6575

  Implementations based on combinatorial logic, e.g. Boolean circuits · CPC title

• H03M13/112 Primary

  with correction functions for the min-sum rule, e.g. using an offset or a scaling factor · CPC title

• H03M13/6577

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