Method and apparatus for vertical layered decoding of quasi-cyclic low-density parity check codes using predictive magnitude maps

Abstract

A method and apparatus for decoding quasi-cyclic LDPC codes using a vertical layered iterative message passing algorithm. The algorithm of the method improves the efficiency of the check node update by using one or more additional magnitudes, predicted with predictive magnitude maps, for the computation of messages and update of the check node states. The method allows reducing the computational complexity, as well as the storage requirements, of the processing units in the check node update. Several embodiments for the apparatus are presented, using one or more predictive magnitude maps, targeting significant savings in resource usage and power consumption, while minimizing the impact on the error correction performance loss.

Claims

1. A method for vertical layered decoding of quasi-cyclic low-density parity-check (LDPC) codes, the method comprising: receiving, as inputs, channel values belonging to a channel output alphabet; using the channel values for initializing and iteratively processing messages between variable nodes and check nodes within block-columns in an arbitrary order, and sequentially; initializing, during the initializing, check node states associated with the check nodes by computing syndrome bits and magnitudes of the check node states; computing, during the initializing, respective signs of variable-to-check messages; storing the check node states in a check node memory, with each check node state associated to a check node comprising a syndrome bit computed from the signs of the variable-to-check messages of the associated check node and a set of values comprising one or more smallest magnitudes of the variable-to-check messages of the associated check node, along with a same number of respective block-column indices; iteratively processing a group of the one or more block-columns, wherein the iterative processing includes: computing new check-to-variable messages with inputs comprising the check node states and the signs of the variable-to-check messages as inputs, wherein for each check node, the computation is performed using a check node update-generator (CNU-Generator) step that uses the magnitudes of the associated check node state and one or more additional magnitudes generated from the magnitudes of the associated check node state, by using one or more predictive magnitude maps; computing new variable-to-check messages with inputs comprising the channel values and the check-to-variable messages, using one or more variable node update functions; and updating the check node states to new values with inputs comprising the variable-to-check messages, wherein for each check node state, the updating is performed using a check node update-updater (CNU-Updater) step that uses the magnitudes of the associated check node state and one or more additional magnitudes generated from the magnitudes of the associated check node state by using one or more predictive magnitude maps; computing the syndrome bits from the hard decision estimates and checking whether the hard-decision estimates constitute a codeword; and outputting the codeword, in accordance with the hard-decision estimates constituting a codeword.

2. The method of claim 1, wherein: each check node state associated to a check node comprises the syndrome bit computed from the signs of the variable-to-check messages of the associated check node and a set of two smallest magnitudes of the variable-to-check messages of the associated check node along with their two respective block-column indices; and during the CNU-Updater step at each check node, the associated check node state is updated using the set of two smallest magnitudes of the associated check node state and a third magnitude generated from the set of two smallest magnitudes of the associated check node state by using a predictive magnitude map.

3. The method of claim 1, wherein: each check node state associated to a check node comprises the syndrome bit computed from the signs of the variable-to-check messages of the associated check node and a single smallest magnitude of the variable-to-check messages of the associated check node along with its respective block-column index; during the CNU-Updater step at each check node, the associated check node state is updated using the single magnitude of the associated check node state and a second magnitude generated from the single magnitude of the associated check node state by using a predictive magnitude map; and during the CNU-generator step at each check node, the new check-to-variable messages are computed using the single magnitude of the associated check node state and a second magnitude generated from the magnitude of the associated check node state by using a predictive magnitude map.

4. The method of claim 1, wherein: the iterative processing is performed sequentially in arbitrary order from one block-column to another block-column; each check node state associated to a check node comprises the syndrome bit computed from the signs of the variable-to-check messages of the associated check node and a set of two smallest magnitudes of the variable-to-check messages of the associated check node along with their two respective block-column indices; during the CNU-Updater step at each check node, the associated check node state is updated using the two magnitudes of the associated check node state and a third magnitude that is selected from a plurality of magnitudes generated from the two magnitudes of the associated check node state by using a plurality of predictive magnitude maps; and the third magnitude is selected from a plurality of magnitudes for use in the CNU-Updater step based on the index of the block-column that is being processed.

5. The method of claim 1, further comprising computing the syndrome weight during the iterative processing of each group of one or more block-columns, and wherein: each check node state associated to a check node comprises the syndrome bit computed from the signs of the variable-to-check messages of the associated check node and the set of two smallest magnitudes of the variable-to-check messages of the associated check node along with their two respective block-column indices; during the CNU-Updater step at each check node, the associated check node state is updated using the set of two smallest magnitudes of the associated check node state and a third magnitude that is selected from a plurality of magnitudes generated from the set of two smallest magnitudes of the associated check node state by using a plurality of predictive magnitude maps; and the third magnitude is selected from a plurality of magnitudes for use in the CNU-Updater step based on the value of the syndrome weight.

6. The method of claim 1, wherein: each check node state associated to a check node comprises the syndrome bit computed from the signs of the variable-to-check messages of the associated check node and a set of two smallest magnitudes of the variable-to-check messages of the associated check node along with their two respective block-column indices; during the CNU-Updater step at a check node, the associated check node state is updated using the set of two smallest magnitudes of the associated check node state and a third magnitude that is selected from a plurality of magnitudes generated from the set of two smallest magnitudes of the associated check node state by using a plurality of predictive magnitude maps; and a third magnitude is selected from a plurality of magnitudes for use in the CNU-Updater step at a check node during the processing of a group of one or more block-columns, and a different third magnitude is selected from the plurality of magnitudes for use in the CNU-Updater step during the processing of another group of one or more block-columns.

7. The method of claim 1, wherein: the iterative processing is performed sequentially in arbitrary order from one block-column to another block-column; each check node state associated to a check node comprises the syndrome bit computed from the signs of the variable-to-check messages of the associated check node and a single smallest magnitude of the variable-to-check messages of the associated check node along with its respective block-column index; during the CNU-Updater step at a check node, the associated check node state is updated using the single magnitude of the associated check node state and a second magnitude that is selected from a plurality of magnitudes generated from the single magnitude of the associated check node state by using a plurality of predictive magnitude maps; the second magnitude is selected from a plurality of magnitudes for use in the CNU-Updater step based on the index of the block-column that is being processed; during the CNU-Generator step at a check node, the new check-to-variable messages are computed using the single magnitude of the associated check node state and a second magnitude that is selected from a plurality of magnitudes generated from the single magnitude of the associated check node state by using a plurality of predictive magnitude maps; and the second magnitude is selected from a plurality of magnitudes for use in the CNU-Generator step based on the index of the block-column that is being processed.

8. The method of claim 1, further comprising computing the syndrome weight during the iterative processing of each group of one or more block-columns, and wherein: each check node state associated to a check node comprises the syndrome bit computed from the signs of the variable-to-check messages of the associated check node and a single smallest magnitude of the variable-to-check messages of the associated check node along with its respective block-column index; during the CNU-Updater step at a check node, the associated check node state is updated using the single magnitude of the associated check node state and a second magnitude that is selected from a plurality of magnitudes generated from the single magnitude of the associated check node state by using a plurality of predictive magnitude maps; the second magnitude is selected from a plurality of magnitudes for use in the CNU-Updater step based on the syndrome weight; during the CNU-Generator step at a check node, the new check-to-variable messages are computed using the single magnitude of the associated check node state and a second magnitude that is selected from a plurality of magnitudes generated from the single magnitude of the associated check node state by using a plurality of predictive magnitude maps; and the second magnitude is selected from a plurality of magnitudes for use in the CNU-Generator step based on the value of the syndrome weight.

9. The method of claim 1, wherein: each check node state associated to a check node comprises the syndrome bit computed from the signs of the variable-to-check messages of the associated check node and a single smallest magnitude of the variable-to-check messages of the associated check node along with its respective block-column index; during the CNU-Updater step at a check node, the associated check node state is updated using the single magnitude of the associated check node state and a second magnitude that is selected from a plurality of magnitudes generated from the single magnitude of the associated check node state by using a plurality of predictive magnitude maps; a second magnitude is selected from a plurality of magnitudes for use in the CNU-Updater step at a check node during the processing of a group of one or more block-columns, and a different second magnitude is selected from the plurality of magnitudes for use in the CNU-Updater step during the processing of another group of one or more block columns; during the CNU-Generator step at a check node, the new check-to-variable messages are computed using the single magnitude of the associated check node state and a second magnitude that is selected from a plurality of magnitudes generated from the single magnitude of the associated check node state by using a plurality of predictive magnitude maps; and a second magnitude is selected from a plurality of magnitudes for use in the CNU-Generator step at a check node during the processing of a group of one or more block-columns, and a different second magnitude is selected from the plurality of magnitudes for use in the CNU-Generator step during the processing of another group of one or more block-columns.

10. The method of claim 1, further comprising computing the syndrome weight during the iterative processing of each group of one or more block-columns, and wherein: each check node state associated to a check node comprises the syndrome bit computed from the signs of the variable-to-check messages of the associated check node and a set of two smallest magnitudes of the variable-to-check messages of the associated check node along with their two respective block-column indices; during the CNU-Updater step at a check node, the associated check node state is updated using the two magnitudes of the associated check node state and a third magnitude that is selected from two values generated from the two magnitudes of the associated check node state by using two different predictive magnitude maps; and the first value of the two values is selected as the third magnitude for use in the CNU-Updater step when the syndrome weight is larger than a predetermined threshold, and the second value of the two values is selected as the third magnitude for use in the CNU-Updater step when the syndrome weight is smaller or equal to the predetermined threshold.

11. The method of claim 1, further comprising computing the syndrome weight during the iterative processing of each group of one or more block-columns, and wherein: each check node state associated to a check node comprises the syndrome bit computed from the signs of the variable-to-check messages of the associated check node and a single smallest magnitude of the variable-to-check messages of the associated check node along with its respective block-column index; during the CNU-Updater step at a check node, the associated check node state is updated using the single magnitude of the associated check node state and a second magnitude that is selected from two values generated from the single magnitude of the associated check node state by using two different predictive magnitude maps; the first value of the two values is selected as the second magnitude for use in the CNU-Updater step when the syndrome weight is larger than a predetermined threshold, and the second value of the two values is selected as the second magnitude for use in the CNU-Updater step when the syndrome weight is smaller or equal to the predetermined threshold; during the CNU-Generator step at a check node, the new check-to-variable messages are computed using the single magnitude of the associated check node state and a second magnitude that is selected from two values generated from the single magnitude of the associated check node state by using two different predictive magnitude maps; and the first value of the two values is selected as the second magnitude for use in the CNU-Generator step when the syndrome weight is larger than a predetermined threshold, and the second value of the two values is selected as the second magnitude for use in the CNU-Generator step when the syndrome weight is smaller or equal to the predetermined threshold.

12. The method of claim 1, wherein: each check node state associated to a check node comprises the syndrome bit computed from the signs of the variable-to-check messages of the associated check node and a set of smallest magnitudes of the variable-to-check messages of the associated check node along with their respective block-column indices; a predictive magnitude map is selected from a plurality of predictive magnitude maps to generate one or more magnitudes from the magnitudes of each check node state for computing the new check-to-variable messages during the CNU-Generator step; a variable node update function is selected from a plurality of variable node update functions to compute the new variable-to-check messages at each variable node using the channel value and the check-to-variable messages of the associated variable node as inputs; and the variable node update function is selected based on the predictive magnitude map that is used during the CNU-Generator step at each check node.

13. An apparatus for vertical layered decoding of quasi-cyclic low-density parity-check (LDPC) codes, the apparatus comprising: a check node memory storing check node states associated to check nodes, wherein each stored check node state associated to a check node comprises a syndrome bit computed from signs of variable-to-check messages of the associated check node and a set of values comprising one or more smallest magnitudes of the variable-to-check messages of the associated check node along with a same number of respective block-column indices; a predictive magnitude map check node update-generator (PMM-CNU-Generator) processing unit that computes new check-to-variable messages at each check node using magnitudes of the associated check node state and one or more additional magnitudes generated from the magnitudes of the associated check node state by using one or more predictive magnitude maps; and a predictive magnitude map check node update-updater (PMM-CNU-Updater) processing unit that updates the check node state of each check node by using the magnitudes of the associated check node state and one or more additional magnitudes generated from the magnitudes of the associated check node state by using one or more predictive magnitude maps.

14. The apparatus of claim 13, wherein: each check node state associated to a check node comprises the syndrome bit computed from the signs of the variable-to-check messages of the associated check node and the set of two smallest magnitudes of the variable-to-check messages of the associated check node along with their two respective block-column indices; and the PMM-CNU-Updater processing unit updates the check node state of each check node by using the set of two smallest magnitudes of the associated check node state and a third magnitude that is selected from a plurality of magnitudes generated from the set of two smallest magnitudes of the associated check node state by using a plurality of predictive magnitude maps.

15. The apparatus of claim 13, wherein: each check node state associated to a check node comprises the syndrome bit computed from the signs of the variable-to-check messages of the associated check node and a single smallest magnitude of the variable-to-check messages of the associated check node along with its respective block-column index; the PMM-CNU-Generator processing unit computes the new check-to-variable messages at each check node by using the single magnitude of the associated check node state and a second magnitude that is selected from a plurality of magnitudes generated from the single magnitude of the associated check node state by using a plurality of predictive magnitude maps; and the PMM-CNU-Updater processing unit updates the check node state of each check node by using the single magnitude of the associated check node state and a second magnitude that is selected from a plurality of magnitudes generated from the single magnitude of the associated check node state by using a plurality of predictive magnitude maps.

16. The apparatus of claim 13, further comprising a variable node update module that uses a plurality of variable node update functions, wherein: each check node state associated to a check node comprises the syndrome bit computed from the signs of the variable-to-check messages of the associated check node and a set of smallest magnitudes of the variable-to-check messages of the associated check node along with their respective block-column indices; the PMM-CNU-Generator processing unit selects a predictive magnitude map from a plurality of predictive magnitude maps to generate one or more magnitudes from the magnitudes of each check node state for computing the new check-to-variable messages at each check node; the variable node update module selects a variable node update function from a plurality of variable node update functions to compute the new variable-to-check messages at each variable node using the channel value and the check-to-variable messages of the associated variable node as inputs; and the variable node update module selects the variable node update function based on the predictive magnitude map that is used at each check node by the PMM-CNU-Generator processing unit.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) For a more complete understanding of the invention, reference is made to the following description and accompanying drawings, in which:

(2) FIG. 1 shows the top level architecture of a PMM-VL decoder showing the proposed PMM-CNU module. The two units that use the predictive magnitude maps, as part of this invention, are the PMM-CNU-Generator and the PMM-CNU-Updater;

(3) FIG. 2 shows a preferred embodiment for the architecture of a PMM-CNU-Generator unit, in the case of a check node state with only ω=1 magnitude pair;

(4) FIG. 3 shows a preferred embodiment for the architecture of a PMM-CNU-Updater unit, in the general case of a check node state with ω magnitude pairs;

(5) FIG. 4 shows a preferred embodiment for the architecture of a Multiple-PMM unit to be used in the PMM-CNU-Generator and the PMM-CNU-Updater, for dynamical PMM switching based on the iteration number and/or the block-column index;

(6) FIG. 5 shows the top Level architecture of a Multiple-PMM-VL decoder showing the proposed Multiple-PMM-CNU module, for dynamical PMM switching based on Syndrome weight; and

(7) FIG. 6 shows a preferred embodiment for the architecture of a Multiple-PMM unit to be used in the PMM-CNU-Generator and the PMM-CNU-Updater, for dynamical PMM switching based on the syndrome weight.

DETAILED DESCRIPTION OF THE INVENTION

(8) The method of the present invention relates to an iterative message-passing LDPC decoder operating on QC-LDPC codes, whose parity-check matrix consists of circulant permutation matrices (CPMs) of size L×L. The parity-check matrix is configured to have N.sub.b block-columns and M.sub.b block-rows. The j-th block-column contains d.sub.v(j) CPMs, and the i-th block-row contains d.sub.c(i) CPMs. In the rest of the description, we will drop the indices i and j in these notations. Nonetheless, all embodiments of the present invention apply both for regular and irregular LDPC codes.

(9) The message-passing decoder of the present invention follows the VL scheduling, exchanging messages between the VNU module and the CNU module. The messages passing from the VNU module to the CNU module are named variable-to-check messages, denoted μ.sub.v.sub.n.sub.,c.sub.m, and the messages passing from the CNU module to the VNU module are named check-to-variable messages, denoted μ.sub.c.sub.m.sub.,v.sub.n. The messages μ.sub.v.sub.n.sub.,c.sub.m and μ.sub.c.sub.m.sub.,v.sub.n are associated to the edge in the Tanner Graph of the LDPC code connecting VN v.sub.n and CN c.sub.m. In preferred embodiments of the present invention, the messages are represented using a fixed, typically small, number of precision bits, denoted n.sub.s. The messages belong to a finite alphabet , as described in the background.

(10) In various preferred embodiments of the method of the present invention, the VL decoder processes the N.sub.b block-columns of the QC-LDPC code in an arbitrary order, during a decoding iteration. We assume without loss of generality that the block-columns are processed sequentially from index j=1 to index j=N.sub.b. During a decoding iteration, the current block-column will be denoted as the processed block-column. Furthermore, each block-column is composed of L variable nodes. When the decoder operates the VNU of a VN v.sub.n within the processed block-column, v.sub.n will be denoted as a processed VN. Finally, when the decoder operates the CNU of a check-node c.sub.m connected to a processed VN, c.sub.m will be denoted as processed CN.

(11) In other preferred embodiments of the method, the VL decoder performs the processing of a plurality of block-columns, each of them composed of L variable nodes. Although for purposes of exposition, the method is described assuming the processing of a single processed block-column, the skilled in the art could easily generalize the method to a plurality of processed block-columns.

(12) As described in the background, the VL decoder requires the use of several smallest magnitudes, denoted mag.sub.k, and their corresponding block-column indices, denoted index.sub.k, which are stored in the CNM.

(13) In this invention, we propose to simplify the CNU processing (CNU-Step-A and CNU-Step-B) and reduce the size of the CNM, with the objective of reducing the resource usage of the VL decoder implementation, and minimizing its computational complexity. The proposed method implements the closest approximation of the CNU that would use a CNS with MAG(ω+1), but using only values available in a CNS with MAG(ω).

(14) In order to describe the method, let us first assume that the CNS is composed of ω magnitude pairs:

(15) $\begin{array}{cc}\begin{array}{c}{\mathrm{CNS}}^{\left(\omega \right)}\left(c_m\right)=\left\{s_m;\mathrm{MAG}\left(\omega \right)\right\}\\ =\{s_m;\left(\mathrm{ma}{g}_1,\mathrm{inde}{x}_1\right),\mathrm{.Math.},\left(\mathrm{ma}{g}_k,\mathrm{inde}{x}_k\right),\mathrm{.Math.},\\ \left(\mathrm{ma}{g}_{\omega },\mathrm{inde}{x}_{\omega }\right)\}\end{array}& \left(13\right)\end{array}$
We equip the CNU module in the decoder with a function χ.sub.ω which maps the ω magnitudes of the CNS into an additional magnitude:
.sub.ω+1=χ.sub.ω(mag.sub.1, . . . ,mag.sub.2)  (14)
We will call this function predictive magnitude map (PMM) throughout the description. The PMM could be any linear or non-linear mapping function from .sup.ω to .

(16) Although described in a very general manner, the proposed method is of special interest for small values of ω. In preferred embodiments of this invention, the PMM is defined for the following cases: .sub.2=χ.sub.1(mag.sub.1) In this minimum configuration, the CNM stores, for each check node, a CNS composed only of three values: (i) the value of the syndrome bit s.sub.m, (ii) the smallest magnitude mag.sub.1 of the incoming variable-to-check messages, and (iii) the edge index index.sub.1 corresponding to the smallest magnitude. In this preferred embodiment, we aim at getting decoding performance close to a decoder using CNS.sup.(2)(c.sub.m), but using only values from CNS.sup.(1)(c.sub.m). Exemplary, non-limiting, PMM functions for this embodiment are given by:
.sub.2=min(mag.sub.1+a,s) a=0, . . . ,s  (15)  where s is the maximum magnitude in the message alphabet. .sub.3=χ.sub.2(mag.sub.1, mag.sub.2) In this second preferred embodiment, the CNS that is considered is CNS.sup.(2)(c.sub.m)={s.sub.m; (mag.sub.1, index.sub.1), (mag.sub.2, index.sub.2)}, and the value of .sub.3 is predicted from the two smallest magnitudes, in order to approach the performance of a decoder with CNS.sup.(3)(c.sub.m). Note that in this second preferred embodiment, there exist a larger number of PMM functions. χ.sub.2 could be a function of mag.sub.1 only, of mag.sub.2 only or of both mag.sub.1 and mag.sub.2.

(17) By definition of the magnitude state which is a sorted list, we must have .sub.ω+1≥mag.sub.ω. In preferred embodiments of the invention, we will further assume that .sub.ω+1>mag.sub.ω.

(18) The VL decoder that is proposed in this invention uses the PMM additional magnitude in the CNU processing, and is referred to as PMM-VL decoder. For a PMM-VL decoder, the two steps of the CNU presented in Algorithm 2 are replaced with a PMM-CNU with a PMM-CNU-Step-A for the check-to-variable message generation, and with a PMM-CNU-Step-B for the CNS update. The main steps of the PMM-VL decoder are described in Algorithm 3.

(19) TABLE-US-00003 Algorithm 3: PMM-VL iterative decoding Input: Channel Values Output: Hard Decision Estimates {{circumflex over (x)}.sub.n}.sub.1≤n≤N Initialization: same as in Algorithm 1 for iter = 1 to It.sub.max do  | for j = 1 to N.sub.b do  |  | PMM-CNU-Step-A: Message Generation  |  |  described in Table 1  |  | VNU-Step:  |  |  same as in Algorithm 1  |  | PMM-CNU-Step-B: CNS Update  |  |_  described in Table 2  |_

(20) An apparatus for the top level architecture of the PMM-VL decoder proposed in this invention is depicted in FIG. 1. This architecture, and especially the PMM-CNU module, is primarily designed around the Check Node Memory (CNM) 103, which stores the check node states CNS(c.sub.m) for all check nodes in the LDPC code. Each CNS(c.sub.m) is composed of the syndrome bit, s.sub.m, the corresponding check node, and the magnitude state MAG(ω), which contains ω pairs of (mag.sub.k, index.sub.k). The sign memory 106 stores the signs sign.sub.m,n of the variable-to-check messages μ.sub.v.sub.n.sub.,c.sub.m. Consequently, there is one sign for each edge connecting a VN to a CN.

(21) One can refer to the high-level description of a PMM-VL decoder in Table 3 for relating the decoding steps to the architecture units presented in FIG. 1.

(22) For ease of exposition, we now describe the functioning of the modules assuming the processing of a single processed block-column. However, the description of the modules are also applicable to the more general case of processing a plurality of processed block-columns.

(23) The initializer unit 102 takes the channel values 101, or any transformation of the channel values as inputs, and uses them to initialize the CNSs in the CNM 103. It computes the initial syndrome bits for all CNs, and the initial values of the magnitude states, which depend only on the magnitudes of the channel values or of their transformation. Alternatively, the initial magnitude states could be set by the initializer unit to fixed, predetermined values. After the initialization is performed, the CNM contains the initial values of the CNSs. The initializer unit also computes the initial values of the variable-to-check message signs, which are stored in the sign memory 106.

(24) The PMM-CNU module is composed of two processing units: the PMM-CNU-Generator 105, which implements the message generation of PMM-CNU-Step-A, and the PMM-CNU-Updater 104, which implements the CNS update of PMM-CNU-Step-B. After initialization, the PMM-CNU module and the VNU module exchange messages iteratively, flowing through the Barrel Shifter units 107 and 108. The barrel shifters re-order the messages addresses according to the circulant permutation matrices of the QC-LDPC code.

(25) For a processed block-column of degree d.sub.v, the decoder proceeds as follows for each processed VN v.sub.n in the block-column. For each processed CN connected to v.sub.n, the PMM-CNU-Generator 105 reads the CNS from the CNM and the message sign from the sign memory 106, computes the PMM additional magnitude, and generates the check-to-variable messages μ.sub.c.sub.m.sub.,v.sub.n that will serve as inputs to the VNU module. For each processed VN, there are d.sub.v check-to-variable messages that need to be generated. After processing all VNs in the processed block-column, the messages are then cyclically shifted by the barrel shifter unit 108 according to the d.sub.v CPMs of the processed block-column.

(26) For each processed VN in the processed block-column, the VNU module 109 receives d.sub.v check-to-variable messages and the channel value corresponding to the processed VN. The VNU module computes d.sub.v variable-to-check messages μ.sub.v.sub.n.sub.,c.sub.m using the variable node update function Φ.sub.v, according to equation (5). Once all VNs in the processed block-column have been processed, the messages are cyclically shifted by the barrel shifter unit 107 and sent to the PMM-CNU-Updater 104.

(27) For each processed CN, the PMM-CNU-Updater takes as inputs the corresponding variable-to-check message from 107, its associated CNS from 103 and the corresponding sign from 106. Note that the sign sign.sub.m,n coming from the sign memory is the sign of the corresponding variable-to-check message μ.sub.v.sub.n.sub.,c.sub.m, but from the previous decoding iteration. Then, the PMM-CNU-Updater computes the PMM additional magnitude, updates the new CNS for the processed CN which is written in the CNM 103, and extracts the new sign of the message μ.sub.v.sub.n.sub.,c.sub.m which is written in the sign memory 106.

(28) The computation and update of messages and CNSs described previously is repeated until the entire parity-check matrix has been traversed which then constitutes one decoding iteration, and then the decoding process restarts again from the first block-column to begin the next decoding iteration.

(29) The VNU module also computes the APP following (8) for all VNs in the processed block-column and computes hard-decision estimates i. The hard decision estimates are sent to the validation unit 110 to check if the decoder has converged to a codeword. The validation unit computes the syndrome of the LDPC code with the most recent values of {circumflex over (x)} received from the VNU module, and stops the decoding whenever the syndrome is zero, following equation (10), meaning that the hard-decision estimates {circumflex over (x)} 111 form a valid codeword. Both the computation of the APP and the validation of the syndrome can be performed at any time during the decoding process, at the end of the processing of a block-column.

(30) The CNU-Generator computes the incoming messages to the VNU module using the CNM and the sign memory. A CNU-Generator that uses the PMM functions is referred to as PMM-CNU-Generator and implements the PMM-CNU-Step-A of Algorithm 3.

(31) From the description in Algorithm 1, it can be seen that the CNU-Generator requires only the following values from MAG(ω): (mag.sub.1, index.sub.1, mag.sub.2). As a result, this module does not require much modification to incorporate the use of the PMM function. When MAG(ω) with ω≥2 is used in a PMM-CNU-Generator, no change in the algorithm is required. When MAG(ω) with ω=1 is used in a PMM-CNU-Generator, then is computed from the PMM function χ.sub.1, and used in PMM-CNU-Step-A, as described in Table 1.

(32) TABLE-US-00004 TABLE 1 PMM-CNU-Generator processing: case of w = 1 PMM-CNU-Step-A: Message Generation for each variable node v.sub.n in block-column j, for each check node c.sub.m connected to variable node v.sub.n read the check node state CNS.sup.(1)(c.sub.m) = {s.sub.m; MAG (1)}  (a) compute the temporary extrinsic sign: {tilde over (s)} = s.sub.m .Math. sign.sub.m,n  (b) compute the PMM additional magnitude:    = χ.sub.1 (mag.sub.1)  (c) compute the input messages to the VNU: μ.sub.c.sub.m.sub.,v.sub.n = {tilde over (s)} .Math. mag.sub.1 if index.sub.1 ≠ j ; and μ.sub.c.sub.m.sub.,v.sub.n = {tilde over (s)} .Math.    if index.sub.1 = j

(33) In FIG. 2, we show the architecture of the apparatus implementing the PMM-CNU-Generator, which computes the incoming check-to-variable messages to the VNU module, in the case of ω=1.

(34) For each of the d.sub.v processed CNs c.sub.m connected to the processed VN v.sub.n in the processed block-column index*=j 203, the corresponding CNS 201 is read from the CNM, and the corresponding sign 202 is read from the sign memory. Since ω=1, the CNS is composed only of the syndrome bit s.sub.m and a single pair MAG(1)=(mag.sub.1, index.sub.1). An XOR operation is performed between the syndrome bit and the message sign sign.sub.m,n in unit 204 to compute the temporary extrinsic sign {tilde over (s)}. The PMM unit 205 computes the predicted value of from MAG(1), using function χ.sub.1. The message generation unit 206 implements the step PMM-CNU-Step-A-(c) of Table 1. At the output of unit 206, we get the check-to-variable message μ.sub.c.sub.m.sub.,v.sub.n which serves as input to the VNU.

(35) In the case of ω≥2, the PMM unit 205 is bypassed and the message generation unit 206 takes only the CNS values, the temporary extrinsic sign {tilde over (s)}, and the processed block-column index as inputs.

(36) At the output of the CNU-Generator, and for each processed VN in the processed block-column, d.sub.v check-to-variable messages are sent to the VNU module to compute the variable-to-check messages μ.sub.v.sub.n.sub.,c.sub.m, that will serve as inputs to the CNU-Updater.

(37) In a preferred embodiment of the present invention, the VNU update function is defined as a low precision function Φ.sub.v, corresponding to the FAID algorithm as described in the background. Numerous embodiments of the VNU update function Φ.sub.v are within the scope of this invention where Φ.sub.v, can be defined as a closed-form function, a look-up table, an arbitrary map, a set of equations, or any other applicable finite precision update function. The messages are represented in n.sub.s bits of precision, and the VNU update function will be referred to as a n.sub.s-bits FAID update function, which can be applied indifferently to hard output channels, or any n.sub.q-bits soft input channel.

(38) In other preferred embodiments of the present invention, the VNU module can use multiple VNU update functions {Φ.sub.v.sup.(1), . . . , Φ.sub.v.sup.(d)} for the computation of the variable-to-check messages, in order to improve the error correction performance of the decoder. For example, different VNU update functions can be used for different block-column processing.

(39) For each processed VN v.sub.n in the processed block-column, composed of d.sub.v circulants, the CNU-Updater computes new values of the CNS for the d.sub.v processed CNs connected to v.sub.n. A CNU-Updater that uses the PMM functions is referred to as PMM-CNU-Updater and implements the PMM-CNU-Step-B of Algorithm 3.

(40) The PMM-CNU-Updater described in Table 2 differs from the CNU-Updater of the classical VL decoder in steps (f) and (i). From the magnitudes stored in MAG(ω) of a CNS, the PMM function χ.sub.ω computes an additional magnitude .sub.ω+1, which forms a additional magnitude pair together with the current block-column index: (.sub.ω+1, index*). On top of the new magnitude pair (mag*, index*), the PMM additional pair is also considered in the sorted list before truncation, in step (i).

(41) TABLE-US-00005 TABLE 2 PMM-CNU-Updater processing PMM-CNU-Step-B: CNS Update for each variable node v.sub.n in block-column j, for each check node c.sub.m connected to variable node v.sub.n, read the check node state CNS(c.sub.m) = {s.sub.m; MAG (w)}  (d) compute the temporary extrinsic sign: {tilde over (s)} = s.sub.m .Math. sign.sub.m,n  (e) compute mag* = |μ.sub.v.sub.n.sub.,c.sub.m| and set index* = j  (f) compute the PMM additional magnitude: .sub.  .sub.+1 = χ.sub.w (mag.sub.1,..., mag.sub.w) compute the new check node state CNS(c.sub.m):  (g) s.sub.m = {tilde over (s)} .Math. sign (μ.sub.v.sub.n.sub.,c.sub.m)  (h) if index.sub.k in the truncated list MAG (w) is equal to index*, remove  (mag.sub.k, index.sub.k) from the list  (i) insert (mag*, index*) and the additional PMM pair ( .sub.+1, index*)  in the sorted list and truncate it to w values.

(42) In FIG. 3 we show the architecture of the apparatus implementing the PMM-CNU-Updater, which updates the CNS stored in the CNM, for the general case of ω magnitude states.

(43) For a processed VN v.sub.n in a given processed block-column index*=j 304 and for each processed CN c.sub.m connected to v.sub.n, the PMM-CNU-Updater takes as inputs the new variable-to-check message μ.sub.v.sub.n.sub.,c.sub.m 301 that has been generated by the VNU module, the corresponding sign sign.sub.m,n 303 from the previous iteration, and the old CNS for c.sub.m 302. The CNS is composed of the syndrome bit s.sub.m and ω pairs (mag.sub.k, index.sub.k) in the magnitude state, MAG(ω).

(44) The sign and magnitude of the new variable-to-check message 301 are extracted, i.e. mag*=|μ.sub.v.sub.n.sub.,c.sub.m| and sign*=sign (μ.sub.v.sub.n.sub.,c.sub.m). The value sign* corresponds to the new sign sign.sub.m,n.sup.new 310 to be stored in the sign memory 101. The updated syndrome bit s.sub.m.sup.new is obtained using a 3-input XOR unit 306 which performs an XOR operation of the old syndrome bit s.sub.m with the old sign sign.sub.m,n, and with the sign of the new input message sign*.

(45) The PMM unit 307 computes the value of .sub.ω+1 from the magnitudes in MAG(ω), using the PMM function χ.sub.ω.

(46) For each processed CN, the Magnitude State Updater unit 308 computes the updated magnitude state MAG.sup.new(ω). It receives as inputs the magnitude of the input message mag*, the old magnitude state MAG(ω), the PMM additional magnitude .sub.ω+1, and the index of the processed block-column index*=j.

(47) The Magnitude State Updater proceeds as follows. First, the unit checks if the current index index* is present in the old magnitude state MAG(ω), and removes the corresponding pair (mag.sub.k, index.sub.k). If index* does not appear in MAG(ω), no pair is removed. Then, we associate the current block-column index to the PMM additional magnitude to form a PMM pair (.sub.ω+1, index*). The PMM pair and the newly generated pair (mag*, index*) are inserted in the sorted list to compute the new magnitude state, MAG.sup.new(Ω). At this stage of the processing, the size of the magnitude state is either Ω=ω+1 or Ω=ω+2, depending on whether a pair (mag.sub.k, index.sub.k) has been removed from the old magnitude state or not. The sorted magnitude state MAG.sup.new(Ω) is truncated to the smallest w magnitudes, in order to form the updated magnitude state MAG.sup.new(ω).

(48) Finally, the updated syndrome bit and the updated magnitude state are combined into the new check node state 309, which is sent and written to the CNM.

(49) For the preferred embodiment of ω=1, the Magnitude State Updater 308 computes the new magnitude state according to the following rules:
If(index*=index.sub.1)&(mag*≤).Math.MAG.sup.new(1)=(mag*,index*)
If(index*=index.sub.1)&(mag*>).Math.MAG.sup.new(1)=(,index*)
If(index*≠index.sub.1)&(mag*≤mag.sub.1).Math.MAG.sup.new(1)=(mag*,index*)
If(index*≠index.sub.1)&(mag*>mag.sub.1).Math.MAG.sup.new(1)=(mag.sub.1,index.sub.1)

(50) For the preferred embodiment of ω=2, the Magnitude State Updater 308 computes the new magnitude state according to the following rules:
If(index*=index.sub.1)&(mag*≤mag.sub.2).Math.MAG.sup.new(2)={(mag*,index*),(mag.sub.2,index.sub.2)}
If(index*=index.sub.1)&(mag*>mag.sub.2)&(mag*≤).Math.MAG.sup.new(2)={(mag.sub.2,index.sub.2),(mag*,index*)}
If(index*=index.sub.1)&(mag*>).Math.MAG.sup.new(2)={(mag.sub.2,index.sub.2),(,index*)}
If(index*=index.sub.2)&(mag*≤mag.sub.1).Math.MAG.sup.new(2)={(mag*,index*),(mag.sub.1,index.sub.1)}
If(index*=index.sub.2)&(mag*>mag.sub.1)&(mag*≤).Math.MAG.sup.new(2)={(mag.sub.1,index.sub.1),(mag*,index*)}
If(index*=index.sub.2)&(mag*>).Math.MAG.sup.new(2)={(mag.sub.1,index.sub.1),(,index*)}
If(index*≠index.sub.1)&(index*≠index.sub.2)&(mag*≤mag.sub.1).Math.MAG.sup.new(2)={(mag*,index*),(mag.sub.1,index.sub.1)}
If(index*≠index.sub.1)&(index*≠index.sub.2)&(mag*>mag.sub.1)&(mag*≤mag.sub.2).Math.MAG.sup.new(2)={(mag.sub.1,index.sub.1),(mag*,index*)}
If(index*≠index.sub.1)&(index*≠index.sub.2)&(mag*>mag.sub.2).Math.MAG.sup.new(2)={(mag.sub.1,index.sub.1),(mag.sub.2,index.sub.2)}

(51) As part of this invention, the PMM-VL decoder may also use a plurality of PMM functions in order to improve the error correction performance. For purposes of exposition, let us assume that for a magnitude state of size w, there are d PMM functions in the set {χ.sub.ω.sup.(1), . . . , χ.sub.ω.sup.(d)} that are available to use.

(52) The proposed method is based on the fact that a PMM-VL decoder that uses χ.sub.ω.sup.(k) and a PMM-VL decoder that uses χ.sub.ω.sup.(k′) with k≠k′ can have different iterative decoding dynamics, and therefore yield different decoding results. For example, some PMM functions could be more effective to correct the errors in the so-called waterfall region of the error rate performance of the LDPC code, while other PMM functions could be more efficient in the error floor region of the error rate performance of the LDPC code.

(53) We propose to use the diversity of decoder dynamics brought by multiple different PMM functions to improve the overall error correction performance of a PPM-VL decoder. Such a decoder will be referred to as Multiple-PMM-VL decoder. There are several ways of switching between different PMM functions during decoding. We present, as examples, three preferred embodiments of the method that switches between different PMM functions during decoding in a Multiple-PMM-VL decoder. However, any other strategy of combining the outcomes of a plurality of PMM functions in a Multiple-PMM-VL decoder falls within the scope of this invention.

(54) Static Switching: we refer to static switching as the case when the Multiple-PMM-VL decoder uses sequentially different PMM functions and re-initializes the decoding with the channel values each time the decoder switches to a new PMM function.

(55) In this preferred embodiment, the Multiple-PMM-VL starts the decoding of PMM-VL using χ.sub.ω.sup.(1), for a maximum of It.sub.max.sup.(1) iterations. If the decoder has not converged to a valid codeword, then the decoding of PMM-VL is restarted with the same inputs but uses the next PMM function χ.sub.ω.sup.(2), for a maximum of It.sub.max.sup.(2) iterations. When the decoder is restarted, the channel values 101 are used as inputs, going through the Initializer unit 102, therefore initializing the CNM 103 and the sign memory 106 with the same values as in the beginning of the decoding. This process is repeated until decoding is successful, or all d PMM functions have been exhausted.

(56) Dynamical Switching based on the block-column index and/or the iteration number: we refer to dynamical switching as the case when the Multiple-PMM-VL decoder can select dynamically a particular PMM function, among the d available functions, during decoding and at each block-column processing, according to some constraint or a particular value of a decoder parameter. In dynamical switching, the decoder does not restart with a new initialization, and proceeds with the decoding only modifying the PMM function.

(57) In this second preferred embodiment, the Multiple-PMM-VL switches between different PMM functions based on the iteration number and/or the index of the block-column. In this embodiment, a list of D pre-determined values for the iteration numbers and for the block-column indices needs to be chosen. The iteration numbers are denoted {It.sup.(1), . . . , It.sup.(D)}, with It.sup.(k)≤It.sup.(k+1) and the block-column indices are denoted {index.sup.(1), . . . , index.sup.(D)}. Each pair of value (It.sup.(k), index.sup.(k)) is associated with a particular PMM function PMM(k). The architecture of the apparatus which implements the Multiple-PMM selection unit is described in FIG. 4. The Multiple-PMM unit described in this figure replaces the PMM units, 205 in the PMM-CNU-Generator and 307 in the PMM-CNU-Updater. In this Multiple-PMM unit, the magnitudes in MAG(ω) are input in 401 and are used to generate the PMM additional magnitude 406, using one of the available PMM functions. During decoding, when It*=It.sup.(k) and index*=index.sup.(k), then the multiplexer 405 selects PMM.sub.k 404 to generate the PMM additional magnitude.

(58) In the general case, the number of PMM functions d is allowed to be different than the number of switches D. For example, if D>d, the same PMM functions can be selected multiple times during the decoding process.

(59) Dynamical Switching Based on Syndrome Weight.

(60) In this third preferred embodiment, the Multiple-PMM-VL switches between different PMM functions based on the value of the syndrome weight, equal to the sum of all syndrome bits stored in the CNSs, i.e. S.sub.ω=Σ.sub.m=1.sup.M s.sub.m. The architecture of this embodiment of the Multiple-PMM-VL decoder is shown in FIG. 5. The decoder is equipped with a syndrome weight computation unit 512 which uses, as inputs, the syndrome bits produced by the Validation unit 510. The value of the syndrome weight is sent to the Multiple-PMM-CNU modules 504 and 505.

(61) The PMM units, 205 in the PMM-CNU-Generator and 307 in the PMM-CNU-Updater, are replaced with the Multiple-PMM unit described in FIG. 6. As an example, we describe the non-limiting case of d=2 PMM functions, and the generalization to a larger number of PMM functions follows easily. The decoding starts with the first PMM function 603, and the syndrome weight S.sub.ω in 602 is monitored at each block-column processing. The decision to switch between the two PMM functions 603 and 604 is taken by comparing the syndrome weight to a fixed, predetermined threshold δ, in unit 606. When the constraint S.sub.ω≥δ is satisfied, PMM.sub.1 is selected, and when the constraint S.sub.ω<δ is satisfied, then PMM.sub.2 is selected. The generalization to d>2 PMM functions requires the use of d−1 predetermined thresholds {δ.sup.(1), . . . , δ.sup.(d−1)}.

(62) Other possible embodiments of the Multiple-PMM-VL decoder include (i) using a combination of the iteration and block-column index together with the syndrome weight for taking the decision to switch to a different PMM functions, or (ii) using a different metric than S, for switching between different PMM functions, including metrics that combine the syndrome bits and the values of the magnitudes stored in the CNSs.

(63) In other preferred embodiments of the Multiple-PMM-VL decoder, we consider also the use of multiple VNU update functions {ϕ.sub.ω.sup.(1), . . . , ϕ.sub.ω.sup.(d)}, which can be defined, without loss of generality, as finite precision FAID update functions. In these embodiments, each PMM function in the set {χ.sub.ω.sup.(1), . . . , χ.sub.ω.sup.(d)} is associated to a VNU update function to form pairs of functions (ϕ.sub.ω.sup.(k), χ.sub.ω.sup.(k)). Whenever the Multiple-PMM-VL decoder switches to a different PMM function, according to one of the switching strategies described previously, the new PMM function is used in the Multiple-PMM-CNU modules while the associated new VNU update function is used in the VNU module 509.