38

논문 09-34-06-02 한국통신학회논문지 '09-06 Vol. 34 No. 6 LDPC 부호를위한복잡도와대기시간을낮춘 VCRBP 알고리즘 준회원김정현 *, 종신회원송홍엽 * Reduced Complexity-and-Latency Variable-to-Check Residual Belief Propagation for LDPC Codes Jung-Hyun Kim* Associate Member, Hong-Yeop Song* Lifelong Member 요 약 본논문에서는, LDPC 부호를위한 node-wise VCRBP 의개선된기법인, 강제수렴 node-wise VCRBP 와부호 기반 node-wise VCRBP 를제안한다. 두가지기법모두 node-wise VCRBP 에비하여매우적은오류정정성 능열화만으로복호복잡도와대기시간을현저하게줄인다. Key Words : LDPC Codes, VCRBP, Fast Convergence Decoding, Informed Dynamic Scheduling ABSTRACT This paper proposes some new improved versions of node-wise VCRBP algorithm for low-density parity-check (LDPC) codes, called forced-convergence node-wise VCRBP algorithm and sign based node-wise VCRBP, both of which significatly reduce the decoding complexity and latency, with only negligible deterioration in error correcting performance. Ⅰ. 서론 LDPC 부호 [1] 는낮은복호복잡도로 Shannon의채널용량한계에거의근접하는성능을갖는오류정정부호로다양한통신분야에서주목받고있다. 대표적인복호알고리즘으로모든변수노드와체크노드의메시지를동시에전달하는표준신뢰전달 (belief propagation 이하 BP) 알고리즘이있으며, 이를반복복호횟수면에서개선시킨순차적스케줄링 BP 알고리즘이있다. 순차적스케줄링기법은변수노드방향으로업데이트하는지체크노드방향으로업데이트하는지에따라 Shuffled BP (SBP) 와 Layered BP (LBP) 로구분된다. 이러한순차적스케줄링기법들은표준 BP 알고리즘보다두배의 복호수렴속도를갖는다 [2][3]. SBP와 LBP 기법이소개된이후로, Replica SBP [4], 개선된 SBP [5], 결합열-행복호 [6], 에지기반스케줄링 BP [7] 등과같은더욱향상된기법들이연구되고있다. 최근레지듀얼 BP (Residual Belief Propagation 이하 RBP) 라 [8] 불리는매우효과적인동적스케줄링기법이소개되었으며, 또한이를 LDPC 부호에적용시킨 RBP 복호알고리즘과 [9][10] Variable-to-Check RBP(VCRBP) 복호알고리즘이 [11][12] 제안되었다. 위의두가지동적스케줄링기법들은모두기존의정적스케줄링기법들에비하여더욱빠른복호수렴속도를갖는다. 또한트래핑셋 (trapping set) 을효과적으로해결함으로써정적스케줄링기법들에비하여현저한성능개선을보인다 [9][10]. 그러나 RBP 본연구는한국과학재단특정기초연구 (R01-2008-000-20578-0) 지원으로수행되었음. * 연세대학교전기전자공학부부호및암호연구실 ({jh.kim06, hysong}@yonsei.ac.kr) 논문번호 :KICS2009-04-152, 접수일자 :2009 년 4 월 13 일, 최종논문접수일자 :2009 년 5 월 22 일 571

한국통신학회논문지 '09-06 Vol. 34 No. 6 복호알고리즘은그리디니스 (greediness) 특성으로 인해성능면에서결점을갖을뿐만아니라 [9][10], 복 잡도면에서도결점이있다. 이러한 RBP 복호알고 리즘의문제점들을개선시킨것이 VCRBP 복호알 고리즘이다 [11][12]. RBP 복호알고리즘은체크 - 변수 메시지값의차이로정렬기준값인레지듀얼을계산하는반면 VCRBP 복호알고리즘은변수- 체크메시지값의차이로레지듀얼을계산한다. 이러한변화로인하여작은반복복호횟수만으로탁월한성능개선을얻을수있으며, RBP 복호알고리즘에서의불필요한연산을피함으로써복잡도를현저하게줄일수있다. 또한 node-wise VCRBP (NVCRBP) 복호알고리즘은 [12] VCRBP 복호알고리즘에비해보다낮은복호복잡도로거의근접한성능을보인다. 그러나 RBP 스케줄링기법을사용하는모든동적스케줄링복호알고리즘들은매반복복호시추가적으로레지듀얼값을계산하고정렬해야하므로표준 BP 복호알고리즘에비하여복호복잡도와실제복호가이루어지기전까지의대기시간이증가한다. 본논문에서는이러한문제점들을최소화하기위하여 NVCRBP 복호알고리즘의복잡도와대기시간을줄인두가지새로운기법인강제수렴 NVCRBP (forced-convergence NVCRBP, 이하 FC-NVCRBP) 복호알고리즘과부호기반 NVCRBP (sign-based NVCRBP, 이하 S-NVCRBP) 복호알고리즘을제안한다. FC-NVCRBP 복호알고리즘은이미수렴되었다고판단되는메시지의업데이트를생략함으로써복잡도와대기시간을줄인다. 반면, S-NVCRBP 복호알고리즘은메시지의부호에근거한새로운정렬기준값을사용하여복잡도와대기시간을줄인다. 본논문의 II절에서 LDPC 부호를위한 NVCRBP 복호알고리즘을소개하고, III절에서는제안하는 FC-NVCRBP 복호알고리즘과 S-NVCRBP 복호알고리즘을설명한다. 그리고 IV절에서는모의실험을통한성능비교를보여주고 V절에서결론을맺는다. Ⅱ. LDPC 부호를위한 NVCRBP 알고리즘 2.1 Dual-min-sum 복호알고리즘 LDPC 부호를위한표준 BP 복호알고리즘은변수노드와체크노드간의반복적메시지전달을통해이루어진다. 체크노드 와이웃변수노드 에대해메시지업데이트함수는다음과같이정의된다 [1]. (1) (2) 여기서 를수신신호라고할때, 에대한채 널정보를 로정의한다. 또한 는 노드를제외한 노드의이웃노드들의집합을의미하고 는 노드를제외한 노드의이웃노드들의집합을의미한다. 표준 BP 복호알고리즘에서체크 -변수메시지의계산이연산량의대부분을차지하므로우리는복잡도를줄이기위하여다음과같은 dual-min-sum 알고리즘을 [13] 사용한다. dual-min-sum 알고리즘에서는수식 (2) 가다음과같이대체된다 : (3) 여기서 는성능을최적화시키는적당한실험값이다 [14]. 본논문의이하실험결과들은모두위의 dual-min- sum 알고리즘을사용하였으며 값을 0.5 로고정하 였다. 2.2 NVCRBP 복호알고리즘 RBP 는레지듀얼 (residual) 이라불리는정렬기 준값을가장크게갖는메시지를우선업데이트하는동적스케줄링기법이다. 메시지 에대하여레지듀얼은다음과같이정의된다 [8] : (4) 여기서 와 는각각 번째반복복호에서 식 (1) 또는 (2) 와같은메시지업데이트함수에의 한업데이트전후메시지값이다. 직관적으로, 업데이트전후의메시지값의차이가 572

논문 /LDPC 부호를위한복잡도와대기시간을낮춘 VCRBP 알고리즘 0에가깝다는것은그메시지가거의수렴되었다고 볼수있다. 반대로큰레지듀얼값을갖는메시지 는전체부호그래프에서아직수렴하지않은부분 을나타낸다고볼수있다. 따라서가장큰레지듀 얼값을갖는메시지를먼저업데이트하는것은전 체부호가더욱빠르게복호될수있도록해준다 [8]. RBP 기법은 LDPC 부호의복호에다양한형태 로적용될수있다 [9][10][11][12]. VCRBP 복호는이중 가장좋은성능을보이며 NVCRBP 복호는보다낮 은복잡도로거의근접한성능을보인다 [11][12]. 따라 서본논문에서는 NVCRBP 복호에대해서만다룬 다. VCRBP 복호는선택된에지에대응되는하나의 변수- 체크메시지를업데이트하는반면, NVCRBP 복호는선택된변수노드에대응되는모든변수 -체크 메시지들을동시에업데이트한다. 이러한점에서 NVCRBP 복호는 SBP 복호와유사하다. 주요차이 점은 SBP 복호는미리정해진순서에의하여변수 노드를순차적으로업데이트하는반면 NVCRBP 복호는레지듀얼에근거하여다음업데이트될변수 노드를동적으로선택한다는점이다. NVCRBP 복 호알고리즘의자세한과정이알고리즘 1에표현되 어있다. 알고리즘 1 NVCRBP 복호알고리즘 [12] 1: 모든 로, 로초기화 2: 모든 을비교 3: 가장큰 에대응되는 를선택 4: for 모든 5: 로정함 6: for 모든 7: 8: for 모든 9: 10: 를계산 11: end for 12: end for 13: end for 14: if 정지조건이만족되지않으면 then 15: 2번째줄로돌아감 16: end if 2.3 복호복잡도와대기시간 지금까지의동적스케줄링복호알고리즘을다룬 표 1. 근사복호복잡도 BP NRBP NVCRBP 매반복복호시 의연산횟수 1 그림 1 에서의실제사용된값 1 (6.33-1)(3.17-1)+1 12.57 6.33-1=5.33 근사복호복잡도 = 최대반복복호횟수 100 8 12.57 100 19 5.33 101 의연산횟수 그림 1. BP, NRBP, NVCRBP 복호의프레임오류율성능비교 ( 각각최대반복횟수 100, 8, 19 회사용 ) 논문들은오직같은반복복호내에서복호알고리즘들의성능을비교하였다. 그러나 RBP 복호알고리즘과 VCRBP 복호알고리즘은표준 BP 복호알고리즘에비해추가적으로레지듀얼을계산하고그값을서로비교해야하므로일회반복복호내에서더많은복잡도와대기시간을필요로한다. 따라서우리는실제같은복잡도내에서 BP, NRBP, NVCRBP 복호알고리즘의성능을비교분석하고자한다. 표 1은일회반복복호내에서근사복잡도를보여준다. LDPC 부호의복호복잡도의대부분을체크 -변수메시지연산이차지하므로일회반복복호내에서체크 -변수메시지의연산횟수를통해근사복잡도를구한다. 여기서 와 는각각변수노드와체크노드의평균디그리 (degree), 즉, 에지로연결된이웃노드의평균개수를말한다. 또한이를통해실제부호의근사복잡도를구하고같은근사복잡도를갖기위한반복복호횟수의비율을구하였다. 그림 1는표 1에의해산출된근사복호복잡도에근거하여같은복잡도내에서 BP, NRBP, 573

한국통신학회논문지 '09-06 Vol. 34 No. 6 NVCRBP 복호알고리즘의성능을비교한것이다. 이를통해 NRBP 복호는같은반복복호횟수에서 는 BP 복호알고리즘보다나은성능을보이지만 같은복잡도내에서는나은성능을보장하지못함을알수있다. 반면 NVCRBP 복호는같은반복복호횟수에서뿐만아니라같은복잡도내에서도탁월한성능을보임을확인할수있다. Ⅲ. 감소된복호복잡도와대기시간을갖는 NVCRBP 복호알고리즘 3.1. FC-NVCRBP 복호알고리즘강제수렴기법은매우작은횟수의반복복호내에서많은수의변수노드들이높은신뢰도로수렴한다는점을이용하여복호복잡도를낮추는기법이다. 즉, 이러한변수노드들은이미높은신뢰도로복호되었으므로그들의메시지값을남은반복복호내에서업데이트하지않는다. 이전의논문들 [15][16][17] 에서는메시지값의크기로수렴여부를판단하였다. 또한수렴되었다고판단된메시지를남은반복복호내에서특정값으로고정하였다. 이로인해만약고정된메시지가오류값을가졌다면전체부호가복호되는데심각한악영향을끼치게된다. 따라서우리는메시지의수렴판단값으로레지듀얼을사용한 FC-NVCRBP 복호알고리즘을제안한다. 만약어떤메시지의레지듀얼이실험적상수값 보다작다면그메시지를수렴되었다고판단하고남은반복복호내에서가아닌현재반복복호에서만업데이트및비교대상에서제외시킨다. 이를통해불필요한연산량과비교대상을줄임으로써복호복잡도뿐만아니라대기시간도감소시킬수있다. 알고리즘 2는 FC-NVCRBP 복호의상세과정이다. 그런데 는실험적인값이기때문에목표로하는성능을얻기위하여얼마나큰 를설정해야하는지예측하기는쉽지않다. 그러므로우리는근사 FC-NVCRBP 복호알고리즘을다음과같이제안한다. 다수의실험결과에서많은수의메시지들이반복복호동안전체복호에크게영향을미치지않는굉장히작은레지듀얼값을갖는다. 따라서우리는충분히큰레지듀얼값을갖는일부의메시지들만을사용하여, 즉, 실제복호에사용되는메시지의양을조절하여더낮은복잡도로전체메시지를사용했을때의성능에거의근접한성능을얻을수 있다. 게다가사용할메시지의양을매반복복호시조절하여성능은유지하면서더욱복호복잡도를낮출수있다. 알고리즘 2 FC-NVCRBP 복호알고리즘 1: 모든 로, 로초기화 2: 모든 을비교 3: 가장큰 에대응되는 를선택 4: for 모든 5: 로정함 6: for 모든 7: 8: for 모든 9: 10: 를계산 11: end for 12: end for 13: end for 14: if 정지조건이만족되지않으면 then 15: 2번째줄로돌아감 16: end if 3.2 S-NVCRBP 복호알고리즘 NVCRBP 복호와 FC-NVCRBP 복호는정적스케줄링복호방식들에비하여탁월한성능을보이지만레지듀얼을계산하고그값의크기에따라정렬해야하는추가적인연산이필요하다. 따라서이러한단점을최소화하기위하여새로운동적스케줄링복호기법인 S-NVCRBP 복호알고리즘을제안한다. 알고리즘을간략화하기위하여다음과같은새로운정렬기준값인 를다음과같이정의한다 : (5) 여기서 와 는각각 번째반복복호에서 업데이트전후의메시지값을말한다. 가양수 값을가지면, 가음수값을가지 면 로정한다. 만약어떤에지에서 이면그에지에대응되는메시지값이 업데이트후에부호가반전되었음을의미하고 이면그에지에대응되는메시지값이 업데이트후에부호가반전되지않았음을의미한다. S-NVCRBP 복호는 가음수인메시지를 574

논문 /LDPC 부호를위한복잡도와대기시간을낮춘 VCRBP 알고리즘 포함하는변수노드를먼저업데이트한다. 이는부 호가반전되는메시지는높은확률로큰레지듀얼을갖는다는점으로미루어볼때타당하다. 만일더이상 가음수인메시지가없으면미리정해진순서에의해나머지변수노드들을업데이트한다. 본논문에서는미리정해진순서로변수노드디그리의내림차순정렬을사용하였다. 따라서일회반복복호내에모든변수노드들이한번씩업데이트된다. S-NVCRBP 복호알고리즘의상세과정이알고리즘 3에표현되어있다. 알고리즘 3 S-NVCRBP 복호알고리즘 1: 모든 로, 로초기화 2: 이되는 를선택 3: for 모든 4: 로정함 5: for 모든 6: 7: for 모든 8: 9: 를계산 10: end for 11: end for 12: end for 13: if 정지조건이만족되지않으면 then 14: 2번째줄로돌아감 15: end if S-NVCRBP 복호는모든레지듀얼값을계산할필요가없을뿐더러레지듀얼값을서로비교하지않아도된다. 그러므로 S-NVCRBP 복호는 NVCRBP 복호의탁월한성능은유지하면서복잡도와대기시간을현저히감소시킬수있다. 그림 2에서최대 8번반복복호하에서 FC- NVCRBP 복호가 NRBP 복호보다절반이하의낮은복잡도와대기시간으로더나은성능을보인다. 또한 S-NVCRBP 복호역시복잡도와대기시간을현저히줄이면서 NVCRBP 복호에매우근접한성능을보인다. 그림 3은신호대잡음비 (SNR) 을 2.5dB로고정하고반복복호횟수를최대 50회까지증가시키면서오류정정성능을확인한것이다. 이를통하여 FC-NVCRBP 복호와 S-NVCRBP 복호는작은반복복호횟수에서뿐만아니라많은반복복호후에도 NVCRBP 복호에비하여낮은복잡도와대기시간으로근접한성능을보임을확인할수있다. 그림 2. BP, LBP, NRBP, FC-NVCRBP (1/2), S-NVCRBP, NVCRBP 복호의 SNR에따른프레임오류율성능비교 ( 최대반복횟수 8회사용 ) Ⅳ. 실험결과 모의실험은 IEEE 802.16e 표준 [18] 에설계된다양한 LDPC 부호를사용하였다. AWGN 채널을가정하고, 부호길이는 576, 1152, 2304 그리고부호율은 1/2, 3/4 각각에대하여실험하였다. 실험결과모든부호에서유사한형태를보이므로부호길이 576, 부호율 1/2의결과만보이도록하겠다. 또한 FC-NVCRBP 복호는앞에서정의한근사 FC-NVCRBP 복호를적용하였으며매반복복호시전체노드의절반만을사용하였다. 그림 3. BP, LBP, NRBP, FC-NVCRBP (1/2), S-NVCRBP, NVCRBP 복호의반복횟수에따른프레임오류율성능비교 (SNR 2.5dB로고정 ) 575

한국통신학회논문지 '09-06 Vol. 34 No. 6 Ⅴ. 결론 NVCRBP 복호알고리즘의복잡도와대기시간을줄이기위하여 FC-NVCRBP 복호알고리즘과 S-NVCRBP 복호알고리즘을제안하였다. 실험결과제안하는두알고리즘모두작은반복복호횟수에서뿐만아니라적당히큰반복복호횟수에서도 NVCRBP 복호알고리즘보다낮은복잡도와대기시간으로거의근접한성능을보였다. 참고문헌 [1] R. G. Gallager, Low density parity check codes, MIT press, 1963. [2] J. Zhang and M. Fossorier, Shuffled belief propagation decoding, IEEE Trans. on Comm., 53:209-213, February, 2005. [3] M. Rovini, F. Rossi, P. Ciao, N. L Insalata, and L. Fanucci, Layered Decoding of Non-Layered LDPC Codes, In Proc. 9th EUROMICRO Conference on Digital System Design, pages 537-544, August, 2006. [4] Zhang, J., Wang, Y., Fossorier, M., and Yedidia, J.S., Replica Shuffled Iterative Decoding, IEEE ISIT 2005, pages 454-458, September, 2005. [5] Junsheng Han, Siegel, P. H., lee P., Lin jia-ru, improvement of Shuffled Iterative Decoding, IEEE ITW 2006, Chengdu, China, October, 2006. [6] Zhiyong He, Sebastien Roy, and Paul Fortier, Lowering error floor of LDPC codes using a joint row-column decoding algorithm, ICC 2007, Glasgow, Ecosse, 24-28 june, 2007. [7] Oren Golov and Ofer Amrani, Edge-based Scheduled BP in LDPC Codes, ISIT2007, Nice, France, 24-29 June, 2007 [8] G. Elidan, I. McGraw, and D. Koller, Residual belief propagation: informed scheduling for asynchronous message passing, In Proc. 22nd Conference on Uncertainty in Artificial Intelligence, MIT, Cambridge, MA, July, 2006. [9] A. I. Vila Casa, M. Griot, and R. D. Wesel, Informed Dynamic Scheduling for Belief- Propagation Decoding of LDPC Codes, In Proc. IEEE ICC 2007, Glasgow, Scotland, June, 2007. [10] A. I. Vila Casa, M. Griot, and R. D. Wesel, Improving LDPC Decoders via Informed Dynamic Scheduling, IEEE Information Theory Workshop 2007, Lake Tahoe, CA, September, 2007. [11] Jung-Hyun Kim, Mi-Young Nam, and Hong-Yeop Song, Variable-to-Check Residual Belief Propagation for LDPC Codes, IEE Electronic Letters, vol. 45, no. 2, pages 117-118, January 2009. [12] Jung-Hyun Kim, Mi-Young Nam and Hong-Yeop Song, Variable-to-Check Residual Belief Propagation for Informed Dynamic Scheduling of LDPC Codes, ISITA 2008, The Langham Hotel, Auckland, New Zealand, December 7-10, 2008. [13] J. Li and X. D. Zhang, Reduced-complexity belief propagation decoding for low-density parity-check codes, IEE Electronic Letters, vol. 44, no. 3, pages 220-222, January 2008. [14] Eleftheriou, E., Mittelholzer, T., and Dholakia, A., Reduced-complexity decoding algorithm for low-density parity-check codes, IEE Electronic Letters, vol. 37, no. 2, pages 102-104, January 2001. [15] E. Zimmermann, P. Pattisapu, P. K. Bora, and G. Fettweis, Reduced Complexity LDPC Decoding using Forced Convergence, in Proceedings of the 7th International Symposium on Wireless Personal Multimedia Communications (WPMC04), Abano Terme, Italy, pages 12-15, September, 2004. [16] E. Zimmermann, W. Rave, and G. Fettweis, Forced Convergence Decoding of LDPC Codes - EXIT Chart Analysis and Combination with Node Complexity Reduction Techniques, in Proceedings of the 11th European Wireless Conference (EW 2005), Nicosia, Cyprus, pages 11-13, April, 2005. [17] E. Zimmermann, P. Pattisapu, and G. Fettweis, Bit-Flipping Post-Processing for Forced Convergence Decoding of LDPC Codes, in Proceedings of the 13th European Signal Processing Conference (EUSIPCO'05), Antalya, Turkey, pages 04-08, September, 2005. [18] IEEE C802.16e-05/0066r3, LDPC coding for OFDMA PHY. 576

논문 /LDPC 부호를위한복잡도와대기시간을낮춘 VCRBP 알고리즘 김정현 (Jung-Hyun Kim) 준회원 2006년 8월연세대학교전기전자공학부졸업 2008년 8월연세대학교전기전자공학부석사 2009년 3월 ~ 현재연세대학교전기전자공학부연구원 < 관심분야 > Error Correcting Codes, Network Coding 송홍엽 (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 577