Check node processing methods and devices with insertion sort

Abstract

A sorting device and method for determining elementary check node components in an elementary check node processor implemented in a non-binary error correcting code decoder by sorting auxiliary components are presented. The auxiliary components are stored in a plurality of FIFO memories, each FIFO memory being assigned a FIFO number index. Each auxiliary component stored in a given FIFO memory comprises an auxiliary symbol, a reliability metrics representing the reliability of the auxiliary symbol, and the FIFO number index assigned to the given FIFO memory. The sorting device is configured to sort the auxiliary components by a plurality of multiplexers arranged sequentially. Each multiplexer is configured to initialize a candidate elementary check node component from the components of a FIFO memory corresponding to the auxiliary component which comprise the most reliable auxiliary symbol and to perform one or more iterations of the illustrated receiving, updating and sorting steps.

Claims

1. A sorting device for determining elementary check node components in an elementary check node processor implemented in a non-binary error correcting code decoder by sorting auxiliary components, said auxiliary components being stored in a plurality of FIFO memories, each FIFO memory being assigned a FIFO number index, each auxiliary component stored in a given FIFO memory comprising an auxiliary symbol, an auxiliary reliability metrics representing the reliability of said auxiliary symbol, and the FIFO number index assigned to said given FIFO memory, the sorting device comprising a plurality of multiplexers arranged sequentially, the multiplexers being configured to initialize a set of candidate elementary check node components, each candidate elementary check node component being determined from one of the FIFO memories and corresponding to the auxiliary component which comprises the most reliable auxiliary symbol among the auxiliary components stored in said FIFO memory, said candidate elementary check node components being sorted according to the auxiliary reliability metrics of the auxiliary symbols, wherein each multiplexer is configured to perform one or more iterations of the following steps: receive an auxiliary component extracted from the FIFO memory which is assigned the FIFO number index comprised in the candidate elementary check node component determined at the previous iteration which comprises the most reliable candidate symbol, and update said candidate elementary check node component determined at the previous iteration by selecting one component among the received auxiliary component, the candidate elementary check node component determined at the previous iteration by said multiplexer, and the candidate elementary check node component determined at the previous iteration by the subsequent multiplexer; the sorting device being configured to determine, at each of said one or more iterations, an elementary check node component by selecting the candidate elementary check node component which comprises the most reliable candidate symbol.

2. The sorting device of claim 1, wherein the elementary check node processor is configured to receive a first message and a second message derived from two or more variable node messages, the elementary check node processor comprising a calculation unit configured to determine said auxiliary components from said first message and second message.

3. The sorting device of claim 2, wherein said first message comprises a first given number of components and said second message comprises a second given number of components, each component of the first message and the second message comprising a symbol and a reliability metrics associated with said symbol, the calculation unit being configured to determine each auxiliary component among said auxiliary components from a component comprised in said first message and a component comprised in said second message, the calculation unit being configured to: determine the auxiliary symbol comprised in each auxiliary component by applying a first addition operation over an algebraic structure of construction of said non-binary error correcting code, said first addition operation being applied to a symbol comprised in a component of said first message and a symbol comprised in a component of said second message; determine the auxiliary reliability metrics associated with each auxiliary symbol by applying a second addition operation over a predefined algebraic structure, said second addition operation being applied to a reliability metrics associated with a symbol comprised in a component of said first message and a reliability metrics associated with a symbol comprised in a component of said second message; the auxiliary components stored in each FIFO memory being sorted according to a decreasing reliability of the auxiliary symbols.

4. The sorting device of claim 3, wherein the predefined algebraic structure is chosen in a group comprising the field of real numbers, the field of integer numbers, and the field of natural numbers.

5. The sorting device of claim 3, wherein the first given number of components and the second given number of components are equal.

6. The sorting device of claim 3, wherein the first given number of components and the second given number of components are different.

7. The sorting device of claim 1, wherein the elementary check node processor is implemented in a check node processing unit configured to exchange two or more variable node messages with at least one variable node processing unit implemented in said non-binary error correcting code decoder during a number of message exchange iterations, the elementary check node processor being configured to previously determine the number of said auxiliary components depending on at least one parameter chosen in a group comprising said number of message exchange iterations, an algebraic structure of construction of said non-binary error correcting code, a signal-to-noise ratio, one or more of a first predefined number of components of the first message or a second predefined number of components of the second message, and a position of the elementary check node processor within said check node processing unit.

8. The sorting device of claim 1, wherein a candidate elementary check node component comprises a candidate symbol and a candidate reliability metrics associated with said candidate symbol, each multiplexer being associated with a reliability metrics comparator configured to perform a comparison between the auxiliary reliability metrics comprised in the received auxiliary component and the candidate reliability metrics comprised in the candidate elementary check node component determined by said multiplexer at a previous iteration, each multiplexer being configured to perform a control action for selecting a component among the received auxiliary component and the candidate elementary check node components determined at a previous iteration by the multiplexer (34-m) and the subsequent multiplexer depending on the comparison performed by the reliability metrics comparator associated with said multiplexer (34-m) and the comparison performed by the reliability metrics comparator associated with the subsequent multiplexer.

9. The sorting device of claim 8, wherein each multiplexer is configured to: perform a keeping action by setting the candidate elementary check node component to the candidate elementary check node component determined by the multiplexer at a previous iteration if it is determined that the auxiliary symbol comprised in the received auxiliary component is more reliable than the candidate symbol comprised in the candidate elementary check node component determined at the previous iteration by the multiplexer; perform an insertion action by setting the candidate elementary check node component to the received auxiliary component if it is determined that the auxiliary symbol comprised in said auxiliary component is less reliable than the candidate symbol comprised in the candidate elementary check node component determined by the multiplexer at a previous iteration and that said auxiliary symbol is more reliable than the candidate symbol comprised in the candidate elementary check node component determined by the subsequent multiplexer at a previous iteration; perform a shift action by setting the candidate elementary check node component to the candidate elementary check node component determined by the subsequent multiplexer at a previous iteration if it is determined that the auxiliary symbol comprised in the received auxiliary component is more reliable than the candidate symbol comprised in the candidate elementary check node component determined by the subsequent multiplexer at a previous iteration.

10. A sorting method for determining elementary check node components in an elementary check node processor implemented in a non-binary error correcting code decoder by sorting auxiliary components, said auxiliary components being stored in a plurality of FIFO memories, each FIFO memory being assigned a FIFO number index, each auxiliary component stored in a given FIFO memory comprising an auxiliary symbol, a reliability metrics representing the reliability of said auxiliary symbol, and the FIFO number index assigned to said given FIFO memory, the sorting method comprises performing by a plurality of multiplexers initialization of a set of candidate elementary check node components, each candidate elementary check node component being determined from one of the FIFO memories and corresponding to the auxiliary component which comprises the most reliable auxiliary symbol among the auxiliary components stored in said FIFO memory, said candidate elementary check node components being sorted according to the reliability metrics of the auxiliary symbols, wherein the method comprises performing, by each multiplexer, one or more iterations of the following steps: receiving an auxiliary component extracted from the FIFO memory which is assigned the FIFO number index comprised in the candidate elementary check node component determined at the previous iteration which comprises the most reliable candidate symbol, and updating said candidate elementary check node component determined at the previous iteration by selecting one component among the received auxiliary component, the candidate elementary check node component determined at the previous iteration by said multiplexer, and the candidate elementary check node component determined at the previous iteration by the subsequent multiplexer; the method further comprises determining, at each of said one or more iterations, an elementary check node component by selecting the candidate elementary check node component which comprises the most reliable candidate symbol.

Description

BRIEF DESCRIPTION OF DRAWINGS

(1) The accompanying drawings, which are incorporated in and constitute a part of this specification, illustrate various embodiments of the invention together with the general description of the invention given above, and the detailed description of the embodiments given below.

(2) FIG. 1 is a block diagram of an exemplary application of the invention to communication systems, according to some embodiments;

(3) FIG. 2 is a block diagram of a non-binary error correcting code decoder, according to some embodiments in which the EMS decoding algorithm is used;

(4) FIG. 3 is a block diagram illustrating the structure of an elementary check node processor implemented in a check node processing unit, according to some embodiments in which the EMS algorithm is used;

(5) FIG. 4A and FIG. 4B illustrate two exemplary grouping of auxiliary components into paths, according to some embodiments;

(6) FIG. 5 is a flowchart depicting a method for determining an elementary check node message from a first message and a second message, according to some embodiments in which iterative sorting is performed, and

(7) FIG. 6 is a flowchart depicting a method for performing control actions, according to some embodiments.

DETAILED DESCRIPTION

(8) Embodiments of the present disclosure provide devices, methods, and computer program products for decoding a signal encoded using a non-binary error correcting code with a low computational complexity and a low latency. In particular, they provide efficient reduced-latency and reduced-complexity architectures for elementary check node processors implemented in check node processing units, used in iterative message passing decoders for decoding signals encoded using a non-binary error correcting code.

(9) Methods, devices and computer program products according to the various embodiments as disclosed may be implemented in several types of digital data transmission and storage devices and systems used in several types of applications. Exemplary devices and systems comprise, but are not limited to, computers, disks, laptops, phones, smart-phones, recorders, base stations, drones, satellites, Internet of Things devices (IoT), embedded devices or the like. Exemplary applications comprise magnetic and optical recording, digital television and video broadcasting, digital communications, etc.

(10) The following description of some embodiments of the disclosure will be made with reference to digital communication systems, for illustration purposes only. However, the skilled person will readily understand that the various embodiments of the disclosure may be integrated in other types of systems, used for other applications such as positioning systems, memory and storage systems, and spacecraft systems.

(11) Referring to FIG. 1, there is illustrated an exemplary application of the disclosure in a digital communication system 100. The communication system 100 may be for example: wired; wireless (e.g. radio or Visible Light communication systems); optical (e.g. optical fiber-based, laser-based); acoustic (e.g. underwater acoustic communication systems); molecular (used for example in underground structures, e.g. tunnels and pipelines or in underwater environments).

(12) The communication system 100 may comprise at least a transmitter device 10 and a receiver device 12. The transmitter device 10 (also referred to hereinafter as a “transmitter”) may be configured to communicate data information to the receiver device 12 (also referred to hereinafter as “receiver”) via the transmission channel 11.

(13) In an application of the disclosure to wired communication systems such as computer networking systems, the transmitter 10 and/or receiver 12 may be any device configured to operate in a wired network. Exemplary devices in such applications comprise computers, routers or switches connected to a small or large area wired network. The transmission channel 11 may be in this case any type of physical cable used to ensure the transfer of data between the different connected devices.

(14) In an application of the disclosure to wireless communication systems such as ad-hoc wireless networks, wireless sensor networks, and radio communication systems, the transmitter 10 and receiver 12 may be any type of fixed or mobile wireless device configured to operate in a wireless environment. Exemplary devices in such applications comprise laptops, mobile phones, base stations and any computer device. The transmission channel 11 may be in this case any wireless propagation medium. Further, the transmission channel 11 may accommodate several transmitters 10 and/or several receivers 12. In such embodiments, multiple access techniques and/or network coding techniques may be used in combination with error correcting codes. Exemplary multiple access techniques comprise Time Division Multiple Access (TDMA), Frequency Division Multiple Access (FDMA), Code Division Multiple Access (CDMA), and Space Division Multiple Access (SDMA).

(15) In an application of the disclosure to optical communication systems such as optical fiber-based systems, the transmitter 10 and receiver 12 may be any optical transceiver devices configured to respectively transmit and receive data information propagated over an optical link. The transmission channel 11 may be any optical fiber link designed to carry data over short or long distances. Exemplary applications using optical fiber links over short distances comprise high-capacity networks such as data center interconnections. Exemplary applications using optical fiber links over long distances comprise terrestrial and transoceanic transmissions. In such embodiments, the information symbols conveyed by the transmitter 10 may be carried by optical signals polarized according to the different polarization states of the fiber. The optical signals propagate along the fiber-based transmission channel 11, according to one or more propagation modes, until reaching the receiver 12. Exemplary optical communication systems comprise Polarization Division Multiplexing (PDM) and Mode Division Multiplexing (MDM) systems.

(16) For any type of wired, wireless or optical communication systems, the transmission channel 11 may be any noisy channel. The noise may result from the thermal noise of the system components or the interfering radiation intercepted by antennas. Other exemplary sources of noise comprise switching, manual interruptions, electrical sparks and lightning. In some embodiments, the total noise may be modeled by an Additive White Gaussian Noise (AWGN).

(17) Further, according to some embodiments applied to digital mass storage, the transmission channel 11 may be modeled for example by an erasure channel, a binary symmetric channel, or a Gaussian channel. In such embodiments, the transmission channel 11 may be any type of storage device that can be sent to (written on) and received from (read).

(18) In addition, the transmitter 10 and receiver 12 may be equipped with single or multiple antennas. In particular, in the presence of multiple transmit and/or receive antennas, Space-Time coding and decoding techniques may be used in combination with error correcting coding and decoding.

(19) Further, encoded data may be transmitted over one or multiple frequency bands. When encoded data are transmitted over multiple frequency bands, the modulator 105 may use multi-carrier modulation formats such as OFDM (acronym for Orthogonal Frequency Division Multiplexing) and FBMC (acronym for Filter Bank Multi-Carrier).

(20) According to some embodiments of the disclosure, the transmitter 10 comprises an error correcting code (ECC) encoder 103, configured to encode a digital input data block 101 denoted u using a non-binary error correcting code into a codeword vector denoted c. The receiver 12 may be configured to receive a noisy copy p of the encoded data, or codeword vector, through the transmission channel 11. The receiver 12 may comprise an error correcting code decoder 123 configured to deliver a digital output data block 125 as an estimate û of the original digital input data block 101.

(21) The digital input data 101 may be previously compressed before being encoded by the ECC encoder 103. Any source coding scheme (not shown in FIG. 1) adapted to increase the information throughput may be used to perform the compression. Data encoded by the ECC encoder 103 may be further modulated by a modulator 105. The modulator 105 may be configured to map the encoded data onto an analog signal s and to send it through the transmission channel.

(22) The receiver 12 may comprise homologous processing blocks configured to perform the reverse functions. The receiver 12 may comprise a demodulator 121, configured to generate a signal y, by performing a demodulation of the received signal p from the transmission channel prior to ECC decoding by the ECC decoder 123. The demodulator 121 may be configured to move the received signal or channel output back into baseband and perform low-pass filtering, sampling and quantization. The data decoded by the ECC decoder 123 may be further decompressed using any source decoder (not shown in FIG. 1). The ECC decoder 123 may be configured to implement an iterative decoder (referred to as ‘iterative decoding algorithm’) involving check node processing units and variable node processing units according to the various embodiments of the disclosure.

(23) The following description of some embodiments of the disclosure will be made with reference to linear block non-binary error correcting codes, for illustration purposes only. However, the skilled person will readily understand that the various embodiments of the disclosure apply to any linear non-binary error correcting codes comprising non-binary convolutional codes.

(24) Accordingly, the ECC encoder 103 may implement a linear block non-binary error correcting code designated by C(n, K); n and K referring respectively to the length of codeword vectors and the length of the encoded data block. The ECC encoder 103 encodes accordingly a data block u of length K into a codeword vector c, with c=(c.sub.1, . . . , c.sub.n) being a vector of length, comprising n elements of the algebraic structure of construction of the error correcting code C(n, K), also referred to as “symbols”.

(25) A linear code C(n, K) may be represented in a matrix form using a generator matrix denoted by G and a parity-check matrix denoted by H. Using a row notation of vectors, the generator matrix G is of dimensions K×n while the parity-check matrix has dimensions of (n−K)×n. The two matrices are linked by the relation G.Math.H.sup.t=0. In addition, entries of both matrices belong to the algebraic structure over which the error correcting code is constructed. Using the matrix representation, any codeword vector c satisfies the equation c. H.sup.t=0. This equation is also called “parity-check equation”. It defines (n−K) parity-check constraints, designed to be satisfied by any codeword vector.

(26) In association with the matrix representation, the linear code C (n, K) may be represented using the Tanner graph denoted by H. This graph comprises n variable nodes and n−K check nodes.

(27) Each variable node vn∈ {1, 2, . . . , n} corresponds to a column of the parity-check matrix. Each check node cn∈ {1,2, . . . , n−K} corresponds to a row of the parity-check matrix, i.e. to a parity-check equation. A variable node vn is connected to a check node cn if the entry H.sub.vn,cn of the parity-check matrix is equal to a non-null element of the algebraic structure of construction of the code C (n, K).

(28) H.sub.v(vn) denotes the set of the check nodes connected to the variable node vn. Similarly, H.sub.c(cn) denotes the set of the variable nodes connected to the check node cn.

(29) The degree d.sub.VN of a variable node vn (respectively d.sub.CN of a check node cn) corresponds to the cardinality of the set H.sub.v(vn) (respectively the cardinality of the set H.sub.c(cn)).

(30) According to some embodiments, the algebraic structure of construction of the non-binary error correcting code C(n, K) may be any non-zero commutative division ring, such as ‘Galois fields’.

(31) The following description of some embodiments will be made with reference to finite fields, for illustration purposes only. However the skilled person will readily understand that the disclosure may be applied to any division rings-like algebraic structures such as non-zero commutative division rings and to any near-rings such as finite division near-rings. Insights on the design of non-binary error correcting codes over finite division near-rings can be found in the article “Non-binary LDPC codes over finite division near rings, 23rd International Conference on Telecommunications (ICT), pp. 1-7, Thessaloniki, 2016”.

(32) For non-binary linear codes constructed over Galois Fields, generally denoted by GF(q), where q>2 designates the cardinality of the code, the symbols take values in GF(q). A codeword vector c is thus a vector of n symbols that each belong to GF(q).

(33) The following description of some embodiments will be made with reference to an ECC encoder 103 encoding data using a non-binary LDPC code, for illustration purposes only. However, the skilled person will readily understand that the various embodiments of the disclosure also apply to other non-binary codes such as non-binary polar codes, non-binary convolutional codes, non-binary turbo codes, and in general to non-binary linear block error correcting codes. Non-binary error correcting codes can advantageously be used for high spectral efficiency coding.

(34) For exemplary purposes, in one embodiment, the ECC decoder 123 implements a non-binary LDPC codes decoder for decoding the data encoded by the ECC encoder 103, using a non-binary LDPC code.

(35) The description of the disclosure is made with reference to the EMS algorithm. However, the skilled person will readily understand that the various embodiments apply to any iterative non-binary LDPC codes decoder such as the min-max.

(36) For ease of presentation of the various embodiments of the disclosure, the following definitions will be used in the remaining of the description.

(37) An elementary check node-based architecture refers to any implementation architecture of a check node processing unit that comprises one or more elementary check node processors.

(38) A message generated by a variable node processing unit 27-vn is referred to as a ‘variable node message’. A message generated by a check node processing unit 25-cn is referred to as a ‘check node message’.

(39) The variable node messages and check node messages may comprise components carrying data representative of the symbols. The components comprised in a variable node message are referred to as ‘variable node components’ and the components comprised in a check node message are referred to as ‘check node components’.

(40) An intrinsic message refers to a message comprising components referred to as intrinsic components, each intrinsic component comprising an intrinsic symbol and an intrinsic reliability metrics associated with the intrinsic symbol. The intrinsic reliability metrics are computed from the received sequence only. The wording ‘intrinsic’ refers accordingly to the dependence of the intrinsic reliability metrics only on the (transmission) channel.

(41) The first message and the second message processed by an elementary check node processor refer to messages derived from the variable node messages received by the check node processing unit in which the elementary check node processing unit is implemented. The first message comprises a first predefined number of components and the second message comprises a second predefined number of components.

(42) An elementary check node message refers to a message computed by an elementary check node processor from a first message and a second message. The components of an elementary check node message are referred to as elementary check node components.

(43) An auxiliary component (also referred to as ‘a bubble’) refers to a component determined by an elementary check node processor from a component comprised in a first message and a component comprised in a second message. An auxiliary component comprises an auxiliary symbol and an auxiliary reliability metrics associated with the auxiliary symbol.

(44) A candidate elementary check node component refers to a component determined by an elementary check node processor at a given iteration of the iterative sorting of the auxiliary components performed by said elementary check node processor.

(45) Referring to FIG. 2, there is illustrated a structure of an iterative non-binary LDPC decoder 123 according to some embodiments using the EMS algorithm.

(46) The iterative decoder 123 may be configured to determine an estimate û of the transmitted codeword c by the transmitter 10 from a received noisy sequence represented by a vector y=(y.sub.1, . . . , y.sub.n). The codeword c=(c.sub.1, . . . , c.sub.n) may have been encoded at the transmitter using a non-binary LDPC code designated by C(n,K) constructed over the Galois Field GF(q) with q>2. It may process a signal over several iterations trying, at each iteration, to reduce the remaining errors.

(47) The iterative decoder 123 may be configured to determine the estimate u based on the Tanner graph representation of the code C(n, K) used at the transmitter 10. Each variable node in the Tanner graph maps to a variable node processing unit. Each check node in the Tanner graph maps to a check node processing unit.

(48) Accordingly, the iterative decoder 123 may comprise n variable node processing units 27 (also denoted by 27-1 to 27-n or 27-vn with vn=1, . . . , n) and n−K check node processing units 25 (also denoted by 25-1 to 25-(n−K) or 25-cn with cn=1, . . . , n−K).

(49) The variable node processing units 27-vn for vn=1, . . . , n and check node processing units 25-cn for cn=1, . . . , n−K may be configured to iteratively exchange variable node messages and check node messages during a number of message exchange iterations to estimate the most reliable codeword û from the noisy sequence y.

(50) According to some embodiments, the variable node and check node components comprised respectively in the variable node messages and the check node messages may carry values of the symbols and metrics measuring their reliabilities (also referred to hereinafter as ‘reliability metrics’). The value of the reliability metrics is related to the reliability of the symbol. In such embodiments, each variable node message (respectively check node message) may comprise q variable node components (respectively check node components), a component (check node component or variable node component) comprising: a value of a symbol in GF(q), and a reliability metrics associated with the symbol.

(51) In some embodiments, the reliability metrics of a symbol may correspond to an estimated probability density function of the symbol which represents the probability that the symbol is correct. In particular, the reliability metrics may be represented in the log-domain by a logarithmic likelihood ratio (LLR) value.

(52) Depending on the expression of the reliability metrics, the most reliable symbols may be associated with the smallest or the greatest values of the reliability metrics.

(53) One definition of the LLR metric involves a fixed symbol denoted by β.sub.i and corresponding to the most reliable symbol satisfying:

(54) $\begin{array}{cc}{\beta }_i=\underset{t=0,\mathrm{.Math.},q-1}{\arg \max }p\left({\alpha }_t|y_i\right)& \left(1\right)\end{array}$

(55) In equation (1), α.sub.t designates a symbol over the Galois field.

(56) Accordingly, with the hypothesis that the symbols in the Galois field are equiprobable, for the i.sup.th symbol c.sub.i, the LLR value for this symbol to be equal to α.sub.t is noted LLR.sub.t(c.sub.i) and may be expressed as:

(57) $\begin{array}{cc}LL{R}_t\left(c_i\right)=-\log \left(\frac{p\left(c_i={\alpha }_t|y_i\right)}{p\left(c_i={\beta }_i|y_i\right)}\right)& \left(2\right)\end{array}$

(58) Using such definition of the LLR metrics, the most reliable symbols are those that are associated with the smallest LLR values according to equation (2).

(59) The following description of some embodiments will be made with reference to reliability metrics represented in the logarithm domain by log-likelihood ratio (LLR) values, for illustration purposes only. However, the skilled person will readily understand that other types of decoding and reliability metrics may be used to measure the reliability of symbols. For instance, the reliability metrics may be a quadratic distance or any monotonic function of the probability density function of symbols.

(60) According to some embodiments using the EMS algorithm, the variable node messages and/or the check node messages may be sorted according to their reliability i.e. according to a given order (for example increasing or decreasing) of the reliability metrics comprised in the variable node components and the check node components. Further, the variable node messages may be truncated so as to keep only a predefined number n.sub.VN of the variable node components comprising the most reliable symbols, with n.sub.VN being strictly lower than q. Similarly, the check node messages may be truncated so as to keep only a predefined number n.sub.CN of the check node components comprising the most reliable symbols, with n.sub.CN being strictly lower than q. Further, the sorting and truncation operations may be performed by the variable node processing units 27-vn or by the check node processing units 25-cn.

(61) In an embodiment, the predefined number of variable node components n.sub.VN and the predefined number of check node components n.sub.CN are different, i.e. n.sub.VN≠n.sub.CN.

(62) In another embodiment, the predefined number of variable node components n.sub.VN and the predefined number of check node components n.sub.CN are identical, i.e. n.sub.VN=n.sub.CN.

(63) The following description of the embodiments of the disclosure will be made with reference to sorted and truncated variable node messages and check node messages, the number of check node components and variable node components being equal or different.

(64) The processing performed by the various variable node processing units 27-vn and check node processing units 25-cn may be implemented according to several scheduling mechanisms including, without limitation, the three examples described in the following.

(65) According to a first implementation, all the variable node processing units 27-vn for vn=1, . . . , n, are configured to operate in a first round and then all the check node processing units 25-cn, for cn=1, . . . , n−K, may be configured to update the check node messages to be delivered to the variable node processing units in their corresponding sets H.sub.c(cn). This specific scheduling is known as “flooding scheduling”. In particular, the check node processing units 25-cn may be configured to operate serially or in parallel, where, from 2 to n−K,check node processing units 25-cn may operate at the same time.

(66) According to a second implementation based on a “horizontal scheduling”, the check node processing units 25-cn, for cn=1, . . . , n−K, are configured to operate serially, updating all variable node processing units 27-vn which are connected to them. In particular, a group of check node processing units 25-cn may be configured to operate in parallel, updating all connected variable node processing units 27-vn.

(67) According to a third implementation based on a “vertical scheduling”, the variable node processing units 27-vn is configured to operate serially, updating all check node processing units 25-cn which are connected to them.

(68) The exchange of messages may be started by the variable node processing units 27-vn. The variable node messages sent to the check node processing units 25-cn at the start of the decoding process may comprise intrinsic messages.

(69) The iterative decoder 123 may accordingly comprise a data processing unit 23 configured to determine intrinsic symbols and intrinsic reliability metrics from the received sequence, an intrinsic symbol denoted x∈ GF(q) and that belongs to the Galois field (in general to the algebraic structure of the non-binary error correcting code) being associated with an intrinsic reliability metrics denoted I.sup.+(x). The intrinsic reliability metrics may be computed from devices external to the error correcting code decoder 123. Intrinsic information can comprise the channel information. Alternatively, in case of concatenated codes, intrinsic information can be obtained from the channel and from the output of distinct decoders.

(70) More specifically, the data processing unit 23 may comprise: a symbol generator 231 configured to generate intrinsic symbols x that belong to the algebraic structure over which the non-binary error correcting code is constructed, and an intrinsic reliability metrics generator unit 233 configured to generate the intrinsic reliability metrics I.sup.+(x) associated with each intrinsic symbol x from the received sequence y.

(71) Using the LLR notation of equation (2), the intrinsic reliability metrics associated with a symbol x may be determined in logarithmic scale according to:

(72) $\begin{array}{cc}{I}^{+}\left(x\right)=-\log \left(\frac{p\left(x={\alpha }_t|y_i\right)}{p\left(x={\beta }_i|y_i\right)}\right)& \left(3\right)\end{array}$

(73) In equation (3), β.sub.i refers to the most reliable symbol previously defined in equation (1).

(74) According to some embodiments, the intrinsic reliability metrics generator unit 233 is configured to load the received signal y from a storage unit 21, the storage unit 21 being configured to store the received signal y.

(75) In some embodiments illustrated in FIG. 2, the storage unit 21 is comprised within the data processing unit 23.

(76) In other embodiments (not illustrated in FIG. 2), the storage unit 21 is comprised in the iterative decoder 123 outside the data processing unit 23.

(77) According to some embodiments, the intrinsic reliability metrics generator unit 233 is configured to determine at least a part of the intrinsic reliability metrics offline before the starting of the iterative decoding process. In such embodiments, the intrinsic reliability metrics generator unit 233 may be further configured to store at least a part of the computed intrinsic reliability metrics in the storage unit 21. Such embodiments may be advantageously implemented for decoding codes constructed over algebraic structures of small order to store all the intrinsic reliability metrics, as computed, in the storage unit 21. For algebraic structures of high orders, only a part of the computed intrinsic reliability metrics may be stored in the storage unit 21.

(78) In some embodiments, the intrinsic reliability metrics generator unit 233 is configured to determine the intrinsic reliability metrics online during the iterative decoding process. Such embodiments may be advantageously implemented for decoding high-order non-binary error correcting codes enabling memorization savings.

(79) In some embodiments, the intrinsic reliability metrics generator unit 233 is configured to determine at least some of the intrinsic reliability metrics offline and to determine the remaining intrinsic reliability metrics online.

(80) According to some embodiments (illustrated in FIG. 2), the iterative decoder 123 comprises a single data processing unit 23 configured to determine intrinsic reliability metrics to be delivered to all of the variable node processing units 27-vn for vn=1, . . . , n.

(81) In other embodiments (not illustrated), the iterative decoder 123 comprises a plurality of data processing units 23-vn for vn=1, . . . , n, each data processing unit 23-vn being comprised in a variable node processing unit 23-vn, for vn=1, . . . , n.

(82) A variable node processing unit 27-vn may be configured to receive intrinsic reliability metrics derived from the received signal y and to receive check node messages from the check node processing units 25-cn corresponding to the set H.sub.v(vn). A variable node processing unit 27-vn may be further configured to process the received check node messages and intrinsic reliability metrics, compute local decisions, and deliver variable node messages to at least one check node processing unit 25-cn corresponding to the check nodes in the set H.sub.v(vn).

(83) Similarly, a check node processing unit 25-cn may be configured to process variable node messages sent by the variable node processing units 27-vn corresponding to the set H.sub.c(cn). A check node processing unit 25-cn may be further configured to deliver check node messages to at least one variable node processing unit 27-vn corresponding to the variable nodes in the set H.sub.c(cn).

(84) The decoding process may terminate either if the processed signal satisfies the parity-check equation or if a maximum number of message exchange iterations is reached without meeting all parity-check constraints.

(85) Accordingly, the iterative decoder 123 may comprise a decoding decision unit 29 configured to receive, at each iteration of the decoding process, the local decisions computed by the variable node processing units 27-vn and to: deliver the processed signal as an estimate of the original codeword vector if the processed signal satisfies the parity-check equation; or declare a decoding failure but nevertheless output the codeword vector estimated at the last iteration if a maximum number of iterations is reached without meeting all parity-check constraints.

(86) The various embodiments of the disclosure provide efficient low-complexity and low-cost architectures of elementary check node processors implemented in check node processing units 25-cn for cn∈ {1, . . . , n−K}.

(87) According to the various embodiments of the disclosure, the check node processing unit 25-cn implements one or more elementary check node processors and is configured to determine at least one check node message based on a plurality of elementary computations performed by said one or more elementary check node processors.

(88) Each elementary check node processor implemented in a check node processing unit 25-cn may be configured to: receive a first message and a second message derived from the three or more variable node messages received by the check node processing unit 25-cn, and to determine an elementary check node message from the first message and second message, the elementary check node message comprising one or more elementary check node components.

(89) According to some embodiments, the iterative decoder 123 may comprise two or more check node processing units 25-cn with cn=1, . . . , (n−K), each of said two or more check node processing units 25-cn implementing an elementary check node-based architecture.

(90) The various embodiments of the disclosure provide efficient reduced-complexity and reduced latency techniques for iterative sorting in elementary check node processors.

(91) FIG. 3 is a block diagram illustrating the structure of an elementary check node processor 3 implemented in a check node processing unit 25-cn of degree d.sub.CN≥3, the check node processing unit 25-cn being accordingly configured to: receive d.sub.CN≥3 (three or more) variable node messages denoted by U.sub.1, . . . , U.sub.d.sub.CN from the variable node processing units 27-vn in the set H.sub.c(cn), and to determine one or more check node messages, denoted by V.sub.1, . . . , V.sub.d.sub.CN, from the received variable node messages U.sub.1, . . . , U.sub.d.sub.CN.

(92) According to some embodiments using the EMS algorithm with a sorting and truncation of the check node messages and the variable node messages, each variable node message U.sub.i, i=1, . . . , d.sub.CN comprises n.sub.VN variable node components denoted by U.sub.i[j]=(U.sub.i.sup.⊕[j], U.sub.i.sup.+[j]) for j=0, . . . , n.sub.VN−1, a variable node component U.sub.i[j]=(U.sub.i.sup.⊕[j], U.sub.i.sup.+[j]) comprising a symbol U.sub.i.sup.⊕[j] that belongs to the Galois field GF(q) and a reliability metrics U.sub.i.sup.+[j] associated with the symbol U.sub.i.sup.⊕[j]. The variable node components may be sorted according to a decreasing reliability corresponding to a given order (increasing or decreasing) of the reliability metrics U.sub.i.sup.+[j] such that U.sub.i.sup.+[j]≤U.sub.i.sup.+[j+1] (respectively U.sub.i.sup.+[j]≥U.sub.i.sup.+[j+1]) for j=0, . . . , n.sub.VN−2 and the component comprising the most reliable symbol is U.sub.i[0]=(U.sub.i.sup.⊕[0], U.sub.i.sup.+[0]=0) (respectively U.sub.i[n.sub.VN−1]) for an increasing order (respectively decreasing order) of the reliability metrics.

(93) Similarly, each check node message V.sub.i, i=1, . . . , d.sub.CN may comprise n.sub.CN check node components denoted by V.sub.i[l]=(V.sub.i.sup.⊕[l], V.sub.i.sup.+[l]) for l=0, . . . , n.sub.CN−1, a check node component V.sub.i[l]=(V.sub.i.sup.⊕[l], V.sub.i.sup.+[l]) comprising a symbol V.sub.i.sup.⊕[l] that belongs to the Galois field GF(q) and a reliability metrics V.sub.i.sup.+[l] associated with the symbol V.sub.i.sup.⊕[l]. The check node components may be sorted according to a decreasing reliability corresponding to a given order (increasing or decreasing) of the reliability metrics V.sub.i.sup.+[l] such that V.sub.i.sup.+[l]≤V.sub.i.sup.+[l+1] (respectively V.sub.i.sup.+[j]≥V.sub.i.sup.+[j+1]) for l=0, . . . , n.sub.CN−2 and the component comprising the most reliable symbol is V.sub.i[0]=(V.sub.i.sup.⊕[0], V.sub.i.sup.+[0]) (respectively V.sub.i[n.sub.VN−1]) for an increasing order (respectively decreasing order) of the reliability metrics.

(94) Without loss of generality, the following description of some embodiments will be made with reference to a decreasing reliability corresponding to an increasing order of the reliability metrics associated with the symbols, for illustration purposes only.

(95) The elementary check node processor 3 may be configured to receive a first message denoted by X comprising a first given number n.sub.X of components denoted by X[x]=(X.sup.⊕[x], X.sup.+[x]) for x=0, . . . , n.sub.X−1 and to receive a second message denoted by Y comprising a second given number n.sub.Y of components denoted by Y[y]=(Y.sup.⊕[y], Y.sup.+[y]) for y=0, . . . , n.sub.Y−1, the first and the second messages being derived from the variable node messages U.sub.1, . . . , U.sub.d.sub.CN. Each component of the first message and the second message may comprise a symbol and a reliability metrics associated with the symbol. The components of the first message and the components of the second message may be sorted according to a decreasing reliability corresponding to a given order (increasing or decreasing) of the reliability metrics X.sup.+[x] and Y.sup.+[y] comprised therein such that:

(96) i) X.sup.+[x]≤X.sup.+[x+1] for x=0, . . . , n.sub.X−1 and Y.sup.+[y]≤Y.sup.+[y+1] for y=0, . . . , n.sub.Y−1, and that

(97) ii) the components comprising the most reliable symbols are respectively X[0]=(X.sup.⊕[0], X.sup.+[0]=0) and Y[0]=(Y.sup.⊕[0], Y.sup.+[0]=0).

(98) According to some embodiments, the first message and the second message may comprise a same number of components, according to which the first given number and the second given number are equal, i.e. n.sub.X=n.sub.Y.

(99) In another embodiment, the first message and the second message may comprise a different number of components, according to which the first given number and the second given number are different, i.e. n.sub.X≠n.sub.Y.

(100) The elementary check node processor 3 is configured to determine an elementary check node message denoted by E from the first message X and the second message Y, the elementary check node message E comprising n.sub.E elementary check node components denoted by E[e]=(E[e].sup.⊕, E[e].sup.+) for e=0, . . . , n.sub.E−1, each elementary check node component E[e] comprising a symbol E[e].sup.⊕ and a reliability metrics E[e].sup.+ associated with the symbol, the elementary check node components being sorted according to an increasing order of the reliability metrics E[e].sup.+ such that:

(101) i) E[e].sup.+≤E[e+1].sup.+ for e=0, . . . , n.sub.E−2, and

(102) ii) the elementary check node component comprising the most reliable symbol is E[0]=(E[0].sup.⊕, E[0].sup.+).

(103) According to some embodiments, the elementary check node processor 3 may be configured to determine the elementary check node components of the elementary check node message E from auxiliary components derived from combinations of the components comprised in the first message X and the second message Y, the elementary check node processor 3 being configured to determine said elementary check node components by sorting the auxiliary components and selecting the n.sub.E components comprising the most reliable symbols.

(104) Accordingly, as depicted in FIG. 3, the elementary check node processor 3 may comprise: a calculation unit 31 configured to determine a predefined number n.sub.B of auxiliary components designated by B.sub.t[x][y]=(B.sub.t[x][y].sup.⊕, B.sub.t[x][y].sup.+) for t=1, . . . , n.sub.B from the first message X and the second message Y. More specifically, the auxiliary component denoted by B.sub.t[x][y]=(B.sub.t[x][y].sup.⊕, B.sub.t[x][y].sup.+) for t=1, . . . , n.sub.B refers to the auxiliary component determined from the component X[x]=(X[x].sup.⊕, X[x].sup.+) comprised in the first message X and from the component Y[y]=(Y[y].sup.⊕, Y[y].sup.+) comprised in the second message, the index x varying in 0,1, . . . , n.sub.x−1 and the index y varying in 0,1, . . . , n.sub.Y−1. The auxiliary component B.sub.t[x][y]=(B.sub.t[x][y].sup.⊕, B.sub.t[x][y].sup.+) is a component comprising: an auxiliary symbol designated by B.sub.t[x][y].sup.⊕, and an auxiliary reliability metrics designated by B.sub.t[x][y].sup.+ associated with the auxiliary symbol.

(105) The maximum possible number of auxiliary components may be given by the total number of the possible combinations of the components comprised in the first message and of the components comprised in the second message. The maximum possible number of auxiliary components may be equal to n.sub.X×n.sub.Y.

(106) The predefined number of auxiliary components n.sub.B may vary between a predefined number n.sub.E of elementary check node components and the maximum possible number of auxiliary components n.sub.X×n.sub.Y. In other words, the predefined number n.sub.B of auxiliary components may be higher than or equal to the predefined number of elementary check node components n.sub.E and lower than or equal to the maximum number of auxiliary components, that is n.sub.E≤n.sub.B≤n.sub.X×n.sub.Y.

(107) According to some embodiments, the calculation unit 31 may be configured to: determine the auxiliary symbol B.sub.t[x][y].sup.⊕ comprised in each auxiliary component B.sub.t[x][y] for t=1, . . . , n.sub.B by applying a first addition operation over the algebraic structure of construction of the non-binary error correcting code, the first addition operation being applied to a symbol X[x].sup.⊕ comprised in a component X[x]=(X[x].sup.⊕, X[x].sup.+) of the first message X and a symbol Y[y].sup.⊕ comprised in a component Y[y] of the second message Y according to:
B.sub.t[x][y].sup.⊕=X[x].sup.⊕⊕Y[y].sup.⊕  (4)

(108) For error correcting codes constructed over Galois fields, the first addition operation of equation (4) is performed over the Galois field GF(q). determine the auxiliary reliability metrics B.sub.t[x][y].sup.+ associated with each auxiliary symbol B.sub.t[x][y].sup.⊕ by applying a second addition operation over a predefined algebraic structure chosen in a group comprising the field of real numbers, the field of integer numbers, and the field of natural numbers, the second addition operation being applied to a reliability metrics X[x].sup.+ associated with a symbol X[x].sup.⊕ comprised in a component X[x] of the first message X and a reliability metrics Y[y].sup.+ associated with a symbol Y[y].sup.⊕ comprised in a component Y[y] of the second message Y according to:
B.sub.t[x][y].sup.+=X[x].sup.++Y[y].sup.+  (5)

(109) According to some embodiments, the elementary check node processor 3 may be configured to previously determine the predefined number n.sub.B of auxiliary components depending on at least one parameter chosen in a group comprising: the number of iterations of the messages exchanged between the check node processing unit 25-cn and at least one variable node processing unit 27-vn in the set H.sub.c(cn), the algebraic structure of construction of the non-binary error correcting code (for example the Galois field for codes constructed over Galois fields), a signal-to-noise ratio, one or both of the first predefined number of components n.sub.X of the first message X and the second predefined number of components n.sub.Y of the second message Y, and the position of the elementary check node processor 3 within the check node processing unit 25-cn.

(110) In some embodiments, the components of the first message and the second message may be received by the calculation unit 31 in serial such that at each clock cycle one component of the first message or one component of the second message is received.

(111) In such embodiments, the calculation unit 31 may be configured to determine the n.sub.B auxiliary components depending on the received components of the first message and the components of the second message. For example, the calculation unit 31 may be configured to compute auxiliary components B.sub.t[0][y] derived from the component X[0] of the first message and the components Y[y] comprised in the second message for each y varying in 0,1, . . . , n.sub.Y−1. In this example, the calculation unit 31 may be configured to store the component X[0] of the first message, in response to receiving the component X[0] in a register (not shown in FIG. 3), and determine at each clock cycle an auxiliary component B.sub.t[0][y] in response to receiving a component Y[y] comprised in the second message. The computation of the auxiliary components may accordingly depend on the order of reception of the components of the first message and of the second message.

(112) The serial computation of the auxiliary components depending on the order of reception of the components of the first message and the components of the second message enables grouping the computed auxiliary components into a plurality of n.sub.p paths denoted by Path.sub.1, . . . , Path.sub.n.sub.p such that each path Path.sub.n=(Path.sub.n[0], . . . , Path.sub.n[N.sub.n−1]) for n=1, . . . , n.sub.p comprises at least one auxiliary component denoted by Path.sub.n[g]=(Path.sub.n.sup.⊕[g], Path.sub.n.sup.+[g]) for g=0, . . . , N.sub.n−1.

(113) The auxiliary components may be grouped into the paths according to a decreasing reliability of the auxiliary symbols such that: the auxiliary components comprised in each path of index n are sorted according to a decreasing reliability of the auxiliary symbols satisfying Path.sub.n.sup.+[g]≤Path.sub.n.sup.+[g+1] for g=0, . . . , N.sub.n−1 and the auxiliary components comprising the most reliable auxiliary symbol of each path are sorted according to a decreasing reliability of the auxiliary symbols such that Path.sub.1.sup.+[0]≤Path.sub.2.sup.+[0]≤ . . . ≤Path.sub.n.sub.p.sup.+[0].

(114) According to some embodiments, as depicted in FIG. 3, the auxiliary components of each path Path.sub.n constructed during the computation of the auxiliary components may be stored in a FIFO memory 33-n for n=1, . . . , n.sub.p, each FIFO memory 33-n being assigned a FIFO number index denoted by FNI given by the index n varying between 1 and n.sub.p and the auxiliary components stored in each FIFO memory 33-n being assigned the FIFO number index of the FIFO memory 33-n in which they are stored. The auxiliary components stored in a FIFO memory 33-n are denoted by FIFO.sub.n[a] with a varying between 0 and N.sub.n−1 with N.sub.n designating the total number of auxiliary components stored in the FIFO memory 33-n (equivalently the total number of auxiliary components in the path Path.sub.n). The filling the different FIFO memories 33-n may depend on the order of arrival of the components of the first message and of the second message, on the computation of the auxiliary components of each path, as well as on the structure of the paths grouping the auxiliary components.

(115) Referring to FIG. 4, two exemplary constructions of paths, while computing the auxiliary components from the first message and the second message, are shown. The computation of the auxiliary components is accordingly illustrated using a two-dimensional representation. The vertical axis designates the processed components of the first message. The horizontal axis designates the processed components of the second message. The computed auxiliary components are represented by filled circles.

(116) FIG. 4A depicts a first exemplary construction of four paths such that: the auxiliary components of the path Path.sub.1 are determined from the component Y[0] of the second message and from the components X[x] of the first message for x varying between 0 and n.sub.X−1; the auxiliary components of the path Path.sub.2 are determined from the component X[0] of the first message and from the components Y[y] of the second message for y varying between 1 and n.sub.Y−2; the auxiliary components of the path Path.sub.3 are determined from the component Y[1] of the second message and from the components X[x] of the first message for x varying between 1 and n.sub.X−3; the auxiliary components of the path Path.sub.4 are determined from the component X[1] of the first message and from the components Y[y] of the second message for y varying between 2 and n.sub.Y−2;

(117) FIG. 4B depicts a second exemplary construction of five paths such that: the auxiliary components of the path Path.sub.1 are determined from the component Y[0] of the second message and from the components X[x] of the first message for x varying between 0 and n.sub.X−1; the auxiliary components of the path Path.sub.2 are determined from the component Y[1] of the second message and from the components X[x] of the first message for x varying between 0 and n.sub.X−3; the auxiliary components of the path Path.sub.3 are determined from the component Y[2] of the second message and from the components X[x] of the first message for x varying between 0 and n.sub.X−3; the auxiliary components of the path Path.sub.4 are determined from the component Y[3] of the second message and from the components X[x] of the first message for x varying between 0 and n.sub.X−4, and the auxiliary components of the path Path.sub.5 are determined from the component X[0] of the first message and from the components Y[y] of the second message for y varying between 4 and n.sub.Y−1.

(118) The two examples depicted in FIG. 4 illustrate possible constructions of the paths while computing the auxiliary components. However, the skilled person will readily understand that other path constructions may be obtained depending on the order of reception of the components of the first and the second messages. In particular, the order of reception of the components of the first and of the second messages may be taken into account, in order to compute the first elements of the FIFO memories, i.e. the elements Path.sub.n[0] for n=1, . . . , n.sub.p, as soon as possible, in order to minimize the latency of the elementary check node processor 3. It should be noted that when the first element of the FIFO is ready, the sorting process can start. In such situation, the filling the FIFO with the path and the generation of the elementary check node components of the elementary check node message E may be performed simultaneously.

(119) The various embodiments of the disclosure provide efficient and low-complexity sorting devices implemented in the elementary check node processor 3 to determine n.sub.E elementary check node components of at least one elementary check node message by iteratively sorting the auxiliary components derived from the first and from the second messages.

(120) To facilitate understanding of the disclosure, the following definitions are provided in connection to the notations used hereinafter in the description of some embodiments: n.sub.IT=n.sub.E designates the number of iterations of the auxiliary components sorting process, the script it=1, . . . , n.sub.IT referring to the it.sup.th iteration of the sorting process; n.sub.MUX=n.sub.p designates a number of multiplexers used for the sorting process; n.sub.comp=n.sub.MUX designates a number of reliability metrics comparators used for the sorting process; B.sub.aux.sup.it=(B.sub.aux.sup.it,⊕, B.sub.aux.sup.it,+, B.sub.aux.sup.it,FNI) refers to an auxiliary component extracted from the auxiliary components at the it.sup.th iteration of the sorting process, the auxiliary component comprising an auxiliary symbol B.sub.aux.sup.it,⊕, an auxiliary reliability metrics B.sub.aux.sup.it,+, and a FIFO number index B.sub.aux.sup.it,FNI indicating the FIFO memory from which the auxiliary component at iteration it was extracted; B.sub.cand,m.sup.it=(B.sub.cand,m.sup.it,⊕, B.sub.cand,m.sup.it,+, B.sub.cand,m.sup.it,FNI) refers to a candidate elementary check node component determined by the m.sup.th multiplexer 34-m at the it.sup.th iteration of the sorting process, the candidate elementary check node component comprising a candidate symbol B.sub.cand,m.sup.it,⊕, a candidate reliability metrics B.sub.cand,m.sup.it,+ associated with said candidate symbol, and a FIFO number index B.sub.cand,m.sup.it,FNI indicating the FIFO memory from which the candidate symbol B.sub.cand,m.sup.it,⊕ and the candidate reliability metrics B.sub.cand,m.sup.it,+ originate; B.sub.cand,min.sup.it=B.sub.cand,1.sup.it=(B.sub.cand,1.sup.it,⊕, B.sub.cand,1.sup.it,+, B.sub.cand,1.sup.it,FNI) refers to the candidate elementary check node component determined by the 1.sup.st multiplexer 34-1 at the it.sup.th iteration of the sorting process, the candidate elementary check node component B.sub.cand,min.sup.it comprising the most reliable candidate symbol at the it.sup.th iteration of the sorting process.

(121) Referring to FIG. 3, the elementary check node processor 3 may comprise a sorting device configured to determine the elementary check node components (more precisely a predefined number n.sub.E of elementary check node components) from the n.sub.B auxiliary components determined by the calculation unit 31 by sorting the auxiliary components during a number n.sub.IT of iterations according to a given order of the auxiliary reliability metrics. The sorting device may comprise a plurality n.sub.MUX=n.sub.p of multiplexers 34-m, the multiplexers 34-m for m=1, . . . , n.sub.MUX being configured to perform initialization actions at a first iteration (i.e. it=1) of the sorting process by setting candidate elementary check node components B.sub.cand,m.sup.1 to the auxiliary component B.sub.m(0)=FIFO.sub.m[0] stored in the FIFO memory 33-m (n=m) and comprising the most reliable auxiliary symbol.

(122) Accordingly, at the first iteration of the sorting process, the candidate elementary check node components B.sub.cand,1.sup.1, B.sub.cand,2.sup.1, . . . , B.sub.cand,n.sub.p.sup.1 are sorted according to a decreasing reliability of the candidate symbols corresponding to an increasing or decreasing order of the reliability metrics B.sub.cand,m.sup.1,+ for m=1, . . . , n.sub.p.

(123) Each candidate elementary check node component B.sub.cand,m.sup.it is assigned a FIFO number index B.sub.cand,m.sup.it,FNI, the FIFO memory number index corresponding to the number of the FIFO memory in which the candidate elementary check node component was stored.

(124) For each next iteration it=2, . . . , n.sub.IT, each multiplexer 34-m may be configured to: receive an auxiliary component denoted by B.sub.aux.sup.it=(B.sub.aux.sup.it,⊕, B.sub.aux.sup.it,+, B.sub.aux.sup.it,FNI) extracted from a candidate FIFO memory 33-n, the candidate FIFO memory being assigned as a FIFO number index the FIFO number index B.sub.cand,1.sup.it−1,FNI comprised in the candidate elementary check node component B.sub.cand,min.sup.it−1=B.sub.cand,1.sup.it−1, as determined at a previous iteration and comprising the most reliable candidate symbol. This means that the auxiliary component extracted at iteration it corresponds to the next component stored in the FIFO memory 33-n of a FIFO number index the FIFO number index B.sub.cand,1.sup.it−1,FNI and may be extracted using the pull operation of FIFO memories such that the pull operation (i.e. Pull.sub.n=1) is performed at the candidate FIFO memory 33-n assigned the FIFO number index n=B.sub.cand,1.sup.it−1,FNI; update the candidate elementary check node component B.sub.cand,m.sup.it by performing a control action for selecting a component among the received auxiliary component B.sub.aux.sup.it, and the candidate elementary check node components B.sub.cand,m.sup.it−1 and B.sub.cand,m+1.sup.it−1 determined at a previous iteration by the multiplexer 34-m and the multiplexer 34-(m+1).

(125) The processing of an auxiliary component at each iteration of the sorting process provides, at each iteration, n.sub.p candidate elementary check node components B.sub.cand,1.sup.it, B.sub.cand,2.sup.it, . . . , B.sub.cand,n.sub.p.sup.it, ordered according to a given order of the candidate reliability metrics such that: the candidate elementary check node component comprising the most reliable candidate symbol is the candidate elementary check node component B.sub.cand,1.sup.it also denoted by B.sub.cand,min.sup.it=(B.sub.cand,min.sup.it,⊕, B.sub.cand,min.sup.it,+, B.sub.cand,m.sup.it,FNI), and that each m.sup.th candidate elementary check node component B.sub.cand,m.sup.it comprises a candidate symbol B.sub.cand,m.sup.it,⊕ that is more reliable than the candidate symbol B.sub.cand,m+1.sup.it,⊕ comprised in the (m+1).sup.th candidate elementary check node component B.sub.cand,m+1.sup.it.

(126) In other words, for a decreasing (respectively increasing) order of the reliability metrics, the candidate elementary check node components determined at each iteration satisfy B.sub.cand,m.sup.it,+≤B.sub.cand,m+1.sup.it,+ (respectively B.sub.cand,m.sup.it,+≥B.sub.cand,m+1.sup.it,+) for m=1, . . . , n.sub.p−1.

(127) The sorting device may be configured to determine the elementary check node components E[e] for e=0, . . . , n.sub.E−1 by generating and/or selecting, at each iteration of a total of n.sub.IT=n.sub.E iterations, the candidate elementary check node component B.sub.cand,min.sup.it=B.sub.cand,1.sup.it comprising the most reliable candidate symbol.

(128) After the generation of the candidate elementary check node component B.sub.cand,1.sup.it comprising the most reliable candidate symbol at the it.sup.th iteration, the sorting device may be configured to determine the candidate FIFO memory to be used in the next iteration for the extraction of an auxiliary component. The candidate FIFO memory corresponds to the FIFO memory 33-n from which the selected candidate elementary check node component B.sub.cand,1.sup.it comprising the most reliable candidate symbol at the it.sup.th iteration originates. Accordingly, the sorting device may be further configured to determine an updated component index from the component index assigned to the selected candidate elementary check node component B.sub.cand,1.sup.it comprising the most reliable candidate symbol at the it.sup.th iteration, for example by incrementing by one (‘1’) the component index assigned to the selected candidate elementary check node component B.sub.cand,1.sup.it. The auxiliary component to be processed at the next iteration of the sorting process thus corresponds to the auxiliary component stored in the candidate FIFO memory and assigned with the updated component index.

(129) At the end of the processing/sorting of at least n.sub.E auxiliary components, the elementary check node message E is constructed from the selected candidate elementary check node components at the different iterations it=1, . . . , n.sub.E such that:

(130) $E=\left[\begin{array}{c}{B}_{\mathrm{cand},\min }^1\\ B_{\mathrm{cand},\min }^2\\ \mathrm{.Math.}\\ B_{\mathrm{cand},\min }^{n_E}\end{array}\right]=\left[\begin{array}{c}{B}_{c\mathrm{and},1}^1\\ B_{c\mathrm{and},1}^2\\ \mathrm{.Math.}\\ B_{c\mathrm{and},1}^{n_E}\end{array}\right].$

(131) The sorting device may further comprise a plurality n.sub.comp of reliability metrics comparators 36-m with m=1, . . . , n.sub.p. Each multiplexer 34-m for m=1, . . . , n.sub.p may be associated with a reliability metrics comparator 36-m configured to perform a reliability metrics comparison between the auxiliary reliability metrics B.sub.aux.sup.it,+ comprised in the received auxiliary component B.sub.aux.sup.it and the candidate reliability metrics B.sub.cand,m.sup.it−1,+ comprised in the candidate elementary check node component B.sub.cand,m.sup.it−1, as determined by the multiplexer 34-m at a previous iteration. Each multiplexer 34-m may be configured to perform at each iteration a control action for selecting a component among the received auxiliary component and the candidate elementary check node components, determined at a previous iteration by the multiplexer 34-m and the multiplexer 34-m+1, depending on the comparison performed by the reliability metrics comparator 36-m associated with said multiplexer 34-m and the comparison performed by the reliability metrics comparator 36-(m+1) associated with the multiplexer 36-(m+1).

(132) In to some embodiments, the control action performed by the multiplexer 34-m may be for example a keeping action, an insertion action, or a shift action. However, the skilled person will readily understand that other control actions may be performed.

(133) For example, at each iteration it=2, . . . , n.sub.IT, each multiplexer 34-m may be configured to: perform a keeping action by setting the candidate elementary check node component B.sub.cand,m.sup.it to the candidate elementary check node component B.sub.cand,m.sup.it−1 determined by the multiplexer 34-m at a previous iteration if it is determined that the auxiliary symbol B.sub.aux.sup.it,⊕ comprised in the received auxiliary component B.sub.aux.sup.it at the it.sup.th iteration is more reliable than the candidate symbol B.sub.cand,m.sup.it−1,⊕ comprised in the candidate elementary check node component B.sub.cand,m.sup.it−1 determined at the previous iteration by the multiplexer 34-m. According to the keeping action, the multiplexer 34-m may keep the candidate elementary check node component previously selected during the previous iteration as the candidate elementary check node component for the current iteration. Accordingly, the following equalities may be satisfied: B.sub.cand,m.sup.it,⊕=B.sub.cand,m.sup.it−1,⊕, B.sub.cand,m.sup.it,+=B.sub.cand,m.sup.it−1,+, and B.sub.cand,m.sup.it,FNI=B.sub.cand,m.sup.it−1,FNI; perform an insertion action by setting the candidate elementary check node component B.sub.cand,m.sup.it to the received auxiliary component B.sub.aux.sup.it if it is determined that the auxiliary symbol B.sub.aux.sup.it,⊕ comprised in the auxiliary component is less reliable than the candidate symbol B.sub.cand,m.sup.it−1,⊕ comprised in the candidate elementary check node component B.sub.cand,m.sup.it−1 determined by the multiplexer 34-m at a previous iteration and that the auxiliary symbol B.sub.aux.sup.it,⊕ is more reliable than the candidate symbol B.sub.cand,m+1.sup.it−1,⊕ comprised in the candidate elementary check node component B.sub.cand,m+1.sup.it−1 determined by the multiplexer 34-(m+1) at a previous iteration. According to the insertion action: B.sub.cand,m.sup.it,⊕=B.sub.aux.sup.it,⊕, B.sub.cand,m.sup.it,+=B.sub.aux.sup.it,+, and B.sub.cand,m.sup.it,FNI=B.sub.aux.sup.it,FNI; perform a shift action by setting the candidate elementary check node component B.sub.cand,m.sup.it to the candidate elementary check node component B.sub.cand,m+1.sup.it−1 determined by the multiplexer 34-(m+1) at a previous iteration if it is determined that the auxiliary symbol comprised in the received auxiliary component is less reliable than the candidate symbol comprised in the candidate elementary check node component B.sub.cand,m+1.sup.it−1 determined by the multiplexer 315-(m+1) at a previous iteration. According to the shift action: B.sub.cand,m.sup.it,⊕=B.sub.cand,m+1.sup.it−1,⊕, B.sub.cand,m.sup.it,+=B.sub.cand,m+1.sup.it−1,+, and B.sub.cand,m.sup.it,FNI=B.sub.cand,m+1.sup.it−1,FNI.

(134) The control actions performed by each multiplexer 34-m may depend on the results of the reliability metrics comparisons performed by the reliability metrics comparator 36-m, associated with the multiplexer 34-m, and the reliability metrics comparator 36-(m+1) associated with the multiplexer 34-(m+1), the right-side neighbor multiplexer to the multiplexer 34-m. Given that the multiplexer 34-n.sub.p is the last multiplexer and does not have a right-side neighbor multiplexer, it is assumed that the reliability metrics comparison involving the candidate elementary check node component B.sub.cand,m+1.sup.it−1 when m=n.sub.p uses a candidate component B.sub.cst comprising a constant symbol and a constant value of the reliability metrics. Such constant value of the reliability metrics makes the result of any reliability metrics comparison between the auxiliary symbol B.sub.aux.sup.it,⊕ and the constant reliability metrics always constant such that the candidate component B.sub.cst is less reliable than the auxiliary symbol B.sub.aux.sup.it,⊕.

(135) Referring to FIG. 5, a sorting method for determining elementary check node components in an elementary check node processor implemented in a non-binary error correcting code decoder is shown. The method comprises calculating auxiliary components from a first message and from a second message derived from variable node messages and sorting said auxiliary components during a number n.sub.IT=n.sub.E of iterations, an auxiliary component comprising an auxiliary symbol, an auxiliary reliability metrics, and a FIFO number index.

(136) Accordingly, at step 501, a first message denoted by X and a second message denoted by Y derived from three or more variable node messages U.sub.1, . . . , U.sub.d.sub.cn may be received.

(137) According to some embodiments, the first message X may comprise a first given number n.sub.X of components denoted by X[x] for x=0, . . . , n.sub.X−1 and the second message Y may comprise a second given number n.sub.Y of components Y[y] for y=0, . . . , n.sub.Y−1.

(138) According to some embodiments, the first message and the second message may comprise a same number of components, according to which the first given number and the second given number may be equal, i.e. n.sub.X=n.sub.Y.

(139) In other embodiments, the first message and the second message comprise a different number of components, according to which the first given number and the second given number may be different, i.e. n.sub.X≠n.sub.Y.

(140) At step 503, a predefined number n.sub.B of auxiliary components designated by B.sub.t[x][y]=(B.sub.t[x][y].sup.⊕, B.sub.t[x][y].sup.+) for t=1, . . . , n.sub.B may be determined from the first message X and the second message Y. More specifically, the auxiliary component B.sub.t[x][y]=(B.sub.t[x][y].sup.⊕, B.sub.t[x][y].sup.+) for t=1, . . . , n.sub.B refers to the auxiliary component determined from the component X[x]=(X[x].sup.⊕, X[x].sup.+) comprised in the first message X and from the component Y[y]=[y].sup.⊕, Y[y].sup.+) comprised in the second message, the index x varying in 0,1, . . . , n.sub.X−1 and the index y varying in 0,1, . . . , n.sub.Y−1. The auxiliary component B.sub.t[x][y]=(B.sub.t[x][y].sup.⊕, B.sub.t[x][y].sup.+) may be a component comprising: an auxiliary symbol designated by B.sub.t[x][y].sup.⊕, and an auxiliary reliability metrics designated by B.sub.t[x][y].sup.+ associated with said auxiliary symbol.

(141) According to some embodiments, step 503 may comprise: determining the auxiliary symbol B.sub.t[x][y].sup.⊕ comprised in each auxiliary component B.sub.t[x][y] for t=1, . . . , n.sub.B by applying a first addition operation over the algebraic structure of construction of the non-binary error correcting code, the first addition operation being applied to a symbol X[x].sup.⊕ comprised in a component X[x]=(X[x].sup.⊕, X[x].sup.+) of the first message X and a symbol Y[y].sup.⊕ comprised in a component Y[y] of the second message Y according equation (4), and determining the auxiliary reliability metrics B.sub.t[x][y].sup.+ associated with each auxiliary symbol B.sub.t[x][y].sup.⊕ by applying a second addition operation over a predefined algebraic structure, the second addition operation being applied to a reliability metrics X[x].sup.+ associated with a symbol X[x].sup.⊕ comprised in a component X[x] of the first message X and a reliability metrics Y[y].sup.+ associated with a symbol Y[y].sup.⊕ comprised in a component Y[y] of the second message Y according to equation (5).

(142) According to some embodiments, the predefined algebraic structure over which the second addition operation is performed is chosen in a group comprising the field of real numbers, the field of integer numbers, and the field of natural numbers.

(143) According to some embodiments, the number n.sub.B of auxiliary components may be determined depending on at least one parameter chosen in a group comprising the number of iterations N.sub.iter of the variable node and check node messages exchange between, the algebraic structure of construction of the non-binary error correcting code (for example the Galois field for codes constructed over Galois fields), a signal-to-noise ratio, one or both of the first predefined number of components n.sub.X of the first message X and the second predefined number of components n.sub.Y of the second message Y, and the position of the elementary check node processor within the check node processing unit.

(144) The determined auxiliary components may be grouped into a plurality of n.sub.p paths denoted by Path.sub.1, . . . , Path.sub.n.sub.p such that each path Path.sub.n=(Path.sub.n[0], . . . , Path.sub.n[N.sub.n−1]) for n=1, . . . , n.sub.p comprises at least one auxiliary component denoted by Path.sub.n[g]=(Path.sub.n.sup.⊕[g], Path.sub.n.sup.+[g]) for g=0, . . . , N.sub.n−1.

(145) The auxiliary components may be grouped into the paths, according to a decreasing reliability of the auxiliary symbols such that: the auxiliary components comprised in each path of index n are sorted according to a decreasing reliability of the auxiliary symbols satisfying Path.sub.n.sup.+[g]≤Path.sub.n.sup.+[g+1] for g=0, . . . , N.sub.n−1, and the auxiliary components comprising the most reliable auxiliary symbol of each path are sorted according to a decreasing reliability of the auxiliary symbols such that Path.sub.1.sup.+[0]≤Path.sub.2.sup.+[0]≤ . . . ≤Path.sub.n.sub.p.sup.+[0].

(146) At step 507, the auxiliary components of each path Path.sub.n may be stored in a FIFO memory 33-n for n=1, . . . , n.sub.p, each FIFO memory 33-n being assigned a FIFO number index FNI given by the index n varying between 1 and n.sub.p and the auxiliary components stored in each FIFO memory 33-n further comprising the FIFO number index assigned to the FIFO memory 33-n in which they are stored.

(147) Steps 509 to 525 may be performed to determine n.sub.E elementary check node components E[e]=(E[e].sup.⊕, E[e].sup.+) for e=0, . . . , n.sub.E−1 of an elementary check node message E from the n.sub.B auxiliary components stored in the different FIFO memories by performing n.sub.IT=n.sub.E iterations.

(148) According to some embodiments, each elementary check node component E[e] may comprise a symbol E[e].sup.⊕ and a reliability metrics E[e].sup.+ associated with said symbol, the elementary check node components being sorted according to a given order of the reliability metrics E[e].sup.+ such that E[e].sup.+≤E[e+1].sup.+ for e=0, . . . , n.sub.E−2 and the elementary check node component comprising the most reliable symbol is E[0]=(E[0].sup.⊕, E[0].sup.+).

(149) In one embodiment, an iteration may correspond to a clock cycle.

(150) Each iteration of the iterative sorting may provide n.sub.p candidate elementary check node components B.sub.cand,m.sup.it=(B.sub.cand,m.sup.it,⊕, B.sub.cand,m.sup.it,+, B.sub.cand,m.sup.it,FNI) for m=1, . . . , n.sub.p depending on comparisons performed between the auxiliary reliability metrics, comprised in an auxiliary component extracted from the n.sub.B auxiliary components stored in the FIFO memories and the candidate reliability metrics comprised in the candidate elementary check node components determined at the previous iteration. The candidate elementary check node components B.sub.cand,1.sup.it, B.sub.cand,2.sup.it, . . . , B.sub.cand,n.sub.E.sup.it may be ordered according to a given order of the candidate reliability metrics such that: the candidate elementary check node component comprising the most reliable candidate symbol is the candidate elementary check node component B.sub.cand,1.sup.it=B.sub.cand,min.sup.it, and that the m.sup.th candidate elementary check node component B.sub.cand,m.sup.it comprises a candidate symbol B.sub.cand,m.sup.it,⊕ that is more reliable than the candidate symbol B.sub.cand,m+1.sup.it,⊕ comprised in the (m+1).sup.th candidate elementary check node component B.sub.cand,m+1.sup.it.

(151) Depending on the comparisons results, control actions may be decided and performed, at each iteration, to determine candidate elementary check node components by updating the candidate components previously determined at the previous iteration.

(152) The control action may be for example a keeping action, an insertion action, or a shift action.

(153) At step 509, an initialization of the number of iterations of the iterative sorting process may be performed according to it=1. In embodiments in which an iteration is performed during a clock cycle, the number of iterations of the sorting process may correspond to the sorting processing time period i.e. the latency in terms of the number of clock cycles.

(154) At step 509, initialization actions may be performed at the first iteration (it=1) of the iterative sorting process. The initialization actions may consist in setting the candidate elementary check node components B.sub.cand,m.sup.1 to the auxiliary component B.sub.m(0)=FIFO.sub.m[0] stored in the FIFO memory 33-m (n=m) and comprising the most reliable auxiliary symbol, the candidate elementary check node components B.sub.cand,1.sup.1, B.sub.cand,2.sup.1, . . . , B.sub.cand,n.sub.p.sup.1 being sorted according to a decreasing reliability of the candidate symbols corresponding to an increasing or decreasing order of the reliability metrics B.sub.cand,m.sup.1,+ for m=1, . . . , n.sub.p.

(155) At step 511, the number of the iterations of the sorting process may be incremented.

(156) At step 513, the generation of the n.sub.E elementary check node components may be controlled by checking if the number of iterations of the sorting process it reached n.sub.E.

(157) If it is determined at step 513 that it=n.sub.E, this means that the desired number n.sub.E of elementary check node components has been determined. Thus, at step 527, the sorting process may be stopped and the n.sub.E elementary check node components may be delivered as the selected candidate elementary check node components B.sub.cand,min.sup.it=B.sub.cand,1.sup.it selected at each iteration for it=1, . . . , n.sub.E such that:

(158) $E=\left[\begin{array}{c}{B}_{\mathrm{cand},\min }^1\\ B_{\mathrm{cand},\min }^2\\ \mathrm{.Math.}\\ B_{\mathrm{cand},\min }^{n_E}\end{array}\right]=\left[\begin{array}{c}{B}_{c\mathrm{and},1}^1\\ B_{c\mathrm{and},1}^2\\ \mathrm{.Math.}\\ B_{\mathrm{cand},1}^{n_E}\end{array}\right]$

(159) If it is determined at step 513 that it≠n.sub.E, and more specifically that Δ<n.sub.E, this means that the desired number of elementary check node components is not determined. Steps 515 to 525 may be performed to determine n.sub.E elementary check node components.

(160) At step 515, a candidate FIFO memory may be determined, the candidate FIFO memory being assigned as a FIFO number index the FIFO number index B.sub.cand,m.sup.it−1,FNI comprised in the candidate elementary check node component B.sub.cand,min.sup.it−1=B.sub.cand,1.sup.it−1, determined at a previous iteration and comprising the most reliable candidate symbol.

(161) At step 519, an auxiliary component may be extracted from the candidate FIFO memory determined at step 515, the auxiliary component being the auxiliary component in the candidate FIFO memory next to the candidate elementary check node component B.sub.cand,m.sup.it−1.

(162) At step 521, reliability metrics comparisons between the auxiliary reliability metrics B.sub.aux.sup.it,+, comprised in the received auxiliary component B.sub.aux.sup.it, and each of the candidate reliability metrics B.sub.cand,m.sup.it−1,+, comprised in the candidate elementary check node components B.sub.cand,m.sup.it−1 for m=1, . . . , n.sub.p, may be performed.

(163) At step 523, n.sub.p candidate elementary check node components B.sub.cand,m.sup.it, for m=1, . . . , n.sub.p, may be determined by performing control actions depending on the comparisons performed at step 521.

(164) At step 525, the updated candidate elementary check node component B.sub.cand,min.sup.it=B.sub.cand,1.sup.it comprising the most reliable candidate symbol may be selected and delivered.

(165) FIG. 6 is a flowchart illustrating the control actions performed at step 523 depending on the comparisons performed between the auxiliary reliability metrics, comprised in the received auxiliary component, and the reliability metrics, comprised in the candidate elementary check node components B.sub.cand,m.sup.it−1 for m=1, . . . , n.sub.p.

(166) At step 601, the candidate elementary check node component B.sub.cand,m.sup.it−1, the candidate elementary check node component B.sub.cand,m+1.sup.it−1, and the auxiliary component B.sub.aux.sup.it may be received.

(167) Control actions may be performed at steps 605, 609, and 611 to determine, in parallel, n.sub.p candidate elementary check node components B.sub.cand,m.sup.it depending on the results of the reliability metrics comparisons. More specifically, for each m=1, . . . , n.sub.p: a keeping action may be performed at step 601 by setting the candidate elementary check node component B.sub.cand,m.sup.it to the candidate elementary check node component B.sub.cand,m.sup.it−1 determined by the multiplexer 34-m at a previous iteration, if it is determined at step 603 that the auxiliary symbol B.sub.aux.sup.it,⊕ comprised in the received auxiliary component B.sub.aux.sup.it at the it.sup.th iteration is more reliable than the candidate symbol B.sub.cand,m.sup.it−1,⊕ comprised in the candidate elementary check node component B.sub.cand,m.sup.it−1 determined at the previous iteration by the multiplexer 315-m. According to the keeping action: B.sub.cand,m.sup.it,⊕=B.sub.cand,m.sup.it−1,⊕, B.sub.cand,m.sup.it,+=B.sub.cand,m.sup.it−1,+, and B.sub.cand,m.sup.it,FNI=B.sub.cand,m.sup.it−1,FNI; an insertion action may be performed at step 609 by setting the candidate elementary check node component B.sub.cand,m.sup.it to the received auxiliary component B.sub.aux.sup.it if it is determined at step 603 that the auxiliary symbol comprised in the auxiliary component is less reliable than the candidate symbol B.sub.cand,m.sup.it−1,⊕ comprised in the candidate elementary check node component B.sub.cand,m.sup.it−1 determined at a previous iteration and that it is determined at step 607 that the auxiliary symbol B.sub.aux.sup.it,⊕ is more reliable than the candidate symbol B.sub.cand,m+1.sup.it−1,⊕ comprised in the candidate elementary check node component B.sub.cand,m+1.sup.it−1 determined at a previous iteration. According to the insertion action: B.sub.cand,m.sup.it,⊕=B.sub.aux.sup.it,⊕, B.sub.cand,m.sup.it,+=B.sub.aux.sup.it,+, B.sub.cand,m.sup.it,FNI=B.sub.aux.sup.it,FNI; a shift action may be performed at step 611 by setting the candidate elementary check node component B.sub.cand,m.sup.it to the candidate elementary check node component B.sub.cand,m+1.sup.it−1 determined at a previous iteration if it is determined at step 607 that the auxiliary symbol comprised in the received auxiliary component is less reliable than the candidate symbol comprised in the candidate elementary check node component B.sub.cand,m+1.sup.it−1 determined at a previous iteration. According to the shift action: B.sub.cand,m.sup.it,⊕=B.sub.cand,m+1.sup.it−1,⊕, B.sub.cand,m.sup.it,+=B.sub.cand,m+1.sup.it−1,+, and B.sub.cand,m.sup.it,FNI=B.sub.cand,m+1.sup.it−1,FNI.

(168) It should be noted that it is assumed that the comparison of step 607 has a constant ‘Yes’ result when performed for m=n.sub.p considering a constant candidate component B.sub.cand,n.sub.p.sub.+1.sup.it−1=B.sub.cst comprising a constant symbol and a constant reliability metrics such that the constant candidate component is always less reliable than any auxiliary symbol B.sub.aux.sup.it,⊕.

(169) The methods and devices described herein may be implemented by various means. For example, these techniques may be implemented in hardware, software, or a combination thereof. For a hardware implementation, the processing elements of an iterative decoder 123 can be implemented for instance according to a hardware-only configuration (as example, in one or more FPGA, ASIC or VLSI integrated circuits with the corresponding memory) or according to a configuration using both VLSI and DSP.

(170) While embodiments of the disclosure have been illustrated by a description of various examples, and while these embodiments have been described in considerable detail, it is not the intent of the applicant to restrict or in any way limit the scope of the appended claims to such details.

(171) In particular, while the description of some embodiments of the disclosure has been performed with reference to a particular implementation of the EMS algorithm, it should be noted that the disclosure may be also applied to other iterative decoding algorithms such as the min-max algorithm.

(172) Furthermore, while some embodiments of the disclosure have been described with reference to error correcting codes constructed over Galois Fields, the skilled person will readily understand that the proposed embodiments may be also applied to any non-binary LDPC codes and any non-binary graph error correcting code constructed over non-commutative groups such as polynomial codes (e.g. cyclic codes).

(173) Further, even if the disclosure has some advantages in an application to communication systems, it should be noted that the disclosure is not limited to such communication devices and may be integrated in numerous devices such as data storage devices.

(174) The methods described herein can be implemented by computer program instructions supplied to the processor of any type of computer to produce a machine with a processor that executes the instructions to implement the functions/acts specified herein. These computer program instructions may also be stored in a computer-readable medium that can direct a computer to function in a particular manner. To that end, the computer program instructions may be loaded onto a computer to cause the performance of a series of operational steps and thereby produce a computer implemented process such that the executed instructions provide processes for implementing the functions specified herein.