Error Correction for LDPC Decoders

Abstract

A reception unit for use in a data link and a method for error correction on a reception word in a data link are specified. A low-density parity-check code, LDPC code, is used to iteratively adapt the reception word by virtue of bit node messages and check node messages being exchanged. The check node messages that are transmitted to the bit nodes are quantized in three levels and adopt the values −1, 0 or +1. The method may thus be implemented with low computational expenditure.

Claims

1. A reception unit for use in a data link, comprising: a preprocessing unit configured to quantize an analogue value, received from a transmission channel, into a three-level signal Q, wherein the three-level signal may adopt a first value, a second value or a third value, wherein the first value corresponds to a first logic state, the third value corresponds to a second logic state and the second value corresponds to an indeterminate logic state; and a decoder having a multiplicity of bit nodes and a multiplicity of check nodes, wherein a number of bit nodes is linked in each case to one check node; wherein the decoder is configured to iteratively update bit node messages in accordance with the rule: $B^{\left(n\right)}\left(k\right)=r\left(k\right)+\underset{l\in \gamma \left(k\right)}{.Math.}{C}_k^{\left(n-1\right)}\left(l\right),$ wherein: B.sup.(n)(k) is the nth iteration of a message from the bit node n to the check node linked to the bit node n; C.sub.k.sup.(n) is the nth iteration of a message from the check node n to the bit node k; and γ(k) is a set of indices of the check nodes linked to the bit node k; wherein the decoder (120) is configured to iteratively update check node messages to the bit nodes in accordance with the rule: $C_l^{\left(n\right)}\left(k\right)=\underset{\lambda \in \beta \left(k\right),\lambda \ne 1}{.Math.}Q\left(B^{\left(n\right)}\left(\lambda \right)-C_{\lambda }^{\left(n-1\right)}\left(k\right)\right),$ wherein β(k) is a set of indices of the bit nodes linked to the check node k; and wherein the decoder is configured to determine the three-level signal Q(x) as follows: $Q\left(x\right)=\{\begin{array}{cc}+1,& x>0,\\ 0,& x=0,\\ -1,& x<0\end{array}.$

2. The reception unit according to claim 1, wherein the decoder is a low-density parity-check code.

3. The reception unit according to claim 1, wherein the preprocessing unit comprises a first comparator and a second comparator; wherein the first comparator is configured to check whether the received analogue value is above a first threshold value; wherein the second comparator is configured to check whether the received analogue value is below a second threshold value; wherein the preprocessing unit is configured to output the first value of the three-level signal when the received analogue value is above the first threshold value, to output the third value of the three-level signal when the received analogue value is below the second threshold value, and otherwise to output the second value of the three-level signal.

4. The reception unit according to claim 1, wherein the preprocessing unit is configured, for a reception sequence containing multiple information bits, in each case to ascertain one value per information bit according to the three-level signal Q and in each case to transmit a value to each bit node of the decoder.

5. The reception unit according to claim 1, wherein all of the check nodes are linked to the same number of bit nodes in an alternating grouping of the bit nodes.

6. A data link, comprising: a coder; a modulator linked to the coder; a transmission channel linked to the modulator; a reception unit according to claim 1; wherein the reception unit is linked to the transmission channel such that data are able to be transmitted from the coder to the reception unit.

7. The data link according to claim 6, wherein the modulator is configured to perform binary phase shift keying and to output a signal thereby generated on the transmission channel.

8. A method for error correction on a response word on a data link, comprising: quantizing an analogue value into a three-level signal Q, wherein the three-level signal may adopt a first value, a second value or a third value, wherein the first value corresponds to a first logic state, the third value corresponds to a second logic state and the second value corresponds to an indeterminate logic state; assigning a multiplicity of quantized analogue values to a multiplicity of bit nodes; determining check values in a multiplicity of check nodes, wherein each check node is linked to a predefined group of bit nodes; iteratively updating bit node messages to the check nodes in accordance with the rule: $B^{\left(n\right)}\left(k\right)=r\left(k\right)+\underset{l\in \gamma \left(k\right)}{.Math.}{C}_k^{\left(n-1\right)}\left(l\right),$ wherein: B.sup.(n)(k) is the nth iteration of a message from the bit node n to the check node linked to the bit node n; C.sub.k.sup.(n) is the nth iteration of a message from the check node n to the bit node k; and γ(k) is a set of indices of the check nodes linked to the bit node k; iteratively updating check node messages to the bit nodes in accordance with the rule: $C_l^{\left(n\right)}\left(k\right)=\underset{\lambda \in \beta \left(k\right),\lambda \ne 1}{.Math.}Q\left(B^{\left(n\right)}\left(\lambda \right)-C_{\lambda }^{\left(n-1\right)}\left(k\right)\right),$ wherein β(k) is a set of indices of the bit nodes linked to the check node k; and wherein the three-level signal Q(x) is determined as follows: $Q\left(x\right)=\{\begin{array}{cc}+1,& x>0,\\ 0,& x=0,\\ -1,& x<0\end{array}.$

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0054] Exemplary embodiments are described in more detail below with reference to the appended drawings. The illustrations are schematic and not to scale. Identical reference signs refer to identical or similar elements. In the figures:

[0055] FIG. 1 shows a schematic illustration of a Tanner graph, the principles of which define the operating basis of an LDPC code.

[0056] FIG. 2 shows a schematic illustration of a data link.

[0057] FIG. 3 shows a schematic illustration of a reception unit.

[0058] FIG. 4 shows a schematic illustration of a preprocessing unit.

DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS

[0059] FIG. 1 shows a schematic illustration of a Tanner graph, in order to explain the basic operation of an LDPC code and the operation of the reception unit, including decoder, set forth here.

[0060] A reception sequence 1, in this case a binary reception sequence, is transmitted to the bit nodes 2. The number of bits in the reception sequence, which corresponds to the number of bit nodes, is referred to as reception word. In the present case, the Tanner graph contains 20 bit nodes (0 . . . 19), such that a reception word consists of 20 bits. The Tanner graph also contains 15 check nodes (0 . . . 14).

[0061] Four bit nodes are linked in each case to a check node. By way of example, the bit nodes 0 . . . 3 are linked to the check node 0, the bit nodes 4 . . . 7 are linked to the check node 1, etc. There are also groupings of bit nodes other than groups containing successive bit nodes. By way of example, the bit nodes 0, 4, 8, 12 are linked to the check node 5. In any case, each check node is linked to a combination of bit nodes that is present exactly once.

[0062] In order to indicate error-free transmission, for each reception word to the bit nodes, it is necessary to meet the condition whereby each check node meets the parity or check condition. This check condition makes provision for the check value to have the value 0. The check value is normally calculated as follows (given here by way of example for the check node 0, the same operation being performed for all check nodes):

c(0)⊕c(1)⊕c(2)⊕c(3)=0,

wherein ⊕ means a modulo-2 addition. If c(k) is replaced with BPSK-modulated keys (binary phase shift keying, BPSK), the parity condition for the check node 0 may be expressed as follows:

s(0).Math.s(1).Math.s(2).Math.s(3)=1,

[0063] The decoding is an iterative process. The values of the bit nodes are first of all set to the bits of the received reception word, and the check value is calculated in the check nodes, shown here again by way of example for the check node 0:

B(0).Math.B(1).Math.B(2).Math.B(3)=1.

[0064] From the bit node values present at the check node 0, it is then possible to perform reverse calculation and determine a required value for a bit node by applying the other bit node values of this check node. It is then possible to calculate the required value for the bit node 0 in the check node 0 by applying the values of the other bit nodes from this group, that is to say the bit nodes 1 to 3:

C.sub.0(0)=B(1).Math.B(2).Math.B(3),

[0065] The same thing happens for the reverse-calculated value for the other three bit nodes 1 to 3, shown by way of example for the bit node 1:

C.sub.1(0)=B(0).Math.B(2).Math.B(3),

[0066] The values of the bit nodes 0, 2 and 3 are thus used here to determine the value of the bit node 1 such that the check value is correct.

[0067] As may be seen in FIG. 1, the bit node 0 is linked to the check nodes 0, 5, 10. A required value of the bit node 0 is calculated in each of these three check nodes (based on the in each case remaining bit nodes in the respective groups). Using these calculated values and the originally received bit at the bit node 0, it is then possible to iteratively ascertain a value for the bit node 0 with regard to what this value would have to be in order for the parity conditions to be met at all check nodes. The value of the bit node is then changed and the method is run through again.

[0068] In conventional LDPC decoders, highly resolved values are used to determine the values of the bit nodes, for example between 4 and 6 bits. In order to reverse-calculate the assumed values of the bit nodes based on the values of the check nodes, use is made of probability theory techniques.

[0069] In contrast thereto, it is proposed here for the values of the bits of the reception word and the values of the check nodes to be quantized and to adopt exclusively one of the values −1, 0 and +1.

[0070] In a first step, the values of the reception word that are quantized in this way are assigned to the bit nodes, and the bit nodes are initialized with these values. The initial values are given here as r(k), wherein k indicates the number of the bit node. The check values are then calculated in the check nodes and a reverse calculation is performed in each node for each connected bit node as to what the value of the bit node in question has to be in order for the parity condition to be met (see above).

[0071] The bit nodes receive feedback from multiple check nodes and thus change their value for the next iteration step when required, for example according to a majority decision regarding the reverse-calculated values received from the check nodes and taking into consideration the initial value from the reception word. In the nth iteration step, the (new) value of a bit node (here for example the bit node 0) is set to the sum that corresponds to the value of the associated bit from the reception word (r(0)) and the responses from the check nodes (C, here the responses from the check nodes 0, 5 and 10 for the bit node 0 from the previous iteration step n-1):

B.sup.(n)(0)=r(0)+C.sub.0.sup.(n-1)(0)+C.sub.0.sup.(n-1)(5)+C.sub.0.sup.(n-1)(10).

[0072] Using the following quantization function, wherein x is an arbitrary integer,

[00007]$Q\left(x\right)=\{\begin{array}{cc}+1,& x>0,\\ 0,& x=0,\\ -1,& x<0\end{array}.$

[0073] it is possible to state the following for the calculation of the response at a bit node by a check node:

C.sub.0.sup.(n)(0)=Q({circumflex over (B)}.sup.(n)(1)).Math.Q({circumflex over (B)}.sup.(n)(2)).Math.Q({circumflex over (B)}.sup.(n)(3)),

[0074] The response from the check node 0 to the bit node 0 for the value of the bit node 0 in the iteration step n corresponds to the product of the quantized values of the bit nodes 1, 2 and 3, wherein the following holds true:

{circumflex over (B)}.sup.(n)(k)=B.sup.(n)(k)−C.sub.k.sup.(n-1)(0).

[0075] This means that, in order to update the value of a check node, use should be made only of bit node information that was received by the used bit node exclusively from other check nodes in the previous iteration step. This is achieved by again subtracting the information that the check node to be updated transmitted to the bit node to be used for the update in the previous iteration step.

[0076] FIG. 2 shows a schematic illustration of a data link 10. The data link contains a coder 12 that codes values and outputs them to a modulator 14. The moderator outputs a modulated bit sequence on the transmission channel 16. At the output of the transmission channel 16, a reception sequence is output to the reception unit 100.

[0077] The reception unit 100 performs the method described above. The reception unit may be linked to a data consumer (not shown) and forwards the received data to the data consumer.

[0078] The data link 10 may be used for any data transmission link between a data source and a data consumer. The transmission channel may contain a wireless or wired transmission section.

[0079] The transmission channel 16 may be what is known as an erasure channel and already output three values (logic 1, logic 0, indeterminate) at its output. This distinction between the three values may however also be made by a dedicated unit that is present separately, for example by the preprocessing unit (see FIG. 3).

[0080] FIG. 3 shows a schematic illustration of a reception unit 100. The reception unit 100 has a preprocessing unit 110 and a decoder 120. The preprocessing unit 110 may be spatially and structurally separate from the decoder. By way of example, the preprocessing unit 110 may be arranged as a functional component of the transmission channel 16 (see FIG. 2). In any case, a bit that may adopt three values: logic 0, logic 1, indeterminate, is delivered to the decoder 120. This is the functional prerequisite for the decoder, and it is irrelevant whether this input value arrives at the decoder directly from the transmission channel or from a separate functional unit.

[0081] FIG. 4 shows an exemplary structure of the preprocessing unit 110 in order to obtain the three output values logic 0, logic 1 and indeterminate.

[0082] The preprocessing unit 110 has two comparators 112, 114. An information bit is conveyed to the two comparators. If a voltage level of the information bit is greater than a first threshold value, then the first comparator 112 outputs a value such that the preprocessing unit outputs a first logic value, for example a logic 1. If the voltage level of the information bit is on the other hand lower than a second threshold value, then the second comparator 114 outputs a value such that the preprocessing unit outputs a second logic value, for example a logic 0. If the value of the voltage level is between the first and second voltage level (in each case including this bound), then the preprocessing unit 110 outputs “indeterminate” as output value.

[0083] The preprocessing unit 110 may thus be used to provide the bit nodes initially with the associated three-level values of the reception word.

[0084] It is additionally pointed out that “comprising” or “having” does not rule out any other elements or steps, and “a” or “an” does not rule out a multiplicity. It is furthermore pointed out that features or steps that have been described with reference to one of the exemplary embodiments above may also be used in combination with other features or steps of other exemplary embodiments described above. Reference signs in the claims should not be considered to be restrictive.

LIST OF REFERENCE SIGNS

[0085] 1 Reception sequence [0086] 2 Bit nodes [0087] 3 Check nodes [0088] 10 Data link [0089] 12 Coder [0090] 14 Modulator [0091] 16 Transmission channel [0092] 100 Reception unit [0093] 110 Preprocessing unit [0094] 112 First comparator [0095] 114 Second comparator [0096] 120 Decoder, LDPC decoder