Abstract:
A method performs iterative decoding of information coded by an error correction code. The method includes: defining a transcendent first function representing a quantity to be evaluated for the decoding method; defining a quantized second function approximating the first function; computing first values of the second function obtained based on first arguments; the first values being not null and the first arguments being variable in a limited range having a maximum limit; computing second values of the second function obtained on the basis of second arguments, the second values being null; and generating a look-up table representing the first function and containing the first and second values associated to indexes correlated to said first arguments and to an expected maximum limit.

Description:
BACKGROUND OF THE INVENTION  
       [0001]     1. Field of the Invention  
         [0002]     The present invention relates to the field of error correction codes such as the ones employed for wireline and wireless digital communication systems and in data storage systems. As an example, the present invention relates to iterative decoding methods that implement the Maximum A Posteriori (MAP) Algorithm.  
         [0003]     2. Description of the Related Art  
         [0004]     A digital communication system of both wireless and wireline type usually comprises a transmitter, a communication channel and a receiver as known by those skilled in the art.  
         [0005]     The communication channel of such system is often noisy and introduces errors in the information being transmitted such that the information received at the receiver is different from the information transmitted.  
         [0006]     In general, in order to correct an error of the channel transmitted through wireline and wireless environments, the digital communication system uses a protection method by which the transmitter performs a coding operation using an error correction code and the receiver corrects the error produced by the noisy channel.  
         [0007]     Various coding schemes have been proposed and developed for performing correction of errors introduced by the channel. In particular, turbo codes (which are Forward Error Correction codes, FEC) are capable of achieving better error performance than conventional codes. Furthermore, turbo codes can achieve exceptionally low error rates in a low signal-to-noise ratio environment.  
         [0008]     For this reason, such turbo codes can usefully be employed in wireless communications, for example in the more recent CDMA wireless communication standard.  
         [0009]     A detailed description of turbo coding and decoding schemes can be found in “ Near Shannon Limit Error - Correcting Coding and Decoding: Turbo - codes ”, Berrou et al., Proc., IEEE Int&#39;l Conf. On communications, Geneva, Switzerland, 1993, pp. 1064-1070. Particularly, turbo codes are the parallel concatenation of two or more recursive systematic convolutional codes separated by interleavers.  
         [0010]     As known by those skilled in the art, decoding of turbo codes is often complex and involves a large amount of complex computations. Turbo decoding is typically based on a Maximum A Posteriori (MAP) algorithm which operates by calculating the maximum a posteriori probabilities for the data encoded by each constituent code.  
         [0011]     While it has been recognized that the MAP algorithm is the optimal decoding algorithm for turbo codes, it is also recognized that implementation of the MAP decoding algorithm is very difficult in practice because of its computational complexities.  
         [0012]     To reduce such complexities, approximations and modifications to the MAP algorithm have been developed. These include a Max-Log-MAP algorithm and a Log-MAP algorithm. The Max-Log-MAP and Log-MAP algorithms are described in detail in “ A Comparison of Optimal and Sub - Optimal MAP Decoding Algorithms Operating in the Log Domain ”, Robertson et al., IEEE Int&#39;l Conf. on Communications (Seattle, Wash.), June, 1995.  
         [0013]     To reduce the computational complexity of the MAP algorithm, the Max-Log-MAP and Log-MAP algorithms perform the entire decoding operation in the logarithmic domain. In fact, in the log domain, multiplication operations become addition operations, thus simplifying numeric computations involving multiplication.  
       BRIEF SUMMARY OF THE INVENTION  
       [0014]     The object of the present invention is to provide an improved method for performing iterative decoding of information which has been coded in accordance with error correction codes such as, for example, a turbo code.  
         [0015]     Particularly the inventive method comprises:  
         [0016]     defining a first transcendent function representing a quantity to be evaluated for the decoding method;  
         [0017]     defining a second quantized function approximating the first function;  
         [0018]     computing first values of the second function obtained on the basis of first arguments; the first values being not null and the first arguments being variable in a limited range having a maximum limit;  
         [0019]     computing second values of the second function obtained on the basis of second arguments, the second values being null and the second arguments being external to the range;  
         [0020]     generating a look-up table representing the first function and containing the first and second values associated to a plurality of indexes correlated to said first arguments and said maximum limit;  
         [0021]     retrieving tabled values from said look-up table on the basis of corresponding indexes for computing said quantity.  
         [0022]     In accordance with another object, the present invention relates with a receiving apparatus comprising a decoder for performing in a communication system iterative decoding of information coded by an error correction code, the decoder comprising:  
         [0023]     a memory storing a look-up table comprising a plurality of tabled values associated to corresponding indexes, said plurality of tabled values comprising:  
         [0024]     a first set of non null values associated to a first set of arguments included in a limited range; and  
         [0025]     a second set of null values associated to a second set of arguments external to said limited range;  
         [0026]     a processor module for retrieving said tabled values from the look-up table an the basis of said indexes and evaluating a quantity related to a transcendent function.  
     
    
     BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS  
       [0027]     The characteristics and the advantages of the present invention will be understood from the following detailed description of exemplary non-limiting embodiments thereof with reference to the annexed Figures, in which:  
         [0028]      FIG. 1  schematically shows in a block diagram an exemplary digital communication system;  
         [0029]      FIG. 2  schematically shows an exemplary encoder for a PCCC turbo code comprised in the communication system of  FIG. 1 ;  
         [0030]      FIG. 3  schematically shows an exemplary decoder for a PCCC turbo code comprised in the communication system of  FIG. 1 ;  
         [0031]      FIG. 4  schematically shows an architecture of a decoder block included in the decoder of  FIG. 3 ;  
         [0032]      FIG. 5  shows a flow diagram of the operations related to the use of a Look-Up_Table in accordance with a standard approach;  
         [0033]      FIG. 6  shows a flow diagram of the operations related to the use of another Look-Up_Table in accordance with a preferred embodiment of the invention.  
         [0034]      FIG. 7  shows an architecture illustrating the operations implemented to compute a value of the forward metric.  
         [0035]      FIG. 8  shows an architecture illustrating the operations performed by a first decoder for computing the log-likelihoods ratio. 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0036]      FIG. 1  is a block diagram schematically showing an exemplary digital communication system  100  of both wireless and wireline type. It has to be observed that the present invention is also applicable to data storage systems.  
         [0037]     Particularly, the communication system  100  comprises a transmitter  101 , a communication channel  102  and a receiver apparatus  103 . The transmitter  101  comprises a source  104  of digital data and an encoder  105  to encode data in accordance with error correction codes in order to make the transmission more robust against errors introduced by the channel  102 . Furthermore, the transmitter  101  comprises a modulator  106  to translate the encoded bits  107  into signals suitable to be transmitted through the channel  102 .  
         [0038]     Instead, the receiver apparatus  103  comprises a demodulator  108  for translating the received signals into bit likelihoods or soft values indicating with which probability a received bit is a 0 or 1 logic. Subsequently, such soft values are elaborated by a decoder  109  that retrieves the source bits  110 .  
         [0039]     In order to avoid errors introduced by the noisy channel  102 , the data bits to be transmitted can be, advantageously, encoded using a PCCC (Parallel Concatenated Convolutional Coding) turbo code known in the art.  
         [0040]     Particularly, employing the PCCC turbo code in the digital communication system  100 , data bits to be transmitted over the communication channel  102  are encoded as an information sequence (also called systematic information) and two or more parity sequences (also called parity information).  
         [0041]      FIG. 2  shows schematically an example of a PCCC turbo encoder  200  which can be comprised in the transmitter  101  of the communication system  100 .  
         [0042]     Particularly, such encoder  200  comprises a first  201  and a second  202  encoder, for example, substantially equal each other. The encoders  201  and  202  are chosen among the recursive systematic convolutional codes (RSC) and are described in “ Near Shannon Limit Error - Correcting Coding and Decoding: Turbo - codes ”, Berrou et al., Proc., IEEE Int&#39;l Conf. On communications, Geneva, Switzerland, 1993, pp. 1064-1070 and in U.S. Pat. No. 6,298,463 B1 (Bingeman et al.), herein incorporated by reference.  
         [0043]     With reference to a first information bit sequence d k  which corresponds to the data to be transmitted, the PCCC encoder  200  generates a systematic sequence of bits X k , a first parity sequence Y 1k  and a second parity sequence Y 2k .  
         [0044]     As shown in  FIG. 2 , the systematic sequence X k  corresponds to the first information bit sequence d k . Moreover, such bit sequence d k  represents the input of the first encoder  201  which produces at its output the first parity sequence Y 1k .  
         [0045]     On the contrary, a second information bit sequence d k   1  corresponds to the first information bit sequence d k  after elaboration made by an interleaver  203 . Such second information bit sequence d k   1  represents the input of the second encoder  202  which produces the second parity sequence Y 2k  at its output.  
         [0046]     The interleaver  203  in the PCCC turbo code encoder  200  operates, as it is known, to interleave the information bits supplied to the same encoder  200 . Such interleaving operation can be accomplished, for example, storing all input information bits consecutively in the rows of a matrix of storage locations and then reading consecutively the columns of the same matrix to access the stored bits (row-column interleaver).  
         [0047]     It should be observed that, typically, in the PCCC encoder  200 , the interleaver  203  is embedded into the encoder structure to form an overall concatenated code. In more detail, the interleaver  203  is employed to decorrelate the decoding errors produced in the first convolutional code (i.e. the first encoder  201 ) from those coming from the second convolutional code (i.e. the second encoder  202 ).  
         [0048]     The systematic sequence of bits X k , the first Y 1k  and second Y 2k  parity sequences produced by the PCCC encoder  200  are then multiplexed to form a code word. After encoding, the code word is modulated according to techniques known in the art and transmitted over the noisy communication channel  102 , either wired or wireless.  
         [0049]      FIG. 3  is a block diagram schematically showing the structure of a general PCCC turbo decoder  300  included in the receiver apparatus  103  of the communication system  100 .  
         [0050]     In more detail, such decoder  300  comprises a first  301  and a second  302  decoder for receiving and decoding the soft values x k , y 1k  and y 2k  produced by the demodulator  108  of the receiver apparatus  103 . Such soft values x k , y 1k  and y 2k  correspond to the systematic bit X k , the first parity bit Y 1k  and the second parity bit Y 2k , respectively, which have been demodulated and then filtered and sampled by, for example, a suitable filter/match/sample unit not shown in  FIG. 3 .  
         [0051]     Furthermore, the PCCC turbo decoder  300  may comprise a computation unit and a memory unit both not shown in  FIG. 3 . For example, the computation unit may include a microprocessor (Central Processing Unit or CPU) or other kinds of processing unit and the memory unit may include one or more RAM (random access memory).  
         [0052]     Moreover, the PCCC turbo decoder  300  can be constructed as an application specific integrated circuit (ASIC) or mapped on a field-programmable gate-array (FPGA) or a digital signal processor (DSP) software or using other suitable technologies known by one skilled in the art.  
         [0053]     As can be seen, the soft values x k  and y 1k  corresponding to the systematic bit X k  and the first parity bit Y 1k , represent the inputs of the first decoder  301 . The output of the first decoder  301  is a first log-likelihood ratio Λ 1e (d k ) to be sent to the second decoder  302  through a first interleaver  303 . Such first interleaver  303  is analogous to the interleaver  203  of the PCCC encoder  200 .  
         [0054]     Moreover, a first interleaved log-likelihood ratio Λ 1e (d k   1 ) represents a first input of the second decoder  302  and the soft value y 2k  corresponding to the second parity bit Y 2k  represent a second input for the same decoder  302 .  
         [0055]     Furthermore, a second interleaved log-likelihood ratio Λ 2e (d k   1 ) produced at the output of the second decoder  302  represents the input of a deinterleaver  304  in order to generate a deinterleaved log-likelihood ratio Λ 2e (d k ) to be sent to the first decoder  301  as a feedback signal.  
         [0056]     As known by those skilled in the art, the log-likelihood ratios Λ 1e (d k ) and Λ 2e (d k   1 ) produced at the output of the first  301  and second  302  decoders are the so called “extrinsic information”. Such extrinsic information Λ 1e (d k ), Λ 2e (d k   1 ) each one feeding the successive decoder in an iterative fashion is used as an estimation of the “a priori probability” of the logic value (0 or 1) of information bits. The first interleaver  303  and the deinterleaver  304  reorder the extrinsic information Λ 1e (d k ) and Λ 2e (d k   1 ), respectively, before each exchange between the first  301  and second  302  decoders.  
         [0057]     The reliability of the estimation increases for each iterative decoding step. Finally, a hard decision on the information bits is taken at the end of the last iteration. Particularly, at the last step of iteration, a further deinterleaver  304 ′ deinterleaves the second log-likelihood ratio Λ 2e (d k   1 ) produced by the second decoder  302  and the decoded bits are provided at the output of a threshold circuit  305 .  
         [0058]     According to the described example, the first  301  and second  302  modules are identical for the PCCC Turbo decoder. They can operate using different algorithms of the type Maximum A Posteriori (MAP).  
         [0059]     An example, the first  301  and second  302  decoders implement a MAP algorithm, such as the one proposed by Bahl et al in “ Optimal Decoding Of Linear Of Linear Codes For Minimizing Symbol Error Rate ”, IEEE Trans. Inform. Theory, vol. IT-20, pp. 248-287, March 1974, herein incorporated by reference.  
         [0060]     Particularly, the first  301  and the second  302  decoders can employ the MAP algorithms in the forms “Log-MAP” and “Max-Log-MAP” algorithms, which are described in “ A Comparison of Optimal and Sub - Optimal MAP Decoding Algorithms Operating in the Log Domain ”, Robertson et al., IEEE Int&#39;l Conf. on Communications (Seattle, Wash.), June, 1995, herein incorporated by reference.  
         [0061]     More particularly, as it will be described hereinafter, the first decoder  301  can perform at least one calculation in accordance with the “Log-MAP” algorithm.  
         [0062]      FIG. 4  shows schematically a possible architecture to implement the first decoder  301 , in accordance with an example of the invention. The first decoder  301  includes a processor module  400  and a memory module  500 , which can be written and read by the processor module  400 . The processor module  400  comprises a computing module  401  for performing calculations and a retrieving module  402  for retrieving data from the memory  500 . The modules  400 ,  401 ,  402  and the memory  500  can be hardware and/or software modules exclusively dedicated to perform the functions of the first decoder  301 , or can be included in the same hardware and/or software modules that perform all the functions of the first decoder  301 .  
         [0063]     Preferably, the modules of the architecture shown in  FIG. 4  can also be so as to perform not only the functions of the first decoder  301  but also the functions of the second decoder  301  or the ones of the whole decoder  300 .  
         [0064]     Following, an example of the inventive decoding method provided by the PCCC turbo decoder  300  will be described. As already stated, such turbo decoder  300  operates, at least in part, in accordance with the Log-MAP algorithm.  
         [0065]     Further details on the mathematical bases of the inventive method can be found in the above mentioned paper “ Near Shannon Limit Error - Correcting Coding and Decoding: Turbo - codes ”, Berrou et al., Proc., IEEE Int&#39;l Conf. On communications, Geneva, Switzerland, 1993, pp. 1064-1070.  
         [0066]     Particularly, the first decoder  301  computes the A Posteriori Probability in logarithmic domain. The output of such decoder  301 , i.e. the first log-likelihood ratio Λ 1 (d k ), can be expressed as:  
                       Λ   1     ⁡     (     d   k     )       =       ⁢     log   ⁢         P   r     ⁡     (       d   k     =     1   /   observation       )           P   r     ⁡     (       d   k     =     0   /   observation       )                       =       ⁢     log   ⁢         ∑   m     ⁢       ∑     m   ′       ⁢       ∑     j   =   0     1     ⁢         γ   1     ⁡     (       R   k     ,     m   ′     ,   m     )       ⁢       α     k   -   1     j     ⁡     (     m   ′     )       ⁢       β   k     ⁡     (   m   )                   ∑   m     ⁢       ∑     m   ′       ⁢       ∑     j   =   0     1     ⁢         γ   0     ⁡     (       R   k     ,     m   ′     ,   m     )       ⁢       α     k   -   1     j     ⁡     (     m   ′     )       ⁢       β   k     ⁡     (   m   )                                 (   1   )             
 
         [0067]     where m and m′ are the trellis states (known to the skilled person) at time k and k−1, respectively. Moreover, values α, β are usually called forward, and backward metrics and γ is usually called branch transition probability. These three quantities are kind of probabilities computed on the basis of the following equations:  
                 α   k   j     ⁡     (   m   )       =       h   a     ⁢       ∑     m   ′       ⁢       ∑     j   =   0     1     ⁢         γ   i     ⁡     (       R   k     ,     m   ′     ,   m     )       ⁢       α     k   -   1     j     ⁡     (     m   ′     )                       (   2   )                   β   k     ⁡     (   m   )       =       h   β     ⁢       ∑     m   ′       ⁢       ∑     i   =   0     1     ⁢         γ   i     ⁡     (       R     k   +   1       ,   m   ,     m   ′       )       ⁢       β     k   +   1       ⁡     (     m   ′     )                       (   3   )                   γ   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   ′         )                 (   4   )             
 
         [0068]     where h α  and h β  are normalization constants.  
         [0069]     Moreover, R k  corresponds to the soft values x k , y 1k  at the output of the noisy channel  102  after demodulation. With p( ) is indicated the transition probability of a discrete gaussian memoryless channel. Then, q( ) is the function that select the possible transition in a convolutional encoder finite state machine and π( ) is the transition state probability.  
         [0070]     As known by those skilled in the art, the values α and β can be recursively calculated from γ during the trellis forward and backward recursions, respectively.  
         [0071]     If we apply the logarithm operator to the branch transition probability γ, we obtain a further branch transition probability {circumflex over (γ)} expressed as: 
 
{circumflex over (γ)}( R   k   ,m′,m ) i =log γ( i ( R   k   ,m′,m ))=log [ p ( R   k   /d   k   =i,S   k   =m,S   k−1   =m′)   q ( d   k   =i/S   k   =m,S   k−1   =m ′)]+log(π( S   k   =m/S   k−1   =m′))    (5) 
 
         [0072]     then, the forward α and backward β metrics can be expressed as further forward {circumflex over (α)} and backward {circumflex over (β)} metrics:  
                         α   ^     k   j     ⁡     (   m   )       =       ⁢       log   ⁡     (       h   a     ⁢       ∑     m   ′       ⁢       ∑     j   =   0     1     ⁢       exp   ⁡     (         γ   ^     i     ⁡     (       R   k     ,     m   ′     ,   m     )       )       ⁢     exp   ⁡     (         α   ^       k   -   1     j     ⁡     (     m   ′     )       )               )       =                 =       ⁢       log   ⁡     (       ∑     m   ′       ⁢       ∑     j   =   0     1     ⁢     exp   ⁡     (           γ   ^     i     ⁡     (       R   k     ,     m   ′     ,   m     )       +         α   ^       k   -   1     j     ⁡     (     m   ′     )         )           )       +     H   a                     (   6   )                     β   ^     k     ⁡     (   m   )       =       log   ⁡     (       ∑     m   ′       ⁢       ∑     i   =   0     1     ⁢     exp   ⁡     (           γ   ^     i     ⁡     (       R     k   +   1       ,   m   ,     m   ′       )       +       β     k   +   1       ⁡     (     m   ′     )         )           )       +     H   β               (   7   )             
 
         [0073]     where the terms H α  and H β  correspond to the above indicated normalization constants h α  and h β  and the first log-likelihood ratio Λ 1 (d k ), can be expressed as:  
                       Λ   1     ⁡     (     d   k     )       =       ⁢       log   ⁢         P   r     ⁡     (       d   k     =     1   /   observation       )           P   r     ⁡     (       d   k     =     0   /   observation       )           =                 =       ⁢       log   ⁢         ∑   m     ⁢       ∑     m   ′       ⁢       ∑     j   =   0     1     ⁢     exp   ⁡     (                 γ   ^     1     ⁡     (       R   k     ,     m   ′     ,   m     )       +                     α   ^       k   -   1     j     ⁡     (     m   ′     )       +         β   ^     k     ⁡     (   m   )               )                 ∑   m     ⁢       ∑     m   ′       ⁢       ∑     j   =   0     1     ⁢     exp   ⁡     (                 γ   ^     0     ⁡     (       R   k     ,     m   ′     ,   m     )       +                     α   ^       k   -   1     j     ⁡     (     m   ′     )       +         β   ^     k     ⁡     (   m   )               )                 =                 =       ⁢       log   ⁡     (       ∑   m     ⁢       ∑     m   ′       ⁢       ∑     j   =   0     1     ⁢     exp   ⁡     (                 γ   ^     1     ⁡     (       R   k     ,     m   ′     ,   m     )       +                     α   ^       k   -   1     j     ⁡     (     m   ′     )       +         β   ^     k     ⁡     (   m   )               )             )       --                     ⁢     log   ⁡     (       ∑   m     ⁢       ∑     m   ′       ⁢       ∑     j   =   0     1     ⁢     exp   ⁡     (                 γ   ^     0     ⁡     (       R   k     ,     m   ′     ,   m     )       +                     α   ^       k   -   1     j     ⁡     (     m   ′     )       +         β   ^     k     ⁡     (   m   )               )             )                   =       ⁢       Λ_   ⁢   1     -     Λ_   ⁢   2                     (   8   )             
 
         [0074]     It should be observed that the quantities in (6), (7) and (8) can be computed by solving recursively terms such as the following: 
 
log(exp(α 1 +α 2 ))=max(α 1 ,α 2 )+log(1+e −|α     1     −α     2   |)=max*(α 1,α   2 )   (9) 
 
         [0075]     where the operator max*(a 1 ,a 2 ) comprises a max operator between general quantities a 1  and a 2  and a correcting factor log(1+e −|a     1     −a   2| ) that is function (in particular, a transcendent function) of the modulus of the difference between the same quantities.  
         [0076]     As an example, the recursion to compute the metrics {circumflex over (α)} will be performed by a recursive application of Eq (9) where the arguments will be terms like: 
 
{circumflex over (γ)} i (R k ,m′,m)+{circumflex over (α)} k−1   j (m′). 
 
         [0077]     Instead, the computation of Λ will be performed by a two recursive application of Eq (9) (one for each term of the subtraction of expression (8)) where the arguments will be terms like: 
 
({circumflex over (γ)}(R k ,m′,m)+{circumflex over (α)} k−1   j (m′)+{circumflex over (β)} k (m)). 
 
         [0078]     Advantageously, to approximate the correcting factor log(1+e −|a     1     −a     2|   ) a Look-Up Table or LUT is adopted.  
         [0079]     Such LUT could be memorized in the memory  500  provided in the decoder  300  and, for example, it can be generated by a processor external to the turbo decoder  300  and downloaded into the decoder itself during data processing of the input data. Alternatively, the LUT can be generated within the turbo decoder  300 .  
         [0080]     It should be observed that the number of elements of the LUT depends on the metric representation precision.  
         [0081]     Accordingly, we assume that the branch transition probabilities {circumflex over (γ)} are digitized according to the formula: 
 
{circumflex over (γ)} q =round( {circumflex over (γ)} 2 p )   (10) 
 
         [0082]     where p is the number of bits dedicated to the precision or equivalently 2 −p  is the quantization interval.  
         [0083]     Then, assuming that a saturation is applied and considering that a limited number of bits is available in any real implementation:  
             if   ⁢           ⁢     {                   γ   ^     q     ≥     2     (     p   +   d   -   1     )         ⇒       γ   ^     q       =       2     (     p   +   d   -   1     )       -   1                         γ   ^     q     ≤     -     2     (     p   +   d   -   1     )           ⇒       γ   ^     q       =     -     2     (     p   +   d   -   1     )                           (   11   )             
 
         [0084]     where d is the number of bit dedicated to the signal dynamic and p+d is equal to the number of ADC bits as known by those skilled in the art.  
         [0085]     Consequently, each element in the LUT can be defined as: 
 
LUT(Δ)=round(log(1+exp(−Δ/2 p ))2 p )   (12) 
 
         [0086]     where Δ=|{circumflex over (γ)} q1 −{circumflex over (γ)} q2 | and the round operator represents the nearest integer. Each value LUT(Δ) represents the correcting factor of the max*(a 1 ,a 2 ) operator expressed by the formula (9).  
         [0087]     Generally, the LUT has a limited number of elements given by the maximum integer Δ max  that satisfies the following inequality: 
 
log(1+exp(−Δ max /2 p ))≧2 −(p+1)    (13) 
 
         [0088]     For example, the LUT obtainable the levels of precision p=1 is shown in  
                                             TABLE 1                       P = 1                                    LUT (Δ)   1   1   1   1   1           Δ   0   1   2   3   4                      
 
         [0089]     The argument Δ of the LUT can varies within a limited range having Δ max =4 as maximum limit. Each tabled value is associated to a corresponding value of the argument Δ.  
         [0090]     The following Table 2 shows the tabled values of the LUTs for the level of precision p=2 and p=3. The values of the argument Δ are not shown in Table 2 for seek of clarity.  
                           TABLE 2                                   P   LUT                           2   3; 2; 2; 2; 1; 1; 1; 1; 1           3   6; 5; 5; 4; 4; 3; 3; 3; 3; 2; 2; 2; 2; 1; 1; 1; 1; 1; 1; 1; 1; 1                      
 
         [0091]     Neglecting the correcting factor log(1+e −|a     1     −a     e|   ) in (9) the Log-MAP algorithm becomes the well-known Max-Log-MAP algorithm. Particularly, such Max-Log-MAP algorithm presents a loss of performances compared to the Log-MAP because the Max-Log-MAP requires an increase of 0.3-0.4 dB of signal-to-noise ratio to achieve the same BER given by Log-MAP. Equation (12) and the corresponding LUTs, of the examples of Table 1 and Table 2, represent a standard approach to implement and use a look-up table.  
         [0092]     In the description below the LUT corresponding to the equation (12) will be called standard LUT, “Std LUT”.  
         [0093]     Moreover, a method of using the Std LUT will be now described with reference to  FIG. 5  and will be named Standard Approach. The steps for taking into account the correcting factor through the Std LUT of equation (12) are listed below:  
         [0094]     Step  10 : initial step “Init”;  
         [0095]     Step  11 : computing Δ=({circumflex over (γ)} 1 −{circumflex over (γ)} 2 );  
         [0096]     Step  12 : computing |Δ|;  
         [0097]     Step  13 : performing the conditional procedure:  
         [0098]     if Δ≦Δ max  (step block  13  of  FIG. 5  )  
         [0099]     applying max*({circumflex over (γ)} 1 ,{circumflex over (γ)} 2 )=max({circumflex over (γ)} 1 ,{circumflex over (γ)} 2 )+LUT(Δ), (evaluating LUT (Δ) by retrieving tabled values from the standard LUT Std LUT, step block  14 );  
         [0100]     else  
         [0101]     evaluating max*({circumflex over (γ)} 1 ,{circumflex over (γ)} 2 )=max({circumflex over (γ)} 1 ,{circumflex over (γ)} 2 ), without using the standard LUT Std LUT, (transition  15 );  
         [0102]     Step  16 : end of the method.  
         [0103]     It has to be noticed that the standard look-up tables Std LUTs have size reduced at minimum, but the standard approach requires the computation of the modulus and a check on its value. These operations that have to be performed in a recursive manner require great computational power.  
         [0104]     In view of the above, a look-up table alternative to the standard one STd LUT and a method of using the table alternative to the standard approach, are proposed, in accordance with one embodiment of the invention. Particularly, in the memory  500  is memorized a look-up table “Ext LUT”  600  still derivable from equation (12) but different from the Sdt LUT discussed above.  
         [0105]     In grater detail, such Ext LUT  600  is such that:  
         [0106]     the number of tabled values, N, is equal to twice than the maximum expected metric difference Δ M  plus one: N=2Δ M +1  
         [0107]     the LUT is filled with values equal to zeros (that is to say, null values) except in the positions  
         [0108]     i=Δ M +1+k with k=0:Δ max  where Ext LUT(i)=Std LUT(k+1)  
         [0109]     i=Δ M   −k  with k=1:Δ max  where Ext LUT(i)=Std LUT(k)  
         [0110]     the maximum expected metric difference Δ M  can be estimated on the basis of the particular turbo code employed.  
         [0111]     In other words, the look-up table Ext LUT  600  includes:  
         [0112]     the same not null values of the standard look-up table Std LUT for arguments i (i.e. indexes) included in the range Δ M +1:Δ M +1+Δ max ; in this range the values are ordered from left to right according to the same order of the look-up table Std LUT;  
         [0113]     a second group of values constituted by the same values of the first group but ordered in an opposite way (i.e. according a “mirror-like order”) for arguments i included in the range Δ M -Δ max :Δ M +1; in accordance with said “mirror-like order” the values of the second group correspond to the ones of look-up table Std LUT but they are ordered from right to left;  
         [0114]     the center value of the array of the Ext LUT  600  corresponds to the first value of the Standard LUT and is indicated only once in the LUT; in other words for the center value the mirror-like order is not applied to; and  
         [0115]     a third group constituted by null values for arguments i external to the above ranges.  
         [0116]     Therefore, the Ext LUT shows an “extended size” in comparison with standard LUT, Std LUT.  
         [0117]     Table 4 shows three examples of extended look-up tables Ext LUT  600 , for different precisions p.  
                   TABLE 4                       p                   1   0; . . . 0; 1; 1; 1; 1; 1; 1; 1; 1; 1; 0; . . . 0;       2   0; . . . 0; 1; 1; 1; 1; 1; 2; 2; 2; 3; 2; 2; 2; 1; 1; 1; 1; 1; 0; . . . 0;       3   0; . . . 0; 1; 1; 1; 1; 1; 1; 1; 1; 1; 2; 2; 2; 2; 3; 3; 3; 3; 4; 4; 5; 5; 6;           5; 5; 4; 4; 3; 3; 3; 3; 2; 2; 2; 2; 1; 1; 1; 1; 1; 1; 1; 1; 1; 0; . . . 0;                  
 
         [0118]     Each of the tabled values is associated to the index i above defined.  
         [0119]     The max*( ) algorithm implemented by the first decoder  301  is: 
 
max*({circumflex over (γ)} 1 ,{circumflex over (γ)} 2 )=max({circumflex over (γ)} 1 ,{circumflex over (γ)} 2 )+LUT(Δ M +1+{circumflex over (γ)} 1 −{circumflex over (γ)} 2 )   (14). 
 
         [0120]     In accordance with an example of the invention, the processor module  400  of the first decoder  301  uses the look-up table Ext LUT  600  as schematically shown in  FIG. 6 :  
         [0121]     Step  1 : start “Init”;  
         [0122]     Step  2 : the first computing module  401  computes the current index i by summing said first argument, said maximum limit and the value one: 
 
 i=Δ+Δ   M +1; 
 
         [0123]     Step  3 : on the basis of the computed index i the retrieving module  403  reads the look-up table Ext LUT  600  from the memory  500 , and retrieves a corresponding tabled value;  
         [0124]     Step  4 : end of the procedure.  
         [0125]     Therefore, by means of the Step  3 , the processor module  400  obtains the corrective factor of equation (14) that can be zero or different from zero. It has to be observed that the procedure described with reference to  FIG. 6  does not require any conditional expression such as the expression  13  of  FIG. 5 . Moreover, the quantity Δ may assume negative values, but the argument i (which is the index for accessing to the Etx LUT) will assume positive values.  
         [0126]     According to the example described, the computing module  401  computes the transition probabilities {circumflex over (γ)} and computes the Forward {circumflex over (α)}, the Backward {circumflex over (β)} metrics and the Log-Likelihoods Ratio Δ 1 (d k ) in accordance with the equations (6), (7) and (8).  
         [0127]     As an example,  FIG. 7  shows an architecture  700  illustrating the operations implemented to compute a value of the Forward metric {circumflex over (α)}, in accordance with equation (6), the max*( ) algorithm and by employing the Ext LUT  600 .  
         [0128]     In  FIG. 7  adding and subtracting nodes are shown, which are necessary for the computing of the quantity Δ. Moreover, the architecture  700  includes a selector SEL for evaluating the term max of the max*( ) algorithm.  
         [0129]     Another branch of the architecture  700  shows the operations performed to compute the index i and the use of the Ext LUT  600  in such a way to obtain the correcting factor of the max algorithm. The correcting factor is then added, by means of a corresponding node, to the max term. The backward metrics {circumflex over (β)} are computed in an analogous way.  
         [0130]     Moreover,  FIG. 8  shows an architecture  800  illustrating the operations performed by the first decoder  301  for computing the Log-Likelihoods Ratio Δ 1 (d k ).  
         [0131]     On the basis of the systematic bit X and the first parity bit Y 1  and on the basis of a value of a Log-Likelihoods Ratio Λ 1,  evaluated in a previous recursion step, a computing module  801  gives the transition probabilities {circumflex over (γ)} which is stored in a corresponding first memory module  802 .  
         [0132]     The architecture  800  includes recursion modules  700 ,  701 ,  702  and  703  for computing, respectively, the Forward metrics {circumflex over (α)}, the Backward metrics {circumflex over (β)} and the first and second terms Λ — 1-Λ — 2 of the expression (8).  
         [0133]     The recursion module  700  has been already described with reference to  FIG. 7 , and each of the other recursion modules  701 ,  702  and  703  are analogous to the module  700  and, therefore, they are not described in detail. During the recursive processing, the values of the Forward metrics {circumflex over (α)} and Backward metrics {circumflex over (β)} are stored in respective memory modules  803  and  804 .  
         [0134]     With reference to the evaluation of the quantities of the equations (6), (7) and (8), in accordance with an example of the invention the architectures  700  and  800  can be configured so as to evaluate all these three quantities by applying for each of them the Log-MAP algorithm using the look-up table Ext LUT  600 .  
         [0135]     According to an alternative embodiment, the Log-MAP algorithm can be applied to only one or two of the above quantity, while the remaining one is computed by means of the Max-Log-Map algorithm. The applicant has made a profiling test with a proprietary VLIW (very long instruction word) digital signal processor. In this test the complexity of the decoding process using a look-up table in accordance with the invention (Ext LUT) is compared with the complexity of the decoding process using the standard look-up table and the decoding process using the Max-Log MAP algorithm.  
         [0136]     Table 5 shows the results of the test reporting the complexity increase with respect to Max-Log-MAP algorithm. The test reports the case of PCCC with 8 decoding iterations and the complexity is measured in terms of clock cycles required by the decoding processes.  
                                                                                           Performance   Complexity   Complexity           @ BER = 10 −5     Std LUT   Ext LUT                                    Max-Log-MAP   REF   100%                Log-MAP   ≈+0.4 dB   ≈510%   ≈210%                  
 
         [0137]     The adoption of Ext LUT reduces the amount of clock cycles more than 50% compared to the Std LUT case. The implementation of Log-MAP algorithm in software, using the Std LUT, costs 5 times more than Max-Log-MAP in term of complexity; the cost becomes approximately two time with same performances at the expense of a certain amount of extra memory. However, in practical cases, Ext LUT size is not very large and the advantage in term of complexity/speed is often a good reason to accept the extra amount of memory.  
         [0138]     The gain, obtained using Ext LUT, is due to the fact that a software implementation becomes extremely inefficient when operations are “interrupted” by conditional expression. Specifically, for VLIW machines, like the one used for the complexity estimation presented in, the pipeline must be discharged due to a branch operation: this fact justifies the large difference between the two cases.  
         [0139]     No performance loss is paid with the adoption of Ext LUT because Std and Ext LUTs are perfectly equivalent in terms of signal processing.  
         [0140]     Also in hardware implementation the present invention allows a complexity reduction in the management of max* operator. As shown in  FIG. 5  and  FIG. 6 , it is clear the algorithm simplification in the LUT usage.  
         [0141]     Even if the above description refers to the case in which the teachings of the invention are implemented only by the first decoder  301 , it has to be pointed out that such teachings can be applied alternatively or, preferably, in addition also to the second decoder  302 . Advantageously, the second decoder  302  is so as to compute quantities analogous to the above described probabilities α, β and computes the likelihood-ratio Λ 2  in accordance with the method above described with reference to the first decoder  301 . To this end, a further look-up table, analogous to the table  600 , can be stored in the decoder  300  and employed by the second decoder  302  or alternatively, the second decoder can employ the same look-up table  600  of the first decoder  301 . The processing performed by the second decoder  302  is analogous to the one described with reference to the architectures  700  and  800  shown in  FIGS. 7 and 8 . Particularly, with reference to  FIG. 7 , the second decoder  302  receives the second parity sequence Y 2  and the log-likelihood ratio Λ 2  evaluated at a previous step.  
         [0142]     Moreover, it has to be noticed that the teachings of the present invention can be applied also to codes different from the turbo code. An example of another code, for which the extended look-up table (including values equal to zero) can be used, is described in the paper of Hagenauer J.; Offer E.; Papke L.: “ Iterative Decoding of Binary Block and Convolutional Codes ” IEEE Trans. Inform. Theory, March 1996, pp. 429-445, herein incorporated by reference.  
         [0143]     In accordance with the authors of the above paper, the Log-Likelihoods Ratio LLR of the sum of two binary variables a,b with LLR La, Lb is given by:  
               L     (     a   ⊕   b     )       =     log   ⁡     (       1   +     ⅇ       L   a     +     L   b               ⅇ     L   a       +     ⅇ     L   b           )               (   15   )             
 
         [0144]     The LLR of the sum of more than two binary variables is given by the recursive application of the equation (15). This formula can be exploited to decode every linear binary block code. It is worth to note that:  
               L     (     a   ⊕   b     )       =       log   ⁡     (       1   +     ⅇ       L   a     +     L   b               ⅇ     L   a       +     ⅇ     L   b           )       =         max   *     ⁢     (     0   ,       L   a     +     L   b         )       -       max   *     ⁢     (       L   a     ,     L   b       )                   (   16   )             
 
         [0145]     Another code to which the present invention can be applied is the Low-Density Parity Check Codes (LDPCC) proposed by Gallager R. G. in “Low-Density Parity-Check Codes”, IRE Trans. Information Theory, pop. 22-28, January 1962. The LDPCCs are an important class of codes decodable through the application of the above formulas (16). An interesting application of the above formulas to the decoding of LDPCC can be found in the paper of X. Hu, E. Eleftheriou, D.-M. Arnold and A. Dholakia. “Efficient Implementations of the Sum-Product Algorithm for Decoding LDPC Codes”. In Proc. IEEE Globecom, 2001.  
         [0146]     As clear from the above, the present invention shows important advantages:  
         [0147]     reduces complexity to implement max* operation for Turbo decoding and for MAP decoding of linear binary block codes;  
         [0148]     valid solutions for both software and hardware implementation;  
         [0149]     no drawback in terms of performances;  
         [0150]     the cost to be paid is a small amount of extra-memory.  
         [0151]     Obviously, to the decoding method of the present invention, those skilled in the art, aiming at satisfying contingent and specific requirements, may carry out further modifications and variations, all however being contemplated within the scope of protection of the invention, such as defined in the annexed claims.