논문 08-33-09-06 한국통신학회논문지 '08-09 Vol. 33 No. 9 H-ARQ 시스템에서 LDPC 부호의반복복호중단기법 정회원신범규 *, 김상효 **, 종신회원노종선 *, 신동준 *** New Stopping Criteria for Iterative Decoding of LDPC Codes in H-ARQ Systems Beomkyu Shin*, Sang-Hyo Kim** Regular Members, Jong-Seon No*, Dong-Joon Shin*** Lifelong Members 요 약 반복적인신뢰전파알고리듬을 low-density parity-check(ldpc) 부호에적용하는경우패리티- 검사를이용한기존복호중단기법은높은 signal-to-noise ratio(snr) 영역에서반복복호수를줄이는것을가능케한다. 그러나재전송요청이빈번한 Hybrid-ARQ(H-ARQ) 시스템에서는낮은 SNR 영역에적합한복호중단기법이없기때문에복호에실패하는경우많은양의불필요한반복복호가수행된다. 본논문에서는결국복호에실패하게될 LDPC 부호블록들을복호초기단계에서발견하기위하여신뢰전파복호에서임시부호어의신드롬무게를이용한중단기법을제안한다. 제안된기법은 H-ARQ 시스템을위한 LDPC 복호기에서구현복잡도의증가와성능의열화없이도연산량을 70-80% 감소시킨다. Key Words : LDPC codes, Stopping criteria, Hybrid-ARQ, Iterative decoding, belief propagation ABSTRACT By using inherent stopping criteria of LDPC codes, the average number of iterations can be substantially reduced at high signal to noise ratio (SNR). However, we encounter a problem when hybrid automatic repeat request (H-ARQ) systems are applied. Frequent failures of decoding at low SNR region imply that the decoder reaches the maximum number of iterations frequently and thus the decoding complexity increases. In this paper, we propose a combination of stopping criteria using the syndrome weight of tentative codeword. By numerical analysis, it is shown that the decoding complexity of given H-ARQ system is reduced by 70-80% with the proposed algorithms. Ⅰ. 서론 1993 년 Berrou 등은 Shannon 의한계에근접하는 성능의터보부호 (turbo code) 를제안하였다 [1]. 이연구결과는실현이어려운것으로여겨졌던 Shannon의채널용량 (channel capacity) 을실용적 본연구는교육인적자원부, 산업자원부, 노동부에의해추진된최우수연구실지원사업과지식경제부및정보통신연구진흥원의 IT 핵심기술개발사업 [2008-F-007-01, 3 차원환경에서의지능형무선통신시스템 ] 의일환으로수행되었습니다. * 서울대학교전기 컴퓨터공학부부호및암호연구실및뉴미디어통신공동연구소 ({thechi76,jsno}@snu.ac.ac.kr) ** 성균관대학교정보통신공학부통신및부호이론연구실 (iamshkim@skku.edu) *** 한양대학교전자컴퓨터통신공학부부호및통신연구실 (djshin@hanyang.ac.kr) 논문번호 :KICS2008-05-250, 접수일자 :2008 년 5 월 27 일, 최종논문접수일자 : 2008 년 9 월 3 일 683
한국통신학회논문지 '08-09 Vol. 33 No. 9 복잡도로실현가능함을최초로보임으로써, 뒤를이은관련분야연구의기폭제가되었다. 실제로터보부호의복호는부호의길이에대하여선형복잡도를갖는알고리듬 [2] 을반복적으로적용함으로써실현가능한복잡도를갖는다는점에서큰의의가있다. 터보부호의발견에영향을받아실용적복잡도의복호방식을가지며채널용량에근접하는성능을갖는 low-density parity-check(ldpc) 부호가재발견되었다 [3]. LDPC 부호는신뢰전파알고리듬 (belief propagation algorithm) 이라는선형복잡도의알고리듬의반복적인수행으로복호가가능하다. 터보부호와 LDPC 부호는탁월한복호성능을인정받아다양한무선통신표준의오류정정부호로채택되었다 [4][5][6][7]. 터보부호나 LDPC 부호의복호가실현가능한복잡도로구현될수있지만여전히높은계산복잡도를필요로한다. 이에따라복호기의계산복잡도를줄이기위하여반복복호중단기법 (stopping criteria) 에관한연구들이진행되어왔는데, 그대표적인예로교차엔트로피중단기법과경판정보조중단기법을들수있다 [8]. LDPC 부호의경우복호결과가유효부호어에도달하였을때, 복호를중단하는신드롬검사혹은패리티검사중단기법이있다 [3]. 신드롬검사중단은신뢰전파복호고유의중단기법으로, 복호성능의저하없이매우우수한중단성능을보인다. 이는터보부호와비교되는장점중하나다. 지금까지반복복호의중단기법에대한연구는주로복호기가전송된부호어로성공적으로수렴한경우불필요한반복복호를막기위한것이었다. 때문에낮은패킷오율을보이는높은신호대잡음비 (signal-to-noise ratio; SNR) 영역이주요관심영역이었고이러한영역에서는효과적인중단성능을달성할수있었다. 하지만이러한반복복호부호가 Hybrid-ARQ (H-ARQ) 전송기법과결합되는경우새로운문제가발생한다. H-ARQ 전송기법을사용하는경우주어진변조부호율이최대의효율을보이는 SNR 에서높은비율로재전송이이루어지게되는것이일반적이다. 즉, 수신기에서는복호불가능한수신신호에대해복호시도를하게되는경우가많아진다. 이러한경우복호기가정해진최대반복복호횟수까지동작하게되어복호기의계산복잡도를상승시킨다. 그러므로 H-ARQ가적용된시스템에서 는결국복호실패로귀결될낮은 SNR 입력에대해서초기에성공적으로복호중지판정을내려주는기법으로계산복잡도를크게감소시키는것이중요하다. 가능한방법으로 SNR과같은채널관찰값이나복호기입력메트릭의통계를이용한중단을가정할수있으나, 상용시스템에서는채널의빠른변화등의요인으로 log likelihood ratio(llr) 를정확하게계산하기힘든경우가많다. [9] 에서는신뢰전파복호의특성을관찰하고, 각단계의출력 LLR의절대값의합의수렴여부를이용한복호중단기법을제시하였고, 이는많은복호불가능한프레임을미리판정하여낮은 SNR에서계산복잡도를크게낮추었다. [10] 에서는위와독립적으로출력 LLR의절대값의평균의수렴을이용한중단기법을제시하였다. 이방법들은먼저다수의부동점연산혹은많은비트의고정점연산을요구하므로, 다소높은복잡도가요구된다. 또한, 중단기법의성능이파라미터의변화나, 채널변화, LLR 계산오류등에민감한단점을갖고있다. [11] 에서는 [9] 의관찰및중단전략을참조하여, LDPC 복호과정에포함되는패리티검사결과즉, 출력 LLR의경판정벡터의신드롬벡터만을이용한효과적인중단기법을제시하였다. [11] 의기법은 AWGN 뿐만아니라, 레일리페이딩채널 (Rayleigh fading channel) 에동시에좋은중단성능을보인다는큰의미를갖는다. [9]-[11] 의정지기법들은실제로복호성공이불가능한프레임을미리판정할수있어, 논문에서고려하는 H-ARQ가적용된시스템을위한반복복호중단기법으로사용이가능하다. 하지만, 현재까지이러한중단기법에의한 H-ARQ 에서의복잡도감소이득이평가된바가없었다. 또한, 상기기법들은매우열악한채널을거쳐복호시도를할필요가없는프레임이라하더라도, 상당한수의반복복호를거친후복호실패판정을하는문제를갖는다. 본논문에서는 [11] 에서와같이신드롬벡터의해밍무게 (Hamming weight) 만을이용하는효율적인반복복호중단기법을제시한다. 제안기법은 H-ARQ 시스템의특성상많은복호실패및재전송이발생할수있으므로, 더열악한채널을겪은프레임일수록빨리중단판정을하는것을목표로한다. 특히, 제안기법은다양한크기의 LDPC 부호및채널에대하여공통된기법을적용하는것이가능하며, 특히입력메트릭의스케일링에오류가 684
논문 /H-ARQ 시스템에서 LDPC 부호의반복복호중단기법 있는경우에도안정적으로동작한다. 제안기법은매우적은계산량으로효과적인중단성능을보이며, 특히 H-ARQ 시스템에서극적인복잡도감소효과를얻게한다. 본논문의구성은다음과같다. Ⅱ장에서는제안하고자하는기법의기준메트릭과신뢰전파복호에따른기준메트릭의변화추이에대한관찰이제시된다. Ⅲ장에서는위의관찰에기반한새로운반복복호중단기법을제시한다. Ⅳ장에서는제안된기법의효용성을 AWGN (additive white Gaussian noise) 채널에서검증하고뒤이어 IEEE 802.16e 표준안에제시되어있는 H-ARQ 구조에적용한결과를제시하고자한다. 마지막으로 Ⅴ장에서는결론을맺는다. Ⅱ. 신뢰도전파복호와신드롬무게의추이 2.1 신드롬무게패리티 -검사행렬 H를갖는 LDPC 부호에대하여입력 LLR 벡터를 로표시하고신뢰전파복호의 번째복호단계의경판정결과를벡터 로표현하면복호중간단계의신드롬검사결과를다음과같은벡터로나타낼수있다. (1) 이때 를신드롬 의해밍무게라하면그값은신뢰전파복호과정의 번째반복복호후만족되지않은체크노드의수를의미하게되며, 신뢰전파복호의진행정도를평가하는좋은척도가된다. 이메트릭은신뢰전파복호에추가적인계산을필요로하지않으며, [11] 에서제안된기법의기준척도가된다. 본논문에서도이신드롬무게를중단기법의척도로삼는다. 2.2 반복신뢰전파복호에따른신드롬무게의추이본논문에서제안하는기법은최대복호횟수에도달할때까지복호를수행해도결국복호에실패하게될부호블록을미리검출하는것을목표로한다. 따라서가급적반복복호과정의초반부에정확하게복호실패여부를판별해내는것이관건이다. 복호실패의안정적인조기판별을위해서는최대반복횟수까지수행되는 LDPC 부호의반복복호결과후에도반드시복호에실패하는경우에대 그림 1. 복호실패하는경우의반복복호수에따른 추이 (IEEE802.16e LDPC 부호, N=2304, R=0.5, ( 실선 ), ( 점선 )). 해신드롬무게 의추이를분석해야한다. 그림 1에서는 AWGN 채널의낮은 영역에서복호에실패하는경우해당복호과정중의신드롬벡터의해밍무게, 즉만족되지못한체크노드의수를 200 프레임에대해서만반복복호횟수의함수로도시하였다. 초기수회의수렴과정후에는대부분의오류프레임들의 가고정된값으로수렴함을확인할수있다. 즉더이상복호를시도하더라도 는고정된채최대반복횟수까지변화가없게된다. 비교적높은 의경우에이러한현상은전체오류프레임중일부에지나지않지만 가낮아질수록발생비율이점점높아져일정수준이하의 에서는관측된모든오류프레임에서이러한현상을발견할수있게된다. 그림 1에서오류프레임의또다른양상을볼수있다. 사용된 LDPC 부호의거스 (girth) 에따라다르지만초기수회의반복복호과정은사이클의존재가복호알고리듬에영향을주지않으므로이상적인복호기의동작과유사하게복호가진행됨에따라 가단조감소한다. 의변화추이를 의값과높은상관성을가짐을알수있다. 예를들어그림 1에서초기 3회째의반복복호결과를보면 값은 250~300 사이를기준으로 에서의복호결과와 에서의결과가잘구분됨을알수있다. 이러한오류프레임들의 의값을변화시켜가면서비교해보아도유사한양상을관측할수있다. 이경향을이용하면, 낮은 를갖는프레임의복호실패를조기에판별할수있게된다. 685
한국통신학회논문지 '08-09 Vol. 33 No. 9 while ( maximum number of iteration) { run -th iteration of BP decoding if stop decoding if if > stop decoding update, in 그림 2. 제안된조기중단기법의순서도 물론정확한 의추정이가능한경우에는해당 LDPC 부호의복호성능을고려한중단기법을생각할수있다. 하지만, 일반적인부호화된 OFDM 시스템에서는각부반송파마다각기다른채널을겪게되고, 시간에따라채널상태가변하는페이딩채널을겪으며, H-ARQ가적용되는경우결합된 LLR의상태를평가해야하기때문에, 단순히 을이용하는중단기법은구현이어렵거나, 다소심각한성능열화를수반할것이다. Ⅲ. 새로운조기중단기법 본절에서는앞절에서신뢰전파복호에대한관찰결과를이용하여조기중단기법을제시한다. 먼저, 복호기의정체상태를검출해서복호를조기중단하는기법은다음과같이일반화된형태로정의할수있다. 정체구간의길이에대한기준값을 라하면임의의 구간동안매반복복호과정에서의 의최댓값과최솟값의차이가정해진기준 이내이면, 복호를중단한다. 즉 구간내에서 의최댓값과최솟값을각각 와 이라하면다음이성립하는경우복호를중단한다. 오류프레임대부분이 가주기적으로변하기보다는고정된값으로수렴하는것으로관측되므로다음장에서일반적인복호중지기법을완화 if stop decoding } 하여 인경우에대해서만중단성능을살펴보기로한다. 이는 으로 구간만큼동일한값이유지되는경우에해당한다. 오류프레임의관측결과에의해제안되는또하나의조기중단기법은다음과같다. 정체상태를검출하기이전에, 복호초기수회 ( ) 반복이이루어진후 를점검하여그값이정해진기준 ( ) 보다작으면복호에성공할가능성이있다고판단하지만기준보다크면오류확률이거의 100% 에달하는낮은 영역으로판단하여복호를중단한다. 이는아주낮은 를갖는수신블록들의복호실패여부의조기판별에이용한다. 위두가지중단기법과신뢰전파알고리듬고유의중단기법인신드롬검사기법을다음과같이조합하여사용한다. 본논문에서제안하는상기의조합은복호과정에서의 만을관측함으로써간단하게구현된다. Ⅳ. 모의실험결과 4.1 AWGN 채널의결과그림 3과그림 4는앞서설명한복호중단기법을 AWGN채널에적용한모의실험결과이다. 궁극적으로는제안하는기법을 H-ARQ 시스템에적용하는것이목표이지만 AWGN채널에서의동작을확인해보는것도기법의효용성을추량하는데도움이될수있다. 본실험에서는매개변수 선택에따른 frame error rate(fer) 성능및연산량의변화를비교한다. 모의실험에사용된부호는 686
논문 /H-ARQ 시스템에서 LDPC 부호의반복복호중단기법 그림 3. 정체구간의길이만으로복호중단을판정하는기법의 FER 성능 그림 5. 두기법을모두적용한경우의 FER 성능 그림 4. 정체구간의길이만으로복호중단을판정하는기법의평균반복복호횟수 IEEE802.16e의길이 2304, 부호율 1/2의 LDPC 부호이며, 최대반복복호횟수는 50회로제한하였다. 실험결과에따르면 에서성능열화없이도 미만의구간에서많은양의연산량감소가일어났음을확인할수있다. 이러한연산량의개선폭은최대반복복호횟수의증가에따라커진다. 이렇게정체구간만을이용하여도오류프레임을조기검출하는기법은복호시불필요한연산량을상당부분줄일수있음을확인할수있다. 그러나앞장에서기술한바와같이정체구간에도달하기까지적게는수회에서많게는십수회정도의감소구간을겪어야만하는데이는그림 4에서평균반복횟수값이낮은 SNR에서도 10회이하로떨어지기어려움을의미한다. 정체구간을이용하는기법에 의문턱값을이용하는기법을동시에적용시킨성능결과가그림 5와그림 6에제시되어있다. 의문턱값을같이이용하는경우그림 5 와 그림 6. 두기법을모두적용한경우의평균반복복호횟수 그림 6에서확인할수있듯이성능열화없이도큰연산량의감소가이루어짐을확인할수있고특히예측한바와같이아주낮은 영역에서는 값에의해반복복호로연산량이결정됨을확인할수있다. 4.2 H-ARQ 시스템및페이딩채널 LDPC 부호를사용하는 H-ARQ 시스템에제안된기법을이용하면큰폭의연산량감소가달성됨을보이기위하여 IEEE802.16e 표준에서실제채택된 type-i H-ARQ 전송방식을모의실험에적용해보았다. 실험에사용된 adaptive modulation and coding (AMC) 형식은표 1에정리되어있는데, 이를통해제안된기법이다양한부호율및서로다른형태로설계된 LDPC 부호에포괄적으로적용될수있는지여부를확인할수있다. 사용된 H-ARQ 구조는부호어당최대 4번까지의전송을허용하는것으로설정하였다. 전송에사용되는자원은 288개의 orthogonal frequency-division multiplexing (OFDM) 687
한국통신학회논문지 '08-09 Vol. 33 No. 9 표 1. AMC 적용표 (*: A 타입부호, **: B 타입부호 ) 표 2. 복호조기중단을위한 의문턱값 변조 부호길이 부호율 체크노드수 1/2 288 QPSK 576 3/4 ** 144 1/2 576 16QAM 1152 3/4 ** 288 1/2 864 2/3 * 576 64QAM 1728 3/4 ** 432 5/6 288 변조 QPSK 16QAM 64QAM 부호율 값 ( 비율 ) 100% 10% 15% 20% 25% 30% 1/2 288 28 43 57 72 86 3/4 ** 144 14 21 28 36 43 1/2 576 57 86 115 144 172 3/4 ** 288 28 43 57 72 86 1/2 864 86 129 172 216 259 2/3 * 576 57 86 115 144 172 3/4 ** 432 43 64 86 108 129 5/6 288 28 43 57 72 86 그림 7. IEEE 802.16e 의 H-ARQ 적용시전송률 그림 9. 두기법을모두적용한경우전송률 그림 8. IEEE 802.16e 의 H-ARQ 적용시평균반복복호횟수 부반송파로설정하였으며 3-경로독립페이딩채널을가정하였다. LDPC 복호는최대반복복호횟수 50 번의신뢰전파알고리듬을사용하였다. 표 1의전송구조에따라 H-ARQ전송을하는경우그림 7, 그림 8과같은전송률과평균반복복호횟수에대한결과를얻을수있다. 그림 10. 두기법을모두적용한경우평균반복복호횟수이상적인 H-ARQ 스케줄러라면주어진 SNR에서최대전송률을갖는 AMC 등급을선택할것이다. 그림에서실선은주어진 SNR에서최대의전송률과이에해당되는평균반복복호횟수이다. 제안한기법의연산량감소효과를확인하기위 688
논문 /H-ARQ 시스템에서 LDPC 부호의반복복호중단기법 하여적당한매개변수들을찾아보았다. 먼저정체구간을이용한기법으로부터전송률성능의열화가거의없이연산량을최소화하기위한 값이 5임을실험적으로찾을수있었다. 다음으로 의문턱값을이용한중단기법을적용하기위해적절한문턱값의기준을정하여실험을수행해보았다. 이때적용된문턱값은표 2 에제시되어있다. 표에표시된백분율은전체체크노드수를기준으로문턱값으로사용되는체크노드수의비율을나타낸다. 이는표 1에나와있는 AMC의다양한전송방식에대해동일한기준을적용하기위한공통된기준이된다. 의문턱값인 를전체체크노드수의 1/4 정도로설정하면무시할만한성능열화만으로 LDPC 부호의복호연산량의 70-80% 를감소시킬수있음이그림 9와그림 10을통해확인되었다. Ⅴ. 결론신뢰전파복호의신드롬검사중단기법은높은 SNR 영역에서는수회의반복만으로도복호를성공적으로종료시킨다. 하지만 H-ARQ 시스템에서는 2번이상의재전송이빈번하게발생하며, 이는오류프레임을최대반복복호횟수까지불필요하게동작시켜의미없는연산량의증가를야기한다. 본논문에서는결국복호에실패할오류블록을조기에안정적으로발견하기위한효율적인중단기법을제시하였다. 제안된기법은간단한비교연산만을적용함으로써구현의복잡도가매우낮으며, type-i H-ARQ 시스템이적용된경우에성능의열화없이도전체복호복잡도의 70-80% 를감소시킬수있음이모의실험을통하여확인되었다. 참고문헌 [1] C. Berrou, A. Glavieux, and P. Thitimajshima, Near Shannon limit error-correcting coding and decoding: Turbo codes, in Proc. IEEE Int. Conf. Commun., 1993, pp.1064-1070. [2] L. Bahl et al., Optimal decoding of linear codes for minimizing symbol error rate, IEEE Trans. Inform. Theory, Vol.20, No.2, pp.284-287, 1974. [3] D. Mackay and R. M. Neal, Near Shannon limit performance of low density parity check codes, Elec. Lett., Vol.32, No.18, pp.1645-1646, 1996. [4] IEEE Std. 802.16., IEEE Standard for local and metropolitan area network part 16: Air interface for fixed and mobile broadband access systems, 2004. [5] 3GPP, Technical specification group radio access network multiplexing and channel coding (FDD), 3GPP TS25.212, 1999. [6] 3GPP2, Physical layer standard for cdma2000 spread spectrum systems, Rev. D, C.S0002-D, Feb. 2004. [7] IEEE Std. 802.11n/D2.00, Draft IEEE Standard for Local Metropolitan Networks-Specific Requirements. Part 11: Wireless LAN MAC and PHY Specifications: Enhancements for Higher Throughput, Feb. 2007. [8] R. Shao, S. Lin, and M. Fossorier, Two simple stopping criteria for turbo decoding, IEEE Trans. Commun., Vol.47, No.8, pp.1117-1120, 1999. [9] F. Kienle and N. When, Low complexity stopping criterion for LDPC code decoders, in Proc. IEEE Veh. Tech. Conf. (VTC-2005), 2005, pp.606-609. [10] D. Shin et al., A stoppping criteria for low-density parity-check codes, IEICE Trans. Commun., Vol.E91-B, No.4, pp.1145-1148, Apr. 2008. [11] J. Li, X. You, and J. Li, Early stopping for LDPC decoding: Convergence of mean magnitude (CMM), IEEE Commun. Lett., Vol.10, No.9, pp.667-669, 2006. 689
한국통신학회논문지 '08-09 Vol. 33 No. 9 신범규 (Beomkyu Shin) 정회원 1999년 2월서울대학교전기공학부공학사 1999년 3월 ~2002년 1월 ( 주 ) Locus, 연구원 2002년 1월 ~2003년 6월 ( 주 ) 휴맥스, 전임연구원 2004년 3월 ~ 현재서울대학교전기 컴퓨터공학부석사박사통합과정 < 관심분야 > LDPC 부호, 반복복호알고리듬, 통신시스템김상효 (Sang-Hyo Kim) 정회원 1998년 2월서울대학교전기공학부공학사 2000년 2월서울대학교전기공학부공학석사 2004년 2월서울대학교전기공학부공학박사 2004년 3월 ~2006년 7월삼성전자, 책임연구원 2006년 8월 ~2007년 8월박사후연구원 (USC) 2007년 9월 ~ 현재성균관대학교정보통신공학부조교수 < 관심분야 > LDPC 부호, 시공간부호, MIMO, 릴레이통신, 협력통신 노종선 (Jong-Seon No) 종신회원 1981년 2월서울대학교전자공학과공학사 1984년 2월서울대학교대학원전자공학과공학석사 1988년 5월 Univ. of Southern California, 전기공학과공학박사 1988년 2월 ~1990년 7월 Hughes Network Systems, Senior MTS 1990년 9월 ~1999년 7월건국대학교전자공학과부교수 1999년 8월 ~ 현재서울대학교전기컴퓨터공학부교수 < 관심분야 > 시퀀스, 시공간부호, LDPC 부호, OFDM, 이동통신, 암호학신동준 (Dong-Joon Shin) 종신회원 1990년 2월서울대학교전자공학과공학사 1991년 12월 Northwestern Univ., 전기공학과공학석사 1998년 12월 USC, 전기공학과공학박사 1999년 1월 ~1999년 4월 Research Associate (USC) 1999년 4월 ~2000년 8월 Hughes Network Systems, MTS 2000년 9월 ~ 현재한양대학교전자통신컴퓨터공학부부교수 < 관심분야 > 디지털통신, 이산수학, 시퀀스, 오류정정부호, 암호학 690