논문 6-31-1C-3 한국통신학회논문지 '6-1 Vol.31 No.1C 구조적 LDPC 부호의효율적인설계 준회원정비웅 * 정회원김준성 * 종신회원송홍엽 * Effcent Degn of Structured LDPC Code B-Woong Chung* Aocate Member Joon-Sung Km* Reguler Member Hong-Yeop Song* Lfelong Member 요 약 LDPC 부호의높은부호화복잡도는구조적인패리티검사행렬의설계로해결할수있다. 패리티검사행렬을같은유형의블록으로구성한다면복호화기의구현이간단해지고구조적복호화가가능하며 LDPC 부호를저장하는데필요한메모리를줄일수있는장점이있다. 본논문에서는부행렬단위의 grth 조건과 PEG 알고리즘 비트노드의 connectvty를이용하여부행렬이순환행렬이나영행렬로구성되는짧은길이를갖는구조적 LDPC 부호의생성알고리즘을제안하였다. 이알고리즘으로생성된부호는구조적제한이없이생성된부호에비하여낮은 SNR에서는비슷한성능을 높은 SNR에서는더좋은성능을내는것을모의실험을통해확인하였다. Key Word : LDPC code crculant permutaton matrx grth Progreve Edge Growth(PEG Approxmate Cycle EMD(ACE ABSTRACT The hgh encodng complexty of LDPC code can be olved by degnng tructured party-check matrx. If the party-check matrx of LDPC code compoed of ame type of block decoder mplementaton can be mple th tructure allow tructured decodng and requred memory for torng the party-check matrx can be reduced largely. In th paper we propoe a contructon algorthm for hort block length tructured LDPC code baed on grth condton PEG algorthm and varable node connectvty. The code degned by th algorthm how mlar performance to other code wthout tructured contrant n low SNR and better performance n hgh SNR than thoe by mulaton Ⅰ. 서론 LDPC 부호 (Low Denty Party Check code 는 1962년 Gallager에의해처음제안되었지만 Shannon lmt에근접하는뛰어난성능에도불구하고하드웨어기술력의제한으로오랫동안잊혀져오다가 1995년 Mackay와 Neal의재발견이후차세대통신시스템에쓰일부호로각광받으며활발한연구가이루어지고있다 [1 2]. LDPC 부호는생성방법에따라크게랜덤하게 생성된부호와블록단위의구조적부호로구분할수있다. 구조적부호는랜덤부호와는달리대수학적이거나기하학적인방법으로생성할수있다. IEEE 82.16e 시스템에적합한채널부호화방식으로연구되고있는 LDPC 부호들도대부분패리티검사행렬의열무게와행무게가 1인부행렬또는영행렬로구성된부호이며 Rchardon의부호화기법이나 Repeat-Accumulate 구조를이용한부호화기법을사용하는구조적 LDPC 부호이다 [3][4]. 이렇게구조적인방법으로생성된 LDPC 부호는부호화과정의 본연구는삼성종합기술원의 4G wrele ytem 의연구개발 과제의지원에의해이루어졌음. * 연세대학교전기전자공학과부호및정보이론연구실 ({bw.chung.km hy.ong}@codng.yone.ac.kr 논문번호 :KICS25-8-344 접수일자 :25 년 8 월 22 일 14 Copyrght (C 26 NurMeda Co. Ltd.
논문 / 구조적 LDPC 부호의효율적인설계 복잡도를줄일수있을뿐만아니라하나의행렬로부터부호율조정이나부행렬길이의변환이가능하다는장점을가지고있다. 또한실제구현시랜덤부호에비해단순하며메모리사용면에서도유리하다. 본논문에서는부행렬이단위행렬의순환행렬로구성되는구조적 LDPC 부호의패리티검사행렬을효과적으로생성하는기법을제안한다. 일반적으로사용되는짧은길이의균일 비균일 LDPC 부호를생성하고같은파라미터를갖고구조적제한이없는랜덤부호화의성능비교를통해제안하고있는구조적 LDPC 부호설계기법의효용성을보인다. Ⅱ. 패리티검사행렬구조 2.1 QC-LDPC 부호본논문에서생성하고자하는구조적 LDPC 부호는패리티검사행렬이단위행렬의순환행렬이나영행렬인작은길이의부행렬로구성되므로 Qua-cyclc LDPC 부호의일종이다. X를 N N 단위행렬을오른쪽으로한번 cyclc hft한순환행렬이라정하겠다. X = 1 1 1 1 (2-1 X 는단위행렬을 번 cyclc hft한순환행렬이고 X 는영행렬을나타낸다. 이표시방법을사용하면 LDPC 부호의패리티검사행렬 H 를다음과같이정의할수있다. H = X X 1 X 1 X ( n -1 X 1 X 1 ( n -1 X ( m - 1 1 X ( m - 1 ( n -1 X ( m - 1 (2-2 여기서 는 행 열에해당하는부행렬의 hftvalue를나타내고 {1 N -1 } 이다. H 는 m n 개의부행렬로이루어지기때문에 mn nn 의크기를가지며부호어의길이는 nn 부호율은 full-rank를가정하면다음과같다. R = nn -mn nn =1- m n (2-3 2.2 효과적인부호화알고리즘패리티검사행렬을다음과같이 6부분으로나누어설계하면 Rchardon의효율적인부호화기법을사용할수있다. H = [ A B T C D E ] (2-4 여기서 φ =-ET -1 B+D로정의하면다음의수식을이용하여패리티비트를얻을수있다. p T 1 =- φ -1 (-ET -1 A+Cu T p T 2 =-T -1 (Au T +Bp T 1 (2-5 더간단한부호화를위해 B T D E를 φ= I가되도록조정하면그림 1과같은부호화기를사용할수있다. Ⅲ. 구조적 LDPC 부호생성알고리즘 본논문에서제안하고있는구조적 LDPC 부호생성알고리즘은임의의파라미터 m 과 n 그리고부행렬의크기 N 에대하여주어진무게분포에따라성능이좋은 (mn (nn 패리티검사행렬 H 를만들수있다. 부행렬단위의 grth 조건과비트노드의 connectvty를기준으로하고무게가작은비트노드끼리의짧은 cycle을피하기위해비트노드의무게가작은부행렬부터생성을한다. u A C ET 1 그림 1. Rchardon 의부호화기구조 B T 1 u p 1 p 2 실제부행렬이들어갈위치는현재의그래프상에서연결할최선의 edge를결정하는 Progreve Edge Growth(PEG 알고리즘을사용하고주어진비트노드의무게분포로부터검사노드분포의균형을맞추는역할을한다 [5][6]. 비균일 LDPC 부호의경우 cycle 외에 connectvty라는조건이사용된다. 어떤비트노드의집합에연결된검사노드중이집합에하나의 edge로만연결된검사노드의수는 extrnc meage degree(emd 로정의된다. EMD를쉽게구하기위해 15 Copyrght (C 26 NurMeda Co. Ltd.
한국통신학회논문지 '6-1 Vol.31 No.1C 한 cycle안에포함된비트노드의무게를다음과같이더한값이 approxmate cycle EMD(ACE 이다 [7]. (d -2 (3-1 여기서는어떤비트노드에걸린 cycle안에포함된비트노드무게의합을이노드의 connectvty 라고정하겠다. 부호생성과정은다음과같다. 1 원하는부효율의최적화된무게분포를 denty evoluton을이용하여얻고 m 과 n 의크기에따라수정한다 [8]. 2 비균일 LDPC 부호의경우효과적인부호화가가능한구조로 H 의패리티부분을초기화한다. 3 PEG 알고리즘을이용하여영행렬이아닌부행렬이들어갈위치를결정한다. 4 3 에서결정된위치 ( 에대해 hft-value 를결정한다. 5 해당하는순환행렬을그래프상에추가시키고위치 (mn 까지 4 5 과정을반복한다. 과정 4 의 hft-value 를결정하는알고리즘은다음과같다. Inert ( 는위치 ( 에 X 를넣어 Tanner 그래프상에 N 개의 edge를연결시키는함수이고 Delete ( 는위치 ( 에있는부행렬을빼어 N 개의 edge를제거시키는함수이다. check-local-grth ( x 와 check-connectvty ( x 는각각현재의그래프상에서 x 번째비트노드의 cycle과 connectvty를구하는함수를의미한다 [9][1]. Decde begn f ele end = Inert ( cycle_p ACE( Delete ( for begn end _ tem p Inert ( k cycle_c ACE(k Update k = 1 to check - local - grth check - connectv ty ( _ tem p _ tem p N 1 check - local - grth check - connectv ty ( _ tem p ( N N ( N N 모든부행렬이영행렬이거나단위행렬의순환행렬이기때문에어떤하나의비트노드의 cycle과그노드가속한부행렬에포함된다른비트노드들의 cycle은같게된다. 이성질을이용하여각블록에서첫번째비트노드만을검사를하여조건에따라 hft-value를갱신하게되고조건은다음과같다. Update begn f ele f end cycle_c > cycle_p f cycle_um_ c delete ( Inert ( cycle_um_ p f cycle_p cycle_c delete ( _ temp ACE(k ACE( _ temp cycle_c = cycle_p cycle_um_ c _ temp k 1 l = _ temp k 1 l = _ temp check - local - grth ( l N check > cycle_um_ p - local - grth ( l N 현재 hft-value에해당하는부행렬이그래프상에서추가될경우의 cycle과 connectvty를구하여 cycle이크고 connectvty가크거나같으면현재값으로갱신하고 cycle이같으면현재까지생성된그래프상에서전체 cycle의합을비교하여갱신한다. 이방법은추가할부행렬의 cycle뿐만아니라이미결정된부행렬의 cycle까지고려하기때문에평균 local grth를높일수있고하나의 hft-value를결정하기위해가능한모든값을넣어검사를하지만 N 의비트노드중하나만을검사하기때문에 m 과 n의값이크지않으면알고리즘의복잡도는크지않게된다. 균일 LDPC 부호의생성일경우는 cycle이크다면 connectvty도크기때문에 connectvty 조건은빠지고비균일 LDPC 부호의경우는 cycle이크면서 connectvty가작은경우를배제하여높은 SNR 에서의성능을향상시킬수있다. Ⅳ. 모의실험결과및고찰 실험은가우시안 (AWGN 채널에서 SPA(um product algorthm 으로복호를하였으며최대반복횟수를 5 번으로제한시켰다. 본논문에서제안한알고리즘으로생성한 LDPC 부호는 Propoed LDPC 16 Copyrght (C 26 NurMeda Co. Ltd.
논문 / 구조적 LDPC 부호의효율적인설계 로표현을하였다. 4.1 균일 LDPC 부호 m =3 n =6 이고 N 는 167 과 334 로길이 12와 24 의부호율.5 균일 Propoed LDPC 부호와같은파라미터를갖는 Mackay의랜덤 LDPC 부호 PEG 부호를비교하였다 [9]. 표 1은 cycle 분포를나타내고있는데 Propoed LDPC 부호의 grth가두길이에서 1 으로 Mackay 부호보다높고 PEG 부호와비슷함을알수있다. 표 1. 부호율.5 균일 LDPC 부호의 cyclec 분포 length 12 24 code Mackay PEG Propoed Mackay PEG Propoed 1 Propoed 2 4-cycle 6-cycle 544 666 8-cycle 457 78 1313 1-cycle 1 94 12 25 24 24 24 본논문에서제안한생성알고리즘이효과적이라할수있다. 4.2 비균일 LDPC 부호비균일 Propoed LDPC 부호와같은파라미터를갖는 mproved PEG 부호의성능을비교하였다. 비트노드분포는다음과같고 λ( x =.2895x +.3158x 2 +.3947x 5 (4-1 m =12 n =24 N =24 48로길이 576 1152 부호에대해살펴보았다. 표 2는 cycle 분포를나타내는데 mproved PEG 부호와비슷한평균 local grth를보이고 grth는같다. 표 2. 부호율.5 비균일 LDPC 부호의 cycle 분포 length code 4-cycle 6-cycle 8-cycle 1-cycle 576 mpeg 68 58 Propoed 192 384 1152 mpeg 1148 4 Propoed 18 144 BER 1-1 Performance of rate-.5 regular LDPC Code 1-2 1-3 1-4 1-5 MacKay [12] PEG [12] 1-6 Propoed [12](3by6 MacKay [24] PEG [24] 1-7 Propoed [24](3by6 Propoed [24](6by12 1-8 1 1.2 1.4 1.6 1.8 2 2.2 2.4 2.6 2.8 3 Eb/No 그림 2. 부호율.5 균일 LDPC 부호성능 그림 2는부호율.5 인균일 LDPC 부호의성능을비교한결과이다. Propoed LDPC 부호의성능은높은 SNR에서 Mackay 부호보다좋고 PEG 부호와거의비슷한결과를보여준다. 길이 24 에서살펴보면 m =3 n =6인경우높은 SNR에서 PEG 부호보다약간성능이떨어지는데 m=6 n =12인경우는더좋은성능을보인다. 이것은전체길이에비해상대적으로부행렬의크기가크면무작위성이떨어지기때문이다. 짧은길이에서성능이좋은 PEG 부호보다구조적제한을두고생성한 Propoed LDPC 부호의성능이더좋으므로 그림 3과그림 4는각각길이 576 과 1152 의비균일 LDPC 부호의성능그래프이다. Improved PEG 알고리즘은짧은길이의비균일 LDPC 부호를 edge 단위로효과적으로생성하는기법으로낮은오류마루를갖는부호를만든다. Propoed LDPC 부호가높은 SNR에서성능을향상시킨 mproved PEG 부호와비교하여낮은 SNR에서는비슷한성능을 높은 SNR에서는더좋은성능을보이기때문에제안된알고리즘이구조적비균일 LDPC 부호의생성에도매우효과적임을알수있다. BER / FER 1 Performance of rate-.5 length 576 rregular LDPC Code 1-1 1-2 1-3 1-4 1-5 1-6 1-7 BER mpeg BER Propoed FER mpeg FER Propoed 1-8.5 1 1.5 2 2.5 3 3.5 Eb/No 그림 3. 부호율.5 길이 576 비균일 LDPC 부호성능 17 Copyrght (C 26 NurMeda Co. Ltd.
한국통신학회논문지 '6-1 Vol.31 No.1C BER / FER 1 Performance of rate-.5 length 1152 rregular LDPC Code 1-1 1-2 1-3 1-4 1-5 1-6 1-7 BER mpeg BER Propoed FER mpeg FER Propoed 1-8.5 1 1.5 2 2.5 3 Eb/No 그림 4. 부호율.5 길이 1152 비균일 LDPC 부호성능 Ⅴ. 결론 본논문에서는부행렬단위의구조적인균일 비균일 LDPC 부호를효과적으로생성하는알고리즘을제안하였다. 이알고리즘은다양한길이와부호율 무게분포에대해 grth가크고높은 SNR까지성능이뛰어난부호의설계를가능하게하여짧은길이의구조적 LDPC 부호를생성하는데효과적이다. 참고문헌 [1] R. G. Gallager Low-denty party-check code IRE Tran. Inform. Theory vol. IT-8 pp. 21-28 Jan. 1962. [2] D. J. C. MacKay R. M. Neal Near Shannon lmt performance of low-denty party-check code Electron. Lett. vol. 33 pp.457-458 Mar. 1997. [3] Thoma J. Rchardon and R. L. Urbanke Effcent Encodng of Low-Denty Party- Check Code IEEE Tran. IT vol. 47 pp. 638-656 Feb. 21. [4] Mchael Yang Degn of Effcently Encodable Moderate-Length Hgh-Rate Irregular LDPC Code IEEE Tran. comm Vol. 52. pp. 564-571 Aprl. 24. [5] X. Hu E. Eleftherou and D.-M. Arnold Progreve Edge-Growth Tanner Graph n IEEE GlobeCom vol. 2 pp. 995-11 Nov. 21. [6] Hua Xao and Amr H. Banhaem Improved Progreve-Edge-Growth(PEG Contructon of Irregular LDPC Code IEEE Tran. Commun. vol. 8 pp. 715-717 Dec. 24. [7] T. Tan C. Jone J. D. Vllaenor and R. D. Weel Selectve Avodance of Cycle n Irregular LDPC Code Contructon IEEE Tran. Commun vol. 52 pp. 1242-1247 Aug. 24. [8] T. Rchardon A. Shokrollah and R. Urbanke Degn of capacty-approachng rregular low-denty party-check code IEEE Tran. Inform. Theory vol. 47 pp. 619-637 Fer. 21. [9] Davd J. C. Mackay "Good error-correctng code baed on very pare matrce" IEEE Tran. IT vol. 45 pp. 399-431 Mar. 1999. [1] S. Ln L. Chen J. Xu and I. Durdevc Near Shannon lmt qua-cyclc low-denty party-check code IEEE Tran. Inform. Theory vol. 5 pp. 23-235 June. 23. [11] A. Ramamoorthy R. Weel Contructon of hort block length rregular low-denty party-check code IEEE Tran. Commun vol. 1 pp. 41-414 June. 24. 정비웅 (B-Woong Chung 준회원 24년 2월연세대학교전기전자공학과졸업 24년 3월 ~ 현재연세대학교전기전자공학과석사과정 < 관심분야 > Error Correctng Code PN Sequence LDPC Code 김준성 (Joon-Sung Km 정회원 21년 2월연세대학교전파공학과졸업 23년 2월연세대학교전기전자공학과석사 23년 3월 ~ 현재연세대학교전기전자공학과박사과정 < 관심분야 > Error Correctng Code PN Sequence LDPC Code 18 Copyrght (C 26 NurMeda Co. Ltd.
논문 / 구조적 LDPC 부호의효율적인설계 송홍엽 (Hong-Yeop Song 종신회원 1984년 2월연세대학교전자공학과졸업 1986년 5월 USC 대학원전자공학과석사 1991년 12월 USC 대학원전자공학과박사 1992년 ~1993년 Pot Doc. USC 전자공학과 1994년 ~1995년 Qualcomm Inc. 선임연구원 1995년 9월 ~ 현재연세대학교전기전자공학과교수 < 관심분야 > PN equence Error Correctng Code Spread Spectrum Communcaton Sytem Stream Cpher Sytem 19 Copyrght (C 26 NurMeda Co. Ltd.