Abstract:
A method of decoding a received data word (r) having been transmitted over a radio communication channel, the corresponding sent data word (m) having been encoded as a code word (c), the method includes: 
     multiplying of the received data word by a parity-check matrix, 
     and if the result of the multiplication is zero: performing an algebraic decoding of the received data word without error correction, otherwise performing an error correction by estimating the transmission error, subtracting the estimated error from the received data word, and performing an algebraic decoding of the result of the subtraction, wherein for estimation of the transmission error is used to identify an approximate location of potential errors and the Viterbi algorithm is only applied for these locations, thus avoiding iterations in error-free areas.

Description:
The invention is based on a priority application EP 03292150.4 which is hereby incorporated by reference. 
   FIELD OF THE INVENTION 
   The present invention relates to the field of decoding, and more particularly without limitation, to Viterbi decoding and forward error correction. 
   BACKGROUND OF THE INVENTION 
   A commonly used method to decode convolutional codes is the Viterbi algorithm. The Viterbi algorithm essentially performs maximum likelihood decoding; it reduces the computational load by taking advantage of the special structure in the code trellis. The advantage of Viterbi decoding, compared with brute-force decoding, is that the complexity of a Viterbi decoder is not a function of the number of symbols in the code word sequence. 
   The algorithm involves calculating a measure of similarity, or distance, between the received signal at a certain time and all the trellis paths entering each state at that time. The Viterbi algorithm removes from consideration those trellis paths that could not possibly be candidates for the maximum likelihood choice. When two paths enter the same state, the one having the best metric is chosen; this path is called the surviving path. The early rejection of the unlikely path reduces the decoding complexity. Still the Viterbi algorithm is quite computationally expensive. 
   Further, the Viterbi convolutional decoding algorithm is used for forward error correction. The purpose of forward error correction (FEC) is to improve the capacity of a channel by adding some redundant information to the data being transmitted through the channel. The process of adding this redundant information is known as channel coding. Convolutional coding is a major form of channel coding. Convolutional codes operate on serial data, one or a few bits at a time. Convolutional encoding with Viterbi decoding is a FEC technique that is particularly suited to a radio communication channel. 
   The present invention aims to provide an improved method of decoding of a received data word. 
   SUMMARY OF THE INVENTION 
   These and other objects of the present invention are solved basically by applying the features laid down in the respective independent claims. Preferred embodiments of the invention are given in the dependant claims. 
   The present invention is first based on the fact that error corrective decoding is not always required when a data word is received. In order to determine whether error corrective decoding is or is not required, it is checked whether a received data word is error free (or has undetectable errors) or if the information message has no chance to be recovered, i.e. there are too many errors in the received data words. 
   If the received data word has no errors or undetectable errors decoding is performed without prior error correction. If the information message is not recoverable, the frame is rejected before decoding. 
   Yet, in most cases, the frames will have to be decoded. In these cases, the complexity reduction is achieved by performing the FEC in a much more efficient way than the classical decoding: the Viterbi algorithm is used to estimate the transmission errors rather than the information message. With this type of decoding, a vast majority of state to state iterations can be avoided in the error-free zones. 
   This approach has the advantage that computationally expensive error correction procedures can be prevented in case a determination is made for the received data word that it has no error, undetectable errors or too many errors. 
   This approach also has the advantage that when the FEC is required, some significant complexity reduction is achieved by avoiding a vast majority of state to state iterations during the Viterbi decoding 
   One way of determining whether error correction is required or not is based on the parity-check matrix. The parity-check matrix is also referred to as check-matrix or control matrix in coding theory. A parity-check matrix H for a code C having a generator matrix G satisfies GH t =0 as it is as such known in the prior art. 
   In accordance with a preferred embodiment of the invention the parity-check matrix is calculated once for a given encoding scheme and stored in the receiver. When a data word is received it is multiplied by the pre-calculated parity-check matrix in order to determine whether error correction is required or not. 
   In accordance with a further preferred embodiment of the invention the result of the multiplication of the received data word by the parity-check matrix is used in order to determine whether error correction is required or not.
         If the number of non-null coefficients of the result of the multiplication of the received data word by the parity-check matrix is equal to zero, the received data word is error-free (or the error is not detectable) and the error correction is not required.   If the number of non-null coefficients of the result of the multiplication of the received data word by the parity-check matrix is above a certain threshold level, no error correction and no decoding is performed as the received data word is considered uncorrectable. This has the advantage that useless processing of the uncorrectable data word is avoided.       

   Otherwise, if the FEC has to be performed, the classical Viterbi algorithm can be used to estimate the original information message. 
   Yet, if the FEC has to be performed, the Viterbi algorithm can be used to estimate the transmission errors rather than the information message. The result of the multiplication of the received data word by the parity-check matrix gives an approximate location of potential errors and the Viterbi algorithm is only applied in these identified zones, thus avoiding many iterations in the error-free area. 
   Finally the estimated transmission errors are subtracted to the received data word and an algebraic decoding is performed to evaluate the sent information message. 
   The determination whether error correction is required or not and the fast error correction procedure are based on the parity-check matrix works for arbitrary convolutional code rates, such as convolutional code rates of ½, ⅓, 2/3 (see further examples below). Yet, in the case of a convolutional code of rate ½, some simple polynomial manipulations can also lead to the result of the multiplication of the received data word by the parity-check matrix. Indeed, it can be shown that, in case of a convolutional code rate of 1/2 the result of the received data word multiplied by the parity check matrix can be also obtained by using the simple polynomial manipulations described in annex 3. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
     In the following preferred embodiments of the invention will be described in greater detail by making reference to the drawings in which: 
       FIG. 1  is a block diagram of a telecommunication system, 
       FIG. 2  is illustrative of a flow chart showing an embodiment of a method of the invention. 
   

   DETAILED DESCRIPTION OF THE INVENTION 
     FIG. 1  shows a telecommunication system having a sender  1  for sending of information messages m 1 , m 2 , . . . , m k  to a receiver  2  over channel  3 . Sender  1  has encoder  4  for encoding of the information messages by means of a generator polynomials matrix G={g ij } to provide encoded words c 1 , c 2 , . . . , c n . It is to be noted that the number of information messages k and the number n of encoded words can be arbitrary, i.e. the system works for various convolutional code rates k/n. 
   The encoded words c 1 , c 2 , . . . , c n , are transmitted over noisy channel  3 . The transmission over noisy channel  3  results in the addition of errors e 1 , e 2 , . . . , e n . As a consequence receiver  2  receives messages r 1 , r 2 , . . . , r n , where 
   
     
       
         
           
             
               
                 
                   r 
                   1 
                 
                 = 
                 
                   
                     c 
                     1 
                   
                   + 
                   
                     e 
                     1 
                   
                 
               
             
           
           
             
               
                 
                   r 
                   2 
                 
                 = 
                 
                   
                     c 
                     2 
                   
                   + 
                   
                     e 
                     2 
                   
                 
               
             
           
           
             
               ⋯ 
             
           
           
             
               
                 
                   r 
                   n 
                 
                 = 
                 
                   
                     c 
                     n 
                   
                   + 
                   
                     e 
                     n 
                   
                 
               
             
           
           
             
               with 
             
           
           
             
               
                 
                   c 
                   1 
                 
                 = 
                 
                   
                     
                       g 
                       11 
                     
                     ⁢ 
                     
                       m 
                       1 
                     
                   
                   + 
                   
                     
                       g 
                       12 
                     
                     ⁢ 
                     
                       m 
                       2 
                     
                   
                   + 
                   … 
                   + 
                   
                     
                       g 
                       
                         1 
                         ⁢ 
                         k 
                       
                     
                     ⁢ 
                     
                       m 
                       k 
                     
                   
                 
               
             
           
           
             
               
                 
                   c 
                   2 
                 
                 = 
                 
                   
                     
                       g 
                       21 
                     
                     ⁢ 
                     
                       m 
                       1 
                     
                   
                   + 
                   
                     
                       g 
                       22 
                     
                     ⁢ 
                     
                       m 
                       2 
                     
                   
                   + 
                   … 
                   + 
                   
                     
                       g 
                       
                         2 
                         ⁢ 
                         k 
                       
                     
                     ⁢ 
                     
                       m 
                       k 
                     
                   
                 
               
             
           
           
             
               ⋯ 
             
           
           
             
               
                 
                   c 
                   n 
                 
                 = 
                 
                   
                     
                       g 
                       
                         n 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         1 
                       
                     
                     ⁢ 
                     
                       m 
                       1 
                     
                   
                   + 
                   
                     
                       g 
                       
                         n 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         2 
                       
                     
                     ⁢ 
                     
                       m 
                       2 
                     
                   
                   + 
                   … 
                   + 
                   
                     
                       g 
                       nk 
                     
                     ⁢ 
                     
                       m 
                       k 
                     
                   
                 
               
             
           
         
       
     
   
   Decoder  5  of receiver  2  has an error correction capability in order to eliminate the error vector {e 1 , e 2 , . . . , e n } from the received messages to provide the original information messages. 
   It can be mathematically shown that the above system of n equations and k unknown polynomials, i.e. m 1 , m 2 , . . . , m k , can be divided into:
         k required equations to find the k unknown polynomials m 1 , m 2 , . . . , m k  by an algebraic decoding. For instance       

   
     
       
         
           
             
               
                 
                   
                     c 
                     1 
                   
                   = 
                   
                     
                       
                         g 
                         11 
                       
                       ⁢ 
                       
                         m 
                         1 
                       
                     
                     + 
                     
                       
                         g 
                         12 
                       
                       ⁢ 
                       
                         m 
                         2 
                       
                     
                     + 
                     … 
                     + 
                     
                       
                         g 
                         
                           1 
                           ⁢ 
                           k 
                         
                       
                       ⁢ 
                       
                         m 
                         k 
                       
                     
                   
                 
               
             
             
               
                 
                   
                     c 
                     2 
                   
                   = 
                   
                     
                       
                         g 
                         21 
                       
                       ⁢ 
                       
                         m 
                         1 
                       
                     
                     + 
                     
                       
                         g 
                         22 
                       
                       ⁢ 
                       
                         m 
                         2 
                       
                     
                     + 
                     … 
                     + 
                     
                       
                         g 
                         
                           2 
                           ⁢ 
                           k 
                         
                       
                       ⁢ 
                       
                         m 
                         k 
                       
                     
                   
                 
               
             
             
               
                 ⋯ 
               
             
             
               
                 
                   
                     c 
                     k 
                   
                   = 
                   
                     
                       
                         g 
                         
                           k 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           1 
                         
                       
                       ⁢ 
                       
                         m 
                         1 
                       
                     
                     + 
                     
                       
                         g 
                         
                           k 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           2 
                         
                       
                       ⁢ 
                       
                         m 
                         2 
                       
                     
                     + 
                     … 
                     + 
                     
                       
                         g 
                         kk 
                       
                       ⁢ 
                       
                         m 
                         k 
                       
                     
                   
                 
               
             
           
           → 
           
             
               
                 
                   
                     m 
                     1 
                   
                   = 
                   
                     
                       
                         p 
                         11 
                       
                       ⁢ 
                       
                         c 
                         1 
                       
                     
                     + 
                     
                       
                         p 
                         12 
                       
                       ⁢ 
                       
                         c 
                         2 
                       
                     
                     + 
                     … 
                     + 
                     
                       
                         p 
                         
                           1 
                           ⁢ 
                           k 
                         
                       
                       ⁢ 
                       
                         c 
                         k 
                       
                     
                   
                 
               
             
             
               
                 
                   
                     m 
                     2 
                   
                   = 
                   
                     
                       
                         p 
                         21 
                       
                       ⁢ 
                       
                         c 
                         1 
                       
                     
                     + 
                     
                       
                         p 
                         22 
                       
                       ⁢ 
                       
                         c 
                         2 
                       
                     
                     + 
                     … 
                     + 
                     
                       
                         p 
                         
                           2 
                           ⁢ 
                           k 
                         
                       
                       ⁢ 
                       
                         c 
                         k 
                       
                     
                   
                 
               
             
             
               
                 ⋯ 
               
             
             
               
                 
                   
                     m 
                     k 
                   
                   = 
                   
                     
                       
                         p 
                         
                           k 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           1 
                         
                       
                       ⁢ 
                       
                         c 
                         1 
                       
                     
                     + 
                     
                       
                         p 
                         
                           k 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           2 
                         
                       
                       ⁢ 
                       
                         c 
                         2 
                       
                     
                     + 
                     … 
                     + 
                     
                       
                         p 
                         kk 
                       
                       ⁢ 
                       
                         c 
                         k 
                       
                     
                   
                 
               
             
           
         
       
     
       
       
         
           where the polynomials p ij  are linear combinations of the generator polynomials. 
           n−k “control equations”, independent on m 1 , m 2 , . . . , m k : 
         
       
     
  
   
     
       
         
           
             
               
                 
                   
                     
                       c 
                       1 
                     
                     ⁢ 
                     
                       h 
                       11 
                     
                   
                   + 
                   
                     
                       c 
                       2 
                     
                     ⁢ 
                     
                       h 
                       21 
                     
                   
                   + 
                   … 
                   + 
                   
                     
                       c 
                       n 
                     
                     ⁢ 
                     
                       h 
                       
                         n 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         1 
                       
                     
                   
                 
                 = 
                 0 
               
             
           
           
             
               
                 
                   
                     
                       c 
                       1 
                     
                     ⁢ 
                     
                       h 
                       12 
                     
                   
                   + 
                   
                     
                       c 
                       2 
                     
                     ⁢ 
                     
                       h 
                       22 
                     
                   
                   + 
                   … 
                   + 
                   
                     
                       c 
                       n 
                     
                     ⁢ 
                     
                       h 
                       
                         n 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         2 
                       
                     
                   
                 
                 = 
                 0 
               
             
           
           
             
               ⋯ 
             
           
           
             
               
                 
                   
                     
                       c 
                       1 
                     
                     ⁢ 
                     
                       h 
                       
                         1 
                         , 
                         
                           n 
                           - 
                           k 
                         
                       
                     
                   
                   + 
                   
                     
                       c 
                       2 
                     
                     ⁢ 
                     
                       h 
                       22 
                     
                   
                   + 
                   … 
                   + 
                   
                     
                       c 
                       n 
                     
                     ⁢ 
                     
                       h 
                       
                         n 
                         , 
                         
                           n 
                           - 
                           k 
                         
                       
                     
                   
                 
                 = 
                 0 
               
             
           
         
       
     
       
       
         
           where the polynomials h ij  are linear combinations of the generator polynomials. Examples of polynomials h ij  are provided in annex 1. These n−k control equations can be expressed with one matrix equation. This equation is referred to as “control equation” in the following: 
         
       
     
  
   
     
       
         
           
             
               CH 
               t 
             
             = 
             0 
           
           , 
           
             
               C 
               t 
             
             = 
             
               ( 
               
                 
                   
                     
                       c 
                       1 
                     
                   
                 
                 
                   
                     
                       c 
                       2 
                     
                   
                 
                 
                   
                     · 
                   
                 
                 
                   
                     · 
                   
                 
                 
                   
                     
                       c 
                       n 
                     
                   
                 
               
               ) 
             
           
           , 
           
             
               H 
               t 
             
             = 
             
               ( 
               
                 
                   
                     
                       
                         h 
                         11 
                       
                       ⁢ 
                       
                         h 
                         12 
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       … 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         h 
                         
                           1 
                           , 
                           
                             n 
                             - 
                             k 
                           
                         
                       
                     
                   
                 
                 
                   
                     
                       
                         h 
                         21 
                       
                       ⁢ 
                       
                         h 
                         22 
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       … 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         h 
                         
                           2 
                           , 
                           
                             n 
                             - 
                             k 
                           
                         
                       
                     
                   
                 
                 
                   
                     
                         
                     
                   
                 
                 
                   
                     
                         
                     
                   
                 
                 
                   
                     
                       
                         h 
                         
                           n 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           1 
                         
                       
                       ⁢ 
                       
                         h 
                         
                           n 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           2 
                         
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       … 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         h 
                         
                           n 
                           , 
                           
                             n 
                             - 
                             k 
                           
                         
                       
                     
                   
                 
               
               ) 
             
           
         
       
     
       
       
         
           It can be theoretically show that there is at least one matrix H such as: 
           C is a code word          CH t =0 
           H or H′ is commonly referred to as parity-check matrix. 
         
       
     
  
   For complexity reason (cf annex 2), it is preferable to choose parity check matrix with minimal degree. Let us call q ik  the degree of the polynomial k ik (x); if the generating polynomials verify the following property:
 
{ g   ij ( x ); 1≦ i≦N } have no common factor for all  j.   (1)
 
   Then it can be shown that there exists a set of polynomials {h ik } such as 
               ∑     k   =   1       N   -   K       ⁢           ⁢     q   k       =       M   -     1   ⁢           ⁢   where   ⁢           ⁢     q   k         =       Max     1   ≤   i   ≤   N       ⁡     (     q   ik     )               
and M is the constraint length of the code (maximal length of the generating polynomials). These polynomials are found by searching the polynomials h ik (x) with minimal degree witch verify the system H(x)·G′(x)=0.
 
   It is to be noted that if property (1) is not verified for one column j, it is possible to achieve a code with a minimal memory by dividing this column by the Highest Common Factor of the polynomials {g ij (x); 1≦ i≦N}.    
   The control equation is used to estimate the error vectors. Let E′=(e′ 1 , . . . , e′ n ) t  the total error estimation vector and R=(r 1 , . . . , r n ) t  the total information message vector. 
   The corresponding decoding method is illustrated in  FIG. 2  by way of example: 
   In step  20  a data word is received by the receiver. In step  21  the data word is multiplied by the parity-check matrix. In step  22  it is determined whether all coefficients of the result of the multiplication are equal to zero. If this is the case the control goes to step  23  where the received data word is decoded without error correction. 
   Otherwise the control goes to step  24  where it is determined whether the number of non-zero coefficients of the result of the multiplication is below a predefined threshold level. If this is the case an error correction of the received data word is performed in step  25  in order to eliminate the error vector. Next the error corrected data word is decoded in step  26 . 
   If it is determined in step  24 , that the number of non-zero coefficients of the results of the multiplication is above a predefined threshold level the control goes to step  27  where it is decided that the data word is uncorrectable. 
   This method implements the algorithm as illustrated below:
         1. calculate RH t      2. if the number of non null coefficients of RH t  is superior to a predetermined threshold reject the frame, go to 4.
           else   if RH t  is null:
 
 E ′=0, go to 3.
   else
               use the fast Forward Error Correction algorithm described in annex  2  to find E′ such as:   1. (R+E′)H t =0   2. E′ has the minimal weight (maximum likelihood) go to 3.   
               
           3. algebraic decoding, e.g. solve a linear system to estimate the polynomials m 1 , m 2 , . . . , m k , for example:       

   
     
       
         
           
             
               
                 
                   r 
                   1 
                 
                 = 
                 
                   
                     
                       g 
                       11 
                     
                     ⁢ 
                     
                       m 
                       1 
                     
                   
                   + 
                   
                     
                       g 
                       12 
                     
                     ⁢ 
                     
                       m 
                       2 
                     
                   
                   + 
                   … 
                   + 
                   
                     
                       g 
                       
                         1 
                         ⁢ 
                         k 
                       
                     
                     ⁢ 
                     
                       m 
                       k 
                     
                   
                   + 
                   
                     e 
                     1 
                     ′ 
                   
                 
               
             
           
           
             
               
                 
                   r 
                   2 
                 
                 = 
                 
                   
                     
                       g 
                       21 
                     
                     ⁢ 
                     
                       m 
                       1 
                     
                   
                   + 
                   
                     
                       g 
                       22 
                     
                     ⁢ 
                     
                       m 
                       2 
                     
                   
                   + 
                   … 
                   + 
                   
                     
                       g 
                       
                         2 
                         ⁢ 
                         k 
                       
                     
                     ⁢ 
                     
                       m 
                       k 
                     
                   
                   + 
                   
                     e 
                     2 
                     ′ 
                   
                 
               
             
           
           
             
               ⋯ 
             
           
           
             
               
                 
                   r 
                   k 
                 
                 = 
                 
                   
                     
                       g 
                       
                         k 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         1 
                       
                     
                     ⁢ 
                     
                       m 
                       1 
                     
                   
                   + 
                   
                     
                       g 
                       
                         k 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         2 
                       
                     
                     ⁢ 
                     
                       m 
                       2 
                     
                   
                   + 
                   … 
                   + 
                   
                     
                       g 
                       kk 
                     
                     ⁢ 
                     
                       m 
                       k 
                     
                   
                   + 
                   
                     e 
                     k 
                     ′ 
                   
                 
               
             
           
         
       
     
       
       
         
           4. end 
         
       
     
  
   The complexity reduction is obtained at several steps:
         If the estimated frame error probability (connected to the number of non-null coefficients of RH t ) is superior to a predetermined threshold, the frame has a very low probability to be recovered. It is rejected before the decoding.   If RH t  is null, the raw bit error rate is equal to zero, or the error is undetectable, and the FEC is not performed.   When the frame has to be decoded, RH t  is used to reduce the decoding complexity. The Viterbi Algorithm is applied to estimate the error vector instead of the information message (annex 2). In this case, some iteration, shown to be unnecessary, can be avoided (annex 2).       

   With the proposed algorithm, almost optimal performance is achievable with an order of magnitude in complexity reduction. The following figures show the complexity reduction and the performances degradation for two convolutional codes of rate 1/3 and 2/3 in both the hard decoder input case and the soft decoder input case. The complexity criteria is the percentage of “Add Compare Select (ACS)” operations performed compared to the number of ACS of the classical Viterbi. Performance criteria is the Frame Error Rate (FER) at the decoder output. 
   Convolutional code of rate ⅓: 
   
     
       
         
           
             
               
                   
                 ⁢ 
                 
                   
                     
                       g 
                       11 
                     
                     ⁡ 
                     
                       ( 
                       x 
                       ) 
                     
                   
                   = 
                   
                     1 
                     + 
                     
                       x 
                       2 
                     
                     + 
                     
                       x 
                       3 
                     
                   
                 
               
             
             
               
                   
               
             
           
           
             
               
                   
                 ⁢ 
                 
                   
                     
                       g 
                       21 
                     
                     ⁡ 
                     
                       ( 
                       x 
                       ) 
                     
                   
                   = 
                   
                     1 
                     + 
                     x 
                     + 
                     
                       x 
                       3 
                     
                   
                 
               
             
             
               
                 
                   H 
                   t 
                 
                 = 
                 
                   ( 
                   
                     
                       
                         x 
                       
                       
                         
                           1 
                           + 
                           
                             x 
                             2 
                           
                         
                       
                     
                     
                       
                         1 
                       
                       
                         
                           1 
                           + 
                           
                             x 
                             2 
                           
                         
                       
                     
                     
                       
                         
                           1 
                           + 
                           x 
                         
                       
                       
                         x 
                       
                     
                   
                   ) 
                 
               
             
           
           
             
               
                   
                 ⁢ 
                 
                   
                     
                       g 
                       31 
                     
                     ⁡ 
                     
                       ( 
                       x 
                       ) 
                     
                   
                   = 
                   
                     1 
                     + 
                     x 
                     + 
                     
                       x 
                       2 
                     
                     + 
                     
                       x 
                       3 
                     
                   
                 
               
             
             
               
                   
               
             
           
         
       
     
     
       
         
           G 
           = 
           
             ( 
             
               1 
               + 
               
                 x 
                 2 
               
               + 
               
                 
                   x 
                   3 
                 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 1 
               
               + 
               x 
               + 
               
                 
                   x 
                   3 
                 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 1 
               
               + 
               x 
               + 
               
                 x 
                 2 
               
               + 
               
                 x 
                 3 
               
             
             ) 
           
         
       
     
   
   As shown in  FIGS. 3A , and  3 B, in both the hard and the soft cases, when the SNR is superior to 3.5 db, less than 10% of the ACS are required. Furthermore, the maximal number of required ACS remains inferior to 43% (resp. 65%) in the hard (resp. soft) case. The performances degradation remains inferior to 0.5 db in both cases. 
   Convolution code of rate ⅔: 
   
     
       
         
             
           
             { 
             
               
                 
                   
                     
                       
                         
                           
                             
                               g 
                               11 
                             
                             ⁡ 
                             
                               ( 
                               x 
                               ) 
                             
                           
                           = 
                           
                             1 
                             + 
                             x 
                           
                         
                       
                     
                     
                       
                         
                           
                             
                               g 
                               21 
                             
                             ⁡ 
                             
                               ( 
                               x 
                               ) 
                             
                           
                           = 
                           x 
                         
                       
                     
                     
                       
                         
                           
                             
                               g 
                               31 
                             
                             ⁡ 
                             
                               ( 
                               x 
                               ) 
                             
                           
                           = 
                           
                             1 
                             + 
                             x 
                           
                         
                       
                     
                     
                       
                         
                           
                             
                               g 
                               12 
                             
                             ⁡ 
                             
                               ( 
                               x 
                               ) 
                             
                           
                           = 
                           x 
                         
                       
                     
                     
                       
                         
                           
                             
                               g 
                               22 
                             
                             ⁡ 
                             
                               ( 
                               x 
                               ) 
                             
                           
                           = 
                           1 
                         
                       
                     
                     
                       
                         
                           
                             
                               g 
                               32 
                             
                             ⁡ 
                             
                               ( 
                               x 
                               ) 
                             
                           
                           = 
                           1 
                         
                       
                     
                   
                 
                 
                   
                     
                       H 
                       t 
                     
                     = 
                     
                       ( 
                       
                         
                           
                             1 
                           
                         
                         
                           
                             
                               1 
                               + 
                               
                                 x 
                                 2 
                               
                             
                           
                         
                         
                           
                             
                               1 
                               + 
                               x 
                               + 
                               
                                 x 
                                 2 
                               
                             
                           
                         
                       
                       ) 
                     
                   
                 
                 
                   
                     G 
                     = 
                     
                       ( 
                       
                         
                           
                             
                               1 
                               + 
                               x 
                             
                           
                           
                             x 
                           
                           
                             
                               1 
                               + 
                               x 
                             
                           
                         
                         
                           
                             x 
                           
                           
                             1 
                           
                           
                             1 
                           
                         
                       
                       ) 
                     
                   
                 
               
             
           
         
       
     
   
   As shown in  FIGS. 4A and 4B , in both the hard and the soft cases, when the SNR is superior to 4 db, less than 10% of the ACS are required. Furthermore, the maximal number of required ACS remains inferior to 12% (resp. 27%) in the hard (resp. soft) case. The performances degradation remains inferior to 0.5 db (resp. 0.3 db) in the hard (resp. soft) case. 
                                     List of Reference Numerals                                1   sender       2   receiver       3   channel       4   encoder       5   decoder       200   receiver       202   program module       204   program module       208   program module       209   program module       212   program module                    
Annex 1: Examples of Control Matrix
 
   In the following a polynomial “p(X)” is called “p”. 
   Since all the polynomials p have their coefficients in the {0,1}we always have:
 
 p+p= 0
  1/2  convolutional codes:
 
                 {             C   1     =       g   1     ⁢     m   1                     C   2     =       g   2     ⁢     m   1                           ⇔     {               g   2     ⁢     C   1       =       g   2     ⁢     g   1     ⁢     m   1                       g   1     ⁢     C   2       =       g   1     ⁢     g   2     ⁢     m   1                               ⇒         g   2     ⁢     C   1       +       g   1     ⁢     C   2           =         g   2     ⁢     g   1     ⁢     m   1       +       g   2     ⁢     g   1     ⁢     m   1                       ⇒         g   2     ⁢     C   1       +       g   1     ⁢     C   2           =   0                   CH   t     =   0     ,       C   t     =     (           C   1               C   2           )       ,       H   t     =     (           g   2               g   1           )                    3/5  convolutional codes:
 
                 {             C   1     =         g   11     ⁢     m   1       +       g   12     ⁢     m   2       +       g   13     ⁢     m   3                       C   2     =         g   21     ⁢     m   1       +       g   22     ⁢     m   2       +       g   23     ⁢     m   3                       C   3     =         g   31     ⁢     m   1       +       g   32     ⁢     m   2       +       g   33     ⁢     m   3                       C   4     =         g   41     ⁢     m   1       +       g   42     ⁢     m   2       +       g   43     ⁢     m   3                       C   5     =         g   51     ⁢     m   1       +       g   52     ⁢     m   2       +       g   53     ⁢     m   3                             ⇔     {             C   1     =         g   11     ⁢     m   1       +       g   12     ⁢     m   2       +       g   13     ⁢     m   3                           g   21     ⁢     C   1       +       g   11     ⁢     C   2         =         (         g   11     ⁢     g   22       +       g   12     ⁢     g   21         )     ⁢     m   2       +       (         g   21     ⁢     g   13       +       g   23     ⁢     g   11         )     ⁢     m   3                           g   31     ⁢     C   1       +       g   11     ⁢     C   3         =         (         g   11     ⁢     g   32       +       g   12     ⁢     g   31         )     ⁢     m   2       +       (         g   31     ⁢     g   13       +       g   33     ⁢     g   11         )     ⁢     m   3                           g   41     ⁢     C   1       +       g   11     ⁢     C   4         =         (         g   11     ⁢     g   42       +       g   12     ⁢     g   41         )     ⁢     m   2       +       (         g   41     ⁢     g   13       +       g   43     ⁢     g   11         )     ⁢     m   3                           g   51     ⁢     C   1       +       g   51     ⁢     C   3         =         (         g   11     ⁢     g   52       +       g   12     ⁢     g   51         )     ⁢     m   2       +       (         g   51     ⁢     g   13       +       g   53     ⁢     g   11         )     ⁢     m   3                               ⇔     {             C   1     =         G   11     ⁢     m   1       +       G   12     ⁢     m   2       +       G   13     ⁢     m   3                           g   21     ⁢     C   1       +       g   11     ⁢     C   2         =         G   22     ⁢     m   2       +       G   23     ⁢     m   3                           (         g   31     ⁢     C   1       +       g   11     ⁢     C   3         )     ⁢     (     G   22     )       +       (     G   32     )     ⁢     (         g   21     ⁢     C   1       +       g   11     ⁢     C   2         )         =       G   33     ⁢     m   3                         (         g   41     ⁢     C   1       +       g   11     ⁢     C   4         )     ⁢     (     G   22     )       +       (     G   42     )     ⁢     (         g   21     ⁢     C   1       +       g   11     ⁢     C   2         )         =       G   43     ⁢     m   3                         (         g   51     ⁢     C   1       +       g   11     ⁢     C   5         )     ⁢     (     G   22     )       +       (     G   52     )     ⁢     (         g   21     ⁢     C   1       +       g   11     ⁢     C   2         )         =       G   53     ⁢     m   3                             
with:
 
                       G   11     =     g   11       ;       G   12     =     g   12       ;       G   12     =     g   12                       G   22     =         g   11     ⁢     g   22       +       g   12     ⁢     g   21           ;       G   23     =         g   21     ⁢     g   13       +       g   23     ⁢     g   11                           G   32     =         g   11     ⁢     g   32       +       g   12     ⁢     g   31           ;       G   42     =         g   11     ⁢     g   42       +       g   12     ⁢     g   41           ;       G   52     =         g   11     ⁢     g   52       +       g   12     ⁢     g   51                         G   33     =         (         g   11     ⁢     g   22       +       g   12     ⁢     g   21         )     ⁢     (         g   31     ⁢     g   13       +       g   33     ⁢     g   11         )       +       (         g   21     ⁢     g   13       +       g   23     ⁢     g   11         )     ⁢     (         g   11     ⁢     g   32       +       g   12     ⁢     g   31         )                       G   43     =         (         g   11     ⁢     g   22       +       g   12     ⁢     g   21         )     ⁢     (         g   41     ⁢     g   13       +       g   43     ⁢     g   11         )       +       (         g   21     ⁢     g   13       +       g   23     ⁢     g   11         )     ⁢     (         g   11     ⁢     g   42       +       g   12     ⁢     g   41         )                       G   53     =         (         g   11     ⁢     g   22       +       g   12     ⁢     g   21         )     ⁢     (         g   51     ⁢     g   13       +       g   53     ⁢     g   11         )       +       (         g   21     ⁢     g   13       +       g   23     ⁢     g   11         )     ⁢     (         g   11     ⁢     g   52       +       g   12     ⁢     g   51         )                 ⁢     
     ⇔     {                                 C   1     =         G   11     ⁢     m   1       +       G   12     ⁢     m   2       +       G   13     ⁢     m   3                           g   21     ⁢     C   1       +       g   11     ⁢     C   2         =         G   22     ⁢     m   2       +       G   23     ⁢     m   3                                 (         g   31     ⁢     C   1       +       g   11     ⁢     C   3         )     ⁢     (     G   22     )       +       (     G   32     )     ⁢     (         g   21     ⁢     C   1       +       g   11     ⁢     C   2         )         =       G   33     ⁢     m   3                               (         (         g   41     ⁢     C   1       +       g   11     ⁢     C   4         )     ⁢     (     G   22     )       +       (     G   42     )     ⁢     (         g   21     ⁢     C   1       +       g   11     ⁢     C   2         )         )     ⁢     G   33       +       (         (         g   31     ⁢     C   1       +       g   11     ⁢     C   3         )     ⁢     (     G   22     )       +       (     G   32     )     ⁢     (         g   21     ⁢     C   1       +       g   11     ⁢     C   2         )         )     ⁢     G   43         =   0                           (         (         g   51     ⁢     C   1       +       g   11     ⁢     C   5         )     ⁢     (     G   22     )       +       (     G   52     )     ⁢     (         g   21     ⁢     C   1       +       g   11     ⁢     C   2         )         )     ⁢     G   33       +       (         (         g   31     ⁢     C   1       +       g   11     ⁢     C   3         )     ⁢     (     G   22     )       +       (     G   32     )     ⁢     (         g   21     ⁢     C   1       +       g   11     ⁢     C   2         )         )     ⁢     G   53         =   0           ⁢     
     ⇒     {                   (         (         g   41     ⁢     G   22       +       g   21     ⁢     G   42         )     ⁢     G   33       +       (         g   31     ⁢     G   22       +       g   21     ⁢     G   32         )     ⁢     G   43         )     ⁢     C   1       +       (         g   11     ⁢     G   42     ⁢     G   33       +       g   11     ⁢     G   32     ⁢     G   43         )     ⁢     C   2       +       (       g   11     ⁢     G   22     ⁢     G   43       )     ⁢     C   3       +       (       g   11     ⁢     G   22     ⁢     G   33       )     ⁢     C   4       +       (   0   )     ⁢     C   5         =   0                     (         (         g   51     ⁢     G   22       +       g   21     ⁢     G   52         )     ⁢     G   33       +       (         g   31     ⁢     G   22       +       g   21     ⁢     G   52         )     ⁢     G   53         )     ⁢     C   1       +       (         g   11     ⁢     G   52     ⁢     G   33       +       g   11     ⁢     G   32     ⁢     G   53         )     ⁢     C   2       +       (       g   11     ⁢     G   22     ⁢     G   53       )     ⁢     C   3       +       (   0   )     ⁢     C   4       +       (       g   11     ⁢     G   22     ⁢     G   33       )     ⁢     C   5         =   0           ⁢     
     ⁢             CH   t     =   0               H   =     (               (         g   41     ⁢     G   22       +       g   21     ⁢     G   42         )     ⁢     G   33       +       (         g   31     ⁢     G   22       +       g   21     ⁢     G   32         )     ⁢     G   43                   g   11     ⁢     G   42     ⁢     G   33       +       g   11     ⁢     G   32     ⁢     G   43                 g   11     ⁢     G   22     ⁢     G   43               g   11     ⁢     G   22     ⁢     G   33           0                 (         g   51     ⁢     G   22       +       g   21     ⁢     G   52         )     ⁢     G   33       +       (         g   31     ⁢     G   22       +       g   21     ⁢     G   52         )     ⁢     G   53                   g   11     ⁢     G   52     ⁢     G   33       +       g   11     ⁢     G   32     ⁢     G   53                 g   11     ⁢     G   22     ⁢     G   53           0           g   11     ⁢     G   22     ⁢     G   33             )                 C   =     (           C   1           C   2           C   3           C   4           C   5           )                           
Annex 2: Fast Forward Error Correction (Hard Decoder Input Case)
 
   We hove to find the 
               e   ′     ⁡     (   x   )       =       ∑     i   =   1     N     ⁢       x     i   -   1       ⁢       e   1   ′     ⁡     (     x   N     )                 
word with minimal weight such as
 
             H   ⁡     (   x   )       ·           (               r   1     ⁡     (   x   )       +       e   1   ′     ⁡     (   x   )                 ⋯                 r   N     ⁡     (   x   )       +       e   N   ′     ⁡     (   x   )               )             
is null. We can mathematically show the following equivalence:
 
             H   ⁡     (   x   )       ·             (               r   1     ⁡     (   x   )       +       e   1   ′     ⁡     (   x   )                       ⋯           ⋯                       r   N     ⁡     (   x   )       +       e   N   ′     ⁡     (   x   )               )     =       E   ⁡     (   x   )       =       (         0           ⋯           0         )     ⇔       r   ⁡     (   x   )       +       e   ′     ⁡     (   x   )                       
is a codeword with
 
   
     
       
         
           
             E 
             ⁡ 
             
               ( 
               x 
               ) 
             
           
           = 
           
               
             
               ( 
               
                 
                   
                     
                       
                         E 
                         1 
                       
                       ⁡ 
                       
                         ( 
                         x 
                         ) 
                       
                     
                   
                 
                 
                   
                     ⋯ 
                   
                 
                 
                   
                     
                       
                         E 
                         
                           N 
                           - 
                           K 
                         
                       
                       ⁡ 
                       
                         ( 
                         x 
                         ) 
                       
                     
                   
                 
               
               ) 
             
           
         
       
     
   
   The search of e′(x) can be done by using the Viterbi Algorithm to cancel the matrix E(x) 
   
     
       
         
           
             
               
                 E 
                 j 
               
               ⁡ 
               
                 ( 
                 x 
                 ) 
               
             
             = 
             
               
                 ∑ 
                 i 
               
               ⁢ 
               
                 
                   E 
                   
                     j 
                     , 
                     i 
                   
                 
                 ⁢ 
                 
                   x 
                   i 
                 
               
             
           
           ; 
           
             1 
             ≤ 
             j 
             ≤ 
             
               N 
               - 
               K 
             
           
         
       
     
   
   The trellis used in the Viterbi Algorithm is constituted of nodes corresponding to distinct states. These nodes are connected by branches. A succession of branches is called a path and a path is characterized by a metric. 
   States 
   There are 2 M−1  states, where M−1 is the memory of the code. A matrix E S     k    (x) is associated with each state S k . The value of the state S k  at time n is given by the M−1 elements of the matrix E S     k    (x) as follows: 
   
     
       
         
           
             
               
                 E 
                 j 
                 
                   S 
                   k 
                 
               
               ⁡ 
               
                 ( 
                 x 
                 ) 
               
             
             = 
             
               
                 ∑ 
                 i 
               
               ⁢ 
               
                 
                   E 
                   
                     j 
                     , 
                     i 
                   
                   
                     S 
                     k 
                   
                 
                 ⁢ 
                 
                   x 
                   i 
                 
               
             
           
           ; 
           
             1 
             ≤ 
             j 
             ≤ 
             
               N 
               - 
               K 
             
           
         
       
     
     
       
         
           
             S 
             k 
           
           = 
           
             
               { 
               
                 
                   
                     
                       V 
                       1 
                     
                   
                   
                     
                       V 
                       2 
                     
                   
                   
                     … 
                   
                   
                     
                       V 
                       
                         N 
                         - 
                         K 
                       
                     
                   
                 
               
               } 
             
             ⁢ 
             
                 
             
             ⁢ 
             with 
           
         
       
     
     
       
         
           { 
           
             
               
                 
                   
                     V 
                     j 
                   
                   = 
                   
                     { 
                     
                       
                         E 
                         
                           j 
                           , 
                           n 
                         
                         
                           S 
                           k 
                         
                       
                       , 
                       
                         E 
                         
                           j 
                           , 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           S 
                           k 
                         
                       
                       , 
                       … 
                       ⁢ 
                       
                           
                       
                       , 
                       
                         E 
                         
                           j 
                           , 
                           
                             n 
                             + 
                             Mj 
                             - 
                             2 
                           
                         
                         
                           S 
                           k 
                         
                       
                     
                     } 
                   
                 
               
             
             
               
                 
                   Mj 
                   = 
                   
                     
                       max 
                       i 
                     
                     ⁢ 
                     
                       ( 
                       
                         degree 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         of 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         hij 
                       
                       ) 
                     
                   
                 
               
             
           
         
       
     
   
   The initial state S k,0  is associated to E(x). 
   Branches 
   A branch represents the transition between one state at time n (current state) and one state at time n+1 (following state). Let us call: 
   
     
       
         
           
             e 
             
               i 
               , 
               n 
             
             ′ 
           
           ⁢ 
           
             :  coefficient 
           
           ⁢ 
           
               
           
           ⁢ 
           n 
           ⁢ 
           
               
           
           ⁢ 
           of 
           ⁢ 
           
               
           
           ⁢ 
           
             e 
             i 
             ′ 
           
         
       
     
   
   A set of coefficient 
           {       e     1   ,   n     ′     ,   …   ⁢           ,     e     N   ,   n     ′       }         
is associated to each branch. At time n, one builds the set {Z i (x)} of sequences
 
                 Z   i     ⁡     (   x   )       =           H   ⁡     (   x   )       ·     (                       e     1   ,   n     ′             …                 …                   e     N   ,   n     ′           )       ⁢           ⁢     x   n       =         (                 Z     1   ,   i               …                   Z       N   -   K     ,   i             )     ⁢           ⁢   with   ⁢           ⁢       Z     j   ,   i       ⁡     (   x   )         =       ∑     l   =   0       Mj   -   1       ⁢       Z     j   ,   i     l     ⁢     x     n   +   l                 ;               1   ≤   i   ≤     2   n           
where the first coefficient Z j,i   0  satisfies the condition:
 
   
     
       
         
           
             Z 
             
               j 
               , 
               i 
             
             0 
           
           = 
           
             
               
                 E 
                 
                   j 
                   , 
                   n 
                 
                 Sk 
               
               ⁢ 
               
                   
               
               ⁢ 
               for 
               ⁢ 
               
                   
               
               ⁢ 
               1 
             
             ≤ 
             j 
             ≤ 
             
               N 
               - 
               K 
             
           
         
       
     
   
   Let S k  be the current state at time n, let S i  be S k  following state (at time n+1) and let E S     i    be the associated polynomial. We have: 
   
     
       
         
           
             
               
                 
                   
                     E 
                     j 
                     
                       S 
                       i 
                     
                   
                   ⁡ 
                   
                     ( 
                     x 
                     ) 
                   
                 
                 = 
                 
                   
                     
                       
                         E 
                         j 
                         
                           S 
                           k 
                         
                       
                       ⁡ 
                       
                         ( 
                         x 
                         ) 
                       
                     
                     + 
                     
                       
                         
                           Z 
                           
                             j 
                             , 
                             i 
                           
                         
                         ⁡ 
                         
                           ( 
                           x 
                           ) 
                         
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       for 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       1 
                     
                   
                   ≤ 
                   j 
                   ≤ 
                   
                     N 
                     - 
                     K 
                   
                 
               
             
           
           
             
               
                 
                   S 
                   i 
                 
                 = 
                 
                   
                     { 
                     
                       
                         V 
                         1 
                       
                       ⁢ 
                       
                         V 
                         2 
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       … 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         V 
                         
                           N 
                           - 
                           K 
                         
                       
                     
                     } 
                   
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   with 
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   
                     { 
                     
                       
                         
                           
                             
                               V 
                               j 
                             
                             = 
                             
                               { 
                               
                                 
                                   
                                     E 
                                     
                                       j 
                                       , 
                                       n 
                                     
                                     
                                       S 
                                       k 
                                     
                                   
                                   + 
                                   
                                     Z 
                                     
                                       j 
                                       , 
                                       1 
                                     
                                     i 
                                   
                                 
                                 , 
                                 
                                   
                                     E 
                                     
                                       j 
                                       , 
                                       
                                         n 
                                         + 
                                         1 
                                       
                                     
                                     
                                       S 
                                       k 
                                     
                                   
                                   + 
                                   
                                     Z 
                                     
                                       j 
                                       , 
                                       2 
                                     
                                     i 
                                   
                                 
                                 , 
                                 … 
                                 ⁢ 
                                 
                                     
                                 
                                 , 
                               
                             
                           
                         
                       
                       
                         
                           
                             
                                 
                             
                             ⁢ 
                             
                               
                                 E 
                                 
                                   j 
                                   , 
                                   
                                     n 
                                     + 
                                     Mj 
                                     - 
                                     2 
                                   
                                 
                                 
                                   S 
                                   k 
                                 
                               
                               + 
                               
                                 Z 
                                 
                                   j 
                                   , 
                                   
                                     Mj 
                                     - 
                                     1 
                                   
                                 
                                 i 
                               
                             
                             } 
                           
                         
                       
                       
                         
                           
                             Mj 
                             = 
                             
                               
                                 max 
                                 i 
                               
                               ⁢ 
                               
                                 ( 
                                 
                                   degree 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   of 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   hij 
                                 
                                 ) 
                               
                             
                           
                         
                       
                     
                   
                 
               
             
           
         
       
     
   
   This procedure leads to an iterative cancellation of the matrix E S   s k . 
   Metrics 
   The principle of the proposed decoding technique is to find the sequence e′(x) of minimum weight which cancels the matrix E(x). It leads to define the branch metric at time n by: 
   
     
       
         
           
             Δ 
             ⁡ 
             
               ( 
               n 
               ) 
             
           
           = 
           
             
               ∑ 
               
                 i 
                 = 
                 1 
               
               N 
             
             ⁢ 
             
                 
             
             ⁢ 
             
               e 
               
                 i 
                 , 
                 n 
               
               ′ 
             
           
         
       
     
   
   Remark: in the soft case we have 
             Δ   ⁡     (   n   )       =       ∑     i   =   1     N     ⁢           ⁢            R     i   ,   n            ⁢     e     i   ,   n     ′               
where the R i,n  are the received soft symbols. The path metric mk(n) is the accumulation of the branch metrics. When several paths come to the same state, the survivor is the one with the smallest path metric. At the end of the procedure, the survivor path is the one terminating in the state S 0 ={0 0 . . . 0}, which is the unique state having all the elements of E S     k   (x) to be null. All the set {e 1,n ′, . . . , e N,n ′} associated to each branch of the survivor constitute the decoded error vector e′(x).
 
               e   ′     ⁡     (   x   )       =       ∑   n             ⁢           ⁢       (       ∑     i   =   1     N     ⁢           ⁢       x     i   -   1       ⁢     e     i   ,   n     ′         )     ⁢     x   Nn               
“FEC Useless” Zone
 
   If at one step denoted n 0  the properties (P1) and (P2) are both satisfied, then it is unnecessary to carry on the Viterbi Algorithm. The survivor path is the one which reaches the state S 0 ={0 0 . . . 0} at the iteration n 0  and which remains in this state S 0  after this node.
 
 E   S     0   ( x )={0,0, . . . ,0} for all  j  1≦ j≦N−K   (P1)
 
 m   k ( n   0 )≧ m   0 ( n   0 ) for  k≠ 0  (P2)
 
   Furthermore, let us assume that, at time n−n1, condition (P2) is satisfied and that all the vectors E j   S     k   (x) verify: 
   
     
       
         
           
             
               
                 
                   { 
                   
                     
                       E 
                       
                         j 
                         , 
                         0 
                       
                       
                         S 
                         k 
                       
                     
                     , 
                     
                       E 
                       
                         j 
                         , 
                         1 
                       
                       
                         S 
                         k 
                       
                     
                     , 
                     … 
                     ⁢ 
                     
                         
                     
                     , 
                     
                       E 
                       
                         j 
                         , 
                         
                           n 
                           - 
                           
                             n 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             1 
                           
                           - 
                           1 
                         
                       
                       
                         S 
                         k 
                       
                     
                   
                   } 
                 
                 = 
                 
                   { 
                   
                     0 
                     , 
                     0 
                     , 
                     … 
                     ⁢ 
                     
                         
                     
                     , 
                     0 
                   
                   } 
                 
               
             
           
           
             
               
                 
                   { 
                   
                     
                       E 
                       
                         j 
                         , 
                         
                           n 
                           - 
                           
                             n 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             1 
                           
                         
                       
                       
                         S 
                         k 
                       
                     
                     , 
                     
                       E 
                       
                         j 
                         , 
                         
                           n 
                           - 
                           
                             n 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             1 
                           
                           + 
                           1 
                         
                       
                       
                         S 
                         k 
                       
                     
                     , 
                     … 
                     ⁢ 
                     
                         
                     
                     , 
                     
                       E 
                       
                         j 
                         , 
                         
                           n 
                           - 
                           
                             n 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             1 
                           
                           + 
                           Mj 
                           - 
                           2 
                         
                       
                       
                         S 
                         k 
                       
                     
                   
                   } 
                 
                 = 
                 
                   V 
                   j 
                 
               
             
           
           
             
               
                 
                   { 
                   
                     
                       E 
                       
                         j 
                         , 
                         
                           n 
                           - 
                           
                             n 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             1 
                           
                           + 
                           Mj 
                           - 
                           1 
                         
                       
                       
                         S 
                         k 
                       
                     
                     , 
                     
                       E 
                       
                         j 
                         , 
                         
                           n 
                           - 
                           
                             n 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             1 
                           
                           + 
                           Mj 
                         
                       
                       
                         S 
                         k 
                       
                     
                     , 
                     … 
                     ⁢ 
                     
                         
                     
                     , 
                     
                       E 
                       
                         j 
                         , 
                         n 
                       
                       
                         S 
                         k 
                       
                     
                   
                   } 
                 
                 = 
                 
                   { 
                   
                     0 
                     , 
                     0 
                     , 
                     … 
                     ⁢ 
                     
                         
                     
                     , 
                     0 
                   
                   } 
                 
               
             
           
           
             
               
                 
                   E 
                   
                     j 
                     , 
                     
                       n 
                       + 
                       1 
                     
                   
                   
                     S 
                     k 
                   
                 
                 = 
                 1 
               
             
           
         
       
     
   
   This configuration can occur if there are at least n1 successive zeros in E(x). Then we can theoretically show that it is unnecessary to carry on the Viterbi Algorithm between step n−n1 and n−M+1 if n1 is superior to a certain threshold which depends on the coder. The Viterbi Algorithm is restarted at step n−M+1 with S 0  as initial state. 
   Remark: in the soft case the Viterbi algorithm has to be restarted at step n−A+1 where the choice of A results from a trade-off between complexity reduction and performances degradation. 
   Final Estimation 
   The final decoded information sequence m′(x) is given by an algebraic decoding of the codeword r(x)+e′(x). 
   Annex 3: Proof 
   Convolutional codes of rate ½: 
   m(x): information word 
   g 1 (x),g 2 (x) generator polynomials 
   C 1 (x)=m(x)·g 1 (x): code-word from polynomial g 1 , 
   C 2 (x)=m(X)·g 2 (x): code-word from polynomial g 2 , 
   r 1 (x)=C 1 (x)+e 1 (x): received word  1 , 
   r 2 (x)=C 2 (x)+e 2 (x): received word  2 . 
   Using the Parity Check Matrix: 
   Minimal Parity check Matrix: 
   
     
       
         
           
             H 
             t 
           
           = 
           
             ( 
             
               
                 
                   
                     g 
                     2 
                   
                 
               
               
                 
                   
                     g 
                     1 
                   
                 
               
             
             ) 
           
         
       
     
   
   For any code word 
             C   t     =     (           C   1               C   2           )           
we have: CH t =0
 
   If we call R t =(r 1  r 2 ) the total received data word we have: 
                   R   .     H   t       =       (       r   1     ⁢           ⁢     r   2       )     ⁢     (           g   2               g   1           )                     R   .     H   t       =       (       C   1     +       e   1     ⁢           ⁢     C   2       +     e   2       )     ⁢     (           g   2               g   1           )                     R   .     H   t       =     0   +       e   1     ⁢     g   2       +       e   2     ⁢     g   1                       R   .       H   t     ⁡     (   x   )         =           e   1     ⁡     (   x   )       ⁢       g   2     ⁡     (   x   )         +         e   2     ⁡     (   x   )       ⁢       g   1     ⁡     (   x   )                       
Using Simple Polynomial Manipulations: . . .
 
   We call G the equivalent generator polynomial and C the total resulting code word defined by:
 
 G ( x )= g   1 ( x   2 )+ x·g   2 ( x   2 )
 
 C ( x )= C   1 ( x   2 )+ x·C   2 ( x   2 )= m ( x   2 )· G ( x )
 
   We can show that C(x)G(x) is an even polynomial:
 
 C ( x )· G ( x )= m ( x   2 )· G ( x )· G ( x )= m ( x   2 )· G ( x   2 )
 
if we call e(x) the error polynomial and r(x) the received polynomial defined by
 
 e ( x )= e   1 ( x   2 )+ x·e   2 ( x   2)  
 
 r ( x )= C ( x )+ e ( x )
 
we have:
 
 r ( x )· G ( x )= C ( x )· G ( x )+ e ( x )· G ( x )
 
 r ( x )· G ( x )= C ( x )· G ( x )+e 1 ( x   2 )· g   1 ( x   2 )+ x   2   ·e   2 ( x   2 )·g 2 ( x   2 )+ x     19  (e   1 ( x   2 )·g 2 ( x   2 )+ e   2 ( x   2 )· g   1 (x 2 ))
 
   Therefore:
 
Odd { r ( x )· G ( x )}= e   1 ( x   2 )· g   2 ( x   2 )+ e   2 ( x   2 )· g   1 ( x   2 )=&gt;same coefficient than  R·H   t  
 
   Finally, the odd part of the polynomial r(x)·G(x) has the same coefficient than the results of the received data word multiplied by the parity check matrix.