논문 08-33-02-02 한국통신학회논문지 '08-02 Vol. 33 No. 2 거리분포특성에근거한터보부호의순환조직형컨벌루션부호설계 준회원김대선 *, 종신회원송홍엽 *, 준회원이동학 **, 정회원유재황 ** Design of Recursive Systematic Convolutional Codes for Turbo Codes Based on the Distance Spectrum Properties Dae-Son Kim* Associate Member, Hong-Yeop Song* Lifelong Member, Dong-Hahk Lee** Associate Member, Jaehwang Yu** Regular Member 요 약 본논문에서터보부호의성능을최대화시킬수있도록구성부호의거리분포특성에근거하여구성순환조직형컨벌루션 (RSC : recursive systematic convolutional 부호를설계하는방법을제안한다. 부호율이 1/2인 RSC 부호에대하여컴퓨터로검색하고그결과는표로정리하여제시한다. 찾은부호들의성능은컴퓨터모의실험을통해검증한다. 제안된방법으로설계한부호들은반복복호에따른빠른수렴정도를보여주면서좋은성능을가진다. Key Words : Turbo codes, Effective free distance, Concatenated codes ABSTRACT In this letter, we propose a new design of recursive systematic convolutional (RSC codes based on the distance spectrum properties which can maximize the performance. Good constituent RSC codes of code rate 1/2 are searched by computer and presented in a table. Their performances are shown by computer simulation. New designed codes shows faster convergences according to iterative decoding and good performances. Ⅰ. 서론터보부호화기는두개의 RSC 부호가인터리버를사이에두고병렬로연접되어있으며복호화기는두개의복호기가직렬로연접되어두개의복호기사이에정보를주고받으면서확률적반복복호화알고리즘을이용하며섀넌용량의한계 (Shannon limit 에근접한성능을발휘한다. 터보부호의부호화기구조에서조직 (systematic 형태는 병렬연접시전체부호율을높여주어주파수효율을좋게해주고복호기에서의복호화복잡도또한낮추어준다. 터보부호의순환 (recursive 형태는인터리버의성능을극대화하여터보부호의성능을높이는중요한요소이다 [1], [2]. Benedetto 등은터보부호중구성컨벌루션부호의설계에있어서가장중요한요소가 effective free distance라는것을증명하였으며, 부호율이 1/2인부호들을제시하였다 [3]. Divsalar 등은역시 effective free 본연구는 SK 텔레콤의 "4 세대무선이동네트워크구성을위한핵심기술개발 " 과제의지원에의해이루어졌음 * 연세대학교전기전자공학과부호및정보이론연구실 ({ds.kim, hy.song}@coding.yonsei.ac.kr ** SK 텔레콤 Access 망개발팀논문번호 :KICS2007-07-305, 접수일자 :2007 년 7 월 10 일 155
한국통신학회논문지 '08-02 Vol. 33 No. 2 distance를근간으로여러부호율에대하여확장하여찾은부호들을제시하였다 [4]. Benedetto 등은논문 [5] 에서좀더다양한조건을고려하여설계하는방법을제안하였다. 즉, 가 2부터 6까지순차적으로먼저최대 를가지도록하고그다음최소 를가지도록 를최적화시켜부호를찾는방법을제안하였다. 여기서 는입력부호열의무게가 일때해당부호화기의출력부호열들의무게값중가장작은값이며, 는무게 를가지는서로다른부호열들의개수이다. 중가장작은값을 free distance,, 라고하며입력무게가 2일때즉 가 effective free distance,, 가된다. Benedetto 등은본방법에의해여러부호율에대하여부호들을제시하였으며, 제시된부호들이좋은성능을가지고있다고잘알려져있다. 그외에도터보부호를위한컨벌루션부호의다양한설계방법들이제안되어왔다. 큰메모리크기를가지고있는구성부호들로이루어진터보부호의경우복호과정에서그복호기들이나쁜잉여 a posteriori probability (APP 값을산출함으로인해낮은신호대잡음비에서성능열화가발생한다. 이를위하여논문 [6] 에서는 Big Numerator-Little Denominator (BN-LD 부호를제안하였다. 또한 Jiang등은 BN-LD 부호를이용한시변 (time-varying 터보부호를제안하였다 [7]. 시변컨벌루션부호화기는부호어를발생하는발생다항식 가매시간마다다른형태로바뀌게된다. 시간 일때시변부호화기의발생다항식을 라고하자. 만약모든시간 에대하여 를만족한다면주기 를가진주기시변부호화기라한다. 이면시불변부호화기가된다. 논문 [7] 에서는제안한부호는 를메모리크기가 6인 BN-LD 부호로사용하고 를 maximal free distance (MFD 를가진컨벌루션부호를사용한주기가 2인주기시변터보부호이다. Jiang등은 BN-LD 부호의낮은신호대잡음비에서의수렴특성과 MFD 부호의큰 free distance 특성을결합하고자하였다. Yuan 등은낮은신호대잡음비에서비트오류율을최소화되도록설계하는방법을제안하였는데 optimal distance spectrum (ODS 터보부호라고하였다 [8]. ODS 터보부호는주어진인터리버의크기, 메모리크기, 그리고부호율에대하여가장좋은거리분포특성을가지는구성 RSC 부호로이루어져있다. 표 1. 설계방법에따른구성 RSC 부호화기및거리분포특성 부호 Berrou [1] 4 1 7 1 6 1 Benedetto [3] 4 1 12 1 6 1 TV [7] 6 2 6 1/2 6 1/2 ODS [8] 4 1 6 1 6 1 본논문의 Ⅱ장에서는기존에제안된터보부호를위한구성컨벌루션부호의성능을컴퓨터모의실험을통해알아보고그차이점들을비교해보고자한다. 또한터보부호의좋은구성 RSC 부호를설계하기위한중요한요소들에대하여자세히고찰하고자한다. Ⅲ장에서는새로운설계방법을제안하고부호율 1/2인좋은구성 RSC 부호를제시한후컴퓨터모의실험을통해그부호들의성능을검증하고자한다. 마지막으로 Ⅳ장에서는간단한결론으로본논문을마칠것이다. Ⅱ. Effective free distance와 free distance 본장에서는 effective free distance와 free distance가터보부호에성능에어떤영향을주는지살펴보고자한다. 이전장에서제안한설계방법에따른부호들과그부호들의차이점을고려해보자. 표 1에서는 Berrou가처음제안한부호 [1] 을포함하여설계방법에따른부호들의발생다항식과특성들이나열되어있다. 각부호들의발생다항식은 형태로되어있는데 는귀환연결다항식 (feedback connection polynomial 이고 는출력연결다항식 (feedforward connection polynomial 며, 각연결다항식은오른쪽비트에최소항이오도록 8진수형태로되어있다. 은각부호의메모리크기를나타낸다. 부호들의비트오류율과프레임오류율이그림 1에나와있다. 확산요소가 20이고길이가 1000인서로다른 10개의 s-random 인터리버를사용하여각부호들에대하여평균성능을구하였다. 복호방법은 log-map을사용하였으며최대반복복호회수를 8로하였다. 복호도중복호된부호어에오류가없을경우복호를멈추는 Genie 156
논문 / 거리분포특성에근거한터보부호의순환조직형컨벌루션부호설계 10 0 10-1 10-2 v0,0 v0, v1,0 1, v BER/FER 10-3 10-4 10-5 10-6 [FER]Berrou [FER]Benedetto [FER]TV TC [FER]ODS TC [BER]Berrou [BER]Benedetto [BER]TV TC [BER]ODS TC 10-7 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 E b /N o [db] 그림 1. AWGN 채널에서인터리버의길이가 1000 이고전체부호율이 1/3 일때설계방법에따른표 1 의부호들에성능비교 (a 입력무게 2 인경우 v0,0 0, v1,0 1, (b 입력무게 4 인경우 그림 2. 짧은사이클을이루는두가지경우에대한확장정합그래프 (extended matching graph v v 멈춤규칙을사용하였다. 터보부호의전체부호율은 이며 AWGN 채널에서 BPSK 변복조방식을사용하였다. 전체부호의메모리크기는시변터보부호를제외하고 4이며시변터보부호는 6이다. ODS 터보부호와시변터보부호가낮은신호대잡음비에서좋은성능을보여주고있지만높은신호대잡음비에서는오류마루현상이빨리일어나는것을확인할수있다. 더욱이두부호의 FER 성능은낮은신호대잡음비에서도다른부호들에비해크게좋지않음을알수있다. Benedetto가제안한부호가높은신호대잡음비에서가장좋은성능을보여주고있다. 각부호들은같은 를가지고있지만 는다른값을가지고있다. 가커지면커질수록높은신호대잡음비에서더좋은성능을보여줌을알수있다. 터보부호와 effective free distance의관계는확장정합그래프 (extended matching graph 를이용하여설명할수있다. 구성컨벌루션부호의메모리크기가 2인병렬연접터보부호의확장정합그래프가그림 2에나와있다. 그래프는노드 들과노드들에의해연결된연결선들로구성되어있다. 모두 0인부호열을전송하였다고가정했을경우, 두노드들즉 와 를연결하는연결선들은첫번째부호화기의 에대응하는오류사건이고, 와 를연결하는연결선들은두번째부호화기의 에대응하는오류사건이다. 두노드들, 과 를연결하는연결선들은길이가 인인터리버에의해결정되어진다. 그림 2 는각각입력무게 2인경우와 4인경우일어날수있는짧은사이클들중두가지경우를보여주고 있다. 이러한종류의짧은사이클들은낮은무게를가지는부호어에대응하며수신한부호어들을잘못복호하여프레임오류을발생시키고전체성능을열화시키게된다. 특히높은신호대잡음비에서좋은부호를설계하기위해서는큰 를가지도록설계해야하며, 만약부호율이 인 RSC 부호설계시원시다항식 (primitive polynomial 을귀환연결다항식으로사용한다면최대 를얻을수있다. 하지만메모리의크기가큰경우최대 값은충분히크다. 예를들어메모리크기가 5인경우최대 는 20이며 6인경우최대 는 32가되어잘설계된인터리버를사용시성능에거의영향을주지않게된다. 그와반대로메모리크기가크고최대 를가진부호들의경우복호기에서반복복호시각정보비트들에대하여나쁜잉여 APP 추정값을산출함으로성능이오히려열화되는결과를가져온다. 본논문에서는부호에성능을높여주면서어느정도의 값을유지하는설계방법을제안하고자한다. 터보부호의설계에있어서구성 RSC 부호의 free distance는중요한요소로고려되어오지않고있다. 터보부호의성능과 free distance와의관계를고찰하여보자. 표 2는메모리크기가 4이고부호율이 1/2인 표 2. 메모리크기가 4 인두개의 RSC 부호들과그거리분포특성 Code1 (B4-4 Code2 (N4-4 부호 12 1 8 3 6 1 12 1 7 1 7 2 157
한국통신학회논문지 '08-02 Vol. 33 No. 2 FER/BER 10 0 10-1 10-2 10-3 10-4 10-5 10-6 10-7 [FER]Code1(B4-4 [FER]Code2(N4-4 [BER]Code1(B4-4 [BER]Code2(N4-4 10-8 0.2 0.4 0.6 0.8 1 1.2 1.4 E b /N o [db] 그림 3. AWGN 채널에서인터리버의길이가 1000 이고전체부호율이 1/3 일때설계방법에따른표 1 의부호들에성능비교 구성 RSC 부호의두경우가나와있다. Code1은논문 [5] 에서참조한것이다. 두부호모두 가 12 로같은값을가지고있다. Code2의 는 7로 Code1 의것보다작지만 는 7로 Code1의것보다큰값을가지고있다. 그들의 BER과 FER 성능이그림 3에나와있다. 인터리버와모의실험환경은그림 1과동일하다. 두부호모두거의같은성능을보여주고있지만높은신호대잡음비에서 Code2의성능이더좋아지는것을확인할수있다. Free distance 또한높은신호대잡음비에서좋은성능을얻기위한중요한요소임을알수있다. Ⅲ. 좋은부호를위한구성부호설계 Effective free distance, free distance, 그리고거리분포특성등은병렬연접터보부호의구성 RSC 부호설계에있어서중요한요소를하고있다. 이러한요소들에근거하여부호율이 1/2이고좋은구성 RSC 부호들을컴퓨터를이용하여찾아보았다. 검색알고리즘은다음순서와같다. 메모리크기 을선택하고귀환연결다항식의차수 을메모리크기 과같거나작게선택한다. 출력연결다항식의차수는항상 으로한다. 귀환연결다항식 의경우차수 을가지는원시다항식중에선택한다. 출력연결다항식 는차수 이고 와서로소인다항식중에선택한다. 본알고리즘은먼저실험적으로찾은최적의 effective free distance와 free distance를가지는부호를찾고그다음좋은거리분포를가지는 RSC 부호를찾는다. 본알고리즘에의해찾아진부호들은 Ⅱ장에서와같은 s-random 인터리버와실험환경에서 FER 범위까지컴퓨터모의실험을통해검증하였다. 메모리크기가 4 보다작을경우 값은최댓값을가지는경우가최적이였으며, 메모리크기가 4 와같거나큰경우는 12를가지는경우가가장좋은성능을보였다. 물론같은설계조건에서 12보다더큰 를가지는부호들도존재하였지만 12 의경우보다더좋지않았다. 본알고리즘에의해찾은부호들과성능비교를위한 Benedetto가제안한부호들의연결다항식과간단한특징들이표 3 에나열되어있다. Code(Ni-j 는메모리크기가 이고귀환연결다항식의차수 가 이며본논문에서제시한방법으로찾은새로운부호들을나타내고있으며, Code(Bi-j 는 Benedetto가제시한부호 [5] 들을나타낸다. 그림 4 는메모리크기가 4 인경우 10 0 10-1 표 3. 설계방법에따른구성 RSC 부호화기의기술및거리분포특성 부호 Code(B4-4 4 4 12 1 6 1 Code(B5-5 5 5 20 1 8 3 Code(B6-6 6 6 36 1 9 2 Code(N4-4 4 4 12 1 7 2 Code(N5-4 5 4 12 1 7 2 Code(N6-3 6 3 12 1 7 1 Code(N6-4 6 4 12 1 6 1 FER/BER 10-2 10-3 [FER]Code(B5-5 10-4 [FER]Code(B6-6 [FER]Code(N5-4 10-5 [FER]Code(N6-3 [FER]Code(N6-4 10-6 [BER]Code(B5-5 [BER]Code(B6-6 10-7 [BER]Code(N5-4 [BER]Code(N6-3 [BER]Code(N6-4 10-8 0.2 0.4 0.6 0.8 1 1.2 1.4 E b /N o [db] 그림 4. AWGN 채널에서인터리버의길이가 1000 이고전체부호율이 1/3 일때설계방법에따른표 1 의부호들에성능비교 158
논문 / 거리분포특성에근거한터보부호의순환조직형컨벌루션부호설계 I A2 (I E1 I A2 (I E1 1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 B4-4 B5-5 B6-6 N4-4 N5-4 N6-4 N6-3 0 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 I A1 (I E2 1 0.9 0.8 0.7 0.6 0.5 (a Eb/N0 = 0.6dB 에서의 EXIT chart 0.4 B4-4 B5-5 0.3 B6-6 0.2 N4-4 N5-4 0.1 N6-4 N6-3 0 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 I A1 (I E2 수있다. 즉반복복호에따른정보의수렴이커진다는것을알수있다. 그림 4에서도 Benedetto의부호들은메모리크기가점점증가함에따라성능이더열화되는모습을보여주고있지만새로운부호들은조금씩좋아짐을확인할수있다. Ⅳ. 결론본논문에서실험적으로찾은 effective free distance값에근거하여부호율이 1/2인구성 RSC 부호들을설계하는방법에대하여고찰하였다. 컴퓨터를이용하여새로운부호들을찾아표로나열하였다. 새로운부호들은 FER 범위까지최적화되었으며 는 12값으로하였다. 이론적으로최적의 값이어떤값을가지는지에대한것은앞으로연구할주제이다. Effective free distance값을크게할경우전체터보보호의 free distance는크게할수있지만코드전체의성능을항상향상시키는것은아니며본논문에서제안한설계방법을이용할경우반복복호에따른수렴속도가높여주면서도오류마루현상을어느정도억제할수있는부호를설계할수있다. 참고문헌 (b Eb/N0 = 1.2dB 에서의 EXIT chart 그림 5. 표 3 의부호들의그림 3, 4 환경에서 Eb/No 가 0.6dB 일때와 1.2 db 일때의 EXIT chart 를제외하고표 3에나와있는다양한부호들에대하여신호대잡음비에대하여이전과같은실험환경에서의 BER과 FER 곡선이다. 메모기크기 4 인경우는이미그림 3에서보여주었다. 그림 5 는표 3의그림 3, 4에대한 EXIT chart를보여주고있다 [10][11]. 그림 5의 (a 와 (b 는각각신호대잡음비 E b/n 0 가 0.6dB일경우와 1.2dB의경우의 EXIT chart이다. 채널환경을변화시켜가면서평균상호정보 (mutual information 값을구하였다. Benedetto가제안한부호들은메모리크기가증가함에따라병목지역 (bottleneck region 까지의폭의점점줄어들고있으며 wide-open 지역에서는약간넓어지고있다. 즉반복복호에따른정보의수렴이늦거나큰차이가없다는것을알수있다. 새로제안한부호들의경우메모리의크기가증가함에따라 pinch-off 지역이점점더넓어지며귀환다항식의차수가줄어듦에따라더넓어지는것을알 [1] C. Berrou and A. Glavieux, Near optimum error correcting coding and decoding: turbo-codes, IEEE Trans. Commun., Vol.44, Issue 10, pp.1261-1271, Oct. 1996. [2] S. Benedetto, G. Montorsi, Unveiling Turbo Codes : Some Results on Parallel Concatenated Coding Schemes, IEEE Trans. Commun., Vol. 42, No.2, pp.409-428, Mar. 1996 [3] S. Benedetto, G. Montorsi, Design of parallel concatenated convolutional codes, IEEE Trans. Commun., Vol.44, Issue 5, pp. 591-600, May 1996. [4] D. Divsalar and R. J. McEliece, R.J, Effective free distance of turbo codes, Electronics Letters, Vol.32, Issue 5, pp.445-446, 1996. [5] S. Benedetto, R. Garello and G. Montorsi, A search for good convolutional codes to be used in the construction of turbo codes, IEEE Trans. Commun., Vol.46, Issue 9, pp.1101-1105, Sept. 1998. 159
한국통신학회논문지 '08-02 Vol. 33 No. 2 [6] P.C. Massey, O. Y. Takeshita, and D. J. Costello Jr, Contradicting a myth: good turbo codes with large memory order, in Proceedings IEEE International Symposium on Information Theory,. pp.122, 25-30 June 2000 [7] Fan Jiang, M.R. Becker, and L. C. Perez, Time-varying turbo codes, IEEE Commun. Letters, Vol.8, Issue 8, Aug. 2004, pp.529-531 [8] J. Yuan, B. Vucetic, and W. Feng, Combined turbo codes and interleaver design, IEEE Trans. Commun., Vol.47, Issue 4, pp.484-487, April 1999 [9] A. Perotti and S. Benedetto, A new upper bound on the minimum distance of turbo codes, IEEE Trans. Inform. Theory, Vol.50, Issue 12, pp.2985-2997, Dec. 2004 [10] S. ten Brink, Convergence Behavior of Iteratively Decoded Parallel Concatenated Codes, IEEE Trans. Commun., Vol. 49, No. 10, pp.1727-1737, Oct. 2001 [11] J. W. Lee and R. E. Blahut, Generalized EXIT Chart and BER Analysis of Finite-length Turbo Codes, IEEE Globecom 03, Vol.4, pp.2067-2072, Dec. 2003 김대선 (Dae-Son Kim 준회원 2001년 2월건국대학교전자공학과졸업 ( 공학사 2003년 2월연세대학교대학원전기전자공학과졸업 ( 공학석사 2006년 ~ 현재연세대학교대학원전기전자공학과박사과정 < 관심분야 > Error Correcting Codes, Turbo code, LDPC, MC-CDMA, Spread Spectrum Communication Systems 송홍엽 (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 이동학 (Dong-Hahk Lee 준회원 1988년 2월경북대학교전자공학과졸업 ( 공학사 1991년 2월포항공대전자공학과졸업 ( 공학석사 1996년 2월포항공대전자공학과졸업 ( 공학박사 1996년 ~ 현재 SK텔레콤네트워크선임연구원 < 관심분야 > W-CDMA 모뎀설계,, OFDM, 4G, 통신 / 방송융합기술유재황 (Jaehwang Yu 정회원 1984년 2월경북대학교전자공학과학사 1986년 2월연세대학교전자공학과석사 2005년 8월 KAIST 전기및전자공학과박사 1988년 4월 ~1993년11월국제상사전자기술연구소선임연구원 1993년11월 ~2006년 1월 SK텔레콤 Network연구원엔지니어링기술개발팀장, Network기술기획팀장 2006년 1월 ~ 현재 SK텔레콤 Access기술연구원 Access 망개발 3팀장 2006년 1월 ~ 현재 BcN Forum 무선방송분과장 < 관심분야 > 4G, USN, 통신 / 방송융합기술, SDR 160