Elementary check node processing for syndrome computation for non-binary LDPC codes decoding
10560120 · 2020-02-11
Assignee
Inventors
Cpc classification
H03M13/1171
ELECTRICITY
International classification
Abstract
At least a method and an apparatus are presented to decode a signal encoded using an error correcting code. For example, a decoder comprising a check node processing unit is presented. The check node processing unit is configured to receive at least three input messages and to generate at least one output message. A syndrome calculator is configured to determine a set of syndromes from the at least three input messages using at least two elementary check node processors. A decorrelation unit is configured to determine, in association with at least an output message, a set of candidate components from the set of syndromes. A selection unit is configured to determine at least an output message by selecting components comprising distinct symbols from the set of candidate components associated with the at least an output message.
Claims
1. A decoder for decoding a signal encoded using an error correcting code, comprising: an input for receiving the encoded signal comprising at least three input message: a check node processing unit being configured to process the at least three input messages delivered by at least one variable node processing unit, and to generate at least one output message, wherein the check node processing unit comprises: a syndrome calculator configured to determine a set of syndromes from said at least three input messages using at least two elementary check node processors, each syndrome comprising a symbol, a reliability metric associated with said symbol, and a binary vector comprising at least one binary value; a decorrelation unit configured to determine, in association with at least an output message, a set of candidate components from said set of syndromes, each candidate component comprising a symbol and a reliability metric associated with said symbol, said set of candidate components comprising one or more pairs of components comprising a similar symbol; and a selection unit configured to determine at least an output message by selecting components comprising distinct symbols from the set of candidate components associated with said at least an output message; an output for outputting the decoded signal comprising said at least an output message.
2. The decoder of claim 1, wherein at least one elementary check node processor is configured to determine an intermediary message from a first message and a second message, said first message and second message being derived from said at least three input messages, said intermediary message comprising one or more components and an intermediary binary vector associated with each component, an intermediary binary vector comprising at least one binary value, each component comprising a symbol and a reliability metric associated with said symbol, said one or more components being sorted into a given order of the reliability metrics of symbols, the syndrome calculator being configured to determine said set of syndromes from the intermediary message determined from all input messages.
3. The decoder of claim 1, wherein each message from said at least three input messages comprises one or more components, each component comprising a symbol and a reliability metric associated with said symbol, at least one elementary check node processor being configured to determine the symbol comprised in a component of said intermediary message by applying an addition operation over a field of construction of said at least one error correcting code, said addition operation being applied to the symbol comprised in a component of said first message and to the symbol comprised in a component of said second message.
4. The decoder of claim 1, wherein at least one elementary check node processor is configured to determine the reliability metric comprised in a component of said intermediary message by applying an addition operation over a given algebraic structure, said addition operation being applied to the reliability metric comprised in a component of said first message and to the reliability metric comprised in a component of said second message, said algebraic structure being chosen in a group consisting of the field of real numbers, the field of integer numbers, and the field of natural numbers.
5. The decoder of claim 4, wherein the syndrome calculator is further configured to associate each component comprised in said at least three input messages with an initial binary value, each component of said first message and said second message being associated with a binary vector comprising at least one binary valve derived from said initial binary values, at least one elementary check node processor being configured to determine the intermediary binary vector associated with a component of said intermediary message by applying a vector concatenation operation, said vector concatenation operation being applied to the binary vector associated with a component of said first message and to the binary vector associated with a component of said second message.
6. The decoder of claim 5, wherein the components comprised in each input message are sorted in a given order of the reliability metrics of the symbols comprised in said components, the syndrome calculator being configured to associate the component comprising the most reliable symbol with an initial binary value equal to a predefined first value and to associate the remaining components with an initial binary value equal to a predefined second value.
7. The decoder of claim 6, wherein said predefined first value is equal to zero and said predefined second value is equal to one.
8. The decoder of claim 7, wherein the binary vector comprised in each syndrome comprises a number of bits, each bit of said number of bits being associated with an output message, the decorrelation unit being configured to determine said set of candidate components associated with a given output message by selecting, among said set of syndromes, the syndromes that comprise binary vectors in which the bit associated with said given output message is equal to said predefined first value.
9. The decoder of claim 1, wherein said elementary check node processors are implemented in a serial architecture.
10. The decoder of claim 1, wherein said elementary check node processors are implemented in a tree architecture.
11. The decoder of claim 1, wherein said elementary check node processors are implemented in a hybrid architecture comprising some elementary check node processors implemented in a serial architecture and some elementary check node processors implemented in a tree architecture.
12. The decoder of claim 1, wherein said selection unit is configured to determine at least an output message by selecting a predefined number of components comprising distinct symbols from the set of candidate components associated with said at least an output message depending on the reliability metrics of the symbols in said set of candidate components.
13. The decoder of claim 1, wherein said at least one error correcting code is a non-binary error correcting code.
14. A method performed by a decoder for decoding a signal encoded using an error correcting code, comprising: receiving the encoded signal comprising at least three input messages delivered by at least one variable node processing unit; calculating at least one output message at a check node processing unit implemented in said decoder; determining a set of syndromes from said at least three input messages, each syndrome comprising a symbol, a reliability metric associated with said symbol, and a binary vector comprising at least one binary value; determining, in association with at least an output message, a set of candidate components from said set of syndromes, each candidate component comprising a symbol and a reliability metric associated with said symbol, said set of candidate components comprising one or more pairs of components comprising a similar symbol; determining at least an output message by selecting components comprising distinct symbols from the set of candidate components associated with said at least an output message; and outputting the decoded signal comprising said at least an output message.
15. A non-computer storage medium comprising computing instruction for calculating at least one output message at a check node processing unit implemented in a decoder, said decoder being configured to decode a signal encoded using an error correcting code, the check node processing unit being configured to receive at least three input messages delivered by at least one variable node processing unit, wherein the computing instructions when executed by a processor, cause the processor to: determine a set of syndromes from said at least three input messages, each syndrome comprising a symbol, a reliability metric associated with said symbol, and a binary vector comprising at least one binary value; determine, in association with at least an output message, a set of candidate components from said set of syndromes, each candidate component comprising a symbol and a reliability metric associated with said symbol, said set of candidate components comprising one or more pairs of components comprising a similar symbol; determine at least an output message by selecting components comprising distinct symbols from the set of candidate components associated with said at least an output message; and output the decoded signal comprising said at least an output message.
Description
BRIEF DESCRIPTION OF THE 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)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
(11)
(12)
(13)
(14)
(15)
DETAILED DESCRIPTION
(16) Embodiments of the present invention provide devices, methods, and computer program products for decoding a signal that was encoded using an error correcting code, with a reduced computational complexity. In particular, the various embodiments provide improved architectures of check node processing units implemented in iterative decoding algorithms used to decode a signal that was encoded using a non-binary error correcting code.
(17) Methods, devices and computer program products according to the various embodiments may be implemented in various types of digital data transmission and storage systems and can be used in different types of applications, such as for example wired, wireless and optical communications, solid state data storage, magnetic and optical recording, digital television and video broadcasting.
(18) The following description of some embodiments of the invention will be made with reference to digital communication systems, for illustration purpose only. However, the skilled person will readily understand that the various embodiments of the invention may be integrated in other types of systems (e.g. wired, wireless, acoustic, optical, and molecular systems, etc.).
(19) Further, the following description of some embodiments of the invention will be made with reference to linear block error correcting codes, for illustration purpose only, although the skilled person will readily understand that the various embodiments of the invention may apply to any type of linear codes (comprising convolutional codes) and more generally to any type of error correcting codes.
(20) Referring to
(21) According to some embodiments of the invention, the transmitter 10 may comprise an error correcting code (ECC) encoder 103, configured to encode a digital input data block 101 denoted by u using a linear block error correcting code into a codeword c. The receiver 12 may be configured to receive a noisy copy p of the encoded data, or codeword, 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.
(22) The digital input data 101 may be previously compressed before being encoded by the ECC encoder 103. Any source coding scheme (not shown in
(23) The receiver 12 may comprise homologous processing means configured to perform the reverse functions. It 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
(24) In an application of the invention to wired communication systems such as computer networking systems, the transmitter 10 and/or the receiver 12 may be any device configured to operate in a wired network. Exemplary devices in such application comprise computers, routers or switches connected to a small or large area wired network. Further, in such an application, the transmission channel 11 may be any type of physical cable used to ensure the transfer of data between the different connected devices.
(25) In another application of the invention to wireless communication systems such as ad-hoc wireless networks, wireless sensor networks and radio communication systems, the transmitter 10 and/or the receiver 12 may be any type of fixed or mobile wireless device configured to operate in a wireless environment. Exemplary devices adapted for such application comprise laptops, tablets, mobile phones, robots, IoT devices, base stations, etc. The transmission channel 11 may be any wireless propagation medium suitable for this type of application. Further, the transmission channel 11 may accommodate several transmitters 10 and 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).
(26) In still another application of the invention to optical communication systems such as optical fiber-based systems, the transmitter 10 and the receiver 12 may be any optical transceiver device configured to respectively transmit and receive data information propagated over an optical link. Exemplary optical communication systems comprise Polarization Division Multiplexing (PMD) and Mode Division Multiplexing (MDM) systems.
(27) For any type of wired (e.g. optical fiber-based), wireless or deep-space (e.g. satellites, telescopes, space probes, etc.) 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 intercepted interfering radiation 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).
(28) Further, according to yet another application of the invention 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 application, the transmission channel 11 may be any type of storage device which can be sent to (i.e. written) and received from (i.e. read).
(29) 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.
(30) 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 (Orthogonal Frequency Division Multiplexing) and FBMC (Filter Bank Multi-Carrier).
(31) According to various embodiments, the ECC encoder 103 may implement a linear block error correcting code designated by (n, k); n and k referring respectively to the length of codewords and the length of an encoded data block. The ECC encoder 103 encodes accordingly a message vector u of length k into a codeword c, c being a vector of length n. The codeword c therefore comprises n elements, also referred to as symbols. Among the n symbols, nk symbols correspond to redundancy symbols, also called parity symbols. The function of the extra parity symbols is to allow the receiver 12 to detect and possibly correct any error that occurred during the transmission.
(32) For linear codes constructed over Galois Fields, generally denoted by GF(q), where q2 designates the cardinality of the code, the symbols take values in GF(q). A codeword c is thus a vector of n symbols that each belong to GF(q). The code is binary if the symbols belong to GF(2). In contrast, when q>2, the code is qualified as non-binary.
(33) A linear code (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 kn while the parity-check matrix is of dimensions (nk)n. The two matrices are linked by the relation G. H.sup.t=0. In addition, entries of both matrices belong to the corresponding Galois Field. Using the matrix representation, any codeword c satisfies the equation c. H.sup.t=0. This equation is also called parity-check equation. It defines n parity-check constraints designed to be satisfied by any codeword.
(34) In association with the matrix representation, the linear code (n, k) may be represented using a bipartite graph
termed Tanner graph. This graph comprises n variable nodes and nk check nodes. Each variable node i {1,2, . . . , n} is associated with a column of the parity-check matrix. Each check node j {1,2, . . . , nk} is associated with a row of the parity-check matrix, i.e. with a parity-check equation. A variable node i is connected to a check node j if the entry H.sub.ij of the parity-check matrix is not equal to zero, i.e. if H.sub.ij0.
.sub.v(i) denotes the set of neighbor check nodes connected to the variable node i. Similarly,
.sub.c(j) denotes the set of neighbor variable nodes connected to the check node j. The degree of a variable node i (equivalently a check node j) corresponds to the cardinality of the set
.sub.v(i) (equivalently the cardinality of the set
.sub.c(j)).
(35) 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 purpose only. However, the skilled person will readily understand that the various embodiments of the invention also apply to other non-binary codes and in general to binary and non-binary linear block error correcting codes and non-binary turbo codes.
(36) For the purpose of example, the ECC decoder 123 implements a non-binary LDPC code decoder for decoding the data encoded by the ECC encoder 103 using a non-binary LDPC code. The ECC decoder 123 may implement any iterative non-binary LDPC code decoder such as the Extended Min Sum algorithm or the min-max algorithm.
(37) According to a particular application to the EMS algorithm, the various embodiments of the invention provide efficient and low-complexity implementations of check node processing units involved in the iterative decoding process using an EMS algorithm. The description of the invention 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 decoding algorithm.
(38) Referring to
(39) 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 y. It may process a signal over several iterations bringing it, at each iteration, closer to the transmitted codeword c.
(40) The iterative decoder 123 may be configured to determine the estimate based on the Tanner graph representation of the code (n, k) used at the transmitter 10. Accordingly, the iterative decoder 123 may comprise n variable node processing units 217 and nk check node processing units 215. Each variable node processing unit 217 maps to one variable node in the Tanner graph. Each check node processing unit 215 maps to one check node in the Tanner graph. The variable node processing units 217 and check node processing units 215 may be configured to iteratively exchange messages to estimate the most reliable codeword from the noisy sequence y.
(41) A variable node processing unit 217 corresponding to a variable node i may be configured to receive input messages from the check node processing units 215 of the set .sub.v(i). A variable node processing unit 217 may be further configured to process these input messages and deliver output messages to at least one check node processing unit 215 of the set
.sub.v(i).
(42) Similarly, a check node processing unit 215 corresponding to a check node j may be configured to receive input messages from the variable node processing units 217 of the set .sub.c(j) . A check node processing unit 215 may be further configured to process these input messages and deliver output messages to at least one variable node processing unit 217 of the set
.sub.c(j).
(43) The processing performed by the various variable node processing units and check node processing units may be implemented according to several scheduling techniques.
(44) According to a first implementation, all variable node processing units 217 may be configured to operate in a first round and then the check node processing units 215 may be configured to update the messages to be sent to the variable nodes. This specific scheduling is known as flooding scheduling. In particular, the check node processing units 215 may be configured to operate serially or in parallel where from 2 to nk check node processing units 215 may operate at the same time.
(45) According to a second implementation based on a horizontal scheduling, the check node processing units 215 may be configured to operate serially, updating all variable node processing units 217 connected to the check node processing units 215. In particular, a group of check node processing units 215 may be configured to operate in parallel, updating all connected variable node processing units 217 provided that there is no variable node processing unit 217 in conflict (e.g. when two check node processing units 215 are connected to the same variable node processing unit 217).
(46) According to a third implementation based on a vertical scheduling, the variable node processing units 217 may be configured to operate serially, updating all check node processing units 215 which are connected to them.
(47) The exchange of messages may be initialized by the variable node processing units 217. It may terminate either if the processed signal satisfies the parity-check equation or if a maximum number of iterations is reached without meeting all parity-check constraints. In the former case (if the processed signal satisfies the parity-check equation), the iterative decoder 123 may be configured to deliver the processed signal as an estimate of the original codeword. In the latter case (if a maximum number of iterations is reached without meeting all parity-check constraints), the iterative decoder 123 may be configured to declare a decoding failure but nevertheless output the codeword estimated at the last iteration.
(48) As illustrated in
(49) The exchanged messages between the variable node processing units 217 and the check node processing units 215 may carry information associated with the symbols. A message sent from a variable node processing unit 217, corresponding to a variable node i, to a check node processing unit 215, corresponding to a check node j, in the set .sub.v(i) is denoted by U.sub.i. Similarly, a message sent from a check node processing unit 215 corresponding to a check node j to a variable node processing unit 217 corresponding to a variable node i in the set
.sub.c(j) is denoted by V.sub.i.
(50) According to some embodiments, the length of an exchanged message may be equal to the order of the Galois field used to construct the linear code. Accordingly, each exchanged message U.sub.i and V.sub.i may be a vector of length q for codes constructed over GF(q).
(51) In other embodiments related to soft-decision decoding, exchanged messages may carry the values of the symbols and metrics measuring their reliabilities (hereinafter referred to as reliability metrics). The value of the reliability metric is related to the reliability of the symbol. In such embodiments, each message U.sub.L and V.sub.i may be a vector comprising q couples of values (hereinafter referred to as components), a component comprising a value of a symbol and its reliability metric. Each component of a message accordingly corresponds to a couple of values including: a value of the symbols in GF(q), and its reliability metric.
(52) In some embodiments, the reliability metric 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 metric may be represented in the log-domain by a logarithmic likelihood ratio (LLR) value.
(53) The computational complexity of the decoding process is dominated by the computations performed by the check node processing units 215. In one embodiment using the EMS algorithm for decoding non-binary LDPC codes, the computational complexity of the processing performed by the check node processing units 215 may be reduced without sacrificing the decoding error performance.
(54) Referring to
(55) To facilitate the understanding of the following description of some embodiments, a focus on the processing at a check node processing unit with a notation at the level of the check node processing unit will be used. Accordingly, the check node processing unit 215 depicted in
(56) According to some embodiments using the EMS algorithm, the messages delivered to check node processing units 215 may be sorted and truncated so as to keep only the n.sub.m,in most reliable components, with n.sub.m,in being strictly lower than q(.sub.m,in<<q). The sorting may be performed in a given order (for example by increasing or decreasing order) of the reliability metrics associated with the symbols. Further, the sorting and truncation operations may be performed by the variable node processing units 217 or by the check node processing units 215 which receive the messages as inputs.
(57) The following description will be made with reference to some embodiments using soft-output decoding based on sorting and truncation of the input messages received by the check node processing unit 215, for illustration purpose only. In such embodiments, each input message U.sub.i is a vector comprising n.sub.m,in components of a form U.sub.i=(U.sub.i[0], U.sub.i[1], . . . , U.sub.i[n.sub.m,in1]) and each output message V.sub.i is a vector comprising n.sub.m,outn.sub.m,in, components of a form V.sub.i=(V.sub.i[0], V.sub.i[1], . . . , V.sub.i[n.sub.m,out1]). A component U.sub.i[j]=(U.sub.i.sup.[j], U.sub.i.sup.+[j]) for j=0, . . . , n.sub.m,in1 comprises a symbol denoted by U.sub.i.sup.[j] and the reliability metric associated with this symbol denoted by U.sub.i.sup.+[j]. The components of each input message may be sorted such that the component comprising the most reliable symbol corresponds to the component U.sub.i[0], for i=1, . . . , d.sub.j and that U.sub.i.sup.+[j+1]U.sub.i.sup.+[j] for j=0, . . . , n.sub.m,in2.
(58) Referring to
(59) The syndrome calculator 31 may be configured to determine a set of NS syndromes denoted by S={S.sub.1, S.sub.2, . . . , S.sub.NS} from all the input messages. More specifically, the syndrome calculator 31 may be configured to determine the set of syndromes from the intermediary message computed by a check node processor 311 by processing all input messages. A syndrome denoted by S.sub.r=(S.sub.r.sup., S.sub.r.sup.+, S.sub.r.sup.DBV) for r=1, . . . , NS may comprise a GF(q) symbol denoted by S.sub.r.sup., the reliability metric associated with this symbol and denoted by S.sub.r.sup.+, and a binary vector denoted by S.sub.r.sup.DBV.
(60) The use of the elementary check node processors 311 for the computation of the syndromes enables reducing the computational complexity of syndrome decoding. Indeed, with the use of elementary check node processors 311, the number of computed syndromes used for determining output messages is reduced, thereby making it possible to exploit the parallelism of syndrome decoding while alleviating the computational complexity which is generally due to the high number of computed syndromes. In addition, the elementary check node processors 311 provide sorted components (depending on the order of the reliability metrics of the symbols) in the computed intermediary messages. As a result, the sorting operation conventionally applied after syndrome calculation can be removed, thereby enabling a reduction of the computational complexity required for the sorting process as well as a reduction of the implementation costs.
(61) According to some embodiments, the number of syndromes NS may be greater than or equal to the number of components in each input message and may depend on the order of the Galois Field.
(62) For example, in GF(64), the number of syndromes may be given by NS=3n.sub.m,out=9n.sub.m,in, the number of components comprised in each output message being typically equal to n.sub.m,out=20.
(63) a. In another example considering GF(256), the number of syndromes may be given by NS=3n.sub.m,out=25n.sub.m,in, the number of components comprised in each output message being typically equal to n.sub.m,out=60.
(64) Still in another example for GF(1024), the number of syndromes may be given by NS=3n.sub.m,out=45n.sub.m,in, the number of components comprised in each output message being typically equal to n.sub.m,out=150.
(65) According to some embodiments, each elementary check node processor 311 may be configured to determine the symbol comprised in a component of an intermediary message by applying an addition operation over the Galois Field to the symbol comprised in a component of the first message and the symbol comprised in a component of the second message.
(66) Moreover, each elementary check node processor 311 may be configured to determine the reliability metric associated with the symbol comprised in a component of an intermediary message by applying an addition operation over a given algebraic structure to the reliability metric comprised in a component of the first message and the reliability metric comprised in a component of the second message.
(67) According to some embodiments, the algebraic structure may be chosen in a group consisting of the field of real numbers, the field
of integer numbers, and the field
of natural numbers.
(68) a. For example in quantized hardware implementations and software implementations, each elementary check node processor 311 may be configured to determine the reliability metric associated with the symbol comprised in a component of an intermediary message by applying an addition operation over the integer field or the field of natural numbers
, enabling a complexity reduction.
(69) According to some embodiments, the syndrome calculator 31 may be further configured to associate an initial binary value with each component U.sub.i[j] comprised in the input messages U.sub.i for i=1, . . . , d.sub.j and j=0, . . . , n.sub.m,in1.
(70) According to some embodiments, the syndrome calculator 31 may be configured to associate the initial value with the components U.sub.i [j] depending on the reliability metrics U.sub.i.sup.+[j]. In particular, the syndrome calculator 31 may be configured to associate the component comprising the most reliable symbol with an initial binary value equal to a predefined first value and to associate the remaining components with an initial binary value equal to a predefined second value.
(71) According to some embodiments, the predefined first value may be equal to zero (0) and the predefined second value may be equal to one (1). In such embodiments, the binary value associated with a component U.sub.i [j] may be denoted by U.sub.i.sup.DBV[j] and may be given by:
(72)
(73) Considering sorted input messages, conditional equation (1) states that the initial binary value associated with a component comprised in an input message is assigned a bit 0 value if the symbol comprised in said component is the most reliable symbol.
(74) According to other embodiments, the predefined first value may be equal to one (1) and the predefined second value may be equal to one (0). Accordingly, the initial binary value associated with a component comprised in an input message maybe equal to bit 1 if the symbol comprised in this component is the most reliable symbol, that is
(75)
(76) Accordingly, each component of the first message and the second message processed by a given elementary check node processor 311 may be associated with a binary vector derived from the initial binary values. In such embodiments, each elementary check node processor 311 may be configured to determine the intermediary binary vector associated with a component of an intermediary message by applying a vector concatenation of the binary vector associated with a component of the first message and the binary vector associated with a component of the second message.
(77) In particular, an elementary check node processor 311 may be configured to determine an intermediary message and an intermediary binary vector associated with each component of the intermediary message from two input messages, the first and second messages being equal to a first input message and a second input message respectively.
(78) To illustrate the computation of an intermediary message by an elementary check node processor 311, the following description will be made with reference to processing a first and a second message both equal to input messages.
(79) According to some embodiments, the elementary check node processor 311 may be configured to determine the intermediary message by processing a number n.sub.ln.sub.m,in of components from the first message U.sub.l and/or a number n.sub.pn.sub.m,in of components from the second message U.sub.p.
(80) According to some embodiments in which the first message and second message are different from the input message, i.e. correspond to intermediary messages delivered by previous elementary check node processors 311 in the architecture, the number n.sub.l of components processed from the first message and/or the number n.sub.p of components processed from the second message may correspond to the number of components previously delivered by an elementary check node processor 311. In other words, the number of components processed by a given elementary check node processor 311 may depend on the number of components comprised in the previous intermediary messages processed by the elementary check node processors located at previous stages in the architecture.
(81) According to some embodiments, the elementary check node processor 311 may be configured to determine the intermediary message U.sub.t according to three steps.
(82) At a first step, the elementary check node processor 311 may be configured to determine a set of auxiliary output components from the components of the first message U.sub.l and the components of the second message U.sub.p. An auxiliary output component is referred to as a Bubble. A Bubble denoted by B .sub.t[u][v] refers to the Bubble obtained from the component U.sub.l[u] comprised in the first message U.sub.l and the component U.sub.p[v] comprised in the second message U.sub.p. The index u varies in 0,1, . . . , n.sub.l1 and the index v varies in 0,1, . . . , n.sub.p1. A Bubble comprises a couple of data comprising: a symbol denoted by B.sub.t.sup.[u][v], and its reliability metric denoted by B.sub.t.sup.+[u][v] and a binary vector denoted by B.sub.t.sup.DBV[u][v] associated with this couple. The total number of Bubbles is accordingly given by n.sub.ln.sub.p.
(83) According to some embodiments, the elementary check node processor 311 may be configured to determine the symbol B.sub.t.sup.[u][v] of an auxiliary output component B .sub.t[u][v] by applying an addition operation over the Field of construction of the error correcting code, namely over the Galois Field GF (q). The addition operation is applied to the symbol U.sub.l.sup.[u] comprised in the component U.sub.l[u] of the first message U.sub.l and to the symbol U.sub.p.sup.[v] comprised in the component U.sub.p[v] of the second processed message U.sub.p such that:
B.sub.t.sup.[u][v]=U.sub.l.sup.[u]U.sub.p.sup.[v](2)
(84) In equation (2), the operator stands for the addition operation over the Galois field.
(85) According to some embodiments, the elementary check node processor 311 may be configured to determine the reliability metric B.sub.t.sup.+[u][v] of an auxiliary output component B.sub.t[u][v], by applying an addition operation over a given algebraic structure, to the reliability metric U.sub.l.sup.+[u] comprised in the component U.sub.l[u] of the first message U.sub.l and to the reliability metric U.sub.p.sup.+[v] comprised in the component U.sub.p[v] of the second message U.sub.p such that:
B.sub.t.sup.+[u][v]=U.sub.l.sup.+[u]+U.sub.p.sup.+[v](3)
(86) According to some embodiments, the elementary check node processor 311 may be configured to determine the intermediary binary vector B.sub.t.sup.DBV[u][v] in association with the auxiliary output component B .sub.t[u][v] by applying a vector concatenation operation. The vector concatenation operation may be applied to the binary vector U.sub.l.sup.DBV[u] associated with the component U.sub.l[u] of the first message U.sub.l and to the binary vector U.sub.p.sup.DBV[v] associated with the component U.sub.p[v] of the second message U.sub.p such that:
B.sub.t.sup.DBV[u][v]=(U.sub.l.sup.DBV[u]U.sub.p.sup.DBV[v])(4)
(87) In equation (4), the operator stands for the concatenation operation which provides, from two or more input scalars or vectors, a list in the form of a vector, the elements of the list being equal to the concatenated inputs.
(88) At a second step, the elementary check node processor 311 may be configured to sort the determined n.sub.ln.sub.p auxiliary output components according to a given order of the reliability metrics of the symbols comprised in these components.
(89) At a third step, the elementary check node processor 311 may be configured to select, among the n.sub.ln.sub.p sorted auxiliary output components the n.sub.t components comprising the most reliable symbols, which provides the intermediary message U.sub.t and the binary vector associated with each component of the n.sub.t components comprised in this intermediary message.
(90) Further, the number n.sub.t of components comprised in an intermediary message may be lower than n.sub.ln.sub.p.
(91) The number of elementary check node processors 311 may depend on the implementation architecture used at the syndrome calculator.
(92) According to some embodiments, the syndrome calculator 31 may comprise a plurality of elementary check node processors 311 implemented in a serial architecture.
(93)
(94) According to some other embodiments, the syndrome calculator 31 may comprise a plurality of elementary check node processors implemented in a parallel architecture (hereinafter referred to as tree architecture). In such embodiments, the syndrome calculator 31 may comprise at least one elementary check node processor 311 configured to determine an intermediary message and the intermediary binary vector associated with each component of the intermediary message by processing two input messages. The remaining elementary check node processors 311 may be configured to determine an intermediary message and the intermediary binary vector associated with each component of the intermediary message either by processing two input messages or by processing two intermediary messages previously determined by two elementary check node processors 311 operating at previous stages of the tree architecture.
(95)
(96) According to some other embodiments, the syndrome calculator 31 may comprise a plurality of elementary check node processors 311 implemented in a hybrid architecture mixing the serial and the tree architectures as depicted in
(97) Regardless of the implementation architecture of the elementary check node processors 311 in the syndrome decoder, the syndrome calculator 31 may be configured to determine each syndrome S.sub.r=(S.sub.r.sup., S.sub.r.sup.+, S.sub.r.sup.DBV) in the set S={S.sub.1, S.sub.2, . . . , S.sub.NS} of NS syndromes from the intermediary message delivered by the last elementary check node processor 311 in the architecture obtained from all the input messages.
(98) For example, in embodiments using a serial implementation as illustrated in
(99) In another example using a tree implementation, as illustrated in
(100) Accordingly, a symbol S.sub.r.sup. comprised in the syndrome S.sub.r for r=1, . . . , NS can be expressed as a function of the symbols comprised in the input messages according to:
S.sub.r.sup.=S.sub.r.sup.(u.sub.1, u.sub.2, . . . , u.sub.d.sub.
(101) In equation (5), each index u.sub.i for i=1, . . . , d.sub.j varies in the set {0,1, . . . , n.sub.m,in1}.
(102) Further, the reliability metric S.sub.r.sup.+ associated with the symbol S.sub.r.sup. can be expressed as a function of the reliability metrics comprised in the different components of the input messages according to:
S.sub.r.sup.+=S.sub.r.sup.+(u.sub.1, u.sub.2, . . . , u.sub.d.sub.
(103) Moreover, the binary vector S.sub.r.sup.DBV comprised in the syndrome S.sub.r may be written as a function of the initial binary values associated with each component of the input message, as determined by the syndrome calculator 31 according to:
S.sub.r.sup.DBV=S.sub.r.sup.DVB(u.sub.1, u.sub.2, . . . , u.sub.d.sub.
(104) According to equation (7), a binary vector S.sub.r.sup.DBV comprised in a syndrome S.sub.r comprises d.sub.j bits.
(105) The check node processing unit 215 may further comprise a decorrelation unit 33 configured to determine, in association with each output message V.sub.i, a set of candidate components denoted by V.sub.i from the determined set of NS syndromes S. Each candidate component comprising a symbol and the reliability metric associated with the symbol.
(106) According to some embodiments (illustrated in
(107) According to an embodiment, an elementary decorrelation unit 313-i may be configured to determine a set of candidate components V.sub.i in association with each output message V.sub.i by selecting, among the determined set of syndromes S, the syndromes comprising binary vectors S.sub.r.sup.DBV=(S.sub.r.sup.DBV[1]S.sub.r.sup.DBV[2], . . . , S.sub.r.sup.DBV[d.sub.j]) such that the bit S.sub.r.sup.DBV[i] associated with the output message V.sub.i is equal to zero (0).
(108) According to another embodiment, an elementary decorrelation unit 313-i may be configured to determine a set of candidate components V.sub.i in association with each output message V.sub.i by selecting, among the determined set of syndromes S, the syndromes comprising binary vectors S.sub.r.sup.DBV=(S.sub.r.sup.DBV[1]S.sub.r.sup.DBV[2], . . . , S.sub.r.sup.DBV[d.sub.j]) such that the bit S.sub.r.sup.DBV[i] associated with the output message V.sub.i is equal to one (1).
(109) According to some embodiments in which a serial architecture of the elementary check node processors 311 is used at the syndrome calculator 31, the decorrelation unit 33 may be simplified and may comprise d.sub.j1 elementary decorrelation units 313-i with i=1, . . . , d.sub.j1.
(110)
(111) The check node processing 215 may further comprise a selection unit 35 configured to determine each output message V.sub.i by selecting components comprising distinct symbols from the set of candidate components V.sub.i depending on the reliability metrics of the symbols comprised in the set of candidate components V.sub.i. Accordingly, the selection unit 35 may be configured to retain, from the components in the set of candidate components V.sub.i comprising redundant symbol, the components which comprise the most reliable distinct symbols.
(112) According to some embodiments, the selection unit 35 may e configured to determine each output message V.sub.i by selecting a predefined number n.sub.m,out of components from the set of candidate components V.sub.i associated with the output message V.sub.i depending on the reliability metrics of the symbols comprised in the set of candidate components V.sub.i. Accordingly, the selection unit 35 may be first configured to perform a redundancy elimination in the set of candidate components V.sub.i for keeping, among the components comprising the same symbol (i.e. among the components comprising redundant symbols), the one which comprises the most reliable symbol. In a second step, the selection unit 35 may be configured to select a predefined number n.sub.m,out of components from the processed candidate components, depending on the reliability metrics of the symbols comprised in the processed candidate components, such that the n.sub.m,out components comprising the most reliable distinct symbols are selected.
(113) According to some embodiments, the selection units 35 implemented in the various check node processing units 215 may be configured to select a same predefined number n.sub.m,out of components to determine the output messages.
(114) According to other embodiments, the selection units 35 implemented in the various check node processing units 215 may be configured to select a different predefined number n.sub.m,out of components to determine the output messages. In such embodiments, the variables node processing units 217 recipients of these output messages may be configured to perform a truncation operation to retain a same number of components in each received message.
(115) In some embodiments, the predefined number of components n.sub.m,out may depend on the number of components n.sub.m,in comprised in the input messages.
(116) The predefined number of components n.sub.m,out may further depend on the Field over which the code is constructed and/or on the order of the decoding iteration of the iterative decoding process and/or on the signal-to-noise ratio and/or on the computational and storage capabilities of the check node processing units 215.
(117) In some other embodiments, the number of components n.sub.m,out may depend on a combination of the factors previously cited.
(118) For example, for Galois Fields over GF(64), the number of components n.sub.m,out may be related to the number of components comprised in input messages according to n.sub.m,out=3n.sub.m,in. For Galois Fields over GF(1024), the number of components n.sub.m,out may be related to the number of components comprised in input messages according to n.sub.m,out=15n.sub.m,in.
(119)
(120) The following description of some embodiments will be made with reference to soft-output decoding and reliability metrics represented in the logarithm domain by log-likelihood ratio (LLR) values, for illustration purpose 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.
(121) The method of the computation of output messages at a check node processing unit is a part of the messages exchange performed during the iterative decoding process of the EMS algorithm. The decoding process may be performed to determine an estimate of an original codeword c from a received noisy sequence represented by a vector y by applying the Belief Propagation decoding rule. The codeword c may have been encoded at the transmitter using a non-binary LDPC code designated by (n, k) constructed over the Galois Field GF(q) with q>2.
(122) The following description of some embodiments will be made mainly with a focus on the steps performed at a check node processing unit for the sake of clarity. A check node processing unit of degree d.sub.j configured to receive d.sub.j sorted and truncated input messages U.sub.1, U.sub.2, . . . , U.sub.d.sub.
(123) Step 801 may be performed to receive the input messages from the connected variable nodes in the corresponding Tanner graph. Accordingly, d.sub.j input messages U.sub.1, U.sub.2, . . . , U.sub.d.sub.
(124) In particular embodiments in which the LLR is the metric measuring the reliability of a symbol, the most reliable symbols are those which have the smallest LLR values. Accordingly, each input message U.sub.i may be written in a vector notation according to U.sub.i=(U.sub.i[0], U.sub.i[1], . . . , U.sub.i[n.sub.m,in1]) such that each component U.sub.i[j]=(U.sub.i.sup.[j], U.sub.i.sup.+[j]) for j=0, . . . , n.sub.m,in1 comprises a symbol denoted by U.sub.i.sup.[j] and the LLR metric denoted by U.sub.i.sup.+[j] associated with the symbol and such that the component carrying the most reliable symbol corresponds to the component U.sub.i[0], for i=1, . . . , d.sub.j with U.sub.i.sup.+[u]U.sub.i.sup.+[v] for each 0u<vn.sub.m,in1.
(125) Step 803 may be performed to associate an initial binary value with each component U.sub.i[j] for j=0, . . . , n.sub.m,in1 comprised in the input messages U.sub.i for i=1, . . . , d.sub.j.
(126) According to some embodiments, the initial value associated with the components U.sub.i[j] may depend on the reliability metrics U.sub.i.sup.+[j]. In particular, an initial binary value equal to a predefined first value may be associated with the component comprising the most reliable symbol and an initial binary value equal to a predefined second value may be associated with the remaining components.
(127) According to some embodiments, the predefined first value may be equal to zero (0) and the predefined second value may be equal to one (1). Accordingly, the initial binary value denoted by U.sub.i.sup.DBV[j] associated with a component U.sub.i[j] may be determined according to equation (1), i.e. the initial binary value U.sub.i.sup.DBV[j] associated with a component U.sub.i[j]comprised in an input message U.sub.i may take the bit 0 if the symbol comprised in said component is the most reliable symbol.
(128) According to other embodiments, the predefined first value may be equal to one (1) and the predefined second value may be equal to zero (0). Accordingly, the initial binary value associated with a component comprised in an input message may be equal to the bit 1 if the symbol comprised in this component is the most reliable symbol, that is
(129)
(130) Step 805 may be performed to determine a set of syndromes denoted by S={S.sub.1, S.sub.2, . . . ,S.sub.NS} comprising NS syndromes from the input messages using a plurality of elementary check node processors 311. A syndrome S.sub.r=(S.sub.r.sup.,S.sub.r.sup.+,S.sub.r.sup.DBV) for r=1, . . . , NS may comprise a symbol denoted by S.sub.r.sup., the LLR metric associated with the symbol and denoted by S.sub.r.sup.+, and a binary vector denoted by S.sub.r.sup.DBV.
(131) According to some embodiments, the number NS of syndromes in the set of syndromes S may be greater than or equal to the number of components in each input message. For example, the number of syndromes may be given by NS=3n.sub.m,out=9n.sub.m,min over GF(64).
(132) According to some embodiments, the set of syndromes S may be determined from intermediary results determined from all the input messages.
(133) An intermediary message denoted by U.sub.t may comprise a number n.sub.t of sorted components and an intermediary binary vector associated with each component, the components comprised in a given intermediary message being sorted into a given order of the reliability metrics of the symbols comprised therein. An intermediary message may be determined by processing a first message and a second message derived from the input messages, the number of input messages being advantageously at least equal to three. Further, each component comprised in the first message and the second message may be associated with a binary vector derived from the initial binary values in association with the components of the input messages.
(134) Accordingly, a symbol comprised in a component of an intermediary message may be determined by applying an addition operation over the Galois Field to the symbol comprised in a component of the processed first message and the symbol comprised in a component of the processed second message.
(135) Moreover, the LLR metric associated with a symbol comprised in an intermediary message may be determined by applying an addition operation over a given algebraic structure to the LLR metric associated with a component of the first message and the LLR metric associated with a component of the second message.
(136) According to some embodiments, the algebraic structure may be chosen in a group consisting of the field of real numbers, the field
of integer numbers, and the field
of natural numbers. For example, in embodiments involving hardware quantized implementations or software implementations, the addition operation may be performed over the field of integer numbers
or the field of natural numbers
.
(137) Further, the intermediary binary vector associated with a component of an intermediary message may be determined by applying a vector concatenation of the binary vector associated with a component of the first message and the binary vector associated with a component of the second message.
(138) For an intermediary message determined by processing two input messages denoted respectively by U.sub.l and U.sub.p for l and pl varying in the set of indices from 1 to d.sub.j, an intermediary message denoted by U.sub.t may be determined from the components of the input messages. The intermediary binary vector associated with each component of the intermediary message may be determined from the initial binary values associated with each component of the input messages. Accordingly, an intermediary message U.sub.t may comprise n.sub.t components U.sub.t[j] for j=0, . . . n.sub.t1 and an intermediary binary vector U.sub.t.sup.DBV[j] associated with each component U.sub.t[j]. A component U.sub.t[j]=(U.sub.t.sup.[j], U.sub.t.sup.+[j]) for j=0, . . . n.sub.t1 may comprise a symbol U.sub.t.sup.[j] and the LLR metric U.sub.t.sup.+[j] associated with the symbol. The components of the intermediary message U.sub.t may be sorted into a given order depending on the reliability metrics of the symbols comprised therein such that U.sub.t.sup.+[j+1]U.sub.t.sup.+[j] for all j=0, . . . , n.sub.t2.
(139) According to some embodiments, an intermediary message may be determined by processing a number n.sub.l<n.sub.m,in of components from the first message and/or a number n.sub.pn.sub.m,in of components from the second message.
(140) According to some embodiments, an intermediary message may be determined through three steps.
(141) At a first step, a set of auxiliary output components may be determined from the components of the first message U.sub.l and the components of the second message U.sub.p. An auxiliary output component is referred to as a Bubble. A Bubble denoted by B.sub.t[u][v] refers to the Bubble obtained from the component U.sub.l[u] comprised in the first message U.sub.l and the component U.sub.p[v] comprised in the second message U.sub.p. The index u varies in 0,1, . . . , n.sub.l1 and the index v varies in 0,1, . . . , n.sub.p1. A Bubble may comprise a couple of data comprising a symbol denoted by B.sub.t.sup.[u][v] and its LLR metric, denoted by B.sub.t.sup.+[u][v]. It may also comprise a binary vector denoted by B.sub.t.sup.DBV[u][v] associated with this couple. The total number of output Bubbles is accordingly given by n.sub.ln.sub.p.
(142) According to some embodiments, the symbol B.sub.t.sup.[u][v] comprised in an auxiliary output component B.sub.t[u][v] for u=0,1, . . . , n.sub.l1 and v=0,1, . . . , n.sub.p1 may be determined according to the addition over the Galois Field as previously expressed in equation (2).
(143) According to some embodiments, the LLR metric B.sub.t.sup.+[u][v] comprised in an auxiliary output component B.sub.t[u][v] for u=0,1, . . . , n.sub.l1 and v=0,1, . . . , n.sub.p1 may be determined according to the addition over the Real Field as previously expressed in equation (3).
(144) According to some particular embodiments, for example in quantized hardware implementations and software implementations, the LLR metric B.sub.t.sup.+[u] [v] comprised in an auxiliary output component B.sub.t[u][v] for u=0,1, . . . , n.sub.l1 and v=0,1, . . . , n.sub.p1 may be determined according to the addition over the integer field or the field of natural numbers
, enabling a complexity reduction.
(145) According to some embodiments, the binary vector B.sub.t.sup.DBV[u][v] associated with an auxiliary output component B.sub.t[u][v] for u=0,1, . . . , n.sub.l1 and v=0,1, . . . , n.sub.p1 may be determined according to the vector concatenation operation as previously expressed in equation (4).
(146) After the computation of the n.sub.ln.sub.p auxiliary output components, a sorting step may be performed to order these components in an increasing order of the LLR metrics comprised in each component.
(147) At a last step, a truncation operation may be performed to select, among the n.sub.ln.sub.p sorted auxiliary output components, n.sub.t components, which provides the intermediary message U.sub.t and the binary vector associated with each component of the n.sub.t sorted components comprised in this intermediary message.
(148) According to some embodiments, the number n.sub.t of the components comprised in an intermediary message may be lower than n.sub.ln.sub.p.
(149) The set of syndromes may be determined from the intermediary message computed using all the input messages.
(150) In embodiments using a serial architecture, the set of syndromes may be determined from the intermediary message delivered by the last elementary check node processor in the serial architecture.
(151) In embodiments using a parallel architecture, the set of syndromes may be determined from the intermediary message delivered by the elementary check node processor located at the last stage of the tree architecture.
(152) Independently of the type of the implementation architecture of the various elementary check node processors 311, the set of syndromes S.sub.r=(S.sub.r.sup., S.sub.r.sup.+S.sub.r.sup.DBV) for r=1, . . . , NS may be expressed as a function of the input messages.
(153) Accordingly, the symbol S.sub.r.sup. comprised in the syndrome S.sub.r for r=1, . . . , NS can be expressed as the summation over the Galois field of the symbols U.sub.i.sup.[u.sub.i] comprised in the input messages U.sub.i for i=1, . . . ,d.sub.j and u.sub.i [0, n.sub.m,in1] according to equation (5).
(154) Further, the LLR metric S.sub.r.sup.+ comprised in the syndrome S.sub.r for r=1, . . . , NS can be expressed as the summation over the real field of the LLR metrics U.sub.i.sup.+[u.sub.i] comprised in the input messages U.sub.i for i=1, . . . , d.sub.j and u.sub.i [0, n.sub.m,in1] according to equation (6).
(155) Further, the binary vector S.sub.r.sup.DBV comprised in the syndrome S.sub.r for r=1, . . . , NS can be expressed as the vector concatenation of the initial binary values U.sub.i.sup.DBV[u.sub.i] associated with the input messages U.sub.i for i=1, . . . , d.sub.j and u.sub.i [0, n.sub.m,in1] according to equation (7). Accordingly, the binary vector S.sub.r.sup.DBV comprised in a syndrome S.sub.r comprises d.sub.j bits, each binary value S.sub.r.sup.DBV[i] for i=1, . . . , d.sub.j being associated with an output message V.sub.i.
(156) Step 807 may be performed to determine a set of candidate components denoted by V.sub.i, in association with each output message V.sub.i, from the determined set of syndromes. Step 807 may comprise applying a decorrelation operation that depends on the binary vector S.sub.r.sup.DBV comprised in each syndrome S.sub.r. The binary vectors may accordingly indicate for which output message a syndrome should be discarded or selected in order to determine the set of candidate components. As a binary vector S.sub.r.sup.DBV comprises d.sub.j bits, each bit S.sub.r.sup.DBV[i] for i=1, . . . , d.sub.j being associated with an output message V.sub.i, the value of the bit S.sub.r.sup.DBV[i] may be used to validate or not the selection of the syndrome S.sub.r in order to determine the set of candidate components V.sub.i.
(157) More specifically, according to a first embodiment in which the initial binary value associated with the most reliable symbol is equal to 0 (as in equation (1)), if the bit S.sub.r.sup.DBV[i] is equal to zero (0), then the syndrome S.sub.r is a valid syndrome. The couple of data comprising the symbol S.sub.r.sup. and its LLR metric S.sub.r.sup.+ of the valid syndrome S.sub.r maybe then selected to form a candidate component among the candidate components.
(158) According to another embodiment in which the initial binary value associated with the most reliable symbol is equal to 1, if the bit S.sub.r.sup.DBV[i] is equal to one (1), then the syndrome S.sub.r is a valid syndrome. The couple of the symbol S.sub.r.sup. and its LLR metric S.sub.r.sup.+ of the valid syndrome S.sub.r maybe then selected to form a candidate component among the set of candidate components.
(159) According to some embodiments, the decorrelation operation may be performed to determine a set of candidate components V.sub.i in association with each output message using d.sub.j elementary decorrelation operations, each elementary decorrelation operation being performed to determine a set of candidate components in association with a given output message.
(160) According to some other embodiments typically using a serial architecture, the decorrelation operation may be performed using only d.sub.j1 elementary decorrelation operations. The set of candidate components associated with the last elementary check node processor in the serial architecture may be determined from the intermediary message delivered by the penultimate elementary check node processor.
(161) At step 809, a redundancy elimination operation may be performed on the determined set of candidate components associated with each output message for retaining, from the components comprising the same symbol, the component comprising the most reliable symbol corresponding to the smallest LLR metric. In other words, the components that give rise to a same symbol value are processed such that the component comprising the redundant symbol associated with the smallest LLR metric is kept.
(162) Step 811 may be performed to generate the output messages V.sub.i for i=1, . . . , d.sub.j from the processed sets of candidate components. An output message V.sub.i may be determined by selecting a predefined number n.sub.m,out of the most reliable components from the processed set of candidate components, i.e. by selecting the n.sub.m,out components comprising the symbols associated with the smallest LLR metrics.
(163)
(164)
(165)
(166)
(167) It should be noted that the conventional operations performed by an elementary check node processor, in contrast to the operations performed by an elementary check node processor according to the embodiments of the present invention, involve a redundancy elimination operation that removes redundant components from auxiliary output components or Bubbles.
(168) Depicted error performance results show that the proposed serial and parallel implementations of syndrome decoding using elementary check node processors provide a same performance as the forward-backward architecture, which shows the optimality of the methods according to the embodiments of the invention. In addition, numerical results show the efficiency of the elementary check node processors according to the various embodiments against the operations used in the conventional elementary check node processors. Indeed, when applied to syndrome computation, the processing performed by conventional elementary check node processors fails to achieve optimal error performance and presents a significant loss especially at high signal-to-noise ratio values. This performance loss is due to the redundancy elimination operation performed at the level of the elementary check node processors.
(169) In addition to the error probability performance, the complexity of the following implementations was evaluated in terms of the number of elementary check node processors (ECNs), the number of sorted input couples, and the total number of the auxiliary outputs of the elementary check node processors: FB n.sub.m=20, SB-CN, Serial NS=50, n.sub.m,in=6, n.sub.m,out=20, and SB-CN, Tree NS=50, n.sub.m,in=6, n.sub.m,out=20. The results are shown in
(170) The architecture according to the embodiments of the invention accordingly provides optimal decoding performance with a significant reduction of the decoding computational complexity and implementation hardware cost.
(171) 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 an 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.
(172) While embodiments of the invention 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. Additional advantages and modifications will readily appear to those skilled in the art. The invention in its broader aspects is therefore not limited to the specific details, representative methods, and illustrative examples shown and described.
(173) In particular, while the description of some embodiments of the invention has been performed with reference to a particular implementation to the EMS algorithm, it should be noted that the invention may be also applied to other iterative decoding algorithms such as the min-max algorithm.
(174) Furthermore, while some embodiments of the invention have been described with reference to error correcting codes constructed over Galois Fields, the skilled person will readily understand that the proposed embodiments based on elementary check node processing for syndrome computation may be also applied to any LDPC codes and any graph error correcting code constructed over non-commutative groups such as polynomial codes (e.g. cyclic codes).
(175) Further, even if the invention has some advantages in an application to communication systems, it should be noted that the invention is not limited to such communication devices and may be integrated in numerous devices such as data storage devices.
(176) 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.