Improved Recursive Algorithms for V-BLAST to Save Computations and Memories

Spatial-multiplexing (SM) mutiple-input multiple-output (MIMO) wireless communication systems [1] transmit multiple substreams concurrently from multiple antennas, to achieve very high data rate and spectral efficiency in rich multi-path environments. As the number of transmit antennas increases, the maximum-likelihood (ML) MIMO detectors [2, 3, 4] with the optimum performance quickly require excessive computational complexity. Vertical Bell Laboratories Layered Space-Time (V-BLAST) systems [5] are SM MIMO schemes with good performance-complexity tradeoff, where usually ordered successive interference cancellation (OSIC) detectors based on hard decisions are adopted to detect the substream symbols iteratively with the optimal ordering based on signal-to-noise ratio (SNR). In each iteration, one of the undetected symbols is detected through a linear zero-forcing (ZF) or minimum meansquare error (MMSE) filter, and then the hard decision of the detected symbol is utilized to cancel the interference in the received symbol vector. OSIC detectors choose the undetected symbol with the highest SNR in each iteration to perform detection and interference cancellation, since the unreliable hard decision causes detrimental error propagation (EP) [6].

EP due to imperfect hard decisions can severely limit the performance of OSIC detectors [6, 7]. Then the ordering schemes based on the loglikelihood ratio (LLR) [7, 8] and maximum a posteriori probability (MAP) [9] exploit the instantaneous noise and the resulting symbol decision error, respectively, to achieve a performance gain over the conventional SNR ordering scheme. On the other hand, iterative soft interference cancellation (ISIC) MIMO detectors were proposed to reduce the EP effects by replacing hard decisions with soft decisions in interference cancellation [10, 11, 12, 13], which are extended to iterative detection-decoding (IDD) schemes with soft-decision feedback for coded systems, and can achieve near ML performance with controllable complexity [14, 15]. Since the direct-sequence code-division multiple-access (DS-CDMA) system can be modeled as a MIMO channel [14], the ISIC MIMO detectors are also obtained in [16] and [14] by applying the ISIC detector in [17] for the coded DS-CDMA system. For the case with the non-linear or unknown channel model, a data-driven implementation of the ISIC MIMO detector was proposed in [15], where simple dedicated deep neural networks (DNNs) replace the channel model-based building blocks of the ISIC MIMO detector in [10].

The calculation of OSIC and ISIC detectors for MIMO requires quite high complexity. Several efficient implementations of OSIC were proposed, which mainly include the recursive algorithms [18, 19, 20, 21] and the square-root algorithms [22, 23, 24, 25] based on the detection error covariance matrix and its square-root matrix, respectively. On the other hand, several efficient implementations of ISIC were proposed in [26, 27].

In addition to the above-mentioned EP effect reductions and efficient implementations, there have been many other researches related to the OSIC MIMO detector recently. It was applied in linear dispersion (LD) based perfect space-time coded MIMO systems [28], MIMO orthogonal frequency division multiplexing (OFDM) with index modulation (IM) [29], and the power-domain non-orthogonal multiple access (NOMA) systems with MIMO [30, 31, 32]. For MIMO filter bank multicarrier (FBMC) systems, neighbourhood detection based OSIC detectors with QR and sorted QR decompositions were proposed in [33]. For 5G mobile networks with massive MIMO, the OSIC detector was combined with the K-correction algorithm based on ML criterion and the partial tree search detection in [34] and [35], respectively. In [36], an exact closed-form expression was given for the average outage probability of zero-forcing (ZF) OSIC V-BLAST with $2$ transmitters and $r\geq 2$ receivers. Moreover, comprehensive survey of MIMO detectors (including OSIC detectors) has been given in [37] and [38].

In this paper, we focus on the recursive OSIC detectors [18, 19, 20, 21]. The original recursive algorithm proposed in [18] was improved in [19] and [20] to reduce the computational complexity, and the improvements were then incorporated in [21] to give the “fastest known algorithm” before [21]. The contributions of [21] also include one recursive algorithm with speed advantage that adopts a further improvement for the “fastest known algorithm” with the speedups claimed to be $1.3$, and the other recursive algorithm with memory saving that is slower than the “fastest known algorithm”. We further improve the matrix inversion applied in [19] and the interference cancellation scheme proposed in [20], both of which are part of the recursive algorithm with speed advantage in [21].

Firstly, the lemma for inversion of partitioned matrix [39, Ch. 14.12] applied in [19] is replaced with another one [40, Equ. 8], to accelerate the computation of the initial detection error covariance matrix. Then the formulas adopted by us for matrix inversion are utilized to deduce the improved interference cancellation scheme with memory saving, which uses the entries in the error covariance matrix instead of those in its inverse matrix. Finally, we use the above two improvements to propose the recursive algorithm with both speed advantage and memory saving, which is the fastest and requires the least memories compared to the existing recursive algorithms. In our future works, the proposed recursive OSIC detector with both speed advantage and memory saving will be extended to the recursive ISIC detector, which can reduce the required computations and memories compared to the low-complexity ISIC detector proposed in [27] recently.

The V-BLAST system model is overviewed in section II, followed by the description of the recursive algorithms for V-BLAST in [18, 20, 19, 21] in Section III. Two recursive algorithms for V-BLAST are proposed in Section IV to improve the recursive algorithm with speed advantage in [21]. Then the presented recursive algorithms for V-BLAST are compared in Section V. Finally, we make conclusion in Section VI.

In what follows, uppercase and lowercase bold face letters represent matrices and column vectors, respectively. $(\bullet)^{T}$, $(\bullet)^{*}$, $(\bullet)^{H}$, and $(\bullet)^{-1}$ denote transposition, conjugate, conjugate transposition, and inversion of matrices, respectively. ${\bf{{\rm I}}}_{M}$ is the identity matrix with size $M$. Moreover, the MATLAB standard is followed in the notations for some variables.

The considered V-BLAST system consists of $M$ transmit antennas and $N(\geq M)$ receive antennas in a rich-scattering and flat-fading wireless channel. At the transmitter, the data stream is de-multiplexed into $M$ sub-streams, and each sub-stream is encoded and fed to its respective transmit antenna. Denote the vector of transmit symbols from $M$ antennas as

and denote the $N\times M$ complex channel matrix ${\bf{H}}$ as

where ${\bf{h}}_{:m}$ ($m=1,2,\cdots,M$) is the $m^{th}$ column of ${\bf{H}}$. Then the symbols received in $N$ antennas can be written as

where ${\bf{n}}$ is the $N\times 1$ complex Gaussian noise vector with zero mean and covariance $\sigma_{n}^{2}{\bf{{\rm I}}}_{N}$.

The conventional V-BLAST scheme detects $M$ components of ${\bf{s}}_{M}$ by $M$ recursions with the optimal ordering based on SNR. In each recursion, the component with the highest post detection SNR among all the undetected components is detected by a linear filter and then its effect is substracted from the received signal vector [5, 22, 18]. Assume that in the $i^{th}$ ($i=1,2,\cdots,M$) recursion, the undetected $m=M-i+1$ transmit symbols and the corresponding channel matrix are the first $m$ entries and columns of the permuted ${\bf{s}}_{M}$ and ${\bf{H}}_{M}$, respectively, i.e., ${\bf{s}}_{m}$ and ${\bf{H}}_{m}$ defined by (1) and (2). Then we obtain the reduced-order problem (3) with $M$ replaced by any $m(<M)$. Accordingly, the linear MMSE estimation of the undetected $m$ symbols (i.e., ${\bf{s}}_{m}$) is

where $\alpha=\frac{\sigma_{n}^{2}}{\sigma_{s}^{2}}$, and $\sigma_{s}^{2}$ is the power of each symbol in ${\bf{s}}_{M}$.

In this section, we propose ¹¹1Only Improvement V was presented in part at IEEE International Conference on Communications (ICC). Notice that Improvement V is obtained by applying [40, Equ. 8] in this paper, while it was re-derived without citing any literature at ICC’09. Improvements V and VI to replace the above Improvements I and II, respectively. Improvement V accelerates Improvement I that inverts a partitioned matrix. Then the formulas adopted in Improvement V are applied to deduce Improvement VI, which saves memories without sacrificing speed compared to Improvement II, by using ${\bf{Q}}$ instead of ${\bf{R}}$ for interference cancellation in the recursion phase.

The dominant complexity of (20d) is $\frac{1}{2}M^{3}$ complex multiplications and additions, which is dedicated to computing ${\bf{Q}}_{m-1}{\bf{\bar{r}}}_{m}$ and ${\bf{Q}}_{m-1}+\omega_{m}{\bf{\tilde{q}}}_{m}{\bf{\tilde{q}}}_{m}^{H}$ for $m=2,3,...,M$. The complexity of (13c) should be $\frac{5}{6}M^{3}$ instead of $\frac{1}{2}M^{3}$ claimed in [21], which is dedicated to computing ${\bf{g}}_{m-1}={\bf{Q}}_{m-1}{\bf{\bar{r}}}_{m}$, ${\bf Q}_{m-1}+{\bf g}_{m-1}{\bf g}_{m-1}^{H}/(\cdots)$ and ${\bf{\bar{Q}}}_{m-1}{\bf{\bar{r}}}_{m}$. Compared to the inversion step in [19, 21] to compute the initial ${\bf Q}$ by (13c) and (12), the proposed inversion step by (20d) and (12) achieves the speedup of $(\frac{5}{6})/(\frac{1}{2})=1.67$, and requires only $\frac{1}{3}$ divisions.

The complexity claimed in [21] for the above-mentioned inversion step to compute the initial ${\bf Q}$ should increase by $\frac{5}{6}M^{3}-\frac{1}{2}M^{3}=\frac{1}{3}M^{3}$. Then actually “fastest known algorithm” before [21] and the recursive algorithm with speed advantage in [21] require the complexities of $\frac{1}{2}M^{2}N+\frac{4}{3}M^{3}$ and $\frac{1}{2}M^{2}N+M^{3}$, respectively, instead of $\frac{1}{2}M^{2}N+M^{3}$ and $\frac{1}{2}M^{2}N+\frac{2}{3}M^{3}$ claimed in [21]. Coincidentally, the above $\frac{1}{2}M^{2}N+\frac{2}{3}M^{3}$ (claimed in [21]) is exactly the dominant complexity of the proposed recursive algorithm I with speed advantage, and is also that of the proposed recursive algorithm II with both speed advantage and memory saving, since no dominant complexity is required to compute (15), (17), (23) and (24) from Improvements II and VI. On the other hand, the recursive algorithm with memory saving in [21] requires $2M^{2}N+\frac{1}{6}M^{3}$ multiplications instead of $\frac{5}{2}M^{2}N+\frac{1}{6}M^{3}$ multiplications claimed in [21, Equ. 27], since it adopts Improvement III where the computation of the initial ${\bf{Q}}$ by (6) costs $\frac{3}{2}M^{2}N$ multiplications [20, near Equ. 12] instead of $2M^{2}N$ multiplications claimed in [21, Equ. 27].

The dominant complexities of the presented recursive V-BLAST algorithms are compared in Table I, where an item $j$ denotes $j$ multiplications and additions, and $(j,k)$ denotes $j$ multiplications and $k$ additions. It can be seen from Table I that when $M=N$, the actual speedup of the algorithm with speed advantage in [21] over the previous “fastest known algorithm” should be $(\frac{11}{6})/(\frac{3}{2})=1.22$ instead of $1.3$ claimed in [21], while the speedups of either proposed recursive algorithm over the algorithm in [21] with speed advantage and that with memory saving are $(\frac{3}{2})/(\frac{7}{6})=1.3$ and $(\frac{13}{6})/(\frac{7}{6})\approx 1.86$, respectively.

Assuming $N=M$, we carried out numerical experiments to count the average floating-point operations (flops) of the presented recursive V-BLAST algorithms, including the original algorithm [18], the algorithm with memory saving in [21], the “fastest known algorithm” before [21], the algorithm with speed advantage in [21], the proposed algorithm with speed advantage, and the proposed algorithm with both speed advantage and memory saving. All results are shown in Fig. 1. It can be seen that they are consistent with the theoretical flops calculation.

With respect to the “fastest known algorithm” before [21], the algorithm with memory saving in [21] (i.e., Algorithm 2) costs more computations to save memories for storing ${\bf{R}}$, and then only needs to store ${\bf{H}}$ and ${\bf{Q}}$. As a comparison ⁴⁴4We only compare memories for storing matrices, which are at least $2\times 2$., the proposed recursive algorithm II with both speed advantage and memory saving only stores ${\bf{Q}}$ in the recursion phase, and only uses memories for storing ${\bf{H}}$ in the initialization phase since it covers ${\bf{H}}$ with ${\bf{R}}$ and ${\bf{Q}}$ successively. Accordingly, it can be concluded that the proposed algorithm II saves about half memories with respect to the algorithm with memory saving in [21], and then requires the least memories among the existing recursive V-BLAST algorithms.

Firstly, we presented the original recursive V-BLAST algorithm, and its existing Improvements I-IV to reduce the computational complexity. Moreover, we also described the existing recursive V-BLAST algorithm with speed advantage and that with memory saving, which incorporate Improvements I-IV and only Improvements III-IV into the original algorithm, respectively. Then we propose Improvements V and VI to replace Improvements I and II, respectively. Instead of the lemma for inversion of partitioned matrix applied in Improvement I, the proposed Improvement V uses another lemma to compute the inverse matrix with less complexity. On the other hand, the formulas adopted in the proposed Improvement V are applied to deduce Improvement VI with the improved interference cancellation scheme, which saves memories without sacrificing speed compared to Improvement II.

In the existing recursive V-BLAST algorithm with speed advantage, the proposed recursive algorithm I with speed advantage replaces Improvement I with Improvement V, while the proposed recursive algorithm II with both speed advantage and memory saving replaces Improvements I and II with Improvements V and VI, respectively. With respect to the existing algorithm with speed advantage, both proposed algorithms achieve the speedup of $1.3$, and speed up the matrix inversion step by the factor of $1.67$. On the other hand, the proposed algorithm II achieves the speedup of $1.86$ and saves about half memories, compared to the existing recursive V-BLAST algorithm with memory saving, and requires the least memories among the existing recursive algorithms.

We only focus on the OSIC detectors throughout this paper. In our future works, we will show that the reordered description based on the equivalent channel matrix for the ISIC detector can be regarded as the extension of the OSIC detector. Accordingly, we will extend the recursive OSIC detector with both speed advantage and memory saving proposed in this paper to the recursive ISIC detector, which can reduce the required computations and memories compared to the recently proposed low-complexity ISIC detector.