큰 둘레를 갖는 선형 시간 복잡도의 LDPC 부호와 Belief Propagation 복호를 위한 2-Staged Informed Dynamic Scheduling 기법
Linear-Time LDPC Codes of Large Girth and 2-Staged Informed Dynamic Scheduling for Belief Propagation Decoding of LDPC Codes
- 발행기관 서강대학교 대학원
- 지도교수 김세준
- 발행년도 2009
- 학위수여년월 2009. 2
- 학위명 석사
- 실제URI http://www.dcollection.net/handler/sogang/000000044795
- 본문언어 한국어
초록/요약
Low-density parity-check (LDPC) codes have low decoding complexity and good performance near Shannon limit. However, there are two aspects that are worth being considered to improve their performance. First, LDPC codes have a disadvantage of high encoding complexity. Representative way to approach this problem is to force the parity check matrix to have lower (or upper) triangular form. But this restriction generally results in some degrade of performance. In this paper, we suggest a modified PEG algorithm, an algorithm to construct graphs with a largest girth possible and to force the parity check matrix to have an approximate lower triangular form. With this, the performance loss of LDPC codes can be minimized compared to parity check matrix without any constraints. Second, the scheduling algorithm of belief propagation (BP) can be improved when it is used to decode LDPC codes. The BP decoding decodes LDPC codes by iterative message passing on a code graph. Among many scheduling algorithms that have been proposed to decide the sequence of message passing, residual belief propagation (RBP) and node-wise RBP (NWRBP) are representative informed dynamic scheduling methods. Each algorithm has merit in convergence speed and overall performance respectively. In this research, we propose a novel, modified informed dynamic scheduling algorithm that is capable of combining the merit of both RBP and NWRBP To verify the performance of proposed algorithmic methods, we performed experiments over BEC channel for modified PEG algorithm and over AWGN channel for informed dynamic scheduling algorithm. Results show that the modified PEG can be a good alternative for the existing constructing algorithm while the new informed dynamic scheduling algorithm outperformed existing algorithm.
more초록/요약
최근에 큰 각광을 받고 있는 low-density parity-check (LDPC) codes는 Shannon limit에 근접하는 성능과 빠른 decoding 속도를 갖는다. 반면에 다음의 두 가지 측면에서 개선할 여지가 있다. 첫 번째는 다른 codes에 비해 상대적으로 높은 encoding complexity이다. LDPC codes의 대표적인 단점인 이 문제를 해결하기 위해 여러 가지 방법들이 제안되었다. 그중 가장 대표적인 것은 parity check matrix를 lower(혹은 upper) triangular form으로 제한하는 것이다. 하지만 이러한 제약 조건은 일반적으로 codes의 성능을 하락시킨다. 본 논문에서는 가능한 한 큰 girth를 갖는 graph를 생성하는 기법인 PEG에 approximate lower triangular form을 갖도록 제약 조건을 주어 linear-time encoding이 가능하면서도 동시에 제약 조건이 없는 parity check matrix에 비해 성능 하락이 최소화 되는 LDPC codes를 생성하는 modified PEG algorithm을 제안한다. 두 번째는 LDPC codes의 대표적인 decoding 방법인 belief propagation (BP)의 scheduling algorithm이다. BP decoding은 code graph상에서의 반복적인 message passing을 통해 decoding한다. 이 때 message passing을 하는 순서를 결정하는 여러 scheduling algorithm이 존재하는데 informed dynamic scheduling의 대표적인 기법인 residual belief propagation(RBP)과 node-wise RBP(NWRBP)는 각각 convergence 속도와 성능에서 장점을 갖는 방법들이다. 본 논문에서는 기존의 RBP와 NWRBP의 장점을 합칠 수 있는 변형된 informed dynamic scheduling 기법을 새로운 algorithm으로 제안한다. 제안한 algorithm들의 성능을 확인하기 위해 modified PEG algorithm에 대해서는 BEC channel에서의 실험을 통해 기존 방법에 대한 좋은 대안이 될 수 있음을 확인하였고 새로운 informed dynamic scheduling 기법에 대해서는 AWGN channel에서의 실험을 통해 기존의 방법보다 더 좋은 성능을 내는 것을 보인다.
more목차
제1장 서론 = 1
제2장 배경 지식 및 기호 = 3
제3장 효율적인 부호화와 Progressive Edge-Growth Algorithm = 6
3.1 LDPC codes의 효율적인 부호화 = 6
3.2 PEG algorithm과 PEG의 선형 시간 부호화 = 9
3.2.1 PEG algorithm = 9
3.2.2 PEG의 선형 시간 부호화 = 13
제4장 선형 시간 부호화를 위한 Modified Progressive Edge-Growth Algorithm = 15
4.1 선형 시간 부호화를 위한 modified PEG algorithm = 16
4.1.1 Method A = 16
4.1.2 Method B = 19
4.2 실험 결과 = 21
제5장 LDPC Codes의 복호 방법 = 26
5.1 BP 복호 = 26
5.2 RBP 복호 = 27
5.3 Node-wise RBP 복호 = 30
제6장 2-Staged Informed Dynamic Scheduling = 34
6.1 Suspicious nodes = 35
6.2 2-Staged informed dynamic scheduling = 36
6.3 실험 결과 = 38
제7장 결론 및 향후 연구 과제 = 43
참고문헌 = 45
그림목차
[그림 1] Parity check matrix 와 bipartite graph = 3
[그림 2] Variable node 를 root로 하는 tree = 5
[그림 3] Approximate lower triangular form을 갖는 parity check matrix = 6
[그림 4] 를 root로 하는 tree와 depth 안의 neighborhood = 10
[그림 5] Pseudocode for PEG algorithm = 12
[그림 6] Pseudocode for linear time encoding PEG algorithm = 14
[그림 7] Pseudocode for proposed PEG algorithm = 18
[그림 8] Method B = 19
[그림 9] Pseudocode for proposed transformation algorithm = 20
[그림 10] , 일 때 시뮬레이션 결과 = 22
[그림 11] , 일 때 시뮬레이션 결과 = 24
[그림 12] Pseudocode for RBP algorithm = 29
[그림 13] Pseudocode for Node-wise RBP algorithm = 31
[그림 14] Trapping set을 해결하는 check node의 update sequence = 32
[그림 15] Set of suspicious variable nodes의 평균 크기 = 37
[그림 16] , 일 때 SNR을 고정시킨 상태에서 iteration이 진행될 때 4가지 BP decoding scheduling algorithm의 성능 비교 = 39
[그림 17] , 일 때 iteration(=30)을 고정시킨 상태에서 SNR이 변할 때 4가지 BP decoding scheduling algorithm의 성능 비교 = 41
표목차
[표 1] Computation of parity part = 8
[표 2] Computation of parity part = 8
