Abstract:
The invention relates to methods and apparatus for Turbo Code interleavers for use with third generation code division multiple access (3G CDMA) data. The apparatus includes a memory for receiving and temporarily storing the data, a counter and a clock coupled to the memory and counter for synchronization. The apparatus also includes a table containing a addresses that are selected by the counter. A puncturing device coupled to the table discards addresses if they are greater than a frame size. A buffer is coupled to the memory and the clock. The memory is configured to retrieve data from the selected addresses which are not discarded and forward it to the buffer for output.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS This application claims the benefit of U.S. Provisional Application No. 60/111,747, filed Dec. 10, 1998. 
    
    
     FIELD OF THE INVENTION 
     This invention relates to the field of electronic communications systems and, more particularly, to interleavers for permuting data for communications in these systems. 
     BACKGROUND 
     Techniques for encoding communication channels, known as coded modulation, have been found to improve the bit error rate (BER) of electronic communication systems such as modem and wireless communication systems. Turbo coded modulation has proven to be a practical, power-efficient, and bandwidth-efficient modulation method for “random-error” channels characterized by additive white Gaussian noise (AWGN) or fading. These random-error channels can be found, for example, in the Code Division Multiple Access (CDMA) environment. 
     An innovation of Turbo codes is the interleaver which permutes the original received or transmitted data frame. Conventional permuting of Turbo codes is accomplished by a processor performing a randomizing algorithm, the construction of which is well known. 
     Interleaving a sequence of data can be realized by reading linear array data from different memory locations. The “addressing rule” defines the permutation, which is the interleaving/de-interleaving rule. Such a memory based interleaver/de-interleaver scheme is called an indirect interleaver, since the construction of associated de-interleaver is not required. 
     FIG. 1 shows a conventional interleaver that uses an M-sequence register as the random address generator. A frame of data is written into sequential locations in a memory  5 . An M-sequence generator  1  generates the addresses for a block of data at least as large as the frame, and in a sequence other than a linear sequence. These addresses are then used to read frame elements out of memory  5 , except for addresses outside the frame size which are ignored by puncturing unit  4 . Frame elements are thus read out of memory  5  in permuted order, and are buffered in a FIFO 2. A clock  3  clocks the M-sequence generator and also clocks FIFO 2. Although frame elements may emerge from memory  5  at an uneven (“bursty”) rate because of puncturing, the output of FIFO 2 is at an even rate. 
     A problem with this type of non-uniform interleaving is the difficulty in achieving sufficient “non-uniformity”, since the interleaving algorithms can only be based on pseudo-irregular patterns. Further, conventional interleavers require a significant amount of memory in the encoder. Conventional interleaving matrices also require delay compensations, which limit their use for applications with real-time requirements. Turbo code will be present in 3G CDMA both in the United States and Europe. Therefore, the performance of Turbo code interleavers is an important aspect of 3G CDMA. Another important issue is how to effectively implement an interleaver in an application. 
     Accordingly there exists a need for systems and methods of interleaving codes that improve non-uniformity. 
     There also exists a need for systems and methods of interleaving codes for 3G CDMA. 
     It is thus an object of the present invention to provide systems and methods of interleaving codes that improve non-uniformity. 
     It is also an object of the present invention to provide systems and methods of interleaving codes for 3G CDMA. 
     SUMMARY OF THE INVENTION 
     In accordance with the teachings of the present invention, these and other objects may be accomplished by the present invention, which is a Turbo code interleaver for use with 3G CDMA data. An embodiment of the invention includes an apparatus that receives and temporarily stores frames of data in a memory. A counter is connected to a table. The table includes addresses which may be selected by the counter. A clock is connected to the counter and an output buffer and is configured to synchronize them. 
     The addresses in the table can include the addresses of elements that are outside the frame size, therefore a puncturing device can be connected to the table. The puncturing device can be configured to discard any elements that are outside the frame size. This embodiment also includes a memory. The memory can be connected to the puncturing unit and to the buffer. Data are read out of the memory from addresses which are not discarded by the puncturing device, and are output through the buffer. 
     Another embodiment of the present invention is a method of interleaving 3G CDMA data. This embodiment includes receiving and temporarily storing data. Using a clock to synchronize the data with a counter ensures timing throughout the system is sampled correctly. This embodiment also includes storing a plurality of addresses in at least one table electrically connected to the counter. The counter is used to select the addresses. It can be configured to select some or all of the addresses. This embodiment further includes discarding the selected addresses if they are greater than a frame size, using a puncturing device electrically connected to the table. This embodiment also includes storing the data in address locations in a memory which is electrically connected to the puncturing unit, where the address locations correspond to the selected addresses which are not discarded. 
     Another embodiment of the present invention is an apparatus for interleaving 3G CDMA data. This embodiment includes a memory for receiving and temporarily storing the data. It further includes a counter module for counting, an output buffer module, and a clock module connected to the buffer module and the counter module, for synchronizing the buffer module and the counter module. 
     This embodiment also includes a table storage module for storing addresses. A puncturing module electrically connected to the table module is included for discarding selected addresses if they are outside the frame size. 
    
    
     FIG. 1 is a conventional interleaver that uses an M-sequence generator as the basis for the random address generator; 
     FIG. 2 is a schematic representation of a Galois Field type interleaver in accordance with the present invention; 
     FIG. 2A is a variant of the interleaver depicted in FIG. 2; 
     FIG. 3 is schematic representation of another embodiment of the Galois Field type interleaver of FIG. 2; 
     FIGS. 4 and 4A depict variants of interleavers; 
     FIG. 4B is a schematic representation of an Algebraic type interleaver in accordance with the preset invention; 
     FIG. 5 is a schematic representation of a Direct Algebraic de-interleaver for de-interleaving the output of the algebraic interleaver shown in FIG. 4; and 
     FIG. 6 is a schematic representation of an Indirect Algebraic type interleaver in accordance with the present invention. 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     The present invention provides efficient implementations of Turbo code interleavers proposed for third generation code division multiple access (3G CDMA) standards. 
     Galois Field Random Interleaver 
     FIG. 2 illustrates an embodiment of the present invention. This embodiment is an efficient implementation for the Galois Field interleaver. Data is permuted by pseudo-randomizing the indices of the working memory  210 . The data are output to a FIFO buffer  280  after being read out in permuted fashion from the working memory  210 . 
     The working memory  210  indices can be composed of two parts; columns and rows. The columns and rows can be generated by combining pseudo-random numbers with arranged numbers. In an embodiment the columns are the arranged numbers and the rows are the pseudo-random numbers. However those skilled in the art will realize that this is simply a design choice and can be reversed. In addition row and column can be referred to as most significant bit (MSB) or least significant bit (LSB). 
     A clock  215  triggers a two stage counter  270 ,  260 . The counter initiates generation of the row and column components used to address the working memory  210 . For example, for a frame size of  384 , we may define N 1 =24 and N 2 =16, where N 1  and N 2  are representative of the number of rows and columns, respectively. Thus  384 =24×16. The parameters N 1  and N 2  specify the values to which the counters are permitted to count, and can be changed in software or hardware. The first stage of the counter  270  (i.e. N 2 ), counts to N 2  and then sends a carry bit to the second stage of the counter  260  (N 1  or column counter). As N 2  is counting, a row element is generated. The row element can be further derived by reversing bits using a bit reverser  290 . Thus, for a particular row address a corresponding bit-reversed address can be used. The following is an example of bit reversal: 
     
       
         
               
               
               
             
           
               
                   
                   
               
               
                   
                 Input Data 
                 Output Data 
               
               
                   
                   
               
             
             
               
                   
                 000 
                 000 
               
               
                   
                 001 
                 100 
               
               
                   
                 010 
                 010 
               
               
                   
                 011 
                 110 
               
               
                   
                 100 
                 001 
               
               
                   
                 101 
                 101 
               
               
                   
                 110 
                 011 
               
               
                   
                 111 
                 111 
               
               
                   
                   
               
             
          
         
       
     
     The row portion of the memory index can also be multiplied by an offset by means of a multiplier  295 . Any variable quantity produced in the embodiment may be used for the offset, or a constant may be used. A present embodiment uses the value of N 1  for an offset. Those skilled in the art will realize that the bit reverser  290  may be replaced by an indexed table or real time number generator based on a random or non-random number sequence, and still be within the scope of this invention. Conversely, the bit reverser can be eliminated. 
     The row portion of the memory index is added to a column portion of the memory index to derive the memory index. For example, if the output of the multiplier  295  is 1010, and the output of the puncturing mechanism  220  is 0110 (explained below), then the output of the adder  200  is 1010 in the LSB portion of the address and 0110 in the MSB portion of the address. The memory index is the combination of the LSB and MSB. This can be accomplished by masking the LSB and MSB with 0000ffffH (i.e. LSB mask) and ffff0000H (i.e. MSB mask), respectively, and combining the results. For example: 
     
       
         1010 2 &amp;(0000 ffffH )+0110 2 &amp;( ffff 0000 H )=01101010 2 . 
       
     
     A column index can be generated by combining the contents of a lookup table  240  with a pseudo-random sequencer  250  (i.e. M-sequencer, Gold, Hadamard, Walsh sequencer or the like). Both the sequence generator  250  and the first lookup table  240  are controlled by the two-stage counter  270 ,  260 . The pseudo-random number from the pseudo-random sequence generator  250  is combined by combiners  225  with a value from lookup table  240 . This combination is used as an index to table  230 , which in turn outputs a permuted column index. For example, if the column index is defined by: 
     
       
           j =log(α i     o   +α j ) 
       
     
     where j is the column index and i o  changes row by row as in the following example, 
     
       
         
               
               
               
             
           
               
                   
                   
               
               
                   
                 i 
                 i o   
               
               
                   
                   
               
             
             
               
                   
                 0 
                 0 
               
               
                   
                 1 
                 2 
               
               
                   
                 2 
                 5 
               
               
                   
                 3 
                 5 
               
               
                   
                   
               
             
          
         
       
     
     j can be restated as: 
     
       
           j =log(α i     o   +α j )=α x   
       
     
     where x can be found from the log table  230  defined by the Galois Field equation. 
     If the column index is out of range for a particular block size, then the output of the lookup Table  230  is discarded (i.e. punctured) by a puncturing unit  220 . For example, if N=8, where N is the frame size, and the random sequence generated from table  220  is: [ 5   2   9   4   6   1   7   10   3   8 ], after puncturing, the sequence becomes [ 5   2   4   6   1   7   3   8 ] by removing the numbers larger than 8 from the original sequence. 
     If the column index is within range, then it is added to the row index and a permuted memory index is generated. This memory index, in turn, is used to address the memory  210  for retrieving data. Those skilled in the art will realize that the tables  230 ,  240  can be replaced with real time units that calculate the Galois Field pseudo-random numbers. 
     The FIFO buffer  280  smoothes the rate of data retrieved from memory  210  consistent with the clock rate. For example, at each clock cycle, the random interleaver generator generates the addresses such as [ 5   2   9   4   6   1   7   10   3   8 ] (i.e. before puncturing). However, if the data frame size were 8, the numbers 9 and 10 would be punctured. The M-sequence is reset if a fast carry sign from the counter is changed. Thus, after one clock cycle, the M-sequence generator is set to 1 and the sequence starts over. Those skilled in the art will realize that the entire unit can be made without working memory since the tables and pseudo-random sequences can be accomplished by real time number generators. Thus the received data can be permuted and output through FIFO buffer  280  in real time as it enters the system. The same is true for the following embodiments. 
     FIG. 2A depicts puncturing unit  220  located after adder  200 , rather than before it as in FIG.  2 . This allows the puncturing to be determined by N 2  and N 1  jointly as arbitrary L&lt;(N 1 *N 2 ), rather than L&lt;N 1  . Also in FIG. 2A, N 2  counter  270  provides an input to lookup table  240  along with the input from N 1  counter  260 , thus allowing column permutation to be row-independent. 
     FIG. 4 is simplified from FIG. 2A, regarding its depiction of sequence generation consolidated in sequence generator  255 , which can be an algebraic type of sequence generator. As in FIG. 2A, N 2  counter  270  provides some of the control of lookup table  240 . 
     FIG. 4A shows block  290  able to function as a bit reverser or alternatively as a random sequence generator. Also shown is a connection from block  290  to block  240 , providing additional input to lookup table  240 . 
     FIG. 3 shows another embodiment of the Galois Field interleaver. This embodiment is simplified by the removal of lookup Table  230 . The embodiment may thus operate with a lower memory requirement. 
     Algebraic Interleaver FIG. 4B illustrates another embodiment of the present invention. This embodiment is an efficient implementation of the Algebraic interleaver. The Algebraic interleaver can include tables which can be replaced by real-time pseudo-random generators. In addition, this embodiment can also include a puncturing unit (here called a decoder)  470 , a multiplier  400 , and an adder  420 . These units perform the same functions as those described above. Since such an algebraic interleaver is parameterized it can be reconstructed with an arbitrary size by using a few parameters. This provides a significant advantage by reducing the memory requirement. 
     The interleaver contains two lookup tables  460 ,  430  and a two-stage counter  450 ,  440 . The outputs of the two lookup tables are combined, where the tables are indexed by a two stage counter  440 ,  450 . The table lookup  460  (i.e. N 2 ), can be indexed by the N 2  counter while the table lookup  430  can be indexed by every count generated by the N 1  counter. The FIFO buffer  480  depth is minimized and the decoder  470  punctures the last M tail-bits, thus generating an address for a working memory within a frame size. In addition, the same counter  440 ,  450  can be re-used for the linear array write-in addressing. 
     Since the algebraic interleaver is a row-by-row and column-by-column permuted block interleaver, a direct de-interleaver can be constructed for use with the algebraic interleaver. FIG. 5 depicts a direct Algebraic de-interleaver to de-interleave the output of the algebraic interleaver shown in FIG.  4 . The corresponding inverse tables of N 1  and N 2  are denoted as/N 1  and /JN 2  respectively. The direct de-interleaver can also generate the de-interleaver address on-line (i.e., in real time) without the need for a working memory. 
     Algebraic Indirect Interleaver 
     Another embodiment of the invention is the Indirect Algebraic interleaver shown in FIG.  6 . The Indirect Algebraic interleaver uses a linear block addressing unit  620  to combine the index components (i.e. row and column or MSB and LSB) necessary to pseudo-randomly read out from the working memory  610  to the buffer memory (FIFO)  660 . The pointer to each block is the output of the table lookup N 1   630  and a two-stage counter  640 ,  650 . Thus, the block addressing unit  620  is used as an address generator by either indexing a tabled located within the clock addressing unit  620  (not shown) or by combining the counter  640  output with the table lookup  630  output. Thus, the N 2  counter  640  is directly selecting the offset address, while the table lookup (N 1 )  630  is controlled by the N 1  counter  650 . The FIFO buffer  660  depth is minimized and the decoder  660  punctures any addresses greater than the frame size. A difference between this embodiment and the Algebraic Interleaver (shown in FIG. 4) is that only one table lookup is utilized to generate pseudo-random addresses. 
     Those skilled in the art will realize that instead of choosing a pseudo-random number to index a working memory (for transferring data stored in a FIFO buffer), the pseudo-random number can be used to index the FIFO buffer. The chosen input data from the FIFO buffer can then be sequentially written to working memory. Thus, the data can be stored sequentially into working memory (as opposed to pseudo-randomly) while the FIFO is addressed pseudo-randomly. To use the data in working memory, a sequential counter or other linear addressing module can be used to index the working memory. 
     It will be understood that changes may be made in the above construction and in the foregoing sequences of operation without departing from the scope of the invention. It is accordingly intended that all matter contained in the above description or shown in the accompanying drawings be interpreted as illustrative rather than in a limiting sense. 
     It is also to be understood that the following claims are intended to cover all of the generic and specific features of the invention as described herein, and all statements of the scope of the invention which, as a matter of language, might be said to fall therebetween.