논문 08-33-02-03 한국통신학회논문지 '08-02 Vol. 33 No. 2 병렬처리구조터보부호에서라틴방진행렬로구성된충돌방지인터리버 준회원김대선 *, 오현영 **, 종신회원송홍엽 * Collision-free Interleaver Composed of a Latin Square Matrix for Parallel-architecture Turbo Codes Dae-Son Kim*, Hyun-Young Oh** Associate Members, Hong-Yeop Song* Lifelong Member 요 약 병렬처리구조터보부호에서메모리충돌을피하기위한구성인터리버설계가필요하다. 본논문에서는기존에설계된인터리버들과라틴방진행렬로구성된충돌방지인터리버를제안한다. 제안된인터리버는다양한블록길이와다양한병렬처리차수에대하여쉽게최적화할수있다. 제안된인터리버의성능을컴퓨터모의실험을통해검증하였다. Key Words : Turbo codes, Interleaver, Parallel architecture, Collision-free ABSTRACT In the parallel-architecture turbo codes, the constituent interleaver must avoid memory collision. This paper proposes a collision-free interleaver structure composed of a Latin square matrix and pre-designed interleavers. Our proposed interleavers can be easily optimized for various information block sizes and for various degrees of parallelism. Their performances were evaluated by computer simulation. Ⅰ. 서론터보부호의뛰어난오류정정능력으로인해그동안많은연구가수행되어왔으며다양한표준에채택되어지고있다. 터보부호는쉽고빠르게부호화할수있는장점을가지고있으나, 복호기에서는격자 (trellis) 구조에근간하여 BCJR 알고리즘에의해반복복호를실행하기때문에복호지연이라는문제점을가지고있다 [1],[2]. 이러한문제점과관련하여병렬처리구조터보부호는최근채널부호화분야에서가장뜨거운주제중하나이다 [3]-[6]. 병렬처리구조에서전체블록은몇개의부-블록으로나누어지고, 각각부-블록들이독립된프로세서를가지고있어부호화및복호화를동시에진행하게된다. 순환꼬리물림부호화방법을사용하게되면각부-블록을부호화하는과정에서꼬리비트를필요로하지않는다 [3],[4]. 병렬처리복호화과정에서각프로세서는 SISO(soft-input soft-output) 장치에해당한다. 만일두개이상의프로세서가동시에같은하나의메모리에접근하려고한다면충돌이일어나데이터들을한번에읽어들이지못하고추가적인지연이발생하게된다 [5]. 본연구는삼성전자의 "4G wireless system 에관한연구개발 과제의지원에의해이루어졌음 * 연세대학교전기전자공학과부호및정보이론연구실 ({ds.kim, hy.song}@yonsei.ac.kr) ** 삼성전자 (hy.oh@yonsei.ac.kr) 논문번호 :KICS2007-12-536, 접수일자 :2007 년 12 월 5 일최종논문접수일자 : 2008 년 1 월 25 일 161
한국통신학회논문지 '08-02 Vol. 33 No. 2 이러한충돌들을해결하기위하여병렬처리를위한충돌방지인터리버들이설계되어야한다. 2003년시간적치환 (temporal permutation) 과공간적치환 (spatial permutation) 으로이루어진충돌방지인터리버가제안되었다 [6]. 본논문에서는이인터리버를 2D 인터리버라부르겠다. 2004년에는몇가지변수들로정의된충돌방지 ARP (almost regular permutation) 가제안되었다 [7]. 최근에는대수학적인방법을이용하는 QPP (quadratic permutation polynomial) 인터리버등다양한충돌방지인터리버들이제안되어오고있다 [8]. 제안된충돌방지인터리버들은복잡한최적화과정을가지고있다. 통신시스템에서는일반적으로다양한블록크기들을지원하고있으며, 구성터보부호의인터리버또한가능한모든블록크기들에대하여정의되어야한다. 또한블록길이에따라다양한병렬처리수준을바꾸어줘야한다. 본논문은다양한블록길이와병렬처리수준에대하여쉽게최적화할수있는인터리버를제안하고자한다. Ⅱ. 기존의출동방지인터리버본장에서는참고문헌 [6], [7] 그리고 [8] 에서제안된충돌방지인터리버들에대하여살펴보고자한다. 2.1 2D 인터리버 2D 인터리버는시간적치환과공간적치환으로구성되어있다 [6]. 시간적치환은각각의부-블록에있는데이터심벌들을그부-블록내에서섞어주며, 공간적치환은부-블록간에데이터심벌들을섞게된다. 전체블록의길이를, 부-블록들의개수를 이라고하고각각부-블록의길이를 이라하자. 그러면 은 과같다. 심벌인덱스 는시간적인덱스 와공간적인덱스 를사용하여 2차원적배열구조로나타낼수있으며여기서 이고,, 이다. 시간적치환을, 공간적치환을 라하면 2D 인터리버는다음과같이정의된다. (1) 번째로읽혀지는심벌은 번째부-블록의 번째위치에서읽혀지게된다. 병렬처리구 조의터보부호에서충돌을방지하기위해서는, 공간치환 의모든 에대하여 가부-블록들 과일대일대응관계가있어야한다. 2.2 Almost Regular Permutation (ARP) RP는서로소 (relatively prime) 인터리버를기반으로하고주기적인변화패턴을추가하여제안되었다 [7]. ARP는다음수학식과같이정의된다. (2) 여기서 는 와서로소인수이고, 은병렬처리의차수를뜻하고, 와 는 에대해주기가 이면서양의정수로이루어진수열이고, 는초기오프셋이다. 일반적으로 는 또는 의값을가지며, 는 에서부터 사이의값을가진다. ARP는 IEEE 802.16, DVB-RCS, 그리고 DVB-RCT에서채널부호화표준기술로채택되어사용되고있다. 2.3 Quadratic Permutation Polynomial (QPP) 인터리버 QPP 인터리버는대수학적인방법에의해설계된인터리버이다. QPP 인터리버는 Takeshita에의해최대충돌방지인터리버라는것이증명되었다 [8]. 즉설계된 QPP 인터리버는전체블록길이 를나누는모든부블록길이 에대하여충동방지조건을만족한다. QPP 인터리버는수식 (3) 과같이정의된다. (3) 여기서 과 는음이아닌정수이며 QPP 인터리버가되기위한조건은논문 [8] 에나와있다. Ⅲ. 제안한인터리버충돌방지인터리버를정의함에있어공간적치환을행렬형태로정의하면수식 (4) 와같다. (4) 여기서 행렬 는부-블록사이에서의사상을나타낸다. 즉 번째로읽혀지는심벌은 번째부-블록의 번째위치에있는심벌을읽 162
논문 / 병렬처리구조터보부호에서라틴방진행렬로구성된충돌방지인터리버 어오게된다. 메모리의충돌을피하기위해서 의각각의행벡터는서브블록들, 즉 의치환형태여야한다. 시간적치환 로는미리정의된인터리버를사용한다. 최적화과정은사상행렬인 를정하는과정이다. 즉 에대한 개의치환을정하는과정이다. 인터리빙전과후에같은부-블록에속하게되는데이터심벌들의패턴은성능에영향을미치는요인이된다. 만약같은부-블록에속하는심벌들이인터리빙후에도같은부-블록에속하게된다면그심벌들은낮은무게를가지는부호어가되어성능을열화시킬수있으며, 두개의심벌들의경우그사이클이작다면반복복호과정에서정보전달을막아성능열화를가져오게된다. 따라서같은부-블록에속하는심벌들은최대한다른부-블록으로퍼트려야한다. 라틴방진행렬 은서로다른 개의문자로이루어져있으며, 모든행과열은 개의문자의치환형태로이루어져있다 [10]. 행렬을 라틴방진행렬의열방향으로의반복된형태로정의하겠다. 라틴방진행렬로구조화된 행렬을라틴방진인터리버라부르겠다. 라틴방진인터리버는라틴방진행렬의반복되는형태때문에각각의열벡터에중복되는서브블록의인덱스분포가균일하다. 즉최대한같은블록에있는심벌들을다른블록으로흩어뜨릴수있다. 3.1 라틴방진인터리버짧거나중간크기의블록에서는일반적으로 4 정도의병렬처리수준이고려되어진다. 최적화과정의복잡성을줄이기위해축소된 (reduced) 라틴방진구조를이용하면최적화과정이더간단해진다. 즉 의첫번째행을 으로고정시킨다 [10]. 라틴방진의가능한모든경우의수인 576가지있는데축소된라틴방진구조의경우총 24가지밖에존재하지않는다. 라틴방진인터리버는라틴방진행렬로부터설계되므로즉조사해야할라틴방진인터리버의경우의수는 24가지가된다. 더구나그중에서좋은경우를선택하게되면이숫자를더욱더줄일수있다. 행렬의각열벡터는부-블록의치환패턴을의미하며각열벡터에서의패턴의분포는성능에직접적인영향을주게된다. 행렬열벡터의연속적인 2-tuple 패턴의분포를살펴볼수있는데예를들어 의순환적인열방향에따라 의분포를살펴볼수있다. 여기서 이다. 그림 1에 그림 1. (a) 좋은분포와 (b) 나쁜분포를가지는 2-tuple 패턴의분포비교 그림 2. 좋은그룹과나쁜그룹의 FER 성능비교 좋은분포의경우와나쁜분포의경우가나타나있다. 그림 1. (a) 은, 이한번 이두번존재하지만, 그림 1. (b) 는 과 의패턴만이두번씩만존재한다. 따라서그림 1. (a) 가그림 1. (b) 보다더이상적인분포에가깝기때문에더좋은성능을보일거라고예상할수있다. 그림 1. (a) 와같은분포를가지는라틴방진을좋은그룹이라고하고 1. (b) 와같은분포를가지는라틴방진을나쁜그룹이라고하면 24가지의축소된라틴방진중에서 12개의좋은그룹과 12개의나쁜그룹으로분리된다. 이두그룹으로이루어진라틴방진인터리버의 에대한 FER (frame error rate) 성능비교곡선이그림 2에나타나있다. 시간적치환으로는길이 160의 3GPP 표준인터리버를사용했다. 부호화기는 3GPP 표준부호화기로구성컨벌루션부호의발생행렬은 이며, 전체부호율은 이다. 복호알고리듬으로 max log-map을사용하였고최대반복복호횟수를최대 8번으로하고 Genie 정지알고리듬을사용하였다. 즉반복복호과정에서복호된정보비트에오류가없으면복호를중단하였다. 병렬처리수준은 4인경우를고려하였 163
한국통신학회논문지 '08-02 Vol. 33 No. 2 다. 그림 2에서좋은그룹과나쁜그룹의 FER 곡선이길이 640의 3GPP 인터리버의 FER 곡선을기준으로차이가나며, 좋은그룹의인터리버성능들이더좋은성능을가지는것을확인할수있다. 3.2 확장라틴방진인터리버중간크기나긴블록길이에서는 4보다큰, 예를들어 8이나 12와같은병렬처리수준을고려할수있다. 하지만 축소된라틴방진행렬의경우존재하는경우의수는적어도 개가있다 [11]. 그렇기때문에최적화를위해서모든가능한경우의수를고려할수없다. 그대신 라틴방진행렬을 라틴방진행렬로부터확장하여구할것이다. 여기서 이고, 이다. 확장된 라틴방진행렬은다음수식과같다. (5) 여기서,,, 그리고 이다. 수식 4에의해확장된 행렬은각행과열이서로다른 개의심벌의치환형태가되므로라틴방진행렬이된다. 또한 의첫번째행은 값을가지므로축소된형태가된다. 은수식 5를통해 로부터확장되어지며, 총 24가지 의경우의수가존재하므로 또한총 24가지의경우의수가존재하고, 최적화를위해이경우의수들만조사하면된다. 먼저정보블록길이 320과 640에대해서병렬처리수준 이 인경우, 라틴방진인터리버와 ARP를비교하였다. 제안된인터리버에서시간적치환으로각각길이 80, 160의 3GPP 표준의인터리버를사용하였고, 라틴방진인터리버에사용된라틴방진행렬은다음수식 (6) 와같다. FER 10 0 K=320 and 640, L=4, Max.Iter.=8, maxlogmap 10-1 10-2 10-3 10-4 라틴방진 [640] ARP[640] 라틴방진 [320] ARP[320] (6) 12개의좋은그룹의후보들중에서 일때는 가 일때는 가가장좋은성능을보여주었다. ARP의경우 3GPP2 표준화작업에제안된적이있으며그때의인터리버파라미터들은다음과같다 [9]. 그림 3은블록길이가 일때 에대한 FER 성능곡선이다. 다른모의실험환경은 3장에서와동일하다. 일때제안된라틴방진인터리버는 ARP와거의동일한성능을보여주고있다. 일때는라틴방진인터리버와 ARP가약 1.25dB까지는비슷한성능을보여주다가낙수지역 (waterfall region) 에서는 ARP가약간더좋은성능을보여주고있다. 하지만 ARP는오류마루 (error floor) 현상이빨리일어났으며약 2.25dB 이후로는라틴방진인터리버가더좋은성능을보여주고있으며오류마루현상도거의일어나지않고있다. Ⅳ. 모의실험과토의 10-5 10-6 이번장에서는제안한라틴방진인터리버를 ARP 그리고 QPP 인터리버와성능비교및분석할것이다. 10-7 0 0.5 1 1.5 2 2.5 3 E b /N 0 그림 3. 라틴방진인터리버와 ARP 인터리버의성능비교 164
논문 / 병렬처리구조터보부호에서라틴방진행렬로구성된충돌방지인터리버 정보블록길이 1024 에대해서병렬처리수준 이 8인경우, 라틴방진인터리버와 QPP 인터리버를비교하였다. 라틴방진인터리버의시간적치환으로는길이 128의 3GPP 표준인터리버를사용하였고, 라틴방진인터리버에사용된라틴방진행렬은수식 (7) 과같다. FER 10 0 K=1024, L=8, Max.Iter.=8, maxlogmap 10-1 10-2 10-3 10-4 10-5 10-6 라틴방진 [1024] QPP[1024] 10-7 0 0.5 1 1.5 2 2.5 (7) 은 24개의후보들중에서가장좋은성능을보여주었다. QPP 인터리버의파라미터로 은 31이고 는 64이다. 그림 4는그림 3의 경우와비슷한결과를보여주고있다. QPP 인터리버가낙수지역에서약간더좋은성능을보여주고있지만오류마루현상으로인해성능역전이일어난다. 제안된인터리버는오류마루현상을잘억제할수있음을보여주고있다. 표 1은제안된라틴방진인터리버와다른인터 리버들의최적화를위한복잡도의비교를하고있다. ARP의경우 와 가고정되어있다고가정하였고, 에대하여 가 값을가지고다른 에대하여는 1부터 8 사이의값을가진다고가정하였다 [7]. 병렬처리의차수가 인시스템에최적화된 ARP를설계하기위해서고려해야하는경우의수는 이되며, 여기서 는 의 cardinality이다. QPP 인터리버에서는전체블록길이 가 4로나눠지는경우, 은 와서로소인양의정수값이며, 는 를소수의곱의형태로표시할경우그소수들을원소로가지는양의정수값들이다 [8]. 그러므로총 가지의경우의수가존재한다. 제안된라틴방진인터리버는 이 4일때 12가지경우의수를, 8일때는 24가지의경우의수만고려하면된다. 즉블록길이가증가하거나병렬처리의차수가증가하더라고최적화를위한복잡도가크지않으면서도, 성능또한좋은것을알수있다. 제안된방법에서시간적치환으로어떤종류의미리정의된인터리버라도사용가능하다. Ⅴ. 결론본논문은병렬처리구조의터보부호에서충돌방지인터리버를제안하였다. 기존에제안된인터리버를시간적치환으로사용하고사상행렬 를정의함으로써다양한길이의충돌방지인터리버를만들어낼수있다. 라틴방진행렬구조의사상행렬을사용하면 ARP나 QPP 인터리버보다더간단한최적화과정을갖는다. 제안한라틴방진행렬은최적화를위하여블록길이에상관없이병렬처리의차수가 4인경우 12가지의경우를고려하면되고, 차수가 8인경우 24가지의경우를고려하면된다. 더욱이 ARP나 QPP 인터리버와거의같은성능을보여주고있으며오류마루현상이억제가되어높은신호대잡음비에서좋은성능을보여주었다. E b /N 0 그림 4. 라틴방진인터리버와 QPP 인터리버의성능비교 표 1. 여러인터리버의최적화복잡도의비교 라틴방진 12 12 24 ARP 40960 81920 1073741824 QPP 15200 55360 261632 참고문헌 [1] C. Berrou, A. Glavieux and P. Thitimajshima, Near Shannon limit errorcorrecting coding and decoding: turbo-codes, Proc. of IEEE ICC '93, Geneva, pp.1064-1070, May 1993. [2] L. Bahl, J. Cocke, F. Jelinek, and J. Raviv, 165
한국통신학회논문지 '08-02 Vol. 33 No. 2 Optimal decoding of linear codes for minimizing symbol error rate, IEEE Trans. Inf. Theory, Vol.20, pp.284-287, Mar. 1974. [3] J. B. Anderson and M. Hladik, Tailbiting MAP decoders, IEEE J. Select. Areas Commun., Vol.16, pp.297-302, Feb. 1998. [4] C. Weiß, C. Bettstetter, and S. Riedel, Code Construction and Decoding of Parallel Concatenated Tail-Biting Codes, IEEE Trans. Inf. Theory, Vol.47, pp.368-388, Jan. 2001 [5] A. Tarable, S. Benedetto, and G. Montorsi, Mapping interleaving laws to parallel turbo and LDPC decoder architectures, IEEE Trans. Inf. Theory, Vol.50, No.9, pp.2002~2009, Sep. 2004. [6] D. Gnaedig, E. Boutillon, M. J ez equel, V. Gaudet, and P. Gulak, On multiple slice turbo codes, in Proc. 3rd Int. Symp. on Turbo Codes and Related Topics, Brest, France, pp.343-346, Sep. 2003. [7] C. Berrou, S. Kerouedan Y. Saouter, C. Douillard, and M. J ez equel, Designing good permutations for turbo codes: towards a single model, in Proc. Int. Conf. Commun., Paris, France, Vol.1, pp.341-345, Jun. 2004. [8] O. Y. Takeshita, On Maximum Contention-free Interleavers and Permutation Polynomials Over Integer Rings, IEEE Trans. Inf. Theory, Vol.52, No.3, pp.1249-1253, Mar. 2006. [9] 3GPP TSG RAN WG1-43, Enhancement of Rel. 6 Turbo Code, Nov. 2005. [10] Charles J. Colbourn and Jeffrey H. Dinitz, The CRC Handbook of Combinatorial Designs, 2 nd edition, CRC Press, pp.97-110, 1996 [11] Jr. Marshall Hall, Combinatorial Theory, 2 nd edition, John Wiley & Sons, 1996. 김대선 (Dae-Son Kim) 준회원 2001년 2월건국대학교전자공학과졸업 ( 공학사 ) 2003년 2월연세대학교대학원전기전자공학과졸업 ( 공학석사 ) 2006년현재연세대학교대학원전기전자공학과박사과정 < 관심분야 > Error Correcting Codes, Turbo code, LDPC, MC-CDMA, Spread Spectrum Communication Systems 오현영 (Hyun-Young Oh) 준회원 2005년 2월연세대학교전기전자공학과졸업 ( 공학사 ) 2007년 2월연세대학교대학원전기전자공학과졸업 ( 공학석사 ) 2006년현재삼성전자연구원 < 관심분야 > Error Correcting Codes, Turbo code, LDPC 송홍엽 (Hong-Yeop Song) 종신회원 1984년 2월연세대학교전자공학과졸업 ( 공학사 ) 1986년 5월 USC 대학원전자공학과졸업 ( 공학석사 ) 1991년 12월 USC 대학원전자공학과졸업 ( 공학박사 ) 1992년 ~1993년 Post Doc., USC 전자공학과 1994년 ~1995년 8월 Qualcomm Inc., 선임연구원 2002년 3월 ~2003년 2월 University of Waterloo, Canada, 방문연구교수 1995년 9월 ~ 현재연세대학교전기전자공학부교수 < 관심분야 > PN Sequences, Error Correcting Codes, Spread Spectrum Communication Systems, Steam Cipher Systems 166