Patent Publication Number: US-2007115960-A1

Title: De-interleaver for data decoding

Description:
BACKGROUND  
      The invention relates to communications systems, and more particularly to communications systems and methods that use de-interleaving.  
      With the rapidly growing demand for cellular, mobile radio and other wireless transmission services, there has been an increasing interest in exploiting various technologies to provide reliable, secure, and efficient wireless communications. Orthogonal Frequency Division Multiplexing (OFDM) is well known as a high spectrally efficient transmission scheme capable of dealing with severe channel impairment encountered in a mobile environment. OFDM has been adopted for wireless local area network (WLAN) applications as part of the IEEE 802.11a standard in the 5 GHz frequency band. In June of 2003, the IEEE approved another WLAN standard, known as 802.11g, which also adopts OFDM as a mandatory part for a further high-speed physical layer (PHY) extension to the 802.11b standard in the 2.4 GHz band. The advantages of OFDM have become well known and applications of similar modulation techniques, namely multi-carrier modulation techniques, are under consideration for use in new standards. Although the multi-carrier modulation techniques used in different standards may have differences, the basic idea of using multiple subcarriers to transmit data is a foundation of all multi-carrier modulation techniques.  
      Multi-carrier communications systems are susceptible to continuous sequences of erroneous bits, or burst errors. It is common to use interleaving in communications systems to overcome correlated channel noise such as burst errors or fading. An interleaver disperses contiguous bits of data in a data stream across a transmission sequence so that data bits adjacent in the data stream are no longer adjacent in the transmission sequence. At the receiving end, the interleaved data is rearranged into its original order by a de-interleaver prior to further processing. As a result of interleaving, correlated channel noise introduced in the transmission channel appears to be statistically independent at the receiving end and thus allows superior error correction. Interleavers and de-interleavers are disclosed, for example, in U.S. Pat. No. 6,634,009 and U.S. Pat. No. 6,748,561. One of the greatest challenges facing those devising multi-carrier communications systems is implementation of an efficient and economical interleaver/de-interleaver.  
     SUMMARY  
      Systems and methods involving de-interleaving are provided. In this regard, an embodiment of a de-interleaver comprises a first and second memory bank, a de-interleaving encoder, and a de-interleaving decoder. The first and the second memory banks are configured to store data in column order and output the data in row order. The de-interleaving encoder receives a stream of interleaved data values, and generates an input address for both the first and the second memory banks contingent upon a modulation mode and based on a first count value. According to the input address, the de-interleaving encoder sequentially writes the interleaved data values to either the first memory bank or the second memory bank in column order. On the other hand, the de-interleaving decoder generates a first output address for the first memory bank and a second output address for the second memory bank based on a second count value and contingent upon the modulation mode, a coding rate, and a dummy insertion indicator. According to the respective output addresses, the de-interleaving decoder sequentially reads the interleaved data values from the first and the second memory banks in row order. Furthermore, the de-interleaving decoder extracts decision metrics from the interleaved data values read out of the memory banks according to a first output indicator and a second output indicator.  
      In another aspect, an embodiment of a multi-carrier communications system comprises a de-interleaver for data decoding. The de-interleaver comprises a first and second memory bank, a de-interleaving encoder, and a de-interleaving decoder. The first and the second memory banks are configured to store data in column order and output the data in row order. The de-interleaving encoder receives a stream of interleaved data values, and generates an input address for both the first and the second memory banks contingent upon a modulation mode and based on a first count value. According to the input address, the interleaved data values are sequentially written to either the first memory bank or the second memory bank in column order. On the other hand, the de-interleaving decoder generates a first output address for the first memory bank and a second output address for the second memory bank based on a second count value and contingent upon the modulation mode, a coding rate, and a dummy insertion indicator. According to the respective output addresses, the interleaved data values are sequentially read from the first and the second memory banks in row order. Furthermore, the de-interleaving decoder extracts decision metrics from the interleaved data values read out of the memory banks according to a first output indicator and a second output indicator. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
      The invention will be described by way of exemplary embodiments, but not limitations, illustrated in the accompanying drawings in which like references denote similar elements, and in which:  
       FIG. 1  is a block diagram illustrating an embodiment of a multi-carrier communications system;  
       FIG. 2  is a block diagram of an 8-column by 3-row memory, which stores sequential data bits D 1 -D 24  in column order;  
       FIG. 3  is an exemplary graph illustrating signal waveforms with respect to a de-interleaving encoder involved in the multi-carrier communications system of  FIG. 1 ; and  
       FIG. 4  is an exemplary graph illustrating signal waveforms with respect to a de-interleaving decoder involved in the multi-carrier communications system of  FIG. 1 . 
    
    
     DETAILED DESCRIPTION  
      Reference throughout this specification to “one embodiment” or “an embodiment” indicates that a particular feature, structure, or characteristic described in connection with the embodiments is included in at least one embodiment of the present invention. Thus, the appearance of the phrases “in one embodiment” or “an embodiment” in various places throughout this specification is not necessarily all referring to the same embodiment. Furthermore, the particular features, structures, or characteristics may be combined in one or more embodiments. As to the accompanying drawings, it should be appreciated that not all components necessary for a complete implementation of a practical system may be illustrated or described in detail.  
      To complement OFDM, the IEEE 802.11a/g standard also offers support for a variety of other modulation and coding alternatives. For example, the standard allows designers to combine BPSK, QPSK, and 16-QAM modulation with convolution encoding at a rate of R=½ to generate data rates of 6, 12 and 24 Mbps. All other combinations of coding rate, including R=⅔ and R=¾ combined with 64-QAM, are used to generate rates up to 54 Mbps, which are optional in the standard. The coding rate of ½ can be increased to ⅔ and ¾ by means of puncturing. Puncturing is a bit-stealing procedure for omitting some of encoded bits in the transmitter, thereby reducing the number of transmitted bits and achieving higher data rate. After puncturing, interleaving is applied to ensure that adjacent coded bits are separated by several bits, thus increasing noise immunity to burst errors. According to the standard, all data bits must be interleaved by a block interleaver with a block size corresponding to the number of bits in a single OFDM symbol, N CBPS . The interleaver is defined by a two-step permutation. The first permutation ensures that adjacent coded bits are mapped onto non-adjacent subcarriers. The second ensures that adjacent coded bits are mapped alternately onto less and more significant bits of the constellation and, thereby, long runs of low reliability (LSB) bits are avoided. In the case of 802.11a, the first permutation is defined by: 
 
 i =( N   CBPS /16)( k  mod 16)+floor( k/ 61),  k= 0,1 , . . . ,N   CBPS −1 
 
 where k is the index of the coded bit, i is the index after the first permutation, floor(•) is a function returning the largest integer not exceeding the parameter, and mod denotes modulo arithmetic. The second permutation is of the form: 
 
 j=s ×floor( i/s )+( i+N   CBPS −floor(16× i/N   CBPS ))mod  s, k= 0,1 , . . . , N   CBPS −1 
 
 where j is the index after the second permutation. The value of s is given by 
 
 s =max( N   BPSC /2,1) 
 
      where N BPSC  is the number of coded bits per subcarrier. The encoded and interleaved binary serial data are then divided into groups of N BPSC  bits and converted into complex numbers representing BPSK, QPSK, 16-QAM, or 64-QAM constellation points. The following table summarizes the modulation parameters of the IEEE standard 802.11a.  
                                   TABLE 1                                   Coding                           bits   Coding bits   Data bits               Coding   per sub-   per OFDM   per OFDM       Data Rate       rate   carrier   symbol   symbol       (Mbits/s)   Modulation   (R)   (N BPSC )   (N CBPS )   (N DBPS )                                                        6   BPSK   ½   1   48   24       9   BPSK   ¾   1   48   36       12   QPSK   ½   2   96   48       18   QPSK   ¾   2   96   72       24   16-QAM   ½   4   192   96       36   16-QAM   ¾   4   192   144       48   64-QAM   ⅔   6   288   192       54   64-QAM   ¾   6   288   216                  
 
      Basically, a conformant 802.11a receiver performs the reverse operations of transmission. Incoming data modulated by the form of phase shift keying (PSK) or quadrature amplitude modulation (QAM) can be de-mapped into binary values known as decision metrics and subjected to de-interleaving before entering a Viterbi decoder. A decision metric is deemed hard-decision data if it is quantized to one-bit precision, while a decision metric is deemed soft-decision data if quantized with more than one bit of precision. Referring now to  FIG. 1 , an embodiment of a conformant 802.11a system  10  involving a de-interleaver  100  for data decoding is illustrated by way of a block diagram. As depicted, an embodiment of the de-interleaver  100  comprises a de-interleaving encoder  110 , two memory banks  120   a - b , and a de-interleaving decoder  130 . The memory banks  120   a  and  120   b  are configured to store data in column order and output the data in row order. As an example, sequential data values D 1 -D 24  are written into an 8×3 memory  200  in column order as shown in  FIG. 2 . When the data values are sequentially read from rows  1 ,  2  and  3  of the memory  200  (i.e. in row order), the order of the data values D 1 -D 24  is: D 1 , D 4 , D 7 , D 10 , D 13 , D 16 , D 19 , D 22 , D 2 , D 5 , D 8 , D 11 , D 14 , D 17 , D 20 , D 23 , D 3 , D 6 , D 9 , D 12 , D 15 , D 18 , D 21 , D 24 . The memory banks  120   a  and  120   b  constitute a sufficient capacity to accommodate an OFDM symbol modulated by different types. In one embodiment, each memory bank may comprise two pages so that while one is outputting an OFDM symbol, the other is storing the next symbol.  
      The de-interleaving encoder  110  receives a stream of interleaved data values DQ[14:0] representing decision metrics from a de-mapping module (not shown). An auxiliary signal MODE is also provided, informing the de-interleaving encoder  110  of the modulation mode being used. The interleaving encoder  110  generates an input address W_ADDR[6:0] for both the memory banks  120   a  and  120   b  contingent upon the modulation mode and based on a count value i. A cycle-based counter may be built in the de-interleaving encoder  110  to generate the count value i from 0 to (N CBPS /s)−1, where s is determined by N BPSC  according to the expression: s=max(N BPSC /2,1). In the case of a conformant 802.11a system, the value of s is 1, 1, 2, and 3 for BPSK, QPSK, 16-QAM, and 64-QAM modulation, respectively. In addition to the input address W_ADDR[6:0], the interleaving encoder  110  needs to generate write-enable signals WE 0 # and WE 1 # for the memory banks  120   a  and  120   b , respectively. A #sign at the end of a signal name herein indicates that the active state occurs when the signal is at a logic low level. According to an embodiment of the interleaving encoder  110 , the input address W_ADDR[6:0] and the write-enable signals WE 0 # and WE 1 # are generated from the following pseudo-code:  
                                                  MODE = BPSK             for i = 0, 1, 2,..., (N CBPS  / s) − 1                WA MSB     i mod 3                WA LSB     i / 6                W_ADDR   {WA MSB , WA LSB }                WE0#   (i / 3) mod 2                WE1#   ˜((i / 3) mod 2)           MODE = QPSK             for i = 0, 1, 2,..., (N CBPS  / s) − 1                WA MSB     i mod 6                WA LSB     i / 12                W_ADDR   {WA MSB , WA LSB }                WE0#   (i / 6) mod 2                WE1#   ˜((i / 6) mod 2)           MODE = 16-QAM             for i = 0, 1, 2,..., (N CBPS  / s) − 1                WA MSB     i mod 6                WA LSB     i / 12                W_ADDR   {WA MSB , WA LSB }                REV   (i / 6) mod 2                WE0#   (i / 6) mod 2                WE1#   ˜((i / 6) mod 2)           MODE = 64-QAM             for i = 0, 1, 2,..., (N CBPS  / s) − 1                WA MSB     i mod 6                WA LSB     i / 12                W_ADDR   {WA MSB , WA LSB }                REV   (i / 6) mod 3                WE0#   (i / 6) mod 2                WE1#   ˜(i / 6) mod 2)                      
 
      As can be seen, WA MSB [6:3] and WA LSB [2:0] are concatenated into W_ADDR[6:0], yielding the input address for both the memory banks  120   a    120   b . Hence, the interleaved data values are written to either the memory bank  120   a  or  120   b  in column order according to the address W_ADDR[6:0]. Note that the de-interleaving encoder  110  further generates a reverse indicator REV in the case of quadrature amplitude modulation, and if necessary, permutes the order of the bits of the interleaved data values in advance according to the reverse indicator REV. In this regard, the actual order of the bits of data values written to the memory banks is determined by the rule:  
                                                  MODE = 16-QAM             if (REV = 0)                W_DATA[14:0]   DQ[14:0]             else if (REV = 1)                W_DATA[14:0]   {DQ[14:10], DQ[4:0], DQ[9:5]}           MODE = 64-QAM             if (REV = 0)                W_DATA[14:0]   DQ[14:0]             else if (REV = 1)                W_DATA[14:0]   {DQ[9:5], DQ[4:0], DQ[14:10]}             else if (REV = 2)                W_DATA[14:0]   {DQ[4:10], DQ[14:0], DQ[9:5]}                      
 
 As an example helpful in understanding the de-interleaving encoder  110 ,  FIG. 3  shows a waveform graph of related signals in the case where the MODE signal is indicative of 64-QAM modulation. 
 
      The de-interleaver  100  may insert dummy data into the subsequent Viterbi decoder (not shown) in place of the previously punctured bits at the transmitting end. Specifically, the de-interleaving decoder  130  takes dummy insertion into account when it attempts to read decision metrics out of the memory banks. Therefore, the de-interleaving decoder  130  generates an output address R_ADDR0[6:0] for the memory bank  120   a  and another output address R_ADDR1[6:0] for the memory bank  120   b  based on a count value n and contingent upon the modulation mode, a coding rate, and a dummy insertion indicator (abbreviated as DII). In addition, the interleaving decoder  130  needs to generate output-enable signals OE 0 # and OE 1 # for the memory banks  120   a  and  120   b , respectively. According to an embodiment of the interleaving decoder  130 , the output address R_ADDR0[6:0], the output address R_ADDR1[6:0], the output-enable signal OE 0 #, and the output-enable signal OE 1 # are generated as follows:  
                                                  MODE = BPSK and RATE = 1 / 2             for n = 0, 1, 2,..., N DBPS  − 1                if (DII = 00)                   RA MSB     n / 8                   RA0 LSB     n mod 8                   RA1 LSB     n mod 8                   R_ADDR0   {RA MSB , RA0 LSB }                   R_ADDR1   {RA MSB , RA1 LSB }                   OE0#   0                   OE1#   0           MODE = BPSK and RATE = 3 / 4             for n = 0, 1, 2,..., N DBPS  − 1                if (DII = 00)                   RA MSB     n / 12                   RA0 LSB     (n × 2 / 3) mod 8                   RA1 LSB     (n × 2 / 3) mod 8                   R_ADDR0   {RA MSB , RA0 LSB }                   R_ADDR1   {RA MSB , RA1 LSB }                   OE0#   0                   OE1#   0                else if (DII = 01)                   RA MSB     n / 12                   RA0 LSB     RA0 LSB  + 1                   RA1 LSB     RA1 LSB                     R_ADDR0   {RA MSB , RA0 LSB }                   R_ADDR1   {RA MSB , RA1 LSB }                   OE0#   0                   OE1#   1                else if (DII = 10)                   RA MSB     n / 12                   RA0 LSB     RA0 LSB                     RA1 LSB     RA1 LSB  + 1                   R_ADDR0   {RA MSB , RA0 LSB }                   R_ADDR1   {RA MSB , RA1 LSB }                   OE0#   1                   OE1#   0           MODE = QPSK and RATE = 1 / 2             for n = 0, 1, 2,..., N DBPS  − 1                if (DII = 00)                   RA MSB     n / 8                   RA0 LSB     n mod 8                   RA1 LSB     n mod 8                   R_ADDR0   {RA MSB , RA0 LSB }                   R_ADDR1   {RA MSB , RA1 LSB }                   OE0#   0                   OE1#   0           MODE = QPSK and RATE = 3 / 4             for n = 0, 1, 2,..., N DBPS  − 1                if (DII = 00)                   RA MSB     n / 12                   RA0 LSB     (n × 2 / 3) mod 8                   RA1 LSB     (n × 2 / 3) mod 8                   R_ADDR0   {RA MSB , RA0 LSB }                   R_ADDR1   {RA MSB , RA1 LSB }                   OE0#   0                   OE1#   0                else if (DII = 01)                   RA MSB     n / 12                   RA0 LSB     RA0 LSB  + 1                   RA1 LSB     RA1 LSB                     R_ADDR0   {RA MSB , RA0 LSB }                   R_ADDR1   {RA MSB , RA1 LSB }                   OE0#   0                   OE1#   1                else if (DII = 10)                   RA MSB     n / 12                   RA0 LSB     RA0 LSB                     RA1 LSB     RA1 LSB  + 1                   R_ADDR0   {RA MSB , RA0 LSB }                   R_ADDR1   {RA MSB , RA1 LSB }                   OE0#   1                   OE1#   0           MODE = 16-QAM and RATE = 1 / 2             for n = 0, 1, 2,..., N DBPS  − 1                if (DII = 00)                   RA MSB     n / 16                   RA0 LSB     n mod 8                   RA1 LSB     n mod 8                   R_ADDR0   {RA MSB , RA0 LSB }                   R_ADDR1   {RA MSB , RA1 LSB }                   OE0#   0                   OE1#   0           MODE = 16-QAM and RATE = 3 / 4             for n = 0, 1, 2,..., N DBPS  − 1                if (DII = 00)                   RA MSB     n / 24                   RA0 LSB     (n × 2 / 3) mod 8                   RA1 LSB     (n × 2 / 3 ) mod 8                   R_ADDR0   {RA MSB , RA0 LSB }                   R_ADDR1   {RA MSB , RA1 LSB }                   OE0#   0                   OE1#   0                else if (DII = 01)                   RA MSB     n / 24                   RA0 LSB     RA0 LSB  + 1                   RA1 LSB     RA1 LSB                     R_ADDR0   {RA MSB , RA0 LSB }                   R_ADDR1   {RA MSB , RA1 LSB }                   OE0#   0                   OE1#   1                else if (DII = 10)                   RA MSB     n / 24                   RA0 LSB     RA0 LSB                     RA1 LSB     RA1 LSB  + 1                   R_ADDR0   {RA MSB , RA0 LSB }                   R_ADDR1   {RA MSB , RA1 LSB }                   OE0#   1                   OE1#   0           MODE = 64-QAM and RATE = 2 / 3             for n = 0, 1, 2,..., N DBPS  − 1                if (DII = 00)                   RA MSB     n / 32                   RA0 LSB     (n × 3 / 4) mod 8                   RA1 LSB     (n × 3 / 4) mod 8                   R_ADDR0   {RA MSB , RA0 LSB }                   R_ADDR1   {RA MSB , RA1 LSB }                   OE0#   0                   OE1#   0                else if (DII = 01)                   RA MSB     n / 32                   RA0 LSB     RA0 LSB  + 1                   RA1 LSB     RA1 LSB                     R_ADDR0   {RA MSB , RA0 LSB }                   R_ADDR1   {RA MSB , RA1 LSB }                   OE0#   0                   OE1#   1                else if (DII = 11)                   RA MSB     n / 32                   RA0 LSB     RA0 LSB  + 1                   RA1 LSB     RA1 LSB  + 1                   R_ADDR0   {RA MSB , RA0 LSB }                   R_ADDR1   {RA MSB , RA1 LSB }                   OE0#   0                   OE1#   1                else if (DII = 10)                   RA MSB     n / 32                   RA0 LSB     RA0 LSB                     RA1 LSB     RA1 LSB  + 1                   R_ADDR0   {RA MSB , RA0 LSB }                   R_ADDR1   {RA MSB , RA1 LSB }                   OE0#   1                   OE1#   0           MODE = 16-QAM and RATE = 3 / 4             for n = 0, 1, 2,..., N DBPS  − 1                if (DII = 00)                   RA MSB     n / 36                   RA0 LSB     (n × 2 / 3) mod 8                   RA1 LSB     (n × 2 / 3) mod 8                   R_ADDR0   {RA MSB , RA0 LSB }                   R_ADDR1   {RA MSB , RA1 LSB }                   OE0#   0                   OE1#   0                else if (DII = 01)                   RA MSB     n / 36                   RA0 LSB     RA0 LSB  + 1                   RA1 LSB     RA1 LSB                     R_ADDR0   {RA MSB , RA0 LSB }                   R_ADDR1   {RA MSB , RA1 LSB }                   OE0#   0                   OE1#   1                else if (DII = 10)                   RA MSB     n / 36                   RA0 LSB     RA0 LSB                     RA1 LSB     RA1 LSB  + 1                   R_ADDR0   {RA MSB , RA0 LSB }                   R_ADDR1   {RA MSB , RA1 LSB }                   OE0#   1                   OE1#   0                      
 
 As can be seen, RA MSB [6:3] and RA0 LSB [2:0] are concatenated into R_ADDR0[6:0], yielding the output address for the memory bank  120   a . Likewise, RA MSB [6:3] and RA1 LSB [2:0] are concatenated into R_ADDR1[6:0], yielding the output address for the memory bank  120   b . Note that a cycle-based counter may, be built in the de-interleaving decoder  130  to generate the count value n from 0 to N DBPS −1. According to R_ADDR0[6:0], R_ADDR1[6:0], OE 0 #, and OE 1 #, the memory banks  120   a  and  120   b  send out the data values addressed and place them onto R_DATA0[14:0] and R_DATA1[14:0], leading the de-interleaving decoder  130  to sequentially read the interleaved data values from the memory banks  120   a  and  120   b  in row order. In this manner, a stream of N CBPS  interleaved data can be restored to its original order in N DBPS  cycles. 
 
      There are two more auxiliary signals SEL 0  and SEL 1  applied to the de-interleaving decoder  130 . The SEL0 and SEL1 signals are output indicators dictating which portion of the read data is the final output, such as that described in the following:  
      case(SELx) 
          0: SDx[4:0]←R_DATAx[4:0]    1: SDx[4:0]←R_DATAx[9:5]    2: SDx[4:0]←R_DATAx[14:10]
 
 where x denotes 0 or 1. The output indicator SELx may be a modulo-s counter where the value of s is determined by the expression: S=max(N BPSC /2,1). Every eight read operations increase the output indicator SELx by one. According to the output indicators SEL 0  and SEL 1 , the de-interleaving decoder  130  is thus able to extract desired portions from the interleaved data values read out of the memory banks  120   a  and  120   b  for use as decision metrics. As an example helpful in understanding the de-interleaving decoder  130 ,  FIG. 4  shows a waveform graph of related signals in the case of MODE=64-QAM and RATE=⅔. 
       

      An embodiment of a de-interleaver  100  has been described above in the context of the use of OFDM for communication, although relevant embodiments are not limited to OFDM. The embodiment is also described with reference to a wireless communications system that conforms to the IEEE 802.11a/g standard. However, the communications system need not be wireless and the conformant 802.11a system referred to herein is merely an example of multi-carrier communications equipment.  
      While the invention has been described by way of example and in terms of the preferred embodiments, it is to be understood that the invention is not limited to the disclosed embodiments. To the contrary, it is intended to cover various modifications and similar arrangements (as would be apparent to those skilled in the art). Therefore, the scope of the appended claims should be accorded the broadest interpretation so as to encompass all such modifications and similar arrangements.