DBPIA-NURIMEDIA

Similar documents
Sequences with Low Correlation

DBPIA-NURIMEDIA

DBPIA-NURIMEDIA

DBPIA-NURIMEDIA

DBPIA-NURIMEDIA

±è±¤¼ø Ãâ·Â-1

38

DBPIA-NURIMEDIA

DBPIA-NURIMEDIA

DBPIA-NURIMEDIA

DBPIA-NURIMEDIA

DBPIA-NURIMEDIA

DBPIA-NURIMEDIA

완벽한개념정립 _ 행렬의참, 거짓 수학전문가 NAMU 선생 1. 행렬의참, 거짓개념정리 1. 교환법칙과관련한내용, 는항상성립하지만 는항상성립하지는않는다. < 참인명제 > (1),, (2) ( ) 인경우에는 가성립한다.,,, (3) 다음과같은관계식을만족하는두행렬 A,B에

DBPIA-NURIMEDIA

<333520B0ADBCBAC1F82D46534DC0BB20C0CCBFEBC7D120BCF6C1A4B5C820C0AFC5ACB8AEB5E520BECBB0EDB8AEC1F220BCB3B0E82E687770>

THE JOURNAL OF KOREAN INSTITUTE OF ELECTROMAGNETIC ENGINEERING AND SCIENCE Jun.; 27(6),

DBPIA-NURIMEDIA

°í¼®ÁÖ Ãâ·Â

DBPIA-NURIMEDIA

(JBE Vol. 21, No. 1, January 2016) (Regular Paper) 21 1, (JBE Vol. 21, No. 1, January 2016) ISSN 228

DBPIA-NURIMEDIA

example code are examined in this stage The low pressure pressurizer reactor trip module of the Plant Protection System was programmed as subject for

DBPIA-NURIMEDIA

Microsoft PowerPoint - 26.pptx

THE JOURNAL OF KOREAN INSTITUTE OF ELECTROMAGNETIC ENGINEERING AND SCIENCE. vol. 29, no. 10, Oct ,,. 0.5 %.., cm mm FR4 (ε r =4.4)

07변성우_ok.hwp

8-VSB (Vestigial Sideband Modulation)., (Carrier Phase Offset, CPO) (Timing Frequency Offset),. VSB, 8-PAM(pulse amplitude modulation,, ) DC 1.25V, [2

04 Çмú_±â¼ú±â»ç

Microsoft PowerPoint Relations.pptx

Gray level 변환 및 Arithmetic 연산을 사용한 영상 개선

THE JOURNAL OF KOREAN INSTITUTE OF ELECTROMAGNETIC ENGINEERING AND SCIENCE Feb.; 29(2), IS

¼º¿øÁø Ãâ·Â-1

<333220B1E8C1F8BFB52DB0A1BDC3B1A420C5EBBDC520BDC3BDBAC5DBC0BB20C0A7C7D120B9DDBAB920BAB9C8A320BECBB0EDB8AEC1F22E687770>

본 강의에 들어가기 전

57

THE JOURNAL OF KOREAN INSTITUTE OF ELECTROMAGNETIC ENGINEERING AND SCIENCE Dec.; 25(12),

45-51 ¹Ú¼ø¸¸

DBPIA-NURIMEDIA

THE JOURNAL OF KOREAN INSTITUTE OF ELECTROMAGNETIC ENGINEERING AND SCIENCE Dec.; 27(12),

DBPIA-NURIMEDIA

DBPIA-NURIMEDIA

DBPIA-NURIMEDIA

05 목차(페이지 1,2).hwp

DBPIA-NURIMEDIA

THE JOURNAL OF KOREAN INSTITUTE OF ELECTROMAGNETIC ENGINEERING AND SCIENCE Nov.; 26(11),

DBPIA-NURIMEDIA

DBPIA-NURIMEDIA

04-다시_고속철도61~80p

지능정보연구제 16 권제 1 호 2010 년 3 월 (pp.71~92),.,.,., Support Vector Machines,,., KOSPI200.,. * 지능정보연구제 16 권제 1 호 2010 년 3 월

<333820B1E8C8AFBFEB2D5A B8A620C0CCBFEBC7D120BDC7BFDC20C0A7C4A1C3DFC1A42E687770>

½Éº´È¿ Ãâ·Â

Á¶Áø¼º Ãâ·Â-1

2 : (JEM) QTBT (Yong-Uk Yoon et al.: A Fast Decision Method of Quadtree plus Binary Tree (QTBT) Depth in JEM) (Special Paper) 22 5, (JBE Vol. 2

Deep-Space 광통신을위한터보부호화변조기법 오상목ㅇ, 황인호, 이정우중앙대학교전자전기공학부 A Turbo-Coded Modulation Scheme for Deep-Space Optical Communications Sangmok Oh ㅇ, Inho Hwang,

V. 통신망 기술

09권오설_ok.hwp

DBPIA-NURIMEDIA

I

878 Yu Kim, Dongjae Kim 지막 용량수준까지도 멈춤 규칙이 만족되지 않아 시행이 종료되지 않는 경우에는 MTD의 추정이 불가 능하다는 단점이 있다. 최근 이 SM방법의 단점을 보완하기 위해 O Quigley 등 (1990)이 제안한 CRM(Continu

±è¼ºÃ¶ Ãâ·Â-1

오류정정부호의응용편집위원 : 송홍엽 ( 연세대 ) NAND Flash 메모리저장장치에서의 Error Control Code 응용 이기준, 이명규, 신범규, 공준진 삼성전자 요약 NAND flash 메모리의집적도를높이기위한주요기술로, 데이터가저장되는 cell 자체의크기를

슬라이드 1

PowerPoint 프레젠테이션

학습영역의 Taxonomy에 기초한 CD-ROM Title의 효과분석

???? 1

Chap 6: Graphs

이 장에서 사용되는 MATLAB 명령어들은 비교적 복잡하므로 MATLAB 창에서 명령어를 직접 입력하지 않고 확장자가 m 인 text 파일을 작성하여 실행을 한다

6.24-9년 6월

THE JOURNAL OF KOREAN INSTITUTE OF ELECTROMAGNETIC ENGINEERING AND SCIENCE Nov.; 28(11),

sna-node-ties

DBPIA-NURIMEDIA

<3031B0ADB9CEB1B82E687770>

3.2 함수의정의 Theorem 6 함수 f : X Y 와 Y W 인집합 W 에대하여 f : X W 는함수이다. Proof. f : X Y 가함수이므로 f X Y 이고, Y W 이므로 f X W 이므로 F0이만족된다. 함수의정의 F1, F2은 f : X Y 가함수이므로

DBPIA-NURIMEDIA

THE JOURNAL OF KOREAN INSTITUTE OF ELECTROMAGNETIC ENGINEERING AND SCIENCE May; 27(5),

a), b), c), b) Distributed Video Coding Based on Selective Block Encoding Using Feedback of Motion Information Jin-soo Kim a), Jae-Gon Kim b), Kwang-d

에너지경제연구 제13권 제1호

그룹웨어와 XXXXX 제목 예제

LDPC(Low Density Parity Check) 16 & 32 (APSK, Amplitude and Phase- Shift Keying) DVB-S2 30% [1]. DVB-S2 (SNR, Signal to Noise Ratio), (Offset). DVB-S2

1 경영학을 위한 수학 Final Exam 2015/12/12(토) 13:00-15:00 풀이과정을 모두 명시하시오. 정리를 사용할 경우 명시하시오. 1. (각 6점) 다음 적분을 구하시오 Z 1 4 Z 1 (x + 1) dx (a) 1 (x 1)4 dx 1 Solut

., 3D HDTV. 3D HDTV,, 2 (TTA) [] 3D HDTV,,, /. (RAPA) 3DTV [2] 3DTV, 3DTV, DB(, / ), 3DTV. ATSC (Advanced Television Systems Committee) 8-VSB (8-Vesti

High Resolution Disparity Map Generation Using TOF Depth Camera In this paper, we propose a high-resolution disparity map generation method using a lo

저작자표시 - 비영리 - 변경금지 2.0 대한민국 이용자는아래의조건을따르는경우에한하여자유롭게 이저작물을복제, 배포, 전송, 전시, 공연및방송할수있습니다. 다음과같은조건을따라야합니다 : 저작자표시. 귀하는원저작자를표시하여야합니다. 비영리. 귀하는이저작물을영리목적으로이용할

untitled

1 : HEVC Rough Mode Decision (Ji Hun Jang et al.: Down Sampling for Fast Rough Mode Decision for a Hardware-based HEVC Intra-frame encoder) (Special P

<313920C0CCB1E2BFF82E687770>

THE JOURNAL OF KOREAN INSTITUTE OF ELECTROMAGNETIC ENGINEERING AND SCIENCE. vol. 26, no. 9, Sep GHz 10 W Doherty. [4]. Doherty. Doherty, C

Microsoft Word - 1-차우창.doc


데이터베이스-4부0816

2002 Game White paper 2002 Game White paper

03이승호_ok.hwp

에너지경제연구 Korean Energy Economic Review Volume 11, Number 2, September 2012 : pp. 1~26 실물옵션을이용한해상풍력실증단지 사업의경제성평가 1

¹Ìµå¹Ì3Â÷Àμâ

Microsoft PowerPoint - 알고리즘_5주차_1차시.pptx

,. 3D 2D 3D. 3D. 3D.. 3D 90. Ross. Ross [1]. T. Okino MTD(modified time difference) [2], Y. Matsumoto (motion parallax) [3]. [4], [5,6,7,8] D/3

THE JOURNAL OF KOREAN INSTITUTE OF ELECTROMAGNETIC ENGINEERING AND SCIENCE. vol. 26, no. 3, Mar (NFC: non-foster Circuit).,. (non-foster match

<3130C0E5>

DBPIA-NURIMEDIA

Transcription:

논문 06-31-12C-03 한국통신학회논문지 06-12 Vol.31 No.12C IEEE 802.16e 표준에제시된 LDPC 부호의수렴속도개선을위한복호방법 정회원장민호 *, 신범규 *, 박우명 *, 종신회원노종선 *, 정회원전인산 ** Decoding Method of LDPC Codes in IEEE 802.16e Standards for Improving the Convergence Speed Min-Ho Jang*, Beom-Kyu Shin*, Woo-Myoung Park* Regular Members, Jong-Seon No* Lifelong Member, In-San Jeon** Regular Member 요 약 본논문에서는체크노드분할을이용한변형된반복복호방법 [8] 을 IEEE 802.16e 표준에서제시된 low-density parity-check(ldpc) 부호에적용하여복호의수렴속도개선을확인한다. 또한 IEEE 802.16e에서제시된 LDPC 부호에가장적합한체크노드분할방법을제안한다. 수렴속도개선은반복횟수를줄일수있다는의미에서계산복잡도를감소시킬수있다. 이러한체크노드분할을이용한복호방법은복호기의하드웨어구현이병렬처리방식으로구현되기어려운시스템에서효과적인직렬처리방식으로적용될수있다. 제시된 LDPC 부호의변형된반복복호방법은무선통신시스템환경의실제복호기를구현하는데사용될수있다. Key Words : IEEE 802.16e standards, Iterative decoding, Convergence speed, Check node partitioning, Low-density parity-check (LDPC) codes ABSTRACT In this paper, the modified iterative decoding algorithm[8] by partitioning check nodes is applied to low-density parity-check(ldpc) codes in IEEE 802.16e standards, which gives us the improvement for convergence speed of decoding. Also, the new method of check node partitioning which is suitable for decoding of the LDPC codes in IEEE 802.16e system is proposed. The improvement of convergence speed in decoding reduces the number of iterations and thus the computational complexity of the decoder. The decoding method by partitioning check nodes can be applied to the LDPC codes whose decoder cannot be implemented in the fully parallel processing as an efficient sequential processing method. The modified iterative decoding method of LDPC codes using the proposed check node partitioning method can be used to implement the practical decoder in the wireless communication systems. Ⅰ. 서론 1960 년대에 Gallager [1] 에의하여제안된 low- density parity-check(ldpc) 부호는다양한채널에대하여 Shannon의이론적인한계에근접하는우수한복호성능을보인다. 또한패리티검사행렬의 본연구는교육인적자원부, 산업자원부, 노동부의출연금으로수행한최우수실험실지원사업과 BK21, 그리고정보통신부의출연금으로수행한한국전자통신연구원과제의연구결과입니다. * 서울대학교전기 컴퓨터공학부부호및암호연구실 ({mhjang, thechi, ppakoo}@ccl.snu.ac.kr, jsno@snu.ac.kr) ** 한국전자통신연구원 SoC 설계연구부 (isjeon@etri.re.kr) 논문번호 KICS2006-04-162, 접수일자 2006 년 4 월 6 일, 최종논문접수일자 2006 년 12 월 1 일 1143

한국통신학회논문지 06-12 Vol.31 No.12C 저밀도성에기인한확률기반반복복호의구현이최근비약적인하드웨어기술의발전에힘입어상대적으로용이해지면서 LDPC 부호는적어도지난십여년간오류정정부호분야의중요한연구주제로주목받았다. 실제로 LDPC 부호는통신, 방송, 저장매체등다양한분야에서표준으로제안되어사용되고있다. 현재 LDPC 부호에관련된다양한연구는크게효율적인부호화가가능한부호의설계방법과복잡도감소를위한복호방법으로집약될수있다. LDPC 부호의가장큰단점이었던부호화과정에서복잡도가큰문제점을해결하려는노력의일환으로, 효율적으로부호화가가능한 LDPC 부호를설계하기위하여 protograph 부호 [2] 의개념을이용하여유한길이를갖는블록형태로 LDPC 부호가정의되었다. 최근 IEEE 802.16e 시스템 [3] 에채택된 LDPC 부호도이러한방식으로효율적인부호화가가능하도록설계되었다. 대표적인 LDPC 부호의복호방법으로 belief propagation(bp) 반복복호알고리즘 [4][5] 과 min-sum 반복복호알고리즘 [6] 이있다. 반복복호과정은 Tanner [7] 그래프를이용하여도식적으로이해할수있다. 하지만이러한복호방법에서신뢰할만한정보를복원하기위해서는계산복잡도가커지게되므로구현상제한요인이될수있다. 그러므로복호과정에서계산의복잡도를감소시킬수있다는의미에서성능의수렴속도를개선하는새로운방법이필요하다. 본논문에서는체크노드분할을이용한변형된반복복호방법 [8] 을 IEEE 802.16e 표준에제시된 LDPC 부호에적용하여성능의수렴속도개선을확인한다. 또한 IEEE 802.16e 시스템에제시된 LDPC 부호에가장적합한체크노드분할방법을제안한다. 이러한체크노드분할을이용한복호방법은복호기의하드웨어구현이병렬처리방식으로구현되기어려운시스템에서효과적인직렬처리방식으로적용될수있다. LDPC 부호의변형된반복복호방법은무선통신시스템에서실제복호기를구현하는데사용될수있다. Ⅱ. LDPC 부호의기존복호방법들 2.1 BP 반복복호방법반복복호방법 [5][6] 은 LDPC 부호의그래프를구성하는변수노드와체크노드가메시지를반복 적으로교환하는일련의갱신연산을통하여오류를정정하는알고리즘이다. 이과정을설명하기전에널리사용되고있는몇가지표기법에대하여살펴보자. 은변수노드 에이웃한체크노드의집합을나타내고, 은체크노드 에이웃한변수노드의집합을나타낸다. 그리고 \ 은 에서변수노드 을제외한집합을의미한다. 또한 와 은각각심볼 이 0이거나 1일확률을나타내는변수 ( 심볼 ) 노드 에서체크노드 으로의메시지를의미한다. 유사하게 와 은각각심볼 이 0이거나 1일확률을나타내는체크노드 에서변수노드 으로의메시지를의미한다. 이표기법을바탕으로 LLRs (log-likelihood ratios) 메시지 와 을정의한다. 여기서송신부호어와수신부호어를각각 와 로나타내었다. BP 반복복호방법은구체적으로다음과같이설명할수있다. 우선각각의변수노드 에서이와인접한모든체크노드로 LLRs 메시지 를전달한다. 편의상초기에변수노드에수신된메시지의 LLRs 값을사용하였다. 이제본격적인반복복호과정을시작한다. 각각의 과 에대하여아래수식의체크노드갱신연산을수행한다. \ (1) 연속적으로각각의 에대하여아래수식의변수노드갱신연산을수행한다. (2) \ 수식 (1) 과 (2) 의과정을반복적으로적용하여메시지를교환함으로써오류를정정할수있게된다. 2.2 Min-sum 근사화준최적성능에도달하는복잡도감소를위한복호방법의일환으로체크노드갱신연산을단순화시키는데초점을맞춘 min-sum 근사화방법 [6] 이있다. 이알고리즘은기본적으로 BP 반복복호방법과그과정이거의동일하다. 유일한차이는수식 1144

논문 / IEEE 802.16e 표준에제시된 LDPC 부호의수렴속도개선을위한복호방법 (1) 의체크노드갱신연산 을다음과같이간단하게근사화하여적용한다는점이다. \ \ (3) 수식 (1) 과 (3) 을비교해보면, 두연산은같은부호를가지지만 의크기가 의크기보다항상더크다는사실을알수있다. 이를통하여보다정확한갱신메시지값을얻어내기위하여 의크기를줄여주는추가적인처리과정이필요하다는것을알수있다. 다음의두가지방법이체크노드갱신메시지를개선하기위하여채택되었다. 첫번째방법은 1보다작은정규화상수 를사용하여다음수식과같이체크노드갱신을개선한다. 편의를위하여, 변형된복호알고리즘에서체크노드가 개의부분집합으로분할된다고가정하자. 그러면모든변수노드에서첫번째부분집합내의체크노드들로향하는메시지들이갱신되고, 뒤를이어첫번째부분집합내의체크노드들에서이웃한변수노드들로메시지들이갱신된다. 이과정이체크노드들로구성되어있는첫번째부분집합에대하여한번의반복에해당한다. 이제남아있는 개의체크노드부분집합에대하여동일한과정을연속적으로적용한다. 이과정이 개의부분집합에대하여모두수행되면복호의한번의반복이완료된다. 다시말해서, 한번의반복은모든변수노드들과체크노드들로구성되어있는모든부분집합들에대한직렬메시지갱신과전달을의미한다. 그러므로직렬메시지전달복호알고리즘에서한번의반복에대한계산량은명백히기존의복호알고리즘의계산량과동일하다. \ (4) \ 두번째방법은양의오프셋상수 를사용하여다음수식과같이체크노드갱신을개선한다. \ (5) \ 개선된 min-sum 근사화복호방법은수식 (1) 대신에각각수식 (4) 와 (5) 를이용하여체크노드갱신연산을수행하여메시지를교환하게된다. 이때변수노드갱신연산은수식 (2) 와같이 BP 반복복호에서와동일하게적용된다. (a) 에서복호 (Decoding in ) Ⅲ. 수렴속도개선을위한복호방법 3.1 수렴속도개선을위한복호알고리즘수렴속도개선을위한변형된메시지전달반복복호알고리즘 [8] 에대하여살펴보자. 기존의반복복호알고리즘에서각각의반복은두단계로세분화할수있다. 그것은모든변수노드에서메시지를갱신하여각각의체크노드로전달되는과정과모든체크노드에서메시지를갱신하여각각의변수노드로전달되는과정으로이루어진다. 이때각과정에서모든연산은동시에수행된다. (b) 에서복호 (Decoding in ) 그림 1. 가 2 일때부호길이가 8 인 (2,4) 규칙부호의 1 회반복복호의과정 (Decoding procedure of a (2,4) regular code with length 8 in one iteration, where ) 1145

한국통신학회논문지 06-12 Vol.31 No.12C 그림 1은 일때부호길이가 8인 (2, 4) 규칙부호에대한변형된반복복호방법 [8] 의한번의반복복호과정을보여준다. 여기서원과정사각형은각각변수노드와체크노드를나타내며, 각각의변수노드윗부분에표시한화살표들은채널을통과한초기메시지들을의미한다. 또한,, 는체크노드의 -번째부분집합을나타낸다. 그림 1(b) 에서변수노드에서두번째부분집합내의체크노드들로전달되는메시지들은그림 1(a) 에서와같이이미첫번째체크노드부분집합으로부터갱신되어그변수노드로들어오는메시지들을이용하여갱신된다. 3.2 체크노드분할방법앞서설명한복호알고리즘에서체크노드부분집합을어떻게설정할지에따라서성능의수렴속도가영향을받는다. 여기서는복호시수렴속도를개선하기위한효율적인체크노드분할방법에대하여설명한다. 가장단순한방법은체크노드의부분집합들에속하는노드의개수가모두동일하도록체크노드를앞에서부터순차적으로나누는것이다. 이를순차분할 (sequential partitioning) 이라고부른다. 우리는효율적인체크노드분할방법으로비중복분할 (non-repetition partitioning) 방법을제안한다. LDPC 부호의패리티검사행렬에서행치환은부호자체의특성을바꾸지않는다. 그러므로패리티검사행렬의행순서는임의로교환이가능하다. 이사실을이용하여다음의체크노드부분집합의분할기준에따라원래의부호와동일한특성을갖는패리티검사행렬을생성할수있다. 체크노드분할기준은행들로구성된동일한체크노드부분집합내에서, 각각의열이한개이하의 1 성분을포함하도록분할하는것이다. 즉, 어떠한체크노드부분집합에속한선 (edge) 들에의하여연결된변수노드들이그체크노드부분집합에두개이상연결되지않도록분할하는방법이다. 이때각각의체크노드부분집합내의체크노드의개수가동일할필요는없으며, 구현의편의를위하여분할기준을만족하면서가능한적은수의체크노드부분집합을가지도록설정한다. 이러한체크노드분할기준을설정한이유에대하여살펴보자. 동일한반복횟수에대하여, 어떤체크노드부분집합에속해있는체크노드로부터 변수노드로갱신한메시지는연속적으로그변수노드에서다른부분집합에속해있는체크노드로갱신된메시지를보내게된다. 새로운복호알고리즘에서이갱신된메시지가성능의수렴속도를개선하는요인이라고할수있다. 그러므로동일한반복횟수에대하여가능한많은갱신메시지가 LDPC 부호에대응하는그래프를따라서전파되기위해서체크노드부분집합에속한선에의하여연결된각각의변수노드들이그체크노드부분집합에한개의선만연결되도록분할기준을설정하는것이최적이라는사실을알수있다. Ⅳ. 모의실험결과및분석 이장에서체크노드분할을이용한변형된반복복호방법을 IEEE 802.16e 표준 [3] 에제시된 LDPC 부호에적용하여성능의수렴속도개선을확인한다. 모의실험은 additive white Gaussian noise(awgn) 채널환경에서최대반복횟수를 50번으로제한하여수행하였다. 그림 2는 IEEE 802.16e 표준에제시된부호율 1/2인 LDPC 부호에대하여 protograph 부호의개념을이용하여블록형태로정의된패리티검사행렬을나타낸다. 이동값이표기된각각의블록은 항등행렬 (identity matrix) 을그값만큼우순환이동 (circular right shift) 시킨행렬을의미하고, 빈블록은 영행렬을나타낸다. 그러므로이동값이 0인각블록은 항등행렬을나타낸다. 결국 IEEE 802.16e 표준에제시된바와같이, 값에따라이동값을재조정하는규칙을적용하여다양한부호길이를갖는 LDPC 부호를정의할수있다. 이상의 LDPC 부호에체크노드부분집합의개수가 6인순차분할을적용할경우, 그림 2의 행렬에서 (1,2), (3,4), (5,6), (7,8), (9,10), (11,12)-번째행에해당하는모든체크노드를각각 그림 2. IEEE 802.16e 표준에제시된부호율 1/2 인 LDPC 부호의패리티검사행렬 (Parity-check matrix of LDPC codes with rate 1/2 in IEEE 802.16e standards) 1146

논문 / IEEE 802.16e 표준에 제시된 LDPC 부호의 수렴 속도 개선을 위한 복호 방법 의 부분 집합으로 설정하여 순차적으로 새로운 복호 알고리즘을 수행한다. 또한 보다 수렴 속도를 개선하 기 위하여 비중복 분할 방법을 적용하여 체크 노드를 =1152 (체크 노드의 최대 개수)를 갖는 순차 분할 방법의 성능에 접근하면서도 6개의 체크 노드 부분 집합만을 갖는 비중복 분할 방법이 성능과 구현 측 나누어보자. 이는 그림 2의 행렬에서 (1,10), (2,11), (3,5), (4,6), (7,9), (8,12)-번째 행에 대응하는 모든 체크 노드를 각각의 부분 집합으로 설정하면 된다. 면에서 가장 적합하다. 이제 비중복 분할 방법을 이용하여 체크 노드를 분할한 변형된 복호 알고리즘을 IEEE 802.16e 표준 우선 체크 노드 분할 방법으로 제시한 순차 분할 과 비중복 분할을 적용한 새로운 복호 방법의 성능 결과를 비교해 보자. 그림 3은 부호율이 1/2이고 길 에 제시된 다양한 길이와 부호율을 갖는 LDPC 부 호에 적용하여 성능의 수렴 속도 개선을 확인해보자. 이때 BP 알고리즘을 기반으로 하는 수식 (1)의 체크 이가 2304인 LDPC 부호에 대하여 체크 노드 부분 집합의 개수 를 1(기존 BP), 2, 6으로 설정하여 순 차 분할을 이용한 방법과 비중복 분할을 이용한 방 노드 갱신 연산을 사용한다. 그림 4, 5, 6은 다양한 부호 길이에 대하여 각각 부호율이 1/2, 2/3A, 그리 고 3/4A인 LDPC 부호의 FER 성능 결과를 나타낸 법의 frame error rate (FER) 성능을 보여준다. 순차 분할의 경우 가 커질수록 수렴 속도가 개 선되는 것을 확인할 수 있다. 하지만 가 커질 경우 다. 부호율이 2/3A와 3/4A인 경우, 비중복 분할 방 법에 의하여 체크 노드 부분 집합들은 각 부호율에 서 블록 형태로 정의된 패리티 검사 행렬의 각각의 latency 문제로 실제적 구현이 어렵다. 그러므로 행 블록에 대응된다. 그림 3. 부호율이 1/2이고 길이가 2304인 LDPC 부호에 대 한 순차 분할과 비중복 분할 방법을 적용하였을 때, 각 반복 횟수에 따른 FER 성능 (The FER Performance for LDPC codes with rate 1/2 and length 2304 according to iterations applying sequential and non-repetition partitioning) 그림 4. 부호율이 1/2인 부호에 체크 노드 분할을 이용한 복 호 방법을 적용하였을 때, 각 반복 횟수에 따른 FER 성능 modified decoding method by partitioning check nodes to rate 1/2 codes) 그림 5. 부호율이 2/3인 A부호에 체크 노드 분할을 이용한 복호 방법을 적용하였을 때, 각 반복 횟수에 따른 FER 성능 modified decoding method by partitioning check nodes to rate 2/3A codes) 그림 6. 부호율이 3/4인 A부호에 체크 노드 분할을 이용한 복호 방법을 적용하였을 때, 각 반복 횟수에 따른 FER 성능 modified decoding method by partitioning check nodes to rate 3/4A codes) 1147

한국통신학회논문지 06-12 Vol.31 No.12C 표 1. Min-sum 근사화복호시최적의 와 값 (Optimum values of and in min-sum approximation decoding) Rate 1/2 0.83 0.43 Rate 2/3(A) 0.82 0.44 Rate 3/4(A) 0.76 0.46 그림 4, 5, 6으로부터모든부호율과길이에대하여체크노드분할을이용한복호방법의 25회반복의성능이기존복호방법의 50회반복의성능과유사함을확인할수있다. 두방법모두한번의반복에복호연산량이동일하기때문에, 동일한복호성능을보장하면서도연산의복잡도는절반정도줄어든다는사실을알수있다. 이상으로체크노드분할을이용하여 BP 알고리즘을기반으로변형된복호방법이 LDPC 부호의수렴속도를개선한다는사실을확인하였다. 다음으로 min-sum 근사화알고리즘을기반으로하는수식 (4) 혹은 (5) 의체크노드갱신연산을사용하여새로운복호방법의수렴속도개선을확인해보자. 비교대상으로각부호율에서 min-sum 근사화의성능결과를사용하기위하여전수모의실험을통하여최적의정규화상수 와오프셋상수 를결정하였다. ( 표 1) 표 1의최적의상수값 와 을사용한 Min-sum 근사화복호방법이수식 (4) 혹은 (5) 의비교적단순한체크노드갱신연산을이용하여계산복잡도를줄이는동시에성능측면에서도 BP와비교하여 0.1dB내로근접함을확인할수있었다. 특히최적의 와 값을선택한경우동일한부호율과길이의 LDPC 부호에서유사한성능을보였다. 이제최적의 값에의하여개선된 min-sum 근사화복호알고리즘에체크노드분할을이용한변형된복호방법을적용해보자. 이때체크노드분할은비중복분할방법을이용한다. 그림 7은부호율이 1/2인 LDPC 부호의 FER 성능을보여준다. 그림 7에서최적의 에의하여개선된 min-sum 근사화복호알고리즘에체크노드분할방법을적용한 25회반복의 FER 성능이기존최적의 값에의한 min-sum 근사화복호방법의 50회반복성능과거의유사함을확인할수있다. 이는 BP 알고리즘에체크노드분할을적용한방법과유사한수렴속도개선의경향성을보여준다. 결론적으로 BP 알고리즘과 min-sum 근사화알고리즘에공히비중복분할방법으로체크노드분할복호방법을적용하였을때, 성능의수렴속도가개선됨을알수있다. 그러므로동일한복호성능을보장하면서도복호과정에서연산의복잡도를절반가량줄일수있는장점을갖는다. Ⅴ. 결론본논문에서는 IEEE 802.16e 표준에서제시한효율적인부호화가가능한 LDPC 부호에대하여, 두가지대표적인 LDPC 부호의복호알고리즘 (BP 와 MSA) 을기반으로체크노드분할에의한새로운복호방법을적용하여수렴속도의개선을확인하였다. 그러므로적은반복으로동일한복호성능을보장할수있기때문에, 복호과정에서연산의복잡도를절반가량줄일수있는장점을갖는다. 또한 IEEE 802.16e 시스템에가장적합한체크노드분할방법으로비중복분할방법을제안하였다. 체크노드분할을이용한복호방법은복호기의하드웨어구현이완전하게병렬처리방식으로구현되기어려운시스템에서효과적인직렬처리방식으로고려될수있다. 이는실제무선통신시스템환경의복호기를구현하는데유용하게이용될수있을것이다. 참고문헌 그림 7. 부호율이 1/2 인 LDPC 부호에대하여최적의 에의하여개선된 min-sum 근사화복호알고리즘에체크노드분할방법을적용했을때, 각반복횟수에따른 FER 성능 modified MSA decoding method by partitioning check nodes to rate 1/2 LDPC codes) [1] R. G. Gallager, Low-Density Parity-Check Codes, Cambridge, MA: MIT Press, 1963. [2] J. Thorpe, Low-density parity-check (LDPC) codes constructed from protograph, IPN Progress Report, 42-154, JPL, Aug. 2003. 1148

논문 / IEEE 802.16e 표준에제시된 LDPC 부호의수렴속도개선을위한복호방법 [3] IEEE 802.16 Working Group, Part 16: Air interface for fixed and mobile broadband wireless access systems, IEEE P802.16e/D8, May 2005. [4] Frank R. Kschischang, Brendan J. Frey, and Hans-Andrea Loeliger, Factor graphs and the sum-product algorithm, IEEE Trans. Inform. Theory, vol. 47, no. 2, pp. 533-547, Feb. 2001. [5] T. J. Richardson and R. L. Urbanke, The capacity of low-density parity-check codes under message-passing decoding, IEEE Trans. Inform. Theory, vol. 47, no. 2, pp. 599-618, Feb. 2001. [6] J. Chen, A. Dholakia, E. Eleftheriou, M. P. C. Fossorier, and X. -Y Hu, Reduced-complexity decoding of LDPC codes, IEEE Trans. Commun., vol. 53, no. 8, pp. 1288-1299, Aug. 2005. [7] R. Tanner, A recursive approach to low complexity codes, IEEE Trans. Inform. Theory, vol. 27, no. 5, pp. 533-547, Sep. 1981. [8] Sunghwan Kim, Min-Ho Jang, Jong-Seon No, Song-Nam Hong, and Dong-Joon Shin, Sequential message passing decoding of LDPC codes by partitioning check nodes, submitted to IEEE Trans. Commun., Sep. 2004. 장민호 (Min-Ho Jang) 정회원 2002년 8월연세대학교기계 전자공학부전기전자공학전공공학사 2004년 8월서울대학교전기 컴퓨터공학부공학석사 2004년 9월 ~ 현재서울대학교전기 컴퓨터공학부박사과정 < 관심분야 > 디지털통신, 오류정정부호, LDPC 부호, OFDM 신범규 (Beom-Kyu Shin) 정회원 1999년 2월서울대학교전기공학부공학사 1999년 2월 ~2002년 1월 Locus 주식회사연구원 2002년 1월 ~2003년6월 Humax 주식회사전임연구원 2004년 3월 ~ 현재서울대학교전기 컴퓨터공학부석사박사통합과정 < 관심분야 > 오류정정부호, LDPC 부호, Iterative decoding 박우명 (Woo-Myoung Park) 준회원 2002년 2월서울대학교전기공학부공학사 2002년 3월 ~2003년 12월한국정보시스템연구원 2004년 1월 ~2005년 2월 Soft i-tech 연구원 2005년 3월 ~ 현재서울대학교전기 컴퓨터공학부석사과정 < 관심분야 > 오류정정부호, LDPC 부호, EXIT chart 노종선 (Jong-Seon No) 종신회원 1981년 2월서울대학교전자공학과공학사 1984년 2월서울대학교대학원전자공학과공학석사 1988년 5월 University of Southern California, 전기공학과공학박사 1988년 2월 ~1990년 7월 Hughes Network Systems, Senior MTS 1990년 9월 ~1999년 7월건국대학교전자공학과부교수 1999년 8월 ~ 현재서울대학교전기 컴퓨터공학부정교수 < 관심분야 > 오류정정부호, 의사불규칙수열, 암호학, 시공간부호, LDPC 부호, 무선통신시스템, OFDM 전인산 (In-San Jeon) 정회원 1984년 2월국민대학교전자공학과공학사 2000년 8월충남대학교대학원전자공학과공학석사 2006년 2월연세대학교전기전자공학과박사수료 1984년 3월 ~1990년 1월국방과학연구소연구원 1990년 2월 ~ 현재한국전자통신연구원책임연구원 < 관심분야 > VLSI, SoC/ESW, FEC/ 암호IC Design, 정보통신 SoC 1149