Optimization of Non Binary Parity Check Coefficients

Emmanuel Boutillon, Senior Member, IEEE Lab-STICC, UMR 6582 CNRS, Université de Bretagne Sud, 56100 Lorient, France email: emmanuel.boutillon@univ-ubs.fr Mackay and Neal in 1996 as a generalization of the LDPC matrices [START_REF] Mackay | Near Shannon limit performance of low density parity check codes[END_REF]. In [START_REF] Poulliat | Design of regular (2,dc)ldpc codes over GF(q) using their binary images[END_REF], Poulliat et al. present in 2008 a method to set the non-zero coefficients of a non binary parity check matrix H. The first step of the method concerns the problem of row optimization, i.e, the selection of the coefficients associated to a given parity check. The principle is to optimize the Hamming weight spectrum of the binary code (md c , m(d c -1)) associated to a parity check of degree d c over a Galois Field GF(q) with m = log 2 (q). The authors show that the higher the minimum distance of the binary equivalent code, the better is the convergence of the NB-LDPC code in the waterfall region. They also show that, for two parity checks with the same associated binary minimum distance d H , the multiplicity of binary codewords of Hamming distance d H verifying the parity check equation should be minimized. Once the coefficients of the parity check equation are selected, the second step of [START_REF] Poulliat | Design of regular (2,dc)ldpc codes over GF(q) using their binary images[END_REF] is to enumerate the cycles of short lengths in the Tanner graph associated to the parity check matrix and to constraint the GF(q) coefficients associated to each cycle so that only the zero codeword is associated to the short length cycles. This second step is out of the scope of this paper. The state of the art on coefficients selection is quite sparse, except in [START_REF] Mackay | Optimizing Sparse Graph codes over GF(q)[END_REF] and [START_REF] Dolecek | Non-Binary Protograph-Based LDPC Codes: Enumerators, Analysis, and Designs[END_REF]. In [START_REF] Mackay | Optimizing Sparse Graph codes over GF(q)[END_REF], Mackay proposed to select the set of non null coefficients that maximizes the marginal entropy of one element of the syndrome vector. In [START_REF] Dolecek | Non-Binary Protograph-Based LDPC Codes: Enumerators, Analysis, and Designs[END_REF], a method used to construct the NB-LDPC code used by the Consultative Committee for Space Data Systems (CCSDS) are presented and some sets of coefficients for d c = 4 over GF(64) and GF(256) are given. We should also mention the paper of [START_REF] Brouwer | An updated table of minimum-distance bounds for binary linear codes[END_REF] which shows minimum Hamming distance upper bound of short length binary codes.

A direct exploration of all possible codewords associated to a given set of coefficients is limited to small check node degree and Galois Field order due to the exponential increase of complexity. In fact, the number of codewords for a parity check of degree d c over GF(q) is q dc-1 . For example, for d c = 5 over GF(64), there is 64 4 = 16.8 × 10 6 codewords per set of coefficients. The number of sets of coefficients is around 8 × 10 4 (see section III): the direct method shows rapidly its limit since it requires more that 100 billions of operations. In [START_REF] Poulliat | Design of regular (2,dc)ldpc codes over GF(q) using their binary images[END_REF], optimal, or almost optimal, sets of coefficients are only given for d c = 4 over GF(64), GF(128) and GF(256).

In this paper, we revisit the problem of coefficient optimization in the case where the binary hamming weight associated to the parity check is strictly greater than 2. We propose a method with a complexity of O(d 2 c ) to evaluate the number of codewords of weight 3. When the number of sets of coefficients is too high for an exhaustive search, a local greedy search is performed. Explicit tables of coefficients are given for d c varying from 3 to 20 and for Galois Field GF(64) up to GF(1024). The proposed sets of coefficients can effectively replace the random selection of coefficients often used in NB-LDPC construction. For example, let us consider a check node of degree 12 over GF(256), then, in average, randomly selected set of coefficients leads to 68 codewords of weight 3 while the optimized set of coefficients has only 11 codewords of weight 3. In other words, using proposed coefficients, each parity check equation has a better individual error correction, leading globally to a better convergence in the waterfall of the whole NB-LDPC code.

The remainder of the paper is organized as follows. Section II presents the background on the parity check equation. Section III states the optimization problem and proposes an effective method to find optimal, or optimized, sets of coefficients. Finally, section IV concludes the paper. All the sets of optimal/optimized coefficients are given in the Appendix II.

II. FUNDAMENTAL PROPERTIES OF NB-PARITY CHECK

SPECTRUM

The Galois Field GF(2 m ) will be represented by the set of polynomials over GF(2) modulo P m [X], where P m [X] is an irreducible polynomial of degree m. Thus, by definition, GF(2 m ) = GF [START_REF] Poulliat | Design of regular (2,dc)ldpc codes over GF(q) using their binary images[END_REF][X]/P m [X]. It is usual to represent an element of this field either by setting X = α and representing the non null element as power of α, i.e, if x ∈ GF(q), then x = 0 implies that x can be written as x = α a , with a a natural that takes its value between 0 and q -2. It is also possible to represent an element of GF(q) by a binary vector of size m that represents the coefficients of a polynomial of GF [START_REF] Poulliat | Design of regular (2,dc)ldpc codes over GF(q) using their binary images[END_REF][X]/P m [X] over the base (1, α, . . . α m-1 ). In this paper, we use the following irreducible polynomials to construct the Galois Field of size 64 up to 1024.

           P 6 [X] = 1 + X + X 6 P 7 [X] = 1 + X 3 + X 7 P 8 [X] = 1 + X 2 + X 3 + X 4 + X 8 P 9 [X] = 1 + X 5 + X 9 P 10 [X] = 1 + X 4 + X 10 (1)
A parity check code C of degree d c over GF(q) dc is a code defined by a set of d c non-null GF(q) coefficients H = {h i } i=1,2,...dc , with h i = α ai . Vector X = (x 1 , x 2 , . . . , x dc ) of GF(q) dc belongs to the code C if and only if

h 1 x 1 + h 2 x 2 + . . . + h dc x dc = 0, (2)
where additions and multiplications are done in GF(q). Since addition in GF(q) is commutative, the order of the coefficients does not impact the properties of the code [START_REF] Poulliat | Design of regular (2,dc)ldpc codes over GF(q) using their binary images[END_REF]. Moreover, multiplying (2) by a constant factor does not change the equation [START_REF] Poulliat | Design of regular (2,dc)ldpc codes over GF(q) using their binary images[END_REF]. In other words, we can always select the coefficients of a parity check code C so that h i = α ai verifies h 1 = α 0 (or a 1 = 0) and i ≤ j ⇒ a i ≤ a j . In the sequel, this convention will be used by default. Since X ∈ C is a vector of GF (q) dc , it is possible to determine its binary image to define a binary code of length (md c , m(d c -1)). The Hamming weight spectrum S[X] of this code is defined as

S[X] = 1 + S 1 X + S 2 X 2 + S 3 X 3 + . . . + S mdc X mdc , (3)
where S n is the total number of codewords of Hamming weight n of the code. By convention, for a given set of coefficients H, S n (H) will denote the value of the n th coefficient of the Hamming weight spectrum of the code defined by the set of coefficients H. The computation of the spectrum can be performed with a complexity of q 2 (d c -1) + 2q using the recursive algorithm used to compute the spectrum distance of a convolutional code [START_REF] Rouanne | An algorithm for computing the distance spectrum of trellis codes[END_REF]. The adaptation of the algorithm is given in Algorithm 1. The partial spectrum S y (l)[X], with y ∈ GF(q), l = 0, 1, 2, . . . d c represents the spectrum of codewords (x 1 , x 2 , . . . x l ) of size l that verify

l i=1 h i x i = y. (4)
Note that when l = 0, we will assume that S y (0)[X] = 1 if y = 0 (empty set is a solution), 0 otherwise (there is no solution).

Moreover, it is possible to associate also a Hamming Spectrum S x [X] to an element of x ∈ GF(q). It is the monomial S x [X] = X W (x) where W (x) is the binary Hamming weight of x, i.e., the number of 1 in the polynomial representation of x.

Data:

Initial set of coefficients H Result: Spectrum S[X] S s (0)[X] = 1 if s = 0, 0 otherwise. for l = 1, . . . d c do for d ∈ GF(q) do S d (l)[X] = 0 end for s ∈ GF(q) do for x ∈ GF(q) do d = s + (h l x); S d (l)[X] += S s (l -1)[X]S x [X]; end end end S[X] = S 0 (d c )[X]
Algorithm 1: Computation of Hamming weight spectrum associated to a parity check code In an Additive White Gaussian Noise (AWGN) channel, it is well known that the performance is determined first by the Hamming distance of the code (the index d min of the smallest non null value of S[X], i.e. S dmin = 0 while 0 < i < d min ⇒ S i = 0) and second by the multiplicity of code word of minimum Hamming distance, i.e., the value S dmin .

Lemma 1: Let H be a set of d c non-null coefficients in GF(2 m ) dc , then S 1 (H) = 0.
(5)

Lemma 2: Let H be a set of d c non-null coefficients in GF(2 m ) dc , then S 2 (H) = dc-1 i=1 dc j=i+1 S 2 ({h i , h j }), (6)
where S 2 ({h i , h j }) denotes the number of codewords (x i , x j ) satisfying the reduced parity check equation x i h i + x j h j = 0 of Hamming weight two. Proof: If (x i , x j ) is a Hamming weight two solution of x i h i + x j h j = 0, then a vector X having 0 value in all positions, except X(i) = x i and X(j) = x j is also a Hamming weight two solution of (2). The total number of codewords of binary Hamming weight two is thus the summation of the number of codewords of binary Hamming weight two associated to each distinct couple of coefficients

Lemma 3: Let H be a set of d c non-null coefficients in GF(2 m ) dc , then S 3 (H) = S t 3 (H) -(d c -3)S c 3 (H) (7)
where the term S t 3 (H) indicates the summation of binary Hamming weight 3 associated to all possible triplets of nonnull coefficients, i.e.,

S t 3 (H) = 1≤i<j<k≤dc S 3 ({h i , h j , h k }), (8)
and the term S c 3 (H) indicates the summation of binary Hamming weight 3 associated to all possible couples of non-null coefficients, i.e.,

S c 3 (H) = 1≤a<b≤dc S 3 ({h a , h b }), (9)
Proof: Let us consider a triplet {h i , h j , h k } of coefficients of a parity check of degree 3. The set C(x i , x j , x k ) of Hamming weight 3 triplets

(x i , x j , x k ) verifying x i h i +x j h j + x k h k = 0 can be partitioned in four disjoint sets: C j,k i = (0, x j , x k ) xj =0,x k =0 , C i,k j = (x i , 0, x k ) xi =0,x k =0 , C i,j k = (x i , x j , 0) xi =0,xj =0 and C i,j,k = (x i , x j , x k ) xi =0,xj =0,x k =0 . One can note that the number of elements of C i,j k is in- dependent of k and is equal to |C i,j k | = S 3 ({h i , h j }). Thus S 3 ({h i , h j , h k }) = |C i,j,k | + S 3 (h i , h j ) + S 3 (h i , h k ) + S 3 (h i , h k ). According to (8), S t 3 is thus equal to S t 3 (H) = 1≤i<j<k≤dc |C i,j,k | + S 3 ({h i , h j }) +S 3 ({h i , h k }) + S 3 ({h j , h k }). (10)
A given couple {h a , h b } appears exactly (d c -2) times in (10). Thus, S t 3 (H) is equal to the number of Hamming weight 3 codeword with exactly 3 non-null GF(q) symbols plus (d c -2) times the number of Hamming weight 3 codeword with exactly 2 non-null GF(q) symbols, i.e, S c (H). Thus,

S t 3 (H) -(d c -2)S c 3 (H)
gives the number of Hamming weight 3 codewords with 3 non null GF(q) symbols, while S c 3 (H) gives the number of Hamming weight 3 codewords with exactly two non-null GF(q) symbols. Thus, adding those two terms gives S 3 (H), the total number of Hamming weight 3 codewords

Property 1 Let x = α a an element of GF(2 m ), then W (x) = 1 is equivalent to 0 ≤ a < m.
In others words, the binary representation of x contains exactly one non null value (the binary Hamming weight of x is equal to 1, or S x [X] = X 1 )" is equivalent to the property 0 ≤ a < m. For example, if GF(2 3 ) is defined by P 3 [X] = 1 + X + X 3 , then α 0 = (1, 0, 0), α 1 = (0, 1, 0), α 2 = (0, 0, 1) while

α 3 = (1, 1, 0). Theorem 1: Let H = {α ai } i=1,...,dc be a set of d c non null coefficients in GF(2 m ) dc , then, if m > 2, S 2 (H) = 0 is equivalent to ∀i, j ∈ {1, 2, . . . d c } 2 , i = j ⇒ |a j -a i | q-1 ≥ m, (11)
where |a| q-1 represents min(|a|, |q -1 -a|).

Proof: Let us first prove the equivalence for a check node of degree d c = 2 with the set of coefficients {h 1 , h 2 }, where h 1 = α a1 and h 2 = α a2 and a 2 ≥ a 1 . Since multiplying the coefficients of the check node by α -a1 does not change the code, h 1 can be set to h 1 = α 0 and h 2 can be set to α a ; with a = a 2a 1 . The q -1 non null solutions of the parity check equation are thus

(x b 1 = α b+a , x b 2 = α b ), b = 0, 1, . . . q -2. In fact, h 1 x b 1 + h 2 x b 2 = α 0 α b+a + α a α b = α a+b + α a+b = 0. For a given b, the Hamming weight of the codeword (x b 1 , x b 2 ) is equal to W (x b 1 ) + W (x b 2 ). According to property 1, we have W (x b 1 ) = 1 equivalent to 0 ≤ a + b mod q -1 < m or equivalently (0 ≤ b < m -a) or (q -1 -a ≤ b < q -1). (12) Similarly, W (x b 2 ) = 1 is equivalent to 0 ≤ b < m. (13)
Thus, according to lemma 1,

W (x b 1 ) + W (x b 2 ) = 2 ⇒ W (x b 1 ) = 1 and W (x b 2 ) = 1
, or equivalently, there exists a value of b that satisfies simultaneously (12) and ( 13). There is a solution if and only if

0 ≤ m -1 -a or q -1 -a ≤ m -1.
If m > 2, the second inequality is never fulfilled and the existence of solution is given by a

≤ m -1. Reciprocally, for m > 2, if a > m -1, then W (x b 1 ) + W (x b
2 ) is always strictly greater than 2. The general case can be proven by using lemma 2

Corollary: d c ≤ 2 m
m is a necessary and sufficient condition for the existence of a set H of m non-null coefficients of GF (q) so that S 2 (H) = 0.

Proof: H = {α 0 , α m , α 2m , ..., α (dc-1)m } verifies (11) if and only if

(d c -1)m ≤ q -m
The above properties are now used to find optimal (or optimized) sets of parity check equation coefficients.

III. SEARCH FOR OPTIMAL COEFFICIENTS

The objective of this paper is to find for several values of d c and Galois Field GF(q) the sets of coefficients that minimize S 3 (H) with S 2 (H) = 0. The design objective can be formalized as

H opt = arg min H∈GF(q) * dc {S 3 (H)|S 2 (H) = 0}, (14)
where GF(q) * is the set of non-null elements of GF(q). Moreover, in the case where S 3 (H opt ) = 0, the design objective is modified as

H opt = arg min H∈GF(q) * dc {S 4 (H)|(S 3 (H) = 0, S 2 (H) = 0)}. ( 15
)
This section is divided in 3 sub-sections. First, we explicitly describe how to compute efficiently S 3 (H) (or S 4 (H)) given the set H. Then, we determine ξ m (d c ), the number of sets H verifying S 2 (H) = 0 as a function of the degree d c of the parity check and the order q = 2 m of the Galois Field. Finally, when ξ m (d c ) is too high for an exhaustive search, we rather consider a heuristic search to find good sets of coefficients.

A. Determination of S 3 (H)

In the sequel, we propose an efficient method to compute the value of S 3 (H) for several sets of coefficients H. The first step is to compute tables T 2 and

T 3 . Table T 2 is a table of size (q -1) defined as T 2 (a) = S 3 ({α 0 , α a }) for a = 0, . . . q - 2). Table T 3 is a table of size (q -1) × (q -1) defined as T 3 (a, b) = S 3 ({α 0 , α a , α b }), (a, b) ∈ {0, 1, . . . , q -2} 2 .
For a given couple (a, b), the computation of T 3 (a, b) requires q 2 operations using algorithm 1. The determination of the whole table has thus a global complexity of q 4 . This complexity is high (10 12 for q = 1024) but since it is processed only once for all sets of coefficients H for a given Galois Field order q, it is still feasible.

Once tables T 2 and T 3 are generated, S 3 (H) is obtained thanks to the computation of S c 3 and S t 3 , as described in algorithm 2.

Data

= i + 1, . . . d c -2 do for k = j + 1, . . . d c -1 do S t 3 = S t 3 + T 3 (a j -a i , a k -a i ); end end end S 3 (H) = S t 3 -(d c -3)S c 3 Algorithm 2: Determination of S 3 (H)
To summarize, once tables T 2 and T 3 computed, the additional computational cost to determine S 3 (H) for a parity check node of degree d c is independent of the Galois Field order q and requires exactly C(d c ) = dc 2 + dc m . The enumeration of all sets of coefficients verifying S 2 (H) = 0 required to determine H opt can be performed thanks to algorithm 3. It is useful to compute the exact number of configurations to be tested in order to explore all possible sets of coefficients leading to S (H) = 0. Let us first introduce the set Γ m (p, n) defined as the set of p-tuplet of integers (a(1), a(2), . . . , a(p)) ∈ {0, 1, . . . n -1} p verifying the following constraint

Data: Parity check degree d c , m = log 2 (q) Result: H opt s opt 3 = +∞ ; s opt 4 = +∞ for a 1 = m, . . . , q -1 -m(d c -1) do for a 2 = a 1 + m, . . . , q -1 -m(d c -2) do . . . for a i = a i-1 + m, . . . , q -1 -m(d c -i) do . . . for a dc-1 = a dc-2 + m, . . . , q -1 -m do H = {α 0 ,
a(i + 1) -a(i) ≥ m, i = 1, 2, . . . , p -1 (16)
II gives a method inspired from the Pascal's Triangle [START_REF] Pascal | Traité du triangle arithmétique avec quelques autrez petits traitez sur la même matière[END_REF] to compute the cardinality γ m (p, n) of the set Γ m (p, n).

Let ξ m (d c ) be the number of sets of coefficients in a check node of degree d c over GF (2 m ) that verifies the condition of theorem 1 (i.e. that gives a minimum Hamming weight 3 for its equivalent binary code). The first coefficient can be always h 1 = α 0 , since the multiplication of all coefficients by the same constant value does not change the code [START_REF] Poulliat | Using binary images of non binary LDPC codes to improve overall performance[END_REF]. Once α 0 is selected, {α 1 , α 2 , . . . , α m-1 } and {α q-m , . . . , α q-3 , α q-2 } are removed in order to respect theorem 1, i.e., every pair of coefficients of the check node should have their logarithms separated by at least m modulo q -1. Thus, there are still p = d c -1 points to be placed among 2 m -1 -(2m -1) = 2 m -2m values (see Fig. 1.a), and thus

ξ m (d c ) = γ m (d c -1, 2 m -2m). (17)
For example, according to Table I, there is exactly ξ 5 (4) = γ 5 (3, 22) = 364, i.e., there is 364 sets of coefficients, with the first one equal to α 0 , that lead to a Hamming distance of 3 for a check node of degree 4 over GF(2 m = 32) (coefficients are supposed to be sorted in increasing order of their logarithm). It is thus easy to generate these 364 solutions in order to keep the ones leading to the minimum multiplicity of weight 3 codewords (i.e., the minimum of S 3 (H)). One should note that ξ m (d c ) is exactly the number of time that a set H is tested in algorithm 3. Fig. 2 shows the number of configurations ξ m (d c ) for m equal to 6 (GF(64)) to 10 (GF(1024)) and d c varying from 1 to 20. Note that ξ 8 (20) = 2.39×10 22 (not shown in Fig. 2), which is a far too high number for an exhaustive search. In this paper, the limit for an exhaustive exploration to determine H opt is set to configurations where ξ m (d c ) < 10 9 . When ξ m (d c ) ≥ 10 9 , a heuristic search should be used to find good sets of coefficients.

C. Heuristic search of coefficients

When the value of ξ m (d c ) is too high for an exhaustive exploration, a heuristic search should be used. In this paper, we propose a basic but effective method. It is based on a greedy search repeated several times, each attempt starting from an initial state taken randomly. Let N g be the number of attempt, H 0,k the k th random initial set of coefficients, H0,k = G(H 0,k ) the final state obtained when a greedy algorithm is applied on H 0,k . The optimized solution H f 3 is taken as

H f 3 = arg min{S 3 ( H0,k ), k = 1 . . . N g }. ( 18
)
Let us describe in more details the method to draw the H 0,k and the greedy algorithm.

1) Method to generate initial sets of coefficients: The generation of the initial set should be unbiased, i.e., any set of coefficients should have the same probability P = 1 ξm(dc) of being chosen. This requirement can be achieved by a step by step generation process. In the sequel, the index k is omitted for clarity.

The first element h 0 1 of H 0 is always h 0 1 = α 0 . Then, the smallest (in the sense of logarithm over GF(q)) next element is h 0 2 = α m (a 2 = m) according to theorem 1. In that case, there are still d c -2 coefficients to be drawn among 2 m -3m positions, as shown if Fig. 1.b. The number of elements is thus γ m (d c -2, 2 m -3m) possibilities. If the next chosen element is a 2 > m, as shown in 1.c, there is still d c -2 coefficients to be drawn among 2 m -a 2 -2m, and thus γ m (d c -2, 2 m -a 2 -2m) possibilities. In order to draw a set of coefficients randomly, we should have, for the second coefficient:

Prob(h 0 2 = α a2 ) = γ m (d c -2, 2 m -a 2 -2m) γ m (d c -1, 2 m -2m) . ( 19
)
One should note that the sum of the probability Prob(h 0 2 = α a2 ) for all values of a 2 is equal to 1 according to (29). For the third element (and the fourth up to the last one), the same method can be applied, leading to the general formula to generate the j th coefficients a j knowing that the previous coefficient is a j-1 , a j > a j-1 is given by

Prob(h 0 j = α aj /h 0 j-1 = α aj-1 ) = γ m (d c -j, 2 m -2m -a j ) γ m (d c -j + 1, 2 m -2m -a j-1 ) . ( 20
)
To conclude, the generation of uniformly distributed sets of coefficients reduces to a Markov process where probability of transition at a given stage is given by (20). Finally, the generation of an initial set of coefficients using random values can be enriched by a method proposed by one of the reviewers' paper. They suggested to insert a new coefficient in an already optimized set of coefficients of lower degree to create an a priori good seed value for the greedy optimization process. For high GF order (q = 512, 1024) and d c values, this method sometimes allows to reduce the value of S 3 by a few units.

2) Proposed greedy algorithm: The initial set of H coefficient is H = H 0 , then all possible values for the second coefficient h 2 verifying h 2 = α a2 , with m ≤ a 2 ≤ a 3m are tested. This limited search space guaranties that S 2 (H) = 0 (see Theorem 1). The value of a 2 that minimizes S 3 is selected to generate the new set of coefficients H. Then the same process is applied on the third coefficient (with

a 2 + m ≤ a 3 ≤ a 4 -m) up to the d th c coefficient.
The whole process is started again until no more improvement is obtained. The algorithm is given in details in algorithm 4. Note that when l = d c , l + 1 goes back to 1, and thus, a dc+1m = -m mod 2 m -1 = 2 mm. One should note that many more sophisticated and efficient algorithms can be imagined. Nevertheless, repeated many times from random initial states, the overall search method is effective. Fig. 3 shows the histogram of S 3 (H 0 ) obtained with N = 20, 000 draws as well as the best value found for d c = 6, 8, 10 and 12 over GF(256). In order to evaluate how far is the best found solution S f 3 compared to the average value of S 3 (H 0 ), we use the two following metrics

Data: Initial set of coefficients H 0 = {h i = α ai } i=1,...dc Result: Final set of coefficients H = G(H 0 ) H = H 0 s opt 3 = S 3 ( H); Improved = true; while Improved do Improved = false; for i = 1, . . . d c -1 do H = H; for b = a i-1 + m, ..., a i+1 -m do a i = b; (H = {α a0 , . . . , α ai-1 , α a b , α ai+1 , . . . , α a dc -1 }) Compute s 3 = S 3 (H) thanks to algorithm 2; if s 3 < s opt
∆ 3 = M 3 -S f 3 σ 3 (21) R 3 = S f 3 M 3 × 100 (in %) (22)
where M 3 and σ 3 are respectively the mean and the standard deviation of S 3 (H 0 ) for H 0 satisfying S 2 (H 0 ) = 0. The first metric ∆ 3 measures how far is the found value relatively to the "gaussian like shape" distribution of S 3 (H 0 ) while the second metric indicates the relative gain, in %, compared to the mean value M 3 . Fig. 4 and Fig. 5 show the evolution of ∆ 3 and M 3 for several values of d c and GF(q) order. Values of H f 3 , M 3 , σ 3 and the corresponding set of coefficients are given for GF(64) up to GF(1024) in Appendix II.

IV. CONCLUSION

In this paper, we have generalized the method proposed by Poulliat et al. for the determining the optimal Galois Field coefficients of a Non-Binary LDPC parity check code based on the binary image of the code. An algorithm with a complexity in O(d 3 c ) has been proposed to determine the number S 3 (H) of codewords of binary Hamming weight 3 of a parity check of degree d c over GF(q). The low computational complexity of the algorithm opens exploration to new regions of the design space, i.e. check node degree d c greater than 4 and high order Galois Field (up to GF(1024)) by an exhaustive search. A new greedy search algorithm has also been proposed to find good solutions when the number of sets of coefficients is too high for an exhaustive search. Tables of sets of coefficients are given for values of d c between 4 and 20 and GF(q) order varying from q = 64 to q = 1024. For each set of coefficients, the best found value S f 3 (H) is compared with the distribution of S 3 (H) obtained by taking randomly the coefficients of H. In some cases, S f 3 (H) can be at a distance to the mean value of S 3 (H) greater than 10 times the standard deviation of the distribution. The proposed sets of coefficients can effectively replace the random selection of coefficients often used in NB-LDPC construction over high order Galois Field, and thus helps the construction of new generations of NB-LDPC codes with better decoding performance.

ACKNOWLEDGMENT

The author would like to thank Cédric Marchand who pointed out some errors in the preliminary draft of the paper. He also thanks the reviewers who helped to improve the paper and suggested good ideas.

APPENDIX I

It is useful to compute the exact number of configurations to be tested in order to explore all possible sets of coefficients leading to S 2 (H) = 0. To do so, we use a method inspired from the Pascal' Triangle method [START_REF] Pascal | Traité du triangle arithmétique avec quelques autrez petits traitez sur la même matière[END_REF].

Let Γ m (p, n) be the set of p-tuplet of integer (a(1), a(2), . . . , a(p)) verifying the following two constraints

a(i) ∈ {0, 1, . . . n -1}, i = 1, 2, . . . , p (23)
and

a(i + 1) -a(i) ≥ m, i = 1, 2, . . . , p -1 (24)
The cardinality |Γ| of set Γ will be denoted as

General Case:

In the general case, Γ m (2, n) = Γ m (2, n - 1) ∪ {Γ m (1, n -m)||n -1} and thus γ m (2, n) = γ m (2, n -1) + γ m (1, n -m). (25)
In (25), we recognize the structure of the Pascal's triangle binomial construction, and thus

γ m (2, n) = 2 n -m + 1 = (n -m + 1)(n -m) 2 . (26)
In the general case, Γ m (p, n) and γ m (p, n) can be determined by a double recursive equation. First, let us assume that Γ m (p ′ , ′ ) are known for all couples (p ′ < p, n ′ ∈ N) and (p, n ′ < n). Then, Γ m (p, n) can be generated as

Γ m (p, n) = Γ m (p, n -1) ∪ {Γ m (p -1, n -m)||n -1}. (27)
This equality gives

γ m (p, n) = γ m (p, n -1) + γ m (p -1, n -m). ( 28
)
The derivation of the exact value of γ (p, n) is out of the scope of this paper. We can nevertheless derive from the recursion method that

γ (p, n) = n k=1 γ m (p -1, k -m). (29)
The important point is that the exact number of configurations can be, in practice, determined. As an example, Tab. I gives the first values of γ 5 (p, n) for p ≤ 5 and n ≤ 22

APPENDIX II

In this appendix, we give the results obtained by the proposed methods in order to help the construct optimal, or almost optimal, NB parity check codes. Remind that multiplying a set of coefficients by a constant factor does not change the code. For example H = {α 0 , α 9 , α 22 , α 37 } over GF(64) gives the same code as H ′ = Hα 54 = {α 54 , α 63 , α 76 , α 91 } = {α 54 , α 0 , α 13 , α 28 }. After reordering of the coefficients, H ′ is equal to H ′ = {α 0 , α 13 , α 28 , α 54 }. Since the parity check generated by H, H ′ = Hα 54 , H ′′ = Hα 41 and H ′′′ = Hα 26 are all equal, only the set of coefficients that minimizes the value of a 2 will be given to represent the equivalent set of coefficients through a multiplicative factor. When distinct optimal solutions exist for a given configuration of d c and GF(q), those solutions are enumerated.

Abstract-

  This paper generalizes the method proposed by Poulliat et al. for the determination of the optimal Galois Field coefficients of a Non-Binary LDPC parity check constraint based on the binary image of the code. Optimal, or almost-optimal, parity check coefficients are given for check degree varying from 4 to 20 and Galois Field varying from GF(64) up to GF(1024). For all given sets of coefficients, no codeword of Hamming weight two exists. A reduced complexity algorithm to compute the binary Hamming weight 3 of a parity check is proposed. When the number of sets of coefficients is too high for an exhaustive search and evaluation, a local greedy search is performed. Explicit tables of coefficients are given. The proposed sets of coefficients can effectively replace the random selection of coefficients often used in NB-LDPC construction. Index Terms-Non-Binary Parity Check, Non-Binary LDPC, Hamming Weight, Error control code . I. INTRODUCTION Non-Binary Low Density Parity Check Codes (NB-LDPC) have been proposed by

:

  Initial set of coefficients H = {α ai } i=0,...,dc-1 Result: S 3 (H) S c 3 = 0; S t 3 = 0 for i = 0, . . . d c -2 do for j = i + 1, . . . d c -1 do S c 3 = S c 3 + T 2 (a ja i ); end end for i = 0, . . . d c -3 do for j

3 = 1 6 (d c 3 -

 313 d c ) table accesses and add operations. This low complexity (for d c = 20, C(20) = 1330) permits to test rapidly a large number of potential sets of coefficients. B. Determination of H opt 3 Let us consider a check node of degree d c ≤ 2 m

Fig. 1 .

 1 Fig. 1. Illustration of the random coefficients selection process.

Fig. 2 .

 2 Fig. 2. Number ξ(dc, m) of sets of coefficients for dc ≤ 20 over GF(64) up to GF(1024)

4 :

 4 Greedy algorithm to compute H = G(H 0 ).

Fig. 3 .Fig. 4 .Fig. 5 .

 345 Fig. 3. Histogram of S 3 (H 0 ) and the best value S opt 3 over GF(256) for several values of check node degree dc

6 ( 2 , 8 ) is γ 6 ( 2 , 8 ) = 3 .p = 1 :Case p = 2 :

 628628312 γ = |Γ|.According to this definition, Γ 6[START_REF] Poulliat | Design of regular (2,dc)ldpc codes over GF(q) using their binary images[END_REF][START_REF] Poulliat | Using binary images of non binary LDPC codes to improve overall performance[END_REF] is equal to Γ 6 (2, 8) = {(0, 6), (0, 7), (1, 7)} and the cardinality of Γ Case When p = 1, then only constraint (23) can be applied and thusΓ m (1, n) = {0, 1, . . . , n} and γ m (1, n) = n. When p = 2, if n ≤ m, there is no solution, thus Γ m (2, n) = ∅ and γ m (2, n) = 0. If n = m + 1, there is a unique solution Γ m (2, m + 1) = {(0, m)} and thus γ m (2, m + 1) = 1. If n = m + 2,there are 3 possible solutions: Γ m (2, m + 1) = {(0, m), (0, m + 1), (1, m + 1)} and γ m (2, m + 1) = 3. If n = m + 3, there are 6 elements Γ m (2, m + 3). In fact, the elements of Γ m (2, m + 2) belongs also to Γ m (2, m + 3). The additional elements are the 3 couples (0, m + 2), (1, m + 2) and (2, m + 2). These 3 couples can be represented by {Γ m (1, nm) m + 2}, where {Γ||x} means the set obtained by concatenating x on the right to all elements of Γ. In other words, Γ m (2, m + 3) = Γ m (2, m + 2) ∪ {Γ m (1, nm)||m + 2}, and thus, γ m (2, m + 3) = γ m (2, m + 2) + γ m (1, nm).

  α a1 , . . . , α ai , . . . , α a dc -1 } Compute s 3 = S 3 (H) thanks to algorithm 2 if s 3 < s opt

	then H opt = H 3 s opt 3 = s 3 end
	if s 3 = 0 then
	Compute s 4 = S 4 (H) thanks to
	algorithm 1
	if s 4 < s opt 4 H opt = H; then s opt 4 = s 4 ; end
	end
	end
	end
	end
	end
	Algorithm 3: Determination of H opt

  This set of coefficients is also given in[START_REF] Mackay | Optimizing Sparse Graph codes over GF(q)[END_REF] and[START_REF] Poulliat | Using binary images of non binary LDPC codes to improve overall performance[END_REF] b This set of coefficients is also given in[START_REF] Mackay | Optimizing Sparse Graph codes over GF(q)[END_REF] TABLE II LIST OF OPTIMAL COEFFICIENT'S EXPONENTS {a i } i=1,...dc FOR GF(64). THE SYMBOL * INDICATES THAT THE VALUE OF S f 3 IS EQUAL TO S opt 3 . In[START_REF] Poulliat | Using binary images of non binary LDPC codes to improve overall performance[END_REF], the best given sets of coefficients have S 3 (H) = 5 TABLE III LIST OF OPTIMAL OR OPTIMIZED (Ng = 20,000) SETS OF COEFFICIENT'S EXPONENTS {a i } i=1,...dc FOR GF(128). THE SYMBOL * INDICATES THAT THE VALUE OF S f 3 IS EQUAL TO S opt 3 .

		value of n	n ≤ 5	6 7 8	9 10 11 12 13 14 15 16 17	18	19	20	21	22
		p = 1		n	6 7 8	9 10 11 12 13 14 15 16 17	18	19	20	21	22
		p = 2		0	1 3 6 10 15 21 28 36 45 55 66 78	91 105 120 136 153
		p = 3		0	0 0 0	0	0	1	4 10 20 35 56 84 120 165 220 286 364
		p = 4		0	0 0 0	0	0	0	0	0	0	0	1	5	15	35	70 126 210
		p = 5		0	0 0 0	0	0	0	0	0	0	0	0	0	0	0	0	1	6
											TABLE I
										VALUES OF γ 5 (p, n)
	dc	S f 3	S f 4		M 3	σ 3	∆ 3	R 3 (%) GF(64)
	3	0	68	12.0 3.1	3.9		0 % {0, 15, 41}
	4 a	* 20	206	31.5 3.3	3.5	63.4 % {0, 9, 22, 37}
	5 b	* 51	500	65.0 3.5	4.0	78.4 % {0, 7, 18, 44, 53}
	6	* 100 1020 115.9 3.6	4.4	86.3 % {0, 6, 13, 20, 46, 55}
	7	* 173 1890 187.9 3.1	4.8	92.1 % {0, 6, 13, 21, 28, 44, 54}
	8	* 276 3211 283.3 1.7	4.0	97.4 % {0, 6, 13, 21, 28, 36, 44, 54}
	9	* 402 5196 406.8 1.0	5.0	98.8 % {0, 6, 14, 21, 27, 35, 42, 48, 56}
	10 * 560 7995 560.9 0.2	4.1	99.8 % {0, 6, 12, 18, 24, 30, 37, 44, 50, 56}
	dc	S f 3	S f 4		M 3	σ 3		∆ 3	R 3 (%) GF(128),
	3	* 0	52		9.0	4.0		2.2		0 %	{0, 15, 53} ; {0, 15, 54}; {0, 73, 88} ; {0, 74, 89} ;
											{0, 38, 112} ; {0, 39, 112}
	4 a	* 4	244		23.3 5.7 3.39		17 % {0, 12, 84, 101}
	5	* 20	552		49.0 7.0 4.14		41 % {0, 11, 55, 84, 101}
	6	* 44	1111		87.8 8.1 5.41		50 % {0, 9, 21, 60, 94, 112}
	7	* 92	1985		143.0 8.7 5.86		64 % {0, 7, 24, 39, 48, 60, 99}
	8	* 157	3283		217.2 8.9 6.76		72 % {0, 7, 30, 37, 54, 69, 78, 90}
	9	* 252	5159		313.1 9.0 6.79		80 % {0, 7, 19, 30, 37, 54, 69, 78, 90}
	10	370	7739		433.4 8.4 7.55		85 % {0, 7, 38, 45, 59, 68, 75, 92, 107, 116}
	11	522 11206		581.4 7.7 7.71		90 % {0, 7, 22, 30, 37, 48, 55, 69, 78, 89, 96}
	12	709 15759		759.3 6.5 7.74		93 % {0, 7, 18, 25, 39, 48, 59, 66, 88, 97, 104, 119}
	13	928 21613		969.6 5.5 7.56		96 % {0, 7, 17, 24, 38, 48, 58, 65, 72, 87, 96, 103, 118}
	14	1182 29067 1215.6 4.2 8.00		97 %	{0, 7, 14, 29, 38, 45, 55, 62, 69, 76, 86, 93, 107, 116}
	15	1473 38349 1499.0 3.1 8.39		98 %	{0, 7, 18, 25, 32, 39, 47, 54, 61, 69, 78, 89, 96, 103, 118}
	16 * 1813 49714 1823.0 1.7 5.88		99 % {0, 7, 17, 24, 31, 38, 47, 54, 61, 68, 75, 82, 89, 96, 103, 118}
	17 * 2190 63526 2190.7 0.4 1.75		100 % {0, 7, 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98, 105,
											119}
	18 * 2604 80073 2604.0 0.0		0.0		100 %	{0, 7, 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98, 105,
											112, 119}

a a