Coset probability based decoding for non-binary LDPC codes

A controller for a solid state storage device, wherein the controller is configured for:

• reading bits from memory cells of the solid state storage device, wherein the read bits are encoded with a Q-ary LDPC code defined over a binary-extension Galois field GF(2r) and having length N;
• mapping the read bits into N symbols each one including, for each bit thereof, a bit value and a reliability thereof;
• decoding the N symbols based on a binary Tanner graph of the Q-ary LDPC code, wherein the binary Tanner graph is determined based on a Q-ary Tanner graph of the Q-ary LDPC code, and based on a binary coset representation of the Galois field GF(2r) according to which the Galois field GF(2r) includes a plurality of cosets of additive subgroups of size 2(r-1) and each element of the Galois field GF(2r) is represented as a binary value indicative of the belonging or non-belonging of that element to each one of said plurality of cosets, and wherein the binary Tanner graph comprises for each Q-ary variable node/Q-ary check node pair of the Q-ary Tanner graph:
• (2r−1) binary variable nodes each one being associated with a respective one of said cosets;
• (2r−1−r) binary parity-check nodes each one being connected to one or more of said (2r−1) binary variable nodes according to said binary coset representation of the Galois field GF(2r), wherein each binary parity-check node corresponds to a respective parity-check equation associated with a first parity-check matrix that results from said binary coset representation, and
• (2r−1) binary check nodes each one being connected to a respective one of said (2r−1) binary variable nodes according to a second parity-check matrix defining the Q-ary LDPC code,
• wherein the controller is configured for performing said decoding of the N symbols by providing each symbol of said N symbols to a respective Q-ary variable node, wherein each bit of said each symbol is provided to a respective one of the (2r−1) binary variable nodes of said respective Q-ary variable node, and by iteratively decoding each symbol based on bit reliabilities of each bit of that symbol determined at each respective binary variable node and at each binary check node connected to that binary variable node, and based on the parity-check equation associated with the first parity-check matrix and corresponding to the parity-check node connected to that binary variable node.

A solid state storage device comprising memory cells and a controller, wherein the controller is configured for:

• reading bits from the memory cells of the solid state storage device, wherein the read bits are encoded with a Q-ary LDPC code defined over a binary-extension Galois field GF(2r) and having length N;
• mapping the read bits into N symbols each one including, for each bit thereof, a bit value and a reliability thereof;
• decoding the N symbols based on a binary Tanner graph of the Q-ary LDPC code, wherein the binary Tanner graph is determined based on a Q-ary Tanner graph of the Q-ary LDPC code, and based on a binary coset representation of the Galois field GF(2r) according to which the Galois field GF(2r) includes a plurality of cosets of additive subgroups of size 2(r-1) and each element of the Galois field GF(2r) is represented as a binary value indicative of the belonging or non-belonging of that element to each one of said plurality of cosets, and wherein the binary Tanner graph comprises for each Q-ary variable node/Q-ary check node pair of the Q-ary Tanner graph:
• (2r−1) binary variable nodes each one being associated with a respective one of said cosets;
• (2r−1−r) binary parity-check nodes each one being connected to one or more of said (2r−1) binary variable nodes according to said binary coset representation of the Galois field GF(2r), wherein each binary parity-check node corresponds to a respective parity-check equation associated with a first parity-check matrix that results from said binary coset representation, and
• (2r−1) binary check nodes each one being connected to a respective one of said (2r−1) binary variable nodes according to a second parity-check matrix defining the Q-ary LDPC code,
• wherein the controller is configured for performing said decoding of the N symbols by providing each symbol of said N symbols to a respective Q-ary variable node, wherein each bit of said each symbol is provided to a respective one of the (2r−1) binary variable nodes of said respective Q-ary variable node, and by iteratively decoding each symbol based on bit reliabilities of each bit of that symbol determined at each respective binary variable node and at each binary check node connected to that binary variable node, and based on the parity-check equation associated with the first parity-check matrix and corresponding to the parity-check node connected to that binary variable node.