Patent Publication Number: US-2007113144-A1

Title: Decoding apparatus and decoding method

Description:
TECHNICAL FIELD  
      The present invention relates to a decoding apparatus and a decoding method, and is suitable for application in, for example, a decoding apparatus and a decoding method performing turbo decoding.  
     BACKGROUND ART  
      In recent years, VSF-OFCDM(Variable Spreading Factor-Orthogonal Frequency and Code Division Multiplexing) draws attention as the most likely candidate for the scheme adopted for the fourth generation mobile communication. If VSF-OFCDM is employed, it will be possible to realize a maximum transmission rate of 100 Mbps or more using bandwidth of about 50-100 MHz. It is effective to employ turbo coding/decoding as an error correction scheme for such an ultra high-speed transmission scheme.  
      The turbo coding/decoding scheme is characterized by using both convolutional coding and interleaving for transmission data and performing iterative decoding upon decoding. It is well known that performing iterative decoding achieves excellent error correction capability not only for random errors, but for burst errors.  
      Here, an algorithm of turbo decoding will be explained briefly using equations. With turbo decoding, likelihood information L(d k ) is calculated, and calculated likelihood information L(d k ) is compared with a threshold value “ 0 .” As a result of the comparison, when likelihood information L(d k ) is “0” or more, a hard decision is made that the systematic bit d k =1 transmitted at time k. When likelihood information L(d k ) is less than “0,” a hard decision is made that the systematic bit d k =0 transmitted at time k.  
      Here, likelihood information L(d k ) will be explained. Likelihood information L(d k ) can be represented by the following equation using probability λ k  that is defined as a product of forward probability α k  and backward probability β k .  
             (     Equation   ⁢           ⁢   1     )                             L   ⁡     (     d   k     )       =     log   ⁢           ⁢         ∑   m     ⁢       λ   k   1     ⁡     (   m   )             ∑   m     ⁢       λ   k   0     ⁡     (   m   )                     (   1   )             
 
 (Equation 2)  λ k   i =α k  ( m )·β k ( m )  (2) 
 
 m is the state in a state transition trellis. Forward probability α k  and backward probability β k  can be represented by the following equations respectively.  
             (     Equation   ⁢           ⁢   3     )                               α   k     ⁡     (   m   )       =         ∑     m   ′       ⁢       ∑     i   =   0     1     ⁢         γ   i     ⁡     (       R   k     ,     m   ′     ,   m     )       ⁢       α     k   -   1       ⁡     (     m   ′     )                 ∑   m     ⁢       ∑     m   ′       ⁢       ∑     i   =   0     1     ⁢         γ   i     ⁡     (       R   k     ,     m   ′     ,   m     )       ⁢       α     k   -   1       ⁡     (     m   ′     )                         (   3   )             
 
             (     Equation   ⁢           ⁢   4     )                               β   k     ⁡     (   m   )       =         ∑     m   ′       ⁢       ∑     i   =   0     1     ⁢         γ   i     ⁡     (       R     k   +   1       ,     m   ′     ,   m     )       ⁢       β     k   +   1       ⁡     (     m   ′     )                 ∑   m     ⁢       ∑     m   ′       ⁢       ∑     i   =   0     1     ⁢         γ   i     ⁡     (       R     k   +   1       ,   m   ,     m   ′       )       ⁢       α   k     ⁡     (     m   ′     )                         (   4   )             
 
 m′ is also the state in a state transition trellis, and a transition probability γ i  can be represented by the following equation. 
 
 (Equation 5) 
 
γ i ( R   k   ,m′,m )= p ( R   k   /d   k   =i,S   k   =m,S   k−1   =m′ )· q ( d   k   =i/S   k   =m,S   k−1   =m′ )·π( S   k   =m/S   k−1   =m′ )  (5) 
 
 Here, R k  is an input to a decoder at time k, and p(●/●) is the transition probability of the discrete Gaussian memoryless transmission path. In addition, q corresponds to 0 or 1, and n represents a state transition probability of the trellis. 
 
      With turbo decoding, information bit d k  is decoded by performing the above-noted calculation, which, however, requires an enormous memory capacity. Then, a method called the sliding window method is considered.  
      Using this sliding window method makes possible considerable reduction in memory capacity. Turbo decoding processing procedures are, as described above, generally divided into the calculation of forward probability α (hereinafter referred to as “A calculation”), the calculation of backward probability β (hereinafter referred to as “B calculation”) and the calculation of likelihood information L(d k ). The sliding window method is a method that effectively performs the A calculation and B calculation.  
      In the following, the sliding window method will be explained. The sliding window method divides all sequences of data into predetermined window units, provides a training interval for each window and calculates the backward probability, which must be calculated from the end of the sequences, from the middle of the sequences. According to this sliding window method, it is only necessary to store the backward probability on a per window basis, so that it is possible to considerably reduce memory capacity, compared to the case of storing all backward probabilities of times k to  1 .  
      Here, more specifically, the sliding window method in case of performing the B calculation will be explained with reference to an accompanying drawing.  FIG. 1  is a pattern diagram conceptually showing repetition processing of conventional B calculation. Here, an explanation will be provided making the window size  32  and using three windows for ease of explanation. In this figure, the window at time  0 - 31  is B# 0 , the window at time  32 - 63  is B# 1  and the window at time  64 - 95  is B# 2 . In addition, since the B calculation performs the calculation in backward direction in time, the training interval is put at the last time of each window and generally is four or five times longer than the constraint length.  
      Repetition processing of conventional B calculation initializes the initial value of each training interval to “ 0 ” for each iterative decoding and performs calculation using reliability information of each window obtained in previous decoding processing.  
      Non-Patent Document 1: Claude Berrou, “Near Optimum Error Correcting Coding And Decoding: Turbo-Codes,” IEEE Trans. On Communications, Vol. 44, No 10, October 1996.  
     DISCLOSURE OF INVENTION  
      Problems to be Solved by the Invention  
      However, since conventional sliding window method has a long training interval, there is a problem that the calculation amount and memory capacity of a turbo decoder are large. In addition, since the length of the training interval is fixed, there is a possibility that deterioration of characteristic worsens as the coding rate increases, and there is a problem that the training interval must be long in order to maintain the characteristic.  
      It is therefore an object of the present invention to provide a decoding apparatus and a decoding method that reduce the calculation amount and memory capacity and prevent deterioration of characteristic at high coding rates.  
      Means for Solving the Problems  
      The decoding apparatus of the present invention employs a configuration having: a backward probability calculation section that divides a data sequence into a plurality of windows and calculates a backward probability per window using a backward probability at a predetermined time calculated in previous iterative decoding as an initial value in iterative decoding of this time; a storage section that stores the backward probability at predetermined time calculated by the backward probability calculation section; and a likelihood calculation section that calculates likelihood information using the backward probability calculated by the backward probability calculation section.  
      Advantageous Effect of the Invention  
      With the present invention, the backward probability is calculated using the backward probability at a predetermined time calculated in previous iterative decoding as the initial value for iterative decoding of this time, so that characteristic can be improved even when the training interval is short, and it is therefore possible to reduce the calculation amount and memory capacity and prevent deterioration of characteristic at high coding rates. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       FIG. 1  is a pattern diagram conceptually showing the repetition processing of conventional B calculation;  
       FIG. 2  is a block diagram showing the configuration of the turbo decoder according to Embodiment 1 of the present invention;  
       FIG. 3  is a block diagram showing the internal configuration of the element decoder;  
       FIG. 4  is a pattern diagram conceptually showing the repetition processing of B calculation according to Embodiment 1 of the present invention;  
       FIG. 5  is a diagram showing the decoding characteristic of the turbo decoder according to Embodiment 1 of the present invention; and  
       FIG. 6  is a pattern diagram conceptually showing the repetition processing of B calculation according to Embodiment 2 of the present invention. 
    
    
     BEST MODE FOR CARRYING OUT THE INVENTION  
      Embodiments of the present invention will be explained below in detail with reference to the accompanying drawings.  
     Embodiment 1  
       FIG. 2  is a block diagram showing a configuration of a turbo decoder according to Embodiment 1 of the present invention. In this figure, element decoder  101  executes decoding processing on systematic bit sequence Y 1  and parity bit sequence Y 2  with a priori value La 1 , which is reliability information transmitted from deinterleaver  105 , and outputs external value Le 1  to interleaver  102 . The external value indicates the increment of reliability by the element decoder.  
      Interleaver  102  rearranges external value Le 1  output from element decoder  101  and outputs the result to element decoder  104  as a priori value La 2 . Incidentally, decoding is not performed at element decoder  104  in the first iteration and therefore “0” is substituted for the a priori value.  
      Element decoder  104  receives as input a sequence in which systematic bit sequences Y 1  is rearranged at interleaver  103 , parity bit sequence Y 3  and a priori value La 2 , performs decoding processing and outputs external value Le 2  to deinterleaver  105 .  
      Deinterleaver  105  performs the operation of undoing the rearrangement by the interleaver upon external value Le 2  to restore the rearrangement by the interleaver and outputs the result to element decoder  101  as a priori value La 1 . By this means, iterative decoding is performed. After iterative decoding is performed from several times to over ten times, element decoder  104  calculates posteriori value L 2 , which is defined as the logarithmic posteriori probability ratio, and outputs the calculation result to deinterleaver  106 . Deinterleaver  106  deinterleaves the calculation result output from element decoder  104  and outputs the deinterleaved sequences to hard decision section  107 .  
      Hard decision section  107  performs hard decision with the deinterleaved sequences, thereby outputting decoded bit sequences. Error detection section  108  performs error detection with the decoded bit sequences and outputs the detection result.  
       FIG. 3  is a block diagram showing the internal configuration of element decoder  101 . Assume that element decoder  104  has the same internal configuration as element decoder  101 . Assume that decoding operation described below is performed in a window basis of a predetermined size.  
      First, systematic bit Y 1 , parity bit Y 2  and a priori value La 1  obtained from previous decoding result are input to transition probability calculation section  201 , and transition probability γ is calculated. The calculated transition probability γ is output to forward probability calculation section  202  and backward probability calculation section  203 .  
      Forward probability calculation section  202  performs the calculation of the above equation (3) with respect to the data sequence divided for per window using transition probability γ output from transition probability calculation section  201  and calculates forward probability α k (m). The calculated α k (m) is output to likelihood calculation section  205 .  
      Backward probability calculation section  203  performs the calculation(B calculation) of the above equation (4) with respect to data sequence divided per window using transition probability γ output from transition probability calculation section  201  and a value described below that is stored in memory  204 , which will be described later, and calculates backward probability β k (m). The calculated backward probability β k (m) is output to likelihood calculation section  205 . In addition, backward probability that is used as initial value for the next iterative decoding is output to memory  204 .  
      Memory  204  temporarily stores the backward probability of a predetermined time that is output from backward probability calculation section  203  and, when backward probability calculation section  203  performs iterative decoding, outputs the stored backward probability of a predetermined time in previous decoding to backward probability calculation section  203 . The predetermined time corresponds to the time at which the calculation starts in each window, in the next iterative decoding.  
      Likelihood calculation section  205  performs the calculation of the above equation (1) using forward probability α k (m) output from forward probability calculation section  202  and backward probability β k (m) output from backward probability calculation section  203  and calculates likelihood information.  
      Next, the sliding window method when B calculation is performed by a turbo decoder will be explained.  FIG. 4  is a pattern diagram conceptually showing repetition processing of B calculation according to Embodiment 1 of the present invention. Here, an explanation will be provided making the window size  32  and using three windows for ease of explanation. In this figure, in iteration number  1 , the window of time  0 - 31  is B# 0 , the window of time  32 - 63  is B# 1  and the window of time  64 - 95  is B# 2 . In addition, the training interval has a size of four and is put at the last time of each window.  
      In the B calculation in iteration number  1 , the calculation starts from the training interval of each window and proceeds in backward direction from higher time. Then, the backward probability of time  36  of window B# 1  is stored in memory  204  and the backward probability of time  68  of window B# 2  is stored in memory  204 .  
      In iteration number  2 , the backward probability of time  36  stored in memory  204  in iteration number  1  is made the initial value of the training interval of window B# 0  and the backward probability of time  68  stored in memory  204  is made the initial value of the training interval of window B# 1 . Thus, by using the backward probability obtained in previous decoding as the initial value of this time, it is possible to consider that previous decoding processing correlates to the training interval of this time and improve decoding accuracy.  
      In addition, in iteration number  2 , the window size of window B# 0  is made larger by one and the time is made  0 - 32 . The time of window B# 1  and window B# 2  is brought forward by one, and the time of window B# 1  is  33 - 64  and time of window B# 2  is  65 - 96 . In line with this, the time of the training interval also changes.  
      Assuming that the iteration number is i and generally represented, the B calculation is performed using the backward probability at a predetermined time of iteration number (i−1) as the initial value of the training interval of each window, expanding window B# 0  backward by time i and shifting window B# 1 , B# 2  . . . backward by time i.  
      Next, decoding characteristics when the above sliding window method is used will be explained.  FIG. 5  is a diagram showing decoding characteristics of a turbo decoder according to Embodiment 1 of the present invention. In this figure, the vertical axis is the bit error rate (BER) and the horizontal axis is Eb/NO. In addition, the solid line indicates decoding characteristics of the turbo decoder according to the embodiment and the dotted line indicates decoding characteristic of a conventional turbo decoder. Simulation parameters are as follows:  
      Modulation scheme (Data): QPSK  
      Coding rate: ⅚ 
      Spreading factor:  16   
      Channel model: AWGN (Additive White Gaussian Noise)  
      Training interval:  32   
      As can be seen from this figure, the decoding characteristic of the turbo decoder of the embodiment indicated by the solid line is excellent. Here, good decoding characteristic can be obtained although the coding rate is set high at ⅚, so that it is possible to prevent deterioration of characteristic even when the coding rate is high.  
      Here, comparison is made with a case when a training interval is  32 , however, as described above, the same decoding characteristic as the solid line can be achieved even when the training interval is  4 , so that it is possible to prevent deterioration even when the training interval is short.  
      Thus, according to the embodiment, the backward probability of a predetermined time of each window in previous decoding is made the initial value of the training interval of this time, and the window position is shifted backward each time decoding is iterated, so that the accuracy of the initial value improves every iteration, and it is possible to reduce the training interval and reduce the calculation amount and memory capacity. In addition, it is possible to prevent deterioration of characteristics at high coding rates.  
     Embodiment 2  
      A case will be described with Embodiment 2 of the present invention where the training interval is not provided. The configuration of the turbo decoder of the embodiment is the same as that of  FIG. 2 , and the configuration of the element decoder is the same as that of  FIG. 3 , and, therefore,  FIG. 2  and  FIG. 3  are incorporated by reference and detailed explanations thereof are omitted.  
       FIG. 6  is a pattern diagram conceptually showing the repetition processing of the B calculation according to Embodiment 2 of the present invention. Here, an explanation will be provided making the window size  32  and using three windows for ease of explanation. In this figure, in iteration number  1 , the window of time  0 - 31  is B# 0 , the window of time  32 - 63  is B# 1  and the window of time  64 - 95  is B# 2 .  
      In the B calculation in iteration number  1 , the calculation is performed from higher time to the backward direction, and the backward probability at time  32  of window B# 1  is stored in memory  204  and the backward probability at time  64  of window B# 2  is stored in memory  204 .  
      In iteration number  2 , the backward probability at time  32  stored in memory  204  in iteration number  1  is made the initial value of the training interval of window B# 0  and the backward probability at time  64  stored in memory  204  is made the initial value of the training interval of window B# 1 . In addition, the window size of window B# 0  is made larger by one and the time is made  0 - 32 . The time of window B# 1  and window B# 2  is brought forward by one, and the time of window B# 1  are  33 - 64  and the time of window B# 2  is  65 - 96 .  
      Assuming that iteration number is i and generally represented, the B calculation is performed using the backward probability at a predetermined time in iteration number (i−1) as the initial value at the start of operation in each window, expanding window B# 0  backward by time i and shifting window B# 1 , B# 2  . . . backward by time i.  
      Decoding characteristics when the above sliding window method is used shows substantially the same characteristic as that indicated by the solid line of  FIG. 5  of Embodiment 1, and it is possible to prevent deterioration of characteristic without providing the training interval.  
      Thus, according to this embodiment, the backward probability of a predetermined time in each window in previous decoding is made the initial value of the training interval of this time and the window position is shifted backward each time decoding is iterated, so that the accuracy of the initial value improves every iteration, it is possible to prevent deterioration of characteristics without providing a training interval and reduce the calculation amount and memory capacity.  
      Although cases of backward probability calculation have been described with the above embodiments, the present invention is by no means limited to this, and it is equally possible to calculate the forward probability using the forward probability of a predetermined time calculated in previous iterative decoding as the initial value in iterative decoding of this time. By this means, it is possible to reduce the training interval used in forward probability calculation and reduce the calculation amount and memory capacity.  
      In addition, regarding the amount of shifting the window, cases have been described above with the above embodiments where, when the iteration number is i, a shift is applied in proportion of time i. However, the present invention by no means limited to this, and it is equally possible to make the shift amount (i−1)×j Note that j is a positive number excluding 0.  
      A first aspect of the present invention provides a decoding apparatus having: a backward probability calculation section that divides a data sequence into a plurality of windows and calculates a backward probability per window using the backward probability at a predetermined time calculated in previous iterative decoding as an initial value in iterative decoding of this time; a storage section that stores the backward probability at a predetermined time calculated by the backward probability calculation section; and, a likelihood calculation section that calculates likelihood information using the backward probability calculated by the backward probability calculation section.  
      A second aspect of the present invention provides the decoding apparatus of the above-described aspect in which the backward probability calculation section shifts a window position backward in accordance with a number of iterations of decoding and calculates the backward probability.  
      With these configurations, by calculating the backward probability per window using the backward probability at a predetermined time calculated in previous iterative decoding as the initial value in iterative decoding of this time, the accuracy of the initial value improves as the number of iterations grows, so that it is possible to reduce the training interval and reduce the calculation amount and memory capacity. In addition, it is possible to prevent deterioration of characteristics at high coding rates.  
      A third aspect of the present invention provides the decoding apparatus of the above-described aspect in which the storage section stores the backward probability at the time next iterative decoding begins in accordance with the backward shift of the window position by the backward probability calculation section.  
      According to this configuration, in accordance with the backward shift of the window position by the backward probability calculation section, the storage section stores the backward probability at the time the next iterative decoding begins—that is to say, the initial value—so that, even when the window shifts and the calculation start point changes every iteration, the initial value of high accuracy is used, and it is possible to reduce the training interval and reduce the calculation amount and memory capacity.  
      A fourth aspect of the present invention provides the decoding apparatus having: a forward probability calculation section that divides a data sequence into a plurality of windows and calculates a forward probability per window using the forward probability at a predetermined time calculated in previous iterative decoding as an initial value in iterative decoding of this time; a storage section that stores the forward probability at a predetermined time calculated by the forward probability calculation section; and, a likelihood calculation section that calculates likelihood information using the forward probability calculated by the forward probability calculation section.  
      According to this configuration, by calculating a forward probability per window using the forward probability of a predetermined time calculated in previous iterative decoding as the initial value in iterative decoding of this time, the accuracy of the initial value improves as a number of iteration grows, so that it is possible to reduce a training interval and reduce the calculation amount and memory capacity. In addition, it is possible to prevent deterioration of characteristics at high coding rates.  
      A fifth aspect of the present invention provides a decoding method in which a data sequence is divided into a plurality of windows and a backward probability is calculated per window using the backward probability at predetermined time calculated in previous iterative decoding as an initial value of iterative decoding of this time.  
      With this method, by calculating the backward probability per window using the backward probability at a predetermined time calculated in previous iterative decoding as the initial value in iterative decoding of this time, the accuracy of the initial value improves as the number of iterations grows, so that it is possible to reduce the training interval and reduce the calculation amount and memory capacity. In addition, it is possible to prevent deterioration of characteristics at high coding rates.  
      The present application is based on Japanese Patent Application No. 2003-402218, filed on Dec. 1, 2003, the entire content of which is expressly incorporated by reference herein.  
     INDUSTRIAL APPLICABILITY  
      The decoding apparatus of the present invention calculates a backward probability using the backward probability at a predetermined time calculated in previous iterative decoding as initial value in iterative decoding of this time, thereby providing an advantage of reducing the calculation amount and memory capacity and preventing deterioration of characteristics at high coding rates, and is applicable to a turbo decoder and so forth.