Abstract: In wireless communication, the interleavers are referred as the core component for many multiple access schemes e.g., IDMA, CDMA etc. In CDMA systems, interleavers are mainly employed for providing the coding gain to signal while in IDMA systems, user-specific interleavers are used for the purpose of user separation. For implementation of the interleavers in IDMA, the challenge is to fabricate them at affordable decoding complexity with available technology. In this study, we first introduce various orthogonal and non-orthogonal interleavers user in IDMA scheme. Then, we perform comparison on their performance and implementation complexity. Here we are dealing with suitable interleavers only which are used as the only means of user separation in IDMA scheme. Tree based interleaver turned out to be the best compromise between performance and complexity. Next, we implement interleavers on VHDL as the design and simulation entry.
INTRODUCTION
In recent years, the Interleave Division Multiple Access (IDMA) has become the area of interest to researchers in wireless communication. In Interleave Division Multiple Access (IDMA), users are assigned with specific interleavers (Liu et al., 2003) instead of PN-sequences as in case of Code Division Multiple Access (CDMA) systems to differentiate amongst users. An interleaver-based multiple access scheme gives high spectral efficiency, improved performance and low receiver complexity (Eason et al., 1955; Ping et al., 2002). IDMA scheme shows an interleaver as the only means to distinguish the signals amongst users, and hence called as Interleave-division multiple-access (IDMA). IDMA inherits many advantages from CDMA like, diversity against fading and mitigation of the worst-case other-cell user interference problem.
Interleaving is a permutation rule that scrambles data to break up neighborhood-relations. In CDMA, interleaving is used as one of the most popular ways to correct burst errors. Suitable Interleavers must inherit properties such as easy implementation with lower complexity and minimum number of collisions among them. Minimum collision is important in orthogonal interleavers because they are used for user separation in IDMA scheme.
ORTHOGONALITY OF INTERLEAVERS
Orthogonality is an important factor in generating the interleavers for IDMA scheme. In case of interleavers, the correlation between them increases with increment in user count and consequently BER degrades. So, according to the orthogonality criteria, the generated interleavers have minimum number of collisions among them.
Two interleavers πi and πj (where πi ≠πj) are said to be orthogonal, if for any two words, we have (Pupeza et al., 2006):
Above condition is for the orthogonality check of the interleavers.
INTERLEAVING MECHANISM AND INTERLEAVERS
Interleavers are the key component in designing of IDMA systems. The interleavers assigned to the users should be efficient and least complex. They are trusted to be under state of non-collision with each other as well must be easy to implement. The implementation complexity is a serious concern in terms of not only propagation delay as well in terms of increased power dissipation in the device. The interleavers taken for study are random interleaver (Liu et al., 2003), master random interleaver (Caire et al., 2004) and tree based interleaver (Wu et al., 2006). These interleavers are state of art interleavers suitable of IDMA systems.
Figure 1 shows the random scrambling of data for a given sequence of data. The input data is interleaved randomly at transmitter while de-interleaved at receiver. Hence, the data is arranged in its original sequence.
Random interleaver: Random interleavers scramble the data of different users with different pattern. Patterns of interleaving of data for the users are generated randomly. Due to the interleaving of data, burst errors of the channel are randomized at the receiver side and can be easily detected and corrected (Pupeza et al., 2006). However, this interleaver is termed as non-orthogonal interleaver because, it has minimum cross-correlation amongst the respective interleavers but the value of cross-correlation never reaches to zero.
For proper decoding of the sequence of interleaver, the receiver must have all the relevant information regarding pattern of interleaving at transmitter side. Therefore, in order to operate IDMA scheme properly, base station has to forward the information of interleaving at the receiver side of the system.
The block diagram of random interleaver is shown in Fig. 2. All the first MUX’s are initialized with zero. Random Incrementor 1 is initially used to generate a random number which is used for first swapping position in First Swapping Position MUX Bank (FSPMB). Random Incrementor 2 will increment the output of FSPMB which will generate corresponding second swapping position to be stored in Second Swapping Position MUX Bank (SSPMB). Temporary register and MUX bank stores above two have given position which has to be interchanged. First and second swapping positions are compared with the already utilized swapped positions in order to avoid their repetition.
| Fig. 1: | Random interleaving of data |
| Fig. 2: | Block diagram of random interleaver |
Modulus counting block is used to ensure that generated positions will not exceed from total bit numbers. Temporary register gives the positions to the swapper bank which finally will swap the content of that memory location. After swapping all the data of current user, the comparator will inhibit the USER DATA block and will increment the user count and FSPMB and SSPMB are reset for the next user. Swapper bank will give the interleaved data of users and temporary register will give the position that is interchanged. Therefore, Random Position Setter (RPS) block outputs only the random positions that have to be interchanged which are used in further processing of the data.
Master random interleaver or power interleaver: The limitation associated with random interleavers is that the Base Station (BS) has to use a considerable amount of memory to store these interleavers, causing serious concern in case of large number of users. Also, during the initial link setting-up phase, there should be messages passing between the BS and Mobile Stations (MSs) to inform each other about their interleavers. Extra bandwidth resource will be consumed for this purpose if the interleavers used by the BS and MSs are long and randomly generated. So to overcome these problem master random interleavers are proposed (Caire et al., 2004). This is also a non-orthogonal interleaver.
In master random interleaver or ‘power-interleaver’ method, a master interleaver Φ is assigned. Then K interleavers can be generated using πk = Φk. Here, Φk(c) is defined as Φ1(c) = Φ(c), Φ2(c) = Φ(Φ(c)), Φ3(c) = Φ(Φ(Φ(c))), etc. By this convention, every interleaver is a ‘power’ of Ö. The rationale for this method is that if Φ is an ‘ideal’ random permutation, so are all {Φk} and these permutations are also approximately independent to each other.
| Fig. 3: | FPGA implemented diagram of master random interleaver |
Based on this method, we simply assume that the BS assigns the power index k to each user k, and then Φk will be generated at the MS for user k accordingly. This method of generation increases the performance in the term information that has to be sending by the base station to the mobile station.
In Fig. 3, Random Position Setter (RPS) block will functions in similar way as in case of random interleaver. In master random interleaver, these random positions are given to the swapper bank for interchange the data of current user. All other users are interleaved by the looping of first generated random sequence due to presence of only one master random interleaver sequence. Temporary register will store the generated positions which have to be swapped. This temporary register will disable the RPS block, after reception of swapping positions for data. The temporary register will provide these swapping positions to the Loop Count with User (LCU) block. The LCU block loops the position corresponding to the user count. Finally, according to generated positions in LCU block according to user count, the swapper bank will swap the positions.
Tree based interleaver: The Tree Based Interleaver is basically aimed to minimize the computational complexity and memory requirement that occurs in master random interleavers and random interleavers respectively. This interleaver is orthogonal interleaver.
In a Tree Based Interleaver generation (Shukla et al., 2008, 2009), two randomly generated interleavers are chosen, let Π1 and Π2 is the 2 random interleavers. The combinations of these two interleavers in a particular fashion as shown in the Fig. 4 are used as interleaving masks for the users.
The allocations of the interleaving masks follow the binary tree format. The interleaving masking diagram is shown upon 14 users for simplicity. It is clearly shown through the figure that, for obtaining the interleaving sequence of the 14th user, it needs only 2 cycles of clock, as:
If the power interleaver generation method is used the no. of cycles needed is 13 cycles, if the intermediate variables are not stored. The memory required by the Tree Based Interleaver generation method is only slot more than that required for power interleaver generation method.
In Fig. 5, there are two master sequences so we have to generate two random position sequences for two users all other users are interleaved according to these sequences. Random Position Setter (RPS) block 1 will generate the first sequence and Random Position Setter (RPS) block 2 will provide the second sequence.
| Fig. 4: | Tree based interleaver |
| Fig. 5: | FPGA implemented diagram of tree based interleaver |
The LCU block will receive the positions from temporary register trough RPS block. The LCU block loops the master sequences according to the user number. These loop count with user block will give the positions that has to be interchanged to the swapper bank.
COMPARISON
All the interleavers have been simulated in Xilinx platform for the comparison of their hardware and time constraints. The comparison has been done for 8 users with data of 8 bits/chip.
Summary of hardware: In this part we are comparing digital hardware needed to assemble the interleavers. The efficient interleaver will require least hardware and timing for signal to get propagated to output.
According to Table 1, it is evident that tree based interleaver have least requirement of hardware among all these interleavers.
| Table 1: | Digital hardware comparison of interleavers |
| Table 2: | Port and space comparison of interleavers |
| Table 3: | Timing comparison of interleavers |
Master random requires more hardware due to dependency of hardware-complexity on user count, and requirement of large number of temporary variables required to store the intermediate data.
Device utilization: In this comparison, we are going to show the requirement of bulk devices such as number of slices, number of four inputs LUT’s, number of inputs/ outputs are required to build these interleavers (Table 2). Tree based interleaver has the least requirement of above components to get built and master random interleaver requires the highest number of components in building for the same reason explained earlier.
Timing summary: In this comparison the timing requirements of the interleavers are compared for proper operation of interleavers. In Table 3, the maximum frequency of operation indicates the maximum frequency of the interleavers at it can operate satisfactorily. Minimum input signal arrival time before clock is a vital component for proper propagation of signal. These factors in combination show the timing behavior of these interleavers.
From Table 3, it is evident that tree based interleaver can be operated at maximum frequency with minimum time period requirement it needs least timing for input signal arrival time before clock. Therefore, tree based interleaver has the best timing behavior among all the interleavers and master random interleavers require the largest time for proper operation.
SIMULATION RESULTS
The memory required by the tree based interleaver generation method is only slightly more than that required for master random interleaver generation method (Caire et al., 2004) as shown in Fig. 6. The simulation has been performed for 16 bits of spread length and data length of 256 bits/user. The memory requirement is for all the interleavers are shown below:
| • | Memory required for Random Interleaver = n*cl*log2 (cl) |
| • | Memory required for Master Random Interleaver = cl*log2 (cl) |
| • | Memory required for Tree Based Interleaver = 2* cl*log2 (cl) |
| • | Where cl is chip length |
| Fig. 6: | Simulation results of tree based, random and master random interleaver with respect to memory requirement |
| Fig. 7: | Simulation results of tree based, random and master random interleaver with respect to computational complexity |
The computational complexity for all the interleavers is also compared. Here, the computational complexity of interleaver refers to the number of interleavings per user. The Tree Based Interleaving scheme is extremely efficient for reduction of computational complexity as compared to that in Master Random Interleaving scheme (Ping et al., 2002) as shown in Fig. 7.
For Tree Based Interleaver:
| = | ceil (log2 (i)) | |
| Ceil(x) rounds the elements of x towards infinity. | ||
For Master Random Interleaver:
| = | (i-1) |
where, i is user number.
| Fig. 8: | Simulation results of random, master random, and tree based interleaver |
| Fig. 9: | Comparison of uncoded IDMA systems in single path AWGN channels, using both random and TBI with different no. of users. |
The bit error rate performance of random interleaver, master random interleaver, and tree based interleaver is performed with various constraints. For simplicity, IDMA system with BPSK signaling in single path AWGN channel is assumed with uniform repetitive coding and spread length sl = 16, for all users along with 15 iterations. From Fig. 8, it is evident that the BER performance of tree based interleaver is almost same as that of other interleavers.
In Fig. 9, uncoded IDMA cases are considered, i.e., without any forward error correction coding. The data length is 256 bits is used, for an uncoded system. In Fig. 10, memory-2 rate-1/2 convolutional code is used. The data length used in the coded system is 64.
| Fig. 10: | Comparison of coded IDMA systems in single path AWGN channels, using both random and TBI with various user counts |
From Fig. 9 and 10, the performances of both kinds of interleavers are almost the same, which means that the proposed Tree Based Interleaver can replace the random interleavers.
CONCLUSION
As we discussed, interleavers numerous applications in many fields and interleavers are the basic component for an IDMA system. Here we have compared different designing and timing aspects of interleavers so that a better can be chosen among all. Tree based interleaver has least hardware requirement to build and it has faster operating. In designing the number of looping affect the behavior of interleavers greatly because if large number of loops is in the interleaver operation, it requires large number of temporary variables to store intermediate data. Master random interleaver requires large number of registers, flip flops and all components because of looping, as the number of users increases the number of loops increases proportionally. So according to our work and platform tree based interleaver have best performance.