text:
\section{INTRODUCTION}
Multiple-input multiple-output (MIMO) systems have drawn substantial research and development because they offer high spectral efficiency and performance in a given bandwidth. In such systems, the eventual goal is to minimize the bit error rate (BER) for a given signal-to-noise ratio (SNR). A number of different MIMO systems exist. Most of these systems result in optimum decoding techniques that are complicated. Therefore a number of decoding algorithms with different complexity-performance trade-offs have been introduced. Linear detection methods such as zero-forcing (ZF) or minimum mean squared error (MMSE) provide linear complexity, however their performance are suboptimal. Ordered successive interference cancellation decoders such as vertical Bell Laboratories layered space-time (V-BLAST) algorithm, show slightly better performance compared to ZF and MMSE, but suffer from error propagation and are still suboptimal \cite{Burg_VLSI_SDA}. It is well-known that maximum likelihood (ML) detection is the optimum method. However, the complexity of ML algorithm in MIMO systems increases exponentially with the number of possible constellation points for the modulation scheme, making the algorithm unsuitable for practical purposes \cite{Zimm_SD}. Sphere decoding (SD), on the other hand, is proposed as an alternative for ML that provides optimal performance with reduced complexity \cite{Jalden_SD}.

Although its complexity is much smaller than ML decoding, there is room for complexity reduction in conventional SD. To that end, several complexity reduction techniques for SD have been proposed. In \cite{Cheng_IR_SD} and \cite{Han_SD_IR}, attention is drawn to initial radius selection strategy, since an inappropriate initial radius can result in either a large number of lattice points to be searched, or a large number of restart actions. In \cite{Hassibi_SD
, this complexity is attacked by making a proper choice to update the sphere radius. In \cite{Damen_MLD}, the Schnorr-Euchner (SE) strategy is applied for SD, which executes intelligent enumeration of candidate symbols at each level to reduce the number of visited nodes when the system dimension is small \cite{Rekaya_MLLD}. Channel reordering techniques can also be applied to reduce the number of visited node \cite{Rekaya_MLLD}, \cite{Azzam_SD_NLR}, \cite{Azzam_SD_RLR}. Other methods, such as the K-best lattice decoder \cite{Wong_K-Best}, \cite{Huynh_TLS_SDA}, can significantly reduce the complexity at low SNR, but with the tradeoff of BER performance degradation.

In this paper, the complexity of SD is improved efficiently by reducing the number of operations required at each node to obtain ML solution for flat fading channels. This complexity reduction is achieved by deconstructing the decoding metric in order to reduce the computations to their minimum and exploiting the structure of a lattice representation of SD \cite{Azzam_SD_NLR}, \cite{Azzam_SD_RLR}. In simulations, $2\times2$ and $4\time4$ MIMO systems with $4$-QAM and $64$-QAM have been studied. In these systems, the reduction in the number of real additions is in the range of $40-75\%$, and the reduction in the number of real multiplications is in the range of $70-90\%$, without any change in performance. The complexity gains increase with the MIMO system dimension or the modulation alphabet size.

The remainder of this paper is organized as follows: In Section II, the problem definition is introduced and a brief review of conventional SD algorithm is presented. In Section III, A new technique to implement the SD algorithm with low computational complexity is proposed, and the mathematical derivations for the complexity reduction is carried out. In Section IV, complexity comparisons for different number of antennas or modulation schemes are provided. Finally, a conclusion is provided in Section V.

\section{CONVENTIONAL SPHERE DECODER}
MIMO systems using square quadrature amplitude modulation (QAM) with $N_t$ transmit and $N_r$ receive antennas are considered, and the channel is assumed to be flat fading. Then, the input-output relation is given by
\begin{equation}
{\bf r}={\bf H}{\bf s}+{\bf v}, \label{eq1}
\end{equation}
where ${\bf r}\in\mathbb{C}^{N_r}$ is the $N_r$ dimensional received vector symbol and $\mathbb{C}$ denotes the set of complex numbers; ${\bf H}\in\mathbb{C}^{N_r{\times}N_t}$ is the channel matrix whose channel coefficients are independent and identically distributed (i.i.d.) zero-mean, unit-variance complex Gaussian random variables; ${\bf s}\in\mathbb{C}^{N_t}$ is an $N_t$ dimensional transmitted complex vector with each element in square QAM format; and ${\bf v}\in\mathbb{C}^{N_r}$ is a zero-mean white Gaussian noise vector with variance matrix $\sigma^2{\bf I}$.

Assuming ${\bf H}$ is known at the receiver, ML detection is
\begin{equation}
\hat{\bf s}=\arg \min_{{\bf s}\in\chi^{N_t}}\Vert {\bf r}-{\bf Hs}\Vert^2, \label{eq2}
\end{equation}
where $\chi$ denotes the sample space for QAM modulation scalar symbols. For example,  $\chi=\left\lbrace -3, -1, 1, 3\right\rbrace ^2$ for $16$-QAM.

Solving (\ref{eq2}) is known to be NP-hard, given that a full search over the entire lattice space is performed \cite{Hassibi_EC_ILSP}. SD, on the other hand, solves (\ref{eq2}) by searching only lattice points that lie inside a sphere of radius $\delta$ centering around the received vector $\bf r$.

A frequently used solution for the QAM-modulated signal model is to decompose the $N_r$-dimensional complex-valued problem (\ref{eq1}) into a $2N_r$-dimensional real-valued problem, which can be written as
\begin{equation}
\begin{bmatrix}
\Re \left\lbrace {\bf r} \right\rbrace \\
\Im \left\lbrace {\bf r} \right\rbrace
\end{bmatrix}
=
\begin{bmatrix}
\Re \left\lbrace {\bf H} \right\rbrace & -\Im \left\lbrace {\bf H} \right\rbrace  \\
\Im \left\lbrace {\bf H} \right\rbrace & \Re \left\lbrace {\bf H} \right\rbrace
\end{bmatrix}
\begin{bmatrix}
\Re \left\lbrace {\bf s} \right\rbrace \\
\Im \left\lbrace {\bf s} \right\rbrace
\end{bmatrix}
+
\begin{bmatrix}
\Re \left\lbrace {\bf v} \right\rbrace \\
\Im \left\lbrace {\bf v} \right\rbrace
\end{bmatrix},
\label{eq3}
\end{equation}
where $\Re \left\lbrace {\bf r} \right\rbrace$ and $\Im \left\lbrace {\bf r} \right\rbrace$ denote the real and imaginary parts of ${\bf r}$ respectively \cite{Jalden_SD}, \cite{Hassibi_EC_ILSP}. Let
\begin{equation}
{\bf y}=
\begin{bmatrix}
\Re \left\lbrace {\bf r} \right\rbrace^T &  \Im \left\lbrace {\bf r} \right\rbrace^T
\end{bmatrix}^{T},
\label{eq4}
\end{equation}
\begin{equation}
\bar{\bf H}=
\begin{bmatrix}
\Re \left\lbrace {\bf H} \right\rbrace & -\Im \left\lbrace {\bf H} \right\rbrace  \\
\Im \left\lbrace {\bf H} \right\rbrace & \Re \left\lbrace {\bf H} \right\rbrace
\end{bmatrix},
\label{eq5}
\end{equation}
\begin{equation}
{\bf x}=
\begin{bmatrix}
\Re \left\lbrace {\bf s} \right\rbrace^T & \Im \left\lbrace {\bf s} \right\rbrace^T
\end{bmatrix}^{T},
\label{eq6}
\end{equation}
\begin{equation}
{\bf n}=
\begin{bmatrix}
\Re \left\lbrace {\bf v} \right\rbrace^T & \Im \left\lbrace {\bf v} \right\rbrace^T
\end{bmatrix}^{T},
\label{eq7}
\end{equation}
then (\ref{eq3}) can be written as
\begin{equation}
{\bf y}=\bar{\bf H}{\bf x}+{\bf n}. \label{eq8}
\end{equation}

Assuming $N_t=N_r=N$ in the sequel, and using the QR decomposition of $\bar{\bf{H}}=\bf{QR}$, where ${\bf R}$ is an upper triangular matrix, and the matrix ${\bf Q}$ is unitary, SD solves
\begin{equation}
\hat{\bf x}=\arg \min_{{\bf x}\in\xi}\Vert \bar{\bf y}-{\bf Rx}\Vert^{2},
\label{eq9}
\end{equation}
where $\bar{\bf y}={\bf Q}^{H}{\bf y}$. Let $\Omega$ denote the sample space for one dimension of QAM-modulated symbols, e.g., $\Omega=\left\lbrace -3,-1,1,3\right\rbrace$ for $16$-QAM, then $\xi$ denotes a subset of $\Omega^{2N}$ whose elements satisfy $\Vert \bar{\bf y}-{\bf Rx}\Vert^{2}<\delta^{2}$.

The SD algorithm can be viewed as a pruning algorithm on a tree of depth $2N$, whose branches correspond to elements drawn from the set $\Omega$ \cite{Azzam_SD_NLR}, \cite{Azzam_SD_RLR}, \cite{Hassibi_EC_ILSP}. Conventional SD implements a depth-first search (DFS) strategy in the tree, which can achieve ML performance.

Conventional SD starts the search process from the root of the tree, and then searches down along branches until the total weight of a node exceeds the square of the sphere radius, $\delta^{2}$. At this point, the corresponding branch is pruned, and any path passing through that node is declared as improbable for a candidate solution. Then the algorithm backtracks and proceeds down a different branch. Whenever a valid lattice point at the bottom level of the tree is found within the sphere, $\delta^{2}$ is set to the newly-found point weight, thus reducing the search space for finding other candidate solutions. In the end, the path from the root to the leaf that is inside the sphere with the lowest weight is chosen to be the estimated solution $\hat{\bf x}$. If no candidate solutions can be found, the tree will be searched again with a larger initial radius.

\section{PROPOSED SPHERE DECODER}

The complexity of SD is measured by the number of operations required per visited node multiplied by the number of visited nodes throughout the search procedure \cite{Hassibi_EC_ILSP}. The complexity can be reduced by either reducing the number of visited nodes or the number of operations to be carried out at each node or both. Making a judicious choice of initial radius to start the algorithm with \cite{Cheng_IR_SD}, \cite{Han_SD_IR}, executing a proper sphere radius update strategy \cite{Hassibi_SD}, applying an improved search strategy \cite{Damen_MLD}, and exploiting channel reordering \cite{Rekaya_MLLD}, \cite{Azzam_SD_NLR}, \cite{Azzam_SD_RLR} can all reduce the number of visited nodes. In this paper, focus is on reducing the average number of operations required at each node for SD.

The node weight is given by \cite{Azzam_SD_NLR}, \cite{Azzam_SD_RLR},
\begin{equation}
w({\bf x}^{(l)})=w({\bf x}^{(l+1)})+w_{pw}({\bf x}^{(l)}), \label{eq10}
\end{equation}
with $l=2N, \cdots, 1$, $w({\bf x}^{(2N+1)})=0$, and $w_{pw}({\bf x}^{(2N+1)})=0$, where ${\bf x}^{(l)}$ denotes the partial vector symbol at layer $l$. The partial weight corresponding to ${\bf x}^{(l)}$ is written as
\begin{equation}
w_{pw}({\bf x}^{(l)})=|\bar{y}_l-\sum^{2N}_{k=l}{R_{l,k}x_k}|^{2}, \label{eq11}
\end{equation}
where $R_{i,j}$ denotes the $(i,j)^{th}$ element of $\bf R$, and $x_i$ denotes the $i^{th}$ element of $\bf x$.

\subsection{Check-Table $\mathbb{T}$}

Note that for one channel realization, both $\bf R$ and $\Omega$ are independent of time. In other words, to decode different received symbols for one channel realization, the only term in (\ref{eq11}) which depends on time is ${\bar y}_l$. Consequently, a check-table $\mathbb{T}$ is constructed to store all terms of $R_{i,j}x$, where $R_{i,j}\neq0$ and $x\in\Omega$, before starting the tree search procedure. Equation (\ref{eq10}) and (\ref{eq11}) imply that only one real multiplication needed instead of $2N-l+2$ for each node to calculate the node weight by using $\mathbb{T}$. As a result, the number of real multiplications can be significantly reduced.

Taking the square QAM lattice structure into consideration, $\Omega$ can be divided into two smaller sets $\Omega_{1}$ with negative elements and $\Omega_{2}$ with positive elements. Take 16-QAM for example, $\Omega=\left\lbrace -3,-1,1,3\right\rbrace$, then $\Omega_{1}=\left\lbrace -3,-1\right\rbrace$ and $\Omega_{2}=\left\lbrace 1,3\right\rbrace$. Any negative element in $\Omega_{1}$ has a positive element with the same absolute value in $\Omega_{2}$. Consequently, in order to build $\mathbb{T}$, only terms in the  form of $R_{i,j}x$, where $R_{i,j}\neq0$ and $x\in\Omega_{1}$, need to be calculated and stored. Hence, the size of $\mathbb{T}$ is
\begin{equation}
|\mathbb{T}|=\frac{N_R|\Omega|}{2}, \label{eq12}
\end{equation}
where $N_R$ denotes the number of non-zero elements in matrix $\bf{R}$, and $|\Omega|$ denotes the size of $\Omega$.

In order to build $\mathbb{T}$, both the number of terms that need to be stored and the number of real multiplications required are $|\mathbb{T}|$. Since the channel is assumed to be flat fading,
only one $\mathbb{T}$ needs to be built in one burst. If the burst length is very long, its computational complexity can be neglected.

\subsection{Intermediate Node Weights}

Define
\begin{equation}
M({\bf x}^{(l+1)})=\bar{y}_l-\sum^{2N}_{k=l+1}{R_{l,k}x_k}, \label{eq13}
\end{equation}
where $M({\bf x}^{(2N+1)})=0$, then (\ref{eq11}) can be rewritten as
\begin{equation}
w_{pw}({\bf x}^{(l)})=|M({\bf x}^{(l+1)})-R_{l,l}x_l|^{2}. \label{eq14}
\end{equation}

Equation (\ref{eq13}) shows that $M({\bf x}^{(l+1)})$ is independent of $x_l$, which means for any node not in the last level of the search tree, all children nodes share the same $M({\bf x}^{(l+1)})$. In other words, for these nodes, their $M({\bf x}^{(l+1)})$ values only need to be calculated once to get the whole set of weights for their children nodes. Consequently, the number of operations will be reduced if $M({\bf x}^{(l+1)})$ values are temporally stored at each node, except nodes of the last level, until the whole set of its children are visited. Based on (\ref{eq10}), (\ref{eq13}), and (\ref{eq14}), by temporally storing the $M({\bf x}^{(l+1)})$ values, the number of real additions needed to get all partial weights of children nodes at layer $l$, for a parent node of layer $l+1$, reduces to $2N-l+|\Omega|$ from $(2N-l+1)|\Omega|$. Note that after implementing the check-table $\mathbb{T}$, storing $M({\bf x}^{(l+1)})$ values does not affect the number of real multiplications.

\subsection{New Lattice Representation}

In our previous work \cite{Azzam_SD_NLR}, \cite{Azzam_SD_RLR}, a new lattice representation is proposed for (\ref{eq8}) that enables decoding the real and imaginary parts of each complex symbol independently. Also, a near ML decoding algorithm, which combines DFS, K-best decoding, and quantization, was introduced. In this work, a different application of the lattice representation, which achieves no performance degradation, is employed.

For the new lattice representation, (\ref{eq4})-(\ref{eq7}) become
\begin{equation}
{\bf y}=
\begin{bmatrix}
\Re \left\lbrace r_1 \right\rbrace & \Im \left\lbrace r_1 \right\rbrace & \cdots & \Re \left\lbrace r_N \right\rbrace & \Im \left\lbrace r_N \right\rbrace
\end{bmatrix}^{T},
\label{eq15}
\end{equation}
\begin{equation}
\bar{\bf H}=
\setlength{\arraycolsep}{0.0em}
\begin{bmatrix}
\Re \left\lbrace H_{1,1} \right\rbrace & -\Im \left\lbrace H_{1,1} \right\rbrace & \cdots & \Re \left\lbrace H_{1,N} \right\rbrace & -\Im \left\lbrace H_{1,N} \right\rbrace \\
\Im \left\lbrace H_{1,1} \right\rbrace & \Re \left\lbrace H_{1,1} \right\rbrace & \cdots & \Im \left\lbrace H_{1,N} \right\rbrace & \Re \left\lbrace H_{1,N} \right\rbrace \\
\vdots &  \vdots & \ddots & \vdots & \vdots \\
\Re \left\lbrace H_{N,1} \right\rbrace & -\Im \left\lbrace H_{N,1} \right\rbrace & \cdots & \Re \left\lbrace H_{N,N} \right\rbrace & -\Im \left\lbrace H_{N,N} \right\rbrace \\
\Im \left\lbrace H_{N,1} \right\rbrace & \Re \left\lbrace H_{N,1} \right\rbrace & \cdots & \Im \left\lbrace H_{N,N} \right\rbrace & \Re \left\lbrace H_{N,N} \right\rbrace \\
\end{bmatrix},
\label{eq16}
\end{equation}
\begin{equation}
{\bf x}=
\begin{bmatrix}
\Re \left\lbrace s_1 \right\rbrace & \Im \left\lbrace s_1 \right\rbrace & \cdots & \Re \left\lbrace s_N \right\rbrace & \Im \left\lbrace s_N \right\rbrace
\end{bmatrix}^{T},
\label{eq17}
\end{equation}
\begin{equation}
{\bf n}=
\begin{bmatrix}
\Re \left\lbrace v_1 \right\rbrace & \Im \left\lbrace v_1 \right\rbrace & \cdots & \Re \left\lbrace v_N \right\rbrace & \Im \left\lbrace v_N \right\rbrace
\end{bmatrix}^{T}.
\label{eq18}
\end{equation}

The structure of the new lattice representation (\ref{eq15})-(\ref{eq18}) becomes advantageous after applying the QR decomposition to $\bar{\bf H}$. By doing so, and due to the special form of orthogonality between each pair of columns, all elements $R_{k,k+1}$ for $k=1,3,\ldots,2N-1$, in the upper triangular matrix $\bf{R}$ become zero. The locations of these zeros introduce orthogonality between the real and imaginary parts of every detected symbol, which can be taken advantage of to reduce the computational complexity of SD. The following example is provided to explain this.

\textsl{Example:} Consider a MIMO system having $N_r=N_t=N=2$, and employing $4$-QAM. Then, SD constructs a tree with $2N=4$ levels, where the branches coming out from each node represent the real values in the set $\Omega=\lbrace-1,1\rbrace$. This tree is shown in Fig. \ref{fig1}. Now using the real-valued lattice representation (\ref{eq15})-(\ref{eq18}), and applying the QR decomposition to the channel matrix, the input-output relation is given by

\begin{equation}
\begin{bmatrix}
\bar{y}_1 \\ \bar{y}_2 \\ \bar{y}_3 \\ \bar{y}_4
\end{bmatrix}
=
\begin{bmatrix}
R_{1,1} & 0 & R_{1,3} & R_{1,4} \\
0 & R_{2,2} & R_{2,3} & R_{2,4} \\
0 & 0 & R_{3,3} & 0 \\
0 & 0 & 0 & R_{4,4}
\end{bmatrix}
\begin{bmatrix}
x_{1} \\ x_{2} \\ x_{3} \\ x_{4}
\end{bmatrix}
+
\begin{bmatrix}
n_{1} \\ n_{2} \\ n_{3} \\ n_{4}
\end{bmatrix}.
\label{eq19}
\end{equation}

\ifCLASSOPTIONonecolumn
\begin{figure}[!p]
\centering
\includegraphics[width=1.0\textwidth]{tree_eg.eps}
\caption{Tree structure for a 2x2 system employing 4-QAM}
\label{fig1}
\end{figure}
\else
\begin{figure}[!t]
\centering
\includegraphics[width=0.5\textwidth]{tree_eg.eps} \caption{Tree structure for a 2x2 system employing 4-QAM}
\label{fig1}
\end{figure}
\fi

Based on (\ref{eq11}) and (\ref{eq19}), calculating partial node weights for the first level and the second level are independent, similar to the third level and the forth level, because of the additional zero locations in the $\bf R$ matrix. For instance, the partial weights of node $A$ and node $B$ only depend on $x_3$ but $x_4$, and the partial weights of node $C$, node $D$, node $E$, and node $F$, depend on $x_4$, $x_3$, and $x_1$ except $x_2$. In other words, the partial weights of node $A$ and node $B$ are equal, and only need to be calculated once. Similarly, partial weights of node $C$ and node $D$ can be used when calculating the partial weights of node $E$ and node $F$, respectively.

SD is then modified because of this feature. Once the tree is searched in layer $l$, where $l$ is an odd number, partial weights of this node and all of its sibling nodes are computed, temporally stored, and recycled when calculating partial node weights with the same grandparent node of layer $l+2$ but with different parent nodes of layer $l+1$.

By applying the modification, further complexity reduction is achieved beyond the reduction due to the check-table $\mathbb{T}$ and intermediate $M({\bf x}^{(l+1)})$ values. For a node of layer $l+2$, where $l$ is an odd number, let $\alpha\in[0,|\Omega|]$ denote the number of non-pruned branches for its children nodes of layer $l+1$. If $\alpha=0$, which means all branches of its children nodes of layer $l+1$ are pruned, the number of operations needed stay the same. If $\alpha\neq0$, to get all partial weights of its grandchildren nodes in layer $l$, the number of real multiplications and real additions reduce further from $(\alpha+1)|\Omega|$ to $2|\Omega|$, and $(\alpha+1)(2N-l-1+|\Omega|)+\alpha$ to $2(2N-l-1+|\Omega|)$ respectively.

\section{SIMULATION RESULTS}

To verify the proposed technique, simulations are carried out for $2\times2$ and $4\times4$ systems using $4$-QAM and $64$-QAM. Assuming $4000$ symbols are transmitted during one channel realization and considering $1000$ channel realizations for each simulation, the average number of real multiplications and real additions for decoding one transmitted vector symbol are calculated. In the figures, conventional SD is denoted by CSD and proposed SD by PSD. In our simulations, $\delta^2=2\sigma_n^2N$ is chosen as the square of initial radius. A lattice point lies inside a sphere of this radius with high probability \cite{Damen_MLD}.

Fig. \ref{fig2} and Fig. \ref{fig3} show comparisons for the number of operations between conventional SD and proposed SD for $2\times2$ systems using $4$-QAM and $64$-QAM. For $4$-QAM, the complexity gains for the average numbers of real multiplications and real additions are around $70\%$ and $45\%$ respectively at high SNR. Corresponding numbers are $75\%$ and $40\%$ respectively at low SNR. For the $64$-QAM case, gains increase to around $70\%$ and $65\%$ at high SNR respectively, while they are around $85\%$ and $60\%$ at low SNR respectively.

Similarly, Fig. \ref{fig4} and Fig. \ref{fig5} show complexity comparisons using $4$-QAM and $64$-QAM for $4\times4$ systems. For $4$-QAM, gains for the average number of real multiplications and real additions are around $80\%$ and $50\%$ respectively at high SNR, while they are around $85\%$ and $45\%$ respectively at low SNR. For $64$-QAM, gains rise up to around $80\%$ and $75\%$ respectively at high SNR, while they are around $90\%$ and $70\%$ respectively at low SNR.

Simulation results show that proposed SD reduces the complexity significantly compared to conventional SD, particularly for real multiplications, which are the most expensive operations in terms of machine cycles, and the reduction becomes larger as the system dimension or the modulation alphabet size increases. An important property of our proposed SD is that the substantial complexity reduction achieved causes no performance degradation. The proposed technique can be combined with other techniques which reduce the number of visited nodes such as SE, and other near-optimal techniques such as K-best.

\ifCLASSOPTIONonecolumn
\begin{figure}[!m]
\centering
\scalebox{.7}{\includegraphics{numofmul_2x2.eps}}
\caption{Average number of real multiplications vs. SNR for conventional SD and proposed SD over a $2\times2$ MIMO flat fading channel using $4$-QAM and $64$-QAM.}
\label{fig2}
\end{figure}

\begin{figure}[!m]
\centering
\scalebox{.7}{\includegraphics{numofadd_2x2.eps}}
\caption{Average number of real additions vs. SNR for conventional SD and proposed SD over a $2\times2$ MIMO flat fading channel.}
\label{fig3}
\end{figure}

\begin{figure}[!m]
\centering
\scalebox{.7}{\includegraphics{numofmul_4x4.eps}}
\caption{Average number of real multiplications vs. SNR for conventional SD and proposed SD over a $4\times4$ MIMO flat fading channel.}
\label{fig4}
\end{figure}

\begin{figure}[!m]
\centering
\scalebox{.7}{\includegraphics{numofadd_4x4.eps}}
\caption{Average number of real additions vs. SNR for conventional SD and proposed SD over a $4\times4$ MIMO flat fading channel.}
\label{fig5}
\end{figure}
\else
\begin{figure}[!p]
\centering
\scalebox{.5}{\includegraphics{numofmul_2x2.eps}}
\caption{Average number of real multiplications vs. SNR for conventional SD and proposed SD over a $2\times2$ MIMO flat fading channel.}
\label{fig2}
\end{figure}

\begin{figure}[!p]
\centering
\scalebox{.5}{\includegraphics{numofadd_2x2.eps}}
\caption{Average number of real additions vs. SNR for conventional SD and proposed SD over a $2\times2$ MIMO flat fading channel.}
\label{fig3}
\end{figure}

\begin{figure}[!p]
\centering
\scalebox{.5}{\includegraphics{numofmul_4x4.eps}}
\caption{Average number of real multiplications vs. SNR for conventional SD and proposed SD over a $4\times4$ MIMO flat fading channel.}
\label{fig4}
\end{figure}

\begin{figure}[!p]
\centering
\scalebox{.5}{\includegraphics{numofadd_4x4.eps}}
\caption{Average number of real additions vs. SNR for conventional SD and proposed SD over a $4\times4$ MIMO flat fading channel.}
\label{fig5}
\end{figure}
\fi

\section{CONCLUSIONS}

A simple and general technique to implement the SD algorithm with low computational complexity is proposed in this paper. The focus of the technique is on reducing the average number of operations required at each node for SD. The BER performance of the proposed SD is the same as conventional SD. Moreover, a substantial complexity reduction is achieved. Simulation results are provided for $2\times2$ and $4\times4$ systems employing $4$-QAM and $64$-QAM. The complexity gains for the average numbers of real multiplications and real additions are substantial, ranging from $70\%$ to $90\%$ and $40\%$ to $75\%$ respectively, based on the number of antennas and the constellation size of modulation schemes. These complexity gains become larger as the system dimension or the modulation alphabet size increases.

\ifCLASSOPTIONonecolumn \newpage \fi

\bibliographystyle{IEEEtran}