Comments on “A New ML Based Interference Cancellation Technique for Layered Space-Time Codes”

A maximum likelihood (ML) based interference cancellation (IC) detector was proposed in [1] for double space-time transmit diversity (DSTTD), which consists of two Alamouti’s space-time block codes (STBC) units [2]. In many application areas of interest, the computational complexity of the detector in [1] can be less than that of the conventional minimum mean squared error (MMSE) IC detector for DSTTD [3]. However, the complexity claimed in [1] needs to be modified, as will be discussed in this comment.

Let $N$ denote the number of receive antennas. In [1], the theoretical analysis gaves a complexity of $O(N^{2})$ (i.e. $7N^{2}+62N-103$ real multiplications and $12N^{2}+47N-103$ real additions) [1, Table \@slowromancapi@], while numerical experiments were not carried out to verify the given complexity. In what follows, we show that the complexity is not $O(N^{2})$, but $O(N^{3})$, and then give the exact complexity that is verified by our numerical experiments.

Firstly, we show that a complexity of $O(N^{3})$ is required to perform the orthonormalization process by equations (9), (13), (14) and (15) in [1]. Let $(\bullet)^{T}$ and $(\bullet)^{H}$ denote transpose and conjugate transpose of a vector, respectively. Equation (9) in [1] defines the basis vectors

$${\bf{v}}_{i}=\left[{\begin{array}[]{*{20}c}{a_{i}}&{b_{i}}&{\bf e}_{i}^{T}\\ \end{array}}\right]^{T},$$

(1)

where $i=1,2,\cdots,2N-2$, and ${\bf e}_{i}$ is the $(2N-2)\times 1$ vector with the $i^{th}$ element to be $1$ and all others to be zero. Equation (13) in [1] utilizes ${\bf{v}}_{1}$ and ${\bf{v}}_{2}$, which is

$${\bm{\uptheta}}_{1}={\bf{v}}_{1}/\left\|{\bf{v}}_{1}\right\|,\quad{\bm{\uptheta}}_{2}={\bf{v}}_{2}/\left\|{\bf{v}}_{2}\right\|.$$

(2)

Moreover, we represent equations (14) and (15) in [1] as

		$\displaystyle{\bm{\uptheta}}_{2n-1}=\left({{\bf{v}}_{2n-1}-\sum\nolimits_{j=1}^{2n-2}{c_{2n-1}^{j}{\bm{\uptheta}}_{j}}}\right)/\left\|\cdots\right\|,$			(3a)
		$\displaystyle{\bm{\uptheta}}_{2n}=\left({{\bf{v}}_{2n}-\sum\nolimits_{j=1}^{2n-2}{c_{2n}^{j}{\bm{\uptheta}}_{j}}}\right)/\left\|\cdots\right\|,$			(3b)

where

		$\displaystyle{c_{2n-1}^{j}={{\bm{\uptheta}}_{j}^{H}{\bf{v}}_{2n-1}}},$			(4a)
		$\displaystyle{c_{2n}^{j}={{\bm{\uptheta}}_{j}^{H}{\bf{v}}_{2n}}},$			(4b)

and $n=2,3,\cdots,N-1$. It can be seen that $\left[{\begin{array}[]{*{20}c}{{\bm{\uptheta}}_{2n-1}}&{{\bm{\uptheta}}_{2n}}\\ \end{array}}\right]$ consists of $2\times 2$ Alamouti sub-blocks [4]. Thus we can obtain ${\bm{\uptheta}}_{2n}$ from ${\bm{\uptheta}}_{2n-1}$, to avoid computing (3b) and (4b).

Let ${\bm{\uptheta}}\sim\left\lfloor{i,j,\cdots,k}\right\rfloor$ denote that only the $i^{th},j^{th},\cdots,k^{th}$ entries in the vector ${\bm{\uptheta}}$ are non-zero. From (1), we obtain

$${\bf{v}}_{i}\sim\left\lfloor{1,2,i+2}\right\rfloor,$$

(5)

where $i=1,2,\cdots,2N-2$. From (2) and (5), we obtain

$${\bm{\uptheta}}_{1}\sim\left\lfloor{1,2,3}\right\rfloor,\quad{\bm{\uptheta}}_{2}\sim\left\lfloor{1,2,4}\right\rfloor.$$

(6)

Let $n=2$ in (3b) to obtain

$${\bm{\uptheta}}_{3}=\left({{\bf{v}}_{3}-c_{3}^{1}{\bm{\uptheta}}_{1}-c_{3}^{2}{\bm{\uptheta}}_{2}}\right)/\left\|\cdots\right\|\\ \sim\left\lfloor{1,2,3,4,5}\right\rfloor=\left\lfloor{1-5}\right\rfloor$$

(7)

and

$${\bm{\uptheta}}_{4}=\left({{\bf{v}}_{4}-c_{4}^{1}{\bm{\uptheta}}_{1}-c_{4}^{2}{\bm{\uptheta}}_{2}}\right)/\left\|\cdots\right\|\sim\left\lfloor{1-4,6}\right\rfloor,$$

(8)

where (5) and (6) are utilized. From (6)$-$(8), it can be seen that for $n=1,2$, we have

$${\bm{\uptheta}}_{2n-1}\sim\left\lfloor{1-(2n+1)}\right\rfloor,\quad{\bm{\uptheta}}_{2n}\sim\left\lfloor{1-2n,2n+2}\right\rfloor.$$

(9)

Assume for any $n$, ${\bm{\uptheta}}_{2n-1}$ and ${\bm{\uptheta}}_{2n}$ satisfy (9). This assumption will be verified in this paragraph. From (3b), it can be seen that ${\bm{\uptheta}}_{2(n+1)-1}$ includes the sum of ${\bm{\uptheta}}_{2n-1}$, ${\bm{\uptheta}}_{2n}$ and ${\bf{v}}_{2(n+1)-1}$, while ${\bm{\uptheta}}_{2(n+1)}$ includes the sum of ${\bm{\uptheta}}_{2n-1}$, ${\bm{\uptheta}}_{2n}$ and ${\bf{v}}_{2(n+1)}$. From (5) and the assumption (9), we can conclude that ${\bm{\uptheta}}_{2(n+1)-1}$ and ${\bm{\uptheta}}_{2(n+1)}$ also satisfy (9). Then the assumption (9), which is valid for $n=1,2$, is still valid for all the subsequent $(n+1)$s where $n=1,2,\cdots,N-2$. Thus we have verified the assumption (9) for any $n$.

It can be seen from (9) that in (3a), $c_{2n-1}^{j}{\bm{\uptheta}}_{j}$ requires more than $j$ multiplications, while $\sum\nolimits_{j=1}^{2n-2}{c_{2n-1}^{j}{\bm{\uptheta}}_{j}}$ requires more than $\sum\nolimits_{j=1}^{2n-2}{j}\approx 2n^{2}$ multiplications. Then totally it requires more than $\sum\nolimits_{n=2}^{N-1}{2n^{2}}\approx\frac{2}{3}N^{3}$ multiplications to compute (3a) for $n=2,3,\cdots,N-1$. Thus we have shown that the actual complexities of the detector in [1] should be at least $O(N^{3})$.

The dominant computations of the ML based IC detector [1] come from equations (9), (11), (13), (14), (23), (25) and (28) in [1], of which the complexities are listed in Table \@slowromancapi@. One complex multiplication takes four real multiplications and two real additions, while one complex addition needs two real additions. Therefore, it can be seen from Table \@slowromancapi@ that the complexities of the detector are equivalent to

$$\frac{8}{3}N^{3}+14N^{2}+\frac{79}{3}N-25$$

(10)

real multiplications and

$$\frac{8}{3}N^{3}+10N^{2}+\frac{46}{3}N-9$$

(11)

real additions. The total complexity is the sum of real multiplications and additions [1], which is

$$\frac{16}{3}N^{3}+24N^{2}+\frac{125}{3}N-34$$

(12)

floating-point operations (flops). We also carried out numerical experiments to count the flops required by the detector in [1]. The results of our numerical experiments are identical to those computed by (12), i.e., our numerical experiments have accurately verified (12).

Table \@slowromancapi@ in [1] compared the complexities of the ML based IC detector for DSTTD in [1] and the conventional MMSE IC detector for DSTTD in [3]. From (10), (11) and (12), it can be seen that Table \@slowromancapi@ in [1] should be modified to Table \@slowromancapii@ in this comment, where the total complexity of the MMSE IC detector in [3] is

$$15N^{3}+\frac{73}{2}N^{2}-\frac{3}{2}N$$

(13)

flops [1]. From Table \@slowromancapii@, it can be seen that the complexity of the detector proposed in [1] is about $2.2$ times smaller than that of the MMSE IC detector [3] when the number of receive antennas is $8$.