This disclosure relates generally to data decoding, and more particularly to iterative decoders for data encoded with a low-density parity check (LDPC) encoder.
An LDPC code is an error correcting code that may be used in the transmission of information through a noisy communications channel, with or without memory. A variety of LDPC decoding techniques may be used to recover and correct the information received from the channel, most of which are iterative in nature.
In the case of a memoryless channel, an LDPC decoder may directly receive log-likelihood-ratio (LLR) information, a bit reliability metric representative of the encoded data received from the channel, for use in the decoding operation. In the case of a channel with memory, a soft-in soft-out (SISO) channel detector, such as a soft output Viterbi algorithm (SOYA) detector, may be used in conjunction with the LDPC decoder. The decoding operation may alternate between use of the SISO channel detector and the LDPC decoder in order to decode the data. In particular, LLR information may be passed from the SISO channel detector to the LDPC decoder for use in the next LDPC decoding iteration and vice versa, in an iterative process that may be repeated, as desired, in order to improve data reliability.
LDPC codes may be represented by many different types of parity check matrices. The structure of an LDPC code's parity check matrix may be, for example, random, cyclic, or quasi-cyclic. LDPC codes defined by quasi-cyclic parity check matrices are particularly common and computationally efficient. These codes are known as quasi-cyclic low density parity check (QC-LDPC) codes.
A parity check matrix representative of a particular LDPC code may correspond to a bi-partite graph with check nodes and variable nodes. An LDPC decoder may decode received codewords using an iterative message passing algorithm, in which each iteration or sub-iteration includes two update steps involving the variable nodes and check nodes. (As used herein, the term “message” refers to a numerical value, usually representing an LLR.) In the first update step, messages may be passed from some (or all) check nodes to some (or all) variable nodes, and in the second update step, messages may be passed from some (or all) variable nodes to some (or all) check nodes.
An LDPC decoder may perform the update steps in accordance with a serial (layered) or flooding decoding schedule. In the flooding technique, all check nodes may be updated before a variable node is updated and all variable nodes may be updated before a check node is updated. In layered decoding, on the other hand, only those variable nodes necessary for updating a particular check node may be updated; or only those check nodes necessary for updating a particular variable node may be updated. An LDPC decoder that uses a layered update schedule for the message passing algorithm is herein referred to as a layered LDPC decoder.
A layered LDPC decoder may be used to decode QC-LDPC codes. For a QC-LDPC code with a quasi-cyclic parity check matrix consisting of circular submatrices (circulants) of size Sc, the number of check node processors necessary to implement layered decoding in the layered LDPC decoder may be Sc. This quantity is the parallelization level.
A layered LDPC decoder has several advantages over an LDPC decoder using the flooding technique. For example, a layered LDPC decoder may converge faster than a decoder with a flooding decoding schedule. As another example, a layered LDPC decoder implemented in hardware may take up less area than a decoder that employs the flooding technique. However, layered LDPC decoders are limited by power consumption demands and memory size requirements, both of which arise from the number of memory accesses required by traditional layered decoding scheduling.
Therefore, it would be desirable to provide LDPC decoders having reduced memory access requirements. Reducing the number of memory accesses during decoding may decrease power consumption, allow for the minimization of memory area, and improve application performance.