논문 14-39C-08-03 The Journal of Korea Information and Communications Society '14-08 Vol.39C No.08 http://dx.doi.org/10.7840/kics.2014.39c.8.637 블록저밀도패리티검사부호설계를위한테너그래프기반의저복잡도순환주기탐색알고리즘 명세창, 전기준 *, 고병훈 *, 이성로 **, 김광순 Tanner Graph Based Low Complexity Cycle Search Algorithm for Design of Block LDPC Codes Se Chang Myung, Ki Jun Jeon *, Byung hoon Ko *, Seong Ro Lee **, Kwang Soon Kim 요 약 본논문은블록 LDPC(low density parity check) 부호설계를위한순환천이값 (shift index) 을탐색하는효율적인알고리즘을제안한다. 여기에는메시지- 패싱 (message-passing) 기반의순환주기 (cycle) 탐색알고리즘과 ACE(approximate cycle extrinsic message degree) 알고리즘이결합되어있다. LDPC 부호성능에영향을미치는요인들에우선순위를두어효율적으로순환천이값을찾을수있도록했다. 이알고리즘을통해기존의탐색알고리즘보다훨씬낮은복잡도로행렬저장공간을절약하면서좋은성능의패리티검사행렬 (parity check matrix) 을만들수있다. Key Words : block LDPC code, shift index, cycle search algorithm, maritime satellite communication, low complexity ABSTRACT In this paper, we propose a efficient shift index searching algorithm for design of the block LDPC codes. It is combined with the message-passing based cycle search algorithm and ACE algorithm. We can determine the shift indices by ordering of priority factors which are effect on the LDPC code performance. Using this algorithm, we can construct the LDPC codes with low complexity compare to trellis-based search algorithm and save the memory for storing the parity check matrix. Ⅰ. 서론 해양위성통신은바다에서선박과육상, 선박과선박사이에정보교환이나위치추적, 긴급의료지원 등에사용되는중요한통신수단이다. 지상통신서비스를받기어려운해양에서는신뢰도높은통신채널을확보하는것이중요하다. Gallager가 LDPC 부호를제안한이래로 [1] LDPC 부호는뛰어난비트오 이논문은 2013 년도정부 ( 미래창조과학부 ) 의재원으로한국연구재단의지원을받아수행된연구임 (NRF-2011-0029321) 본연구는미래창조과학부및정보통신산업진흥원의 IT 융합고급인력과정지원사업의연구결과로수행되었음 (NIPA-2014-H0401-14-1009) First Author : The department of Electrical and Electronic Engineering, Yonsei University, myungse@yonsei.ac.kr, 학생회원 Corresponding Author : The department of Electrical and Electronic Engineering, Yonsei University, ks.kim@yonsei.ac.kr, 종신회원 * 연세대학교전기전자공학부 puco201@yonsei.ac.kr, bhko@yonsei.ac.kr, 학생회원 ** 목포대학교정보전자공학과 srlee@mokpo.ac.kr, 정회원논문번호 :KICS2014-04-151, Received April 30, 2014; Revised August, 8, 2014; Accepted August 8, 2014 637
The Journal of Korea Information and Communications Society '14-08 Vol.39C No.08 류율 (bit error rate) 과병렬처리 (parallel processing) 에의한효율적인인코딩 (encoding) 이가능한장점때문에수많은연구들이진행되어왔다. 또한낮은디코딩복잡도를갖기때문에현재해양위성통신에서사용되는 DVB-S2 표준부호에도사용되고있다 [2]. 더불어멀티미디어기반해상통신등에도응용이가능하고최근여러분야에서터보코드를대체하는오류정정부호로주목받고있다 [3]. LDPC 부호의성능은패리티검사행렬을어떻게구성하느냐에달려있다. 이상적으로무한한블록길이에순환주기가없다고가정한 LDPC 부호의성능은샤논한계 (Shannon limit) 에가깝다 [4]. 하지만실제유한한블록길이를갖는테너그래프 (Tanner graph) 에서는순환주기가존재하기때문에심각한성능저하가발생한다. 따라서좋은성능의 LDPC 부호설계를위해서는패리티검사행렬에서순환주기를탐색하여성능저하를발생시키는순환주기들을미리제거해주는것이필요하다. 특히짧은길이의순환주기는 LDPC 부호의폭포영역 (waterfall region) 에큰영향을미치고, 순환주기가어떻게구성되어있는지에대한연결성 (connetivity) 은오류- 마루 (error-floor) 에영향을미친다 [5]. 또한최근안테나와 MCS(modulation and coding scheme) 의증가로부호어 (codeword) 의길이가길어지면서길이가긴순환주기의고려가중요해졌다. 그런데기존의트렐리스 (trellis) 순환주기탐색알고리즘 [6] 은긴길이의순환주기를찾기엔복잡도가높고메시지 -패싱기반의순환주기탐색알고리즘 [7] 은복잡도는낮지만이진단계 (binary level) 의순환주기탐색만가능한한계가있다. 본논문은순환천이행렬과패리티검사행렬의관계 [8] 를활용하여블록단계 (block level) 에서모든길이의순환주기탐색이가능한낮은복잡도의알고리즘을제안한다. 이알고리즘은메시지 -패싱기반의순환주기탐색알고리즘 [9] 과 ACE 알고리즘을결합된형태로패리티검사행렬전체를저장하지않아도되기때문에행렬저장공간또한절약할수있다. 이알고리즘을활용하면순환주기들의길이뿐만아니라개수와 ACE값들까지고려하여최적의폭포영역과오류- 마루특성을갖는 LDPC 부호설계를효율적으로할수있다. 본론에서는 1) 제안하는탐색알고리즘을예제와함께간단하게설명하고 2) 같은크기로확장 (Lifting) 했을경우에기존의순환주기탐색알고리즘과제안하는알고리즘의계산복잡도를비교하여제안하는알고리즘의효율성을보였다. Ⅱ. 본론 2.1 제안하는순환주기탐색알고리즘순환주기탐색은 [7] 에서와같이테너그래프에서변형된메시지 -패싱알고리즘을사용한다. 0 과 1 을메시지로변수노드 (variable node) 와검사노드 (check node) 가엣지 (edge) 를통해서로메시지 (message) 를주고받으면서시작노드에연결된한엣지출발한메시지가다시시작노드로돌아오면순환주기가형성된다. [8] 은순환천이값을원소로갖는특성행렬을정의하고이특성행렬과패리티검사행렬간의관계를이용하여블록단계에서패리티검사행렬순환주기를탐색할수있다. [9] 는위두논문을결합한형태로블록단계의특성행렬에서주어진패리티검사행렬의모든길이의순환주기와개수를탐색할수있다. 본논문은여기에 [5] 에서제시한 ACE 알고리즘을결합하여패리티검사행렬의모든순환주기의길이 그림 1. 제안하는탐색알고리즘의예제 Fig. 1. Example of the proposed search algorithm 638
논문 / 블록저밀도패리티검사부호설계를위한테너그래프기반의저복잡도순환주기탐색알고리즘 와개수, ACE값탐색할수있는알고리즘을제안한다. 성능에더큰영향을주는요인을고려하여최적의순환천이값을결정한다. 블록단계에서모든순환주기탐색이가능키때문에행렬저장공간을절약할수있고메시지- 패싱알고리즘을사용하기때문에계산복잡도를크게줄이면서빠르고효율적으로 LDPC 부호설계가가능하다. 그림 1에서검은색숫자는메시지를, 소괄호안의빨간색숫자는교차합값을그리고대괄호안의파란색숫자는 ACE 값을의미한다. 여기서 ACE 값 는아래와같이정의한다. (1) 여기서 는 번째변수노드에연결된엣지의수 (degree) 를의미한다. 부호워드의길이와확장 (lifting) 값이정해지면순환천이값의범위가정해진다. 이범위내에서후보순환천이값들을바꿔가며반복적으로탐색한다. 각순환천이값들로부터다양한길이, 개수그리고 ACE 값을갖는순환주기를찾을수있고크게아래 3가지경우로분류할수있다. (i) 길이가서로다른복수의순환주기 (ii) 길이가같고개수가다른복수의순환주기 (iii) 길이와개수가같고 ACE값이다른복수의순환주기 LDPC부호성능에더큰영향을미치는요인을고려하여우선순위를매기게되는데첫번째경우에는순환주기의길이가긴것, 두번째로길이가같다면개수가적은것, 세번째로길이와개수가같다면 ACE값이큰순환천이값을택한다. 2.2 기존순환주기탐색알고리즘과의복잡도비교이절에서는간단한예제를통하여패리티검사행렬을구성하는방법을설명하고제안하는알고리즘을사용하여패리티검사행렬을구성했을때와기존알고리즘을사용했을때의계산복잡도를비교해본다. (2) (3) 식 (3) 는크기가 기본프로토그래프 (protograph) 를인접 (adjacent) 행렬로나타낸식 (2) 를 배확장하여만든 파생 (derived) 그래프를행렬로나타낸예제이다. 패리티검사행렬을만들기위해서는두번의확장 (lifting) 을수행해야하는데기본프로토그래프로부터인접행렬의행과열사이의연결정도조건을만족하는위치후보들의모든조합들을고려하고이와동시에순환주기탐색을반복적으로수행하여 1의위치를결정한다. 2차확장은파생그래프의해당 1의위치에 길이의순환행렬을이용한다. 두번의확장수행에서제안하는알고리즘을활용하여순환주기의길이가길고개수가적으며큰 ACE값을갖는순환천이값을선택한다. 패리티검사행렬을구성하고자할때아래세가지경우에대해계산복잡도를비교해보자. 1) 이진 PEG(progressive edge growth) 와 [7] 의 MP (message-passing) 알고리즘을사용할때 2) 블록 PEG와 [8] 의블록연산식과결합된트렐리스 (trellis) 순환주기탐색방법을사용할때 3) 본논문에서제안하는알고리즘을사용할때먼저블록행렬의크기와패리티검사행렬의크기를각각, 으로두었을때, 2) 와 3) 의 1의위치후보수는 이고 1) 은 이다. 여기서 는열의평균연결정도이고 는확장값이다. 길이의순환주기탐색을위해 번의반복혹은깊이 까지탐색할때후보 1의위치마다필요한연산횟수는 1) 의경우 정도이고 3) 은 이다. 그리고변수노드와검사노드의연결정도를각각 와 로가정하면 2) 는 의후보경로를검사해야한다. 또한 1) 에서비트하나의논리연산과비교하여 [8] 의블록연산식에필요한정수연산은 개의논리연산과비슷하고후보경로들의순환천이값연산에필요한연산횟수와이로부터패리티검사행렬의순환주기를계산하는데필요한연산횟수는 2) 639
The Journal of Korea Information and Communications Society '14-08 Vol.39C No.08, 3), 이다. 따라서최종적인비트논리연산횟 수로따진계산복잡도는아래와같다. 1) 2) 3) Ⅲ. 모의실험결과 이장에서는주어진프로토그래프로부터제안한알고리즘을사용해실제패리티검사행렬을구성했을때부호의성능과기존의알고리즘과의계산복잡도차이를모의실험으로보인다. 그림 2의예제프로토그래프로부터코드워드길이 16200 및 360 비트당블록병렬처리를위해서부호율 의경우는 으로 1차, 2차확장을수행하고 의경우는 으로 1차, 2차확장을수행한다. 그림 3은그림 2의프로토그래프를제안하는알고리즘을사용하여패리티검사행렬을구성했을때의 BER/FER 그래프로좋은폭포영역과오류 -마루특성을갖는다. 이결과는 BPSK 변조를사용하고수신단에서 SPA 기반최대반복횟수 100번이하에서복호수행시얻어지는비트오류확률및프레임오류확률에대한모의실험결과로프레임오류개수 200개에서의성능그래프이다. 표 1은그림 2의프로토그래프로부터얻은파생그래프를 으로 2차확장하여패리티검사행렬을구성할때필요한계산복잡도이다. 그림 4는그림 2의부호율 프로토그래프로부터패리티검사행렬을구성할때앞에서언급한세가지알고리즘을각각사용하여확장값 에따른계산복잡도를구해본것이다. 그래프로부터이진단계에서설계하는첫번째방법은 가커짐에따라서복잡도가점점증가하여가장복잡도가높고두번째트렐리스알고리즘은일정확장값이상이면이진단계설계보다유리하지만깊이 에따라복잡도차이가크게났다. 제안하는알고리즘은확장값이커져도상대적으로낮은계산복잡도를갖는것을확인할수있다. 이상의모의실험결과로부터제안하는알고리즘 표 1. 각알고리즘별비트연산횟수비교 Table 1. Comparison of the number of bit operations for each algorithm 그림 2. 부호율 1/3, 1/5 프로토그래프예제 Fig. 2. Example of the protograph with rate 1/3 and 1/5 Code rate Binary+MP Trellis+BL Proposed 5.1e+14 5.3e+11 1.3e+8 4.6e+14 2.8e+11 1.2e+8 10 0 Performance Comparison ER 10-1 10-2 10-3 10-4 10-5 BER (R=1/5) [Protograph Code] FER (R=1/5) [Protograph Code] BER (R=1/3) [Protograph Code] FER (R=1/3) [Protograph Code] The number of bit operation 10 16 10 14 10 12 10 10 L=6 L=12 Binary Trellis Proposed 10 8 10-6 10-7 -0.5 0 0.5 1 1.5 E b /N 0 (db) 10 6 0 50 100 150 200 250 300 350 Block size B 그림 3. 주어진프로토그래프의부호비트오류확률 / 프레임오류확률성능 Fig. 3. BER/FER performance of given protograph code 그림 4. 블록크기따른비트연산횟수의반로그그림 Fig. 4. Semilogarithmic plot of the number of bit operations as a function of block size 640
논문 / 블록저밀도패리티검사부호설계를위한테너그래프기반의저복잡도순환주기탐색알고리즘 이주어진프로토그래프로부터패리티검사행렬을구성할때낮은계산복잡도로순환주기탐색이가능하고부호성능에영향을미치는요인들을고려하여최적의순환천이값을결정하였기때문에좋은특성을가지는부호를낮은복잡도로설계가가능함을알수있다. Ⅳ. 결론본논문에서는해양위성통신에응용가능한블록 LDPC 부호설계를위한효율적인순환천이값탐색알고리즘을제안하였다. 간단한예제를통하여순환천이값결정방법과기존알고리즘대비제안하는알고리즘이갖는장점들에대해설명하였다. 또한주어진프로토그래프로부터기존의알고리즘을사용할때와제안하는알고리즘을사용하여패리티검사행렬을만들때의계산복잡도를비교하였다. 모의실험결과블록단계에서 LDPC 부호를설계함에있어서기존대비계산복잡도면에서이득을얻을수있는효율적인알고리즘임을보였고, 이를이용해성능이우수한 LDPC 부호를낮은복잡도로설계할수있음을보였다. irregular LDPC code construction, IEEE Trans. Commun., vol. 52, pp. 1242-1247, Aug. 2004. [6] Y. Mao and A. H. Banihashemi, A heuristic search for good low-density parity-check codes at short block lengths. in Proc. IEEE Int. Conf. Commun., vol. 1, pp. 11-14, Helsinki, Finland, Jun. 2001. [7] S. H. Lee, K. S. Kim, Y. H. Kim, and J. Y. Ahn, A cycle search algorithm based on a message-passing for the design of good LDPC codes, IEICE Trans. Fundam., vol. E88-A, no. 6, pp. 1955-1604, Jun. 2005. [8] K. S. Kim, S. H. Lee, Y. H. Kim, and J. Y. Ahn, Design of binary LDPC code using cyclic shift matrices, Electron. Lett., vol. 40, no. 5, pp. 325-326, Mar. 2004. [9] S. C. Myung, K. J. Jeon, B. H. Ko, K. J. Kim, and K. S. Kim, A cycle search algorithm for design of block LDPC codes, in Proc. KICS Winter Conf., pp. 850-851, Yongpyong, Korea, Jan. 2014. References [1] R. G. Gallager, Low-density parity check codes, IRE Trans. Inform. Theory, vol. 8, no. 1, pp. 21-28, Jan. 1962. [2] J. G. Ryu, D. G. Oh, and H. J. Yu, Design of maritime satellite communication systems sharing frequency with DVB-S2, J. Korea Soc. Comm. Space Tech.(KOSST), vol. 8, no. 4, pp. 75-80, Dec. 2013. [3] J. W. Jung, H. C. Kwon, Y. J. Kim, S. H. Park, and S. R. Lee, A study on high speed LDPC decoder algorithm based on DVB-S2 standard, J. KICS, vol. 38C, no. 03, pp. 311-317, Mar. 2013. [4] T. Richardson, M. Shokrollahi, and R. Urbanke, Design of capacity-approaching irregular low-density parity-check codes, IEEE Trans. Inf. Theory, vol. 47, no. 2, pp. 638-656, Feb. 2001. [5] T. Tian, C. R. Jones, J. D. Villasenor, and R. D. Wesel, Selective avoidance of cycles in 명세창 (Se Chang Myung) 2013년 2월 : 연세대학교전기전자공학부공학사 2013년 3월 ~ 현재 : 연세대학교전기전자공학부석사과정 < 관심분야 > 통신이론, LDPC, 채널코딩전기준 (Ki Jun Jeon) 2008년 2월 : 경희대학교전기전자공학과공학사 2010년 2월 : 연세대학교전기전자공학과석사 2010년 3월 ~ 현재 : 연세대학교전자공학과박사과정 < 관심분야 > 정보이론, 소스- 채널코딩, 영상코딩 641
The Journal of Korea Information and Communications Society '14-08 Vol.39C No.08 고병훈 (Byung hoon Ko) 2006년 8월 : 연세대학교전기전자공학부졸업 ( 공학사 ) 2007년 2월 ~ 현재 : 연세대학교전기전자공학과석박사통합과정 < 관심분야 > 애드혹멀티캐스트네트워크, 계층간최적화이성로 (Seong Ro Lee) 1987년 2월 : 고려대학교전자공학과공학사 1990년 2월 : 한국과학기술원전기및전자공학과공학석사 1996년 8월 : 한국과학기술원전기및전자공학과공학박사 1997년 9월 ~ 현재목포대학교공과대학정보전자공학과교수 < 관심분야 > 디지털통신시스템, 이동및위성통신시스템, USN/ 텔레미틱스응용분야, 임베디드시스템, 생체인식시스템 김광순 (Kwang Soon Kim) 1994년 2월 : 한국과학기술원전기전산학과공학사 ( 최우등 ) 1996년 2월 : 한국과학기술원전기전산학과공학석사 1999년 2월 : 한국과학기술원전기전산학과공학박사 1999년 3월 ~2000년 3월 :UC San Diego 박사후연구원 2000년 4월 ~2004년 2월 : ETRI 책임연구원 2004년 3월 ~2009년 2월 : 연세대학교전기전자공학부조교수 2009년 3월 ~ 현재 : 연세대학교전기전자공학부부교수 < 관심분야 > 통신이론, 코딩이론, LDPC부호설계, 하이브리드빔형성기, 신호검출이론, 이종셀방식네트워크, D2D 네트워크 642