Adaptive scaling of parity check messages for LDPC decoding
The disclosure relates to an LDPC decoding method which involves performing iterations until a stop criterion is satisfied. Each iteration involves calculating variable messages (α n,m ), calculating parity check messages (β m,n ), and calculating a posteriori estimation variables. The parity check messages (β m,n ) and the posteriori estimation variables (γn) being saturated at a predetermined maximum value. At the end of an iteration, when the number of saturations reaches a specified threshold, the method involves at least a first scaling of the parity check messages (β m,n ) and the a posteriori estimation variables (γ n ). Scaling corresponds to assigning, to a value, an integer which has the same sign and whose absolute value is the nearest integer greater than the absolute value of the value divided by two.
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 taken respectively by said variables, the method comprising executing one or more iterations by a processing unit until a stop criterion is met, each iteration comprising:
calculating variable messages, for the different variable nodes, from parity check messages,
calculating parity check messages, for the different parity check nodes, from the variable messages, wherein the parity check messages are stored in a first volatile memory of the decoder,
when the calculated value of a parity check message or of an a posteriori estimation variable exceeds a predetermined saturation value, saturating said calculated value at said saturation value,
calculating a posteriori estimation variables from the parity check messages, wherein the a posteriori estimation variables are stored in a second volatile memory of the decoder,
wherein at the end of an iteration, when a saturation criterion is met, the processing unit performs a first 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, and
wherein, when the stop criterion is met, the method comprises outputting a decoded value of the codeword based on current values of the a posteriori estimation variables.
2. The method according to claim 1 , further including, following the first scaling of the parity check messages and of the a posteriori estimation variables, a second scaling of the parity check messages and of the a posteriori estimation variables after a predetermined number of successive iterations.
3. The method according to claim 2 , in which the decoder supports different coding rates and the predetermined number of successive iterations is predetermined according to the used coding rate.
4. The method according to claim 1 , in which the decoder supports different coding rates and the saturation threshold is predetermined according to the used coding rate.
5. The method according to claim 1 , wherein the parity matrix has a horizontal layered structure, each layer corresponding to one or more consecutive lines of the parity matrix, each layer having one single non-zero element for a given variable.
6. The method according to claim 1 , wherein the LDPC code is a quasi-cyclic code, the parity matrix being obtained by extending a base matrix of size R×C by an expansion factor Z, Z being a positive integer, each element of the base 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.
7. The method according to claim 6 , wherein the parity matrix has a horizontal layered structure, each layer corresponding to one or more consecutive lines of the parity matrix, each layer having one 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 base matrix.
8. The method according to claim 1 , wherein the LDPC code is an irregular code of the “accumulate repeat accumulate” type, so-called LDPC ARA code, or of the “irregular repeat accumulate” type, so-called LPDC IRA code, or of the protograph-based Raptor-like type, so-called LPDC PBRL.
9. The method according to claim 1 , wherein N is greater than or equal to 1,000.
10. The method according to claim 1 , wherein the decoder is configured to decode a codeword with a flow rate greater than or equal to 100 Mbit/s.
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 taken respectively by said variables, the decoder including a processing unit configured to execute one or more iterations until a stop criterion is met, to:
calculate variable messages, for the different variable nodes, from parity check messages,
calculate parity check messages, for the different parity check nodes, from the variable messages, wherein the parity check messages are stored in a first volatile memory of the decoder,
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,
calculate a posteriori estimation variables from the parity check messages, wherein the a posteriori estimation variables are stored in a second volatile memory of the decoder,
wherein, at the end of an iteration, when a saturation criterion is met, the processing unit is configured to perform a first 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, and
wherein, when the stop criterion is met, the processing unit is configured to output a decoded value of the codeword based on current values of the a posteriori estimation variables.
12. The decoder according to claim 11 , wherein, following the first scaling of the parity check messages and of the a posteriori estimation variables, the processing unit is configured to perform a second scaling of the parity check messages and of the a posteriori estimation variables after a predetermined number of successive iterations.
13. The decoder according to claim 12 , wherein the decoder supports different coding rates and the predetermined number of successive iterations is predetermined according to the used coding rate.
14. The decoder according to claim 13 , wherein the decoder supports different coding rates and the saturation threshold is predetermined according to the used coding rate.
15. A satellite including a decoder according to claim 11 .