Interleaving techniques are commonly used in communication systems to protect transmissions against burst errors. Burst errors result in a number of consecutive bits being received erroneously, with the rest of the transmission being received successfully.
Data correction bits are derived for the data prior to transmission, which are used by the receiver to detect whether the data has been received successfully, and whether erroneously received bits can be corrected. Only a certain number of erroneous bits can be corrected in each symbol to be transmitted. Therefore, interleaving is used to spread the bits for each symbol across the transmission. Thus, if a burst error occurs, only a small number of bits from each symbol are affected, so the receiver will be able to correct the received symbols using the data correction bits.
In many established standards, for example wireless communication standards, block interleaving is used, as it is easy and straightforward to implement. However, as data rates and distances between nodes increase, nested or concatenated interleaving schemes are becoming more important. The direct mapping of deinterleavers for such advanced interleaving schemes to hardware is usually suboptimal, so different optimization techniques can be used to save silicon area and reduce power consumption.
The “MultiBand OFDM Physical Layer Specification” Release 1.0 from the MultiBand OFDM Alliance proposes a three-stage interleaving scheme. In the first stage, symbol interleaving is used which permutes the bits across a number of consecutive OFDM symbols (usually six) to exploit frequency diversity within a band group. In the second stage, intra-tone interleaving is used which permutes the bits across the data sub-carriers (tones) within an OFDM symbol to exploit frequency diversity across sub-carriers. In the third stage, intra-symbol cyclic shifts are used which cyclically shift the bits in successive OFDM symbols by deterministic amounts.
FIG. 1 shows a block diagram of an interleaver in accordance with the above scheme. The interleaver 2 comprises a symbol interleaving unit 4, a tone interleaving unit 6 and a cyclic shift unit 8 connected in series. The symbol interleaving unit 4 receives input bits denoted {U(i)}, operates on the bits and outputs bits denoted {S(i)}. The tone interleaving unit 6 receives the bits denoted {S(i)}, operates on the bits and outputs bits denoted {V(i)}. The cyclic shift unit 8 receives the bits denoted {V(i)}, operates on the bits and outputs bits denoted {B(i)}.
The symbol interleaving operation performed by symbol interleaving unit 4 comprises dividing the coded bits into blocks of 6NCBPS coded bits, where NCBPS is the number of coded bits per symbol, and therefore 6NCBPS corresponds to six OFDM symbols. Each group of coded bits is then permuted using a block interleaver of size 6NCBPS by 6/NTDS, where NTDS is the time spreading factor. The sequences {U(i)} and {S(i)}, where i=0, . . . , NCBP6S−1 and NCBP6S is the number of coded bits in six symbols, represent the input and output bits of the symbol interleaving unit 4 respectively. The input-output relationship of this unit is given by the equation
                                          S            ⁡                          (              i              )                                =                      U            ⁢                          {                                                Floor                  ⁡                                      (                                          i                                              N                        CBPS                                                              )                                                  +                                                      6                                          N                      TDS                                                        ⁢                                      Mod                    ⁡                                          (                                              i                        ,                                                  N                          CBPS                                                                    )                                                                                  }                                      ,                            (        1        )            where Floor(x) is a function which returns the largest integer value less than or equal to its argument value, and Mod(x,y) is the modulus operator which returns the non-negative integer remainder when x is divided by y.
The output bits of the symbol interleaving unit 4, which are grouped together into blocks of NCBP6S bits, are permuted together using a regular block interleaver of size NTint×10, where NTint=NCBPS/10. The sequences {S(i)} and {V(i)}, where i=0, . . . , NCBP6S−1, represent the input and output bits of the tone block interleaver unit 6 respectively. The input-output relationship of this unit is given by the equation
                                          V            ⁡                          (              i              )                                =                      S            ⁢                          {                                                Floor                  ⁡                                      (                                          i                                              N                        Tint                                                              )                                                  +                                  10                  ⁢                                                                          ⁢                                      Mod                    ⁡                                          (                                              i                        ,                                                  N                          Tint                                                                    )                                                                                  }                                      ,                            (        2        )            
The output of the tone interleaving unit 6 is passed through intra-symbol cyclic shift unit 8. The sequences {V(i)} and {B(i)}, where i=0, . . . , NCBP6S−1, represent the input and output bits of the cyclic shift unit 8 respectively. The output of the cyclic shift unit 8 is given by the following equationB(i)=V[m(i)×NCBPS+mod(i+m(i)×Ncyc,NCBPS)]  (3)where m(i)=Floor (i/NCBPS) and i=0, . . . , NCBP6S−1.
US 2005/0152327 discloses an interleaver for a multiband OFDM transceiver of an ultra wideband personal access network in accordance with the above three-stage interleaving scheme. This document also describes a deinterleaver which is a concatenation of three blocks, a cyclic de-shift unit, a tone-deinterleaving unit and a symbol deinterleaving unit, which is costly in terms of silicon area and is not scalable.