IEICE TRANS. FUNDAMENTALS, VOL.E87–A, NO.10 OCTOBER 2004

2571

PAPER

Special Section on Information Theory and Its Applications

Two Methods for Decreasing the Computational Complexity of
the MIMO ML Decoder
Takayuki FUKATANI† , Nonmember, Ryutaroh MATSUMOTO†a) , and Tomohiko UYEMATSU† , Members

SUMMARY
We propose use of QR factorization with sort and Dijkstra’s algorithm for decreasing the computational complexity of the spheredecoder that is used for ML detection of signals on the multi-antenna fading
channel. QR factorization with sort decreases the complexity of searchingpart of the decoder with small increase in the complexity required for preprocessing part of the decoder. Dijkstra’s algorithm decreases the complexity of searching part of the decoder with increase in the storage complexity.
The computer simulation demonstrates that the complexity of the decoder
is reduced by the proposed methods significantly.
key words: MIMO fading channel, maximum likelihood detection, spheredecoder, lattice

1.

Introduction

In the multi-antenna mobile communication, it is wellknown that use of multiple transmit and receive antennas
linearly increases the channel capacity of a frequency nonselective fading channel with the channel state information(CSI) known at the receiver [1], [2]. In the case of the uncoded multi-antenna systems, the computational complexityof the naive maximum-likelihood (ML) decoding algorithm
grows exponentially with the number of transmit antennas,
so we need an eﬃcient algorithm to implement ML decoding. On the multi-antenna fading channel, if the receiver
has CSI, the receiver can compute the set of ideal received
signal points considering only influence of the fading anddisregarding influence of the additive noise. So when thenoise at each receive antenna is the additive white Gaussian,
to implement ML decoding we search for the ideal received
signal point closest to the actual received signal point. By
regarding the ideal received points as lattice points, the ML
decoding problem is reduced to the classical closest lattice
point search problem. Fincke and Pohst proposed an efficient algorithm for that problem [3], and recently it wasapplied to the decoding problem and called sphere decoder(SD) [4].
SD can be divided into the two parts. The first partcomputes QR factorization (or Cholesky factorization) of
the fading matrix. The second part computes the ML estimate of transmitted signal from the received signal and QR
factorization. We call the first part preprocessing part andthe second part searching part. In this paper we propose QR
Manuscript received January 16, 2004.
Manuscript revised April 14, 2004.
Final manuscript received June 7, 2004.
†
The authors are with the Department of Communications andIntegrated Systems, Tokyo Institute of Technology, Tokyo, 1528552 Japan.
a) E-mail: ryutaroh@it.ss.titech.ac.jp

factorization with sort and use of Dijkstra’s algorithm for
decreasing the computational complexity of SD. QR factorization with sort gives an eﬃcient order of decisions on signal components. It reduces the complexity of searching partwith increase in the complexity of preprocessing part. Dijkstra’s algorithm is an eﬃcient algorithm used to solve theshortest path problem in the graph. We apply this algorithm
to searching part. It reduces the complexity of searchingpart with increase in the storage complexity.
The QR factorization with sort modifies only preprocessing part and use of Dijkstra’s algorithm modifies only
searching part. Thus these improvements are independentand can be used together or alone.
This paper is organized as follows: Sect. 2 introduces
the channel model of the multi-antenna fading channel andshows how the original SD works. Section 3 introduces QR
factorization with sort and Sect. 4 proposes application of
Dijkstra’s algorithm to SD. Section 5 shows the comparison
between the complexity of the original SD and that of SD
using the proposed methods by the computer simulations.
These simulations show that the proposed methods decrease
the complexity of a decoder significantly.
2.

Original Sphere Decoder

2.1 Channel Model
Suppose that we have the uncoded system with t transmit
antennas and r receive antennas, that the noise at each receive antenna is the additive white Gaussian, and that thereceiver has CSI. At the transmitter, information sources aredemultiplexed into t substreams, and transmitted by transmit
antennas. Let a be a (t × 1) vector consisting of complex envelopes of transmitted signals with the signal constellation
S, M the (r × t) fading matrix whose (k, j) entry is a complex
fading coeﬃcient between j-th transmit antenna and k-th receive antenna, ν a (r × 1) complex vector whose component
is noise at each receive antenna, and x a (r × 1) complex
vector whose component is the received signal component
at each receive antenna. The model of this channel is written as
x = Ma + ν(a ∈ St ).

(1)

On the channel described by Eq. (1), when the componentsof ν are independent complex Gaussian random variables,
the ML decoding problem can be reduced to the closest
lattice point search problem for the set of lattice points

IEICE TRANS. FUNDAMENTALS, VOL.E87–A, NO.10 OCTOBER 2004

2572

{Ma | a ∈ St } and a received signal point x. See [4], [5]for details.
We also remark that when we use linear space-timecoding, the ML decoding problem is reduced to the closest lattice point search problem by describing the channel as
Eq. (1) [6].
2.2 Algorithm
In this section, we show how the original SD works when t ≤r. Fincke and Pohst’s original method treats real numbers,
and we can treat complex numbers in the almost same way[5].
To implement ML decoding on the channel describedby Eq. (1), we must compute the ML transmit signal â =(â1 , · · · , ât )T equal toargmin x − M â .

(2)

â∈St

To compute Eq. (2), SD considers a sphere with center at
the received signal in the complex Euclidean space. If there
are lattice points in the sphere, the closest point is in thesphere. SD takes a suitable value as the radius of sphere,
and searches for lattice points in the sphere.
First we compute QR factorization of M and obtain an
upper triangular matrix R and a unitary matrix Q with M =QR. Since Q is a unitary matrix,x − M â 2 = Q∗ x − Q∗ M â 2 = Q∗ x − Râ 2 .

(3)

Let ρ = Q∗ x = (ρ1 , · · · , ρr )T , C the square of suitable radiusand ri j the (i, j) element of R. The lattice points M â thatsatisfyx − M â 2 = Râ − ρ 2

2

t 
t





=
ri j â j 
rii âi − ρi −

i=1 
j=i+1
r

+
ρ2i < C(4)

are in the sphere. Satisfying Eq. (4) is equivalent to satisfying the following inequalities for all k = 1, · · · , t:

2

t




 < Crkk âk − ρi −
r
â
k
j
j




j=k+1

2

t 
t





−
ri j â j 
(5)
rii âi − ρi −


j=i+1

where C = C − ri=t+1 ρ2i . SD computes â satisfying Eq. (4)by deciding âi in order of i = t, · · · , 1 from Eq. (5).
To simplify Eq. (5), we define S k , and Dk as


t



rk j â j  /rkk
(6)
S k = ρi −
j=k+1

(7)

Then Eq. (5) is written by S k and Dk as|âi − S i |2 < (C − Di )/|rii |2 .

(8)

The candidates of âi satisfying Eq. (8) are in the circle with the center S i and the radius (C − Di )/|rii |2 on thecomplex plane. If there is no candidate of âi , SD goes backto decision on âi+1 . If there are some candidates, we mustchoose one of them. To reduce the complexity of searching part, a method starting with âi nearest to S i among the
all candidates is proposed in [7]. When SD only treats real
numbers, it is clear which âi is nearest to S i . But when SD
treats complex numbers, finding âi nearest to S i needs tocompute |âi − S i |2 for all âi ∈ S and not necessarily reduces
the complexity. So we employ another method. In Sect. 5,
SD chooses âi in the increasing order of | (âi − S i )| and, if
there are two or more candidates of âi with the same valueof | (âi − S i )|, SD chooses âi with a smaller |(âi − S i )|,where (·) denotes the real part and (·) denotes the imaginary part. When (âi − S i )2 is larger than (C − Di )/|rii |2 ,SD concludes that there is no âi in the circle any more.
When â satisfies all inequalities (8), SD concludes that
M â is a lattice point in the sphere. Then the new radius is set
to M â−x and SD repeats the same operations until there isno lattice point in the sphere, and the last point is the closest
point. If there is no lattice point in the sphere with the radius
given first, SD will declare the erasure of signal or increase
the radius.
3.

QR Factorization with Sort

3.1 Changing the Order of Decisions on âi

i=t+1

i=k+1


2

t 
t





ri j â j  .
Dk =rii âi − ρi −
j=i+1
i=k+1 In the previous section, we obtained the inequality with eachsignal component âi . In searching part, the computational
complexity largely depends on the order of decisions on âi .
In this section, we consider an eﬃcient order of decisions
on âi .
For a permutation σ and M = (v1 , · · · , vt ), Eq. (1) isequivalently described by P = (vσ(1) , · · · , vσ(t) ) and p =(aσ(1) , · · · , aσ(t) )T as
x = Pp + ν.

(9)When SD processes the channel described as Eq. (9), theorder of decisions on âi follows the order of components of
p. So we can change the order of decisions on âi arbitrarily
by σ. SD can obtain p̂ that is the ML estimate of p, and one
can get the ML estimate of the original channel (1) from p̂
by the inverse permutation σ−1 .
Next we consider the eﬃcient order of decisions on âi .
The number of candidates of âi satisfying Eq. (8) is proportional to(C − Di )/|rii |2 .

(10)

FUKATANI et al.: TWO METHODS FOR DECREASING THE COMPUTATIONAL COMPLEXITY OF THE MIMO ML DECODER

2573

Intuitively we can reduce the complexity of searching partby changing the order of decisions on âi so that the value ofEq. (10) is small for large i, because âi are decided in orderof i = t, · · · , 1. Because the value of Eq. (10) is inversely
proportional to |rii |2 , we can reduce the complexity by constructing the matrix R so that |rii | takes the large value forlarge i.
Now we propose QR factorization with sort to computethe eﬃcient order of decisions on âi . QR factorization computes rii in increasing order of i. QR factorization with sort
permutes columns of the factorized matrix before each computation of rii such that rii is minimized. QR factorization
with sort is used for decreasing the error probability of thenulling and canceling decoder in [8]. In this paper, we use
QR factorization with sort for decreasing the complexity of
ML decoder without changing the error probability.
In [9], it is claimed that the order maximizing
min1≤i≤t |rii | is optimal for reducing the computational complexity of searching part. But the computation of this order requires QR factorizations t2 /2 times. In the mobile
environment, the fading matrix M often changes. So thecomputational complexity of preprocessing part proposed in[9] is not negligible because preprocessing part is computed
whenever fading matrix M changes. In [3], [9], it is also said
that we can reduce the complexity of SD by reordering decisions on âi according to the norm of corresponding basis
vectors. In Sect. 5, we compare QR factorization with sortand other methods by computer simulations.
3.2 Algorithm
In this subsection, we show how QR factorization with sortworks. QR factorization with sort gives a permutation realizing an eﬃcient order of decisions on âi and QR factorization for the permuted matrix P in Eq. (9). The following algorithm is almost the same as [8]. The method in [8] is basedon Gram-Schmidt algorithm, and our method is based on
Householder method. It is known that Householder method
is numerically more stable than Gram-Schmidt algrithm[10].
The ordinary QR factorization of M can be sketched asfollows: Compute a unitary matrix Q1 such that the first column of Q1 M is (r11 , 0, · · · , 0)T . Let M2 be ((r − 1) × (t − 1))submatrix of Q1 M with the first column and the first row
of Q1 M removed. Compute a unitary matrix Q2 such thatthe first column of Q2 M2 is (r22 , 0, · · · , 0)T . The computation process is recursively repeated until i = t. See [10] fordetails.
We will describe QR factorization with sort. Observethat in the ordinary QR factorization r11 is equal to the normof the first column vector of M. In order to minimize r11 ,we replace the first column of M with the column with minimum norm. Let M be the column replaced version of M.
Compute a unitary matrix Q1 such that the first column of
Q1 H is (r11 , 0, · · · , 0)T . Let M̃2 be ((r − 1) × (t − 1)) submatrix of Q1 M with the first column and the first row of Q1 M
removed. Replace the first column of M̃2 with the column

with minimum norm in M̃2 . Let M2 be the column replaced
version of M̃2 . Compute a unitary matrix Q2 such that thefirst column of Q2 H2 is (r22 , 0, · · · , 0)T . The computation
process is recursively repeated until i = t.
With this process we get a QR factorization Q̂R̂ of thecolumn permuted matrix P of M. If we apply searchingpart in Sect. 2 to Q̂R̂, then we get more eﬃciently the ML
estimate p. The ML estimate of â can be obtained by the
inverse permutation.
4.

Dijkstra’s Algorithm

In this section we apply Dijkstra’s algorithm to searchingpart to reduce the complexity of searching part with increasein the storage complexity. Dijkstra’s algorithm is an eﬃcientalgorithm to find the shortest path from a point to a destination in a weighted directed graph [11]. In this algorithm,
the vertices on the graph are searched for in order of theirdistance from the departure.
The decisions on âi essentially constructs a tree where
nodes at k-th level are correspond to the candidates of ât−k+1[5], and the root is placed at the 0-th level. Set the weight ofthe branch from the node âi to its parent to

2

t




 = r2 |âi − S i |2 .
rii âi − ρi −
r
â
(11)
i,
j
j
ii




j=i+1
Then the distance of node âi from the root is equal to Di−1 .
The nodes having the same parent are arranged in the increasing order of the distance from left to right.
If we use Dijkstra’s algorithm to find the shortest pathfrom the root to one of nodes at the bottom level, we can get
the node with the minimum D0 = x−M â 2 among all nodes
at the bottom level and it corresponds to the ML estimate.
We show Dijkstra’s algorithm.
1. Create an empty priority queue for nodes. The priority
is the distance from the root.
2. Insert the leftmost node at the first level into the priority
queue.
3. Select the node A having smallest distance in the priority queue and remove it from the priority queue. If thelevel of A is t, finish this algorithm.
4. Insert the leftmost A’s child node into the priority
queue.
5. Insert the right neighboring node of A into the priority
queue.
6. Go back to Step 3
Because the node selected in Step 3 has the smaller distancethan the nodes selected later, the node at the bottom levelselected first has the minimum value of D0 among all nodes
at the bottom level.
In the sequel, we refer to SD not using Dijkstra’s algorithm as SD, and SD using Dijkstra’s algorithm as Dijkstra’salgorithm.
Figure 1 shows an example of the order of search by
Dijkstra’s algorithm and SD. The values in circles show theIEICE TRANS. FUNDAMENTALS, VOL.E87–A, NO.10 OCTOBER 2004

2574

Fig. 1The order of search by Dijkstra’s algorithm and the original SD.

distance from the root. The numbers in upper rectangles
show the order by Dijkstra’s algorithm and the numbers inlower rectangles show the order by SD. SD is the depth
first search algorithm for a tree. In this case, the numberof searched nodes is 5 by Dijkstra’s algorithm and is 8 bySD.
Dijkstra’s algorithm searches for only the nodes whose
distance is smaller than the minimum distance of nodes atthe bottom level, but SD searches for the node whose distance is smaller than C and C must be greater than the minimum distance of nodes at the bottom level in order for ML
detection succeed. So the number of searched nodes of Dijkstra’s algorithm is smaller than that of SD. However because
we use the priority queue in Dijkstra’s algorithm, the storage
complexity increases. In addition, Dikstra’s algorithm does
not require the radius of the sphere to be initially set, and it
always finds out ML estimate without retrying to search fora lattice point with increased radius.
Arranging the nodes having the same parent according
to the distance needs to compute |âi − S i |2 of nodes. Instead of doing this, our algorithm considers the candidatesof (ât−k+1 ) and the candidates of (ât−k+1 ) separately in
Sect. 5. Then the level of tree is equal to 2t excluding theroot, and arranging the nodes having the same parent only
needs to compute | (âi ) − (S i )| and |(âi ) − (S i )|.
5.

Computer Simulation

In this section, we show how much the complexity ofsearching part is reduced by QR factorization with sort and
Dijkstra’s algorithm, the complexity of preprocessing partis increased by QR factorization with sort, and the storage
complexity is increased by Dijkstra’s algorithm over an uncoded multi-antenna fading channel.
The radius of sphere used by SD is defined so that
Pr{transmit point is in sphere} = Pr{C > |ν|2 }≈ 0.99(12)

where C is the square of radius and ν is a vector whose element is noise at each receive antenna [5]. When there is no
lattice point in sphere, we increase the radius to C + 1, andcontinue until a lattice point is found.
5.1 The System Model
We consider the following system model.

Fig. 2The complexity of searching part for each receiving point.

• The number of transmit antennas is equal to the numberof receive antennas.
• The fading coeﬃcients obey the CN(0, 1) distribution.
• The signal constellation for each transmit antenna is
64-QAM and all signals are drawn according to the uniform i.i.d. distribution.
5.2 The Computer Simulations
In this subsection we show comparisons of complexities ofthe proposed methods and other variants of SD. We remarkthat all methods in this subsection are ML decoding andhence the error rates of these ML decoding methods are thesame. First we show the comparison of the complexities of
SD not reordering decisions on âi (SD), SD reordering decisions on âi according to norms of basis vectors (Norm-SD)[3], [9], SD reordering decisions on âi so that min1≤i≤t |rii |is maximized (Optimal-SD) [9] and SD with the QR factorization with sort (QR sort-SD). The value of SNR is set
to 26 dB. In these simulations we use the average numberof real multiplications and divisions for each processing as
the measure of complexity, and in these simulations we use
the complex multiplications that needs three real multiplications and seven real additions, and the complex divisions
that needs five real multiplications, two real divisions, andnine real additions [12]. Figure 2 shows the complexity ofsearching part and Fig. 3 shows the complexity of preprocessing part. When the number of transmit antennas is 8 thecomplexity of searching part is reduced about 55 percent
from the original SD by QR factorization with sort. However Fig. 3 shows the complexity of preprocessing part increases about 10 percent. Figure 4 shows the total complexity of SD for 10 transmissions with the same fading matrix.
In this case the complexity of SD is reduced about 60 percent from the original SD by QR factorization with sort.
Next we show the comparison of the complexities
of SD (SD), Dijkstra’s algorithm (Dijkstra), and both ofthem using QR factorization with sort (QR sort-SD, QR
sort+Dijkstra).
The number of antennas is set to 8. Figure 5 shows thatthe complexity of searching part and Fig. 6 shows the cu-

FUKATANI et al.: TWO METHODS FOR DECREASING THE COMPUTATIONAL COMPLEXITY OF THE MIMO ML DECODER

2575

Fig. 3Fig. 6The complexity of preprocessing part for each fading matrix.

6.

Fig. 4 The complexity of SD for 10 transmissions with the same fading
matrix.

The cumulative distribution of the size of priority queue.

Conclusion

We proposed the QR factorization with sort and use of Dijkstra’s algorithm as methods for decreasing the computational complexity of the sphere decoder. QR factorization
with sort reduces the complexity of searching part of a decoder with little increase in the complexity of preprocessing
part of a decoder. Because the preprocessing part is computed once for each fading matrix and the increase in thecomplexity of preprocessing part is little enough, the total
complexity of SD can be reduced. Dijkstra’s algorithm reduces the complexity of searching part of a decoder withincrease in the storage complexity. By these reductions of
the complexity, the proposed methods enable us to implement ML decoding for the multi-antenna system with a lager
number of transmit antennas.
References

Fig. 5The complexity of searching part for each receiving point.

mulative distribution of the size of priority queue with QR
factorization with sort. When SNR is 26 dB, the complexityof searching part is reduced about 25 percent from the original SD by Dijkstra’s algorithm, and is reduced about 65
percent from the original SD by combining QR factorization with sort and Dijkstra’s algorithm. Figure 5 also showsthat Dijkstra’s algorithm is much faster than SD when SNR
is low.

[1] E. Telatar, “Capacity of multi-antenna Gaussian channels,” Europ.
Trans. Telecommun., vol.10, pp.585–595, Nov. 1999.
[2] G.J. Foschini, “Layered space-time architecture for wireless communication in a fading environment when using multi-element antennas,” Bell Labs Tech. J., vol.1, pp.41–59, 1996.
[3] U. Fincke and M. Pohst, “Improved methods for calculating vectorsof short length in a lattice, including a complexity analysis,” Math.
Comput., vol.44, pp.436–471, April 1985.
[4] E. Viterbo and J. Boutros, “A universal lattice code decoder for fading channels,” IEEE Trans. Inf. Theory, vol.45, no.5, pp.1639–1642,
July 1999.
[5] B. Hassibi and H. Vikalo, “On the sphere decoding algorithm: Part
I and II,” http://www.systems.caltech.edu/EE/Faculty/babak/pubs/
sphere.html[6] M.O. Damen, A. Chkeif, and J.C. Belfiore, “Lattice code decoder for
space-time codes,” IEEE Commun. Lett., vol.36, no.5, pp.166–168,Jan. 2000.
[7] A.M. Chan and I. Lee, “A new reduced-complexity sphere decoder
for multiple antenna systems,” Proc. ICC, vol.1, pp.460–464, April
2002.
[8] D. Wubben, R. Bohnke, J. Rinas, V. Kuhn, and K.D. Kammeyer,“Eﬃcient algorithm for decoding layered space-time codes,” Electron. Lett., vol.37, pp.1348–1350, Oct. 2001.
[9] M.O. Damen, H.E. Gamal, and G. Caire, “On maximum-likelihood
detection and the search for the closest lattice point,” IEEE Trans.
Inf. Theory, vol.49, no.10, pp.2389–2402, Oct. 2003.

IEICE TRANS. FUNDAMENTALS, VOL.E87–A, NO.10 OCTOBER 2004

2576

[10] J. Stoer and R. Bulirsch, Introduction to numerical analysis, 2nd ed.,pp.190–197, Springer-Verlag, 1983.
[11] A.V. Aho, J.E. Hopcroft, and J.D. Ullman, Data Structures and Algorithms, Chapter 6.3, Addison-Wesley, Reading, MA, 1983.
[12] D.E. Knuth, The art of computer programming, vol.2, 2nd ed., Problem 6.41, Addison-Wesley, Reading, MA, 1981.

Takayuki Fukatani
was born in Chiba,
Japan in 1981, and received the B.E. degreefrom Tokyo Institute of Technology in 2004.
Since April 2004, he has been a graduate student
in the Department of Computer Science, Graduate School of Information Science and Engineering, Tokyo Institute of Technology.

Ryutaroh Matsumoto
was born in Nagoya, Japan, on November 29, 1973. He received the B.E. degree in computer science, theM.E. degree in information processing, and the
Ph.D. degree in electrical and electronic engineering, all from Tokyo Institute of Technology,
Japan, in 1996, 1998, 2001, respectively. He
was an Assistant Professor from 2001 to 2004,
and has been an Associate Professor since 2004
in the Department of Communications and Integrated Systems of Tokyo Institute of Technology. Dr. Matsumoto received the Young Engineer Award and the Excellent
Paper Award from IEICE as well as the Ericsson Young Scientist Award
from Ericsson Japan in 2001.

Tomohiko Uyematsu
received the B.E.,
M.E. and D.E. degrees from Tokyo Institute ofTechnology in 1982, 1984 and 1988, respectively. From 1984 to 1992, He was with the Department of Electrical and Electronic Engineering of Tokyo Institute of Technology, first as research associate, next as lecturer, and lastly as
associate professor. From 1992 to 1997, he waswith School of Information Science of Japan
Advanced Institute of Science and Technology
as associate professor. Since 1997, he returnedto Tokyo Institute of Technology as associate professor, and currently he iswith the Department of Communications and Integrated Systems as professor. In 1992 and 1996, he was a visiting researcher at the Centre Nationalde la Recherche Scientifique, France and Delft University of Technology,
Netherlands, respectively. He received Shinohara Memorial Young Engineer Award in 1989, and the Best Paper Award in 1993, 1996, and 2002
both from IEICE. His current research interests are in the areas of information theory, especially Shannon theory and multi-terminal information
theory. Dr. Uyematsu is a member of IEEE.