We propose a pipeline structure for Schnorr-Euchner sphere decoding algorithm in this article. It divides the search tree of the original algorithm into blocks and executes the search from block to block. When one blo...We propose a pipeline structure for Schnorr-Euchner sphere decoding algorithm in this article. It divides the search tree of the original algorithm into blocks and executes the search from block to block. When one block search of a signal is over, the part in the pipeline structure that processes this block search can load another signal and search. Several signals can be processed at the same time in one pipeline. Blocks are arranged to lower the whole complexity in the way that the previously search blocks are the blocks those have more probability to generate the final solution. Simulation experiment results show the average process delay can drop to the range from 48.77% to 60.18% in a 4-by-4 antenna system with 16QAM modulation, or from 30.31% to 61.59% in a 4-by-4 antenna system with 64QAM modulation.展开更多
Various efficient generalized sphere decoding (GSD) algorithms have been proposed to approach optimal ML performance for underdetermined linear systems, by transforming the original problem into the full-column-rank o...Various efficient generalized sphere decoding (GSD) algorithms have been proposed to approach optimal ML performance for underdetermined linear systems, by transforming the original problem into the full-column-rank one so that standard SD can be fully applied. However, their design parameters are heuristically set based on observation or the possibility of an ill-conditioned transformed matrix can affect their searching efficiency. This paper presents a better transformation to alleviate the ill-conditioned structure and provides a systematic approach to select design parameters for various GSD algorithms in order to high efficiency. Simulation results on the searching performance confirm that the proposed techniques can provide significant improvement.展开更多
This paper focuses on reducing the complexity of K-best sphere decoding （SD） algorithm for the detection of uncoded multi-ple input multiple output （MIMO） systems. The proposed algorithm utilizes the threshold-pru...This paper focuses on reducing the complexity of K-best sphere decoding （SD） algorithm for the detection of uncoded multi-ple input multiple output （MIMO） systems. The proposed algorithm utilizes the threshold-pruning method to cut nodes with partial Euclidean distances （PEDs） larger than the threshold. Both the known noise value and the unknown noise value are considered to generate the threshold, which is the sum of the two values. The known noise value is the smal est PED of signals in the detected layers. The unknown noise value is generated by the noise power, the quality of service （QoS） and the signal-to-noise ratio （SNR） bound. Simulation results show that by considering both two noise values, the proposed algorithm makes an efficient reduction while the performance drops little.展开更多
Multiple Input Multiple Output (MIMO) technology is of great significance in high data rate wireless communication. The K-Best Sphere Decoding (K-Best SD) algorithm was proposed as a powerful method for MIMO detection...Multiple Input Multiple Output (MIMO) technology is of great significance in high data rate wireless communication. The K-Best Sphere Decoding (K-Best SD) algorithm was proposed as a powerful method for MIMO detection that can approach near-optimal performance. However, some extra computational complexity is contained in K-Best SD. In this paper, we propose an improved K-Best SD to reduce the complexity of conventional K-Best SD by assigning K for each level dynamically following some rules. Simulation proves that the performance degradation of the improved K-Best SD is very little and the complexity is significantly reduced.展开更多
An improved list sphere decoder （ILSD） is proposed based on the conventional list sphere decoder （LSD） and the reduced- complexity maximum likelihood sphere-decoding algorithm. Unlike the conventional LSD with fix...An improved list sphere decoder （ILSD） is proposed based on the conventional list sphere decoder （LSD） and the reduced- complexity maximum likelihood sphere-decoding algorithm. Unlike the conventional LSD with fixed initial radius, the ILSD adopts an adaptive radius to accelerate the list cdnstruction. Characterized by low-complexity and radius-insensitivity, the proposed algorithm makes iterative joint detection and decoding more realizable in multiple-antenna systems. Simulation results show that computational savings of ILSD over LSD are more apparent with more transmit antennas or larger constellations, and with no performance degradation. Because the complexity of the ILSD algorithm almost keeps invariant with the increasing of initial radius, the BER performance can be improved by selecting a sufficiently large radius.展开更多
Recently, a new soft-in soft-out detection algorithm based on the Markov Chain Monte Carlo (MCMC) simulation technique for Multiple-Input Multiple-Output (MIMO) systems is proposed, which is shown to perform significa...Recently, a new soft-in soft-out detection algorithm based on the Markov Chain Monte Carlo (MCMC) simulation technique for Multiple-Input Multiple-Output (MIMO) systems is proposed, which is shown to perform significantly better than their sphere decoding counterparts with relatively low complexity. However, the MCMC simulator is likely to get trapped in a fixed state when the channel SNR is high, thus lots of repetitive samples are observed and the accuracy of A Posteriori Probability (APP) estimation deteriorates. To solve this problem, an improved version of MCMC simulator, named forced-dispersed MCMC algorithm is proposed. Based on the a posteriori variance of each bit, the Gibbs sampler is monitored. Once the trapped state is detected, the sample is dispersed intentionally according to the a posteriori variance. Extensive simulation shows that, compared with the existing solution, the proposed algorithm enables the markov chain to travel more states, which ensures a near-optimal performance.展开更多
The demand for high-data-rate underwater acoustic communications(UACs)in marine development is increasing;however,severe multipaths make demodulation a challenge.The decision feedback equalizer(DFE)is one of the most ...The demand for high-data-rate underwater acoustic communications(UACs)in marine development is increasing;however,severe multipaths make demodulation a challenge.The decision feedback equalizer(DFE)is one of the most popular equalizers in UAC;however,it is not the optimal algorithm.Although maximum likelihood sequence estimation(MLSE)is the optimal algorithm,its complexity increases exponentially with the number of channel taps,making it challenging to apply to UAC.Therefore,this paper proposes a complexity-reduced MLSE to improve the bit error rate(BER)performance in multipath channels.In the proposed algorithm,the original channel is first shortened using a channel-shortening method,and several dominant channel taps are selected for MLSE.Subsequently,sphere decoding(SD)is performed in the following MLSE.Iterations are applied to eliminate inter-symbol interference caused by weak channel taps.The simulation and sea experiment demonstrate the superiority of the proposed algorithm.The simulation results show that channel shortening combined with SD can drastically reduce computational complexity,and iterative SD performs better than DFE based on recursive least squares(RLS-DFE),DFE based on improved proportionate normalized least mean squares(IPNLMS-DFE),and channel estimation-based DFE(CE-DFE).Moreover,the sea experimental results at Zhairuoshan Island in Zhoushan show that the proposed receiver scheme has improved BER performance over RLSDFE,IPNLMS-DFE,and CE-DFE.Compared with the RLS-DFE,the BER,after five iterations,is reduced from 0.0076 to 0.0037 in the 8–12 k Hz band and from 0.1516 to 0.1145 in the 13–17 k Hz band at a distance of 2000 m.Thus,the proposed algorithm makes it possible to apply MLSE in UAC in practical scenarios.展开更多
Multiple-Input Multiple-Output (MIMO) techniques are promising in wireless communication systems for its high spectral efficiency. Sphere Detector (SD) is favoured in MIMO detection to achieve Maximum-Likelihood (ML) ...Multiple-Input Multiple-Output (MIMO) techniques are promising in wireless communication systems for its high spectral efficiency. Sphere Detector (SD) is favoured in MIMO detection to achieve Maximum-Likelihood (ML) performance. In this paper, we proposed a new SD method for MIMO-Orthogonal Frequency Division Multiplexing (OFDM) systems based on IEEE802.11n, which uses Singular Value Decomposition (SVD) in complex domain to reduce the computation complexity. Furthermore, a new Schnorr-Euchner (SE) enumeration algorithm is also discussed in detail. The computer simulation result shows that the computational complexity and the number of visited nodes can be reduced significantly compared with conventional SD detectors with the same Bit Error Rate (BER) performance.展开更多
球形译码(Sphere Decoding,SD)能够有效地实现极化码最大似然译码的误码性能,文章提出基于比特翻转的多重球形译码树搜索(Multiple Sphere Decoding Tree Searches Based on Bit-Flipping,BF-MSDTS)算法进一步提升短极化码的性能,该算...球形译码(Sphere Decoding,SD)能够有效地实现极化码最大似然译码的误码性能,文章提出基于比特翻转的多重球形译码树搜索(Multiple Sphere Decoding Tree Searches Based on Bit-Flipping,BF-MSDTS)算法进一步提升短极化码的性能,该算法通过扩大半径搜索和翻转不可靠比特提升误码性能,同时利用搜索终止准则和固定可靠比特降低复杂度,有效地解决了多重球形译码树搜索(Multiple Sphere Decoding Tree Searches,MSDTS)算法低信噪比下误码性能不如循环冗余校验(Cyclic Redundancy Check,CRC)辅助的串行消除列表(CRC Aided Successive Cancellation List,CA-SCL)算法的问题.仿真结果表明,在低信噪比时,当误码率为10-4时,与CA-SCL算法比较,提高了0.41dB,与MSDTS算法比较,提高了1.17dB.提出的BF-MSDTS算法的误码性能在较差的信道环境下优于现有的MSDTS算法以及CA-SCL算法.展开更多
In this article a bridge between the expected complexity and performance of sphere decoding （SD） is built. The expected complexity of SD for infinite lattices is then investigated, which naturally is the upper-bound...In this article a bridge between the expected complexity and performance of sphere decoding （SD） is built. The expected complexity of SD for infinite lattices is then investigated, which naturally is the upper-bound of those for all the finite lattices if given by the same channel matrix and signal noise ratio （SNR）. Such expected complexity is an important characterization of SD in multi-antenna systems, because no matter what modulation scheme is used in practice （generally it has finite constellation size） this upper-bound holds. Above bridge also leads to a new method of determining the radius for SD. The numerical results show both the real value and upper-bound of average searched number of candidates in SD for 16-QAM modulated system using the proposed sphere radius determining method. Most important of all new understandings of expected complexity of SD are given based on above mentioned theoretic analysis and numerical results.展开更多
Recently, a multiple symbol differential （MSD） sphere decoding （SD） algorithm for unitary spacetime modulation over quasi-static channel has been proved to achieve the performance of maximumlikelihood （ML） detec...Recently, a multiple symbol differential （MSD） sphere decoding （SD） algorithm for unitary spacetime modulation over quasi-static channel has been proved to achieve the performance of maximumlikelihood （ML） detection with relatively low complexity. However, an error floor occurs if the algorithm is applied over rapid-fading channels. Based on the assumption of continuous fading, a multiple symbol differential automatic sphere decoding （MSDASD） algorithm is developed by incorporating a recursive form of an ML metric into automatic SD （ASD） algorithm. Furthermore, two algorithms, termed as MSD approximate ASD （MSDAASD） and MSD pruning ASD （MSDPASD）, are proposed to reduce computational complexity and the number of comparisons, respectively. Compared with the existing typical algorithms, i.e., multiple symbol differential feedback detection （MS-DFD） and noncoherent sequence detection （NSD）, the performance of the proposed algorithms is much superior to that of MS-DFD and a little inferior to that of NSD, while the complexity is lower than that of MS-DFD in most cases and significantly lower than that of NSD.展开更多
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 prop...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.展开更多
Overlapped time division multiplexing （OvTDM） is a new type of transmission scheme with high spectrum efficiency and low threshold signal-to-noise ratio （SNR）. In this article, the structure of OvTDM is introduced...Overlapped time division multiplexing （OvTDM） is a new type of transmission scheme with high spectrum efficiency and low threshold signal-to-noise ratio （SNR）. In this article, the structure of OvTDM is introduced and the sphere-decoding algorithm of complex domain is proposed for OvTDM. Simulations demonstrate that the proposed algorithm can achieve maximum likelihood （ML） decoding with lower complexity as compared to traditional maximum likelihood sequence demodulation （MLSD） or viterbi algorithm （VA）.展开更多
文摘We propose a pipeline structure for Schnorr-Euchner sphere decoding algorithm in this article. It divides the search tree of the original algorithm into blocks and executes the search from block to block. When one block search of a signal is over, the part in the pipeline structure that processes this block search can load another signal and search. Several signals can be processed at the same time in one pipeline. Blocks are arranged to lower the whole complexity in the way that the previously search blocks are the blocks those have more probability to generate the final solution. Simulation experiment results show the average process delay can drop to the range from 48.77% to 60.18% in a 4-by-4 antenna system with 16QAM modulation, or from 30.31% to 61.59% in a 4-by-4 antenna system with 64QAM modulation.
文摘Various efficient generalized sphere decoding (GSD) algorithms have been proposed to approach optimal ML performance for underdetermined linear systems, by transforming the original problem into the full-column-rank one so that standard SD can be fully applied. However, their design parameters are heuristically set based on observation or the possibility of an ill-conditioned transformed matrix can affect their searching efficiency. This paper presents a better transformation to alleviate the ill-conditioned structure and provides a systematic approach to select design parameters for various GSD algorithms in order to high efficiency. Simulation results on the searching performance confirm that the proposed techniques can provide significant improvement.
基金supported by the National Natural Science Foundation of China(61071083)
文摘This paper focuses on reducing the complexity of K-best sphere decoding （SD） algorithm for the detection of uncoded multi-ple input multiple output （MIMO） systems. The proposed algorithm utilizes the threshold-pruning method to cut nodes with partial Euclidean distances （PEDs） larger than the threshold. Both the known noise value and the unknown noise value are considered to generate the threshold, which is the sum of the two values. The known noise value is the smal est PED of signals in the detected layers. The unknown noise value is generated by the noise power, the quality of service （QoS） and the signal-to-noise ratio （SNR） bound. Simulation results show that by considering both two noise values, the proposed algorithm makes an efficient reduction while the performance drops little.
文摘Multiple Input Multiple Output (MIMO) technology is of great significance in high data rate wireless communication. The K-Best Sphere Decoding (K-Best SD) algorithm was proposed as a powerful method for MIMO detection that can approach near-optimal performance. However, some extra computational complexity is contained in K-Best SD. In this paper, we propose an improved K-Best SD to reduce the complexity of conventional K-Best SD by assigning K for each level dynamically following some rules. Simulation proves that the performance degradation of the improved K-Best SD is very little and the complexity is significantly reduced.
基金The National Natural Science Founda-tion of China ( No 60496316)the National Hi-Tech Re-search and Development Program (863) of China (No2006-AA01Z270)
文摘An improved list sphere decoder （ILSD） is proposed based on the conventional list sphere decoder （LSD） and the reduced- complexity maximum likelihood sphere-decoding algorithm. Unlike the conventional LSD with fixed initial radius, the ILSD adopts an adaptive radius to accelerate the list cdnstruction. Characterized by low-complexity and radius-insensitivity, the proposed algorithm makes iterative joint detection and decoding more realizable in multiple-antenna systems. Simulation results show that computational savings of ILSD over LSD are more apparent with more transmit antennas or larger constellations, and with no performance degradation. Because the complexity of the ILSD algorithm almost keeps invariant with the increasing of initial radius, the BER performance can be improved by selecting a sufficiently large radius.
文摘Recently, a new soft-in soft-out detection algorithm based on the Markov Chain Monte Carlo (MCMC) simulation technique for Multiple-Input Multiple-Output (MIMO) systems is proposed, which is shown to perform significantly better than their sphere decoding counterparts with relatively low complexity. However, the MCMC simulator is likely to get trapped in a fixed state when the channel SNR is high, thus lots of repetitive samples are observed and the accuracy of A Posteriori Probability (APP) estimation deteriorates. To solve this problem, an improved version of MCMC simulator, named forced-dispersed MCMC algorithm is proposed. Based on the a posteriori variance of each bit, the Gibbs sampler is monitored. Once the trapped state is detected, the sample is dispersed intentionally according to the a posteriori variance. Extensive simulation shows that, compared with the existing solution, the proposed algorithm enables the markov chain to travel more states, which ensures a near-optimal performance.
基金Supported by the National Natural Science Foundation of China under Grant Nos. 62101489, 62171405 and 62225114.
文摘The demand for high-data-rate underwater acoustic communications(UACs)in marine development is increasing;however,severe multipaths make demodulation a challenge.The decision feedback equalizer(DFE)is one of the most popular equalizers in UAC;however,it is not the optimal algorithm.Although maximum likelihood sequence estimation(MLSE)is the optimal algorithm,its complexity increases exponentially with the number of channel taps,making it challenging to apply to UAC.Therefore,this paper proposes a complexity-reduced MLSE to improve the bit error rate(BER)performance in multipath channels.In the proposed algorithm,the original channel is first shortened using a channel-shortening method,and several dominant channel taps are selected for MLSE.Subsequently,sphere decoding(SD)is performed in the following MLSE.Iterations are applied to eliminate inter-symbol interference caused by weak channel taps.The simulation and sea experiment demonstrate the superiority of the proposed algorithm.The simulation results show that channel shortening combined with SD can drastically reduce computational complexity,and iterative SD performs better than DFE based on recursive least squares(RLS-DFE),DFE based on improved proportionate normalized least mean squares(IPNLMS-DFE),and channel estimation-based DFE(CE-DFE).Moreover,the sea experimental results at Zhairuoshan Island in Zhoushan show that the proposed receiver scheme has improved BER performance over RLSDFE,IPNLMS-DFE,and CE-DFE.Compared with the RLS-DFE,the BER,after five iterations,is reduced from 0.0076 to 0.0037 in the 8–12 k Hz band and from 0.1516 to 0.1145 in the 13–17 k Hz band at a distance of 2000 m.Thus,the proposed algorithm makes it possible to apply MLSE in UAC in practical scenarios.
文摘Multiple-Input Multiple-Output (MIMO) techniques are promising in wireless communication systems for its high spectral efficiency. Sphere Detector (SD) is favoured in MIMO detection to achieve Maximum-Likelihood (ML) performance. In this paper, we proposed a new SD method for MIMO-Orthogonal Frequency Division Multiplexing (OFDM) systems based on IEEE802.11n, which uses Singular Value Decomposition (SVD) in complex domain to reduce the computation complexity. Furthermore, a new Schnorr-Euchner (SE) enumeration algorithm is also discussed in detail. The computer simulation result shows that the computational complexity and the number of visited nodes can be reduced significantly compared with conventional SD detectors with the same Bit Error Rate (BER) performance.
文摘球形译码(Sphere Decoding,SD)能够有效地实现极化码最大似然译码的误码性能,文章提出基于比特翻转的多重球形译码树搜索(Multiple Sphere Decoding Tree Searches Based on Bit-Flipping,BF-MSDTS)算法进一步提升短极化码的性能,该算法通过扩大半径搜索和翻转不可靠比特提升误码性能,同时利用搜索终止准则和固定可靠比特降低复杂度,有效地解决了多重球形译码树搜索(Multiple Sphere Decoding Tree Searches,MSDTS)算法低信噪比下误码性能不如循环冗余校验(Cyclic Redundancy Check,CRC)辅助的串行消除列表(CRC Aided Successive Cancellation List,CA-SCL)算法的问题.仿真结果表明,在低信噪比时,当误码率为10-4时,与CA-SCL算法比较,提高了0.41dB,与MSDTS算法比较,提高了1.17dB.提出的BF-MSDTS算法的误码性能在较差的信道环境下优于现有的MSDTS算法以及CA-SCL算法.
基金supported by the National Natural Science Foundation of China (60572120, 60602058)the Hi-Tech Research and Development Program of China (2006AA01Z257)the National Basic Research Program of China (2007CB310602)
文摘In this article a bridge between the expected complexity and performance of sphere decoding （SD） is built. The expected complexity of SD for infinite lattices is then investigated, which naturally is the upper-bound of those for all the finite lattices if given by the same channel matrix and signal noise ratio （SNR）. Such expected complexity is an important characterization of SD in multi-antenna systems, because no matter what modulation scheme is used in practice （generally it has finite constellation size） this upper-bound holds. Above bridge also leads to a new method of determining the radius for SD. The numerical results show both the real value and upper-bound of average searched number of candidates in SD for 16-QAM modulated system using the proposed sphere radius determining method. Most important of all new understandings of expected complexity of SD are given based on above mentioned theoretic analysis and numerical results.
基金Supported by the National Basic Research Program of China (973 Program) (Grant No. 2009CB320403)the National Defense Pre-researchProject of the 11th Five-Year-Plan of China (Grant No. 1060741001020102)
文摘Recently, a multiple symbol differential （MSD） sphere decoding （SD） algorithm for unitary spacetime modulation over quasi-static channel has been proved to achieve the performance of maximumlikelihood （ML） detection with relatively low complexity. However, an error floor occurs if the algorithm is applied over rapid-fading channels. Based on the assumption of continuous fading, a multiple symbol differential automatic sphere decoding （MSDASD） algorithm is developed by incorporating a recursive form of an ML metric into automatic SD （ASD） algorithm. Furthermore, two algorithms, termed as MSD approximate ASD （MSDAASD） and MSD pruning ASD （MSDPASD）, are proposed to reduce computational complexity and the number of comparisons, respectively. Compared with the existing typical algorithms, i.e., multiple symbol differential feedback detection （MS-DFD） and noncoherent sequence detection （NSD）, the performance of the proposed algorithms is much superior to that of MS-DFD and a little inferior to that of NSD, while the complexity is lower than that of MS-DFD in most cases and significantly lower than that of NSD.
基金supported by the Beijing University of Posts and Telecommunications and Qualcomm Joint Research Program
文摘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.
基金the National Natural Science Foundation of China (90604035)
文摘Overlapped time division multiplexing （OvTDM） is a new type of transmission scheme with high spectrum efficiency and low threshold signal-to-noise ratio （SNR）. In this article, the structure of OvTDM is introduced and the sphere-decoding algorithm of complex domain is proposed for OvTDM. Simulations demonstrate that the proposed algorithm can achieve maximum likelihood （ML） decoding with lower complexity as compared to traditional maximum likelihood sequence demodulation （MLSD） or viterbi algorithm （VA）.
