Non-binary LDPC decoder using binary subgroup processing
View Patent ↗In one embodiment, an electronic system includes a decoder configured to decode an encoded data unit using multiple variable nodes and multiple check nodes to perform a low-density parity check (LDPC) decoding process. The encoded data unit can be received from a solid-state memory array. As part of performing the LDPC decoding process, the decoder can (i) convert reliability information representing first non-binary values to reliability information representing first binary values, (ii) determine reliability information representing second binary values using the reliability information representing first binary values, and (iii) convert the reliability information representing the second binary values to reliability information representing second non-binary values.
1. A decoder configured to:
convert, during each of a plurality of iterations, a plurality of first non-binary values provided at a plurality of variable nodes to input binary values;
generate, by a plurality of check nodes, output binary values based on the converted input binary values;
convert the output binary values to second non-binary values for processing by the plurality of variable nodes;
update, by the plurality of variable nodes, reliability data based on the converted second non-binary values; and
determine at least a portion of a valid codeword based on the updated reliability data over the plurality of iterations.
2. The decoder of claim 1 , wherein a respective variable node of the plurality of variable nodes store a vector of reliability values, the decoder further configured to:
permute the vector into a plurality of permutations based on at least a portion of a decoding matrix, wherein each permutation is converted to a respective one of the input binary values and distributed among the plurality of check nodes according to a code graph.
3. The decoder of claim 2 , wherein each of the input binary values is generated based on a respective permutation and a respective decomposition algorithm corresponding to the respective permutation.
4. The decoder of claim 3 , wherein each of the output binary values is generated based on a respective one of the input binary values and a conversion algorithm corresponding to the respective one of the input binary values.
5. The decoder of claim 4 , wherein the conversion algorithm functions as an inverse of the decomposition algorithm that corresponds to the respective one of the input binary values.
6. The decoder of claim 5 , wherein the decoder is further configured to:
sort at least a subset of the input binary values;
compare each sorted input binary value with zero; and
assign one or more of the sorted input binary value to one or more respective elements of a return vector according to the comparison.
7. The decoder of claim 6 , wherein zero is assigned to a largest element of the return vector, a second largest of the input binary values is assigned to a second largest element of the return vector, a third largest of the input binary values is assigned to a third largest element of the return vector, and a result of a function of a third and fourth of the input binary values is assigned to a fourth largest element of the return vector.
8. The decoder of claim 1 , wherein the first non-binary values are first vectors and the second non-binary values are second vectors of a same vector size as the first vectors, each of the first and second vectors comprising a number of reliability values according to the same vector size.
9. The decoder of claim 8 , wherein the reliability values are log-likelihood ratio values.
10. The decoder of claim 9 , wherein the reliability values of each of the first vectors are permutated into three or more respective permutations, converted to three or more corresponding binary permutations, and distributed among three or more corresponding check nodes, and
wherein each of the three or more corresponding check nodes operates on one of the three or more corresponding binary permutations, which are then each converted to vectors in accordance with an inverse decomposition algorithm.
11. A method, comprising:
converting, during each of a plurality of decoding iterations, a plurality of first non-binary values provided at a plurality of variable nodes to input binary values;
generating, by a plurality of check nodes, output binary values based on the converted input binary values;
converting the output binary values to second non-binary values for processing by the plurality of variable nodes;
updating, by the plurality of variable nodes, reliability data based on the converted second non-binary values; and
determining at least a portion of a valid codeword based on the updated reliability data over the plurality of decoding iterations.
12. The method of claim 11 , wherein a respective variable node of the plurality of variable nodes comprises a vector of reliability values, the method further comprising:
arranging the vector into a plurality of permutations based on at least a portion of a decoding matrix, wherein each permutation is converted to a respective one of the input binary values and distributed among the plurality of check nodes according to a code graph.
13. The method of claim 12 , wherein each of the input binary values is generated based on a respective permutation and a respective decomposition algorithm corresponding to the respective permutation.
14. The method of claim 13 , wherein each of the output binary values is generated based on a respective one of the input binary values and a conversion algorithm corresponding to the respective one of the input binary values.
15. The method of claim 14 , wherein the conversion algorithm functions as an inverse of the decomposition algorithm that corresponds to the respective one of the input binary values.
16. The method of claim 15 , further comprising:
sort at least a subset of the input binary values;
compare each sorted input binary value with zero; and
assign one or more of the sorted input binary value to one or more respective elements of a return vector according to the comparison.
17. The method of claim 16 , wherein zero is assigned to a largest element of the return vector, a second largest of the input binary values is assigned to a second largest element of the return vector, a third largest of the input binary values is assigned to a third largest element of the return vector, and a result of a function of a third and fourth of the input binary values is assigned to a fourth largest element of the return vector.
18. The method of claim 11 , wherein the first non-binary values are first vectors and the second non-binary values are second vectors of a same vector size as the first vectors, each of the first and second vectors comprising a number of reliability values according to the same vector size.
19. The method of claim 18 , wherein the reliability values are log-likelihood ratio values.
20. The method of claim 19 , wherein the reliability values of each of the first vectors are permutated into three or more respective permutations, converted to three or more corresponding binary permutations, and distributed among three or more corresponding check nodes, and
wherein each of the three or more corresponding check nodes operates on one of the three or more corresponding binary permutations, which are then each converted to vectors in accordance with an inverse decomposition algorithm.