METHOD FOR DECODING NON-BINARY CODES AND CORRESPONDING DECODING APPARATUS

• US 20170012642A1
• Filed: 02/03/2015
• Published: 01/12/2017
• Est. Priority Date: 02/03/2014
• Status: Abandoned Application

• Current Assignee: Centre National De La Recherche Scientifique, Universite Cergy-Pontoise (CY Cergy Paris Université), Universidad Politecnica De Cataluna
• Original Assignee: Centre National De La Recherche Scientifique, Universite Cergy-Pontoise (CY Cergy Paris Université), Universidad Politecnica De Cataluna
• Inventors: Garcia Herrero, Francisco Miguel, Valls Coquillat, Javier, Declercq, David, Li, Erbao
• Application Number:
  US15/116,291
• Publication Number:
  US 20170012642A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H03M 13/1108 Hard decision decoding, e.g. bit flipping, modified or weighted bit flipping
• CPC Class Codes: H03M 13/1171 Parity-check or generator matrices with non-binary elements, e.g. for non-binary LDPC codes

Abstract

An extension to the enhanced serial generalized bit-flipping decoding algorithm (ES-GBFDA) of non-binary LDPC codes by introducing soft information in the check node operation. The application not only considers the most reliable symbol in the syndrome computation, but also takes at least the second most reliable symbol of each incoming message into account. An extended information set is available for the parity-check node update and this allows introducing the concept of weak and strong votes performed by the check node unit. Each variable node can receive two kinds of votes, whose amplitudes can be tuned to the reliability of the syndrome that produces the vote.

Claims

1. A method for decoding a non-binary low density parity-check (NB-LDPC) code defined in a finite field of size q, which is a symbol flipping decoding method using multiple votes performed by the check node unit and transferred to the variable node unit,

the code can be displayed in a bipartite graph comprising at least one variable node V_n, n=0, . . . , N−

1 and at least one check node C_m, m=0, . . . , M−

1, said method comprising for each iteration j of I_t decoding iterations, the steps consisting in that;

each variable node V_n, connected to a check node C_m, is configured for determining (A1.1, A1.2) a most reliable symbol Q_n^1(j) and at least one symbol which is at least a p^th most reliable symbol Q_n^p(j), with p≧

2 for obtaining a vector of d_c most reliable symbols;

each check node C_m is configured for determining;

(A3.1) a first symbol to be voted R_n^0(j)=R_n^(j) based on the vector of d_c most reliable symbols passed by the variable nodes connected to him in the bipartite graph;

(A3.2) a list of i=1, . . . , L second symbols to be voted R_n^i(j) based on a list of L+1 test vectors defined as a combination of d_c symbols with a restriction according to which at most η

of these d_c symbols are a p^th most reliable symbol Q_n^p(j) with p≧

2, and at least d_c−

η

of these d_c symbols are a most reliable symbol Q_n^1(j).

2. The method according to claim 1, wherein each variable node is configured for determining (A1.1, A1.2) the most reliable symbols Q_n^(j) and the second most reliable symbol Q_n^2(j)=Q′

_n^(j) and their corresponding extrinsic reliability Δ

W_n^(j), Δ

W′

_n^(j) so that at a check node (A2.1, A2.2) the list of L+1 test vectors are built by replacing symbol Q_n^(j) by the second most reliable symbol Q′

_n^(j) in at most η

≦

L locations were the differences between Δ

W_n^(j) and Δ

W′

_n^(j) are the smallest.

3. The method according to the preceding claim, wherein η

≦

L, the method comprising a step consisting in that a sorter unit is configured for sorting (A1.3) the differences of extrinsic reliability Δ

W_nm^(j)−

Δ

W_nm^2(j) from the highest value to the lowest value for obtaining a sequence ′

of L sorted indices n, the sequence ′

comprising the η

locations where Q_n^(j) is replaced by Q_n^2(j) in the L+1 test vectors.

4. The method according to claims 1 to 3, wherein each variable node is further configured for computing (A4.1, A4.2) an intrinsic information W_mn^(j) from check node counting the votes of R_n^0(j) and of R_n^i(j) with the respectively amplitude voting v₀, v₂.

5. The method according to claims 1 to 4, comprising before the I_t decoding iterations an initialization step (Initialization) comprising the sub-steps of:

determining a LLR vector L_n=(L_n[0], L_n[1], . . . , L_n[q−

1]) of a n^th symbol in a sequence of N non-binary noisy symbols;

initializing a vector of APP vectors W_n⁽⁰⁾ to the LLR vector L_n and initializing a matrix W_mn⁽⁰⁾ to an all-zero matrix, said matrix W_mn^(j) being the intrinsic information from the check node m.

6. The method according to the preceding claim, wherein each variable node taking as input the LLR vector and the vector W_mn^(j) combines (A4.1, A4.2) the previous vector W_mn^(j−

1), the voting symbols R_n^0(j) and of R′

_n^(j) and the voting amplitudes v₀, v₁ through a function F₁ for obtaining the vector defined as the intrinsic information W_mn^(j).

7. The method according to the preceding claim, wherein the function F₁ is a simple summation of the values of the previous vector W_mn^(j−

1) at indices indicated by the voting symbols R_n^0(j) and of R_n^i(j) and the voting amplitudes v₀, v₁.

8. The method according to claim 5, wherein each variable node taking as input the LLR vector and the vector W_n^(j) combines (A5.1, A5.2) the previous vector W_n^(j−

1)W_mn<sup>(j−

1)</sup>, the voting symbols R_n^0(j) and of R_n^i(j) and the voting amplitudes v₀, v₁ through a function F₂ for obtaining the vector W_n^(j).

9. The method according to the preceding claim, wherein the function F₂ is a simple summation of the values of the previous vector W_n^(j−

1) at indices indicated by the voting) symbols R_n^0(j) and of R_n^i(j) and the voting amplitudes v₀, v₁.

10. A decoding apparatus comprising at least one variable node V_n and a at least one check node C_m, said decoder being configured for implementing a method for decoding a non-binary low density parity-check (NB-LDPC) code defined in a finite field of size q, according to one of the preceding claims.

11. A decoding apparatus according to the preceding claim, said apparatus being configured for implementing check node operations by means of L processing units configured dynamically to compute R_n^i(j), with i=1, . . . , L, each one of the L processing units share 3×

d_c inputs that correspond to the symbols Q_n^1(j),Q_n^2(j) and to the coefficients of the code, said inputs of each processing unit are combined by means of 2×

d_c GF multipliers and 2×

d_c GF adders, said processing units including all the logic necessary to compute L different syndromes as an intermediate step and a variable number of pipeline stages that may vary from 0 to log 2(d_c)+2 depending on the speed of said processing unit.

12. A decoding apparatus according to the preceding claim, said apparatus being configured for implementing the method of claims 6, 7, 8 and 9 and comprising:

i) a bank of memories that store R_n^i(j), with i=0, . . . , L symbols, ii) q processors with a logic required to compare the symbols R_n^i(j), with i=0, . . . , L, with the q elements of the Galois Field and determine the amplitude of the votes corresponding to that symbols; and

iii) q cells that implement functions F₁ and F₂, the bank of memories being implemented with L RAM memories or a bank of L registers., the processors being implemented with L-XNOR gates of log 2(q) bits and L-OR gates of 1 bit to compare the input symbols, i.e., symbols R_n^i(j), with i=0, . . . , L−

1, with the q Galois Field elements and determine the amplitude of the votes, the cells including a logic necessary for implementing F₁ and F₂ and the storage resources for W_mn^(j) and W_n^(j).

13. A decoding apparatus according to claim 11, said apparatus comprising a sorter unit configured for obtaining the sequence ′

of L sorted indices n according to the method defined in claim 3, the sorter unit including at least one sub-processors of radix L, each sub-processor including;

i) one stage of comparators configured for performing all the possible combinations of the inputs;

ii) a plurality of adders and a plurality of NOT gates configured for computing a summation of the output signals of the different comparators associated to the same input, the adders being configured for checking how many times a condition of greater than or less than is satisfied for each one of the inputs;

iv) a plurality of logic gates configured for implementing a L different masks that allows ordering the inputs according to the information provided by the outputs of the adders, logic gates are XNOR, OR and AND gates.