The Experts below are selected from a list of 5064 Experts worldwide ranked by ideXlab platform
John Thompson - One of the best experts on this subject based on the ideXlab platform.
-
the error probability of the fixed complexity Sphere Decoder
IEEE Transactions on Signal Processing, 2009Co-Authors: Joakim Jalden, L G Barbero, Bjorn Ottersten, John ThompsonAbstract:The fixed-complexity Sphere Decoder (FSD) has been previously proposed for multiple-input multiple-output (MIMO) detection in order to overcome the two main drawbacks of the Sphere Decoder (SD), namely its variable complexity and its sequential structure. Although the FSD has shown remarkable quasi-maximum-likelihood (ML) performance and has resulted in a highly optimized real-time implementation, no analytical study of its performance existed for an arbitrary MIMO system. Herein, the error probability of the FSD is analyzed, proving that it achieves the same diversity as the maximum-likelihood detector (MLD) independent of the constellation used. In addition, it can also asymptotically yield ML performance in the high-signal-to-noise ratio (SNR) regime. Those two results, together with its fixed complexity, make the FSD a very promising algorithm for uncoded MIMO detection.
-
extending a fixed complexity Sphere Decoder to obtain likelihood information for turbo mimo systems
IEEE Transactions on Vehicular Technology, 2008Co-Authors: L G Barbero, John ThompsonAbstract:A list extension for a fixed-complexity Sphere Decoder (FSD) to perform iterative detection and decoding in turbo-multiple input-multiple output (MIMO) systems is proposed in this paper. The algorithm obtains a list of candidates that can be used to calculate likelihood information about the transmitted bits required by the outer Decoder. The list FSD (LFSD) overcomes the two main problems of the list Sphere Decoder (LSD), namely, its variable complexity and the sequential nature of its tree search. It combines a search through a very small subset of the complete transmit constellation and a specific channel matrix ordering to approximate the soft- quality of the list of candidates obtained by the LSD. A simple method is proposed to generate that subset, extending the subset searched by the original FSD. Simulation results show that the LFSD can be used to approach the performance of the LSD while having a lower and fixed complexity, making the algorithm suitable for hardware implementation.
-
fixing the complexity of the Sphere Decoder for mimo detection
IEEE Transactions on Wireless Communications, 2008Co-Authors: L G Barbero, John ThompsonAbstract:A new detection algorithm for uncoded multiple input-multiple output (MIMO) systems based on the complex version of the Sphere Decoder (SD) is presented in this paper. It performs a fixed number of operations during the detection process, overcoming the two main problems of the SD from an implementation point of view: its variable complexity and its sequential nature. The algorithm combines a novel channel matrix ordering with a search through a very small subset of the complete transmit constellation. A geometrically-based method is used to study the effect the proposed ordering has on the statistics of the MIMO channel. Using those results, a generalization is given for the structure this subset needs to follow in order to achieve quasi-maximum likelihood (ML) performance. Simulation results show that it has only a very small bit error rate (BER) degradation compared to the original SD while being suited for a fully-pipelined hardware implementation due to its low and fixed complexity.
-
full diversity detection in mimo systems with a fixed complexity Sphere Decoder
International Conference on Acoustics Speech and Signal Processing, 2007Co-Authors: Joakim Jalden, L G Barbero, Bjorn Ottersten, John ThompsonAbstract:The fixed-complexity Sphere Decoder (FSD) has been previously proposed for multiple input-multiple output (MIMO) detection to overcome the two main drawbacks of the original Sphere Decoder (SD), namely its variable complexity and sequential structure. As such, the FSD is highly suitable for hardware implementation and has shown remarkable performance through simulations. Herein, we explore the theoretical aspects of the algorithm and prove that the FSD achieves the same diversity order as the maximum likelihood detector (MLD). Further, we show that the coding loss can be made negligible in the high signal to noise ratio (SNR) regime with a significantly lower complexity than that of the MLD.
-
performance of the complex Sphere Decoder in spatially correlated mimo channels
Iet Communications, 2007Co-Authors: L G Barbero, John ThompsonAbstract:The use of multiple antennas at both transmitter and receiver is a promising technique for significantly increasing the capacity and spectral efficiency of wireless communication systems. In particular, spatial multiplexing techniques provide a means of increasing the data rate of the system without having to increase the transmitter power or the bandwidth. In recent years, special attention has been paid to the Sphere Decoder (SD) to detect spatially multiplexed signals. It provides optimal maximum likelihood (ML) performance with reduced complexity, compared to the maximum likelihood detector (MLD). An analysis of the performance of the SD in the presence of spatially correlated multiple-input multiple-output (MIMO) channels is presented. Analytical and simulation results show that, compared to suboptimal linear and nonlinear MIMO detectors, the SD suffers a complexity increase when correlation exists between the antennas at the transmitter or the receiver. In addition, a novel low-complexity channel ordering technique is introduced to reduce the complexity of the SD.
L G Barbero - One of the best experts on this subject based on the ideXlab platform.
-
ICC - A Sphere Decoder with Approximate QR Decomposition for Frequency-Selective Channels
2010 IEEE International Conference on Communications, 2010Co-Authors: L G Barbero, Tharmalingam Ratnarajah, Pei Xiao, Mathini Sellathurai, Colin F. N. CowanAbstract:This paper presents a method to significantly reduce the preprocessing complexity of the Sphere Decoder (SD) in frequency-selective channels. The method consists of calculating an approximate QR decomposition (AQRD) of the channel matrix, making use of its special Toeptliz and block-Topelitz structure in single and multiple-antenna frequency-selective channels, respectively. The AQRD obtains the QR decomposition of a small submatrix of the channel matrix and extends that result to the rest of the matrix, resulting in a considerable complexity reduction compared to the original full QR decomposition (FQRD). Simulation results show that, despite the lower complexity of the AQRD, it causes only a small bit error rate (BER) performance degradation in the SD.
-
the error probability of the fixed complexity Sphere Decoder
IEEE Transactions on Signal Processing, 2009Co-Authors: Joakim Jalden, L G Barbero, Bjorn Ottersten, John ThompsonAbstract:The fixed-complexity Sphere Decoder (FSD) has been previously proposed for multiple-input multiple-output (MIMO) detection in order to overcome the two main drawbacks of the Sphere Decoder (SD), namely its variable complexity and its sequential structure. Although the FSD has shown remarkable quasi-maximum-likelihood (ML) performance and has resulted in a highly optimized real-time implementation, no analytical study of its performance existed for an arbitrary MIMO system. Herein, the error probability of the FSD is analyzed, proving that it achieves the same diversity as the maximum-likelihood detector (MLD) independent of the constellation used. In addition, it can also asymptotically yield ML performance in the high-signal-to-noise ratio (SNR) regime. Those two results, together with its fixed complexity, make the FSD a very promising algorithm for uncoded MIMO detection.
-
on the complexity of the Sphere Decoder for frequency selective mimo channels
IEEE Transactions on Signal Processing, 2008Co-Authors: L G Barbero, Tharmalingam Ratnarajah, C F N CowanAbstract:This paper compares the complexity of the Sphere Decoder (SD) and a previously proposed detection scheme, denoted here as block SD (BSD), when they are applied to the detection of multiple-input multiple-output (MIMO) systems in frequency-selective channels. The complexity of both algorithms depends on their preprocessing and tree search stages. Although the BSD was proposed as a means of greatly reducing the complexity of the preprocessing stage of the SD, no study was done on how the complexity of the tree search stage could be affected by that reduced preprocessing stage. This paper shows, both analytically and through simulation, that the reduction in preprocessing complexity provided by the BSD has the side effect of increasing the complexity of its tree search stage compared to that of the SD, independent of the signal-to-noise ratio (SNR). In addition, this paper shows how sorting the columns of the frequency-selective channel matrix in the SD does not reduce the complexity of the tree search stage, contrary to what occurs in frequency-flat channels.
-
extending a fixed complexity Sphere Decoder to obtain likelihood information for turbo mimo systems
IEEE Transactions on Vehicular Technology, 2008Co-Authors: L G Barbero, John ThompsonAbstract:A list extension for a fixed-complexity Sphere Decoder (FSD) to perform iterative detection and decoding in turbo-multiple input-multiple output (MIMO) systems is proposed in this paper. The algorithm obtains a list of candidates that can be used to calculate likelihood information about the transmitted bits required by the outer Decoder. The list FSD (LFSD) overcomes the two main problems of the list Sphere Decoder (LSD), namely, its variable complexity and the sequential nature of its tree search. It combines a search through a very small subset of the complete transmit constellation and a specific channel matrix ordering to approximate the soft- quality of the list of candidates obtained by the LSD. A simple method is proposed to generate that subset, extending the subset searched by the original FSD. Simulation results show that the LFSD can be used to approach the performance of the LSD while having a lower and fixed complexity, making the algorithm suitable for hardware implementation.
-
fixing the complexity of the Sphere Decoder for mimo detection
IEEE Transactions on Wireless Communications, 2008Co-Authors: L G Barbero, John ThompsonAbstract:A new detection algorithm for uncoded multiple input-multiple output (MIMO) systems based on the complex version of the Sphere Decoder (SD) is presented in this paper. It performs a fixed number of operations during the detection process, overcoming the two main problems of the SD from an implementation point of view: its variable complexity and its sequential nature. The algorithm combines a novel channel matrix ordering with a search through a very small subset of the complete transmit constellation. A geometrically-based method is used to study the effect the proposed ordering has on the statistics of the MIMO channel. Using those results, a generalization is given for the structure this subset needs to follow in order to achieve quasi-maximum likelihood (ML) performance. Simulation results show that it has only a very small bit error rate (BER) degradation compared to the original SD while being suited for a fully-pipelined hardware implementation due to its low and fixed complexity.
Babak Hassibi - One of the best experts on this subject based on the ideXlab platform.
-
further results on speeding up the Sphere Decoder
International Conference on Acoustics Speech and Signal Processing, 2006Co-Authors: M Stojnic, Haris Vikalo, Babak HassibiAbstract:In many communication applications, maximum-likelihood decoding 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 and SNR, the Sphere Decoder can be used to find the exact solution with an expected complexity that is roughly cubic in the dimension of the problem. However, the computational complexity becomes prohibitive if the SNR is too low and/or if the dimension of the problem is too large. In earlier work, we targeted these two regimes attempting to find faster algorithms by pruning the search tree beyond what is done in the standard Sphere Decoder. The search tree is pruned by computing lower bounds on the possible optimal solution as we proceed to go down the tree. A trade-off between the computational complexity required to compute the lower bound and the size of the pruned tree is readily observed: the more effort we spend in computing a tight lower bound, the more branches that can be eliminated in the tree. Thus, even though it is possible to prune the search tree (and hence the number of points visited) by several orders of magnitude, this may be offset by the computations required to perform the pruning. In this paper, we propose a computationally efficient lower bound which requires solving a single semi-definite program (SDP) at the top of the search tree; the solution to the SDP is then used to deduce the lower bounds on the optimal solution on all levels of the search tree. Simulation results indicate significant improvement in the computational complexity of the proposed algorithm over the standard Sphere decoding
-
an h infinity based lower bound to speed up the Sphere Decoder
International Workshop on Signal Processing Advances in Wireless Communications, 2005Co-Authors: M Stojnic, Haris Vikalo, Babak HassibiAbstract:It is well known that maximum-likelihood (ML) decoding in many digital communication schemes reduces to solving an integer least 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 and signal-to-noise ratios (SNR), the Sphere Decoder can be used to find the exact solution with an expected complexity that is roughly cubic in the dimension of the problem. 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 recent work M. Stonjic et al. (2005), we have targeted these two regimes and attempted to find faster algorithms by employing a branch-and-bound technique based on convex relaxations of the original integer least-squares problem. In this paper, using ideas from H/sup /spl infin// estimation theory, we propose new lower bounds that are generally tighter than the ones obtained in M. Stonjic et al. (2005). Simulation results snow the advantages, in terms of computational complexity, of the new H/sup /spl infin//-based branch-and-bound algorithm over the ones based on convex relaxation, as well as the original Sphere Decoder.
-
a branch and bound approach to speed up the Sphere Decoder
International Conference on Acoustics Speech and Signal Processing, 2005Co-Authors: M Stojnic, Haris Vikalo, Babak HassibiAbstract:In many communications applications, maximum-likelihood decoding reduces to solving an integer least-squares problem which is NP hard in the worst-case. However, as has recently been shown, over a wide range of dimensions and SNRs, the Sphere Decoder can be used to find the exact solution with an expected complexity that is roughly cubic in the dimension of the problem. However, the computational complexity becomes prohibitive if the SNR is too low and/or if the dimension of the problem is too large. We target these two regimes and attempt to find faster algorithms by pruning the search tree beyond what is done in the standard Sphere Decoder. The search tree is pruned by computing lower bounds on the possible optimal solution as we proceed down the tree. We observe a trade-off between the computational complexity required to compute the lower bound and the size of the pruned tree: the more effort spent computing a tight lower bound, the more branches that can be eliminated in the tree. Thus, even though it is possible to prune the search tree (and hence the number of points visited) by several orders of magnitude, this may be offset by the computations required to perform the pruning. All of which suggests the need for computationally-efficient tight lower bounds. We present three different lower bounds (based on spherical-relaxation, polytope-relaxation and duality), simulate their performances and discuss their relative merits.
Sin-chong Park - One of the best experts on this subject based on the ideXlab platform.
-
VTC Fall - A Novel Architecture of Sphere Decoder for Low Complexity and High Throughput
2008 IEEE 68th Vehicular Technology Conference, 2008Co-Authors: Jin Lee, Sin-chong ParkAbstract:Since finding the nearest point in a lattice for multi-input multi-output (MIMO) channels is NP-hard, simplified algorithms such as a Sphere Decoder (SD) have been proposed. In this paper, we propose a low area and high throughput Sphere Decoder based on the well-known one-node-per-cycle architecture and present the implementation result. Three key contributions are a new direct Schnorr-Euchener (SE) enumeration scheme for QAM modulation, an efficient storage manipulation and the calculation interleaving to reduce the critical path. Compared with current state-of-the-art Sphere Decoder architecture, the proposed Sphere Decoder can save 48% of hardware complexity and enhance 54% of the maximum operation clock frequency.
-
complexity evaluation for mimo Sphere Decoder with various tree searching algorithms
International Conference on Communication Technology, 2006Co-Authors: Hyoungsoon Kim, Jin Lee, Sin-chong ParkAbstract:Since finding the nearest point in a lattice for multi -input multi-output (MIMO) channels is NP-hard, simplified algorithms such as a Sphere Decoder (SD) have been proposed with various tree-searching strategy. This paper evaluate the complexity of MIMO Sphere Decoder in terms of resource complexity and processing cycle with various tree- searching algorithm for SD. Resource complexity is analyzed in closed form with various parameter such as the number of antennas and modulations, etc. and processing cycles is evaluated by computer simulation, as a result the resource complexity of Fincke and Phost algorithm is the lowest resource complexity among tree-searching algorithms for SD, but to obtain same processing cycles per one MIMO vector, Schnorr Euchner algorithm has the smallest resource complexity among tree-searching algorithms for SD.
-
a pipelined vlsi architecture for a list Sphere Decoder
International Symposium on Circuits and Systems, 2006Co-Authors: Jin Lee, Sin-chong Park, Sung Chung ParkAbstract:Since finding the nearest point in a lattice for multi-input multi-output (MIMO) channels is NP-hard, simplified algorithms such as a Sphere Decoder (SD) have been proposed. With simple modification of SD, a list Sphere Decoder (LSD), soft information can be extracted for channel decoding and iterative detection/decoding. However, generating such information increases the computational complexity for selecting a specific number of candidate lattice points. In this paper an efficient pipelined VLSI architecture for LSD is presented and its complexity is analyzed. The architecture is constructed with three pipeline stages, two stages for metric calculation units (MCU) and one stage for metric enumeration unit (MEU). It also has three storage units and list units for three successive input MIMO vectors. The pipeline can increase the operating clock frequency and keep one-node-per-cycle policy, so that the average throughput can enhance according to the increment of the clock frequency.
-
implementation issues of a list Sphere Decoder
International Conference on Acoustics Speech and Signal Processing, 2006Co-Authors: Jin Lee, Sung Chung Park, Yuping Zhang, Keshab K Parhi, Sin-chong ParkAbstract:Since finding the nearest point in a lattice for multi-input multi-output (MIMO) channels is NP-hard, simplified algorithms such as Sphere Decoder (SD) have been proposed. List Sphere Decoder (LSD), which is a modified version of SD, allows soft information to be extracted for channel decoding and iterative detection/decoding. In this paper, recently proposed efficient methods for reducing the computational complexity of SD and LSD with depth-first tree searching are summarized. Numerous simulations have been carried out and comparison has been made based on the average number of processing cycles. We also present two efficient schemes which can decrease hardware complexity without significant performance degradation, restricted list updating in LSD and restricted node storing at each tree level.
-
Novel techniques of a list Sphere Decoder for high throughput
2006 8th International Conference Advanced Communication Technology, 2006Co-Authors: Jin Lee, Sin-chong ParkAbstract:Since finding the nearest point in a lattice for multi-input multi-output (MIMO) channels is NP-hard, simplified algorithms such as a Sphere Decoder (SD) have been proposed. List Sphere Decoder (LSD), which is a modified version of SD, allows soft information to be extracted for channel decoding and iterative detection/decoding. In this paper, recently proposed efficient methods for reducing the computational complexity of a Sphere Decoder (SD) and a list Sphere Decoder (LSD) with depth-first tree searching are summarized. Numerous simulations have been carried out and comparison has been made based on of the average number of processing cycles.
Yuehua Ding - One of the best experts on this subject based on the ideXlab platform.
-
Widely Linear Sphere Decoder in MIMO Systems by Exploiting the Conjugate Symmetry of Linearly Modulated Signals
IEEE Transactions on Signal Processing, 2016Co-Authors: Yuehua Ding, Suili Feng, Nanxi Li, Yide Wang, Hongbin ChenAbstract:This paper investigates the widely linear processing (WLP) for the detection of circular signals, such as M-ary phaseshift keying (MPSK) signals and M-ary quadrature amplitude modulation (MQAM) signals. First, a unified mathematical model is derived to describe the conjugate symmetry of general MPSK/MQAM signals. In the unified model, a phase-rotation matrix (PRM) is introduced to partition the constellation of multiple-input multiple-output (MIMO) signals into subsets. Signals in a subset share the same PRM. Second, a widely linear receiver is proposed in each subset for MIMO detection. To avoid repetitive WLP in each subset, a widely linear Sphere Decoder (WLSD) is further proposed for MIMO systems. WLSD transforms the traditional Sphere Decoder (SD) searching for a true transmitted vector into a shrunk one by searching for the corresponding phase-rotation vector. Finally, the diversity order of WLSD is proven to be more than NR - NT -1/2 and less than NR, where NT (or NR) denotes the number of transmitting (or receiving) antennas. Additional performance analysis is also conducted to quantify the signal-to-noise ratio improvement. The complexity analysis reveals that the candidate phase-rotation vectors of WLSD are no more than (1/2)NT of the SD candidates. Simulation results show that the proposed WLSD can achieve quasi-optimal bit error rate performance, while the computational complexity is reduced by more than a half compared with the Schnorr-Euchner Sphere Decoder.
-
Widely Linear Sphere Decoder in MIMO Systems by Exploiting the Conjugate Symmetry of Linearly Modulated Signals
IEEE Transactions on Signal Processing, 2016Co-Authors: Yuehua Ding, Suili Feng, Yide Wang, Hongbing ChenAbstract:This paper investigates the widely linear processing(WLP) for the detection of circular signals such as M-aryphase shift keying (MPSK) signals, M-ary quadrature amplitudemodulation (MQAM) signals. Firstly, a unified mathematicalmodel is derived to describe the conjugate symmetry of generalMPSK/MQAM signals. In the unified model, a phase-rotation matrix(PRM) is introduced to partition the constellation of multipleinputmultiple-output (MIMO) signals into subsets. Signals in asubset share the same PRM. Secondly, a widely linear receiver isproposed in each subset for MIMO detection. To avoid repetitiveWLP in each subset, a widely linear Sphere Decoder (WLSD)is further proposed for MIMO systems. WLSD transforms thetraditional SD searching for a true transmitted vector into ashrunk one by searching for the corresponding phase-rotationvector.
-
simplified robust fixed complexity Sphere Decoder
European Signal Processing Conference, 2011Co-Authors: Yuehua Ding, Yide Wang, Jeanfrancois DiourisAbstract:A simplified robust fixed-complexity Sphere Decoder (SRFSD) is proposed in this paper. SRFSD reduces the complexity of robust fixed complexity Sphere Decoder (RFSD) by choosing a detection order minimizing the upper bound of the power of the interference in single expansion (SE) stage. Theoretical proof is given to support the feasibility of SRFSD. Simulation results show that SRFSD retains the robustness of RFSD, and sharply reduces the complexity of RFSD with little sacrifice in bit error rate (BER) performance.
-
robust fixed complexity Sphere Decoder
Global Communications Conference, 2010Co-Authors: Yuehua Ding, Yide Wang, Jeanfrancois DiourisAbstract:In this paper, RFSD (Robust Fixed-complexity Sphere Decoder) based on a new preprocessing algorithm is proposed for MIMO (Multiple Input Multiple Output) detection. Unlike the original FSD (Fixed-complexity Sphere Decoder) ordering which determines the FE (Full expansion) stage by choosing the signal component with greatest post-processing noise amplification on itself, the proposed RFSD determines the FE stage by selecting the signal component with the smallest postprocessing impact on the undetected signal component in following SE (Single Expansion) stage. Besides better performance than the original FSD ordering, RFSD is robust to the configuration of MIMO antennas (both NT NR), which is another advantage over original FSD ordering.
-
GLOBECOM - Robust Fixed Complexity Sphere Decoder
2010 IEEE Global Telecommunications Conference GLOBECOM 2010, 2010Co-Authors: Yuehua Ding, Yide Wang, Jeanfrancois DiourisAbstract:In this paper, RFSD (Robust Fixed-complexity Sphere Decoder) based on a new preprocessing algorithm is proposed for MIMO (Multiple Input Multiple Output) detection. Unlike the original FSD (Fixed-complexity Sphere Decoder) ordering which determines the FE (Full expansion) stage by choosing the signal component with greatest post-processing noise amplification on itself, the proposed RFSD determines the FE stage by selecting the signal component with the smallest postprocessing impact on the undetected signal component in following SE (Single Expansion) stage. Besides better performance than the original FSD ordering, RFSD is robust to the configuration of MIMO antennas (both NT NR), which is another advantage over original FSD ordering.
