Abstract:
A method is proposed for decoding a plurality of data packets received through a meshed communications network for the retrieval of source packets transmitted by one or more source nodes, the meshed communications network comprising relay nodes generating combined packets, each combined packet consisting of a linear combination of source packets. During the decoding by a destination node, this method consists in performing two decoding operations of which the first is a decoding by group of packets and the second is a decoding that takes account of pieces of likelihood information resulting from the first decoding. The fact of first of all carrying out a decoding with groups of packets makes it possible to exploit the repetitions (or redundancies) of packets in a meshed network to optimize the bit error rate during the decoding of source data transmitted on the communications network.

Description:
BACKGROUND 
       [0001]    1. Field of the Disclosure 
         [0002]    The field of the disclosure is that of communications networks. More specifically, the disclosure can be applied in the context of a communications network in which each data packet coming from a source node is encoded, for example with an LDPC (low density parity check) type encoding, i.e. a code for which the parity check matrix is of low density), and is then decoded by a destination node. 
         [0003]    2. Related Art 
         [0004]    Here below in this document, the disclosure will focus more particularly on a description of the problems and issues existing in the decoding of source data packets encoded according to an LDPC type encoding in a meshed communications network, which the inventors of the present patent application have had to cope with. Naturally, the disclosure is not limited to this particular field of application. 
         [0005]      FIG. 1  is a schematic illustration of a wireless meshed network formed by a source node  101 , several relay nodes ( 101 ,  102 ,  103 ,  104 ,  105 ) and a destination node  106 . 
         [0006]    Clearly, a meshed network of this kind may comprise several source nodes  101  and several destination nodes  106 . 
         [0007]    The description here below will be situated by way of an illustrative example in a case where the data packets sent out by the source node  101  are encoded source packets b 1  and b 2  resulting from an LDPC type channel encoding. 
         [0008]    In  FIG. 1 , the encoded source packets b 1  and b 2  are relayed by the relay nodes  101  to  105 . 
         [0009]    Classically, the encoded source packets b 1  and b 2  may be either relayed as such (i.e. without combination with other data packets), as is the case with the relay nodes  102  and  103  in the example of  FIG. 1 , or combined with other data packets as is the case for example with the relay nodes  104  and  105  in the example of  FIG. 1 . 
         [0010]    A relay node may therefore:
       either combine data packets received at input and then transmit a combined data packet, for example a linear combination of the data packets received at input. This case, the relay node is called a “combinant relay node”;   or simply relay data packets received at input without creating a combination between data packets. In this case, the relay node is called a “non-combinant relay node”.       
 
         [0013]    It must be noted that a packet received at input of a relay node may be either an encoded source packet (b 1  or b 2 ) or a linear combination of encoded source packets. 
         [0014]    In the example of  FIG. 1 , the destination node  106  receives four packets:
       two packets y 1  and y 2  not combined by the non-combinant relay nodes  102  and  103  respectively, and   two combined packets Pc and Pc′, each resulting from a same linear combination of the encoded source packets b 1  and b 2 . This linear combination (b 1 +b 2 ) is made by the combinant relay node  104  for the combined packet Pc and by the combinant relay node  105  for the combined packet Pc′).       
 
         [0017]    A description shall now be given of a prior art technique currently used in the above-mentioned context, i.e. a meshed network comprising a destination node which must perform a decoding on the basis of several received packets, for which certain packets (known as combined packets) result from a same linear combination. 
         [0018]    Once the set of data packets has been received at its input, the destination node  106  applies an LDPC decoding to each data packet received. Each decoding is done with a parity check matrix for the LDPC decoding on an input vector formed by the four received packets: y 1 , y 2 , Pc and Pc′. 
         [0019]    If the LDPC decoding converges towards a correct solution, the destination node retrieves the originally sent source data packets. 
         [0020]    Such a convergence of an LDPC decoding is obtained when the rows and the columns of the decoding parity check matrix built at the destination node  106  are mutually independent, i.e. when the parity check matrix has no cycles. Indeed, these cycles are present when the rows or columns of the parity matrix have a certain correlation or resemblance with one another. 
         [0021]    The cycles in question are determined from a representation in the form of a graph of an LDPC parity matrix. These graphs link the nodes of variables (which correspond to the bits of each LDPC code word) and parity variables (which correspond to the parity bits in an LDPC code word) 
         [0022]    A cycle in a graph is a path on the graph that makes it possible to go out from a node and return to this same node without passing through the same branch. The size of a cycle is given by the number of branches contained within the cycle. The size of the shortest cycle is called a “girth”. The presence of cycles in the graph impairs decoding performance because of a phenomenon of self-confirmation during the decoding. 
         [0023]    Now, when the decoding is done from received packets which result from a same linear combination, this inevitably leads to a correlation between the rows of the parity matrix, even in the event of different errors present in each of the packets. Different errors may affect the combined packets when these packets are transmitted through different channels to the destination node. 
         [0024]    This is the case for example in  FIG. 1  where the combined packets Pc and Pc′ come from a same basic combination and are therefore mutually correlated. The rows of the decoding matrix are therefore not independent of one another. 
         [0025]    Thus, for a meshed network, the classic LDPC decoding using a parity matrix is not optimal owing to the presence of these repetitions of messages within the communications network. 
       SUMMARY 
       [0026]    The disclosure, in at least one embodiment, is aimed especially at overcoming these different drawbacks of the prior art. 
         [0027]    More specifically, it is the goal of at least one embodiment of the invention to provide the technique for optimising the bit error rate during the decoding of source data transmitted on a communications network in the above-mentioned context, i.e. in the context of a meshed network comprising a destination node that has to perform a decoding on the basis of several received packets, and of which certain packets (known as combined packets) result from a same linear combination, but is performed by at least one different combinant relay node (for each combined packet). 
         [0028]    It is another goal of at least one embodiment of the invention to provide a technique for implementing a solution adapted to any type whatsoever of combination of data packets made by the relay nodes. 
         [0029]    It is another goal of at least one embodiment of the invention to provide a technique by which it is not necessary to modify the encoding operations performed by the source nodes and the combining operations or relaying operations of the relay nodes. 
         [0030]    It is another goal of at least one embodiment of the invention to provide a technique of this kind that can be used to optimise bandwidth. 
         [0031]    It is another goal of at least one embodiment of the invention to provide a technique of this kind that is simple to implement and costs little. 
         [0032]    One particular embodiment of the invention proposes a method for decoding a plurality of data packets received through a meshed communications network for the retrieval of source packets transmitted by one or more source nodes, the meshed communications network comprising relay nodes generating combined packets, each combined packet consisting of a linear combination of source packets. 
         [0033]    In a remarkable way, this method is implemented by a destination node and comprises steps for:
       forming groups of received packets comprising combined packets, each group comprising no more than one packet among a plurality of combined packets which consist of a same linear combination of source packets;   performing, for each group, a first decoding of the packets of said group, said first decoding being performed by a first decoder implementing a belief propagation algorithm delivering a piece of likelihood information for said group;   combining the pieces of likelihood information obtained by the first decoding performed for the different groups, to obtain a combination of pieces of likelihood information;   performing a second decoding of said combination of pieces of likelihood information, said second decoding being performed by a second decoder capable of processing pieces of likelihood information.       
 
         [0038]    Thus, this particular embodiment of the invention relies on a wholly novel and inventive approach in which two consecutive decoding operations (instead of only one decoding operation as in the prior art) are performed during the decoding by the destination node, the first decoding operation of which is a decoding by groups of packets and the second of which is a decoding that takes account of likelihood information resulting from the first decoding. The fact of performing first of all one decoding with groups of packets enables the exploitation of repetitions (or redundancies) of packets in a meshed network to optimise the bit error rate during the decoding of source data transmitted on the communications network. 
         [0039]    The present disclosure finds application more particularly in a decoding operation that implements hollow decoding matrices jointly with an application of the belief propagation algorithm so as to obtain a convergence of said decoding, for example of an LDPC type, toward an accurate solution. Indeed, through the use of groups of data packets, each first decoding is done with a small-sized decoding matrix whose rows are not mutually correlated. The bit error rate is thereby reduced during the application of the second decoding to a single vector formed out of the trust values of each group. 
         [0040]    Thus, the present disclosure can be used to adapt to any type of combination of data packets performed by the relay nodes. 
         [0041]    The step of combining pieces of trust information advantageously also optimises the bandwidth by averaging the pieces of trust information. This combination gives an average value of this information with a low value of standard deviation of the noise related to the communications channel. 
         [0042]    Advantageously, each group of received packets comprises data packets corresponding to a same set of at least one source packet transmitted by said source node or nodes. 
         [0043]    Thus, the present disclosure enables the use of smaller-sized decoding matrices and therefore reduces the computation time during the decoding of the source data by the destination node. 
         [0044]    Advantageously, the first and second decoding operations are LDPC type operations. 
         [0045]    The decoding is thereby improved, the belief propagation algorithm improving the decoding when the decoding matrices are hollow, which is the case for an LDPC decoding. 
         [0046]    Advantageously, the first and second decoding operations are decodings in the logarithmic domain, the step for combining being a step of summation or weighted summation of each piece of trust information. 
         [0047]    Thus, the computation operations are limited. 
         [0048]    According to an advantageous characteristic, each linear combination is done by means of an “Exclusive-OR” operation. 
         [0049]    Thus, the computation operations are simplified. 
         [0050]    In another embodiment, the disclosure concerns a computer program product downloadable from a communications network and/or recorded on a computer-readable carrier and/or executable by a processor. This computer program product comprises program code instructions for implementing the above-mentioned method (in any of its different embodiments) when said program is executed on a computer. 
         [0051]    In another particular embodiment, the disclosure concerns a computer-readable storage means storing a computer program comprising a set of instructions executable by a computer for implementing the above-mentioned method (in any of its different embodiments). 
         [0052]    In another embodiment, the disclosure pertains to a destination node for decoding a plurality of data packets received through a meshed communications network for the retrieval of source packets transmitted by one or more source nodes, the meshed communications network comprising relay nodes generating combined packets, each combined packet consisting of a linear combination of source packets. 
         [0053]    In a remarkable way, the destination node comprises:
       means for forming groups of received packets comprising combined packets, each group comprising no more than one packet among the combined packets consisting of a same linear combination of source packets;   first means for decoding making it possible to perform, for each group, a first decoding of the packets of said group, said first decoding being performed by a first decoder implementing a belief propagation algorithm delivering a piece of likelihood information for said group;   means for combining the pieces of likelihood information obtained by the first decoding performed for the different groups, to obtain a combination of pieces of likelihood information;   second means for decoding to perform a second decoding of said combination of pieces of likelihood information, said second decoding being performed by a second decoder capable of processing pieces of likelihood information.       
 
         [0058]    Advantageously, said destination node comprises means for selecting a same set of at least one source packet transmitted by said source node or nodes, each group of received packets comprising data packets corresponding to said same set. 
         [0059]    Thus, at least one embodiment of the invention enables the use of smaller-sized decoding matrices and therefore reduces the computation time during the decoding of the source data by the destination node. 
         [0060]    Advantageously, the first and second decoding operations are LDPC type operations. 
         [0061]    Advantageously, the first and second decoding operations are decodings in the logarithmic domain, said means for combining likelihood information performing a summation or a weighted summation of each piece of trust information. 
         [0062]    Again, each linear combination is done by means of an “Exclusive-OR” type operation. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0063]    Other features and advantages of the disclosure shall appear from the following description, given by way of an indicative and non-restrictive example, and from the appended drawings, of which: 
           [0064]      FIG. 1  (described with reference to the prior art) is a schematic illustration of a classic example of a wireless meshed communications network with multiple paths comprising a source node, a destination node and relay nodes; 
           [0065]      FIG. 2  is a schematic illustration of a Tanner graph (a) and a graph (b) organised with a view to graph decoding; 
           [0066]      FIG. 3  is a schematic illustration of an encoding scheme in a meshed communications network comprising two source nodes, two relay nodes and one destination node, according to one particular embodiment of the invention; 
           [0067]      FIG. 4  is a schematic illustration of an architecture of a decoder of a destination node, according to one particular embodiment of the invention; 
           [0068]      FIG. 5  is a schematic illustration of a decoding method implemented by the decoder of  FIG. 4 , according to one particular embodiment of the invention; 
           [0069]      FIG. 6  illustrates a bit error rate curve as a function of the signal-to-noise ratio for a decoding without relay nodes, with two relay nodes (the classic method) and with two relay nodes according to one particular embodiment of the invention; 
           [0070]      FIG. 7  is a schematic illustration of a device adapted to implementing the method of  FIG. 5 , according to one particular embodiment of the invention. 
       
    
    
     DETAILED DESCRIPTION 
       [0071]      FIG. 3  is a schematic illustration of an example of an encoding scheme in a meshed communications network comprising two source nodes, two relay nodes and one destination node, according to one particular embodiment of the invention. 
         [0072]    More specifically,  FIG. 3  illustrates a joint LDPC and network encoding scheme in one and the same meshed network. 
         [0073]    Classically, a packet received at input of a relay node can be either an encoded source packet or a linear combination of encoded source packets. In the latter case, the combining operation done by the relay nodes corresponds to the network encoding. 
         [0074]    Let us take two source nodes  301  and  302  applying an LDPC type encoding, respectively  306  and  307 . 
         [0075]    The source nodes  301  and  302  each transmit an encoded source packet respectively b 1  and b 2 :
       to each relay node  303  and  304  through communications channels  311 ,  312 ,  313  and  314 ;   to the destination node  305  through communication channels  315  and  318 .       
 
         [0078]    The destination node  305  thus directly receives the packets b 1  and b 2  from the source nodes  301  and  302  if it is assumed that the transmission channel is without communications errors. If we consider the transmission errors on the transmission channels, the encoded source data packets b 1  and b 2  respectively have corresponding data packets Y 1  and Y 2 , i.e. the source data packets b 1  and b 2  affected by communications errors. 
         [0079]    The relay nodes  303  and  304  for their part apply a linear combination of the encoded source packets b 1  and b 2  received at input, respectively by means of the blocks  308  and  309  in order to determine combined packets, YR 1  and YR 2  respectively, which will them be transmitted to the destination node  305  through the channels  316  and  317 . 
         [0080]    In one particular embodiment of the invention, the combination of the packets by the relay nodes  303  and  304  can be performed by a simple “Exclusive-OR” (commonly abbreviated as “XOR”) addition on all the bits of the packets to be combined. 
         [0081]    A description shall now be made of a combination of received packets at input of a relay node (for example the relay node  303  of  FIG. 3 ). These packet may be either encoded source packets b 1  and b 2  that are not modified or linear combinations of the source packets b 1  and b 2 . 
         [0082]    Let us take two source packets sized 10 bits each:
       a packet b 1 =[1 0 0 1 0 0 1 1 0 0] and;   a packet b 2 =[0 1 0 1 1 0 1 0 0 0].   The resulting combined packet is then written (using the “Exclusive-OR” operation) as: b 1 XOR b 2 =[1 1 0 0 1 0 0 1 0 0].       
 
         [0086]    An identical form of reasoning is applied to the relay node  304  in  FIG. 3 . 
         [0087]    The non-combined packets Y 1 , Y 2  correspond to the source data packets b 1  and b 2  received directly from the source nodes  301  and  302  respectively and possibly affected by transmission errors owing to the fact that a communications channel of a network is subject to communications errors during data transmission. 
         [0088]    The non-combined packets YR 1  and YR 2  for their part correspond to the combinations of encoded source data packets b 1  and b 2  or else to combinations of data packets Y 1 , Y 2  possibly affected by errors. These two combined packets YR 1  and YR 2  come respectively from the relay nodes  303  and  304 . 
         [0089]    The destination node  305  of  FIG. 3  therefore receives four packets (in the example of  FIG. 3 ): Y 1 , Y 2 , YR 1  and YR 2 . These packets are then decoded by this destination node by means of a joint network and LDPC decoding on the basis of the four received packets and a parity matrix HH (or decoding matrix). 
         [0090]    We shall now describe an example of computation of the parity matrix HH. 
         [0091]    Let H be the parity matrix used to encode messages at the source nodes  301  and  302 . The packets transmitted by the source nodes are formed by blocks. Each of these blocks is an LDPC code word denoted as b 1  (for the source node  301 ) and b 2  (for the source node  302 ). These last two packets satisfy the following two equations: 
         [0000]      H.b 1   T =0 
         [0000]      H.b 2   T =0 
         [0092]    Each of the relay nodes  303  and  304  (in the example of  FIG. 3 ) for its part computes a combined packet b 3 =b 1  XOR b 2 . A comprehensive parity matrix can thus be determined as a function of the parity matrix H and the relationship between b 3 , b 2  and b 1 . The comprehensive parity matrix is written as followed: 
         [0000]    
       
         
           
             
               
                 
                   HH 
                   = 
                   
                     ( 
                     
                       
                         
                           H 
                         
                         
                           
                             zeros 
                              
                             
                                 
                             
                              
                             
                               ( 
                               
                                 K 
                                 , 
                                 N 
                               
                               ) 
                             
                           
                         
                         
                           
                             zeros 
                              
                             
                                 
                             
                              
                             
                               ( 
                               
                                 K 
                                 , 
                                 N 
                               
                               ) 
                             
                           
                         
                       
                       
                         
                           
                             zeros 
                              
                             
                                 
                             
                              
                             
                               ( 
                               
                                 K 
                                 , 
                                 N 
                               
                               ) 
                             
                           
                         
                         
                           H 
                         
                         
                           
                             zeros 
                              
                             
                                 
                             
                              
                             
                               ( 
                               
                                 K 
                                 , 
                                 N 
                               
                               ) 
                             
                           
                         
                       
                       
                         
                           
                             I 
                              
                             
                               ( 
                               
                                 N 
                                 , 
                                 N 
                               
                               ) 
                             
                           
                         
                         
                           
                             I 
                              
                             
                               ( 
                               
                                 N 
                                 , 
                                 N 
                               
                               ) 
                             
                           
                         
                         
                           
                             I 
                              
                             
                               ( 
                               
                                 N 
                                 , 
                                 N 
                               
                               ) 
                             
                           
                         
                       
                     
                     ) 
                   
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
         [0093]    With: N being the size of the LDPC code word;
       K the number of parity bits of an LDPC code word;   zeros(K,N) represents a matrix with zero elements, sized K×N;   I(N,N) represents an identity matrix N×N.       
 
         [0097]      FIG. 4  is a schematic illustration of an architecture of a joint LDPC and network decoder  400  according to a particular embodiment for a meshed network comprising at least two relay nodes and two source nodes (corresponding to the two source nodes  301  and  302  in  FIG. 3 ). This decoder  400  corresponds to the decoder  310  of the destination node  305  in  FIG. 3 . 
         [0098]    According to one particular embodiment of the invention, the decoder  400  (of the destination node  305 ) receives at input at least two different groups of data packets, each group comprising non-combined packets identical for all the groups and a combined packet which is different from each group, each non-combined packet resulting from the transmission, by a different source node, of a different encoded source packet included in a determined set of encoded source packets, all the combined packets resulting from a same linear combination of the encoded source packets of said set, said linear combination being done by at least one different combinant relay node for each combined packet. 
         [0099]    In the example of  FIG. 4 , the decoder  400  (of the destination node  305 ) inputs N different groups of data packets, each group being a triplet of packets comprising the two non-combined packets Y 1  and Y 2  coming from the source nodes and a combined packet YRi (with i ranging from 1 to n) coming from a relay node i, the destination node receiving n combined packets coming from n relay nodes of the set of relay nodes of the meshed network. 
         [0100]    According to one particular embodiment of the invention, on all the triplets of packets (Y 1 , Y 2 , YRn) a first LDPC decoding is applied, this encoding being performed respectively by first LDPC decoders  401 ,  402  . . .  40   n.  Each first LDPC decoding is done using the corresponding triplet of packets and the matrix HH with application of a Tanner graph and the steps of a “belief propagation” algorithm. 
         [0101]    A brief description shall now be provided of the way in which a Tanner graph is built as well as the different steps implemented during the execution of a “belief propragation” algorithm to carry out a decoding better known as a “decoding on graphs”. 
         [0102]    A code may be defined as a set of variables which meet a set of constraints. A graph can then be built so as to represent these relationships between variables and constraints. 
         [0103]      FIG. 2  provides a schematic illustration of a graph of this kind in which a variable is represented by a square and a constrain by a circle. 
         [0104]    Let C be the code on the Galois field of the binary elements or bits defined by the parity check matrix H. 
         [0000]    
       
         
           
             H 
             = 
             
               [ 
               
                 
                   
                     1 
                   
                   
                     1 
                   
                   
                     1 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     1 
                   
                   
                     1 
                   
                   
                     1 
                   
                   
                     0 
                   
                   
                     0 
                   
                 
                 
                   
                     1 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     1 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     1 
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     1 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     1 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     1 
                   
                 
               
               ] 
             
           
         
       
     
         [0105]    The linear code C is the set of 8-uplets x={x 1 ,x 2 ,x 3 ,x 4 ,x 5 ,x 6 ,x 7 ,x 8 } which satisfy the equation: 
         [0000]      H.x t =0. 
         [0106]    Thus, checking that x belongs to the linear code C is equivalent to checking the following condition: 
         [0000]      [ x 1+ x 2+ x 3=0] and; 
         [0000]      [ x 4+ x 5+ x 6=0] and; 
         [0000]      [ x 1+ x 4+ x 7=0] and [ x 2+ x 5+ x 8=0]. 
         [0107]    The constraints consist in meeting all the parities and the function associated with this constraint is the sum modulo 2. 
         [0108]      FIG. 2  illustrates the corresponding graph in two depictions where the circle represents the sum modulo 2. This graph is better known as a Tanner graph. 
         [0109]    This Tanner graph is used especially to set up a quantified decision decoding. Associated with each variable of the code is the value of the symbol received after transmission, this value being capable of being quantified. 
         [0110]    An algorithm known as a “belief propagation” algorithm or “message propagation” algorithm is then set up with a graph as a support. 
         [0111]    There are several existing versions of belief propagation algorithms. 
         [0112]    We shall now describe the most commonly implemented version which makes use of logarithmic values and is better known as an algorithm for decoding in the logarithmic domain. Indeed, it is desirable to do the computations in the logarithmic domain because the multiplications are converted into additions, thus making the computations far less complex. 
         [0113]    This algorithm is more amply described in Jian Sun, “An introduction to low density parity check (LDPC) codes”, WCRL Seminar Series, 3 Jun. 2003. 
         [0114]    The algorithm for decoding in the logarithmic domain can be defined as follows: 
         [0000]        L ( q   ij )=α ij .β ij  
 
         [0000]      α ij =sign( L ( q   ij ))
 
         [0000]      β ij =abs( L ( q   ij ))
 
         [0000]    At the initializing step: 
         [0000]        L ( c   i )=2 y   i /σ 2  
 
         [0000]        L ( q   ij )= L ( c   i ) 
         [0115]    With: 
         [0116]    y i  the ith noisy sample received and modulated in BPSK (1 for 0 et −1 for 1)) 
         [0117]    σ the standard deviation of the noise 
         [0118]    A first step (step 1) is a step for sending a message to a constraint node and then computing the response L(r ji ): 
         [0000]    
       
         
           
             
               L 
                
               
                 ( 
                 
                   r 
                   ji 
                 
                 ) 
               
             
             = 
             
               
                 φ 
                 ( 
                 
                   
                     ∑ 
                     
                       
                         i 
                         ′ 
                       
                       ∈ 
                       
                         R 
                         
                           j 
                           / 
                           i 
                         
                       
                     
                   
                    
                   
                     φ 
                      
                     
                       ( 
                       
                         β 
                         
                           
                             i 
                             ′ 
                           
                            
                           j 
                         
                       
                       ) 
                     
                   
                 
                 ) 
               
               · 
               
                 
                   ∏ 
                   
                     
                       i 
                       ′ 
                     
                     ∈ 
                     
                       R 
                       
                         j 
                         / 
                         i 
                       
                     
                   
                 
                  
                 
                   α 
                   
                     
                       i 
                       ′ 
                     
                      
                     j 
                   
                 
               
             
           
         
       
       
         
           
             
               With 
                
               
                 : 
               
                
               
                   
               
                
               
                 φ 
                  
                 
                   ( 
                   x 
                   ) 
                 
               
             
             = 
             
               log 
               ( 
               
                 
                   
                      
                     x 
                   
                   + 
                   1 
                 
                 
                   
                      
                     x 
                   
                   - 
                   1 
                 
               
               ) 
             
           
         
       
     
         [0119]    A second step (step 2) is a step for receiving the responses and computing the new message 
         [0000]    
       
         
           
             
               L 
                
               
                 ( 
                 
                   q 
                   ij 
                 
                 ) 
               
             
             = 
             
               
                 L 
                  
                 
                   ( 
                   
                     c 
                     i 
                   
                   ) 
                 
               
               + 
               
                 
                   ∑ 
                   
                     
                       j 
                       ′ 
                     
                     ∈ 
                     
                       C 
                       
                         i 
                         / 
                         j 
                       
                     
                   
                 
                  
                 
                   L 
                    
                   
                     ( 
                     
                       r 
                       
                         
                           j 
                           ′ 
                         
                          
                         i 
                       
                     
                     ) 
                   
                 
               
             
           
         
       
     
         [0120]    Then the steps 1 and 2 are repeated for a predefined number of iterations. 
         [0121]    A third step (step 3) is a step for making a quantified decision on the basis of the computer logarithmic values: 
         [0000]    
       
         
           
             
               L 
                
               
                 ( 
                 
                   Q 
                   i 
                 
                 ) 
               
             
             = 
             
               
                 L 
                  
                 
                   ( 
                   
                     c 
                     i 
                   
                   ) 
                 
               
               + 
               
                 
                   ∑ 
                   
                     
                       j 
                       ′ 
                     
                     ∈ 
                     
                       C 
                       i 
                     
                   
                 
                  
                 
                   L 
                    
                   
                     ( 
                     
                       r 
                       ji 
                     
                     ) 
                   
                 
               
             
           
         
       
     
         [0122]    A fourth step (step four) is used to take a decision: 
         [0000]      If  L ( Qi )&lt;0 then  c   i =1 
         [0000]      Else c i =0 
         [0123]    In this belief propagation algorithm, it is necessary to know the value of the standard deviation of the noise σ. This implies an estimation of the signal-to-noise ratio. 
         [0124]    One simplification described here below enables this constraint to be overcome. However, the result of this is a less optimal decoding. This simplification is more amply described in Ahmad Darabiha, Anthony Chan Carusone and Frank R. Kschischang, “A Bit-Serial Approximate Min-Sum LDPC Decoder and FPGA Implementation”, IEEE International Symposium on Circuits and Systems (ISCAS) 2006, Island of Kos, Greece. 
         [0125]    Indeed, at initialization we may consider: 
         [0000]        L ( c   i )= y   i    
         [0126]    Another simplification can be made when computing the expression 
         [0000]    
       
         
           
             
               φ 
               ( 
               
                 
                   ∑ 
                   
                     
                       i 
                       ′ 
                     
                     ∈ 
                     
                       R 
                       
                         j 
                         / 
                         i 
                       
                     
                   
                 
                  
                 
                   φ 
                    
                   
                     ( 
                     
                       β 
                       
                         
                           i 
                           ′ 
                         
                          
                         j 
                       
                     
                     ) 
                   
                 
               
               ) 
             
             . 
           
         
       
     
         [0000]    Indeed, this term may be approximated by the expression 
         [0000]    
       
         
           
             φ 
             ( 
             
               φ 
               ( 
               
                 
                   min 
                   
                     i 
                     ′ 
                   
                 
                  
                 
                   β 
                   
                     
                       i 
                       ′ 
                     
                      
                     j 
                   
                 
               
               ) 
             
             ) 
           
         
       
     
         [0000]    which is equal to 
         [0000]    
       
         
           
             
               min 
               
                 i 
                 ′ 
               
             
              
             
               
                 β 
                 
                   
                     i 
                     ′ 
                   
                    
                   j 
                 
               
               . 
             
           
         
       
     
         [0000]    The expression of the step one then becomes: 
         [0000]    
       
         
           
             
               L 
                
               
                 ( 
                 
                   r 
                   ji 
                 
                 ) 
               
             
             = 
             
               
                 min 
                 
                   i 
                   ′ 
                 
               
                
               
                 
                   β 
                   
                     
                       i 
                       ′ 
                     
                      
                     j 
                   
                 
                 · 
                 
                   
                     ∏ 
                     
                       
                         i 
                         ′ 
                       
                       ∈ 
                       
                         R 
                         
                           j 
                           / 
                           i 
                         
                       
                     
                   
                    
                   
                     α 
                     
                       
                         i 
                         ′ 
                       
                        
                       j 
                     
                   
                 
               
             
           
         
       
     
         [0127]    According to one particular embodiment of the invention, each first decoder implements only the initializing steps 1, 2 and 3 of the belief propagation algorithm. Thus, each first decoding of a group (or triplet of packets y 1 , y 2  and yRi) has, at output of each first LDPC decoder ( 401 ,  402 , . . .  40   n ), a corresponding vector which is a vector of likelihood logarithm values respectively (L 1 , L 2 , . . . Ln). Indeed, each vector of the likelihood values Li is the concatenation of the likelihood vectors of the packets y 1 , y 2  and yRi. These vectors Li are obtained from application of the steps 1, 2 and 3 of the belief propagation algorithm in using the matrix HH given by the equation 1. Should one of the packets y 1 , y 2  and yRi be missing before the first decoding, the initial values of the likelihood logarithm of the missing packet are initialized with the value zero. 
         [0128]    These computed values of likelihood logarithms (L 1 , L 2  . . . Ln) are then added up, bit by bit, by means of an addition block  404 . The result Lr generated at output of this addition block is then a vector sized 3*N if each group has three packets. 
         [0129]    This result Lr is then used by the second LDPC decoder  405 . Just like the first LDPC decoders  401 ,  402 , . . .  40   n,  the second LDPC decoder  405  uses the parity matrix HH to carry out its decoding. Indeed the packets b 1 , b 2  and b 3 =b 1  XOR b 2  meet the following equation: 
         [0000]    
       
         
           
             
               
                 ( 
                 
                   
                     
                       H 
                     
                     
                       
                         zeros 
                          
                         
                             
                         
                          
                         
                           ( 
                           
                             K 
                             , 
                             N 
                           
                           ) 
                         
                       
                     
                     
                       
                         zeros 
                          
                         
                             
                         
                          
                         
                           ( 
                           
                             K 
                             , 
                             N 
                           
                           ) 
                         
                       
                     
                   
                   
                     
                       
                         zeros 
                          
                         
                             
                         
                          
                         
                           ( 
                           
                             K 
                             , 
                             N 
                           
                           ) 
                         
                       
                     
                     
                       H 
                     
                     
                       
                         zeros 
                          
                         
                             
                         
                          
                         
                           ( 
                           
                             K 
                             , 
                             N 
                           
                           ) 
                         
                       
                     
                   
                   
                     
                       
                         I 
                          
                         
                           ( 
                           
                             N 
                             , 
                             N 
                           
                           ) 
                         
                       
                     
                     
                       
                         I 
                          
                         
                           ( 
                           
                             N 
                             , 
                             N 
                           
                           ) 
                         
                       
                     
                     
                       
                         I 
                          
                         
                           ( 
                           
                             N 
                             , 
                             N 
                           
                           ) 
                         
                       
                     
                   
                 
                 ) 
               
               · 
               
                 [ 
                 
                   
                     
                       
                         b 
                          
                         
                             
                         
                          
                         1 
                       
                     
                   
                   
                     
                       
                         b 
                          
                         
                             
                         
                          
                         2 
                       
                     
                   
                   
                     
                       
                         b 
                          
                         
                             
                         
                          
                         1 
                          
                         
                             
                         
                          
                         xor 
                          
                         
                             
                         
                          
                         b 
                          
                         
                             
                         
                          
                         2 
                       
                     
                   
                 
                 ] 
               
             
             = 
             
                 
               
                 [ 
                 
                   
                     
                       
                         zeros 
                          
                         
                             
                         
                          
                         
                           ( 
                           
                             K 
                             , 
                             1 
                           
                           ) 
                         
                       
                     
                   
                   
                     
                       
                         zeros 
                          
                         
                             
                         
                          
                         
                           ( 
                           
                             K 
                             , 
                             1 
                           
                           ) 
                         
                       
                     
                   
                   
                     
                       
                         zeros 
                          
                         
                             
                         
                          
                         
                           ( 
                           
                             N 
                             , 
                             1 
                           
                           ) 
                         
                       
                     
                   
                 
                 ] 
               
             
           
         
       
     
         [0000]    Or else again: HH.B=zeros(K+K+N,1) with B=[b 1 ;b 2 ;b 1  xor b 2 ] 
         [0130]      FIG. 5  provides a schematic illustration of a decoding method  500  implemented by the decoder  400  of  FIG. 4 , this decoder  400  being implanted at the destination node  305  ( FIG. 5 ). 
         [0131]    A first step  501  is a step for initializing the decoder  400 . 
         [0132]    A second step  502  enables the reception of:
       of at least two non-combined data packets (i.e. transmitted directly by the source nodes  301  and  302  in the example of an architecture in  FIG. 3 ) and;   n combined packets YR 1 , YR 2 , . . . YRn (i.e. the packets generated and transmitted by n relay nodes along the n relay nodes belonging to the meshed network).       
 
         [0135]    A third step  503  then determines n groups of packets (or n triplets), each nth group (or triplet) comprising at least two non-combined packets and one combined nth packet. 
         [0136]    Then, in a step  504 , a first LDPC decoding (as explained in greater detail here-above) with application of the Tanner graph and a “belief propagation” algorithm is performed for each of the groups in order to compute a value of a likelihood logarithm Li associated with a group i among the set of groups of packets (or triplets). 
         [0137]    This first LDPC decoding is then performed on the basis of each triplet of packets and from the matrix HH introduced here above. 
         [0138]    A step  505  is then used for the adding up of the likelihood logarithm values by means of the addition block  404  in  FIG. 4 . We then obtain a sum vector Lr of the likelihood logarithms. 
         [0139]    Then, in a step  506 , a second LDPC decoding is performed using the sum vector Lr of the likelihood logarithms. This second decoding is done by the second decoder  405  of  FIG. 4 . This decoder, like the first decoders of the step  504 , uses the parity matrix HH to perform the second decoding. 
         [0140]      FIG. 6  is a schematic illustration of the graphic progress of the bit error rate or BER as a function of the signal-to-noise ratio (or SNR) for:
       decoding without relay nodes (represented by squares on a curve  3 );   a classic decoding with two relay nodes (represented by circles on a curve  2 );   a decoding with two relay nodes (represented by stars on a curve  1 ), according to a particular embodiment of the present invention.       
 
         [0144]    The curve of  FIG. 6  clearly shows that, for a decoding with two relay nodes, the bit error rate obtained according to the method of the present invention ( FIG. 5 , curve  1 ) is smaller than that obtained with the classic method (curve  2 ), and that this is so for the same values of the signal-to-noise ratio. 
         [0145]    The classic LDPC decoding, in a meshed network, of two source packets and two combined packets coming from two relay nodes corresponds to an LDPC decoding performed with the following matrix (i.e. without a first decoding with an estimation of the logarithmic values of each group of data packets, these values being then used for a second LDPC decoding). 
         [0000]    
       
         
           
             HHH 
             = 
             
               ( 
               
                 
                   
                     H 
                   
                   
                     
                       zeros 
                        
                       
                           
                       
                        
                       
                         ( 
                         
                           K 
                           , 
                           N 
                         
                         ) 
                       
                     
                   
                   
                     
                       zeros 
                        
                       
                           
                       
                        
                       
                         ( 
                         
                           K 
                           , 
                           N 
                         
                         ) 
                       
                     
                   
                   
                     
                       zeros 
                        
                       
                           
                       
                        
                       
                         ( 
                         
                           K 
                           , 
                           N 
                         
                         ) 
                       
                     
                   
                 
                 
                   
                     
                       zeros 
                        
                       
                           
                       
                        
                       
                         ( 
                         
                           K 
                           , 
                           N 
                         
                         ) 
                       
                     
                   
                   
                     H 
                   
                   
                     
                       zeros 
                        
                       
                           
                       
                        
                       
                         ( 
                         
                           K 
                           , 
                           N 
                         
                         ) 
                       
                     
                   
                   
                     
                       zeros 
                        
                       
                           
                       
                        
                       
                         ( 
                         
                           K 
                           , 
                           N 
                         
                         ) 
                       
                     
                   
                 
                 
                   
                     
                       I 
                        
                       
                         ( 
                         
                           N 
                           , 
                           N 
                         
                         ) 
                       
                     
                   
                   
                     
                       I 
                        
                       
                         ( 
                         
                           N 
                           , 
                           N 
                         
                         ) 
                       
                     
                   
                   
                     
                       I 
                        
                       
                         ( 
                         
                           N 
                           , 
                           N 
                         
                         ) 
                       
                     
                   
                   
                     
                       zeros 
                        
                       
                           
                       
                        
                       
                         ( 
                         
                           N 
                           , 
                           N 
                         
                         ) 
                       
                     
                   
                 
                 
                   
                     
                       I 
                        
                       
                         ( 
                         
                           N 
                           , 
                           N 
                         
                         ) 
                       
                     
                   
                   
                     
                       I 
                        
                       
                         ( 
                         
                           N 
                           , 
                           N 
                         
                         ) 
                       
                     
                   
                   
                     
                       zeros 
                        
                       
                           
                       
                        
                       
                         ( 
                         
                           N 
                           , 
                           N 
                         
                         ) 
                       
                     
                   
                   
                     
                       I 
                        
                       
                         ( 
                         
                           N 
                           , 
                           N 
                         
                         ) 
                       
                     
                   
                 
               
               ) 
             
           
         
       
     
         [0146]    In this classic decoding, the LDPC decoding is therefore done with the matrix HHH and an input vector [Y 1 ; Y 2 ; YR 1 ; YR 2 ] (in the example of  FIG. 3  with reception of two combined packets YR 1  and YR 2 ). 
         [0147]    In this example, a correlation (or likelihood) appears between the last two rows of the matrix HHH corresponding to the rows for the decoding of the two packets coming from the two relay nodes. 
         [0148]    In this example of a matrix, for a given configuration of a communications network, this correlation between rows is presented solely when each of the relay nodes does a same linear combination of the source data packets. As discussed here above, a decoding (for example an LDPC decoding) that is done with such a matrix presents a bit error rate that is greater than that of an ideal decoding matrix HHH for which the rows and columns would not be correlated with one another. 
         [0149]    This correlation of rows and columns of the decoding matrix is especially sensitive for an LDPC type decoding requiring a hollow matrix, i.e. a matrix with low correlation between the rows and columns. 
         [0150]    Again, this value of the bit error rate is appreciably lower if it is compared with the value obtained for an LDPC decoding without relay nodes (curve  3 ) performed with the matrix H and a packet b 1 . 
         [0151]    It must be noted that the simulation has been done with a BPSK (Binary Phase Shift Keying) modulation. 
         [0152]      FIG. 7  is a schematic illustration of a communications device  700  adapted to implementing the method of  FIG. 5  according to a particular embodiment. 
         [0153]    This communication device  700  comprises:
       a block  713  used to execute the method  500  ( FIG. 5 ). This block  713  contains the blocks  714 ,  715 ,  716  and  717  corresponding repectively to a block for selecting groups of data packets, a block implementing the first LDPC decoding for each group of packets (or triplets), a likelihood algorithm addition block and a block implementing the second LDPC decoding;   a “CPU IF” block  711  corresponding to the interface between the CPU and the baseband part;   a block  712  corresponding to the data memory;   a block  718  corresponding to a data packet reception circuit;   a block  719  corresponding to a data packet reception circuit;   a block  730  corresponding to a random-access memory (RAM);   a block  740  corresponding to a read-only memory (ROM);   a block  750  corresponding to a radiofrequency transmitter;   a block  760  corresponding to a central processing unit (CPU).       
 
         [0163]    It will be noted that the disclosure is not limited to a purely software implantation in the form of a sequence of instructions of a computer program but that it can also be implemented in hardware form or any other form combining a hardware part and a software part. Should one embodiment of the invention be implanted partially or totally in software form, the corresponding sequence of instructions could be stored in a detachable storage means (such as for example a floppy, a CD-ROM or a DVD-ROM) or in a non-detachable storage means, this storage means being readable by a computer or a microprocessor. 
         [0164]    Thus, one embodiment of the invention can be implemented equally well as a program executed: 
         [0165]    on a reprogrammable computation machine such as a personal computer (or PC), a digital signal processor (or DSP) or a microcontroller; 
         [0166]    or else again on a dedicated computation machine such as a set of logic gates, for example a field programmable gate array (FPGA) or applications specific integrated circuit (ASIC).