Abstract:
This invention provides an iterative process to maximum a posteriori (MAP) decoding. The iterative process uses an auxiliary function which is defined in terms of a complete data probability distribution. The auxiliary function is derived based on an expectation maximization (EM) algorithm. For a special case of trellis coded modulators, the auxiliary function may be iteratively evaluated by a combination of forward-backward and Viterbi algorithms. The iterative process converges monotonically and thus improves the performance of any decoding algorithm. The MAP decoding minimizes a probability of error. A direct approach to achieve this minimization results in complexity which grows exponentially with T, where T is the size of the input. The iterative process avoids this complexity by converging on the MAP solution through repeated maximization of the auxiliary function.

Description:
[0001]    This is a continuation of U.S. patent application Ser. No. 10/789,794 filed Feb. 28, 2004, which is a continuation of U.S. patent application Ser. No. 09/549,201 filed Apr. 13, 2000, that followed provisional application No. 60/174,601 entitled “Map Decoding In Channels With Memory” filed on Jan. 5, 2000 now U.S. Pat. No. 6,700,937, issued Mar. 2, 2004. All materials included in the aforementioned applications directly or by incorporation are hereby incorporated by reference including all references cited therein. 
     
    
     BACKGROUND OF THE INVENTION 
       [0002]    1. Field of Invention 
         [0003]    This invention relates to iterative decoding of input sequences. 
         [0004]    2. Description of Related Art 
         [0005]    Maximum a posteriori (MAP) sequence decoding selects a most probable information sequence X 1   T =(X 1 , X 2 , . . . , X T ) that produced the received sequence Y 1   T =(Y 1 , Y 2 , . . . , Y T ). For transmitters and/or channels that are modeled using Hidden Markov Models (HMM), the process for obtaining the information sequence X 1   T  that corresponds to a maximum probability is difficult due to a large number of possible hidden states as well as a large number of possible information sequences X 1   T . Thus, new technology is needed to improve MAP decoding for HMMs. 
       SUMMARY OF THE INVENTION 
       [0006]    This invention provides an iterative process to maximum a posteriori (MAP) decoding. The iterative process uses an auxiliary function which is defined in terms of a complete data probability distribution. The MAP decoding is based on an expectation maximization (EM) algorithm which finds the maximum by iteratively maximizing the auxiliary function. For a special case of trellis coded modulation, the auxiliary function may be maximized by a combination of forward-backward and Viterbi algorithms. The iterative process converges monotonically and thus improves the performance of any decoding algorithm. 
         [0007]    The MAP decoding decodes received inputs by minimizing a probability of error. A direct approach to achieve this minimization results in a complexity which grows exponentially with T, where T is the size of the input. The iterative process avoids this complexity by converging on the MAP solution through repeated use of the auxiliary function. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0008]    The invention is described in detail with reference to the following figures where like numerals reference like elements, and wherein: 
           [0009]      FIG. 1  shows a diagram of a communication system; 
           [0010]      FIG. 2  shows a flow chart of an exemplary iterative process; 
           [0011]      FIGS. 3-6  show state trajectories determined by the iterative process; 
           [0012]      FIG. 7  shows an exemplary block diagram of the receiver shown in  FIG. 1 ; 
           [0013]      FIG. 8  shows a flowchart for an exemplary process of the iterative process for a TCM example; and 
           [0014]      FIG. 9  shows step  1004  of the flowchart of  FIG. 8  in greater detail. 
       
    
    
     DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS 
       [0015]      FIG. 1  shows an exemplary block diagram of a communication system  100 . The communication system  100  includes a transmitter  102 , a channel  106  and a receiver  104 . The transmitter  102  receives an input information sequence I 1   T  (i.e., I 1 , I 2 , . . . , I T ) of length T, for example. The input information sequence may represent any type of data including analog voice, analog video, digital image, etc. The transmitter  102  may represent a speech synthesizer, a signal modulator, etc.; the receiver  104  may represent a speech recognizer, a radio receiver, etc.; and the channel  106  may be any medium through which the information sequence X 1   T  (i.e., X 1 , X 2 , . . . , X T ) is conveyed to the receiver  104 . The transmitter  102  may encode the information sequence I 1   T  and transmit encoded information sequence X 1   T  through the channel  106  and the receiver  104  receives information sequence Y 1   T  (i.e., Y 1 , Y 2 , . . . , Y T ). The problem in communications is, of course, to decode Y 1   T  in such a way as to retrieve I 1   T . 
         [0016]    Maximum a posteriori (MAP) sequence decoding is a technique that decodes the received sequence Y 1   T  by minimizing a probability of error to obtain X 1   T  (and if a model of the transmitter  102  is included, to obtain I 1   T ). In MAP, the goal is to choose a most probable X 1   T  that produces the received Y 1   T  The MAP estimator may be expressed by equation 1 below. 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       X 
                       ^ 
                     
                     1 
                     T 
                   
                   = 
                   
                     
                       
                         arg 
                          
                         
                             
                         
                          
                         max 
                       
                       
                         X 
                         1 
                         T 
                       
                     
                      
                     
                       Pr 
                        
                       
                         ( 
                         
                           
                             X 
                             1 
                             T 
                           
                           , 
                           
                             Y 
                             1 
                             T 
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where Pr(·) denotes a corresponding probability or probability density function and {circumflex over (X)} 1   T  is an estimate of X 1   T . Equation 1 sets {circumflex over (X)} 1   T  to the X 1   T  that maximizes Pr(X 1   T , Y 1   T ). 
         [0017]    The Pr (X 1   T , Y 1   T ) term may be obtained by modeling the channel  106  of the communication system  100  using techniques such as Hidden Markov Models (HMMs). An input-output HMM λ=(S,X,Y,π,{P(X,Y)}) is defined by its internal states S={1,2, . . . n}, inputs X, outputs Y, initial state probability vector λ, and the input-output probability density matrices (PDMs) P(X,Y), XεX, YεY. The elements of P(X,Y), p ij (X,Y)=Pr(j,X,Y|i), are conditional probability density functions (PDFs) of input x and corresponding output y after transferring from the state i to state j. It is assumed that the state sequence S 0   t =(S 0 , S 1 , . . . , S t ), input sequence X 1   t =(X 1 , X 2 , . . . X t ), and output sequence Y 1   t =(Y 1 , Y 2 , . . . , Y t ) possess the following Markovian property 
         [0000]        Pr ( S   t   ,X   t   ,Y   t   |S   0   t−1   ,Y   1   t−1 )= Pr ( S   t   ,X   t   ,Y   t   |S   t−1 ). 
         [0000]    Using HMM, the PDF of the input sequence X 1   T  and output sequence Y 1   T  may be expressed by equation 2 below: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       p 
                       T 
                     
                      
                     
                       ( 
                       
                         
                           X 
                           1 
                           T 
                         
                         , 
                         
                           Y 
                           1 
                           T 
                         
                       
                       ) 
                     
                   
                   = 
                   
                     π 
                      
                     
                       
                         ∏ 
                         
                           i 
                           = 
                           1 
                         
                         T 
                       
                        
                       
                           
                       
                        
                       
                         
                           P 
                            
                           
                             ( 
                             
                               
                                 X 
                                 i 
                               
                               , 
                               
                                 Y 
                                 i 
                               
                             
                             ) 
                           
                         
                          
                         1 
                       
                     
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where 1 is a column vector of n ones, π is a vector of state initial probabilities, and n is a number of states in the HMM. Thus, the MAP estimator when using HMM may be expressed by equation 3 below: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       X 
                       ^ 
                     
                     1 
                     T 
                   
                   = 
                   
                     arg 
                      
                     
                         
                     
                      
                     
                       
                         max 
                         
                           X 
                           1 
                           T 
                         
                       
                        
                       
                         [ 
                         
                           π 
                            
                           
                             
                               ∏ 
                               
                                 i 
                                 = 
                                 1 
                               
                               T 
                             
                              
                             
                                 
                             
                              
                             
                               
                                 P 
                                  
                                 
                                   ( 
                                   
                                     
                                       X 
                                       i 
                                     
                                     , 
                                     
                                       Y 
                                       i 
                                     
                                   
                                   ) 
                                 
                               
                                
                               1 
                             
                           
                         
                         ] 
                       
                     
                   
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
           
         
       
     
         [0018]    The maximization required by equation 3 is a difficult problem because all possible sequences of X 1   T  must be considered. This requirement results in a complexity that grows exponentially with T. This invention provides an iterative process to obtain the maximum without the complexity of directly achieving the maximization by evaluating equation 2 for all possible X 1   T , for example. In the iterative process, an auxiliary function is developed whose iterative maximization generates a sequence of estimates for X 1   T  approaching the maximum point of equation 2. 
         [0019]    The iterative process is derived based on the expectation maximization (EM) algorithm. Because the EM algorithm converges monotonically, the iterative process may improve the performance of any decoding algorithm by using its output as an initial sequence of the iterative decoding algorithm. In the following description, it is assumed that HMM parameters for the channel  106  and/or the transmitter  102  are available either by design or by techniques such as training. 
         [0020]    The auxiliary function may be defined in terms of a complete data probability distribution shown in equation 4 below. 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       Ψ 
                        
                       
                         ( 
                         
                           z 
                           , 
                           
                             X 
                             1 
                             T 
                           
                           , 
                           
                             Y 
                             1 
                             T 
                           
                         
                         ) 
                       
                     
                     = 
                     
                       
                         π 
                         
                           i 
                           o 
                         
                       
                        
                       
                         
                           ∏ 
                           
                             i 
                             = 
                             1 
                           
                           T 
                         
                          
                         
                             
                         
                          
                         
                           
                             p 
                             
                               
                                 i 
                                 
                                   t 
                                   - 
                                   1 
                                 
                               
                                
                               
                                 i 
                                 t 
                               
                             
                           
                            
                           
                             ( 
                             
                               
                                 X 
                                 t 
                               
                               , 
                               
                                 Y 
                                 t 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where z=i 0   T  is an HMM state sequence, π i     0    is an initial probability vector for state i 0 , and p ij (X,Y) are the elements of the matrix P(X,Y). The MAP estimator of equation 1 can be obtained iteratively by equations 5-9 as shown below. 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       X 
                       
                         1 
                         , 
                         
                           p 
                           + 
                           1 
                         
                       
                       T 
                     
                     = 
                     
                       arg 
                        
                       
                           
                       
                        
                       
                         
                           max 
                           
                             X 
                             1 
                             T 
                           
                         
                          
                         
                           Q 
                            
                           
                             ( 
                             
                               
                                 X 
                                 1 
                                 T 
                               
                               , 
                               
                                 X 
                                 
                                   1 
                                   , 
                                   p 
                                 
                                 T 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                   , 
                   
                     p 
                     = 
                     0 
                   
                   , 
                   1 
                   , 
                   2 
                   , 
                   … 
                 
               
               
                 
                   ( 
                   5 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where p is a number of iterations and Q(X i   t , X i,p   t ) is the auxiliary function which may be expressed as 
         [0000]    
       
         
           
             
               
                 
                   
                     Q 
                      
                     
                       ( 
                       
                         
                           X 
                           1 
                           T 
                         
                         , 
                         
                           X 
                           
                             1 
                             , 
                             p 
                           
                           T 
                         
                       
                       ) 
                     
                   
                   = 
                   
                     
                       ∑ 
                       z 
                     
                      
                     
                       
                         Ψ 
                          
                         
                           ( 
                           
                             z 
                             , 
                             
                               X 
                               
                                 1 
                                 , 
                                 p 
                               
                               T 
                             
                             , 
                             
                               Y 
                               1 
                               T 
                             
                           
                           ) 
                         
                       
                        
                       
                         
                           log 
                            
                           
                             ( 
                             
                               Ψ 
                                
                               
                                 ( 
                                 
                                   z 
                                   , 
                                   
                                     X 
                                     1 
                                     T 
                                   
                                   , 
                                   
                                     Y 
                                     1 
                                     T 
                                   
                                 
                                 ) 
                               
                             
                             ) 
                           
                         
                         . 
                       
                     
                   
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
           
         
       
     
         [0000]    The auxiliary function may be expanded based on equation 4 as follows: 
         [0000]    
       
         
           
             
               
                 
                   
                     Q 
                      
                     
                       ( 
                       
                         
                           X 
                           1 
                           T 
                         
                         , 
                         
                           X 
                           
                             1 
                             , 
                             p 
                           
                           T 
                         
                       
                       ) 
                     
                   
                   = 
                   
                     
                       
                         ∑ 
                         
                           t 
                           = 
                           1 
                         
                         T 
                       
                        
                       
                         
                           ∑ 
                           
                             i 
                             = 
                             1 
                           
                           n 
                         
                          
                         
                           
                             ∑ 
                             
                               j 
                               = 
                               1 
                             
                             n 
                           
                            
                           
                             
                               
                                 γ 
                                 
                                   t 
                                   , 
                                   ij 
                                 
                               
                                
                               
                                 ( 
                                 
                                   X 
                                   
                                     1 
                                     , 
                                     p 
                                   
                                   T 
                                 
                                 ) 
                               
                             
                              
                             
                               log 
                                
                               
                                 ( 
                                 
                                   
                                     p 
                                     ij 
                                   
                                    
                                   
                                     ( 
                                     
                                       
                                         X 
                                         t 
                                       
                                       , 
                                       
                                         Y 
                                         t 
                                       
                                     
                                     ) 
                                   
                                 
                                 ) 
                               
                             
                           
                         
                       
                     
                     + 
                     C 
                   
                 
               
               
                 
                   ( 
                   7 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where C does not depend on X 1   T , n is a number of states in the HMM and 
         [0000]      γ t,ij ( X   1,p   T )=α i ( X   1,p   t−1   ,Y   1   t−1 ) p   ij ( X   t,p   ,Y   t )β j ( X   t+1,p   T   ,Y   1+1   T )  (8) 
         [0000]    where α i (X 1,p   t , Y 1   t ) and β j (X t+1,p   T , Y t+1   T ) are the elements of the following forward and backward probability vectors 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         α 
                          
                         
                           ( 
                           
                             
                               X 
                               1 
                               T 
                             
                             , 
                             
                               Y 
                               1 
                               T 
                             
                           
                           ) 
                         
                       
                       = 
                       
                         π 
                          
                         
                           
                             ∏ 
                             
                               i 
                               = 
                               1 
                             
                             T 
                           
                            
                           
                               
                           
                            
                           
                             P 
                              
                             
                               ( 
                               
                                 
                                   X 
                                   i 
                                 
                                 , 
                                 
                                   Y 
                                   i 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                     , 
                     
                       
 
                     
                      
                     and 
                   
                    
                   
                       
                   
                    
                   
                     
 
                   
                    
                   
                     
                       β 
                        
                       
                         ( 
                         
                           
                             X 
                             
                               t 
                               + 
                               1 
                             
                             T 
                           
                           , 
                           
                             Y 
                             
                               t 
                               + 
                               1 
                             
                             T 
                           
                         
                         ) 
                       
                     
                     = 
                     
                       
                         ∏ 
                         
                           i 
                           = 
                           
                             t 
                             + 
                             1 
                           
                         
                         T 
                       
                        
                       
                           
                       
                        
                       
                         
                           P 
                            
                           
                             ( 
                             
                               
                                 X 
                                 i 
                               
                               , 
                               
                                 Y 
                                 i 
                               
                             
                             ) 
                           
                         
                          
                         1. 
                       
                     
                   
                 
               
               
                 
                   ( 
                   9 
                   ) 
                 
               
             
           
         
       
     
         [0021]    Based on equations 5-9, the iterative process may proceed as follows. At p=0, an initial estimate of X 1,0   T  is generated. Then, Q(X 1   T ,X 1,0   T ) is generated for all possible sequences of X 1   T . From equations 7 and 8, Q(X 1   T ,X 1,0   T ) may be evaluated by generating γ t,ij (X 1,0   T ) and log (p ij (X t ,Y t )) for each t, i, and j. γ t,ij (X 1,0   T ) may be generated by using the forward-backward algorithm as shown below: 
         [0000]      α( X   1,p   0   ,Y   1   0 )=π, α( X   1,p   t   ,Y   1   t )=α( X   1,p   t−1   ,Y   1   t−1 ) P ( X   t,p   ,Y   t ), t=1,2, . . .  T    
         [0000]      β( X   T+1,p   T   ,Y   T+1   T )=1, β( X   t,p   T   ,Y   t   T )= P ( X   t+1,p   T   ,Y   t+1   T ),  t=T− 1 ,T− 2, . . . , 1 
         [0022]    Log(p ij (X t ,Y t )) is generated for all possible X t  for t=1, 2, . . . , T and the (X t )s that maximize D(X 1   T ,X 1,0   T ) are selected as X 1,1   T . After X 1,1   T  is obtained, it is compared with X 1,0   T . If a measure D(X 1,1   T ,X 1,0   T ) of difference between the sequences exceeds a compare threshold, then the above process is repeated until the difference measure D(X 1,p   T ,X 1,p−1   T ) is within the threshold. The last X 1,p   T  for p iterations is the decoded output. The measure of difference may be an amount of mismatch information. For example, if X 1   T  is a sequence of symbols, then the measure may be a number of different symbols between X 1,p   T  and X 1,p−1   T  (Hamming distance); if X 1   T  is a sequence of real numbers, then the measure may be an Euclidean distance D(X 1,p   T ,X 1,p−1   T )=[Σ i=1   T (X i,p −X i,p−1 ) 2 ] 1/2 . 
         [0023]      FIG. 2  shows a flowchart of the above-described process. In step  1000 , the receiver  104  receives the input information sequence Y 1   T  and goes to step  1002 . In step  1002 , the receiver  104  selects an initial estimate for the decode output information sequence X 1,0   T  and goes to step  1004 . In step  1004 , the receiver  104  generates γ t,ij (X 1,p   T ) where p=0 for the first iteration and goes to step  1006 . In step  1006 , the receiver  104  generates all the log (p ij (X t ,Y t )) values and goes to step  1008 . 
         [0024]    In step  1008 , the receiver  104  selects a sequence X 1,p+1   T  that maximizes Q(X 1,p+1   T ,X 1,p   T ) and goes to step  1010 . In step  1010 , the receiver  104  compares X 1,p   T  with X 1,p+1   T . If the compare result is within the compare threshold, then the receiver  104  goes to step  1012 ; otherwise, the receiver  104  returns to step  1004  and continues the process with the new sequence X 1,p+1   T . In step  1012 , the receiver  104  outputs X 1,p+1   T , and goes to step  1014  and ends the process. 
         [0025]    The efficiency of the above described iterative technique may be improved if the transmitted sequence is generated by modulators such as a trellis coded modulator (TCM). A TCM may be described as a finite state machine that may be defined by equations 10 and 11 shown below. 
         [0000]        S   t+1   =f   t ( S   t   ,I   t )  (10) 
         [0000]        X   t   =g   t ( S   t   ,I   t )  (11) 
         [0000]    Equation 10 specifies the TCM state transitions while equation 11 specifies the transmitted information sequence based on the state and the input information sequence. For example, after receiving input I t  in state S t , the finite state machine transfers to state S t+1 , based on S t  and I t  as shown in equation 10. The actual output by the transmitter  102  is X t  according to equation 11. Equation 10 may represent a convolutional encoder and equation 11 may represent a modulator. For the above example, the transmitter output information sequence X 1   T  may not be independent even if the input information sequence I 1   T  is independent. 
         [0026]    In equation 15, the log(p ij (Y t ,X t )) term may be analyzed based on the TCM state transitions because the information actually transmitted X is related to the source information I t  by X t =g t (S t , I t ). This relationship between X t  and I t  forces many elements p ij (Y t ,X t ) of P (Y t ,X t ), to zero since the finite state machine (equations 10 and 11) removes many possibilities that otherwise must be considered. Thus, unlike the general case discussed in relation to equations 5-9, evaluation of p ij (Y t ,X t ) may be divided into a portion that is channel related and another portion that is TCM related. The following discussion describes the iterative technique in detail for the TCM example. 
         [0027]    For a TCM system with an independent and identically distributed information sequence, an input-output HMM may be described by equations 12 and 13 below. 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       P 
                        
                       
                         ( 
                         
                           
                             X 
                             t 
                           
                           , 
                           
                             Y 
                             t 
                           
                         
                         ) 
                       
                     
                     = 
                     
                       ⌊ 
                       
                         
                           p 
                           
                             
                               S 
                               t 
                             
                              
                             
                               S 
                               
                                 t 
                                 + 
                                 1 
                               
                             
                           
                         
                          
                         
                           
                             P 
                             c 
                           
                            
                           
                             ( 
                             
                               
                                 X 
                                 t 
                               
                               | 
                               
                                 Y 
                                 t 
                               
                             
                             ) 
                           
                         
                       
                       ⌋ 
                     
                   
                   , 
                   
                     
 
                   
                    
                   where 
                 
               
               
                 
                   ( 
                   12 
                   ) 
                 
               
             
             
               
                 
                   
                     p 
                     
                       
                         S 
                         t 
                       
                        
                       
                         S 
                         
                           t 
                           + 
                           1 
                         
                       
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             Pr 
                              
                             
                               ( 
                               
                                 I 
                                 t 
                               
                               ) 
                             
                           
                         
                         
                           
                             
                               if 
                                
                               
                                   
                               
                                
                               
                                 S 
                                 
                                   t 
                                   + 
                                   1 
                                 
                               
                             
                             = 
                             
                               
                                 f 
                                 t 
                               
                                
                               
                                 ( 
                                 
                                   
                                     S 
                                     t 
                                   
                                   , 
                                   
                                     I 
                                     t 
                                   
                                 
                                 ) 
                               
                             
                           
                         
                       
                       
                         
                           0 
                         
                         
                           otherwise 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   13 
                   ) 
                 
               
             
           
         
       
     
         [0000]    P c (Y t |X t ) is the conditional PDM of receiving Y t  given that X t  has been transmitted for the HMM of a medium (channel) through which the information sequence is transmitted; p s     t     S     t+1    is the probability of the TCM transition from state S t  to state S t+1 , and Pr(I t ) is the probability of an input I t . Thus, equation 2 may be written as 
         [0000]    
       
         
           
             
               
                 
                   p 
                   T 
                 
                  
                 
                   ( 
                   
                     
                       I 
                       1 
                       T 
                     
                     , 
                     
                       Y 
                       1 
                       T 
                     
                   
                   ) 
                 
               
               = 
               
                 
                   π 
                   c 
                 
                  
                 
                   
                     ∏ 
                     
                       i 
                       = 
                       1 
                     
                     T 
                   
                    
                   
                       
                   
                    
                   
                     
                       p 
                       
                         
                           s 
                           t 
                         
                          
                         
                           s 
                           
                             t 
                             + 
                             1 
                           
                         
                       
                     
                      
                     
                       
                         P 
                         c 
                       
                        
                       
                         ( 
                         
                           
                             Y 
                             t 
                           
                           | 
                           
                             X 
                             t 
                           
                         
                         ) 
                       
                     
                      
                     1 
                   
                 
               
             
             , 
           
         
       
     
         [0000]    where π is a vector of the initial probabilities of the channel states, X t =g t (S t ,I t ), and the product is taken along the state trajectory S t+1 =f t (S t ,I t ) for t=1, 2, . . . , T. 
         [0028]    If all elements of the input information sequence are equally probable, then the MAP estimate may be expressed by equation 14 below. 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         I 
                         ^ 
                       
                       1 
                       T 
                     
                     = 
                     
                       arg 
                        
                       
                         
                           max 
                           
                             I 
                             1 
                             T 
                           
                         
                          
                         
                             
                         
                          
                         
                           
                             π 
                             c 
                           
                            
                           
                             
                               ∏ 
                               
                                 t 
                                 = 
                                 1 
                               
                               T 
                             
                              
                             
                                 
                             
                              
                             
                               
                                 
                                   P 
                                   c 
                                 
                                  
                                 
                                   ( 
                                   
                                     
                                       Y 
                                       t 
                                     
                                     | 
                                     
                                       X 
                                       t 
                                     
                                   
                                   ) 
                                 
                               
                                
                               1 
                             
                           
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   14 
                   ) 
                 
               
             
           
         
       
     
         [0000]    The auxiliary function may be expressed by equations 15-17 below corresponding to equations 7-9 above. 
         [0000]    
       
         
           
             
               
                 
                   
                     Q 
                      
                     
                       ( 
                       
                         
                           I 
                           1 
                           T 
                         
                         , 
                         
                           I 
                           
                             1 
                             , 
                             p 
                           
                           T 
                         
                       
                       ) 
                     
                   
                   = 
                   
                     
                       
                         ∑ 
                         
                           t 
                           = 
                           1 
                         
                         T 
                       
                        
                       
                         
                           ∑ 
                           
                             i 
                             = 
                             1 
                           
                           n 
                         
                          
                         
                           
                             ∑ 
                             
                               j 
                               = 
                               1 
                             
                             n 
                           
                            
                           
                             
                               · 
                               
                                 
                                   γ 
                                   
                                     t 
                                     , 
                                     ij 
                                   
                                 
                                  
                                 
                                   ( 
                                   
                                     I 
                                     
                                       1 
                                       , 
                                       p 
                                     
                                     T 
                                   
                                   ) 
                                 
                               
                             
                              
                             
                               log 
                                
                               
                                 ( 
                                 
                                   
                                     p 
                                     ij 
                                   
                                    
                                   
                                     ( 
                                     
                                       
                                         Y 
                                         t 
                                       
                                       | 
                                       
                                         X 
                                         t 
                                       
                                     
                                     ) 
                                   
                                 
                                 ) 
                               
                             
                           
                         
                       
                     
                     + 
                     C 
                   
                 
               
               
                 
                   ( 
                   15 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where X t =g t (S t ,I t ) and 
         [0000]      γ t,ij ( I   1,p   T )=α i ( Y   1   t−1   |T   1,p ) p   c,ij ( Y   t   |X   t,p )β j ( Y   t+1,p   T   |I   t+1,p   T )  (16) 
         [0000]    α i (Y 1   T−1 |I 1,p   t−1 ) and β j (Y t+1,p   T |I t+1,p   T ) are the elements of the forward and backward probability vectors 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       α 
                        
                       
                         ( 
                         
                           
                             Y 
                             1 
                             T 
                           
                           | 
                           
                             I 
                             1 
                             T 
                           
                         
                         ) 
                       
                     
                     = 
                     
                       
                         π 
                         c 
                       
                        
                       
                         
                           ∏ 
                           
                             i 
                             = 
                             1 
                           
                           t 
                         
                          
                         
                             
                         
                          
                         
                           
                             P 
                             c 
                           
                            
                           
                             ( 
                             
                               
                                 Y 
                                 i 
                               
                               | 
                               
                                 X 
                                 i 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                    
                   
                       
                   
                    
                   
                     
 
                   
                    
                   and 
                    
                   
                     
 
                   
                    
                   
                     
                       β 
                        
                       
                         ( 
                         
                           
                             Y 
                             
                               t 
                               + 
                               1 
                             
                             T 
                           
                           | 
                           
                             I 
                             
                               t 
                               + 
                               1 
                             
                             T 
                           
                         
                         ) 
                       
                     
                     = 
                     
                       
                         ∏ 
                         
                           i 
                           = 
                           
                             t 
                             + 
                             1 
                           
                         
                         T 
                       
                        
                       
                         
                           
                             P 
                             c 
                           
                            
                           
                             ( 
                             
                               
                                 Y 
                                 i 
                               
                               | 
                               
                                 X 
                                 i 
                               
                             
                             ) 
                           
                         
                          
                         1 
                       
                     
                   
                 
               
               
                 
                   ( 
                   17 
                   ) 
                 
               
             
           
         
       
     
         [0029]    From equation 15, the Viterbi algorithm may be applied with the branch metric 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       m 
                        
                       
                         ( 
                         
                           I 
                           t 
                         
                         ) 
                       
                     
                     = 
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           1 
                         
                         n 
                       
                        
                       
                         
                           ∑ 
                           
                             j 
                             = 
                             1 
                           
                           n 
                         
                          
                         
                           
                             
                               γ 
                               
                                 t 
                                 , 
                                 ij 
                               
                             
                              
                             
                               ( 
                               
                                 I 
                                 
                                   1 
                                   , 
                                   p 
                                 
                                 T 
                               
                               ) 
                             
                           
                            
                           log 
                            
                           
                               
                           
                            
                           
                             
                               p 
                               
                                 c 
                                 , 
                                 ij 
                               
                             
                              
                             
                               ( 
                               
                                 
                                   Y 
                                   t 
                                 
                                 | 
                                 
                                   X 
                                   t 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   , 
                   
                     t 
                     = 
                     
                       1 
                       , 
                       2 
                        
                       
                         , 
                         
                             
                         
                       
                        
                       … 
                     
                   
                    
                   
                       
                   
                   , 
                   T 
                 
               
               
                 
                   ( 
                   18 
                   ) 
                 
               
             
           
         
       
     
         [0000]    to find a maximum of Q(I 1   T , I 1,p   T ) which can be interpreted as a longest path leading from the initial zero state to one of the states S T  where only the encoder trellis is considered. The Viterbi algorithm may be combined with the backward portion of the forward-backward algorithm as follows. 
         [0030]    1. Select an initial source information sequence I 1,0   T =I 1,0 , I 2,0 , . . . , I T,0    
         [0031]    2. Forward part:
       a. set α(Y 1   0 |I 1   0 )=π, where π is an initial state probability estimate; and   b. for t=1, 2, . . . , T, compute X t,p =g t (S t ,I t,p ),       
 
         [0000]      α( Y   1   t   |T   1,p   t )=α( Y   1   t−1   |I   1,p   t−1 ) P   c ( Y   t   |X   1,p ),           where I 1,p   t  is a prior estimate of I′t.             
         [0035]    3. Backward part:
       a. set β(Y T+1   T |I T+1,p   T )=1 and last state transition lengths L(S T ) to 0 for all the states;   for t=T,T−1, . . . , 1 compute:   b. X t =g t (S t ,I t ),   c. γ t,ij (I 1,p   T )=α i (Y 1   t−1 |I 1,p   t−1 )p c,j (Y t |X t,p )β j (Y t+1   T |I t−1,p   T ),   d.       
 
         [0000]    
       
         
           
             
               L 
                
               
                 ( 
                 
                   S 
                   t 
                 
                 ) 
               
             
             = 
             
               
                 max 
                 
                   I 
                   t 
                 
               
                
               
                 
                   { 
                   
                     
                       L 
                        
                       
                         ⌊ 
                         
                           
                             f 
                             t 
                           
                            
                           
                             ( 
                             
                               
                                 S 
                                 t 
                               
                               , 
                               
                                 I 
                                 t 
                               
                             
                             ) 
                           
                         
                         ⌋ 
                       
                     
                     + 
                     
                       m 
                        
                       
                         ( 
                         
                           I 
                           t 
                         
                         ) 
                       
                     
                   
                   } 
                 
                 . 
               
             
           
         
       
     
         [0000]    This step selects the paths with the largest lengths (the survivors).
       e.       
 
         [0000]    
       
         
           
             
               
                 
                   I 
                   ^ 
                 
                 t 
               
                
               
                 ( 
                 
                   S 
                   t 
                 
                 ) 
               
             
             = 
             
               arg 
                
               
                   
               
                
               
                 
                   max 
                   
                     I 
                     1 
                   
                 
                  
                 
                   
                     { 
                     
                       
                         L 
                          
                         
                           [ 
                           
                             
                               f 
                               t 
                             
                              
                             
                               ( 
                               
                                 
                                   S 
                                   t 
                                 
                                 , 
                                 
                                   I 
                                   t 
                                 
                               
                               ) 
                             
                           
                           ] 
                         
                       
                       + 
                       
                         m 
                          
                         
                           ( 
                           
                             I 
                             t 
                           
                           ) 
                         
                       
                     
                     } 
                   
                   . 
                 
               
             
           
         
       
     
         [0000]    This step estimates I t  corresponding to the state S t  by selecting the I t  of the survivor in step d.
       f. β(Y t   T |I t,p   T )=P c (Y t |X t,p )β(Y t+1   T |X t+1,p   T ).   g. End (of “for” loop).       
 
         [0044]    4. Reestimate the information sequence: 
         [0000]        I   t,p+1   =Î   t ( Ŝ   t+1   =f   t ( Ŝ   t   ,I   t,p+1 ), t=1,2, . . . ,  T where Ŝ   1 =0; and 
         [0045]    5. If T t,p+1 ≠I t,p , go to step  2 ; otherwise decode the information sequence as I t,p+1   T . 
         [0046]      FIGS. 3-6  show an example of the iterative process discussed above where there are four states in the TCM and T=5. The dots represent possible states and the arrows represent a state trajectory that corresponds to a particular information sequence. The iterative process may proceed as follows. First, an initial input information sequence I 1,0   5  is obtained. I 1,0   5  may be the output of an existing decoder or may simply be a guess. 
         [0047]    The Viterbi algorithm together with the backward algorithm may be used to obtain a next estimate of the input information sequence I 1,1   5 . This process begins with the state transitions between t=4 and t=5 by selecting state transitions leading to each of the states s 0 -s 3  at t=4 from states at t=5 that have the largest value of the branch metric L(S 4 )=m(I 5 ) of equation 18 above. Then, the process moves to select state transitions between the states at t=3 and t=4 that have the largest cumulative distance L(S 3 )=L(S 4 )+m(I 4 ). This process continues until t=0 and the sequence of input information I′ corresponding to the path connecting the states from t=0 to t=5 that has the longest path 
         [0000]    
       
         
           
             
               L 
                
               
                 ( 
                 
                   S 
                   0 
                 
                 ) 
               
             
             = 
             
               
                 ∑ 
                 
                   t 
                   = 
                   1 
                 
                 5 
               
                
               
                 m 
                  
                 
                   ( 
                   
                     I 
                     t 
                   
                   ) 
                 
               
             
           
         
       
     
         [0000]    is selected as the next input information sequence I 1,1   5 . 
         [0048]    For the example in  FIG. 3 , state transitions from the states at t=4 to all the states at t=5 are considered. Assuming that the (I t )s are binary, then only two transitions can emanate from each of the states at t=4: one transition for 15=0 and one transition for I 5 =1. Thus,  FIG. 3  shows two arrows terminating on each state at t=4 (arrows are “backwards” because the backward algorithm is used). State transitions  301  and  302  terminate at state s 0 ; state transitions  303  and  304  terminate at state s 1 ; state transitions  305  and  306  terminate at state s 2 ; and state transitions  307  and  308  terminate at state s 3 . 
         [0049]    The branch metric m(I t ) of equation 18 represents a “distance” between the states and is used to select the state transition that corresponds to the longest path for each of the states s 0 -s 3  at t=4: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         
                           m 
                            
                           
                             ( 
                             
                               I 
                               5 
                             
                             ) 
                           
                         
                         = 
                           
                          
                         
                           
                             ∑ 
                             i 
                           
                            
                           
                             
                               ∑ 
                               j 
                             
                              
                             
                               
                                 
                                   γ 
                                   
                                     5 
                                     , 
                                     ij 
                                   
                                 
                                  
                                 
                                   ( 
                                   
                                     X 
                                     
                                       1 
                                       , 
                                       0 
                                     
                                     5 
                                   
                                   ) 
                                 
                               
                                
                               log 
                                
                               
                                   
                               
                                
                               
                                 
                                   p 
                                   ij 
                                 
                                  
                                 
                                   ( 
                                   
                                     
                                       X 
                                       5 
                                     
                                     , 
                                     
                                       Y 
                                       5 
                                     
                                   
                                   ) 
                                 
                               
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           
                             ∑ 
                             i 
                           
                            
                           
                             
                               ∑ 
                               j 
                             
                              
                             
                               
                                 
                                   α 
                                   i 
                                 
                                  
                                 
                                   ( 
                                   
                                     
                                       X 
                                       
                                         1 
                                         , 
                                         0 
                                       
                                       4 
                                     
                                     , 
                                     
                                       Y 
                                       1 
                                       4 
                                     
                                   
                                   ) 
                                 
                               
                                
                               
                                 
                                   p 
                                   ij 
                                 
                                  
                                 
                                   ( 
                                   
                                     
                                       X 
                                       
                                         5 
                                         , 
                                         0 
                                       
                                     
                                     , 
                                     
                                       Y 
                                       5 
                                     
                                   
                                   ) 
                                 
                               
                             
                           
                         
                       
                     
                   
                   
                     
                       
                           
                          
                         
                           
                             
                               
                                 β 
                                 j 
                               
                                
                               
                                 ( 
                                 
                                   
                                     X 
                                     
                                       6 
                                       , 
                                       0 
                                     
                                     5 
                                   
                                   , 
                                   
                                     Y 
                                     6 
                                     5 
                                   
                                 
                                 ) 
                               
                             
                              
                             log 
                              
                             
                                 
                             
                              
                             
                               
                                 p 
                                 ij 
                               
                                
                               
                                 ( 
                                 
                                   
                                     Y 
                                     5 
                                   
                                   | 
                                   
                                     X 
                                     5 
                                   
                                 
                                 ) 
                               
                             
                           
                           , 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   19 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where βj(X 6,0   5 , Y 6   5 )=1, and X 5 =g 5 (S 5 , I 5 ) by definition. There is an I 5  that corresponds to each of the state transitions  301 - 308 . For this example, L(S 4 )=m(I 5 ) corresponding to odd numbered state transitions  301 - 307  are greater than that for even numbered state transitions  302 - 308 . Thus, odd numbered state transitions are “survivors.” Each of them may be part of the state trajectory that has the longest path from t=0 to t=5. This transition (the survivor) is depicted by the solid arrow while the transitions with smaller lengths are depicted by dashed lines. 
         [0050]    The state sequence determination process continues by extending the survivors to t=3 as shown in  FIG. 4  forming state transitions  309 - 316 . The distance between state transitions for each of the states are compared based on L(S 4 )+m(I 4 ), where m(I 4 ) is shown in equation 20 below. 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         
                           m 
                            
                           
                             ( 
                             
                               I 
                               4 
                             
                             ) 
                           
                         
                         = 
                           
                          
                         
                           
                             ∑ 
                             i 
                           
                            
                           
                             
                               ∑ 
                               j 
                             
                              
                             
                               
                                 
                                   γ 
                                   
                                     5 
                                     , 
                                     ij 
                                   
                                 
                                  
                                 
                                   ( 
                                   
                                     X 
                                     
                                       1 
                                       , 
                                       0 
                                     
                                     5 
                                   
                                   ) 
                                 
                               
                                
                               log 
                                
                               
                                   
                               
                                
                               
                                 
                                   p 
                                   ij 
                                 
                                  
                                 
                                   ( 
                                   
                                     
                                       X 
                                       4 
                                     
                                     , 
                                     
                                       Y 
                                       4 
                                     
                                   
                                   ) 
                                 
                               
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           
                             ∑ 
                             i 
                           
                            
                           
                             
                               ∑ 
                               j 
                             
                              
                             
                               
                                 
                                   α 
                                   i 
                                 
                                  
                                 
                                   ( 
                                   
                                     
                                       X 
                                       
                                         1 
                                         , 
                                         0 
                                       
                                       3 
                                     
                                     , 
                                     
                                       Y 
                                       1 
                                       3 
                                     
                                   
                                   ) 
                                 
                               
                                
                               
                                 
                                   p 
                                   ij 
                                 
                                  
                                 
                                   ( 
                                   
                                     
                                       X 
                                       
                                         4 
                                         , 
                                         0 
                                       
                                     
                                     , 
                                     
                                       Y 
                                       4 
                                     
                                   
                                   ) 
                                 
                               
                             
                           
                         
                       
                     
                   
                   
                     
                       
                           
                          
                         
                           
                             
                               β 
                               j 
                             
                              
                             
                               ( 
                               
                                 
                                   X 
                                   
                                     5 
                                     , 
                                     0 
                                   
                                 
                                 , 
                                 
                                   Y 
                                   5 
                                 
                               
                               ) 
                             
                           
                            
                           log 
                            
                           
                               
                           
                            
                           
                             
                               
                                 p 
                                 ij 
                               
                                
                               
                                 ( 
                                 
                                   
                                     Y 
                                     4 
                                   
                                   | 
                                   
                                     X 
                                     4 
                                   
                                 
                                 ) 
                               
                             
                             . 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   20 
                   ) 
                 
               
             
           
         
       
     
         [0000]    For this example, the distances corresponding to the odd numbered state transitions  309 - 315  are longer than distances corresponding to even numbered state transitions  310 - 316 . Thus, the paths corresponding to the odd numbered state transitions are the survivors. As shown in  FIG. 4 , the state transition  301  is not connected to any of the states at t=3 and thus is eliminated even though it was a survivor. The other surviving state transitions may be connected into partial state trajectories. For example, partial state trajectories are formed by odd numbered state transitions  307 - 309 ,  303 - 311 ,  303 - 313  and  305 - 315 . 
         [0051]    The above process continues until t=0 is reached as shown in  FIG. 5  where two surviving state trajectories  320 - 322  are formed by the surviving state trajectories. All the state trajectories terminate at state zero for this example because, usually, encoders start at state zero. As shown in  FIG. 6 , the state trajectory that corresponds to the longest cumulative distance is selected and the input information sequence I 1   5 (via S t+1 =f t (S t ,I t ) that corresponds to the selected trajectory is selected as the next estimated input information sequence Î 1,1   5 . For this example, the state trajectory  320  is selected and the input information sequence I 1   5  corresponding to the state trajectory  320  is selected as Î 1,1   5 . 
         [0052]      FIG. 7  shows an exemplary block diagram of the receiver  104 . The receiver  104  may include a controller  202 , a memory  204 , a forward processor  206 , a backward processor  208 , a maximal length processor  210  and an input/output device  212 . The above components may be coupled together via a signal bus  214 . While the receiver  104  is illustrated using a bus architecture, any architecture may be suitable as is well known to one of ordinary skill in the art. 
         [0053]    All the functions of the forward, backward and maximal length processors  206 ,  208  and  210  may also be performed by the controller  202  which may be either a general purpose or special purpose computer (e.g., DSP).  FIG. 7  shows separate processors for illustration only. The forward, backward maximal length processors  206 ,  208  and  210  may be combined and may be implemented by using ASICs, PLAs, PLDs, etc. as is well known in the art. 
         [0054]    The forward processor  206  generates the forward probability vectors α i (X 1,p   t−1 ,Y 1   t−1 ) herein referred to as α i . For every iteration, when a new X 1,p   T  (or I 1,p   T ) is generated, the forward processor  206  may generate a complete set of α i . 
         [0055]    The backward processor  208  together with the maximal length processor  210  generate a new state sequence by searching for maximal length state transitions based on the branch metric m(I t ). Starting with the final state transition between states corresponding to t=T−1 and t=T, the backward processor generates β j (X t+1,p   T , Y t+1   T ) (hereinafter referred as β j ) as shown in equation 8 for each state transition. 
         [0056]    The maximal length processor  210  generates m(I t ) based on the results of the forward processor  206 , the backward processor  208  and p ij (X t ,Y t ). After generating all the m(I t )s corresponding to each of the possible state transitions, the maximal length processor  210  compares all the L(S t )+m(I t )s and selects the state transition that corresponds to the largest L(S t )+m(I t ), and the I t  (via S t+1 =f t (S t , I t )) that corresponds to the selected state transition is selected as the estimated input information for that t. The above process is performed for each t=1, 2, . . . , T to generate a new estimate I 1,p   T  for each of the iteration p. 
         [0057]    Initially, the controller  202  places an estimate of the PDM P(X,Y) and π in the memory  204  that corresponds to the HMM for the channel  106  and/or the transmitter  102 . The PDM P(X,Y) may be obtained via well known training processes, for example. 
         [0058]    When ready, the controller  202  receives the received input information sequence Y 1   T  and places them in the memory  204  and selects an initial estimate of I 1,0   T  (or X 1,0   T ). The controller  202  coordinates the above-described iterative process until a new estimate I 1,1   T  (or X 1,1   T ) is obtained. Then, the controller  202  compares I 1,0   T  with I 1,1   T  to determine if the compare result is below the compare threshold value (e.g., matching a predetermined number of elements or symbols of the information sequence). The compare threshold may be set to 0, in which case I 1,0   T  must be identical with I 1,1   T . If an acceptable compare result is reached, I 1,1   T  is output as the decoded output. Otherwise, the controller  202  iterates the above-described process again and compares the estimated I 1,p   T  with I 1,p   T  until an acceptable result is reached and I 1,p   T  is output as the decoded output. 
         [0059]      FIG. 8  shows a flowchart of the above-described process. In step  1000 , the controller  202  receives Y 1   T  via the input/output device  212  and places Y 1   T  in the memory  204  and goes to step  1002 . In step  1002 , the controller  202  selects an initial estimate for I 1,0   T  and goes to step  1004 . In step  1004 , the controller  202  determines a new state sequence and a next estimated I 1,1   T  (I 1,p   T , where p=1) (via the forward, backward and maximal length processors  206 ,  208  and  210 ) and goes to step  1006 . In step  1006 , the controller  202  compares I 1,0   T  with I 1,1   T . If the compare result is within the predetermined threshold, then the controller  202  goes to step  1008 ; otherwise, the controller  202  returns to step  1004 . In step  1008 , the controller  202  outputs I 1,p   T , where p is the index of the last iteration and goes to step  1010  and ends the process. 
         [0060]      FIG. 9  shows a flowchart that expands step  1004  in greater detail. In step  2000 , the controller  202  instructs the forward processor  206  to generate α i  as shown in equation 8, and goes to step  2002 . In step  2002 , the controller  202  sets the parameter t=T and goes to step  2004 . In step  2004 , the controller  202  instructs the backward processor  208  to generate β j  and the maximal length processor  210  to determine next set of survivors based on equation 18 and time t+1 survivors and goes to step  2006 . 
         [0061]    In step  2006 , the controller  202  decrements t and goes to step  2008 . In step  2008 , the controller  202  determines whether t is equal to 0. If t is equal to 0, the controller  202  goes to step  2010 ; otherwise, the controller  202  returns to step  2004 . In step  2010 , the controller  202  outputs the new estimated I t   T  and goes to step  2012  and returns to step  1006  of  FIG. 5 . 
         [0062]    A specific example of the iterative process for convolutional encoders is enclosed in the appendix. 
         [0063]    While this invention has been described in conjunction with specific embodiments thereof, it is evident that many alternatives, modifications, and variations will be apparent to those skilled in the art. Accordingly, preferred embodiments of the invention as set forth herein are intended to be illustrative, not limiting. Various changes may be made without departing from the spirit and scope of the invention. 
         [0064]    For example, a channel may be modeled as P c (Y|X)=P c B c (Y|X) where P c  is a channel state transition probability matrix and B c (Y|X) is a diagonal matrix of state output probabilities. For example, based on the Gilbert-Elliott model 
         [0000]    
       
         
           
             
               
                 
                   B 
                   c 
                 
                  
                 
                   ( 
                   
                     X 
                     | 
                     X 
                   
                   ) 
                 
               
               = 
               
                 [ 
                 
                   
                     
                       
                         1 
                         - 
                         
                           b 
                           1 
                         
                       
                     
                     
                       0 
                     
                   
                   
                     
                       0 
                     
                     
                       
                         1 
                         - 
                         
                           b 
                           2 
                         
                       
                     
                   
                 
                 ] 
               
             
              
             
                 
             
           
         
       
       
         
           and 
         
       
       
         
           
             
               
                 
                   B 
                   c 
                 
                  
                 
                   ( 
                   
                     
                       X 
                       _ 
                     
                     | 
                     X 
                   
                   ) 
                 
               
               = 
               
                 [ 
                 
                   
                     
                       
                         b 
                         1 
                       
                     
                     
                       0 
                     
                   
                   
                     
                       0 
                     
                     
                       
                         b 
                         2 
                       
                     
                   
                 
                 ] 
               
             
             , 
           
         
       
     
         [0000]    where  X  is the complement of X. For this case, m(I t ) may be simplified as 
         [0000]    
       
         
           
             
               
                 m 
                  
                 
                   ( 
                   
                     I 
                     t 
                   
                   ) 
                 
               
               = 
               
                 
                   ∑ 
                   
                     i 
                     = 
                     1 
                   
                   
                     n 
                     c 
                   
                 
                  
                 
                   
                     
                       γ 
                       
                         t 
                         , 
                         i 
                       
                     
                      
                     
                       ( 
                       
                         I 
                         
                           1 
                           , 
                           p 
                         
                         T 
                       
                       ) 
                     
                   
                    
                   
                     
                       b 
                       j 
                     
                      
                     
                       ( 
                       
                         
                           Y 
                           t 
                         
                         | 
                         
                           X 
                           t 
                         
                       
                       ) 
                     
                   
                 
               
             
             , 
             
               t 
               = 
               1 
             
             , 
             2 
             , 
             … 
              
             
                 
             
             , 
             T 
             , 
             and 
           
         
       
       
         
           
             γ t,i (I 1,p   T )=α i (Y 1   t |I 1,p   t )β i (Y t+1   T |I t+1,p   T ), where by b j (Y t |X t ) are the elements of B c .