High speed LDPC decoder

A method and decoder are provided to decode a Low Density Parity Check codeword. An additional check processor performs hard-decision processing functions on the LDPC codeword in order to avoid running unnecessary decoder iterations. The method comprises: receiving the ECC codeword at a memory, the received ECC codeword comprising ECC data bits, ECC parity bits, and error detection code bits; soft-decision decoding the received ECC codeword at a soft-decision decoder, to update the ECC codeword according to ECC parity check equations; hard-decision processing the received ECC codeword at a check processor, while the soft-decision decoder performs the soft-decision decoding, to verify the ECC data bits using the error detection code bits; terminating the soft-decision decoding when the ECC data bits are verified, regardless of whether the updated ECC codeword satisfies all of the ECC parity check equations; and, outputting the decoded ECC codeword from the memory after termination of the decoding.

FIELD

The present disclosure relates generally to the field of data communications and error coding.

BACKGROUND

Low Density Parity Code (LDPC) decoders are current generation iterative soft-input forward error correction (FEC) decoders that have found increasing popularity in FEC applications where low error floor and high performance are desired. LDPC decoders are defined in terms of a two-dimensional matrix, referred to as an H matrix, which describes the connections between the data and the parity. The H matrix comprises rows and columns of data and parity information. Decoding an LDPC code requires solving the LDPC code according to the H matrix based on a two-step iterative method. Soft-decision decoding the code causes convergence of the solved code with the true code; convergence is achieved over a number of iterations and results in a corrected code with no errors.

A category of LDPC codes, known as quasi-cyclic (QC) codes, generates an H matrix with features that improve the ease of implementing the LDPC encoder and decoder. In particular, it is possible to generate a QC-LDPC H matrix where some rows are orthogonal to each other. These orthogonal rows are treated as a layer, and rows within a layer can be processed in parallel, thus reducing the iterative cost of the decoder. It is advantageous to reduce the number of iterations necessary to decode an LDPC code.

The standard criteria for determining when to exit the soft-decision decoding iterations uses check node outputs to determine when the decoder has converged. This is an area efficient exit criteria, but requires nearly a full iteration of extra run time beyond the iteration in which the decoder has converged. This full iteration cost is especially steep at typical operating points for an LDPC code where it is desirable to have codes that are converging in as few iterations as possible. For instance, if an operating point is defined by code convergence in an average of 5 iterations, then an extra iteration to determine exit status costs on the order of 20% more time and power. Even when the average convergence is 10 iterations, the exit status determination will cost approximately 10% more time and power than necessary.

One known approach to allow the decoder to exit as soon as possible comprises adding a check processor to recheck all parity equations after every soft-decision decoding iteration. Full parity check exit determination is most suitable for small fixed code LDPC decoders. However, while such an approach overcomes the extra iteration of the standard method, the additional check processor comes at the cost of a large area footprint, even for a small fixed code LDPC code. Large FEC block LDPC codes are advantageous for various reasons relating to reduced overhead; however, full parity check exit determination of a large FEC block LDPC code is difficult to implement due to the necessity of routing massive XOR trees.

Known LDPC decoders are also adversely affected by codeword loading and unloading to and from the codeword memory of the LDPC decoder. When loading a codeword from a decoder input into the memory of the decoder, or when unloading a codeword from the memory to the output of the decoder, the decoder core is unable to access the memory and remains idle, reducing the overall decoding speed of the LDPC decoder.

Improvements to error decoding methods and decoders are desirable.

DETAILED DESCRIPTION

A method and decoder are provided to decode a Low Density Parity Check codeword. The present disclosure provides an additional check processor to perform hard-decision processing functions on the LDPC codeword in order to avoid running unnecessary decoder iterations. In contrast to known approaches, the check processor allows for timely exiting of the power intensive decoding process while doing so in an area and power efficient manner and while supporting high throughput applications.

In an embodiment of the present disclosure, a method for decoding an error correcting code (ECC) codeword comprises: receiving the ECC codeword at a memory, the received ECC codeword comprising ECC data bits, ECC parity bits, and error detection code bits; soft-decision decoding the received ECC codeword at a soft-decision decoder, to update the ECC codeword according to ECC parity check equations; hard-decision processing the received ECC codeword at a check processor, while the soft-decision decoder performs the soft-decision decoding, to verify the ECC data bits using the error detection code bits; terminating the soft-decision decoding when the ECC data bits are verified, regardless of whether the updated ECC codeword satisfies all of the ECC parity check equations; and, outputting the decoded ECC codeword from the memory after termination of the decoding.

In a further embodiment of the present disclosure, the method comprises: determining a convergence status of the soft-decision decoding; and initiating the hard-decision processing when the convergence status of the soft-decision decoding exceeds a threshold.

In yet a further embodiment of the present disclosure, the method comprises: hard-decision processing the decoded ECC codeword stored in memory after terminating the decoding and before outputting the decoded ECC codeword in order to further verify the ECC data bits; and soft-decision decoding the decoded ECC codeword stored in memory if the further verification fails.

In yet a further embodiment of the present disclosure the ECC codeword is a low density parity check (LDPC) codeword comprising LDPC data bits, CRC bits, and LDPC parity bits.

In yet a further embodiment of the present disclosure, the method comprises: calculating a CRC check value from the LDPC data bits; extracting a CRC check value from the CRC bits; and comparing the calculated CRC check value to the extracted CRC check value.

In yet a further embodiment of the present disclosure, the method comprises calculating at least a portion of parity check equations of an LDPC code with the decoded codeword; and verifying whether the number of successfully calculated parity check equations exceeds a threshold.

In yet a further embodiment of the present disclosure, the method comprises updating variable node values of the LDPC codeword according to one check node constraint, the variable nodes updated by the one check node corresponding to reference addresses stored in one row of a quasi-cyclic (QC) H matrix, the QC H matrix being stored in the decoder and representing an LDPC code for encoding and decoding the LDPC codeword.

In yet a further embodiment of the present disclosure, the method comprises: performing a memory address lookup of reference addresses in the one QC H matrix row; and loading, from the memory to the soft-decision decoder, in one memory clock cycle, a first set of variable node values corresponding to a first group of check node constraints in the QC H matrix row.

In yet a further embodiment of the present disclosure, the method comprises loading, from the memory to the soft-decision decoder, a second set of variable node values corresponding to a second group of check node constraints in the QC H matrix, concurrently to loading the first set of variable node values in the same one memory clock cycle.

In yet a further embodiment of the present disclosure, the method comprises: receiving at least two variable node values at a shift processor from the two sets of variable node values; providing the first of the two variable node values to a layer processor and subsequently providing the second of the two variable node values to the layer processor, if the first of the two variable node values corresponds to the first check node constraint and the second of the two variable node values corresponds to the second check node constraint; and providing the second of the two variable node values to the layer processor and subsequently providing the first of the two variable node values to the layer processor, if the second of the two variable node values corresponds to the first check node constraint and the first of the two variable node values corresponds to the second check node constraint.

In yet a further embodiment of the present disclosure, the method comprises: receiving all of the variable node values of the one check node at the layer processor; removing previous extrinsic information relating to the check node from all of the variable node values to form a check node processor input information; calculating a belief propagation function at a check node processor to determine extrinsic information relating to the check node; storing the calculated extrinsic information relating to the check node; and combining the check node processor input information with the extrinsic information relating to the check node to update the variable node values of the check node.

In yet a further embodiment of the present disclosure, the method comprises: receiving, from at least one layer processor, two updated variable node values at a reorder buffer; providing the first of the two updated variable node values to the memory and subsequently providing the second of the two updated variable node values to the memory, in a first minor shift condition; and providing the second of the two updated variable node values to the memory and subsequently providing the first of the two updated variable node values to the memory, in a second minor shift condition.

In another embodiment of the present disclosure, a decoder for decoding an error correcting code (ECC) codeword comprises: a memory for receiving the ECC codeword, the received ECC codeword comprising ECC data bits, ECC parity bits, and error detection code bits; a soft-decision decoder for soft-decision decoding the received ECC codeword stored in the memory to update the ECC codeword according to ECC parity check equations; and a hard-decision processor for hard-decision processing the received ECC codeword stored in the memory, while the soft-decision decoder performs the soft-decision decoding, the hard-decision processor configured to verify the integrity of the ECC data bits using the error detection code bits; terminate the soft-decision decoding when the ECC data bits are verified, regardless of whether the updated ECC codeword satisfies all of the ECC parity check equations; and output the decoded ECC codeword stored in memory after termination of the decoding.

In a further embodiment of the present disclosure, the decoder comprises an exit determiner for: determining a convergence status of the soft-decision decoding; and initiating the hard-decision processing when the convergence status of the soft-decision decoding exceeds a threshold.

In yet a further embodiment of the present disclosure, the hard-decision processor performs further hard-decision processing of the decoded ECC codeword stored in memory after terminating the decoding and before outputting the decoded ECC codeword in order to further verify the ECC data bits; and the soft-decision decoder performs further soft-decision decoding of the decoded ECC codeword stored in memory if the further verification fails.

In yet a further embodiment of the present disclosure, the ECC codeword is a low density parity check (LDPC) codeword comprising LDPC data bits, CRC bits, and LDPC parity bits.

In yet a further embodiment of the present disclosure, the hard-decision processor performs a hard-decision operation comprising: calculating a CRC check value from the LDPC data bits; extracting a CRC check value from the CRC bits; and comparing the calculated CRC check value to the extracted CRC check value.

In yet a further embodiment of the present disclosure, the hard-decision processor performs a hard-decision operation further comprising: calculating at least a portion of parity check equations of an LDPC code with the decoded codeword; and verifying whether the number of successfully calculated parity check equations exceeds a threshold.

In yet a further embodiment of the present disclosure, the soft-decision decoder updates variable node values of the LDPC codeword according to one check node constraint, the variable nodes updated by the one check node corresponding to reference addresses stored in one row of a quasi-cyclic (QC) H matrix, the QC H matrix being stored in the decoder and representing an LDPC code for encoding and decoding the LDPC codeword.

In yet a further embodiment of the present disclosure, the decoder further comprises a plurality of memory elements wherein all variable node values referenced by each column of the QC H matrix are stored in a single memory element.

In yet a further embodiment of the present disclosure, the memory: performs a memory address lookup of reference addresses in the one QC H matrix row; and provides to the soft-decision decoder, in one memory clock cycle, a first set of variable node values corresponding to a first group of check node constraints in the QC H matrix row.

In yet a further embodiment of the present disclosure, the memory provides, to the soft-decision decoder, a second set of variable node values corresponding to a second group of check node constraints in the QC H matrix, concurrently to providing the first set of variable node values in the same one memory clock cycle.

In yet a further embodiment of the present disclosure, the decoder further comprises: a shift processor for receiving at least two variable node values from the two sets of variable node values; and a layer processor for updating the two variable node values, the shift processor configured to: provide the first of the two variable node values to the layer processor and subsequently provide the second of the two variable node values to the layer processor, if the first of the two variable node values corresponds to the first check node constraint and the second of the two variable node values corresponds to the second check node constraint; and provide the second of the two variable node values to the layer processor and subsequently provide the first of the two variable node values to the layer processor, if the second of the two variable node values corresponds to the first check node constraint and the first of the two variable node values corresponds to the second check node constraint.

In yet a further embodiment of the present disclosure, the decoder further comprises a plurality of shift processors wherein each shift processor receives variable nodes from a different column of the QC H matrix.

In yet a further embodiment of the present disclosure, the layer processor further comprises: an input for receiving all of the variable node values of the one check node; a first adder for removing previous extrinsic information relating to the check node from all of the variable node values to form a check node processor input information; a check node processor for calculating a belief propagation function to determine extrinsic information relating to the check node; a delay element for storing the calculated extrinsic information relating to the check node; and a second adder for combining the check node processor input information with the extrinsic information relating to the check node to update the variable node values of the check node.

In yet a further embodiment of the present disclosure, the decoder further comprises: a reorder buffer for receiving, from at least one layer processor, two updated variable node values, the reorder buffer configured to: provide the first of the two updated variable node values to the memory and subsequently provide the second of the two updated variable node values to the memory, in a first condition; and provide the second of the two updated variable node values to the memory and subsequently provide the first of the two updated variable node values to the memory, in a second condition.

Reference to specific elements of various embodiments of the present disclosure will now be made.

FIG. 1shows an exemplary known LDPC H matrix100. The H matrix is used for encoding and decoding an LDPC codeword, and describes the connections between the data and the parity. The connections represented by the H matrix can also be represented graphically as a Tanner graph (not shown), which shows variable nodes and check nodes used to represent the decoding of an LDPC codeword.

The rows102of H matrix100are often equated to the check nodes in a Tanner graph because each row represents a constraint in the decoding, and each check node represents a constraint on connected variable nodes. Consequently, there are as many rows in an H matrix as there are check nodes in a Tanner graph.

Since the rows represent the constraints on the bits of the LDPC codeword, there are as many columns in H matrix100as there are bits (both data bits and parity bits) in the LDPC codeword. The columns of H matrix100generally equate to the function of the variable nodes in the Tanner graph. Each constraint (row value) in a given column helps generate a belief value, and the sum of all of the belief values in a column generates an updated variable node, or an updated codeword bit.

H matrix100corresponds to an LDPC codeword having N data bits and M parity bits. Therefore, H matrix100has N number of data columns104and M number of parity columns106, representing the entire length of the LDPC codeword. H matrix100also has M number of rows102, representing the length of the parity portion of the LDPC codeword.

FIG. 2shows an exemplary known Quasi-Cyclic (QC) H matrix200used for decoding QC LDPC codes. QC LDPC codes are a subclass of LDPC codes that are generally easier to implement and generally more efficient for encoding and decoding LDPC codewords. QC H matrix200has NDnumber of data columns, NPnumber of parity columns, and NPnumber of rows. Each entry in matrix200includes a circulant matrix.

FIG. 3shows an exemplary known circulant matrix300used in QC H matrix200. A circulant matrix is a Q×Q sized matrix having the following entries: either an identity matrix that has been rotated between ‘0’ and ‘Q−1’, or an all-zero matrix. Circulant matrix300has size Q=8 a rotation of 4. Referring toFIGS. 2 and 3, each entry in QC H matrix200is a circulant matrix. A ‘−1’ entry in QC H matrix200corresponds to an all-zero circulant matrix. A ‘0’ entry in QC H matrix200corresponds to an identity circulant matrix. A positive integer entry in QC H matrix200corresponds to a rotated identity matrix circulant matrix. Thus, entries201in QC H matrix200correspond to circulant matrix300.

Every row and column in a non-zero circulant matrix, such as circulant matrix300, has a weight of one; that is, it contains only a single ‘1’ entry in each row and column. This characteristic of QC H matrices beneficially provides for easier encoder and decoder implementation. Specifically, this characteristic allows for implementing a QC H matrix in which some rows are orthogonal to each other. Rows in a QC H matrix are orthogonal to each other where each column has at most one entry with a value greater than ‘−1’. That is, each column, in a group of orthogonal rows, has at most one non-zero circulant matrix. In QC H matrix200inFIG. 2, rows R1, R2, R3, and R4are orthogonal to each other, and together form a layer202. Similarly, rows R5and R6are also orthogonal, and together form a layer203. Multi-row layers202and203can reduce decoder iterations because the orthogonality of the rows in each of the layers allows the rows in the layers to be processed in parallel by separate layer processors.

FIG. 4is a flowchart illustrating a method400for decoding an error correcting code (ECC) codeword according to an embodiment of the present disclosure. At401, method400receives a codeword comprising ECC data bits, ECC parity bits, and error detection code bits. A soft-decision decoder, at402, decodes the received codeword, while at the same time and in parallel, at403, a hard-decision processor processes the received codeword according to a hard-decision determination.

Soft-decision decoding at402comprises updating the bits of the codeword. Each bit of the codeword is exemplarily an m-bit soft-value, representing the amount of confidence that the bit is either a ‘0’ value or a ‘1’ value. Thus, updating exemplarily comprises iteratively updating the soft-values, or variable nodes, according to the check node constraints, or parity check equations, of the error correcting code. As the soft-values are iteratively updated, more and more constraints of the error correcting code will be satisfied by the set of soft-values representing the codeword being decoded.

In a further embodiment, method400comprises determining when to initiate hard-decision processing at403. In this embodiment, soft-decision decoding is first initiated to decode the codeword. As the codeword is iteratively decoded, its decoding status is compared to a completion threshold. Once the completeness of the decoding exceeds the threshold, the hard-decision processing is initiated at403. Delaying the initiation of the hard-decision processing further reduces overall decoder power consumption.

Furthermore, delaying the initiation of the hard-decision processing reduces the chance of a false convergence. Soft-decision decoding at402can randomly generate a false codeword having internally consistent ECC data bits and error detection code bits. By choosing a sufficient completion threshold, method400will reduce the chance that hard-decision processing at403terminates the decoding based on a false codeword.

Hard-decision processing at403comprises verifying the ECC data bits using the error detection code bits. Verifying can comprise, for example, a CRC check that the value of the received error detection code bits matches an error detection code value calculated from the received ECC data bits.

At404, in response to a successful verification that received error detection code bits match the error detection code bits calculated from the received ECC data bits, method400terminates the soft-decision decoding. Step404terminates the soft-decision decoding of the received codeword regardless of whether the updated codeword satisfies all of the parity check equations of the error correcting code.

In an embodiment, method400optionally proceeds to406to process the decoded codeword at the hard-decision processor once again. The soft-decision decoding and the hard-decision processing proceed in parallel using different address sequences but reference the same memory space; thus, there exists a possibility that the soft-decision decoding at402altered a bit of the decoded codeword between the hard-decision processing at403and the terminating at404. The second processing operation at406verifies that the soft-decision decoding at402did not alter any bits of the decoded codeword between the hard-decision processing at403and the terminating at404. If the second verification at406fails, the codeword decoded at402is further soft-decision decoded to correct any bits altered between the hard-decision process at403and the terminating at404.

In a further embodiment, method400optionally includes step405comprising terminating the soft-decision decoding when the entire codeword (ECC data bits, ECC parity bits, and error detection code bits) satisfies all of the check node constraints of the error correcting code. That is, all of the parity check equations associated with the check nodes are passing. After optional step405, method400proceeds to406to output the decoded codeword. In this embodiment, optional step405is usually skipped because parallel step404usually terminates the soft-decision decoding before optional step405. This condition is informally known as an early exit of the soft-decision decoding operation.

In addition to allowing for the early exit at404, hard-decision processing at403advantageously provides verification that the decoded codeword is not a false convergence. Soft-decision decoding at402can also randomly generate another type of false codeword having internally consistent ECC data bits and ECC parity bits. While a particular ECC code can be selected to minimize the occurrence of false ECC codewords, this rare occurrence will still exist. Since the false codeword will not likely also have internally consistent ECC data bits and error detection code bits, hard-decision processing at403will provide detection for this type of false codeword.

In an embodiment, the ECC codeword is an LDPC codeword, and the LDPC codeword comprises LDPC data bits, CRC bits, and LDPC parity bits. However, embodiments described herein are applicable to any type of ECC codeword. While detailed examples are provided herein with respect to LDPC and CRC codes, in other embodiments similar approaches are implemented with respect to other types of error correcting and error detecting codes.

FIG. 5is a block diagram of a decoder500for decoding an LDPC codeword512,514, according to an embodiment of the present disclosure. Decoder500comprises a memory510for receiving the LDPC codeword512,514, a soft-decision decoder520for soft-decision decoding the received LDPC codeword512,514, stored in the memory510, and a hard-decision processor530for verifying the LDPC codeword512,514, stored in memory510, while the soft-decision decoder520performs the soft-decision decoding. LDPC codeword512,514, comprises LDPC data bits, LDPC parity bits, and CRC bits. Hard-decision processor530may also be referred to as check processor530, and is configured to terminate both the soft-decision decoding and the hard-decision processing when the CRC check value calculated from the LDPC data bits matches the CRC check value stored in the CRC bits, and to output the decoded LDPC codeword512,514, stored in memory510after termination of the decoding. Therefore, decoder500will output the LDPC codeword even when the soft-decision decoder has not completed decoding the entire LDPC codeword (i.e., not all check node constraints are passing). This operation reduces the power consumption of decoder500.

Since only the LDPC data bits are considered the payload of the codeword, and the LDPC data bits can be verified by the CRC bits, decoder500can ignore the correctness of the LDPC parity bits. Thus, decoder500can terminate the decoding and output the codeword upon verifying the LDPC data bits with the CRC bits only. In other words, decoder500will use the LDPC parity bits to converge the entire codeword at soft-decision decoder520, in order to correct the LDPC data bits and the CRC bits, but does not necessarily require that the converging codeword correct the LDPC parity bits.

In addition to causing an early exit of the decoding, check processor530advantageously provides verification that the decoded codeword is not a false convergence. Soft-decision decoder520can randomly generate a type of false codeword having internally consistent LDPC data bits and LDPC parity bits. While a particular LDPC code can be selected to minimize the occurrence of false LDPC codewords, this rare occurrence will still exist. Since the false LDPC codeword will not likely also have internally consistent LDPC data bits and CRC bits, check processor530will also provide detection for this type of false codeword.

Decoder500further comprises exit determiner528to enable the operation of hard-decision processor530only once the codeword is nearly ready for hard-decision processing, which further reduces the power consumption of decoder500.

In operation, the LDPC decoder input502receives an LDPC codeword for decoding. The input is connected to an input/output (IO) memory510in order to load the LDPC codeword into the memory. IO memory510, for example, is sized to hold two codewords: codeword A512and codeword B514. I/O memory510is connected to an output504for outputting the decoded LDPC codeword.

IO memory510is also connected to both an LDPC soft-decision decoder520and to a hard-decision processor530. In an example embodiment, the memory510has sufficient bandwidth to serve data to both the soft and the hard processors in parallel. LDPC soft-decision decoder520performs soft-decision decoding operations on the codeword to decode the codeword, over several soft-decision decoding iterations, to obtain a corrected codeword. Check processor530can perform convergence checking operations on the codeword to check the correctness of the codeword while the soft-decision decoder520performs the soft-decision decoding. LDPC soft-decision decoder520comprises a shift processor522and a layer processor524. The shift processor performs a cyclic shift of a circulant300stored in the memory. The layer processor processes one layer, such as layer202comprising a number of orthogonal rows of the H matrix200, in a single soft-decision decoding iteration.

The decoder input502and output504are connected to IO memory510and are not directly connected to soft-decision decoder520. Therefore, the overall input/output rate of decoder500does not have to match the rate of soft-decision decoder520, which is typically much higher than the input/output rate of decoder500. This simplifies the external input/output circuitry for connecting decoder500to other circuits.

The following expressions, provided with corresponding definitions, are used throughout the detailed description to describe the decoder and the decoding method:

HR,C: Shift value in the Quasi-Cyclic H matrix in Layer R and Column C

ND: Number of data columns in H matrix

NP: Number of parity columns in H matrix

NC: Number of columns in H matrix (note that NC=ND+NP)

Q: Expansion factor on Quasi-Cyclic H matrix

L: Number of layer processors in the device

FP: Fractional shift remainder

LC: Number of clock cycles in a layer (note that LC=Q/L)

The decoder500operates by evaluating L check nodes per clock where each check node is one element of a row in H matrix200. Because each entry in H matrix200includes a circulant matrix300, each row in H matrix200includes Q sub-rows, or elements. Therefore, decoder500can evaluate one row of H matrix200every Lc clock cycles

In an embodiment, soft-decision decoder520performs variable and check node operations on all soft-values of the codeword read from IO memory510and writes back the updated soft-values continuously to IO memory510. On each layer boundary, the soft decoder finishes and writes back into IO memory510a current layer before beginning to process the next layer. Each value in memory510represents the summation of the channel information and the extrinsic information obtained from each row, that is

As shown in the embodiment ofFIG. 5, codeword memory510can hold two LDPC codewords (A512and B514) of information. For high speed decoding, storing two codewords of information in the memory is often favorable since the aspect ratio of the memories results in a nominal increase in gate area (on the order of 25% or less) to store twice the data. Each codeword memory510is composed of several hardware memory elements. Each circulant300is a Q×Q matrix in memory510and each ‘1’ entry in circulant300is a reference to a codeword soft value stored in memory510. Therefore, each circulant contains Q soft value references. Each soft value is described by M bits of information in codeword memory510. Thus, the bit depth M describes the precision of decoder500. Bit depth M can be used for representing soft value information as a log likelihood ratio. Since circulant300is orthogonal, no two soft value references of circulant300are ever accessed at the same time; therefore, all of the codeword data referenced by one circulant300in Quasi-Cyclic H matrix200is stored in a single hardware memory element. Thus, the number of hardware memory elements in the codeword memory is equal to the number of columns in QC-H matrix200.

Furthermore, IO memory510holds two LDPC codewords512,514. Each hardware memory element stores all of the codeword data referenced by a circulant of codeword512as well as all of the codeword data referenced by a circulant of codeword514. The bandwidth of each hardware memory element is effectively shared between codewords512and514. Thus, in an exemplary embodiment, the memory bandwidth from the codeword memory is configured to ensure sufficient bandwidth to support both LDPC soft-decision decoder520and check processor530(i.e. input, output and exit determination processing) without stalling either the soft-decision decoding or the hard-decision processing. For example, effectively half of the available memory bandwidth is available to the soft-decision decoding and half is available to the hard-decision processing. In order to ensure sufficient bandwidth to support both soft-decision decoder520and check processor530, decoder500is configured to alternate soft-decision decoding and hard-decision processing of codewords512and514. Therefore, when IO memory510is occupied by decoder input, decoder output, and check processor loading operations on codeword512(i.e., IO memory510is unavailable to soft-decision decoder520), soft-decision decoder520is not necessarily idle because soft-decision decoder520can perform soft-decision decoding on codeword514. Similarly, when IO memory510is occupied with codeword514, soft-decision decoder520can operate on codeword512. This allows soft-decision decoder520to be operational 100% of the time so long as there is a new codeword available in IO memory510to be processed.

In an embodiment of the present disclosure, each codeword memory510comprises NChardware memory elements where each memory element is a two-port memory supporting one write and one read per clock cycle. Typically these memories will be implemented as two-port register files. In an embodiment, decoder500supports up to 2L M-bit soft value reads from each hardware memory element and 2L M-bit soft value writes to each hardware memory element per clock cycle, where M is the precision of layer processor524. The reads on the even clock cycles are routed to shift processors522and the reads on the odd clock cycles are routed to check processor530, or to data output504if the LDPC decoder has completed processing. The writes on the even clock cycles are routed from layer processor524and the writes on the odd clock cycles are routed from data input502. Each column's even clock cycle read address, destined for shift processor522, is defined by the following equation:

AC⁡(t)={HR,C2⁢L,t=0(AC⁡(t-1)+1)⁢mod⁡(Q2⁢⁢L),0<t<Q2⁢L
ACis the address in the column C IO memory510hardware memory element (note that 0<C≦NC) and t is the time step within the layer. This addressing formula performs the first part of the QC-H matrix shifting. That is, it performs address lookup based on the shift value in Quasi-Cyclic H matrix200.

The write address to IO memory510from layer processor524is defined by the following equation:

An L to 2L reorder buffer526is placed between the layer processor and the codeword memory to convert the L per clock output from layer processor524to a 2L wide value that can be written back to IO memory510. The total storage in reorder buffer526is 3L−1 soft values; L soft value storage elements hold the results from the L layer processors524on the odd clock cycle. On the even clock cycle, the L layer processor524outputs are combined with the stored L values from the odd clock cycle to form a 2L wide value that can be written back to IO memory510.

In a further embodiment, reorder buffer526comprises an additional FP=HR,Cmod(2L) storage elements used to save the first FPoutputs from layer processor524(in the worst case FP=2L−1). These FPstored values are combined with the last 2L−FPvalues and written back to IO memory510on the final clock cycle of the layer. Note that when FPis zero the additional FPelements of reorder buffer526holds no elements. Reorder buffer526reverses the operation of shift processor522in order to return the updated codeword data to IO memory510.

The write address to IO memory510from data input502is defined by the following equation:

AC⁡(t)={0,t=0(AC⁡(t-1)+1)⁢mod⁡(Q2⁢⁢L),0<t<Q2⁢⁢L
The write address equation is equivalent to writing the input values to IO memory510in the order they are received at data input502.

In an embodiment, decoder500includes exit determiner528for determining when to initiate hard-decision processing at check processor530. In this embodiment, soft-decision decoding is first initiated to decode the LDPC codeword at soft-decision decoder520. As the codeword is iteratively decoded, exit determiner528compares its decoding status to a completion threshold. Once the progress of the decoding exceeds the threshold, exit determiner528initiates hard-decision processing at check processor530. Selectively enabling the operation of check processor530further reduces overall decoder power consumption.

In an example embodiment, exit determiner528keeps track of the passing check node count as provided by layer processor524. For each layer processed at layer processor524, a count is maintained of the number of check nodes that have passed; summing this total over all the layers of the codeword provides the total number of passing check nodes for that codeword. This total is compared against a threshold, which is typically set to between 95 and 99% of the total number of check nodes. Advantageously, a high threshold reduces the chance of a false convergence. Soft-decision decoder520can generate a type of false codeword having internally consistent LDPC data bits and CRC bits. Though the codeword being decoded at soft-decision decoder520may be incorrect, check processor530may nevertheless indicate a CRC pass. By choosing a sufficiently large completion threshold, such as between 95 and 99%, exit determiner528will reduce the chance that check processor530terminates the decoding based on a false codeword.

FIG. 6is a diagram illustrating the operation of an exemplary shift processor522according to an embodiment of the present disclosure. Shift processor522performs the second part of the QC-H matrix shifting in order to present the correct codeword elements to the input of layer processor524. The first part of presenting the correct codeword to layer processor524is the address lookup and translation step described in relation to the operation of IO memory510.

Depending on the shift value HR,Cstored in an entry of QC H matrix200, the second shift performed by shift processor522may or may not be necessary. Shift value HR,Cdescribes the address of the first M-bit soft value in each hardware memory to be processed at layer processor524. Because 2L M-bits are read from each hardware memory element, the M-bit soft value specified by shift value HR,Cmay or may not be at the beginning of the 2L M-bits read from memory. In the case of an HR,Cshift value wherein the specified M-bit soft value is at the beginning of the 2L M-bits read from memory, a shift will not be necessary. In the case of an HR,Cshift value wherein the specified M-bit soft value is not at the beginning of the 2L M-bits read from memory, a shift will be necessary. Therefore, shift processor522removes the first unused M-bits read from memory, and stores those M-bits for appending to the last bits sent to layer processor524.

Shift processor522receives 2L M-bit soft values every second clock cycle from IO memory510and provides L M-bit outputs every clock cycle to layer processor524. In order to keep the routing distance for shift processor522as short as possible, the shifting distance is at most 2L elements. Shift processor522completes the shift operation initiated by the IO memory read. IO memory510performs the macro shift by accessing the memory address as described above, and shift processor522performs the minor shift. The minor shift is calculated by:
FP=HR,Cmod(2L)

Shift processor522also handles the stitching of the beginning of the shift to the end, required for a cyclic shift.FIG. 6demonstrates the operation of shift processor522. A and B are a number of elements adding up to 2L and are calculated as:
A=FP
B=2L−FP

In the example ofFIG. 6, decoder500includes two layer processors and QC H matrix200is constructed with circulant size twenty. Therefore, L=2 and Q=20. Shift value HR,Cspecified in the matrix200entry204is 7. Thus, the minor shift remainder, FP, is 3. Table600shows the indexes of memory addresses accessed from a hardware memory element associated with a single circulant before the minor shift. Each row identifies a memory address lookup and translation performed by IO memory510and the entire content of each row is sent to shift processor522. Row601represents the first memory read. However, shift value HR,Cspecified a shift of 7 which represents the contents of602. Therefore, shift processor522calculates the minor shift remainder FP=3 and stores the contents603. These contents603are appended to the last data transfer to layer processor524, as shown below.

Table610shows the indexes of memory addresses accessed from a hardware memory element associated with a single circulant after the minor shift. The content of602is now at the beginning of the data presented to layer processor524and corresponds correctly to shift value HR,C=7 specified in matrix200entry204. The contents in the remainder603are appended to the end of the last row604, representing the last data transfer to the layer processor524for this particular circulant.

FIG. 7is a block diagram of layer processor524according to an embodiment of the present disclosure. Layer processor524processes several check nodes in parallel on the shifted input data. In a single pass, layer processor524performs both the check node and variable node processing steps for a single layer (e.g. layer202). According to embodiments of the present disclosure, it is never necessary to stall layer processor524while loading or unloading the codeword data being processed.

Point A701is the summation of the channel and all extrinsic values for a given column C in QC-H matrix200, that is A=VC(t). The adder702between point A701and point B703removes the extrinsic information for the row currently being operated on. Point B703represents the channel information, plus the extrinsic information for all rows except the row currently being operated on. Point B703can be defined by the formula B(t)=VC(t)−CC,r(t) where CC,r(t) is the check node output of the previous cycle. This calculation ensures that the input to the check node does not contain previous check node output for the same row. Check node704output, point C705, is calculated based on the following equation:

CC,r⁡(t+1)=f⁡(minj=1,NC⁢BC,j⁡(t))
Where f is an approximation of belief propagation function and where 0<j≦NCand j≠r. Common approximation functions include minsum adjust, attenuated minimum, and others as described in, for example,Channel Codes: Classical and Modern, by W. Ryan and S. Lin, Cambridge University Press, 2009; and inError Control Coding, by S. Lin and D. J. Costello Jr., Pearson Press, 2004. The output of layer processor524, point D706, represents the channel information, plus the extrinsic information for all rows except the row currently being operated on, plus the updated extrinsic information for the row being processed. Point D706is defined by the formula D(t+1)=VC(t)−CC,r(t)+CC,r(t+1). Delay element707stores the updated extrinsic information for the current column and row and saves it for the next time this column is processed, thus forming the data at point B703.

The variable node update operation of layer processor524is performed by the adders surrounding check node704: adder702and the adder708. The variable node update operation is the summation of all votes on a given column of H matrix200. The value at point A701represents the summation of all historical votes on a given column of H matrix200. Before performing a check node operation on a variable node value at check node704, layer processor524first subtracts the previous contribution of check node704at adder702. After the check node operation, layer processor524adds the updated contribution from check node704to the partial value at point B703, again creating a full variable node value. The output at point D706is the updated variable node value.

FIG. 8is a diagram of an LDPC codeword800according to an embodiment of the present disclosure. LDPC codeword800comprises an LDPC data portion801, a CRC portion802, and an LDPC parity portion803. LDPC soft-decision decoder520converges the entire codeword800(that is, the LDPC data portion801, the CRC portion802, and the LDPC parity portion803) during the soft-decision decoding. Therefore, errors in the LDPC data portion801, the CRC portion802, and the LDPC parity portion803will be corrected during the soft-decision decoding operation.

Check processor530, however, distinguishes between the LDPC data portion801and the CRC portion802. Check processor530performs the hard-decision processing operation by calculating a CRC check on the LDPC data portion801and comparing it to the CRC portion802of codeword800.

Every two clock cycles, check processor530is updated with 2L number of sign bits from each hardware memory element in IO memory510. In an embodiment of the present disclosure, only LDPC data portion801and CRC portion802are returned and it is not necessary to return LDPC parity portion803. In this case it is sufficient to exit the decoding process when LDPC data portion801and CRC portion802have converged, thereby potentially saving iterations while waiting for LDPC parity portion803to converge.

Check processor530retrieves LDPC data portion801and CRC portion802from IO memory510. Check processor520calculates the CRC check value of LDPC data portion801and compares the calculated CRC check value of LDPC data portion801to the decoded CRC check value contained in CRC portion802. If check processor530determines a match, decoder500will terminate the soft-decision decoding iterations, thus saving the overall decoding process from extra decoding iterations. In this embodiment, the read address from each hardware memory element in IO memory510is defined by the following equation:

In a further embodiment, check processor530evaluates the codeword by performing a full LDPC parity check in addition to the CRC check described above. The full LDPC parity check comprises checking the entire LDPC codeword (including the LDPC data portion801, CRC portion802, and LDPC parity portion803) according to QC H matrix200and evaluating the syndrome of the decoded codeword. In this embodiment, the read address from each hardware memory element in IO memory510is defined by the following equation:

AC⁡(t)={HR,C2⁢L,t=0(AC⁡(t-1)+1)⁢mod⁡(Q2⁢L),0<t<Q2⁢⁢L
Check processor530only processes the sign bits from the soft values taken from all of the rows of QC H matrix200stored in IO memory510. Since the soft-decision decoding of codeword800was terminated upon the completion of the hard-decision CRC check at check processor530, it is possible that codeword800includes a small number of parity check errors in LDPC parity portion803; therefore, the full LDPC parity check in the present embodiment may successfully pass while permitting a certain percentage of parity check errors. While the additional full LDPC parity check of the present embodiment provides additional hard-decision checking of codeword800, the full LDPC parity check requires more processing time as compared to the hard-decision CRC check of check processor530.

FIGS. 9A and 9Bis a flowchart of a method900of decoding LDPC codeword800according to an embodiment of the present disclosure. With respect toFIG. 9A, method900begins at the start of decoding901. At step902, layer processor524processes a layer of QC H matrix200. At step903, decoder500determines whether the number of converged check nodes in the layer is greater than or equal to a threshold number or check nodes. If the number of converged check nodes is less than the threshold number, layer processor524processes the next layer in sequence. The determination at903comprises recording the pass/fail state of each check node processed at902. The total number of passing check nodes of all layers (Cnode_total) is compared to the threshold number (Cnode_thresh). Once the total number of passing check nodes of all layers exceeds the threshold, method900proceeds to step904, and check processor530calculates the CRC check value of the LDPC data portion801of LDPC codeword800. At step905, check processor530compares the CRC calculated at step904to the CRC stored in the CRC portion802of LDPC codeword800. If the comparison is successful, method900proceeds to step906; if the comparison is unsuccessful, method900returns to step902, layer processor524processes the layer again, and the following steps are repeated.

While steps901to905are presented in a serialized manner inFIGS. 9A and 9B, processes902/908and904are performed in parallel in an embodiment of the present disclosure. Referring back toFIG. 4, method400shows parallel processes402and403, corresponding to soft-decision decoding and hard-decision processing, respectively. Similarly, processes902/908and904can be arranged to execute in parallel analogously to processes402and403.

At step906, a CRC pass count is incremented and method900proceeds to step907. The pass count represents the number of successful CRC comparisons at step905. At step907, decoder500compares the current CRC pass count to a CRC pass threshold. If the CRC pass count is less than the pass threshold, method900proceeds to step908and layer processor524processes the layer again. After step908, method900returns to step904to calculate the CRC of LDPC data portion801once again.

If, at step907, the CRC pass count is greater than or equal to the pass threshold, LDPC codeword800is read from IO memory510and sent to check processor530at step909to calculate the CRC of LDPC data portion801.

Reference is now made toFIG. 9B, which describes the second half of method900. At step910, check processor compares the CRC calculated at step909to the CRC stored in corrected CRC portion802. If the two CRC values match, method900proceeds to step913and declares the decoding operation successful.

In a further embodiment, method900includes steps911and912. After check processor530matches the two CRC values at step910, check processor530performs a full or partial parity check of codeword800by multiplying QC H matrix200with codeword800to generate a decoding syndrome at step911and evaluating the syndrome at step912. If the evaluation is successful, method900continues to step913. Otherwise, the further embodiment of method900proceeds to step914. Optional steps911and912demonstrate that LDPC data portion801and CRC portion802can be decoded successfully (indicated by a successful CRC check at step910), yet LDPC parity portion803can be incompletely decoded (indicated by failed full parity check at steps911and912). Because many applications only require LDPC data portion801and discard LDPC parity portion803, this illustrates how decoder500can be used to save decoder processing time.

Returning to step910, check processor530compared the CRC calculated from LDPC data portion801to the CRC stored in CRC portion802. If the CRC values do not match, method900also proceeds to step914. At step914, decoder500reads a second run flag to determine whether codeword800had one decoding process or had two decoding processes. If the flag indicates decoder500has attempted to decode codeword800twice already, method900proceeds to step915and declares a failed decoding operation.

If decoder500has only attempted one decoding operation of codeword800, decoder500proceeds to attempt a second decoding operation at step916. At916, the second run flag is asserted, and the check node threshold number used at step903and the CRC pass threshold number used at step907are increased. Method900returns to step901to begin a second decoding operation on codeword800.

Since check processor530runs in parallel to shift processor522and layer processors524, this allows the CRC processing for exit determination to proceed asynchronously to the soft-decision LDPC decoding. Due to asynchronous processing it is possible for check processor530to signal convergence while layer processor524independently triggers a change that would result in a non-convergence state. Therefore, an embodiment of the present disclosure includes additional processing logic to manage these rare events. In this embodiment, check processor530can be configured to perform post-exit rechecking on codeword800to verify convergence and in these rare cases restart the decoding process to allow convergence to be obtained.

Embodiments of the disclosure can be represented as a hardware product implemented in an Integrated Circuit (IC), Programmable Gate Array, or some combination of Integrated Circuit(s), Programmable Gate Array(s), and Software. Those of ordinary skill in the art will appreciate that other functions can also be implemented on such Integrated Circuits or Programmable Gate Arrays.