Method for controlling a check node of a NB-LDPC decoder and corresponding check node

Abstract

Some embodiments are directed to a method for controlling a check node of a NB-LDPC decoder. The check node receives d.sub.c input lists U.sub.i and delivers and delivers d.sub.c output lists V.sub.i, with i[1 . . . d.sub.c]. Each input list and output list includes n.sub.m elements and each element of the input or output lists includes a reliability value associated to a symbol of a Galois Field GF(q) with q>n.sub.m. The input elements and output elements are sorted according to the reliability values in the lists. The method is a syndrome-based method. The syndromes are sums of d.sub.c elements of input lists U.sub.i. The method includes a step of syndrome calculation, a step of decorrelation and a step for generating the output list.

Claims

1. A method for controlling a check node of a decoder for decoding non-binary LDPC codes, the check node receiving dc input lists Ui of nm elements (Ui[j]) and delivering dc output lists Vi of nm elements (Vi[j]), with i[1. . . d c ], with dc>2, each element of the input or output lists, called respectively input element and output, comprising a reliability value (LLR(Ui[j]), LLR(Vi[j])) associated to a symbol (GF(Ui[j]), GF(Vi[j])) of a Galois Field GF(q) with q>nm and q>nm, the input elements and output elements being substantially sorted according to the reliability values respectively in the input list and output list, the method comprising: adding dc input elements of input lists Ui in order to generate a plurality of sums called syndromes, each of the input elements belonging to a distinctive input list among the dc input lists Ui and each syndrome comprising a reliability value which is the sum of the reliability values of the input elements and a symbol of the Galois field which is the sum of the symbols of the input elements in the Galois field, applying, for each output list Vi, a decorrelation to the syndromes by subtracting the input element of the input list Ui from the syndromes in order to generate decorrelated syndromes, and selecting, for each output list Vi, as output elements of the output list Vi, the nm decorrelated syndromes having the highest reliability values and generated for the output list Vi.

2. The method according to claim 1, wherein, in the adding step, each syndrome is generated based on at most k input elements different from the input elements having the highest reliability values, with k<dc.

3. The method according to claim 1, wherein, in the adding step, each syndrome is generated based on input elements whose distance, called reliability distance, from the input elements having the highest reliability values is lower than a maximum reliability distance.

4. The method according to claim 3, wherein the maximum reliability distance is depending on k.

5. The method according to claim 1, wherein the output elements of the output list Vi are selected by sorting the decorrelated syndromes generated for the output list Vi according to the reliability values and by selecting the nm decorrelated syndromes having the highest reliability values.

6. The method according to claim 1, wherein, for an output list Vi to be generated, the decorrelation is applied to syndromes generated from the input element of the input list Ui having the highest reliability values.

7. The method according to claim 6, wherein, before the decorrelation step, the syndromes are sorted according to the reliability values of the syndromes such that, after the decorrelation step, the decorrelated syndromes generated for the output list Vi are sorted according to the reliability values, and the elements of the output list Vi are the nm decorrelated syndromes having the highest reliability values.

8. The method according to claim 1, wherein, before or after or in parallel with the syndrome generation, the method further comprises the steps of: preselecting input elements, called probes, in the input lists Ui, each probe having a reliability value representative for a group of p neighboring input elements comprising the probe, evaluating the preselected probes in order to select and sort a predetermined number of the preselected probes, the probes, called final probes, being sorted according to the reliability values; and selecting generated syndromes based on the final probes, the syndromes being sorted in the order of the final probes.

9. The method according to claim 8, wherein the probe is the input element having the highest reliability value in the group of p neighboring input elements comprising the probe and the reliability value of the probe is the highest reliability value.

10. The method according to claim 8, wherein the reliability value of the probe is a combination of the reliability values of the p neighboring input elements.

11. The method according to claim 1, wherein, before the syndrome generation, the method further comprises the steps of: preselecting input element, called probes, in the input lists Ui, each probe having a reliability value representative for a group of p neighboring input elements comprising the probe, and evaluating the preselected probes in order to select and sort a predetermined number of the preselected probes, the probes, called final probes, being sorted according to the reliability values; and wherein in the syndrome generation step, the syndromes are generated based on the final probes, the syndromes being sorted in the order of the final probes.

12. A check node of a decoder for decoding non-binary LDPC codes comprising: dc inputs for receiving dc input lists Ui of nm elements (Ui[j]), called input elements, with i [1. . . d c ], nm>1 and dc>2, each input element comprising a reliability value (LLR(Ui[j])) associated to a symbol (GF(Ui[j])) of a Galois Field GF(q) with q>nm, the input elements being substantially sorted according to the reliability values in the input list, dc outputs for delivering dc output lists Vi of nm elements (Vi[j])called output elements, with q>nm, each output element comprising a reliability value (LLR(Vi[j])) associated to a symbol (GF(Vi[j])) of a Galois Field GF(q), the output elements being substantially sorted according to the reliability values in the output list, a syndrome calculator for adding dc input elements of input lists Ui in order to generate a plurality of sums called syndromes, each of the input element belonging to a distinctive input list among the dc input lists Ui and each syndrome comprising a reliability value which is the sum of the reliability values of the input elements and a symbol of the Galois field which is the sum of the symbols of the input elements in the Galois field, dc decorrelators for applying, for each output list Vi, a decorrelation to the syndromes by subtracting the input element of the input list Ui from the syndromes in order to generate decorrelated syndromes, and selecting selector that selects, for each output list Vi, as output elements for the output list Vi, nm decorrelated syndromes having the highest reliability values and generated for the output list Vi.

13. The check node according to claim 12, further comprising dc sorters for sorting the decorrelated syndromes according to the reliability values, each one of the sorters being dedicated for sorting the decorrelated syndromes generated for a dedicated output list Vi.

14. The check node according to claim 12, further comprising one sorter for sorting the syndromes generated by the syndrome calculator according to the reliability values, the decorrelation being applied, for an output list Vi to be generated, to syndromes generated from the input element of the input list Ui having the highest reliability values.

15. The check node according to claim 12, further comprising: a probe selector for selecting input elements, and in particular probes, in the input lists Ui, each probe having a reliability value representative for a group of p neighboring input elements comprising the probe, a probe sorter for sorting the probes according to the reliability values, and a syndrome selector selecting generated syndromes based on the sorted probes, the syndromes being sorted in the order of the sorted probes.

16. The check node according to claim 12, further comprising: a probe selector for selecting input elements, and in particular probes, in the input lists Ui, each probe having a reliability value representative for a group of p neighboring input elements comprising the probe, and a probe sorter for sorting the probes according to the reliability values, wherein the syndrome calculator is driven to generate syndromes based on the sorted probes, the syndromes being sorted in the order of the sorted probes.

Description

BRIEF DESCRIPTION OF THE FIGURES

(1) Some embodiments can be better understood with reference to the following description and drawings, given by way of example and not limiting the scope of protection, and in which:

(2) FIG. 1 is a schematic representation of a check node;

(3) FIG. 2 is a flow chart illustrating the syndrome-based method according to some embodiments;

(4) FIG. 3 is a schematic representation of a check node implementing the syndrome-based method of FIG. 2;

(5) FIG. 4 is a schematic representation of syndromes;

(6) FIG. 5 are graphs showing the average LLR values of syndromes of different deviation sets;

(7) FIG. 6 is a flow chart illustrating the steps of a first variant of the syndrome-based method according to some embodiments;

(8) FIG. 7 is a schematic representation of a check node implementing the syndrome-based method of FIG. 6;

(9) FIG. 8 is a schematic representation of a decorrelator of the check illustrated by FIG. 7;

(10) FIG. 9 is a schematic representation of a sorter for sorting syndromes of the deviation sets D.sub.1 and D.sub.2;

(11) FIG. 10 is a schematic representation of a portion of the sorter of FIG. 9;

(12) FIG. 11 is a schematic view showing the distribution of probes;

(13) FIG. 12 is a flow chart illustrating the steps of a second variant of the syndrome-based method according to some embodiments using probes;

(14) FIG. 13 are curves illustrating results of the method of FIG. 12;

(15) FIG. 14 is a schematic representation of a check node implementing the syndrome-based method of FIG. 12;

(16) FIG. 15 is a schematic representation of a probe evaluator of the check node of FIG. 14;

(17) FIG. 16 is a schematic representation of a syndrome calculator of the check node of FIG. 14;

(18) FIG. 17 is a schematic representation of a syndrome selector of the check node of FIG. 14;

(19) FIG. 18 is a schematic representation of a variant of the check of FIG. 14; and

(20) FIG. 19 is a flow chart illustrating the steps of the syndrome-based method implemented by the check node of FIG. 18.

DETAILED DESCRIPTION OF THE EMBODIMENTS

(21) In the description which follows, a check node is considered, receiving as input lists of n.sub.m elements sorted in descending or ascending order and delivering as outputs lists of n.sub.m=n.sub.m elements likewise sorted in descending or ascending order. It is likewise considered that this check node works in the logarithmic field, the data exchanged between nodes then being LLR values. Of course, n.sub.m can be different from n.sub.m.

(22) More specifically, some embodiments will be described hereinbelow with reference to a check node receiving, as incoming messages, d.sub.c inputs U.sub.i and delivering, as outgoing messages, d.sub.c outputs V.sub.i, with i[1 . . . d.sub.c]. Each input U.sub.i and output V.sub.i is a tuple (ordered list) of n.sub.m LLR values each associated to a symbol of GF(q), with n.sub.m<q, the tuple elements being ordered according an ascending or descending order of their LLR values. The n.sub.m symbols of the tuple are the n.sub.m most reliable symbols (symbols having the lowest LLR values) as defined in the state-of-the-art EMS algorithm. The symbols (or Galois field elements) with the highest reliability value have a LLR=0.

(23) In the following, U.sub.i[j] designates the j.sup.th element of the input list U.sub.i and V.sub.i[j] designates the j.sup.th element of the output list V.sub.i, with j[0 . . . n.sub.m1].

(24) Before describing in detail the method of some embodiments for a check node with d.sub.c inputs and d.sub.c outputs, the principle of the inventive method is briefly described with a check node as illustrated by FIG. 1, with four inputs U.sub.1, U.sub.2, U.sub.3, U.sub.4 and four outputs V.sub.1, V.sub.2, V.sub.3, V.sub.4.

(25) As mentioned before, the four outputs are as follows:

(26) $\{\begin{array}{c}{V}_1=U_2+U_3+U_4\\ V_2=U_1+U_3+U_4\\ V_3=U_1+U_2+U_4\\ V_4=U_1+U_2+U_3\end{array}$

(27) It can be rewritten as follows:

(28) $\{\begin{array}{c}{V}_1=U_1+U_2+U_3+U_4-U_1\\ V_2=U_1+U_2+U_3+U_4-U_2\\ V_3=U_1+U_2+U_3+U_4-U_3\\ V_4=U_1+U_2+U_3+U_4-U_4\end{array}$

(29) wherein is the subtraction operator in Galois Field GF(q) and for LLR values.

(30) The basic principle of some embodiments is to first calculate the sum U.sub.1+U.sub.2+U.sub.3+U.sub.4, called syndrome, common to all or most outputs V.sub.1, V.sub.2, V.sub.3, V.sub.4 before carrying out the appropriate subtraction (decorellation) in order to obtain the 4 outputs V.sub.1, V.sub.2, V.sub.3, V.sub.4. It allows making lots of operations in parallel.

(31) FIG. 2 represents a basic flow chart of the method of some embodiments and FIG. 3 represents a basic architecture for implementing the method.

(32) According to FIG. 2, the method includes the following steps: Step S1: adding d.sub.c input elements of input lists U.sub.i in order to generate a plurality of sums called syndromes; each of the added input elements belongs to a distinctive input list U.sub.i among the d.sub.c input lists; each syndrome includes a reliability value which is the sum of the reliability values of the input elements and a symbol of the Galois field which is also the sum of the symbols of the input elements in the Galois field; the reliability values are LLR values. Step S2: for each output list V.sub.i, a decorrelation is applied to the syndromes by subtracting the input element of the input list U.sub.i from the syndromes in order to generate decorrelated syndromes, and Step S3: for each output list V.sub.i, selecting, as output elements of the output list V.sub.i, the n.sub.m decorrelated syndromes having the highest reliability values and generated for the output list V.sub.i.

(33) In the step S1, a plurality of syndromes is calculated.

(34) The set of syndromes is called S. Individual syndromes are distinguished by the elements which are chosen for the sum. This step is implemented by the syndrome calculator 10 depicted in FIG. 3.

(35) If x.sub.i designates one element U.sub.i[j] of the input list U.sub.i, with j[0 . . . n.sub.m] and i[1 . . . d.sub.c], the syndrome generated from the input elements (x.sub.1 . . . x.sub.dc), called SYN(x.sub.1 . . . x.sub.dc), is as follows:

(36) $\mathrm{SYN}\left(x_1\mathrm{.Math.}{x}_{d_c}\right)=\left\{\mathrm{LLR}\left(x_1\mathrm{.Math.}{x}_{d_c}\right),\mathrm{GF}\left(x_1\mathrm{.Math.}{x}_{d_c}\right)\right\}$$\mathrm{with}$$\{\begin{array}{c}\mathrm{LLR}\left(x_1\mathrm{.Math.}{x}_{d_c}\right)=\underset{t=1}{\overset{d_c}{.Math.}}\mathrm{LLR}\left[x_t\right],\\ \mathrm{GF}\left(x_1\mathrm{.Math.}{x}_{d_c}\right)=\underset{t=1}{\overset{d_c}{.Math.}}\mathrm{GF}\left[x_t\right],\end{array}$

(37) The syndrome set S including all or most the possible syndromes includes n.sub.m.sup.d.sup.c syndromes and is defined as follows:
S={SYN(x.sub.1. . . x.sub.d.sub.c):x.sub.iU.sub.i and i[1 . . . d.sub.c]}

(38) In the step S2, a decorrelation is applied to the syndromes by subtracting, for each output list V.sub.i to be generated, the input element of the input list U.sub.i from the syndromes in order to generate decorrelated syndromes. This step is implemented by the decorrelators 11 depicted in FIG. 3. The technical effect of this step is the decorrelation of the outputs of the check node from the inputs of the check node.

(39) This step can include or can consist of generating a dedicated syndrome set S.sup.i for every output V.sub.i, which has no correlation with input U.sub.i:

(40) $S^i=\left\{{\mathrm{SYN}}^i\left(x_1\mathrm{.Math.}{x}_{d_c}\right)\text{:}{x}_i{U}_i\mathrm{and}i\left[1\mathrm{.Math.}{d}_c\right]\right\}$$\mathrm{with}$${\mathrm{SYN}}^i\left(x_1\mathrm{.Math.}{x}_{d_c}\right)=\left\{R^i\left(x_1\mathrm{.Math.}{x}_{d_c}\right),G^i\left(x_1\mathrm{.Math.}{x}_{d_c}\right)\right\}$$\mathrm{and}$$\{\begin{array}{c}{\mathrm{LLR}}^i\left(x_1\mathrm{.Math.}{x}_{d_c}\right)=\mathrm{LLR}\left(x_1\mathrm{.Math.}{x}_{d_c}\right)-\mathrm{LLR}\left[x_i\right],\\ {\mathrm{GF}}^i\left(x_1\mathrm{.Math.}{x}_{d_c}\right)=\mathrm{GF}\left(x_1\mathrm{.Math.}{x}_{d_c}\right)-\mathrm{GF}\left[x_i\right]\end{array}$

(41) Each set Si includes n.sub.m.sup.d.sup.c.sup.1 syndromes.

(42) Once the sets S.sup.i are computed, the decorrelated syndromes within the sets S.sup.i are sorted in the step S3 according to their syndrome reliability represented by the LLR values. The sorting step is carried by the sorters 12 depicted in FIG. 3. Each output list Vi is then constituted by the n.sub.m most reliable decorrelated syndromes of the set S.sup.i.

(43) This processing method is an alternative to state-of-the-art check node processings. It is the first approach for high-order Galois field decoding, allowing for massive parallel implementations and thus high throughput and low latency. Once the syndrome set S is calculated, the decorrelation steps and the sorting steps for every output V.sub.i can be executed in parallel. The syndrome calculation can also be done in parallel. It allows having low latency processing.

(44) However, without special treatment, the calculation of the syndrome set S and the sorting of S.sup.i introduce a high complexity. It has to be reduced to make the algorithm attractive for hardware implementations. For that purpose, different improvements are proposed hereinafter. More specifically, different approaches for simplifications of the syndrome set generation and the sorting while maintaining the communications performance are proposed.

(45) According to a first advantageous embodiment, the number of syndromes of the set S is reduced. For the output computation only the most reliable values of S are used which makes the computation of all or most other syndromes superfluous. Thus a smart reduction of the cardinality of S, noted |S|, can significantly reduce the overall complexity of the algorithm without sacrificing the communications performance.

(46) The first step for a reduction of |S| is the separation of syndromes with high reliability from ones with low reliability. The syndrome set S can be defined as the union of d.sub.c+1 subsets D.sub.k (also called deviation sets), with k[0 . . . d.sub.c], such that:

(47) $S=\stackrel{d_c}{\underset{k=0}{.Math.}}{D}_k$

(48) Each subset D.sub.k contains only syndromes deviating in exactly k elements from the most reliable element. FIG. 4 represents graphically two exemplary syndromes, one with two deviations (filled circles) and one with three deviations (open circles). The deviations designate the input elements used for generating the syndrome and not having a LLR value equal to zero (highest reliability value). The subset D.sub.0 contains only one syndrome, which is the sum of the most reliable elements from all or most inputs. The subset D.sub.1 contains d.sub.c.Math.n.sub.m syndromes. More generally, the subset D.sub.k contains

(49) $\left(\begin{array}{c}{d}_c\\ k\end{array}\right).Math.{\left(n_m\right)}^k$
syndromes.

(50) FIG. 5 shows the average LLR values of the syndromes in the sorted deviation sets D.sub.k. One can observe, that the distribution of reliable LLRs depends on the Signal-to-Noise Ratio (SNR) expressed by E.sub.b/N.sub.o. However, syndromes with more than two deviations e.g. D.sub.k for k>2 have such a low reliability (high LLR value) that they rarely contribute to the generation of the outputs V.sub.i. Thus, advantageously, we can limit the calculation of subsets D.sub.k to the ones with a low amount of deviations. FIG. 5 shows that considering syndromes with one and two deviations works very well for GF(64).

(51) Therefore, according to an advantageous embodiment, the set S is limited to the union of D.sub.0, D.sub.1 and D.sub.2:

(52) 0$S=\stackrel{2}{\underset{k=0}{.Math.}}{D}_k$

(53) Another parameter for reduction of |S| is the maximum allowed reliability distance d.sub.k of elements contributing to the deviation set D.sub.k. The reliability distance describes the position of the element in the input list relative to the most reliable element (LLR=0). In FIG. 4, the most reliable element has the index zero. Less reliable elements have higher indices which describe their rank in the sorted list of LLRs.

(54) For the calculation of D.sub.k only elements with indices less or equal to d.sub.k are considered. The maximum allowed reliability distance for a certain deviation can be set dynamically based on the LLR value of the elements or it is fixed, as a predefined parameter. For each deviation a different maximum reliability distance can be set. e.g. the higher the number of allowed deviations, the lower the maximum reliability distance of the deviations, d.sub.1d.sub.2 . . . d.sub.dc. In FIG. 4, d.sub.2 is fixed to 8 and d.sub.3 is fixed to 2. The maximum reliability distance d.sub.i is not shown in this figure but is equal to n.sub.m1.

(55) Using this scheme implicitly keeps the best or better syndromes in each D.sub.k and removes the less reliable ones. The cardinality of the subsets Di can be calculated as follows:

(56) $.Math.D_k.Math.=\{\begin{array}{cc}\left(\begin{array}{c}{d}_c\\ k\end{array}\right).Math.{\left(d_k\right)}^k& \mathrm{if}{d}_{k}1;k>0\\ 1& \mathrm{if}k=0\\ 0& \mathrm{else}\end{array}$

(57) Combining both proposed techniques strictly reduces the cardinality of S and thus the computational complexity. The most reliable syndromes are calculated and only unreliable ones are removed. The parameterization for the number of deviations and their maximum reliability distances is a critical step in the algorithm. Using for example only D.sub.0, D.sub.1 and D.sub.2 with fixed reliability distances d.sub.0=0; d.sub.1=n.sub.m1; d.sub.2=2, d.sub.c=4 and n.sub.m=13, shrinks |S| from 28561 to 73. For a code in GF(64) this is a very good trade-off between complexity and communications performance.

(58) Another way to reduce the complexity is to simplify the sorting step. One big drawback of the processing presented hereinabove is that every syndrome set S.sup.i must or should be sorted separately to output the n.sub.m most reliable decorrelated syndromes. This is the case because of the decorrelation step applied before. To avoid the sorting of the decorrelated syndrome sets S.sup.i, a simple but effective approach can be chosen. Instead of decorrelating every value, only syndromes using the most reliable element (LLR=0) from the currently handled output edge i are considered. All or most other syndromes are not used for the current output V.sub.i. By this approach the order of the syndromes is not changed by the decorrelation step and it is sufficient to sort one set S instead of the d.sub.c sets S.sup.i. In addition, the LLR values are not modified in the decorrelation step which saves a real valued subtraction for every element in the output V.sub.i. Finally only the most reliable input element and not the complete input sets must or should be stored for the decorrelation.

(59) This simplified decorrelation allows also for the sorting step to be applied before the decorrelation step, as illustrated by FIGS. 6 and 7. It reduces the number of sorters from d.sub.c to 1. FIG. 6 shows a flow chart of this embodiment and FIG. 7 is an implementation of this embodiment.

(60) In FIG. 6, the sorting operation which was executed in the output generation step S3 in FIG. 2 is here operated before the decorrelation step S3. The sorting operation, referenced S10, is applied on the syndromes of the set S. In FIG. 7, the check node includes a syndrome calculator 200 for generating the set of syndromes S, a sorter 220 for sorting the syndromes of S according to their LLR values and d.sub.c decorrelators 210 for applying the decorrelation to the sorted sets S.

(61) FIG. 8 shows the schematic operations of one decorrelator of FIG. 7. In FIG. 8, each syndrome is denoted with an additional information SRC about which of the input edges contributed to the syndrome with a deviation. SRC in FIG. 8 stores the input edges where deviations occurred and ADDR.sub.i represents the current output edge. A simple comparison evaluates if a deviation from the current edge was involved in the syndrome calculation and thus if the syndrome is valid for the current edge or not. Only if no deviation occurred on the current edge, the decorrelated syndrome is marked as valid and used for the output V.sub.i.

(62) It has to be noted that the expression edge is used here interchangeably with the term input as each input corresponds to one edge in the Tanner graph.

(63) Even though the sorting has been reduced to the syndrome set S, there is more potential for simplification. Sorting S can be divided into sorting the deviation sets D.sub.i and merging them. Especially for D.sub.1 the sorting can be further simplified. This is achieved due to the previous knowledge we have of the input data. We implicitly know that the lists U.sub.i are sorted according to their LLRs. The sorting of D.sub.1 can thus be limited to merging d.sub.c sorted sets. For the higher-order deviations D.sub.i for i2, the sorting can also be simplified because of the sorted input lists. An example of the circuit for sorting the syndromes of D.sub.1 and D.sub.2, with d.sub.c=4, is shown in FIG. 9. The part P1 is used for sorting the syndromes of D.sub.2 and the part P2 is used for sorting the syndromes of D.sub.2 with d.sub.2=2.

(64) As can be seen from FIG. 9 and as mentioned, the sorting of the syndromes of D.sub.1 is simplified since the lists U.sub.i are already sorted according to their LLRs and the LLR of the syndrome is the LLR of the input element not having a LLR equal to zero.

(65) For the syndromes of D2 (part P2 of FIG. 9), sorted sub-lists have first to be generated by six circuits SC.sub.p generating subsets of ordered input elements, one circuit CS.sub.1 for generating a sorted sub-list of the input elements U.sub.i[1], U.sub.1[2], U.sub.2[1] and U.sub.2[2], one circuit CS.sub.2 for generating a sorted sub-list of the input elements U.sub.1[1], U.sub.1[2], U.sub.3[1] and U.sub.3[2], one circuit CS.sub.3 for generating a sorted sub-list of the input elements U.sub.1[1], U.sub.1[2], U.sub.4[1] and U.sub.4[2], one circuit CS.sub.4 for generating a sorted sub-list of the input elements U.sub.2[1], U.sub.2[2], U.sub.3[1] and U.sub.3[2], one circuit CS.sub.5 for generating a sorted sub-list of the input elements U.sub.2[1], U.sub.2[2], U.sub.4[1] and U.sub.4[2], and one circuit CS.sub.6 for generating a sorted sub-list of the input elements U.sub.3[1], U.sub.3[2], U.sub.4[1] and U.sub.4[2].

(66) FIG. 10 shows the circuit CS.sub.1 used for generating the sorted sub-list of the input elements U.sub.1[1], U.sub.1[2], U.sub.2[1] and U.sub.2[2]. The circuit of FIG. 10 can be extended easily to other deviations and reliability distances. Once the sub-lists are sorted, the outputs can be generated by merging them sequentially as shown in FIG. 9.

(67) In view of the above specification, three notable benefits arise from the method according to some embodiments Significant reduction of |S|. No LLR subtractions and no storage for Ui in the decorrelation step.

(68) The method of some embodiments can further be simplified. Considering the NB-LDPC decoder as a whole, it can be observed, that an exact sorting of the check node outputs may not be required. When a variable node has calculated the a posteriori probability (APP) messages as the sum of the channel values and messages from the check nodes, they have to be resorted anyway. Thus an approximately sorted check node output is sufficient and does not impair the decoder's communications performance. Therefore, it is proposed hereinafter a new method which uses the robustness against approximately sorted check node outputs to further reduce the algorithms complexity.

(69) To allow for this approximate sorting, so called probes are chosen among the elements of the input lists U.sub.i and sorted according to their LLR. The LLR of each probe is considered as representative of the LLRs of the group of p neighboring elements including the probe. FIG. 11 shows the distribution of probes within the input list U.sub.1 used for D.sub.1. In this example, the probes are equally distributed in the input lists which work well for the investigated configuration. The considered probes are the elements indexed 1, 4, 7 and 10. However, for other parameters of d.sub.c and n.sub.m other distributions can be used.

(70) In this figure, the probe is the input element having the lowest reliability value in the group of p neighboring input elements including the probe and the reliability value of the probe is the lowest reliability value of the elements of this group. In the example of FIG. 11, the LLR value of probe 1 (=U.sub.1[3]) is considered as representative of the LLR values of all or most of the elements of the group probe1_group which includes the elements U.sub.1[1], U.sub.1[2] and U.sub.1[3]. Of course, the LLR value of the probe can also be a combination of the LLR values of the elements of the group, for example the average value of the LLR values of the elements of the group.

(71) In this embodiment, once the probes are selected, they are evaluated in order to select a reduced number of sorted probes, and then syndromes in the set S (which is for example D.sub.0D.sub.1D.sub.2 with d.sub.2=2) are selected based on these sorted probes, the selected syndromes being sorted in the order of the sorted probes.

(72) The flow chart of such an embodiment is illustrated by FIG. 12. The method includes the following steps: Step S200: preselecting probes in the input lists U.sub.i as described before; this preselection can be a predefined one as described in FIG. 11; in this figure, the elements U.sub.i[j] with i=1;2;3;4 and j=3;6;9;12 are preselected; so 16 probes are preselected; Step S210: calculating syndromes in order to generate the set of syndromes S; Step S220: evaluating the preselected probes in order to select and sort a reduced predetermined number of the preselected probes, the probes, called final probes, being sorted according to the reliability values; the step S220 can be carried out before or after or in parallel with the step S210; Step S230: selecting syndromes from the set S based on the final probes; the selected syndromes are sorted in the order of the final probes; and Step S240: applying a decorrelation to the sorted syndromes in order to generate the output lists V.sub.i.

(73) This scheme leads to some uncertainty in the set of syndromes issued from the step S230 but is close enough to the exact solution not to degrade the decoders communications performance.

(74) FIG. 13 shows the LLR values of the approximately sorted syndromes used for the CN output calculation. The approximation works well for low LLRs (high reliability) and only for the less reliable outputs there is a difference compared to the optimal sorting results.

(75) In the following, a hardware implementation of the inventive solution with use of probes is given. The architecture is independent of the actual used NB-LDPC code, only the parameters d.sub.c=4, q=64 and n.sub.m=13 are given.

(76) FIG. 14 shows an overview of the check node hardware. To achieve low latency and high throughput, the input parallelism of the check node is chosen to be six GF(q), LLR tuples and an additional GF(q) input for the most reliable element (LLR=0). All or most input elements U.sub.i[j] can thus be read within two clock cycles. The evaluation of the probes can be processed in parallel with the actual calculation of the syndrome set S. In this example, the syndrome set S is reduced to D.sub.0D.sub.1D.sub.2 with d.sub.2=2. D.sub.0 includes 1 syndrome, D.sub.1 includes 48 syndromes and D.sub.2 includes 24 syndromes.

(77) The check node includes a probe evaluator PE1 for determining a reduced number of probes used for selecting syndromes of D.sub.1, a probe evaluator PE2 for determining a reduced number of probes used for selecting syndromes of D.sub.2, a syndrome calculator SC for calculating the syndromes of D.sub.0, D.sub.1 and D.sub.2, a syndrome selector SS1 for selecting, among the syndromes of D.sub.1 generated by the syndrome calculator SC, 6 syndromes; a syndrome selector SS2 for selecting, among the syndromes of D.sub.2 generated by the syndrome calculator SC, 3 syndromes; and d.sub.c decorrelators receiving the syndrome of D.sub.0 and the syndromes of D.sub.1 and D.sub.2 selected by the syndrome selectors SS1 and SS2.

(78) In this embodiment, once S=D.sub.0D.sub.1D.sub.2 is calculated and the probes are sorted, the most reliable subsets selected by the syndrome selectors SS1 and SS2 are used for the decorrelation. The parallelism with which the syndromes are processed has significant impact on the overall throughput. It has been chosen to be three times three syndromes. In each clock cycle two sets of neighboring syndromes from D.sub.1 and one set from D.sub.2, overall nine syndromes are processed. Thus, after a maximum of four clock cycles all or most output edges are filled with n.sub.m valid messages. The output parallelism of the CN is chosen symmetrically to the inputs to be six GF(q), LLR tuples and one GF(q) message for D.sub.0.

(79) An example of the probe evaluator PE1 is illustrated by FIG. 15. This probe evaluator processes two probes per input edge in each clock cycle. For d.sub.c=4 overall eight LLRs have to be sorted, which is performed by a latency optimized sorting network. As each two probes are implicitly sorted already because they belong to the same input list, some simplifications on the network can be applied.

(80) The probe evaluator PE1 receives the probes U.sub.1[1], U.sub.1[4], U.sub.2[1], U.sub.2[4], U.sub.3[1], U.sub.3[4], U.sub.4[1], U.sub.4[4] in a first cycle and the probes U.sub.1[7], U.sub.1[10], U.sub.2[7], U.sub.2[10], U.sub.3[7], U.sub.3[10], U.sub.4[7], U.sub.4[10] in a second cycle. These probes are processed by a sorting network. The result of the sorting is not a sorted list of LLRs but rather the positions of the inputs where they come from. They are stored in a register and the same task is performed a second time for the second half of the input LLRs in the next clock cycle. Starting from the second clock cycle, every following clock cycle the positions of the two smallest probes are output. To perform this task, an additional sorter, selecting the two smallest probes from the registers is utilized. Once a probe is used for an output generation, it is removed by shifting the register content accordingly. The probe evaluator PE2 for D.sub.2 is a simplified version of the one for D.sub.1 as it considers only four inputs. Moreover it needs to generate only one output per clock cycle. The output of the probe evaluators is used as control signal for the syndrome selector components.

(81) FIG. 16 depicts partially an example of the syndrome calculator SC. The syndrome calculation is carried out fully parallel. Due to the restrictions on the deviation reliability distances (d.sub.0=0, d.sub.1=n.sub.m1, d.sub.2=2), the required hardware is strictly limited. A sophisticated scheme for the calculation allows for further reduced hardware cost. Instead of calculating each syndrome as a sum of d.sub.c inputs, intermediate results are used to minimize the number of explicit calculations. The calculation of D.sub.0 involves d.sub.c1 GF(q) additions, for D.sub.1 overall d.sub.c.Math.n.sub.m GF(q) additions may be required. Thus for D.sub.0 and D.sub.1 only GF(q) calculations may be required. For D.sub.2 the processing scheme of D.sub.1 can easily be extended and may require only one real valued addition per syndrome in addition to the GF(q) operations. Compared with state-of-the-art processing, there is a significant saving in computational complexity. The output of the syndrome calculator is a number of sorted subsets used as input for the syndrome selectors.

(82) FIG. 17 depicts partially an example of the syndrome selector SS1 for D.sub.1. The syndrome selector receives the addresses of the most reliable syndrome sets from the probe evaluator PE1 and the syndromes D.sub.i sorted in sub-sets from the syndrome calculator. The complete hardware can include or can consist of a multiplexer tree choosing a set of the three most reliable syndromes from the subsets. To achieve six messages from D.sub.1, the multiplexer tree of FIG. 17 is to be duplicated in this unit. For D.sub.2 a single tree choosing between the six sub-sets of D.sub.2 suffices.

(83) The decorrelation has to be performed individually for each output edge of the check node. The output parallelism of the decorrelator is six messages per clock cycle. Two times three syndromes from D.sub.1 and another three from D.sub.2 are processed per clock cycle. By construction the messages of a set usually have deviations on the same edges. Thus it is sufficient to check for one of the messages in a set if it is valid or not, which is indicated with a valid flag. If only a part of the received sets is valid, they are rearranged by multiplexers in such a way, that only valid messages are used for the output. In the best or better case all or most syndromes received in one clock cycles are valid. As the output parallelism is only six, the surplus syndromes are stored in an additional register and reused in the next clock cycle. Before the messages are sent to the variable node, the actual decorrelation is applied which is a subtraction of the most reliable GF(q) value of the current input edge.

(84) In the hardware implementation of FIG. 14, all or most of the syndromes of D.sub.1 and D.sub.2 are generated by the syndrome calculator SC and only nine of them are selected by the syndrome selectors SS1 and SS2.

(85) In a variant illustrated by FIG. 18 and FIG. 19, it is proposed to only generate the syndromes that will be decorrelated. In this variant, the control signals ctrl generated by the probe evaluators are transmitted to the syndrome calculator SC such that the latter one only generates the syndrome of D.sub.0 and the nine syndromes of D.sub.1 and D.sub.2 to be decorrelated. The syndrome selectors SS1 and SS2 are removed.

(86) The method executed by the check node in this variant can be summarized the following steps depicted in FIG. 19: Step S300: preselecting probes in the input lists U.sub.i as described before, Step S310: evaluating the probes in order to select and sort a predetermined number of the preselected probes, called final probes, the probes being sorted according to the reliability values; Step S320: calculating a reduced number of syndromes based on the final probes; and Step S340: applying a decorrelation to the sorted syndromes in order to generate the output lists V.sub.i.