Patent Publication Number: US-8543881-B2

Title: Apparatus and method for high throughput unified turbo decoding

Description:
FIELD 
     This disclosure relates generally to apparatus and methods for error correction decoding. More particularly, the disclosure relates to high throughput unified turbo decoding. 
     BACKGROUND 
     Wireless communications systems are susceptible to errors introduced in the communications link between the transmitter and receiver. Various error mitigation schemes including, for example, error detection, error correction, interleaving, etc. may be applied to control the error rate in the communications link. Error detection techniques employ parity bits to detect errors at the receiver. If an error is detected, then typically the transmitter is notified to resend the bits that were received in error. In contrast, error correction techniques employ redundant bits to both detect and correct bits that were received in error. 
     The total number of transmitted bits in a codeword is equal to the sum of information bits and redundant bits. The code rate of an error correction code is defined as the ratio of information bits to the total number of transmitted bits. Error correction codes include block codes, convolutional codes, turbo codes, low density parity check (LDPC) codes, and combinations thereof. Turbo codes are popular error correction codes in modern wireless communications systems. 
     Turbo codes were first introduced in 1993 by Berrou, Glavieux, and Thitimajshima and have been extensively developed since then. Turbo codes provide near-Shannon limit decoding by employing a combination of simpler encoders and an iterative decoding structure which exchanges soft decision information among a plurality of decoders. 
     Many wireless system are being introduced today such as Long Term Evolution (LTE) as part of the evolution of third generation partnership project (3GPP) systems, Worldwide Interoperability Microwave Access (WiMAX), wideband code division multiple access (WCDMA), evolution-data optimized (EVDO)/cdma2000, etc. These newer wireless systems utilize various forms of turbo encoding and decoding. 
     Conventional turbo decoding introduces overhead which reduces throughput. Improvements are desired which minimize turbo decoding overhead to allow enhancement of decoder throughput. In addition, a unified turbo decoder architecture which can be employed across a variety of wireless systems such as LTE, WiMAX, WCDMA, EVDO, etc. is desirable. 
     SUMMARY 
     Disclosed is an apparatus and method for error correction decoding using high throughput unified turbo decoding. According to one aspect, a method for high throughput unified turbo decoding comprising loading data from a first data window; computing a first forward state metric using the data from the first data window; storing the first forward state metric in a memory; computing a first reverse state metric using the data from the first data window; storing the first reverse state metric in the memory; and computing the log likelihood ratio (LLR) of the first forward state metric and the first reverse state metric. 
     According to another aspect, a receiver for high throughput unified turbo decoding comprising an antenna for receiving an electromagnetic wave comprising a received signal; a receiver front-end for generating a digital signal from the received signal; a demodulator coupled to the receiver front-end for demodulating the digital signal and outputting a demodulated bit stream; and a turbo decoder for performing the following: loading data from a first data window of the demodulated bit stream; computing a first forward state metric using the data from the first data window; storing the first forward state metric in a memory; computing a first reverse state metric using the data from the first data window; storing the first reverse state metric in the memory; and computing the log likelihood ratio (LLR) of the first forward state metric and the first reverse state metric. 
     According to another aspect, a receiver for high throughput unified turbo decoding comprising means for receiving an electromagnetic wave comprising a received signal; means for generating a digital signal from the received signal; means for demodulating the digital signal and outputting a demodulated bit stream; and means for performing the following: loading data from a first data window of the demodulated bit stream; computing a first forward state metric using the data from the first data window; storing the first forward state metric in a memory; computing a first reverse state metric using the data from the first data window; storing the first reverse state metric in the memory; and computing the log likelihood ratio (LLR) of the first forward state metric and the first reverse state metric. 
     According to another aspect, a computer-readable medium storing a computer program, wherein execution of the computer program is for: loading data from a first data window; computing a first forward state metric using the data from the first data window; storing the first forward state metric in a memory; computing a first reverse state metric using the data from the first data window; storing the first reverse state metric in the memory; and computing the log likelihood ratio (LLR) of the first forward state metric and the first reverse state metric. 
     Advantages of the present disclosure include the ability to use a single turbo decoder for a variety of wireless systems. 
     It is understood that other aspects will become readily apparent to those skilled in the art from the following detailed description, wherein it is shown and described various aspects by way of illustration. The drawings and detailed description are to be regarded as illustrative in nature and not as restrictive. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  illustrates an example wireless communications system which employs a concatenated code. 
         FIG. 2  illustrates an example structure of a LTE turbo encoder. 
         FIG. 3  illustrates an example structure of a WiMAX turbo encoder. 
         FIG. 4  illustrates an example structure of an EVDO/cdma2000 turbo encoder. 
         FIG. 5  illustrates an example turbo interleaver output address calculation procedure. 
         FIG. 6  illustrates the relative throughput with respect to single maximum a posteriori (MAP) without overhead. 
         FIG. 7  illustrates an example of a SuperTurbo maximum a posteriori (MAP) architecture. 
         FIG. 8  illustrates an example operational flow diagram of a SuperTurbo single maximum a posteriori (MAP). 
         FIG. 9  illustrates an example of a single maximum a posteriori (MAP), single log likelihood ratio computation (LLRC) architecture. 
         FIG. 10  illustrates an example operational flow diagram of the single maximum a posteriori (MAP), single log likelihood ratio computation (LLRC) architecture depicted in  FIG. 9 . 
         FIG. 11  illustrates another example of a single maximum a posteriori (MAP), dual log likelihood ratio computation (LLRC) architecture. 
         FIG. 12  illustrates an example operational flow of the single maximum a posteriori (MAP), dual log likelihood ratio computation (LLRC) architecture for N=3 windows depicted in  FIG. 11 . 
         FIG. 13  illustrates an example of a second decoder of a dual maximum a posteriori (MAP), single log likelihood ratio computation (LLRC) architecture. 
         FIG. 14  illustrates an example operational flow of the second decoder of the dual maximum a posteriori (MAP), single log likelihood ratio computation (LLRC) architecture for N=6 windows depicted in  FIG. 13 . 
         FIG. 15  illustrates an example operational flow of dual maximum a posteriori (MAP), dual log likelihood ratio computation (LLRC) for N=6 windows. 
         FIG. 16  illustrates a state propagation scheme in a single maximum a posteriori (MAP), single log likelihood ratio computation (LLRC) where RSMC utilizes the state propagation scheme. 
         FIG. 17  illustrates a state propagation scheme in a single maximum a posteriori (MAP), single log likelihood ratio computation (LLRC) where FSMC utilizes the state propagation scheme. 
         FIG. 18  illustrates an operational flow of a conventional sliding window scheme. 
         FIG. 19  illustrates an example of an operational flow of a sliding window scheme in accordance with the present disclosure. 
         FIG. 20  illustrates an example of a simplified branch metric computation for rate ⅓ code. 
         FIG. 21  illustrates an example reverse state metric computation with state 0 shown. 
         FIG. 22   a  illustrated an example diagram of log likelihood ratio (LLR) computation. 
         FIG. 22   b  illustrates an example diagram of APP computation for symbol value 0. 
         FIG. 23  illustrates an example receiver block diagram for implementing turbo decoding. 
         FIG. 24  is an example flow diagram for high throughput unified turbo decoding. 
         FIG. 25  is an example flow diagram for high throughput unified turbo decoding for a single maximum a posteriori (MAP), single log likelihood ratio computation (LLRC) architecture. 
         FIG. 26  is an example flow diagram for high throughput unified turbo decoding for a dual maximum a posteriori (MAP), single log likelihood ratio computation (LLRC) architecture. 
         FIG. 27  is an example flow diagram for high throughput unified turbo decoding for a single maximum a posteriori (MAP) architecture. 
         FIG. 28  illustrates an example of a device comprising a processor in communication with a memory for executing the processes for high throughput unified turbo decoding. 
     
    
    
     DETAILED DESCRIPTION 
     The detailed description set forth below in connection with the appended drawings is intended as a description of various aspects of the present disclosure and is not intended to represent the only aspects in which the present disclosure may be practiced. Each aspect described in this disclosure is provided merely as an example or illustration of the present disclosure, and should not necessarily be construed as preferred or advantageous over other aspects. The detailed description includes specific details for the purpose of providing a thorough understanding of the present disclosure. However, it will be apparent to those skilled in the art that the present disclosure may be practiced without these specific details. In some instances, well-known structures and devices are shown in block diagram form in order to avoid obscuring the concepts of the present disclosure. Acronyms and other descriptive terminology may be used merely for convenience and clarity and are not intended to limit the scope of the disclosure. 
     While for purposes of simplicity of explanation, the methodologies are shown and described as a series of acts, it is to be understood and appreciated that the methodologies are not limited by the order of acts, as some acts may, in accordance with one or more aspects, occur in different orders and/or concurrently with other acts from that shown and described herein. For example, those skilled in the art will understand and appreciate that a methodology could alternatively be represented as a series of interrelated states or events, such as in a state diagram. Moreover, not all illustrated acts may be required to implement a methodology in accordance with one or more aspects. 
       FIG. 1  illustrates an example of a wireless communication system which employs a concatenated code. In one aspect, the wireless communication system comprises a transmitter  100 , a wireless channel  150 , and a receiver  197  coupled to an output destination data  195 . The transmitter  100  receives an input source data  105 . A concatenated code consists of two codes: an outer code and an inner code. In one aspect, the transmitter  100  comprises an outer encoder  110 , an interleaver  120 , an inner encoder  130 , and a modulator  140  for processing the input source data  105  to produce a transmitted signal  145  (not shown). The wireless channel  150  propagates the transmitted signal  145  from the transmitter  100  and delivers a received signal  155  (not shown). The received signal  155  is an attenuated, distorted version of transmitted signal  145  along with additive noise. The receiver  197  receives the received signal  155 . In one aspect, the receiver  197  comprises a demodulator  160 , an inner decoder  170 , a deinterleaver  180 , and an outer decoder  190  for processing the received signal  155  to produce the output destination data  195 . Not shown in  FIG. 1  are a high power amplifier and a transmit antenna associated with the transmitter  100 . Also not shown are a receive antenna and a low noise amplifier associated with the receiver  197 . 
     Table 1 summarizes the peak data rates and code block size for four different wireless systems. In one aspect, the turbo decoder should provide a throughput consistent with all of the peak data rates and provide both a sliding window mode and no window mode operations. 
     
       
         
           
               
               
               
               
               
             
               
                   
                 TABLE 1 
               
               
                   
                   
               
               
                   
                 LTE 
                 WiMAX 
                 WCDMA 
                 EVDO 
               
               
                   
                   
               
             
            
               
                   
               
            
           
           
               
               
               
               
               
            
               
                 Peak data 
                 50 Mbps 
                 46.1 Mbps average 
                 28.8 Mbps 
                 14.75 1  Mbps 
               
               
                 rate 
                   
                   70 Mbps peak 
               
               
                 Code block 
                 40 to 6144 
                 48 to 480 
                 40 to 5114 
                 128 to 8192 
               
               
                 size in bits 
               
               
                 per stream 
               
               
                   
               
            
           
         
       
     
     In one aspect, the turbo decoder unifies the decoding needs of LTE, WiMAX, WCDMA, CDMA2000, and EVDO. As shown in Table 2, all these wireless standards have the same feedback polynomial (denominator of the generator polynomial), except WiMAX. Since the feedback polynomial determines the state transition, WiMAX will have a different state transition from other standards. In this table G(D) refers to a generator polynomial for a non-interleaved bit sequence and G′(D) refers to a generator polynomial for an interleaved bit sequence. 
                                     TABLE 2                               EVDO/           LTE   WiMAX   WCDMA   CDMA2000                  Mother code   1/3 binary   1/3 duo-binary   1/3 binary   1/5 binary               G(D)             1   +   D   +     D   3         1   +     D   2     +     D   3                         1   +     D   2     +     D   3         1   +   D   +     D   3                         1   +   D   +     D   3         1   +     D   2     +     D   3                           1   +   D   +     D   3         1   +     D   2     +     D   3         ,       1   +   D   +     D   2     +     D   3         1   +     D   2     +     D   3                             G′(D)   Same as G(D)             1   +     D   3         1   +   D   +     D   3               Same as G(D)   Same as  G(D)               Turbo   LTE-   WiMAX-   WCDMA-   CDMA-       interleaver   specific   specific   specific   specific       Trellis   6 tail bits   No tail bits   6 tail bits   6 tail bits       Termination       -- tail-                       biting                       trellis                    
LTE Turbo
 
     One example of a LTE turbo encoder scheme is a Parallel Concatenated Convolutional Code (PCCC) with two 8-state constituent encoders and one 1 code internal interleaver. In one example, the coding rate of the turbo encoder is ⅓.  FIG. 2  illustrates an example structure of a LTE turbo encoder. In one aspect, the LTE turbo encoder is used for high throughput unified turbo encoding. 
     The transfer function of the 8-state constituent code for the PCCC is: 
     
       
         
           
             
               
                 G 
                 ⁡ 
                 
                   ( 
                   D 
                   ) 
                 
               
               = 
               
                 [ 
                 
                   1 
                   , 
                   
                     
                       
                         g 
                         1 
                       
                       ⁡ 
                       
                         ( 
                         D 
                         ) 
                       
                     
                     
                       
                         g 
                         0 
                       
                       ⁡ 
                       
                         ( 
                         D 
                         ) 
                       
                     
                   
                 
                 ] 
               
             
             , 
           
         
       
     
     where
 
 g   0 ( D )=1+ D   2   +D   3 ,
 
 g   1 ( D )=1+ D+D   3 .
 
     The initial value of the shift registers of the 8-state constituent encoders shall be all zeros when starting to encode the input bits. The output from the turbo encoder is:
 
 d   k   (0)   =x   k  
 
 d   k   (1)   =y   k  
 
 d   k   (2)   =y′   k  
 
for  k= 0,1,2 , . . . , K− 1.
 
     If the code block to be encoded is the 0-th code block and the number of filler bits is greater than zero, i.e., F&gt;0, then the encoder shall set c k , =0, k=0, . . . , (F−1) at its input and shall set d k   (0) =&lt;NULL&gt;, k=0, . . . , (F−1) and d k   (1) =&lt;NULL&gt;, k=0, . . . , (F−1) at its output. 
     The bits input to the turbo encoder are denoted by c 0 , c 1 , c 2 , c 3 , . . . , c K−1 , and the bits output from the first and second 8-state constituent encoders are denoted by y 0 , y 1 , y 2 , y 3 , . . . , y K−1  and y′ 0 , y′ 1 , y′ 2 , y′ 3 , . . . , y′ K−1 , respectively. The bits output from the turbo code internal interleaver are denoted by c′ 0 , c′ 1 , . . . , c′ K−1 , and these bits are the input to the second 8-state constituent encoder. 
     One example of trellis termination for the LTE turbo encoder is performed by taking the tail bits from the shift register feedback after all information bits are encoded. Tail bits are padded after the encoding of information bits. 
     The first three tail bits shall be used to terminate the first constituent encoder (upper switch of  FIG. 2  in lower position) while the second constituent encoder is disabled. The last three tail bits shall be used to terminate the second constituent encoder (lower switch of  FIG. 2  in lower position) while the first constituent encoder is disabled. 
     The transmitted bits for trellis termination shall then be:
 
 d   K   (0)   =x   K   , d   K+1   (0)   =y   K+1   , d   K+2   (0)   =x′   K   , d   K+3   (0)   =y′   K+1  
 
 d   K   (1)   =y   K   , d   K+1   (1)   =x   K+2   , d   K+2   (1)   =y′   K   , d   K+3   (1)   =x′   K+2  
 
 d   K   (2)   =x   K+1   , d   K+1   (2)   =y   K+2   , d   K+2   (2)   =x′   K+1   , d   K+3   (2)   =y′   K+2  
 
     The bits input to the turbo code internal interleaver are denoted by c 0 , c 1 , . . . , c K−1 , where K is the number of input bits. The bits output from the turbo code internal interleaver are denoted by c′ 0 , c′ 1 , . . . , c′ K−1 . 
     The relationship between the input and output bits is as follows:
 
 c′   i   =c   π(i)   , i= 0, 1, . . . ,( K− 1)
 
where the relationship between the output index i and the input index π(i) satisfies the following quadratic form:
 
π( i )=( f   1   ·i+f   2   ·i   2 )mod  K  
 
The parameters f 1  and f 2  depend on the block size K and are summarized in Table 3.
 
                                     TABLE 3                   i   K i     f 1     f 2                                                          1   40   3   10           2   48   7   12           3   56   19   42           4   64   7   16           5   72   7   18           6   80   11   20           7   88   5   22           8   96   11   24           9   104   7   26           10   112   41   84           11   120   103   90           12   128   15   32           13   136   9   34           14   144   17   108           15   152   9   38           16   169   21   120           17   168   101   84           18   176   21   44           19   184   57   46           20   192   23   48           21   200   13   50           22   208   27   52           23   216   11   36           24   224   27   56           25   232   85   58           26   240   29   60           27   248   33   62           28   256   15   32           29   264   17   193           30   272   33   68           31   230   103   210           32   283   19   36           33   296   19   74           34   304   37   76           35   312   19   78           36   320   21   120           37   328   21   82           38   336   115   84           39   344   193   86           40   352   21   44           41   360   133   90           42   368   81   46           43   376   45   94           44   384   23   48           45   392   243   98           46   400   151   40           47   408   155   102           48   416   25   52           49   424   51   106           50   432   47   72           51   440   91   110           52   448   29   168           53   456   29   114           54   464   247   58           55   472   29   118           56   480   89   180           57   488   91   122           58   496   157   62           59   504   55   84           60   532   31   64           61   528   17   66           62   544   35   68           63   560   227   420           64   576   65   96           65   592   19   74           66   608   37   76           67   624   41   234           68   640   39   80           69   656   185   82           70   672   43   252           71   688   21   86           72   704   155   44           73   720   79   120           74   736   139   92           75   752   23   94           76   768   237   48           77   784   25   98           78   800   17   80           79   816   127   102           80   832   25   52           81   848   239   106           82   864   17   48           83   880   137   110           84   896   215   112           85   912   29   114           86   928   15   58           87   944   147   118           88   960   29   60           89   976   59   122           90   992   65   124           91   1008   55   84           92   1024   31   64           93   1056   17   66           94   1088   171   204           95   1120   67   140           96   1152   35   72           97   1184   19   74           98   1216   39   76           99   1248   19   78           100   1280   199   240           101   1312   21   82           102   1344   211   252           103   1376   21   86           104   1408   43   88           105   1440   149   60           106   1472   45   92           107   1504   49   846           108   1536   71   48           109   1568   13   28           110   1600   17   80           111   1632   25   102           112   1664   183   104           113   1696   55   954           114   1728   127   96           115   1760   27   110           116   1792   29   112           117   1824   29   114           118   1856   57   116           119   1888   45   354           120   1920   31   120           121   1952   59   610           122   1984   185   124           123   2016   113   420           124   2048   31   64           125   2132   17   66           126   2176   171   136           127   2240   209   420           128   2304   253   216           129   2368   367   444           130   2432   265   456           131   2496   181   468           132   2560   39   80           133   2624   27   164           134   2688   127   504           135   2752   143   172           136   2816   43   88           137   2880   29   300           138   2944   45   92           139   3008   157   188           140   3072   47   96           141   3136   13   28           142   3200   111   240           143   3264   443   204           144   3328   51   104           145   3392   51   212           146   3456   451   192           147   3520   257   220           148   3584   57   336           149   3648   313   228           150   3712   271   232           151   3776   179   236           152   3840   331   110           153   3904   363   244           154   3968   375   248           155   4032   127   168           156   4096   31   64           157   4160   33   130           158   4224   43   264           159   4288   33   134           160   4352   477   408           161   4416   35   138           162   4480   233   280           163   4544   357   142           164   4608   337   450           165   4672   37   146           166   4736   71   444           167   4800   71   120           168   4864   37   152           169   4928   39   462           170   4992   127   234           171   5056   39   156           172   5120   39   80           173   5184   31   96           174   5248   113   902           175   5312   41   166           176   5376   251   336           177   5440   43   170           178   5504   21   86           179   5568   43   174           180   5632   45   176           181   5696   45   178           182   5760   161   120           183   5824   89   182           184   5888   323   184           185   5952   47   186           186   6016   23   94           187   6050   47   190           188   6144   263   450                    
WiMAX Turbo Encoder
 
     Another example of a turbo scheme is the WiMAX turbo encoder, also known as a convolutional turbo code (CTC) encoder, including its constituent encoder, as depicted in  FIG. 3 .  FIG. 3  illustrates an example structure of a WiMAX turbo encoder. It uses a double-binary Circular Recursive Systematic Convolutional code. The bits of data to be encoded are alternately fed to A and B. The encoder is fed by blocks of k bits or N couples (k=2*N bits). For all frame sizes, k is a multiple of 8 and N is a multiple of 4. The polynomials defining the connections are described in octal and symbolic notations as follows:
         For the feedback branch: 0xB, equivalently 1+D+D 3      For the Y parity bit: 0xD, equivalently 1+D 2 +D 3  
 
The CTC interleaver requires the parameters P 0 , P 1 , P 2 , and P 3 , as shown in Table 4.
       

     
       
         
           
               
               
               
               
               
             
               
                 TABLE 4 
               
               
                   
               
               
                 N 
                 P 0   
                 P 1   
                 P 2   
                 P 3   
               
               
                   
               
             
            
               
                   
               
            
           
           
               
               
               
               
               
            
               
                 24 
                 5 
                 0 
                 0 
                 0 
               
               
                 36 
                 11 
                 18 
                 0 
                 18 
               
               
                 48 
                 13 
                 24 
                 0 
                 24 
               
               
                 72 
                 11 
                 6 
                 0 
                 6 
               
               
                 96 
                 7 
                 48 
                 24 
                 72 
               
               
                 108 
                 11 
                 54 
                 56 
                 2 
               
               
                 120 
                 13 
                 60 
                 0 
                 60 
               
               
                 144 
                 17 
                 74 
                 72 
                 2 
               
               
                 180 
                 11 
                 90 
                 0 
                 90 
               
               
                 192 
                 11 
                 96 
                 48 
                 144 
               
               
                 216 
                 13 
                 108 
                 0 
                 108 
               
               
                 240 
                 13 
                 120 
                 60 
                 180 
               
               
                   
               
            
           
         
       
     
     The two-step interleaver shall be performed as follows: 
     Step 1: Switch Alternate Couples 
     
         
         
           
             Let the sequence u 0 =[(A 0 ,B 0 ), (A 1 ,B 1 ), (A 2 ,B 2 ), . . . , (A N−1 ,B N−1 )] be the input to the first encoding C 1 . 
             for i=0, . . . , N−1
           if (i mode 2), let (A i ,B i )→(B i ,A i ) (i.e., switch the couple)   
         
             This step gives a sequence u 1 =[u 1 (0), u 1 (1), u 1 (2), u 1 (3), . . . , u 1 (N−1)]=[(A 0 ,B 0 ), (B 1 ,A 1 ), (A 2 ,B 2 ), (B 3 ,A 3 ), . . . (B N−1 ,A N−1 )].
 
Step 2: P(j)
 
             The function P(j) provides the address of the couple of the sequence u1 that shall be mapped onto address j of the interleaved sequence (i.e., u2(j)=u1(P(j))). 
             for j=0, . . . , N−1
           switch (j mod 4)   case 0: P(j)=(P 0 *j+1) mod N   case 1: P(j)=(P 0 *j+1+N/2+P 1 ) mod N   case 2: P(j)=(P 0 *j+1+P 2 ) mod N   case 3: P(j)=(P 0 *j+1+N/2+P 3 ) mod N   This step gives a sequence u 2 =[u 1 (P(0)), u 1 (P(1)), u 1 (P(2)), u 1 (P(3)), . . . , u 1 (P(N−1))]. Sequence u 2  us the input to the second encoding C 2 .
 
WCDMA Turbo Encoder
   
         
           
         
       
    
     In another example, the WCDMA turbo encoder is the same as the LTE Turbo encoder, except for the internal interleaver. The WCDMA turbo code internal interleaver consists of bits-input to a rectangular matrix with padding, intra-row and inter-row permutations of the rectangular matrix, and bits-output from the rectangular matrix with pruning. The bits input to the Turbo code internal interleaver are denoted by x 1 , x 2 , x 3 , . . . , x K , where K is the integer number of the bits and takes one value of 40≦K≦5114. The relationship between the bits input to the turbo code internal interleaver and the bits input to the channel coding is defined by x k =o irk  and K=K i . 
     The following specific symbols are used herein regarding the WCDMA turbo encoder: 
     K Number of bits input to turbo code internal interleaver 
     R Number of rows of rectangular matrix 
     C Number of columns of rectangular matrix 
     p Prime number 
     v Primitive root 
       s(j)   jε{0, 1, . . . , p−2}  Base sequence for intra-row permutation 
     q i  Minimum prime integers 
     r i  Permuted prime integers 
       T(i)   iε{0, 1, . . . , R−1}  Inter-row permutation pattern 
       U i (j)   jε{0, 1, . . . , C−1}  Intra-row permutation pattern of i-th row 
     i Index of row number of rectangular matrix 
     j Index of column number of rectangular matrix 
     k Index of bit sequence 
     The bit sequence x 1 , x 2 , x 3 , . . . , x K  input to the turbo code internal interleaver is written into the rectangular matrix as follows:
         (1) Determine the number of rows of the rectangular matrix, R, such that:       

     
       
         
           
             R 
             = 
             
               { 
               
                 
                   
                     
                       5 
                       , 
                       
                         if 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         
                           ( 
                           
                             40 
                             ≤ 
                             K 
                             ≤ 
                             159 
                           
                           ) 
                         
                       
                     
                   
                 
                 
                   
                     
                       10 
                       , 
                       
                         if 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         
                           ( 
                           
                             
                               ( 
                               
                                 160 
                                 ≤ 
                                 K 
                                 ≤ 
                                 200 
                               
                               ) 
                             
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             or 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               ( 
                               
                                 481 
                                 ≤ 
                                 K 
                                 ≤ 
                                 530 
                               
                               ) 
                             
                           
                           ) 
                         
                       
                     
                   
                 
                 
                   
                     
                       20 
                       , 
                       
                         if 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         
                           
                             ( 
                             
                               K 
                               = 
                               
                                 any 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 other 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 value 
                               
                             
                             ) 
                           
                           . 
                         
                       
                     
                   
                 
               
             
           
         
       
         
         
           
             The rows of the rectangular matrix are numbered 0, 1, . . . , R−1 from top to bottom. 
             (2) Determine the prime number to be used in the intra-permutation, p, and the number of columns of the rectangular matrix, C, such that: 
           
         
       
    
     
       
         
           
               
               
             
               
                   
               
             
            
               
                   
                 if(481 ≦ K ≦ 530), then 
               
               
                   
                 p = 53 and C = p. 
               
               
                   
                 else 
               
               
                   
               
            
           
         
       
         
         
           
             Find minimum prime number p from Table 5 such that:
 
 K≦R ×( p+ 1),
 
             and determine C such that: 
           
         
       
    
     
       
         
           
             C 
             = 
             
               { 
               
                 
                   
                     
                       p 
                       - 
                       1 
                     
                   
                   
                     
                       
                         if 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         K 
                       
                       ≤ 
                       
                         R 
                         × 
                         
                           ( 
                           
                             p 
                             - 
                             1 
                           
                           ) 
                         
                       
                     
                   
                 
                 
                   
                     p 
                   
                   
                     
                       
                         if 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         R 
                         × 
                         
                           ( 
                           
                             p 
                             - 
                             1 
                           
                           ) 
                         
                       
                       &lt; 
                       K 
                       ≤ 
                       
                         R 
                         × 
                         p 
                       
                     
                   
                 
                 
                   
                     
                       p 
                       + 
                       1 
                     
                   
                   
                     
                       
                         if 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         R 
                         × 
                         p 
                       
                       &lt; 
                       
                         K 
                         . 
                       
                     
                   
                 
               
             
           
         
       
         
         
           
             end if: 
             The columns of the rectangular matrix are numbered 0, 1, . . . , C−1 from left to right.
 
Table 5 lists the prime number p and associated primitive root v.
 
           
         
       
    
     
       
         
           
               
               
               
               
               
               
               
               
               
               
             
               
                 TABLE 5 
               
               
                   
               
               
                 p 
                 v 
                 p 
                 v 
                 p 
                 v 
                 p 
                 v 
                 p 
                 v 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
               
               
               
               
               
               
               
               
               
            
               
                 7 
                 3 
                 47 
                 5 
                 101 
                 2 
                 157 
                 5 
                 223 
                 3 
               
               
                 11 
                 2 
                 53 
                 2 
                 103 
                 5 
                 163 
                 2 
                 227 
                 2 
               
               
                 13 
                 2 
                 59 
                 2 
                 107 
                 2 
                 167 
                 5 
                 229 
                 6 
               
               
                 17 
                 3 
                 61 
                 2 
                 109 
                 6 
                 173 
                 2 
                 233 
                 3 
               
               
                 19 
                 2 
                 67 
                 2 
                 113 
                 3 
                 179 
                 2 
                 239 
                 7 
               
               
                 23 
                 5 
                 71 
                 7 
                 127 
                 3 
                 181 
                 2 
                 241 
                 7 
               
               
                 29 
                 2 
                 73 
                 5 
                 131 
                 2 
                 191 
                 19 
                 251 
                 6 
               
               
                 31 
                 3 
                 79 
                 3 
                 137 
                 3 
                 193 
                 5 
                 257 
                 3 
               
               
                 37 
                 2 
                 83 
                 2 
                 139 
                 2 
                 197 
                 2 
                   
                   
               
               
                 41 
                 6 
                 89 
                 3 
                 149 
                 2 
                 199 
                 3 
                   
                   
               
               
                 43 
                 3 
                 97 
                 5 
                 151 
                 6 
                 211 
                 2 
               
               
                   
               
            
           
         
       
         
         
           
             (3) Write the input bit sequence x 1 , x 2 , x 3 , . . . , x K  into the R×C rectangular matrix row by row, starting with bit y 1  in column 0 of row 0: 
           
         
       
    
     
       
         
           
               
             
               [ 
               
                 
                   
                     
                       y 
                       1 
                     
                   
                   
                     
                       y 
                       2 
                     
                   
                   
                     
                       y 
                       3 
                     
                   
                   
                     ⋯ 
                   
                   
                     
                       y 
                       C 
                     
                   
                 
                 
                   
                     
                       y 
                       
                         ( 
                         
                           C 
                           + 
                           1 
                         
                         ) 
                       
                     
                   
                   
                     
                       y 
                       
                         ( 
                         
                           C 
                           + 
                           2 
                         
                         ) 
                       
                     
                   
                   
                     
                       y 
                       
                         ( 
                         
                           C 
                           + 
                           3 
                         
                         ) 
                       
                     
                   
                   
                     ⋯ 
                   
                   
                     
                       y 
                       
                         2 
                         ⁢ 
                         C 
                       
                     
                   
                 
                 
                   
                     ⋮ 
                   
                   
                     ⋮ 
                   
                   
                     ⋮ 
                   
                   
                     ⋯ 
                   
                   
                     ⋮ 
                   
                 
                 
                   
                     
                       y 
                       
                         ( 
                         
                           
                             
                               ( 
                               
                                 R 
                                 - 
                                 1 
                               
                               ) 
                             
                             ⁢ 
                             C 
                           
                           + 
                           1 
                         
                         ) 
                       
                     
                   
                   
                     
                       y 
                       
                         ( 
                         
                           
                             
                               ( 
                               
                                 R 
                                 - 
                                 1 
                               
                               ) 
                             
                             ⁢ 
                             C 
                           
                           + 
                           2 
                         
                         ) 
                       
                     
                   
                   
                     
                       y 
                       
                         ( 
                         
                           
                             
                               ( 
                               
                                 R 
                                 - 
                                 1 
                               
                               ) 
                             
                             ⁢ 
                             C 
                           
                           + 
                           3 
                         
                         ) 
                       
                     
                   
                   
                     ⋯ 
                   
                   
                     
                       y 
                       
                         R 
                         × 
                         C 
                       
                     
                   
                 
               
               ] 
             
           
         
       
         
         
           
             where y k =x k  for k=1, 2, . . . , K and if R×C&gt;K, the dummy bits are padded such that y k =0 or 1 for k=K+1, K+2, . . . , R×C. These dummy bits are pruned away from the output of the rectangular matrix after the intra-row and inter-row permutations. 
           
         
       
    
     After the bits-input to the R×C rectangular matrix, the intra-row and inter-row permutations for the R×C rectangular matrix are performed stepwise by using the following algorithm with steps 1 through 6:
         (1) Select a primitive root v from Table 5 which is indicated on the right side of the prime number p.   (2) Construct the base sequence  s(j)   jε{0, 1, . . . , p−2}  for intra-row permutation as:
 
 s ( j )=( v×s ( j− 1))mod  p, j= 1, 2, . . . ,( p− 2), and  s (0)=1.
   (3) Assign q 0 =1 to be the first prime integer in the sequence  q i     iε{0, 1, . . . , R−1}  and determine the prime integer q i  in the sequence  q i     iε{0, 1, . . . , R−1}  to be a least prime integer, such that g.c.d(q i ,p−1)=1, q i &gt;6, and q i &gt;q (i−1)  for each i=1, 2, . . . , R−1. Here g.c.d. is greatest common divisor.   (4) Permute the sequence  q i     iε{0, 1, . . . , R−1}  to make the sequence  r i     iε{0, 1, . . . , R−1}  such that
 
 r   T(i)   =q   i   , i= 0, 1, . . . ,  R− 1
   where  T(i)   iε{0, 1, . . . , R−1}  is the inter-row permutation pattern defined as one of the four kinds of patterns, which are shown in Table 6, depending on the number of input bits K.   (5) Perform the i-th (i=0, 1, . . . , R−1) intra-row permutation as:   if (C=p) then:
 
 U   i ( j )= s (( j×r   i )mod( p− 1)),  j= 0, 1, . . . ,( p− 2), and  U   i ( p− 1)=0,
   where U i (j) is the original bit position of j-th permuted bit of i-th row. End if:   if (C=p+1) then:
 
 U   i ( j )= s (( j×r   i )mod( p− 1)),  j= 0, 1, . . . ,( p− 2).  U   i ( p− 1)=0, and  U   i ( p )= p,  
   where U i (j) is the original bit position of j-th permuted bit of i-th row and if (K=R×C) then:   exchange U R−1 (p) with U R−1 (0).   End if:   if (C=p−1) then:
 
 U   i ( j )= s (( j×r   i )mod( p− 1))−1 , j= 0, 1, . . . ,( p− 2),
   where U i (j) is the original bit position of j-th permuted bit of i-th row.   End if:   (6) Perform the inter-row permutation for the rectangular matrix based on the pattern  T(i)   iε{0, 1, . . . , R−1}     where T(i) is the original row position of the i-th permuted row.       

     Table 6 lists the inter-row permutation patterns for turbo code internal interleaver. 
     
       
         
           
               
               
               
             
               
                 TABLE 6 
               
               
                   
               
               
                   
                 Number of 
                 Inter-row permutation patterns 
               
               
                 Number of input bits K 
                 rows R 
                 &lt;T(0), T(1), . . . , T(R − 1)&gt; 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
               
               
            
               
                 (40 ≦ K ≦ 159) 
                 5 
                 &lt;4, 3, 2, 1, 0&gt; 
               
               
                 (160 ≦ K ≦ 200) or 
                 10 
                 &lt;9, 8, 7, 6, 5, 4, 3, 2, 1, 0&gt; 
               
               
                 (481 ≦ K ≦ 530) 
               
               
                 (2281 ≦ K ≦ 2480) or 
                 20 
                 &lt;19, 9, 14, 4, 0, 2, 5, 7, 12, 18, 16, 
               
               
                 (3161 ≦ K ≦ 3210) 
                   
                 13, 17,15, 3, 1, 6, 11, 8, 10&gt; 
               
               
                 K = any other value 
                 20 
                 &lt;19, 9, 14, 4, 0, 2, 5, 7, 12, 18, 10, 
               
               
                   
                   
                 8, 13, 17, 3, 1, 16, 6, 15, 11&gt; 
               
               
                   
               
            
           
         
       
     
     After intra-row and inter-row permutations, the bits of the permuted rectangular matrix are denoted by y′ k : 
     
       
         
           
               
             
               [ 
               
                 
                   
                     
                       y 
                       1 
                       ′ 
                     
                   
                   
                     
                       y 
                       
                         ( 
                         
                           R 
                           + 
                           1 
                         
                         ) 
                       
                       ′ 
                     
                   
                   
                     
                       y 
                       
                         ( 
                         
                           
                             2 
                             ⁢ 
                             R 
                           
                           + 
                           1 
                         
                         ) 
                       
                       ′ 
                     
                   
                   
                     ⋯ 
                   
                   
                     
                       y 
                       
                         ( 
                         
                           
                             
                               ( 
                               
                                 C 
                                 - 
                                 1 
                               
                               ) 
                             
                             ⁢ 
                             R 
                           
                           + 
                           1 
                         
                         ) 
                       
                       ′ 
                     
                   
                 
                 
                   
                     
                       y 
                       2 
                       ′ 
                     
                   
                   
                     
                       y 
                       
                         ( 
                         
                           R 
                           + 
                           2 
                         
                         ) 
                       
                       ′ 
                     
                   
                   
                     
                       y 
                       
                         ( 
                         
                           
                             2 
                             ⁢ 
                             R 
                           
                           + 
                           2 
                         
                         ) 
                       
                       ′ 
                     
                   
                   
                     ⋯ 
                   
                   
                     
                       y 
                       
                         ( 
                         
                           
                             
                               ( 
                               
                                 C 
                                 - 
                                 1 
                               
                               ) 
                             
                             ⁢ 
                             R 
                           
                           + 
                           2 
                         
                         ) 
                       
                       ′ 
                     
                   
                 
                 
                   
                     ⋮ 
                   
                   
                     ⋮ 
                   
                   
                     ⋮ 
                   
                   
                     ⋯ 
                   
                   
                     ⋮ 
                   
                 
                 
                   
                     
                       y 
                       R 
                       ′ 
                     
                   
                   
                     
                       y 
                       
                         2 
                         ⁢ 
                         R 
                       
                       ′ 
                     
                   
                   
                     
                       y 
                       
                         3 
                         ⁢ 
                         R 
                       
                       ′ 
                     
                   
                   
                     ⋯ 
                   
                   
                     
                       y 
                       
                         C 
                         × 
                         R 
                       
                       ′ 
                     
                   
                 
               
               ] 
             
           
         
       
     
     The output of the turbo code internal interleaver is the bit sequence read out column by column from the intra-row and inter-row permuted R×C rectangular matrix, starting with bit y′ 1  in row 0 of column 0 and ending with bit y′ CR  in row R−1 of column C−1. The output is pruned by deleting dummy bits that were padded to the input of the rectangular matrix before intra-row and inter row permutations, i.e. bits y′ k  that correspond to bits y k  with k&gt;K are removed from the output. The bits output from the turbo code internal interleaver are denoted by x′ 1 , x′ 2 , . . . , x′ K , where x′ 1  corresponds to the bit y′ k  with the smallest index k after pruning, x′ 2  to the bit y′ k  with the second smallest index k after pruning, and so on. The number of bits output from the turbo code internal interleaver is K and the total number of pruned bits is:
 
 R×C−K.  
 
EVDO/CDMA 2000 Turbo Encoder
 
     In another example, the EVDO/cdma2000 turbo encoder employs two systematic, recursive, convolutional encoders that are connected in parallel, with the turbo interleaver preceding the second recursive, convolutional encoder. The two recursive convolutional codes are called the constituent codes of the turbo code. The outputs of the constituent encoders are punctured and repeated to achieve the desired number of turbo encoder output symbols. The transfer function for the constituent code shall be: 
               G   ⁡     (   D   )       =     [         1             n   0     ⁡     (   D   )         d   ⁡     (   D   )                   n   1     ⁡     (   D   )         d   ⁡     (   D   )               ]           
where d(D)=1+D 2 +D 3 , n 0 (D)=1+D+D 3 , and n 1 (D)=1+D+D 2 +D 3 .
 
     The turbo encoder shall generate an output symbol sequence that is identical to the one generated by the encoder shown in  FIG. 4 .  FIG. 4  illustrates an example structure of an EVDO/cdma2000 turbo encoder. Initially, the states of the constituent encoder registers in this figure are set to zero. Then, the constituent encoders are clocked with the switches in the positions noted. 
     Let N turbo  be the number of bits into the turbo encoder after the 6-bit physical layer packet TAIL field is discarded. Then, the encoded data output symbols are generated by clocking the constituent encoders N turbo  times with the switches in the up positions, and puncturing the outputs as specified in Table 7 and Table 8. Table 7 lists the puncturing patterns for data bit periods in EVDO. Table 8 lists the puncturing patterns for data bit periods in cdma2000. Within a puncturing pattern, a “0” means that the symbol shall be deleted and a “1” means that the symbol shall be passed onward. The constituent encoder outputs for each bit period shall be output in the sequence X, Y 0 , Y 1 , X′, Y′ 0 , Y′ 1  with the X output first. Symbol repetition is not used in generating the encoded data output symbols. 
     
       
         
           
               
               
               
             
               
                   
                 TABLE 7 
               
             
            
               
                   
                   
               
               
                   
                 Code rate 
                   
               
            
           
           
               
               
               
               
            
               
                   
                 Output 
                 ⅓ 
                 ⅕ 
               
               
                   
                   
               
               
                   
                 X 
                 1 
                 1 
               
               
                   
                 Y 0   
                 1 
                 1 
               
               
                   
                 Y 1   
                 0 
                 1 
               
               
                   
                 X′ 
                 0 
                 0 
               
               
                   
                 Y′ 0   
                 1 
                 1 
               
               
                   
                 Y′ 1   
                 0 
                 1 
               
               
                   
                   
               
               
                   
                 For each rate, the puncturing table shall be read from top to bottom. 
               
            
           
         
       
     
     
       
         
           
               
               
             
               
                   
                 TABLE 8 
               
             
            
               
                   
                   
               
               
                   
                 Code rate 
               
            
           
           
               
               
               
               
               
            
               
                   
                 Output 
                 ½ 
                 ⅓ 
                 ¼ 
               
               
                   
                   
               
               
                   
                 X 
                 11 
                 11 
                 11 
               
               
                   
                 Y 0   
                 10 
                 11 
                 11 
               
               
                   
                 Y 1   
                 00 
                 00 
                 10 
               
               
                   
                 X′ 
                 00 
                 00 
                 00 
               
               
                   
                 Y′ 0   
                 01 
                 11 
                 01 
               
               
                   
                 Y′ 1   
                 00 
                 00 
                 11 
               
               
                   
                   
               
               
                   
                 For each rate, the puncturing table shall be read first from top to bottom and then from left to right. 
               
            
           
         
       
     
     The turbo encoder shall generate 6/R tail output symbols following the encoded data output symbols. This tail output symbol sequence shall be identical to the sequence generated by the encoder shown in  FIG. 4 . The tail output symbols are generated after the constituent encoders have been clocked N turbo  times with the switches in the up position. The first 3/R tail output symbols are generated by clocking Constituent Encoder 1 three times with its switch in the down position while Constituent Encoder 2 is not clocked, and puncturing and repeating the resulting constituent encoder output symbols. The last 3/R tail output symbols are generated by clocking Constituent Encoder 2 three times with its switch in the down position while Constituent Encoder 1 is not clocked, and puncturing and repeating the resulting constituent encoder output symbols. The constituent encoder outputs for each bit period shall be output in the sequence X, Y 0 , Y 1 , X′, Y′ 0 , Y′ 1  with the X output first. 
     The constituent encoder output symbol puncturing for the tail symbols shall be as specified in Table 9. Within a puncturing pattern, a “0” means that the symbol shall be deleted, a “1” means that the symbol shall be passed onward, and a “2” means that the symbol shall be repeated. Table 9 lists the puncturing patterns for tail bit periods in EVDO. Table 10 lists the puncturing patterns for tail bit periods in cdma2000. 
     
       
         
           
               
               
               
             
               
                   
                 TABLE 9 
               
             
            
               
                   
                   
               
               
                   
                 Code rate 
                   
               
            
           
           
               
               
               
               
            
               
                   
                 Output 
                 ⅓ 
                 ⅕ 
               
               
                   
                   
               
               
                   
                 X 
                 222 000 
                 222 000 
               
               
                   
                 Y 0   
                 111 000 
                 111 000 
               
               
                   
                 Y 1   
                 000 000 
                 222 000 
               
               
                   
                 X′ 
                 000 222 
                 000 222 
               
               
                   
                 Y′ 0   
                 000 111 
                 000 111 
               
               
                   
                 Y′ 1   
                 000 000 
                 000 222 
               
               
                   
                   
               
               
                   
                 For rate-⅓ turbo codes, the puncturing table shall be read first from top to bottom repeating X and X′, and then from left to right. 
               
               
                   
                 For rate-⅕ turbo codes, the puncturing table shall be read first from top to bottom repeating X, X′, Y 1 , and Y′ 1  and then from left to right. 
               
            
           
         
       
     
     
       
         
           
               
               
             
               
                   
                 TABLE 10 
               
             
            
               
                   
                   
               
               
                   
                 Code rate 
               
            
           
           
               
               
               
               
               
            
               
                   
                 Output 
                 ½ 
                 ⅓ 
                 ¼ 
               
               
                   
                   
               
               
                   
                 X 
                 111 000 
                 222 000 
                 222 000 
               
               
                   
                 Y 0   
                 111 000 
                 111 000 
                 111 000 
               
               
                   
                 Y 1   
                 000 000 
                 000 000 
                 111 000 
               
               
                   
                 X′ 
                 000 111 
                 000 222 
                 000 222 
               
               
                   
                 Y′ 0   
                 000 111 
                 000 111 
                 000 111 
               
               
                   
                 Y′ 1   
                 000 000 
                 000 000 
                 000 111 
               
               
                   
                   
               
               
                   
                 Note: 
               
               
                   
                 For rate ½ turbo codes, the puncturing table shall be read first from top to bottom and then from left to right. 
               
               
                   
                 For rate ⅓ and ¼ turbo codes, the puncturing table shall be read first from top to bottom repeating X and X′, and then from left to right. 
               
            
           
         
       
     
     The turbo interleaver, which is part of the turbo encoder, shall block-interleave the turbo encoder input data that is fed to Constituent Encoder 2. The turbo interleaver shall be functionally equivalent to an approach where the entire sequence of turbo interleaver input bits are written sequentially into an array at a sequence of addresses, and then the entire sequence is read out from a sequence of addresses that are defined by the procedure described below. 
     Let the sequence of input addresses be from 0 to N turbo −1. Then, the sequence of interleaver output addresses shall be equivalent to those generated by the procedure illustrated in  FIG. 5 .  FIG. 5  illustrates an example turbo interleaver output address calculation procedure. The example procedure illustrated in  FIG. 5  is equivalent to one where the counter values are written into a 2 5 -row by 2 n -column array by rows, the rows are shuffled according to a bit-reversal rule, the elements within each row are permuted according to a row-specific linear congruential sequence, and tentative output addresses are read out by column. The linear congruential sequence rule is x(i+1)=(x(i)+c) mod 2 n , where x(0)=c and c is a row-specific value from a table lookup.
         1. Determine the turbo interleaver parameter, n, where n is the smallest integer such that N turbo ≦2 n+5  Table 11 and Table 12 give this parameter for the different physical layer packet sizes. Table 11 lists the turbo interleaver parameter for EVDO. Table 12 lists the turbo interleaver parameter for cdma2000.   2. Initialize an (n+5)-bit counter to 0.   3. Extract the n most significant bits (MSBs) from the counter and add one to form a new value. Then, discard all except the n Least Significant Bits (LSBs) of this value.   4. Obtain the n-bit output of the table lookup defined in Table 13 and Table 14 with a read address equal to the five LSBs of the counter. Tables 13 and 14 depend on the value of n. Table 13 lists the turbo interleaver lookup table definition for EVDO. Table 14 lists the turbo interleaver lookup table definition for cdma2000.   5. Multiply the values obtained in Steps 3 and 4, and discard all except the n LSBs.   6. Bit-reverse the five LSBs of the counter.   7. Form a tentative output address that has its MSBs equal to the value obtained in Step 6 and its LSBs equal to the value obtained in Step 5.   8. Accept the tentative output address as an output address if it is less than N turbo ; otherwise, discard it.   9. Increment the counter and repeat Steps 3 through 8 until all N turbo  interleaver output addresses are obtained.       

     
       
         
           
               
               
               
             
               
                 TABLE 11 
               
               
                   
               
               
                   
                 Turbo 
                   
               
               
                   
                 interleaver 
                 Turbo 
               
               
                 Physical layer 
                 block size 
                 interleaver 
               
               
                 packet size 
                 N turbo   
                 parameter n 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
               
               
            
               
                 128 
                 122 
                 2 
               
               
                 256 
                 250 
                 3 
               
               
                 512 
                 506 
                 4 
               
               
                 1,024 
                 1,018 
                 5 
               
               
                 2,048 
                 2,042 
                 6 
               
               
                 3,072 
                 3,066 
                 7 
               
               
                 4,096 
                 4,090 
                 7 
               
               
                 5,120 
                 5,114 
                 8 
               
               
                 6144 
                 6138 
                 8 
               
               
                 7168 
                 7162 
                 8 
               
               
                 8192 
                 8186 
                 8 
               
               
                   
               
            
           
         
       
     
     
       
         
           
               
               
               
             
               
                   
                 TABLE 12 
               
               
                   
                   
               
               
                   
                 Turbo 
                   
               
               
                   
                 interleaver 
                 Turbo 
               
               
                   
                 block size 
                 interleaver 
               
               
                   
                 N turbo   
                 parameter n 
               
               
                   
                   
               
             
            
               
                   
               
            
           
           
               
               
               
            
               
                   
                 378 
                 4 
               
               
                   
                 570 
                 5 
               
               
                   
                 762 
                 5 
               
               
                   
                 1,146 
                 6 
               
               
                   
                 1,530 
                 6 
               
               
                   
                 2,298 
                 7 
               
               
                   
                 3,066 
                 7 
               
               
                   
                 4,602 
                 8 
               
               
                   
                 6,138 
                 8 
               
               
                   
                 9,210 
                 9 
               
               
                   
                 12,282 
                 9 
               
               
                   
                 20,730 
                 10 
               
               
                   
                   
               
            
           
         
       
     
     
       
         
           
               
               
               
               
               
               
               
               
             
               
                 TABLE 13 
               
               
                   
               
               
                 Table 
                 n = 2 
                 n = 3 
                 n = 4 
                 n = 5 
                 n = 6 
                 n = 7 
                 n = 8 
               
               
                 index 
                 entries 
                 entries 
                 entries 
                 entries 
                 entries 
                 entries 
                 entries 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
               
               
               
               
               
               
               
            
               
                 0 
                 3 
                 1 
                 5 
                 27 
                 3 
                 15 
                 3 
               
               
                 1 
                 3 
                 1 
                 15 
                 3 
                 27 
                 127 
                 1 
               
               
                 2 
                 3 
                 3 
                 5 
                 1 
                 15 
                 89 
                 5 
               
               
                 3 
                 1 
                 5 
                 15 
                 15 
                 13 
                 1 
                 83 
               
               
                 4 
                 3 
                 1 
                 1 
                 13 
                 29 
                 31 
                 19 
               
               
                 5 
                 1 
                 5 
                 9 
                 17 
                 5 
                 15 
                 179 
               
               
                 6 
                 3 
                 1 
                 9 
                 23 
                 1 
                 61 
                 19 
               
               
                 7 
                 1 
                 5 
                 15 
                 13 
                 31 
                 47 
                 99 
               
               
                 8 
                 1 
                 3 
                 13 
                 9 
                 3 
                 127 
                 23 
               
               
                 9 
                 1 
                 5 
                 15 
                 3 
                 9 
                 17 
                 1 
               
               
                 10 
                 3 
                 3 
                 7 
                 15 
                 15 
                 119 
                 3 
               
               
                 11 
                 1 
                 5 
                 11 
                 3 
                 31 
                 15 
                 13 
               
               
                 12 
                 1 
                 3 
                 15 
                 13 
                 17 
                 57 
                 13 
               
               
                 13 
                 1 
                 5 
                 3 
                 1 
                 5 
                 123 
                 3 
               
               
                 14 
                 1 
                 5 
                 15 
                 13 
                 39 
                 95 
                 17 
               
               
                 15 
                 3 
                 1 
                 5 
                 29 
                 1 
                 5 
                 1 
               
               
                 16 
                 3 
                 3 
                 13 
                 21 
                 19 
                 85 
                 63 
               
               
                 17 
                 1 
                 5 
                 15 
                 19 
                 27 
                 17 
                 131 
               
               
                 18 
                 3 
                 3 
                 9 
                 1 
                 15 
                 55 
                 17 
               
               
                 19 
                 3 
                 5 
                 3 
                 3 
                 13 
                 57 
                 131 
               
               
                 20 
                 3 
                 3 
                 1 
                 29 
                 45 
                 15 
                 211 
               
               
                 21 
                 1 
                 5 
                 3 
                 17 
                 5 
                 41 
                 173 
               
               
                 22 
                 3 
                 5 
                 15 
                 25 
                 33 
                 93 
                 231 
               
               
                 23 
                 1 
                 5 
                 1 
                 29 
                 15 
                 87 
                 171 
               
               
                 24 
                 3 
                 1 
                 13 
                 9 
                 13 
                 63 
                 23 
               
               
                 25 
                 1 
                 5 
                 1 
                 13 
                 9 
                 15 
                 147 
               
               
                 26 
                 3 
                 1 
                 9 
                 23 
                 15 
                 13 
                 243 
               
               
                 27 
                 1 
                 5 
                 15 
                 13 
                 31 
                 15 
                 213 
               
               
                 28 
                 3 
                 3 
                 11 
                 13 
                 17 
                 81 
                 189 
               
               
                 29 
                 1 
                 5 
                 3 
                 1 
                 5 
                 57 
                 51 
               
               
                 30 
                 1 
                 5 
                 15 
                 13 
                 15 
                 31 
                 15 
               
               
                 31 
                 3 
                 3 
                 5 
                 13 
                 33 
                 69 
                 67 
               
               
                   
               
            
           
         
       
     
                                                 TABLE 14               Table   n = 4   n = 5   n = 6   n = 7   n = 8   n = 9   n = 10       index   entries   entries   entries   entries   entries   entries   entries                                                                0   5   27   3   15   3   13   1       1   15   3   27   127   1   335   349       2   5   1   15   89   5   87   303       3   15   15   13   1   83   15   721       4   1   13   29   31   19   15   973       5   9   17   5   15   179   1   703       6   9   23   1   61   19   333   761       7   15   13   31   47   99   11   327       8   13   9   3   127   23   13   453       9   15   3   9   17   1   1   95       10   7   15   15   119   3   121   241       11   11   3   31   15   13   155   187       12   15   13   17   57   13   1   497       13   3   1   5   123   3   175   909       14   15   13   39   95   17   421   769       15   5   29   1   5   1   5   349       16   13   21   19   85   63   509   71       17   15   19   27   17   131   215   557       18   9   1   15   55   17   47   197       19   3   3   13   57   131   425   499       20   1   29   45   15   211   295   409       21   3   17   5   41   173   229   259       22   15   25   33   93   231   427   335       23   1   29   15   87   171   83   253       24   13   9   13   63   23   409   677       25   1   13   9   15   147   387   717       26   9   23   15   13   243   193   313       27   15   13   31   15   213   57   757       28   11   13   17   81   189   501   189       29   3   1   5   57   51   313   15       30   15   13   15   31   15   489   75       31   5   13   33   69   67   391   163                    
Logmap Algorithm
 
     Consider a binary phase shift keying (BPSK) communication system model given by: 
                 r   ~     t     =             (       E   s       N   0       )     x       ⁢     (     1   -     2   ⁢     x   t         )       +     n     r   ,   t                         z   ~     t     =             (       E   s       N   0       )     y       ⁢     (     1   -     2   ⁢     y   t         )       +     n     z   ,   t               
where:
         {tilde over (r)} t  is the received signal for systematic bit x t  at time t   {tilde over (z)} t  is the received vector (possibly 1×1) signal for parity bit vector y t  at time t   n r,t  and n z,t  are additive white Gaussian noise (AWGN)   (E s /N 0 ) x  and (E s /N 0 ) y  are signal/noise ratios (SNRs) of received signal {tilde over (r)} t  and {tilde over (z)} t          

     Further, define the quaternary systematic symbol c t , the systematic bit log likelihood ratio (LLR) vector r t , and the systematic bit vector s t  by: 
                 c   t     =       2   ⁢     x       2   ⁢   t     +   1         +     x     2   ⁢   t           ,     
     ⁢       r   t     =           2   ⁢       E   s           N   0       ⁡     [             r   ~         2   ⁢   t     +   1               r   ~       2   ⁢   t             ]       T       ,     
     ⁢       s   t     =         [           1   -     2   ⁢     x       2   ⁢   t     +   1                 1   -     2   ⁢     x     2   ⁢   t                 ]     T     .             
Then the quaternary log likelihood is given by:
 
                       λ   i     ⁡     (   t   )       =     log   ⁡     (       Pr   ⁡     (         c   t     =     i   ❘     r   1   τ         ,     z   1   τ       )         Pr   ⁡     (         c   t     =     0   ❘     r   1   τ         ,     z   1   τ       )         )                   =     log   ⁡     (         ∑       (       l   ′     ,   l     )     ∈     B   t   i         ⁢         α     l   ′       ⁡     (     t   -   1     )       ⁢       γ       l   ′     ,   l     i     ⁡     (   t   )       ⁢       β   l     ⁡     (   t   )               ∑       (       l   ′     ,   l     )     ∈     B   t   0         ⁢         α     l   ′       ⁡     (     t   -   1     )       ⁢       γ       l   ′     ,   l     0     ⁡     (   t   )       ⁢       β   l     ⁡     (   t   )             )                   =       log   ⁡     (       Pr   ⁡     (       c   t     =   i     )         Pr   ⁡     (       c   t     =   0     )         )       +       r   t   T     ·     (       s   t   i     -     s   t   0       )       +       λ   e   i     ⁡     (   t   )                     =       (     Input   ⁢           ⁢   Extrinsic     )     +     (     Systematic   ⁢           ⁢   LLR     )     +     (     Output   ⁢           ⁢   Extrinsic     )                   
where r 1   T  and z 1   T  are the received vector sequence for the systematic symbols and parity symbols from time 1 to τ, respectively. Also, λ represents log likelihood ratio (LLR).
 
     The quaternary output extrinsic information is obtained from the LLR by: 
                 λ   e   i     ⁡     (   t   )       =         λ   i     ⁡     (   t   )       -     log   ⁡     (       Pr   ⁡     (       c   t     =   i     )         Pr   ⁡     (       c   t     =   0     )         )       -       r   t   T     ·       (       s   t   i     -     s   t   0       )     .               
where λ i (t) is the quaternary log likelihood ratio;
     log   

             (       Pr   ⁡     (       c   t     =   i     )         Pr   ⁡     (       c   t     =   0     )         )         
is the input extrinsic log likelihood ratio, defined by the logarithm of the ratio of the probabilities for systematic symbol c t ;
     r t   T  (s t   i   −s   t   0 ) is the systematic log likelihood ratio (LLR) defined by the vector dot product between the systematic bit LLR vector r t  and the difference between two systematic bit vectors s t   i  and s t   0 .   

     The forward state metrics, reverse state metrics, and the branch metrics are needed to compute the LLR. The forward state metrics are given by: 
                       α   l     ⁡     (   t   )       =     Pr   ⁡     (         S   t     =   l     ,     r   1   t     ,     z   1   t       )                   =       ∑       l   ′     ∈     {     0   ,   …   ⁢           ,   7     }         ⁢         α     l   ′       ⁡     (     t   -   1     )       ⁢       ∑     i   ∈     {     0   ,   …   ⁢           ,   3     }         ⁢       γ       l   ′     ,   l     i     ⁡     (   t   )                         
where S t  is the state at time t. The reverse state metrics are given by:
 
                       β   l     ⁡     (   t   )       =     Pr   ⁡     (       r     t   +   1     τ     ,         z     t   +   1     τ     ❘     S   t       =   l       )                   =       ∑       l   ′     ∈     {     0   ,   …   ⁢           ,   7     }         ⁢         β     l   ′       ⁡     (     t   +   1     )       ⁢       ∑     i   ∈     {     0   ,   …   ⁢           ,   3     }         ⁢       γ     l   ,     l   ′       i     ⁡     (     t   +   1     )                         
The branch metrics are given by
 
                       γ       l   ′     ,   l     i     ⁡     (   t   )       =     Pr   ⁡     (         c   t     =   i     ,       S   t     =   l     ,     r   t     ,         z   t     ❘     S     t   -   1         =     l   ′         )                   =     {             log   ⁢           ⁢     Pr   ⁡     (       c   t     =   i     )         +     (         r   t   T     ·     s   t   i       +       ∑     j   =   1       n   -   1       ⁢       z     j   ,   t     T     ·       v     j   ,   t     i     ⁡     (     l   ′     )             )               for   ⁢           ⁢     (       l   ′     ,   l     )       ∈     B   t   i               0       otherwise                       
where n−1 is the number of parity bits per systematic bit in the constituent encoder, B t   i  is the set of branches connecting state l′ at time t−1 and state l at time t by the quaternary systematic symbol value of i, z j,t  is the parity bit LLR vector for the j th  parity symbol, and v j,t   i (l′) is the BPSK modulated j th  parity bit vector corresponding to c t =i and S t−1 =l′. Also, a are the forward state metrics, β are the reverse state metrics, γ are the branch metrics of rate ⅓ code, and ζ are the branch metrics of rate ⅕ code.
 
Architecture
 
     The following decoder architectural options are discussed herein: Single maximum a posteriori (MAP), single log likelihood ratio computation (LLRC), single MAP dual LLRC, dual MAP single LLRC, and dual MAP dual LLRC. Table 15 is a summary of architecture comparison, showing the major differences among the different architectures.  FIG. 6  illustrates the relative throughput with respect to single maximum a posteriori (MAP) without overhead. That is, in  FIG. 6 , the relative throughput is illustrated versus the number of windows where the unit throughput is the throughput of single MAP without overheads. As expected, all architectures have lower throughput for less number of windows. An alternative solution tailored to a small packet size will be presented below. 
                                         TABLE 15                   SuperTurbo   Single MAP   Single MAP   Dual MAP   Dual MAP           single MAP   single LLRC   dual LLRC   single LLRC   dual LLRC                  Data   2 windows   1 window   1 window   2 windows   2 windows       preloading                           overhead                           MAP engine   1 window   1 window   0   2 windows   0       Overhead                           Systematic   4 windows   3 windows   2 windows   6 windows   4 windows       bits memory                           size                           Systematic   6   4   4   8   8       bits/APP   symbols/clock   symbols/clock   symbols/clock   symbols/clock   symbols/clock       throughput                           requirement                           Systematic   2   2   2   4   4       bits/APP   symbols/clock   symbols/clock   symbols/clock   symbols/clock   symbols/clock       throughput                           requirement                           per loading                           APP   Yes   Possible   Possible   Possible   Possible       memory                           reuse               APP: A Priori Probability or A Posteriori Probability, depending on context.            
The following parameters relate to Table 15.
         1. All architectures are based on radix-4 decoder.   2. Data preloading/MAP engine overheads are shown with respect to the total number of windows.   3. APP throughput requirement is the worse one between read and write for binary APP. Throughput requirement for quaternary APP is lower since three extrinsic symbols can be packed together.   4. APP memory reuse is possible if write is sequential and read is (de)interleaved.       

     One architectural trade-off is whether to use max log or max log*. Since Forward State Metric Computation unit (FSMC) and Reverse State Metric Computation unit (RSMC) must finish state update in a single cycle (otherwise, state update cannot proceed), it is critical to make their timing as short as possible. Table 16 shows the expected timing of FSMC and RSMC in 45 nm. We will discuss mostly max log*, since max log is a subset of max log*. 
     
       
         
           
               
               
               
             
               
                   
                 TABLE 16 
               
               
                   
                   
               
               
                   
                 maxlog* 
                 maxlog 
               
               
                   
                   
               
             
            
               
                   
               
            
           
           
               
               
               
               
            
               
                   
                 FSMC/RSMC 
                 5 ns 
                 3 ns 
               
               
                   
                   
               
            
           
         
       
     
     In one aspect, a SuperTurbo single MAP architecture is shown in  FIG. 7 .  FIG. 7  illustrates an example of a SuperTurbo maximum a posteriori (MAP) architecture. This consists of one FSMC, two RSMCs, three Branch Metric Computation units (BMCs), and one LLRC, with additional memories. Control machines are not shown.  FIG. 8  illustrates an example operational flow diagram of a SuperTurbo single maximum a posteriori (MAP). The operational flow diagram is depicted in  FIG. 8  where α, β 1 , β 2 , and λ denote FSMC, RSMC  1 , RSMC  2  and LLRC, respectively. 
     The example illustrated in  FIG. 8  is for 5 windows. In the example, x-axis is the window index and y-axis is the time index where one time period is the time taken to process one window. Decoder starts with preloading two windows of data. After preloading is done, FSMC starts to compute the forward state metrics of the first window and saves them in memory. At the same time, RSMC  1  computes the reverse state metrics of the second data window that are eventually discarded. Data of the third window is loaded at the same time. One window of data loading continues on each time period. 
     RSMC  1  continues moving onto the first window to compute the reverse state metrics of the first window. As soon as RSMC  1  computes the reverse state metrics on each trellis time in the first window, LLRC uses them together with the saved forward state metrics to compute LLR and extrinsic information. During this period, FSMC computes the forward state metrics of the second data window and saves them. At the same time, RSMC  2  computes the reverse state metrics of the third window. This pattern repeats until the last window is computed. In the example in  FIG. 8 , LLR and extrinsic information are not obtained until time periods 3. Thus the total overhead is 3 time periods, among which two time periods are for preloading data. Also, there are three active windows on which FSMC, RSMC  1 , RSMC  2 , or LLRC is working. Thus 6 systematic and 6 APP symbols are needed per clock cycle. 
       FIG. 9  illustrates an example of a single maximum a posteriori (MAP), single log likelihood ratio computation (LLRC) architecture. In one aspect, the single MAP single LLRC architecture shown in  FIG. 9  comprises one FSMC, one RSMC, two BMCs, and one LLRC, with additional memories. Control machines are not shown in  FIG. 9 .  FIG. 10  illustrates an example operational flow diagram of the single maximum a posteriori (MAP), single log likelihood ratio computation (LLRC) architecture depicted in  FIG. 9  where α, β, and λ denote FSMC, RSMC, and LLRC, respectively. 
     The example illustrated in  FIG. 10  is for 5 windows. In the  FIG. 10  example, x-axis is the window index and y-axis is the time index where one time period is the time taken to process one window. Decoder starts with preloading one window of data. After preloading is done, RSMC starts to compute the reverse state metrics of the first window and saves them in memory. Once RSMC finishes the first window, it moves to the second data window and FSMC starts to compute the forward state metrics of the first window. Data of the second data window is loaded at the same time. One window of data loading continues on each time period. As soon as FSMC computes the forward state metrics on each trellis time in the first window, LLRC uses them together with the saved reverse state metrics to compute LLR and extrinsic information. During this period, RSMC computes the reverse state metrics of the second data window and saves them. This pattern repeats until the last window is computed. 
     In the example, the LLR and extrinsic information are not obtained until time periods 2. Thus the total overhead is 2 time periods, among which one time period is for preloading data. And, there are two active windows on which FSMC, RSMC, or LLRC is working. Thus 4 systematic and 4 APP symbols are needed per clock cycle. APP memory is reusable if de-interleaving is done by read address. The initial state metrics of RSMC at each window are propagated from the last state metrics of the next window obtained from the previous iteration. 
     In another aspect,  FIG. 11  illustrates another example of a single maximum a posteriori (MAP), dual log likelihood ratio computation (LLRC) architecture. And,  FIG. 12  illustrates an example operational flow of the single MAP, dual log likelihood ratio computation (LLRC) architecture for N=3 windows depicted in  FIG. 11 . 
     In another aspect, a dual MAP single LLRC architecture instantiates two of single MAP single LLRC decoders. The total number of windows is equally divided into two halves. One decoder starts from the first window and moves onto the next window. The other decoder starts from the last window and moves onto the previous window. Each decoder computes one half of the total windows. The first decoder is the same as single MAP single LLRC decoder shown in the example in  FIG. 9 .  FIG. 13  illustrates an example of a second decoder of a dual maximum a posteriori (MAP), single log likelihood ratio computation (LLRC) architecture. In the he second decoder illustrated in  FIG. 13 , the FSRM and RSMC are switched and the forward state metrics are saved. 
       FIG. 14  illustrates an example operational flow of the second decoder of the dual maximum a posteriori (MAP), single log likelihood ratio computation (LLRC) architecture for N=6 windows depicted in  FIG. 13 . As depicted in  FIG. 14 , the operational flow on the first half is the same as one for the single maximum a posteriori (MAP), single log likelihood ratio computation (LLRC) decoder. The operational flow on the second half is similarly done. The only difference is that FSMC and RSMC are switched. The first decoder propagates the reverse state metrics between windows and the second decoder propagates the forward state metrics between windows. In the boundary of two decoders, the two decoders exchange the forward and reverse state metrics. 
       FIG. 15  illustrates an example operational flow of dual maximum a posteriori (MAP), dual log likelihood ratio computation (LLRC) for N=6 windows. 
     When a packet size is small, both interleaved and non-interleaved sequences can be stored. Then preloading overhead is only needed for the first iteration. As iteration continues, the preloading overhead diminishes. For example, suppose 17 half iterations and no-window operation for single MAP dual LLRC decoder. Then the overhead of the first half iteration is one window for the non-interleaved data preloading. The overhead of the second half iteration is also one window for the interleaved data preloading. Thus the relative throughput is 17 half iterations/19 window time periods=0.895. 
     In one aspect, a new sliding window scheme with state propagation between adjacent windows is implemented. Depending on which state metrics are first computed and saved, the state propagation is performed mainly in RSMC or in FSMC or both. For illustrational purpose,  FIG. 16  illustrates a state propagation scheme in a single maximum a posteriori (MAP), single log likelihood ratio computation (LLRC) where RSMC utilizes the state propagation scheme. In the RSMC, the final state of the current window is transferred to the previous window on the next iteration and is used as the initial state. This is illustrated in  FIG. 16 .  FIG. 17  illustrates a state propagation scheme in a single maximum a posteriori (MAP), single log likelihood ratio computation (LLRC) where FSMC utilizes the state propagation scheme. In the FSMC, the final state of the current window is continuously used as the initial state of the next window in the same iteration, as illustrated in  FIG. 17 . 
     In one example, there is a small difference between WiMAX mode and non-WiMAX mode. In the RSMC of the WiMAX mode, the final state of the first window is transferred to the last window on the next iteration and is used as the initial state. In the FSMC of the WiMAX mode, the final state of the last window is transferred to the first window on the next iteration and is used as the initial state. In the non-WiMAX mode, there is no need of state transfers between the first window and the last window. The state storages connected to the last window in the RSMC and the first window in the FSMC is initialized to the known states. If no windowing is used in the WiMAX mode, the final states of the RSMC and FSMC are used as the initial states of each unit on the next iteration. If no windowing is used in the non-WiMAX mode, known states are used as the initial states. 
     The disclosed sliding window scheme has two distinctive advantages compared to the conventional sliding window scheme: reduced number of RSMC and reduced computational overhead. 
       FIG. 18  illustrates an operational flow of a conventional sliding window scheme. The conventional sliding window scheme must run RSMC twice as fast as FSMC or equivalently two RSMC for one FSMC, as shown in  FIG. 18 , where α, β 1 , β 2 , are FSMC, RSMC  1 , RSMC  2 , and LLRC, respectively. In the conventional sliding window scheme, the RSMC starts one window ahead of the current window to obtain reliable reverse state metrics. Thus, the RSMC computes two windows, while FSMC and LLRC compute one window. And, two RSMCs are needed. This is illustrated in  FIG. 18  where five windows are for exemplar purpose, and x-axis denotes the window and y-axis denotes the time period to compute the window. A time period is the duration needed to compute one window. As illustrated, two RSMCs, β 1  and β 2 , compute window n and window n+2 alternately. To compute N windows in the conventional sliding window scheme, N+3 time periods are needed. 
       FIG. 19  illustrates an example of an operational flow of a sliding window scheme in accordance with the present disclosure. On the contrary, the sliding window scheme can remove one RSMC, as shown in  FIG. 19 , where the final states propagate through windows in the next iterations. And, only one RSMC is running at any point of the time period. In addition to the reduced number of RSMC, the sliding window scheme needs only N+2 time periods (as opposed to the conventional scheme of needing N+3 time periods) to compute N windows. Thus, one window time period is saved. 
     As shown in Table 15, the worst case throughput requirement for systematic bits and APP are 4 symbols per clock cycle per loading. Thus, De-Rate-Matching block (DRM), which is an inverse operation of rate matching as defined in the standards, is able to provide 4 systematic symbols and corresponding parity symbols per clock. 
     In one example, the WiMAX interleaver has the following properties: a) if j, the address for the duo-binary symbol, is even, then Π(j) is odd; and b) if j is odd, then Π(j) is even. Π stands for the contents of the interleaver. In one example, given two banks, one for even addresses and the other for odd addresses, there are 4 interleaved systematic symbols (two duo-binary symbols) per clock cycle. The LTE interleaver has the following properties: a) if j, the address for the binary symbol, is even, then Π(j) is even; and b) if j is odd, then Π(j) is odd. Since two banks provide only two interleaved systematic (binary) symbols per clock cycle, this LTE interleaver property is not enough. However, the LTE interleaver has an additional property: the address j mod 4 is one-to-one mapped to Π(j) mod 4. This additional property provides 4 interleaved systematic symbols if there are 4 banks and each bank is selected by the interleaved address mod 4; i.e., the two LSBs of the address Π(j). 
     In one example, an EVDO/CDMA interleaver has the following property: the 5 LSBs of address j are one-to-one mapped to the 5 MSBs of Π(j). This property allows for enabling 4 interleaved systematic symbols if there are 4 banks and each bank is selected by 2 MSBs of the address. However, there are addresses dropped by the interleaver and If the addresses dropped are not account for, then the decoder will stall. To avoid stalls, use 8 banks. Also, each bank should have 4 consecutive addresses in a row to provide 4 non-interleaved symbols. 
     In one example, an WCDMA interleaver has the following property: the address j mod 5 is one-to-one mapped to └Π(j)/C┘ mod 5 up to 4 addresses, where C is the number of the column in the interleaver. Here, 5 banks must be used to avoid stalls. Thus, 8 banks are needed for systematic (binary) symbol memory. Each bank contains 4 symbols in one address. The memory access schemes are then tailored to different standards. 
     Regarding MAP engine components, each MAP engine, for example, commonly contains BMC, FSMC, RSMC, and LLRC. In one example, the BMC computes one cycle ahead the branch metrics that are necessary to the FSMC and RSMC, and stores the metrics in a register bank. The branch metric computation depends on the mother code rate only. 
     There are two ways to tag branch metrics: state // systematic bits and systematic bits // parity bits. Tagging is a numbering scheme. The first one is more efficient for the rate ⅕ code and the second one is more efficient for the rate ⅓ code. In one example, the first method is used for cdma2000/EVDO mode and the second method is used for all other modes. 
     Table 17 shows the direct implementation of the branch metric computation for rate ⅓ code. Since a common term in the branch metric eventually cancels in LLR computation, we can add (r(2t+1)+r(2t)+z(2t+1)+z(20)/2−APP0 to all branch metrics. Table 18 is the resultant simplified branch metric computation. Three stages of adders are needed which take approximately 3.6 ns in 45 nm. At the cost of more adders, the three stages can be reduced to two stages since each branch metric is a sum of up to 4 terms.  FIG. 20  illustrates an example of a simplified branch metric computation for rate ⅓ code. 
     
       
         
           
               
               
             
               
                 TABLE 17 
               
               
                   
               
               
                 Branch metric tag 
                   
               
               
                 [x(2t + 1), x(2t), y(2t + 1), y(2t)] 
                 Branch metric 
               
               
                   
               
             
            
               
                 0000 
                 γ 0 (t) = (2 * APP0 + r(2t + 1) + r(2t) + z(2t + 1) + z(2t))/2 
               
               
                 0001 
                 γ 1 (t) = (2 * APP0 + r(2t + 1) + r(2t) + z(2t + 1) − z(2t))/2 
               
               
                 0010 
                 γ 2 (t) = (2 * APP0 + r(2t + 1) + r(2r) − z(2t + 1) + z(2t))/2 
               
               
                 0011 
                 γ 3 (t) = (2 * APP0 + r(2t + 1) + r(2t) − z(2t + 1) − z(2t))/2 
               
               
                 0100 
                 γ 4 (t) = (2 * APP1 + r(2t + 1) − r(2t) + z(2t + 1) + z(2t))/2 
               
               
                 0101 
                 γ 5 (t) = (2 * APP1 + r(2t + 1) − r(2t) + z(2t + 1) − z(2t)/2 
               
               
                 0110 
                 γ 6 (t) = (2 * APP1 + r(2t + 1) − r(2t) − z(2t + 1) + z(2t))/2 
               
               
                 0111 
                 γ 7 (t) = (2 * APP1 + r(2t + 1) − r(2t) − z(2t + 1) − z(2t))/2 
               
               
                 1000 
                 γ 8 (t) = (2 * APP2 − r(2t + 1) + r(2t) + z(2t + 1) + z(2t))/2 
               
               
                 1001 
                 γ 9 (t) = (2 * APP2 − r(2t + 1) + r(2t) + z(2t + 1) − z(2t))/2 
               
               
                 1010 
                 γ 10 (t) = (2 * APP2 − r(2t + 1) + r(2t) − z(2t + 1) + z(2t))/2 
               
               
                 1011 
                 γ 11 (t) = (2 * APP2 − r(2t + 1) + r(2t) − z(2t + 1) − z(2t))/2 
               
               
                 1100 
                 γ 12 (t) = (2 * APP3 − r(2t + 1) − r(2t) + z(2t + 1) + z(2t))/2 
               
               
                 1101 
                 γ 13 (t) = (2 * APP3 − r(2t + 1) − r(2t) + z(2t + 1) − z(2t))/2 
               
               
                 1110 
                 γ 14 (t) = (2 * APP3 − r(2t + 1) − r(2t) − z(2t + 1) + z(2t))/2 
               
               
                 1111 
                 γ 15 (t) = (2 * APP3 − r(2t + 1) − r(2t) − z(2t + 1) − z(2t))/2 
               
               
                   
               
            
           
         
       
     
     
       
         
           
               
               
             
               
                 TABLE 18 
               
               
                   
               
               
                 Branch metric tag 
                   
               
               
                 [x(2t + 1), x(2t), 
               
               
                 y(2t + 1), y(2t)] 
                 Branch metric 
               
               
                   
               
             
            
               
                 0000 
                 γ 0 (t) = r(2t + 1) + r(2t) + z(2t + 1) + z(2t) 
               
               
                 0001 
                 γ 1 (t) = r(2t + 1) + r(2t) + z(2t + 1) 
               
               
                 0010 
                 γ 2 (t) = r(2t + 1) + r(2t) + z(2t) 
               
               
                 0011 
                 γ 3 (t) = r(2t + 1) + r(2t) 
               
               
                 0100 
                 γ 4 (t) = λ e   1 (t) + r(2t + 1) + z(2t + 1) + z(2t) 
               
               
                 0101 
                 γ 5 (t) = λ e   1 (t) + r(2t + 1) + z(2t + 1) 
               
               
                 0110 
                 γ 6 (t) = λ e   1 (t) + r(2t + 1) + z(2t) 
               
               
                 0111 
                 γ 7 (t) = λ e   1 (t) + r(2t + 1) 
               
               
                 1000 
                 γ 8 (t) = λ e   2 (t) + r(2t) + z(2t + 1) + z(2t) 
               
               
                 1001 
                 γ 9 (t) = λ e   2 (t) + r(2t) + z(2t + 1) 
               
               
                 1010 
                 γ 10 (t) = λ e   2 (t) + r(2t) + z(2t) 
               
               
                 1011 
                 γ 11 (t) = λ e   2 (t) + r(2t) 
               
               
                 1100 
                 γ 12 (t) = λ e   3 (t) + z(2t + 1) + z(2t) 
               
               
                 1101 
                 γ 13 (t) = λ e   3 (t) + z(2t + 1) 
               
               
                 1110 
                 γ 14 (t) = λ e   3 (t) + z(2t) 
               
               
                 1111 
                 γ 15 (t) = λ e   3 (t) 
               
               
                   
               
            
           
         
       
     
     Similarly, the simplified branch metric computation for rate ⅕ code is shown in Table 19. The branch metric computation for rate ⅕ needs one more adder stage than the branch metric computation for rate ⅓. Either 3 stages of adders or 4 stages of adders can be used depending on the timing and complexity. 
                         TABLE 19               Branch metric tag           [s2(t), s1(t), s0(t),       x(2t + 1), x(2t)]   Branch metric                  00000   ζ 0 (t) = γ 0 (t) + z1(2t + 1) + z1(2t)       00001   ζ 1 (t) = γ 7 (t)       00010   ζ 2 (t) = γ 10 (t) + z1(2t)       00011   ζ 3 (t) = γ 13 (t) + z1(2t + 1)       00100   ζ 4 (t) = γ 2 (t) + z1(2t)       00101   ζ 5 (t) = γ 5 (t) + z1(2t + 1)       00110   ζ 6 (t) = γ 8 (t) + z1(2t + 1) + z1(2t)       00111   ζ 7 (t) = γ 15 (t)       01000   ζ 8 (t) = γ 3 (t) + z1(2t)       01001   ζ 9 (t) = γ 4 (t) + z1(2t + 1)       01010   ζ 10 (t) = γ 9 (t) + z1(2t + 1) + z1(2t)       01011   ζ 11 (t) = γ 14 (t)       01100   ζ 12 (t) = γ 1 (t) + z1(2t + 1) + z1(2t)       01101   ζ 13 (t) = γ 6 (t)       01110   ζ 14 (t) = γ 11 (t) + z1(2t)       01111   ζ 15 (t) = γ 12 (t) + z1(2t + 1)       10000   ζ 16 (t) = γ 3 (t) + z1(2t + 1)       10001   ζ 17 (t) = γ 4 (t) + z1(2t)       10010   ζ 18 (t) = γ 9 (t)       10011   ζ 19 (t) = γ 14 (t) + z1(2t + 1) + z1(2t)       10100   ζ 20 (t) = γ 1 (t)       10101   ζ 21 (t) = γ 6 (t) + z1(2t + 1) + z1(2t)       10110   ζ 22 (t) = γ 11 (t) + z1(2t + 1)       10111   ζ 23 (t) = γ 3 (t) + z1(2t)       11000   ζ 24 (t) = γ 0 (t)       11001   ζ 25 (t) = γ 7 (t) + z1(2t + 1) + z1(2t)       11010   ζ 26 (t) = γ 10 (t) + z1(2t + 1)       11011   ζ 27 (t) = γ 13 (t) + z1(2t)       11100   ζ 28 (t) = γ 2 (t) + z1(2t + 1)       11101   ζ 29 (t) = γ 5 (t) + z1(2t)       11110   ζ 30 (t) = γ 8 (t)       11111   ζ 31 (t) = γ 15 (t) + z1(2t + 1) + z1(2t)                    
NB: s2(t), s1(t), s0(t) are the encoder states with s0(t) denoting the rightmost state bit.
 
     Regarding APP computation for WiMax, in the WiMAX mode, the extrinsic information for the quaternary symbol is stored. The a priori probability is related to the extrinsic information as follows: 
                   λ   e   i     ⁡     (   t   )       =         log   ⁡     (       Pr   ⁡     (       c   t     =   i     )         Pr   ⁡     (       c   t     =   0     )         )       ⁢           ⁢   for   ⁢           ⁢   i     =   1       ,   2   ,   3                   ∑     i   =   0     3     ⁢     Pr   ⁡     (       c   t     =   i     )         =   1.         
Solving the above two equations, yields:
 
     
       
         
           
             
               
                 
                   
                     APP 
                     0 
                   
                   = 
                   
                     log 
                     ⁡ 
                     
                       ( 
                       
                         Pr 
                         ⁡ 
                         
                           ( 
                           
                             
                               c 
                               t 
                             
                             = 
                             0 
                           
                           ) 
                         
                       
                       ) 
                     
                   
                 
               
             
             
               
                 
                   = 
                   
                     - 
                     
                       log 
                       ⁡ 
                       
                         ( 
                         
                           1 
                           + 
                           
                             ⅇ 
                             
                               
                                 λ 
                                 e 
                                 1 
                               
                               ⁡ 
                               
                                 ( 
                                 t 
                                 ) 
                               
                             
                           
                           + 
                           
                             ⅇ 
                             
                               
                                 λ 
                                 e 
                                 2 
                               
                               ⁡ 
                               
                                 ( 
                                 t 
                                 ) 
                               
                             
                           
                           + 
                           
                             ⅇ 
                             
                               
                                 λ 
                                 e 
                                 3 
                               
                               ⁡ 
                               
                                 ( 
                                 t 
                                 ) 
                               
                             
                           
                         
                         ) 
                       
                     
                   
                 
               
             
           
         
       
       
         
           
             
               
                 
                   
                     APP 
                     i 
                   
                   = 
                   
                     log 
                     ⁡ 
                     
                       ( 
                       
                         Pr 
                         ⁡ 
                         
                           ( 
                           
                             
                               c 
                               t 
                             
                             = 
                             i 
                           
                           ) 
                         
                       
                       ) 
                     
                   
                 
               
             
             
               
                 
                   
                     = 
                     
                       
                         
                           APP 
                           0 
                         
                         + 
                         
                           
                             
                               λ 
                               e 
                               i 
                             
                             ⁡ 
                             
                               ( 
                               t 
                               ) 
                             
                           
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           for 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           9 
                         
                       
                       = 
                       1 
                     
                   
                   , 
                   2 
                   , 
                   3. 
                 
               
             
           
         
       
     
     Regarding APP computation for non-WiMax, in non-WiMAX mode, the extrinsic information for binary symbols is stored. Thus, the binary extrinsic information is converted to the quaternary extrinsic information. Since the systematic bits are independent, the relationship between the quaternary extrinsic information and the binary extrinsic information is as follows: 
                       λ   e   1     ⁡     (   t   )       =     log   ⁡     (       Pr   ⁡     (       c   t     =   1     )         Pr   ⁡     (       c   t     =   0     )         )                   =     log   ⁡     (       Pr   ⁡     (         x       2   ⁢   t     +   1       =   0     ,       x     2   ⁢   t       =   1       )         Pr   ⁡     (         x       2   ⁢   t     +   1       =   0     ,       x     2   ⁢   t       =   0       )         )                   =     log   ⁡     (         Pr   ⁡     (       x       2   ⁢   t     +   1       =   0     )       ⁢     Pr   ⁡     (       x     2   ⁢   t       =   1     )             Pr   ⁡     (       x       2   ⁢   t     +   1       =   0     )       ⁢     Pr   ⁡     (       x     2   ⁢   t       =   0     )           )                   =     log   ⁡     (       Pr   ⁡     (       x     2   ⁢   t       =   1     )         Pr   ⁡     (       x     2   ⁢   t       =   0     )         )                     =       λ   2     ⁡     (     2   ⁢   t     )         ,                           λ   e   2     ⁡     (   t   )       =       λ   e     ⁡     (       2   ⁢   t     +   1     )         ,     
     ⁢         λ   e   3     ⁡     (   t   )       =         λ   e     ⁡     (     2   ⁢   t     )       +       λ   e     ⁡     (       2   ⁢   t     +   1     )                 
where λ e  is the binary extrinsic information.
 
     Reverse state metric computation starts from the end of a window and moves backward in the trellis. In non-WiMAX mode, the initial reverse state metrics of the last window are loaded with trellis ending states obtained from the trellis termination bits irrespective of iteration. In WiMAX mode, it is loaded with all zeros in the beginning. After the first iteration, it is loaded with the final reverse state metrics of the first window. This is due to the tail-biting trellis in WiMAX mode. If no windowing is used, then the final reverse state metrics are used as the initial reverse state metrics of the same window in WiMAX mode. 
     Reverse State Metric Computation 
     Reverse state metric computation starts from the end of a window and moves backward in the trellis. In non-WiMAX mode, the initial reverse state metrics of the last window are loaded with trellis ending states obtained from the trellis termination bits irrespective of iteration. In WiMAX mode, it is loaded with all zeros in the beginning. After the first iteration, it is loaded with the final reverse state metrics of the first window. This is due to the tail-biting trellis in WiMAX mode. If no windowing is used, then the final reverse state metrics are used as the initial reverse state metrics of the same window in WiMAX mode. 
     Tables 20, 21 and 22 show the reverse state metric update for LTE/WCDMA, WiMAX, and cdma2000/EVDO, respectively.  FIG. 21  illustrates an example reverse state metric computation.  FIG. 21  shows the unified update scheme for the RSMC, where update for state 0 is shown. Other states are similarly updated according to Table 20. Note that the RSMC timing is the sum of one mux, one adder, and max log*( ) timings. It will be approximately 0.3+1.2+3.5=5 ns in 45 nm. 
     
       
         
           
               
             
               
                 TABLE 20 
               
               
                   
               
             
            
               
                 β 0 (t) = maxlog * (β 0 (t + 1) + γ 0 (t + 1), β 2 (t + 1) + γ 7 (t + 1), β 4 (t + 1) + γ 10 (t + 1), β 6 (t + 1) + γ 13 (t + 1)) 
               
               
                 β 1 (t) = maxlog * (β 0 (t + 1) + γ 5 (t + 1), β 2 (t + 1) + γ 2 (t + 1), β 4 (t + 1) + γ 15 (t + 1), β 6 (t + 1) + γ 8 (t + 1)) 
               
               
                 β 2 (t) = maxlog * (β 0 (t + 1) + γ 14 (t + 1), β 2 (t + 1) + γ 9 (t + 1), β 4 (t + 1) + γ 4 (t + 1), β 6 (t + 1) + γ 3 (t + 1)) 
               
               
                 β 3 (t) = maxlog * (β 0 (t + 1) + γ 0 (t + 1), β 2 (t + 1) + γ 7 (t + 1), β 4 (t + 1) + γ 10 (t + 1), β 6 (t + 1) + γ 13 (t + 1)) 
               
               
                 β 4 (t) = maxlog * (β 1 (t + 1) + γ 9 (t + 1), β 3 (t + 1) + γ 14 (t + 1), β 5 (t + 1) + γ 3 (t + 1), β 7 (t + 1) + γ 4 (t + 1)) 
               
               
                 β 5 (t) = maxlog * (β 1 (t + 1) + γ 12 (t + 1), β 3 (t + 1) + γ 11 (t + 1), β 5 (t + 1) + γ 6 (t + 1), β 7 (t + 1) + γ 1 (t + 1)) 
               
               
                 β 6 (t) = maxlog * (β 1 (t + 1) + γ 7 (t + 1), β 3 (t + 1) + γ 0 (t + 1), β 5 (t + 1) + γ 13 (t + 1), β 7 (t + 1) + γ 10 (t + 1)) 
               
               
                 β 7 (t) = maxlog * (β 1 (t + 1) + γ 2 (t + 1), β 3 (t + 1) + γ 5 (t + 1), β 5 (t + 1) + γ 8 (t + 1), β 7 (t + 1) + γ 15 (t + 1)) 
               
               
                   
               
            
           
         
       
     
     
       
         
           
               
             
               
                 TABLE 21 
               
               
                   
               
             
            
               
                 β 0 (t) = maxlog * (β 0 (t + 1) + γ 0 (t + 1), β 3 (t + 1) + γ 12 (t + 1), β 4 (t + 1) + γ 7 (t + 1), β 7 (t + 1) + γ 11 (t + 1)) 
               
               
                 β 1 (t) = maxlog * (β 0 (t + 1) + γ 7 (t + 1), β 3 (t + 1) + γ 11 (t + 1), β 4 (t + 1) + γ 0 (t + 1), β 7 (t + 1) + γ 12 (t + 1)) 
               
               
                 β 2 (t) = maxlog * (β 1 (t + 1) + γ 1 (t + 1), β 2 (t + 1) + γ 13 (t + 1), β 5 (t + 1) + γ 6 (t + 1), β 6 (t + 1) + γ 10 (t + 1)) 
               
               
                 β 3 (t) = maxlog * (β 1 (t + 1) + γ 6 (t + 1), β 2 (t + 1) + γ 10 (t + 1), β 5 (t + 1) + γ 1 (t + 1), β 6 (t + 1) + γ 13 (t + 1)) 
               
               
                 β 4 (t) = maxlog * (β 1 (t + 1) + γ 8 (t + 1), β 2 (t + 1) + γ 4 (t + 1), β 5 (t + 1) + γ 15 (t + 1), β 6 (t + 1) + γ 3 (t + 1)) 
               
               
                 β 5 (t) = maxlog * (β 1 (t + 1) + γ 15 (t + 1), β 2 (t + 1) + γ 3 (t + 1), β 5 (t + 1) + γ 8 (t + 1), β 6 (t + 1) + γ 4 (t + 1)) 
               
               
                 β 6 (t) = maxlog * (β 0 (t + 1) + γ 9 (t + 1), β 3 (t + 1) + γ 5 (t + 1), β 4 (t + 1) + γ 14 (t + 1), β 7 (t + 1) + γ 2 (t + 1)) 
               
               
                 β 7 (t) = maxlog * (β 0 (t + 1) + γ 14 (t + 1), β 3 (t + 1) + γ 2 (t + 1), β 4 (t + 1) + γ 9 (t + 1), β 7 (t + 1) + γ 5 (t + 1)) 
               
               
                   
               
            
           
         
       
     
                     TABLE 22                  β 0 (t) = maxlog * (β 0 (t + 1) + ζ 0 (t + 1), β 2 (t + 1) + ζ 1 (t + 1), β 4 (t + 1) + ζ 2 (t + 1), β 6 (t + 1) + ζ 3 (t + 1))       β 1 (t) = maxlog * (β 0 (t + 1) + ζ 5 (t + 1), β 2 (t + 1) + ζ 4 (t + 1), β 4 (t + 1) + ζ 7 (t + 1), β 6 (t + 1) + ζ 6 (t + 1))       β 2 (t) = maxlog * (β 0 (t + 1) + ζ 11 (t + 1), β 2 (t + 1) + ζ 10 (t + 1), β 4 (t + 1) + ζ 9 (t + 1), β 6 (t + 1) + ζ 8 (t + 1))       β 3 (t) = maxlog * (β 0 (t + 1) + ζ 14 (t + 1), β 2 (t + 1) + ζ 15 (t + 1), β 4 (t + 1) + ζ 12 (t + 1), β 6 (t + 1) + ζ 13 (t + 1))       β 4 (t) = maxlog * (β 1 (t + 1) + ζ 18 (t + 1), β 3 (t + 1) + ζ 19 (t + 1), β 5 (t + 1) + ζ 16 (t + 1), β 7 (t + 1) + ζ 17 (t + 1))       β 5 (t) = maxlog * (β 1 (t + 1) + ζ 23 (t + 1), β 3 (t + 1) + ζ 22 (t + 1), β 5 (t + 1) + ζ 21 (t + 1), β 7 (t + 1) + ζ 20 (t + 1))       β 6 (t) = maxlog * (β 1 (t + 1) + ζ 25 (t + 1), β 3 (t + 1) + ζ 24 (t + 1), β 5 (t + 1) + ζ 27 (t + 1), β 7 (t + 1) + ζ 26 (t + 1))       β 7 (t) = maxlog * (β 1 (t + 1) + ζ 28 (t + 1), β 3 (t + 1) + ζ 29 (t + 1), β 5 (t + 1) + ζ 30 (t + 1), β 7 (t + 1) + ζ 31 (t + 1))                    
Forward State Metric Computation
 
     Forward state metric computation starts from the beginning of the window and moves forward in the trellis. The initial forward state metrics of the first window are known in the non-WiMAX mode (state 0 is the starting state). Thus, these known state metrics of the first window are used in all iterations. In WiMAX mode, it is loaded with all zeros in the beginning. After the first iteration, it is loaded with the final forward state metrics of the last window. This is due to the tail-biting trellis in WiMAX mode. If no windowing is used, then the final forward state metrics are used as the initial forward state metrics of the same window in WiMAX mode. 
     Tables 23, 24 and 25 show the forward state metric update for LTE/WCDMA, WiMAX, and cdma2000/EVDO, respectively. The timing for FSMC and RSMC are the same. 
     
       
         
           
               
             
               
                 TABLE 23 
               
               
                   
               
             
            
               
                 α 0 (t) = maxlog * (α 0 (t − 1) + γ 0 (t), α 1 (t − 1) + γ 5 (t), α 2 (t − 1) γ 14 (t), α 3 (t − 1) + γ 11 (t)) 
               
               
                 α 1 (t) = maxlog * (α 4 (t − 1) + γ 9 (t), α 5 (t − 1) + γ 12 (t), α 6 (t − 1) + γ 7 (t), α 7 (t − 1) + γ 2 (t)) 
               
               
                 α 2 (t) = maxlog * (α 0 (t − 1) + γ 7 (t), α 1 (t − 1) + γ 2 (t), α 2 (t − 1) + γ 9 (t), α 3 (t − 1) + γ 12 (t)) 
               
               
                 α 3 (t) = maxlog * (α 4 (t − 1) + γ 14 (t), α 5 (t − 1) + γ 11 (t), α 6 (t − 1) + γ 0 (t), α 7 (t − 1) + γ 5 (t)) 
               
               
                 α 4 (t) = maxlog * (α 0 (t − 1) + γ 10 (t), α 1 (t − 1) + γ 15 (t), α 2 (t − 1) + γ 4 (t), α 3 (t − 1) + γ 1 (t)) 
               
               
                 α 5 (t) = maxlog * (α 4 (t − 1) + γ 3 (t), α 5 (t − 1) + γ 6 (t), α 6 (t − 1) + γ 13 (t), α 7 (t − 1) + γ 8 (t)) 
               
               
                 α 6 (t) = maxlog * (α 0 (t − 1) + γ 13 (t), α 1 (t − 1) + γ 8 (t), α 2 (t − 1) + γ 3 (t), α 3 (t − 1) + γ 6 (t)) 
               
               
                 α 7 (t) = maxlog * (α 4 (t − 1) + γ 4 (t), α 5 (t − 1) + γ 1 (t), α 6 (t − 1) + γ 10 (t), α 7 (t − 1) + γ 15 (t)) 
               
               
                   
               
            
           
         
       
     
     
       
         
           
               
             
               
                 TABLE 24 
               
               
                   
               
             
            
               
                 α 0 (t) = maxlog * (α 0 (t − 1) + γ 0 (t), α 1 (t − 1) + γ 7 (t), α 6 (t − 1) + γ 9 (t), α 7 (t − 1) + γ 14 (t)) 
               
               
                 α 1 (t) = maxlog * (α 2 (t − 1) + γ 1 (t), α 3 (t − 1) + γ 6 (t), α 4 (t − 1) + γ 8 (t), α 5 (t − 1) + γ 15 (t)) 
               
               
                 α 2 (t) = maxlog * (α 2 (t − 1) + γ 13 (t), α 3 (t − 1) + γ 10 (t), α 4 (t − 1) + γ 4 (t), α 5 (t − 1) + γ 3 (t)) 
               
               
                 α 3 (t) = maxlog * (α 0 (t − 1) + γ 12 (t), α 1 (t − 1) + γ 11 (t), α 6 (t − 1) + γ 5 (t), α 7 (t − 1) + γ 2 (t)) 
               
               
                 α 4 (t) = maxlog * (α 0 (t − 1) + γ 7 (t), α 1 (t − 1) + γ 0 (t), α 6 (t − 1) + γ 14 (t), α 7 (t − 1) + γ 9 (t)) 
               
               
                 α 5 (t) = maxlog * (α 2 (t − 1) + γ 6 (t), α 3 (t − 1) + γ 1 (t), α 4 (t − 1) + γ 15 (t), α 5 (t − 1) + γ 8 (t)) 
               
               
                 α 6 (t) = maxlog * (α 0 (t − 1) + γ 10 (t), α 3 (t − 1) + γ 13 (t), α 4 (t − 1) + γ 3 (t), α 5 (t − 1) + γ 4 (t)) 
               
               
                 α 7 (t) = maxlog * (α 0 (t − 1) + γ 11 (t), α 1 (t − 1) + γ 12 (t), α 6 (t − 1) + γ 2 (t), α 7 (t − 1) + γ 5 (t)) 
               
               
                   
               
            
           
         
       
     
                     TABLE 25                  α 0 (t) = maxlog * (α 0 (t − 1) + ζ 0 (t), α 1 (t − 1) + ζ 5 (t), α 2 (t − 1) + ζ 11 (t), α 3 (t − 1) + ζ 14 (t))       α 1 (t) = maxlog * (α 4 (t − 1) + ζ 18 (t), α 5 (t − 1) + ζ 23 (t), α 6 (t − 1) + ζ 25 (t), α 7 (t − 1) + ζ 28 (t))       α 2 (t) = maxlog * (α 0 (t − 1) + ζ 1 (t), α 1 (t − 1) + ζ 4 (t), α 2 (t − 1) + ζ 10 (t), α 3 (t − 1) + ζ 15 (t))       α 3 (t) = maxlog * (α 4 (t − 1) + ζ 19 (t), α 5 (t − 1) + ζ 22 (t), α 6 (t − 1) + ζ 24 (t), α 7 (t − 1) + ζ 29 (t))       α 4 (t) = maxlog * (α 0 (t − 1) + ζ 2 (t), α 1 (t − 1) + ζ 7 (t), α 2 (t − 1) + ζ 9 (t), α 3 (t − 1) + ζ 12 (t))       α 5 (t) = maxlog * (α 4 (t − 1) + ζ 16 (t), α 5 (t − 1) + ζ 21 (t), α 6 (t − 1) + ζ 27 (t), α 7 (t − 1) + ζ 30 (t))       α 6 (t) = maxlog * (α 0 (t − 1) + ζ 3 (t), α 1 (t − 1) + ζ 6 (t), α 2 (t − 1) + ζ 8 (t), α 3 (t − 1) + ζ 13 (t))       α 7 (t) = maxlog * (α 4 (t − 1) + ζ 17 (t), α 5 (t − 1) + ζ 20 (t), α 6 (t − 1) + ζ 26 (t), α 7 (t − 1) + ζ 31 (t))                    
LLR Computation
 
     LLRC starts to compute the LLR and the extrinsic information as soon as the forward state metric at trellis time t and the reverse state metric at trellis time t+1 are available. In one example, state by computing APP. Tables 26, 27 and 28 show the APP computations for LTE/WCDMA, WiMax and CDMA2000/EVDO, respectively. 
     
       
         
           
               
             
               
                 TABLE 26 
               
               
                   
               
             
            
               
                 p 0 (t) = maxlog * (α 0 (t) + β 0 (t + 1) + γ 0 (t + 1), α 1 (t) + β 2 (t + 1) + γ 2 (t + 1), α 2 (t) + β 6 (t + 1) + γ 3 (t + 1), 
               
               
                 α 3 (t) + β 4 (t + 1) + γ 1 (t + 1), α 4 (t) + β 5 (t + 1) + γ 3 (t + 1), α 5 (t) + β 7 (t + 1) + γ 1 (t + 1), 
               
               
                 α 6 (t) + β 3 (t + 1) + γ 0 (t + 1), α 7 (t) + β 1 (t + 1) + γ 2 (t + 1)) 
               
               
                 p 1 (t) = maxlog * (α 0 (t) + β 2 (t + 1) + γ 7 (t + 1), α 1 (t) + β 0 (t + 1) + γ 5 (t + 1), α 2 (t) + β 4 (t + 1) + γ 4 (t + 1), 
               
               
                 α 3 (t) + β 6 (t + 1) + γ 6 (t + 1), α 4 (t) + β 7 (t + 1) + γ 4 (t + 1), α 5 (t) + β 5 (t + 1) + γ 6 (t + 1), 
               
               
                 α 6 (t) + β 1 (t + 1) + γ 7 (t + 1), α 7 (t) + β 3 (t + 1) + γ 5 (t + 1)) 
               
               
                 p 2 (t) = maxlog * (α 0 (t) + β 4 (t + 1) + γ 10 (t + 1), α 1 (t) + β 6 (t + 1) + γ 8 (t + 1), α 2 (t) + β 2 (t + 1) + γ 9 (t + 1), 
               
               
                 α 3 (t) + β 0 (t + 1) + γ 11 (t + 1), α 4 (t) + β 1 (t + 1) + γ 9 (t + 1), α 5 (t) + β 3 (t + 1) + γ 11 (t + 1), 
               
               
                 α 6 (t) + β 7 (t + 1) + γ 10 (t + 1), α 7 (t) + β 5 (t + 1) + γ 8 (t + 1)) 
               
               
                 p 3 (t) = maxlog * (α 0 (t) + β 6 (t + 1) + γ 13 (t + 1), α 1 (t) + β 4 (t + 1) + γ 15 (t + 1), 
               
               
                 α 2 (t) + β 0 (t + 1) + γ 14 (t + 1), α 3 (t) + β 2 (t + 1) + γ 12 (t + 1), α 4 (t) + β 3 (t + 1) + γ 14 (t + 1), 
               
               
                 α 5 (t) + β 1 (t + 1) + γ 12 (t + 1), α 6 (t) + β 5 (t + 1) + γ 13 (t + 1), α 7 (t) + β 7 (t + 1) + γ 15 (t + 1)) 
               
               
                   
               
            
           
         
       
     
     
       
         
           
               
             
               
                 TABLE 27 
               
               
                   
               
             
            
               
                 p 0 (t) = maxlog * (α 0 (t) + β 0 (t + 1) + γ 0 (t + 1), α 1 (t) + β 4 (t + 1) + γ 0 (t + 1), α 2 (t) + β 1 (t + 1) + γ 1 (t + 1), 
               
               
                 α 3 (t) + β 5 (t + 1) + γ 1 (t + 1), α 4 (t) + β 6 (t + 1) + γ 3 (t + 1), α 5 (t) + β 2 (t + 1) + γ 3 (t + 1), 
               
               
                 α 6 (t) + β 7 (t + 1) + γ 2 (t + 1), α 7 (t) + β 3 (t + 1) + γ 2 (t + 1)) 
               
               
                 p 1 (t) = maxlog * (α 0 (t) + β 4 (t + 1) + γ 7 (t + 1), α 1 (t) + β 0 (t + 1) + γ 7 (t + 1), α 2 (t) + β 5 (t + 1) + γ 6 (t + 1), 
               
               
                 α 3 (t) + β 1 (t + 1) + γ 6 (t + 1), α 4 (t) + β 2 (t + 1) + γ 4 (t + 1), α 5 (t) + β 6 (t + 1) + γ 4 (t + 1), 
               
               
                 α 6 (t) + β 3 (t + 1) + γ 5 (t + 1), α 7 (t) + β 7 (t + 1) + γ 5 (t + 1)) 
               
               
                 p 2 (t) = maxlog * (α 0 (t) + β 7 (t + 1) + γ 11 (t + 1), α 1 (t) + β 3 (t + 1) + γ 11 (t + 1), 
               
               
                 α 2 (t) + β 6 (t + 1) + γ 10 (t + 1), α 3 (t) + β 2 (t + 1) + γ 10 (t + 1), α 4 (t) + β 1 (t + 1) + γ 8 (t + 1), 
               
               
                 α 5 (t) + β 5 (t + 1) + γ 8 (t + 1), α 6 (t) + β 0 (t + 1) + γ 9 (t + 1), α 7 (t) + β 4 (t + 1) + γ 9 (t + 1)) 
               
               
                 p 3 (t) = maxlog * (α 0 (t) + β 3 (t + 1) + γ 12 (t + 1), α 1 (t) + β 7 (t + 1) + γ 12 (t + 1), 
               
               
                 α 2 (t) + β 2 (t + 1) + γ 13 (t + 1), α 3 (t) + β 6 (t + 1) + γ 13 (t + 1), α 4 (t) + β 5 (t + 1) + γ 15 (t + 1), 
               
               
                 α 5 (t) + β 1 (t + 1) + γ 15 (t + 1), α 6 (t) + β 4 (t + 1) + γ 14 (t + 1), α 7 (t) + β 0 (t + 1) + γ 14 (t + 1)) 
               
               
                   
               
            
           
         
       
     
     
       
         
           
               
             
               
                 TABLE 28 
               
               
                   
               
             
            
               
                 p 0 (t) = maxlog * (α 0 (t) + β 0 (t + 1) + ζ 0 (t + 1), α 1 (t) + β 2 (t + 1) + ζ 4 (t + 1), α 2 (t) + β 6 (t + 1) + ζ 8 (t + 1), 
               
               
                 α 3 (t) + β 4 (t + 1) + ζ 12 (t + 1), α 4 (t) + β 5 (t + 1) + ζ 16 (t + 1), α 5 (t) + β 7 (t + 1) + ζ 20 (t + 1), 
               
               
                 α 6 (t) + β 3 (t + 1) + ζ 24 (t + 1), α 7 (t) + β 1 (t + 1) + ζ 28 (t + 1)) 
               
               
                 p 1 (t) = maxlog * (α 0 (t) + β 2 (t + 1) + ζ 1 (t + 1), α 1 (t) + β 0 (t + 1) + ζ 5 (t + 1), α 2 (t) + β 4 (t + 1) + ζ 9 (t + 1), 
               
               
                 α 3 (t) + β 6 (t + 1) + ζ 13 (t + 1), α 4 (t) + β 7 (t + 1) + ζ 17 (t + 1), α 5 (t) + β 5 (t + 1) + ζ 21 (t + 1), 
               
               
                 α 6 (t) + β 1 (t + 1) + ζ 25 (t + 1), α 7 (t) + β 3 (t + 1) + ζ 29 (t + 1)) 
               
               
                 p 2 (t) = maxlog * (α 0 (t) + β 4 (t + 1) + ζ 2 (t + 1), α 1 (t) + β 6 (t + 1) + ζ 6 (t + 1), 
               
               
                 α 2 (t) + β 2 (t + 1) + ζ 10 (t + 1), α 3 (t) + β 0 (t + 1) + ζ 14 (t + 1), α 4 (t) + β 1 (t + 1) + ζ 18 (t + 1), 
               
               
                 α 5 (t) + β 3 (t + 1) + ζ 22 (t + 1), α 6 (t) + β 7 (t + 1) + ζ 26 (t + 1), α 7 (t) + β 5 (t + 1) + ζ 30 (t + 1)) 
               
               
                 p 3 (t) = maxlog * (α 0 (t) + β 6 (t + 1) + ζ 3 (t + 1), α 1 (t) + β 4 (t + 1) + ζ 7 (t + 1), 
               
               
                 α 2 (t) + β 0 (t + 1) + ζ 11 (t + 1), α 3 (t) + β 2 (t + 1) + ζ 15 (t + 1), α 4 (t) + β 3 (t + 1) + ζ 19 (t + 1), 
               
               
                 α 5 (t) + β 1 (t + 1) + ζ 23 (t + 1), α 6 (t) + β 5 (t + 1) + ζ 27 (t + 1), α 7 (t) + β 7 (t + 1) + ζ 31 (t + 1)) 
               
               
                   
               
            
           
         
       
     
     LLR is obtained by:
 
λ i ( t )= p   i ( t )− p   o ( t ) for  i= 1,2,3.
 
The extrinsic information is obtained by:
 
λ e   i ( t )=λ i ( t )−λ ie   i ( t )− r   t   T   ·s   t   i .
 
where λ ie  is the intrinsic information.
 
     The LLRC uses a max log of 8 elements that is obtained by a cascade of max log* of 2 elements with two max logs of 4 elements. Max log is an approximation of the log of the sum of the exponential terms (i.e., log (e a1 + . . . +e an )=max(a 1 , . . . , a n )). 
               max   ⁢           ⁢       log   *     ⁡     (       ∑     i   =   0     7     ⁢     a   i       )         ≃     max   ⁢           ⁢         log   *     ⁡     (       max   ⁢           ⁢       log   *     ⁡     (       ∑     i   =   0     3     ⁢     a   i       )         ,     max   ⁢           ⁢       log   *     ⁡     (       ∑     i   =   4     7     ⁢     a   i       )           )       .             
As understood by one skilled in the art, max log* is max log with compensation term(s). Then, the LLRC timing is the sum of two stages of adders, 2 stages of max log*s, and three stages of adders. The LLRC computation is divided into four pipeline stages as:
 
     1. Two stages of adders for the sum of α, β, and γ 
     2. Two max log*s of 4 elements 
     3. One max log* of two elements 
     4. Three stages of adders for λ and λ e    
       FIG. 22   a  illustrates an example diagram of log likelihood ratio (LLR) computation.  FIG. 22   b  illustrates an example diagram of APP computation for symbol value 0. 
       FIG. 23  illustrates an example receiver block diagram for implementing turbo decoding. In one aspect, the receiver  2300  comprises an antenna  2310 , a receiver front-end  2320 , a demodulator  2330 , a turbo decoder  2340  and a post-processing unit  2350 . The antenna  2310  receives electromagnetic waves comprising a received signal which are inputted to the receiver front-end. In the receiver front-end  2320 , the received signal is amplified, downconverted, filtered and/or analog-to-digital converted to output a digital waveform. From the output of the receiver front-end, the digital waveform is then inputted into the demodulator  2330 . The demodulator  2330  demodulates the digital waveform according to the modulation techniques previously applied, for example, binary phase shift keying (BPSK), quadrature phase shift keying (QPSK), M-ary phase shift keying (M-PSK), quadrature amplitude modulation (QAM), or frequency shift keying (FSK), etc. 
     The output of the demodulator  2330 , a demodulated bit stream, is then inputted to the turbo decoder  2340 . High throughput unified turbo decoding techniques are disclosed in the present disclosure. The decoded bits outputted from the turbo decoder are inputted to a post-processing unit  2350 . In one example, the decoded bits are further processed by the post-processing unit  2350  which deinterleaves, decrypts, and/or decompresses, etc. In one aspect, the decoded bits or the post-processed decoded bits are routed to another destination, such as but not limited to, a network node, a router and/or switch, etc. 
       FIG. 24  is an example flow diagram for high throughput unified turbo decoding. In block  2400 , load data from a first data window. In one aspect, a data window is a time interval portion of a demodulated bit stream inputted to a turbo decoder. In block  2410 , compute at least one forward state metric using the data from the first data window and store the at least one forward state metric in a memory. Following block  2410 , in block  2420 , compute at least one reverse state metric using the data from the first data window and store the at least one reverse state metric in the memory. In another aspect, the reverse state metric is computed before the forward state metric and stored in the memory before proceeding to computing the forward state metric and storing it in the memory. One skilled in the art would understand that the sequential order of computing the forward state metric and the reverse state metric can be done in any order without affecting the spirit and scope of the present disclosure. 
     Following block  2420 , in block  2430 , compute the log likelihood ratio (LLR) of the at least one forward state metric and the at least one reverse state metric and compute the extrinsic information. The extrinsic information is fed back to the decoder input. In one aspect, the extrinsic information is defined by equation (1) 
                       λ   e   i     ⁡     (   t   )       =         λ   i     ⁡     (   t   )       -     log   ⁡     (       Pr   ⁡     (       c   t     =   i     )         Pr   ⁡     (       c   t     =   0     )         )       -       r   t   T     ·       (       s   t   i     -     s   t   0       )     .                 (   1   )               
Following block  2430 , in block  2440 , repeat the steps in blocks  2400  through  2430  using data from a second data window. One skilled in the art would understand that the steps in blocks  2400  through  2430  can be repeated multiple times using data from multiple data windows. In one aspect, the computed LLR is further inputted into a post processing unit. In another aspect, the extrinsic information is fed back to the decoder input.
 
       FIG. 25  is an example flow diagram for high throughput unified turbo decoding for a single maximum a posteriori (MAP), single log likelihood ratio computation (LLRC) architecture. In block  2510 , load data from a first data window. Following block  2510 , in block  2520 , compute a first reverse state metric using the data loaded from the first data window and store the first reverse state metric in a memory. Following block  2520 , in block  2530 , compute a first forward state metric using the data loaded from the first data window and store the first forward state metric in the memory. In parallel with the step of block  2530 , perform the step in block  2535 . In block  2535 , load data from a second data window. Following block  2530 , in block  2540 , compute the log likelihood ratio (LLR) of the first forward state metric and the first reverse state metric and compute the extrinsic information. In one aspect, the extrinsic information is defined by equation (1). 
     In parallel with the step of block  2540 , perform the step in block  2545 . In block  2545 , compute a second reverse state metric using data from the second data window and store the second reverse state metric in the memory. Following block  2545 , in block  2555 , compute a second forward state metric using data from the second data window and store the second forward state metric in the memory. In one aspect, the memory used for storing the second reverse state metric and the second forward state metric is the same as the memory for storing the first reverse state metric and the first forward state metric. In another aspect, different memories are used. Following block  2555 , in block  2565 , compute the log likelihood ratio (LLR) of the second forward state metric and the second reverse state metric and compute the extrinsic information. In one aspect, the computed LLR and is further inputted to a post processing unit. In another aspect, the extrinsic information is fed back to the decoder input. 
       FIG. 26  is an example flow diagram for high throughput unified turbo decoding for a dual maximum a posteriori (MAP), single log likelihood ratio computation (LLRC) architecture. In block  2610 , load data from a first data window and load data from a last data window. The last data window is the data window that is the last in a sequence of data windows in a data stream received by a turbo decoder. Following block  2610 , in block  2620 , compute a first reverse state metric using data from the first data window and store the first reverse state metric in a memory. In parallel to the step of block  2620 , perform the step of block  2623  and the step of block  2625 . In block  2623 , compute a last forward state metric using data from the last data window and store the last forward state metric in the memory. In block  2625 , load data from a second data window and load data from a next-to-last data window. The next-to-last data window is the data window that is the second to the last in a sequence of data windows in the data stream received by the turbo decoder. 
     Following block  2620 , in block  2630 , compute a first forward state metric using data from the first data window and compute the log likelihood ratio (LLR) of the first reverse state metric and the first forward state metric. In one aspect, the first forward state metric is stored in the memory. In parallel to the step of block  2630 , perform the steps of block  2633 , block  2635  and block  2638 . In block  2633 , compute a last reverse state metric using data from the last data window and compute the log likelihood ratio (LLR) of the last reverse state metric and the last forward state metric. In one aspect, the last reverse state metric is stored in the memory. In block  2635 , compute a second reverse state metric using data from the second data window. In block  2638 , compute a next-to-last forward state metric using data from the next-to-last data window. In one aspect, the second reverse state metric and the next-to-last forward state metric are stored in the memory. 
     Following block  2635 , in block  2645 , compute a second forward state metric using data from the second data window. In one aspect, the second forward state metric is stored in the memory. In parallel to the step of block  2645 , perform the step of block  2648 . In block  2648 , compute the next-to-last reverse state metric using data from the next-to-last data window and compute the log likelihood ratio (LLR) of the next-to-last reverse state metric and the next-to-last forward state metric. In one aspect, the next-to-last reverse state metric is stored in the memory. In one aspect, the same memory is used for storing all the reverse state metrics and the forward state metrics. In another aspect, one or more different memories are used. In one aspect, one or more of the computed LLR is inputted into a post-processing unit for further processing. 
       FIG. 27  is an example flow diagram for high throughput unified turbo decoding for a single maximum a posteriori (MAP) architecture. In block  2710 , load data from a first data window and load data from a second data window. Following block  2710 , perform the steps of block  2720 , block  2725  and block  2728  in parallel. In block  2720 , compute a first forward state metric using data from the first data window and store the first forward state metric in a memory. In block  2725 , compute a second reverse state metric using data from the second data window. In block  2728 , load data from a third data window. 
     Following blocks  2720 ,  2725  and  2728 , perform the steps of block  2730 , block  2735  and block  2738  in parallel. In block  2730 , compute a first reverse state metric using data from the first data window. In block  2735 , compute a second forward state metric using data from the second data window and store the second forward state metric in the memory. In block  2738 , compute a third reverse state metric using data from the third data window. 
     Following blocks  2730 ,  2735  and  2738 , perform the steps from block  2740 , block  2745  and block  2748 . In block  2740 , compute the log likelihood ratio (LLR) of the first forward state metric and the first reverse state metric and compute the extrinsic information. In one aspect, the extrinsic information is defined by equation (1). 
     In block  2745 , compute a second reverse state metric using data from the second data window. In block  2748 , compute a third forward state metric using data from the third data window and store the third forward state metric in the memory. Following blocks  2740 ,  2745  and  2748 , perform the steps of block  2755  and block  2758  in parallel. In block  2755 , compute the LLR of the second reverse state metric and the second forward state metric and compute the extrinsic information. In one aspect, the extrinsic information is defined by equation (1). 
     In block  2758 , compute a third reverse state metric using the data from the third data window. Following block  2758 , in block  2768 , compute the LLR of the third reverse state metric and the third forward state metric and compute the extrinsic information. In one aspect, the extrinsic information is defined by equation (1). In one aspect, one or more of the computed LLR is inputted into a post-processing unit for further processing. 
     One skilled in the art would understand that the steps disclosed in each of the example flow diagrams in  FIGS. 24-27  can be interchanged in their order without departing from the scope and spirit of the present disclosure. Also, one skilled in the art would understand that the steps illustrated in the flow diagram are not exclusive and other steps may be included or one or more of the steps in the example flow diagram may be deleted without affecting the scope and spirit of the present disclosure. 
     Those of skill would further appreciate that the various illustrative components, logical blocks, modules, circuits, and/or algorithm steps described in connection with the examples disclosed herein may be implemented as electronic hardware, firmware, computer software, or combinations thereof. To clearly illustrate this interchangeability of hardware, firmware and software, various illustrative components, blocks, modules, circuits, and/or algorithm steps have been described above generally in terms of their functionality. Whether such functionality is implemented as hardware, firmware or software depends upon the particular application and design constraints imposed on the overall system. Skilled artisans may implement the described functionality in varying ways for each particular application, but such implementation decisions should not be interpreted as causing a departure from the scope or spirit of the present disclosure. 
     For example, for a hardware implementation, the processing units may be implemented within one or more application specific integrated circuits (ASICs), digital signal processors (DSPs), digital signal processing devices (DSPDs), programmable logic devices (PLDs), field programmable gate arrays (FPGAs), processors, controllers, micro-controllers, microprocessors, other electronic units designed to perform the functions described therein, or a combination thereof. With software, the implementation may be through modules (e.g., procedures, functions, etc.) that perform the functions described therein. The software codes may be stored in memory units and executed by a processor unit. Additionally, the various illustrative flow diagrams, logical blocks, modules and/or algorithm steps described herein may also be coded as computer-readable instructions carried on any computer-readable medium known in the art or implemented in any computer program product known in the art. 
     In one example, the illustrative components, flow diagrams, logical blocks, modules and/or algorithm steps described herein are implemented or performed with one or more processors. In one aspect, a processor is coupled with a memory which stores data, metadata, program instructions, etc. to be executed by the processor for implementing or performing the various flow diagrams, logical blocks and/or modules described herein.  FIG. 28  illustrates an example of a device  2800  comprising a processor  2810  in communication with a memory  2820  for executing the processes for high throughput unified turbo decoding. In one example, the device  2800  is used to implement any of the algorithms illustrated in  FIGS. 24-27 . In one aspect, the memory  2820  is located within the processor  2810 . In another aspect, the memory  2820  is external to the processor  2810 . In one aspect, the processor includes circuitry for implementing or performing the various flow diagrams, logical blocks and/or modules described herein. 
     In one aspect, each of the blocks illustrated in  FIGS. 24-27  are replaced with modules wherein each module comprises hardware, firmware, software, or any combination thereof for implementing the steps in the corresponding blocks. In one example, the blocks are implemented by at least one memory in communication with the at least one processor. 
     The previous description of the disclosed aspects is provided to enable any person skilled in the art to make or use the present disclosure. Various modifications to these aspects will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other aspects without departing from the spirit or scope of the disclosure.