Combined simplified maximum likelihood and sphere decoding algorithm for MIMO system

In this article, a new system model for sphere decoding （SD） algorithm is introduced. For the 2 × 2 multipleinput multiple-out （MIMO） system, a simplified maximum likelihood （SML） decoding algorithm is proposed based on the new model. The SML algorithm achieves optimal maximum likelihood （ML） performance, and drastically reduces the complexity as compared to the conventional SD algorithm. The improved algorithm is presented by combining the sphere decoding algorithm based on Schnorr-Euchner strategy （SE-SD） with the SML algorithm when the number of transmit antennas exceeds 2. Compared to conventional SD, the proposed algorithm has low complexity especially at low signal to noise ratio （SNR）. It is shown by simulation that the proposed algorithm has performance very close to conventional SD.     

一种低复杂度空间调制球形译码检测算法

现有的空间调制系统球形译码（Sphere-Decoding,SD）检测算法虽然能够较大地降低最大似然（Maximum-Likelihood,ML）检测算法的计算复杂度,但由于其更新半径比较松散、收敛较慢,计算复杂度降低的水平仍十分有限,尤其是在高阶调制系统下.针对上述问题,采用统计分布的思想对现有算法更新半径中的冗余项进行估计,提出了两种改进的球形译码检测算法.理论分析与仿真结果表明,改进算法在达到最优检测性能的同时,极大地降低了传统球形译码的计算复杂度,具有较好的理论和实际应用意义.     

Speeding up the Sphere Decoder With H∞ and SDP Inspired Lower Bounds

It is well known that maximum-likelihood (ML) decoding in many digital communication schemes reduces to solving an integer least-squares problem, which is NP hard in the worst-case. On the other hand, it has recently been shown that, over a wide range of dimensions N and signal-to-noise ratios (SNRs), the sphere decoding algorithm can be used to find the exact ML solution with an expected complexity that is often less than N³. However, the computational complexity of sphere decoding becomes prohibitive if the SNR is too low and/or if the dimension of the problem is too large. In this paper, we target these two regimes and attempt to find faster algorithms by pruning the search tree beyond what is done in the standard sphere decoding algorithm. The search tree is pruned by computing lower bounds on the optimal value of the objective function as the algorithm proceeds to descend down the search tree. We observe a tradeoff between the computational complexity required to compute a lower bound and the size of the pruned tree: the more effort we spend in computing a tight lower bound, the more branches that can be eliminated in the tree. Using ideas from semidefinite program (SDP)-duality theory and H^infin estimation theory, we propose general frameworks for computing lower bounds on integer least-squares problems. We propose two families of algorithms, one that is appropriate for large problem dimensions and binary modulation, and the other that is appropriate for moderate-size dimensions yet high-order constellations. We then show how in each case these bounds can be efficiently incorporated in the sphere decoding algorithm, often resulting in significant improvement of the expected complexity of solving the ML decoding problem, while maintaining the exact ML-performance.     

Efficient maximum-likelihood decoding of spherical lattice codes

A new framework for efficient exact Maximum- Likelihood (ML) decoding of spherical lattice codes is developed. It employs a double-tree structure: The first is that which underlies established tree-search decoders; the second plays the crucial role of guiding the primary search by specifying admissible candidates and is our present focus. Lattice codes have long been of interest due to their rich structure, leading to decoding algorithms for unbounded lattices, as well as those with axis-aligned rectangular shaping regions. Recently, spherical Lattice Space-Time (LAST) codes were proposed to realize the optimal diversity-multiplexing tradeoff of MIMO channels. We address the so-called boundary control problem arising from the spherical shaping region defining these codes. This problem is complicated because of the varying number of candidates to consider at each search stage; it is not obvious how to address it effectively within the frameworks of existing decoders. Our proposed strategy is compatible with all sequential tree-search detectors, as well as auxiliary processing such as the MMSEGDFE and lattice reduction. We demonstrate the superior performance and complexity profiles achieved when applying the proposed boundary control in conjunction with two current efficient ML detectors and show an improvement of 1dB over the state-of-the-art at a comparable complexity.     

Sphere decoding algorithms with improved radius search

We start by identifying a relatively efficient version of sphere decoding algorithm (SDA) that performs exact maximum-likelihood (ML) decoding. We develop novel algorithms based on an improved increasing radius search (IIRS), which offer error performance and decoding complexity between two extremes: the ML receiver and the ing-canceling (NC) receiver with detection ordering. With appropriate choices of parameters, our IIRS offers the flexibility to trade error performance for complexity. We provide design intuitions and guidelines, analytical parameter specifications, and a semianalytical error-performance analysis. Simulations illustrate that IIRS achieves considerable complexity reduction, while maintaining performance close to ML.     

Breadth-First Signal Decoder: A Novel Maximum-Likelihood Scheme for Multi-Input–Multi-Output Systems

A number of decoding schemes have recently been proposed to perform maximum-likelihood (ML) detection for multi-input-multi-output (MIMO) systems. In this paper, employing a ldquobreadth-firstrdquo search algorithm for closet points in a lattice, we propose a novel ML decoding scheme called the breadth-first signal decoder (BSIDE). Through analysis and computer simulations, it is shown that the BSIDE has the same bit-error-rate performance as the conventional ML decoders while allowing significantly lower computational complexity. In addition, we introduce a simple tuning scheme that allows the BSIDE to have a performance-complexity tradeoff capability as necessary.     

Accelerated sphere decoding for multipleinput multiple-output systems using an adaptive statistical threshold

The authors present a complexity reduced near-maximum-likelihood (ML) scheme for the decoding of multiple-input multiple-output (MIMO) systems, which is targeted at a recently proposed fixed-complexity sphere decoder (FSD). The proposed decoder that the authors call the statistical threshold-based FSD (ST-FSD) combines a threshold constraint strategy with the FSD search region, thus speeding up the FSD algorithm by avoiding unnecessary search paths. As a consequence, higher efficiency and lower complexity can be obtained. The optimum threshold is derived through analysis of the statistical distributions of the correct and erroneous estimates. Furthermore, a tight lower bound on the threshold has been obtained by using the singular value decomposition (SVD) method and applied to the FSD. From simulation results, the proposed scheme is shown to be able to achieve a significant reduction in computational complexity with almost no performance degradation compared to the original FSD algorithm. Moreover, a novel grouped architecture for efficient hardware implementation of the proposed ST-FSD algorithm is motivated through simulation results and shown to compare favourably with the alternative options. This confirms that the ST-FSD is advantageous with respect to the original FSD in terms of the overall complexity.     

Area-Efficient Antenna-Scalable MIMO Detector for K-best Sphere Decoding

K-best sphere decoding is one of the most popular MIMO (Multi-Input Multi-Output) detection algorithms because of its low complexity and close to Maximum Likelihood (ML) Bit Error Rate (BER) performance. Unfortunately, conventional multi-stage sphere decoders suffer from the inability to adapt to varying antenna configurations, requiring implementation redesign for each specific array structure. In this paper, we propose a reconfigurable in-place architecture that is scalable to an arbitrary number of antennas at run-time, while reducing area significantly compared with other sphere decoders. To improve the throughput of the in-place architecture without any degradation in BER performance, we propose partial-sort-bypass and symbol interleaving techniques, and also exploit multi-core design. Implementation results for a 16-QAM MIMO decoder in a 130 nm CMOS technology show a 41% reduction in area compared to the smallest sphere decoder while maintaining antenna reconfigurability, and better throughput. When implemented for the 802.11n standard, our architecture results in 42% reduction in area compared to the multi-stage architecture.     

基于可信位置排序的咬尾卷积码译码算法

咬尾卷积码的传统译码算法没有考虑咬尾格形图的循环性,译码起始位置固定,译码效率相对较低。该文首次证明了咬尾卷积码基于格形图的译码算法与译码起始位置无关,即从任意位置开始译码得到的最优咬尾路径即为全局最优咬尾路径。基于此提出一种基于可信位置排序的咬尾卷积码译码算法。新算法利用咬尾格形图的循环性,根据接收到的信道输出序列估算每个译码起始位置的可靠性,从而选择一个可靠性最高的译码起始位置。和传统译码算法相比,所提算法具有更快的收敛速度。     

多天线系统中逼近最大似然的快速检测算法

该文针对无编码的多输入多输出无线通信系统中的最大似然检测接收机在发端天线数较多、调制阶数较高时计算复杂度过高的问题,提出了一种低复杂度的球形译码算法。该算法首先利用信道信息对待检测的发送信号矢量进行分组,然后对各组内的信号矢量采用球形译码进行最大似然检测,并在组间做干扰消除。理论分析和仿真表明,该算法不仅复杂度低,而且能够逼近最大似然检测的性能。     

基于MIMO系统的球形译码算法的改进

在最大似然检测中,球形译码算法是一种有效的快速算法。提出一种基于MIMO系统的新的快速球形译码算法,它的复杂度比传统的算法要小的多。在提出的方法中,初始半径的选择并不重要。这种改进算法的译码性能和复杂度由两个参数来控制。因此,该方法存在着译码性能和复杂度的均衡。通过计算机仿真,可以看到,提出改进算法的译码性能得到了较大的提高。     

A unified framework for tree search decoding: rediscovering the sequential decoder

We consider receiver design for coded transmission over linear Gaussian channels. We restrict ourselves to the class of lattice codes and formulate the joint detection and decoding problem as a closest lattice point search (CLPS). Here, a tree search framework for solving the CLPS is adopted. In our framework, the CLPS algorithm is decomposed into the preprocessing and tree search stages. The role of the preprocessing stage is to expose the tree structure in a form matched to the search stage. We argue that the forward and feedback (matrix) filters of the minimum mean-square error decision feedback equalizer (MMSE-DFE) are instrumental for solving the joint detection and decoding problem in a single search stage. It is further shown that MMSE-DFE filtering allows for solving underdetermined linear systems and using lattice reduction methods to diminish complexity, at the expense of a marginal performance loss. For the search stage, we present a generic method, based on the branch and bound (BB) algorithm, and show that it encompasses all existing sphere decoders as special cases. The proposed generic algorithm further allows for an interesting classification of tree search decoders, sheds more light on the structural properties of all known sphere decoders, and inspires the design of more efficient decoders. In particular, an efficient decoding algorithm that resembles the well-known Fano sequential decoder is identified. The excellent performance-complexity tradeoff achieved by the proposed MMSE-DFE Fano decoder is established via simulation results and analytical arguments in several multiple-input multiple-output (MIMO) and intersymbol interference (ISI) scenarios.     

Parallel High Throughput Soft-Output Sphere Decoding Algorithm

Multiple-Input-Multiple-Output communication systems demand fast sphere decoding with high performance. To speed up the computation, we propose a scheme with multiple fixed complexity sphere decoders to construct a parallel soft-output fixed complexity sphere decoder (PFSD). The proposed decoder is highly parallel and has performance comparable to soft-output list fixed complexity sphere decoder (LFSD) and K-best sphere decoder. In addition, we propose a parallel QR decomposition algorithm to lower the preprocessing overhead, and a low complexity LLR algorithm to allow parallel update of LLR values. We demonstrate that the PFSD algorithm can increase the throughput and reduce bit error rate of a soft-output solution in a 4 × 4 16-QAM system, and has superior performance compared to other soft decoders with comparable throughput and computation complexity. The PFSD algorithm has been mapped onto Xilinx XC4VLX160 FPGA. The resulting PFSD decoder can achieve up to 75 Mbps throughput for 4 × 4 64-QAM configuration at 100MHz with low control overhead.     

连续衰落信道下适用于酉空时调制的多符号差分球形译码算法

基于连续衰落信道假设,将一种具有递推形式的近似最大似然(ML)度量嵌入自动球形译码算法中,提出了多符号差分近似自动球形译码(MSDAASD)。该算法适用于一般酉空时星座,克服了准静态信道假设下多符号差分球形译码(MSDSD)的错误平层现象,具有接近ML检测的性能,其平均复杂度在大多数情况下低于相同假设下的判决反馈检测算法。     

Iterative decoding of convolutionally encoded signals overmultipath Rayleigh fading channels

We analyze and compare several strategies for iteratively decoding trellis-encoded signals over channels with memory. Soft-in/soft-out extensions of reduced-complexity trellis search algorithms such as delayed decision-feedback sequence estimating (DDFSE) or parallel decision-feedback decoding (PDFD) algorithms are used instead of conventional BCJR and min-log-BCJR algorithms. It has been shown that for long channel impulse responses and/or high modulation orders where the BCJR algorithm becomes prohibitively complex, the proposed algorithms offer very good performance with low complexity. The problem of channel estimation in practical implementation of turbo detection schemes is studied in the second part. Two methods of channel reestimation are proposed: one based on the expectation-maximization (EM) algorithm and the second on a simple Bootstrap technique. Both algorithms are shown to dramatically improve the performance of the classical pseudo inverse channel estimation performed initially on a training sequence     

Two decoding algorithms for tailbiting codes

The paper presents two efficient Viterbi decoding-based suboptimal algorithms for tailbiting codes. The first algorithm, the wrap-around Viterbi algorithm (WAVA), falls into the circular decoding category. It processes the tailbiting trellis iteratively, explores the initial state of the transmitted sequence through continuous Viterbi decoding, and improves the decoding decision with iterations. A sufficient condition for the decision to be optimal is derived. For long tailbiting codes, the WAVA gives essentially optimal performance with about one round of Viterbi trial. For short- and medium-length tailbiting codes, simulations show that the WAVA achieves closer-to-optimum performance with fewer decoding stages compared with the other suboptimal circular decoding algorithms. The second algorithm, the bidirectional Viterbi algorithm (BVA), employs two wrap-around Viterbi decoders to process the tailbiting trellis from both ends in opposite directions. The surviving paths from the two decoders are combined to form composite paths once the decoders meet in the middle of the trellis. The composite paths at each stage thereafter serve as candidates for decision update. The bidirectional process improves the error performance and shortens the decoding latency of unidirectional decoding with additional storage and computation requirements. Simulation results show that both proposed algorithms effectively achieve practically optimum performance for tailbiting codes of any length.     

A simple low-complexity algorithm for generalized spatial modulation

Generalized spatial modulation (GSM) is an extension of spatial modulation which is significant for the next generation communication systems. Optimal detection process for the GSM is the maximum-likelihood (ML) detection which jointly detects the antenna combinations and transmitted symbols. However, the receiver is much more complicated than SM due to inter-antenna interference and/or increased number of combinations. Therefore, the computational complexity of the ML detection grows with the number of transmit antennas and the signal constellation size. In this letter, we introduce a novel and simple detection algorithm which uses sub-optimal method based on the least squares solution to detect likely antenna combinations. Once the antenna indices are detected, ML detection is utilized to identify the transmitted symbols. For obtaining near-ML performance while keeping lower complexity than ML detection, sphere decoding is applied. Our proposed algorithm reduces the search complexity while achieving a near optimum solution. Computer simulation results show that the proposed algorithm performs close to the optimal (ML) detection resulting in a significant reduction of computational complexity.     

BEAST decoding of block codes obtained via convolutional codes

BEAST is a bidirectional efficient algorithm for searching trees. In this correspondence, BEAST is extended to maximum-likelihood (ML) decoding of block codes obtained via convolutional codes. First it is shown by simulations that the decoding complexity of BEAST is significantly less than that of the Viterbi algorithm. Then asymptotic upper bounds on the BEAST decoding complexity for three important ensembles of codes are derived. They verify BEAST's high efficiency compared to other algorithms. For high rates, the new asymptotic bound for the best ensemble is in fact better than previously known bounds.     

On decoding of low-density parity-check codes over the binary erasure channel

This paper investigates decoding of low-density parity-check (LDPC) codes over the binary erasure channel (BEC). We study the iterative and maximum-likelihood (ML) decoding of LDPC codes on this channel. We derive bounds on the ML decoding of LDPC codes on the BEC. We then present an improved decoding algorithm. The proposed algorithm has almost the same complexity as the standard iterative decoding. However, it has better performance. Simulations show that we can decrease the error rate by several orders of magnitude using the proposed algorithm. We also provide some graph-theoretic properties of different decoding algorithms of LDPC codes over the BEC which we think are useful to better understand the LDPC decoding methods, in particular, for finite-length codes.     

基于贪心策略的大规模MIMO系统信号检测算法

针对传统球形译码性能和计算复杂度受到初始半径及搜索策略制约的问题,提出了一种新的基于M算法的贪心策略球形译码检测算法,对树搜索的方法进行了改进,先将该层信号集合中的距离增量进行排序,然后选择距离增量最小的M个点为信号点,这样每一次选取的信号点相对该层都是局部最优的.仿真结果表明,相比于传统球形译码检测算法,当M为1时,该算法可以降低约30％的计算复杂度.使球形译码算法的效率得到了很大的提高,可以运用于大规模MIMO系统中.