News Column

Patent Issued for Layered Low Density Parity Check Decoder

June 24, 2014



By a News Reporter-Staff News Editor at Information Technology Newsweekly -- A patent by the inventors Varnica, Nedeljko (Sunnyvale, CA); Chaichanavong, Panu (Sunnyvale, CA); Tang, Heng (San Jose, CA), filed on January 10, 2011, was published online on June 10, 2014, according to news reporting originating from Alexandria, Virginia, by VerticalNews correspondents.

Patent number 8751912 is assigned to Marvell International Ltd. (BM).

The following quote was obtained by the news editors from the background information supplied by the inventors: "A basic problem in communications and data storage involves determining whether information received at a receiver accurately reflects information transmitted from a transmitter. Conventionally, additional verification bits (e.g., parity bits, cyclic redundancy check bits) have been added to message bits to facilitate improving confidence that a received message matches a transmitted message. The communication/data storage system, therefore typically includes an Error-Correcting Code (ECC). For example, in the encoding process, the codeword of an ECC code is constructed by adding redundancy/check bits to the data field. Low density parity check (LDPC) codes define one type of ECC.

"LDPC codes are linear block codes associated with a sparse parity check matrix that can be represented as a bipartite graph. The sparsity refers to a condition where a parity check matrix for an LDPC code may be constrained to have less than a certain number of ones per column and to have less than a certain number of ones per row.

"An LDPC decoder receives a vector (received vector), attempts to decode the most likely codeword corresponding to the received vector, and reports on whether the decoder vector is a valid codeword. An LDPC codeword may include message bits and redundancy bits. The redundancy bits may be, for example, parity bits. An LDPC code may be a linear (N,K) block code with K information bits mapped to a codeword of block length N. An LDPC code C can be specified in terms of a low-density (e.g., sparse) N.times.K binary parity check matrix. While examples are provided in terms of binary codes herein, it should be understood that similar methodologies can be applied to non-binary codes, where the word 'bit' is replaced by the word 'non-binary symbol'.

"A codeword can be decoded and verified in pieces where beliefs are built up about certain pieces of the codeword and then those beliefs are used to decode other pieces of the codeword. Decoding will continue until the constraints for a codeword have been satisfied, until a maximum number of tries (e.g., iterations through an LDPC decoder) have been attempted, or until other criteria terminate decoding.

"One type of LDPC decoder is a layered decoder. FIG. 1 illustrates one example of a conventional layered decoder 10. The layered decoder 10 provides a convergence flag when the convergence verification unit 12 determines that the layered decoder 10 has converged on a decision concerning decoding a codeword. The convergence verification unit 12 will accept a syndrome input from a syndrome computation unit 20 and will also accept a hard decision ('HD') change input from an HD tracking unit 22. The syndrome and HD change signals can be combined to determine whether the layered LDPC decoder 10 has reached convergence. The syndrome computation unit 20 computes the syndromes of a current layer in the layered decoder 10 based on whether all check nodes in the layer are satisfied. The HD tracking unit 22 can verify whether the updated HD has changed its value compared to the previous update of the same bit (variable) node. The update will have been performed in a layer that was processed earlier.

"The syndrome computation unit 20 and the HD tracking unit 22 receive an updated HD from a logic 30 that is responsible for processing and/or updating bit nodes and check nodes. The logic 30 also provides updated R messages to an R memory 14 and provides updated Q or P messages to a Q or P memory 16. The logic 30 receives values from the R memory 14 and the Q or P memory 16.

"Conventionally, a layered decoder like layered LDPC decoder 10 may have L layers, L being an integer. A conventional decoder may go around and around through processing layers until L layers in a row report that the syndromes are all satisfied and until there have been no HD changes for L layers in a row. In a standard convergence unit 12, a layer count may only be incremented up towards L if all the HD change flags indicated that the HD had not changed and if the current syndrome is satisfied. If either an HD changed, or a syndrome was not satisfied, then the layer count may not be incremented up towards L, and/or may be reset all the way to zero. If the layer count ever reaches L, then the decoder 10 can stop and report convergence. However, this convergence technique is not optimal.

"In one layered approach, different layers may be tasked with providing different partial decoding results. In one example, a syndrome is a function (e.g., binary addition) of all the variable node values in the bipartite graph that are connected to the same check node. The syndrome calculation involves verifying the parity checks of the current HD values (current decoded vector). A non-zero syndrome vector may signal some number of erroneous HD values. In one example, b.sub.i is a binary sequence corresponding to the bits connected to the check nodes at layer i. Syndrome S.sub.i=A.sup.Tb.sub.i is the syndrome of layer i, where A is the parity check matrix of the layer i (this is a submatrix of the LDPC parity check matrix) and T is the transpose of a matrix. A layered decoder may sequentially decode given syndromes S.sub.i from the top layer to the bottom layer, and then return to the top layer to complete additional iterations, using previous decoding results to update the log likelihood ratios (LLRs) for each node or edge in the decoder graph until decoding is completed.

"Conventional convergence logic for a layered decoder is sub-optimal because all layers of the layered LDPC decoder are considered and/or reconsidered before convergence can be determined. Conventionally, in a layered LDPC decoder, a syndrome update occurs in the current layer of the layered decoder. To finish updating an entire syndrome at least once for all layers requires running through at least one entire iteration of LDPC decoding. When a bit is flipped (e.g., corrected) during layered decoding, conventional decoders may cycle through yet another entire iteration of the decoder to insure that all syndromes are satisfied before reporting convergence. This may waste time and power.

"Completing yet another entire iteration through a layered decoder may be wasteful when a correct codeword may be successfully and conclusively decoded in the current iteration. Also, in some instances, a correct codeword may be decoded after just a few layers in a layered decoder when, for example, the received vectors (e.g., LLRs) are correct or nearly correct.

"FIG. 2 illustrates example convergence detection with conventional standard convergence logic in a conventional layered decoder 50. The current HD for a column J for a circulant 52, prior to processing at layer i, is the HD produced during the processing for a circulant 51 at layer i-3. During the processing of layer i, some HD for block column J may change due to updates obtained while processing circulant 52. It may take L-3 layers after layer i is processed to actually detect that the decoder 50 arrived at a valid codeword at layer i. This is sub-optimal.

"LDPC codes are designed to have a structured parity check matrix to facilitate enhancing efficiency in storage (e.g., memory) and processing (e.g., encoder, decoder) units. An LDPC encoder takes in a word of length K and outputs a codeword of length N by inserting N-K redundancy bits. The encoder adds the bits as a function of an LDPC code."

In addition to the background information obtained for this patent, VerticalNews journalists also obtained the inventors' summary information for this patent: "In one embodiment an apparatus includes a plurality of hardware layers, where a hardware layer is configured to compute a syndrome value from one or more bit values in the codeword. The apparatus includes a plurality of physical memories configured to store a plurality of syndrome values, where a physical memory is configured to store syndrome values computed by one or more hardware layers. The apparatus includes circuitry configured to simultaneously store a syndrome value computed by a hardware layer in physical memories associated with a bit in the codeword. The apparatus includes a decode logic configured to signal successful decoding of the codeword based, at least in part, on determining that a set of syndromes are satisfied based on values stored in the plurality of physical memories.

"In another embodiment, a method includes initializing an LDPC code for use with a layered LDPC decoder configured with physical syndrome memories, and configuring the layered LDPC decoder to reduce the number of syndrome memories by restricting the position of non-zero circulants in a matrix associated with the LDPC code so that a column in the matrix has no more than a threshold number of non-zero circulants per physical syndrome memory in the layered LDPC decoder.

"In another embodiment, a device includes an encoder configured to encode a codeword based, at least in part, on an LDPC code configured for use with a layered LDPC decoder configured with syndrome memories and configured to perform syndrome computation based on values in the syndrome memories."

URL and more information on this patent, see: Varnica, Nedeljko; Chaichanavong, Panu; Tang, Heng. Layered Low Density Parity Check Decoder. U.S. Patent Number 8751912, filed January 10, 2011, and published online on June 10, 2014. Patent URL: http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.htm&r=1&f=G&l=50&s1=8751912.PN.&OS=PN/8751912RS=PN/8751912

Keywords for this news article include: Information Technology, Marvell International Ltd, Information and Data Storage.

Our reports deliver fact-based news of research and discoveries from around the world. Copyright 2014, NewsRx LLC


For more stories covering the world of technology, please see HispanicBusiness' Tech Channel



Source: Information Technology Newsweekly