In this thesis, efficient lattice reduction (LR) algorithms are developed using matrix structures. As a well-known LR algorithm, LLL algorithm developed by Lenstra, Lenstra, and $Lov\acute{a}sz$ is considered. First, by understanding the LLL algorithm, a class of matrices for which the LLL algorithm requires much less computational complexities is identified. Furthermore, by reformulating the conventional minimum mean-square-error decision feedback equalizer (MMSE-DFE) algorithm using matrix operations, it is shown that the matrix appearing in MMSE-DFE is a special case of our identified class and, accordingly, a new MMSE-DFE adopting the LLL algorithm for a multi-path channel is proposed. Second, by decoupling a given matrix into multiple submatrices having smaller dimension through linear preprocessing based on the correlations among the columns of the given matrix, the computational complexity of LLL algorithm is reduced. As its application, LR aided successive interference cancellation (SIC) combined with linear preprocessing is developed for clustered mobile stations (MSs). LR aided SIC has been extensively studied due to its near-maximum-likelihood (ML) performance. However, the LLL algorithm and the computation of nulling vectors in SIC inherently incurs considerable computational complexity overhead. To reduce their computational complexities, the entire system is decoupled into multiple lower dimensional subsystems using linear preprocessing based on the spatial correlation among MSs. The LR aided SIC is then utilized parallel in each subsystem. Furthermore, to maximize the system performance, MS grouping algorithms are also proposed. Here, the computational complexity and diversity gain of the proposed LR aided SIC with preprocessing are analyzed. Third, a modified lattice reduction algorithm robust to perturbation errors is proposed. The parameters used in the LLL algorithm are statistically analyzed when the perturbation errors are independent and identically distributed (i.i.d.) Gaussian random variables, which leads us to propose a modified LLL algorithm providing a better-conditioned output matrix than the conventional LLL algorithm. Furthermore, a new LR aided multiple-input multiple-output (MIMO) SIC that considers channel errors is proposed. It is shown that the proposed LR aided SIC works well in conjunction with the modified LLL when channel errors exist. Finally, efficient column-wise/row-wise LLL updating and downdating methods are developed and their complexities are analyzed. When columns or rows are appended/deleted in a given lattice basis matrix $\bf{H}$, the proposed updating and downdating schemes modify the preconditioning matrix that is primarily computed to reduce $\bf{H}$ and provide initial parameters to reduce the updated lattice basis matrix efficiently. Since the modified preconditioning matrix keeps the information of the original reduced lattice bases, redundant computational complexities can be eliminated when reducing the lattice by using the proposed methods. The proposed LLL updating and downdating methods could be important in many applications; especially, in multi-user (MU) MIMO precoding system when new users enter current system or existing users leave the system, the updating and downdating methods can reduce the computational complexity to find the preconditioning matrix for the newly updated channel matrix.
본 논문에서는 잘 알려진 격자축소(lattice reduction, LR) 기법의 하나인 LLL 알고리즘을 연구하고 여러 통신 환경에 따라 달리 나타나는 행렬 구조를 이용하여 각 환경에 적합한 효과적인 격자 축소 기법을 제안한다.
첫번째로, LLL 알고리즘의 원리를 이해하고 LLL 알고리즘을 적용할 때 계산량이 매우 줄어들 수 있는 행렬구조를 규명한다. 추가적으로 기존의 최소 평균 제곱 오차 결정 재입력 등화기(minimum mean square error decision feedback equalizer, MMSE-DFE)를 행렬 연산을 통해 재수식화 하여, 여기에 나타나는 행렬이 우리가 규명한 행렬구조의 특수한 경우임을 보인다. 이를 바탕으로 LLL 알고리즘을 적용한 새로운 최소 평균 제곱 오차 결정 재입력 등화기를 제안한다. 제안한 격자 축소 방식을 통해 최소 평균 제곱 오차 결정 재입력 등화기의 성능을 개선 시킬 수 있다.
두번째로, 주어진 행렬의 열간의 상관도에 기반한 선형 전처리(linear preprocessing) 기법을 통해 주어진 행렬을 여러 개의 작은 행렬들로 분리하여 LLL 알고리즘의 계산 복잡도를 줄인다. 이를 응용하여, 이동국들(mobile stations, MSs)이 군집화되어 있을 때, 선형 전처리기와 결합한 격자 축소 기반의 순차 간섭 제거기(LR aided successive interference cancellation, LR aided SIC)를 개발한다. 격자 축소 기반의 순차 간섭 제거기는 최우도(maximum-likelihood, ML) 검파 성능과 비슷한 성능을 보이기 때문에 많은 연구가 진행되었지만, 격자축소 알고리즘과 간섭제거기의 무효화 벡터 (nulling vector)를 계산하는 부분이 많은 계산 복잡도를 필요로 하게 된다. 이 계산량을 줄이기 위해, 이동국들 사이의 공간 상관도(spatial correlation)에 기반한 선형전처리기를 통해 전체 시스템을 여러 개의 부시스템으로 분할한 뒤, 격자 축소 기반의 순차 간섭 제거기를 각각의 부시스템에 적용할 수 있다. 추가적으로 시스템 성능을 최대화 하기 위해 이동국 집합화(MS grouping) 알고리즘을 제안한다. 계산량 및 다양화 차수(diversity order) 분석을 통해 선형 전처리기와 결합된 격자 축소 기반의 순차 간섭 제거기가 최우도 검파기와 비슷한 성능을 가지면서 매우 적은 계산 복잡도를 가지는 것을 확인할 수 있다.
세번째로, 혼란 오차(perturbation error)가 독립적이고 동일한 (independent and identically distributed, i.i.d.) 가우시안 분포를 따를 때, LLL 알고리즘에 쓰이는 변수들을 통계적으로 분석한다. 이를 바탕으로 혼란 오차에 강인한 격자축소 알고리즘을 제안한다. 추가적으로, 채널 오차가 존재할 때 격자 축소 기반의 다중입력 다중출력 (multiple-input multiple-output, MIMO) 순차 간섭 제거기를 개발한다. 제안한 격자 축소 기반의 다중입력 다중출력 순차 간섭 제거기는 수정된 LLL 알고리즘과 결합하여 채널오차가 존재할 때 기존 격자 축소 기반의 다중입력 다중출력 순차 간섭 제거기보다 좋은 성능을 가지는 것을 확인할 수 있다.
끝으로, 효율적인 LLL 갱신 (updating/downdating) 기법을 개발하고 복잡도를 분석한다. 즉, 주어진 격자 기저 행렬(lattice basis matrix)에 대해 이를 격자 축소 시키는 선개선 행렬(preconditioning matrix) 역시 주어졌다고 가정하자. 이때, 새로운 행이나 열이 격자 기저 행렬에 추가될 경우 제안한 LLL 갱신 기법은 기존의 선개선 행렬을 적절하게 수정하여 기존의 격자 축소된 정보를 유지하여 갱신된 격자 기저행렬을 격자 축소 시킬 때 계산량을 줄일 수 있게된다. 이 LLL 갱신 기법은 다양한 분야에 응용될 수 있는데, 특히, 격자 축소 기반의 다중 사용자 다중입력 다중출력(multi-user MIMO) 선복호(precoding) 시스템에서 새로운 사용자가 들어오거나 기존 사용자가 떠날 때마다 선개선 행렬을 다시 계산하여야 한다. 하지만 제안한 LLL 갱신 기법을 통해 계산량을 크게 줄일 수 있다.
