Reduction of Complexity in DS-CDMA Using PPIC
J.RAVINDRABABU
1
, K.SRI KRISHNA
1
, K.SATYA NARAYANA SWAMI
1
, B.KAVYA SRI
1
,
G MADHURI
1
, J.V. RAVI TEJA
2
, J.V.RAVI CHANDRA
3
1
E.C.E Department, P.V.P. Siddhartha Institute of Technology, Vijayawada,
Andhra Pradesh, INDIA
2
Software Engineer-1, FactSet Systems Pvt.Ltd, Hyderabad, Andhra Pradesh, INDIA
3
C.S.E Department, V.R. Siddhartha Engineering College, Vijayawada, Andhra Pradesh, INDIA
Abstract— Reduction of MAI to improve system capacity without increasing computational
Complexity is the motivation to do this work. The objective of this paper is to develop an efficient
multiuser detection algorithms that reduce the computational complexity in DS-CDMA system. The
BER performance of the multistage multiuser detection schemes using Kasami spreading sequences
and MMSE detector is found to be better than that of a conventional Matched Filter detector in a
single stage multiuser detection schemes but the Computational Complexity is increasing with the
number of stages and the number of users. The BER performance of the multistage multiuser PIC
detection scheme is found to be better than that of a single stage multiuser PPIC detection scheme but
at the cost of computational complexity increasing with number of stages and users.
Keywords— Multiuser Detection, MAI, PIC, PPIC, Complexity.
Received: March 27, 2024. Revised: September 11, 2024. Accepted: November 12, 2024. Published: December 17, 2024.
1. Introduction
As limited bandwidth is allocated for
various wireless services and as many users as
possible are required to be accommodated and
which has to be achieved by effectively sharing
the allotted bandwidth, multiple access
techniques need to be used in the field of
communications for a minimum degradation in
the system performance [1-4]. Since the
spectrum utilization in Frequency Division
Multiple Access (FDMA) is not efficient and
exact synchronization is needed in Time
Division Multiple Access (TDMA), one has to
go in for a Code Division Multiple Access
(CDMA) technique. In this users can occupy
the entire channel at all the times unlike in
FDMA and TDMA and the users are recognized
by their a-priori codes assigned uniquely. The
users can be recognized at the receiver by using
a correlator treating the remaining users signal
energies as noise. The CDMA has more spectral
efficiency and user capacity when compared to
FDMA and TDMA. CDMA uses a "spread
spectrum" technology where in a large
bandwidth spreading signal multiplies the
narrowband message signal and the users are
differentiated by their unique codes [5-10].
In a perfect synchronous DS-CDMA
transmission, the spreading codes retain their
orthogonality where as in the asynchronous
case they exhibit non zero off peak auto-
correlation and cross-correlation values. But a
perfect synchronous DS-CDMA system may
not possible to realize in practice and thus
suffers from MAI as well as from near-far
effects [11-15].
In a mobile environment MAI can exist
in a single user conventional detection at the
receiver even though mutually orthogonal codes
are employed for all the users at the transmitter
end. The single user conventional detector can
also suffer from near-far effect in practice. The
received signal contains the desired signal,
thermal noise and the MAI. In a single user
conventional detector the signal from each user
at the receiver end is demodulated independent
of other users where in MAI is treated as
additional noise adding to thermal noise and
hence limiting the system capacity [16-18].
In multiuser detection scheme, the
received signals from all the users with the
presence of MAI is demodulated
simultaneously and hence also known as joint
detection. The receiver has a priori knowledge
of the spreading codes of each user and MAI is
not treated as additional noise in multiuser
DESIGN, CONSTRUCTION, MAINTENANCE
DOI: 10.37394/232022.2024.4.21
J. Ravindrababu, K. Sri Krishna, K. Satya Narayana Swami,
B. Kavya Sri, G. Madhuri, J. V. Ravi Teja,
J. V. Ravi Chandra
E-ISSN: 2732-9984
201
Volume 4, 2024
detection. When optimum MUD systems are
used no power control is required but the
computational complexity increases. Hence,
sub-optimum approaches are being sought [19-
21].
2. Literature Review
Dhammika et al [5] present the optimum
symbol based multi user detector to reduce the
interference where in each user has to utilize
two or more receiving antennas. But the
computational complexity also increases.
Zhao Zhijin et al [6] have presented a
discrete shuffled frog leaping algorithm to
reduce the computational complexity in the
optimal multiuser detector and hence improve
the detection performance in a single stage.
Daniele Angelosante et al [17] have
presented a Sphere Detection (SD) algorithm, it
shows that computational burden can be
drastically reduced, with little or no loss of
performance, by applying a suitable version of
the sphere detection (SD) algorithm.
Linglong Dai, et al [18] proposed the
Gauss–Seidel (GS) method to iteratively realize
the MMSE algorithm without the complicated
matrix inversion.
Yang Du, et al [19] propose a novel
low-complexity detector based on an edge
selection approach, which remarkably reduces
the computational complexity.
Yinman Lee, et al [20] a low-complexity
hybrid analog-digital signal detector for uplink
multiuser massive multiple-input multiple-
output (MIMO) systems. Specially, both the
hardware cost and computation load can be
reduced.
Rong Ran and Hayoung Oh [21] Sparse-
aware (SA) detectors have attracted a lot
attention due to its significant performance and
low-complexity, in particular for large-scale
multiple-input multiple-output (MIMO)
systems. Similar to the conventional multiuser
detectors, the nonlinear or compressive sensing
based SA detectors provide the better
performance but are not appropriate for the over
determined multiuser MIMO systems in sense
of power and time consumption. The linear SA
detector provides a more elegant tradeoff
between performance and complexity compared
to the nonlinear ones.
After the review of the existing relevant
literature, the following observations are being
made:
i. The overall BER performance
among all the multi-user detectors
was found better in maximum
likelihood detector/the optimum
detector at the cost of very high
computational complexity and thus
not realistic for implementation.
ii. Reduced computational complexity
exists in decorrelating detectors and
MMSE detectors. But in these linear
detectors, the calculation of the
inverse cross-correlation matrix is
difficult.
iii. The computational complexity
increases linearly with the number of
users in SIC, PIC, HIC and PPIC
techniques. Each type of interference
cancellation detectors has its own
level of complexity, processing time
and BER performance.
In view of the above observations, there exists a
need to make studies to enhance visual DS-
CDMA system performance and reduce the
difficulty of computing. Further, interference
cancellation methods other than the existing
ones are to be explored for DS-CDMA systems.
The CDMA signal and channel model
are covered in the following chapter. Standard
single-user and multiuser detection methods are
covered in Section 3. The fourth section
describes multiple phases of detection
techniques and noise. Simulation results on the
performance comparison of several multistage
multiuser identification approaches are
presented in Section 5. An overview of the
results is provided within Chapter 6's results.
3. Multiuser Detection Techniques
3.1 Multiuser PIC with MMSE Detector
Data bit estimation and interference
cancellation need to be done for each user at
every stage in multistage PIC schemes. The
DESIGN, CONSTRUCTION, MAINTENANCE
DOI: 10.37394/232022.2024.4.21
J. Ravindrababu, K. Sri Krishna, K. Satya Narayana Swami,
B. Kavya Sri, G. Madhuri, J. V. Ravi Teja,
J. V. Ravi Chandra
E-ISSN: 2732-9984
202
MMSE detector estimates data bits and
subtracts interference from the first stage on
wards in this Multistage Multiuser PIC scheme
[14-16]. The Multistage Multiuser PIC with
MMSE Detector is shown in Fig 1.
Fig 1: Multistage Multiuser PIC with MMSE
Detector
Algorithm for Multistage Multiuser
PIC with MMSE detector:
(1)
1 mmse
b sgn(y )
For s=2 to S %/ Cancellation of Interference s-
1 stages/
For k=1 to K %/ The interference is subtracted
from every user signal at each stage
/
(s)
(s-1)
k m m s e j jk j
j=1
jk
Z =y - A ρb
K
where
kj kj
kj R - diag(R )ρ
(s)
K
(s-1)
k m m s e j kj kj j
j=1
jk
z =y - A (R -diag(R ))b
End
()
( -1)
sgn( )
s
s
k
kz
b
%/ Decision /
End
3.2 Computational Complexity of PIC
Computational Complexity involves the amount
of time taken to accomplish the multiuser
detection starting from the time of arrival of
transmitted signal at the first stage of the
detector of the receiver. Therefore, the time
required to perform the number of
multiplications and the wide variety of
additions in the detection process need to be
DESIGN, CONSTRUCTION, MAINTENANCE
DOI: 10.37394/232022.2024.4.21
J. Ravindrababu, K. Sri Krishna, K. Satya Narayana Swami,
B. Kavya Sri, G. Madhuri, J. V. Ravi Teja,
J. V. Ravi Chandra
E-ISSN: 2732-9984
203
calculated to arrive at the computational
complexity.
The cancellation of MAI from the
stronger user every time until the closing user
requires multiplication of two matrices. To
accomplish the multiplication of an (A1×B1)
matrix with an (B1×C1) matrix, A1B1C1
multiplications and A1B1C additions are
needed.
Therefore, assuming K users in the
system wherein the transmission is a burst
waveform, each user transmits D data symbols
in the burst, B represents the number of chips in
the spreading code for every user, and U is the
complicated matrix which includes the factors
that describe the channel impulse response, then
one needs DB instances of multiplications and
DB instances of additions for each user for one
data symbol in a single path burst. If the bursts
arrive along L multi-path channels, then the
receiver would require DBL instances of
multiplications and DBL instances ofadditions
for one data symbol. To combine the D symbols
transmitted from the dispersive paths, it requires
in addition DL instances of multiplications and
DL instances of additions. Therefore, DBL+DL
times of multiplications and DBL+DL times of
additions are required to get the data estimates
from the receiver. In the signal reconstruction
process, the data estimates need to be respread
with the spreading code first and then
convolved with the corresponding channel
impulse response, which leads to DBL
multiplications and (DB+U−1) additions. To get
the data estimate for every user, the affects of
remaining users need to be subtracted. To
cancel one user’s MAI, it needs (DB+U−1)
subtractions. Therefore, for every user,
(K−1)(DB+U−1) subtractions are needed. For a
system supporting K users, the whole number
of mathematical operations are SPIC1 = K
[DBL+DL+DBL+DL+DBN+DBL+DB+U-
1+(K-1) (DB+D-1)]
= K [3DBL+2DL+DB+K(DB+U-1)] for
first stage
Therefore, for two stage,
SPIC2 = 2 K [3DBL+2DL+DB+K(DB+U-1)]
Therefore, the number of operations needed by
the two stage PIC detector for every one symbol
is
SPIC2 /symbol = SPIC2 / KD
3.3 Multistage Multiuser PPIC with MMSE
Detector
In this scheme, the MAI Cancellation is
implemented using a weight factor at every stage to
decide about the amount of cancellation to be
implemented [14-16].
In a Multistage Multiuser PPIC scheme, the weight
factor used for interference cancellation affects a
biased selection statistic. The bias has its strongest
effect on the first stage of interference cancellation.
In the subsequent stages its effect decreases.
However, if the biased selection statistic is unfair at
the first stage leading to a wrong cancellation, then
the effects of these errors can get escalated in the
subsequent stages [13-16].
One way to mitigate the effect of the biased
selection statistic to enhance the overall
performance of multistage PPIC is to multiply the
amplitude estimates with a partial cancellation
factor, CK(s) lying between 0 and 1 [i.e.,
()
01
s
KC
]
which varies with the stage of cancellation ‘s’ and
the number of users ‘K’.
In this scheme also, various stages are involved
for interference estimation and cancellation.
The MMSE is used in the first stage to estimate
the information bits whereas the subsequent
stages also use MMSE detectors. The signal
reconstruction and subtraction of the predicted
interference from other users obtained by
weighting the estimates of the information bit of
the user in question is carried out at all stages
[14-16]. The multistage multiuser PPIC with
MMSE detector is shown in Fig 2.
Fig 2: Partial PIC detector
DESIGN, CONSTRUCTION, MAINTENANCE
DOI: 10.37394/232022.2024.4.21
J. Ravindrababu, K. Sri Krishna, K. Satya Narayana Swami,
B. Kavya Sri, G. Madhuri, J. V. Ravi Teja,
J. V. Ravi Chandra
E-ISSN: 2732-9984
204
Algorithm for Multistage Multiuser
PPIC with MMSE detector:
(1)
1sgn( )
mmse
by
For s=2 to S %/ Cancellation of
Interference s-1 stages /
For k=1 to K %/ The interference is
subtracted from every
user signal
at each stage /
K()
(s-1) (s)
k m m s e k j kj j
j=1
jk
z =y - c A ρb
s
where
kj ()ρij ij
R diag R
()
(s-1) (s)
k m m s e k j ij ij j
j=1
jk
=y - c A (R -diag(R )) b
Ks
z
End
(s) (s-1)
kk
b sgn( )z
%/
Decision /
End
3.4 Computational Complexity of PPIC:
For this case, assuming K users in the system
where in the transmission is a burst waveform,
each user transmits D data symbols in the burst,
n represents the number of chips in the
spreading code for every user, C represents the
partial cancellation factor and U is the
complicated matrix which includes the factors
that describe the channel impulse response, then
one needs CDBinstances of multiplications and
CDB instances of additions for each user for
one data symbol in a single path burst . If the
bursts arrive along L multi-path channels, then
the receiver would require CDBL instances of
multiplications and CDBL instances of
additions for one data symbol. To combine the
q symbols transmitted from the dispersive paths
requires CDL instances of multiplications and
CDL instances of additions. Therefore, to get
the data estimates from the receiver,
CDBL+CDL times of multiplications and
CDBL+CDL times of additions are required. In
the signal reconstruction part, the detected data
have to be re-spread with the spreading code
first leading to CDB instances of
multiplications, and then convolve with the
corresponding channel impulse response
resulting in DBL times of multiplications and
C(DB+U−1) times of additions. To get the
estimate for every user, all of the different users
affects need to be subtracted. To cancel one
user’s MAI, it will need C(DB+U−1) instances
of subtraction. Therefore, for every user,
(K−1)C(DB+U−1) instances of subtractions are
needed. For a system supporting K users, the
whole number of mathematical operations are
SPPIC1 = KC [DBL+DL+DBL+DL+DB+DBL+DB+U-1+(K-1)
(DB+U-1)]
= KC [3DBL+2DL+DB+K(DB+U-1)] for first stage
Therefore, for two stage,
SPPIC2 = 2 KC [3DBL+2DL+DB+K(DB+U-1)]
Therefore, the number of operations needed by
the two stage PIC detector for every one symbol
is
SPPIC2 /symbol = SPPIC2/ KD .
4. Simulation Results
The DS-CDMA basic multistage multiuser
discrete time paradigm was applied. The
customer's data is disseminated via BPSK
modulation and Kasami spreading sequence.
It is evident from the below simulation results
that with increasing number of stages, the system
overall BER performance is improved as PIC with
MMSE detector. However, the computational
complexity also increases. The BER performance
did not alternate dramatically beyond 4thstage (not
shown here). Three stages are only considered for
simplicity. BER performance is better at 3rdstage
when compared to that at 1ststage and 2ndstage for
DESIGN, CONSTRUCTION, MAINTENANCE
DOI: 10.37394/232022.2024.4.21
J. Ravindrababu, K. Sri Krishna, K. Satya Narayana Swami,
B. Kavya Sri, G. Madhuri, J. V. Ravi Teja,
J. V. Ravi Chandra
E-ISSN: 2732-9984
205
all the cases like PIC and PPIC from Fig 4 and 6
for clarity.
It is evident from the simulations results shown
in 5 and 7 computational complexity increases
increasing number of users.
0 5 10 15 20 25 30 35 40 45 50
10-6
10-5
10-4
10-3
10-2
10-1
100
BER
Eb/No
PIC with MMSE
stage 1
stage 2
stage 3
Fig 4: Bit-Error-Rate performance of PIC with
MMSE for K=10 users.
101102
0
0.5
1
1.5
2
2.5
3
3.5 x 105Computational complexity of PIC
Number of users (K)
No.of Computations(S)
PIC
Fig 5: Computational complexity of PIC
0 5 10 15 20 25 30 35 40 45 50
10-6
10-5
10-4
10-3
10-2
10-1
100
BER
Eb/No
PPIC with MMSE
stage 1
stage 2
stage 3
Fig 6: Bit-Error-Rate performance of PPIC with
MMSE for K=10
101102
0
0.5
1
1.5
2
2.5
3
3.5
4x 105Computational Complexity comparison
No.of users (K)
No.of Computations (S)
PIC
PPIC
Fig 7: Computational complexity of PIC and
PPIC
6. Conclusions
Employing multiple-stage multiuser approaches in
DS-CDMA systems can also minimize the
complexity of computation and Multiple Access
Interference. In the multistage PIC approach, bit
error rate (BER) drops and detection becomes more
dependable as the number of stages rises. The ability
to increase in subsequent phases cannot be
guaranteed by the PIC. In a DS-CDMA system, the
effectiveness of the Partial Parallel Interference
Cancellation (PPIC) technique is assessed. But there
is no improvement in computational complexity.
References
[1]. J. Viterbi. CDMA, “Principles of Spread Spectrum
Communication”. Addison-Wesley Wireless
Communications, 1995..
[2]. R.A. Scholtz, “The Origins of Spread-Spectrum
Communications”. IEEE Transactions on
Communications, Vol. No 30(5), May 1982, PP 822–
854.
[3]. S. Verdu, “Multiuser Detection”, Cambridge
University Press, Cambridge, UK, ISBN:0521593735,
1998.
[4]. L.Vanderdorpe, “Multitone spread spectrum multiple
access communications systems in a multipath Rician
fading channel,” IEEE Transactions on Vehicular
Technology, Vol.No. 44, May 1995, PP 327-337
[5]. B. Dhammika and T.Aulin, “Multiuser detection for
continuous phase modulation over Rayleigh fading
channels,” IEEE Communication letters, Vol. No.9,
October2005, PP 906-908.
[6]. Zhao Zhijin, and Zhao Zhidong “Discrete Shuffled
Frog Leaping Algorithm for Multi-user Detection in
DS-CDMA Communication System” IEEE
international conference on communication
technology proceedings, 2008, PP 421-444.
[7]. M. K. Varanasi and B. Aazhang, “Near optimum
demodulators for coherent communications in
asynchronous Gaussian CDMA channels,” in Proc.
DESIGN, CONSTRUCTION, MAINTENANCE
DOI: 10.37394/232022.2024.4.21
J. Ravindrababu, K. Sri Krishna, K. Satya Narayana Swami,
B. Kavya Sri, G. Madhuri, J. V. Ravi Teja,
J. V. Ravi Chandra
E-ISSN: 2732-9984
206
22nd conf. on Information Sciences and Systems,
March1998, PP 832-839.
[8]. S. Gray, et.al.“Multiuser detection in mismatched
multiple access channels,” IEEE Transactions on
Communications, Vol. N.43, December1995, PP
3080-3089.
[9]. M. Latva-aho, et.al. “Parallel interference cancellation
receiver for DS-CDMA systems in fading channels,”
in Proc. IEEE Int. Symp. Personal, Indoor and Mobile
Radio Communications (PIMRC), 1997, PP 559–564.
[10]. Zhendong Yin, et.al. “A complexity-performance-
balanced multiuser detector based on artificial fish
swarm algorithm for DS-UWB systems in the AWGN
and multipath environments” EURASIP Journal on
Advances in Signal Processing, 2012: Vol. No.229,
PP 1-13.
[11]. Yao Xie, et.al. “Reduced-Dimension Multiuser
Detection” IEEE Transactions on Information Theory,
Vol. No.59, June 2013, PP 3858-3874.
[12]. Bo Ma, et.al. “GMM-MUD: An Effective Multiuser
Detection Algorithm for DS-UWB-Based Space
Formation Flying Systems” Hindawi Mathematical
Problems in Engineering, 2019, Vol. No.5, PP 1-10.
[13]. SaifHikmatMousa, et.al. “Effective Wide Spectrum
Sharing Techniques Relying on CR Technology
toward 5G”: A Survey Journal of Communications
Vol. No.15, February 2020, PP 122-147.
[14]. J.Ravindrababu and Dr.E.V.KrishnaRao,
“Performance Analysis, improvement and complexity
reduction in Multi stage Multi-User Detector with
parallel interference cancellation for DS-CDMA
System Using odd kasami sequence” World Scientific
and Engineering Academy and Society (WSEAS)
Transactions on communications Vol. No.12, April
2013, PP 133-142.
[15]. J.Ravindrababu, and E.V.KrishnaRao, Y.RajaRao,
“Interference and complexity reduction in multi stage
multi-user detection” Springer: Wireless Personal
Communications Vol. No.79, November 2014, PP
1385–1400.
[16]. J.Ravindrababu,and E.V.KrishnaRao, “Interference
Reduction in fading environment using Multistage
Multiuser Detection Techniques” World Scientific
and Engineering Academy and Society (WSEAS)
transactions on signal processing, Vol. No.15, August
2019, PP 36-46.
[17]. Daniele Angelosante, EzioBiglieri, MarcoLops “Low-
complexity receivers for multiuser detection with an
unknown number of active users” Signal Processing
Vol: 90, 2010, PP:1486–1495.
[18]. Linglong Dai, Xinyu Gao, Shuangfeng Han “Low-
Complexity Soft-Output Signal Detection Based on
Gauss–Seidel Method for Uplink Multiuser
Large-Scale MIMO Systems” IEEE
TRANSACTIONS ON VEHICULAR
TECHNOLOGY, VOL. 64, NO. 10, OCTOBER
2015, PP:4839-4845.
[19]. Yang Du, Binhong Dong “Low-Complexity Detector
in Sparse Code Multiple Access Systems” IEEE
COMMUNICATIONS LETTERS, VOL. 20, NO. 9,
SEPTEMBER 2016, PP:1812-1815.
[20]. Yinman Lee, Meng-Wei Liang, “Low-Complexity
Hybrid Analog-Digital Signal Detector for Uplink
Multiuser Massive MIMO Systems” 2019 IEEE 8th
Global Conference on Consumer Electronics (GCCE),
PP:415-417.
[21]. Rong Ran, and Hayoung Oh, “Low‑complexity
sparse‑aware multiuser detection for large‑scale
MIMO systems” EURASIP Journal on Wireless
Communications and Networking, Vol 58,2021,PP:1-
15.
Contribution of Individual Authors to the
Creation of a Scientific Article (Ghostwriting
Policy)
The authors equally contributed in the present
research, at all stages from the formulation of the
problem to the final findings and solution.
Sources of Funding for Research Presented in a
Scientific Article or Scientific Article Itself
No funding was received for conducting this study.
Conflict of Interest
The authors have no conflicts of interest to declare
that are relevant to the content of this article.
Creative Commons Attribution License 4.0
(Attribution 4.0 International, CC BY 4.0)
This article is published under the terms of the
Creative Commons Attribution License 4.0
https://creativecommons.org/licenses/by/4.0/deed.en
_US
DESIGN, CONSTRUCTION, MAINTENANCE
DOI: 10.37394/232022.2024.4.21
J. Ravindrababu, K. Sri Krishna, K. Satya Narayana Swami,
B. Kavya Sri, G. Madhuri, J. V. Ravi Teja,
J. V. Ravi Chandra
E-ISSN: 2732-9984
207