1. Field of the disclosure

The field of the disclosure is that of decoding of error correction code.

In particular, the disclosure provides a new technique for decoding a codeword obtained by implementing a non-binary error correction code.

The invention finds applications for instance in the field of wireless (DAB, DVB-T, WLAN, unguided optics, etc.) or wired (xDSL, PLC, optics, etc.) communications and memory storage.

2. Background

The error correcting codes conventionally used in digital communication systems are binary. In other words, the information symbols at the input of the encoder, and the redundancy symbols obtained at the output of the encoder, are binary elements, belonging to the Galois field GF(2).

In some cases, error correcting codes can also be non-binary, i.e. defined on a Galois field with a cardinal q greater than 2, GF(q).

For example, Non-Binary Low-Density Parity Check (NB-LDPC) codes are an extension of the Binary LDPC codes that were proposed by R. Gallager in 1963. NB-LDPC are defined by a set of parity check equations on GF(q = 2 ^p ) with p > 1. NB-LDPC codes outperform LDPC codes when short frames are used, since they have higher coding gain and lower error floor.

Non binary codes also include code over a set S with a group structure, as proposed for example by B. Shams, D. Declercq and V. Heinrich in "Non-binary split LDPC codes defined over finite groups" (6th International Symposium on Wireless Communication Systems, Siena, Italy, 2009, pp. 493-497).

In the background section below, we focus on code over GF(q).

NB-LDPC code designed on GF(q) is a linear block code defined by a sparse parity check matrix H. It has a block length of N symbols (number of codeword symbols) and an information length of K symbols (number of information symbols) on GF(q) with a coding rate r = K/N. The number of redundant symbols added by the encoder is thus M = N - K.

The connections between the check nodes (CNs) and the variable nodes (VNs) are specified by the parity check matrix H which consists of N — K rows and N columns representing the total number of CNs and VNs respectively, where its element in row / and column j is denoted as H(i,j) = h _i,j

Figures 1A and IB illustrate an example of Tanner Graph representation of a NB-LDPC code with the corresponding parity check matrix H. Figure 1C illustrate the connection or edge between a variable node V J: and a check node C _i .

Let x = (x ₁ , x ₂ , ... , x _N ) be a codeword verifying Hx = 0 transmitted through a noisy channel.

For each transmitted GF symbol Xj, the receiver computes Ij, the Log-Likelihood Ratio (LLR) intrinsic vector defined as / _j (a) = log ( P(x _j = â)/P(x _j = a) ) ∈ G GF(q), with â = argmax{p(x _j = a)}. Note that by construction, / _j (â) = 0 and / _j (a) ≥ 0.

Let M _Vj 2c _i be a message sent from VN _j to CN _i . The message vector is permuted by h _i,j before being processed by the CN, and denoted as

The CN generates a message sent from Q to Vj. The message is inversely permuted and inputted to the VN as M

Lastly, the notations N (i) and M (j) represent the indices of the VN/CN connected to the i ^th / j ^th CN/VN respectively.

The horizontal layered decoding scheduling according to an example of decoding algorithm is presented in Annex 1.

In this example, the degree d _v of the variable node is assumed to be equal to 2. In the sequel, the check node index i of C _i is omitted, since using d _v = 2 suppresses the ambiguity on the check node index during the decoding process.

The decoding process starts with an initialization stage (line 3). Then, each decoding iteration is composed of the serial processing of the CN of the matrix (line 6). Each CN processing implies edge permutations and inverse edge permutations (lines 8 and 10). The CN processing (line 9) is presented by the Ф function that processes the d _c incoming M _{V j2c} , j ∈ N(i), messages, to generate d _c M _{C2V j} messages.

The function Ф could be any of the different algorithms used for CN processing. After the CN processing, all VNs connected to the CN (line 12) are updated (lines 13, 14, 15, and 16). The third stage is the decision stage (line 20) which computes the tentative codeword and checks if the decoded message is a codeword (all parity constraints are satisfied).

Decoding NB-LDPC is thus significantly more complex than decoding binary LDPC.

In order to reduce the complexity of the NB-LDPC decoding, different approaches and schemes has been proposed and implemented, mainly focused on Check Nodes complexity reduction.

For example, the Extended Min-Sum (EMS) introduced by D. Declercq and M. Fossorier in "Decoding Algorithms for Non-Binary LDPC Codes Over GF(q)" (IEEE Transactions on Communications, vol. 55, no. 4, pp. 633-643, 2007) truncates the message vector between the Variable Nodes and the Check Nodes from q down to n _m , where n _m « q, to reduce the computational load in the CN unit and hence reduces the hardware complexity.

Trellis Extended Min-Sum (T-EMS) decoders, described for example by E. Li, F. Garcia-Herrero, D.

Declercq, K. Gunnam, J. O. Lacruz, and J. Valls, in "Low Latency T-EMS Decoder for Non-Binary LDPC codes" (Asilomar Conference on Signals, Systems and Computers, 2013, pp. 831-835), are based on the trellis representation of the input messages which allows high parallelism between the CN and VN. In "Efficient T-EMS Based Decoding Algorithms for High-Order LDPC Codes" (IEEE Access, vol. 7 , pp. 50 980-50 992, 2019), J. Tian, S. Song, J. Lin, and Z. Wang present a threshold-based truncation decoding scheme (TS-TEC-TEMS) where two thresholds are used to truncate the incoming messages of the CN M _V2C and the outgoing messages from the CN to the VN M _C2v .

V. Savin also proposes a Min-Max decoding algorithm in "Min-Max decoding for non binary LDPC codes" (IEEE International Symposium on Information Theory, 2008, pp. 960- 964.

The function Ф used in the decoding algorithm illustrated in Annex 1 could be any of the different algorithms used for CN processing, such as the above-mentioned Min-Max, Extended Min- Sum or Trellis- EMS algorithm.

Although the above-mentioned algorithms allow reducing the complexity of the decoding, there is still a need for further reducing the decoding complexity, or for improving the performance of the decoder.

3. Summary of the invention

According to at least one embodiment, the disclosure thus provides a method for decoding a codeword, said codeword being obtained by implementing a code comprising at least one non-binary constraint node C over a set S' of cardinality q > 2 defined from a parity check matrix H _c of the non- binary constraint node C by the equation are a sub-set of non-binary variable nodes of the codeword implied in the non-binary constraint node C, with d _c > 2 the degree of connectivity of the non-binary constraint node C and p ₁₍ p ₂ , ... p _dc are permutations over the set S, wherein the decoding method implements, for at least one connection between the non-binary variable node V and the non-binary constraint node C, at least one decoding iteration comprising sending a message from the non-binary constraint node C to the non- binary variable node Vj, said message comprising: n _R measures of reliability obtained for n _R candidate symbols selected by the non-binary variable node Vj or by a first compression block implemented between the non-binary variable node Vj and the non- binary constraint node C, said n _R candidate symbols being denoted n _R requested symbols, n _B measures of reliability obtained for n _B candidate symbols selected by the non-binary constraint node C or by a second compression block implemented between the non-binary constraint node C and the non-binary variable node Vj, said n _B candidate symbols being denoted n _B best symbols, with

According to such embodiment, the message sent by the non-binary constraint node to the variable node comprises both measures of reliability obtained for the n _B best symbols, that are selected by the non-binary constraint node (where the non-binary constraint node can be for example a parity check node, or a sub-code, for example a convolutional code), and measures of reliability obtained for the n _R requested symbols, that are requested by the variable node.

The proposed algorithm is thus based on requesting measures of reliability associated with relevant symbols from the non-binary constraint node such that the measures of reliability associated with the requested symbols (for example LLR) can be concatenated with the measures of reliability associated with the n _B best symbols, and sent back to the variable node.

In this way, the proposed algorithm can reduce complexity of the non-binary error correction code by reducing the communication load between the variable nodes and the non-binary constraint nodes. It indeed allows a variable node to request the reliability associated with specific symbols to be included in the extrinsic message sent by the non-binary constraint node. It can be noted that the proposed algorithm is independent of the non-binary constraint node / variable node processing.

In particular, reducing the communication load can reduce at least one of the memory resources allocated for the messages exchanged between the variable nodes and the non-binary constraint nodes, the sorting process, the permutation / inverse permutation processes, and/or other hardware requirements.

According at least one embodiment, the proposed algorithm allows decreasing the size of the exchanged messages, which reduces the complexity and latency of the decoder, without significant performance degradation. In addition, decreasing the message size allows increasing the throughput in serial architectures and reduces the routing congestion in highly parallel architectures.

In particular, the requested candidates can enhance code convergence, with lower candidates propagating to/from a variable node, by increasing the probability that the symbol reliability of the j ^th transmitted symbol belongs effectively to the message sent from the non-binary constraint node C to the variable node Vj.

According to at least one embodiment, said n _R requested symbols are selected as the n _R most reliable symbols from at least one of: an intrinsic message obtained from the channel observation, an a posteriori probability message, a message from the variable node Vj to the non-binary constraint node C.

In this way, the variable node can request a new measure of reliability of a symbol (the reliability being determined by the non-binary constraint node) for a symbol which is for example already considered by the variable node as reliable. The proposed method can thus increase the convergence of the code by increasing the probability that the transmitted symbol belongs to the set of the most reliable candidates. In particular, one symbol of the n _R requested symbol can be obtained from the intrinsic message, another symbol can be obtained from the a posteriori probability message, yet another symbol can be obtained from the message from the variable node Vj to the non-binary constraint node, etc.

As an alternative, all the n _R requested symbols are obtained from the same message.

According to at least one embodiment, said n _B best symbols are selected as the n _B most reliable symbols from an extrinsic message issued by the non-binary constraint node.

It can be noted that some symbols can be both selected as requested symbols and best symbols.

According to at least one embodiment, said message sent from the non-binary constraint node C to the variable node Vj also comprises the n _B best symbols.

In this way, the message sent by the non-binary constraint node to the variable node comprises measures of reliability associated with the n _B best symbols, selected by the non-binary constraint node, measures of reliability associated with the n _R requested symbols, requested by the variable node, as well as the n _B best symbols. There is no need to send the n _R requested symbols to the variable node V _j , as they are already known by the variable node V _j .

According to at least one embodiment, said at least one decoding iteration further comprises transmitting a message from the variable node V _j to the non-binary constraint node C, comprising: generating a message M _{V .2C} comprising measures of reliability obtained for the q candidate symbols of the set S' (for example a Galois Field GF(q)), selecting from the message M _{V .2C} , by a first compression block candidate symbols (for example the most reliable) and generating a message comprising the n _vc symbols and the measures of reliability obtained for said n _vc symbols, selecting, by the first compression block Ω, the n _R requested symbols from the message M _{V .2C} , and sending a message to a second decompression block comprising the n _R requested symbols, permuting the n _vc symbols of the message Ω (M _v.2 c), delivering a message and the n _R requested symbols, delivering a message reconstructing, by a first decompression block a message comprising the n _vc symbols, the measures of reliability obtained for said n _vc symbols, remaining q — n _vc symbols, and measures of reliability set to a default value for the remaining q — n _vc symbols, transmitting to a second compression block T the message comprising the n _R requested symbols after permutation.

Such embodiment can be implemented when the compression / decompression of the message is not directly implemented by the variable node / non-binary constraint node. According to at least one embodiment, said message sent from the non-binary constraint node C to the variable node Vj is sent when the non-binary constraint node C has received messages from all the variable nodes connected to the non-binary constraint node C, and is obtained from: generating, from the received messages, k ≠ j, a message comprising measures of reliability obtained for the q candidate symbols of the set S, selecting from the message by the second compression block г, n _B best symbols (for example the most reliable) and generating a message comprising the n _B best symbols and the measures of reliability obtained for said n _B best symbols, obtaining, from the message M the measures of reliability of the n _R requested symbols after permutation received by the second compression block r in the message M generating a message г comprising the message and the measures of reliability of the n _R requested symbols after permutation, inversely permuting the n _B best symbols of the message delivering a message reconstructing, by the second decompression block a message comprising the n _B best symbols, the measures of reliability obtained for said n _B best symbols, the n _R requested symbols, the measures of reliability obtained for said n _R requested symbols, n _D remaining symbols and measures of reliability obtained for said n _D remaining symbols set to a default value S _D .

Such embodiment can be implemented when the compression / decompression of the message is not directly implemented by the non-binary constraint node / variable node.

In particular, the measure of reliability associated with at least one of said n _R requested symbols can be set to a default value S _R when said measure of reliability is above a threshold.

According to at least one embodiment, said at least one non-binary constraint node implements a decoding function belonging to the group comprising: a Min-Max function, an Extended MinSum (EMS) function, a Trellis-Extended MinSum (T-EMS) function, a threshold-based truncation decoding (TS-TEC-TEMS) function, a Belief Propagation (BP) function, a Fourier domain implementation of a BP function, such as for example disclosed in "Fast Decoding Algorithm for LDPC over GF(2q)", L. Barnault and D. Declercq (The Proc. 2003 Inform. Theory Workshop, Paris, France, pp. 70-73, Mar. 2003), a Forward/Backward function, etc. The proposed algorithm can thus be used with any of the different algorithms used for CN processing, such as those disclosed in the background section for example. In particular, it can be used with sub-optimal algorithm, such as the EMS, or with optimal algorithm, such as the BP.

Decoding functions such as those cited above can be used by a parity check node, when the code is for example a LDPC or a polar code.

Decoding functions such as BP, Fourier domain implementation of a BP, Forward/Backward can be used by a sub-code, when the code is for example a turbo-code.

It can also be used with any variable/non-binary constraint node degree of connectivity d _v and d _c respectively.

According to at least one embodiment, the code belongs to the group comprising: a LDPC code, a polar code, a turbo-code.

For example, the non-binary constraint node is a parity check node with a degree of connectivity d _v given as p1(V1) + p2(V2) + — +" P _dc (V _dc ) = 0 over the set S' when the code is a LDPC or a polar code, or a convolutional code when the code is a turbo code.

According to at least one embodiment, the message sent from the non-binary constraint node C to the variable node V _j comprises a default symbol reliability associated with n _D remaining symbols that do not belong to the set of n _B best symbols nor to the set of n _R requested symbols.

In this way, the message sent by the non-binary constraint node to the variable node comprises measures of reliability obtained for the n _B best symbols, which are selected by the non-binary constraint node, measures of reliability obtained for the n _R requested symbols, which are requested by the variable node, and measures of reliability obtained for the n _D remaining symbols, that can be set to a default value S _D . There is no need to send the n _D remaining symbols to the variable node V _j , as they can be deduced by the variable node V _j .

For example, the default value can be computed in the decompression block of the message sent from the non-binary constraint node to the variable node using the n _R measures of reliability and n _B measures of reliability.

In particular, at least one measure of reliability obtained for one of said n _R requested symbols and/or at least one measure of reliability obtained for one of said n _D remaining symbols can be set to a default value.

According to at least one embodiment, the message sent from the non-binary constraint node C to the variable node Vj comprises at most n _B + n _R + 1 measures of reliabilities.

The disclosure also relates to a corresponding device for decoding a codeword. Such a device for decoding a codeword is in particular adapted to implement the decoding method described above. It is, for example, a non-binary LDPC decoder, turbo-decoder, or polar code decoder. This device could of course include the various features relating to the decoding method according to the invention, which can be combined or taken in isolation. Thus, the features and advantages of this device are the same as those of the method described above. Therefore, they are not further detailed.

The invention also relates to one or more computer programs including instructions for the implementation of a method for decoding a codeword as described above when this or these programs are executed by at least one processor.

The invention also relates to an information medium readable by a computer, and including instructions of a computer program as mentioned above.

4. List of figures

Other features and advantages of the invention will emerge more clearly upon reading the following description of a particular embodiment, given by way of simple illustrative and non-limiting example, and the appended drawings, among which:

Figures 1A and IB illustrate an example of Tanner Graph representation of a NB-LDPC code;

Figure 1C illustrate the connection or edge between a variable node and a check node;

Figure 2A illustrates an example high-level block diagram of a non-binary error-correcting system, in accordance with at least one embodiment of the present disclosure;

Figure 2B illustrates the main step implemented by a method for decoding a codeword according to at least one embodiment;

Figures 3A and 3B illustrate an embodiment of the "BRD" algorithm according to the disclosure, where the compression / decompression functions are not implemented by the variable/check nodes;

Figure 4 gives an example of an Elementary Check Node architecture for the EMS-based BRD decoder;

Figure 5 illustrates how to find the requested symbols in a n _m x n _m matrix;

Figure 6 illustrates the probability P (x _j ∈ M _C2V ) that the transmitted symbol Xj belongs effectively to the message M _{C2V j} for different decoding algorithms;

Figure 7 shows the impact of the decoder parameters on the Frame Error Rate (FER) for different decoding algorithms;

Figure 8 shows simulation results for different sizes of code and for different decoding algorithms;

Figure 9 illustrates a non-binary turbo-code represented as a bipartite graph;

Figure 10 illustrates the kernel of a polar code; Figure 11 shows the simplified structure of a device for decoding a codeword according to one embodiment of the invention

5. Description of at least one embodiment

5.1 General principle

The disclosure is based on the idea of identifying at least one symbol, denoted as requested symbol, for which a variable node (VN) wishes to obtain a measure of reliability from a non-binary constraint node (CN).

The non-binary constraint node thus has a knowledge of the information requested by the variable node, and does not select "blindly" the symbols and associated measures of reliability that have to be sent to the variable node.

In other words, the requested symbols are the symbols sent by the VN to the CN such that their measures of reliability (LLRs for example) are obtained by the CN (using any CN processing algorithm) and sent to the VN.

Figure 2A illustrates a non-binary error-correcting system, in accordance with at least one embodiment of the present disclosure. As illustrated, a non-binary encoder 21 receives information symbols that represent data to be transmitted, and outputs codewords. Such codewords can be transmitted through a transmission channel and/or stored in a storage device for later use. Upon reception of a transmitted codeword, which can include errors, a non-binary decoder 22 can perform decoding operations to retrieve decoded symbols.

Figure 2B illustrates the main steps implemented by a method for decoding a codeword according to at least one embodiment. Such steps can be implemented by a non-binary decoder (for example the non-binary decoder 22) to improve decoding operations. Indeed, as explained below, the communication load between the variable nodes and the constraint nodes can be reduced through at least one embodiment of the disclosure, which helps, for example, reducing the decoding complexity, reducing the memory resources allocated for the exchange of messages between the variable nodes and the constraint nodes, reducing the sorting process complexity, reducing the permutation / inverse permutation processes complexity, etc).

We thus consider a codeword generated by a non-binary encoder (for example the non-binary encoder 21) from a non-binary error correction code comprising at least one non-binary constraint node C over a set S' of cardinality q > 2 defined from a parity check matrix H _c of the non-binary constraint node C by the equation = 0, where V _1, V ₂ , ... V _dc are a sub-set of non- binary variable nodes representing at least one symbol of the codeword implied in the non-binary constraint node C, with d _c > 2 the degree of connectivity of the non-binary constraint node C and P ₁ , p ₂ , ••• P _dc are permutations over the set S. Such codeword can be received, and then decoded, by the non-binary decoder 22.

For at least one connection between a non-binary variable node Vj from the set of variable nodes and the non-binary constraint node C said method implements at least one decoding iteration comprising sending (221) a message from the non-binary constraint node C to the variable node V _j , said message comprising: n _R measures of reliability obtained for n _R candidate symbols selected by the variable node V _j or by a first compression block implemented between the variable node Vj and the non-binary constraint node C, said n _R candidate symbols being denoted n _R requested symbols, n _B measures of reliability obtained for n _B candidate symbols selected by the non-binary constraint node C or by a second compression block implemented between the non-binary constraint node C and the variable node Vj, said n _B candidate symbols being denoted n _B best symbols, with

For example, the n _R requested symbols (for which a measure of reliability is requested by the variable node) are the n _R most reliable symbols among the q symbols of the set (for example GF(q)) of the variable node to the non-binary constraint node message M _V2C , since it achieved the best performance in terms of Frame Error Rate (FER). The requested symbols can, as an alternative, be obtained from the intrinsic information I _j (a) or the "a posteriori probability" APP _j [a],

The n _R requested symbols can thus be some of the n _R most reliable intrinsic symbols and/or some of the n _R most reliable symbols of the APP message and/or some of the n _R most reliable symbols of the message M _V2C .

Once the n _R requested symbols have been selected, the non-binary constraint node is informed and can determine the measures of reliability associated with said n _R requested symbols, using any techniques classically used for CN processing, such as those disclosed in the background section for example. For example, the measures of reliability are Log-Likelihood Ratio.

The variable node can thus obtain, from the non-binary constraint node, measures of reliability associated with said n _R requested symbols.

The non-binary constraint node can also select n _B best symbols of the set, for example the n _B most reliable symbols among the q symbols of the set, from the extrinsic information. The number of requested symbols n _R and of best symbols n _B is independent. As a consequence, the number of requested symbols n _R can be less than, greater than, or equal to the number of best symbols n _B . If a symbol appears twice, one as a requested symbol and one as a best symbol, the measure of reliability associated with this symbol can only be transmitted once to the variable node.

The variable node can thus obtain, from the non-binary constraint node, measures of reliability associated with said n _B best symbols. According to at least one embodiment, the message can also comprise at least one remaining symbol reliability obtained for the n _D remaining symbols that do not belong to the set of n _B best symbols nor to the set of n _R requested symbols.

A default value can be set to the measures of reliability associated with the remaining symbols.

For example, the default value can be determined by the non-binary constraint node and send explicitly within the message from the non-binary constraint node C to the variable node Vj. The default value can also be determined from the n _R measures of reliability and n _B measures of reliability. Other methods can be proposed to determine the default value.

The variable node can thus obtain information for all the q symbols of the set. For example, the set can be a Galois field GF(q).

The proposed algorithm can be called the Best, the Requested and the Default, or BRD algorithm.

At least one iteration of decoding can be implemented. At each iteration, the set of n _R requested symbols / n _B best symbols can be changed. The number n _R of requested symbols / n _B of best symbols can also change at each iteration.

5.2 Non-binary LDPC

We describe hereafter an example of a method for decoding a non-binary LDPC according to at least one embodiment. In this case, the non-binary constraint nodes are parity check nodes. However, as already mentioned, the disclosure is not limited to this kind of error correction code, and the proposed method can be implemented for the decoding of other error correction codes, such as turbo codes or polar codes for example.

In the example below, we also consider a non-binary error correction code designed on a Galois Field GF(q), with q > 2. However, the proposed method could also be extended from a NB-LDPC code on a Galois Field to any NB-LDPC code on a group, like the one proposed in the previously cited document "Non-binary split LDPC codes defined over finite groups".

The edge permutation can also be generalized from a permutation defined by a constant GF multiplication to any permutation.

As already mentioned, the proposed algorithm is a generic decoding algorithm used with any check node processing algorithm, such as for example the EMS algorithm, the T-EMS algorithm, the TS- TEC-TEMS algorithm, the Min-Max algorithm. It can also be used for any variable/check node degree of connectivity d _v and d _c respectively. The algorithm allows the variable node to request the reliability associated with specific symbols such that the symbols' reliability are sent back by the check node.

According to at least one embodiment, the measure of reliability of the requested symbols, for example LLR values, are concatenated with the most reliable extrinsic elements obtained at the check node and sent all together to the variable node. The M _C2V message can thus be considered as a union of three subsets: a first set which comprises n _B measures of reliability obtained for n _B candidate symbols, for example the n _B best candidates generated by the check node (the n _B candidate symbols being denoted best symbols). Such n _B best symbols and/or measures of reliability can be obtained, for example, using the classical EMS algorithm; a second set which comprises n _R measures of reliability obtained for n _R candidate symbols that are requested by the variable node (the n _R candidate symbols being denoted requested symbols); eventually a third set which comprises a measure of reliability associated with the remaining candidate symbols (i.e. the candidate symbols that are neither best symbols, nor requested symbols). The measure of reliability of the remaining symbols can be set to a default value S _D .

This concatenation contributes to increasing the probability of the correct symbol Xj being propagating from/to the CN, hence, increasing the decoding performance of the decoder.

In the sequel, an exponent A ⁺ indicates the LLR values, and indicates the values of the symbols (for example GF values) of the set A.

Figures 3A and 3B illustrate an embodiment of the BRD algorithm, where the compression / decompression functions are not implemented by the variable/check nodes. In other words, a message M _V2C output by the variable node is a vector of size q, and a message M _C2V output by the check node is a vector of size q.

Figure 3A shows the size of the messages in brackets, with the first element corresponding to the number of measures of reliability and the second element corresponding to the number of candidate symbols. Figure 3B shows an example on GF(8).

For a variable node V _j , the intrinsic message I _j comprises q values of LLR. In the example illustrated in Figure 3B, the intrinsic message I _j is given as I _j = [7,1,12,4,18,9,0,9],

In a first step, a message M _Vj2ci comprising measures of reliability associated with the q candidate symbols of GF(q) is generated. For the first iteration, the message M _Vj2ci is set to If. M _Vj2ci = I _j . The position of each LLR values gives implicitly the associated candidate symbol value.

A. Compression and Decompression of M _{V .2C} . message

A first compression block Ω generates a message from the message M _Vj2c , _i by selecting n _vc candidate symbols of GF(q). For example, the first compression block Ω selects the n _vc smallest LLRs and their associated GF value. The message thus comprises the n _vc symbols and the measures of reliability associated with said n _vc symbols. Since after normalization, the smallest LLR is always equal to 0, the message is composed of LLR and GF values, respectively.

In the example illustrated in Figure 3B, with n _vc = 3, the first compression block Ω extracts the three smallest LLR of the message M _{v .2ci} to generate the message comprising three pairs: After normalization, since the LLR of the first pair is always equal to 0, it could be omitted. The message thus contains two LLR and three GF symbols.

The first compression block Ω also selects n _R requested symbols, from the message M _{v j2Cl} , and sends a message to a second decompression block comprising the n _R requested symbols, for example the GF values of the first n _R pairs of the message

In the example illustrated in Figure 3B, with n _R = 2, the first compression block Ω extracts the two GF symbols of the most reliable candidates to generate the message comprising two GF symbols: (α ⁵ , α ⁰ ).

The n _vc symbols of the message and the n _R requested symbols are then permuted. For example, the edge multiplicative factor h _i,j is applied to each GF element of the message to generate a message and the edge multiplicative factor is applied to each

GF element of the message to generate a message

In the example illustrated in Figure 3B, with h _i,j = α ¹ , the GF values of the message are multiplied by h _i,j = α ¹ , generating a message The GF values of the message are also multiplied by h _i,j = α ¹ , generating a message

A first decompression block Ω ^-1 then decompresses the message back to a message of size q, by setting the n _vc GF values of with their corresponding LLRs and by setting a default value (for example a very high value, denoted infinity) to the remaining GF values. A message comprising the n _vc symbols, the measures of reliability associated with said n _vc symbols, remaining q — n _vc symbols, and measures of reliability set to a default value for the remaining q — n _vc symbols.

In the example illustrated in Figure 3B, the first decompression block Ω ^-1 generates the input check node by assigning the LLRs 0, 1 and 4 in positions α ⁶ , α ¹ , α ³ respectively, and infinite values otherwise.

Moreover, the first decompression block Ω ^{- 1} can also transmit to a second compression block г the message comprising the n _R requested symbols after permutation. It is for example composed of the n _R most reliable GF symbols in

In the example illustrated in Figure 3B, the first decompression block fl ^-1 transmit to the second compression block r the two requested symbols, in the message It could be noted that when the EMS algorithm is used for the check node processing, the first compression block Ω and the first decompression block Ωl ^-1 can be bypassed, since EMS, by construction, used truncated messages.

The proposed compression of exchange messages is however fully compatible with the EMS message representation.

B. Compression and Decompression of message

When the check node C _i has received messages from all the variable nodes connected to the check node C _i , the check node processes the using any processing algorithm, such as for example EMS or T-EMS.

The check node can thus generate, from the received messages, k ≠ j, a message comprising measures of reliability associated with the q candidate symbols of GF(q).

In the example illustrated in Figure 3B, the check node generates the message [12,9,4,2,4,10,0,8],

The message can be truncated by the second compression block г in two steps.

Firstly, the second compression block T selects, from the message best symbols of

GF(q) and generates a message comprising the n _B best symbols and the measures of reliability associated with said n _B best symbols. For example, the second compression block г selects the n _B most reliable candidates to generate the message of size

Secondly, the measures of reliability of the n _R requested symbols after permutation, received by the second compression block T in the message are obtained from the message M . For example, the LLR of the n _R requested symbols of the message are extracted from

A message comprising the message and the measures of reliability of the n _R requested symbols after permutation can thus be generated, for example by concatenating the message and the LLR of the n _R requested symbols of the message The size of the message

In the example illustrated in Figure 3B, with n _B = 2, the second compression block T selects the most reliable n _B = 2 candidates from the message and it concatenates the LLR of the n _R requested candidates of the message Thus

The n _B best symbols of the message г ^are then inversely permuted by delivering a message and sent to the second decompression block г ^-1 .

After the inverse permutation process, the message is received by the second decompression block г ^-1 and expanded back to q (for example q =8 in the example illustrated in Figure 3B). The second decompression block T ¹ thus reconstructs the full-set q message T ¹ 1 T ( M _C.2V , ] ).

This reconstruction can be based on a three steps process.

First, the LLRs of the n _B best candidates are placed into their corresponding GF positions. Then, the LLR of the n _R requested symbols are also set into their corresponding GF positions. Finally, the remaining positions are filled with the default LLR value S _D .

More specifically, the measure of reliability (LLR) associated with at least one of said n _R requested symbols can be set to a default value S _R when said measure of reliability is above a threshold. Such saturation process prevents high values from entering the variable node.

In summary, for a given GF value a E GF(q):

The saturation values of S _R and S _D can impact the decoder performance. given as a linear where the values of (y _B , y _R , O _R , O _D ) depend on the code rate.

In the example illustrated in Figure 3B, if the saturation parameters (y _B , y _R , O _R , O _D ) are set to (2, 1/8, 1,2) respectively, then the saturation values of S _R and S _D are S _R = 6 and S _D = 7, with

S _R = 5 + 1 = 6

S _D = 5 + 2 = 7

In the full-set q message the n _B best candidates are kept unchanged, the LLR on the requested symbol a ⁰ , which is equal to 4, is also kept unchanged, while the LLR on the requested on symbol a ⁵ , which is equal to 8, is saturated from 8 down to S _R = 6. The remaining candidates are all assigned the value S _D = 7. Thus T- [7, 4, 2, 7, 7, 0,6, 7] = M _C.2V ..

The first decoding iteration is now finished.

At least one other decoding iteration can be implemented, based on a next message M _{V .2C} . determined by the variable node processing, such as for example disclosed in lines 13, 14 and 15 of the LDBC non binary decoding algorithm described in Annex 1.

In the example illustrated in Figure 3B, for the second decoding iteration, the next message M _{V .2C} .

C. EMS-based BRD Decoder As disclosed above, the proposed BRD algorithm can be well integrated with the Trellis Extended Min Sum (T-EMS) based decoders since, by construction, the CN unit of the T-EMS decoder obtains the reliability of the q candidates without any truncation.

According to at least one embodiment, when the proposed BRD algorithm is integrated with an EMS-based decoder, additional operations could be implemented to obtain the LLR of the requested symbols. Indeed, by construction, the size of the exchanged messages between the CN and the VN is truncated from q to n _m in EMS-based decoder. The message truncation leads to losing the reliability of the requested candidates if those candidates are not in the set of the most reliable (n _m ) candidates.

The EMS algorithm can be implemented using the Elementary Check Node (ECN) architecture. The ECN architecture is a semi-parallel architecture based on 3. (d _c — 2) ECNs, where d _c is the degree of connectivity of the CN, arranged in three layers (the forward layer, the backward layer and the merge), each having d _c — 2. Such architecture is for example disclosed in "Simplified check node processing in nonbinary LDPC decoders" (E. Boutillon and L. Conde-Canencia, in 2010 6th International Symposium on Turbo Codes Iterative Information Processing, 2010, pp. 201-205).

Figure 4 gives an example of an ECN architecture for d _c = 6.

According to at least one embodiment, the output ECNs (shaded in Figure 4) implement an additional process which is finding or approximating the reliability of the requested symbols.

As illustrated in Figure 5, the requested symbols can be found in a n _m x n _m matrix, by using two input values. Two values can be set: the index of the vertical value i _v and the index of the horizontal value i _h -

If we assume that the inputs of an output ECN (shaded ECN of figure 4) are two vectors of a (GF, LLR) pair each of size n _m , resulting in matrices of size n _m x n _m respectively, the n _R best candidates can be found by using the conventional bubble check presented in the above mentioned document "Simplified check node processing in nonbinary LDPC decoders".

In addition, the reliability of a requested symbol a can be found as the minimum value of three possible values: the first possible value is the value obtained from the minimum value such that the second value is the horizontal approximation value , the third value is the vertical approximation value where O _H and O _v are offset values, that can for example be obtained from simulation.

Once the reliability values of the requested symbols are found or approximated, the saturation process of the BRD decoder can determine the saturation value S _D that can be used as a default value for the remaining symbols, as well as the saturation value S _R that can be used for some of the requested symbols as previously described.

The remaining candidates in have a fixed reliability which is S _D = Sat.

The requested candidates are saturated at S _R =γx Sat if their LLR exceeds the threshold y x Sat:

D. Simulation results

In the prior art EMS algorithm, it is known that the size n _m of the M _C2V messages affects the performance of the decoder. However, the main criterion that affects the performance is not the size of the message in itself, but the probability P {xj ® ^Ci2Vj^ that the transmitted symbol Xj belongs effectively to the exchanged message.

As demonstrated below, the proposed BRD algorithm with requested candidates increase this probability significantly, thus leading to good decoding performance even with low message size.

D.l. Statistical Analysis

In this section, a Monte-Carlo estimation of P (x _j ∈ M _Ci2VJ ) is presented as a function of the message size for several decoding algorithms. The Monte-Carlo simulations are performed for a rate 5/6 (d _v = 2, d _c = 12) GF(64) NB- LDPC code of size N = 864 symbols. As d _v = 2, the index i of the check node can be omitted.

The Signal-to-Noise Ratio (SNR) is set to 3 dB (beginning of the waterfall region) with a maximum of 30 decoding iterations. The probability P (x _j ∈ M _C2V ) is estimated in the whole decoding process as a function of the M _C2V message length.

For the EMS algorithm, the message length is given by n _m . The algorithm parameters are n _op = n _m + 5 and offset value equals to 0.3, such as for example detailed in the document "Decoding Algorithms for Non-Binary LDPC Codes Over GF(q)" cited in the background section.

For the BRD proposed algorithm, the message length is characterized by n _cv = n _B + n _R . For this simulation, the CN process is for example based on the TEC-TEMS algorithm, with specific parameters given below.

Figure 6 illustrates the probability P (x _j ∈ M _{C2V j} ) for N = 864, K = 720 on GF(64), for different decoding algorithms: the EMS algorithm with n _m = 20, the TEC-TEMS algorithm with n _m = 64, the Truncated TEC-TEMS with n _vc = 4 and n _cv = 7, the BRD algorithm with n _vc = 4 , n _B = 6 and n _R = 1, the BRD algorithm with n _vc = 4 , n _B = 5 and n _R = 2, the BRD algorithm with n _vc = 4 , n _B = 4 and n _R = 3, the BRD algorithm with n _vc = 4 , n _B = 4 and n _R = 4, the BRD algorithm with n _vc = 4 , n _B = 4 and n _R = 5.

It can be seen on Figure 6 that including the requested symbols greatly enhances the probability that the transmitted symbol Xj belongs to the propagated message M _C2V , and hence becomes a possible candidate to be processed at both VN and CN.

The probability P (X _j ∈ M _C2Vj ) is around 85% in EMS with n _m = 20. The probability P (x _j ∈ M _C2VJ ) in TEC-TEMS has a similar percentage (87%) to EMS. When truncating the size of considered candidates to n _vc = 4 and n _cv = 7 (i.e n _B = 7 and n _R = 0), the probability drops down to 59%. Including one requested symbol n _B = 6 and n _R = 1 enhances the overall probability from 59% to 89% with the same message size (n _cv = 7). The proposed decoder with n _B = 4 and n _R = 3, achieves a probability of 96%.

Figure 7 shows the impact of the decoder parameters on the Frame Error Rate (FER), for the aforementioned analyzed schemes.

It can be seen on Figure 7 that the worst performance is for the truncated TEC-TEMS with n _vc = 4 and n _cv = 7. Moreover, it can be noted that increasing the number of requested symbols further does not enhance the decoding performance of the decoder.

D.2 Results

The number of the exchanged messages reflects the number of memory resources required for the decoding process to be performed. Reducing the number of messages exchanged reduces the latency/complexity of different processes of the decoder such as the sorting processes, the permutation and inverse permutation processes, the configuration sets builder, and the memory resources allocation which benefits both hardware-implemented and software-implemented decoders. The overhead complexity of the compression and decompression block depends on the CN processing algorithm used.

Table I below shows the size of exchanged messages per edge (a connection between a VN and a CN) for different schemes based on GF(64). The message size is characterized by the number of GF values (coded on log ₂ (64) = 6 bits) and the number of LLR values (also coded on 6 bits). The last column sums the number of GF and LLR elements exchanged per edge and per iteration.

Table I

For a code on GF(64) with r = 5/6 and a CN degree of connectivity d _c = 12, the lowest number of the exchanged elements among the studied scheme is 48, achieved by the hybrid EMS decoder (disclosed for example by C. Marchand, E. Boutillon, H. Harb, L. Conde-Canencia, and A. Al Ghouwayel, in "Hybrid Check Node Architectures for NB-LDPC Decoders" (IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 66, no. 2, pp. 869-880, 2019)), whereas the total number of exchanged elements per edge in the proposed BRD decoder is 17. Furthermore, the number of the memory resources reserved is greatly reduced from d _c x q down to d _c x 7 for M _V2C messages, and from d _c x q down to d _c x 10 for M _C2V messages.

For a code rate r = 0.5 with a degree of connectivity d _c = 4, the number of exchanged messages is set to n _vc = 5 , n _B = 6 and n _R = 3. The factors γ _R and γ _B are for example 0.127 and 2.24 respectively, and can be optimized to 0.125 and 2 such that the multiplication is simplified to a shifting operation.

The simulation is done for NB-LDPC codes of size (in bits) (96,48), (864,720) and (1260,1134) on GF(64). The simulated decoder is based on the layered scheduling and a maximum of 10 decoding iterations.

Simulation results for different sizes of code are illustrated in Figure 8.

As shown in Figure 8, the proposed BRD scheme has a performance similar to that of the EMS (with n _m = 20 and n _op = 25) and TEC-TEMS. The performance is simulated down to a FER of 10 ^-5 and no significant performance degradation is experienced.

The parameters used for simulating the BRD decoder for r > 5/6 are n _vc = 4, n _B = 4, n _R = 3, γ _R = 0,125, γ _B — 2, O _D — 0.4, O _R = 0.2 and a compensation factor (TEC-TEMS) = 0.8.

For a code of size N = 96, K — 48 with d _c — 4, the BRD decoder showed similar performance to EMS with a lower number of exchanged messages (n _vc = 5, n _B = 6, and n _R = 3, instead of n _m = 20 and n _op = 25). The parameters used for this simulation are γ _R = 0,125, γ _B — 2, O _D — 0.2, O _R = 0.1 and a compensation factor (TEC-TEMS) = 0.8.

As compared to a binary LDPC code, it can be noticed that a binary LDPC code sends two messages per edge per iteration. For a d _v = 3 LDPC code, each binary VN exchanges 6 messages per iteration. Thus, 6 binary VNs (equivalent to 1 VN in GF(64)) sends 36 messages per iteration. Considering a rate r ≥ 5/6 and d _v = 2 in GF(64)-LDPC code, only 17 x d _v = 34 messages are exchanged. Therefore, the BRD decoder requires less communication load than a binary decoder.

5.3 Other codes As already mentioned, the scope of the invention is not limited to the NB-LDPC codes, nor to the use of parity check. In fact, any code represented by a graph with several "non-binary constraint nodes" (or "sub-codes") and "variable nodes" (each sub-codes constraint a sub-set of variables) can implement the disclosure.

We present below two examples with different codes, one considering a turbo-code, the other one considering a polar code.

Document "Design of Low-Complexity Convolutional Codes over GF(q)" from R. Klaimi, C. Abdel Nour, C. Douillard and J. Farah (2018 IEEE Global Communications Conference (GLOBECOM), Abu Dhabi, United Arab Emirates, 2018, pp. 1-7) gives an example of non-binary convolutional encoder used in a non- binary Turbo-code.

A non-binary turbo-code can be viewed as a bipartite graph, such as illustrated in Figure 9. For example, the set of k information symbols I = {I(1), I(2), ... , I(k )} and of k redundancy symbols R1 = {R 1(1), R 1(2), ... R1 (k )} participate to a first non-binary convolutional code Cl, while the set of a permuted version of the information symbols P(I) and of k redundancy R2 = {R2 (1), R 2 (2), ... R2 (kc)} participate to a second non-binary convolutional code C2.

The turbo-decoding algorithm is also an instance of the Belief Propagation algorithm in this Tanner graph. This mean that symbol reliabilities are exchanged among the branches of the graph, between the convolutional decoder C1 or C2 ("non-binary constraint nodes") and the information or redundancy symbols ("variable nodes").

Using known principle of the extrinsic information, the message M _C12I(j) send for example from the convolutional decoder C1 to the j ^th information symbol I(j) is a function of the symbol reliabilities of I \ I(j) (i.e. vector I with the symbol I(j) excluded) and R1.

In this context, reducing the size of the message M _C12I(j) as proposed in the disclosure, as a union of the set of the n _B best symbol reliabilities, the n _R requested symbol reliabilities (the n _R best symbols of the M _I(j)2C1 message for example) and a default value, is a natural extension of what has been presented in the NB-LDPC context.

We now consider a polar code; the so-called kernel of a polar code is presented in Figure 10. The "+" box 101 represents a parity check of degree 3 over GF(q), while the "=" box represents an identity constraint of degree 3, which is similar in processing to a variable node.

Many polar code decoding algorithms (such as "Successive Cancellation", or iterative decoder) process the parity check node of degree 3 to generate an output message that is used in a following kernel or in a decision unit. For example, from messages D, B it is possible to generate a message E, then from messages E and A, it is possible to generate an output message C by a classical non-binary check node processing. The size of the message C sent by the check node 101 to a "variable node" of a following kernel or a decision unit can be reduced by applying the same Best/Requested/Default mechanisms than described for the NB-LDPC code or Turbo-Code.

More generally, the method can be applied to any non-binary code that can be decoded as an instance of a message passing algorithm.

5.4 Structure

Finally, in relation to Figure 11, the simplified structure of a non-binary decoder according to at least one embodiment described above is presented.

Such a decoder comprises at least one memory 111 comprising a buffer memory, at least one processing unit 112, equipped for example with a programmable computing machine or with a dedicated computing machine, for example a processor P, and controlled by the computer program 113, implementing steps of the method for decoding a codeword according to at least one embodiment of the invention.

Upon initialisation, the code instructions of the computer program 113 are for example loaded into a RAM memory before being executed by the processor of the processing unit 112.

The processor of the processing unit 112 implements steps of the method for decoding a codeword described above, according to the instructions of the computer program 113, to send a message from the non-binary constraint node to the non-binary variable node Vj, said message comprising: n _R measures of reliability obtained for n _R candidate symbols selected by the variable node Vj or by a first compression block implemented between the non-binary variable node Vj and the non-binary constraint node C, n _B measures of reliability obtained for n _B candidate symbols selected by the non-binary constraint node C or by a second compression block implemented between the non-binary constraint node C and the variable node Vj, with 1 ≤ n _B < q, 1 ≤ n _R < q and n _R + n _B < q.

ANNEX 1

2