논문 07-32-1C-05 한국통신학회논문지 07-1, Vol. 32, No. 1C 여러입력여러출력시스템에알맞도록너비를먼저탐색하는가장비슷함복호방식 준회원강현구 *, 종신회원송익호 *, 준회원안태훈 *, 종신회원김윤희 ** A Maximum Likelihood Decoding Scheme Based on Breadth-First Searching for Multi-Input Multi-Output Systems Hyun Gu Kang* Associate Member, Iickho Song* Lifelong Member, Taehun An* Associate Member, Yun Hee Kim** Lifelong Member 요 약 여러입력여러출력시스템에서쓰는복호방식인공복호기는깊이를먼저탐색하는가장비슷함복호방식이다. 이논문에서는너비를먼저탐색하는방법을바탕으로, 여러입력여러출력시스템에알맞은새로운가장비슷함복호기를제안한다. 제안한복호기는가장비슷함검파기와비트오류율이같으며공복호기보다계산량이꽤적다는것을모의실험으로보인다. Key Words : Multi-Input Multi-Output, Maximum Likelihood Decoding, Sphere Decoder, Breadth-First Searching, Computational Burden ABSTRACT The sphere decoder (SD) has recently been proposed to perform maximum likelihood (ML) decoding for multi-input multi-output systems. Employing a `breadth-first' searching algorithm for closet points in a lattice, we propose a novel ML decoding scheme for multi-input multi-output systems. Simulation results show that the proposed scheme has the same bit error rate performance as the conventional ML decoders while allowing significantly lower computational burden than the SD. Ⅰ. 서론무선통신채널에서여러길감쇄가일어날때보내는쪽과받는쪽에안테나를여러개쓰면여러길감쇄의영향을줄일뿐아니라주파수효율도높일수있다 [1]. 이러한여러입력여러출력 (multiinput multi-output) 시스템의보기로는, 꾸미기쉽고 얼개가비교적간단한브이- 블래스트 (vertical-bell Laboratories Layered Space-Time: V-BLAST) 시스템을들수있다 [2]. 브이- 블래스트시스템에서는보내려는데이터를몇개로나누고, 이를나눈수만큼의송신안테나에서보낸다. 이때, 이와같이송신안테나를여러개쓰면보낸신호끼리간섭을일으키기때문에효율적인검파기를설계하는것이무엇 이논문은과학기술부의재원으로한국과학재단이선정하여지원하는 2005 년국가지정연구실사업과제 M10500000005-05J0000-00510 의결과가운데하나입니다. * 한국과학기술원전자전산학과 (khg@sejong.kaist.ac.kr, i.song@ieee.org, tahn@sejong.kaist.ac.kr) ** 경희대학교전자정보학부 (yheekim@khu.ac.kr) 논문번호 :KICS2006-09-374, 접수일자 :2006 년 9 월 5 일, 최종논문접수일자 :2007 년 1 월 2 일 34
논문 / 여러입력여러출력시스템에알맞도록너비를먼저탐색하는가장비슷함복호방식 보다중요하다. 이제까지여러논문에서여러입력여러출력시스템에알맞은효율적인검파기들을연구하였다 [3, 4]. 이론적으로, 가장비슷함기준을따라신호를검파하면비트오류율 (bit error rate) 성능이가장뛰어나다. 이때, 모든가능성을다살펴보는 (full-search: 줄여서, 모가살 ) 복호기를써서신호를가장비슷함검파하면안테나나별자리신호수가많은시스템에서는계산량이너무많다. 보기를들어, 송신 수신안테나를 4개씩쓰고 16진직교진폭변조하여 (quadrature amplitude modulation: QAM) 신호를보낼때, 모가살복호기로신호를검파하려면 번곱셈해야한다. 이에, 모가살복호기보다간단한여러검파기들이제안되었다. 영만들기결정되먹임등화 (zero forcing decision feedback equalization: 줄여서, 영결되 ) 검파기는모가살복호기보다계산량이적지만비트오류율성능이많이떨어진다 [5]. 영결되검파기보다비트오류율성능이좋은검파기들이많이제안되었지만 [6, 7], 이들은여전히비트오류율관점에서최적이아니다. 한편, 공복호기는 (sphere decoder) 가장비슷함검파를초공간에숨어있는격자점들을찾는문제로바꾸어풀이를찾는방식이다 [8-10]. 공복호기는비트오류율이최적이고모가살복호기보다평균계산량이적다. 다만, 공복호기에서는신호대잡음비를추정해처음문턱값을얻는데, 처음얻은문턱값이가장비슷함풀이의유클리드거리보다아주크면계산량이매우많이늘어나고, 처음얻은문턱값이가장비슷함풀이의유클리드거리보다작아복호를실패하면, 더큰문턱값을써서처음부터다시복호를시작하거나지움을선언한다. 공복호기가지움을선언하면공복호기의비트오류율은최적이아니다. 이논문에서는, 너비를먼저탐색하는방법으로 [11] 초공간에숨어있는격자점들을찾아가장비슷함풀이를얻는신호복호기를제안한다. 제안한복호기는신호대잡음비를추정하지않고, 비트오류율이최적이며, 공복호기보다계산량이적다. 더욱이, 비트오류율성능에서조금손해를보기로하면, 알고리즘을조금고쳐계산량을훨씬더줄일수도있다. Ⅱ. 시스템모형 송신기에서는데이터를 개로나누고데이터마다부호를입힌다음직교진폭변조한신호를무선 채널로보내며, 수신안테나 개에서는이들신호의조합을받는다. 이때, 송신기마다같은수의별자리를써서직교진폭변조한다고둔다. 이제, 보낸복소신호벡터 는아래와같이나타 낼수있다. (1) 여기서, 윗첨자 는벡터전치를나타내고벡터 의째원소 는째송신기에서직교진폭변조한신호를나타낸다. 그러면, 받은신호벡터 를아래와같이쓸수있다. 여기서, (2) 는평균이 이고, 분산이 이며, 서로독립이고, 분포가같은복소정규잡음 개가이루는벡터이고, 벡터 의째원소 는 째수신안테나에서받은신호이며, (3) 은크기가 인채널전달행렬이다. 행렬 의원소 는째송신안테나와째수신안테나사이의복소채널전달계수를나타낸다. 이논문에서수신기는 의모든원소를알고있다고둔다. 받은신호벡터 (2) 는복소수꼴인데, 이를실수꼴로쓰면아래와같다. 여기서, (4) (5) (6) (7) 35
한국통신학회논문지 07-1, Vol. 32, No. 1C 그리고 (8) 신호벡터 에서 (10) 을바로계산하면효율이떨어진다. 이에, 효율적으로가장비슷함풀이 을찾도록 (10) 의모양을바꾸면아래와같다 [8]. 이다. 한편, 과 은각각실수와허수부분을나타내고,,, 는 행렬이다. 식 (7) 에서, 차원벡터는신호집합 의 원소인데, 보기를들어, 4진직교진폭변조하여신호를보낸다면 이고 16진직교진폭변조하여신호를보낸다면 이다. 시스템모형 (4) 에서, 가주어졌을때의확률 밀도함수 는아래와같다. (9) 여기서, 는채널행렬 의째행째열의원소이다. 한편, 가장비슷함기준을써서신호를검파하면, (9) 에서 (10) 을가장작게하는벡터 를찾아야한다. 여기서, 은유클리드거리이다. 따라서, 시스템모형 (4) 에서최적풀이는아래와같이나타낼수있다. (11) 이논문에서는 이라 ( 곧, 이라 ) 두지만, 이논문에서얻은결과들을바탕으로 인때의결과도쉽게얻을수있다. Ⅲ. 제안한복호기 3.1 제안한복호알고리즘 검파기의비트오류율성능을가장좋게하려면 (9)-(11) 에서본바와같이가장비슷함풀이 를찾아야한다. 이를이제, (11) 을바탕으로가장비슷함풀이 을찾으려할때모든 (12) 여기서, 행렬 와 은 를 분해하여얻은것으로서, 와 를만족시킨다. 한편, 이고 (13) (14) 이다. 식 (13) 에서, 차원정규잡음벡터 의원소들은서로독립이고분포가같다. 이제, (12) 와 (13) 을바탕으로 (11) 을아래와같이다시쓸수있다. (15) 한편, 가장비슷함거리 는아래와같이뜻매김한다. (16) 여기서, 는 의째행째열의원소이다. 3.2 복호알고리즘이제, 성능이가장좋으면서공복호기보다계산량이적은새로운방식을생각해보자. 이해하기쉽도록, 나무얼개를써서신호벡터를나타내고이를바탕으로제안한방식을설명하고자한다. 먼저, 뿌리에서시작하고 층으로이루어진 진나무얼개를생각하자. 여기서, 는집합 의원소의개수이다. 이나무얼개에서째층의째마디가나타내는벡 터를 라하자. 여기서, 이고 이다. 그러면, 신호벡터 은이나무얼개맨아래층의째마디에해 36
논문 / 여러입력여러출력시스템에알맞도록너비를먼저탐색하는가장비슷함복호방식 당하는벡터 로나타낼수있다. 이제, 차원벡터 의마디거리 을아래와같이뜻매김하자. (17) 그러면, 째층의째마디에해당하는벡터 의 마디거리는 이고, 이는 (16) 의오른쪽 항가운데에서가장오른쪽부터 개더한꼴이다. 식 (14) 를살펴보면, 을이루는신호성분은신 호들 가운데 뿐이다. 곧, 다른신호들의간섭이없는 을써서 을먼저복호하는것이가장바람직하다. 이제, 째층의모든마디거리를계산한다음 보다마디거리가큰마디를모두버린다. 여기서, 은 을만족시키는수이다. 버린마디들과그마디들에서뻗은마디들은더이상생각하지않는다. 다음에, 째층에서살아남은 ( 버리지않은 ) 마디들에서뻗은 째층의모든마디의마디거리를계산하고, 보다마디거리가큰마디를모두버린다. 여기서, 은 을만족시키는수이다. 이런과정을되풀이하여맨아래층에서 ( 첫째층 ) 마디거리가가장작은마디를찾으면복호과정이끝난다. 맨아래층에서마디거리가가장작은마디가나타내는벡터가바로가장비슷함풀이 이다. 여기서, 가작을수록마디를더많이버릴수있으며, 이는계산량이득이더큼을뜻한다. 한 편, 제안한방식에서는 를얻을때 분해를쓰는잘알려진검파방법들가운데계산량이가장적은결정되먹임등화방법을쓴다. 결정되먹임등화풀이와결정되먹임등화거리를각각 와 이라두고, 째층에서살아남은마디들에서뻗은째층의마디들가운데마디거리가째로작은마디에해당하는 벡터를 는아래와같이얻을수있다. 라두자. 그러면, (18) 여기서, 이고 은 와 을나란히놓아만든것으로아래와같다. (19) 여기서, 와 는가장비슷함거리 보다언제나 크거나같으므로, 는아래를만족시킨다는것을눈여겨볼만하다. (20) 제안한방식에서는복호실패가일어나지않으며, 버린마디에는결코가장비슷함풀이가들어있지않음을 (20) 에서알수있다. 한편, (18) 에서 를계산하는데 드는계산량도꽤많다. 이에, 검사벡터 를써서 의계산량 을줄인다. 처음에는검사벡터를 으로두고, 일때에는를 로바꾼다. 구 체적으로는, (18) 의 을계산하기에앞서 서 와 을견주어보고 와 이같으면 이므 로 을계산하지않는다 : 이는 을계산하는데드는연산을줄일 수있음을뜻한다. 한편, 와 이다 르면 을계산한다음 (18) 을써서을 얻는다. 표 1은제안한방식의알고리즘을정리한것이다. 표 1에보인알고리즘에서, 둘째단계의 2-2와 2-3 을좀더자세히설명하면다음과같다. 앞에서말한대로살아남은마디들만생각하여, 째층에서살아남은마디수를 이라하고, 이라두자. 한 편, 집합 은집합 과같다. 보기를들어,,,,, 그리고 일때, 집합 는순서만조금 다를뿐집합 와같다. 그러면, 이고 일때 37
한국통신학회논문지 07-1, Vol. 32, No. 1C 표 1. 제안한방식의알고리즘 (21) 첫째단계입력 (,, ). 1-1. 행렬 를 분해한뒤 를계산한다. 1-2. 결정되먹임등화방법을써서 을얻고 을계산한다. 을계산하면째층의마디거리 을얻 을수있다. 여기서, 고,, 그리 (22) 이다. 식 (21) 에서, 는이미 째층에서 얻었으므로째층에서마디거리를얻으려면 와 만계산하면된다. 한편, 계산량을더욱줄이고자 를다음과 같이계산한다. 먼저, (22) 를다시쓰면아래와같다. 여기서, 이고 (23) 이라둔다. 이제, 일때부터 를얻는데, (23) 의둘째항을 계산하기에앞서서 와 을견주어본다 : 이면 가다를때에만 을계산하지않는다. 곧, 이므로 와 을계산하여 계산량을줄일수있다. 식 (21) 은공복호기에서도쓰지만 (23) 을써서계산량을줄이는방법은제안한방식에서만쓸수있음을새겨두자 : 공복호기에서는깊이를먼저탐색하기때문에 (23) 을써서계산량을줄이기에는매우까다롭다. 그림 1은 이고 일때, 제안한방식을쓴복호과정을보여준다. 제안한방식에서는마디마다마디거리를많아야한번계산하고, 마디거리를계산할때에도이웃벡 터를 ( 보기를들면, (23) 에서벡터 과짝을이루 는벡터 ) 써서계산량을줄인다. 한편, 공복호기에서는깊이를먼저탐색하므로한마디를여러번탐색할때도있고, 따라서, 살아남은마디마다마디거리를적어도한번계산한다. 공복호기에서도마디마다마디거리를한번만계산할수있으나, 그 출력 (,,, ). 둘째단계 입력 (,,,, ). 2-1. 먼저,, 그리고 으로둔다. 2-2. 째층에서모든마디들의마디거리를 계산하고 을얻은다음 2-4로간다. 2-3. 째층에서살아남은마디들에서뻗은째층의모든마디들의마디거리를계산하고 을얻는다. 이면 2-4로가고, 이면 2-7로간다. 2-4. 이면, 로두고 2-6으로간다. 이면, 2-5로간다. 2-5. 을계산한다. 이면, 로두고 2-6으로간다. 이면, 그리고 로두고 2-6으로간다. 2-6. 마디거리가보다큰마디들을모두버리고, 을하나줄인다음 2-3으로간다. 2-7. 복호를끝낸다. 출력 ( ) 렇게하려면계산했던모든마디거리를복호가끝날때까지저장해두어야한다. 그림 1. 제안한방식의복호과정 ( ) 38
논문 / 여러입력여러출력시스템에알맞도록너비를먼저탐색하는가장비슷함복호방식 4.1 계산량분석 Ⅳ. 성능평가 곱셈횟수는복호기의계산량을견주는데많이쓰인다. 이제, 제안한방식과다른복호기들이가장비슷함풀이를찾는데 ( 복호하는데 ) 드는곱셈횟수를견주어보자. 표 1에보인알고리즘의첫째단계에서 를 분해하는데 번쯤 [12], 를계산하는 데 번, 을얻는데 번곱셈하고, 을얻는데 번나눗셈한다. 곱셈과나눗셈의계산량이같다고두면, 첫째단계에서는아래만큼곱셈한다. (24) 이제, 둘째단계에서 과을계산하는데드는곱셈횟수를각각 과 로두면, 이고 이며, 째층에서계산을하는데드는곱셈횟수를아래와같이쓸수있다. (25) 따라서, 둘째단계에서는아래만큼곱셈한다. (26) 식 (26) 에서,,, 그리고 은신호대잡음비 (signal to noise ratio: SNR), 신호별자리크기, 그리고송신 / 수신안테나수의영향을받으며아래를만족시킨다. 그리고 (27) (28) (29) 식 (26)-(29) 을바탕으로둘째단계에서가장많이계산할때와가장적게계산할때드는곱셈횟수를얻으면각각아래와같다. (30) (31) 곧, 제안한방식은가장비슷함풀이를찾을때, 많으면 (24) 와 (30) 을더한만큼, 적으면 (24) 와 (31) 를더한만큼곱셈한다. 4.2 모의실험 이제, 몬테카를로방법으로 번모의실험하여얻은평균곱셈횟수를바탕으로제안한방식과공복호기의계산량을견주어보자. 또한, 제안한방식, 모가살복호기, 그리고공복호기의비트오류율성능도견주어보자. 모의실험에서, 신호대잡음비는 전송신호전력 으로두었으며, 모든결과는 번거듭실험하여얻었다. 한편, 공복호기에서, 처음얻은문턱값이가장비슷함거리보다작아복호할수없을때에는문턱값을두배로하여다시복호를시작하였다. 그림 2 는제안한방식과공복호기가복호과정을 번되풀이하는동안얻은곱셈횟수들을오름차순으로세운것이다. 이그림에서점 는째로적은곱셈횟수가임을나타내며, 결정- 공복호기는공복호기의처음문턱값을결정되먹임등화방법을써서얻었음을나타낸다. 이그림에서제안한방식은결정-공복호기보다더적게계산할것임을알수있다. 그림 3은제안한방식과결정 -공복호기의곱셈횟수를가장나쁠때와가장좋을때로나누어보여준다. 결정- 공복호기에서이론적으로가장나쁠때의곱셈횟수를얻기는매우어렵지만, 가장좋을때의곱셈횟수는이론적으로 쯤이다. 이론과모의실험에서얻은가장좋을때의곱셈횟수와가장나쁠때의곱셈횟수모두제안한방식이결정 -공복호기보다적다. 그림 4는제안한방식, 결정- 공복호기, 그리고추정-공복호기의평균곱셈횟수를보여준다. 여기서, 추정- 공복호기는신호대잡음비를추정하여처음문턱값을얻은공복호기를뜻한다. 이때, 수신기가신호대잡음비를제대로추정하였다고두었고, 가장비슷함거리가문턱값보다작을확률이 가되도 39
한국통신학회논문지 07-1, Vol. 32, No. 1C 그림 2. 제안한방식과결정 - 공복호기의곱셈횟수분포 (, 진직교진폭변조 ) 그림 4. 제안한방식과공복호기의평균곱셈횟수 ( ) 그림 3. 제안한방식과결정 - 공복호기의이론적인곱셈횟수모의실험에서얻은곱셈횟수 (, 진직교진폭변조 ) 록처음문턱값을잡았다. 이그림에서제안한방식은공복호기보다평균적으로적게계산함을알수있다. 게다가, 추정-공복호기에서신호대잡음비를추정하는데드는곱셈횟수는생각하지않았음에도, 제안한방식의평균곱셈횟수가추정- 공복호기의평균곱셈횟수의 밖에되지않음을새겨두자. 한편, 신호대잡음비가낮아질수록제안한방식과공복호기의평균곱셈횟수차가점점더커진 그림 5. 제안한방식, 모가살복호기, 공복호기의성능특성다. 그림 5는제안한방식, 모가살복호기, 그리고공복호기의비트오류율성능을보여준다. 복호기모두가장비슷함기준을따라풀이를찾으므로, 비트오류율성능이같음을알수있다. Ⅴ. 맺음말이논문에서는여러입력여러출력통신시스템에서비트오류율은최적이고공복호기보다계산량 40
논문 / 여러입력여러출력시스템에알맞도록너비를먼저탐색하는가장비슷함복호방식 이적은새로운복호기를제안하였다. 제안한방식은너비를먼저탐색하여얻는정보를바탕으로복호하는데드는계산량을줄였을뿐만아니라신호대잡음비도추정하지않는다. 모의실험으로제안한방식은비트오류율성능이최적이고공복호기보다더적게계산함을보았다. 아울러, 신호대잡음비가낮아질수록제안한방식의계산량이득이더높아짐을보았다. Lett., vol. 4, no. 5, pp. 161-163, May 2000. [10] B. Hochwald and S. ten Brink, Achieving near capacity on a multiple antenna channel, IEEE Tr. Comm., vol. 51, no. 3, pp. 389-399, Mar. 2003. [11] D. W. Patterson, Introduction to Artificial Intelligence and Expert Systems, Prentice Hall, 1990. [12] G. H. Golub and C. F. Van Loan, Matrix Computations, Johns Hopkins University Press, 1996. 참고문헌 [1] G. J. Foschini and M. J. Gans, On limits of wireless communications in a fading environment when using multiple antennas, Wireless Pers. Comm., vol. 6, no. 3, pp. 311-335, Mar. 1998. [2] G. D. Golden, G. J. Foschini, R. A. Valenzuela, and P. W. Wolniansky, Detection algorithm and initial laboratory results using the V-BLAST space-time communication architecture, Electron. Lett., vol. 35, no. 1, pp. 14-15, Jan. 1999. [3] G. J. Foschini, G. D. Golden, R. A. Valenzuela, and P. W. Wolniansky, Simplified processing for high spectral efficiency wireless communication employing multi-element arrays, IEEE J. Sel. Area. Comm., vol. 17, no. 11, pp. 1841-1852, Nov. 1999. [4] 황현철, 신승훈, 이철진, 곽경섭, 시공간블록부호화를적용한공간다중화시스템수신기 : 복잡도감소방안, 한국통신학회논문지, 29권, 11호, 1244-1252쪽, 2004년 11월. [5] C. Shen, H. Zhuang, L. Dai, and S. Zhou, Detection algorithm improving V-BLAST performance over error propagation, Electron. Lett., vol. 39, no. 13, pp. 1007-1008, June 2003. [6] S. W. Kim and K. P. Kim, Log-likelihood-ratio -based detection ordering in V-BLAST, IEEE Tr. Comm., vol. 54, no. 2, pp. 302-307, Feb. 2006. [7] 오종호, 안태훈, 송익호, 박주호, 박소령, 감쇄환경에서여러입력여러출력시스템에알맞은혼합검파방식, 한국통신학회논문지, 31권, 9호, 897-904쪽, 2006년 9월. [8] E. Viterbo and J. Boutros, A universal lattice code decoder for fading channels, IEEE Tr. Inform. Theory, vol. 45, no. 5, pp. 1639-1642, July 1999. [9] O. Damen, A. Chkeif, and J. C. Belfiore, Lattice code decoder for space-time codes, IEEE Comm. 강현구 (Hyun Gu Kang) 준회원 2004년 8월고려대학교전자및정보공학부공학사 2006년 8월한국과학기술원전자전산학과공학석사 2006년 9월 ~ 현재한국과학기술원전자전산학과박사과정 < 관심분야 > 이동통신, 정보이론, 검파와추정송익호 (Iickho Song) 종신회원 1982년 2월, 1984년 2월서울대학교전자공학과공학사 ( 준최우등 ), 공학석사 1985년 8월, 1987년 5월펜실베니아대학교전기공학과공학석사, 공학박사 1987년 3월 ~1988년 2월벨통신연구소연구원 1988년 3월 ~ 현재한국과학기술원전자전산학과조교수, 부교수, 교수 1995년 1월 ~ 현재한국통신학회논문지편집위원대한전자공학회, 한국음향학회, 한국통신학회평생회원, IET 석학회원, IEEE 준석학회원 < 관심분야 > 통계학적신호처리와통신이론, 신호검파와추정, 이동통신안태훈 (Taehun An) 준회원 2006년 2월성균관대학교정보통신공학부공학사 2006년 3월 ~ 현재한국과학기술원전자전산학과석사과정 < 관심분야 > 이동통신, 검파와추정 41
한국통신학회논문지 07-1, Vol. 32, No. 1C 김윤희 (Yun Hee Kim) 종신회원 1995년 2월한국과학기술원전기및전자공학과공학사 1997년 2월한국과학기술원전기및전자공학과공학석사 2000년 1월 ~2000년 4월 UCSD 방문연구원 2000년 8월한국과학기술원전자전산학과박사 2000년 9월 ~2004년 8월한국전자통신연구원선임연구원 2004년 9월 ~ 현재경희대학교전자정보학부조교수 2006년 1월 ~ 현재한국통신학회논문지편집위원 IEEE 준석학회원 < 관심분야 > 이동 / 무선통신, 통계학적신호처리와통신이론, 부호화변조, 적응전송 42