# Multimode Flex-Interleaver Core for Baseband Processor Platform

Authors: Rizwan Asghar; Dake Liu
Journal: Journal of Computer Systems, Networks, and Communications
 (2010)

---

## Abstract

This paper presents a flexible interleaver architecture supporting multiple standards like WLAN, WiMAX, HSPA+, 3GPP-LTE, and DVB. Algorithmic level optimizations like 2D transformation and realization of recursive computation are applied, which appear to be the key to reach to an efficient hardware multiplexing among different interleaver implementations. The presented hardware enables the mapping of vital types of interleavers including multiple block interleavers and convolutional interleaver onto a single architecture. By exploiting the hardware reuse methodology the silicon cost is reduced, and it consumes 0.126mm2 area in total in 65 nm CMOS process for a fully reconfigurable architecture. It can operate at a frequency of 166 MHz, providing a maximum throughput up to 664 Mbps for a multistream system and 166 Mbps for single stream communication systems, respectively. One of the vital requirements for multimode operation is the fast switching between different standards, which is supported by this hardware with minimal cycle cost overheads. Maximum flexibility and fast switchability among multiple standards during run time makes the proposed architecture a right choice for the radio baseband processing platform.


---

## Body

## 1. Introduction

Growth of high-performance wireless communication systems has been drastically increased over the last few years. Due to rapid advancements and changes in radio communication systems, there is always a need of flexible and general purpose solutions for processing the data. The solution not only requires adopting the variances within a particular standard but also needs to cover a range of standards to enable a true multimode environment. The symbol processing is usually done in baseband processors. A fully flexible and programmable baseband processor [1–3] provides a platform for true multimode communication. To handle the fast transition between different standards, such type of platform is needed in both mobile devices and especially in base stations. Other than symbol processing, one of the challenging area is the provision of flexible subsystems for forward error correction (FEC). FEC subsystems can further be divided in two categories, channel coding/decoding and interleaving/deinterleaving. Among these categories, interleavers and deinterleavers appeared to be more silicon consuming due to the silicon cost of the permutation tables used in conventional approaches. For multistandard support devices the silicon cost of the permutation tables can grow much higher, resulting in an unefficient solution. Therefore, the hardware reuse among different interleaver modules to support multimode processing platform is of significance. This paper presents a flexible and low-cost hardware interleaver architecture which covers a range of interleavers adopted in different communication standards like HSPA Evolution (HSPA+) [4], 3GPP-LTE [5], WiMAX; IEEE 802.16e [6], WLAN; IEEE 802.11a/b/g [7], IEEE 802.11n [8], and DVB-T/H [9].Interleaving plays a vital role in improving the performance of FEC in terms of bit error rate. The primary function of the interleaver is to improve the distance properties of the coding schemes and to disperse the sequence of bits in a bit stream so as to minimize the effect of burst errors introduced in transmission [10, 11]. The main categories of interleavers are block interleavers and convolutional interleavers. In block interleavers the data are written row wise in a memory configured as a row-column matrix and then read column-wise after applying certain intra-row and inter-row permutations. They are usually specified in the form of a row-column matrix with row and/or column permutations given in tabular form, however; they can also be specified by a modulo function having more complex functions involved to define the permutation patterns. On the other hand, convolutional interleavers use multiple first-in-first-out (FIFO) cells with different width and depth. They are defined mainly by two parameters, the depth of memory cells and number of branches.Looking at the range of interleavers used in different standards (Table1) it seems difficult to converge to a single architecture; however, the fact that multimode coverage does not require multiple interleavers to work at the same time provides opportunities to use hardware multiplexing. The multimode functionality is then achieved by fast switching between standards. This research is to merge the functionality of different types of interleavers into a single architecture to demonstrate a way to reuse the hardware for a variety of interleavers having different structural properties. The method in general is the so-called hardware multiplexing technique well presented in [12]. It starts at analyzing and profiling multiple implementation flows, identifying opportunities of hardware multiplexing, and eventually fine tuning the microarchitecture, using minimal hardware, and maximal reuse of multifunctions.Table 1
List of algorithms and permutations in different interleaver implementations and the cost comparison.
StandardInterleaver typeAlgorithm/permutation methodologyHW costAddr. Gen.Data memory@65 nm@6 soft bits(μm2)(kbits)HSPA+BTCMultistep computation including intra-row permutation computation1281659.92S(j)=(v×S(j-1))%p;  r(i)=T(q(i));U(i,j)=S((j×r(i))%(p-1)); qmod(i)=r(i)%(p-1);RA(i,j)={RA(i,j-1)+qmod(i)}%(p-1); Ii,j={C×r(i)}+U(i,j)1st, 2nd, and HS-DSCH int.Standard block interleaving with given column permutations.228829.96π(k)=(P⌊kR⌋+C×(k%R))%KπLTEQPP for BTCI(x)=(f1.x+f2.x2)%N374472.0Sub-Blk. int.Standard block interleaving with given column permutations.208036.0WiMAXChannel interleaverTwo step permutation89449.0Mk=(Nd)×(k%d)+⌊kd⌋;Jk=s×⌊Mks⌋+((Mk+N-⌊d×MkN⌋)%s)Blk. int. b/w RS & CCStandard block interleaver without any permutations208019.92CTC interleaverI(x%4=0)=(P0·x+1)%N;I(x%4=1)=(P0·x+1+N2+P1)%N;728056.25I(x%4=2)=(P0·x+1+P1)%N;I(x%4=3)=(P0·x+1+N2+P3)%NWLANChannel interleaverTwo step permutation89441.68Mk=(Nd)×(k%d)+⌊kd⌋;Jk=s×⌊Mks⌋+((Mk+N-⌊d×MkN⌋)%s)802.11nCh. Interleaver with frequency rotationTwo step permutation as above, with extra frequency interleaving, that is,1156324.54Rk=[Jk-{(((iss-1)×2)%3+3⌊iss-13⌋)×NROT×NBPSC}]%NDVB-HOuter conv. interleaverPermutation defined by depth of first FIFO branch (M) and number of total braches.122728.76Inner bit interleaverSix parallel interleavers with different cyclic shift31200.738He(w)=(w+Δ)%126; where Δ=0,63,105,42,21and84Inner symbol interleaveryH(q)=xq for even symbols; yq=xH(q)for odd symbols;353635.4whereH(q)=(i%2)×2Nr-1+∑j=0Nr-2Ri(j)×2j;General purpose useRow or/and Col. Perm. GivenStandard block interleaver with or without row or/and column permutation.395224.0Total cost∑ (all)Independent implementations~82619~378.0This workReconfigurable SolutionHW Multiplexed Design2775772.0This paper is organized as follows. Section2 presents the previous work done for the interleaver algorithm implementations. The challenges involved to cover the wide range of standards are mentioned in Section 3. It also presents a shared data flow and hardware cost associated with different implementations. Section 4 provides the detailed explanation of the unified interleaver architecture and its subblocks. A brief explanation of the algorithmic transformations and optimizations used for efficient mapping onto single architecture is given in Section 5 with selected example cases. The usage of the proposed architecture while integrating into baseband system is explained in Section 6. Section 7 provided the VLSI implementation results and comparison to others followed by a conclusion in Section 8.


## 2. Previous Work

A variety of interleaver implementations having different structural properties have been addressed in literature. The main area of focus has been low cost and throughput. Most of the work covers a single or a couple of interleaver implementations which is not sufficient for a true multimode operation. The design of interleaver architecture for turbo code internal interleaver has been addressed in [13–17]. Some of these designs targeted very low-cost solutions. A recent work in [18] provides a good unified design for different standards; however, it covers only the turbo code interleavers and does not meet the complete baseband processing requirements demanding an all-in-one solution. The work in [19–22] covers the DVB-related interleaver implementations. Literature [23–27] focuses on more than one interleaver implementations with reconfigurability for multiple variants of wireless LAN and DVB. High-throughput interleaver architectures for emerging wireless communications based on MIMO-OFDM techniques have been addressed in [25, 27]. These techniques require multiple-stream processing in parallel, thus requiring parallel addresses generation and memory architecture as shown in Figure 1.Figure 1
3D view of interleaver configuration for a multistream communication system.Some commercial solutions [28–30] from major FPGA vendors are also available for general purpose use. The available literature reveals that they do not compute the row or column permutations on the fly; instead they take row or column permutation tables in the form of a configuration file as input and use them to generate the final interleaved address. In this way, the complexity for on-the-fly computation of permutation patterns is avoided. This approach needs extra memory to store the permutation patterns. As these implementations are targeted for FPGA use only, they also enjoy the availability of dual port block RAM, which is not a good choice for chip implementations.


## 3. Shared Data Flow and Algorithm Analysis

The motivation of the research is to explore an all-in-one reconfigurable architecture which can help to meet fast time-to-market requirements from industry and customers. A summary of targeted interleaver implementations which are being widely used is provided in Table1. The broadness of the interleaving algorithms gives rise to many challenges when considering a true multimode interleaver implementation. The main challenges are as follows:(i)
on the fly computation of permutation patterns,(ii)
wide range of interleaving block sizes,(iii)
wide range of algorithms,(iv)
fast switching between different standards,(v)
sufficient throughput for high-speed communications,(vi)
maximum standard coverage,(vii)
acceptable silicon cost and power consumption.Exploring the similarities between different interleaving algorithms a shared data flow in general is shown in Figure2. This data flow is shared by different interleaver types summarized in Table 1. Many of the interleaver algorithms, for example, [4, 6–9] need some preprocessing before starting actual interleaving process. Therefore the whole data flow has been divided into two phases named as precomputation phase as shown in Figure 2(a) and the execution phase as shown in Figure 2(b). There are many minor differences in both the phases when we consider different types of interleavers; however, one of the main differences might be due to the type of interleaver, that is, block interleaver or convolutional interleaver. Other than the differences in address calculation for the two categories, a major difference is the memory access mechanism. In case of block interleaver the memory read and write is explicit but a convolutional interleaver needs to write and read at the same time. This demands a dual port memory; however, it has been dealt by dividing the memories and introducing a delay in the read path. To get the general idea of cost saving by using hardware multiplexed architecture with shared data flow, each of the algorithms is implemented separately after applying appropriate algorithmic transformations. Comparing the hardware cost for different implementations as given in Table 1, the proposed hardware multiplexed architecture based on shared data flow provides 3 times lower silicon cost for address generation and about 5 times lower silicon cost for data memory in shared mode. Going through all the interleaver implementations given in Table 1, different hardware requirements for computing elements and memory are summarized in Table 2. Looking at the modulo computation requirements, the use of adder appears to be the common computing element for all kinds of implementations. Further observation reveals that adder is mostly followed by a selection logic. Therefore, a common computing cell named acc_sel as shown in Figure 3 is used to cover all the cases. Table 2 shows that the computational part of the reconfigurable implementation can be restricted to have 8 additions, 1 multiplication, and a comparator.Table 2
Architecture exploration for different standards.
StandardInterleaver typeBlock sizeAdders/comparatorMultiplierHW LUTConfigurable LUT/registersMemory size (SB: soft bits)HSPA+Prime interleaver for BTC51147120×5b20×8b2×5114×SB440×7b256×8b52×14b1st, 2nd, and HS-DSCH interleaving51142115×3b—5114×SB32×5b3GPP-LTEQPP interleaver for BTC61445—188×19b2×13b2×6144×SBSub-Block interleaver61442132×5b—6144×SBWiMAX (802.16e)Channel interleaver15365115×4b2×2b1536×SB1×11bBlock interleaver b/w RS and CC255021——2550×8bCTC interleaver24004—32×27b1×12b4×2400×SBWLAN (802.11 a/b/g)Channel interleaver2885115×4b2×2b288×SB1×9b802.11nEnhanced WLANChannel interleaver with frequency rotation25929130×4b2×2b4×648×SB24×9b2×10bDVBETSI EN 300-744Outer convolutional interleaver112241—11×11b357×8b765×8bInner bit interleaver1268——21×1b2×126×1b126×1b2×126×2bInner symbol interleaver60481—30×1b—6048×6bGeneral purpose useRow or/and Column permutation given as a table409621—256×8b4096×SB64×6bData flow graph for (a) precomputation phase (b) execution phase.
(a)(b)Figure 3
An accumulation and selection cell (acc_sel).The memory requirements for different implementations are also very wide, due to different sizes, width, memory banks and ports. The memory organization and address computation is explained in detail in the next section.


## 4. Multimode Interleaver Architecture

The study from algorithm analysis provides the basis to multiplex the hardware intensive components and combine the functionality of multiple types of interleavers. The architecture for the multimode interleaver is given in Figure4. The hardware partitioning is done in such a way that all computation intensive components are included in the address generation block. The other partitioned blocks are register file, control-FSM, and memory organization block. These blocks are briefly described in the following subsections.Figure 4
Address generation schematic in detail.


### 4.1. Address Generation (ADG) Block

Address generation is the main concern for any kind of interleaving. Unified address generation is achieved by multiplexing the computation intensive blocks mentioned in Table2. The address generation hardware is shown in detail in Figure 4. It is surrounded by other blocks like control FSM, register file, and some lookup tables. It utilizes 8 acc_sel units with a multiplier and a comparator. The reconfigurability is mainly achieved through changing the behavior of acc_sel and appropriate multiplexer selection. The control signals Add_Sub, Ext_Ctrl_En and, Sel_Ctrl are used to define the behavior of acc_sel block. Using these signals in an appropriate way this block can be configured as an adder, a subtractor, a modulo operation with MSB of output as select line, or just a bypass. All the combinations are fully utilized and make it a very useful common computing element. The address generation block takes the configuration vector and configures itself with the help of a decoder block and part of the LUT. The configuration vector is 32 bit wide, which defines block size, interleaver depth, interleaving modes, and modulation schemes.The ADG block generates the interleaved address based on all the permutations involved for implementing a block interleaver, whereas it generates memory read and write addresses concurrently while implementing a convolutional interleaver. The role of ADG block to be used as an interleaver or deinterleaver is mainly controlled by the controller after employing an addressing combination (permuted or sequential addressing) for writes and reads from the memory.


### 4.2. Control FSM

Two modes of operation for the hardware are defined as precomputation mode and execution mode. In order to handle the sequence of operations in the two modes a multistate control-FSM is used. The flow graph of the control-FSM is shown in Figure5. During precomputation phase, the FSM may perform two main functions: (1) computation of necessary parameters required for interleaver address computation and (2) initialization of registers to become ready for execution phase. Other than IDLE state, 5 states (S1~S4, S8) are assigned for precomputation. The common parameter to be computed in the precomputation phase is number of rows or columns; however, some specific parameters like prime number p; and intra-row permutation sequence S(j) in WCDMA turbo code interleaver are also computed during this phase. For the interleaver functions which do not require precomputation, the initialization steps for precomputation are bypassed, and the control FSM directly jumps to the execution phase. The extra cycle cost associated with the precomputation has been investigated for the current implementation and the results are presented in a later section. In the execution phase, the control-FSM helps in sequencing the loading of data frames into memory or reading data frames from memory. In total 4 states (S5~S7, S9) are assigned for execution phase. S9 is used for convolutional interleaver case only, whereas states S5~S7 are reused for all types of interleavers. During the execution phase the control-FSM keeps track of block size also by employing row and column counter, thus providing the block synchronization required for each type of interleaver implementation.Figure 5
FSM state graph.


### 4.3. Register File

The requirement of temporary storage of parameters arises with many types of interleaver implementations. Register requirements from different implementations are listed in Table2. Some special usage configuration is also required for different cases; for example, WCDMA turbo code interleaver needs 20 registers to form a circular buffer, convolutional interleaver in DVB requires 11 registers to be used as a general purpose register file, and the bit interleaver in DVB requires a long chain of single bit registers. Due to small size and special configuration requirements, a general purpose register file is not feasible here, and a fully customized register file is used. The width of registers is not the same and it is optimized as per requirement from different implementations. The registers can also be connected to form a chain, thus the single bit buffer for a bit interleaver is managed by circulating the shifted output inside register file. The two data input ports of the register file are fed through multiplexers M18 and M19 as shown in Figure 4.


### 4.4. Memory Organization

Memory requirements for different types of interleaver implementations are very much different as listed in Table2. Also, soft bit processing in the decoder implies different requirements of bit width for different conditions and decoding architectures. The maximum width requirement is 6 bits for symbol interleaving and 8 bits for part of the memory in WCDMA. Multistream transmission requires multiple banks of memories in parallel. The size of the memory is taken as 2×6144×SB, which is due to large block size requirements for 3GPP-LTE, 3GPP-WCDMA, and DVB.Memory partitioning is mainly motivated by the high-throughput requirements from the multistream system, for example, 802.11n. It requires four memory banks in parallel which appears to be a good choice to meet other requirements as well. Parallel memory banks can also be used in series to form a big memory. Partial parallelism can also be used where larger memory width is needed. Another worth full benefit of using multiple memory banks is avoiding the use of dual port RAM, which is not silicon efficient. Thus all the memories in the design are single port memories. The interleaved addresses for block and convolution interleavers computed by address generation block are combined according to the configuration requirement to make the final memory address. Figure6 shows the memory organization with address selection logic. Particularly for convolutional interleaving, a small delay line with depth of 6 in the path of read addresses and control signals is used to avoid the data write and read for the same memory in a single clock cycle.Figure 6
Memory address selection and data handle.


## 4.1. Address Generation (ADG) Block

Address generation is the main concern for any kind of interleaving. Unified address generation is achieved by multiplexing the computation intensive blocks mentioned in Table2. The address generation hardware is shown in detail in Figure 4. It is surrounded by other blocks like control FSM, register file, and some lookup tables. It utilizes 8 acc_sel units with a multiplier and a comparator. The reconfigurability is mainly achieved through changing the behavior of acc_sel and appropriate multiplexer selection. The control signals Add_Sub, Ext_Ctrl_En and, Sel_Ctrl are used to define the behavior of acc_sel block. Using these signals in an appropriate way this block can be configured as an adder, a subtractor, a modulo operation with MSB of output as select line, or just a bypass. All the combinations are fully utilized and make it a very useful common computing element. The address generation block takes the configuration vector and configures itself with the help of a decoder block and part of the LUT. The configuration vector is 32 bit wide, which defines block size, interleaver depth, interleaving modes, and modulation schemes.The ADG block generates the interleaved address based on all the permutations involved for implementing a block interleaver, whereas it generates memory read and write addresses concurrently while implementing a convolutional interleaver. The role of ADG block to be used as an interleaver or deinterleaver is mainly controlled by the controller after employing an addressing combination (permuted or sequential addressing) for writes and reads from the memory.


## 4.2. Control FSM

Two modes of operation for the hardware are defined as precomputation mode and execution mode. In order to handle the sequence of operations in the two modes a multistate control-FSM is used. The flow graph of the control-FSM is shown in Figure5. During precomputation phase, the FSM may perform two main functions: (1) computation of necessary parameters required for interleaver address computation and (2) initialization of registers to become ready for execution phase. Other than IDLE state, 5 states (S1~S4, S8) are assigned for precomputation. The common parameter to be computed in the precomputation phase is number of rows or columns; however, some specific parameters like prime number p; and intra-row permutation sequence S(j) in WCDMA turbo code interleaver are also computed during this phase. For the interleaver functions which do not require precomputation, the initialization steps for precomputation are bypassed, and the control FSM directly jumps to the execution phase. The extra cycle cost associated with the precomputation has been investigated for the current implementation and the results are presented in a later section. In the execution phase, the control-FSM helps in sequencing the loading of data frames into memory or reading data frames from memory. In total 4 states (S5~S7, S9) are assigned for execution phase. S9 is used for convolutional interleaver case only, whereas states S5~S7 are reused for all types of interleavers. During the execution phase the control-FSM keeps track of block size also by employing row and column counter, thus providing the block synchronization required for each type of interleaver implementation.Figure 5
FSM state graph.


## 4.3. Register File

The requirement of temporary storage of parameters arises with many types of interleaver implementations. Register requirements from different implementations are listed in Table2. Some special usage configuration is also required for different cases; for example, WCDMA turbo code interleaver needs 20 registers to form a circular buffer, convolutional interleaver in DVB requires 11 registers to be used as a general purpose register file, and the bit interleaver in DVB requires a long chain of single bit registers. Due to small size and special configuration requirements, a general purpose register file is not feasible here, and a fully customized register file is used. The width of registers is not the same and it is optimized as per requirement from different implementations. The registers can also be connected to form a chain, thus the single bit buffer for a bit interleaver is managed by circulating the shifted output inside register file. The two data input ports of the register file are fed through multiplexers M18 and M19 as shown in Figure 4.


## 4.4. Memory Organization

Memory requirements for different types of interleaver implementations are very much different as listed in Table2. Also, soft bit processing in the decoder implies different requirements of bit width for different conditions and decoding architectures. The maximum width requirement is 6 bits for symbol interleaving and 8 bits for part of the memory in WCDMA. Multistream transmission requires multiple banks of memories in parallel. The size of the memory is taken as 2×6144×SB, which is due to large block size requirements for 3GPP-LTE, 3GPP-WCDMA, and DVB.Memory partitioning is mainly motivated by the high-throughput requirements from the multistream system, for example, 802.11n. It requires four memory banks in parallel which appears to be a good choice to meet other requirements as well. Parallel memory banks can also be used in series to form a big memory. Partial parallelism can also be used where larger memory width is needed. Another worth full benefit of using multiple memory banks is avoiding the use of dual port RAM, which is not silicon efficient. Thus all the memories in the design are single port memories. The interleaved addresses for block and convolution interleavers computed by address generation block are combined according to the configuration requirement to make the final memory address. Figure6 shows the memory organization with address selection logic. Particularly for convolutional interleaving, a small delay line with depth of 6 in the path of read addresses and control signals is used to avoid the data write and read for the same memory in a single clock cycle.Figure 6
Memory address selection and data handle.


## 5. Algorithm Transformation for Efficient Mapping

The main objective is to use single architecture for interleaver implementation with maximum hardware sharing among different algorithms. The versatility of interleaving algorithms makes it an in-efficient implementation when original algorithms are directly mapped to same architecture. On the other hand some transformations based on modular algebra can be applied on the original algorithms to make them hardware efficient. Same algorithmic transformations can be used to reach to an efficient hardware multiplexing among different standards. The following subsections present some transformation examples for selected algorithms which are very much versatile in the implementation point of view. These subsections cover channel interleaving for WiMAX and WLAN including 802.11n with frequency rotation, turbo code block interleaving for LTE, WiMAX, and HSPA Evolution, and convolutional interleaving used in DVB.


### 5.1. Channel Interleaving in WiMAX and WLAN

The channel interleaving in 802.11a/b/g (WLAN) and 802.16e (WiMAX) is of the same type. The interleaver function defined by a set of two equations for two steps of permutations, provides spatial interleaving, whereas the newly evolved standard 802.11n [8] based on MIMO-OFDM employs frequency interleaving in addition to spatial interleaving. Most of literature available [31–36] covers the performance and evaluation of WLAN interleaver design for a high-speed communication system; however, some recent work [23–27] focuses on interleaver architecture design including some complexity reduction techniques along with feasibility to gain higher throughput. The 2D realization of interleaver functions is exploited to enable efficient hardware implementation. The two steps of permutations for index k for interleaver data are expressed by the following equations:(1)Mk=(Nd)×(k%d)+⌊kd⌋,(2)Jk=s×⌊Mks⌋+((Mk+N-⌊d×MkN⌋)%s).HereN is the block size corresponding to number of coded bits per allocated subchannels and the parameter s is defined as s=max{1,NBPSC/2} where NBPSC is the number of coded bits per subcarrier, (i.e., 1, 2, 4 or 6 for BPSK, QPSK, 16-QAM, or 64-QAM, resp.). The operator % is the modulo function computing the remainder and the operator ⌊x⌋ is the floor function, that is, rounding x towards zero. The range of  n and k is defined as 0,1,2,…(N-1). The direct implementation of the above mentioned equations is very much hardware in-efficient and also the mapping onto the proposed unified interleaver architecture is not possible. Therefore, realization of two 1D equations into 2D space and computation of interleaved address in recursive way is adopted to reduce the hardware complexity as explained in the following subsections.


#### 5.1.1. BPSK-QPSK

AsNBPSC is 1 and 2 for BPSK and QPSK, respectively; thus s=1 for both cases and (2) simplifies to the following form:(3)Jk=(Nd)×(k%d)+⌊kd⌋.Considering the interleaver as a block interleaver, the parameterd is usually considered as total number of columns NCOL, and parameter N/d is taken as total number of rows NROW, but the column and row definition are swapped hereafter. The parameter d is taken as total number of rows and parameter N/d is taken as total number of columns. The functionality still remains the same, with the benefit that it ends up with the recursive expression for all the modulation schemes. According to new definitions, the term (k%d) provides the behavior of row counter and the term ⌊k/d⌋ provides the behavior of column counter. Thus introducing two new variables i and j as two dimensions, such that j increments when i expires, the ranges for i and j are mentioned as follows:
(4)i=0,1,…(d-1),j=0,1,…(Nd-1),
which satisfies against k when i=(k%d) and j=⌊k/d⌋. Defining total number of columns as C=N/d, (3) can be written as(5)Ji,j=C×i+j.The recursive form after handling the exception againsti=0 can be written as(6)Ji,j={j,if(i=0),J(i-1),j+C,otherwise.Defining row counteri as i=Rc and column counter j as j=Cc, the hardware for (6) is shown in Figure 7(a). The case of BPSK and QPSK do not carry any specific inter-row or inter-column permutation pattern; thus it ends up with relatively simple hardware, but it provides the basis for analysis for 16-QAM and 64-QAM cases, which are more complicated.Interleaver address generation for (a) BPSK-QPSK, (b) 16-QAM, and (c) combined for all modulation schemes.
(a)(b)(c)


#### 5.1.2.16-QAM

16-QAM scheme has 4 code bits per subcarrier; thus parameters is 2 and (2) becomes(7)Jk=2×⌊Mk2⌋+((Mk+N+⌊d×MkN⌋)%2).Like BPSK/QPSK case, algebraic only steps cannot be used here to proceed due to the presence of floor and modulo functions. Instead, all the possible block sizes for 16-QAM are analyzed to restructure the above equation. The following structure appears to be equivalent to (7) and at the same time resembles the structure of (3); thus it suits well for hardware multiplexing:(8)Jk=(Nd)×(k%d)+⌊kd⌋+rk2.The extra termrk2 is defined by the following expression:(9)rk2=[(1-(k%2))-(k%2)]{1-(⌊kd⌋%2)}+[((k%2)-1)+(k%2)]{⌊kd⌋%2}.This term appears due to the reason that the interleaver for 16-QAM carries specific permutation patterns, making the structure more complicated. Considering the 2-dimensions i and j having range as mentioned in (4), the behavior of the term k%2 is the same as that of i%2, when i is the row counter. Thus (8) can be written in 2D representation as follows:(10)Ji,j={j,if(i=0),J(i-1),j+C+ri,j2,otherwise,
where
(11)ri,j2=[(1-(i%2))-(i%2)]{1-(j%2)}+[(i%2)+(1-(i%2))]{j%2}.The term can further be simplified to a smaller expression but it is easy to realize the hardware from its current form. The modulo terms can be implemented by using the LSB of row counterRc and column counter Cc, and the required sequence can be generated with the help of an XOR gate and an adder as shown in Figure 7(b).


#### 5.1.3.64-QAM

The parameters is 3 for 64-QAM; thus (2) becomes(12)Jk=3×⌊Mk3⌋+((Mk+N+⌊d×MkN⌋)%3).The presence of modulo functionx%3 makes it much harder to reach some valid mathematical expression algebraically. Different structures for all possible block sizes for 64-QAM are analyzed and the structure similar to (6) and (10) and equivalent to (12) is given as follows:(13)Ji,j={j,if(i=0),J(i-1),j+C+ri,j3,otherwise,
where i and j represent two dimensions and their range is given by (4). Defining  i′=(i%3) and j′=(j%3), ri,j3 is given as(14)ri,j3=((1-j′)+j′(j′-1)2){2((1-i′)+i′(i′-1)2)-(i′-i′(i′-1)2)}+(j′-j′(j′-1)){2(i′-i′(i′-1))-((1-i′)+i′(i′-1))}+(j′(j′-1)2){2(i′(i′-1)2)-(1-i′(i′-1)2)}.
The term ri,j3 provides the inter-row and inter-column permutation for s=3 against row counter i and column counter j. The expression for ri,j3 looks very long and complicated, but eventually, it gives a hardware efficient solution as the terms inside braces are easier to generate through a very small lookup table. The generic form for (6), (10), and (13) to compute the interleaved address Ii,j can be written as(15)Ii,j={j,if(i=0),I(i-1),j+C+ri,js,otherwise.Here parameters distinguishes different modulation schemes. For BPSK/QPSK ri,j1=0, and for 16-QAM and 64-QAM, ri,j2 and ri,j3 are given by (9) and (14), respectively. The hardware realization supporting all modulation schemes is shown in Figure 7(c). It appears to be a much optimized implementation as it involves only two additions, some registers, and a very small lookup table.


### 5.2. Frequency Interleaving in 802.11n

The transmission in 802.11n can be distributed among four spatial streams as shown in Figure8. The interleaving requires frequency rotation in case more than one spatial streams are being transmitted. The frequency rotation is applied to the output of the second permutation Jk. The expression for frequency rotation for spatial stream iss is given as follows:Figure 8
Use of interleaver in multiple spatial streams (802.11n).(16)Rk=[Jk-{(((iss-1)×2)%3+3⌊iss-13⌋)×NROT×NBPSC(((iss-1)×2)%3+3⌊iss-13⌋)}]%N.HereNROT is the parameter which defines different frequency rotations for 20 MHz and 40 MHz case in 802.11n. The frequency rotation also depends on the index of the spatial stream iss, thus each spatial stream faces different frequency rotations. Defining the rotation term as JROT, that is,(17)JROT={(((iss-1)×2)%3+3⌊iss-13⌋)×NROT×NBPSC(((iss-1)×2)%3+3⌊iss-13⌋)}(((iss-1)×2)%3+3⌊iss-13⌋),we have(18)Rk=(Jk-JROT)%N.The range for the term(Jk-JROT) is not bounded and it can have value greater than 2N; thus direct implementation cannot be low cost. Analyzing the two terms  [Jk%N]  and (-JROT)%N separately, it is observed that the second term provides the starting point for computing the rotation Rk. As the rotation is fixed for a specific spatial stream, thus the starting value rks=(-JROT)%N  also holds for all run time computations. Equation (18) in combination with (10) can be written as(19)Ji,jiss≡Rk=(Ji,j+rks)%N.HereJi,jiss  is the joint address after applying both, spatial interleaving and frequency interleaving against row index i, column index j and spatial stream index iss. A lookup can be used for the starting values for rks against different spatial streams. The rks values for all the cases follow the condition, that is, (rks<N) which depicts that the term (Jk+rks) cannot be larger than 2N. Therefore, the frequency rotation can be computed with a very small hardware as shown in Figure 9.Figure 9
HW for frequency rotation in 802.11n.


### 5.3. Multistream Interleaver Support in 802.11n

The spatial interleaver address generation block shown in Figure7(c) is denoted as Basic Block (BB) and the frequency rotation block as shown in Figure 9 is denoted as Auxiliary Block (AB). Both these blocks combine to form a complete address generation circuit for one spatial stream. In order to provide support for four streams in parallel, one may consider replicating the two blocks four times. However, an optimized solution would be to use 2 basic blocks and 2 auxiliary blocks, still providing support for 4 spatial streams. The hardware block diagram to generate the interleaver addresses for multiple streams in parallel is shown in Figure 10. This hardware supports quick configuration changes thus providing full support to any multitasking environment. If some new combination of modulation schemes is needed to be implemented, which is not supported already, the interfacing processor can do task scheduling for different types of modulation schemes.Figure 10
HW for quad stream interleaver.


### 5.4. Turbo Code Interleaver for HSPA+

The channel coding block in HAPA+ including WCDMA uses turbo coding [37] for forward error correction. 3GPP standard [4] proposes the algorithm for block interleaving in turbo encoding/decoding as mentioned below. Here N is the block size, R is the row size, and C is the column size in bits.(i)
Find appropriate number of rows “R”, prime number “p”, and primitive root “v” for particular block size as given in the standard.(ii)
Col Size:(20)C=p-1,if(N≤R×(p-1)),C=p,if(R×(p-1)<N≤(R×p)),C=p+1,if(R×p<N).(iii)
Construct intra-row permutation sequenceS(j) by(21)S(j)=[v×S(j-1)]%p;j=1,2,…p-2.(iv)
Determine the least prime integer sequenceq(i) for i=1,2,…R-1,by taking q(0)=1,such that g.c.d(q(i),p-1)=1,q(i)>6 and q(i)>q(i-1).(v)
Apply inter-row permutations toq(i) to find r(i):(22)r(i)=T(q(i)).(vi)
Perform the intra-row permutationsUi,j,for i=0,1,…R-1 and  j=0,1,…p-2.If(C=p):Ui,j=S[(j×r(i))mod(p-1)] and Ui,(p-1)=0.If(C=p+1):Ui,j=S[(j×r(i))mod(p-1)],and Ui,(p-1)=0,Ui,p=p,and if (N=R×C) then exchange U(R-1,0) with U(R-1,p).If(C=p-1):Ui,j=S[(j×r(i))mod(p-1)]-1.(vii)
Perform the inter-row permutations.(viii)
Read the address columns wise.The presence of complex functions like modulo computation, intra-row and inter-row permutations, multiplications, finding least prime integers, and computing greatest common divisor makes it in-efficient while implementing it in its original form. Further, to get one interleaving address in each cycle, some preprocessing is also required where parameters like total number of rows or columns, least prime number sequenceq(i), inter-row permutation patterns T(i), intra-row permutations S(j), prime number p, and associated integer v are computed. Some of these parameters can be computed using lookup tables while the others need some close loop or recursive computations. The simplifications considered in the implementation are discussed in the following paragraphs.One of the main hurdles to generate on-the-fly interleaved address is the computation of intra-row permutation sequenceS(j). Before applying the intra-row permutations, the term (j×r(i)%(p-1)) is computed which produces random values due to r(i) and modulo function. These random values appear as index to compute S(j), due to which it may require many clock cycles to be computed on-the-fly. To resolve it, some precomputations are made and results are stored in a memory. These precomputations involve the computation of a modulo function which requires a divider for direct implementation. To avoid the use of divider, indirect computation of modulo function is done by using Interleaved Modulo Multiplication Algorithm [38]. It computes the modulo function in an iterative way requiring more than one clock cycles. Looking at maximum value of v, which is 5 bits, a maximum of 5 iterations are needed to compute one modulo multiplication. The algorithm to compute the Interleaved Modulo Multiplications is shown in Figure 11 and the hardware required is shown in Figure 12. This hardware produces the data for memory while in precomputation phase; however, same hardware is utilized to generate the address for the memory, while in execution phase.  The usage of memory depends on the parameter p and it will be filled upto (p-2) locations.Figure 11
Flow graph for interleaved modulo multiplication algorithm.Figure 12
WCDMA turbo code interleaver hardware.Findingqmod(i)=q(i)%(p-1) instead of direct computation of least prime number sequence q(i) gives the benefit of computing the RAM address recursively and avoiding computation of the modulo function. This idea was introduced in [13] and later on it has been used in [14, 16, 17]. The computation of q(i)%(p-1) can be managed by a subtractor and a look up table, provided that all the values of q(i) placed in the look up table satisfy the condition q(i)<2(p-1). The similarities between different sequences for q(i)%(p-1) for all possible p values are very helpful to improve the efficiency of the lookup table. The parameters p and v are stored in combined fashion in a lookup table of size 52×14b. The lookup table is addressed via a counter. Against each value of p, the condition (p×R≥N-R) is checked using a comparator to find the appropriate value for p and v. Once p is found, the total number of columns C can have only three values, that is, p-1, p, or p+1. Hence C is found in at most three clock cycles by checking the condition (R×C≥N). The recursive function used to compute the RAM address with the help of parameter qmod(i) is given by(23)RA(i,j)={RA(i,j-1)+qmod(i)}%(p-1).The data from RAM are denoted asU(i,j) after passing through some exception handling logic. Parameter U(i,j) provides the intra-row permutation pattern for a particular row. The final interleaved address Ii,j can be found by combining the inter-row permutation with intra-row permutation as follows:(24)Ii,j={C×r(i)}+U(i,j).The complete hardware for interleaver address generation for Turbo Code interleaver is shown in Figure12. It can be mapped to the proposed unified interleaver architecture quite efficiently.


### 5.5. Turbo Code Interleaving in 3GPP-LTE and WiMAX

The newly evolved standard, 3GPP LTE [5], involves interleaving in the channel coding and rate matching section. The interleaving in rate matching is called subblock interleaving and is based on simple block interleaving scheme. The channel coding in LTE involves Turbo Code with an internal interleaver. The type of interleaver here is different and it is based on quadratic permutation polynomial (QPP), which provides very compact representation. The turbo interleaver in LTE is specified by the following quadratic permutation polynomial:(25)I(x)=(f1·x+f2·x2)%N.Herex=0,1,2,…(N-1), with N as block size. This polynomial provides deterministic interleaver behavior for different block sizes and appropriate values of f1 and f2. Direct implementation of the permutation polynomial given in (25) is hardware in-efficient due to multiplications, modulo function, and bit growth problem. To simplify the hardware, (25) can be rewritten for recursive computation as(26)I(x+1)=(I(x)+g(x))%N,
where  g(x)=(f1+f2+2·f2·x)%N. This can also be computed recursively as(27)g(x+1)=(g(x)+2·f2)%N.The two recursive terms mentioned in (26) and (27) are easy to implement in hardware (Figure 13) with the help of a LUT to provide the starting values for g(x) and f2.Figure 13
Simplified HW for 3GPP-LTE and CTC interleaver.WiMAX standard [6] uses convolutional turbo coding (CTC) also termed duo-binary turbo coding. They can offer many advantages like performance, over classical single-binary turbo codes [39]. Parameters to define the interleaver function as described in [6] are designated as P0,P1,P2, and P3. Two steps of interleaving are described as follows.Step 1.
Let the incoming sequence be(28)u0=[(A0,B0),(A1,B1),(A2,B2),…(AN-1,BN-1)];forx=0⋯N-1,if(i%2)=1,then(Ai,Bi)=(Bi,Ai).
The new sequence is(29)u1=[(A0,B0),(B1,A1),(A3,B3),…(BN-1,AN-1)].Step 2.
The functionI(x) provides the address of the couple from the sequence u1 that will be mapped onto address x of the interleaved sequence. I(x) is defined by the set of four expressions with a switch selection as follows:
forx=0⋯N-1
switch(x%4).
case  0:I(x%4=0)=(P0·x+1)%N.
case  1:I(x%4=1)=(P0·x+1+N/2+P1)%N.
case  2:I(x%4=2)=(P0·x+1+P2)%N.
case  3:I(x%4=3)=(P0·x+1+N/2+P3)%N.Combining the four equations provided in step-2, the interleaver functionI(x) becomes(30)I(x)=(βx+Qx)%N,
where βx can be computed using recursion, that is, β(x+1)=(βx+P0)%N by taking  β0=0·Qx is given by(31)Qx={1,if(j%4=0),1+N2+P1,if(j%4=1),1+P2,if(j%4=2),1+N2+P3,if(j%4=3).As range ofβx and Qx is less than N, thus Ix can be computed by using addition and subtraction with compare and select logic as shown in Figure 13.


### 5.6. Convolutional Interleaving in DVB

The convolutional interleaver used in DVB is based on the Forney [40] and Ramsey type III approach [41]. The convolutional interleaver being part of outer coding resides in between RS encoding and convolutional encoding. The convolutional interleaver for DVB consists of 12 branches as shown in Figure 14. Each branch j is composed of first-in-first-out (FIFO) shift registers with depth j×M, where M=17 for DVB. The packet of 204 bytes consisting of one sync byte (0×47or0×B8) is entered into the interleaver in a periodic way. For synchronization purpose the sync bytes are always routed to branch-0 of interleaver.Figure 14
Convolutional interleaver and deinterleaver in DVB.Convolutional interleaving is best suited for real time applications with some added benefits of half the latency and less memory utilization as compared to block interleaving. Recently, convolutional interleavers have been analyzed to work with Turbo codes [42–44], with improved performance, which make them more versatile; thus general and reconfigurable convolutional interleaver architecture integrated with block interleaver functionality can be of significance.Implementation of convolutional interleavers using first-in-first-out (FIFO) register cells is silicon inefficient. To achieve a silicon efficient solution, RAM-based implementation is adopted. The memory partitioning is made in such a way that by applying appropriate read/write addresses in a cyclic way, it exhibits the branch behavior as required by a convolutional interleaver. RAM write and read addresses are generated by the hardware shown in Figure15. The hardware components used here are almost the same as used by interleaver implementation for other standards, thus providing the basis for multiplexing the hardware blocks for reuse. To keep track of next write address for each branch, 11 registers are needed, which provides the idea of using cyclic pointers instead of using FIFO shift registers. For each branch the corresponding write address is provided by the concerned pointer register and next write address (which is also called current read address) is computed by using an addition and a comparison with the branch boundaries. Other reference implementations have used branch boundary tables directly, but to keep the design general, the branch boundaries are computed on-the-fly using an adder and a multiplier in connection with a branch counter.Figure 15
HW for RAM read/write address generation for convolutional interleaver.For implementing a convolutional deinterleaver, the same hardware is used by implementing the branch counter in reverse order (decrementing by 1). In this way, same branch boundaries are used, and the only difference is that the sync byte in the data is now synchronized with the largest branch size as shown in Figure14. Keeping the same branch boundaries for the deinterleaver, the width of the pointer register becomes fixed. This gives an additional benefit that the width of pointer register may be optimized efficiently.


## 5.1. Channel Interleaving in WiMAX and WLAN

The channel interleaving in 802.11a/b/g (WLAN) and 802.16e (WiMAX) is of the same type. The interleaver function defined by a set of two equations for two steps of permutations, provides spatial interleaving, whereas the newly evolved standard 802.11n [8] based on MIMO-OFDM employs frequency interleaving in addition to spatial interleaving. Most of literature available [31–36] covers the performance and evaluation of WLAN interleaver design for a high-speed communication system; however, some recent work [23–27] focuses on interleaver architecture design including some complexity reduction techniques along with feasibility to gain higher throughput. The 2D realization of interleaver functions is exploited to enable efficient hardware implementation. The two steps of permutations for index k for interleaver data are expressed by the following equations:(1)Mk=(Nd)×(k%d)+⌊kd⌋,(2)Jk=s×⌊Mks⌋+((Mk+N-⌊d×MkN⌋)%s).HereN is the block size corresponding to number of coded bits per allocated subchannels and the parameter s is defined as s=max{1,NBPSC/2} where NBPSC is the number of coded bits per subcarrier, (i.e., 1, 2, 4 or 6 for BPSK, QPSK, 16-QAM, or 64-QAM, resp.). The operator % is the modulo function computing the remainder and the operator ⌊x⌋ is the floor function, that is, rounding x towards zero. The range of  n and k is defined as 0,1,2,…(N-1). The direct implementation of the above mentioned equations is very much hardware in-efficient and also the mapping onto the proposed unified interleaver architecture is not possible. Therefore, realization of two 1D equations into 2D space and computation of interleaved address in recursive way is adopted to reduce the hardware complexity as explained in the following subsections.


### 5.1.1. BPSK-QPSK

AsNBPSC is 1 and 2 for BPSK and QPSK, respectively; thus s=1 for both cases and (2) simplifies to the following form:(3)Jk=(Nd)×(k%d)+⌊kd⌋.Considering the interleaver as a block interleaver, the parameterd is usually considered as total number of columns NCOL, and parameter N/d is taken as total number of rows NROW, but the column and row definition are swapped hereafter. The parameter d is taken as total number of rows and parameter N/d is taken as total number of columns. The functionality still remains the same, with the benefit that it ends up with the recursive expression for all the modulation schemes. According to new definitions, the term (k%d) provides the behavior of row counter and the term ⌊k/d⌋ provides the behavior of column counter. Thus introducing two new variables i and j as two dimensions, such that j increments when i expires, the ranges for i and j are mentioned as follows:
(4)i=0,1,…(d-1),j=0,1,…(Nd-1),
which satisfies against k when i=(k%d) and j=⌊k/d⌋. Defining total number of columns as C=N/d, (3) can be written as(5)Ji,j=C×i+j.The recursive form after handling the exception againsti=0 can be written as(6)Ji,j={j,if(i=0),J(i-1),j+C,otherwise.Defining row counteri as i=Rc and column counter j as j=Cc, the hardware for (6) is shown in Figure 7(a). The case of BPSK and QPSK do not carry any specific inter-row or inter-column permutation pattern; thus it ends up with relatively simple hardware, but it provides the basis for analysis for 16-QAM and 64-QAM cases, which are more complicated.Interleaver address generation for (a) BPSK-QPSK, (b) 16-QAM, and (c) combined for all modulation schemes.
(a)(b)(c)


### 5.1.2.16-QAM

16-QAM scheme has 4 code bits per subcarrier; thus parameters is 2 and (2) becomes(7)Jk=2×⌊Mk2⌋+((Mk+N+⌊d×MkN⌋)%2).Like BPSK/QPSK case, algebraic only steps cannot be used here to proceed due to the presence of floor and modulo functions. Instead, all the possible block sizes for 16-QAM are analyzed to restructure the above equation. The following structure appears to be equivalent to (7) and at the same time resembles the structure of (3); thus it suits well for hardware multiplexing:(8)Jk=(Nd)×(k%d)+⌊kd⌋+rk2.The extra termrk2 is defined by the following expression:(9)rk2=[(1-(k%2))-(k%2)]{1-(⌊kd⌋%2)}+[((k%2)-1)+(k%2)]{⌊kd⌋%2}.This term appears due to the reason that the interleaver for 16-QAM carries specific permutation patterns, making the structure more complicated. Considering the 2-dimensions i and j having range as mentioned in (4), the behavior of the term k%2 is the same as that of i%2, when i is the row counter. Thus (8) can be written in 2D representation as follows:(10)Ji,j={j,if(i=0),J(i-1),j+C+ri,j2,otherwise,
where
(11)ri,j2=[(1-(i%2))-(i%2)]{1-(j%2)}+[(i%2)+(1-(i%2))]{j%2}.The term can further be simplified to a smaller expression but it is easy to realize the hardware from its current form. The modulo terms can be implemented by using the LSB of row counterRc and column counter Cc, and the required sequence can be generated with the help of an XOR gate and an adder as shown in Figure 7(b).


### 5.1.3.64-QAM

The parameters is 3 for 64-QAM; thus (2) becomes(12)Jk=3×⌊Mk3⌋+((Mk+N+⌊d×MkN⌋)%3).The presence of modulo functionx%3 makes it much harder to reach some valid mathematical expression algebraically. Different structures for all possible block sizes for 64-QAM are analyzed and the structure similar to (6) and (10) and equivalent to (12) is given as follows:(13)Ji,j={j,if(i=0),J(i-1),j+C+ri,j3,otherwise,
where i and j represent two dimensions and their range is given by (4). Defining  i′=(i%3) and j′=(j%3), ri,j3 is given as(14)ri,j3=((1-j′)+j′(j′-1)2){2((1-i′)+i′(i′-1)2)-(i′-i′(i′-1)2)}+(j′-j′(j′-1)){2(i′-i′(i′-1))-((1-i′)+i′(i′-1))}+(j′(j′-1)2){2(i′(i′-1)2)-(1-i′(i′-1)2)}.
The term ri,j3 provides the inter-row and inter-column permutation for s=3 against row counter i and column counter j. The expression for ri,j3 looks very long and complicated, but eventually, it gives a hardware efficient solution as the terms inside braces are easier to generate through a very small lookup table. The generic form for (6), (10), and (13) to compute the interleaved address Ii,j can be written as(15)Ii,j={j,if(i=0),I(i-1),j+C+ri,js,otherwise.Here parameters distinguishes different modulation schemes. For BPSK/QPSK ri,j1=0, and for 16-QAM and 64-QAM, ri,j2 and ri,j3 are given by (9) and (14), respectively. The hardware realization supporting all modulation schemes is shown in Figure 7(c). It appears to be a much optimized implementation as it involves only two additions, some registers, and a very small lookup table.


## 5.1.1. BPSK-QPSK

AsNBPSC is 1 and 2 for BPSK and QPSK, respectively; thus s=1 for both cases and (2) simplifies to the following form:(3)Jk=(Nd)×(k%d)+⌊kd⌋.Considering the interleaver as a block interleaver, the parameterd is usually considered as total number of columns NCOL, and parameter N/d is taken as total number of rows NROW, but the column and row definition are swapped hereafter. The parameter d is taken as total number of rows and parameter N/d is taken as total number of columns. The functionality still remains the same, with the benefit that it ends up with the recursive expression for all the modulation schemes. According to new definitions, the term (k%d) provides the behavior of row counter and the term ⌊k/d⌋ provides the behavior of column counter. Thus introducing two new variables i and j as two dimensions, such that j increments when i expires, the ranges for i and j are mentioned as follows:
(4)i=0,1,…(d-1),j=0,1,…(Nd-1),
which satisfies against k when i=(k%d) and j=⌊k/d⌋. Defining total number of columns as C=N/d, (3) can be written as(5)Ji,j=C×i+j.The recursive form after handling the exception againsti=0 can be written as(6)Ji,j={j,if(i=0),J(i-1),j+C,otherwise.Defining row counteri as i=Rc and column counter j as j=Cc, the hardware for (6) is shown in Figure 7(a). The case of BPSK and QPSK do not carry any specific inter-row or inter-column permutation pattern; thus it ends up with relatively simple hardware, but it provides the basis for analysis for 16-QAM and 64-QAM cases, which are more complicated.Interleaver address generation for (a) BPSK-QPSK, (b) 16-QAM, and (c) combined for all modulation schemes.
(a)(b)(c)


## 5.1.2.16-QAM

16-QAM scheme has 4 code bits per subcarrier; thus parameters is 2 and (2) becomes(7)Jk=2×⌊Mk2⌋+((Mk+N+⌊d×MkN⌋)%2).Like BPSK/QPSK case, algebraic only steps cannot be used here to proceed due to the presence of floor and modulo functions. Instead, all the possible block sizes for 16-QAM are analyzed to restructure the above equation. The following structure appears to be equivalent to (7) and at the same time resembles the structure of (3); thus it suits well for hardware multiplexing:(8)Jk=(Nd)×(k%d)+⌊kd⌋+rk2.The extra termrk2 is defined by the following expression:(9)rk2=[(1-(k%2))-(k%2)]{1-(⌊kd⌋%2)}+[((k%2)-1)+(k%2)]{⌊kd⌋%2}.This term appears due to the reason that the interleaver for 16-QAM carries specific permutation patterns, making the structure more complicated. Considering the 2-dimensions i and j having range as mentioned in (4), the behavior of the term k%2 is the same as that of i%2, when i is the row counter. Thus (8) can be written in 2D representation as follows:(10)Ji,j={j,if(i=0),J(i-1),j+C+ri,j2,otherwise,
where
(11)ri,j2=[(1-(i%2))-(i%2)]{1-(j%2)}+[(i%2)+(1-(i%2))]{j%2}.The term can further be simplified to a smaller expression but it is easy to realize the hardware from its current form. The modulo terms can be implemented by using the LSB of row counterRc and column counter Cc, and the required sequence can be generated with the help of an XOR gate and an adder as shown in Figure 7(b).


## 5.1.3.64-QAM

The parameters is 3 for 64-QAM; thus (2) becomes(12)Jk=3×⌊Mk3⌋+((Mk+N+⌊d×MkN⌋)%3).The presence of modulo functionx%3 makes it much harder to reach some valid mathematical expression algebraically. Different structures for all possible block sizes for 64-QAM are analyzed and the structure similar to (6) and (10) and equivalent to (12) is given as follows:(13)Ji,j={j,if(i=0),J(i-1),j+C+ri,j3,otherwise,
where i and j represent two dimensions and their range is given by (4). Defining  i′=(i%3) and j′=(j%3), ri,j3 is given as(14)ri,j3=((1-j′)+j′(j′-1)2){2((1-i′)+i′(i′-1)2)-(i′-i′(i′-1)2)}+(j′-j′(j′-1)){2(i′-i′(i′-1))-((1-i′)+i′(i′-1))}+(j′(j′-1)2){2(i′(i′-1)2)-(1-i′(i′-1)2)}.
The term ri,j3 provides the inter-row and inter-column permutation for s=3 against row counter i and column counter j. The expression for ri,j3 looks very long and complicated, but eventually, it gives a hardware efficient solution as the terms inside braces are easier to generate through a very small lookup table. The generic form for (6), (10), and (13) to compute the interleaved address Ii,j can be written as(15)Ii,j={j,if(i=0),I(i-1),j+C+ri,js,otherwise.Here parameters distinguishes different modulation schemes. For BPSK/QPSK ri,j1=0, and for 16-QAM and 64-QAM, ri,j2 and ri,j3 are given by (9) and (14), respectively. The hardware realization supporting all modulation schemes is shown in Figure 7(c). It appears to be a much optimized implementation as it involves only two additions, some registers, and a very small lookup table.


## 5.2. Frequency Interleaving in 802.11n

The transmission in 802.11n can be distributed among four spatial streams as shown in Figure8. The interleaving requires frequency rotation in case more than one spatial streams are being transmitted. The frequency rotation is applied to the output of the second permutation Jk. The expression for frequency rotation for spatial stream iss is given as follows:Figure 8
Use of interleaver in multiple spatial streams (802.11n).(16)Rk=[Jk-{(((iss-1)×2)%3+3⌊iss-13⌋)×NROT×NBPSC(((iss-1)×2)%3+3⌊iss-13⌋)}]%N.HereNROT is the parameter which defines different frequency rotations for 20 MHz and 40 MHz case in 802.11n. The frequency rotation also depends on the index of the spatial stream iss, thus each spatial stream faces different frequency rotations. Defining the rotation term as JROT, that is,(17)JROT={(((iss-1)×2)%3+3⌊iss-13⌋)×NROT×NBPSC(((iss-1)×2)%3+3⌊iss-13⌋)}(((iss-1)×2)%3+3⌊iss-13⌋),we have(18)Rk=(Jk-JROT)%N.The range for the term(Jk-JROT) is not bounded and it can have value greater than 2N; thus direct implementation cannot be low cost. Analyzing the two terms  [Jk%N]  and (-JROT)%N separately, it is observed that the second term provides the starting point for computing the rotation Rk. As the rotation is fixed for a specific spatial stream, thus the starting value rks=(-JROT)%N  also holds for all run time computations. Equation (18) in combination with (10) can be written as(19)Ji,jiss≡Rk=(Ji,j+rks)%N.HereJi,jiss  is the joint address after applying both, spatial interleaving and frequency interleaving against row index i, column index j and spatial stream index iss. A lookup can be used for the starting values for rks against different spatial streams. The rks values for all the cases follow the condition, that is, (rks<N) which depicts that the term (Jk+rks) cannot be larger than 2N. Therefore, the frequency rotation can be computed with a very small hardware as shown in Figure 9.Figure 9
HW for frequency rotation in 802.11n.


## 5.3. Multistream Interleaver Support in 802.11n

The spatial interleaver address generation block shown in Figure7(c) is denoted as Basic Block (BB) and the frequency rotation block as shown in Figure 9 is denoted as Auxiliary Block (AB). Both these blocks combine to form a complete address generation circuit for one spatial stream. In order to provide support for four streams in parallel, one may consider replicating the two blocks four times. However, an optimized solution would be to use 2 basic blocks and 2 auxiliary blocks, still providing support for 4 spatial streams. The hardware block diagram to generate the interleaver addresses for multiple streams in parallel is shown in Figure 10. This hardware supports quick configuration changes thus providing full support to any multitasking environment. If some new combination of modulation schemes is needed to be implemented, which is not supported already, the interfacing processor can do task scheduling for different types of modulation schemes.Figure 10
HW for quad stream interleaver.


## 5.4. Turbo Code Interleaver for HSPA+

The channel coding block in HAPA+ including WCDMA uses turbo coding [37] for forward error correction. 3GPP standard [4] proposes the algorithm for block interleaving in turbo encoding/decoding as mentioned below. Here N is the block size, R is the row size, and C is the column size in bits.(i)
Find appropriate number of rows “R”, prime number “p”, and primitive root “v” for particular block size as given in the standard.(ii)
Col Size:(20)C=p-1,if(N≤R×(p-1)),C=p,if(R×(p-1)<N≤(R×p)),C=p+1,if(R×p<N).(iii)
Construct intra-row permutation sequenceS(j) by(21)S(j)=[v×S(j-1)]%p;j=1,2,…p-2.(iv)
Determine the least prime integer sequenceq(i) for i=1,2,…R-1,by taking q(0)=1,such that g.c.d(q(i),p-1)=1,q(i)>6 and q(i)>q(i-1).(v)
Apply inter-row permutations toq(i) to find r(i):(22)r(i)=T(q(i)).(vi)
Perform the intra-row permutationsUi,j,for i=0,1,…R-1 and  j=0,1,…p-2.If(C=p):Ui,j=S[(j×r(i))mod(p-1)] and Ui,(p-1)=0.If(C=p+1):Ui,j=S[(j×r(i))mod(p-1)],and Ui,(p-1)=0,Ui,p=p,and if (N=R×C) then exchange U(R-1,0) with U(R-1,p).If(C=p-1):Ui,j=S[(j×r(i))mod(p-1)]-1.(vii)
Perform the inter-row permutations.(viii)
Read the address columns wise.The presence of complex functions like modulo computation, intra-row and inter-row permutations, multiplications, finding least prime integers, and computing greatest common divisor makes it in-efficient while implementing it in its original form. Further, to get one interleaving address in each cycle, some preprocessing is also required where parameters like total number of rows or columns, least prime number sequenceq(i), inter-row permutation patterns T(i), intra-row permutations S(j), prime number p, and associated integer v are computed. Some of these parameters can be computed using lookup tables while the others need some close loop or recursive computations. The simplifications considered in the implementation are discussed in the following paragraphs.One of the main hurdles to generate on-the-fly interleaved address is the computation of intra-row permutation sequenceS(j). Before applying the intra-row permutations, the term (j×r(i)%(p-1)) is computed which produces random values due to r(i) and modulo function. These random values appear as index to compute S(j), due to which it may require many clock cycles to be computed on-the-fly. To resolve it, some precomputations are made and results are stored in a memory. These precomputations involve the computation of a modulo function which requires a divider for direct implementation. To avoid the use of divider, indirect computation of modulo function is done by using Interleaved Modulo Multiplication Algorithm [38]. It computes the modulo function in an iterative way requiring more than one clock cycles. Looking at maximum value of v, which is 5 bits, a maximum of 5 iterations are needed to compute one modulo multiplication. The algorithm to compute the Interleaved Modulo Multiplications is shown in Figure 11 and the hardware required is shown in Figure 12. This hardware produces the data for memory while in precomputation phase; however, same hardware is utilized to generate the address for the memory, while in execution phase.  The usage of memory depends on the parameter p and it will be filled upto (p-2) locations.Figure 11
Flow graph for interleaved modulo multiplication algorithm.Figure 12
WCDMA turbo code interleaver hardware.Findingqmod(i)=q(i)%(p-1) instead of direct computation of least prime number sequence q(i) gives the benefit of computing the RAM address recursively and avoiding computation of the modulo function. This idea was introduced in [13] and later on it has been used in [14, 16, 17]. The computation of q(i)%(p-1) can be managed by a subtractor and a look up table, provided that all the values of q(i) placed in the look up table satisfy the condition q(i)<2(p-1). The similarities between different sequences for q(i)%(p-1) for all possible p values are very helpful to improve the efficiency of the lookup table. The parameters p and v are stored in combined fashion in a lookup table of size 52×14b. The lookup table is addressed via a counter. Against each value of p, the condition (p×R≥N-R) is checked using a comparator to find the appropriate value for p and v. Once p is found, the total number of columns C can have only three values, that is, p-1, p, or p+1. Hence C is found in at most three clock cycles by checking the condition (R×C≥N). The recursive function used to compute the RAM address with the help of parameter qmod(i) is given by(23)RA(i,j)={RA(i,j-1)+qmod(i)}%(p-1).The data from RAM are denoted asU(i,j) after passing through some exception handling logic. Parameter U(i,j) provides the intra-row permutation pattern for a particular row. The final interleaved address Ii,j can be found by combining the inter-row permutation with intra-row permutation as follows:(24)Ii,j={C×r(i)}+U(i,j).The complete hardware for interleaver address generation for Turbo Code interleaver is shown in Figure12. It can be mapped to the proposed unified interleaver architecture quite efficiently.


## 5.5. Turbo Code Interleaving in 3GPP-LTE and WiMAX

The newly evolved standard, 3GPP LTE [5], involves interleaving in the channel coding and rate matching section. The interleaving in rate matching is called subblock interleaving and is based on simple block interleaving scheme. The channel coding in LTE involves Turbo Code with an internal interleaver. The type of interleaver here is different and it is based on quadratic permutation polynomial (QPP), which provides very compact representation. The turbo interleaver in LTE is specified by the following quadratic permutation polynomial:(25)I(x)=(f1·x+f2·x2)%N.Herex=0,1,2,…(N-1), with N as block size. This polynomial provides deterministic interleaver behavior for different block sizes and appropriate values of f1 and f2. Direct implementation of the permutation polynomial given in (25) is hardware in-efficient due to multiplications, modulo function, and bit growth problem. To simplify the hardware, (25) can be rewritten for recursive computation as(26)I(x+1)=(I(x)+g(x))%N,
where  g(x)=(f1+f2+2·f2·x)%N. This can also be computed recursively as(27)g(x+1)=(g(x)+2·f2)%N.The two recursive terms mentioned in (26) and (27) are easy to implement in hardware (Figure 13) with the help of a LUT to provide the starting values for g(x) and f2.Figure 13
Simplified HW for 3GPP-LTE and CTC interleaver.WiMAX standard [6] uses convolutional turbo coding (CTC) also termed duo-binary turbo coding. They can offer many advantages like performance, over classical single-binary turbo codes [39]. Parameters to define the interleaver function as described in [6] are designated as P0,P1,P2, and P3. Two steps of interleaving are described as follows.Step 1.
Let the incoming sequence be(28)u0=[(A0,B0),(A1,B1),(A2,B2),…(AN-1,BN-1)];forx=0⋯N-1,if(i%2)=1,then(Ai,Bi)=(Bi,Ai).
The new sequence is(29)u1=[(A0,B0),(B1,A1),(A3,B3),…(BN-1,AN-1)].Step 2.
The functionI(x) provides the address of the couple from the sequence u1 that will be mapped onto address x of the interleaved sequence. I(x) is defined by the set of four expressions with a switch selection as follows:
forx=0⋯N-1
switch(x%4).
case  0:I(x%4=0)=(P0·x+1)%N.
case  1:I(x%4=1)=(P0·x+1+N/2+P1)%N.
case  2:I(x%4=2)=(P0·x+1+P2)%N.
case  3:I(x%4=3)=(P0·x+1+N/2+P3)%N.Combining the four equations provided in step-2, the interleaver functionI(x) becomes(30)I(x)=(βx+Qx)%N,
where βx can be computed using recursion, that is, β(x+1)=(βx+P0)%N by taking  β0=0·Qx is given by(31)Qx={1,if(j%4=0),1+N2+P1,if(j%4=1),1+P2,if(j%4=2),1+N2+P3,if(j%4=3).As range ofβx and Qx is less than N, thus Ix can be computed by using addition and subtraction with compare and select logic as shown in Figure 13.


## 5.6. Convolutional Interleaving in DVB

The convolutional interleaver used in DVB is based on the Forney [40] and Ramsey type III approach [41]. The convolutional interleaver being part of outer coding resides in between RS encoding and convolutional encoding. The convolutional interleaver for DVB consists of 12 branches as shown in Figure 14. Each branch j is composed of first-in-first-out (FIFO) shift registers with depth j×M, where M=17 for DVB. The packet of 204 bytes consisting of one sync byte (0×47or0×B8) is entered into the interleaver in a periodic way. For synchronization purpose the sync bytes are always routed to branch-0 of interleaver.Figure 14
Convolutional interleaver and deinterleaver in DVB.Convolutional interleaving is best suited for real time applications with some added benefits of half the latency and less memory utilization as compared to block interleaving. Recently, convolutional interleavers have been analyzed to work with Turbo codes [42–44], with improved performance, which make them more versatile; thus general and reconfigurable convolutional interleaver architecture integrated with block interleaver functionality can be of significance.Implementation of convolutional interleavers using first-in-first-out (FIFO) register cells is silicon inefficient. To achieve a silicon efficient solution, RAM-based implementation is adopted. The memory partitioning is made in such a way that by applying appropriate read/write addresses in a cyclic way, it exhibits the branch behavior as required by a convolutional interleaver. RAM write and read addresses are generated by the hardware shown in Figure15. The hardware components used here are almost the same as used by interleaver implementation for other standards, thus providing the basis for multiplexing the hardware blocks for reuse. To keep track of next write address for each branch, 11 registers are needed, which provides the idea of using cyclic pointers instead of using FIFO shift registers. For each branch the corresponding write address is provided by the concerned pointer register and next write address (which is also called current read address) is computed by using an addition and a comparison with the branch boundaries. Other reference implementations have used branch boundary tables directly, but to keep the design general, the branch boundaries are computed on-the-fly using an adder and a multiplier in connection with a branch counter.Figure 15
HW for RAM read/write address generation for convolutional interleaver.For implementing a convolutional deinterleaver, the same hardware is used by implementing the branch counter in reverse order (decrementing by 1). In this way, same branch boundaries are used, and the only difference is that the sync byte in the data is now synchronized with the largest branch size as shown in Figure14. Keeping the same branch boundaries for the deinterleaver, the width of the pointer register becomes fixed. This gives an additional benefit that the width of pointer register may be optimized efficiently.


## 6. Integration into Baseband System

The multimode interleaver architecture can perform interleaving or deinterleaving for various communication systems. It is targeted to be used as an accelerator core with a programmable baseband processor. The usage of the multimode interleaver core completely depends on the capability of the baseband processor. For lower throughput requirements only a single core can be utilized with baseband processor and the operations are performed sequentially. However, as a matter of fact, usual system level implementations require interleaver at multiple stages. Number of stages can be up to three, for example, WCDMA (turbo code interleaving, 1st interleaving, and 2nd interleaving). A fully parallel implementation can be realized by using three instances of the proposed multimode interleaver core, but in order to optimize the hardware cost a wise usage would be to use two instances hooked up with the main bus of the processor as shown in Figure16. In this way the interleaving stages can be categorized as channel interleaving and coding/decoding interleaving. Further optimizations can be made in the two cores to fit in the particular requirements, for example, one interleaver core dedicated for coding/decoding and the second core dedicated for channel interleaving. By doing so the reduction of silicon cost associated with address generation is not significant, however, memory sizes can be optimized as per the targeted implementations, which can reduce the silicon cost significantly. For current implementation of multimode interleaver, the input memory used for any kind of decoding is considered to be the part of baseband processor data memory. In this way the extra memory inside interleaver core can be avoided which might be redundant in many cases. However, the integration of input memory in the main decoding operation is facilitated by the interleaver core by providing the address for input memory. In this way the interleaved/deinterleaved data can be fed to the decoder block in synchronized manner.Figure 16
Integration of interleaver core with baseband processor.Although the main focus is to support the targeted standards, however, programmability of the processor may target some different types of interleaver implementation which is not directly supported by this core. To make it still usable, support for some indirect implementation of any block interleaver with or without having row or column permutations is also provided. In this case the interleaver core is configured to implement a general interleaver with external permutation patterns. The permutation patterns are computed inside baseband processor using its programmability feature and loaded in a couple of the interleaver memories during precomputation phase. Excluding these memories, a restriction on maximum block size (i.e., 4096) will be imposed in this case. This type of approach is adopted by all commercially available interleaver implementations like Xilinx [28], Altera [29], and Lattice Semiconductor [30]. The computation of interleaver permutations on processor side and loading them into memory can impose more computation and time overheads on the processor side. Another drawback is that it does not support fast switching between different interleaver implementations. A real multimode processor may require fast transition from one standard to another; therefore, it is not a perfect choice for a real multimode environment. However, it is supported by the proposed multimode interleaver core for the completeness of the design.


## 7. Implementation Results

The reconfigurable hardware interleaver design shown in Figure4 provides the complete solution for multimode radio baseband processing. The wide range of standard support is the key benefit associated with it. The RTL code for the reconfigurable interleaver design was written in Verilog HDL and the correctness of the design was verified by testing for maximum possible cases. Targeting the use of interleaver core with a multimode baseband processor, one of the important parameters to be investigated is precomputation cycle cost. A lower precomputation cycle cost is beneficial for fast switching between different standards. Table 3 shows the worst case cycle cost during precomputation for different interleavers. It is observed that the cycle cost in WCDMA is higher for some block sizes, but still it works fine, as it is less than the frame size and it can be easily hidden behind the first SISO decoding by the turbo decoder. The worst case precomputation cycle cost for other interleaver implementations is not very high. Therefore, the design supports fast switching among different standards and hence it is very much suitable for a multimode environment.Table 3
Precomputation cycle cost for different standards.
StandardWorst case precomputation cycle cost802.11 a/b/g—WLAN Channel interleaver20802.16e—WiMAX Channel interleaver983GPP—WCDMA Block turbo code (Depends on Block size “N”)15 for (N=40)23 for (N=41)802 for (N=5040)563 for (N=5114)ETSI EN 300-744—DVB Inner symbol interleaver15802.11n—Extended WLAN38General purpose useDepends on external HW, that is, loading the permutationsAll othersLess than 3The multimode interleaver design was implemented in 65 nm standard CMOS technology and it consumes0.126mm2 area. The chip layout is shown in Figure 17 and the summary of the implementation results is provided in Table 4. The design can run at a frequency of 166 MHz and consumes 11.7 mW power in total. Therefore, having 4-bit parallel processing for four spatial streams (e.g., 802.11n) maximum throughput can reach up to 664 Mbps. However, this throughput is limited to 166 Mbps for single stream communication systems. Table 5provides the comparison of the proposed design to others in terms of standard coverage, silicon cost, and power consumption. The reference implementations have lower standard coverage as compared to the proposed design. Though more silicon is needed for more standard coverage, our solution still provides a good trade-off with an acceptable silicon cost and power consumption.Table 4
Summary of implementation results.
ParameterValueTarget technology65 nmMemory configuration2048×6b×4; 1024×6b×4Total memory72 KbitMemory area97972μm2Memory power consumption10.5 mWLogic area28436μm2Total area0.126mm2Clock rate166 MHzThroughput (Max)664 MbpsTotal power consumption11.7 mWTable 5
HW comparison with other implementations.
ImplementationStandard coverageTechnologyOperating frequencyPowerMemory sizeTotal core sizeXilinx [28] Virtex-5General purpose (commercial use)FPGA262/360 MHz Speed Grade-1/-3—18 Kbits210 LUTs + MemoryAltera [29] FLEX-10KEGeneral purpose (commercial use)FPGA120 MHz—16 Kbits392 LEs + MemoryLattice [30] ispXPGAGeneral purpose (commercial use)FPGA132 MHz—36 Kbits284 LUTs + MemoryShin and Park [13]WCDMA turbo code; cdma20000.25μm——35 Kbits2.678mm2Asghar et al. [18]WCDMA, LTE, WiMAX and DVB-SH Turbo Code Interleaver Only65 nm200 MHz10.04 mW30 Kbits0.084mm2Chang and Ding [23]WiMAX, WLAN, DVB0.18μm100 MHz—12 Kbits0.60mm2Chang [24]WiMAX, WLAN, DVB0.18μm150 MHz—12 Kbits0.484mm2Wu et al. [25]WiMAX, WLAN, 802.11n0.18μm200 MHz—32 Kbits0.72mm2Asghar and Liu [26]WiMAX, WLAN, DVB0.12μm140 MHz3.5 mW12 Kbits0.18mm2Asghar and Liu [27]WiMAX, WLAN, 802.11n65 nm225 MHz4 mW15.6 Kbits0.035mm2Horvath et al. [20]DVB bit and symbol interleaver0.6μm36.57 MHz300 mW48 Kbits69mm2Chang [21]DVB bit and symbol interleaver0.35μm——52.2 Kbits2.9mm2This workAll range including WLAN, WiMAX, DVB, HSPA+, LTE, 802.11n and General purpose implementation65 nm166 MHz11.7 mW72 Kbits0.126mm2Figure 17
Layout of proposed multimode interleaver.


## 8. Conclusion

This paper presents a flexible and reconfigurable interleaver architecture for multimode communication environment. The presented architecture supports a number of standards including WLAN, WiMAX, HSPA+, 3GPP-LTE, and DVB, thus providing coverage for maximum range. To meet the design challenges, the algorithmic level simplifications like 2D transformation of interleaver functions and recursive computation for different implementations are used. The major focus has been to compute the permutation patterns on-the-fly with flexibility. Architecture level results have shown that the design provides a good tradeoff in term of silicon cost and reconfigurability when comparing with other reference designs with less standard coverage. As compared to individual implementations for different standards, the proposed unified address generation offers a reduction of silicon by a factor of three. Finally, the basic requirement of a multimode processor platform, that is, fast switching between different standards has been met with minimal precomputation cycle cost. It enables the processor to use the interleaver core for one standard at some time and use it for another standard in the next time slot by just changing the configuration vector and small preprocessing overheads.



---

*Source: 793807-2010-02-02.xml*