Devices, systems and methods for improving the convergence of a bit-flipping 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 an irregular QC-LDPC code, the irregular QC-LDPC code having an associated parity matrix comprising a plurality of columns of circulant matrices, computing a plurality of flipping energies for each column of a first subset of columns from the plurality of columns of circulant matrices, computing, based on the plurality of flipping energies, one or more metrics, selecting, based on the one or more metrics, a second subset of columns from the first subset of columns in an order that is different from a sequential indexing order of the second subset of columns, determining, based on processing the second subset of columns using a vertically shuffled scheduling operation, a candidate version of the transmitted codeword.

A method to decode low-density parity check (LDPC) encoded data using a parity check matrix having a plurality of layers, includes receiving a plurality of values at a decoder. Each value of the plurality of values represents one of a plurality of bits of an LDPC codeword encoded using the parity check matrix. The LDPC codeword is decoded using layered scheduling. A functional adjustment is applied to an approximation of belief propagation used during the decoding. At least one layer specific functional adjustment is used to provide an estimate of the codeword. An apparatus to decode low-density parity check (LDPC) encoded data using a parity check matrix having a plurality of layers includes a decoder. The decoder includes circuitry to decode, layer by layer, the LDPC encoded data utilizing functional adjustments and an algorithmic approximation to belief propagation to provide an estimate of the LDPC codeword. The functional adjustments include layer specific parameters for at least two layers of the parity check matrix associated with the codeword.

Methods and devices are disclosed for encoding source words and decoding codewords with LDPC matrices, comprising: receiving a 1×K source word row vector ū; and generating a 1×N codeword vector c=ū.Math.G, wherein G is a K×N generator matrix derived from a parity check matrix H.sub.l; and wherein H.sub.l is derived from a base parity check matrix H by summing different rows in the base parity check matrix H to obtain an intermediate parity check matrix, and applying a lifting matrix to the intermediate base parity check matrix to obtain H.sub.l.

This invention provides a cyclically-coupled (CC-) quasi-cyclic (QC-) low-density parity-check (LDPC) code and its decoder architecture. The essence of the invention is to introduce the convolutional nature to a plurality of individual block codes internally so as to form a resultant block code with a prolonged code length while slightly increasing the hardware complexity in decoder realization. The CC-QC-LDPC code is formed by cyclically coupling a plurality of sub-codes each being a QC-LDPC code such that overlapping of some variable nodes between two consecutive sub-codes results. The decoder comprises plural sub-decoders each configured to decode the channel messages for one sub-code. The sub-decoders are arranged in a ring shape such that an individual sub-decoder is configured to communicate edge messages with two neighboring sub-decoders adjacent to said individual sub-decoder in the decoding of the channel messages. The sub-decoders are configured to operate concurrently for simultaneously decoding individual sub-codes.

This invention presents a method and the corresponding hardware apparatus for decoding LDPC codes using a vertical layered (VL) iterative message passing algorithm. The invention operates on quasi-cyclic LDPC (QC-LDPC) codes, for which the non-zero circulant permutation matrices (CPMs) are placed at specific locations in the parity-check matrix of the codes, forming concentrated clusters of CPMs. The purpose of the invention is to take advantage of the organization of CPMs in clusters in order to derive a specific hardware architecture, consuming less power than the classical VL decoders. This is achieved by minimizing the number of read and write accesses to the main memories of the design.

A low-density parity check (LDPC) decoding apparatus for performing shuffle decoding includes: an input wrapper, for receiving input data and padding the input data; an LDPC decoder, coupled to the input wrapper, for receiving the padded input data, performing a plurality of iterations of LDPC decoding upon the padded input data to generate channel values corresponding to the padded input data, and outputting a hard decision channel value in a final iteration; and an initialization circuit, coupled to the LDPC decoder, for receiving the input data in a first iteration of the plurality of iterations, storing the input data into an ordered set data, and immediately sending the ordered set data to the LDPC decoder.

An operating method of an error correction decoder includes receiving data, setting initial log-likelihood values of variable nodes, and decoding the received data by updating a log-likelihood value of a selected variable node by use of a minimum value and a minimum candidate value associated with the selected variable node. The minimum value indicates a minimum value of absolute values of log-likelihood values of first variable nodes sharing a check node with the selected variable node and including the selected variable node. The minimum candidate value indicates one from among absolute values of log-likelihood values of second variable nodes that has the smallest value greater than the minimum value. The second variable nodes are selected later than one from among the first variable nodes corresponding to the minimum value.

A controller is configured to access information to generate data blocks. The controller includes a data block interleaver and a low-density parity check (LDPC) decoder. The data block interleaver is configured to interleave the data blocks to generate interleaved data blocks. The LDPC decoder is configured to decode the interleaved data blocks.

A sorting device and method for determining elementary check node components in an elementary check node processor implemented in a non-binary error correcting code decoder by sorting auxiliary components are presented. The auxiliary components are stored in a plurality of FIFO memories, each FIFO memory being assigned a FIFO number index. Each auxiliary component stored in a given FIFO memory comprises an auxiliary symbol, a reliability metrics representing the reliability of the auxiliary symbol, and the FIFO number index assigned to the given FIFO memory. The sorting device is configured to sort the auxiliary components by a plurality of multiplexers arranged sequentially. Each multiplexer is configured to initialize a candidate elementary check node component from the components of a FIFO memory corresponding to the auxiliary component which comprise the most reliable auxiliary symbol and to perform one or more iterations of the illustrated receiving, updating and sorting steps.

A method and apparatus for a quasi-cyclic low density parity check (QC-LDPC) decoder utilizes a parity check matrix (H matrix) having a matrix value for each row and column position in the matrix. Each matrix value is associated with an initial soft information element where, for each one of the matrix values associated with a constrained row, the one of the matrix values is constrained to a set of constraint values associated with a set of initial soft information elements. The set of initial soft information elements excludes a number of soft information elements that immediately precede a first initial soft information element. The first initial soft information element is associated with a selected first matrix value associated with a first row that immediately precedes the constrained row, and with the same column as the one of the matrix values in the constrained row.