PATENT DOCUMENT

Abstract:
A coding system in which the coding apparatus generates information bits and parity bits and transmits the parity bits and information bits selectively to the decoding apparatus. The decoding apparatus predicts the information bits, stores the predicted information bits, also stores the parity and information bits received from the encoding apparatus, combines the received information bits with the predicted information bits, and uses an error correcting decoder to decode the combined information bits and the stored parity bits. Combining the predicted information bits with received information bits improves decoding accuracy and enables the decoding apparatus to conserve computational resources.

Full Description:
BACKGROUND OF THE INVENTION 
       [0001]    1. Field of the Invention 
         [0002]    The present invention relates to an encoder, a decoder, and a coding system, and is particularly applicable to the Slepian-Wolf coding system used in, for example, distributed video coding. 
         [0003]    2. Description of the Related Art 
         [0004]    Distributed video coding (DVC) is a new coding method that has grown out of coding theoretical research by Slepian and Wolf and further work by Wyner, Ziv, and others. In one DVC method, the encoder carries out only intraframe coding, while the decoder carries out both intraframe and interframe decoding. Distributed video coding has been attracting considerable attention because it can greatly reduce the computational load on the encoder. 
         [0005]    An example of distributed coding is outlined in  FIG. 1 , which is taken from Aaron et al., ‘Transform-Domain Wyner-Ziv Codec for Video’,  Proc. SPIE Visual Communications and Image Processing,  San Jose, Calif., 2004. In the encoder, a video image sequence is divided into key frames, to which conventional intraframe coding and decoding are applied, and so-called Wyner-Ziv frames, to which Slepian-Wolf coding and decoding processes are applied. In the encoding process, a discrete cosine transform (DCT) is used to transform each Wyner-Ziv frame to the coefficient domain, the coefficients are grouped into bands, the coefficients in the k-th band are quantized by a 2 M     k   -level quantizer, the quantized coefficients (q k ) are expressed in fixed numbers of bits, and the bit planes are extracted and supplied to a Slepian-Wolf encoder that that produces information bits and error-correcting bits, called parity bits. The parity bits are stored in a buffer for transmission to the decoder. The information bits are discarded (as implied but not explicitly shown by Aaron et al.). 
         [0006]    To decode a Wyner-Ziv frame, the decoder generates a predicted image by interpolation or extrapolation from one or more key frames, applies a DCT to convert the predicted image to the coefficient domain, groups the coefficients into bands, and inputs the coefficients in each band as side information to a Slepian-Wolf decoder (a type of turbo decoder) The Slepian-Wolf decoder requests the parity bits it needs to detect and correct errors in the side information. If necessary, further parity bits can be requested and the turbo decoding process can be repeated until a satisfactorily consistent result is obtained. 
         [0007]    Finally, the decoded values and the side information are both used to reconstruct the coefficients of the Wyner-Ziv frame, and an inverse discrete cosine transform (IDCT) is carried out to recover the image. 
         [0008]      FIG. 2  further illustrates the processes from Slepian-Wolf coding to Slepian-Wolf decoding. The systematic encoder  101  in the encoding apparatus  100 A is a type of Slepian-Wolf turbo encoder that generates information bits and parity bits separately. The information bits are discarded; the parity bits are stored in a parity bit buffer  102 . Some of the parity bits are sent immediately to a parity bit transmitter  203  and transmitted to the decoding apparatus  100 B; the other parity bits are held until requested by the decoding apparatus  100 B. 
         [0009]    In the decoding apparatus  100 B, the transmitted parity bits are received by a parity bit receiver  209  and placed in a parity bit buffer  108 , from which they are supplied to an error correcting decoder  107 . An information bit predictor  112  supplies predicted information bits to the error correcting decoder  107 . The error correcting decoder  107  uses the parity bits to carry out an error-correcting decoding process. If this does not produce a satisfactory decoded result, a transmission request signal controller  213  generates a transmission request signal, which is transmitted by a transmission request signal transmitter  214  to the encoding apparatus  100 A as a request for more parity bits. The request is received by a transmission request signal receiver  206  in the encoding apparatus  100 A and passed to a parity bit transmission controller  205 . Operating according to a predetermined table, the parity bit transmission controller  205  controls the parity bit buffer  102  and parity bit transmitter  203  so as to transfer additional parity bits from the parity bit buffer  102  to the parity bit transmitter  203  and transmit them to the decoding apparatus  100 B. This process is iterated until a satisfactory decoded result is obtained. 
         [0010]    The error correcting decoder  107  may use the maximum a-posteriori probability (MAP) decoding algorithm described by Sklar in  Digital Communication: Fundamentals and Applications,  Prentice-Hall, 2001. This algorithm, which is used in turbo coding and other coding methods, is a high-performance error-correcting decoding method in which the coder uses the parity bits and predicted information bits, which are predicted at the decoder, to calculate the probability that each information bit is 0 or 1. 
         [0011]    The conventional coding and decoding operations are illustrated in  FIGS. 3A ,  3 B, and  3 C. The systematic encoder  101 , represented schematically in  FIG. 3A , is a convolutional encoder with a constraint length of three and a coding rate of one-half. At times n−1, n, and n+1, the encoder receives data bits d {1, 0, 0}, outputs them as information bits u {1, 0, 0}, and generates parity bits v {1, 0, 1}. The parity bit v (0) for time n, for example, is transmitted to the decoding apparatus  100 B. The parity bits v (1) for times n−1 and n+1 are not transmitted (unless requested later), and the information bits u are never transmitted. 
         [0012]    In the decoder, bit values are represented algebraically: a 0 parity bit is represented as −1, for example, and a 1 parity bit as +1. Predicted values x of information bits are represented by positive and negative values indicating likelihoods that the true value of the bit is 1 or 0. In  FIG. 3B , the predicted values at time n are {1.5, 0.0, −0.6} and the received parity bit values y are {0.0, −1.0, 0.0}, where 0.0 represents a non-transmitted parity bit. The a-priori probabilities π i=0 k are 0.5; a bit is equally likely to be 1 or 0 (π 1 =π 0 ). 
         [0013]    At an arbitrary time k, the encoder may be in one of four states (a, b, c, d) representing the two most recent input data bits. Branch metrics can be calculated for all possible state transitions from time k to time k+1. For example, a branch metric δ i=0, m=1 k for the transition from state a (m=a) caused by input of a data bit with value 0 (i=0) at time k at which the predicted value of the information bit x k , if consistent with the parity bit output at time k, is A k π i=0   k exp(−x k /σ 2 ), where A k  and σ 2  are parameters. For the transition from state a at time n (k=n), when x k =0.0, to state a at time n+1, which is consistent with the output of the known parity bit value of 0 at time n, if the parameters A k  and σ 2  are both equal to unity, the branch metric is calculated as follows. 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         
                           δ 
                           k 
                           
                             
                               i 
                               = 
                               0 
                             
                             , 
                             
                               m 
                               = 
                               a 
                             
                           
                         
                         = 
                         
                           
                             A 
                             k 
                           
                            
                           
                             π 
                             k 
                             
                               i 
                               = 
                               0 
                             
                           
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 
                                   - 
                                   
                                     x 
                                     k 
                                   
                                 
                                 / 
                                 
                                   σ 
                                   2 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                         
                           0.5 
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 - 
                                 
                                   x 
                                   k 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                         
                           0.5 
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 - 
                                 
                                   ( 
                                   0.0 
                                   ) 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                         0.5 
                       
                     
                   
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
         [0014]    Branch metrics for the transitions from the other states b (10), c (01), and d (11) that produce 0 parity bits at time n are calculated similarly as shown by equations (2) to (4). 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         
                           δ 
                           k 
                           
                             
                               i 
                               = 
                               0 
                             
                             , 
                             
                               m 
                               = 
                               b 
                             
                           
                         
                         = 
                         
                           
                             A 
                             k 
                           
                            
                           
                             π 
                             k 
                             
                               i 
                               = 
                               0 
                             
                           
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 
                                   - 
                                   
                                     x 
                                     k 
                                   
                                 
                                 / 
                                 
                                   σ 
                                   2 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                         
                           0.5 
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 - 
                                 
                                   x 
                                   k 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                         
                           0.5 
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 - 
                                 
                                   ( 
                                   0.0 
                                   ) 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                         0.5 
                       
                     
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       
                         
                           δ 
                           k 
                           
                             
                               i 
                               = 
                               1 
                             
                             , 
                             
                               m 
                               = 
                               c 
                             
                           
                         
                         = 
                         
                           
                             A 
                             k 
                           
                            
                           
                             π 
                             k 
                             
                               i 
                               = 
                               0 
                             
                           
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 
                                   - 
                                   
                                     x 
                                     k 
                                   
                                 
                                 / 
                                 
                                   σ 
                                   2 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                         
                           0.5 
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 - 
                                 
                                   x 
                                   k 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                         
                           0.5 
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 - 
                                 
                                   ( 
                                   0.0 
                                   ) 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                         0.5 
                       
                     
                   
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       
                         
                           δ 
                           k 
                           
                             
                               i 
                               = 
                               1 
                             
                             , 
                             
                               m 
                               = 
                               d 
                             
                           
                         
                         = 
                         
                           
                             A 
                             k 
                           
                            
                           
                             π 
                             k 
                             
                               i 
                               = 
                               0 
                             
                           
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 
                                   - 
                                   
                                     x 
                                     k 
                                   
                                 
                                 / 
                                 
                                   σ 
                                   2 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                         
                           0.5 
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 - 
                                 
                                   x 
                                   k 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                         
                           0.5 
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 - 
                                 
                                   ( 
                                   0.0 
                                   ) 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                         0.5 
                       
                     
                   
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
         [0015]    If the parity bits are assumed to be received without corruption, there is zero likelihood that the parity bit value is 1, so the remaining branch metrics are zero as indicated in equations (5) to (8). 
         [0000]      δ i=1, m=1   k =0   (5) 
         [0000]      δ i=1, m=b   k =0   (6) 
         [0000]      δ i=0, m=c   k =0   (7) 
         [0000]      δ i=0, m=d   k =0   (8) 
         [0016]    Given a guaranteed value of 0 for the parity bit input at the transition from time n to time n+1, in state a an information bit value of 1 cannot be output, as can be seen from the trellis diagram in  FIG. 3C . 
         [0017]    For the transition from time n−1 to time n, branch metrics are calculated as follows. If the state at time n−1 is a and if the encoding apparatus does not transmit a parity bit, the calculation can be divided into two cases, depending on whether the parity bit value is 0 or 1, and can be expressed by equations (9) and (10), in which 
         [0000]      u i=0   k=n−1 =1 
         [0000]      and 
         [0000]      u i=1   k=n−1 =−1. 
         [0000]    Equation (9) gives the branch metric expressed by equation (11), and equation (10) gives the branch metric expressed by equation (12). 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         
                           δ 
                           
                             k 
                             = 
                             
                               n 
                               - 
                               1 
                             
                           
                           
                             
                               i 
                               = 
                               0 
                             
                             , 
                             m 
                           
                         
                         = 
                           
                          
                         
                           
                             A 
                             
                               k 
                               = 
                               
                                 n 
                                 - 
                                 1 
                               
                             
                           
                            
                           
                             π 
                             
                               k 
                               = 
                               
                                 n 
                                 - 
                                 1 
                               
                             
                             
                               i 
                               = 
                               0 
                             
                           
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 
                                   x 
                                   
                                     k 
                                     = 
                                     
                                       n 
                                       - 
                                       1 
                                     
                                   
                                 
                                  
                                 
                                   
                                     u 
                                     
                                       k 
                                       = 
                                       
                                         n 
                                         - 
                                         1 
                                       
                                     
                                     
                                       i 
                                       = 
                                       0 
                                     
                                   
                                   / 
                                   
                                     σ 
                                     2 
                                   
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           
                             A 
                             
                               k 
                               = 
                               
                                 n 
                                 - 
                                 1 
                               
                             
                           
                            
                           
                             π 
                             
                               k 
                               = 
                               
                                 n 
                                 - 
                                 1 
                               
                             
                             
                               i 
                               = 
                               0 
                             
                           
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 
                                   - 
                                   
                                     x 
                                     
                                       k 
                                       = 
                                       
                                         n 
                                         - 
                                         1 
                                       
                                     
                                   
                                 
                                 / 
                                 
                                   σ 
                                   2 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   9 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       
                         
                           δ 
                           
                             k 
                             = 
                             
                               n 
                               - 
                               1 
                             
                           
                           
                             
                               i 
                               = 
                               1 
                             
                             , 
                             m 
                           
                         
                         = 
                           
                          
                         
                           
                             A 
                             
                               k 
                               = 
                               
                                 n 
                                 - 
                                 1 
                               
                             
                           
                            
                           
                             π 
                             
                               k 
                               = 
                               
                                 n 
                                 - 
                                 1 
                               
                             
                             
                               i 
                               = 
                               1 
                             
                           
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 
                                   x 
                                   
                                     k 
                                     = 
                                     
                                       n 
                                       - 
                                       1 
                                     
                                   
                                 
                                  
                                 
                                   
                                     u 
                                     
                                       k 
                                       = 
                                       
                                         n 
                                         - 
                                         1 
                                       
                                     
                                     
                                       i 
                                       = 
                                       1 
                                     
                                   
                                   / 
                                   
                                     σ 
                                     2 
                                   
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           
                             A 
                             
                               k 
                               = 
                               
                                 n 
                                 - 
                                 1 
                               
                             
                           
                            
                           
                             π 
                             
                               k 
                               = 
                               
                                 n 
                                 - 
                                 1 
                               
                             
                             
                               i 
                               = 
                               1 
                             
                           
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 
                                   x 
                                   
                                     k 
                                     = 
                                     
                                       n 
                                       - 
                                       1 
                                     
                                   
                                 
                                 / 
                                 
                                   σ 
                                   2 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   10 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       
                         
                           δ 
                           
                             k 
                             = 
                             
                               n 
                               - 
                               1 
                             
                           
                           
                             
                               i 
                               = 
                               1 
                             
                             , 
                             m 
                           
                         
                         = 
                           
                          
                         
                           
                             A 
                             
                               k 
                               = 
                               
                                 n 
                                 - 
                                 1 
                               
                             
                           
                            
                           
                             π 
                             
                               k 
                               = 
                               
                                 n 
                                 - 
                                 1 
                               
                             
                             
                               i 
                               = 
                               0 
                             
                           
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 
                                   - 
                                   
                                     x 
                                     
                                       k 
                                       = 
                                       
                                         n 
                                         - 
                                         1 
                                       
                                     
                                   
                                 
                                 / 
                                 
                                   σ 
                                   2 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           0.5 
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 - 
                                 
                                   x 
                                   
                                     k 
                                     = 
                                     
                                       n 
                                       - 
                                       1 
                                     
                                   
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           0.5 
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 - 
                                 
                                   ( 
                                   1.5 
                                   ) 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         0.11 
                       
                     
                   
                 
               
               
                 
                   ( 
                   11 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       
                         
                           δ 
                           
                             k 
                             = 
                             
                               n 
                               - 
                               1 
                             
                           
                           
                             
                               i 
                               = 
                               1 
                             
                             , 
                             m 
                           
                         
                         = 
                           
                          
                         
                           
                             A 
                             
                               k 
                               = 
                               
                                 n 
                                 - 
                                 1 
                               
                             
                           
                            
                           
                             π 
                             
                               k 
                               = 
                               
                                 n 
                                 - 
                                 1 
                               
                             
                             
                               i 
                               = 
                               1 
                             
                           
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 
                                   x 
                                   
                                     k 
                                     = 
                                     
                                       n 
                                       - 
                                       1 
                                     
                                   
                                 
                                 / 
                                 
                                   σ 
                                   2 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           0.5 
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 x 
                                 
                                   k 
                                   = 
                                   
                                     n 
                                     - 
                                     1 
                                   
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           0.5 
                            
                           
                             exp 
                              
                             
                               ( 
                               1.5 
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         2.24 
                       
                     
                   
                 
               
               
                 
                   ( 
                   12 
                   ) 
                 
               
             
           
         
       
     
         [0018]    Branch metric calculations for the transition from time n+1 to time n+2 are the same as for the transition from time n to time n+1. The results are shown in  FIG. 3C . The method of calculating decoded bit values will be described with further reference to  FIG. 3C . 
         [0019]    A forward state metric α and backward state metric β for each state at each time can be calculated by multiplying the branch metrics of the paths converging on the state by the state metrics of the states from which those paths originate and adding the results. Given the state metrics at time n shown in  FIG. 3C , for example, the forward state metric α for state a at time n+1 is calculated as in equation (13). The forward state metrics a for the other states are calculated similarly. 
         [0000]      α=0.14×0.50+0.56×0.0=0.07   (13) 
         [0020]    The backward state metrics β are calculated in the same way as the forward state metrics α, except for the direction of calculation (right to left in  FIG. 3C , instead of left to right). 
         [0021]    The process for calculating decoded values will now be described. Specifically, the process of decoding the information bit for the transition from time n−1 to time n will be described. If an information bit value of 0 is assumed to have been input for the transition from time n−1 to time n, a value is calculated as expressed by equation (14). If an information bit value of 1 is assumed to have been input for the transition from time n−1 to time n, a value is calculated as expressed by equation (15). Based on these calculated values, the log likelihood of the bit value obtained by equation (16) is 1.31. As this value is positive, a decoded information bit value of 1 is obtained; the bit is correctly decoded. 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         α 
                         
                           k 
                           = 
                           
                             n 
                             - 
                             1 
                           
                         
                         
                           m 
                           = 
                           a 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           
                             n 
                             - 
                             1 
                           
                         
                         
                           
                             i 
                             = 
                             0 
                           
                           , 
                           
                             m 
                             = 
                             a 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           n 
                         
                         
                           m 
                           = 
                           a 
                         
                       
                     
                     + 
                     
                       
                         α 
                         
                           k 
                           = 
                           
                             n 
                             - 
                             1 
                           
                         
                         
                           m 
                           = 
                           b 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           
                             n 
                             - 
                             1 
                           
                         
                         
                           
                             i 
                             = 
                             0 
                           
                           , 
                           
                             m 
                             = 
                             b 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           n 
                         
                         
                           m 
                           = 
                           c 
                         
                       
                     
                     + 
                     
                       
                         α 
                         
                           k 
                           = 
                           
                             n 
                             - 
                             1 
                           
                         
                         
                           m 
                           = 
                           c 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           
                             n 
                             - 
                             1 
                           
                         
                         
                           
                             i 
                             = 
                             0 
                           
                           , 
                           
                             m 
                             = 
                             c 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           n 
                         
                         
                           m 
                           = 
                           a 
                         
                       
                     
                     + 
                     
                       
                         α 
                         
                           k 
                           = 
                           
                             n 
                             - 
                             1 
                           
                         
                         
                           m 
                           = 
                           d 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           
                             n 
                             - 
                             1 
                           
                         
                         
                           
                             i 
                             = 
                             0 
                           
                           , 
                           
                             m 
                             = 
                             d 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           n 
                         
                         
                           m 
                           = 
                           c 
                         
                       
                     
                   
                   = 
                   
                     
                       
                         0.01 
                         × 
                         0.11 
                         × 
                         2.46 
                       
                       + 
                       
                         0.05 
                         × 
                         0.11 
                         × 
                         0.56 
                       
                       + 
                       
                         1.25 
                         × 
                         0.11 
                         × 
                         2.46 
                       
                       + 
                       
                         5.0 
                         × 
                         0.11 
                         × 
                         0.50 
                       
                     
                     = 
                     0.620630285 
                   
                 
               
               
                 
                   ( 
                   14 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       
                         α 
                         
                           k 
                           = 
                           
                             n 
                             - 
                             1 
                           
                         
                         
                           m 
                           = 
                           a 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           
                             n 
                             - 
                             1 
                           
                         
                         
                           
                             i 
                             = 
                             1 
                           
                           , 
                           
                             m 
                             = 
                             a 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           n 
                         
                         
                           m 
                           = 
                           b 
                         
                       
                     
                     + 
                     
                       
                         α 
                         
                           k 
                           = 
                           
                             n 
                             - 
                             1 
                           
                         
                         
                           m 
                           = 
                           b 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           
                             n 
                             - 
                             1 
                           
                         
                         
                           
                             i 
                             = 
                             1 
                           
                           , 
                           
                             m 
                             = 
                             b 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           n 
                         
                         
                           m 
                           = 
                           d 
                         
                       
                     
                     + 
                     
                       
                         α 
                         
                           k 
                           = 
                           
                             n 
                             - 
                             1 
                           
                         
                         
                           m 
                           = 
                           c 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           
                             n 
                             - 
                             1 
                           
                         
                         
                           
                             i 
                             = 
                             1 
                           
                           , 
                           
                             m 
                             = 
                             c 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           n 
                         
                         
                           m 
                           = 
                           b 
                         
                       
                     
                     + 
                     
                       
                         α 
                         
                           k 
                           = 
                           
                             n 
                             - 
                             1 
                           
                         
                         
                           m 
                           = 
                           d 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           
                             n 
                             - 
                             1 
                           
                         
                         
                           
                             i 
                             = 
                             1 
                           
                           , 
                           
                             m 
                             = 
                             d 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           n 
                         
                         
                           m 
                           = 
                           d 
                         
                       
                     
                   
                   = 
                   
                     
                       
                         5.77 
                         × 
                         2.24 
                         × 
                         2.46 
                       
                       + 
                       
                         0.05 
                         × 
                         2.24 
                         × 
                         0.50 
                       
                       + 
                       
                         1.25 
                         × 
                         2.24 
                         × 
                         2.46 
                       
                       + 
                       
                         5.0 
                         × 
                         2.24 
                         × 
                         0.50 
                       
                     
                     = 
                     12.63828944 
                   
                 
               
               
                 
                   ( 
                   15 
                   ) 
                 
               
             
             
               
                 
                   
                       
                   
                    
                   
                     
                       log 
                        
                       
                           
                       
                        
                       
                         ( 
                         
                           12.63829 
                           / 
                           0.620630285 
                         
                          
                         
                             
                         
                         ) 
                       
                     
                     = 
                     1.31 
                   
                 
               
               
                 
                   ( 
                   16 
                   ) 
                 
               
             
           
         
       
     
         [0022]    The method of decoding an information bit for the transition from time n to time n+1 will now be described. If an information bit value of 0 is assumed to have been input for the transition from time n to time n+1, a value is calculated as expressed by equation (17). If an information bit value of 1 is assumed to have been input for the transition from time n to time n+1, a value is calculated as expressed by equation (18). Based on these calculated values, the log likelihood of the bit value obtained by equation (19) is −0.08. As this value is negative, a decoded information bit value of 0 is obtained; this bit is also decoded correctly. 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         α 
                         
                           k 
                           = 
                           n 
                         
                         
                           m 
                           = 
                           a 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           n 
                         
                         
                           
                             i 
                             = 
                             0 
                           
                           , 
                           
                             m 
                             = 
                             a 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           m 
                           = 
                           a 
                         
                       
                     
                     + 
                     
                       
                         α 
                         
                           k 
                           = 
                           n 
                         
                         
                           m 
                           = 
                           b 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           n 
                         
                         
                           
                             i 
                             = 
                             0 
                           
                           , 
                           
                             m 
                             = 
                             b 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           m 
                           = 
                           c 
                         
                       
                     
                     + 
                     
                       
                         α 
                         
                           k 
                           = 
                           n 
                         
                         
                           m 
                           = 
                           c 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           n 
                         
                         
                           
                             i 
                             = 
                             0 
                           
                           , 
                           
                             m 
                             = 
                             c 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           m 
                           = 
                           a 
                         
                       
                     
                     + 
                     
                       
                         α 
                         
                           k 
                           = 
                           n 
                         
                         
                           m 
                           = 
                           d 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           n 
                         
                         
                           
                             i 
                             = 
                             0 
                           
                           , 
                           
                             m 
                             = 
                             d 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           m 
                           = 
                           c 
                         
                       
                     
                   
                   = 
                   
                     
                       
                         0.14 
                         × 
                         0.50 
                         × 
                         4.91 
                       
                       + 
                       
                         2.82 
                         × 
                         0.50 
                         × 
                         4.91 
                       
                       + 
                       
                         0.56 
                         × 
                         0.0 
                         × 
                         4.91 
                       
                       + 
                       
                         11.31 
                         × 
                         0.0 
                         × 
                         4.91 
                       
                     
                     = 
                     7.27473285 
                   
                 
               
               
                 
                   ( 
                   17 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       
                         α 
                         
                           k 
                           = 
                           n 
                         
                         
                           m 
                           = 
                           a 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           n 
                         
                         
                           
                             i 
                             = 
                             1 
                           
                           , 
                           
                             m 
                             = 
                             a 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           m 
                           = 
                           b 
                         
                       
                     
                     + 
                     
                       
                         α 
                         
                           k 
                           = 
                           n 
                         
                         
                           m 
                           = 
                           b 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           n 
                         
                         
                           
                             i 
                             = 
                             1 
                           
                           , 
                           
                             m 
                             = 
                             b 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           m 
                           = 
                           d 
                         
                       
                     
                     + 
                     
                       
                         α 
                         
                           k 
                           = 
                           n 
                         
                         
                           m 
                           = 
                           c 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           n 
                         
                         
                           
                             i 
                             = 
                             1 
                           
                           , 
                           
                             m 
                             = 
                             c 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           m 
                           = 
                           b 
                         
                       
                     
                     + 
                     
                       
                         α 
                         
                           k 
                           = 
                           n 
                         
                         
                           m 
                           = 
                           d 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           n 
                         
                         
                           
                             i 
                             = 
                             1 
                           
                           , 
                           
                             m 
                             = 
                             d 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           m 
                           = 
                           d 
                         
                       
                     
                   
                   = 
                   
                     
                       
                         0.14 
                         × 
                         0.0 
                         × 
                         1.01 
                       
                       + 
                       
                         2.82 
                         × 
                         0.0 
                         × 
                         1.01 
                       
                       + 
                       
                         0.56 
                         × 
                         0.50 
                         × 
                         1.01 
                       
                       + 
                       
                         11.31 
                         × 
                         0.50 
                         × 
                         1.01 
                       
                     
                     = 
                     5.984186875 
                   
                 
               
               
                 
                   ( 
                   18 
                   ) 
                 
               
             
             
               
                 
                   
                       
                   
                    
                   
                     
                       log 
                        
                       
                           
                       
                        
                       
                         ( 
                         
                           5.984187 
                           / 
                           7.27473285 
                         
                          
                         
                             
                         
                         ) 
                       
                     
                     = 
                     
                       - 
                       0.08 
                     
                   
                 
               
               
                 
                   ( 
                   19 
                   ) 
                 
               
             
           
         
       
     
         [0023]    The method of decoding an information bit for the transition from time n+1 to time n+2 will also be described. If an information bit value of 0 is assumed to have been input for the transition from time n+1 to time n+2, a value is calculated as expressed by equation (20). If an information bit value of 1 is assumed to have been input for the transition from time n+1 to time n+2, a value is calculated as expressed by equation (21). Based on these calculated values, the log likelihood of the bit value obtained by equation (22) is −0.36. As this value is negative, a decoded information bit value of 0 is obtained, which is again the correctly decoded value of the bit. 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         α 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           m 
                           = 
                           a 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           
                             i 
                             = 
                             0 
                           
                           , 
                           
                             m 
                             = 
                             a 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             2 
                           
                         
                         
                           m 
                           = 
                           a 
                         
                       
                     
                     + 
                     
                       
                         α 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           m 
                           = 
                           b 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           
                             i 
                             = 
                             0 
                           
                           , 
                           
                             m 
                             = 
                             b 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             2 
                           
                         
                         
                           m 
                           = 
                           c 
                         
                       
                     
                     + 
                     
                       
                         α 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           m 
                           = 
                           c 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           
                             i 
                             = 
                             0 
                           
                           , 
                           
                             m 
                             = 
                             c 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             2 
                           
                         
                         
                           m 
                           = 
                           a 
                         
                       
                     
                     + 
                     
                       
                         α 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           m 
                           = 
                           d 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           
                             i 
                             = 
                             0 
                           
                           , 
                           
                             m 
                             = 
                             d 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             2 
                           
                         
                         
                           m 
                           = 
                           c 
                         
                       
                     
                   
                   = 
                   
                     
                       
                         0.07 
                         × 
                         0.91 
                         × 
                         3.75 
                       
                       + 
                       
                         0.28 
                         × 
                         0.91 
                         × 
                         0.77 
                       
                       + 
                       
                         1.41 
                         × 
                         0.91 
                         × 
                         3.75 
                       
                       + 
                       
                         5.66 
                         × 
                         0.91 
                         × 
                         0.77 
                       
                     
                     = 
                     9.209984875 
                   
                 
               
               
                 
                   ( 
                   20 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       
                         α 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           m 
                           = 
                           a 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           
                             i 
                             = 
                             1 
                           
                           , 
                           
                             m 
                             = 
                             a 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             2 
                           
                         
                         
                           m 
                           = 
                           b 
                         
                       
                     
                     + 
                     
                       
                         α 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           m 
                           = 
                           b 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           
                             i 
                             = 
                             1 
                           
                           , 
                           
                             m 
                             = 
                             b 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             2 
                           
                         
                         
                           m 
                           = 
                           d 
                         
                       
                     
                     + 
                     
                       
                         α 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           m 
                           = 
                           c 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           
                             i 
                             = 
                             1 
                           
                           , 
                           
                             m 
                             = 
                             c 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             2 
                           
                         
                         
                           m 
                           = 
                           b 
                         
                       
                     
                     + 
                     
                       
                         α 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           m 
                           = 
                           d 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           
                             i 
                             = 
                             1 
                           
                           , 
                           
                             m 
                             = 
                             d 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             2 
                           
                         
                         
                           m 
                           = 
                           d 
                         
                       
                     
                   
                   = 
                   
                     
                       
                         0.07 
                         × 
                         0.27 
                         × 
                         5.56 
                       
                       + 
                       
                         0.28 
                         × 
                         0.27 
                         × 
                         1.60 
                       
                       + 
                       
                         1.41 
                         × 
                         0.27 
                         × 
                         1.14 
                       
                       + 
                       
                         5.66 
                         × 
                         0.27 
                         × 
                         1.14 
                       
                     
                     = 
                     4.04893485 
                   
                 
               
               
                 
                   ( 
                   21 
                   ) 
                 
               
             
             
               
                 
                   
                       
                   
                    
                   
                     
                       log 
                        
                       
                           
                       
                        
                       
                         ( 
                         
                           4.048935 
                           / 
                           9.209984875 
                         
                          
                         
                             
                         
                         ) 
                       
                     
                     = 
                     
                       - 
                       0.36 
                     
                   
                 
               
               
                 
                   ( 
                   22 
                   ) 
                 
               
             
           
         
       
     
         [0024]      FIG. 4  illustrates the result of removing paths with branch metric values of zero from the trellis diagram in  FIG. 3C . If a single parity bit can be received correctly, the computations for four paths can be eliminated, as shown in the figure. 
         [0025]    The MAP algorithm is known to yield extremely good error-correcting results, but as these examples show, it requires extensive computation. 
         [0026]    The algorithm allows high-speed processing of a relatively small amount of information, such as sound information, but high-speed processing of larger amounts of information, such as video image information, is difficult. A high-performance computing device (a high-performance microprocessor or central processing unit, for example) is required and much power is consumed. 
         [0027]    The MAP algorithm also requires considerable memory space for storing computation results. This requirement, like the requirement for computing power, increases with the amount of information to be processed, so that more memory space is required for video and other massive types of information than for sound information. This requirement increases the size of the decoding apparatus. 
         [0028]    There is a need for an encoder, a decoder, and a coding system that can reduce the necessary amounts of computation and memory in the decoder. 
       SUMMARY OF THE INVENTION 
       [0029]    The invention provides an encoding apparatus having a systematic encoder that generates information bits representing data input to the encoder, and parity bits providing redundancy for error correction. The encoding apparatus also has an information bit storage unit for storing the generated information bits, a parity bit storage unit for storing the generated parity bits, a bit transmission controller for controlling the output of the bits stored in the information bit storage unit and the parity bit storage unit, and a bit transmitter for selectively transmitting both information bits and parity bits output from the storage units under control of the bit transmission controller. 
         [0030]    The invention also provides a decoding apparatus having a bit receiver for receiving the parity bits and information bits transmitted from the encoding apparatus, an information bit storage unit for storing the received information bits, a parity bit storage unit for storing the received parity bits, an information bit predictor for predicting the information bits, an input information generator for generating input information bits by combining the predicted information bits and the received information bits, and an error correcting decoder for decoding the input information bits and the stored parity bits. 
         [0031]    The invention further provides a coding system including the above encoding apparatus and the above decoding apparatus. The coding system may also include an error-free channel on which the information bits and parity bits are transmitted from the encoding apparatus and the decoding apparatus. Alternatively, the bit transmitter may encode the transmitted bits using an error-correcting code that enables transmission errors occurring in the channel to be corrected by the bit receiver. 
         [0032]    The decoding apparatus may also have a transmission request signal transmitter for transmitting transmission request signals to the encoding apparatus, and a transmission request control unit for controlling the transmission of request signals according to status information received from the error correcting decoder. The transmission request signals may request further information bits or further parity bits, or both. The transmission request signals may also specify whether consecutive or non-consecutive information bits are to be transmitted. 
         [0033]    The encoding apparatus, decoding apparatus, and encoding system provided by the present invention can reduce the computational load and memory usage in the decoding apparatus. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0034]    In the attached drawings: 
           [0035]      FIG. 1  is an explanatory diagram illustrating conventional distributed video coding; 
           [0036]      FIG. 2  is a block diagram illustrating apparatus for conventional Slepian-Wolf coding and decoding; 
           [0037]      FIGS. 3A ,  3 B, and  3 C illustrate the operation of the error correcting decoder in  FIG. 2 ; 
           [0038]      FIG. 4  illustrates the result of removing paths with branch metric values of zero from the trellis diagram in  FIG. 3C ; 
           [0039]      FIG. 5  is a block diagram showing the structure of a coding system according to a first embodiment of the invention; 
           [0040]      FIG. 6  is a flowchart illustrating the operation of the coding system in the first embodiment; 
           [0041]      FIGS. 7A ,  7 B, and  7 C illustrate the operation of the error correcting decoder in the first embodiment; 
           [0042]      FIG. 8  illustrates the result of removing paths with branch metric values of zero from the trellis diagram in  FIG. 7C ; 
           [0043]      FIG. 9  is a block diagram showing the structure of a coding system according to a second embodiment of the invention; 
           [0044]      FIG. 10  is a flowchart illustrating the operation of the coding system in the second embodiment; 
           [0045]      FIGS. 11A ,  11 B, and  11 C illustrate the operation of the error correcting decoder in the second embodiment when the computational load is reduced; 
           [0046]      FIG. 12  illustrates the result of removing paths with branch metric values of zero from the trellis diagram in  FIG. 11C ; 
           [0047]      FIGS. 13A ,  13 B, and  13 C illustrate the operation of the error correcting decoder in the second embodiment when memory usage is reduced; and 
           [0048]      FIG. 14  illustrates the result of removing paths with branch metric values of zero from the trellis diagram in  FIG. 13C . 
       
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       [0049]    Embodiments of the invention will now be described with reference to the attached drawings, in which like elements are indicated by like reference characters. 
       First Embodiment 
       [0050]    Referring to  FIG. 5 , the first embodiment is a coding system  10  comprising an encoding apparatus  10 A and a decoding apparatus  10 B. The encoding apparatus  10 A encodes input information, sends encoded data to the decoding apparatus  10 B, and receives requests for additional bits from the decoding apparatus  10 B. The decoding apparatus  10 B receives and decodes the encoded data and may request additional bits from the encoding apparatus  10 A. 
         [0051]    The encoding apparatus  10 A comprises a systematic encoder  101  for coding input information to generate information bits and parity bits, a parity bit buffer  102  for storing the parity bits generated by the systematic encoder  101 , a information bit buffer  104  for storing the information bits generated by the systematic encoder  101 , a bit transmitter  103  for transmitting the information bits and parity bits selectively, a bit transmission controller  105  for controlling the transmission of bits by the bit transmitter  103 , and a transmission request signal receiver  106  for receiving requests from the decoding apparatus and passing the requests to the bit transmission controller  105 . 
         [0052]    The decoding apparatus  10 B comprises a bit receiver  109  for receiving information bits and parity bits from the encoding apparatus, a parity bit buffer  108  for storing the parity bits received by the bit receiver  109 , an information bit buffer  111  for storing the information bits received by the bit receiver  109 , an information bit predictor  112  for predicting the information bits, an input information generator  110  for generating information bits for input to an error correcting decoder  107  from the bits predicted by the information bit predictor  112  and the bits output from the information bit buffer  111 , an error correcting decoder  107  for carrying out an error-correcting decoding process on the information bits generated by the input information generator  110  and the parity bits stored in the parity bit buffer  108 , a transmission request signal controller  113  for controlling the sending of requests for the transmission of additional information bits or parity bits to the encoding apparatus, responsive to status information supplied by the error correcting decoder  107 , and a transmission request signal transmitter  114  for sending transmission requests to the encoding apparatus as specified by the transmission request signal controller  113 . 
         [0053]    The parity bits generated by the systematic encoder  101  function as compressively encoded image information. If the parity bits are corrupted in transmission between the encoding apparatus  10 A and  10 B, the decoding accuracy suffers significantly. To avoid such corruption, before transmitting the parity bits and information bits, the bit transmitter  103  adds information that enables transmission errors to be detected and corrected by the bit receiver  109 . That is, the bit transmitter encodes the transmitted bits by using an error correcting code strong enough to correct all anticipated transmission errors. Alternatively, the bit transmitter  103  may simply add error detection information such as a check code to the transmitted bits, and the bit receiver  109  may request retransmission if an error is detected. As another alternative, the bit transmitter  103  and bit receiver  109  may be interconnected by an error-free transmission channel. 
         [0054]    The operation of the coding system  10  in the first embodiment will be described with reference to the flowchart in  FIG. 6 . 
         [0055]    When the data to be encoded are input, the systematic encoder  101  encodes the data and generates information bits and parity bits (step S 101 ). The systematic code employed by the systematic encoder  101  makes a clear distinction between information bits, which represent the input data, and parity bits, which provide redundant information for detecting and correcting errors in the information bits. A convolutional encoder or a turbo encoder may be used, for example. 
         [0056]    The information bits generated by the systematic encoder  101  are stored in the information bit buffer  104  (step S 102 ), and the parity bits generated by the systematic encoder  101  are stored in the parity bit buffer  102  (step S 103 ). 
         [0057]    The bit transmission controller  105  gives the parity bit buffer  102 , information bit buffer  104 , and bit transmitter  103  an instruction to transmit the parity bits or information bits in accordance with a predetermined table or the like (step S 104 ). The bit transmitter  103  transmits the specified bits (step S 105 ). The table may be similar to the puncturing tables generally used for the puncturing of parity bits. The table can control the transmission of parity bits to the decoding apparatus so that, for example, one of every sixteen parity bits is transmitted and control the transmission of the information bits so that one out of every thirty-two information bits is transmitted. 
         [0058]    The bits are transmitted from the encoding apparatus through a communication channel and are received by the decoding apparatus  10 B, more specifically by the bit receiver  109  (step S 106 ). The information bits received by the bit receiver  109  are stored in the information bit buffer  111  (step S 107 ), and the received parity bits are stored in the parity bit buffer  108  (step S 108 ). 
         [0059]    The information bit predictor  112  predicts the information bits generated by the encoding apparatus (step S 109 ) by using data decoded before. The information bits of a video image frame are predicted from a preceding frame or by interpolation between preceding and following frames. The information bits of a sound waveform are predicted from past waveform information by detecting short-term periodicities by autocorrelation processing and by detecting the envelope of the waveform. 
         [0060]    The input information generator  110  generates input information bits for input to the error correcting decoder  107  from the information bits predicted by the information bit predictor  112  and the information bits stored in the information bit buffer  111  (step S 110 ). The input information generator  110  may generate the input information bits by overwriting the stored information bits on the predicted information bits. 
         [0061]    The input information bits generated by the input information generator  110  and the parity bits stored in the parity bit buffer  108  are input to the error correcting decoder  107 , where an error-correcting decoding process is carried out (step S 111 ), and whether the result of the decoding process is satisfactory is decided (step  112 ). The decoding process may use the MAP algorithm, for example, to obtain a likelihood that each bit is 0 or 1, or may employ a turbo decoding process, in which different convolutional decoders repeatedly supply their results to each other as a-priori probabilities. 
         [0062]    When satisfactorily error-free decoding results are obtained, a decision is made as to whether to terminate the decoding process (step S 113 ). To continue the process, the error correcting decoder  107  notifies the transmission request signal controller  113 . The transmission request signal controller  113  gives the transmission request signal transmitter  114  an instruction to output a transmission request for data for the next frame. The transmission request signal transmitter  114  sends the transmission request to the encoding apparatus  10 A through a network or the like (step S 114 ). In response, the encoding apparatus  10 A returns to step S 101  to process the next data. 
         [0063]    If satisfactory decoding results have not been obtained in step S 112 , the error correcting decoder  107  notifies the transmission request signal controller  113 . The transmission request signal controller  113  gives the transmission request signal transmitter  114  an instruction to output a transmission request for additional data for the same frame, such as additional data for the same bit plane or data for the next bit plane in the same frame. The transmission request signal transmitter  114  sends a transmission request to the encoding apparatus  10 A through the network (step S 115 ). In response, the encoding apparatus  10 A returns to step S 104  in order to transmit additional data from one of its buffers. Transmission requests for additional data may be sent repeatedly until the error correcting decoder  107  decides in step S 112  that satisfactory decoding results have been obtained. Satisfactory decoding results can be recognized when, for example, the log likelihood obtained in decoding using the MAP algorithm exceeds a predetermined value. 
         [0064]    The decision in step S 112  may be made on a bit-plane-by-bit-plane-basis, instead of a frame-by-frame basis. 
         [0065]    When the encoding apparatus  10 A receives a transmission request from the decoding apparatus, the transmission request signal receiver  106  identifies the type of data requested, e.g., data in the next bit plane or the next frame, or additional data in the same bit plane or the same frame (step S 116 ). 
         [0066]    If additional data for the same bit plane or the same frame etc. are requested, the transmission request signal receiver  106  notifies the bit transmission controller  105  (step S 117 ). The bit transmission controller  105  commands the parity bit buffer  102  or information bit buffer  104  to output the requested data (step S 104 ). The bit transmitter  103  sends the requested data (step S 105 ). 
         [0067]    If new data such as data for the next bit plane or the next frame are requested, the encoding process for the next bit plane or next frame starts from step S 101 . 
         [0068]    The coding system  10  repeats the processing described above until an end command is issued (step S 113 ). 
         [0069]    The operation of the error correcting decoder  107  in the decoding apparatus  10 B will next be described in detail, on the assumption that the error correcting decoder  107  uses the MAP. As explained above, in the MAP algorithm the input bit values received from the input information generator  110  and the parity bit values received from the parity bit buffer  108  are used to calculate metrics that indicate whether the true value of each information bit is more likely to be 0 or 1. In the present invention, however, the input bit values include not only the conventional bit values predicted by the input information generator  110  as side information, but also occasional information bit values received directly from the encoding apparatus  10 A. 
         [0070]      FIGS. 7A ,  7 B, and  7 C illustrate the operation of the error correcting decoder  107  in the first embodiment by showing an example of calculations analogous to the conventional calculations illustrated in  FIGS. 4A ,  4 B, and  4 C. 
         [0071]    A systematic convolutional encoder with a constraint length of three and a coding rate of one-half is used in this example, as shown in  FIG. 7A . Information bits u {1, 0, 0} and parity bits v {1, 0, 1} are generated at times n−1, n, and n+1. Of these bits, only the information bit (0) for time n is transmitted. 
         [0072]    Suppose that the decoding apparatus updates the predicted values x {1.5, 0.0, −0.6} of the information bits in  FIG. 4B  to {1.5, −1.0, −0.6} because the information bit (0) for time n has been received, as shown in  FIG. 7B . The parity bits y in  FIG. 7B  are {0.0, 0.0, 0.0}, indicating that they have not been transmitted. 
         [0073]    For the transition from time n to time n+1, branch metrics are calculated as follows. 
         [0074]    Given the known information bit of zero (i=0) input at time n, branch metrics for the resulting transitions from states a (00), b (10), c (01), and d (11) are calculated as in equations (23) to (26). The a-priori probability (π i=0   k ) of input of a zero bit at time k is one-half (0.5). The parameters A k  and σ 2  are taken to be unity. 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         
                           δ 
                           k 
                           
                             
                               i 
                               = 
                               0 
                             
                             , 
                             
                               m 
                               = 
                               a 
                             
                           
                         
                         = 
                           
                          
                         
                           
                             A 
                             k 
                           
                            
                           
                             π 
                             k 
                             
                               i 
                               = 
                               0 
                             
                           
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 
                                   y 
                                   k 
                                 
                                  
                                 
                                   
                                     v 
                                     k 
                                     
                                       
                                         i 
                                         = 
                                         0 
                                       
                                       , 
                                       
                                         m 
                                         = 
                                         a 
                                       
                                     
                                   
                                   / 
                                   
                                     σ 
                                     2 
                                   
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           0.5 
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 
                                   y 
                                   k 
                                 
                                  
                                 
                                   v 
                                   k 
                                   
                                     
                                       i 
                                       = 
                                       0 
                                     
                                     , 
                                     
                                       m 
                                       = 
                                       a 
                                     
                                   
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           0.5 
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 
                                   ( 
                                   0.0 
                                   ) 
                                 
                                 × 
                                 
                                   ( 
                                   
                                     - 
                                     1 
                                   
                                   ) 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         0.50 
                       
                     
                   
                 
               
               
                 
                   ( 
                   23 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       
                         
                           δ 
                           k 
                           
                             
                               i 
                               = 
                               0 
                             
                             , 
                             
                               m 
                               = 
                               b 
                             
                           
                         
                         = 
                           
                          
                         
                           
                             A 
                             k 
                           
                            
                           
                             π 
                             k 
                             
                               i 
                               = 
                               0 
                             
                           
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 
                                   y 
                                   k 
                                 
                                  
                                 
                                   
                                     v 
                                     k 
                                     
                                       
                                         i 
                                         = 
                                         0 
                                       
                                       , 
                                       
                                         m 
                                         = 
                                         b 
                                       
                                     
                                   
                                   / 
                                   
                                     σ 
                                     2 
                                   
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           0.5 
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 
                                   y 
                                   k 
                                 
                                  
                                 
                                   v 
                                   k 
                                   
                                     
                                       i 
                                       = 
                                       0 
                                     
                                     , 
                                     
                                       m 
                                       = 
                                       b 
                                     
                                   
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           0.5 
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 
                                   ( 
                                   0.0 
                                   ) 
                                 
                                 × 
                                 
                                   ( 
                                   
                                     - 
                                     1 
                                   
                                   ) 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         0.50 
                       
                     
                   
                 
               
               
                 
                   ( 
                   24 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       
                         
                           δ 
                           k 
                           
                             
                               i 
                               = 
                               0 
                             
                             , 
                             
                               m 
                               = 
                               c 
                             
                           
                         
                         = 
                           
                          
                         
                           
                             A 
                             k 
                           
                            
                           
                             π 
                             k 
                             
                               i 
                               = 
                               0 
                             
                           
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 
                                   y 
                                   k 
                                 
                                  
                                 
                                   
                                     v 
                                     k 
                                     
                                       
                                         i 
                                         = 
                                         0 
                                       
                                       , 
                                       
                                         m 
                                         = 
                                         c 
                                       
                                     
                                   
                                   / 
                                   
                                     σ 
                                     2 
                                   
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           0.5 
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 
                                   y 
                                   k 
                                 
                                  
                                 
                                   v 
                                   k 
                                   
                                     
                                       i 
                                       = 
                                       0 
                                     
                                     , 
                                     
                                       m 
                                       = 
                                       c 
                                     
                                   
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           0.5 
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 
                                   ( 
                                   0.0 
                                   ) 
                                 
                                 × 
                                 
                                   ( 
                                   
                                     + 
                                     1 
                                   
                                   ) 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         0.50 
                       
                     
                   
                 
               
               
                 
                   ( 
                   25 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       
                         
                           δ 
                           k 
                           
                             
                               i 
                               = 
                               0 
                             
                             , 
                             
                               m 
                               = 
                               d 
                             
                           
                         
                         = 
                           
                          
                         
                           
                             A 
                             k 
                           
                            
                           
                             π 
                             k 
                             
                               i 
                               = 
                               0 
                             
                           
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 
                                   y 
                                   k 
                                 
                                  
                                 
                                   
                                     v 
                                     k 
                                     
                                       
                                         i 
                                         = 
                                         0 
                                       
                                       , 
                                       
                                         m 
                                         = 
                                         d 
                                       
                                     
                                   
                                   / 
                                   
                                     σ 
                                     2 
                                   
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           0.5 
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 
                                   y 
                                   k 
                                 
                                  
                                 
                                   v 
                                   k 
                                   
                                     
                                       i 
                                       = 
                                       0 
                                     
                                     , 
                                     
                                       m 
                                       = 
                                       d 
                                     
                                   
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           0.5 
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 
                                   ( 
                                   0.0 
                                   ) 
                                 
                                 × 
                                 
                                   ( 
                                   
                                     + 
                                     1 
                                   
                                   ) 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         0.50 
                       
                     
                   
                 
               
               
                 
                   ( 
                   26 
                   ) 
                 
               
             
           
         
       
     
         [0075]    If the transmitted bits are assumed to be received without corruption, there is zero likelihood that the information bit input at time n has a value of 1, yielding the zero branch metrics expressed by equations (27) to (30). 
         [0000]      δ i=1, m=a   k =0   (27) 
         [0000]      δ i=1, m=b   k =0   (28) 
         [0000]      δ i=1, m=c   k =0   (29) 
         [0000]      δ i=1, m=d   k =0   (30) 
         [0076]    In contrast to the prior art shown in  FIG. 3C , in  FIG. 7C  the values of the branch metrics on the dotted lines extending from time n are all 0.0. This is because the dotted lines represent information bit values of 1, and given a guaranteed value of 0 for the information bit at the transition from time n to time n+1, an information bit value of 1 cannot be output. 
         [0077]    For the transition from time n−1 to time n, branch metrics are calculated as follows. 
         [0078]    Since the encoding apparatus does not transmit any bit at time n−1, the calculation is divided into two cases corresponding to information bit values of 0 and 1, expressed as follows. 
         [0000]      u i=0   k=n−1 =−1 
         [0000]      u i=1   k=n−1 =−1 
         [0000]    The calculations for the two cases are expressed by equations (31) and (32). 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         
                           δ 
                           
                             k 
                             = 
                             
                               n 
                               - 
                               1 
                             
                           
                           
                             
                               i 
                               = 
                               0 
                             
                             , 
                             m 
                           
                         
                         = 
                           
                          
                         
                           
                             A 
                             
                               k 
                               = 
                               
                                 n 
                                 - 
                                 1 
                               
                             
                           
                            
                           
                             π 
                             
                               k 
                               = 
                               
                                 n 
                                 - 
                                 1 
                               
                             
                             
                               i 
                               = 
                               0 
                             
                           
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 
                                   x 
                                   
                                     k 
                                     = 
                                     
                                       n 
                                       - 
                                       1 
                                     
                                   
                                 
                                  
                                 
                                   
                                     u 
                                     
                                       k 
                                       = 
                                       
                                         n 
                                         - 
                                         1 
                                       
                                     
                                     
                                       i 
                                       = 
                                       0 
                                     
                                   
                                   / 
                                   
                                     σ 
                                     2 
                                   
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           
                             A 
                             
                               k 
                               = 
                               
                                 n 
                                 - 
                                 1 
                               
                             
                           
                            
                           
                             π 
                             
                               k 
                               = 
                               
                                 n 
                                 - 
                                 1 
                               
                             
                             
                               i 
                               = 
                               0 
                             
                           
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 
                                   - 
                                   
                                     x 
                                     
                                       k 
                                       = 
                                       
                                         n 
                                         - 
                                         1 
                                       
                                     
                                   
                                 
                                 / 
                                 
                                   σ 
                                   2 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   31 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       
                         
                           δ 
                           
                             k 
                             = 
                             
                               n 
                               - 
                               1 
                             
                           
                           
                             
                               i 
                               = 
                               1 
                             
                             , 
                             m 
                           
                         
                         = 
                           
                          
                         
                           
                             A 
                             
                               k 
                               = 
                               
                                 n 
                                 - 
                                 1 
                               
                             
                           
                            
                           
                             π 
                             
                               k 
                               = 
                               
                                 n 
                                 - 
                                 1 
                               
                             
                             
                               i 
                               = 
                               1 
                             
                           
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 
                                   x 
                                   
                                     k 
                                     = 
                                     
                                       n 
                                       - 
                                       1 
                                     
                                   
                                 
                                  
                                 
                                   
                                     u 
                                     
                                       k 
                                       = 
                                       
                                         n 
                                         - 
                                         1 
                                       
                                     
                                     
                                       i 
                                       = 
                                       1 
                                     
                                   
                                   / 
                                   
                                     σ 
                                     2 
                                   
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           
                             A 
                             
                               k 
                               = 
                               
                                 n 
                                 - 
                                 1 
                               
                             
                           
                            
                           
                             π 
                             
                               k 
                               = 
                               
                                 n 
                                 - 
                                 1 
                               
                             
                             
                               i 
                               = 
                               1 
                             
                           
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 
                                   - 
                                   
                                     x 
                                     
                                       k 
                                       = 
                                       
                                         n 
                                         - 
                                         1 
                                       
                                     
                                   
                                 
                                 / 
                                 
                                   σ 
                                   2 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   32 
                   ) 
                 
               
             
           
         
       
     
         [0079]    Assuming again that A k=n−1 =1 and σ 2 −1, equation (31) gives equation (33), and equation (32) gives equation (34). 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         
                           δ 
                           
                             k 
                             = 
                             
                               n 
                               - 
                               1 
                             
                           
                           
                             
                               i 
                               = 
                               0 
                             
                             , 
                             m 
                           
                         
                         = 
                           
                          
                         
                           
                             A 
                             
                               k 
                               = 
                               
                                 n 
                                 - 
                                 1 
                               
                             
                           
                            
                           
                             π 
                             
                               k 
                               = 
                               
                                 n 
                                 - 
                                 1 
                               
                             
                             
                               i 
                               = 
                               0 
                             
                           
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 
                                   - 
                                   
                                     x 
                                     
                                       k 
                                       = 
                                       
                                         n 
                                         - 
                                         1 
                                       
                                     
                                   
                                 
                                 / 
                                 
                                   σ 
                                   2 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           0.5 
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 - 
                                 
                                   x 
                                   
                                     k 
                                     = 
                                     
                                       n 
                                       - 
                                       1 
                                     
                                   
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           0.5 
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 - 
                                 
                                   ( 
                                   1.5 
                                   ) 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         0.11 
                       
                     
                   
                 
               
               
                 
                   ( 
                   33 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       
                         
                           δ 
                           
                             k 
                             = 
                             
                               n 
                               - 
                               1 
                             
                           
                           
                             
                               i 
                               = 
                               1 
                             
                             , 
                             m 
                           
                         
                         = 
                           
                          
                         
                           
                             A 
                             
                               k 
                               = 
                               
                                 n 
                                 - 
                                 1 
                               
                             
                           
                            
                           
                             π 
                             
                               k 
                               = 
                               
                                 n 
                                 - 
                                 1 
                               
                             
                             
                               i 
                               = 
                               1 
                             
                           
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 
                                   x 
                                   
                                     k 
                                     = 
                                     
                                       n 
                                       - 
                                       1 
                                     
                                   
                                 
                                 / 
                                 
                                   σ 
                                   2 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           0.5 
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 x 
                                 
                                   k 
                                   = 
                                   
                                     n 
                                     - 
                                     1 
                                   
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           0.5 
                            
                           
                             exp 
                              
                             
                               ( 
                               1.5 
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         2.24 
                       
                     
                   
                 
               
               
                 
                   ( 
                   34 
                   ) 
                 
               
             
           
         
       
     
         [0080]    The branch metric calculations for the transition from time n+1 to time n+2 are similar to the branch metric calculations for the transition from time n−1 to time n, and give the results shown in  FIG. 7C . 
         [0081]    The calculation of the decoded bit values will be described by using  FIG. 7C . 
         [0082]    The process of decoding the information bit for the transition from time n−1 to time n will be described. If an information bit value of 0 is assumed to have been input for the transition from time n−1 to time n, a value is calculated as expressed by equation (35). If an information bit value of 1 is assumed to have been input for the transition from time n−1 to time n, a value is calculated as expressed by equation (36). Based on these calculated values, the log likelihood of the bit value obtained by equation (37) is 1.31. As this value is positive, a correctly decoded information bit value of 1 is obtained. 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         α 
                         
                           k 
                           = 
                           
                             n 
                             - 
                             1 
                           
                         
                         
                           m 
                           = 
                           a 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           
                             n 
                             - 
                             1 
                           
                         
                         
                           
                             i 
                             = 
                             0 
                           
                           , 
                           
                             m 
                             = 
                             a 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           n 
                         
                         
                           m 
                           = 
                           a 
                         
                       
                     
                     + 
                     
                       
                         α 
                         
                           k 
                           = 
                           
                             n 
                             - 
                             1 
                           
                         
                         
                           m 
                           = 
                           b 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           
                             n 
                             - 
                             1 
                           
                         
                         
                           
                             i 
                             = 
                             0 
                           
                           , 
                           
                             m 
                             = 
                             b 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           n 
                         
                         
                           m 
                           = 
                           c 
                         
                       
                     
                     + 
                     
                       
                         α 
                         
                           k 
                           = 
                           
                             n 
                             - 
                             1 
                           
                         
                         
                           m 
                           = 
                           c 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           
                             n 
                             - 
                             1 
                           
                         
                         
                           
                             i 
                             = 
                             0 
                           
                           , 
                           
                             m 
                             = 
                             c 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           n 
                         
                         
                           m 
                           = 
                           a 
                         
                       
                     
                     + 
                     
                       
                         α 
                         
                           k 
                           = 
                           
                             n 
                             - 
                             1 
                           
                         
                         
                           m 
                           = 
                           d 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           
                             n 
                             - 
                             1 
                           
                         
                         
                           
                             i 
                             = 
                             0 
                           
                           , 
                           
                             m 
                             = 
                             d 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           n 
                         
                         
                           m 
                           = 
                           c 
                         
                       
                     
                     + 
                     
                       0.01 
                       × 
                       0.11 
                       × 
                       2.46 
                     
                     + 
                     
                       0.05 
                       × 
                       0.11 
                       × 
                       0.56 
                     
                     + 
                     
                       1.25 
                       × 
                       0.11 
                       × 
                       2.46 
                     
                     + 
                     
                       5.0 
                       × 
                       0.11 
                       × 
                       2.46 
                     
                   
                   = 
                   1.705299585 
                 
               
               
                 
                   ( 
                   35 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       
                         α 
                         
                           k 
                           = 
                           
                             n 
                             - 
                             1 
                           
                         
                         
                           m 
                           = 
                           a 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           
                             n 
                             - 
                             1 
                           
                         
                         
                           
                             i 
                             = 
                             1 
                           
                           , 
                           
                             m 
                             = 
                             a 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           n 
                         
                         
                           m 
                           = 
                           b 
                         
                       
                     
                     + 
                     
                       
                         α 
                         
                           k 
                           = 
                           
                             n 
                             - 
                             1 
                           
                         
                         
                           m 
                           = 
                           b 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           
                             n 
                             - 
                             1 
                           
                         
                         
                           
                             i 
                             = 
                             1 
                           
                           , 
                           
                             m 
                             = 
                             b 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           n 
                         
                         
                           m 
                           = 
                           d 
                         
                       
                     
                     + 
                     
                       
                         α 
                         
                           k 
                           = 
                           
                             n 
                             - 
                             1 
                           
                         
                         
                           m 
                           = 
                           c 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           
                             n 
                             - 
                             1 
                           
                         
                         
                           
                             i 
                             = 
                             1 
                           
                           , 
                           
                             m 
                             = 
                             c 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           n 
                         
                         
                           m 
                           = 
                           b 
                         
                       
                     
                     + 
                     
                       
                         α 
                         
                           k 
                           = 
                           
                             n 
                             - 
                             1 
                           
                         
                         
                           m 
                           = 
                           d 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           
                             n 
                             - 
                             1 
                           
                         
                         
                           
                             i 
                             = 
                             1 
                           
                           , 
                           
                             m 
                             = 
                             d 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           n 
                         
                         
                           m 
                           = 
                           d 
                         
                       
                     
                     + 
                     
                       5.77 
                       × 
                       2.24 
                       × 
                       2.46 
                     
                     + 
                     
                       0.05 
                       × 
                       2.24 
                       × 
                       2.46 
                     
                     + 
                     
                       1.25 
                       × 
                       2.24 
                       × 
                       2.46 
                     
                     + 
                     
                       5.0 
                       × 
                       2.24 
                       × 
                       2.46 
                     
                   
                   = 
                   34.72610064 
                 
               
               
                 
                   ( 
                   36 
                   ) 
                 
               
             
             
               
                 
                   
                       
                   
                    
                   
                     
                       log 
                        
                       
                           
                       
                        
                       
                         ( 
                         
                           34.7261 
                           / 
                           1.705299585 
                         
                          
                         
                             
                         
                         ) 
                       
                     
                     = 
                     1.31 
                   
                 
               
               
                 
                   ( 
                   37 
                   ) 
                 
               
             
           
         
       
     
         [0083]    The process of decoding the information bit for the transition from time n to time n+1 will now be described. If an information bit value of 0 is assumed to have been input for the transition from time n to time n+1, a value is calculated as expressed by equation (38). If an information bit value of 1 is assumed to be input for the transition from time n to time n+1, a value is calculated as expressed by equation (39). Based on these calculated values, the log likelihood of the bit value obtained by equation (40) is −∞. As this value is negative, a correctly decoded information bit value of 0 is obtained. 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         α 
                         
                           k 
                           = 
                           n 
                         
                         
                           m 
                           = 
                           a 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           n 
                         
                         
                           
                             i 
                             = 
                             0 
                           
                           , 
                           
                             m 
                             = 
                             a 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           m 
                           = 
                           a 
                         
                       
                     
                     + 
                     
                       
                         α 
                         
                           k 
                           = 
                           n 
                         
                         
                           m 
                           = 
                           b 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           n 
                         
                         
                           
                             i 
                             = 
                             0 
                           
                           , 
                           
                             m 
                             = 
                             b 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           m 
                           = 
                           c 
                         
                       
                     
                     + 
                     
                       
                         α 
                         
                           k 
                           = 
                           n 
                         
                         
                           m 
                           = 
                           c 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           n 
                         
                         
                           
                             i 
                             = 
                             0 
                           
                           , 
                           
                             m 
                             = 
                             c 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           m 
                           = 
                           a 
                         
                       
                     
                     + 
                     
                       
                         α 
                         
                           k 
                           = 
                           n 
                         
                         
                           m 
                           = 
                           d 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           n 
                         
                         
                           
                             i 
                             = 
                             0 
                           
                           , 
                           
                             m 
                             = 
                             d 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           m 
                           = 
                           c 
                         
                       
                     
                     + 
                     
                       0.14 
                       × 
                       0.50 
                       × 
                       4.91 
                     
                     + 
                     
                       2.82 
                       × 
                       0.50 
                       × 
                       4.91 
                     
                     + 
                     
                       0.56 
                       × 
                       0.50 
                       × 
                       4.91 
                     
                     + 
                     
                       11.31 
                       × 
                       0.50 
                       × 
                       4.91 
                     
                   
                   = 
                   36.43140023 
                 
               
               
                 
                   ( 
                   38 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       
                         α 
                         
                           k 
                           = 
                           n 
                         
                         
                           m 
                           = 
                           a 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           n 
                         
                         
                           
                             i 
                             = 
                             1 
                           
                           , 
                           
                             m 
                             = 
                             a 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           m 
                           = 
                           b 
                         
                       
                     
                     + 
                     
                       
                         α 
                         
                           k 
                           = 
                           n 
                         
                         
                           m 
                           = 
                           b 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           n 
                         
                         
                           
                             i 
                             = 
                             1 
                           
                           , 
                           
                             m 
                             = 
                             b 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           m 
                           = 
                           d 
                         
                       
                     
                     + 
                     
                       
                         α 
                         
                           k 
                           = 
                           n 
                         
                         
                           m 
                           = 
                           c 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           n 
                         
                         
                           
                             i 
                             = 
                             1 
                           
                           , 
                           
                             m 
                             = 
                             c 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           m 
                           = 
                           b 
                         
                       
                     
                     + 
                     
                       
                         α 
                         
                           k 
                           = 
                           n 
                         
                         
                           m 
                           = 
                           d 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           n 
                         
                         
                           
                             i 
                             = 
                             1 
                           
                           , 
                           
                             m 
                             = 
                             d 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           m 
                           = 
                           d 
                         
                       
                     
                     + 
                     
                       0.14 
                       × 
                       0.0 
                       × 
                       1.01 
                     
                     + 
                     
                       2.82 
                       × 
                       0.0 
                       × 
                       1.01 
                     
                     + 
                     
                       0.56 
                       × 
                       0.0 
                       × 
                       1.01 
                     
                     + 
                     
                       11.31 
                       × 
                       0.0 
                       × 
                       1.01 
                     
                   
                   = 
                   0 
                 
               
               
                 
                   ( 
                   39 
                   ) 
                 
               
             
             
               
                 
                   
                       
                   
                    
                   
                     
                       log 
                        
                       
                           
                       
                        
                       
                         ( 
                         
                           0 
                           / 
                           36.43140023 
                         
                          
                         
                             
                         
                         ) 
                       
                     
                     = 
                     
                       - 
                       ∞ 
                     
                   
                 
               
               
                 
                   ( 
                   40 
                   ) 
                 
               
             
           
         
       
     
         [0084]    The process of decoding the information bit for the transition from time n+1 to time n+2 will also be described. If an information bit value of 0 is assumed to have been input for the transition from time n+1 to time n+2, a value is calculated as expressed by equation (41). If an information bit value of 1 is assumed to have been input for the transition from time n+1 to time n+2, a value is calculated as expressed by equation (42). Based on these calculated values, the log likelihood of the bit value, obtained by equation (43), is −0.36. As this value is negative, a correctly decoded information bit value of 0 is obtained. 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         α 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           m 
                           = 
                           a 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           
                             i 
                             = 
                             0 
                           
                           , 
                           
                             m 
                             = 
                             a 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             2 
                           
                         
                         
                           m 
                           = 
                           a 
                         
                       
                     
                     + 
                     
                       
                         α 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           m 
                           = 
                           b 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           
                             i 
                             = 
                             0 
                           
                           , 
                           
                             m 
                             = 
                             b 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             2 
                           
                         
                         
                           m 
                           = 
                           c 
                         
                       
                     
                     + 
                     
                       
                         α 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           m 
                           = 
                           c 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           
                             i 
                             = 
                             0 
                           
                           , 
                           
                             m 
                             = 
                             c 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             2 
                           
                         
                         
                           m 
                           = 
                           a 
                         
                       
                     
                     + 
                     
                       
                         α 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           m 
                           = 
                           d 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           
                             i 
                             = 
                             0 
                           
                           , 
                           
                             m 
                             = 
                             d 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             2 
                           
                         
                         
                           m 
                           = 
                           c 
                         
                       
                     
                     + 
                     
                       0.35 
                       × 
                       0.91 
                       × 
                       3.75 
                     
                     + 
                     
                       0.00 
                       × 
                       0.91 
                       × 
                       0.77 
                     
                     + 
                     
                       7.07 
                       × 
                       0.91 
                       × 
                       3.75 
                     
                     + 
                     
                       0.00 
                       × 
                       0.91 
                       × 
                       0.77 
                     
                   
                   = 
                   25.30112813 
                 
               
               
                 
                   ( 
                   41 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       
                         α 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           m 
                           = 
                           a 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           
                             i 
                             = 
                             1 
                           
                           , 
                           
                             m 
                             = 
                             a 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             2 
                           
                         
                         
                           m 
                           = 
                           b 
                         
                       
                     
                     + 
                     
                       
                         α 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           m 
                           = 
                           b 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           
                             i 
                             = 
                             1 
                           
                           , 
                           
                             m 
                             = 
                             b 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             2 
                           
                         
                         
                           m 
                           = 
                           d 
                         
                       
                     
                     + 
                     
                       
                         α 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           m 
                           = 
                           c 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           
                             i 
                             = 
                             1 
                           
                           , 
                           
                             m 
                             = 
                             c 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             2 
                           
                         
                         
                           m 
                           = 
                           b 
                         
                       
                     
                     + 
                     
                       
                         α 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           m 
                           = 
                           d 
                         
                       
                       × 
                       
                         δ 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             1 
                           
                         
                         
                           
                             i 
                             = 
                             1 
                           
                           , 
                           
                             m 
                             = 
                             d 
                           
                         
                       
                       × 
                       
                         β 
                         
                           k 
                           = 
                           
                             n 
                             + 
                             2 
                           
                         
                         
                           m 
                           = 
                           d 
                         
                       
                     
                     + 
                     
                       0.35 
                       × 
                       0.27 
                       × 
                       5.56 
                     
                     + 
                     
                       0.00 
                       × 
                       0.27 
                       × 
                       1.14 
                     
                     + 
                     
                       7.07 
                       × 
                       0.27 
                       × 
                       5.66 
                     
                     + 
                     
                       0.00 
                       × 
                       0.27 
                       × 
                       1.14 
                     
                   
                   = 
                   11.1302721 
                 
               
               
                 
                   ( 
                   42 
                   ) 
                 
               
             
             
               
                 
                   
                       
                   
                    
                   
                     
                       log 
                        
                       
                           
                       
                        
                       
                         ( 
                         
                           11.13027 
                           / 
                           25.30113 
                         
                          
                         
                             
                         
                         ) 
                       
                     
                     = 
                     
                       - 
                       0.36 
                     
                   
                 
               
               
                 
                   ( 
                   43 
                   ) 
                 
               
             
           
         
       
     
         [0085]      FIG. 8  illustrates the result of removing paths with branch metric values of zero from the trellis diagram in  FIG. 7C . If a single information bit can be received correctly, the computation of eight paths can be eliminated, as compared with  FIG. 7C . Moreover, the values of forward state metrics α and backward state metrics β related to four states do not have to be stored. 
         [0086]    In the first embodiment, instead of transmitting only parity bits, the encoding apparatus transmits a combination of information bits and parity bits to the decoding apparatus. While maintaining the correctness of the decoded results, this enables the decoding apparatus to rule out certain states at certain times and remove their associated paths. The amount of computation required by the MAP algorithm can be reduced accordingly. As can be seen from a comparison between  FIGS. 4 and 8 , transmitting a single information bit instead of a single parity bit eliminates the computations associated with four paths. 
         [0087]    Eliminating states also eliminates the need to store their forward and backward state metrics α and β. This reduces the memory usage of the decoding apparatus. In the example shown in  FIGS. 7A to 7C , and  FIG. 8 , transmitting a single information bit eliminates the need to store forward and backward state metrics α and β for four states. 
       Second Embodiment 
       [0088]    Referring to  FIG. 9 , the second embodiment is a coding system  20  comprising an encoding apparatus  20 A and a decoding apparatus  20 B identical to the decoding apparatus  10 B in the first embodiment. The encoding apparatus  20 A differs from the encoding apparatus  10 A in the first embodiment only in regard to the bit transmission controller  105   a , the operation and functions of which will be described below with reference to the flowchart in  FIG. 10 . Steps identical to steps in the first embodiment, shown in  FIG. 6 , are indicated by the same reference characters. 
         [0089]    The second embodiment differs from the first embodiment in that step S 104  is replaced by step S 104   a.    
         [0090]    In step S 104   a , the bit transmission controller  105   a  gives the parity bit buffer  102 , information bit buffer  104 , and bit transmitter  103  instructions to transmit parity bits and information bits in accordance with, for example, a predetermined table. This table is similar to the table used in the first embodiment, except that it specifies the transmission of information bits in consecutive pairs, or non-consecutive pairs, or information bits paired with parity bits. A plurality of tables are provided in the bit transmission controller  105   a , enabling the bit transmission controller  105   a  to select a table that fits the requirements of the decoding apparatus, as explained below. 
         [0091]    If a reduction of memory usage is the main requirement of the decoding apparatus, the bit transmission controller  105   a  causes two information bits separated by one non-transmitted information bit to be transmitted (instead of the transmission of information bits at, for example, thirty-two bit intervals).  FIGS. 11A ,  11 B, and  11 C illustrate the operation of the error correcting decoder  107  in the decoding apparatus  20 B for this case. 
         [0092]    The error correcting decoder  107  in the decoding apparatus  10 B is assumed to use the MAP algorithm in the error-correcting decoding process. In the operation illustrated in  FIG. 11A , a systematic convolutional encoder with a constraint length of three and a coding rate of one-half is used. At times n−1, n, n+1, n+2, and n+3, the information bits u {1, 0, 0, 0, 0} and parity bits v {1, 0, 1, 0, 0} are generated. However, only the information bits (both 0) for time n and time n+2 are transmitted. 
         [0093]    The decoding apparatus calculates a predicted value for each information bit. Upon receiving the information bits (0) for time n and time n+2, the apparatus updates its previously predicted bit values x for times n−1 to n+3 to {1.5, −1.0, −0.6, −1.0, ×0.6}. No parity bits have been received for these times, so the received parity bit values y are {0.0, 0.0, 0.0, 0.0, 0.0}. 
         [0094]    For the transitions from time n−1 to time n, from time n to time n+1, and from time n+1 to time n+2, branch metrics are calculated in the same way as in the first embodiment. For the transition from time n+2 to time n+3, branch metrics are calculated in the same way as for the transition from time n to time n+1. For the transition from time n+3 to time n+4, branch metrics are calculated in the same way as for the transition from time n+1 to time n+2. A description of the calculations will be omitted; the calculated metrics are simply shown in  FIG. 11C . 
         [0095]      FIG. 12  illustrates the result of removing paths with branch metric values of zero from the trellis diagram in  FIG. 11C . If the two information bits can be received correctly, the computations associated with eighteen paths can be eliminated, as shown. In addition, the values of forward and backward state metrics α and β related to eight states need not be stored, so memory usage is reduced. 
         [0096]    If a reduction of computational load is the main requirement of the decoding apparatus, the bit transmission controller  105   a  causes two or more information bits to be transmitted in succession.  FIGS. 13A ,  13 B, and  13 C illustrate the operation of the error correcting decoder  107  in the decoding apparatus  10 B when two information bits are transmitted in succession. 
         [0097]    In the illustrated operation, a systematic convolutional encoder with a constraint length of three and a coding rate of one-half is used. At times n−1, n, n+1, n+2, and n+3, the information bits u {1, 0, 0, 0, 0} and parity bits v {1, 0, 1, 0, 0} are generated, but only the information bits (both 0) for time n and time n+1 are transmitted. 
         [0098]    The decoding apparatus obtains a predicted value for each information bit. Receiving the information bit (0) for time n and the information bit (0) for time n+1, the apparatus updates the predicted value to x {1.5, −1.0, −1.0, −0.6, −0.6}. The parity bits y {0.0, 0.0, 0.0, 0.0, 0.0} are assumed to be received. The value 0.0 represents a parity bit value not transmitted from the encoding apparatus. 
         [0099]    Branch metrics are calculated in the same way as in the first and second embodiments.  FIG. 13C  shows the calculated metric values. 
         [0100]      FIG. 14  illustrates the result of removing paths with branch metric values of zero from the trellis diagram in  FIG. 13C . If two successive information bits can be received correctly, the computations associated with twenty paths can be eliminated, as shown. In addition, the values of forward and backward state metrics α and β related to seven states need not be stored, so memory usage can also be reduced. 
         [0101]    The second embodiment achieves the same general effect as the first embodiment, but can alter the effect to provide a greater reduction of memory usage or a greater reduction of computational load, to satisfy the requirements of the decoding apparatus, by changing the method of transmitting the information bits. 
         [0102]    If a reduction of memory usage is the main requirement of the decoding apparatus, information bits may be transmitted, eliminating the need to store the values of the forward and backward state metrics α and β related to eight states, one state more than when pairs of consecutive information bits are transmitted. 
         [0103]    If a reduction of computational load is the main requirement of the decoding apparatus, successive information bits may be transmitted to eliminate the computations for twenty paths, two more than the number of paths for which computations are eliminated by transmitting a non-consecutive pair of information bits. If two successive information bits are transmitted and the convolutional encoder has a constraint length of three, a single state can be identified for time n+2. Accordingly, an improvement in error-correcting capability can be expected. 
       Other Embodiments 
       [0104]    Some variations of embodiments have been described above; further modifications will be described below. 
         [0105]    Although the MAP algorithm is used for decoding in the description of the first and second embodiments, other algorithms such as the log-MAP algorithm and max-log-MAP algorithm can also be used. The present invention can be applied to all decoding algorithms that keep track of a plurality of states over time and calculate values for possible state transitions representing input of data bits. 
         [0106]    A systematic convolutional encoder with a constraint length of three and a coding rate of one-half is used in the description of the first and second embodiments, but other convolutional encoders can also be used. 
         [0107]    The second embodiment described the transmission of two information bits at an interval of one bit, but it is possible to transmit information bits at intervals of two or more bits, still achieving a reduction in memory usage and computational load. 
         [0108]    The second embodiment described the successive transmission of two information bits, but it is possible to transmit three or more successive information bits to achieve a reduction in memory usage and computational load. In particular, if a convolutional code with a given constraint length M is used, transmitting at least M−1 information bits in succession enables the decoder to eliminate numerous path metric calculations by identifying states in the trellis diagram, so this bit transmission strategy can be used as a particularly effective method of reducing the computational load. 
         [0109]    The second embodiment described only the transmission of information bits, but similar techniques can be applied to the transmission of parity bits. For example an information bit and the parity bit generated by input of the information bit to the encoder can be transmitted as a pair of bits to reduce the computational load by improving the decoding accuracy, so that the decoding process finishes in fewer iterations. Transmitting such pairs of parity and information bits at intervals of one or more information bits, or transmitting two such pairs of parity and information bits in succession, can both improve decoding accuracy and greatly reduce memory usage by the decoder or its computational load. Alternatively, M−1 such pairs of parity and information bits can be transmitted in succession, where M is any integer greater than two, such as an integer equal to the constraint length, to reduce the computational load still more. 
         [0110]    In the description of the preceding embodiments, a convolutional encoder of the non-feedback type was used, but a convolutional encoder of the feedback type may also be used. The transmission of information bits and parity bits in pairs is effective when a feedback convolutional encoder is used. 
         [0111]    In the description of the second embodiment, the encoding apparatus knows the requirements of the decoding apparatus beforehand. A more flexible system can be established by allowing the encoding apparatus to accept requests for reduced memory usage or reduced computational load from the decoding apparatus and modify its information bit transmission scheme accordingly. Such requests may be included in one of the transmission request signals transmitted by the transmission request signal transmitter in the decoding apparatus and received by the transmission signal request receiver in the encoding apparatus. If the decoding apparatus is implemented on a personal computer, transmission request signals of this type may be sent in response to user input requesting for example, improved display of moving pictures. 
         [0112]    Those skilled in the art will recognize that still further variations are possible within the scope of the invention, which is defined in the appended claims.