# Fast Maximum-Likelihood Decoder for Quasi-Orthogonal Space-Time Block Code

Authors: Adel Ahmadi; Siamak Talebi
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Motivated by the decompositions of sphere and QR-based methods, in this paper we present an extremely fast maximum-likelihood (ML) detection approach for quasi-orthogonal space-time block code (QOSTBC). The proposed algorithm with a relatively simple design exploits structure of quadrature amplitude modulation (QAM) constellations to achieve its goal and can be extended to any arbitrary constellation. Our decoder utilizes a new decomposition technique for ML metric which divides the metric into independent positive parts and a positive interference part. Search spaces of symbols are substantially reduced by employing the independent parts and statistics of noise. Symbols within the search spaces are successively evaluated until the metric is minimized. Simulation results confirm that the proposed decoder’s performance is superior to many of the recently published state-of-the-art solutions in terms of complexity level. More specifically, it was possible to verify that application of the new algorithms with 1024-QAM would decrease the computational complexity compared to state-of-the-art solution with 16-QAM.


---

## Body

## 1. Introduction

Quasi-orthogonal space-time block codes (QOSTBCs) [1, 2] have attracted much attention lately due to their desired performances and pairwise detections. Given these advantages, in [3–5] investigation is carried out to optimize diversity and coding gain performances. One drawback of these codes, however, is that complexity of pairwise optimum maximum-likelihood (ML) decoder rises drastically when size of constellation is increased. A survey of related literature shows that much research has been underway to develop an approach that reduces complexity of QOSTBC decoder. In [6, 7], lattice reduction aided (LRA) method is combined with suboptimal detectors in order to improve performance of the suboptimal decoders in multiple-input multiple-output (MIMO) communications systems. In [8], the QOSTBC is employed to reduce gap between error ratio of ML and LRA methods. This work also compares the performances of spatial multiplexing and QOSTBC with those of LRA zero-forcing and ML decoders. Authors of [9] employ QR decomposition and sorting to simplify detection of QOSTBC with four transmit antennas. This method achieves ML error performance and offers low complexity. For rotated QOSTBC with four transmit antennas and quadrature amplitude modulation (QAM) constellation, [10] explores a fast scheme with ML error performance and reduced complexity. In [11], a different pairwise structure is proposed for QOSTBCs decoding with three or four transmit antennas. The algorithm in [11] initializes the first symbol by rounding its zero-forcing estimation to the nearest constellation point. Then, the other symbol of the pair is detected by minimizing its cost function and the first symbol is discovered by minimizing its cost function. The quality of the detected symbols is dependent upon the initial value which means that the detection procedure may have to be repeated a number of times if the distance between the selected value and equalized symbol is higher than a threshold. This method achieves a near-ML performance with low complexity decoder. A new 4 × 4 QOSTBC is reported in [12] that employs precoder and rotated symbols. The complexity of the decoder is low and a reasonable suboptimum error performance is obtained when rotation angles are optimized. The optimization procedure is related to signal-to-noise ratio (SNR) and utilized constellation. In [13], a suboptimum fast decoding algorithm is investigated for block diagonal QOSTBC with arbitrary transmit antennas. This decoder employs precomputed look-up tables and statistics of phases in order to prepare a limited search area. Authors of [14] introduce a 4 × 4 nonorthogonal space-time block code (STBC) with improved coding gain and a low complexity decoder. In [15], a STBC is proposed for four transmit antennas based on mapping of PAM and QAM constellations. This code offers a high coding gain and authors design a low complexity decoder for it. A new structure for fast group decodable codes is presented in [16] whose decoder offers the lowest worst-case complexity among STBCs.The innovative method developed in this letter decomposes the received vector into two pairs of symbols which are detected independently. To do this, the ML metric minimization of each pair is transformed into a sum of independent positive parts and an interference part. It should be noted that independency of the positive parts facilitates detection by allowing us to considerably limit the search spaces of the symbols. The candidates placed in relevant partial search areas are gradually evaluated and then the transmitted symbols are estimated by computing interference between them. If the search areas are small and no symbol is detected, then they are extended and evaluation is repeated till the transmitted symbols are detected. The ML metric decomposition studied in this letter boasts two important features, namely, decomposition is not a highly complex process, and more significantly, most of the decomposed parts are independent of each other and therefore the search space can be efficiently limited. Based on these features the proposed method offers the desired ML performance at very low complexity.Compared with the proposed method, Sphere [17] and QR [9] decoders are more complex because their search spaces cannot effectively be reduced, and they both require significant precomputation steps. As for the fast ML decoder in [10], authors utilize a simplified quadratic ML decoding statistic for QAM constellations, and comparison of the simulation results indicates that the average complexity of this work is higher than that of the proposed method confirming that the latter can be extended to any arbitrary constellations. On the other hand, the nonoptimum detectors in [12, 13] both require rotation angle optimization and significant memory locations for look-up tables, respectively, whereas the proposed solution does not require any optimization or look-up tables.


## 2. System Model

QOSTBC forM
T
=
4 transmit antennas has the following form:(1)
X
=
s
1
s
2
s
~
3
s
~
4
-
s
2
∗
s
1
∗
-
s
~
4
∗
s
~
3
∗
s
~
3
s
~
4
s
1
s
2
-
s
~
4
∗
s
~
3
∗
-
s
2
∗
s
1
∗
,where s
~
3
=
e
j
θ
s
3, s
~
4
=
e
j
θ
s
4, j
=
-
1, and the data symbols s
1
,
…
,
s
4 belong to constellation C with unit average energy. The rotation angle θ can be selected such that full diversity and high coding gain are attained. For example, θ
=
π
/
4 is optimum for QAM [10]. A space-time communication system with four transmit antennas and M
R receive antennas that transmits four symbols over four time slots can be represented by an equivalent receive antenna j as(2)
y
j
=
ρ
M
T
H
j
s
+
w
j
,where SNR is indicated by ρ and s
=
s
1
,
…
,
s
4
T is the transmitted vector. The equivalent received vector and equivalent additive white Gaussian noise (AWGN) vector are denoted by y
j
=
y
1
,
j
,
…
,
y
M
T
,
j
T and w
j
=
w
1
,
j
,
…
,
w
M
T
,
j
T, respectively. Also, y
i
,
j and w
i
,
j denote the equivalent received signal and its relative noise at the ith time slot of the jth receive antenna, respectively. The AWGN has complex Gaussian distribution with zero mean and unit variance. The equivalent channel matrix for the jth receive antenna is defined as(3)
H
j
≜
B
h
1
,
j
,
h
2
,
j
e
j
θ
B
h
3
,
j
,
h
4
,
j
B
h
3
,
j
,
h
4
,
j
e
j
θ
B
h
1
,
j
,
h
2
,
j
,where h
i
,
j stands for channel fade between the ith transmit antenna and the jth receive antenna such that(4)
B
h
i
,
j
,
h
i
+
1
,
j
≜
h
i
,
j
h
i
+
1
,
j
h
i
+
1
,
j
∗
-
h
i
,
j
∗
.The complete received vectors can be concatenated as:(5)
y
=
ρ
M
T
H
s
+
w
,where y
≜
y
1
T
,
…
,
y
M
R
T
T,  w
≜
w
1
T
,
…
,
w
M
R
T
T and H
≜
H
1
T
,
…
,
H
M
R
T
T.


## 3. Fast Maximum-Likelihood Decoder

### 3.1. Proposed ML Detection Method

The ML decoder should minimize the following norm in order to estimate the transmitted symbols:(6)
s
~
=
arg
⁡
min
⁡
s
∈
C
M
T
⁡
y
-
ρ
M
T
H
s
,where norm x is defined as x
=
x
H
x and x
H indicates conjugate transpose of x. The above minimization can be rewritten as(7)
s
~
=
arg
⁡
min
⁡
s
∈
C
M
T
⁡
H
s
-
z
,where z
=
z
1
,
…
,
z
M
T
T is defined as(8)
z
≜
M
T
ρ
H
H
H
-
1
H
H
y
.The matrixH
j can be decomposed into(9)
H
j
=
1
2
U
H
j
′
U
V
,where V
≜
diag
I
2
,
e
j
θ
I
2,  U
≜
I
2
I
2
I
2
-
I
2,  I
2
≜
1
0
0
1, and(10)
H
j
′
≜
B
h
1
,
j
+
h
3
,
j
,
h
2
,
j
+
h
4
,
j
0
2
×
2
0
2
×
2
B
h
1
,
j
-
h
3
,
j
,
h
2
,
j
+
h
4
,
j
.By employing (9) and doing some math operations, we are able to compute z through fewer mathematic operations as(11)
z
=
M
T
4
ρ
V
H
U
D
-
1
∑
j
=
1
N
H
j
′
H
U
y
j
,where D
≜
diag
α
I
2
,
β
I
2 and (12)
α
≜
∑
j
=
1
M
R
h
1
,
j
+
h
3
,
j
2
+
h
2
,
j
+
h
4
,
j
2
,
β
≜
∑
j
=
1
M
R
h
1
,
j
-
h
3
,
j
2
+
h
2
,
j
-
h
4
,
j
2
.In addition,H
s
-
z
2 can be decomposed into two independent parts by utilizing (9), which results in(13)
H
s
-
z
2
=
∑
l
=
1
2
s
l
-
z
l
H
T
s
l
-
z
l
,where z
l
≜
z
l
,
z
l
+
2
T and s
k
≜
s
l
,
s
l
+
2
T for l
=
1 and 2. By defining t
0
≜
α
+
β
/
2 and t
1
≜
α
-
β
/
2, the matrix T can be represented as(14)
T
≜
t
0
e
j
θ
t
1
e
-
j
θ
t
1
t
0
.Based on (13), for l
=
1 and 2, the ML decoder can independently detect s
~
l
≜
s
~
l
,
s
~
l
+
2
T by(15)
s
~
l
,
s
~
l
+
2
=
arg
⁡
min
⁡
s
l
,
s
l
+
2
∈
C
⁡
s
l
-
z
l
H
T
s
l
-
z
l
.For the remaining part of this section, we focus on detection of s
~
1
,
s
~
3 noting that the other pair s
~
2
,
s
~
4 can be detectable by applying a similar approach. Furthermore, for the sake of simplicity and clarity, let us consider a square M
2-QAM constellation, although the solution can also be straightforwardly extended to other constellations. For k
=
1 and 3, s
k and z
k can be represented by their real and imaginary parts as s
k
=
s
k
+
j
s
k
+
1 and z
k
=
z
k
+
j
z
k
+
1, respectively. Under this scenario, s
l
l
=
1
4 are independent and belong to the set R
=
a
1
,
a
2
,
…
,
a
M with real members. The decoder searches within R to find the best choices for the real and imaginary parts of symbols which minimizes the ML metric.The ML minimization (15) can be reformulated as(16)
γ
≜
∑
l
=
1
4
δ
l
2
+
τ
1
κ
1
+
τ
2
κ
2
,where τ
1
≜
2
λ
cos
⁡
⁡
θ,  τ
2
≜
2
λ
sin
⁡
θ,  λ
≜
t
1
/
t
0,  κ
1
≜
δ
1
δ
3
+
δ
2
δ
4, κ
2
≜
δ
2
δ
3
-
δ
1
δ
4, and δ
l
≜
s
l
-
z
l for l
=
1
,
…
,
4. Based on (12), t
0
≥
|
t
1
| and we can rewrite minimization of (16) as minimization of ε
≜
γ
/
t
0
-
t
1 which is decomposable into sum of positive parts:(17)
ε
=
∑
l
=
1
4
δ
l
2
+
λ
1
-
λ
δ
1
+
j
δ
2
+
μ
δ
3
+
j
δ
4
2
,where μ
≜
sign
t
1
e
j
θ and sign
· stands for the signum function. In (17), the parts δ
l
l
=
1
4 are independent of each other which allows us to reduce the search space effectively, and the purpose of the third part is to represent interference between the other parts.By assuming that the minimum of (17) is smaller than r
2, we deduce that δ
l
<
r for l
=
1
,
…
,
4. Therefore, the output of the ML decoder has to be located within corresponding intervals z
l
-
r
,
z
l
+
r which reduces the search spaces effectively. The ML metric (16) for the remaining members is incrementally evaluated piece by piece to remove more inappropriate members and finally we obtain symbols s
~
1
=
s
~
1
+
j
s
~
2 and s
~
3
=
s
~
3
+
j
s
~
4 which minimize the ML metric. These steps for an M
2-QAM constellation are demonstrated as a pseudocode in Pseudocode 1. In this pseudocode, cardinality of set R is indicated by R
c, the mth member of this set is denoted by R
m, and R
l
≜
a
∈
R
:
a
-
z
l
<
r for l
=
1
,
…
,
4.Pseudocode 1:Pseudocode of search stage of proposed method.
γ
th
=
1
-
λ
r
2;
ν
=
1
/
1
-
λ;
FORm
1
=
1,2
,
…
,
R
1
c
δ
1
=
R
1
m
1
-
z
1;
ε
1
=
δ
1
2;
FORm
2
=
1,2
,
…
,
R
2
c
δ
2
=
R
2
m
2
-
z
2;
ε
2
=
ε
1
+
δ
2
2;
IFε
2
>
r
2
CONTINUE;
END
FORm
3
=
1,2
,
…
,
R
3
c
δ
3
=
R
3
m
3
-
z
3;
ε
3
=
ε
2
+
δ
3
2;
IFε
3
>
r
2
CONTINUE;
END
FORm
4
=
1,2
,
…
,
R
4
c
δ
4
=
R
4
m
4
-
z
4;
ε
4
=
ε
3
+
δ
4
2;
IFε
4
>
r
2
CONTINUE;
END
κ
1
=
δ
1
δ
3
+
δ
2
δ
4;
κ
2
=
δ
2
δ
3
-
δ
1
δ
4;
γ
=
ε
4
+
τ
1
κ
1
+
τ
2
κ
2;
IFγ
>
γ
th
ε
=
ν
γ;
r
=
ε;
γ
th
=
γ;
s
~
1
=
R
1
m
1
+
j
R
2
m
2;
s
~
3
=
R
3
m
3
+
j
R
4
m
4;
END
END
END
END
ENDThe proposed method can be extended to other constellations with arbitrary distribution of signal points. Under this condition, the real part of a symbol is related to its imaginary part and therefore they are examined together.


### 3.2. Algorithm Initialization

The proposed method needs to begin with an appropriate initial value forr which should be suitably selected to avoid unnecessary complexity. It is worth mentioning that in the proposed method the initial value selection is approximately similar to the initial radius selection in the sphere method. If the initial value of r is too high, size of search spaces and thus the detection complexity will be raised. Conversely, if value of r is initialized with a very small value, the search spaces include no candidate and no symbol will be detected. Under this situation, we have to increase the value of r and apply our method again till symbols are detected. In this letter, we set the initial value of r to r
initial
=
d
min
⁡
/
2, where d
min
⁡ indicates the minimum distance between two distinct constellation points. In this case, search region of each symbol contains just one candidate point which is almost the best possible choice for moderate to high SNRs. As will be shown in Section 4, this type of initialization ensures that the proposed decoder achieves low complexity.


### 3.3. Complexity Analysis

The decoder operation can be divided into precomputation and search stages. The initial value of variables and candidate points are obtained by performing about64
M
R
+
29 real additions, 40
M
R
+
31 multiplications, and four divisions during the first stage. In addition, the proposed decoder on average employs about 8
log
⁡
2
⁡
M and 8
M relational operators for an M-ary QAM and other constellations, respectively.The complexity of the search stage depends on complex Gaussian noises. From (8), we infer that z
1
=
s
1
+
σ
n
1 and z
3
=
s
3
+
ϱ
/
σ
e
-
j
θ
n
1
+
σ
′
n
3, where s
1 and s
3 are transmitted symbols, n
1 and n
3 are independent complex Gaussian noises with zero means and unit variances, σ
2
=
M
T
α
+
β
/
2
ρ
α
β, ϱ
=
M
T
α
-
β
/
2
ρ
α
β, and σ
′
2
=
2
M
T
/
ρ
(
α
+
β
). Based on the complex Gaussian distribution, the real and imaginary parts of z
1
-
s
1 and z
3
-
s
3 are located within -
ω
,
+
ω with probability P
ω. This probability is given by(18)
P
ω
=
1
2
π
·
∫
-
ω
/
σ
ω
/
σ
∫
-
ω
/
σ
ω
/
σ
Q
-
ω
σ
′
-
η
1
-
Q
ω
σ
′
-
η
1
·
Q
-
ω
σ
′
-
η
2
-
Q
ω
σ
′
-
η
2
e
-
1
/
2
n
2
+
n
′
2
d
n
d
n
′
,where η
1
=
ϱ
/
σ
σ
′
n
cos
⁡
⁡
θ
+
n
′
sin
⁡
θ, η
2
=
ϱ
/
σ
σ
′
n
′
cos
⁡
⁡
θ
-
n
sin
⁡
θ, and Q
u
=
1
/
2
π
∫
u
∞
exp
⁡
⁡
-
ζ
2
/
2
d
ζ. When ω
≫
σ
′, the value of P
ω can be bounded by(19)
P
ω
>
1
-
2
Q
ω
σ
′
2
1
-
2
Q
4
2
.By assuming that the decoder can truly detects
1 and s
3, the complexity of our pseudocode can be bounded by(20)
C
1,3
≤
c
M
ω
N
ω
,where c is a constant value and M
ω and N
ω are functions that indicate the number of constellation points which are located within the search intervals of s
1 and s
3, respectively. The inequality (19) implies that P
ω gets very close to one for d
min
⁡
/
2
≤
ω
≤
d
min
⁡ and acceptable values of SNRs which results in σ
′
≪
d
min
⁡. Under this scenario, the real and imaginary parts of z
k approach those of s
k, such that very few signal points take place inside the created search regions. This statistic feature reduces the complexity of search stage and makes it become independent of constellation size when SNR is reasonable.The detection complexity ofs
k
k
=
1
4 in the search stage depends on the power of noises which practically become small for reasonable values of SNRs. Under this condition, on average either one or two candidates are selected for evaluation per each dimension, hence requiring about 22–44 additions and 22–44 multiplications for a QAM constellation. This means that complexity of the search stage is low and therefore that of precomputation is taken as the dominant factor.Compared against the sphere detection (SD) method, where the precomputation stage requires about424
M
R
+
28 additions, 432
M
R
+
120 multiplications with real equivalent channel having 8
M
R rows and 8 columns [17], or against the QR-based methods involving about 104
M
R
-
8 additions and 136
M
R
+
112 multiplications for the preparation stage [9], it is obvious that the overall complexity of the proposed model enjoys a clear advantage.


### 3.4. Comparison with Sphere

The SD method reformulates the complex ML metric of (6) in a real form as y
-
H
s, where y
∈
R
8
M
R
×
1, H
∈
R
8
M
R
×
8, and s
∈
R
8
×
1. Then, after applying Cholesky factorization and solving two linear systems, a new metric is obtained in form of R
z
-
s, where R
∈
R
8
×
8 is an upper triangular matrix and z is the real zero-force equalized vector. Therefore, the algorithm should minimize the following metric for the real entries of s
∈
R
8
×
1:(21)
∑
i
=
1
8
∑
j
=
i
8
r
i
,
j
z
j
-
s
j
2
=
r
8,8
z
8
-
s
8
2
+
r
7,7
z
7
-
s
7
+
r
7,8
z
8
-
s
8
2
+
⋯
+
r
1,1
z
1
-
s
1
+
r
1,2
z
2
-
s
2
+
⋯
+
r
1,8
z
8
-
s
8
2
,where r
i
,
j, z
j, and s
j are entries of r, z, and s, respectively. This equation consists of eight positive terms which are dependent on each other. This means that the search spaces of s
i’s (for i
=
1
,
…
,
8) are dependent on the values of s
i
+
1
,
s
i
+
2
,
… and s
8 while in the decomposed metric (17) of the proposed method, all terms are independent of each other except the last term. This fact helps us to prepare the search spaces individually and reduce their sizes more efficiently which is not possible with the SD method. Also, the SD algorithm requires Cholesky factorization and two linear systems solving which results in higher complexity.


## 3.1. Proposed ML Detection Method

The ML decoder should minimize the following norm in order to estimate the transmitted symbols:(6)
s
~
=
arg
⁡
min
⁡
s
∈
C
M
T
⁡
y
-
ρ
M
T
H
s
,where norm x is defined as x
=
x
H
x and x
H indicates conjugate transpose of x. The above minimization can be rewritten as(7)
s
~
=
arg
⁡
min
⁡
s
∈
C
M
T
⁡
H
s
-
z
,where z
=
z
1
,
…
,
z
M
T
T is defined as(8)
z
≜
M
T
ρ
H
H
H
-
1
H
H
y
.The matrixH
j can be decomposed into(9)
H
j
=
1
2
U
H
j
′
U
V
,where V
≜
diag
I
2
,
e
j
θ
I
2,  U
≜
I
2
I
2
I
2
-
I
2,  I
2
≜
1
0
0
1, and(10)
H
j
′
≜
B
h
1
,
j
+
h
3
,
j
,
h
2
,
j
+
h
4
,
j
0
2
×
2
0
2
×
2
B
h
1
,
j
-
h
3
,
j
,
h
2
,
j
+
h
4
,
j
.By employing (9) and doing some math operations, we are able to compute z through fewer mathematic operations as(11)
z
=
M
T
4
ρ
V
H
U
D
-
1
∑
j
=
1
N
H
j
′
H
U
y
j
,where D
≜
diag
α
I
2
,
β
I
2 and (12)
α
≜
∑
j
=
1
M
R
h
1
,
j
+
h
3
,
j
2
+
h
2
,
j
+
h
4
,
j
2
,
β
≜
∑
j
=
1
M
R
h
1
,
j
-
h
3
,
j
2
+
h
2
,
j
-
h
4
,
j
2
.In addition,H
s
-
z
2 can be decomposed into two independent parts by utilizing (9), which results in(13)
H
s
-
z
2
=
∑
l
=
1
2
s
l
-
z
l
H
T
s
l
-
z
l
,where z
l
≜
z
l
,
z
l
+
2
T and s
k
≜
s
l
,
s
l
+
2
T for l
=
1 and 2. By defining t
0
≜
α
+
β
/
2 and t
1
≜
α
-
β
/
2, the matrix T can be represented as(14)
T
≜
t
0
e
j
θ
t
1
e
-
j
θ
t
1
t
0
.Based on (13), for l
=
1 and 2, the ML decoder can independently detect s
~
l
≜
s
~
l
,
s
~
l
+
2
T by(15)
s
~
l
,
s
~
l
+
2
=
arg
⁡
min
⁡
s
l
,
s
l
+
2
∈
C
⁡
s
l
-
z
l
H
T
s
l
-
z
l
.For the remaining part of this section, we focus on detection of s
~
1
,
s
~
3 noting that the other pair s
~
2
,
s
~
4 can be detectable by applying a similar approach. Furthermore, for the sake of simplicity and clarity, let us consider a square M
2-QAM constellation, although the solution can also be straightforwardly extended to other constellations. For k
=
1 and 3, s
k and z
k can be represented by their real and imaginary parts as s
k
=
s
k
+
j
s
k
+
1 and z
k
=
z
k
+
j
z
k
+
1, respectively. Under this scenario, s
l
l
=
1
4 are independent and belong to the set R
=
a
1
,
a
2
,
…
,
a
M with real members. The decoder searches within R to find the best choices for the real and imaginary parts of symbols which minimizes the ML metric.The ML minimization (15) can be reformulated as(16)
γ
≜
∑
l
=
1
4
δ
l
2
+
τ
1
κ
1
+
τ
2
κ
2
,where τ
1
≜
2
λ
cos
⁡
⁡
θ,  τ
2
≜
2
λ
sin
⁡
θ,  λ
≜
t
1
/
t
0,  κ
1
≜
δ
1
δ
3
+
δ
2
δ
4, κ
2
≜
δ
2
δ
3
-
δ
1
δ
4, and δ
l
≜
s
l
-
z
l for l
=
1
,
…
,
4. Based on (12), t
0
≥
|
t
1
| and we can rewrite minimization of (16) as minimization of ε
≜
γ
/
t
0
-
t
1 which is decomposable into sum of positive parts:(17)
ε
=
∑
l
=
1
4
δ
l
2
+
λ
1
-
λ
δ
1
+
j
δ
2
+
μ
δ
3
+
j
δ
4
2
,where μ
≜
sign
t
1
e
j
θ and sign
· stands for the signum function. In (17), the parts δ
l
l
=
1
4 are independent of each other which allows us to reduce the search space effectively, and the purpose of the third part is to represent interference between the other parts.By assuming that the minimum of (17) is smaller than r
2, we deduce that δ
l
<
r for l
=
1
,
…
,
4. Therefore, the output of the ML decoder has to be located within corresponding intervals z
l
-
r
,
z
l
+
r which reduces the search spaces effectively. The ML metric (16) for the remaining members is incrementally evaluated piece by piece to remove more inappropriate members and finally we obtain symbols s
~
1
=
s
~
1
+
j
s
~
2 and s
~
3
=
s
~
3
+
j
s
~
4 which minimize the ML metric. These steps for an M
2-QAM constellation are demonstrated as a pseudocode in Pseudocode 1. In this pseudocode, cardinality of set R is indicated by R
c, the mth member of this set is denoted by R
m, and R
l
≜
a
∈
R
:
a
-
z
l
<
r for l
=
1
,
…
,
4.Pseudocode 1:Pseudocode of search stage of proposed method.
γ
th
=
1
-
λ
r
2;
ν
=
1
/
1
-
λ;
FORm
1
=
1,2
,
…
,
R
1
c
δ
1
=
R
1
m
1
-
z
1;
ε
1
=
δ
1
2;
FORm
2
=
1,2
,
…
,
R
2
c
δ
2
=
R
2
m
2
-
z
2;
ε
2
=
ε
1
+
δ
2
2;
IFε
2
>
r
2
CONTINUE;
END
FORm
3
=
1,2
,
…
,
R
3
c
δ
3
=
R
3
m
3
-
z
3;
ε
3
=
ε
2
+
δ
3
2;
IFε
3
>
r
2
CONTINUE;
END
FORm
4
=
1,2
,
…
,
R
4
c
δ
4
=
R
4
m
4
-
z
4;
ε
4
=
ε
3
+
δ
4
2;
IFε
4
>
r
2
CONTINUE;
END
κ
1
=
δ
1
δ
3
+
δ
2
δ
4;
κ
2
=
δ
2
δ
3
-
δ
1
δ
4;
γ
=
ε
4
+
τ
1
κ
1
+
τ
2
κ
2;
IFγ
>
γ
th
ε
=
ν
γ;
r
=
ε;
γ
th
=
γ;
s
~
1
=
R
1
m
1
+
j
R
2
m
2;
s
~
3
=
R
3
m
3
+
j
R
4
m
4;
END
END
END
END
ENDThe proposed method can be extended to other constellations with arbitrary distribution of signal points. Under this condition, the real part of a symbol is related to its imaginary part and therefore they are examined together.


## 3.2. Algorithm Initialization

The proposed method needs to begin with an appropriate initial value forr which should be suitably selected to avoid unnecessary complexity. It is worth mentioning that in the proposed method the initial value selection is approximately similar to the initial radius selection in the sphere method. If the initial value of r is too high, size of search spaces and thus the detection complexity will be raised. Conversely, if value of r is initialized with a very small value, the search spaces include no candidate and no symbol will be detected. Under this situation, we have to increase the value of r and apply our method again till symbols are detected. In this letter, we set the initial value of r to r
initial
=
d
min
⁡
/
2, where d
min
⁡ indicates the minimum distance between two distinct constellation points. In this case, search region of each symbol contains just one candidate point which is almost the best possible choice for moderate to high SNRs. As will be shown in Section 4, this type of initialization ensures that the proposed decoder achieves low complexity.


## 3.3. Complexity Analysis

The decoder operation can be divided into precomputation and search stages. The initial value of variables and candidate points are obtained by performing about64
M
R
+
29 real additions, 40
M
R
+
31 multiplications, and four divisions during the first stage. In addition, the proposed decoder on average employs about 8
log
⁡
2
⁡
M and 8
M relational operators for an M-ary QAM and other constellations, respectively.The complexity of the search stage depends on complex Gaussian noises. From (8), we infer that z
1
=
s
1
+
σ
n
1 and z
3
=
s
3
+
ϱ
/
σ
e
-
j
θ
n
1
+
σ
′
n
3, where s
1 and s
3 are transmitted symbols, n
1 and n
3 are independent complex Gaussian noises with zero means and unit variances, σ
2
=
M
T
α
+
β
/
2
ρ
α
β, ϱ
=
M
T
α
-
β
/
2
ρ
α
β, and σ
′
2
=
2
M
T
/
ρ
(
α
+
β
). Based on the complex Gaussian distribution, the real and imaginary parts of z
1
-
s
1 and z
3
-
s
3 are located within -
ω
,
+
ω with probability P
ω. This probability is given by(18)
P
ω
=
1
2
π
·
∫
-
ω
/
σ
ω
/
σ
∫
-
ω
/
σ
ω
/
σ
Q
-
ω
σ
′
-
η
1
-
Q
ω
σ
′
-
η
1
·
Q
-
ω
σ
′
-
η
2
-
Q
ω
σ
′
-
η
2
e
-
1
/
2
n
2
+
n
′
2
d
n
d
n
′
,where η
1
=
ϱ
/
σ
σ
′
n
cos
⁡
⁡
θ
+
n
′
sin
⁡
θ, η
2
=
ϱ
/
σ
σ
′
n
′
cos
⁡
⁡
θ
-
n
sin
⁡
θ, and Q
u
=
1
/
2
π
∫
u
∞
exp
⁡
⁡
-
ζ
2
/
2
d
ζ. When ω
≫
σ
′, the value of P
ω can be bounded by(19)
P
ω
>
1
-
2
Q
ω
σ
′
2
1
-
2
Q
4
2
.By assuming that the decoder can truly detects
1 and s
3, the complexity of our pseudocode can be bounded by(20)
C
1,3
≤
c
M
ω
N
ω
,where c is a constant value and M
ω and N
ω are functions that indicate the number of constellation points which are located within the search intervals of s
1 and s
3, respectively. The inequality (19) implies that P
ω gets very close to one for d
min
⁡
/
2
≤
ω
≤
d
min
⁡ and acceptable values of SNRs which results in σ
′
≪
d
min
⁡. Under this scenario, the real and imaginary parts of z
k approach those of s
k, such that very few signal points take place inside the created search regions. This statistic feature reduces the complexity of search stage and makes it become independent of constellation size when SNR is reasonable.The detection complexity ofs
k
k
=
1
4 in the search stage depends on the power of noises which practically become small for reasonable values of SNRs. Under this condition, on average either one or two candidates are selected for evaluation per each dimension, hence requiring about 22–44 additions and 22–44 multiplications for a QAM constellation. This means that complexity of the search stage is low and therefore that of precomputation is taken as the dominant factor.Compared against the sphere detection (SD) method, where the precomputation stage requires about424
M
R
+
28 additions, 432
M
R
+
120 multiplications with real equivalent channel having 8
M
R rows and 8 columns [17], or against the QR-based methods involving about 104
M
R
-
8 additions and 136
M
R
+
112 multiplications for the preparation stage [9], it is obvious that the overall complexity of the proposed model enjoys a clear advantage.


## 3.4. Comparison with Sphere

The SD method reformulates the complex ML metric of (6) in a real form as y
-
H
s, where y
∈
R
8
M
R
×
1, H
∈
R
8
M
R
×
8, and s
∈
R
8
×
1. Then, after applying Cholesky factorization and solving two linear systems, a new metric is obtained in form of R
z
-
s, where R
∈
R
8
×
8 is an upper triangular matrix and z is the real zero-force equalized vector. Therefore, the algorithm should minimize the following metric for the real entries of s
∈
R
8
×
1:(21)
∑
i
=
1
8
∑
j
=
i
8
r
i
,
j
z
j
-
s
j
2
=
r
8,8
z
8
-
s
8
2
+
r
7,7
z
7
-
s
7
+
r
7,8
z
8
-
s
8
2
+
⋯
+
r
1,1
z
1
-
s
1
+
r
1,2
z
2
-
s
2
+
⋯
+
r
1,8
z
8
-
s
8
2
,where r
i
,
j, z
j, and s
j are entries of r, z, and s, respectively. This equation consists of eight positive terms which are dependent on each other. This means that the search spaces of s
i’s (for i
=
1
,
…
,
8) are dependent on the values of s
i
+
1
,
s
i
+
2
,
… and s
8 while in the decomposed metric (17) of the proposed method, all terms are independent of each other except the last term. This fact helps us to prepare the search spaces individually and reduce their sizes more efficiently which is not possible with the SD method. Also, the SD algorithm requires Cholesky factorization and two linear systems solving which results in higher complexity.


## 4. Simulation Results

In order to evaluate performance of the proposed decoder experimentally, authors simulated a QOSTBC system with Rayleigh channel model under different constellations using four transmit antennas and one receive antenna. As mentioned in Section3, the complexity of the algorithm depends on the initial value. Figure 1 clearly illustrates the impacts of initial value selection on average complexity for different types of constellation when the BER is approximately 10
-
4 and the constellations have unit average energy. From Figure 1 it is evident that complexity is reduced when initial value of r is selected to be about d
min
⁡
/
2. For the remainder of this section, we set the initial value of r as r
initial
=
d
min
⁡
/
2 which results in a reasonably acceptable complexity.Figure 1
The relation between average complexity and initial value.The required number of real additions and multiplications by the proposed method and those of several state-of-the-art works are tabulated in Tables1 and 2. These results show that the numbers by the proposed method are lower than those by the competitors and that they remain almost unaltered for different constellations. For example, when bit error rate (BER) is about 10−4, complexity of our method for the given QAMs reduces to about 118 addition and 96 multiplication operations, respectively, which is comparatively lower than that of the other solutions even with smaller constellation size. This is a good indication of the superiority of the new algorithm. Moreover, Figure 2 charts BERs of the proposed and ML decoders which illustrates that it is quite possible to arrive at a solution capable of optimum performance at very low complexity.Table 1
Average number of additions and multiplications for the proposed method and several BERs.
Const.
16-QAM
64-QAM
256-QAM
1024-QAM
BER
+
×
+
×
+
×
+
×
10−2
143.6
119.9
151.5
126.6
159.7
133.8
163.6
137.1
10−3
122.2
99.8
124.3
101.7
126.9
104.0
127.7
104.7
10−4
116.2
94.1
116.9
94.7
117.6
95.4
118.0
95.7
Const.
QPSK
8-PSK
8-APSK
16-APSK
BER
+
×
+
×
+
×
+
×
10−2
135.7
111.7
150.6
124.9
139.7
114.2
154.2
127.1
10−3
120.3
97.8
121.7
99.1
120.3
97.5
124.2
101.2
10−4
115.6
93.6
115.9
93.7
115.4
93.2
116.3
94.1Table 2
Average number of additions and multiplications.
# of
16-QAM
64-QAM
256-QAM
+
×
+
×
+
×
[9]
373
469
1311
1179
5637
4302
[10]
327
437
647
443
1479
1445
[11]
232
308
808
1076
3112
4148
[12]
225
332
225
348
225
364Figure 2
Error performance of ML and proposed method.


## 5. Conclusion

In this letter, an innovative fast maximum-likelihood (ML) decoder for QOSTBC was introduced. The proposed method exploited structure of QAM constellations in order to develop an algorithm at low computational complexity. By using new algorithm, the ML metrics was decomposed into a sum of independent positive parts and an interference part. Given that metrics within the positive parts are independent of each other, the proposed technique substantially limited the search area and hence complexity of detection decreased exponentially. It was demonstrated that for bit error rate of10
-
4, the resulting complexity remained almost unaltered for different constellations and was less than those of state-of-the-art schemes. Also, the proposed scheme can be extended to work with any constellation type.



---

*Source: 654865-2015-05-10.xml*