RU2575399C1 - Method of decoding ldpc codes and apparatus therefor - Google Patents

Abstract

FIELD: radio engineering, communication.

SUBSTANCE: for a received codeword of a LDPC code, possibly distorted in a communication link, when searching for a correlation vector, a weight-ordered adjacent class of error vectors is generated. When decoding with a "hard" solution, the correlation vector selected is the first generated error vector, which is the leader of the adjacent class of error vectors. When decoding with a "soft" solution, the correlation vector selected is an error vector of an adjacent class having a maximum metric.

EFFECT: obtaining decoding quality which corresponds to maximum-likelihood criterion decoding methods, with both hard and soft solutions, reduced hardware and computational complexity of decoding.

2 cl, 1 dwg

Description

The invention relates to the field of communication technology and, in particular, to information transmission systems in which LDPC codes are used to protect it from distortion in the communication channel. The invention can be used in codecs (encoder-decoder) systems for the transmission and storage of discrete information.

A known iterative method for decoding LDPC codes with a “hard” solution [1], which includes a repeatedly repeated procedure for correcting bits of a distorted code word. First, the distorted codeword syndrome is computed and a “relationship vector” of each bit of the codeword with nonzero elements of the syndrome is formed. For this, the elements of the syndrome are scanned, non-zero are selected, and for each of them, the positions of the “relationship vector” are incremented, which correspond to non-zero elements of the row of the verification matrix. After the formation of the “relationship vector” is completed, those bits of the codeword whose numbers correspond to the positions of the “relationship vector” in which a number is written that exceeds the selected threshold (usually a threshold equal to more than half the number of “units” in the column of the LDPC code). If the corrected codeword has a non-zero syndrome, then the bit correction procedure is repeated until the corrected codeword syndrome becomes zero. At the end of the decoding process, the corrected codeword is mapped to an information sequence performed by inverse transformation according to the encoding rule.

The disadvantages of an iterative method for decoding LDPC codes with a “hard” solution [1] include the fact that, firstly, it does not belong to the class of decoding methods by the maximum likelihood criterion. This was pointed out by R. Gallager [1, p. 64, 94-97], who introduced LDPC codes into consideration. From his point of view, a reasonable compromise is achieved between LDPC codes between computational complexity and decoding reliability. And secondly, some combinations of both correctable and uncorrectable errors lead to an iterative decoding method looping. Therefore, it is necessary to introduce a limit on the admissible number of iterations.

The technical result of the proposed technical solution is to improve the quality of decoding LDPC codes.

To achieve a technical result, a method for decoding LDPC codes with a “tough” solution is proposed, in which, after calculating the syndrome, the steps are taken to construct, by weight, an adjacent class of error vectors. At each step, they are being completed, i.e. only those fragments of V _g error vectors whose metric m _g is equal to the step number t continue to be formed:

Where:

Δ _i is the number of nonzero elements of the current syndrome when adding to the fragment of the error vector V _{g the} next element at step t,

r is the number of steps for which the fragment V _g of the error vector was formed, while r is less than or equal to the current step t of forming the fragment of the error vector.

The current syndrome s _{t of} each newly formed fragment of the error vector at step t is determined as a result of modulo 2 addition of the initial syndrome obtained at the (t-1) step with the jth column of the verification matrix:

where j is the position of the added element in the fragment of the error vector.

The construction of the weighted adjacent class of error vectors is completed when the current syndrome of one of the vectors V _g becomes equal to the zero vector. This moment corresponds to the localization of the error vector, which is either the leader of the adjacent class of error vectors (correctable error), or one of the errors of the minimum weight in the adjacent class of error vectors (fatal error).

Consider a regular LDPC code that has l “units” in a column and ρ “units” in a row in a sparse check matrix.

A method for decoding an LDPC code using an ordered weight class of an adjacent class of error vectors:

1. Calculate the syndrome of a codeword being decoded, possibly distorted in the communication channel. If the syndrome is equal to the zero vector, go to step 7.

2. Select any row of the verification matrix that corresponds to the nonzero element of the syndrome, and determine ρ the initial elements of the generated fragments of error vectors of the adjacent class that correspond to the positions of nonzero elements in the selected row of the verification matrix. The initial step number is t = 1.

3. Calculate the metric m _g (1) and determine the current syndrome s _t (2) for each fragment of the error vectors generated in step t.

4. If the current syndrome s _{t of} one of the error vectors is equal to the zero vector, then generate a correction vector from this error vector and go to step 6.

5. Choose any row of the check matrix that corresponds to a non-zero element of the current syndrome, and determine ρ of the continuation elements of generated fragments of error vectors of an adjacent class for each fragment of error vectors generated at the current step t that has a metric equal to the step number m _g = t. Increase the step number t = t + 1 and go to step 3.

6. Add mod 2 to the received distorted codeword with the generated correction vector.

7. Form the information sequence of the code word.

When decoding LDPC codes with a “soft” solution, you must:

- calculate the metric according to the formula:

where: b _i is the value of the i-th bit of the code word of the LDPC code, p _o0 , p _i1 are the conditional probabilities of transmission over the communication channel at the i-th position of the code word 0 or 1, respectively.

- at step t, change the condition for determining the correction vector: the correction vector is the generated error vector of an adjacent class, the current syndrome of which is a zero vector, and which has a maximum metric (3). For this, at step t, it is necessary to sequentially memorize the error vectors with the “zero” syndrome and the metric calculated for it until the metric of the next error vector begins to decrease.

The decoder LDPC code using ordered by weight of the adjacent class of error vectors (figure 1) contains:

- block calculation of the syndrome - 1;

- block for the formation of the initial elements of the error vectors - 2;

- unit for calculating the metric and current syndrome - 3;

- block forming the elements of the continuation of the error vectors - 4;

- block for the formation of the correction vector - 5;

- correction block - 6;

- block forming the information sequence of the code word - 7;

- random access memory - 8.

The syndrome 1 calculation unit determines the syndrome of the decoded codeword of the LDPC code.

The unit for generating the initial elements of the error vectors 2 determines the initial nonzero positions of the error vectors of the adjacent class corresponding to the calculated syndrome. The sparse check matrix allows one to determine ρ of the initial nonzero bits for fragments of error vectors of an adjacent class from any nonzero element of the syndrome. The selected nonzero initial values are recorded in fragments of error vectors of an adjacent class generated and stored in the RAM 8.

The unit for calculating the metric and the current syndrome 3 sequentially iterates over the newly formed fragments of the error vectors stored in the random access memory 8, determines for each of them the metric (1) and the current syndrome (2). The current syndrome is the sum of mod 2 of the previous syndrome and the column of the verification matrix, the number of which corresponds to the error position defined in the metric and current syndrome 3 calculation unit. The generated current syndrome is stored in random access memory 8 together with its fragment of the error vector. If a “zero” syndrome is defined for one of the errors vector fragments received in the block, the error class of the adjacent class is generated and transmitted to the block for generating the correction vector 5.

The block for generating the error vector continuation elements 4 sequentially selects from the random access memory 8 generated fragments of the error vectors of the current step t, the metric of which is equal to the step number m _g = t, for each of the selected fragments determines ρ positions of possible errors for any non-zero element of the corresponding syndrome, generates based on them, fragments of error vectors of the next step t = t + 1 and passes them to the block for calculating the metric and current syndrome 3.

The correction vector generation unit 5 creates a correction vector from an error vector generated in step t, the syndrome of which is a zero vector.

Correction block 6 corrects errors in the distorted codeword according to the criterion of maximum likelihood. To do this, the distorted code word received from the input of the syndrome 1 calculation unit is added in mod 2 with the correction vector, which is generated in the block for generating the correction vector 5.

The block for generating the information sequence of the codeword 7 performs the inverse transformation of the encoding rule, the corrected or undistorted codeword of the LDPC code into the information sequence, which is transmitted to the output for further processing.

Random access memory 8 performs the storage of current syndromes and, corresponding to them, fragments of error vectors of an adjacent class.

The proposed device operates as follows.

The decoded codeword, possibly distorted in the communication channel, is fed to the input of the syndrome 1 calculation unit, in which the syndrome is determined.

If the syndrome is a zero vector, then the code word according to the maximum likelihood criterion is not distorted, and control is transferred to the block for generating the information sequence of the code word 7.

If the syndrome is not a zero vector, then the syndrome is transmitted to the block for the formation of the initial elements of the error vectors 2.

In the block for generating the initial elements of error vectors 2, for any non-zero element of the syndrome, using the check matrix, we determine the positions from which fragments of error vectors of the adjacent class can begin. These positions allow the formation of nonzero initial elements of fragments of error vectors of an adjacent class, which are stored in random access memory 8 and control is transferred to the unit for calculating the metric and current syndrome 3.

In the block for calculating the metric and the current syndrome 3, for each newly formed fragment of the error vector, the metric and the current syndrome are determined, which, together with its fragment of the error vector, is stored in random access memory 8. If the current syndrome of one of the error vectors is equal to zero vector, then the formation of error vectors of the adjacent class is completed and the error vector with the “zero” syndrome is transmitted to the block for the formation of the correction vector 5, otherwise the control is transferred to the block for the formation of elements longer error vectors 4.

The block for generating the error vector continuation elements 4 sequentially selects the generated fragments of the error vectors of the current step from the random access memory 8, the metric of which is equal to the step number, for each of which the error vector continuation elements are determined. They allow you to continue the formation of error vectors of an adjacent class, which are transmitted to the unit for determining the metric and current syndrome 3.

In the block for generating the correction vector 5, a correction vector is formed from the error vector with the “zero” syndrome.

In block 6 correction is performed bitwise addition mod 2 of the distorted code word with the correction vector.

The corrected codeword is transmitted to the block for generating the information sequence of the codeword 7, in which the information sequence is generated, which is transmitted to the output for further processing.

Decoding of the LDPC codeword is completed.

The implementation of the described device may be hardware, software or hardware-software.

A method of decoding LDPC codes can be applied to decoding with a “soft” solution. To do this, in the calculation unit of the metric and current syndrome 3, when forming the “zero” current syndrome, it is necessary to determine the metric for the adjusted code word, store it in RAM 8 along with its current syndrome and error vector. The execution of the calculation unit of the metric and the current syndrome 3 and the block for generating the continuation elements of the error vectors 4 is repeated until the metric of the newly formed error vectors with “zero” syndromes begins to decrease.

Achievable technical result of the proposed method for decoding LDPC codes with a “hard” and “soft” solution is to improve the quality of decoding LDPC codes by constructing an adjacent class of error vectors ordered by weight, the proposed method belongs to the class of decoding methods by the criterion of maximum likelihood.

Bibliography

1. Gallager R.J. Codes with a low density of parity checks / Per. from English // Ed. Dobrushina R.L .: M., Mir, 1966.

Claims (2)

1. The method of decoding the LDPC code, namely, that for the received possibly distorted codeword, the syndrome and the “relationship vector” of each bit of the codeword with non-zero elements of the syndrome are determined, then those bits of the codeword whose numbers correspond to the positions of the “relationship vector” are inverted "Having values exceeding the selected threshold, and the definition of the current syndrome, the" relationship vector "and the bit inversion is repeated until the current syndrome becomes a zero vector, characterized in that for of any non-zero element of the distorted codeword syndrome, select the corresponding row of the verification matrix, determine the initial elements of fragments of error vectors of an adjacent class by non-zero elements of the selected row, form these fragments, calculate the metric and current syndrome for each of them, then follow the steps for each generated fragment of the error vector the current step, having a metric equal to the step number, for any non-zero element of its current syndrome, select the corresponding row of the check matrix , the non-zero elements of which determine the continuation elements of fragments of error vectors of an adjacent class, form new fragments for which the metric and current syndrome are also calculated, the construction of an adjacent class of error vectors is completed when the current syndrome of one of the error vectors becomes a zero vector, and when decoding with With a “soft” solution, the construction of the weighted adjacent class of error vectors is completed when several error vectors of the adjacent class are generated, and as a correction vector and select the error vector, which has a maximum metric, and then perform the correction of the distorted code word, from which form the information sequence. 2. The LDPC code decoding device for implementing the method according to claim 1, consisting of a block for computing a syndrome, a block for generating the initial elements of the error vectors, a block for calculating the metrics and the current syndrome, a block for generating the elements for continuing the error vectors, a block for generating the correction vector, and a correction block, block forming the information sequence of the code word, random access memory, while the block computing the syndrome has an input for the distorted code word LDPC code, and the first output is connected with the first input of the codeword information sequence generating unit for transmitting the codeword having zero syndrome, and the second output is connected to the first input of the correction unit for transmitting the distorted codeword, and the third output is connected to the initial vector error generating unit for transmitting the distorted codeword and its syndrome, and the first output of the unit for generating the initial elements of the error vectors is connected to the first input of the metric calculation unit and the current syndrome for distortion transmission of the code word and the formed initial elements of the error vectors, and the second output is connected to the random access memory for saving the syndromes and the initial elements of the error vectors, the metric and current syndrome calculation unit is connected to the block for the formation of the error vector continuation elements for transmitting the current syndromes and the continuation elements of the error vectors , as well as connected to random access memory for saving current syndromes and reading elements for continuing error vectors, generating error vector continuation elements is also connected to random access memory for storing error vector continuation elements and reading current syndromes of previously generated error vector fragments, and the third output of the metric calculation unit and the current syndrome are connected to the input of the correction vector generation unit for transmitting an error vector of an adjacent class; the output of the correction vector generation unit is connected to the second input of the correction unit for transmitting the correction vector; the output of the correction block is connected to the second input of the codeword information sequence generating unit for transmitting the corrected codeword, and the codeword information sequence forming unit has an output for transmitting the corrected codeword information sequence of the LDPC code for further processing.