A Fast Recursive Algorithm for G-STBC

Multiple-input multiple-output (MIMO) wireless communication systems possess huge channel capacities [1] when the multipath scattering is sufficiently rich. A MIMO system can provide two types of gains simultaneously, i.e. spatial multiplexing gain and diversity gain, while usually the increase in one type of gain needs the sacrifice in the other type of gain [2]. Two extreme examples of MIMO systems are Vertical Bell Laboratories Layered Space-Time architecture (V-BLAST) [3] and space-time block code (STBC) [4, 5], which achieve full spatial multiplexing gain and full diversity gain, respectively. The combination of V-BLAST and STBC is known as Group-wise STBC (G-STBC) or Multi-layered STBC (MLSTBC) [6, 8, 7, 9, 10, 11, 12, 13, 14], which achieves both spatial multiplexing gain and diversity gain concurrently. Specifically, the Alamouti code (the simplest and most popular STBC) [4] and the G-STBC consisting of two Alamouti codes [8, 12, 13, 14] have been adopted in wireless standards [15], where they are named space-time transmit diversity (STTD) and double-STTD (DSTTD), respectively.

In G-STBC, the transmit antennas are divided into $M$ layers (groups), of which each has $K$ transmit antennas and a corresponding STBC encoder. To detect one layer by suppressing the interferences from the other $M-1$ layers, the detector in [6] requires $N\geq(M-1)\times K+1$ receive antennas, while the linear or successive interference cancelation (SIC) detectors in [8, 7, 9, 10, 11, 12, 13, 14] only require $N\geq M$ receive antennas, which are developed from the equivalent channel model based on the temporal and spatial structure of STBC. Moreover, group-wise SIC detectors and trellis-coded modulation (TCM) encoders/decoders are jointly designed for G-STBC in [16]. The minimum mean-square error (MMSE) ordered SIC (OSIC) detector for G-STBC [7] and that only for DSTTD [8] both require high computational complexities. Then some efficient detectors for G-STBC or only for DSTTD are proposed in [9, 10, 11, 12, 13, 14]. The MMSE sub-optimal OSIC detector for V-BLAST [17] using sorted QR decomposition (SQRD) are extended to decode G-STBC in [9]. The simple linear Zero Forcing (ZF) detector for G-STBC in [10] is further simplified in [11] by utilizing Strassen algorithm. For DSTTD, SIC detectors are reported in [12, 13]. Recently the authors of [14] notice that none of the DSTTD detectors in [8, 12, 13] utilizes the post-cancellation orthogonal structure, and then utilizes that structure to develop the SIC detector [14] for DSTDD that reduces the complexity at the sacrifice of performance.

In this letter, we consider the G-STBC consisting of $M\geq 2$ Alamouti Codes. We deduce an efficient recursive algorithm to compute the initial estimation error covariance matrix, based on which we propose a fast recursive algorithm for G-STBC. The proposed algorithm exploits the Alamouti structure [18] in the equivalent channel matrix to reduce the complexity dramatically.

In what follows, $(\bullet)^{T}$, $(\bullet)^{*}$, and $(\bullet)^{H}$ denote matrix transposition, matrix conjugate, and matrix conjugate transposition, respectively. ${\bf{{\rm I}}}_{M}$ is the identity matrix of size $M$.

The considered G-STBC system consists of $M\times K$ transmit antennas and $N$ ($\geq M$) receive antennas in a rich-scattering and flat-fading wireless channel. It includes $M$ parallel and independent STBC encoders. In this letter, we consider the Alamouti STBC encoder [4] with $K=2$. The transmitted data stream ${\bf{s^{\prime}}}=\left[{\begin{array}[]{*{20}c}{s_{11}}&{s_{12}}&{s_{21}}&{s_{22}}&\cdots&{s_{M1}}&{s_{M2}}\\ \end{array}}\right]^{T}$ is de-multiplexed into $M$ sub-streams. Each sub-stream $s_{m1},s_{m2}$ ($m=1,2,...,M$) is encoded by an independent Alamouti encoder, and then fed to its respective $K=2$ transmit antennas. Correspondingly the received symbols over two time slots are

where $x_{nj}$ is the $j^{th}$ symbol received by the $n^{th}$ receive antenna, $h_{nm}$ is the fading gain from the $m^{th}$ transmitter to the $n^{th}$ receiver, and ${\bf{N}}$ is the $N\times 2$ complex Gaussian noise matrix. We can transform (1) into the equivalent channel model [8]

where the equivalent received symbol vector ${\bf{x^{\prime}}}=\left[{\begin{array}[]{*{20}c}{x_{11}}&{x_{12}^{*}}&{x_{21}}&{x_{22}^{*}}&\cdots&{x_{N1}}&{x_{N2}^{*}}\\ \end{array}}\right]^{T}$, and the equivalent channel matrix

In (2), the transmitted data stream ${\bf s^{\prime}}$ is with the covariance $E({\bf{s^{\prime}s^{\prime}}}^{H})=\sigma_{{s}}^{2}{\bf{{\rm I}}}_{2M}$, and the $2N\times 1$ Gaussian noise vector ${\bf{n^{\prime}}}$ is with zero mean and the covariance $E({\bf{n^{\prime}n^{\prime}}}^{H})=\sigma_{n}^{2}{\bf{{\rm I}}}_{2N}$.

The MMSE OSIC detector for V-BLAST can be extended to the equivalent channel model (2) for G-STBC, since mathematically (2) has the same form as the standard channel model for V-BLAST [7]. Correspondingly the linear MMSE estimate of $\bf{s^{\prime}}$ can be [7, 9]

where $\alpha=\sigma_{n}^{2}/\sigma_{s}^{2}$, and ${\bf{Q^{\prime}}}=\left({{\bf{H^{\prime}}}^{H}{\bf{H^{\prime}}}+\alpha{\bf{I}}_{2M}}\right)^{-1}$ is the estimation error covariance matrix.

The OSIC detector for G-STBC [7] detects $2M$ entries of $\bf{s^{\prime}}$ iteratively with the optimal order. In each iteration, the entry with the highest SINR (Signal to Interference plus Noise Ratio) is detected, and then its interference is cancelled in ${\bf{x^{\prime}}}$. Suppose that the entries of ${\bf{s^{\prime}}}$ are permuted such that the successive detection order is ${s_{M2}},{s_{M1}},{s_{(M-1)2}},{s_{(M-1)1}},\cdots,{s_{12}},{s_{11}}$. Then in the $(2M-k+1)^{th}$ ($k=2M,2M-1,\cdots,1$) iteration, the $k$ undetected entries can be represented as ${\bf{s^{\prime}}}_{k}$ that includes the first $k$ entries of ${\bf{s^{\prime}}}$, while the corresponding equivalent channel matrix

where ${\bf{h}}^{\prime}_{i}$ ($i=1,2,\cdots,k$) denotes the $i^{th}$ column of ${\bf{H^{\prime}}}$.

In this section, we deduce an efficient recursive algorithm to compute the initial ${\bf{Q^{\prime}}}$, based on which we develop a fast recursive algorithm for G-STBC.

The $2\times 2$ Alamouti structure $\left[{\begin{array}[]{*{20}c}{a_{1}}&{-a_{2}^{*}}\\ {a_{2}}&{a_{1}^{*}}\\ \end{array}}\right]$ in the equivalent channel matrix ${{\bf{H^{\prime}}}}$, which remains invariant under several matrix operations [18], is regarded as the matrix representation of a quaternion and then called as a block entry [18]. Block entries can form vectors and matrices, which are then called as block vectors and block matrices [18], respectively. In what follows, scalars, vectors and matrices with overlines always represent the above-mentioned block entries (i.e. block scalars), block vectors, and block matrices, respectively. We define the block matrix

where $m=1,2,\cdots,M$, and the block column vector ${\bf{\bar{h}}}_{m}=\left[{\begin{array}[]{*{20}c}{{\bf{h^{\prime}}}_{2m-1}}&{{\bf{h^{\prime}}}_{2m}}\\ \end{array}}\right]$. Then we write

where ${\bf{\bar{R}}}_{m-1}$ and ${\bf{\bar{T}}}_{m-1}$ are the leading principal $2(m-1)\times 2(m-1)$ sub-matrices of ${\bf{\bar{R}}}_{M}$ and ${\bf{\bar{Q}}}_{m}$ [19, 20], respectively. In (12c), ${\bf{\bar{H}}}_{m}^{H}{{\bf{\bar{H}}}_{m}}$ (computed from the block matrix ${{\bf{\bar{H}}}_{m}}$) must be Hermitian with diagonal $2\times 2$ sub-blocks that are non-negative scaled multiples of the identity matrix and with off-diagonal $2\times 2$ sub-blocks that are Alamouti matrices [18, Property 3 in the subsection “B. Block Matrices”], and the same is ${\bf{{\bar{R}}}}_{m}$. Then in (12c), the block entry

(where ${{{\upsilon}^{\prime}}}_{m}$ is a scalar), while ${\bf{{\bar{v}}}}_{{m-1}}$ is the block column vector, which can be represented as ${\bf{{\bar{v}}}}_{{m-1}}=\left[{\begin{array}[]{*{20}c}{{\bf{v^{\prime}}}_{2(m-1)}}&{{\bf{v^{\prime\prime}}}_{2(m-1)}}\\ \end{array}}\right].$ Moreover, in Appendix A we derive ${{{\bar{{\omega}}}}}_{m}$, ${{\bf{\bar{w}}}}_{m-1}$ and ${\bf{{{\bar{T}}}}}_{m-1}$ in (12f) respectively as

Base on (14d), we develop the recursive G-STBC algorithm. In the initialization phase, to obtain ${\bf{{{\bar{Q}}}}}_{M}$ from ${\bf{{{\bar{Q}}}}}_{1}={\bf{{{\bar{R}}}}}_{1}^{-1}$, we compute ${\bf{{{\bar{Q}}}}}_{m}$ from ${\bf{{{\bar{Q}}}}}_{m-1}$ recursively (for $m=2,3,...,M$) by (14d) and (12f). Moreover, as the V-BLAST algorithms in [19, 20], we perform interference cancellation not in ${\bf{x^{\prime}}}$, but in ${\bf z}^{\prime}={\bf{\bar{H}}}_{M}^{H}{\bf{x^{\prime}}}$. Then we need to compute the initial

In the recursion phase, we detect $M$ layers of STBC encoded symbols recursively by group-wise OSIC. The subscript $|$ is added to some variables for the recursion phase, to distinguish them from the variables for the initialization phase, e.g., usually ${\bf{\bar{Q}}}_{|m}\neq{\bf{\bar{Q}}}_{m}$. In each recursion, estimate the $p_{m}^{th}$ layer, i.e. the layer with the highest SINR among all the undetected layers, by

where ${\bf{{q}}}^{\prime}_{|2{m}-1}$ and ${\bf{{q}}}^{\prime}_{|2{m}}$ are the $\left({2m-1}\right)^{th}$ and $2m^{th}$ columns of the permuted ${\bf{{{\bar{Q}}}}}_{|m}$, respectively. Quantize ${y_{p_{m}1}}$ and ${y_{p_{m}2}}$ to obtain ${\hat{s}_{p_{m}1}}={Q\left\{{y_{p_{m}1}}\right\}}$ and ${\hat{s}_{p_{m}2}}={Q\left\{{y_{p_{m}2}}\right\}}$, respectively. Then as in [19, 20], we cancel the effect of ${s_{p_{m}1}}$ and ${s_{p_{m}2}}$ in ${\bf z}^{\prime}_{m}$ by

where ${\bf z^{\prime}}_{m}^{\left[{-2}\right]}$ is ${\bf z}^{\prime}_{m}$ with the last two entries removed, and ${\bf{{\bar{v}}}}_{{|m-1}}$ is in ${\bf{{\bar{R}}}}_{|m}$, as shown in (12c). In the next recursion, ${\bf{{{\bar{Q}}}}}_{|m-1}$ is required to compute (16). Thus we deflate ${\bf{{{\bar{Q}}}}}_{|m}$ by (14d) to obtain

To some extent, (18) (that deflates a block matrix recursively) has a similar form as equation (15) in [21] and equation (21) in [20] (that deflates a matrix recursively), while the vector ${{\bf{{w}}}}_{m-1}$ in the equations of [21, 20] is replaced with the block vector ${{\bf{\bar{w}}}}_{|m-1}$ in (18). On the other hand, as (18), equation (24) in [22] also deflates a block matrix recursively, while it deflates the matched-filtered (MF) real-valued channel matrix for G-STBC that is obtained from the augmented real-valued channel matrix.

Table \@slowromancapi@ summarizes the proposed recursive G-STBC algorithm, where ${r^{\prime}}_{|i,k}^{m}$ and ${q^{\prime}}^{m}_{|i,k}$ are the entries in the $i^{th}$ row and $k^{th}$ column of the permuted ${\bf{\bar{R}}}_{|m}$ and ${\bf{\bar{Q}}}_{|m}$, respectively. Notice that ${\bf{{{\bar{Q}}}}}_{m}$($={\bf{{{\bar{R}}}}}_{m}^{-1}$) and ${\bf{{{\bar{Q}}}}}_{|m}$ consist of Alamouti sub-blocks[18, Lemma “Invariance Under Inversion”].

In the recursion phase, the proposed group-wise OSIC only needs to compute the block matrices ${\bf{\bar{Q}}}_{|m-1}$s ($m=M,M-1,\cdots,2$) that consist of Alamouti sub-blocks, while the symbol-wise OSIC [7] implemented by the recursive V-BLAST algorithm in [20] needs to compute the matrices ${\bf{Q}}_{|k-1}$s ($k=2M,2M-1,2M-2,2M-3,\cdots,2$) that usually do not consist of Alamouti sub-blocks. So the proposed group-wise OSIC can save much computational complexity, with respect to the symbol-wise OSIC [7]. On the other hand, the proposed group-wise OSIC is equivalent to the symbol-wise SIC with the group-wise optimal detection order, as shown in Appendix B. Thus its performance loss with respect to the symbol-wise OSIC (for G-STBC) [7] only comes from different detection orders (i.e., the group-wise optimal order vs. the symbol-wise optimal order), and is relatively small, as shown in the rest of this section.

We list the computational complexities of the presented G-STBC and DSTTD algorithms in Table \@slowromancapii@, where the exact complexities of the presented DSTTD algorithms have been verified by our numerical experiments to count the floating-point operations (flops — One flop can be one real multiplication or one real addition). In this table, “Proposed DSTTD Alg.” denotes the proposed G-STBC algorithm applied to D-STTD. When counting the complexities, we utilize the fact that one complex multiplication needs $4$ real multiplications and $2$ real additions, while one complex addition needs $2$ real additions. The total complexity of the proposed G-STBC algorithm is the sum of the complexities to compute ${\bf{\bar{R}}}_{M}$, ${\bf{\bar{Q}}}_{M}$ and ${\bf{\bar{Q}}}_{|m-1}$s ($m=M,M-1,\cdots,2$) that are $\langle{2M^{2}N}\rangle$, $\langle{2M^{3}}\rangle$ and $\langle{\frac{2}{3}M^{3}}\rangle$, respectively, where $\langle{k}\rangle$ denotes $k$ complex multiplications and $k$ complex additions. The algorithm in [9] nearly requires the same number of complex multiplications and additions [9], [17, Table \@slowromancapi@], while [9, equation (19)] claims a complexity of $2N_{t}^{3}+2N_{t}^{2}N_{r}+O(N_{t}^{2}+N_{t}N_{r})$ operations, where $N_{t}=2M$, $N_{r}=N$, and an operation can be a complex multiplication or addition. The complexity of the one-step SIC algorithm for DSTTD in [14] has been revised in [24], while the two-step SIC algorithm and the SINR-ordered SIC algorithm for DSTTD in [14] both need nearly double the complexity of the one-step SIC algorithm.

For DSTTD, the special case of G-STBC with the minimum number of transmit antennas, the ML(maximum likelihood)-like sphere detectors [23] are alternative methods worth considering. For example, with respect to the SIC DSTTD detector in [8], the ML-like DSTTD detector in [23] performs about $1.7$ dB better at BER=$10^{-2}$, but requires about $2.7$ times of complexity [23, Fig. 5]. Although ML-like DSTTD detectors can be preferred in some applications, they usually do not have advantage in both complexity and BER performance [23]. Thus quite a few recent literatures focusing on SIC DSTTD receivers [12, 13, 14, 16] did not discuss ML-like sphere detectors, and neither does this letter focusing on SIC G-STBC receivers, which, due to the limited space, cannot give too extensive discussion for only the special case of G-STBC (i.e. DSTTD).

From Table \@slowromancapii@, we can compare the complexities of the presented algorithms. When $M=N$, the proposed G-STBC algorithm speeds up the G-STBC algorithm in [9] by $48/(\frac{56}{3})=2.57$ approximately, and even requires less real multiplications than the linear ZF G-STBC algorithm in [11]. When $N\geq 3$, the proposed DSTTD algorithm is faster than the one-step SIC DSTTD algorithm in [14], and the speedup (in the number of flops) grows with $N$, which is $1.02$ for $N=3$, $1.54$ for $N=4$, and $4.55$ for $N=8$. However, when $N=2$, the one-step SIC DSTTD algorithm in [14] (with much performance loss) is faster than the proposed DSTTD algorithm, while the speedup is $1.76$.

Let $N=M$. For different $N$, we carried out numerical experiments to count the average flops per time slot of the G-STBC algorithm in [9] and the proposed G-STBC algorithm in Fig. 1. It can be seen that they are consistent with the theoretical flops calculation. On the other hand, Fig. 2 shows the BER (bit error rate) performance of the algorithms in [7, 9] and the proposed algorithm in a G-STBC system with $8$ transmit and $4$ receive antennas, while Fig. 3 and Fig. 4 show the BER performance of the algorithms in [7, 8, 14] and the proposed algorithm in a DSTTD system with $2$ and $8$ receive antennas, respectively. We used QPSK modulation in Fig. 2, Fig. 3 and Fig. 4. As shown in Fig. 2 and Fig. 3, the proposed algorithm performs better than the efficient G-STBC algorithms in [9] and the efficient DSTTD algorithms in [14]. For example, it performs about $0.4$ dB better than the SQRD algorithm in [9] at BER $=10^{-4}$, and performs about $2$ dB better than the one-step fixed-order SIC algorithm for DSTTD in [14] at BER$=10^{-3}$. Fig. 2 and Fig. 3 also shows that with respect to the MMSE OSIC algorithm in [7], the proposed algorithm performs about $0.3$ dB worse in the G-STBC system and $0.4$ dB worse in the DSTTD system, at BER $=10^{-3}$. Moreover, it can be seen from Fig. 4 that for a large number of receive antennas, the performance difference among the presented DSTTD algorithms is small and even negligible.

We propose a fast recursive algorithm for G-STBC, which takes full advantage of the Alamouti structure in the equivalent channel matrix to reduce the computational complexity dramatically. With respect to the existing efficient algorithms for G-STBC or only for DSTTD, the proposed group-wise MMSE OSIC algorithm for G-STBC achieves better performance and usually requires less complexity. When $M=N$, the proposed algorithm speeds up the MMSE sub-optimal OSIC algorithm for G-STBC by $2.57$, speeds up the recently proposed DSTTD algorithm by up to $4.55$, and even requires less real multiplications than the linear ZF G-STBC algorithm.