[논문]제한된 연산량을 갖는 Dijkstra 탐색 기반의 스피어 디코딩

윤혜연; 김태환

doi:10.5573/ieie.2017.54.7.12

제한된 연산량을 갖는 Dijkstra 탐색 기반의 스피어 디코딩
Dijkstra's Search-Based Sphere Decoding with Complexity Constraint 원문보기

Journal of the Institute of Electronics and Information Engineers = 전자공학회논문지, v.54 no.7 = no.476, 2017년, pp.12 - 18

윤혜연 (한국항공대학교 항공전자정보공학과) , 김태환 (한국항공대학교 항공전자정보공학과)

초록
AI-Helper

본 논문은 MIMO 통신 시스템을 위한 Dijkstra 탐색 기반의 제한된 연산량을 갖는 스피어 디코딩 (sphere decoding; SD) 알고리즘을 제안하고 이에 대한 성능을 평가한다. Dijkstra 탐색 기반의 SD는 MIMO 심볼 검파 과정에서 저 복잡도로 준 최적의 에러율 성능을 달성하는 효율적인 tree 탐색 알고리즘이다. 하지만 Dijkstra 탐색 기반의 SD는 채널 환경에 따라 연산량이 가변적이고, 최악의 경우 전역 탐색의 경우에 해당하는 높은 연산량을 갖는 심각한 문제가 있다. 본 논문에서는 이러한 문제를 해결하기 위해서 연산량을 제한시킨 새로운 Dijkstra 탐색 기반의 SD 알고리즘을 제시한다. 제안된 알고리즘은 연산량이 제한되었음에도 여전히 준 최적의 에러율 성능을 달성함을 모의 실험을 통해 검증하였다.

Abstract ▼ AI-Helper

This paper presents a Dijkstra's-search-based sphere decoding (SD) algorithm with limited complexity for the symbol detection in MIMO communication systems. The Dijkstra search-based SD is efficient to achieve a near-optimal error rate in the MIMO symbol detection, but has a critical problem in that its complexity is variable and can correspond to that of the exhaustive search in the worst case. The proposed algorithm limits the computations while achieving a near-optimal error rate. Simulation results show that the error rate is near optimal even with the limited complexity.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문에서는 MIMO 시스템을 위한 제한된 연산량을 갖는 Dijkstra 탐색 기반의 효율적인 SD를 제시하였다. 제안된 알고리즘은 Dijkstra-SD에 연산량 내에 알고리즘을 효율적으로 종료시키는 방법을 추가하여 검파에 소요되는 연산량을 제한한다.
본 논문에서는 제한된 연산량을 갖는 새로운 DijkstraSD 알고리즘을 제안한다. 제안하는 알고리즘은 기존의 Dijkstra-SD를 기반으로, 연산량의 상한을 설정하고, 이를 초과할 수 있는 상황을 감지하여 알고리즘을 효과적으로 종료하는 방법을 추가하여 검파에 소요되는 연산량을 제한한다.

제안 방법

5번 줄에서, 조기 종료를 위해 저장된 path의 말단 노드의 레이어 위치와 잔여 tree 방문 횟수를 고려하여 조기 종료 조건을 만족하면 조기 종료를 수행한다. 21-26번 줄에서, 조기 종료를 위해 저장된 path의 나머지 노드를 SIC에 기반하여 순차적으로 확장하여 full-length path를 완성하고, 이를 검파 결과로 출력하여 알고리즘을 종료한다. 그림 2는 제안하는 알고리즘을 통해 심볼을 검파 하는 예를 보인다.
Ⅲ장에서는 연산량이 제한된 새로운 Dijkstra-SD 알고리즘을 제안한다. Ⅳ장에서 제안하는 알고리즘을 다양한 환경에서의 모의 실험하고 이를 바탕으로 유효성을 고찰한다. 마지막으로 Ⅴ장에서 본 논문의 결론을 유도한다.
여기서 | Ω |는 Ω의 크기를 의미한다. 뽑혀진 path가 full-length path라면 해당 path에 대응되는 심볼 벡터를 검파의 결과로 출력하며 알고리즘을 종료한다. s는 검파 과정의 복잡도를 줄이고 하드웨어 구현을 용이하게 할 수 있도록 제한되는 탐색 공간의 크기이다.
제안된 알고리즘은 Dijkstra-SD에 연산량 내에 알고리즘을 효율적으로 종료시키는 방법을 추가하여 검파에 소요되는 연산량을 제한한다. 이를 위해, 검파에 소요되는 연산량의 상한을 설정하고, 후보 해와 사용 가능한 잔여 연산량을 고려하여 제한된 연산량을 초과할 수 있는 상황에서 SIC를 기반으로 잔여 연산량 내에 알고리즘을 종료한다. 다양한 환경의 모의 실험을 통해, 제안된 알고리즘은 검파에 필요한 연산량이 제한됨에도 불구하고 준 최적의 성능을 달성한다는 것이 증명되었다: 4×4 16QAM 시스템에서 10^-5의 비트 에러율을 달성 했을 때, 제안된 알고리즘은 기존의 연산량이 제한되지 않은 기존의 알고리즘과 SNR 0.
이를 위해, 탐색 과정 중 연산량의 상한을 초과할 수 있는 상황에서 후보 해와 사용 가능한 잔여 연산량을 고려하여 연속 간섭 제거 기법 (successive interference cancellation; SIC)[18] 을 도입하여 잔여 연산량 내에 검파를 종료한다.
이렇게 조기 종료를 수행하기 위해서, 해당 path의 leaf쪽 말단 노드가 L번째 레이어에 위치해 있다면, L-1번의 추가적인 tree 방문이 소요된다. 이를 통해, 알고리즘의 진행 과정 중에 확장된 path들 중에서 말단 노드가 가장 낮은 레이어에 위치한 것을 바탕으로 조기 종료 시간과 잔여 tree 방문 횟수를 비교하여 조기 종료 조건 (stopping criterion)을 설정한다.
제안된 알고리즘은 uncoded AWGN 채널 환경의 모의 실험을 통해 심볼 검파기 자체의 성능이 면밀히 평가 되었다. 모의 실험에서 신호대잡음비(signal-to-noise ratio; SNR)는 E_S/N₀으로 정의하고, Es는 수신 안테나의 심볼 에너지를 의미한다.
제안하는 알고리즘은 기존의 Dijkstra-SD 알고리즘에서 tree 탐색 도중 연산량의 상한을 초과할 수 있는 상황을 감지하여, 잔여 시간 동안 검파를 완료하여 알고리즘을 조기 종료한다. 제안하는 알고리즘의 연산량은 tree 방문 횟수로 추산되고, 최대 tree 방문 횟수를 설정하여 연산량을 제안한다.
제안하는 알고리즘은 기존의 Dijkstra-SD를 기반으로, 연산량의 상한을 설정하고, 이를 초과할 수 있는 상황을 감지하여 알고리즘을 효과적으로 종료하는 방법을 추가하여 검파에 소요되는 연산량을 제한한다.
제안하는 알고리즘은 기존의 Dijkstra-SD 알고리즘에서 tree 탐색 도중 연산량의 상한을 초과할 수 있는 상황을 감지하여, 잔여 시간 동안 검파를 완료하여 알고리즘을 조기 종료한다. 제안하는 알고리즘의 연산량은 tree 방문 횟수로 추산되고, 최대 tree 방문 횟수를 설정하여 연산량을 제안한다. 알고리즘의 조기 종료는 확장된 path들 중에서 말단 노드가 가장 낮은 레이어에 위치한 것을 기반으로 진행된다.

데이터처리

추가적으로 실제적인 환경을 고려하기 위해, 상관 채널에서 제안된 알고리즘의 성능이 평가되었다. 채널 환경은 (#Latex구현필요)에 의해 만들어 진다.

이론/모형

Dijkstra-SD는 검파 tree의 탐색을 Dijkstra가 제안한 best-first tree 탐색 방법에 의해 수행한다. 여러 문헌에서 Dijkstra-SD는 DFS-SD나 K-best SD보다 낮은 연산 복잡도를 보이면서 준 최적의 에러율 성능을 달성함이 입증되었다^[12～14].

성능/효과

다양한 환경의 모의 실험을 통해, 제안된 알고리즘은 검파에 필요한 연산량이 제한됨에도 불구하고 준 최적의 성능을 달성한다는 것이 증명되었다: 4×4 16QAM 시스템에서 10-5의 비트 에러율을 달성 했을 때, 제안된 알고리즘은 기존의 연산량이 제한되지 않은 기존의 알고리즘과 SNR 0.2dB 이하의 성능 차이를 보였다.
그림 5에 상관 채널 환경에서 검파 tree의 방문 횟수와 에러율 성능을 보인다. 상관 채널 환경에서 제안된 알고리즘은 연산량이 적절히 제한됨에도 불구하고 준 최적의 에러율 성능을 달성한다.
제안하는 알고리즘은 다수의 심볼 벡터로 구성된 전체 블록에 대해 검파에 소요되는 총 연산량이 주어진 경우 더 높은 에러율 성능을 달성할 수 있다^[16]. 이 경우, 전체 블록에서 심볼 검파에 소요되는 연산량의 상한을 초과하지 않는 범위 내에서 개별 심볼 벡터 검파에 소요되는 연산량의 상한을 유동적으로 할당한다.
이를 위해, 탐색 과정 중 연산량의 상한을 초과할 수 있는 상황에서 후보 해와 사용 가능한 잔여 연산량을 고려하여 연속 간섭 제거 기법 (successive interference cancellation; SIC)^[18] 을 도입하여 잔여 연산량 내에 검파를 종료한다. 제안하는 알고리즘은 블록 기반으로 검파에 필요한 총 연산량이 주어지는 경우 더 우수한 에러율 성능을 달성한다^[16]. 제안하는 알고리즘의 유효성이 다양한 환경에서의 모의 시험을 통해 검증되었다: 4×4 16QAM 시스템에서 10-5의 비트 에러율을 달성 할 때, 제안하는 알고리즘은 기존의 연산량이 제한되지 않은 Dijkstra 탐색 기반 SD와 비교했을 때 SNR 0.
제안하는 알고리즘의 유효성이 다양한 환경에서의 모의 시험을 통해 검증되었다: 4×4 16QAM 시스템에서 10-5의 비트 에러율을 달성 할 때, 제안하는 알고리즘은 기존의 연산량이 제한되지 않은 Dijkstra 탐색 기반 SD와 비교했을 때 SNR 0.2dB 이하의 성능 차이를 보였다.

후속연구

본 논문에서는 MIMO 시스템을 위한 제한된 연산량을 갖는 Dijkstra 탐색 기반의 효율적인 SD를 제시하였다. 제안된 알고리즘은 Dijkstra-SD에 연산량 내에 알고리즘을 효율적으로 종료시키는 방법을 추가하여 검파에 소요되는 연산량을 제한한다. 이를 위해, 검파에 소요되는 연산량의 상한을 설정하고, 후보 해와 사용 가능한 잔여 연산량을 고려하여 제한된 연산량을 초과할 수 있는 상황에서 SIC를 기반으로 잔여 연산량 내에 알고리즘을 종료한다.

질의응답

핵심어	질문	논문에서 추출한 답변
	무선 통신 시스템에서 MIMO기술을 통해 무엇을 가능케 하는가?	무선 통신 시스템에서 multiple-input multiple-output(MIMO) 기술은 추가적인 전송 전력 및 대역폭 사용 없이 공간 상의 다수의 전송 채널을 동시에 사용하여 에러율과 전송 속도를 향상 시킨다[1]. 이를 통해 고성능의 데이터 통신을 가능케 한다. 하지만 MIMO 시스템에서는 복잡한 심볼 검파 과정 때문에 수신 단의 높은 연산 복잡도를 가지게 된다.
	Dijkstra 탐색 기반의 SD는 무엇인가?	본 논문은 MIMO 통신 시스템을 위한 Dijkstra 탐색 기반의 제한된 연산량을 갖는 스피어 디코딩 (sphere decoding; SD) 알고리즘을 제안하고 이에 대한 성능을 평가한다. Dijkstra 탐색 기반의 SD는 MIMO 심볼 검파 과정에서 저 복잡도로 준 최적의 에러율 성능을 달성하는 효율적인 tree 탐색 알고리즘이다. 하지만 Dijkstra 탐색 기반의 SD는 채널 환경에 따라 연산량이 가변적이고, 최악의 경우 전역 탐색의 경우에 해당하는 높은 연산량을 갖는 심각한 문제가 있다.
	DFS-SD의 문제점은 무엇인가?	DFS-SD는 분기한정법(Branch and bound)에 기반한 깊이 우선 탐색을 통해 최적의 해를 찾는다[5～7]. DFS-SD는 최적의 에러율 성능을 보장하지만 채널 환경에 따라서 검파에 소요되는 연산량이 유동적인 문제점이 있다. 2008년, L.

참고문헌 (19)

B. M. Hochwald and S. Ten Brink, "Achieving near-capacity on a multiple-antenna channel," IEEE Trans. Commun., vol. 51, no. 3, pp. 389-399, Mar. 2003.

상세보기
E. G. Larsson, "MIMO detection methods: How they work [lecture notes]," IEEE Signal Process. Mag., vol. 26, no. 3, pp. 91-95, May 2009.

상세보기
S. Yang and L. Hanzo, "Fifty years of MIMO detection: The road to large-scale MIMOs," IEEE Commun. Surveys & Tutorials, vol. 17, no. 4, pp. 1941-1988, Sep. 2015.

상세보기
M. C. Shin, Y. S. Song, D. S. Kwon, J. T. Seo, C. Y. Lee, "Performance analysis of maximum likelihood detection for the spatial multiplexing system with multiple antennas," Journal of The Institute of Electronics and Information Engineers, vol 42, no 12, pp 103-110, Dec. 2005.
C. P. Schnorr and M. Euchner, "Lattice basis reduction: improved practical algorithms and solving subset sum problems," Mathematical Programming, vol. 66, pp. 181-199, 1994.

상세보기
X. Chen, G. He, and J. Ma, "VLSI implementation of a high-throughput iterative fixed-complexity sphere decoder," IEEE Trans. Circuits Syst. II, vol. 60, no. 5, pp. 272-276, May 2013.

상세보기
D. Seethaler and H. Bolcskei, "Infinity-norm sphere-decoding," in Proc. Int. Symp. Inf. Theory, Jul. 2008, pp. 2002-2006.
L. G. Barbero and J. S. Thompson, "Fixing the complexity of the sphere decoder for MIMO detection,"IEEE Trans. Wireless Commun., vol. 7, pp. 2131-2142, June 2008.

상세보기
M.Wenk, M. Zellweger, A. Burg, N. Felber, and W. Fichtner, "K-best MIMO detection VLSI architectures achieving up to 424 Mbps," in Proc. Int. Symp. Circuits Syst., May 2006, pp. 1151-1154.
T.-H. Kim and I.-C. Park, "Small-area and low-energy K-best MIMO detector using relaxed tree expansion and early forwarding," IEEE Trans. Circuits Syst. I, vol. 57, no. 10, pp. 2753-2761, Oct. 2010.

상세보기
J. W. Kim, J. W. Kang, C. Y. Lee, "An Adaptive K-best detection algorithm for MIMO systems," Journal of The Institute of Electronics and Information Engineers, vol 43, no 10, pp 1-7, Oct. 2006.
T. Fukatani, R. Matsumoto, and T. Uyematsu, "Two methods for decreasing the computational complexity of the MIMO ML decoder," IEICE Trans. Fundamentals, vol. E87-A, no. 10, pp. 2571-2576, Oct.2004.
M. Myllyla, M. Juntti, and J. R. Cavallaro, "A list sphere detector based on Dijkstra's algorithm for MIMO-OFDM systems," in Proc. Personal, Indoor Mobile Radio Commun., Sep. 2007, pp. 1-5.
T.-H. Kim and I.-C. Park, "High-throughput and area-efficient MIMO symbol detection based on modified Dijkstra's search," IEEE Trans. Circuits Syst. I, vol. 57, no. 7, pp. 1756-1766, July 2010.

상세보기
A. Burg, M. Wenk, and W. Fichtner, "VLSI implementation of pipelined sphere decoding with early termination," presented at the EUSIPCO, Florence, Italy, Sep. 2006.
A. Burg, M. Borgmann, M. Wenk, C. Studer, and H. BOlcskei, "Advanced receiver algorithms for MIMO wireless communications," in Proc. Conf. Design, Automation and Test in Europe. European Design and Automation Association, 2006, pp. 593-598.
T.-H. Kim and J.-H. Kim "Partitioned scheduling for sphere decoding with runtime constraints for practical MIMO communication systems," in Proc. Personal, Indoor Mobile Radio Commun., Aug. 2015, pp. 721-725.
G. D. Golden, G. J. Foschini, R. A. Valenzuela, and P. W. Wolniansky, "Detection algorithm and initial laboratory results using V-BLAST space-time communications architecture," IEE Electron. Lett., vol. 35, pp. 14-16, Jan. 1999.

상세보기
T. Handte, A. Muller, and J. Speidel, "BER analysis and optimization of generalized spatial modulation in correlated fading channels," in Proc. Veh. Tech. Conf. IEEE, Sep. 2009, pp. 1-5.

저자의 다른 논문 :

LOADING...

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증