Patent Publication Number: US-7594161-B2

Title: Map decoding

Description:
PRIORITY 
     This application claims priority under 35 U.S.C. § 119 to an application entitled “MAP DECODING” filed in the Great Britain Property Office on Sep. 10, 2004 and assigned Serial No. 0420145.5, the contents of which are herein incorporated by reference. 
     BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     This invention relates to decoding. More particularly, this invention relates to decoding using the maximum a Posteriori (MAP) decoding technique. Particularly but not exclusively, the invention is used for decoding turbo encoded signal, and particularly but not exclusively in mobile telecommunication systems. 
     2. Description of the Related Art 
     Turbo codes are widely used in challenging communications environments such as mobile telephony because they offer a transmission performance which approaches the Shannon limit in noisy conditions. In turbo coding, two recursive systematic convolutional (RSC) coders are provided in parallel, receiving the same information bits but in different orders. 
     The output of the turbo coder is the systematic information (the original bit stream) which forms the input to one of the RSC coders, together with the parity outputs of each of the RSC coders. This corresponds essentially to two stochastic processes running on the same input data. At the receiver end, a turbo decoder can operate by independently estimating each of the two processes with a decoder, then refining the estimates by iteratively sharing information between the two decoders. In other words, the output of one decoder can be used as a-priori information by the other decoder. 
     Each decoder therefore produces a soft output indicating the likelihood that the input bit was a one, referred to as a “log likelihood ratio” (LLR). 
     Each decoder is arranged to accept the received bit stream (comprising systematic imparity information) together with a-priori information (in the form of an LLR or data derived from it) from the other decoder, and generate an output (which can itself be fed to the other decoder). 
     The calculations which are performed during each iteration are described in, for example, “Implementation of a 3GSP Turbo Decoder on a Programmable DSP Core”, James G. Harrison, 3DSP Corporation White Paper, presented at the Communications Design Conference, San Jose, Calif., Oct. 2, 2001 (www.3dsp.com/pdf/3dspturbowhitepaper.pdf). Briefly, it is not feasible to implement MAP decoding in real time for most commercially desirable data rates at present. Accordingly, simplifications of the MAP algorithm have been sought. 
     In one, referred to as log-MAP, the simplification is performed by eliminating the substantial number of exponentiation and multiplication operations required by operating in the logarithm domain, so that multiplications become additions and exponentiation is not required. A problem with the log-MAP process is that it is necessary to compute the log of the sum of exponentials. The Jacobian formula provides the following alternative:
 
log( e   δ     1     +e   δ2 =max(δ 1 ,δ 2 )+log(1+ e   −|δ     2     −δ     1     | )  (1)
 
     The first term, the Max (a, b) function, is a single instruction for DSP&#39;s (digital signal processors) and is easily performed in any other type of processing device. However, the second term (the correction term) must still be computed. For this, various approaches have been proposed. The simplest approach is to ignore the term altogether. This is referred to as the Max-log-MAP algorithm. It provides a reasonable approximation where (a) is much larger than (b) or vice versa, but leads to errors where they are of similar magnitudes. 
     The above-mentioned paper by Harrison proposes to use a lookup table of eight entries to approximate the second term. In the paper “Linearly Approximated Log-MAP Algorithms for Turbo Decoding”, Cheng &amp; Ottoson, a linear approximation (i.e. a first order approximation, employing a single coefficient) is used which is stated to be particularly suitable for wide band CDMA (WCDMA). 
     U.S. Pat. No. 6,760,390 (Desai et al) takes a different approach: instead of using the Jacobian substitution to replace the logarithm with the sum of the exponents of several numbers, it uses an alternative expression comprising a first term consisting of the average of the numbers, followed by a second term which must be computed 
     This second term, like the one above, involves taking the logarithms of exponents. It is therefore approximated by using a Taylor series (a power series). To make calculation in real time possible, the Taylor series is truncated after a number of terms which, since the exponential function converges slowly, means that it is of limited accuracy. 
     Although in these three approaches some attempt is made to take account of the second term, there is inevitably some sacrifice of accuracy for computational efficiency to a greater or lesser extent. The present invention is intended to provide an alternative implementation of the log-MAP algorithm with good accuracy which can be implemented in real time. Under some circumstances, it will provide a more accurate decoding than the above approaches. 
     In another aspect, the present invention is intended to provide an approximation which is straightforward to implement, and scalable. These aspects are defined in the claims. 
     In a first aspect, the invention provides a log-MAP type decoder in which the correction term is computed by using a Padé approximant or continued fraction. In each case, the operation includes at least one division stage, as will be clear from what follows, and in contradistinction to the above-referenced prior art. 
     Padé approximants and their relation to continued fractions are discussed in H. Padé, ‘Sur la représentation approchée d&#39;une fonction par des fractions rationnelles’, Annales Scientifiques de l&#39;ENS, 1892, and H. Padé, ‘Mémoire sur les développements en fractions continues de la fonction exponentielle, pouvant servir d&#39;introduction à la théorie des fractions continues algébriques’, Annales Scientifiques de l&#39;ENS, 1899. 
     SUMMARY OF THE INVENTION 
     In general, a Padé approximant based on a given number of coefficients (i.e. given a level of complexity) gives a more accurate result than the equivalent series expansion (e.g. McLaurin or Taylor series expansion). For a given level of complexity then, the present invention provides more accurate decoding than the solution proposed in U.S. Pat. No. 6,760,390. It is likewise considerably more accurate than the lookup table or linear approximations described in the above disclosed prior art. 
     Padé reveals that the approximants which bear his name are closely related to continued fractions (CF). Continued fractions form another alternative method of approximating functions and can be seen as a special case of Padé approximants. In another aspects, the present invention provides another alternative method of approximating functions by using a repeating continued fraction implementation block (hardware or software). 
     This aspect of the invention likewise provides good accuracy, and additionally is particularly suited for hardware or DSP software implementation, since it consists of simple repetitive division operations. It therefore enables flexible and scalable implementations. Further, increasing the number of such blocks allows incremental increases of accuracy, so that where there is extra time during decoding, the accuracy can be improved. 
     The above described aspects may, in a preferred embodiment, be used adaptively; particularly the decoder may test the difference between the two numbers (i.e. vertical line a-b vertical line) and employ the above described aspects only where this difference is relatively small. Where the difference is relatively large, the second term can simply be ignored and, for speed the Max (a, b) term alone can be used. 
     Preferably, the invention is utilised in a mobile telecommunication system; it may be either at the user terminal end or at the system end, which is particularly useful in the former case where the computation hardware available is more constrained. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       Other aspects, embodiments and preferred features will be apparent from the following description and claims. Embodiments of the invention will now be illustrated, by way of example only, with reference to the accompanying drawings in which: 
         FIG. 1  is a block diagram of the elements of a communications system according to an embodiment of the invention; 
         FIG. 2  is a block diagram of the elements of a user equipment mobile terminal forming part of  FIG. 1 ; 
         FIG. 3  is a diagram of a Parallel Concatenated Convolutional Coder (Turbo Coder); 
         FIG. 4  is a diagram of an iterative Turbo-Decoder (MAP decoder); 
         FIG. 5  is a flow diagram of the process of iterative Turbo-Decoding; 
         FIG. 6  is a plot of analytical function values against approximated function values according to the first embodiment; 
         FIG. 7  is a plot of probability density function (PDF) against relative error for a prior art 1-MAP decoder; 
         FIG. 8  corresponds to  FIG. 6  and is a plot of probability density function (PDF) against relative error for a prior art MAX Log-MAP decoder; 
         FIG. 9  is a plot of probability density function (PDF) against relative error for the analytic values of a MAP decoder according to the first embodiment; 
         FIG. 10  is a plot of probability against error for a decoder according to the first embodiment as against a MAX Log-MAP decoder; 
         FIG. 11  is a plot of CDF against error for a decoder according to the first embodiment as against a MAX Log-MAP decoder; 
         FIG. 12  is a plot of Bit Error Rate (BER) against noise for different numbers of iterations (1-4) for the MAX*-Log-MAP decoder; 
         FIG. 13  is a plot of Bit Error Rate (BER) against noise for different numbers of iterations (1-4) for the MAX-Log-MAP decoder; 
         FIG. 14  is a plot of Bit Error Rate (BER) against noise for different numbers of iterations (1-4) for the approximated Log-MAP decoder according to a first embodiment; 
         FIG. 15  is a plot of Bit Error Rate (BER) against noise for 4 iterations for the present embodiment against the prior art; 
         FIG. 16  is a block diagram of a continuous fraction evaluation unit according to a second embodiment of the invention; and 
         FIG. 17  is a block diagram of a cascade of continuous fraction evaluation units according to the second embodiment. 
     
    
    
     PREFERRED EMBODIMENTS OF THE INVENTION 
     Preferred embodiments of the present invention will be described herein below with reference to the accompanying drawings. In the following description, well-known functions or constructions are not described in detail since they would obscure the invention in unnecessary detail. 
     Referring to  FIG. 1 , a communication system such as a mobile telephony system comprises a plurality of user equipment (UE) such as mobile terminals  300   a ,  300   bb , in radio communication with a base station  100 , provided within a cell, and having a fixed link connection to a backbone network (such as an IP network) via a switch computer  200 . The IP backbone network will not further be discussed since it is of conventional type. 
     It will be clear to the skilled person that, other than the modulation and RF components, the blocks making up the embodiment at the base station and the mobile terminals comprise suitably programmed digital signal processor devices (DSPs) or ASICs executing signal processing. 
     In both the base station and the terminals, in order to receive data transmitted over the communications link, the received data are first demodulated, then processed in error control decoders using the redundancy to correct any errors occurred in transmission, such that the data are then available at the receiver&#39;s output port (for example for display or audio reproduction). 
     Referring to  FIG. 2 , the mobile terminal  300  comprises a control unit  302  such as a microcontroller, a power supply  304  such as a rechargeable battery, a user interface  306  such as a touch screen. A radio receiver section  312  receives and amplifies radio signals from the network, which are demodulated to base band by demodulator section  314 . 
     Channel decoding is performed by a channel decoder  316 , with which the present invention is principally concerned as discussed further below. The decoded data is then passed to an output processing unit  318  in which higher layer processing is performed, for example to remove source coding, reassemble packets and so on, and the output data from the output processing unit  318  is supplied either to the user interface  306  for display, to the control unit  302 , or to an output port assumption by an external device. 
     For completeness, the transmit side components are also shown, comprising a data input processing device  328  applying source coding and packetising; a channel coder  326  for applying channel coding such as turbo coding; a modulator  324  for applying modulation such as quadrature amplitude modulation and modulating at RF, and an RF transmitter device  322  comprising a power amplifier for transmitting the modulated radio signal. 
     The channel coding and decoding units  316 ,  326  may be provided by a suitably programmed digital signal processing devices or by a specially designed hardware chip set. The same is true of the input and output processing devices  318 ,  328 . All of these may be integrated into a single unit, suitably programmed, and comprising a digital signal processor with associated RAM flash memory, storing a control program and scratch calculations performed during the operation of the terminal. 
     The base station  100  includes components generally equivalent to the components  312 - 318 ,  322 - 328  for performing transmission and reception, and will not be further discussed here. 
     Turbo-Coding &amp; De-Coding 
     Referring to  FIG. 3 , the channel coder  326  of the user equipment  300 , and the equivalent channel coder of the base station  100 , comprise a turbo coder consisting of an input port  3262  which accepts an input bit stream; a pair of equivalent recursive systematic convolutional (RSC) encoders  3264   a ,  3264   b  fed in parallel from the input port  3262 ; an interleaver  3266  in the path between the input port and one of the RSC encoders  3264   b ; a puncturing unit  3268  for varying the coding rate by selectively removing bits from the output stream; and an output port  3270  comprising a multiplexer for multiplexing into a single bit stream the input bit stream from the input port  3262 , and the punctured output streams of the encoders  3264   a ,  3264   b  via the puncturing unit  3268 . 
     This corresponds to the parallel concatenation of two recursive systematic convolutional (RSC) encoders. These encoders are separated by one interleaving module π. As these encoders are processing the same input bits stream x s , this scheme is referred to as “parallel concatenated convolutional codes” (PCCC). 
     Each RSC component is composed of two generator polynomials, namely feedback and feedforward polynomials, respectively g 1  (D) and g 2  (D). Thus, two parity check sequences are generated, namely x 1   p , and x 2   p . 
     The turbo-decoding process which takes places in the receivers at the base station and the terminals uses the basic iterative scheme. Again two component decoders, called Soft Input Soft Output (SISO) decoders D 1  and D 2 , are serially concatenated via an interleaving process. The major key feature of this iterative process, is that the extrinsic information delivered by one SISO decoder, feeds the following SISO decoder as a priori information for decoding information bits. The feedback loop iteratively improves the performance of this scheme. 
     Referring to  FIG. 4 , the decoder  316  comprises an input port  3162  at which the received modulated samples (represented as multibit data) are demultiplexed into a data stream and two separate parity streams. Each parity stream is fed in parallel to a respective soft input soft output (SISO) decoder  3164   a ,  3164   b . An interleaver  3166  of depth equivalent to the interleaver  3266  decoder lies in the path from the input port  3162  to the second decoder  3164   b.    
     Each of the coders  3164  has four ports. A first input port  31642  (shown only on the first decoder  3164   a  for clarity) accepts the observation samples from the input port  3162  and a second  31644  accepts a-priori information from an extrinsic information output port  31646  of the other decoder. Finally, an a posteriori output port supplies decoded output bits from each decoder  3164  to a combiner and thresholder  3168  at which the decoded bit-stream is made available as a series of binary bits. 
     In the output path from the second decoder  3164   b  to the output port  3168  is an output deinterleaver  3169 . 
     Interconnecting the output port  31646  of the first decoder and the a-priori input port  31644  of the second decoder  3164   b  is an interleaver  3171 . Conversely, interconnecting the output port  31646  of the second decoder  3164   b  with the a-priori input port  31644  of the first decoder  3164   a  is a deinterleaver  3173 . 
     Referring to  FIG. 5 , an overview of the operation of the decoder of  FIG. 4  will be given. 
     Step  1002 , a new demodulated sample (in the form of a 32 bit value from the demodulator) is received at the input port. 
     In step  1006 , each decoder computes and stores the branch metrics (often referred to as gamma values) for all trellis branches. The skilled person is aware that a trellis diagram is a representation of the different states applied by the modulator over a succession of bit periods (equal in length to the length of the interleaver plus a predetermined number of periods for flushing the encoder back to an initial state). The decoder attempts to trace the path through the trellis taken by the signal by calculating the state transition probability. 
     The branch metrics (gamma values) are calculated based on the distance between the hard coder values and the received values from the demodulator, taking into account the channel noise variants, multiplied by the a-priori input from the other decoder. 
     After computing and storing the branch metrics, in step  1008 , each decoder performs a forward recursion on the trellis by computing forward (alpha) probabilities for each node on the trellis. The alpha values are the sum of the previous alpha multiplied by the branch metric along each branch from the two previous nodes to the node in question. 
     In step  1010 , each decoder performs backward recursion to calculate backwards (beta) probabilities for each node, similarly to the forward recursion but starting at the end of the trellis and going backward. 
     In step  1012 , the log likelihood ratio (LLR) for each time t is calculated as the sum of the products of the alphas, betas and gammas at that time for each branch associated with a one value in the encoder, divided by the sum of the products of the alphas, betas and gammas for each branch associated with a zero. 
     In step  1016 , the decoders determine whether the maximum number of iterations (for example, four iterations), Niter, has been reached. If not, then in step  1018  each decoder calculates extrinsic information to be fed from each coder to the other is calculated as the difference between the LLR and the input probability estimate and in step  1020  outputs the extrinsic information at its output port. 
     In step  1022 , each of the two decoders accepts a new a-priori value from the other decoder. 
     When all iterations have been complete (step  1016 ) the output device thresholds the log likelihood ratio outputs of the two decoders to form the decoded output bit. If the bit rate is sufficiently slow, the test  1016  may determine whether the decoded outputs have converged, rather than applying a limited number of iterations. 
     Within the forward and backward recursion steps  1008 ,  1010  in particular, the calculation of the alpha and beta probabilities involves the approximation to the log of the sum of the exponentials of plural numbers, as discussed above. In other respects, the process described in relation to  FIG. 4  is entirely conventional and well known to the skilled person. At this stage, therefore the present embodiment uses the approximation based on Padé approximants which will be described below. First, the necessary mathematical relationships will be laid out. 
     The MAP algorithm, given below, represents the optimal soft-output processing: 
                     Λ   ⁡     (     c   t     )       =     log   ⁢           [         ∑       (     l   ,     l   ′       )     ∈     B   t   1         ⁢         α     t   -   1       ⁡     (     l   ′     )       ·       γ   t   1     ⁡     (       l   ′     ,   l     )       ·       β   t     ⁡     (   l   )               ∑       (     l   ,     l   ′       )     ∈     B   t   0         ⁢         α     t   -   1       ⁡     (     l   ′     )       ·       γ   t   0     ⁡     (       l   ′     ,   l     )       ·       β   t     ⁡     (   l   )             ]             (   2   )               
This computation is performed by the forward-backward algorithm.
 
In step  1018 , the extrinsic information to be fed from each coder to the other is calculated as the difference between the LLR and the input probability estimate.
 
Max-Log-MAP Algorithm
 
To reduce the complexity, the log-domain is used.
   γ   t   i ( l′,l )=log [γ t   i ( l′,l )]  (3)   α   t ( l )=log [α t ( l )]  (4)   β   t ( l )=log [β t ( l )]  (5) 
Then the soft-output expression (i.e. the LLR) becomes:
 
                     Λ   ⁡     (     c   t     )       =     log   ⁢           [         ∑       (     l   ,     l   ′       )     ∈     B   t   1         ⁢     ⅇ           α   _       t   -   1       ⁡     (     l   ′     )       +         γ   _     t   1     ⁡     (       l   ′     ,   l     )       +         β   _     t     ⁡     (   l   )                 ∑       (     l   ,     l   ′       )     ∈     B   t   0         ⁢     ⅇ           α   _       t   -   1       ⁡     (     l   ′     )       +         γ   _     t   0     ⁡     (       l   ′     ,   l     )       +         β   _     t     ⁡     (   l   )               ]             (   6   )               
Now, the complexity reduction is obtained by means of the following approximation (the Jacobian relation, with the correction term omitted):
 
                     log   ⁢           [       ∑     i   =   1     n     ⁢     ⅇ     δ   i         ⁢           ]     ≈       max   i     ⁢     {     δ   i     }               (   7   )               
This reduces the complexity considerably, as the previous soft-output reduces to:
 
                     Λ   ⁡     (     c   t     )       ≈         max   l     ⁢     [           γ   _     t   1     ⁡     (       l   ′     ,   l     )       +         α   _       t   -   1       ⁡     (     l   ′     )       +         β   _     t     ⁡     (   l   )         ]       -       max   l     ⁢     [           γ   _     t   0     ⁡     (       l   ′     ,   l     )       +         α   _       t   -   1       ⁡     (     l   ′     )       +         β   _     t     ⁡     (   l   )         ]                 (   8   )               
However, this complexity reduction works only by impacting the performance—the Bit Error Rate (BER) performance falls.
 
Log-MAP Algorithm
 
This version is an extension of that above.
 
So the previous approximation is applied, but additionally with a correction function:
 log( e   δ     1     +e   δ2 )=max(δ 1 ,δ 2 )+log(1+ e   −|δ     2     −δ     1     | )  (9) log( e   δ     1     +e   δ2 )=max(δ 1 ,δ 2 )+ƒ c (|δ 2 −δ 1 |)  (10) 
with ƒ c (x)=log(1+e −x ). The term (x) corresponds to the absolute difference between the two values.
 
For some summation with more terms, the following recursive algorithm can be used:
 
Let&#39;s note first
 
                       Δ     n   -   1       =       ∑     k   =   1       n   -   1       ⁢           ⁢     ⅇ     δ   k           ,           (   11   )               
To process log
 
             [           ⁢                   ∑     k   =   1     n     ⁢           ⁢     ⅇ     δ   k         ]     =       log   ⁢           [         ∑     k   =   1       n   -   1       ⁢           ⁢     ⅇ     δ   k         +     ⅇ     δ   n         ]     =     log   ⁢           [       Δ     n   -   1       +     ⅇ     δ   n         ]         ⁢                   (   12   )                 
So, from the above equations this leads to the following relation:
 log [Δ n ]=max(log [Δ n−1 ],δ n )+ƒ c (|log [Δ n−1 ]−δ n |)  (13) log [Δ n ]=max(  δ   n−1 ,δ n )+ƒ c (|  δ   n−1 −δ n |)  (14) 
Where Δ n−1 =e   δ       n−1   , or equivalently log [Δ n−1 ]=  δ   n−1    
Finally, with this notation:
   δ   n =max(  δ   n−1 ,δ n )+ƒ c (|  δ   n−1 −δ n |)  (15) 
Padé Approximant
 
Now follow some details about the Padé approximants theory. To approximate the following McLaurin series:
 
                     A   ⁡     (   x   )       =       ∑     j   =   0       +   ∞       ⁢           ⁢       c   j     ·     x   j                 (   16   )               
One approximation method is the use of special rational functions, called Padé approximants, and defined as the following:
 
                         R     L   /   M       ≡     [     L   /   M     ]       =         P   L     ⁡     (   x   )           Q   M     ⁡     (   x   )           ⁢     
     ⁢   Where           (   17   )                   P   L     ⁡     (   x   )       =       a   0     +       a   1     ·   x     +   …   +       a   L     ·     x   L                 (   18   )                   Q   M     ⁡     (   x   )       =     1   +       b   1     ·   x     +   …   +       b   M     ·     x   M                 (   19   )               
It is therefore seen that they correspond to the ratio of two power series, P and Q. These series may contain different numbers of terms (i.e. be of different orders). The order of the Padé approximation is the sum of the orders of the series—for example, if the numerator series is third order and the denominator series is second order, then the Padé approximation is fifth order.
 
Finally, the approximation reaches the following target:
   A ( x )=[ L/M]+O ( x   L+M+1 )  (20) 
Approximation of Logarithm Function
 
The aim in this embodiment is to provide an accurate, and low complexity, approximation to the correction function used within the Log-MAP algorithm above which is in the form ƒ c (x)=log(1+e −x ), in order to both reduce the overall complexity of the decoder, whilst maintaining a good performance.
 
We will thus use the two following Padé Approximants:
 
e.g. for order 3,
 
                       exp     1   /   2       ⁡     (   x   )       =       6   +     2   ·   x         6   -     4   ·   x     +     x   2                 (   21   )                   log     2   /   1       ⁡     (     1   +   x     )       =     x   ·     [       6   +   x       6   +     4   ·   x         ]               (   22   )               
After some basic manipulations:
 
     
       
         
           
             
               
                 
                   
                     log 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       ( 
                       
                         1 
                         + 
                         
                           e 
                           x 
                         
                       
                       ) 
                     
                   
                   ≅ 
                   
                     
                       [ 
                       
                         
                           6 
                           + 
                           
                             2 
                             · 
                             x 
                           
                         
                         
                           6 
                           - 
                           
                             4 
                             · 
                             x 
                           
                           + 
                           
                             x 
                             2 
                           
                         
                       
                       ] 
                     
                     · 
                     
                       [ 
                       
                         
                           
                             6 
                             · 
                             
                               x 
                               2 
                             
                           
                           - 
                           
                             22 
                             · 
                             x 
                           
                           + 
                           42 
                         
                         
                           
                             6 
                             · 
                             
                               x 
                               2 
                             
                           
                           - 
                           
                             16 
                             · 
                             x 
                           
                           + 
                           60 
                         
                       
                       ] 
                     
                   
                 
               
               
                 
                   ( 
                   23 
                   ) 
                 
               
             
           
         
       
     
     The desired correction function (of the absolute difference between the two values) to add to the maximum of the two values is therefore calculated in this embodiment using the above relation, involving simple multiplication/division and addition/subtraction operations and a small number of simple integer coefficients. 
     As distinct from conventional expansion series which employ (or are resolvable to) multiplication and addition of coefficients and powers of the absolute difference value, the present embodiment necessarily involves division operations since the approximation involves the ratio of two power series. 
     It will now be clear that, in the steps in  FIG. 4  where the alpha, beta and gamma values are calculated, in each case the present embodiment calculates a first term, comprising the maximum of the values, calculates the absolute difference between the two values, and calculates a second, correction, term, from the absolute difference, using Equation (23). 
     Resulting Performance of First Embodiment 
       FIG. 6  shows the estimated error introduced when applying the Padé approximation of this embodiment instead of the actual correction function (which, of itself, is time-consuming to calculate). Note from  FIG. 6  that the accuracy appears adequate, and the error increases only from 2.5.
 
Estimation of Error in Prior Art.
 
When using the full logarithmic correction function of Equation (1), the optimal probability density function (PDF) of  FIG. 7  would be obtained. Now, applying the same technique, when estimating log of a sum of exponentials, with random values, the probability density function (PDF) of  FIG. 8  would be obtained when applying only the prior art max-log-MAP algorithm of Equation (7). Clearly, this is much worse than that of  FIG. 7 ; it is one-sided, and has a wider band.
 
Estimation of Error with Padé Based Aproximant According to this Embodiment.
 
The same error distribution for the present embodiment is shown in  FIG. 9 . Obviously, the distribution is considerably better than that of  FIG. 8 . The difference is emphasised by the comparison shown in  FIG. 10 . The related CDF is depicted in  FIG. 11 .
 
Bit Error Rate (BER) Assessment
 
Log-MAP Algorithm (MAX*) Turbo-Decoding
 
       FIGS. 12 to 15  show that the new decoder has a somewhat similar performance to the Log-MAP (MAX*), and considerably better performance than the simple MAP algorithm. Thus, this embodiment offers a good, low-complexity (low order) yet high accuracy approximation to the optimal method of applying the log-MAP decoding algorithm. 
     From the  FIG. 15  full comparison, it is clear that the complexity reduction obtained by means of the use of rational approximants of Padé, has nonetheless maintained a good performance. That means that this technique could be a good candidate for future 4G receiver implementation of turbo-decoding scheme. 
     Second Embodiment 
     The above embodiment describes the use of the Padé approximants; for example, the third order approximant described in equation (23). In this embodiment, however, the use of the closely related continued fraction approximation technique is described. Padé&#39;s work explain the close relationship between Padé approximants and continued fractions, and shows how to convert between one representation and the other. 
     In this embodiment, continued fraction are employed firstly to obtain the same level of accuracy as the first embodiment, but secondly for the implementation advantages which will be described below. 
     By way of an example, the exponential function will be reviewed here in view of its very low convergence when represented as a McLaurin or Taylor series (so that it is poorly modelled by such series unless a large number of coefficients are provided). 
     It can be found that Padé approximants have an explicit representation given below: 
                       P   L     ⁡     (   x   )       =       ∑     k   =   0     L     ⁢             (     L   +   M   -   k     )     !     ·     L   !             (     L   +   M     )     !     ·     k   !     ·       (     L   -   k     )     !         ·     x   k                 (   24   )                   Q   M     ⁡     (   x   )       =       ∑     k   =   0     M     ⁢               (     L   +   M   -   k     )     !     ·     M   !             (     L   +   M     )     !     ·     k   !     ·       (     M   -   k     )     !         ·       (     -   1     )     k       ⁢     x   k                 (   25   )               
It can be shown that the continued fraction expansion of the exponential function can be described by the sequence of following matrices:
 
                     (           A   n           B   n               C   n           D   n           )     =       ∏     h   =   0     n     ⁢           ⁢     [             (       2   ⁢   h     +   1     )     +   x           (       2   ⁢   h     +   1     )               (       2   ⁢   h     +   1     )             (       2   ⁢   h     +   1     )     -   x           ]               (   26   )               
We will thus derive the continued fraction of the following approximant:
 
                                    (27)                   exp     1   /   2       ⁡     (   x   )       =       6   +     2   ·   x         6   -     4   ·   x     +     x   2                                                       0   1   2                                                 0   +1   −⅔   +⅙           1   +1   +⅓   0           2   −1   +⅙   0           3   −½   0   0           4   − 1/12   0   0           5   0   0   0                        
Therefore the decomposition in continued fractions can be straightforwardly re-written as the standardized expression:
 
                       Exp     [     1   /   2     ]       ⁡     (   x   )       =     [     0   ;     1   1     ;       -   x     1     ;           -   1     /   2     ·   x       -   1       ;           -   1     /   12     ·   x         -   1     /   2         ]             (   28   )               
For the purpose of the new design implementation to be described, this can be written as:
 
                       Exp     [     1   /   2     ]       ⁡     (   x   )       =     1     1   -     x     1   -         1   /   2     ·   x         -   1     -         1   /   12     ·   x         -   1     /   2                           (   29   )               
Or after basic divisions, and algebraic manipulations:
 
     
       
         
           
             
               
                 
                   
                     
                       
                         Exp 
                         
                           [ 
                           
                             1 
                             / 
                             2 
                           
                           ] 
                         
                       
                       ⁡ 
                       
                         ( 
                         x 
                         ) 
                       
                     
                     = 
                     
                       1 
                       
                         1 
                         + 
                         
                           
                             
                               α 
                               2 
                             
                             ⁢ 
                             x 
                           
                           
                             1 
                             + 
                             
                               
                                 
                                   α 
                                   3 
                                 
                                 ⁢ 
                                 x 
                               
                               
                                 1 
                                 + 
                                 
                                   
                                     α 
                                     4 
                                   
                                   ⁢ 
                                   x 
                                 
                               
                             
                           
                         
                       
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     
                       
                         where 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         
                           α 
                           2 
                         
                       
                       = 
                       
                         - 
                         1 
                       
                     
                     ; 
                     
                       
                         α 
                         3 
                       
                       = 
                       
                         1 
                         2 
                       
                     
                     ; 
                     
                       
                         α 
                         4 
                       
                       = 
                       
                         - 
                         
                           1 
                           6 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   30 
                   ) 
                 
               
             
           
         
       
     
       FIG. 16  shows a continued fraction evaluation unit according to the present invention. It comprises three input terminals,  502 ,  504 ,  506  and an output terminal  508 . The lower two input terminals  504 ,  506  are connected to an adder  510 . A divider  512  is provided. The first input terminal is connected to the numerator input of the divider  510  and the output of the adder  508  is connected to the denominator input of the divider  510 . The output of the divider  510  is connected to the output port. 
     Thus, where the values of the input ports are, respectively x 1 , x 2 , x 3  then the value of y at the output port is given by:
 
 y=x   1 /( x   2   +x   3 ).
 
     Referring to  FIG. 17 , a respective scalar multiplier  520  is provided with each of the units shown in  FIG. 16 . A plurality of units  500  of the type shown in  FIG. 16  are provided arranged in cascade. The output port of the first unit is connected to the middle input port (leading to the adder  508 ) of the next, and so on until the last. The first input port of each (connected to the denominator of the divider  510 ) is connected to the output of its respective scalar multiplier  520 , except for the first (of which the scalar multiplier is connected to the second input terminal brackets leading to the adder). 
     In all units, the first input terminal (leading to the adder  508 ) is connected to a constant having the value 1, as is the last input terminal (leading to the denominator of the divider  510 ) over the last unit  500   c . Each of the multipliers  520  multiplies by a respective coefficient alpha. 
     In operation, then, it will be clear that the structure described in the  FIG. 17  represents a very simple and scalable structure for performing the calculation of equation 29, to calculate approximate exponentials of the number supplied in parallel to the imports of the multipliers  520 . Strictly, the adders  508  in this case are merely performing an increment instruction and do not require an external input, but for more general functions, a different scalar could be used. 
     A more accurate calculation can be provided simply by appending further such units (and changing the values of the coefficients appropriately). Whilst exponentiation has been described as a particular case where the continued fraction approximation has substantial advantages over conventional series expansions due to the low convergence, any Padé approximant (such as that disclosed in equation 23) can be transformed into a continued fraction representation as mentioned above, and accordingly with appropriate coefficient values the apparatus of  FIG. 17  can be used. 
     Where, as in a signal processing operation such as decoding, multiple different functions must be calculated (e.g. exponentiation, logarithms, trigonometric functions and so on) a single device according to  FIG. 17  can be employed with alternative sets of coefficients to calculate different such functions. 
     Whilst the structure shown in  FIG. 17  is particularly suitable for dedicated hardware implementation as a series of simple calculating units, it can also be implemented as an iterative program on, for example, a digital signal processor device. Obviously this represents just a part of the flexibility and scalability brought by the use of such Padé approximations. Indeed, by using the full Padé table, and depending on the path followed to reach the final rational approximation, both accuracy and modularity are ensured. 
     Other Embodiments and Variants 
     It will be clear that the above described embodiments are examples only, and that many other embodiments are possible. 
     For example, rather than providing a correction for the Max-LOG-MAP algorithm, the present embodiments could provide the correction factor for the AVG function described in U.S. Pat. No. 6,760,390. 
     Whereas the above described embodiments disclose the calculation of the correction factor, in fact, as mentioned above, the Max approximation is reasonable where the absolute difference between the two values is large and, accordingly, in another embodiment, the decoders test whether the magnitude of the difference between the two numbers is a predetermined threshold and, if so, only the maximum is used without the calculation of the additional correction factors disclosed herein. In other words, the decoder uses the calculation described in the present embodiment only where the absolute difference is less than the predetermined threshold. 
     Other techniques disclosed in, for example, the Harrison paper, the Cheng and Ottoson paper, or the Vallejo et al paper could be employed. 
     While the invention has been shown and described with reference to certain preferred embodiments thereof, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the spirit and scope of the invention as defined by the appended claims.