Stop criterion for decoding an LDPC code
An LDPC decoding method is disclosed in which the LDPC code is defined by a parity matrix having a layered structure, and the method involves performing iterations until a stop criterion is satisfied. Each iteration involves the successive processing of the different layers. Processing a layer involves calculating variable messages (a n,m ), calculating parity check messages, calculating a posteriori estimation variables (γ n ), and calculating a partial syndrome. The evaluation of the stop criterion involves checking if, for a plurality of successive iterations, the number of iterations for which all the partial syndromes are zero, from which the number of iterations for which at least one of the partial syndromes is non-zero is subtracted, is greater than or equal to a predetermined stop threshold.
1. A method for decoding a codeword with a decoder of low-density parity-check code (LDPC) code, said LDPC code being defined by a binary parity matrix of size M×N stored in a memory of the decoder, M and N being positive integers, the parity matrix corresponding to a representation of a bipartite graph comprising connections between M parity check nodes and N variable nodes, each line of the parity matrix corresponding to a parity equation associated with a parity check node, each column of the parity matrix corresponding to a variable associated with a variable node, each non-zero element of the parity matrix corresponding to a connection between a parity check node and a variable node, the codeword to be decoded corresponding to a set of values respectively taken by said variables, the parity matrix presenting a layered structure, the method comprising the execution of one or more iterations by a processing unit until a stop criterion is met, each iteration comprising a successive processing of the layers of the parity matrix, the processing of one layer comprising:
a calculation of variable messages, for the variable nodes involved in said layer, on the basis of a posteriori estimation variables of the codeword and on the basis of parity check messages calculated during the previous iteration,
a calculation of parity check messages, for the parity check nodes involved in said layer, on the basis of the variable messages, wherein the parity check messages are stored in a first volatile memory of the decoder,
a calculation of a posteriori estimation variables on the basis of the parity check messages, wherein the posteriori estimation variables are stored in a second volatile memory of the decoder,
a calculation of a partial syndrome for said layer by applying the parity equations of said layer to the a posteriori estimation variables,
wherein an evaluation of the stop criterion comprises checking, for a plurality of successive iterations, whether the number of iterations for which all the partial syndromes are zero subtracted by the number of iterations for which at least one of the partial syndromes is non-zero is greater than or equal to a predetermined stop threshold.
2. The method according to claim 1 wherein the evaluation of the stop criterion comprises initializing a counter to zero and, at the end of each iteration:
if at least one of the partial syndromes calculated for the different layers during said iteration is non-zero, decrementing the counter by one, unless the counter is equal to zero,
if all the partial syndromes calculated for the different layers during said iteration are zero, incrementing the counter by one, the stop criterion being met when the counter is greater than or equal to the stop threshold.
3. The method according to claim 1 , wherein the parity matrix has a structure in horizontal layers, each layer corresponding to one or more consecutive lines of the parity matrix, each layer having a single non-zero element for a given variable.
4. The method according to claim 1 , wherein the LDPC code is a quasi-cyclic code, the parity matrix being obtained by extending a basis matrix of size R×C by an expansion factor Z, Z being a positive integer, each element of the basis matrix being replaced by a matrix of size Z×Z corresponding either to a zero matrix or to an offset-shift of an identity matrix, the parity matrix including R×Z lines and C×Z columns.
5. The method according to claim 4 , wherein the parity matrix has a structure in horizontal layers, each layer corresponding to one or more consecutive lines of the parity matrix, each layer having a single non-zero element for a given variable, and wherein each layer corresponds to the Z lines of the parity matrix corresponding to a line of the basis matrix.
6. The method according to claim 1 , wherein N is greater than or equal to 1000.
7. The method according to claim 1 , wherein the decoder is configured to decode a codeword with a data rate greater than or equal to 100 Mbit/s.
8. The method according to claim 1 , wherein the decoder supports different coding rates and the stop criterion is predetermined on the basis of the coding rate in use.
9. The method according to claim 1 , wherein for each parity check node and for each variable node to which said parity check node is connected, the calculation of a parity check message comprises:
a determination of a first smallest value among the absolute values of the variable messages associated with said parity check node,
a determination of a second smallest value among the absolute values of the variable messages associated with said parity check node,
at least one first comparison of the difference between the second smallest value and the first smallest value to a first threshold,
a determination of a correction value out of at least two possible values according to a result of the first comparison,
a calculation of the parity check message according to the first smallest value and the correction value.
10. The method according to claim 1 , wherein: when the calculated value of a parity check message or of an a posteriori estimation variable exceeds a predetermined saturation value, said calculated value is saturated at said saturation value, and at the end of an iteration, when a saturation criterion is met, the method comprises a scaling of the parity check messages and of the a posteriori estimation variables, a scaling corresponding to assigning to a value the integer with the same sign whose absolute value is the closest integer greater than the absolute value of the value divided by two, the saturation criterion being met when one or more of the following conditions is met:
a number of saturations of the parity check messages is greater than or equal to a first saturation threshold,
a number of saturations of the a posteriori estimation variables is greater than or equal to a second saturation threshold,
a sum of the number of saturations of the parity check messages and of the number of saturations of the a posteriori estimation variables is greater than or equal to a third saturation threshold.
11. A decoder of low-density parity-check code (LDPC) code, said LDPC code being defined by a binary parity matrix of size M×N stored in a memory of the decoder, M and N being positive integers, the parity matrix corresponding to a representation of a bipartite graph comprising connections between M parity check nodes and N variable nodes, each line of the parity matrix corresponding to a parity equation associated with a parity check node, each column of the parity matrix corresponding to a variable associated with a variable node, each non-zero element of the parity matrix corresponding to a connection between a parity check node and a variable node, a codeword to be decoded corresponding to a set of values respectively taken by said variables, the parity matrix presenting a layered structure, the decoder including a processing unit configured to execute one or more iterations until a stop criterion is met and, at each iteration and for each layer, to:
calculate variable messages, for the variable nodes involved in said layer, on the basis of a posteriori estimation variables of the codeword and on the basis of parity check messages calculated during the previous iteration,
calculate parity check messages, for the parity check nodes involved in said layer, on the basis of the variable messages, wherein the parity check messages are stored in a first volatile memory of the decoder,
calculate a posteriori estimation variables on the basis of the parity check messages, wherein the posteriori estimation variables are stored in a second volatile memory of the decoder,
calculate a partial syndrome for said layer by applying the parity equations of said layer to the a posteriori estimation variables,
wherein the processing unit is configured to evaluate the stop criterion by checking, for a plurality of successive iterations, whether the number of iterations for which all the partial syndromes are zero subtracted by the number of iterations for which at least one of the partial syndromes is non-zero is greater than or equal to a predetermined stop threshold.
12. The decoder according to claim 11 wherein the processing unit is configured to initialize a counter to zero and, at the end of each iteration:
if at least one of the partial syndromes calculated for the different layers during said iteration is non-zero, decrement the counter by one, unless the counter is equal to zero,
if all the partial syndromes calculated for the different layers during said iteration are zero, increment the counter by one, the stop criterion being met when the counter is greater than or equal to the stop threshold.
13. The decoder according to claim 11 wherein, for each parity check node and for each variable node to which said parity check node is connected, in order to calculate a parity check message, the processing unit is configured to:
determine a first smallest value among the absolute values of the variable messages associated with said parity check node,
determine a second smallest value among the absolute values of the variable messages associated with said parity check node,
perform at least one first comparison of the difference between the second smallest value and the first smallest value to a first threshold,
determine a correction value out of at least two possible values according to a result of the first comparison,
calculate the parity check message according to the first smallest value and the correction value.
14. The decoder according to claim 11 wherein, when the calculated value of a parity check message or of an a posteriori estimation variable exceeds a predetermined saturation value, said calculated value is saturated at said saturation value, and at the end of an iteration, when a saturation criterion is met, the processing unit is configured to perform a scaling of the parity check messages and of the a posteriori estimation variables, a scaling corresponding to assigning to a value the integer with the same sign whose absolute value is the closest integer greater than the absolute value of the value divided by two, the saturation criterion being met when one or more of the following conditions is met:
a number of saturations of the parity check messages is greater than or equal to a first saturation threshold,
a number of saturations of the a posteriori estimation variables is greater than or equal to a second saturation threshold,
a sum of the number of saturations of the parity check messages and of the number of saturations of the a posteriori estimation variables is greater than or equal to a third saturation threshold.
15. A satellite comprising a decoder according to claim 11 .