Int'l J. of Communications, Network and System Sciences
Vol.3 No.1(2010), Article ID:1181,4 pages DOI:10.4236/ijcns.2010.31014

IDMA Based on Deterministic Interleavers

Shu-Ming TSENG

Department of Electronic Engineering, National Taipei University of Technology, Taiwan, China


Received October 8, 2009; revised November 9, 2009; accepted December 21, 2009

Keywords: Chip-Level Interleaver, Deterministic, IDMA, Turbo Code


Previously, the interleavers is generated randomly for users of Interleave Division Multiple Access (IDMA) systems. Therefore, transmitting the entire chip-level interleaver matrix or power interleaver generation is required, which either adds redundancy or increases delay. In this paper, we propose to use deterministic chip-level interleavers for multiple users of IDMA systems. These chip-level interleavers are modified from single-user symbol-level interleavers for turbo codes. The receiver can generate the chip-level interleavers for user k automatically without the redundancy of transmitting the entire interleaver matrix or the delay of generating power interleavers. Simulation results show that the proposed deterministic–interleaver-based IDMA performance is better than Gold-code-based CDMA in the multipath environment.

1. Introduction

The performance of the Code Division Multiple Access (CDMA) system is mainly limited by Multiple Access Interference (MAI), Inspired by popular turbo principle, the iterative decoding and the symbol-by-symbol soft interference cancellation/MMSE instantaneous filter Multi-User Detection (MUD) scheme that in [1] helps to mitigates MAI significantly in CDMA systems.

Recently, an attractive multiple access system was proposed, so called Interleave Division Multiple Access (IDMA) [2,3]. In IDMA systems, each user has the same spreading sequence but different chip-level interleavers. The MUD of IDMA only applies soft interference cancellation without MMSE instantaneous filter and is achieved by chip-by-chip (CBC) estimation algorithm. The computational complexity of the IDMA receiver is significantly less than that of the CDMA one because the IDMA receiver does not need MMSE instantaneous filter with complexity O(K2), where K is the number of users.

From a point of view, IDMA is a special form of CDMA. IDMA uses the same spreading sequences {+1,-1,+1,-1,+1,-1,…} for different users and different chip-level interleavers (its depth is larger than data symbol interval) for different users. The net effect is that the IDMA is like the long code CDMA. Note that IDMA’s composite spreading sequence ({+1,-1,+1,-1,+1,-1,…}+ user-specific chip-level interleaver) is more random than CDMA’s, such that long code CDMA need additional scrambling (adding randomness) to have similar bit error probability performance to IDMA [4].

However, all previous schemes for IDMA uses randomly generated interleaverd to separate different users, thus the entire interleaving matrix has to be transmitted to the receiver which may seen to be infeasible and costly for implementation. A user-specific interleaver [5] was proposed for IDMA system, which use a master interleaver φ(c) for user 1 and “power interleaver generation” for user k=2,3,…. For example, is for user 3. However, this master interleaver is still randomly generated and the users with higher user index k would have higher time delay to generation their interleavers.

In this paper, we propose the use of the deterministic chip-level interleaver, which is modified from deterministic symbol-level interleaver for single-user turbocoded systems [6]. We don’t need to transmit the entire interleaver matrix, neither we use power interleaver generation. The receiver will automatically generate the interleaver based on the user index k. Because the systems with random and deterministic spreading sequences may have different bit error probability performance, so we also conduct the simulation to compare deterministic interleaver based IDMA systems and Gold-code-based CDMA systems.

The rest of this paper is presented as follows. Section 2 presents the system model. Then the proposed deterministic interleaver is described in Section 3. The BER performance comparison in multipath fading is presented in Section 4, and we conclude this paper in Section 5.

Figure 1. The transmitter model for user k.

Figure 2. The multipath channel model, where Dc is the number of paths.

Figure 3. The receiver model for user k. The multiuser detector and channel decoder exchange extrinsic information using the turbo principle.

2. System Model

The transmitter model is shown in Figure 1. bk [n] is the information bit of user k, k=1,…,K, where K is the number of users. is the output of the convolutional encoder, and is spread by the spreading sequences {+1,-1,+1,-1,…,+1,-1} for all k (same for each user) to form, then the interleaver (different for different users) permutes to form. Then is modulated into BPSK symbol, which is transmitted through the channel.

The channel model is shown in Figure 2., where j is the chip index. The channel is of dimension. Then the received signal vector can be represented as


where is the AWGN with zero mean and variance, Dc and Tc are the number of paths and chip duration, respectively.

Previous IDMA papers [2,3] didn’t write IDMA system model in the matrix form, so it is hard to see IDMA is a special form of CDMA Thus we use the matrix form in [4] for the proposed IDMA system.

Define the symbol vector

of dimension K( 2Dc – 1), and the

channel matrix as

Then the dimension Dc received signal vector is given by

Figure 4. BER of four-user IDMA and CDMA systems in three-path Rayleigh fading channels, iteration=3.

And can be expressed as follows

, (2)


The receiver is shown in Figure 3. the multiuser detector and dcoder blocks in Figure 3. use turbo principle to exchange log likelihood ratio (LLR) values between each other, the extrinsic LLR calculated by multiuser detector is as follows:

, (3)

where the index is the path, k is the user index, and the path diversity can be seen by this equation above.

Then we pass the extrinsic LLR to the decoder to calculate extrinsic LLR and fed back to multiuser detector iteratively, and the decoder makes hard decision at the last iteration, and the details of above algorithms were refer to [4].

3. Proposed Deterministic Interleaver

We propose to use the deterministic interleavers in [6] into our IDMA system. It is originally designed for single-user turbo coded systems. Our modification is that k in [6] is now 2k-1 in (4) such that k is the user index in IDMA system and 2k-1 is an odd integer as required. The deterministic interleaver for user k is generated as follows:

Step1: set = 0.



where N is the interleaver size. Then we have index sequence D=(c0,c1,…).

Step3: the index mapping function d is given by circularly right shift the index sequence D:

That is, the last element must be mapped back to the first element.

Step 4: maps D into d as the interleaver index D’.


Step1: =0.

Step2: D =

Step3: d = (4,0,1,3,6,2,7,5).

Step4: D’ = (1,3,7,6,0,4,2,5).

The 0-th element of D is 0 and the 0-the element of d is 4, so 0 is the 4-th element of D’.

4. Simulation results

In the section, we present the simulated bit error probability of deterministic interleaver based IDMA in multipath Rayleigh fading channels. Blocks of 32 information bits are encoded by the rate 1/2, memory 2 convolutional code with generator polynomial [5,7], the trellis for this convolutional encoder is terminated by 2 zero bits to return to all zero states. So each codeword has 68 coded bits. For deterministic interleaver based IDMA the coded bits are then spreaded by the length 8 spreading sequence which is the same for every user. Therefore, the interleaver size of each πk is bits. The spreading sequence for CDMA is length 7 Gold codes that used in [1] for K=4 and the interleaver for CDMA is generated randomly and independently for each user. The simulation parameters for random interleaver based IDMA and random sequence CDMA are the same as deterministic interleaver based IDMA and Gold code CDMA, respectively, except that the interleavers and spreading sequences are generated randomly and independently.

Figure 4. shows that the BER performance of deterministic interleaver based IDMA and random interleaver based IDMA and Gold code CDMA in three-path Rayleigh fading channel. We can see that the proposed IDMA systems based on deterministic interleavers significantly outperforms CDMA systems.

5. Conclusions

The proposed deterministic interleaver can be easily generated for each IDMA user. Because user-specific interleaver is not generated randomly, so we don’t need to transmit large amount of interleaver matrix to the receiver side. We don’t waste time to generation the interleaver for user k by k-th power of the interleaver for user 1. This way is more feasible and cost less for implementation. The proposed scheme has lower bit error rate than CDMA systems with random or Gold spreading sequences.

6. Acknowledgment

This work was presented in part in 14th Asia-Pacific Conference on Communications (APCC2008), Tokyo, Japan, Oct. 14-16, 2008. This work was supported in part by National Science Council, Taiwan, under Grant NSC 96-2221-E-027-003, and also National Taipei University of Technology, Taiwan, under Grant NTUT 98-140-05.

7. References

[1]       X. Wang and H. V. Poor, “Iterative (turbo) soft interference cancellation and decoding for coded CDMA,” IEEE Transactions on Communication, Vol. 47, pp.1046–1061, July 1999.

[2]       L. Ping, L. Liu, and W. K. Leung, “A simple approach to near-optimal multiuser detection: Interleave-division multiple-access,” in Proceedings IEEE Wireless Communications and Networking Conference (WCNC2003), Vol. 1, pp. 391–396, March 2003.

[3]       L. Ping, L. Liu, K. Y. Wu, and W. K. Leung, “Interleave-division multiple-access,” IEEE Transacitons on Wireless Communication, Vol. 5, No. 4, pp. 938–947, April 2006.

[4]       K. Katsutoshi and B. Gerhard, “CDMA and IDMA: Iterative multiuser detections for near-far asynchronous communications,” in Proceedings IEEE 16th International Symposium on Personal, Indoor and Moobile Radio Communications, Vol. 1, pp. 426–431, September 11–14, 2005.

[5]       H. Wu, L. Ping, and A. Perotti, “User-specific chip-level interleavaer design for IDMA systems,” Electronics Papers, Vol. 42, No. 4, pp. 233–234, February 16, 2006

[6]       O. Y. Takeshita and D. J. Costello, “New deterministic interleaver designs for turbo codes,” IEEE Transactions on  Information Theory, Vol. 46, No. 6, pp. 1988–2006, September 2000.