비트 반전 알고리즘을 이용한 SSD의 오류 정정 부호 Error Control Coding for Solid-State Drive Using Bit-Flipping Algorithm

석 사 학 위 논 문 Master s Thesis 비트 반전 알고리즘을 이용한 SSD의 오류 정정 부호 Error Control Coding for Solid-State Drive Using Bit-Flipping Algorithm 강 동 협 ( 姜 棟 俠 Kang, Donghyub) 전기 및 전자공학과 Department of Electrical Engineering KAIST 2010

비트 반전 알고리즘을 이용한 SSD의 오류 정정 부호 Error Control Coding for Solid-State Drive Using Bit-Flipping Algorithm

Error Control Coding for Solid-State Drive Using Bit-Flipping Algorithm Advisor : Professor Jeongseok Ha by Kang, Donghyub Department of Electrical Engineering KAIST A thesis submitted to the faculty of the KAIST in partial fulfillment of the requirements for the degree of Master of Science in Engineering in the Department of Electrical Engineering Daejeon, Korea June 10, 2010 Approved by Professor Jeongseok Ha Advisor

비트 반전 알고리즘을 이용한 SSD의 오류 정정 부호 강 동 협 위 논문은 한국과학기술원 석사학위논문으로 학위논문심사 위원회에서 심사 통과하였음. 2010년 6월 10일 심사위원장 하 정 석 (인) 심사위원 박 현 철 (인) 심사위원 문 재 균 (인)

MEE 20084192 강 동 협. Kang, Donghyub. Error Control Coding for Solid-State Drive Using Bit-Flipping Algorithm. 비트 반전 알고리즘을 이용한 SSD의 오 류 정정 부호. Department of Electrical Engineering. 2010. 54p. Advisor Prof. Jeongseok Ha. Abstract For Solid-state Drive (SSD), conventional flash memories utilize simple error control codes such ad Hamming codes and RS code. In high density multilevel cell (MLC) flash memories, bit error rate (BER) will be poorer as the number of charge levels are incresed. Therefore, the conventional error control code is not sufficient for these memories. Low-density parity-check (LDPC) codes are a class of strong error control codes, and hence the LDPC codes are an important candidate for error control codes in MLC memories. For LDPC decoding, bit-flipping (BP) algorithms are much simpler algorithms that the sum-product algorithm (SPA) and min-sum algorithm (MSA). However, BF algorithm have the disavantages of poorer performances. There are many decoding methods based on BF in literature. The weighted bit-flipping (WBF) algorithm and the modified WBF (MWBF) attain better performance than the conventional BF algorithm with the cost of additional computation. An improved MWBF (IMWBF) and a reliability-ratio based WBF (RRWBF) algorithm further improve the decoding performance. Nevertheless, there still exist noticeable performance gaps between those algorithms and SPA and MSA. To increase the performance of BF algorithm, we propose a modified WBF altorithm, which estimates and updates the reliability of flipped bit. Even though a new algorithm needs additional calculations for weighting factor of flipping function, with considering of the average number of iteration, proposed i

algorithm achieves better performances than the conventional WBF algorithms. ii

목 차 Abstract................................... i 목 차.................................... iv 표 목 차................................... vi 그 림 목 차................................. vii 제 1 장 서 론 1 제 2 장 MLC 구조에서의 오류 정정 4 2.1 메모리 셀 구조............................ 4 2.2 MLC 구조에서의 오류 정정..................... 5 제 3 장 저밀도 패리티 검사 (LDPC) 부호 11 3.1 패리티 검사 행렬 (Parity Check Matrix).............. 12 3.2 LDPC 부호의 부호화 방법 (Encoding)............... 14 3.2.1 하삼각 행렬 부호화 기법................... 14 3.2.2 QC (Quasi-cyclic) LDPC 부호................ 15 제 4 장 LDPC 부호의 복호 알고리즘 19 4.1 합곱 (Sum-product) 알고리즘.................... 21 4.2 최소합 (min-sum) 알고리즘..................... 32 4.3 비트 반전 (Bit-flipping) 알고리즘.................. 34 4.4 신뢰도 추정 기반의 BF 알고리즘.................. 38 iv

목 차 제 5 장 실험 결과 41 5.1 실험 환경............................... 41 5.2 실험 결과............................... 41 제 6 장 결론 50 참 고 문 헌 52 v

표 목 차 5.1 성능 실험에 사용된 LDPC 부호.................... 41 vi

그 림 목 차 1.1 SSP (Storage Signal Processing)의 내부 구조 개념도........ 2 2.1 플래시 메모리 셀의 (a): 구조 (b) Program 상태 (c) Erase 상태.. 4 2.2 Q = 2 2 = 4일때의 V C G와 I D 의 관계.................. 5 2.3 4-PAM 신호의 AWGN 채널 통과 후 조건부 확률 분포도...... 6 2.4 소거사건이 발생한 경우 비트 오류율 대 평균 비트 오류율; ϵ = 0.1 8 2.5 NAND 플래시 메모리의 성능을 평가하기 위한 시스템 모형.... 9 2.6 두개의 BSC로 구성된 등가 채널 모형................. 9 3.1 태너 그래프의 예시........................... 13 3.2 하삼각 행렬 구조............................. 16 4.1 AWGN 채널에서의 태너 그래프.................... 20 4.2 H의 첫번째 열에 대응되는 서브 그래프................ 20 4.3 H의 첫번째 열에 대응되는 메시지 전달................ 21 4.4 H의 첫번째 행에 대응되는 서브 그래프................ 21 4.5 H의 첫번째 행에 대응되는 메시지 전달................ 22 4.6 검사 노드로부터 가변 노드로 신뢰도 전파.............. 27 4.7 가변 노드로부터 검사 노드로 신뢰도 전달.............. 28 4.8 Φ(x) 그래프................................ 33 vii

그 림 목 차 5.1 M1 부호의 비트 오류율 성능...................... 42 5.2 Q1 부호의 AWGN 채널에서의 비트 오류율 성능.......... 43 5.3 Q2 부호의 AWGN 채널에서의 비트 오류율 성능.......... 44 5.4 등가 채널 모델의 ϵ값의 최적화..................... 45 5.5 Q1 부호의 4-PAM 채널에서의 비트 오류율 성능: ϵ = 0.3...... 46 5.6 Q1 부호의 4-PAM 채널에서의 비트 오류율 성능: ϵ = 0.3...... 46 5.7 Q1 부호의 4-PAM 채널에서의 비트 오류율 성능:......... 47 5.8 Q1 부호의 AWGN 채널에서의 평균 반복 복호 횟수:........ 47 5.9 Q2 부호의 AWGN 채널에서의 평균 반복 복호 횟수:........ 48 5.10 Q1 부호의 4-PAM 채널에서의 평균 반복 복호 횟수:........ 48 5.11 Q2 부호의 4-PAM 채널에서의 평균 반복 복호 횟수:........ 49 viii

제 1 장 서 론 SSD (Solid-State Drive)는 NAND 플래시 메모리와 같은 solid-state 메모리를 이용하는 데이터 저장 장치이다. SSD는 기존 하드디스크 (Hard Disk Drive; HDD) 와 달리 기계적인 부분 없이 반도체 및 구동 회로로만 구성되기 때문에 자료의 입 출력 속도, 소모전력, 내충격성 등 다양한 측면에서 HDD에 비해 매우 매력적인 특성을 갖고있다. SSD는 HDD의 단점을 효과적으로 해결함으로써 기존 대용량 저장 장치를 대체하는 제품으로 자리매김하고 있다. 이런 SSD는 데이터를 저장하 는 NAND 플래시 메모리, 데이터 저장 및 인출을 관장하는 SSD 콘트롤러, 외부와 데이터 교환을 담당하는 호스트 인터페이스 (Host Interface), 그리고 NAND 플래 시에서 발생하는 오류를 정정하는 SSP (Storage Signal Processing)로 구성된다. NAND 플래쉬의 정보저장 밀도는 셀당 저장되는 비트수와 공정의 미세화 정 도에 의해 결정된다. 현재 상용화 되고 있는 MLC (Multi-Level Cell) NAND 소자 는 정보의 집적도 측면에서는 매우 우수한 성질을 지니고 있으나 정보 오류율 및 자료 신뢰성 측면에서는 많은 문제를 지니고 있다. 개별 셀 당 저장되는 비트수 가 증가함에 따라 소자의 오류율, 프로그램 속도 등이 악화되기 때문이다. 이처럼 저장 매체의 고밀도화 연구가 진행될수록 그에 대한 에러를 정정할 수 있는 에러 정정 부호의 연구가 필요하다. 40nm 이하 공정의 사용과 3비트 또는 4비트 MLC의 도입에 따라 SNR (signalto-noise ratio)이 감소하고 예측할 수 없는 간섭 신호가 증가하는 등 플래시 메모 리의 비트 오류 증가 문제가 심각해 지는 추세이다. 대부분의 저장 매체에서는 1

제 1 장 서 론 자체적으로 데이터를 보호하기 위하여 Reed-Solomon (RS) 부호를 사용한다. RS 부호의 경우 부호화와 복호화 과정에서 비교적 복잡한 계산 과정인 유한체 연산 (Galois Fields arithmetic)을 사용함으로 인해 큰 오버헤드를 가지고 있다. 반면 LDPC 부호는 비교적 단순한 XOR 연산을 이용해 큰 부하 없이 부호화와 복호를 하며 데이터 복구 능력 또한 뛰어나다. 또한, RS 부호는 큰 d min 에도 불구하고 밀도가 높은 패리티 검사 행렬의 구조를 갖기 때문에 강력한 신뢰 전파 (Belief Propagation) 복호 알고리즘을 쉽게 적용할 수 없다. 그렇기 때문에, 동일한 부 호 길이와 부호률에서 RS 부호와 비교하여 낮은 d min 값과 높은 오류마루를 갖는 LDPC 부호이지만, RS 부호의 연판정 복호보다 LDPC 부호의 반복 복호 방법이 채널 용량에 접근하는데 용이하다. Figure 1.1: SSP (Storage Signal Processing)의 내부 구조 개념도 SSP에 대한 연구는 신호처리 및 오류 정정 기법을 적용하여 MLC 구조로 인 한 NAND 플래시 의 신뢰성 악화 문제를 해결하는 부분이다. 보다 정교한 SSP 알고리즘을 개발하기 위해서는 크게 세가지를 고려해야 한다. 첫째, 정확한 채널 모델 (channel model)의 개발이다. SSP의 채널 모델은 알고리즘 분석과 개발이 가능하도록 통신식 입출력 모델이어야 하고 MLC NAND 플래시 소자의 특성을 정확히 반영하여야 한다. 두번째, 최적화된 신호 처리 알고리즘의 개발이다. 신호 처리 알고리즘은 NAND 플래시에서 출력된 신호를 일차적으로 처리하여 신호 대 2

제 1 장 서 론 잡음비을 극대화하고 간섭신호를 제어하는 역할을 한다. 세번째, 소자의 오류 특 성에 적합한 오류 정정 부호의 개발이다. ECC (error control coding)는 신호 처리 모듈의 출력 신호를 받아 오류를 제거하는 역할을 한다. 3

제 2 장 MLC 구조에서의 오류 정정 2.1 메모리 셀 구조 그림 (2.1)(a)는 제어 게이트 (control gate), 플로팅 게이트 (floating gate), 소 스 (source) 그리고 드레인 (drain)을 가지는 플래시 메모리 셀의 구조를 나타내 며, 플로팅 게이트는 제어 게이트와 회로 기판(substrate)로 부터 절연되어 있다. 제어 게이트에 높은 전압이 인가되면 셀은 programmed 되었다고 하고 회로 기 판에 높은 전압이 인가되면 셀은 erased 되었다고 한다. 그림 (2.1)(b) 와 (c)에 program/erase 동작을 도시하였다. 셀에서 데이터를 읽기 위해서는 제어 게이트 에 적당한 전압을 인가하여 플로팅 게이트의 전하 레벨을 확인해야 한다. 플로 팅 게이트의 전하 레벨이 낮은 경우에는 제어 게이트에 낮은 전압이 인가되어도 드레인과 소스 사이에 전류가 흐르고 전하 레벨이 높은 경우에는 제어 게이트에 충분히 높은 전압이 인가되어야 전류가 흐르기 때문이다. Figure 2.1: 플래시 메모리 셀의 (a): 구조 (b) Program 상태 (c) Erase 상태 4

제 2 장 MLC 구조에서의 오류 정정 2.2 MLC 구조에서의 오류 정정 SLC는 programmed 상태가 하나뿐인 경우로, 하나의 메모리 셀이 programmed 상태이면 전하가 모두 플로팅 게이트에 들어있고 논리 상태 0을 나타낸다. 반대로, erased 상태에서는 플로팅 게이트에서 전하가 모두 제거되고 이 때의 논리 상태는 1로 정의된다. MLC는 플로팅 게이트에 Q = 2 b 개의 전하 레벨을 이용하여 b개의 비트를 저장한다. 전하 레벨은 제어 게이트의 전압 V CG 와 드레인-소스 전류 I D 의 관계에 의해 확인된다. 그림 (2.2)에 Q = 2 2 = 4일때의 V CG 와 I D 의 관계를 도시 하였다. Figure 2.2: Q = 2 2 = 4일때의 V C G와 I D 의 관계 MLC에서는 하나의 셀에 다수의 정보를 저장함으로써 저장 밀도를 높일 수 있지만, 전하 레벨을 확인하기 위한 문턱 전압 V T H 의 간격이 조밀해지기 때문에 SLC에 비해서 오류의 발생 확률이 높아지게 된다. MLC 에서 이러한 오류들을 정정하기 위해서는 이를 표현하는 등가의 채널 모델이 필요하게 된다. Q 레벨의 MLC 셀에서 Q개의 전하 레벨은 각각 하나의 정수로 표현이 가능하고, 각 전하 레벨을 확인 할때의 문턱 전압의 확률 분포는 가우스 분포로 어림될 수 있다. 본 5

제 2 장 MLC 구조에서의 오류 정정 논문에서는 MLC 플래시 메모리의 출력 신호가 M-ary PAM (Pulse Amplitude Modulation) 신호의 형태를 가진다고 가정한다. M = 4 인 4-ary PAM 신호가 AWGN 채널을 통과하여 수신된 신호의 조건부 확률 분포 (conditional probability density function)을 그림 (2.3))에 나타내었다. Figure 2.3: 4-PAM 신호의 AWGN 채널 통과 후 조건부 확률 분포도 이 때 심벌 오류율 (symbol error rate)는 다음의 식과 같이 표현할 수 있다. P S E (SNR) = ( ) 2(M 1) 3 m Q M 2 1 SNR 또한, Gray 맵핑을 사용하는 경우 인접 심벌간의 비트 오류가 1비트 이므로, 비트 오류율 (bit error rate)는 다음과 같이 표현 할 수 있다. P B E (SNR) = 1 log 2 M ( ) 2(M 1) 3 m Q M 2 1 SNR 만일 MLC 플래시 메모리 소자가 읽은 전압 값이 판경 경계값 (τ i )에서 ±ϵ/2 에 있는 경우 (그림 (2.3)의 예에서 수신 신호값이 τ i ± ϵ/2 범위에 있는 경우) 소 자의 출력값은 경판정 값과 함께 판정 결과의 신뢰성이 떨어지는 것을 표현하는 이진 신호가 출력 된다고 가정하고 이러한 현상을 소거사건 (erasure event)으로 6

제 2 장 MLC 구조에서의 오류 정정 정의 한다. 메모리 소자에서 전압 값을 읽을 때 소거 사건이 발생할 확률은 다음과 같다. P ε (SNR) = 2(M 1) m ( ) ( ) 3(1 ϵ/2) 2 3(1 + ϵ/2) Q M 2 1 SNR 2 Q M 2 1 SNR 만일 소거 사건이 발생한 경우, 판정오류가 일어나는 조건부 확률을 표현하면 다음과 같다. = P (E ε) (SNR) = Pr(E ε) Pr(ε) Q(γ) Q(γ(1 + ϵ/2)) Q(γ(1 ϵ/2)) Q(γ(1 + ϵ/2)) 여기서 3/(M 2 1)SNR를 γ로 대체하였다. Gray 맵핑을 고려하면 심벌 오 류가 일어나는 경우 1비트 오류만 발생한다고 간략화 할 수 있다. 따라서 소거 사건이 발생하는 경우 비트 오류율은 아래와 같이 표현 할 수 있다. P B E ε (SNR) = 1 log 2 M P (E ε(snr) 위 식의 조건부 확률 값을 Y 축으로 하고 X축을 비트 오류율 값으로 그림 (2.4)에 도시하였다. 이 결과에서 비트 오류율이 10 4 인 경우, 소거 사건이 발생 하면 약 17.5%의 확률로 심벌 오류가 발생하는 것을 알수 있다. 현재의 NAND 플래시 메모리 소자는 경판정된 결과만 출력으로 제공하므로 소자에 정보를 기록하고 다시 읽었을 때 발생하는 오류를 등가적인 통신 모형 (Equivalent Communication Channel Model)로 표현할 수 있다. 이때 적합한 통신 채널 모형은 이진대칭 채널 (Binary Symmetric Channel; BSC)이다. BSC 채널의 특성은 크로스오버 확률 (crossover probability)로 나타낼 수 있고 메모리 소자의 신호대 잡음 비가 결정되면 크로스오버 확률값을 계산할 수 있다. 그림 (2.5)은 7

제 2 장 MLC 구조에서의 오류 정정 Figure 2.4: 소거사건이 발생한 경우 비트 오류율 대 평균 비트 오류율; ϵ = 0.1 LDPC 부호를 이용한 시스템의 성능을 분석하기 위한 방법을 나타낸다. 제시된 그림에서 M-ary PAM 복조기는 경판정된 출력값을 제공하고 LDPC 복호기는 평 균 오류율을 알고 있으므로 LLR (log likelihood ratio) 값을 계산하여 복호하는 합곱 (Sum-product; SP) 복호방식과 평균 비트 오류율을 이용하지 않는 비트 반 전 (bit-flipping; BF) 복호기를 가정할 수 있다. 만일 BF 복호기를 사용한다면 그림(2.5) 성능 분석 모형은 간단한 BSC 채널 모형으로 나타낼 수 있다. M-ary PAM 복조기가 소거 사건이 발생한 경우 이를 알려주는 신호(그림에서 ϵ)를 제공함으로 아래 그림 (2.6)과 같은 두개의 채널 모 형이 번갈아 가며 사용되는 것으로 이해할 수 있다. 소거 사건 발생시 나타나는 아래쪽 채널 (BSC-2)이 선택될 확률값을 소거 사건이 일어나는 확률 값을 심벌당 비트수로 나눈 값과 같다. 본 논문에서는 위에서 설명한 바와 같이 NAND 플래시 메모리소자에서 발 8

제 2 장 MLC 구조에서의 오류 정정 Figure 2.5: NAND 플래시 메모리의 성능을 평가하기 위한 시스템 모형 Figure 2.6: 두개의 BSC로 구성된 등가 채널 모형 생하는 오류의 등가적인 통신 모형에서 보다 좋은 성능을 얻기 위한 비트 반전 알고리즘을 제안하였으며, 제안된 알고리즘을 기존의 비트 반전 알고리즘과 비교 하여 성능을 검증하였다. 본 논문의 구성은 다음과 같다. 2장에서 LDPC 부호와 패리티 검사 행렬, 태너 그래프를 설명하고, 효율적인 부호화 방법을 소개한다. 다음으로 3장에서는 LDPC 부호의 복호 알고리즘인 합곱 알고리즘, 최소합 알고 리즘, 비트 반전 알고리즘을 소개하고 본 논문에서 제안한 알고리즘을 소개한다. 4장에서는 실험에 대한 결과들로 본 논문에서 제안한 알고리즘을 적용하였을때 등가 채널 모델에서 더 나은 성능을 보여줄 수 있음을 보여준다. 마지막으로 5 9

제 2 장 MLC 구조에서의 오류 정정 장에서는 본 논문의 결론을 내리도록 한다. 10

제 3 장 저밀도 패리티 검사 (LDPC) 부호 LDPC 부호는 1962년 Robert G. Gallager에 의해 제안되었으나 당시의 기술 력으로 구현이 불가능한 복호 복잡도로 인해 수십년간 주목을 받지 못하였다. [1] 1990년대에 이르러서 Tanner에 의해 LDPC 부호를 이분 그래프 (Bipartite graph) 로 나타내면서 효과적인 합곱 알고리즘 (sum-product)이 제안되어 LDPC 부호의 복호 복잡도를 해결하기 위한 연구가 진행되기 시작하였고 [8, 7], 1993년 Berrou 등이 터보 부호를 발표한 이후 터보 부호와 LDPC 부호의 유사성으로 인해 기존에 제안된 LDPC 부호가 다시 주목받게 되었다. 그 후 MacKay에 의해 LDPC 부호 가 Shannon 한계에 접근하는 것이 밝혀졌고 [2,3], Luby에 의해 비균일(irregular) LDPC 부호가 균일한 LDPC 부호에 비해 더 한계에 접근하는 것이 밝혀지면서 터보 부호와 LDPC 부호는 반복적인 복호 방식을 이용하여 Shannon 한계에 근접 하는 오류정정 부호로써, 차세대 채널 부호로 많은 연구가 이루어지고 있다. 또한 Richardson, Shokrollahi, Urbanke에 의해 체계적으로 차수의 분포를 분 석하여 성능의 한계를 결정하는 밀도 진화 (density evolution) 방법이 만들어졌 고 [6], Chung에 의해 밀도 진화 알고리즘을 단순화시킨 가우스 어림법 (Gaussian approximation) 이 제안되었다. 밀도 진화 방법이 복호과정에서 노드간의 PDF (probability density function) 값들을 따라가기 때문에 복잡도를 증가시키는 것에 비해 가우스 어림법은 PDF의 평균과 분산만을 이용하여 복잡도를 크게 줄일 수 있다. LDPC 부호는 Gallager의 간단한 확률적 복호법을 이용하여 성능이 매우 우 11

제 3 장 저밀도 패리티 검사 (LDPC) 부호 수하며 터보부호에 비해 적은 복호 복잡도를 가지며 부호율의 가변이 간단하다. 또한 LDPC 부호는 기존의 터보 부호가 낮은 오류 율에서 오류 마루(Error floor) 현상이 일어나는 것에 비해 좋은 거리특성으로 오류마루 현상이 나타나지 않아 서 4세대 무선 이동 통신 시스템에서의 오류 정정 부호로 관심을 끌고 있다. 반 면 LDPC 부호는 부호화 복잡도가 매우 높은 단점이 있으나 하삼각 (approximate lower triangular) 행렬 분해법을 이용하여 복잡도를 줄이는 부호화 방법이 제안되 고 있으며 순환 행렬을 이용하여 부호화 복잡도를 낮추는 QC-LDPC 부호에 관한 연구 또한 활발히 진행되고 있다 [17]. 본 장의 첫 번째 절에서는 LDPC 부호의 패리티 검사 행렬 (parity check matrix)를 설명하고, 두 번째 절에서는 LDPC 부 호의 부호와 방법에 대하여 설명한다. 3.1 패리티 검사 행렬 (Parity Check Matrix) LDPC 부호는 1의 개수가 매우 작은 랜덤 패리티 검사 행렬 H에 의해 구성 된다. 패리티 검사 행렬 H의 각 행은 무게 (weight) k의 1로 구성되고 각 열은 무게 j의 1로 구성되며 두 열사이의 내적은 1보다 크지 않게 랜덤하게 구성된다. 예를 들어 행의 무게가 2이며 열의 무게가 4인 균일한 LDPC 부호의 패리티 검사 행렬은 다음과 같다 H = 1 1 1 1 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0 0 1 0 0 1 1 0 0 0 1 0 0 1 0 1 0 1 0 0 0 1 0 0 1 0 1 1 12

제 3 장 저밀도 패리티 검사 (LDPC) 부호 LDPC 부호는 태너 그래프 (Tanner Graph)를 사용하여 효과적으로 표현하는 것이 가능하다. 즉, 모든 H는 태너 그래프로 표현할 수 있는데, 방법은 다음과 같다. 아래의 행렬의 열의 개수만큼의 원들을 열의 순서에 맞추어 만들고 위쪽 에 행렬의 행의 개수만큼의 사각형들을 행의 순서에 맞추어 만든다. 만일 행렬의 (i,j)번째 요소가 1이면 아래의 j번째 원과 위의 i번째 사각형에 연결선을 그린다. 상기의 패리티 검사 행렬을 그래프로 나타내면 아래 그림과 같다. 그래프의 위쪽 사각형 노드는 검사 노드 (check node)를 나타내며, 아래쪽 원 노드는 가변 노드 (varible node)를 나타낸다. Figure 3.1: 태너 그래프의 예시 상기의 패리티 검사 행렬과 같은 LDPC 부호는 행과 열의 무게가 각각 하나의 고정된 값으로 정해져 있는 균일한 (regular) LDPC 부호이다. 하지만 일반적으로 균일한 LDPC 부호보다는 비균일한 (irregullar) LDPC 부호가 성능이 좋다고 알 려져 있다. 비균일 LDPC 부호의 성능 향상을 직관적으로 살펴보면, 가변 노드의 경우 검사 노드로부터 더 많은 정보를 받아야 정확한 판단을 할 수 있기 때문에 높은 차수가 유리하다. 반면에 검사 노드의 경우 더 유용한 정보를 이웃한 노드로 13

제 3 장 저밀도 패리티 검사 (LDPC) 부호 전달해야 하기 때문에 낮은 차수를 가지는 것이 유리하다. 물론 두 가지 경우가 양립할 수는 없기 때문에 적절히 균형을 이루어야 좋은 성능을 보일 수 있다. 태 너 그래프에서 사이클 (cycle)은 한 노드에서 출발하여 다시 그 노드로 돌아오는 것을 말하며 이웃 노드들 간의 독립성을 해치기 때문에 높은 SNR에서 오류 마루 의 원인이 된다. 따라서 LDPC 부호의 구성 시 오류 마루 현상을 막기 위해 짧은 사이클의 구조를 없애야 한다. 3.2 LDPC 부호의 부호화 방법 (Encoding) LDPC 부호는 선형 블록 부호 (linear block code)로 선형 블록 부호에서는 메 시지의 길이가 k인 2진 테이터 벡터 u = [u 0, u 1, u k 1 ] 가 주어졌을 때, 부호화 를 거쳐서 패리티 부분이 첨가되어 길이 u인 벡터 c=[c 0, c 1, c k 1] 를 생성하게 된다. 그리고 이를 (n,k) 부호로 표현한다. 또한 부호율 R은 k/n이 되고, 패리티 [ ] 검사 비트의 크기는 m으로 표시한다. 패리티 검사 행렬 H가 H = P T.I 와 같 [ ] 은 형태로 만들어지면 생성 행렬 (Generator matrix) G는 G = I.P 의 형태로 구성된다. 부호화는 다음과 같이 이루어진다. H = c = ug = [ ] u.up [ ] P T.I 만족하는 패리티 검사 행렬을 만들기 위해서는 H의 열을 재구성하고 가우스 소거법을 이용한다. 3.2.1 하삼각 행렬 부호화 기법 앞서 언급한 방법으로 부호화를 하게 될 때 부호화의 복잡도가 부호길이의 제 곱에 비례하여 증가한다는 단점이 있다. 따라서 이러한 부호화 복잡도를 줄이기 14

제 3 장 저밀도 패리티 검사 (LDPC) 부호 위하여 하삼각 (approximate lower triangular) 행렬 분해법이 이용될수 있다. 이 방법은 생성 행렬을 사용하지 않고, 패리티 검사 행렬의 재구성을 통하여 패리티 검사 행렬만을 이용하여 부호화하며 선형 시간 부호화 (linear-time encoding)가 가 능하다. 패리티 검사 행렬과 부호어 (codeword)는 각각 c = [p, d]와 H = [ H p, H d] 로 구성되며 H = [ H p, H d] c T = 0를 만족한다. H p 행렬은 i = j이면 h i,j 는 1로, i > j이면 h i,j 는 0으로 구성된 하삼각 행렬로 다음과 같다. H p = 1 h p 1,2 h p 1,m 0 1....... 0 1 h p m 1,m 0 0 0 1 부호어의 패리티 비트는 아래의 식을 이용하여 순차적으로 구할 수 있다. p i = m j=i+1 n m h p i,j p j + j=1 h d i,jp j (mod 2) 이러한 구조를 이용하여 부호기를 구성할 경우 가우스 소거법을 사용할 필요가 없어져 복잡도를 줄일 수 있다. 그림 (3.2) 은 이러한 하삼각 행렬 구조로 구성된 H 행렬의 구조를 나타내고 있다. 3.2.2 QC (Quasi-cyclic) LDPC 부호 보다 효율적인 LDPC 부호의 부호화를 위해 무게 1인 순환행렬 블록을 이용 하여 구성한 QC-LDPC 부호에 대하여 최근 많은 연구가 진행되고 있다. Quasicyclic 부호는 선형 블록 부호로서 부호어를 2 이상 오른쪽 혹은 왼쪽으로 순환 15

제 3 장 저밀도 패리티 검사 (LDPC) 부호 Figure 3.2: 하삼각 행렬 구조 이동시켜 생성한 부호어도 역시 부호어가 되는 부호이다. 예를 들어, 다음과 같은 생성 행렬이 주어졌을 때, G = 1 1 1 1 0 0 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 0 1 1 1 G 의 첫 번째 열인 111 100 110을 오른쪽으로 3칸 순환 이동시킨 부호어가 2번째 열에 있다. 마찬가지로 2번째 열을 3칸 오른쪽 순환 이동시킨 부호어는 3번째 열 에 있다. 그러나 1칸 혹은 2칸 이동시킨 부호어는 존재하지 않는다. Quasi-cyclic 부호는 이러한 순환 특성을 가지므로 복잡한 부호화기를 간단한 shift resister와 논리 회로로써 구현할 수 있다. Quasi-cyclic 부호의 패리티 검사 행렬은 각각 다 16

제 3 장 저밀도 패리티 검사 (LDPC) 부호 음과 같은 m n 순환행렬 블록으로 구성할 수 있다. H i,j = c 0 c 1 c m 1 c m 1 c 0 c m 2...... c 1 c 2 c 0 여러 개의 순환행렬 블록으로 구성된 quasi-cyclic 부호는 다음과 같이 r s개의 순환 행렬 H i,j 로 구성된 mr ms 크기의 패리티 검사 행렬 H를 가진다. H 1,1 H 1,2 H 1,s H 2,1 H 2,2 H 2,s H =...... H r,1 H r,2 H r,s QC-LDPC 부호의 패리티 검사 행렬 H는 각각의 순환행렬을 다수의 행 블 록과 열 블록으로 연접하여 구성할 수 있다. 이 때 H로 부터 가우스 소거법으로 유도되는 생성 행렬 G도 순환행렬 블록들로 이루어진다. 일반적으로 LDPC 부호 의 부호화를 위해서는 생렬 곱 연산을 사용하기 때문에 계산량이 매우 많아지게 될 뿐만 아니라, 생성 행렬에 해당하는 정보를 모두 알고 있어야 하므로 메모리와 논리 회로 개수의 증가로 인한 비용의 문제를 야기한다. QC-LDPC 부호는 shift register를 이용한 효율적인 부호화가 가능하며 각 순환행렬 블록에 대한 생성 다 항식만을 알고 있으면 되므로 메모리와 논리 회로 개수를 효율적으로 줄일 수 있 다는 장점이 있다. 본 절에서는 저밀도 패리티 검사 부호와 패리티 검사 행렬, 그리고 부호화 17

제 3 장 저밀도 패리티 검사 (LDPC) 부호 기법에 대해 소개하였다. 다음 장에서는 저밀도 패리티 검사 부호의 복호화 방법 인 합곱 알고리즘, 최소합 알고리즘 그리고 비트 반전 알고리즘에 대해 소개한다. 또한, 본 논문에서 제안하는 신뢰도 추정 기반의 비트 반전 알고리즘에 대해 소개 한다. 18

제 4 장 LDPC 부호의 복호 알고리즘 Gallager가 처음 제안한 확률적 복호법 (probabilistic decoding) 은 터보 부호 의 MAP 복호 알고리즘, 길쌈 부호의 Viterbi 알고리즘 등과 함께 그래프 상에서 국소 함수들의 요약 연산을 수행하는 합곱 알고리즘 (Sum-product algorithm)에 의해 설명이 가능하다. 합곱 알고리즘은 신뢰 전달 (Belief-propagation) 알고리 즘 또는 메시지 전달 (Message-passing) 알고리즘으로도 불린다. 비트 반전 (Bitflipping) 알고리즘이 오로지 메시지의 부호만 나타내는 경판전 (hard-decision) 이 기 때문에 정보의 신뢰성과 안정성을 나타내지 못하는 것에 비해 합곱 알고리즘은 연판정 (Soft-decision) 을 사용함으로써 채널의 정보와 함께 전송된 신호의 확률적 정보를 표현할 수 있다. 합곱 알고리즘의 목적은 각 부호의 사후확률인 APP (A Posteriori Probability) 를 계산 하는 것이다. 합곱 알고리즘은 반복적인 계산을 통해 대략의 APP 값을 얻는데, 이 대략적인 값은 구성된 LDPC 부호의 구조에 사이클이 없다면 정확한 값이 된다. 예를 들어 앞 절의 패리티 검사 행렬로 정의 되는 부호를 AWGN (Additive White Gaussian Noise) 채널을 통해 전송하면 그림 (4.1)과 같다. 부호어 c k 0, 1는 AWGN 채널을 통해 x k = ( 1) c k 를 만족하는 심볼 x k ±1 c k로 전송된다. y k 는 수신된 채널 심볼을 나타내며 아래 식과 같이 표현된다. y k = x k + n k 19

제 4 장 LDPC 부호의 복호 알고리즘 Figure 4.1: AWGN 채널에서의 태너 그래프 패리티 검사 행렬 H의 첫번째 열에 대응되는 서브 그래프는 그림 (4.2)과 같다. 메시지 전달 복호 알고리즘에서 노드 v i 는 가지고 있는 모든 정보를 이미 받은 정 Figure 4.2: H의 첫번째 열에 대응되는 서브 그래프 보에 연결된 노드를 제외하고 연결된 검사 노드 c j 에 보낸다. 예를 들어 v 0 f 1 의 상황을 보면 그림 (4.3)과 같다. 노드 v 0 에서 c 1 으로 보내지는 정보는 채널 정 보와 노드 v 0 가 이미 노드 c 0 로부터 이전 절반 반복 (half iteration)에서 받은 외부 정보 (extrinsic information)로 구성된다. 복호 알고리즘에서 절반 반복은 v i c j 인 가변 노드에서 검사 노드로의 방향과 c j v i 인 검사 노드에서 가변 노드로의 방향이 있다. 패리티 검사 행렬 H의 첫 번째 행에 대응되는 서브 그래프는 그림 (4.4)과 같다. 20

제 4 장 LDPC 부호의 복호 알고리즘 Figure 4.3: H의 첫번째 열에 대응되는 메시지 전달 Figure 4.4: H의 첫번째 행에 대응되는 서브 그래프 노드 c 0 에서 v 3 으로 보내지는 정보는 이전 절반 반복에서 v 0, v 1, v 2 로부터 받은 외부 정보로 구성된다. 결국 한번의 반복은 v i c j 의 계산과 그에 따른 c j v i 의 계산으로 구성된다. 복호는 최대 반복수에 도달하거나 확률 정보로부터 도출된 ĉ 이 ĉh = 0을 만족하면 종료한다. 4.1 합곱 (Sum-product) 알고리즘 LDPC 부호의 복호를 위해 사용되는 합곱 알고리즘은 제한적인 거리 복호 (bounded distance decoder) 보다 성능이 우수하며, 채널로 부처 얻는 우도 (likelihood)를 이용할 수 있는 연판정 복호기 이다. 연집 오류가 발생하는 채널인 경 21

제 4 장 LDPC 부호의 복호 알고리즘 Figure 4.5: H의 첫번째 행에 대응되는 메시지 전달 우에도 연집 오류를 정정할 수 있도록 일반화될 수 있다. LDPC 합곱 알고리즘은 태너 그래프로 나타낼 수 있는데 두 방향의 노드인 비트 노드와 검사 노드는 병 렬식으로 계산을 수행한다. 수신된 신호 y가 주어졌을 때 전송된 메시지 c i 에 대한 APP를 계산하여 식 으로 표시하면 다음과 같다. Pr(c i = 1 y, s i ) 위 수식에서 s i 는 c i 가 패리티 검사를 만족하는 사건을 나타낸다. 보조 정리 4.1. Pr(a k = 1) = p k 를 만족하는 m개의 독립적인 이진 부호 a = (a 1,..., a m )을 정의하면, a가 짝수개의 1을 포함할 확률은 다음과 같다. 1 2 + 1 2 m (1 2p k ) k=1 그리고 a가 홀수 개의 1을 포함할 확률은 다음과 같다. 1 2 1 2 m (1 2p k ) k=1 증명 4.1. m = 2 : 2개의 비트일 경우, 짝수 개의 1을 가질 확률은 두 비트 모두 1이거나 두 비트 모두 0인 경우이다. 식으로 표현하면 다음과 같다. 22

제 4 장 LDPC 부호의 복호 알고리즘 Pr(even) = Pr(a 1 + a 2 = 0) = p 1 p 2 + (1 p 1 )(1 p 2 ) = 1 2 + 1 2 (1 2p 1)(1 2p 2 ) m = L 1 일 때 상기의 짝수에 대한 수식을 만족한다고 가정하면, 다음과 같이 증명된다. Z L 을 다음과 같이 놓으면, Z L a 1 + + a L Pr(Z L = 0) = Pr(Z L 1 + a L = 0) = 1 2 + 1 2 (1 2 Pr(Z L 1 = 1))(1 2p L ) = 1 2 + 1 2 (1 (1 L 1 k=1 (1 2p k)))(1 2p L ) = 1 2 + 1 2 L k=1 (1 2p k) 복호 알고리즘에 사용되는 변수들을 다음과 같이 정의한다. - R j = i : h ji = 1:패리티 검사 행렬의 j번째 열에서 1의 위치. - R j\i = i : h ji = 1 \ i: i번째 비트를 제외한 R j 의 집합. - C i = j : h ji = 1:패리티 검사 행렬의 i번째 행에서 1의 위치. - C i\j = j : h j i = 1 \ j: j번째 비트를 제외한 C i 의 집합. - p i = Pr(c i = 1 y i ): 1을 수신할 확률. - q ij (b): 가변 노드 v i 에서 검사 노드 c j 로 전달되는 확률 정보, b 0, 1. - r ji (b): 가변 노드 c i 에서 검사 노드 v j 로 전달되는 확률 정보, b 0, 1. 23

제 4 장 LDPC 부호의 복호 알고리즘 정리 4.1. 수신된 신호 y와 사건 s i 가 주어졌을 때, c i 의 APP 다음과 같다. Pr(c i = 0 y, s i ) Pr(c i = 1 y, s i ) = (1 p i) p i j C i (1 + i R j\i (1 2p i j)) j C i (1 i R j\i (1 2p i j)) 증명 4.2. Bayes rule에 의해 위 식은 아래와 같이 표현된다. Pr(c i = 0 y, s i ) Pr(c i = 1 y, s i ) = (1 p i) Pr(s i c i = 0, y)/ Pr(s i ) p i Pr(Pr(s i c i = 1, y))/ Pr(s i ) c i = 1이 주어졌을 때, 패리티 검사를 만족시키기 위해 a의 나머지 비트의 홀수 개의 1을 가져야 한다. 보조 정리 3.1에 의해 홀수 개의 1을 포함할 확률은 다음과 같다. 1 2 1 2 m (1 2p k ) k=1 c i = 0인 경우도 비슷한 형태로 정리된다. y i 가 통계적으로 독립이기 때문에 모든 패리티 검사를 만족할 확률은 모든 확률의 곱으로 표현된다. 약분해서 표시하면 다음과 같다. Pr(s i c i = 0, y) Pr(s i c i = 1, y) = j C i (1 + i R j\i (1 2p i j)) j C i (1 i R j\i (1 2p i j)) 그러나 위 식에 의한 APP 비율을 계산하는 것은 복잡하기 때문에 합곱 알 고리즘과 같은 반복 복호 알고리즘이 사용된다. 위에서 언급된 정리 3.1을 합곱 알고리즘에 적용시키면 다음과 같다. 검사 노드에서 가변 노드로 전달되는 확률 정보 r ij (b)는 다음과 같이 표현된다. r ij (0) = 1 2 + 1 2 m (1 2p k ) k=1 24

제 4 장 LDPC 부호의 복호 알고리즘 된다. r ij (1) = 1 2 1 2 m (1 2p k ) k=1 따라서 정리 3.1은 다음과 같이 변형된다. Pr(c i = 0 y, s i ) Pr(c i = 1 y, s i ) = (1 p i) p i j C i r ij (0) j C i r ij (1) 가변 노드에서 검사 노드로 전달되는 확률 정보 q ij (b)는 다음과 같이 표현 q ij (0) = (1 p i ) j C i\j r j i(0) q ij (1) = p i r j i(1) j C i\j 합곱 알고리즘은 위에서 언급된 내용과 같이 q ij (b)와 r ij (b) 사이를 반복하게 된다. 보조 정리 4.2. y i = x i + n i 에서 잡음은 평균이 0이고 분산이 σ 2 인 정규 분포를 따르고 전송되는 1의 양과 0의 양이 같다고 가정하면 즉, Pr(x i = 1) = Pr(x i = 0) = 1/2라고 할때, 초기화되는 확률은 다음과 같이 표현된다. Pr(x i = x y) = 1 1 + exp( 2yx/σ 2 ) 25

제 4 장 LDPC 부호의 복호 알고리즘 증명 4.3. Pr(x i = x y) = Pr(y x i=x) Pr(x i =x) Pr(y) 1 2 = exp( (y x)2 /2σ 2 ) 1 2 exp( (y 1)2 /2σ 2 )+ 1 2 exp( (y+1)2 /2σ 2 ) = 1 exp(y(1 x)/σ 2 )+exp(y(1+x)/σ 2 ) = 1 1+exp( 2yx/σ 2 ) 상기의 합곱 알고리즘을 정리하면 다음과 같다. Step(0) 초기화 각 가변 노드는 사전 확률로 할당된다. 보조 정리 3.2에 의해 채널에 따라 기본적 으로 아래와 같이 초기화된다. q ij (0) = 1 p i = Pr(x i = +1 y i ) = q ij (1) = p i = Pr(x i = 1 y i ) = Step(1) 검사 노드에서 가변 노드로 메시지 전달 1 1 + exp( 2y i /σ 2 ) 1 1 + exp(2y i /σ 2 ) 각 검사 노드 j는 모든 입력 정보 q ij 값들을 모으고, 검사 노드 j에 연결된 모든 다른 비트들에 기초하여 비트 i에 신뢰를 갱신한다. r ji (1)은 r ji (0)을 먼저 구한 후 1에서 r ji (0)을 빼면 간단히 구해진다. r ji (0) = 1 2 + 1 (1 2q i 2 j(1)) i R j\i r ji (1) = 1 r ji (0) 26

제 4 장 LDPC 부호의 복호 알고리즘 Step 1을 그림으로 표현하면 그림(4.6)과 같다. 그림(4.6)은 패리티 검사 행 렬의 첫 번째 행에서 검사 노드로부터 가변 노드로 전달되는 신뢰도를 나타낸다. 검사 노드 c 0 는 연결된 모든 가변 노드로부터 q ij 를 받아 각각의 가변 노드로 신 뢰도를 내려 보낸다. Figure 4.6: 검사 노드로부터 가변 노드로 신뢰도 전파 Step(2) 가변 노드에서 검사 노드로 메시지 전달 각 가변 노드 i는 연결된 검사 노드로부터 확률 정보를 모으고 APP를 갱신한다. APP를 위해 초기 정보와 연결된 검사 노드로부터 입력되는 외부정보가 필요하다. 검사 노드 j 뒤에 전달되는 가변 노드 i의 신뢰도는 검사 노드 j로부터 입력되는 정보에 포함되지 않는다. 따라서 q ij 는 다음과 같이 갱신된다. q ji (0) = K ij (1 p i ) j C i\j r j i(0) q ji (1) = K ij p i r j i(1) j C i\j 정규화 요소 K ij 는 q ij (0)+q ij (1) = 1을 만족하는 값이다. 정규화를 통해 쉽게 0과 1을 구분할 수 있다. Step 2를 그림으로 표현하면 그림 (4.7)와 같다. 27

제 4 장 LDPC 부호의 복호 알고리즘 Figure 4.7: 가변 노드로부터 검사 노드로 신뢰도 전달 Step(3) Q i 계산 결과 판정을 하기 위해 모든 비트에 대하여 Q i 를 계산한다. Q i (0) = K i (1 p i ) j C i r ji (0) Q i (1) = K i p i r ji (1) j C i 정규화 요소 K i 는 Q i (0)+q i (1) = 1을 만족하는 값이다. Q i 는 현재의 반복에서 결과를 판정하기 위해 사용되며, 다음 반복에는 사용되지 않는다. Step(4) 결과 판정 각 비트의 Q i 를 경판정한다. 1, Q i (1) > 0.5 ĉ i = 0, else 정규화 요소를 Q i 값에 곱했기 때문에 Q i 값이 0.5보다 크다는 것운 1을 의미 하며 0.5보다 작다는 것은 0을 의미한다. 만약 ĉh T = 0을 만족하거나 최대 반복 복호 횟수에 도달하면 복호를 멈추고 그렇지 않으면 Step 1에서 4를 반복한다. 28

제 4 장 LDPC 부호의 복호 알고리즘 AWGN 채널상의 이진 부호의 경우인 합곱 알고리즘은 로그 도메인 상에서 더욱 효과적으로 수행될 수 있다. 즉 복호화 과정에서 필요한 곱셈연산을 덧셈연 산으로 변환하여 계산량을 줄일수 있다. 우선 로그 도메인에서 계산을 하기 위하 여 다음과 같은 확률 값들이 LLR (log likelihood retios)로 정의 된다. 초기화 단계는 다음과 같이 바뀐다. L(c i ) log Pr(x i = +1 y i ) Pr(x i = 1 y i ) L(r ji ) log r ji(0) r ji (1) L(q ij ) log q ij(0) q ij (1) L(Q i ) log Q i(0) Q i (1) L(q ij ) = L(c i ) = log (1 + exp( 2y i/σ 2 )) ( 1) (1 + exp(+2y i /σ 2 )) ( 1) = 2y i σ 2 σ 2 는 1/(2R(E b /N 0 ))인 잡음 분산 (noise variance)을 나타낸다. Step 1에서 r ji (0)에 관한 식을 다시 정리하면 다음과 같다. 2r ji (0) = 1 + i R j\i (1 2q i j(1)) 1 r ji (1) = (1 2q i j(1)) i R j\i 위 수식을 정리하기 위해 아래의 수식이 필요하다. tanh( 1 2 log(p 0/p 1 )) = p 0 p 1 = 1 2p 1 29

제 4 장 LDPC 부호의 복호 알고리즘 상기 식을 이용하여 r ji (0)에 관한 식을 정리하면 다음과 같다. tanh( 1 2 L(r ji)) = tanh( 1 2 L(q i j)) i R j\i L(r ji ) = 2 tanh 1 ( tanh( 1 2 L(q i j))) i R j\i 상기 식은 여전히 곱으로 표현되어 있기 때문에 Gallager가 제안한 아래의 방법을 통하여 연산을 줄일 수 있다. L(q ij )를 부호와 크기의 형태로 변형하면 다 음과 같다. L(q ij ) = α ij β ij α ij sign(l(q ij )) β ij L(q ij ) 변형된 L(q ij )를 L(r ji )에 대한 수식에 대입하면 다음과 같다. tanh( 1 2 L(r ij) = i α i j i tanh( 1 2 β i j) L(q ij )에 관해 정리하고 log 1 log를 곱하여 식을 간단히 하면 다음과 같다. L(r ij ) = ( i α i j)2 tanh 1 log 1 log i tanh( 1 2 β i j) = ( α i j)2 tanh 1 log 1 log tanh( 1 2 β i j) i i = ( α i j)φ( Φ(β i j)) i i R j \i 30

제 4 장 LDPC 부호의 복호 알고리즘 위 식에서 함수 Φ(x)는 아래 식과 같이 정의 된다. Φ(x) log tanh( 1 2 x) = logex + 1 e x 1 함수 Φ(x)는 Φ 1 (x) = Φ(x)의 특성을 가진다. Step 2의 경우 간단히 q ij (0)을 q ij (1)로 나누고 양변에 로그를 취하면 아래 식이 유도된다. L(q ij ) = L(c i ) + L(r j i) j C i \j 로그 도메인에서 합곱 알고리즘을 정리하면 다음과 같다. Step(0) 초기화 L(q ij ) = L(c i ) = 2y i σ 2 Step(1) 검사 노드에서 가변 노드로 메시지 전달 L(r ij ) = ( i α i j)φ( i R j \i Φ(β i j)) Step(2) 가변 노드에서 변수 노드로 메시지 전달 Step(3) Q i 계산 L(q ij ) = L(c i ) + L(r j i) j C i \j L(q i ) = L(c i ) + j C i L(r ji ) 31

제 4 장 LDPC 부호의 복호 알고리즘 Step(4) 결과 판정 1, L(Q i ) < 0 ĉ i = 0, else L(Q i )는 log(q i (0)/Q i (1))로 정의 되어있기 때문에 분자가 클 경우 L(Q i )은 0보다 크고, 분자가 작을 경우 0보다 작게 되므로, L(Q i )값이 0보다 크면 1로 판정하고, 0 보다 작으면 0으로 판정한다. 만약 ĉh T = 0을 만족하거나 최대 반복 복호 횟수에 도달하면 복호를 멈추고 그렇지 않으면 Step 1에서 4를 반복한다. 4.2 최소합 (min-sum) 알고리즘 로그 도메인 복호기에서 L(r ji )는 다음과 같이 계산된다. L(r ij ) = ( i α i j)φ( i R j \i Φ(beta i j)) Φ(x) 의 그래프는 그림 (4.8)와 같으며 Φ(x) 에 의해 비선형이 생기고 복호 기의 복잡도가 증가하게 된다. 최소합 알고리즘은 Φ(x) 에 의한 복잡도를 줄이기 위해 Φ(x) 함수 대신에 크기가 가장 작은 β ij 값을 선택한다. L(r ji )를 구하는 식 에서 Φ(x) 함수가 두 번 사용되기 때문에 가장 작은 값을 선택하면 Φ(x) 함수의 그래프에 따라 가장 큰 값이 나오고 그 값이 다시 함수에 입력으로 들어가서 가 장 작은 값을 내보낸다. L(r ji )값이 크다는 것은 신뢰도가 높은 정보를 의미하며 패리티 검사에 큰 영향을 미치지 않는다. 패리티 검사는 작은 L(r ji )값에 의해 결 정되기 때문에 가장 작은 값을 내려 보냄으로써 큰 성능의 저하 없이 복잡도를 줄일 수 있다. Φ(x) 함수의 그래프 특성에 따라 최소합 알고리즘은 L(r ji )계산을 32

제 4 장 LDPC 부호의 복호 알고리즘 Figure 4.8: Φ(x) 그래프 간단히 한다. ( ) ( ) Φ Φ(β i j) Φ(min β i i j) i = min β i i j 간단화된 L(t ji )는 다음과 같다. L(r ij ) = i R j \i (α i j) min i R j \i β i j 이전의 복호 알고리즘에서는 잡음 변수에 대한 정보 σ 2 가 필요했지만, 최소합 알고리즘에서는 성능의 변화 없이 모든 LLR 값을 정규화 (Normailization) 하는 것이 간단하다. 정규화된 LLR을 L로 표시하면 알고리즘은 다음과 같다. Step(0) 초기화 L(q ij ) = L(c i ) = y i Step(1) 검사 노드에서 가변 노드로 메시지 전달 L(r ij ) = ( i α i j)φ( i R j \i Φ( β i j)) Step(2) 가변 노드에서 변수 노드로 메시지 전달 33

제 4 장 LDPC 부호의 복호 알고리즘 L(q ij ) = L(c i ) + L(r j i) j C i \j Step(3) Q i 계산 L(q i ) = L(c i ) + j Ci L(r ji ) Step(4) 결과 판정 1, L(Qi ) < 0 ĉ i = 0, else 만약 ĉh T = 0을 만족하거나 최대 반복 복호 횟수에 도달하면 복호를 멈추고 그 렇지 않으면 Step 1에서 4를 반복한다. 4.3 비트 반전 (Bit-flipping) 알고리즘 비트 반전 알고리즘은 LDPC 부호를 구성하는 가장 간단한 알고리즘으로써 태너 그래프를 이용하여 패리티 검사 연산을 반복적으로 수행하는 방법이다. 또 한 비트 반전 알고리즘은 패리티 검사 부호를 기본으로 하고 있으므로 알고리즘 내의 모든 연산을 모듈러 연산 (modular-2 addition)으로만 이루어져 있다. 따라서 다른 알고리즘에 비해 계산이 간단하고 알고리즘의 복잡도가 낮다는 장점을 가지 고 있지만 에러 정정 성능이 합곱 알고리즘에 비해 뒤떨어진다. 이에 따라 비트 복잡도를 크게 높이지 않으면서도 오류 정정 성능을 높이기 위하여 다양한 연구 가 지속적으로 수행되고 있다. 비트 반전 알고리즘의 성능을 개선하는 시도로서 가중치 비트 반전 (weighted bit-flipping;wbf) 알고리즘 등이 제안되었다. Gallager에 의해 제안된 비트 반전 알고리즘은 패리티 검사 방정식에 모두 34

제 4 장 LDPC 부호의 복호 알고리즘 동일한 가중치를 부여했지만, 이를 개선한 WBF 알고리즘은 각 체크에 괸여되는 비트 가운데 신호의 크기가 가장 작은 것을 방정식의 가중치로 부여함으로써 패 리티 검사 방정식의 신뢰성을 차등화하는 방법을 사용하였다. WBF 알고리즘을 개선한 IMWBF 알고리즘은 WBF와 마찬가지로 체크 방정식에 가중치를 부여하 여 복호를 수행하지만 가중치의 값을 결정하는 방법이 다르다. 다시 말해 WBF 는 각 체크에 연결된 비트의 정보를 모두 이용하는 반면에 IMWBF는 자기 자신 으로부터 제공된 정보를 제거한 후에 메시지를 전달받는 것이다. 비트 반전 알고리즘을 소개하기 위하여 먼저 M N 패리티 검사 행렬 H 에 의하여 정의된 (d v, d c ) 규칙 LDPC 부호를 가정하자. 메시지는 AWGN 채널 에서 BPSK (binary phase-shift keying) 변조를 이용하여 전송하며, 부호어 c = (c 1, c 2,, c N )은 x i = 2c i 1, i [1, N]의 규칙에 의하여 이진 벡터 x = (x 1, x 2,, x N ) 으로 변환된다고 하자. 만약 채널에 평균이 0이고 σ 2 인 잡음 n i 이 존재한다면 수 신된 신호 y = (y 1, y 2,, y N )은 y i = x i + n i 로 표현할 수 있다. 그러면 경판정된 벡터 z = (z 1, z 2,, c N )의 값은 y i 이 양수이면 z i = 1, 음수이면 z i = 0으로 정해 지며, 신드롬 s = (s1, s2,, s M ) = zh T 는 아래 식에 의하여 정의된 체크로부터 구할 수 있다. s j = z i h ji i C j 경판정된 벡터 z만을 이용하는 비트 반전 알고리즘은 다음과 같다. Step(1) 다음의 식을 이용하여 신드롬 벡터 s를 구한다. s j = i C j z i h ji 만약 s = 0 이면 복호를 멈추고 z를 부호어로 판정한다. Step(2) 모든 가변 노드 i에 대하여 신드롬 값이 1인 검사노드의 갯수를 구한다. 35

제 4 장 LDPC 부호의 복호 알고리즘 Step(3) 모든 가변 노드 i에서 (2)에서 구한 값이 미리 정해진 문턱값 보다 큰 경우 z i 를 반전시킨다. Step(4) 최대 반복 복호 횟수에 도달한 경우 복호를 멈추고 아닐 경우 (1)부터 (4) 를 반복한다. WBF 알고리즘과 IMWBF 알고리즘은 채널로 부터 수신한 y를 이용하여 가 중치를 구함으로써 성능향상을 도모하였다. WBF 알고리즘에서 가변 노드에서 검사 노드로 전달되는 메시지의 가중치는 합곱 알고리즘에서 검사 노드 갱신에 필요한 tanh 함수가 최소합 알고리즘에서는 연결된 가변 노드의 LLR값의 최소값 으로 근사화 된다는 사실에 기인한다. 즉, WBF 알고리즘에서 j번째 검사 노드가 가지는 i번째 가변 노드에 대한 가중치 w ji 는 다음과 같이 정의된다. w ji = min i C j\i y i 상기의 가정과 정의를 기반으로 하여 WBF 알고리즘은 다음과 같이 복호를 수행한다. Step(0) 반복 복호 횟수 k를 0으로 초기화하고 최대 반복 복호 횟수 K max 를 설 정한다. 수신된 신호로부터 모든 i [1, N], j [1, M]에 대하여 가중치 w ji 를 구한다. Step(1) 다음의 식을 이용하여 신드롬 벡터 s를 구한다. s j = i C j z i h ji 만약 s = 0 이면 복호를 멈추고 z를 부호어로 판정한다. Step(2) 모든 가변 노드 i에 대하여 다음과 같이 정의된 반전 함수 (flipping func- 36

제 4 장 LDPC 부호의 복호 알고리즘 tion)을 계산한다 E i = j R i (2s j 1)w ji Step(3) 다음의 조건을 만족하는 가변 노드에 대하여 z i 를 갱신한다. i = arg max E i i Step(4) 최대 반복 복호 횟수에 도달한 경우 복호를 멈추고 아닐 경우 k를 k + 1 로 증가시키고 (1)부터 (4)를 반복한다. IMWBF 알고리즘은 자기 자신으로부터 제공된 정보를 제거한 후 반전 함수 를 계산한다. 즉 WBF 알고리즘에 비해 채널로부터 수신한 정보를 더욱 적극적으 로 활용함으로써 성능 향상을 이루었다. IMWBF 알고리즘은 다음과 같이 복호를 수행한다. Step(0) 반복 복호 횟수 k를 0으로 초기화하고 최대 반복 복호 횟수 K max 를 설 정한다. 수신된 신호로부터 모든 i [1, N], j [1, M]에 대하여 가중치 w ji 를 구한다. Step(1) 다음의 식을 이용하여 신드롬 벡터 s를 구한다. s j = i C j z i h ji 만약 s = 0 이면 복호를 멈추고 z를 부호어로 판정한다. Step(2) 모든 가변 노드 i에 대하여 다음과 같이 정의된 반전 함수 (flipping function)을 계산한다 E i = j R i (2s j 1)w ji α y i 37

제 4 장 LDPC 부호의 복호 알고리즘 Step(3) 다음의 조건을 만족하는 가변 노드에 대하여 z i 를 갱신한다. i = arg max E i i Step(4) 최대 반복 복호 횟수에 도달한 경우 복호를 멈추고 아닐 경우 k를 k + 1 로 증가시키고 (1)부터 (4)를 반복한다. 여기서 Step(2)의 인수 α는 신호대 잡음비 (signal-to-noise raio; SNR)에 따라 다른 최적값을 갖는 양의 실수이다. 4.4 신뢰도 추정 기반의 BF 알고리즘 WBF 알고리즘과 IMWBF 알고리즘은 검사 노드 연산 과정에 합곱 알고리즘, 최소합 알고리즘의 방법론을 적용함으로써 기존의 비트 반전 알고리즘에 비해 많 은 성능 향상을 이루었지만 몇 가지 한계를 가지고 있다. 첫 번째는 가변 노드가 처음 채널로부터 수신한 신뢰도가 복호 과정 전체에 동일하게 유지되고 경판정 된 벡터만이 갱신된다는 점이다. 그로 인하여 각 노드들이 반복 복호 과정에서 새로 얻게 되는 정보가 매우 제한적일 수 밖에 없다. 또한 검사 노드로 부터 받 은 신뢰도를 이용하여 가변 노드를 반전 시켰다면 반전된 비트는 이전 반복 복호 과정보다 향상된 신뢰도를 가져야 하지만 그에 대한 고려가 전혀 없다는 문제점 이 있다. 두 번째로, 한번의 반복 복호에서 가장 큰 반전 함수값을 가지는 소수의 비트만이 반전되고 나머지 비트들의 신뢰도가 그대로 유지된다는 점이다. 따라 서 반복 복호 연산에 의해 새로 언게된 정보의 대부분이 다음 복호에서 낭비되게 된다. 이러한 단점들을 보완하기 위하여 본 논문에서 제안한 알고리즘은 다음과 같 은 사실에 기인한다. 먼저 하나의 오류 비트를 가지고 있던 검사 노드의 신뢰도는 그 오류 비트가 반전된 경우 더 큰 신뢰도를 가지게 된다는 사실이다. 그러므로, 38

제 4 장 LDPC 부호의 복호 알고리즘 매 반복 복호시 반전된 비트의 신뢰도를 향상시킴으로써 다음 복호에서 반전된 비 트를 포함하고 있는 검사 노드의 신뢰도를 향상 시킬 수 있다. 또한 구해진 반전 함수 값이 매우 클 경우 가변 노드의 신뢰도를 반대편 신호 방향으로 크게 이동 하고, 반전 함수 값이 매우 작을 경우 가변 노드의 신뢰도를 같은 신호 방향으로 이동하여 신뢰도를 강화시킴으로써 합곱 알고리즘의 동작 원리인 외부에서 받은 신뢰도를 이용한 반복적 복호과정으로 정확한 가변 노드의 메시지를 추정해 나가 는 방법론을 반영할 수 있다. 제안된 알고리즘은 다음 순서에 따라 복호를 수행한다. Step(0) 반복 복호 횟수 k를 0으로 초기화하고 최대 반복 복호 횟수 K max 를 설 정한다. Step(1) 다음의 식을 이용하여 신드롬 벡터 s를 구한다. s j = i C j z i h ji 만약 s = 0 이면 복호를 멈추고 z를 부호어로 판정한다. Step(2) 모든 가변 노드 i에 대하여 다음과 같이 정의된 반전 함수 (flipping function)을 계산한다 E i = (2s j 1)w ji α y i j R i 이때 사용되는 가중치는 다음과 같이 구한다. w ji = min i C j\i y i Step(3) 반전 함수 값에 따라 각 가변 노드의 신뢰도를 갱신한다. 1. E i > δ 1 이면 z i 를 반전시키고 y i = y i + β 2 39

제 4 장 LDPC 부호의 복호 알고리즘 2. E i < δ 2 이면 y i = y i + β 2 3. Step(4) 최대 반복 복호 횟수에 도달한 경우 복호를 멈추고 아닐 경우 k를 k + 1로 증가시키고 (1)부터 (4)를 반복한다. 제안된 신뢰도 추정 방식의 BF 알고리즘은 BSC 채널과 같이 채널 출력이 경 판정된 결과값 뿐인 경우에도 적용이 가능하다. 이러한 경우에는 모든 비트들의 신뢰도를 임의의 양수로 초기화 한 후 각각의 반전 함수 값에 따라 신뢰도를 갱 신한다. 따라서 첫 번째 반복 복호에서는 기존의 경판정 기반의 BF 알고리즘을 수행하게 되고, 두 번째 반복 복호 후 부터는 복호기가 추정한 각 비트의 갱신된 신뢰도를 이용하여 복호를 수행 할 수 있다. 40

제 5 장 실험 결과 5.1 실험 환경 본 논문에서는 IEEE 802.11n 규격에 사용되는 QC-LDPC 부호들과 (8751,8192) 부호를 이용하여 제안된 알고리즘의 성능을 검증하였다. 표 (5.1)에 실험에 사용된 부호들을 표기하였다. 모든 부호들은 BPSK 복조를 사용하고 AWGN 채널을 통과 Table 5.1: 성능 실험에 사용된 LDPC 부호 Code (n,k) coding rate Q1 (1944,1620) 0.83 Q2 (1296,1080) 0.83 M1 (8751,8192) 0.94 한 신호에 대하여 실험이 시행되었으며, 부호 Q1 과 Q2는 4-PAM 복조를 사용한 등가 채널 모델에서의 성능평가가 함께 이루어 졌다. 모든 BF 기반의 알고리즘은 최대 반복 복호 횟수를 200회로 제한하였고 합곱 알고리즘은 50회로 제한하였다. 5.2 실험 결과 그림 (5.1)은 부호율이 0.94인 M1 부호의 비트 오류율을 보여준다. M1 부호는 높은 부호율을 가지는 긴 길이의 부호로써 SSD에 적당한 부호이다. 이 부호에서 제안된 알고리즘은 10 6 의 BER에서 IMWBF 보다 약0.6dB 좋은 성능을 보인다. IEEE 802.11n 규격의 Q1 부호에서의 결과를 보면, 그림 (5.2)에서 볼수 있듯 이 기존의 IMWBF가 합곱 알고리즘에 비해 BER 10 4 에서 약 2dB 성능 열화가 있는데 반해 제안된 알고리즘은 약 1dB 정도까지 근접함을 알수 있다. 41

제 5 장 실험 결과 Figure 5.1: M1 부호의 비트 오류율 성능 또, Q2 부호에서는 그림 (5.3)에서 볼수 있듯이 IMWBF 알고리즘이 합곱 알 고리즘에 비해 BER 10 4 에서 약 2.5dB 뒤떨어지는 성능을 보였으나, 제안된 알 고리즘은 약 1dB까지 근접하였다. 그림 (5.4)는 SSD의 등가 통신 채널 모델인 4-PAM 채널에서 소거 사건의 발 생 확률을 정의하는 ϵ값을 보여준다. SSD 등가 채널 모델에서는 4-PAM 복조기가 소거 사건이 발생한 경우 이를 알려주는 신호를 제공함으로써 두 개의 서로 다른 크로스오버 확률을 가지는 BSC 채널이 번갈아 가며 사용되는 것으로 이해할 수 있다. 즉, 소자의 출력값의 신뢰성이 떨어진다고 판정되면 상대적으로 높은 크로 스오버 확률을 가지는 BSC 채널을 통과한 신호를 수신한 것으로 이해할 수 있다. 이 때의 크로스오버 확률은 신호대 잡음비과 ϵ값에 따라 결정되며 최적의 ϵ값을 찾는 것이 중요하다. 그림 (5.4)에서는 제안된 알고리즘을 사용하였을 때 ϵ값에 따른 비트오류율을 도시하였다. 가장 좋은 성능을 보이는 ϵ = 0.3에서 등가 통신 채널 모델에서의 성능 분석이 이루어 졌다. 42

제 5 장 실험 결과 Figure 5.2: Q1 부호의 AWGN 채널에서의 비트 오류율 성능 그림 (5.5) 과 그림 (5.6)는 SSD의 등가 통신 채널인 4-PAM 채널에서의 Q1 부호의 비트오류율과 블록 오류율 성능을 나타낸다. 제안된 알고리즘은 합곱 알 고리즘에 약 0.5dB정도 까지 근접하는 성능을 나타낸다. 기존의 WBF 알고리즘이나 IMWBF 알고리즘은 채널로부터 수신한 신호의 크기를 신뢰도로 사용하여 BF 알고리즘에 비해 성능 향상을 얻을 수 있었다. 그러 나 이러한 알고리즘은 경판정된 결과값만이 얻을수 있는 BSC와 같은 채널에서는 적용할 수 없다. 그러나 본 논문에서 제안된 알고리즘은 채널에서 수신한 정보가 경판정된 결과값 뿐 일때에도 적용이 가능하다. 즉, 등가 채널 모델에서 ϵ값이 0인 경우에는 모든 심볼에 대해서 소거사건이 발생하지 않으므로 하나의 BSC 채널을 사용하는 것과 동일한 경우이다. 그림 (5.7) 에서 상기와 같은 경우 제안된 알고리즘과 경판정된 결과값만 이 용하여 복호하는 BF 알고리즘의 BER 성능을 도시 하였다. 제안된 알고리즘 BF 알고리즘에 비해 BER 10 5 에서 약 0.5dB의 성능향상을 보인다. 43

제 5 장 실험 결과 Figure 5.3: Q2 부호의 AWGN 채널에서의 비트 오류율 성능 다음은 제안된 알고리즘의 복호 속도에 대한 분석이다. 제안된 알고리즘은 반전 함수의 크기에 따라 수신신호 y n 을 갱신하므로 검사 노드에서 계산하는 가 중치 값 w ji 의 계산을 반복하게 된다. 따라서 기존의 알고리즘에 비해 추가적인 연산이 요구되지만 복호에 소요되는 반복 복호 횟수가 기존의 알고리즘에 비해 매 우 적기 때문에 하나의 부호어를 성공적으로 복호하기 위해 요구되는 전체 연산 횟수에서 약점을 극복할 수 있다. Q1 부호와 Q2 부호를 복호할 때 소요되는 평균 반복 복호 횟수를 그림 (5.8) 와 그림 (5.9)에 도시하였다. 그림에서 볼 수 있듯이 제안된 알고리즘은 기존의 BF 기반의 알고리즘에 비해 복호 수렴 속도가 훨씬 빠르다. 이는 제안된 알고리즘이 한 번의 반복 복호에 다수개의 비트는 반전한다는 사실에 기인한다. 그림 (5.10)와 그림 (5.11)은 Q1 과 Q2 부호의 등가 통신 채널에서의 평균 반복 복호 횟수를 도시한 것이다. AWNG 채널에 비해 그 차이는 줄어들었으나 44

제 5 장 실험 결과 Figure 5.4: 등가 채널 모델의 ϵ값의 최적화 여전히 제안된 알고리즘의 복호 수렴 속도가 빠름을 보인다. 45

제 5 장 실험 결과 Figure 5.5: Q1 부호의 4-PAM 채널에서의 비트 오류율 성능: ϵ = 0.3 Figure 5.6: Q1 부호의 4-PAM 채널에서의 비트 오류율 성능: ϵ = 0.3 46

제 5 장 실험 결과 Figure 5.7: Q1 부호의 4-PAM 채널에서의 비트 오류율 성능: Figure 5.8: Q1 부호의 AWGN 채널에서의 평균 반복 복호 횟수: 47

제 5 장 실험 결과 Figure 5.9: Q2 부호의 AWGN 채널에서의 평균 반복 복호 횟수: Figure 5.10: Q1 부호의 4-PAM 채널에서의 평균 반복 복호 횟수: 48

제 5 장 실험 결과 Figure 5.11: Q2 부호의 4-PAM 채널에서의 평균 반복 복호 횟수: 49

제 6 장 결론 본 논문에서는 MLC NAND 플래시 소자를 이용하는 SSD에서 사용될 수 있는 효율적인 LDPC 부호의 복호 알고리즘을 제안하였다. 소자의 정보 저장 밀도가 증가함에 따라 보다 정교한 오류 정정 부호의 필요성이 대두되면서 좋은 성능과 고속 복호가 가능한 LDPC 부호에 대한 연구가 진행되어 왔다. SSD에서는 제한 된 정보만을 얻을 수 있기 때문에 적은 정보량으로 높은 성능을 낼수 있는 오류 정정 부호로써 LDPC 부호가 관심을 얻고 있다. LDPC 부호의 합곱 알고리즘은 매우 좋은 오류 정정 성능을 보이지만 복호에 필요한 연산을 하드웨어로 구현할 때 높은 복잡도를 요구한다. 그러나 비트 반전 알고리즘은 반복 복호시 간단한 연 산만을 필요로 하기 때문에 고속 복호가 가능하고 낮은 복잡도로 하드웨어 구현이 가능하다. 기존의 비트 반전 알고리즘이나 가중치를 가지는 비트 반전 알고리즘은 반전 된 비트의 신뢰도가 복호 전반에 걸쳐 그래로 유지되기 때문에 좋은 성능을 얻지 못하였다. 또한 한번의 반복 복호시 한 개나 소수개의 경판정된 비트많이 반전될 뿐이고 나머지 비트들은 영향을 받지 않기 때문에 복호 연산에 따른 정보의 상당 량이 낭비되는 문제점이 있었다. 따라서 반전된 비트의 신뢰도를 갱신하여 다음 반복 복호에 사용하고 반전 함수 값에 따라 여러 개의 비트를 반전 시킬수 있는 신뢰도 추정 기반의 비트 반전 알고리즘을 제안하였다. 본 논문에서 제안된 알고리즘을 이용하여 IEEE 802.11n 규격에서 쓰이는 QC- LDPC 부호에 대한 성능 평가를 하였으며, 기존의 알고리즘에 비해 합곱 알고리 즘에 상당히 근접한 BER 성능을 보임을 확인하였다. 또한 SSD에서 발생하는 오 류를 등가의 통신 모형으로 표현하여 실험한 결과에서도 기존의 비트 반전 알고리 50

제 6 장 결론 즘에 비해 BER 뿐만이 아니라 평균 반복 복호 횟수에서도 향상된 성능을 보임을 확인하였다. 그러나 제안된 알고리즘은 비트 반전시 사용하는 문턱값 따라 신뢰도가 갱 신되는 비트의 숫자에 영향을 미치며, 이는 추가적인 복호 복잡도를 요구 한다. 따라서 성능 향상과 복잡도 사이에서 최적의 문턱값을 찾는 방법을 많은 모의 실 험을 통해 구하는 것이 필요하다. 51

참 고 문 헌 [1] R. G. Gallager, Low density parity check codes, IRE Trans.Inf.Theory,vol.8,no.,pp.21-28,Jan.1962. [2] D. J. C. Mackay and R. M. Neal, Near Shannon limit performance of low density parity check codes, Electron. Lett, vol. 32, no. 18, pp. 1645 1646, 1996. [3] D. J. C. Mackay, Good error-correting codes based on very sparse matrices, IEEE Trans.Inf.Theory, vol. 45, pp. 399-431,Mar. 1999. [4] B. Gaines, Advances in Information Systems Science,, New York: Plenum, 1969, ch. 2, pp. 37 172. [5] M. P. C. Fossorier, M. J. Mihaljevic and H. Imai Reduced complexity iterative decoding of low-density parity check codes based on belief propagation, IEEE Trans. Commun., vol. 47, pp. 673 680, May. 1999. [6] T. Richardson and K. Urbanke, The capacity of low-density parity check codes under message-passing decoding, IEEE Trans. Inform. Theory, vol. 47, pp. 599 618, Feb. 2001. [7] F, Kschischang, B, Frey and H, Loeliger Factor graphs and the sum-product algorithm, IEEE Trans. Inf. Theory, vol. 47, pp. 498 519, Feb.2001 [8] R, M, Tanner, A recursive approach to low complexity codes, IEEE Trans. Inform. Theory, vol. IT-27, pp. 533 547, Sept. 1981. 52

참 고 문 헌 [9] Y. Kou, S. Lin and M. P. C. Fossorier, Low-density parity check codes based on very sparse matrices, IEEE Trans. Inf. Theory, vol.47, pp. 271 236, Nov.2001. [10] J. Zhang and M. P. C. Fossorier, A modified weighted bit-flipping decoding of low-density parity-check codes, IEEE Commun. Lett,, vol.8, pp. 165 167, Mar.2004. [11] M. Jiang, C. Zhao, Z. Shi and Y. Chen, An improvement on the modified weighted bit flipping decoding algorithm for LDPC codes, IEEE Commun. Lett,, vol.9, pp. 814 816, Sept.2005. [12] F. Guo and L. Hanzo, Reliability ratio based weighted bit-flipping decoding for LDPC codes, VTC Spring 2005. IEEE, vol.1, pp. 709-713, May.2005. [13] X. Wu, C. Ling, M. Jiang, E. Xu, C. Zhao and X. You, New Insights in Weighted Bit-Flipping Decoding, IEEE Trans. Commun., vol.57, pp. 2177-2180, Aug.2009. [14] Y. Maeda, H, Kaneko, Error Control Coding for multilevel cell flash memories using nonbinary low-density parity-check codes, 24th IEEE international Symposium on Defect and Fault Tolerance in VLSI Systems,pp.368-370, 2009. [15] D. J. C. MacKay, Encyclopedia of sparse graph codes[online]. Available: http://www.inference.phy.cam.ac.uk/mackay/codes/data.thml [16] P. H. Siegel, Recording codes for digital magnetic storage, IEEE Transactions on Magnetics, vol.mag-21, no.5, pp. 1344-1349, Sept. 1985. 53

참 고 문 헌 [17] M. Fossorier, Quasi-cyclic Low-Density Parity-Check Codes from Circulant Permutation Matrices, IEEE Trans. Inf. Theory, vol.50, no.8, pp.1788 1793, 2004. [18] R. Lucas, M. Fossorier,Y. Kou, and S. Lin Iterative decoding of one-step majority logic decodable codes based on belief propagation, IEEE Trans. Commun, vol. 47, pp. 2711 2736, Nov. 2001. [19] Y. Kou, S. Lin and M. Fossorier Low-density parity-check codes based on finite geometries: A Rediscovery and new results, IEEE Trans. Inform. Theory, vol. 47, pp. 2711 2736, Nov. 2001. 54