Abstract:
One controls the number of iterations of a process of iterative decoding of a symbol sequence coded according to a coding scheme using concatenation of convolutional codes in cases of non-convergence. One firstly calculates a quantity related to the convergence of the iterative decoding process, then one compares this quantity with a non-convergence threshold. As a function of this comparison, the iterative decoding process is halted while declaring the sequence undecoded.

Description:
BACKGROUND OF THE INVENTION  
         [0001]    The present invention relates to techniques for the iterative decoding of digital data coded according to error correction code concatenation schemes. It applies in particular to iterative decoding methods (“turbo decoding”) for parallel concatenated codes.  
           [0002]    The present invention finds application in particular in digital data transmission systems or in digital storage systems.  
           [0003]    The studies initiated by Elias (see P. Elias, “Error-free coding”, IRE Trans. On Information Theory, pp. 29-37, 1954) and developed by Formey (see G. D. Formey, “Concatenated codes”, Cambridge, Mass.: MIT res. Monograph no. 37, MIT Press, 1966) conducted with regard to the concatenation of codes, have encouraged the development of iterative decoding procedures that have proved to be particularly well suited to concatenated codes formed by the serial or parallel concatenation of several constituent codes. During the last decade, a family of concatenated codes, consisting of parallel concatenated convolutional codes (PCCC) with interleaving between the codes, commonly referred to as “turbo codes”, has aroused particular interest in the research world and in industry.  
           [0004]    In a conventional configuration, a turbo coder consists of a plurality of convolutional coders, typically of recursive systematic convolutional coders (RSC) concatenated in parallel, which may or may not be identical. The binary input data of each constituent coder beyond the first coder are a permuted version of the input data of the first constituent coder, thus outputting redundant parity binary sequences. In addition to the parity binary sequences, the data output by the encoder are identical to the binary input data when systematic constituent coders are used.  
           [0005]    In the notation used hereinbelow, n designates the index of the iterations of the iterative decoding process (1≦n≦N_ITE_MAX), k designates the index of the order numbers of the bits of the binary symbol sequences, I designates data output by a permutation operator. This permutation operation is in practice carried out by interleaver modules, to which there correspond deinterleaver modules that carry out the operation inverse to the permutation performed by the interleavers.  
           [0006]    [0006]FIG. 1 depicts a diagram illustrating a conventional turbo-encoder comprising two RSC constituent coders  10 ,  11  operating in parallel and an interleaver  12  arranged upstream of the input of the second coder. The sequence of binary random variables representing the information to be coded is denoted {right arrow over (u)}=(u 1 ,u 2 , . . . ,u N ). This sequence {right arrow over (u)} input to the turbo-coder is applied to the first coder  10  which reproduces them identically at the output, thus constituting a sequence of systematic bits {right arrow over (x)} s =(x s   1 ,x s   2 , . . . , x s   N ) at the output of the encoder. A permuted version {right arrow over (x)} s   1  of the data input to the encoder is applied to the input of the second coder  11  by way of the interleaver  12 . The nonsystematic outputs of the coders  10 ,  11  form the group {right arrow over (x)} p   1 , {right arrow over (x)} p   2  of sequences of parity bits output by the encoder.  
           [0007]    The use of turbo codes is currently envisaged in third-generation cellular networks owing to its superior performance to that of other concatenated codes. For the systems of UMTS (“Universal Mobile Telecommunications System”) type the use of turbo codes for the channel coding of transport channels is described in technical specification  3 G TS 25.212, “Multiplexing and channel coding (FDD)—Release 1999”, version 3.9.0, published in December 2001 by the 3GPP.  
           [0008]    Various procedures for decoding concatenated codes have been developed. The principle of iterative decoding, particularly well suited to these codes, has in particular been described by S. Gallager for the decoding of LDPC codes (see “Low-Density Parity-Check Codes”, R. Gallager, IRE Trans. On Information Theory, January 1962, and “Low-Density Parity Check Codes”, R. Gallager, M.I.T. Press, Cambridge, Mass.; 1963). The decoder comprising a constituent decoder for each constituent coder of the encoder, the estimate obtained at the output of one constituent decoder is used as input information for another constituent decoder.  
           [0009]    The growing success of turbo codes stems from the iterative decoding scheme developed for them. It has subsequently been extended to other concatenated codes, such as serially concatenated convolutional codes (see S. Benedetto, G. Montorsi, S. Divsalar, F. Pollara, “Serial concatenation of interleaved codes: Performance analysis, design and iterative decoding”, TDA Progress report 42-126, JPL, April-June 1996).  
           [0010]    [0010]FIG. 2 depicts a diagram illustrating a conventional iterative turbo-decoder suitable for the encoder of FIG. 1.  
           [0011]    The decoder receives as sequence of binary symbols {right arrow over (y)} comprising three groups of symbols {right arrow over (y)} s , {right arrow over (y)} p   1 , {right arrow over (y)} p   2  corresponding respectively to the sequences {right arrow over (x)} s , {right arrow over (x)} p   1 , {right arrow over (x)} p   2  of symbols produced by the encoder. The symbol sequence {right arrow over (y)} s  corresponding to the systematic bit sequence {right arrow over (x)} s  is fed to the first constituent decoder  20 , while a version {right arrow over (y)} s   1  interleaved by an interleaver  22  is fed to the second constituent decoder  21 . The sequences {right arrow over (y)} p   1 ,{right arrow over (y)} p   2  corresponding to the parity bits are fed to the first and second constituent decoders, respectively. Each constituent decoder  20 ,  21  is a with soft input-soft output (SISO) decoder, and produces a sequence of so-called “soft” estimates (decoded symbol estimate sequence, together with reliability measurement information) as well as information derived from these estimates in the form of a pair of sequences {overscore (L)} 1 , {right arrow over (Le)} 1  and {right arrow over (L)} 2,I , {overscore (Le)} 2,I  respectively. The decoding algorithm implemented in the decoders  20 ,  21  may be of MAP (“Maximum A Posteriori”) type or derived type (“max-log-MAP” or “log-MAP” algorithms), or else of Viterbi type with soft outputs (SOVA—“Soft Output Viterbi Algorithm”). A version {right arrow over (Le)} 1,I  interleaved by an interleaver  23  of the sequence {right arrow over (Le)} 1  produced by the first decoder  20  is fed to the input of the second decoder  21 . A version {right arrow over (Le)} 2  deinterleaved by deinterleaver  24  of the sequence {right arrow over (Le)} 2,I  produced by the second decoder  21  is fed to the input of the first constituent decoder  20 .  
           [0012]    The quantities ({right arrow over (L)} j     —     dec ) j   dec=1,2  commonly referred to as LLRs (“Log-Likelihood Ratios”), represent the ratio of the a posteriori probabilities of the element u k  of the decoded sequence {right arrow over (u)} taking one or the other of the possible binary values. They are obtained by the decoders  20 , 21  according to relation (1)  
                 L   j_dec          (     u   k     )       =           log   e          [       Prob        (       u   k     =     1        y   -&gt;         )         Prob        (       u   k     =     0        y   -&gt;         )         ]          k     =     1                 …                 N               (   1   )                               
 
           [0013]    The quantity L j   dec (u k ) represents a weighted estimate because its sign indicates an estimate corresponding to the best decision û k  relating to the symbol sent u k , while its modulus measures the reliability of this decision.  
           [0014]    The sequences ({overscore (Le)} j   dec ) j   dec=1,2  represent a so-called extrinsic information quantity, corresponding to the iterative part transmitted from one decoder to the next. They are exchanged between the decoders  20 ,  21 , so as to be used in each iteration of the decoding process. At iteration n, the quantities ({overscore (Le)} j   dec ) j   dec=1,2  are determined according to relations (2) and (3):  
             Le   n   1 ( û   n   k )=− Le   n−1   2 ( û   n   k )− L   c   ·y   k   +L   n   1 ( û   n   k ) K=1 . . . N  (2)  
             Le   n   2,I ( û   n   k )=− Le   n−1   1,I ( û   n   k )− L   c   ·y   k   +L   n   2,I ( û   n   k ) K=1 . . . N  (3)  
           [0015]    In equations (2) and (3), the factor L c  represents the contribution of an encoded data transmission channel on the received data y k .  
           [0016]    In practice, it is usual to fix a maximum number of iterations N_ITE_MAX beyond which the iterative decoding process is halted. The value of N_ITE_MAX will depend on the application. It is of the order of 8 in radiocommunication applications for third-generation systems. A control module  23  for the iterative decoding process actuates the constituent decoders  20 ,  21  so as to produce the results of the decoding and directs the running of the process during the maximum number of iterations envisaged or according to an algorithm for controlling the number of iterations.  
           [0017]    A detailed description of iterative decoding algorithms is provided in the article by Hagenauer et al. “Iterative Decoding of Binary Block and Convolutional Codes” (IEEE Transactions on Information Theory, vol. 42, No. 2, March 1996).  
           [0018]    Several studies have been conducted with the aim of reducing the number of iterations of the turbo-decoding process that are performed in situations of early convergence. Criteria for stopping the decoding iterations have thus been defined, enabling the iterative decoding process to be halted prematurely when it is considered that the iterations already performed have lead to sufficiently satisfactory estimates. Refer on this subject to the following articles:  
           [0019]    “Two Simple Stopping Criteria for Iterative Decoding”, Shao et al., IEEE Transactions on Communications, Volume: 47 Issue: 8 Aug. 1999;  
           [0020]    “Reducing average number of turbo decoding iterations”, Shibutani et al., IEE Electronics letters, April 1999, vol. 35, No. 9;  
           [0021]    “Increasing throughput of iterative decoders”, Vogt et al., IEE Electronics letters, June 2001, vol. 37, No. 12.  
           [0022]    Within the context of implementation of iterative decoding schemes in the field of radiocommunications, and especially when envisaging their use in a radiocommunication terminal, the complexity of such schemes is a parameter that ought to be optimized. The use of calculation resources (signal processor, coprocessor, etc.) is in this regard an energy consuming factor, whose reduction helps to increase the autonomy of a terminal.  
           [0023]    An object of the present invention is to optimize the iterative decoding methods.  
         SUMMARY OF THE INVENTION  
         [0024]    The invention thus proposes a method of controlling the number of iterations of a process of iterative decoding of a symbol sequence coded according to a coding scheme using concatenation of convolutional codes, wherein, for an iteration beyond the first, a quantity related to the convergence of the iterative decoding process is calculated, this quantity is compared with a non-convergence threshold, and the iterative decoding process is stopped as a function of this comparison while declaring the sequence undecoded.  
           [0025]    The invention relies on the observation, with a view to taking early action, of the situations of non-convergence of an iterative decoding algorithm. Non-convergence cases are encountered when a sequence to be decoded has been altered by the transmission of the data to such an extent that it would not be usable, even if the maximum number of iterations of the decoding process were to be carried out.  
           [0026]    Another aspect of the present invention proposes a device for controlling the number of iterations of an iterative decoding process, comprising means for calculating a quantity related to the convergence of the iterative decoding process, means for comparing this quantity with a no-convergence threshold, and means for stopping the iterative decoding process as a function of this comparison while declaring the sequence undecoded.  
           [0027]    Preferably, the means for calculating a quantity related to the convergence of the iterative decoding process will comprise the means for measuring the discrepancy between two estimates of the symbol sequence that are obtained during distinct iterations of the decoding process, these means typically being devised to measure said discrepancy according to a Hamming distance.  
           [0028]    The invention is also concerned with a computer program, loadable into a memory associated with a processor, and comprising code portions for implementing a method as defined above during the execution of said program by the processor, as well as to a computer-readable medium on which such a program is recorded.  
           [0029]    The invention may be advantageously implemented together with criteria for stopping the decoding based on anticipated convergence, such as those described in the articles mentioned above. 
       
    
    
     BRIEF DESCRIPTION THE DRAWINGS  
       [0030]    [0030]FIG. 1 is a diagram of a conventional turbo encoder.  
         [0031]    [0031]FIG. 2 is a diagram of a conventional turbo decoder to which the invention may be applied.  
         [0032]    [0032]FIG. 3 is a flow chart illustrating the method according to the invention in a first embodiment.  
         [0033]    [0033]FIG. 4 is a flow chart illustrating the method according to the invention in a second embodiment.  
         [0034]    [0034]FIG. 5 is a diagram illustrating a device according to the invention. 
     
    
     DESCRIPTION OF PREFERRED EMBODIMENTS  
       [0035]    The invention is described below in its non-limiting application to a turbo decoder.  
         [0036]    According to the invention, one calculates an estimate of each symbol of the sequence to be decoded during an iteration n of the decoding process, with n≧1. In a preferred embodiment of the invention, this so-called “hard” estimate is obtained by determining the sign of the LLR quantities L n   2  obtained after the interleaving on the basis of the output L n   2,I  of the second constituent decoder submitted to the deinterleaver  25 .  
         [0037]    In another step according to the invention, a quantity related to the convergence of the iterative decoding process is calculated. Preferably, this quantity measures the discrepancy between two estimates of the symbol sequence that are obtained during distinct iterations of the decoding process. Advantageously, this discrepancy is calculated in the sense of the Hamming distance (number of binary positions which differ between the two sequences).  
         [0038]    The algorithms depicted in FIGS. 3 and 4 will typically be implemented within the control module  23  described above. This module will therefore be able to drive the succession of iterations of the decoding process having regard to the maximum number envisaged by using a divergence-based stopping criterion according to the invention and possibly a convergence-based stopping criterion.  
         [0039]    The algorithm represented in FIG. 3 is initialized with n=1. A loop is executed for the successive values of the index n. Each iteration n in this loop starts with the obtaining  31  of the sequence of estimates û n   1 ,û n   2 , . . . ,û n   N  from the quantities L 2 (u k ) whose sign is determined. Step  31  is thus executed in a manner co-ordinated with the iterative decoding process whose execution provides the quantities L 2 (u k ). The sequences of estimates thus obtained are then stored. A test  32  is performed to distinguish the processing carried out during the first few iterations, limited to the obtaining of the sequence and its storage in the previous step. The number of loop iterations for which this limited processing is carried out is determined by the parameter N obs , chosen to be greater than or equal to 1. A setting of N obs  beyond 1 enables the decoding stop criterion to be applied only after a determined number of decoding iterations, thus offering a further degree of flexibility of the method according to the invention. If the iteration in progress is beyond the predetermined number N obs , one obtains ( 33 ) the Hamming distance D n  between the sequence of estimates û n   1 ,û n   2 , . . . ,û n   N  obtained in the previous step  31  and the sequence of estimates û n−1   1 ,û n−1   2 , . . . ,û n−1   N  obtained in step  31  during the previous iteration. Alternatively, it is possible to calculate the discrepancy between the current sequence of estimates û n   1 ,û n   2 , . . . ,û n   N  and the sequence of estimates û n-p   1 ,û n-p   2 , . . . ,û n-p   N  obtained in step  31  during any previous iteration n-p. The quantity D n  obtained in step  33  can then be normalized in step  34  by the size N of the decoded sequence so as to obtain the criterion Γ n   err  which will be compared with the divergence threshold θ div  in the next step  35 . The normalization operation makes it possible to establish a criterion independent of the number N of binary symbols in a sequence. It is also possible to establish a mean of the distances D n  calculated at each iteration n, and to obtain the criterion Γ n   err  without departing from the spirit of the invention. If the value of the criterion Γ n   err  exceeds the threshold value θ div , the iterative decoding is halted  37  and the sequence declared undecoded ( 41 ).  
         [0040]    The output of tests  32  and  35  when the test condition is not fulfilled leads to the incrementation  36  of the decoding iteration index n, before returning to step  31  for the next iteration.  
         [0041]    The criterion Γ n   err  is related to the convergence of the iterative decoding process. When the iterative decoding algorithm converges, its monotonic variations provide an indication of speed of convergence, the algorithm converging to a unique sequence, this being manifested as a reduction toward zero of the value of Γ n   err . The “turbo” effect is observed in cases of convergence after a few iterations of the decoding loop, and the fast convergence of the decoding algorithm is manifested as the fast reducing of the value of Γ n   err . The situations of divergence may thus be detected quickly by comparing Γ n   err  with the threshold θ div . In practice, the choice of θ div  may result from a compromise between the risk of loss of performance and the quantity of calculation resources that is saved.  
         [0042]    In a second embodiment of the invention, a test of non-convergence, based on observation of the variations of Γ n   err  is applied. The non-convergence threshold is estimated on the basis of a measure of the discrepancy between two estimates of the symbol sequence that are obtained during distinct iterations of the decoding process, one at least of which differs from the iterations for which the quantity related to the convergence of the iterative decoding process is calculated. The procedure, illustrated in FIG. 4, is similar to that described above for steps  30  to  34 ,  36  and  37 .  
         [0043]    The algorithm represented in FIG. 4 is initialized with n=1. A loop is executed for the successive values of the index n. Each iteration n in this loop starts with the obtaining  31  of the sequence of estimates û n   1 ,û n   2 , . . . ,û n   N  from the quantities L 2 (u k ). Step  31  is as before executed in a manner coordinated with the iterative decoding process whose execution provides the quantities L 2 (u k ). The sequences of estimates thus obtained are then stored. A test  38  is performed to distinguish the processing carried out during the first iteration, this being limited to the obtaining of the sequence and its storage in the previous step. If the iteration in progress is beyond the first iteration, one obtains  33  the Hamming distance D n  between the sequence of estimates û n   1 ,û n   2 , . . . ,û n   N  obtained in the previous step  31  and the sequence of estimates û n−1   1 ,û n−1   2 , . . . ,û n−1   N  obtained in step  31  during the previous iteration. Alternatively, it is possible to calculate the distance between the current sequence of estimates û n   1 ,û n   2 , . . . ,û n   N  and the sequence of estimates û n-p   1 ,û n-p   2 , . . . ,û n-p   N  obtained in step  31  during any previous iteration n-p. The quantity D n  obtained in step  33  can then be normalized in step  34  by the size N of the decoded sequence so as to obtain the criterion Γ n   err . A test ( 39 ) is then performed to distinguish the processing carried out during the first N′ obs  iterations beyond the first, in the course of which the stopping test  40  is not performed. The number of loop iterations for which this limited processing is carried out is determined by the parameter N′ bs , chosen to be greater than or equal to 2. A setting of N′ obs  beyond 2 enables the decoding stop criterion to be applied only after a determined number of decoding iterations, thus offering a further degree of flexibility in the method according to the invention. When the condition of test  39  is fulfilled, the discrepancy between the criteria Γ n   err  and Γ n−1   err , is calculated. Alternatively, it is possible to calculate the discrepancy between the criterion obtained for the iteration in progress and the criterion obtained in step  34  during any previous iteration n-p. The discrepancy Γ n   err −Γ n−1   err  calculated previously is compared with a threshold θ′ div  in step  40 . If the discrepancy is short of this threshold, a situation of non-convergence is detected, the stopping of the iterative decoding process decided ( 37 ) and the sequence declared undecoded ( 41 ). This amounts to comparing the quantity related to convergence Γ n   err  with a measure of the discrepancy Γ n−1   err  corrected by the value θ′ div .  
         [0044]    It is also possible to establish a mean of the distances Γ n   err −Γ n−1   err  calculated at each iteration n, and to obtain a non-convergence criterion, without departing from the spirit of the invention.  
         [0045]    The output of tests  38 ,  39  and  40  when the test condition is not fulfilled leads to the incrementation  36  of the decoding iteration index n before returning to step  31  for the next iteration.  
         [0046]    The non-convergence threshold according to the invention may be rendered adaptive, for example as a function of service (transmission of voice, data according to a specified or unspecified service quality) in radio communication applications, without departing from the scope of the invention.  
         [0047]    The device represented in FIG. 5 comprises a control module  50  which drives the implementation of the method according to the invention and actuates in succession a module  51  for calculating a quantity related to the convergence of the iterative decoding process and a module  52  for comparing this quantity with a non-convergence threshold. According to the first and second embodiments described above, the module  51  receives the quantities L 2 (u k ) output from the second constituent decoder  21 . The modules  50 - 52  are integrated with the module  23  for controlling the iterative decoding process described above. When a situation of nonconvergence is detected, and the stopping of the iterative decoding process decided, the module  50  transmits an information item for stopping the decoding while declaring the sequence undecoded to a module  53  for controlling the decoding iterations, likewise integrated with the module  23 .  
         [0048]    In accordance with the first embodiment described above, the means  52  will be devised to compare the quantity related to convergence with a non-convergence threshold obtained on the basis of a predetermined value, and the means  50  will be devised to stop the iterative decoding process as soon as the quantity related to the convergence of the iterative decoding process is greater than this value.  
         [0049]    In accordance with the second embodiment described above, the means  52  will be devised to compare the magnitude related to convergence with a non-convergence threshold estimated on the basis of a measurement of the discrepancy between two estimates of the symbol sequence that are obtained during distinct iterations of the decoding process one at least of which differs from the iterations for which the quantity related to the convergence of the iterative decoding process is calculated. Preferably, they will be devised to compare the quantity related to convergence with a non-convergence threshold obtained on the basis of said discrepancy measurement corrected by a predetermined value.