Multi-input multi-output (MIMO) is the promising technology for next generation wireless communication system, since it can obtain high throughput and diversity gain on rich scattering environment. However, Maximum likelihood (ML) detection which is optimal bit error rate detector for MIMO system is infeasible due to the complexity of ML when a large number of antennas used together with high order modulation scheme. Therefore, Sphere Decoding (SD), which is the lattice decoding algorithm, is introduced for MIMO system to reduce the complexity of ML detection. SD is an attractive approach to reduce the implementation complexity of ML detector, significantly. But it still has the high complexity. In this paper, two efficient architectures are proposed for SD. One is efficient for small area and high throughput, the other is the architecture for run-time constraint. First architecture efficiently reduces the memory usage and critical path up to the half of the state-of-the-art architecture. To reduce the complexity, an enhance direct Schnorr-Euchner (SE) enumeration scheme which uses the property of quadrature amplitude modulation (QAM) signal constellation is also proposed. The second one finds the ML solution earlier by adopting parallel processing, and it makes the instantaneous throughput more stable with Modified-Schnorr-Euchner(MSE) algorithm.
SD 는 MIMO 기술에서의 주요 signal processing 으로 전송한 MIMO 벡터에 대한 수신기에서의 검출 scheme 이다. optimal 한 벡터 검출 방식으로 인정받고 있는 ML(Maximum Likelihood) detection 의 경우 Antenna 의 수가 증가하고, Modulation 수가 증가할수록 계산의 복잡도가 너무 심해 실제 application 에서 적용되지 못했으나, 최근 고집적의 chip 양산 기술을 이용하여, ML 의 performance 에 근접하는 SD (Sphere Decoder) 의 Hardware implementation 에 대한 연구가 전 세계적으로 활발히 이루어지고 있다.
Sphere Decoder 의 최신 아키텍쳐는 Burg 의 논문[2]에서 볼 수 있는데, SD의 tree-searching 알고리즘의 특징을 잘 이용하여 2 가지 기본 유닛으로 나눈 뒤 한 사이클에 트리의 한 레벨을 이동할 수 있다는 장점이 있다. 또한 $L^infinite$ norm 을 PED(Partial Euclidian Distance) 계산에 이용하고 QAM signal constellation 의 성질을 이용하여 sorted list 를 만드는 방법을 도입함으로써 SD 의 복잡도를 많이 계선하였다. 하지만 구현된 아키텍쳐에서의 메모리 사용이 크고 한 클럭에 모든 계산을 수행하게 됨으로 critical path 가 길다는 단점이 있다. 또한 SD 는 순간적인 throughput 이 채널의 gain 이나 noise 에 의해 영향을 받게 된다. 그리하여 구현을 하기 위해서는 SD 의 processing cycle 에 제한을 두어야 한다. 하지만 이런 제한은 SD 의 성능 저하를 야기시킨다.
본 논문은 위의 문제점을 해결하기 위하여 두 가지 효율적인 SD 의 아키텍쳐를 제안한다. 첫 번째 아키텍쳐는 critical path 를 줄이고 memory 의 사이즈를 줄이는 것이다. 이를 위해 signal constellation 에서의 decision boundary 를 이용하여 가장 작은 PED 를 갖는 노드를 search 유닛을 거치지 않고 바로 찾아내는 방법을 도입하였다. 이 방법을 도입하게 되면 QAM signal constellation 의 특성을 이용 할 수 있게 되고 이로 인해 각 계산된 노드의 path history 들을 저장하지 않을 수 있게 된다. 또한 모든 계산을 진행하기 전에 MIN 노드를 알 수 있으므로 다음 level 에서 필요한 계산을 미리 수행해 놓을 수가 있게 된다. 결과적으로 메모리의 사이즈를 반으로 줄일 수 있었으며 critical path 또한 36% 줄일 수 있었다.
두 번째로 제안한 아키텍쳐는 실제 구현시 동작 cycle 의 제한이 있는 환경하에서의 효율적인 아키텍쳐이다. 시뮬레이션을 통한 분석을 통해서, ML solution 이 SD 가 찾아내는 첫 번째 candidate 의 근처에 있을 확률이 높음을 알 수 있다. 제안된 아키텍쳐는 정해진 cycle 안에 보다 확률이 높은 node 들을 검색하기 위해 parallel processing 이 적용되었다. Parallel processing 을 효율적으로 이용하기 위해서 Schnorr Euchner 알고리즘을 변경하였고 이를 통해서 cycle 제한이 있는 환경 하에서도 퍼포먼스의 저하가 생기지 않게 된다. 이 방법의 단점은 패럴랠 프로싱에서 생기는 결과중에서 2 개의 MIN node 를 선택하는 로직의 critical path 가 크게 증가한다는 것이다. 이 로직의 critical path 를 줄이기 위해서 signal constellation 의 성질을 이용하는 방법을 적용하였다.
