Abstract:
A method and apparatus for turbo code decoding are provided to reduce memory consumption during calculation of state metrics. In an embodiment of a turbo code decoder, a natural recursion unit comprises a plurality of add-compare-select (ACS) units performing natural recursion operations to generate a state metric. The original state metric is then converted to a differential metric before being stored into a memory device. The differential metric contains less data than the state metric so that memory consumption is reduced. To restore the original state metric from the differential metric, a plurality of revival units operating in parallel is provided. Thereby, the state metric is reacquired from the differential metric, and a Log Likelihood Recursion (LLR) operation is accordingly performed by an LLR unit.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application claims priority of Taiwan Patent Application No. 96151435, filed on Dec. 31, 2007, the entirety of which is incorporated by reference herein. 
       BACKGROUND OF THE INVENTION 
       [0002]    1. Field of the Invention 
         [0003]    The invention relates to wireless communication, and more particularly to a turbo code decoding method. 
         [0004]    2. Description of the Related Art 
         [0005]    Wideband wireless communications infrastructure and applications have been widely developed in recent years. One such example is the WiMAX system. The WiMAX standard adopt the convolutional turbo code (CTC) as one of Forward Error Correction (FEC) mechanisms. CTC provides high performance for telecommunications, and there have been various CTC related enhancements and developments proposed as prior arts.  FIG. 1  shows a conventional turbo code decoder  100 , essentially comprising a pair of decoding units  110  and  120 . The decoding unit  120  receives a transmission signal #IN and a decoding result from the decoding unit  110  via an extrinsic information interleaver  102  and a data interleaver  104  to perform a recursive calculation. Symmetrically, through a deinterleaver  106 , the decoding unit  120  feeds back a decoding result to the decoding unit  110 , such that the decoding unit  110  performs a recursive calculation based on the decoding result and the transmission signal #IN. The transmission signal #IN is typically provided by a transmitter, and contains various channel effect and noise interferences. The recursive calculation processed in the decoding unit  110  and  120  may be one of various algorithms, such as a log-maximum a posterior (Log-MAP) algorithm, a Maximum Log-MAP algorithm or an Enhanced Maximum Log-MAP algorithm. The algorithms are also referred to as Soft-in-Soft-out (SISO) decoding algorithms. 
         [0006]      FIG. 2   a  shows a binary trellis structure of conventional state metrics. The horizontal axis t represents time or stage, and the vertical axis represents multiple states within each stage. As an example, state S 1  and S 2  corresponding to stages t i-1  and t i  are shown in  FIG. 2   a . Generally, three parameters are required for the SISO decoding algorithms, the forward probability α, backward probability β and branch probability γ for each state. Taking the state S 1  at stage t i-1  for example, the parameters are referred to as α 1 (t i-1 ) and β 1 (t i-1 ). The state S 1  at stage t i-1  may be switched to state S 1  or S 2  at stage t i , so that there are two branches each having a probability (or weighting factor) derivable from the received signals, denoted as γ(S 1 ,S 1 ) and γ(S 1 ,S 2 ). Identically, for the state S 2  at stage t i-1 , corresponding parameters comprise α 2 (t i-1 ), β 2 (t i-1 ), γ(S 2 ,S 1 ) and γ(S 2 ,S 2 ). According to MAP algorithm, the forward probability α of the state S 1  at stage t i  is obtained from the forward probabilities α and branch probabilities γ of the previous stage t i-1 , and the backward probability β of stage S 1  at stage t i-1  is obtained from the backward probabilities β and branch probabilities γ at the next stage t i . Detailed introductions for the algorithms are available in public journals, thus further description is omitted herein. To process the algorithms, in the decoding units  110  and  120 , however, significant memory space is required to buffer all the parameters related to a state metric. For example, each parameter may be a 10-bit float value, and if there are N states at each stage, and the state metric is a single binary trellis structure, there would be 2 N  branches to be managed. In other words, the memory requirement increases exponentially with the number of stages N. 
         [0007]      FIG. 2   b  shows a conventional Add-Compare-Selection (ACS) circuit adapted in the decoding units  110  and  120  of  FIG. 1 , used for recursively calculating the probabilities α and β for each state. As an example, if the forward probability α 1 (t i ) of state S 1  at stage t i  is to be calculated, all the associated states of a previous stage and branches therefrom would be considered. In this case, probabilities α 1 (t i-1 ) and α 2 (t i-1 ) are considered. First, the adder  202  adds the forward probability α 1 (t i-1 ) to the branch probability γ(S 1 ,S 2 ), and the adder  204  adds the forward probability α 2 (t i-1 ) to the branch probability γ(S 1 ,S 2 ). Thereafter, the added results are sent to the selector  210  for comparison, among which the larger value is output to the adder  206  to be added with a value from the lookup table  220  so that the forward probability α 1 (t i ) is generated. The lookup table  220  is a table comprising fixed values, providing logarithm corrections for the values output from the adders  202  and  204 . Since the lookup table  220  is a prior art, a detailed description is omitted herein. 
         [0008]    According to the aforementioned approaches, the probabilities α and β of each state are calculated by the ACS circuit  200 , so that the ACS circuit  200  and the memory device are recursively used. The total of parameters α and β therefore establish a state metric in the memory device, and when the state metric is established, a Log Likelihood Ratio (LLR) calculation is processed in the decoding units  110  and  120  to calculate a decoding result which has a maximum probability. 
       BRIEF SUMMARY OF THE INVENTION 
       [0009]    An exemplary embodiment of a turbo code decoder is provided. In which, a state processor comprises a plurality of Add-Compare-Selection (ACS) units operating concurrently to perform a natural recursion operation on an input sequence to generate a state metric, and to convert the state metric into a differential metric. A memory device is utilized for storage of the differential metric. A plurality of revival units are provided, operating concurrently to re-acquire the state metric from the differential metric. A likelihood calculator performs a log likelihood ratio (LLR) calculation based on the state metric. Specifically, the state metric is a radix-4 trellis structure or a radix-2 2  trellis structure. 
         [0010]    The state metric comprises a plurality of state vectors each associated with a stage, and each state vector comprises a plurality of states. The differential metric comprises a plurality of differential vectors each associated with a state vector. In each differential vector, at least one revival parameter represents a dominant state in the state vector, and a plurality of differential values are to re-acquiring other states from the dominant state. 
         [0011]    When the revival unit re-acquires the state metric, the dominant state is first re-acquired from the revival parameter, and the other states are re-acquired based on the dominant state and the differential values. 
         [0012]    The natural recursion operation utilizes a log-maximum a posterior (Log-MAP) algorithm, a Maximum Log-MAP algorithm or an Enhanced Maximum Log-MAP algorithm. The state may represent a forward probability or a backward probability, and the revival unit may recursively re-acquire each state vector in a forward order or a backward order. The likelihood calculator is utilized to derive log likelihood ratios (LLRs) among the state metric. 
         [0013]    Another embodiment provides a turbo code decoding method implemented in the aforementioned turbo code decoder, and a detailed description is given in the following embodiments with reference to the accompanying drawings. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0014]    The invention can be more fully understood by reading the subsequent detailed description and examples with references made to the accompanying drawings, wherein: 
           [0015]      FIG. 1  shows a conventional turbo code decoder; 
           [0016]      FIG. 2   a  shows a binary trellis structure; 
           [0017]      FIG. 2   b  shows a conventional ACS circuit; 
           [0018]      FIG. 3  shows a radix-4 trellis structure of state metrics; 
           [0019]      FIG. 4  shows an embodiment of a decoding unit  400 ; 
           [0020]      FIG. 5   a  shows an embodiment of an ACS circuit  500 ; 
           [0021]      FIG. 5   b  shows an embodiment of a revival unit  550 ; 
           [0022]      FIG. 5   c  shows an embodiment of a first selector according to  FIG. 5   b;    
           [0023]      FIG. 6   a  shows an embodiment of an ACS circuit  600 ; 
           [0024]      FIG. 6   b  shows an embodiment of a revival unit  650 ; and 
           [0025]      FIG. 7  is a flowchart of a track back calculation. 
       
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       [0026]    The following description is of the best-contemplated mode of carrying out the invention. This description is made for the purpose of illustrating the general principles of the invention and should not be taken in a limiting sense. The scope of the invention is best determined by reference to the appended claims. 
         [0027]      FIG. 3  shows a radix-4 trellis structure of state metrics, and an embodiment is described based thereon. Basically, a state metric comprises a plurality of state vectors corresponding to stages t 1  to t M , and each state vector comprises N states S 1  to S N . Taking the state S 1  at stage t k-1  for example, since the trellis is radix 4, there are four possible branches connecting the state S 1  to the next stage. Specifically, the pairs of states connected by the branches between two stages are previously defined in the trellis structure standards. In the embodiment, four branches initiated from the state S 1  at current stage are individually destined to states a, b, c and d at a next stage, each carrying a branch probability γ(S 1 ,a), γ(S 1 ,b), γ(S 1 ,c) and γ(S 1 ,d). Conversely, each state at a current stage may come from one of four states at a previous stage. For example, the state S 3  at stage t k  has four branches associated with four states A, B, C and D at a previous stage (not shown), each carrying a branch probability γ(A,S 3 ), γ(B,S 3 ), γ(C,S 3 ) and γ(D,S 3 ). Based on the MAP algorithm, the process to calculate the state metric is conclusively referred to as a natural recursion operation, with each stage element representing a forward probability or a backward probability. A proceeding Log Likelihood Ratio (LLR) calculation may only be performed when all the probability values are acquired. 
         [0028]      FIG. 4  shows an embodiment of a decoding unit  400  according to the invention. To reduce memory occupation, the decoding unit  400  is proposed to calculate the state metric for the decoding units  110  and  120 . The decoding unit  400  mainly comprises a state processor  402  and a likelihood calculator  404 . The state processor  402  comprises a plurality of ACS circuits  412  operating in concurrence, performing the natural recursion operation based on a transmission signal #IN to generate the state metric #Metrics. In the embodiment, the ACS circuit  412  converts the state metric #Metrics into a differential form, which is stored in the memory device  410  as a differential metric difference value #Diff so that memory occupation can be reduced. Before the likelihood calculator  404  performs an LLR operation, a plurality of revival units  414  are utilized to read the memory device  410  to re-acquire the state metric #Metrics from the differential metric difference value #Diff. 
         [0029]    In the decoding unit  400 , the algorithm adapted to perform the natural recursion operation may be one from the prior arts, such as a Log-MAP algorithm, a Maximum Log-MAP algorithm or an Enhanced Maximum Log-MAP algorithm, and the likelihood calculator  404  is utilized to calculate log likelihood ratios of all paths presented in the state metric. The decoding unit  400  is particularly adaptable for a state metric of a radix-4 trellis structure or a radix-2 2  trellis structure. 
         [0030]    There may be various circuit implementations to convert the state metric into a differential metric, and  FIG. 5   a  shows an exemplary embodiment of an ACS circuit  500 . Each state has a value, and through four adders  502 ,  504 ,  506  and  508 , the ACS circuit  500  adds four state values S P1 , S P2 , S P3  and S P4  respectively with corresponding branch values B 1 , B 2 , B 3  and B 4  to generate four candidates. Thereafter, three selectors  510 ,  520  and  530  are utilized to obtain a state value S C  corresponding to a state of a current stage. More specifically, the state value S C  is the largest value among the four candidate values. Conventionally, the state values S P1 , S P2 , S P3  and S P4  are then directly sent to the memory device for storage. In the invention, alternatively, the state values are not directly stored, but converted to difference values. For example, the selector  510  first compares the outputs from adders  502  and  504 , among which a larger value is selected and sent to the selector  530 , with their difference value #D 1  stored in the memory device  410 . Likewise, the selector  520  compares the outputs from adders  506  and  508 , passes the larger value to the selector  530 , and stores their difference value #D 2  in the memory device  410 . Furthermore, the selector  530  receives the two values sent from the selectors  510  and  520 , selects a larger value, and calculates their difference value #D3. In other words, the output from the selector  530  is the maximum of the four candidates. A lookup table  540  may be looked up for a logarithm correction value #C based on the difference values #D1, #D2 and #D3, and an adder  512  then adds the logarithm correction value #C to the maximum candidate to generate the state value S C . When all state values S C  of a current stage are acquired, the ACS circuit  500  can be recursively reused to calculate state values S C  of a next stage. In this way, every four state values are simplified into three differential values each carrying a sign bit, thus, it is possible to re-acquire the original state values from the three differential values by simple logics. In comparison to storage of four state values, memory occupation is significantly reduced by storing only three differential values. 
         [0031]      FIG. 5   b  shows an embodiment of a revival unit  550 . The revival unit  550  is basically symmetric to the ACS circuit  500 . One state value S C  and three difference values #D1, #D2 and #D3 are input to the revival unit  550 , thereby four state values of a previous stage S P1 , S P2 , S P3  and S P4  are re-acquired. First, the lookup table  545  is looked up for a logarithm correction value #C based on the difference values #D1, #D2 and #D3 stored in the memory device  410 . A subtractor  511  then subtracts the state value S C  by the logarithm correction value #C and sends the result to a selector  535 . Actually, the result is exactly the maximum of the four candidates mentioned in  FIG. 5   a . The selector  535  generates two intermediate values S M1  and S M2  from the maximum candidate based on the difference value #D3. As described in  FIG. 5   a , the maximum candidate is chosen from one of the intermediate values S M1  and S M2 , so in  FIG. 5   b , the selector  535  assesses one of the intermediate values S M1  and S M2  to be the maximum candidate, and the other one to be the maximum candidate minus the difference value #D3. The sign bit of the difference value #D3 determines which intermediate value should be assessed to be the maximum candidate. Based on the same logic, the selector  515  uses the difference value #D1 to re-acquire candidates S O1  and S O2  from the intermediate value S M1 , and the selector  525  uses the difference value #D2 to re-acquire candidates S O3  and S O4  from the intermediate value S M2 . A pair of subtractors  501  and  503  individually subtract the candidates S O1  and S O2  by the branch values B 1  and B 2  to re-acquire state values S P1  and S P2  at a previous stage, and a pair of subtractors  505  and  507  individually subtract the candidates S O3  and S O4  by the branch values B 3  and B 4  to re-acquire the state values S P3  and S P4  at a previous stage. 
         [0032]    There are various ways to implement the logic circuit, and  FIG. 5   c  shows an embodiment of the selectors  515 ,  525  and  535  mentioned in  FIG. 5   b . The selector  535  may comprise a pair of multiplexers  534  and  536 . The input is a base value #Y IN  and a difference value #D IN , and the outputs are #Y OUT1  and #Y OUT2 . One of the output values #Y OUT1  and #Y OUT2  is assessed to be the base value #Y IN , and another is the #Y IN  minus the difference value #D IN . The sign bit of the difference value #D IN  determines whether the #Y IN  should be output through the multiplexer  534  or the multiplexer  536 . The operator  532  may be capable of performing a specific operation, such as absolutizing the difference value #D IN  and subtracting the #Y IN  by the #D IN . 
         [0033]      FIG. 6   a  shows another embodiment of an ACS circuit  600 . When producing the state values S C  of a current stage, the adders  602 ,  604 ,  606  and  608  individually add the branch values B 1 , B 2 , B 3  and B 4  to the four state values S P1 , S P2 , S P3  and S P4  to generate four candidates. The candidates are sequentially sent to a comparison circuit  620  for cross comparison, and finally a flag #flag is generated to indicate which candidate is the maximum one. Simultaneously, the comparison circuit  620  calculates differences between the state values S P1  versus the S P2 , S P3  and S P4  to generate difference values #D1, #D2 and #D3. The difference values are then sent to a lookup table  630 , such that a logarithm correction value #C is looked up. On the other hand, the candidates are sequentially sent to a switch  610 , whereby the maximum candidate is picked and passed to an adder  612  based on the flag #flag. Thereby, the adder  612  adds the maximum candidate with the logarithm correction value #C to obtain the state value S C  of a current stage. In the embodiment, the memory device  410  stores the flag #flag, and the difference values #D1, #D2 and #D3. The state value S C  at a current stage may be reused as an input to calculate state values at a next stage. 
         [0034]      FIG. 6   b  shows an embodiment of a revival unit  650 , having a structure symmetric to the ACS circuit  600 . When a state value S C  of a current stage is input, four state values S P1 , S P2 , S P3  and S P4  of a previous stage can be re-acquired based on the flag #flag and the difference values #D1, #D2 and #D3. Firstly, a lookup table  635  is looked up for a logarithm correction value #C based on the difference values #D1, #D2 and #D3. A subtractor  611  then subtracts the state value S C  by the logarithm correction value #C to re-acquire the maximum candidate as mentioned in  FIG. 6   a . The subtractor  645  and selector  655  are used to re-acquire the candidate S O1 . The selector  655  determines the position where the maximum candidate is located based on the flag #flag. For example, if the maximum candidate is located at the topmost place, the candidate S O1  is assessed as the maximum candidate, so the selector  655  outputs a zero value to the subtractor  645 , such that the S O1  is output as the maximum candidate. Likewise, if the maximum candidate is located at the second place, the selector  655  uses difference value #D1 to be subtracted with the maximum candidate, such that the S O1  is output from the subtractor  645 . When the candidate S O1  is determined, other candidates S O2 , S O3  and S O4  can further be re-acquired by addition with the difference values #D1, #D2 and #D3 via the adders  613 ,  615  and  617 . The subtractors  601 ,  603 ,  605  and  607  then eliminate the branch values B 1 , B 2 , B 3  and B 4  from the candidates S O1 , S O2 , S O3  and S O4  to re-acquire the state values of a previous stage S P1 , S P2 , S P3  and S P4 . 
         [0035]    In the embodiment of the circuit, four states of a previous stage can be re-acquired from one state of a current stage. If a state vector of one stage comprises eight states, the re-acquisition process would be processed twice per stage. The branch associations between each stage are previously defined by trellis code specification, among which only two states are required to sufficiently cover all stage elements of the adjacent stage. Data required for each circuit may only comprise a flag #flag and three difference values, with one dominant state value reused from a previous stage. Memory occupation is thereby significantly reduced in comparison to the prior art. A plurality of circuits can be provided to operate as parallel pipelines, and the number of circuits may be dependent on the number of states in each state vector. 
         [0036]      FIG. 7  is a flowchart of a trace back operation. The embodiments can be summarized as follows. In step  701 , a natural recursion operation is performed to generate a state metric based on an input sequence. In step  703 , the state metric is converted into a differential metric and stored in a memory device. In fact, the conversion is progressively processed, and the parameters may comprise probabilities α and β as specified in the MAP algorithm. In step  705 , a revival operation is processed, whereby the differential metric is read from the memory device to re-acquire the state metric. Although some embodiments of circuits are provided, the invention is not limited thereto. In step  707 , a log likelihood ratio calculation is processed based on the state metric after the re-acquisition is complete. In practice, the log likelihood ratio calculation may also be progressively processed while the re-acquisition is in process. In conclusion, the invention subsequently reduces memory occupation by 25%. 
         [0037]    While the invention has been described by way of example and in terms of preferred embodiment, it is to be understood that the invention is not limited thereto. To the contrary, it is intended to cover various modifications and similar arrangements (as would be apparent to those skilled in the art). Therefore, the scope of the appended claims should be accorded the broadest interpretation so as to encompass all such modifications and similar arrangements.