Compressing check node unit parameters in low-density parity-check codes in non-volatile memory devices
Devices, systems, and methods for improving performance of an iterative decoder in a non-volatile memory are described. An example method includes receiving a noisy codeword that is based on a transmitted codeword generated from a low-density parity-check (LDPC) code, and performing, on the noisy codeword, a message passing algorithm. As part of the message passing algorithm, a check node is configured to receive each of multiple messages from a corresponding variable node connected to the check node. Then, the check node identifies, based on the multiple messages, check node unit (CNU) parameters, and maps a concatenation of the CNU parameters to a bit string that has a length less than that of the concatenation. The bit string, which is a compressed form of the CNU parameters, is stored in a CNU register, and used to process the noisy codeword to determine a candidate version of the transmitted codeword.
1 . A method for improving a performance of an iterative decoder in a non-volatile memory, comprising:
receiving a noisy codeword that is based on a transmitted codeword generated from a low-density parity-check (LDPC) code;
performing, on the noisy codeword for a first iteration, a message passing algorithm between a plurality of variable nodes and a plurality of check nodes that represent a parity matrix of the LDPC code,
wherein, as part of performing the message passing algorithm, at least one check node of the plurality of check nodes is configured to:
receive each of a plurality of messages from a corresponding variable node of a subset of the plurality of variable nodes connected to the at least one check node, each of the plurality of messages comprising a sign and a magnitude,
identify (i) a first minimum value corresponding to a smallest magnitude amongst the plurality of messages, (ii) a second minimum value, greater than the first minimum value, corresponding to a second smallest magnitude amongst the plurality of messages, (iii) a first index associated with the first minimum value, and (iv) a second index associated with the second minimum value,
map a concatenation of the smallest magnitude, the second smallest magnitude, the first index, and the second index to a bit string, wherein a length of the bit string is less than a length of the concatenation, and
store the bit string in a check node unit (CNU) register; and
performing, on the noisy codeword for a remaining number of iterations, the message passing algorithm to determine a candidate version of the transmitted codeword.
2 . The method of claim 1 , wherein, as part of performing the message passing algorithm, the at least one check node of the plurality of check nodes is configured to:
retrieve, from the CNU register, the bit string; and
demap the bit string to determine the smallest magnitude, the second smallest magnitude, the first index, and the second index.
3 . The method of claim 2 , wherein, as part of performing the message passing algorithm, the at least one check node of the plurality of check nodes is configured to:
perform, subsequent to demapping the bit string, a CNU update and a calculation to generate a check node to variable node (C2V) message.
4 . The method of claim 1 , wherein the first index corresponds to a variable node of the subset of the plurality of variable nodes from which a message with the first minimum value is received by the at least one check node.
5 . The method of claim 1 , wherein a length of the first index is based on a largest check node weight amongst the plurality of check nodes.
6 . The method of claim 5 , wherein the largest check node weight is not a power of two.
7 . The method of claim 1 , wherein the message passing algorithm comprises a vertically shuffled scheduling (VSS) operation.
8 . The method of claim 1 , wherein the length of the bit string is based on a total number of CNU configurations.
9 . A system for improving a performance of an iterative decoder in a non-volatile memory, comprising:
a processor and a memory including instructions stored thereupon, wherein the instructions upon execution by the processor cause the processor to:
receive a noisy codeword that is based on a transmitted codeword generated from a low-density parity-check (LDPC) code;
perform, on the noisy codeword for a first iteration, a message passing algorithm between a plurality of variable nodes and a plurality of check nodes that represent a parity matrix of the LDPC code,
wherein, as part of performing the message passing algorithm, at least one check node of the plurality of check nodes is configured to:
receive, each of a plurality of messages from a corresponding variable node of a subset of the plurality of variable nodes connected to the at least one check node, each of the plurality of messages comprising a sign and a magnitude,
identify (i) a first minimum value corresponding to a smallest magnitude amongst the plurality of messages, (ii) a second minimum value, greater than the first minimum value, corresponding to a second smallest magnitude amongst the plurality of messages, (iii) a first index associated with the first minimum value, and (iv) a second index associated with the second minimum value,
map a concatenation of the smallest magnitude, the second smallest magnitude, the first index, and the second index to a bit string, wherein a length of the bit string is less than a length of the concatenation, and
store the bit string in a check node unit (CNU) register; and
perform, on the noisy codeword for a remaining number of iterations, the message passing algorithm to determine a candidate version of the transmitted codeword.
10 . The system of claim 9 , wherein, as part of performing the message passing algorithm, at least one check node of the plurality of check nodes is configured to:
retrieve, from the CNU register, the bit string;
demap the bit string to determine the smallest magnitude, the second smallest magnitude, the first index, and the second index; and
perform, subsequent to demapping the bit string, a CNU update and a calculation to generate a check node to variable node (C2V) message.
11 . The system of claim 9 , wherein the first index corresponds to a variable node of the subset of the plurality of variable nodes from which a message with the first minimum value is received by the at least one check node.
12 . The system of claim 9 , wherein a length of the first index is based on a largest check node weight amongst the plurality of check nodes, and wherein the largest check node weight is not a power of two.
13 . The system of claim 9 , wherein the message passing algorithm comprises a vertically shuffled scheduling (VSS) operation.
14 . The system of claim 9 , wherein the length of the bit string is based on a total number of CNU configurations.
15 . A non-transitory computer-readable storage medium having instructions stored thereupon for improving performance of an iterative decoder in a non-volatile memory device, comprising:
instructions for receiving a noisy codeword that is based on a transmitted codeword generated from a low-density parity-check (LDPC) code;
instructions for performing, on the noisy codeword for a first iteration, a message passing algorithm between a plurality of variable nodes and a plurality of check nodes that represent a parity matrix of the LDPC code,
wherein, as part of performing the message passing algorithm, at least one check node of the plurality of check nodes is configured to:
receive, each of a plurality of messages from a corresponding variable node of a subset of the plurality of variable nodes connected to the at least one check node, each of the plurality of messages comprising a sign and a magnitude,
identify (i) a first minimum value corresponding to a smallest magnitude amongst the plurality of messages, (ii) a second minimum value, greater than the first minimum value, corresponding to a second smallest magnitude amongst the plurality of messages, (iii) a first index associated with the first minimum value, and (iv) a second index associated with the second minimum value,
map a concatenation of the smallest magnitude, the second smallest magnitude, the first index, and the second index to a bit string, wherein a length of the bit string is less than a length of the concatenation, and
store the bit string in a check node unit (CNU) register; and
instructions for performing, on the noisy codeword for a remaining number of iterations, the message passing algorithm to determine a candidate version of the transmitted codeword.
16 . The non-transitory computer-readable storage medium of claim 15 , wherein, as part of performing the message passing algorithm, at least one check node of the plurality of check nodes is configured to:
retrieve, from the CNU register, the bit string; and
demap the bit string to determine the smallest magnitude, the second smallest magnitude, the first index, and the second index.
17 . The non-transitory computer-readable storage medium of claim 16 , wherein, as part of performing the message passing algorithm, the at least one check node of the plurality of check nodes is configured to:
perform, subsequent to demapping the bit string, a CNU update and a calculation to generate a check node to variable node (C2V) message.
18 . The non-transitory computer-readable storage medium of claim 15 , wherein the first index corresponds to a variable node of the subset of the plurality of variable nodes from which a message with the first minimum value is received by the at least one check node.
19 . The non-transitory computer-readable storage medium of claim 15 , wherein a length of the first index is based on a largest check node weight amongst the plurality of check nodes, and wherein the largest check node weight is not a power of two.
20 . The non-transitory computer-readable storage medium of claim 15 , wherein the length of the bit string is based on a total number of CNU configurations.