A method for iteratively decoding read bits in a solid state storage device. The read bits are encoded with a Q-ary LDPC code defined over a binary-extension Galois field GF(2.sup.r) and having length N. The method comprises determining a binary Tanner graph of the Q-ary LDPC code 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(2.sup.r). The binary Tanner graph comprises, for each Q-ary variable node/Q-ary check node pair of the Q-ary Tanner graph, (2.sup.r-1) binary variable nodes each one being associated with a respective one of said cosets; (2.sup.r-1-r) binary parity-check nodes each one being connected to one or more of said (2.sup.r-1) binary variable nodes according to said binary coset representation of the Galois field GF(2.sup.r), 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 (2.sup.r-1) binary check nodes each one being connected to a respective one of said (2.sup.r-1) binary variable nodes according to a second parity-check matrix defining the Q-ary LDPC code. The method further comprises, based on a Majority-Logic decoding algorithm, mapping the read bits into N symbols each one including, for each bit thereof, a bit value and a reliability thereof, and 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 (2.sup.r-1) binary variable nodes of said respective Q-ary variable node. The method also comprises, based on the Majority-Logic decoding algorithm, iteratively performing the following steps: i) at each binary check node, determining a first bit estimate and a first bit reliability of each bit of the respective symbol according to, respectively, a second bit estimate and a second bit reliability of that bit that are determined at each binary variable node connected to that binary check node, and ii) at each binary variable node, updating the second bit estimate and the second bit reliability of each bit of the respective symbol based on the first bit estimate and the first bit reliability of that bit determined 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.

This invention presents a method and apparatus for vertical layered finite alphabet iterative decoding of low-density parity-check codes (LDPC) which operate on parity check matrices that consist of blocks of sub-matrices. The iterative decoding involves passing messages between variable nodes and check nodes of the Tanner graph that associated with one or more sub-matrices constitute decoding blocks, and the messages belong to a finite alphabet. Various embodiments for the method and apparatus of the invention are presented that can achieve very high throughputs with low hardware resource usage and power.

A parity check matrix generator for generating a parity check matrix including non-binary cyclic permutation matrices may include: a first memory configured to store a first weight as location information on a non-binary cyclic permutation matrix within the parity check matrix; a second memory configured to store a second weight as cyclic strength of matrix elements of the non-binary cyclic permutation matrix; a third memory configured to store a third weight used to determine a size of a non-binary matrix element among the matrix elements of the non-binary cyclic permutation matrix; and a matrix generator configured to generate the non-binary cyclic permutation matrix by applying a non-binary value to matrix elements of 1's among matrix elements of a binary cyclic permutation matrix having a size corresponding to the non-binary cyclic permutation matrix and reflecting one or more of the first to third weights into the non-binary value.

The present technology relates to a data processing device and a data processing method which can ensure high communication quality in data transmission using LDPC codes. In group-wise interleaving, an LDPC code having a code length N of 64800 bits and a coding rate r of 13/15 is interleaved in a unit of a bit group of 360 bits. In group-wise deinterleaving, a sequence of bit groups of the LDPC code which has been subjected to the group-wise interleaving is returned to an original sequence. The present technology can be applied to, for example, a case in which data transmission is performed using LDPC codes.

Embodiments of the invention provide a check node processing unit (25-cn) configured to determine at least two check node messages in a decoder to decode a signal encoded using a NB-LDPC code, the check node processing unit comprising: data link to one or more message presorting units (24-cn) configured to determine at least three permuted variable node messages by permuting at least three variable node messages generated by one or more variable node processing units (23), each variable node message comprising components, a component comprising a symbol and a reliability metrics associated with said symbol; a syndrome sub-check node (31) configured to determine check node messages from a set of syndromes, the set of syndromes being determined from one or more intermediate messages computed from the at least three permuted variable node messages; a forward-backward sub-check node (32) configured to determine permuted check node messages at least from one of said one or more intermediate messages; a switching unit (33) configured to generate each check node message of a given index from the check node messages determined by the at least one syndrome sub-check node (31) or from the permuted check node messages determined at the at least a forward-backward sub-check node (32) depending on said given index.

A method and a device of selecting a base graph of a low-density parity-check code are provided. The method includes: acquiring a data information length and a channel coding rate of to-be-encoded data; determining a target base graph selection strategy according to the data information length and an information length range of a base graph; determining a target base graph for the to-be-encoded data according to the target base graph selection strategy and the channel coding rate.

Disclosed are methods and devices for supporting multiple page lengths with unique error correction coding via Galois field dimension folding. In one embodiment, a method comprises receiving a write instruction, the write instruction including user data; generating extended user data based on the user data, the extended user data including at least one symbol comprising a bit of the user data and a pre-stored bit pattern; generating parity data by encoding the extended user data; generating parity extension data by encoding the bit of the user data; writing a codeword to a page of a non-volatile memory device, the codeword including the parity extension data, the user data, and the parity data.

A semiconductor memory system includes: a semiconductor memory device for storing a code word; a decoder for decoding stored the code word based on a parity check matrix formed of sub-matrices to generate decoded data; and a channel for coupling the semiconductor memory device to the decoder and providing the decoder with the stored code word, wherein the decoder includes: a variable node selecting device for sequentially selecting sub-matrices sharing the same layer of the parity check matrix and sequentially selecting variable nodes respectively corresponding to columns forming the selected sub-matrices; a variable node updating device for updating the selected variable nodes based on a channel message and check node messages provided to the selected variable nodes; and a check node updating device for updating the check nodes based on variable node messages provided to the check nodes coupled to the selected variable nodes.

Devices and methods for decoding a signal encoded using an error correcting code are provided. For example, a check node processing unit is provided for a decoder to receive at least two input messages and to generate at least one output message, each message comprising a plurality of components. The check node processing unit comprises a data structure configured to store the input messages, the components of the input messages being associated with an integer index. The check node processing unit also comprises a data processing unit configured to apply one or more iterations of a transformation operation to at least a part of the data structure depending on at least some of the components of the input messages associated with a given value of the integer index, which provides a transformed data structure. The check node processing unit further comprises a calculation unit configured to determine at least one output message from the transformed data structure.

Embodiments of the invention provide a check node processing unit (25) configured to determine at least one check node message to decode a signal encoded using a NB-LDPC code, the check node processing unit comprising: a data link to one or more message presorting units (24) configured to determine permuted variable node messages by applying one or more permutations to at least three variable node messages generated by one or more variable node processing units (23); a syndrome calculation unit (26) configured to determine a set of syndromes from the at least three permuted variable node messages, a syndrome comprising binary values; a decorrelation and permutation unit (27) configured, for each check node message of a given index, to: Determine a permuted index by applying to said given index the inverse of the one or more permutations; Select at least one valid syndrome in the set of syndromes, a valid syndrome comprising a binary value associated with said permuted index equal to a given value; Determine, at least one candidate check node component from said at least one valid syndrome; a selection unit (28) configured to determine at least one check node message from said at least one candidate check node component.