Patent Publication Number: US-8527855-B2

Title: Interleaving and parsing for MIMO-OFDM systems

Description:
CROSS REFERENCE TO RELATED APPLICATION 
     This application claims the benefit of U.S. Provisional Application Ser. No. 60/601,922 filed Aug. 16, 2004 and U.S. Provisional Application Ser. No. 60/624,235 filed Nov. 2, 2004 both of which are incorporated herein by reference. 
    
    
     The present invention relates to an apparatus, method and system for interleaving and parsing in a MIMO-OFDM based wireless multimedia communication system. 
     Wireless local area networks (WLAN) are increasingly important in meeting the needs of the next generation of broadband wireless communication systems for both commercial and military applications. In 1999, the Institute of the Electrical and Electronics Engineers (IEEE) 802.11a working group approved a standard for a 5 GHz band WLAN that supports a variable bit rate from 6 to 54 Mbps, and orthogonal frequency-division multiplexing (OFDM) was chosen because of its well-known ability to avoid multipath effects while achieving high data rates by combining a high order sub-carrier modulation with a high-rate convolutional code. 
     Multiple Input Multiple Output (MIMO) systems, by employing multiple transmit and receive antennas, are known to provide higher capacity and therefore higher throughput than single-link wireless communication systems. MIMO systems form the basis for wireless LANS, as a means to increase data rates in a robust fashion. Another widely used technique in wireless modems in bit-interleaved coded OFDM (BI-COFDM), is explained, for example, in the IEEE 802.11a/g standard. When using MIMO with BI-COFDM, the design of the interleaver and parser becomes very important. 
     The simplest way of mapping a data stream onto multiple antennae is to split the coded bit stream at the output of the convolutional coder in a round-robin fashion N t  parallel bit-streams, where N t  is the number of antennae. Each stream is then individually interleaved using, for example, an IEEE 802.11a interleaver. The size of the interleaver is determined by the number of bits that are mapped into a single OFDM symbol. The goal is to spread adjacent bits as far apart as possible so that they experience independent fading. When the parsing is done prior to interleaving, as described above, it is not guaranteed, however, that adjacent bits prior to parsing will be mapped to non-adjacent carriers on different antennae. Thus, the amount of frequency and spatial diversity is reduced. 
     The present invention provides an apparatus, system and method that interleaves first map bits into symbols and then parses symbols into N t  separate streams. One advantage of the present invention is improved diversity as seen by a convolutional decoder. 
     In a preferred embodiment, the system and method of the present invention includes the following:
         (1) a bit interleaver that interleaves over the total number of bits in one OFDM symbol over all N t  antennae;   (2) a bit-to-symbol mapper that maps bits into symbols such that a plurality of different constellations on a plurality of different antennae can be supported; and   (3) a parser that sends the plurality of different symbols to the plurality of different antennae.       

    
    
     
         FIG. 1A  illustrates a prior-art MIMO wireless device; 
         FIG. 1B  illustrates a MIMO wireless device modified according to a first embodiment of the present invention; 
         FIG. 1C  illustrates a MIMO wireless device modified according to a second embodiment of the present invention; 
         FIG. 2A  illustrate a flow diagram of the transmitter side of the method of a first embodiment of the present invention; 
         FIG. 2B  illustrates a flow diagram of the receiver side of the method of a first embodiment of the present invention; 
         FIG. 2C  illustrates a flow diagram of the transmitter side of the method of a second embodiment of the present invention; 
         FIG. 2D  illustrates a flow diagram of the receiver side of the method of a second embodiment of the present invention; 
         FIG. 3  illustrates a simplified block diagram of a wireless device in an ad-hoc wireless network system according to an embodiment of the present invention; and 
         FIG. 4  illustrates the performance of the first embodiment of the present invention compared to a system that interleaves separately over each antenna. 
     
    
    
     In the following description, by way of explanation, not limitation, specific details are set forth such as the particular architecture, interfaces, techniques, etc., in order to provide a thorough understanding of the present invention. However, it will be apparent to those skilled in the art that the present invention may be practiced in other embodiments that depart from these specific details. 
     The characteristics of a wireless channel typically vary over time. The error-coding scheme used must be adapted to the changing channel characteristics to achieve the best performance. 
     An encoder/decoder pair can change code rates using a technique termed “code puncturing” to adapt the code&#39;s error correction capabilities without changing their basic structure. 
     The encoder for a punctured code incorporates a bit selector that deletes specific code bits in accordance with a pre-determined puncturing rule. The original low-rate convolutional encoder is followed by the bit selector and is arranged so that only the bit selection rules need to be changed to generate different rates of codes at a transmitter side. 
     At a receiver side a Viterbi decoder decodes the punctured codes and only metrics need to be changed in accordance with the same pre-determined puncturing rule. 
     Interleaving addresses mitigating effects of burst errors. Frequency interleaving exploits the frequency diversity of wide-band transmissions. Time interleaving is not used in WLANs due to the slow-fading characteristics of the channel. 
     Interleaving amounts to interleaving symbols from at least two codewords before transmission. The error distribution is changed by relocating the bits of codewords so that a burst-error channel looks like a channel having only random errors. 
     Let m bet the interleaver depth, i.e., the number of codewords interleaved, and let N be the number of bits in a codeword. The data is written row-by-row into an m×N matrix, i.e., m codewords are written codeword-by-codeword into an array of m rows where each row is of length N (N columns). Then the data is read out column-by-column to send it over the channel. Between symbols of a given codeword there are m−1 symbols, one each from the other m−1 codewords. This approach requires that all interleaved data be received before they can be de-interleaved and is therefore slowed down by the interleaving/de-interleaving. 
     However, even given this somewhat slower approach, the system and method of the present invention provides a more robust transmission within wireless networks by improving the diversity seen by a convolutional decoder in a MIMO system. 
     In a first embodiment, the system and method of the present invention includes an apparatus comprising:
         (1) a bit interleaver;   (2) a bit-to-symbol mapper; and   (3) a parser that sends different symbols to different antennae.       

     The bit interleaver is used to interleave the output of the punctured convolutional code. In IEEE 802.11a, interleaving is done over one OFDM symbol, which has 48 data carriers. When 128-fft and multiple antennae are used, it is advantageous to interleave not only over the 96 data carriers in one OFDM symbol but over all 96*N t  data carriers, where N t  is the number of transmit streams. After interleaving, the bits are grouped N BPSC  at a time, where N BPSC  is the number of bits per symbol, e.g., 6 for 64 QAM. Each group of bits is then sent to a separate antenna in a round-robin fashion. 
     The interleaver is implemented in the following manner. 
     All encoded data bits are interleaved by a block interleaver with a block size corresponding to the number of bits in a single OFDM symbol, N CBPS , multiplied by the number of transmitted streams N t . The interleaver is defined by a two-step permutation:
         (1) the first step of the permutation ensures that adjacent coded bits are mapped onto non-adjacent subcarriers on different antennae; and   (2) the second step of the permutation ensures that adjacent coded bits are mapped alternately onto less and more significant bits of the constellation, and, thereby, long runs of low reliability (least significant bits or LSB) bits are avoided.       

     Let
         kk=number of columns in the interleaver;   k=index of the coded bit before the first permutation;   i=the index after the first and before the second permutation; and   j=the index after the second permutation, just prior to modulation mapping.       

     In a preferred embodiment, the first permutation is defined by the rule: 
                           i   =         N   T     *       N   CBPS     kk     ⁢     (     k   ⁢           ⁢   mod   ⁢           ⁢   kk     )       +     floor   ⁢           ⁢     (     k   kk     )           ,                 k   =   0     ,   1   ,   …   ⁢           ,         N   T     *     N   CBPS       -   1                   (   1   )               
where floor(.) denotes the largest integer not exceeding the parameter.
 
     The second permutation is defined by the rule: 
     
       
         
           
             
               
                 
                   
                     j 
                     = 
                     
                       
                         s 
                         × 
                         floor 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         
                           ( 
                           
                             i 
                             s 
                           
                           ) 
                         
                       
                       + 
                       
                         
                           ( 
                           
                             i 
                             + 
                             
                               
                                 N 
                                 T 
                               
                               * 
                               
                                 N 
                                 CBPS 
                               
                             
                             - 
                             
                               floor 
                               ⁡ 
                               
                                 ( 
                                 
                                   kk 
                                   × 
                                   
                                     i 
                                     
                                       ( 
                                       
                                         
                                           N 
                                           T 
                                         
                                         * 
                                         
                                           N 
                                           CBPS 
                                         
                                       
                                       ) 
                                     
                                   
                                 
                                 ) 
                               
                             
                           
                           ) 
                         
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         mod 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         s 
                       
                     
                   
                   , 
                   
                     
 
                   
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   
                     i 
                     = 
                     0 
                   
                   , 
                   1 
                   , 
                   … 
                   ⁢ 
                   
                       
                   
                   , 
                   
                     
                       
                         N 
                         T 
                       
                       * 
                       
                         N 
                         CBPS 
                       
                     
                     - 
                     1. 
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
     The value of s is determined by the number of coded bits per subcarrier, N BPSC , according to 
     
       
         
           
             
               
                 
                   s 
                   = 
                   
                     max 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       ( 
                       
                         
                           
                             N 
                             BPSC 
                           
                           2 
                         
                         , 
                         1 
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
           
         
       
     
     In this preferred embodiment, the deinterleaver, which performs the inverse transformation, is also defined by two permutations. 
     Let
         j=the index of the original received bit before the first permutation;   i=the index after the first and before the second permutation; and   k=the index after the second permutation, just prior to delivering the coded bits to the convolutional (Viterbi) decoder.       

     The first permutation is defined by the rule: 
                           i   =       (       s   ×   floor   ⁢           ⁢     (     j   s     )       +     (     j   +     floor   ⁢           ⁢     (     kk   ×     j       N   T     *     N   CBPS           )         )       )     ⁢           ⁢   mod   ⁢           ⁢   s       ,                 j   =   0     ,   1   ,   …   ⁢           ,         N   T     *     N   CBPS       -   1                   (   4   )               
where s is defined in Equation (3). This permutation is the inverse of the permutation described in Equation (2).
 
     The second permutation is defined by the rule: 
                           k   =       kk   ×   i     -     (       (         N   T     *     N   CBPS       -   1     )     *   floor   ⁢           ⁢     (     kk   ×     i     (       N   T     *     N   CBPS       )         )       )         ,                 i   =   0     ,   1   ,   …   ⁢           ,         N   T     *     N   CBPS       -   1.                   (   5   )               
This permutation is the inverse of the permutation described in Equation (1). The parameter kk is chosen according to other parameters in the system. For example, simulation results have shown that for a 2×2 system using 64-fft, kk=32 gives the best performance, whereas for a 2×2, 128-fft system, kk-16 gives the best performance. In general, kk depends on the number of antennae and FFT size.
 
     After interleaving, the bits are parsed as follows. The bits are grouped into groups of N BPSC  bits corresponding to one constellation symbol. Each group is then sent to one antenna in a round-robin fashion.  FIG. 4  illustrates that the interleaving method of the present invention performs almost 1 dB better than interleaving separately over each antenna. 
     A second embodiment, where the constellation on each antenna can be different (e.g., 64QAM on Antenna  1  and 16 QAM on Antenna  2 ), comprises the following steps:
         (1) a bit interleaver according to permutation 3 below;   (2) grouping bits according to the desired constellation on each antenna (e.g., 6-bits for 64QAM, 4-bits for 16QAM);   (3) a parser sending each group of bits to the appropriate antenna according to the constellation on each antenna (e.g., in a two-antenna system comprising Antenna  1  and Antenna  2 , 6-bit groups are sent to Antenna  1 , and 4-bit groups are sent to Antenna  2 ); and   (4) bit-interleaving among bits on each antenna using permutation 4 below, and then mapping to symbols.
 
Let
   N T =number of antennae;   N CPBSn =number of coded bits/OFDM symbols for nth antenna;   N CPBS =N CPBS1+ N CPBS2 . . . + N CPBSNT =total number of coded bits/OFDM symbol;   N BPSCn =number of bits/constellation symbols for nth antenna;   kk=number of columns.
 
Interleaver:
 
Permutation 3:
       

                           i   =           N   CBPS     kk     ⁢     (     k   ⁢           ⁢   mod   ⁢           ⁢   kk     )       +     floor   ⁢           ⁢     (     k   kk     )           ,                 i   =   0     ,   1   ,   …   ⁢           ,       N   CBPS     -   1                   (   6   )               
Permutation 4 for nth antenna:
 
                     s   n     =     max   ⁢           ⁢     (         N     BPSC   n       2     ,   1     )               (   7   )                       j   =         s   n     ×   floor   ⁢           ⁢     (     i     s   n       )       +       (     i   +     N     CBPS   n       -     floor   ⁢           ⁢     (       kk   *   i       (     N     CBPS   n       )       )         )     ⁢           ⁢   mod   ⁢           ⁢     s   n           ,                 i   =   0     ,   1   ,       …   ⁢           ⁢       N   CBPS     n       -   1                   (   8   )               
Deinterleaver:
 
Permutation 5 for nth antenna is the inverse of permutation 4:
 
                           i   =       (         s   n     ×   floor   ⁢           ⁢     (     j     s   n       )       +     (     j   +     floor   ⁢           ⁢     (     kk   ×     j     N     CBPS   n           )         )       )     ⁢           ⁢   mod   ⁢           ⁢     s   n         ,                 j   =   0     ,   1   ,   …   ⁢           ,       N     CBPS   n       -   1                   (   9   )               
Permutation 6 is the inverse of permutation 3:
 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           k 
                           = 
                           
                             
                               kk 
                               × 
                               i 
                             
                             - 
                             
                               ( 
                               
                                 
                                   ( 
                                   
                                     
                                       N 
                                       CBPS 
                                     
                                     - 
                                     1 
                                   
                                   ) 
                                 
                                 * 
                                 floor 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 
                                   ( 
                                   
                                     kk 
                                     × 
                                     
                                       i 
                                       
                                         N 
                                         CBPS 
                                       
                                     
                                   
                                   ) 
                                 
                               
                               ) 
                             
                           
                         
                         , 
                       
                     
                   
                   
                     
                       
                         
                           i 
                           = 
                           0 
                         
                         , 
                         1 
                         , 
                         … 
                         ⁢ 
                         
                             
                         
                         , 
                         
                           
                             N 
                             CBPS 
                           
                           - 
                           1 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   10 
                   ) 
                 
               
             
           
         
       
     
     Referring now to  FIG. 1A , a conventional MIMO wireless device  100  is shown that parses the  105  stream into n streams prior to interleaving by n interleavers  104 . 1 - 104 . n  for mapping by a plurality of mappers  103 . 1 - 103 . n  and transmission by a plurality of antennae  108 . 1 - 108 . n , as contrasted with  FIG. 1B  which illustrates a MIMO wireless device  150  modified according to a first embodiment of the present invention which parses the  153  stream produced by a single interleaver  155 . The device  150  comprises a transmitter side and a receiver  161 , both of which are operatively coupled to a plurality of antennae  158 . 1 - 158 . n . On the transmitter side, the device  150  comprises a convolutional encoder  157  that is operatively coupled to a bit selector/puncturer  156  (for puncturing the code) that is operatively coupled to an interleaver  155 , which in turn is operatively coupled to a mapper  154 . The interleaver  155  is a block interleaver defined by the two-step permutation of Equations (1) and (2). A parser  153  is arranged between the mapper  154  and the antennae  158 . 1 - 158 . n  to select an antenna in a round-robin fashion. On the receiver side the device  150  comprises a receiver  161  operatively coupled between the plurality of antennae  158 . 1 - 158 . n  and a deinterleaver  162  that performs the two-step inverse permutation defined by equations (4) and (5). The output of the deinterleaver is coupled to a Viturbi decoder  163 . 
     Referring now to  FIG. 1C , a MIMO device comprising a transmitter side  170  and a receiver side  180  modified according to a second embodiment of the present invention is illustrated. The receiver side  170  comprises a bit-interleaver that interleaves bits 176 according to permutation 3 and a grouper/parser  175  that the groups then bit according to a desired constellation on each antenna (e.g., 6-bits for 64QAM, 4-bits for 16QAM) and sends each group of bits to the appropriate antenna  171 . 1 - 171 . n  according to the constellation on each antenna (i.e., in a two-antenna system comprising Antenna  1  and Antenna  2 , 6-bit groups are sent to Antenna  1 , and 4-bit groups are sent to Antenna  2 ). A bit-interleaver  174 . 1 - 174 . n  interleaves among bits on each antenna using permutation 4, and then a symbol mapper  174 . 1 - 174 . n  maps to symbols. A receiver side  180  comprises a bit-deinterleaver/symbol-demapper  184 . 1 - 184 . n  for receiving a stream from each antenna  181 . 1 - 181 . n  to perform permutation 5 on each stream (inverse of permutation 4) and symbol demapping on each stream, coupled to a joiner  185  that joins the streams and is coupled to a bit-deinterleaver  186  and then performs permutation 6 (inverse of permutation 3) on the joined stream. The bit-deinterleaver  186  is coupled to a decoder  187  such that the output of the bit-deinterleaver  186  is sent to the decoder  187 . 
     Referring now to  FIG. 2A , a flow  200  of the transmitter side of the method of the first embodiment of the present invention is illustrated. At step  201  the convolutional code output by an encoder  106  is punctured by a bit selector  156  according to a pre-determined rule and then at step  202  the bits are interleaved by an interleaver  155  over one OFDM symbol. The interleaved bits are grouped into N CBPS  at step  203 , and at step  204  a parser  153  sends the grouped bits to an antenna of a plurality of antennae  157 . 1 - 157 . n  in a round-robin fashion. 
     Referring now to  FIG. 2B , a flow  250  of the receiver side of the method of the present invention is illustrated. At step  251  the received signal is de-interleaved by a deinterleaver  162  that performs the inverse permutation steps of the interleaver  155  performed at step  202 , and at step  252  the de-interleaved signal is decoded by a Viturbi decoder  163 . 
     Referring now to  FIG. 2C , a flow  270  of the transmitter side of the method of the second embodiment of the present invention is illustrated. At step  271  the convolutional code output by an encoder/puncturer  177  is bit-interleaved  272  using permutation 1 (equation (3)), and then at step  273  the interleaved bits are grouped into N CBPS  bits and a parser  175  sends the grouped bits at step  274  for further processing according to the constellation of the appropriate antenna. At step  275 , for each antenna&#39;s grouped bits, the bits are bit-interleaved using permutation 2 (equation (4)) and symbol-mapped by a bit-interleaver/symbol-mapper  174 . 1 - 174 . n  (for the n antennae). 
     Referring now to  FIG. 2D , a flow  280  of the receiver side of the method of the second embodiment of present invention is illustrated. At step  284  the received signal is bit de-interleaved by a deinterleaver  162  that performs the inverse permutation (equation (5)) of permutation 1, the ‘n’ bit streams are joined at step  285 , the joint stream is bit-deinterleaved using the inverse of permutation 1 (equation (6)) at step  286 , and at step  287  the de-interleaved signal is decoded by a decoder  187 . 
     Referring now to  FIG. 3 , the apparatus and method of the present invention can be used in any wireless multimedia transmission devices  150 . i  with a MIMO system  300 , such as a wireless home network, and in MIMO systems for wireless multimedia transmission using IEEE 802.11a/g. 
     While the preferred embodiments of the present invention have been illustrated and described, it will be understood by those skilled in the art that various changes and modifications may be made, and equivalents may be substituted for elements thereof without departing from the true scope of the present invention. In addition, many modifications may be made to adapt to a particular situation, such as interleaver depth changes, and the teaching of the present invention can be adapted in ways that are equivalent without departing from its central scope. Therefore it is intended that the present invention not be limited to the particular embodiment disclosed as the best mode contemplated for carrying out the present invention, but that the present invention include all embodiments falling within the scope of the appended claims.