논문 11-36-01-06 한국통신학회논문지 '11-01 Vol.36 No.1 깊이우선과너비우선탐색기법의결합과트리분할을이용한다중입출력신호를위한새로운최우도복호기법 준회원이명수 *, 정회원이영포 *, 종신회원송익호 **, 윤석호 * A Novel Decoding Scheme for MIMO Signals Using Combined Depth- and Breadth-First Search and Tree Partitioning Myungsoo Lee* Associate Member, Youngpo Lee* Regular Member, Iickho Song**, Seokho Yoon* Lifelong Members 요 약 본논문에서는다중입출력 (multiple-input multiple-output: MIMO) 시스템을위한깊이우선탐색과 (depth-first search) 너비우선탐색의 (breadth-first search) 혼용을바탕으로한복호기법을제안한다. 제안된기법은먼저탐색트리를여러단계로나눈뒤, 깊이우선탐색과너비우선탐색기법모두의장점을이끌어낼수있도록두기법의유기적인적용을통하여각단계를탐색한다. 또한, 성능평가를통해두탐색기법이적절히적용되었을때, 기존의복호기법들보다상당히낮은연산복잡도를갖는것을확인할수있다. Key Words : ML decoder, depth-first search, breadth-first search, partitioned tree ABSTRACT In this paper, we propose a novel ML decoding scheme based on the combination of depth- and breadth-first search methods on a partitioned tree for multiple input multiple output systems. The proposed scheme first partitions the searching tree into several stages, each of which is then searched by a depth- or breadth-first search method, possibly exploiting the advantages of both the depth- and breadth-first search methods in an organized way. Numerical results indicate that, when the depth- and breadth-first search algorithms are adopted appropriately, the proposed scheme exhibits substantially lower computational complexity than conventional ML decoders while maintaining the ML bit error performance. Ⅰ. 서론 다중 입출력 (multiple-input multiple-output: MIMO) 시스템은 단일 입출력 (single-input single-output) 시스템에비해좋은대역효율을갖는 다 [1]. MIMO 시스템은주파수대역의초과사용없이용량을증가시킬수있다는장점으로차세대통신시스템에이용될핵심기술중하나로서각광받고있다 [2]. 특히 MIMO 시스템의대역효율은공간다중화와사용된안테나수의증가에따라결정된다는장점이있 이논문은 2010 년도정부 ( 교육과학기술부 ) 의재원으로한국연구재단의지원을받아수행된연구 (No.2010-0014610, No.2010-0015786) 와지식경제부및정보통신산업진흥원의대학 IT 연구센터지원사업 (NIPA-2010-C1090-1011-0005) 의연구결과로수행되었음. * 성균관대학교정보통신공학부 (syoon@skku.edu), ( : 교신저자 ), ** 한국과학기술원전기및전자공학과논문번호 : KICS2010-11-522, 접수일자 : 2010 년 11 월 2 일, 최종논문접수일자 : 2010 년 12 월 21 일 37
한국통신학회논문지 '11-01 Vol.36 No.1 다. 하지만이러한장점이있는반면에송신안테나사이의간섭이증가함에따라수신기측면에서복호를위한연산량이늘어나는것은피치못할손실이다. 연산효율이좋은 MIMO 복호기를설계함에있어서의문제점은기존의여러연구에서언급되고있다 [3-8]. 연산효율이좋은복호기의대표적인예로는 zeroforcing, nulling and cancelling, 그리고최적순서화기법을기반으로한 nulling and cancelling과같은준최적복호기들이있다 [1],[9]. 하지만최적비트에러율 (bit error rate: BER) 성능을갖지못하는준최적복호기들은적은연산량에도불구하고 MIMO 시스템고유의장점을온전히이끌어내지못하는단점을갖는다. 이론적으로최우도복호기는 MIMO 시스템에서최적의 BER 성능을갖는다. 트리의모든격자점을검사하는전체탐색최우도복호기는안테나의수, 신호성좌도의크기증가에따라그연산복잡도가급격히증가한다. 따라서최적의 BER 성능을유지하되, 연산복잡도를낮추기위하여구복호 (sphere decoder: SD) 기법이제안되었다 [10-12]. SD 기법은수신신호점을중심에둔다차원의구안에놓여있는격자점들만을탐색하는기법으로연산의복잡도를줄인다는장점이있다. 특히, 신호대잡음비 (signal to noise ratio: SNR) 값이크고, 안테나의수가적은경우에 SD 기법의연산복잡도는준최적복호기의연산복잡도와비슷한정도로나타난다 [13]. 하지만안테나수가증가하거나 SNR 값이작다면, 연산복잡도는크게높아진다는단점이있다 [14]. 다음으로, 너비우선탐색기법에기초하여가장가까운위치의격자점부터탐색하는너비우선탐색복호기가 (breadth-first signal decoder: BSIDE) 제안되었고, 이는최적 BER 성능을가지며, SD 기법에비해더낮은연산복잡도를가진다 [15]. 그러나이역시도신호성좌도가클경우연산복잡도가높아지는단점이있다. 본논문에서는트리를여러단계로나눈뒤, 각단계에깊이우선탐색과너비우선탐색을적절히적용하여최적화를달성하는분할기반혼합복호기법이라는 (partition-based hybrid decoding: PHD) 새로운최우도복호기법을제안한다. 마지막단계를제외한각단계의마지막층에서최우도솔루션을위한노드후보들을추려내고, 마지막단계에서는그후보들중더가능성있는것을먼저검사하는기법을통해 PHD 는연산복잡도를줄인다. PHD의복잡도에대한이득은 SNR이작고안테나수가많을때더확연하게나타난다. 본논문의구성은다음과같다. Ⅱ장에서는본논문에서가정된 MIMO 시스템모델에대해설명한다. Ⅲ 장에서는 PHD의내용을자세히설명한다. 그리고 Ⅳ 장에서는 BSIDE, PHD 그리고 SD의연산복잡도와 BER 성능을비교한다. 마지막으로 Ⅴ장에서는결론을내린다. Ⅱ. 시스템모델 본논문에서는그림 1에서와같이 개의송신안테나와 개의수신안테나로구성된 MIMO 시스템을고려한다. 송신측에서입력데이터스트림은 개의서브스트림으로나누어지고, 각각은특정전송안테나를통해전송된다. 이때채널은한전송주기동안상수값을갖고, 그전송이끝나면그값이변하는정적레일레이페이딩채널로 (flat Rayleigh fading channel) 가정한다. 기저대역복소수신신호 은다 음과같이표현될수있다. (1) 여기서 는 의복소채널전송행렬이고, 는 인복소전송신호벡터이다. 그리고 은 인복소부가 잡음벡터이다. 여기서사용된 는전치행렬을의미 한다. 복소채널전송행렬 의각성분 는평균 값 0과분산 1을갖는독립동일분포의 (independent and identically distributed: i.i.d.) 가우시안랜덤변수 이며, 복소채널전송계수 는수신기에서의복 호과정이전에완벽하게추정되었다고가정한다. 부 가잡음성분 는평균 0 과차원당분산을 로 갖는 i.i.d. 복소가우시안랜덤변수이다. 전송된복소 그림 1. 개의송신안테나와 개의수신안테나를갖는 MIMO 시스템의예. 38
논문 / 깊이우선과너비우선탐색기법의결합과트리분할을이용한다중입출력신호를위한새로운최우도복호기법 신호 는 - 직교진폭변조의 ( -quadrature amplitude modulation: -QAM) 성좌도로부터도출된다고가정한다. 여기서 은 2의제곱의형태이다. PHD의설명을쉽게하기위해, 식 (1) 에서의복소행렬과벡터들을실수형태로변형하기위해, 로설정해준다. 그러면, 식 (1) 로부터다음과같은식을얻을수있다. (2) 여기서 은수 신신호벡터를의미하고, 는채널전송행렬 의실수표현으로서다음과같이나타낼수있다. (3) 는실수영역 에서의전송된신호벡터이고, 는잡음벡터이다. 여기서 과 은각각실수와허수성분을나타낸다. 가 -QAM의성좌도로부터도출되므로 으로나 타낼수있으며, 은다음과같다. (4) 일때, 채널전송행렬 에 행렬분해를수행함으로써, 식 (2) 를다음과같이분해하여나타낼수있다 [16]. (5) 는 인 unitary 행렬이고, 는 인상삼각행렬이다. 그리고 은 인영행렬이다. 를식 (5) 의각항왼쪽에곱해줌으로써, 다음과같은식을얻을수있다. 여기서,, 그리고 이다. 만이전송된신호 에관련이있다. 전송된신호벡터 의최우도복호를구하기위해, 주어진수신신호벡터 과채널전송행렬 를이용 하여 과 사이의거리를구해보면다음과같이표 현된다. (7) 여기서 이므로, 는유클리드평면상의거리를의미한다. 식 (6) 에서보였듯이, 가 에대해독립적이기때문에, 최우도솔루션 는다음과같이표현된다. (8) 반면에, 이면, 채널전송행렬 를먼저 으로나누어준다. 이때, 은 행렬이고, 는 행렬이다. 에 행렬분해를수행하면다음과같이표현된다 [16].. (9) 식 (2) 로부터, 는 의직교행렬이고, 는 의상삼각행렬이다. 식 (9) 의양쪽항의왼쪽에 를곱해주게되면,, 이고, 인 를얻게된다. 최 우도솔루션 를찾기위해먼저 를고정하고 를최소화하는 을탐색한 다. 그리고이과정은 인모든 의선택에 대해반복한다. 여기서최우도솔루션 는다음과같 이나타난다. (6) (10) 39
한국통신학회논문지 '11-01 Vol.36 No.1 본논문에서는단순화를위해 으로가정하지만, 본논문의모든결과는 의경우에도마찬가지로적용될수있다. Ⅲ. 제안된복호기법 3.1 예비연구 PHD 기법에서는다른기존의기법들과마찬가지로상삼각행렬 을이용하여최우도솔루션 을찾 는트리구조가가정된다. -QAM을이용하는 MIMO 시스템의경우, 하나의뿌리로부터시작되어 개의 층을갖는 -ary 트리가생성 된다. 는트리의뿌리를의미하고,, 일때, 번째층의 번째노드는벡 터 로표현된다. 의 성분 은 로부터도출되었기때문에, 전송 된벡터 는첫번째층의노드 로표현할수있 다. 그림 2 는 이고 일때, 인 트리의예이다. 노드 의매트릭을다음과같이정 의하면다음과같다. (11) 식 (8) 로부터, 최우도복호기법에서트리탐색의 목표는첫번째층에서 들중가장작은 노드매트릭을갖는벡터를찾는것임이명확해진다. 본논문의트리탐색의문맥에서, 기존에사용되는 child 노드, descendant 노드, predecessor 노드, 그리 고서브트리등의용어들은기존의문헌 [17] 에서와같은정의로사용될것이다. 3.2 제안된복호기법제안된 PHD 기법은먼저트리를여러단계로나눈다. 개의층을갖는트리에대해임의의단계 가 개의층을포함하도록 단계로나눌수있다. 여기서,, 이 며, 이다. 번째단계는 그리고 의층으로구 성된다. 그림 2를예로들면, 첫번째, 두번째, 세번째단계는각각 {layer 4}, {layer 3, layer 2}, {layer 1} 으로구성되어있다. 각단계에서는, 깊이혹은너비탐색기법을적용하며, 탐색범위는이전단계에서살아남은노드들을뿌리로하는서브트리들만으로국 한된다. 여기서전체트리의뿌리 은첫번째단 계이전에서살아남은유일한노드로가정된다. 3.2.1 Step 1: 처음 단계들에서최우도솔루션후보를결정하기 Step 1의 개의각단계들에깊이우선혹은너비우선탐색을적용시킴으로써결정된각단계의제일아래층의노드들이다음단계에서서브트리들의뿌리로사용된다. 살아남은노드들은그것들의매트릭 이임계값 과같거나그보다작은 노드들이다. 여기서 는결정재입력등호기의 (decision feedback equalizer: DFE) 솔루션이다. DFE의매트릭 를임계값으로사용하게되면, 행렬분해를이용하는기존의방식들에비해연산의복잡도를낮출수있다는장점이있다. 최우도솔 루션은항상 를만족시키므로, 를사용함으로써 step 1에서탐색이진행되는동안최우도솔루션을폐기하는일 이없어지게된다. 여기서, 은첫번째층에서의최우도솔루션과트리의뿌리사이에서측정된매트릭이다. 이는행렬 과신호성좌도 에의해구성된격자점들중가장가까운격자점과변환된수신신 호 사이의거리의제곱과같은값을갖는다. 번째단계의최하단층에서, 그림 2.,, 이며, 세단계로나누어진트리의예 (12) 40
논문 / 깊이우선과너비우선탐색기법의결합과트리분할을이용한다중입출력신호를위한새로운최우도복호기법 개의노드쌍들의집합과단계의최하단층에서 ( 즉, 층 ) 그들의노드매트릭은 에대해, 깊이혹은너비우선탐색기법을적절히적용시킴으로써구할수있다. 여기서살아남은노드들의숫자 은 이다. 번째단계에서는 에서의 개의노드들을뿌리로하는 개의서브트리들을계속탐색한다. Step 1의한단계에서깊이우선탐색기법을사용할때, 그기법은더아래층으로이동하며노드매트릭이임계값보다작거나같은 child 노드한개만을따라가며탐색한다. 이탐색은가장아래층에도착하거나, 한노드의 child 노드모두를탐색하면서모든 children 노드들이임계값보다크거나같은매트릭만을가진것으로판별될때까지계속된다. 그리고난후, 후진이발생하여적어도한개이상의탐색되지않은 child 노드를가지며, 현재층의관점에서위층들중에서가장낮은위치에있는층인 predecessor 노드까지돌아가게된다. 여기서임계값보다작거나같은매트릭을가진탐색되지않은 child 노드를다시깊이우선탐색기법으로검사하게된다. 이작업은깊이우선탐색기법이모든노드를탐색한후뿌리로되돌아갈때까지계속된다. 반면에너비우선탐색기법이 step 1의한단계에적용될때, 그기법은먼저제일위층의모든노드매트릭들을계산한다. 여기서임계값보다큰매트릭을갖는노드들은제외하게된다. 그리고나서제외되지않은노드들로부터이어진아래층의노드들의매트릭들만이연산되며, 이러한과정은그단계에서가장아래층의매트릭들중, 임계값과비교하여같거나작은매트릭이발견되는동안계속된다. 3.2.2. Step 2: 첫번째층에서가장작은노드매트릭을갖는노드찾기 마지막단계에서, 먼저임계값 을설정하고, 개의노드에서내려온 개의서브트리들을깊이혹은너비우선탐색기법을이용한 BSIDE, 리스트구복호기 (list SD: LSD), 그리고 SD 중하나를선택하여탐색한다. BSIDE, LSD와 SD에관한자세한내용은각각문헌 [15], [12], [11] 에서알수있다. 첫번째층에서가장작은매트릭을갖는노드가최우도솔루션으로선언될것이기때문에, 가급적 단계에서살아남은노드들로부터이어진서브 트리들전부를탐색하지않고최우도솔루션인노드를찾기를바라게된다. 그때문에 PHD는 에서노드들을오름차순으로다음과같이재정렬한후, 개의서브트리들을순서에따라탐색한다. (13) 여기서, 이다. 그와동시에 가능한빨리최우도솔루션을찾을확률을최대로하기위해, PHD는첫번째층에서의어떤노드가현재의임계값보다작은크기의매트릭을가진것이발견될때마다그노드의매트릭을새로운임계값으로재설정해준다. 특히, 재정렬된순서에서의첫번째노드 을뿌 리로가진서브트리로부터시작하여첫번째층에서 의가장작은매트릭을갖는노드를찾는다. 을 뿌리로가진서브트리에대한탐색이끝났을때, 만약 모든 의매트릭 이기존의임계값보다크 다면, 임계값으로설정되었던매트릭을갖는노드가최우도솔루션으로선언되고탐색이종료된다. 이는 의모든 descendant 노드들은그이전까지 탐색된가장작은매트릭을갖는노드의매트릭보다큰값을가질것이라는사실을바탕으로한다. 보다가능성있는서브트리를먼저검사하는과정과임계값을적합하게갱신하는과정은가능한빨리최우도솔루션을찾을가능성을최대화하고결과적으로는가능성이희박한서브트리를불필요하게탐색하는것을방지하여연산의복잡도를줄인다. 실제트리를탐색할때하나의탐색기법만을적용하는기존의복호기법들과는다르게 PHD는 SNR, 안테나수, 그리고신호성좌도크기변화와같이복호환경변수들이달라짐에따라여러단계로나뉜트리의각단계에다양한탐색기법들을적응적으로사용하여탐색한다. 각단계에적합한탐색기법을사용함으로써, PHD는여러탐색기법들의장점을최대한이끌어낼수있고연산복잡도를줄일수있다. 또한트리분할의자연스러운이점으로써, 보다가능성있는서브트리후보들을먼저탐색하고가능한빨리최우도솔루션을찾아탐색과정을종료하는것은결과적으로더욱연산의복잡도를줄이게된다. 41
한국통신학회논문지 '11-01 Vol.36 No.1 Ⅳ. 성능평가 4.1 연산복잡도분석곱셈의횟수는복호기법의연산의복잡도를표현하는데있어널리사용되는유용한지표이다 [18]. 본논문에서도, PHD의연산복잡도를곱셈횟수측면에서분석하였으며, 다른최우도복호기법들의연산복잡도와비교하였다. PHD 기법수행시, 먼저 를 행렬형태로 분해하며,,, 그리고 이연산된다. 행렬분해를위해요구되는곱셈의횟수는대략적으로 이다 [19]., 그리 고 는각각 번의곱셈, 번의곱셈, 그 리고 번의나눗셈을필요로한다 [15]. 여기서나눗셈은곱셈과같은연산복잡도를요구한다고가정할때, 위연산들의총곱셈횟수는다음과같이주어진다. (14) 식 (14) 는 SNR과신호성좌도크기와는무관하게요구되는곱셈의횟수를의미한다. PHD의연산복잡도는 개의단계들에서의총곱셈횟수에식 (14) 를더해줌으로써결정된다. 한단계에서의곱셈횟수는사용된복호기법에따라다르며그단계의문턱값과같거나작은값의매트릭을갖는노드들의수에따라다르다. 문턱값보다작거나같은매트릭을갖는노드들은 SNR에의존하는랜덤변수인채널전송행렬 와수신벡터 에관한함수이므 로, 그노드들또한랜덤변수이다 [13]. 트리를탐색하는복호기법의정확한탐색경로는예측불가능하기때문에곱셈의횟수는전송때마다다를것이다. 결론적으로복호기법의정확한곱셈의횟수를닫힌꼴형태로표현하는것은일반적으로불가능하다. 그러므로본논문에서는다양한기법들의곱셈의횟수는컴퓨터시뮬레이션의많은반복을통한평균으로얻어지고, 비교된다. 4.2 시뮬레이션결과및토의컴퓨터시뮬레이션을이용한 번의모의실험을통해얻은평균곱셈횟수로 BSIDE, PHD, 그리고 SD의연산복잡도를계산하고, 비교한다. 또한 BSIDE, PHD, 그리고 SD이 BER 성능측면에서모두최적이라는점을보여줄것이다. PHD의추가적인 특징은몇가지 MIMO 전송시나리오들에서단계들의구성과곱셈의횟수간의관계로논의될것이다. 모든시뮬레이션에서 SNR은다음과같이정의된다. (15) 여기서 는기대값을의미한다. PHD 구조의구체적인표현에서, PHD 는 개층으로이루어진 번째 ( ) 단계에서탐색기법 가사용되었음을의미한다. 탐색기법 를표현하기위해, BF', BS', LS' 그리고 SD' 가각각너비우선탐색, BSIDE, LSD, 그리고 SD를표현하기위해사용될것이다. 이네가지기법중 BS' 와 SD' 는 PHD의 Step 2 과정에서만사용될수있다. BF' 는 PHD의 Step 1 과정에서만사용될수있고, LS 는 Step 1 과 Step 2 모두에서사용될수있다. 결론적으로 PHD의 Step 1, 2에서는여섯가지의가능한조합이있다. 시뮬레이션에서 LSD와 SD의첫탐색반경을 로설정하고제곱근의연산복잡도는곱셈의연산복잡도와같게가정한다. 4.2.1 각단계에속하는층의개수에따른결과 그림 3-8에서는 이고 일때, 두단계에적용가능한여섯개의탐색기법들의조합에대해두단계에서의층의개수 과 에따라 PHD의연산복잡도가변화하는것을보인다. 분명히, PHD의연산복잡도는특정한형태에의존하고탐색기법들과 2개단계에서각층의개수들의변화에의존한다. 그러나 PHD의다양한형태사이의곱셈횟수의차이는 SNR이증가할수록빠르게감소한다. 다른 값에대해서도유사한결과를얻었지만공간상의이유로본논문에는포함하지않았다. 두단계에서층의숫자를다르게설정하는것이각기다른연산복잡도를갖는결과로나타나지만, 로설정하는것은 PHD의연산복잡도를곱셈의평균횟수로판단함에있어불합리한선택이아니다. 직관적으로, 이클수록첫번째단계에서살아남는노드가더많아질것이고이는두번째단계에서의더많은트리탐색을필요로하게될것이다. 이로인해결과적으로 PHD 기법은더높은복잡도를보이게될것이다. 이와마찬가지로 가크면 42
논문 / 깊이우선과너비우선탐색기법의결합과트리분할을이용한다중입출력신호를위한새로운최우도복호기법 그림 3. 일때, PHD[BF, BS ] 의평균곱셈횟수. 그림 4. 일때, PHD[BF, LS ] 의평균곱셈횟수. 그림 5. 일때, PHD[BF, SD ] 의평균곱셈횟수. 그림 6. 일때, PHD[LS, BS ] 의평균곱셈횟수. 그림 7. 일때, PHD[LS, LS ] 의평균곱셈횟수. 그림 8. 일때, PHD[LS, SD ] 의평균곱셈횟수. 43
한국통신학회논문지 '11-01 Vol.36 No.1 2번째단계에서긴트리들이발생하게되고, 이는더높은복잡도를보이게될것이다. 지금부터트리를같은수의층을갖는두단계로나누는 PHD에초점을맞출것이다. 그러나언급되었다시피, 이외의값으로 값을설정해주는것이상황에따라더좋을수도있다. 4.2.2 다양한복호기법들의복잡도비교결과그림 9는변조차수가 이고, 송신, 수신안테나가 2개인경우 BSIDE, LSD, PHD, 그리고 SD로탐색했을때의 BER 성능을보인것이다. BSIDE, LSD, PHD, 그리고 SD 모두최적의 BER 성능을보인다. 세가지변조기법에서 (4-, 16-, 64-QAM) BSIDE, LSD, PHD, 그리고 SD의평균곱셈횟수는그림 10-12에보였다. 이그림들에서, 대부분의경우 PHD는 LSD와 SD 보다뛰어난성능을보였다. 그리고 이클때, BSIDE 보다뛰어난성능을보였다. 다른기법들과비교해 PHD의연산복잡도에있어서의이득은일반적으로 SNR이작고안테나수가많을때, 더크다는것또한관측되었다. 이러한경향은송신과수신안테나들의수가각각 3개와 4개일때도비슷하게관측되었다. 그림 10. 이고, 일때, BSIDE, LSD, PHD[, ] 그리고 SD 기법들의평균곱셈횟수. 4.2.3 두단계를가진 PHD에서탐색기법선택에따른복잡도비교시뮬레이션결과를기반으로다음과같은점들을생각해볼수있다. 우선두번째단계에서고정된하나의탐색기법만사용할경우첫번째단계에서 BF' 는 그리고 일때, LS' 보다덜복잡한연산복잡도를갖는다 : 일때, 낮은 그림 11. 이고, 일때, BSIDE, LSD, PHD[, ] 그리고 SD 기법들의평균곱셈횟수. 그림 9. 이고, 일때, BSIDE, LSD, PHD[, ] 그리고 SD 기법들의 BER 성능. 그림 12. 이고, 일때, BSIDE, LSD, PHD[, ] 그리고 SD 기법들의평균곱셈횟수. 44
논문 / 깊이우선과너비우선탐색기법의결합과트리분할을이용한다중입출력신호를위한새로운최우도복호기법 SNR에서같은결과를얻을수있다. 하지만 SNR이커질수록 LS' 가낮은연산복잡도를갖게된다. 또한첫번째단계에서탐색기법을하나로고정할때, 두번째단계에서 일때, 탐색기법으로는 BS' 가우선적으로고려될것이고, LS' 는 이커질수록고려될것이다. 이러한탐색기법들에영향을받는 PHD 연산복잡도는깊이우선탐색그리고너비우선탐색알고리즘고유의특징의자연스러운결과이다. 이러한관측들을요약해나타낸결과가표 1 및표 2에나타나있다. 있게하는핵심적인역할을한다. 또한제안된기법은나누는단계의수선택에있어서유연성을가지며, 단계별층의수와탐색기법의선택에있어서도마찬가지로유연성을갖는다. 시뮬레이션결과에서, 제안된기법은기존최우도복호기와비교했을때최적 BER 성능은유지하고, 연산복잡도측면에서는상당히낮은연산복잡도를보인다. 또한제안된기법을적용하였을때, SNR이낮아지거나안테나의수가늘어나는경우에, 연산복잡도측면에서의이득이더욱증가됨을알수있다. 표 1. PHD 의첫번째단계에서우선시되는탐색기법 -QAM 송 수신안테나수 송 수신안테나수 -QAM 4-, 16-QAM 64-QAM BF BF BF BF (SNR < 5dB ) LS (SNR > 5dB ) BF (SNR < 17dB) LS (SNR > 17dB) BF (SNR < 28dB) LS (SNR > 28dB) 표 2. PHD 의두번째단계에서우선시되는탐색기법 ( 와 는각각 가 에비해 우선시된다 와 약간우선시된다 를의미한다 ). 4-QAM 16-QAM 64-QAM BSLSLSBSLSSD SD SD BS BSLSLSSDLSSD SD BS BS BSLSLSSDLSSD SD BS BS Ⅴ. 결론 MIMO 시스템에서의응용을위해, 본논문에서는기존의최우도복호기법들에비해연산복잡도측면에서막대한이득을제공하는 PHD라는새로운최우도복호기법을제안하였다. 제안된복호기법은트리를여러단계로나누고, 각단계에깊이우선탐색기법과너비우선탐색기법을적절히적용하여탐색한다. 제안된복호기법에서트리를여러단계로적절히나누는것은매우중요한역할을수행하며, 이는각단계에여러탐색기법들의장점을최대한끌어낼수 참고문헌 [1] 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-16, Jan. 1999. [2] İ. E. Telater, Capacity of multi-antenna Gaussian channels, European Trans. Telecommun., Vol.10, pp.585-596, Nov./Dec. 1999. [3] H. Artés, D. Seethaler, and F. Hlawatsch, Efficient detection algorithms for MIMO channels: a geometrical approach to approximate ML detection, IEEE Trans. Sig. Process., Vol.51, No.11, pp.2808-2820, Nov. 2003. [4] W. Zhao and G. B. Giannakis, Reduced complexity closest point decoding algorithms for random lattices, IEEE Trans. Wireless Commun., Vol.5, No.1, pp.101-111, Jan. 2006. [5] T. H. Khine, K. Fukawa, and H. Suzuki, Suboptimal algorithm of MLD using gradient signal search in direction of noise enhancement for MIMO channels, IEICE Trans. Commun., Vol.E90-B, No.6, pp.1424-1432, June 2007. [6] J. Li, F. F. Cao, and J. Yang, Low-complexity algorithm for near-optimum detection of V-BLAST systems, IEEE Sig. Process. Lett., Vol.14, No.9, pp.593-596, Sep. 2007. [7] M. O. Damen, K. Abed-Meraim, and S. Burykh, Iterative QR detection for BLAST, Wireless Personal Commun., Vol.19, No.3, pp.179-191, 45
한국통신학회논문지 '11-01 Vol.36 No.1 Dec. 2001. [8] K. Higuchi, H. Kawai, N. Maeda, H Taoka, and M Sawahashi, Experiments on real-time 1-Gb/s packet transmission using MLD-based signal detection in MIMO-OFDM broadband radio access, IEEE J. Sel. Areas Commun., Vol.24, No.6, pp.1141-1153, June 2006. [9] L. Babai, On Lovàsz' lattice reduction and the nearest lattice point problem, Combinatorica, Vol.6, No.1, pp.1-13, Mar. 1986. [10] U. Fincke and M. Pohst, Improved methods for calculating vectors of short length in a lattice, including a complexity analysis, Math. Comp., Vol.44, No.170, pp.463-471, Apr. 1985. [11] E. Viterbo and J. Boutros, A universal lattice code decoder for fading channels, IEEE Trans. Inform. Theory, Vol.45, No.5, pp.1639-1642, July 1999. [12] B. 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. [13] B. Hassibi and H. Vikalo, On the sphere-decoding algorithm I. expected complexity, IEEE Trans. Sig. Process., Vol.53, No.8, pp.2806-2818, Aug. 2005. [14] J. Jalden and B. Ottersten, On the complexity of sphere decoding in digital communications, IEEE Trans. Sig. Process., Vol.53, No.4, pp.1474-1484, Apr. 2005. [15] H. G. Kang, I. Song, J. Oh, J. Lee, and S. Yoon, Breadth-first signal decoder (BSIDE): a novel maximum likelihood scheme for multi-input multi-output systems, IEEE Trans. Vehicle Technol., Vol.57, No.3, pp.1576-1584, Mar. 2008. [16] M. O. Damen, H. E. Gamal, and G. Caire, On maximum-likelihood detection and the search for the closest lattice point, IEEE Trans. Inform. Theory, Vol.49, No.10, pp.2389-2402, Oct. 2003. [17] G. Valiente, Algorithms on Trees and Graphs, Springer, 2002. [18] Z. Guo and P. Nilsson, Algorithm and implementation of the K-best sphere decoding for MIMO detection, IEEE J. Sel. Areas Commun., Vol.24, No.3, pp.491-503, Mar. 2006. [19] G. H. Golub and C. F. Van Loan, Matrix Computations, Johns Hopkins University Press, 1996. 이명수 (Myungsoo Lee) 준회원 2008년 2월성균관대학교정보통신공학부공학사 2009년 3월~현재성균관대학교휴대폰학과석사과정 2009년 12월 IEEE Seoul Section Student Paper Contest 동상수상 2010년 6월한국통신학회추계종합학술발표회우수논문상수상 2010년 12월아이디스전자신문대학 ( 원 ) 생과학기술 &IT 논문공모대제전최우수상수상 < 관심분야 > 통신이론, 이동통신, 통계학적신호처리이영포 (Youngpo Lee) 정회원 2008년 2월성균관대학교정보통신공학부공학사 2010년 2월성균관대학교휴대폰학과공학석사 2010년 3월~현재성균관대학교휴대폰학과박사과정 2008년 11월한국통신학회하계종합학술발표회우수논문상수상 2009년 12월 IEEE Seoul Section Student Paper Contest 대상수상 2010년 1월성균관대학교정보통신공학부우수논문상수상 2010년 12월아이디스전자신문대학 ( 원 ) 생과학기술 &IT 논문공모대제전최우수상, 장려상수상 < 관심분야 > 통신이론, 이동통신, 통계학적신호처리 46
논문 / 깊이우선과너비우선탐색기법의결합과트리분할을이용한다중입출력신호를위한새로운최우도복호기법 송익호 (Iickho Song) 종신회원 1982년 2월서울대학교전자공학과공학사 ( 준최우등 ) 1984년 2월서울대학교전자공학과공학석사 1985년 8월펜실베니아대학교전기공학과공학석사 1987년 5월펜실베니아대학교공학박사 1987년 3월~1988년 2월벨통신연구소연구원 1988년 3월~현재한국과학기술원전기및전자공학과조교수, 부교수, 교수 1995년 1월~현재한국과학기술원논문지편집워원, 편집부위원장대한전자공학회, 한국음향학회, 한국통신학회평생회원, IET 석학회원, IEEE 석학회원 < 관심분야 > 통계학적신호처리, 통신이론, 신호검파와추정, 이동통신 윤석호 (Seokho Yoon) 종신회원 1997년 2월한국과학기술원전자전산학과공학사 ( 최우등 ) 1999년 2월한국과학기술원전자전산학과공학석사 2002년 2월한국과학기술원전자전산학과공학박사 2002년 3월~2002년 6월 MIT 박사후연구원 2002년 7월~2003년 2월하버드대학교박사후연구원 2003년 3월~현재성균관대학교정보통신공학부전임강사, 조교수, 부교수 2000년 2월삼성휴먼테크논문대상동상수상 2007년 Marquis Who's Who in Asia에등재 2007년 IEEE 준석학회원 2008년 Marquis Who's Who in World에등재 2009년한국통신학회 LG 학술상수상 < 관심분야 > 통신이론, 이동통신, 통계학적신호처리 47