논문 11-36-08-05 다중안테나시스템에서적응적조기종료를이용한낮은 복잡도반복검출및복호기 정회원정현승 *, 준회원최경준 **, 정회원김경준 **, 종신회원김광순 ** Low Complexity Iterative Detection and Decoding using an Adaptive Early ermination Scheme in MIMO system Kyung Jun Choi* Regular Member, Hyun Sung Joung** Kyung Jun Kim* Regular Member, Kwang Soon Kim** Associate Member, Lifelong Member 요 약 다중안테나를이용한통신시스템에서반복검출및복호수신기 (iterative detction and decoding) 는비트오류율은상당히줄일수있으나, 각비트마다연판정값을계산하여야하므로높은계산복잡도를요구한다. 본논문에서는적은계산복잡도로연판정값을얻을수있는수신기구조를제안한다. 반복검출및복호수신기는내부복호기로구복호기 (sphere decoder) 를사용하고외부복호기로저밀도패리티부호 (low density parity check) 복호기를사용한다. 연판정값을얻기위한구복호기의복잡도를줄이기위하여트리탐색을레이어별로제한하는레이어심볼탐색 (Layer symbol search, LSS) 를제안한다. 그리고채널과잡음상황에따라달라지는구복호기의동작시간을제한하기위하여반복복호횟수를줄이는적응적조기종료를제안한다. 제안한알고리즘은기존의알고리즘대비 20dB에서 70% 정도낮은계산복잡도를갖으며유사한성능을얻을수있다. Key Words : MIMO, Iterative detection and decoding, Sphere decoder, LDPC, Early termination ABSRAC he iterative detection and decoding (IDD) has been shown to dramatically improve the bit error rate (BER) performance of the multiple-input multiple-output (MIMO) communication systems. However, these techniques require a high computational complexity since it is required to compute the soft decisions for each bit. In this paper, we show IDD comprised of sphere decoder with low-density parity check (LDPC) codes and present the tree search strategy, called a layer symbol search (LSS), to obtain soft decisions with a low computational complexity. In addition, an adaptive early termination is proposed to reduce the computational complexity during an iteration between an inner sphere decoder and an outer LDPC decoder. It is shown that the proposed approach can achieve the performance similar to an existing algorithm with 70% lower computational complexity compared to the conventional algorithms. Ⅰ. 서론 최근대역폭의증가없이높은전송속도를얻을 수있는다중안테나시스템이널리사용된다 [1]. 다중 안테나시스템의성능은다중안테나검출기를내부복호기로사용하고터보나 LDPC 같은오류정정부 이논문은 2008 년정부 ( 교육과학기술부 ) 의재원으로한국연구재단의지원을받아수행된연구임 (KRF-2008-314-D00311). * 삼성전자 SYSEM LSI 사업부 AP 개발팀 (jehis.joung@samsung.com) ** 연세대학교전기전자공학부 {kjchoi87, kimkj}@dcl.yonsei.ac.kr, ks.kim@yonsei.ac.kr), ( : 교신저자 ) 논문번호 :KICS2011-05-233, 접수일자 :2011 년 05 월 31 일, 최종논문접수일자 : 2011 년 8 월 5 일 522
논문 / 다중안테나시스템에서적응적조기종료를이용한낮은복잡도반복검출및복호기 호를외부복호기로사용하는반복검출및복호수신기구조를사용함으로써상당히개선된다 [2]. 그러나다중안테나검출기에서반복검출및복호를위한연판정값인로그우도비 (log likelihood ratio, LLR) 을얻기위한복잡도는안테나의수와변조레벨에따라지수적으로증가하므로실제구현이어렵다. 이를해결하기위하여수신신호의일정반지름안의격자점만을탐색하는구복호기기반의알고리즘이제안되었다 [2-5]. 리스트구복호기 (list sphere decoder, LSD) 는수신신호로부터가장가까운 1개의점을구하는구복호기를확장하여가까운 L개의격자점을찾고, 그격자점들을통하여연판정값을생성한다 [2,3]. 그러나이방식으로찾은 L개의격자점은모든비트에대한 LLR 값을생성하지않으므로성능열화가발생한다. 이를해결하기위하여반복적트리탐색 (repeated tree search, RS) 와단일트리탐색 {single tree search, SS) 는 LLR 값에영향을주는모든노드를방문하여모든비트에대한리스트를생성하여성능열화를방지한다 [4,5]. RS는대립가설에대하여각각트리탐색을수행하고 SS는모든대립가설에영향을미치는노드를한번만방문하여복잡도를줄인다. 최근에제안된고정복잡도구복호기 (fixed sphere decoder, FSD) [7] 와스마트정열및후보추가 (smart orderting and candidate adding, SOCA) [8], 그리고집합분할 (set partition) [9] 은기존의구복호기와달리폭우선탐색 (breadth-first search) 을이용하여트리를탐색하여 LLR을생성한다. 그러나 LSD, RS, SS 뿐만아니라 FSD, SOCA는경판정알고리즘에비해여전히높은복잡도를갖고있으므로낮은복잡도를갖는연판정알고리즘의개발이필요하다. 추가적으로반복검출및복호수신기에서반복복호횟수를정하는것은수신기의성능및복잡도에상당한영향을미친다 [6]. 일반적으로수신기의복잡도는반복복호의횟수에선형적으로증가하지만, 성능은일정횟수이후개선되는수준이미미하다. 따라서반복검출및복호과정에서 LLR 값의변화를이용하여반복복호의횟수를결정하는것이중요하다. 본논문에서는기존의반복검출및복호알고리즘에서대부분의복잡도를차지하는연판정검출기의복잡도를낮추기위하여트리의대립가설을각각의레이어에한정하는트리탐색방법으로레이어심볼탐색 (layer symbol searchm LSS) 를제안한다. 그리고외부복호기로 LDPC 복호기를사용하고그것의특성을이용하여복호횟수를결정하는적응적조기 종료알고리즘을제안한다. 제안한알고리즘은시뮬레이션을통하여기존의제안된알고리즘대비낮은복잡도로유사한성능을얻을수있음을보였다. 본논문의구성은다음과같다. II장에서는시스템모델에대해설명한다. III장에서는제안할트리탐색방법을설명한다. IV장에서는 III장에서제안한트리탐색방법을이용한적응적조기종료방식을알아본다. 끝으로 V장에서시뮬레이션을통하여기존의알고리즘과성능을비교하고복잡도를분석한다. Source Sink b $b LDPC Encoder LDPC Decoder Ⅱ. 시스템모델 그림 1은 송신안테나와 수신안테나로이루어진송수신기의구조를보여주고있다. 정보비트인 는 LDPC 코드로부호화되고인터리빙 (interleaving) 되어비트 로변환되고, 공간다중화로각안테나로나뉘어져보내지고 -ary QAM으로변조된다. 심볼은 -QAM 집합 에서선택되고 는집합 의카디널리티 (cardinality) 이다. 변조된심볼벡터 는선형가우시안채널을통과해서수신기로전달된다. 수신기에수신된신호는다음과같다. (1) 여기서 는채널행렬로각원소들은평균이 0이고분산이 0.5인독립이고동일한분포 (i.i.d.) 를갖는가우시안랜덤변수이다. 잡음벡터 는평균이 0이고분산이 인 i.i.d. 가우시안랜덤변수이다. 수신단의다중안테나검출기는수신된신호 를받아서사후확률값인 LLR 을만들어서 LDPC 복호기에전달한다. LDPC 복호기는정보비트에해당하는 을추정하는것과함께다중안테나검출기가사용할사전확률 LLR 를생성한 c L 2 Interleaver Π Deinterleaver 1 Π Interleaver Π x n L 1 Constellation mapper s H y MIMO detector 그림 1. 구복호기와 LDPC 복호기를이용한반복검출및복호기구조 523
다. 다중안테나검출기는수신된신호 와사전확률 를이용하여다시복호를수행한다. 이와같은방식 으로구복호기와 LDPC 복호기간의 LLR 값 과 값을서로반복하여복호함으로써오류율을줄일 수있다. 다중안테나검출기에서는모든비트에해당하는 LLR 을계산하여야한다. 번째심볼 의 번째 비트의 LLR 값은 max-log 근사화를통하여다음과 같이나타난다. (2) 여기서 와 는각각 번째심볼 의 번째 비트가 0 또는 1 을만족하는전송심볼벡터집합이 다. 식 (2) 의두최소값중하나는 MAP 가설 로모든가능한송신심볼벡터 중거리메트릭 을최소로것이다. 색으로표현할수있다. 채널행렬 의 QR- 분할으로 를얻을수있다. 여기서 는 유니타 리행렬로 를만족한다. 는 상삼각행렬이다. 을식 (1) 에곱하면다음을얻 을수있다. (6) 여기서 이고 이다. 식 (3) 을식 (6) 를이용하여나타내면다음과같이나타난다. (7) 상삼각행렬 에의하여식 (7) 의 는,,..., 에의하여결정되고모든 에대하여음수가아 니다. 따라서 는다음과같이구해진다. (3) 나머지최소값은 으로 MAP 대립가설이라 부른다. (4) 여기서 은 MAP 심볼벡터 의 번째심 볼의 번째비트인 의보수 (complement) 이다. 따라서식 (2) 는다음과같이정리된다. (5) 따라서구복호기는낮은복잡도로하나의 MAP 가설과 개의 MAP 대립가설을구해야한다. Ⅲ. 트리탐색방법 식 (5) 의 MAP 가설과그의대립가설은트리탐 (8) 여기서 으로초기화된다. 는 가줄어듦에따라단조증가하므로미리정해진반지름 보다크면탐색을중단한다. 따라서구복호기의복잡도는미리정해진반지름 에의하여결정된다. 일반적으로 는 보다큰값을가지므로더큰반지름 이필요하다. LSD는반지름 을다음과같이설정한다 [2]. (9) LSD는식 (9) 을통하여얻은반지름을이용하여수신신호로부터가장가까운점을 개의점을찾는다. 그리고 개의점을이용하여식 (2) 를계산한다. LSD의문제점은 개의점으로식 (2) 를계산할때, 모든, 에대하여 와 이적어도하나이상의점을가지지못할가능성으로인하여성능열화가발생한다는점이다. 이를해결하기위하여 SS는모든, 에대하여 와 가하나의점을포함하도록반지름을결정한다. 레이어 에서반지름은다음과같다. 524
논문 / 다중안테나시스템에서적응적조기종료를이용한낮은복잡도반복검출및복호기 (10) 여기서 는이미방문한노드들이반지름에영향 을주는부분이고, 는아직방문하지않은노드들이 반지름에영향을미치는부분이다. (11) 그러나 (9) 과 (10) 에서사용한반지름은경판정에 사용하는반지름, 즉, 보다큰값이므로상당한 복잡도증가를야기한다. 추가적으로대립가설을찾는데복잡도를줄이기 위해서는대립가설을찾는트리를제한해야한다. 이 때, zero-forcing (ZF) 선형검출기와유사한방식을 사용한다. ZF 선형검출기는간섭을미치는신호들을 널링 (nulling) 시킨다. 제안할알고리즘은대립가설 에영향을미치는심볼을제외한나머지를모두널링시킨다. 이렇게심볼수준에서트리를제한한방식을 LSS라부른다. 제안한 LSS는찾아야할트리는각각의레이어로한정하여복잡도를줄인다. 즉, 식 (4) 는다음과같이나타난다. (12) 여기서 는 번째레이어로한정한집합으로다음과같다. 의 10 개의노드를방문해야한다. 그러나 LSS 는대립 가설을각레이어에한정하여방문해야할노드의수를 4개로줄어든다. Ⅳ. 적응적조기종료방법 구복호기와 LDPC 복호기로이루어진터보수신기구조는정해지지않은동작시간으로인하여조기종료방법이필요하다. 기존의방식은정해진복호시간이지나면복호기를강제로종료하고그때의결과를이용한다. 그러나이러한조기종료는상당한성능열화를야기한다.. 따라서수신기의성능열화를최대한저하시키면서조기종료를하는적응적조기종료방법을이용하여복잡도를낮추는것이필요하다. 여기서는구복호기와 LDPC 복호기간 LLR의부호의변화를이용한적응적조기종료방법을제안한다. 우선, 번째반복복호에서 번째 LDPC 블록과 번째 LDPC 블록간의 LLR 부호변화율 은다음과같이정의된다. (14) 여기서 는 LDPC 블록의크기이고, 는 번째 LDPC 블록의 번째반복복호와 번째반복복호 LLR 부호변화를누적한 LLR 부호차이로다음과같이정의된다. (13) (15) 그림 2 는 2 2 4QAM 에서 를찾기위한트 리탐색을보여준다. 식 (4) 를이용한트리탐색은 8 개 rd 3 layer nd 2 layer st 1 layer c 0 c0 = [0 0] c 3 = [0 1] c 0 c c3 0 [ ] ML c = 0,1,1,0 c3 = [1 1] = [1 0] c c 3 0 c 3 그림 2. 2 2 4QAM 시스템에서 를찾기위한트리탐색. 굵은노드는식 (4) 를이용할때방문해야하는노드들. 색칠된노드는식 (11) 을이용할때방문해야하는노드들. 적응적조기종료는앞서정의한 LLR 부호변화율 이미리정한한계점인 를넘게되면조기종료 를일정비율만큼늘리고, 그렇지않으면 를일정비율만큼내린다. 여기서올리는비율을 (>1) 이라하고낮추는비율을 (<1) 이라한다. 적응적조기종료알고리즘흐름도은그림 3에나타냈다. 적응적조기종료알고리즘흐름도는세부분으로나뉜다. 적응부분은새로운조기종료를결정한다. 식 (14) 과 (15) 를이용하여 을계산한다. 만약 이미리정한한계점 보다크면,. 그렇지않으면,. 구복호기부분은적응부분에서결정된 를이용하여 LSS 525
IMAX E num_iter=0 num_vn=0 num_ldpc=num_ldpc+ 1 E=EMIN EMIIN>E E=EMAX E=E*RDOWN EMAX>E Obtain the Delta LLR (LLR sign difference from llr_sign) >CR E=E*RUP Apative Scheme num_iter=num_iter+1 Sphere decoding LSS ree search num_vn=num_vn+1 LSS end? LDPC Decoder Find Error? store llr_sign IMAX >num_iter LDPC decoding E >num_vn END 그림 3. 적응적조기종요알고리즘흐름도. 적응적조기종료알고리즘은크게세부분으로나뉜다. 첫번째부분은조기종료값 (E new) 을결정하는적응부분이고, 나머지두부분은결정된조기종료값 (E new) 으로구복호기와 LDPC 복호기를동작시키는부분이다. 입력변수 num_iter 는반복복호횟수, num_vn 은구복호기에서방문노드의수이다. 를수행한다. 만약 보다방문노드의수가많으면조기종료한다. 끝으로 LDPC 복호기에서는복호한 LLR을저장하고오류가존재하는지확인한다. Ⅴ. 시뮬레이션결과제안한 LSS 구복호기와적응적조기종료는 16QAM을이용한 다중안테나시스템에서시뮬레이션하였다. LDPC 코드의블록크기는 1024이고코드율은 이다. 성능은비트오류율 (BER) 로비교되고, 복잡도 는다음과같다. (16) 여기서 는구복호기와 LDPC 복호기간의최대반복복호횟수이고 과 는각각 번째반복복호에서구복호기와 LDPC 복호기의복잡도이다. RS-APX1과 RS-APX2는각각논문 [4] 에있는것으로, APX1은대립가설은 1bit로제한한것이고 APX2는대립가설을 2bit로제한한것이다. 제안한 LSS 와 RS, 그리고 SS 의성능은그림 4 과 5 에비 교하였다. 그림 5 은조기종료를수행하지않은결과 로 LSS 의성능은 RS-APX1 보다우수하며, RS- APX2 와비교할만하다. 그리고모든트리를탐색한 RS-MLM 과비교하여 10-3 에서 1.5dB 의열화가있 음을확인할수있다. 그림 5 에서는고정조기종료와 적응적조기종료를수행하였을때, 얻을수있는성 BER 10 0 Perform ance com parison without early term ination 10-1 10-2 10-3 M L, no iteration LSS RS-APX1 RS-APX2 RS-MLM 10 12 14 16 18 20 SNR 그림 4. 4 4 16QAM 시스템에서조기종료를수행하지않았을때성능곡선. 526
논문 / 다중안테나시스템에서적응적조기종료를이용한낮은복잡도반복검출및복호기 능을나타냈다. 고정조기종료와적응적조기종료의성능차이가거의무시할만하다는것을알수있다. 끝으로고정조기종료와적응적조기종료를수행하였을때, 계산복잡도는그림 6에나타냈다. 낮은 SNR에서반복복호를위한 가증가하므로더큰복잡도를갖는다. 제안한 LSS는모든 SNR 영역에서 RS-APX1과 RX-APX2보다낮은복잡도를갖음을알수있다. 그리고 20dB에서고정조기종료를사용한 LSS 대비적응적조기종료를이용하면 70% 정도복잡도를낮출수있다. Ⅵ. 결론본논문에서는다중안테나시스템에서낮은복잡도를갖는터보수신기구조를제안하였다. 수신기는내부복호기로구복호기를사용하고외부복호기로 LDPC 복호기를사용하였다. 구복호기의복잡도를줄이기위하여 LSS를제안하였다. 그리고 LSS의동작시간을제한하기위하여적응적조기종료를제안하였다. LSS와적응적조기종료를이용하면기존의제안된알고리즘과유사한성능을갖을가지면서 20dB에서 70% 정도의복잡도감소를얻을수있음보였다. 참고문헌 그림 5. 4 4 16QAM 시스템에서고정조기종료와적응조기종료를수행하였을때성능곡선. I MAX =4, E min =S, E max = 2000, =0.01, R UP = 1.5, R DOWN =0.5. 그림 6. 4 4 16QAM 시스템에서고정조기종료와적응조기종료를수행하였을때복잡도곡선. 그림 4 와동일한환경에서시뮬레이션수행. [1] I. E. elatar, Capacity of multi-antenna Gaussian channels, Eur. rans. elecom, Vol. 10, pp.585-595, v. 1999. [2] B. M. Hochwald and S. ten Brink, Achieving near-capacity on a multiple -antenna channel, in Proc. Allerton Conf. Commun., Control, and Computing, Monticello, IL, Oct. 2001. [3] H. Vikalo, B. Hassibi, and. Kailath, Iterative decoding for MIMO channels via modified sphere decoding, in IEEE ransactions on Wireless communications, Vol.3,.6, pp. 2299-2311, v. 2004. [4] R. Wang and G. B. Giannakis, Approaching MIMO channel capacity with reduced-complexity soft sphere decoding, in Proc. IEEE Wireless Commun. and Networking Conf.(WCNC), Vol. 3, pp.1620-1625, Mar. 2004. [5] C. Studer, A. Burg and H. Bolcskei, Soft-Output Sphere Decoding: Algorithm and VLSI Implementation, in IEEE Journal on Selected Areas In Communications, Vol.26, 2, pp.290-300, Feb. 2008. [6] A. Burg, M. Borgmann, M. Wenk, M. Zellweger, W. Fichtner, and H. Bolchkei, \VLSI implementation of MIMO detection using the sphere decoding algorithm, in IEEE J. Solid-State Circuits, Vol.40, 7, pp.1566-1577, July 2005. [7] L. G. Barbero and J. S. hompson, Extending a Fixed-Complexity Sphere Decoder to Obtain 527
Likelihood Information for urbo-mimo Systems, IEEE rans. Vehic. echn., Vol.57,.5, pp.2804-2814, Sept. 2008 [8] D. L. Milliner, E. Zimmermann, J. R. Barry, and G. Fettweis, A fixed complexity smart candidate adding algorithm for soft-output MIMO detection, IEEE. J. Sel. opics in Sign. Process., Vol.3,.6, pp.1016-1024, Dec. 2009. [9] K. Lai, L. Lin, Low-Complexity Adaptive ree Search Algorithm for MIMO Detection, IIEEE ransactions on Wireless communications, Vol. 8,.7, July 2009. 정현승 (Hyun Sung Joung) 정회원 1996년 2월부산대학교컴퓨터공학과학사 2009년 2월연세대학교전기전자공학부석사 1996년 3월 현재삼성전자 SYSEM LSI사업부 < 관심분야 > 무선통신시스템, 무선통신용반도체설계 김경준 (Kyung Jun Kim) 정회원 2006년 2월경희대학교전자전파공학과학사 2008년 2월연세대학교전기전자공학부석사 2008년 3월 현재연세대학교전기전자공학부박사과정 < 관심분야 > 무선통신시스템, 통신신호처리, 자기구성네트워크김광순 (Kwang Soon Kim) 종신회원 1994년 2월 KAIS 전기전자공학과학사 1996년 2월 KAIS 전기전자공학과석사 1999년 2월 KAIS 전기전자공학과박사 1999년 3월 2000년 3월 Dept. ECE, UC San Diego, 박사후연구원 2000년 4월 2004년 2월한국전자통신연구원선임연구원 2004년 3월 현재연세대학교교수 < 관심분야 > 이기종네트워크, 하이브리드네트워크, 채널부호, 계층간최적화, 협력통신 최경준 (Kyung Jun Choi) 준회원 2010년 2월연세대학교전자공학부학사 2010년 3월 현재연세대학교전자공학부석박사통합과정 < 관심분야 > 무선통신시스템, 다중안테나시스템, 통신신호처리 528