Lattice reduction with fast convergence algorithm and its application to the detection in temporally and spatially-correlated MIMO channel

다국어 초록 (Multilingual Abstract)

This thesis proposes a modified LLL algorithm, which named fast convergence algorithm (FC), in lattice reduction (LR) aided detection which provides advantage of the convergence time compared to conventional LLL reduction algorithm. Generally, LLL algorithm transforms MIMO channel, regarded as basis vector, into orthogonal-like one by using iterative basis reduction which is mainly classified into three functional processes: a Gram-Schmidt orthogonalization, a size-reduction, and a basis swapping. The proposed FC algorithm uses the swapping condition that the all of size reduced basis vectors are sorted out in the descending order of their basis vectors at once while conventional LLL algorithm swap only adjacent basis vectors per one-iteration. Since the same time complexity per iteration is applied for both two algorithms, the convergence time depends on the number of iteration needed. Therefore the convergence time to terminate the algorithm can be decreased by iteration number differences between two algorithms. Moreover, this proposed FC algorithm also provides the shorter resultant basis vectors. Results for these properties are developed, and illustrated by analytical and numerical analyses.In addition, three different schemes to reduce the complexity of LR in specific condition are proposed in this thesis: One is sorted basis reduction method, second is consecutive lattice reduction (CLR), and third is pre-lattice reduction (PLR). First sorting out basis vectors at the initial point helps LR algorithm (whether LLL or FC) to achieve the reduced basis vectors with reduced number of iterations. Secondly, time-correlated nature of the channel can be used in reducing the iteration complexity of doing LR by taking advantage of the information of LR results in the previous symbol time. Finally, PLR applied in spatially correlated channel reduces the number of iteration of LR by pre-multiplying the channel matrix by transformation matrix which reduces the square root of the transmitter correlation matrix. These schemes may provide a better stating point for the lattice reduction algorithm.Simulation result shows that the proposed FC algorithm has fast convergence time and three different schemes have low computational efforts due to small number of iteration taken, which leads to fast convergence and reduced complexity for specific condition.

국문 초록 (Abstract)

차세대 통신 시스템에서 요구되는 멀티미디어 서비스 기술의 급속한 확대와 더불어 고품질의 데이터를 고속으로 전송하기 위한 기술로 MIMO 시스템에 대한 많은 연구가 진행 되고 있다. 그러나 MIMO 시스템은 전송된 신호들 사이의 간섭으로 인해 데이터 검출에 어려움이 있다. 최대우도 (ML) 검출 기법은 최적의 성능을 갖지만, 안테나의 수가 증가하거나 변조 차수 (modulation order) 가 증가할수록 복잡도가 기하급수적으로 증가한다는 문제로 인해 실제 시스템에서의 적용에 한계가 존재한다. 또한 ZF과 MMSE와 같은 선형 검출 기법은 낮은 복잡도를 갖지만, ML 검출로 얻을 수 있는 다이버시티 차수 (diversity order)를 잃게 되어 성능의 저하가 발생한다. 최근 LR (Lattice Reduction)을 이용한 선형 검출 기법이 선형 검출 기법과 유사한 복잡도에 ML과 동일한 다이버시티 차수를 제공하는 것이 기존의 많은 연구에서 알려졌다.기존의 대부분의 연구는 채널이 느리게 변하여 일정 심볼시간 (symbol time) 또는 프레임 동안 채널이 변하지 않는 블록 페이딩 채널 (Block fading channel)만을 고려하였다. 그러나 채널 환경이 시간에 대해 빠르게 변하는 상황이라면, 채널의 변화에 따라 계속적으로 LR을 수행해야 하며 이는 시스템 복잡도의 증가를 가져온다. 또한 이는 선형 검출 기법과 유사한 복잡도를 갖는다는 기존의 가정에도 위배된다. 따라서 이러한 채널 환경에서 LR을 이용한 선형 검출 기법이 효과적이기 위해서는 기존의 복잡도를 줄일 수 있는 방법이 필요하다.본 논문은 새로운 LR 알고리즘을 제안하는 것과 시간과 공간 상관이 있는 채널에서 복잡도를 줄일 수 있는 기법의 두 가지 관점에서 연구를 수행하였다. 첫째 FC (Fast Convergence)라고 명명된 LLL의 변형 알고리즘은 기존의 LR 방법으로 가장 많이 사용되는 LLL (Lenstra, Lenstra, and Lovász) 방법을 변형하여 LR을 고속으로 수행하기 위해 제안되었다. LLL 알고리즘은 기저 벡터의 교환 또는 정렬이 없을 때까지 미리 정의된 형태의 순서대로 LR을 반복적으로 수행한다. FC 알고리즘은 LLL 알고리즘의 기저 벡터 교환 조건을 정렬할 수 있는 조건으로 변형하여 반복횟수 (iteration)를 75% 정도 줄여 LR을 빠르게 수행하고, LR을 수행한 기저 벡터의 길이 (Euclidian norm)도 일정 조건에서 LLL보다 더 짧아지는 것을 보였다. 또한 미리 입력 기저 벡터들을 길이 (Euclidian norm) 순서대로 정렬한 후 LR을 수행하여 80% 정도 반복횟수를 줄이는 결과를 보였다. 여기에 FC 알고리즘의 수렴성 (convergence)과 LR을 수한 기저 벡터들의 특성에 대해 LLL과 비교, 분석하여 보다 길이가 짧고 직교성을 띄는 것을 증명하였다.둘째, 본 논문은 시간 또는 공간 상관이 있는 채널에서 복잡도를 줄일 수 있는 방법에 대해서 제안하였다. 시간 상관이 있는 채널에서는 이전 심볼시간에서 수행한 LR의 unimodular 변형 행렬을 현재의 채널에 곱하여 LR을 수행하는 CLR (consecutive lattice reduction) 기법을 사용하여 복잡도를 줄일 수 있다. CLR 기법은 고속의 상황에서도 LLL과 FC 알고리즘에서 각각 65%, 40%의 복잡도를 줄이는 결과를 보였다. 기존의 LLL과 비교하여 미리 정렬된 CLR을 사용할 경우 90% 가량 복잡도를 줄이는 것을 확인 할 수도 있었다.마지막으로 채널의 공간 상관이 있을 때의 복잡도를 줄일 수 있는 PLR (pre-lattice reduction) 기법을 제안하였다. 공간 상관이 있는 경우 채널이 불량조건 (ill-condition)이 되어 LR의 반복횟수를 증가시키게 된다. 따라서 송신 상관 (transmitter correlation)을 알고 있을 때, 송신 상관에 대해 미리 LR을 수행하고 여기서 얻어지는 unimodular 변형 행렬을 채널에 미리 곱하여 LR의 복잡도를 줄여줄 수 있다. 송신 상관과 수신 상관 (receiver correlation)이 모두 있는 경우LLL은 15%, FC는 10% 정도의 복잡도 감소를 보였고, 송신 상관만 있는 경우 LLL은 30%, FC는 15% 정도의 복잡도 감소를 확인 할 수 있었다.본 연구는 기존의 LLL 알고리즘과 동일한 검출 성능을 가지면서 복잡도를 획기적으로 줄일 수 있는 알고리즘과 기법을 제안하였다. 제안한 알고리즘과 기법은 시간에 대해 빠르게 변하는 채널 환경에서도 LR을 효율적으로 적용할 수 있도록 해준다.