구 복호 복잡도 감소의 관한 연구
A study on the Complexity Reduction of Sphere Decoding
- 발행기관 아주대학교
- 지도교수 오성근
- 발행년도 2006
- 학위수여년월 2006. 2
- 학위명 석사
- 학과 및 전공 일반대학원 전자공학과
- 본문언어 영어
초록/요약
In this thesis, we deal with sphere decoding (SD) for maximum likelihood detection (MLD). We consider two different approaches for selecting the ini-tial radius such as deterministic and statistical approaches. But, we focus on the deterministic approach to achieve the exact ML performance without de-tection failure. In the deterministic approach, the initial radius is selected as the Euclidean distance between the received signal vector and the lattice vec-tor corresponding to a suboptimum initial estimate. We first analyze the com-putational complexity for SD according to initial radius selection schemes. Then, we propose an efficient initial radius reduction procedure that reduces further the initial radius. It can be applied to both the Fincke-Pohst (FP) strat-egy and the Schnorr-Euchner (SE) strategy. In the FP strategy, the initial radius for SD is selected as the Euclidean dis-tance between the received signal vector and the lattice vector corresponding to a suboptimum initial estimate. Here, the suboptimum initial estimate can be obtained by using the zero-forcing (ZF) detection, minimum mean-squared error (MMSE) detection, ZF decision feedback equalization (ZF-DFE) and MMSE-DFE. To reduce further the initial radius, we select a new lattice vector closer to the received signal vector than the initial lattice vector. We also pre-sent a simple computational procedure for initial radius reduction. In the SE strategy, the radius after ZF-DFE estimation can be reduced fur-ther if we select a new lattice vector closer to the received signal vector than the lattice vector corresponding to the ZF-DFE estimate does. In our case, we obtain such a better lattice vector by performing a sequence of alternating one-dimensional searches, starting from the ZF-DFE estimate. We then develop a smart radius reduction control (SRRC) scheme to adopt adaptively SRRC process according to the estimated signal-to-noise-power ratio (SNR) after ZF-DFE estimation. As a baseline algorithm for SD, we consider the modified SE-SD algorithm [1] (hereafter, called as the MSE-SD algorithm). For the complexity analysis, we evaluate computations for both pre-processing and tree-search processing. Especially, we analyze the effect of de-tection ordering on the complexity for MSE-SD. Column-norm ordering and optimal ordering of the channel matrix are considered here. From our analyses, using the FP strategy, the computations for pre-processing have a greater influence on the overall complexity as the SNR in-creases and also the reduction in the overall complexity due to additional re-duction of the initial radius gets more significant as the SNR decreases. Espe-cially, the ZF-DFE scheme in a combination with the proposed radius reduc-tion scheme has the fewest computations over practical SNR range for com-munications, and its computations are less than those of the vertical Bell-labs layered space-time (V-BLAST) detection scheme with optimal ordering, even at low SNR values achieving an uncoded bit error rate (BER) of 10-1. In the SE strategy, we see that SRRC can reduce greatly the complexity for SD and the degree of complexity reduction gets significant as the SNR decreases, irre-spective of detection ordering schemes used. In addition, the SRRC scheme can reduce effectively the additional complexity in a high SNR values. Finally, we conclude that the radius reduction schemes reduce the overall complexity of SD both the FP and SE strategies.
more목차
Table of Contents
List of Tables iii
List of Figures iv
Acronyms vi
Abstract vii
Abstract in Korean x
Chapter 1 Introduction 1
Chapter 2 Existing Sphere Decoding Algorithms 7
2.1 MIMO System 7
2.2 Problem Formulation 9
2.3 MVB-SD Algorithm Based on the FP strategy 12
2.4 MSE-SD Algorithm Based on the SE strategy 15
Chapter 3 Initial Radius Selection Schemes 17
3.1 Statistical Approach 17
3.2 Deterministic Approach 18
3.2.1 ZF Detection 18
3.2.2 MMSE Detection 18
3.2.3 ZF-DFE 19
3.2.4 MMSE-DFE 20
Chapter 4 Radius Reduction Schemes 21
4.1 Radius Reduction Control Procedure 21
4.2 Smart Radius Reduction Control Procedure 24
Chapter 5 Computational Complexities 26
5.1 Column-Ordering of Channel Matrix 26
5.1.1 Column-Norm Ordering 27
5.1.2 Optimal Ordering 27
5.2 The Choice of the Initial Radius 28
5.3 Tree-search Processing 35
Chapter 6 Simulation Results 36
6.1 FP Strategy 36
6.2 SE Strategy 49
Chapter 7 Conclusions 57
References 59
Acknowledgements in Korean 63
