순차적 신뢰전달 복호의 동적 스케줄링을 통한 LDPC 부호의 성능
On Performance of LDPC Codes through Informed Dynamic Scheduling of Sequential Belief Propagation Decoding
- 주제(키워드) LDPC , dynamic scheduling , belief propagation , decoding , coding theory
- 발행기관 서강대학교 컴퓨터공학과 대학원
- 지도교수 김세준
- 발행년도 2010
- 학위수여년월 2010. 2
- 학위명 석사
- 학과 일반대학원 컴퓨터공학과
- 실제URI http://www.dcollection.net/handler/sogang/000000045970
- 본문언어 한국어
- 저작권 서강대학교의 논문은 저작권에 의해 보호받습니다
초록/요약
최근에 큰 각광을 받고 있는 저밀도 패리티 검사 (low-density parity-check, 이하 LDPC) codes는 Shannon limit에 근접하는 성능과 빠른 복호 속도를 갖는다. 이러한 LDPC 부호의 더 나은 성능을 얻기 위하여 여러 복호 기법이 연구되고 있다. LDPC 부호의 대표적인 복호 방법은 신뢰 전달(belief propagation, 이하 BP) 알고리즘이다. BP 복호는 그래프 상에서 반복적인 메시지 교환을 통해 복호한다. 기존의 평형 (parallel) 스케줄링 기법인 flooding (이하 FLD)과 비평형 (non-parallel)인 순차적 스케줄링 기법 layered BP (이하 LBP) 기법, 그리고 동적 스케줄링 기법의 대표적인 기법으로 residual BP (이하 RBP)과 node-wise residual BP (이하 NWRBP) 방법이 있다. RBP와 NWRBP의 탐욕적인 특성은 빠른 수렴 속도와 trapping set을 해결하여 향상된 성능을 가지지만, FLD나 LBP에서는 피할 수 있는 non-trapping set 오류가 나타나는 문제가 있다. non-trapping set 오류와 trapping set 오류를 모두 해결하기 위해 LBP와 NWRBP의 혼합 스케줄링 기법이 제안 되었지만, LBP stage에서 NWRBP stage로의 전환 조건은 아직 많은 연구가 되지 않았다. 본 논문에서는 기존의 log-likelihood ratio (이하 LLR)의 부호만을 고려하는 unsatisfied-검사 노드 대신에 LLR의 크기를 전환 조건의 척도로 사용하는 적응-혼합 스케줄링 (adaptive-mixed scheduling) 기법을 제안하였다. 또 기존의 RBP, LBP와 NWRBP의 장점을 결합하는 3-staged informed dynamic scheduling(이하 3-staged IDS) 기법을 제안하고 새로운 전환 조건의 척도를 이에 응용한다. 제안한 알고리즘들의 성능을 확인하기 위해 혼합 스케줄링 기법과 3-stage IDS 기법에 대해서 AWGN channel에서의 실험을 하였다. 새로운 혼합 스케줄링 기법은 기존의 밥법에 대한 좋은 대안이 될 수 있음을 그리고 3-staged IDS는 기존의 방법보다 더 좋은 성능을 보임을 확인한다.
more초록/요약
Low-density parity-check (LDPC) codes have low decoding complexity and performance near the Shannon limit. However, there are two aspects that are worth being considered to improve their performance when code length is finite. 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. With respect to the order of message passing, there are the parallel scheduling scheme (flooding), non-parallel scheduling scheme (Layered BP). Among many scheduling algorithms that have been proposed to decide the sequence of message passing, residual belief propagation (RBP) and node-wise RBP (NWRBP) have shown excellent performance. Due to greediness, RBP and NWRBP have fast convergence speed and solve the trapping set error. Howere RBP and NWRBP have a problem that induce non-trapping set errors and trapping set errors. A mixed scheduling scheme using LBP and NWRBP was proposed by Casado but the switch condition from LBP stage to NWRBP stage and threshold measure of switch condition have many weaknesses. In this research, we propose a novel adaptive mixed scheduling using not sign but size of log-likelihood ratio and a 3-staged informed dynamic scheduling which combine the merit of three decoding scheme RBP, LBP and NWRBP. To verify the performance of proposed schemes, we performed experiments over AWGN channel for adaptive mixed scheduling and 3-staged informed dynamic scheduling scheme. Results show that adaptive mixed scheduling scheme can be a good alternative for the existing method while the 3-staged IDS scheme outperformed existing algorithms.
more