Updating variable nodes associated with an iterative decoder
In various embodiments, an iterative decoder may compute, from sign bits of log likelihood ratios associated with x bits of a plurality of bits of encoded data, a first combination of the x bits having a higher associated log density ratio than any other combination of the x bits. In various embodiments, the iterative decoder may further be configured to compute m combinations of the x bits having m highest associated log density ratios, based on reductions in log density ratios associated with one or more sub-combinations of the x bits and the computed first combination of the x bits. In various embodiments, a variable node associated with the iterative decoder may be updated with the m combinations of the x bits.
1. An apparatus, comprising:
a channel; and
an iterative decoder to decode a message on the channel, the message including a plurality of bits of data, the iterative decoder configured to:
compute, from sign bits of log likelihood ratios associated with x bits on the channel, a first combination of the x bits having a higher associated log density ratio than any other combination of the x bits, x being a positive integer;
compute m combinations of the x bits having m highest associated log density ratios, based on reductions in log density ratios associated with one or more sub-combinations of the x bits and the computed first combination of the x bits; and
update a variable node associated with the iterative decoder with the m combinations of the x bits.
2. The apparatus of claim 1 , wherein the iterative decoder is further configured to compare reductions in log density ratios associated with one or more combinations of a first subset of the x bits with reductions in log density ratios associated with one or more combinations of a second subset of the x bits.
3. The apparatus of claim 1 , wherein the iterative decoder is further configured to recursively divide the x bits into subsets until at least a first two-bit subset of the x bits is determined.
4. The apparatus of claim 3 , wherein the iterative decoder is further configured to compute a first set of tuples associated with possible combinations of the first two-bit subset of the x bits, each tuple in the first set including a symbol difference and a reduction in log density ratio.
5. The apparatus of claim 4 , wherein the iterative decoder is further configured to sort the first set of tuples by their respective reductions in log density ratios.
6. The apparatus of claim 5 , wherein the iterative decoder is further configured to compare reductions in log density ratio of the first set of tuples with reductions in log density ratio of a second set of tuples associated with possible combinations of a second two-bit subset of the x bits.
7. The apparatus of claim 6 , wherein the iterative decoder is further configured to compute a third set of tuples, each tuple in the third set including a combined symbol difference of a tuple from the first set and a tuple from the second set and a combined reduction in log density ratio of the tuple from the first set and the tuple from the second set.
8. The apparatus of claim 7 , wherein the iterative decoder is further configured to compare combined reductions in log density ratio of the third set of tuples with combined reductions in log density ratio of a fourth set of tuples each tuple of the fourth set of tuples also including a combined symbol difference.
9. The apparatus of claim 1 , wherein the iterative decoder is further configured to XOR the m computed symbol differences with the first combination of the x bits having a higher associated log density ratio than any other combination of the x bits.
10. The apparatus of claim 1 , wherein the iterative decoder is further configured to compute a log density ratio associated with at least one of the computed m combinations of the x bits by subtracting, from a log density ratio associated with the first combination of x bits having the higher associated log density ratio than any other combination of the x bits, a reduction in log density ratio associated with a symbol difference that produced the at least one of the computed m combinations of the x bits.
11. The apparatus of claim 1 , wherein the iterative decoder is a low-density parity-check decoder.
12. A computer-implemented method of updating a variable node associated with an iterative decoder of a computing device, comprising:
computing, by the iterative decoder of the computing device, from sign bits of log likelihood ratios associated with x bits on a channel, a first combination of the x bits having a higher associated log density ratio than any other combination of the x bits, x being a positive integer;
computing, by the iterative decoder, m combinations of the x bits having m highest associated log density ratios, based on reductions in log density ratios associated with one or more sub-combinations of the x bits and the computed first combination; and
updating the variable node with m combinations of the x bits.
13. The computer-implemented method of claim 12 , wherein computing m combinations of the x bits having the highest associated log density ratios comprises comparing, by the iterative decoder, reductions in log density ratios associated with one or more combinations of a first subset of the x bits with reductions in log density ratios associated with one or more combinations of a second subset of the x bits.
14. The computer-implemented method of claim 12 , wherein computing m combinations of the x bits having the highest associated log density ratios comprises recursively dividing, by the iterative decoder, the x bits into subsets until at least a first two-bit subset of the x bits is determined.
15. The computer-implemented method of claim 12 , wherein the computing m combinations of the x bits having the highest associated log density ratios comprises XORing the m computed symbol differences with the first combination of the x bits.
16. The computer-implemented method of claim 12 , further comprising computing, by the iterative decoder, a log density ratio associated with at least one of the computed m combinations of the x bits by subtracting, from a log density ratio associated with the first combination of x bits having the higher associated log density ratio than any other combination of the x bits, a reduction in log density ratio associated with a symbol difference that produced the at least one of the computed m combinations of the x bits.
17. A system, comprising:
non-volatile memory; and
a memory controller coupled with the non-volatile memory, and configured to:
compute, from sign bits of log likelihood ratios associated with x bits stored in the non-volatile memory, a first combination of the x bits having a higher associated log density ratio than any other combination of the x bits, x being a positive integer;
compute m x-bit symbol differences from the first combination of x bits, the m x-bit symbol differences having m lowest reductions in log density ratio from the log density ratio of the first combination of x bits; and
XOR the computed m x-bit symbol differences with the first combination of the x bits to compute m combinations of the x bits having m highest associated log density ratios.
18. The system of claim 17 , wherein the memory controller is further configured to compare reductions in log density ratios associated with one or more combinations of a first subset of the x bits with reductions in log density ratios associated with one or more combinations of a second subset of the x bits.
19. The system of claim 17 , wherein the memory controller is further configured to recursively divide the x bits into subsets until at least a first two-bit subset of the x bits is determined.
20. The system of claim 19 , wherein the memory controller is further configured to compute a first set of tuples associated with possible combinations of the first two-bit subset of the x bits, each tuple in the first set including a symbol difference and a reduction in log density ratio; and sort the first set of tuples by their respective reductions in log density ratios.
21. The system of claim 20 , wherein the memory controller is further configured to compare reductions in log density ratio of the first set of tuples with reductions in log density ratio of a second set of tuples associated with possible combinations of a second two-bit subset of the x bits.
22. The system of claim 21 , wherein the memory controller is further configured to compute a third set of tuples, each tuple in the third set including a combined symbol difference of a tuple from the first set and a tuple from the second set and a combined reduction in log density ratio of the tuple from the first set and the tuple from the second set.
23. The system of claim 22 , wherein the memory controller is further configured to compare combined reductions in log density ratio of the third set of tuples with combined reductions in log density ratio of a fourth set of tuples each tuple of the fourth set of tuples also including a combined symbol difference.
24. The system of claim 22 , wherein the memory controller is further configured to XOR the m computed symbol differences with the first combination of the x bits having a higher associated log density ratio than any other combination of the x bits.
25. The system of claim 17 , wherein the memory controller is further configured to compute a log density ratio associated with at least one of the computed m combinations of the x bits by subtracting, from a log density ratio associated with the first combination of x bits having the higher associated log density ratio than any other combination of the x bits, a reduction in log density ratio associated with a symbol difference that was used to produce the at least one of the computed m combinations of the x bits.