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.展开更多
Compared to the successive cancellation(SC)-based decoding algorithms,the sphere decoding(SD)algorithm can achieve better performance with reduced computational complexity,especially for short polar codes.In this pape...Compared to the successive cancellation(SC)-based decoding algorithms,the sphere decoding(SD)algorithm can achieve better performance with reduced computational complexity,especially for short polar codes.In this paper,we propose a new method to construct the binary polar codes with the modified multiplicative repetition(MR)-based matrix.Different from the original construction,we first design a 2×2 q-ary kernel to guarantee the single-level polarization effect.Then,by replacing the new-designed binary companion matrix,a novel strategy is further developed to enhance the polarization in the bit level,resulting in a better distance property.Finally,the SD-based Monte-Carlo(SDMC)method is used to construct MR-based binary polar codes,while the resulting codes without the butterfly pattern are decoded by the SD algorithm.Simulation results show that the proposed method with the SD algorithm can achieve a maximum performance gain of 0.27 dB compared to the original method with slightly lower complexity.展开更多
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.展开更多
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）.展开更多
Polar codes are considered as one of the most competitive channel coding schemes for the future wireless communication system.To improve the performance of polar codes with short code-length for control channels,a sph...Polar codes are considered as one of the most competitive channel coding schemes for the future wireless communication system.To improve the performance of polar codes with short code-length for control channels,a sphere decoding algorithm based on received value flipping is proposed in this paper.When a codeword fails the cyclic redundancy check,the algorithm flips the received value with low reliability and forms a new received sequence.Then,this new sequence is sent to the decoder for another decoding attempt.In addition,we also compare the performance of different flipping sets and evaluate the influence of the associated flipping set sizes.Simulation results show that,the proposed algorithm can achieve performance improvement over additive white Gaussian noise channel with acceptable complexity.For the(64,16)polar code,the proposed algorithm can achieve about 0.23 dB 10-3performance gain at frame error rate=,compared to the conventional sphere decoding algorithm.Finally,we also verify the applicability of the proposed algorithm over Rayleigh fading channel and observe similar results.展开更多
文摘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(Nos.62261003,62361003,and 61961004)the KR&DP of Guangxi(No.GuiKeAB22080048).
文摘Compared to the successive cancellation(SC)-based decoding algorithms,the sphere decoding(SD)algorithm can achieve better performance with reduced computational complexity,especially for short polar codes.In this paper,we propose a new method to construct the binary polar codes with the modified multiplicative repetition(MR)-based matrix.Different from the original construction,we first design a 2×2 q-ary kernel to guarantee the single-level polarization effect.Then,by replacing the new-designed binary companion matrix,a novel strategy is further developed to enhance the polarization in the bit level,resulting in a better distance property.Finally,the SD-based Monte-Carlo(SDMC)method is used to construct MR-based binary polar codes,while the resulting codes without the butterfly pattern are decoded by the SD algorithm.Simulation results show that the proposed method with the SD algorithm can achieve a maximum performance gain of 0.27 dB compared to the original method with slightly lower complexity.
文摘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.
基金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）.
基金supported by the National Natural Science Foundation of China(Nos.61961004,62261003,and 62361003)the Key Research and Development Program of Guangxi(No.GuiKeAB22080048)the Counterpart Aid Project for Discipline Construction from Guangxi University(No.2023N04).
文摘Polar codes are considered as one of the most competitive channel coding schemes for the future wireless communication system.To improve the performance of polar codes with short code-length for control channels,a sphere decoding algorithm based on received value flipping is proposed in this paper.When a codeword fails the cyclic redundancy check,the algorithm flips the received value with low reliability and forms a new received sequence.Then,this new sequence is sent to the decoder for another decoding attempt.In addition,we also compare the performance of different flipping sets and evaluate the influence of the associated flipping set sizes.Simulation results show that,the proposed algorithm can achieve performance improvement over additive white Gaussian noise channel with acceptable complexity.For the(64,16)polar code,the proposed algorithm can achieve about 0.23 dB 10-3performance gain at frame error rate=,compared to the conventional sphere decoding algorithm.Finally,we also verify the applicability of the proposed algorithm over Rayleigh fading channel and observe similar results.
