LDPC decoder variable node units having fewer adder stages
View Patent ↗In one embodiment, the present invention is a variable node unit (VNU) of a low-density parity-check (LDPC) decoder. The VNU receives a soft-input value and w c check node messages, where w c is the column hamming weight of the LDPC code. The VNU generates (i) an extrinsic log-likelihood ratio (LLR) by adding all w c check node messages together; (ii) a hard-decision output by adding the extrinsic LLR to the soft-input value and selecting the sign bit of the resulting sum; and (iii) w c variable node messages. Each variable node message is generated by adding a different set of (w c −1) check node messages to the soft-input value where each set excludes a different check node message. In so doing, VNUs of the present invention may generate variable node messages using fewer adder stages compared to prior-art VNUs such that throughput may be increased over that of prior-art VNUs.
1. In a low-density parity-check (LDPC) decoder having at least one variable node unit (VNU), a method for generating a plurality of variable node messages by the VNU, the method comprising:
(a) receiving a set of three or more check node messages; and
(b) generating each of the plurality of variable node messages by summing a different subset of the set of check node messages, wherein:
each different subset of the check node messages excludes a different check node message of the set; and
each variable node message is generated without subtracting the corresponding different check node message from a value corresponding to a sum of all of the check node messages.
2. The invention of claim 1 , wherein:
step (a) further comprises receiving a soft-input value; and
in step (b), generating each of the plurality of variable node messages is further based on the soft-input value.
3. The invention of claim 2 , wherein step (b) further comprises:
(b1) doubling the soft-input value to generate a doubled soft-input value;
(b2) generating each variable node message by adding in the doubled soft-input value; and
(b3) applying normalization and truncation to each variable node message.
4. The invention of claim 3 , wherein:
step (a) comprises receiving first, second, third, and fourth check node messages; and
step (b) is performed using first, second, and third adder stages, wherein:
the first adder stage (i) sums the first and second check node messages to generate a first partial sum and (ii) sums the third and fourth check node messages to generate a second partial sum;
the second adder stage (i) sums the first partial sum and the doubled soft-input value to generate a third partial sum and (ii) sums the second partial sum and the doubled soft-input value to generate a fourth partial sum; and
the third adder stage (i) sums the fourth partial sum and the second check node message to generate a first variable node message, (ii) sums the fourth partial sum and the first check node message to generate a second variable node message, (iii) sums the third partial sum and the fourth check node message to generate a third variable node message, and (iv) sums the third partial sum and the third check node message to generate a fourth variable node message.
5. The invention of claim 3 , wherein:
step (a) comprises receiving first, second, third, and fourth check node messages; and
step (b) is performed using first and second adder stages, wherein:
the first adder stage (i) sums the first and second check node messages to generate a first partial sum, (ii) sums the third and fourth check node messages to generate a second partial sum, (iii) sums the first check node message and the doubled soft value to generate a third partial sum, (iv) sums the second check node message and the doubled soft value to generate a fourth partial sum, (v) sums the third check node message and the doubled soft value to generate a fifth partial sum, and (vi) sums the fourth check node message and the doubled soft value to generate a sixth partial sum; and
the second adder stage (i) sums the second partial sum and the fourth partial sum to generate the first variable node message, (ii) sums the second partial sum and the third partial sum to generate the second variable node message, (iii) sums the first partial sum and the sixth partial sum to generate the third variable node message, and (iv) sums the first partial sum and the fifth partial sum to generate the fourth variable node message.
6. The invention of claim 1 , wherein:
decoding by the LDPC decoder is based on an LDPC code;
the plurality of variable node messages corresponds to a column of the LDPC code having a hamming weight w c ; and
w c variable node messages are generated using a plurality of adder stages, wherein the plurality of adder stages has no more than ceil(log 2 (w c +1)) adder stages.
7. The invention of claim 6 , wherein:
w c equals four; and
four variable node messages are generated using three adder stages.
8. The invention of claim 6 , wherein:
w c equals four; and
four variable node messages are generated using two adder stages.
9. A low-density parity-check (LDPC) decoder having at least one variable node unit (VNU), wherein the VNU comprises:
a plurality of adder stages adapted to receive a set of three or more check node messages and generate each of a plurality of variable node messages by summing a different subset of the set of check node messages, wherein:
each different subset of the check node messages excludes a different check node message of the set; and
the VNU is adapted to generate each variable node message without subtracting the corresponding different check node message from a value corresponding to a sum of all of the check node messages.
10. The invention of claim 9 , wherein:
the VNU is adapted to receive a soft-input value; and
the plurality of adder stages is adapted to generate each of the plurality of variable node messages based on the soft-input value.
11. The invention of claim 10 , wherein:
the VNU is further adapted to double the soft-input value to generate a doubled soft-input value;
the plurality of adder stages is adapted to generate each variable node message by adding in the doubled soft-input; and
the VNU is further adapted to apply normalization and truncation to each variable node message.
12. The invention of claim 11 , wherein:
the plurality of adder stages receives first, second, third, and fourth check node messages; and
the plurality of adder stages comprises first, second, and third adder stages, wherein:
the first adder stage (i) sums the first and second check node messages to generate a first partial sum and (ii) sums the third and fourth check node messages to generate a second partial sum;
the second adder stage (i) sums the first partial sum and the doubled soft-input value to generate a third partial sum and (ii) sums the second partial sum and the doubled soft-input value to generate a fourth partial sum; and
the third adder stage (i) sums the fourth partial sum and the second check node message to generate a first variable node message, (ii) sums the fourth partial sum and the first check node message to generate a second variable node message, (iii) sums the third partial sum and the fourth check node message to generate a third variable node message, and (iv) sums the third partial sum and the third check node message to generate a fourth variable node message.
13. The invention of claim 11 , wherein:
the plurality of adder stages receives first, second, third, and fourth check node messages; and
the plurality of adder stages comprises first and second adder stages, wherein:
the first adder stage (i) sums the first and second check node messages to generate a first partial sum, (ii) sums the third and fourth check node messages to generate a second partial sum, (iii) sums the first check node message and the doubled soft value to generate a third partial sum, (iv) sums the second check node message and the doubled soft value to generate a fourth partial sum, (v) sums the third check node message and the doubled soft value to generate a fifth partial sum, and (vi) sums the fourth check node message and the doubled soft value to generate a sixth partial sum; and
the second adder stage (i) sums the second partial sum and the fourth partial sum to generate the first variable node message, (ii) sums the second partial sum and the third partial sum to generate the second variable node message, (iii) sums the first partial sum and the sixth partial sum to generate the third variable node message, and (iv) sums the first partial sum and the fifth partial sum to generate the fourth variable node message.
14. The invention of claim 9 , wherein:
decoding by the LDPC decoder is based on an LDPC code;
the plurality of variable node messages corresponds to a column of the LDPC code having a hamming weight w c ; and
w c variable node messages are generated using the plurality of adder stages, wherein the plurality of adder stages has no more than ceil(log 2 (w c +1)) adder stages.
15. The invention of claim 14 , wherein:
w c equals four; and
four variable node messages are generated using three adder stages.
16. The invention of claim 14 , wherein:
w c equals four; and
four variable node messages are generated using two adder stages.
17. A low-density parity-check (LDPC) decoder having at least one variable node unit (VNU), the VNU comprising:
(a) means for receiving a set of three or more check node messages; and
(b) means for generating each of a plurality of variable node messages by summing a different subset of the set of check node messages, wherein:
each different subset of the check node messages excludes a different check node message of the set; and
each variable node message is generated without subtracting the corresponding different check node message from a value corresponding to a sum of all of the check node messages.