[논문]Quasi-Cyclic Low Density Panty Check 복호기의 다양한 설계 관점에 대한 성능분석

정수경; 박태근

[국내논문] Quasi-Cyclic Low Density Panty Check 복호기의 다양한 설계 관점에 대한 성능분석
Performance Analysis on Various Design Issues of Quasi-Cyclic Low Density Parity Check Decoder 원문보기

電子工學會論文誌. Journal of the Institute of Electronics Engineers of Korea. SD, 반도체, v.46 no.11=no.389, 2009년, pp.92 - 100

정수경 (가톨릭대학교 정보통신전자공학부) , 박태근 (가톨릭대학교 정보통신전자공학부)

초록
AI-Helper

본 논문은 LLR-BP 복호 알고리즘을 사용하는 LDPC 복호기의 하드웨어 구조 분석하고 효율적인 복호기의 설계 방법들을 제시하였다. 또한 설계 시 복호 성능 및 하드웨어 복잡도에 영향을 미칠 수 있는 다양한 설계 이슈들을 제시하고 복호 성능의 변화를 모의실험을 통하여 분석하였다. 오류확률을 전달하는 메시지의 양자화는 정수부 3비트, 소수부 4비트를 할당하였고, 복호 성능이 저하되지 않도록 사전정보에 정수부 2비트, 소수부 4비트를 할당하였으며 LUT로 구현되는 $\Psi$(x) 함수를 조합회로인 PWL 블록으로 대체하여 하드웨어 구조의 개선에 대해 논의하였다. 복호 시간을 단축하기 위하여 중첩 스케줄링을 적용하고, 각 복호기 구조 및 설계 변수들의 제한에 따른 하드웨어 자원을 비교함으로써, 하드웨어 복잡도를 분석하였다.

Abstract ▼ AI-Helper

In this paper, we analyze the hardware architecture of Low Density Parity Check (LDPC) decoder using Log Likelihood Ration-Belief Propagation (LLR-BP) decoding algorithm. Various design issues that affect the decoding performance and the hardware complexity are discussed and the tradeoffs between the hardware complexity and the performance are analyzed. The message data for passing error probability is quantized to 7 bits and among them the fractional part is 4 bits. To maintain the decoding performance, the integer and fractional parts for the intrinsic information is 2 bits and 4 bits respectively. We discuss the alternate implementation of $\Psi$(x) function using piecewise linear approximation. Also, we improve the hardware complexity and the decoding time by applying overlapped scheduling.

Keyword

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문에서는 다양한 설계 관점에서 LDPC 복호기의 하드웨어 구현을 살펴보고, 분석하여 효율적인 복호기의 설계 방법들을 제시하였다. 오류확률을 전달하는 메시지의 양자화에 있어서, 하드웨어 복잡도와 복호 성능 간의 균형을 고려하여 정수부 3비트, 소수부에 4비트를 할당한 (7, 4) 양자화를 선택하였다.
본 논문에서는 LLR-BP(Log Likelihood Ration -Belief Propagation) 복호 알고리즘 기반의 QC-LDPC (Quasi Cyclic Low Density Parity Check) 복호기의 및성능 및 복잡도에 영향을 미칠 수 있는 다양한 설계 이슈들을 제시하고, 각 설계 변수들의 변화에 따른 성능을 비교 분석하여 효율적인 QC-LDPC 복호기 설계에 적용할 수 있는 설계 방법을 제안한다.

가설 설정

실험에 사용한 패리티 검사행렬은 NASA 표준문서®의 QC-LDPC H행렬을 사용하였으며, C언어로 구현된 랜덤 발생기로부터 발생된 정보를 메시지로 사용하였다. NASA QC-LDPC 부호화기로부터 부호화된 신호 T과 '0'은 각각 T과 '-T로 변조시키는 BPSK(Binary Phase Shift Keying)변조 후, 평균이 0이고, 분산이 No/2인 AWGN(Additive White Gaussian Noise) 채널을 통하여 정보가 전송된다고 가정한다. 하나의 코드 워드의 길이는 N = 8176이고, 메시지의 길이는 7154비트, 잉여 패리티 비트 P는 1022 비트이다.

제안 방법

먼저 정수부 비트 수를 고정시키고 소수부 비트 수를 변경시킬 경우 전체 비트 수도 같이 변하게 하여 성능 분석을 하였다. 소수점 이하 비트 수가 커짐에 따라 성능이 향상됨을 확인할 수 있다.
이를 근거로 0S) 함수의 값을 입력 c의 범위에 따라 1차 함수의 PWL(Piecewise linear approximation)로 근사화하면 W(z) 값을 LUT 메모리 대신 조합회로만으로 구현할 수 있다. 본 연구에서는 빈도가 높아 복호에 절대적인 영향을 미치는 W(c)값의 최소값 3개를 상수로 선택하고, 나머지 구간을 1차 함수 조각으로 구현하였다. 상수값 3개와 1차 함수 조각의 개수가 1, 2, 3, 4일 때 각각의 블록을 PWL4, PWL5, PWL6, PWL7로 정의하였고 각 구간별 정보 및 각각의 MSE(Mean Square Error)는 표 2 에 나타나 있다.
설계 방법들을 제시하였다. 오류확률을 전달하는 메시지의 양자화에 있어서, 하드웨어 복잡도와 복호 성능 간의 균형을 고려하여 정수부 3비트, 소수부에 4비트를 할당한 (7, 4) 양자화를 선택하였다. 채널로부터의 사전정보를 저장하는 버퍼의 구현이 정수 부에 복호기인 경우에 정수부에 2, 소수부에 4비트를 할당한 (6, 4) 양자화를 하여도 복호 시 성능 저하가 거의 없는 LDPC 복호기를 설계할 수 있다.
기존에 LUT 메모리로 구현되는 비선형 皿) 함수를 PWL 근사방법으로 대체하여 복호기의 주요 연산구조가 모두 조합회로로만 구현할 때 다양한 문제들을 분석하였다. 이렇게 함으로써 파이프라인 등, 구조적인 개선을 용이하게 할 수 있고 ROM 테이블을 제거할 수 있다.
어떤 구조로 복호기를 설계하는가에 따라서 복호기에 적용될 설계 변수들의 제한이 달라짐을 각 구조에 병렬화 지수 를 적용하였을 때 필요한 하드웨어 자원을 비교하였다. 분석된 내용들을 구현할 복호기에 맞게 적절히 선택하면 적은 비용으로 우수한 성능을 갖는 QC-LDPC 복호기를 설계할 수 있다.
비교하였다. 분석된 내용들을 구현할 복호기에 맞게 적절히 선택하면 적은 비용으로 우수한 성능을 갖는 QC-LDPC 복호기를 설계할 수 있다.

대상 데이터

2와 같이 나타내었다. 실험에 사용한 패리티 검사행렬은 NASA 표준문서®의 QC-LDPC H행렬을 사용하였으며, C언어로 구현된 랜덤 발생기로부터 발생된 정보를 메시지로 사용하였다. NASA QC-LDPC 부호화기로부터 부호화된 신호 T과 '0'은 각각 T과 '-T로 변조시키는 BPSK(Binary Phase Shift Keying)변조 후, 평균이 0이고, 분산이 No/2인 AWGN(Additive White Gaussian Noise) 채널을 통하여 정보가 전송된다고 가정한다.

성능/효과

최초로 정의된 S, 顶, 册 LDPC 부호는 부호어의 길이가 n이고, 열(column)이 포함하는 1의 개수를 j, 각각의 행(row)이 갖는 1의 개수로 k를 결정하여 패리티검사 행렬의 각 행과 열이 모두 동일한 개수의 1을 갖도록 균일하게 구성하며, Gallager는 이 부호를 반복 복호 하면 부호 어의 길이 n이 커짐에 따라 오류확률이지 수적으로 0에 접근한다는 것을 보였다. 그러나 논문발표 당시 LDPC부호는 반복 복호가 가지는 많은 계산량 등을 비롯하여 그 당시 컴퓨터 기술로는 모의실험이 어려운 한계 등으로 인해 학계의 주목을 받지 못하였지만, 최근에 이러한 단점을 극복할 수 있는 여러 가지 방법들이 제시되고 있다.
분석을 하였다. 소수점 이하 비트 수가 커짐에 따라 성능이 향상됨을 확인할 수 있다. 소수점 이하 비트 수가 4일 때까지는 비트 오율의 값이 크게 차이를 보이며 향상되나, 5비트 이상부터는 메시지를 양자화하지 않고 실수로 복호한 경우와 비교하여 비트 오율의 차이가 크지 않았다.
소수점 이하 비트 수가 커짐에 따라 성능이 향상됨을 확인할 수 있다. 소수점 이하 비트 수가 4일 때까지는 비트 오율의 값이 크게 차이를 보이며 향상되나, 5비트 이상부터는 메시지를 양자화하지 않고 실수로 복호한 경우와 비교하여 비트 오율의 차이가 크지 않았다. 그러나 소수점 비트가 3으로 할당된 (6, 3)의 경우는(7, 4), (8, 5)의 경우보다 소수점 이하의 비트수가 부족하여 성능이 떨어진다.
그러나 소수점 비트가 3으로 할당된 (6, 3)의 경우는(7, 4), (8, 5)의 경우보다 소수점 이하의 비트수가 부족하여 성능이 떨어진다. 이 실험을 통해 성능을 분석한 결과 고정 소수점 연산에서 전체비트 수를 최적으로 고정시킬 경우 소수점 이하 4비트일 때의 결과가 실수 값을 이용한 결과와 근접함을 확인하였다. 따라서 전체 복호기 내에 전달되는 모든 데이터는 q= 7, /= 4인(3, 4) 고정 비트 할당을 갖도록 하였다.
이 실험 결과로 보아 PWL4는 성능에서 현저한 저하를 보이며 PWL5〜PWL7의 경우는 LUT와 비교할 만한 성능을 보이므로 설계환경에 따라 LUT의 대체가 가능하다.
메모리 영역의 비교를 통해 알아본 것과 같이, 스케줄링을 적용하지 않은 부호 어의 반복복호시간 2mn에비해, 스케줄링을 적용한 복호 시간 (m + 2)n+ (2+1) 은 부행렬의 오프셋 d가 부행렬의 크기 m보다 훨씬 작을수록 중첩으로 얻을 수 있는 효율이 크다. 각 NPU 들이 동시에 메모리에 접근하는 경우-, 각 NPU에 메모리 주소를 전달하는 주소 발생기 (address generator) 는오프셋이 서로 다른 부행렬을 동시에 복호하기 위해서 max {%&}를 기준으로 주소를 발생시켜야 하며, 1회 복호 시 m— max 1 만큼의 복호 시간을 절약할 수 있다.

참고문헌 (12)

R. G. Gallager, "Low-Density Parity-Check Codes," IRE Trans. Iriform Theory, Vol. IT-B, pp, 21-28, Jan. 1962
J. C. Moreira and P. G. Farrell, Essentials of Error-Control Coding, John Wiley&Sons, 2006
David J. C. MacKay et al, "Good error-correctiong codes based on very sparse matrices," IEEE Trans. on Iriform Theory, Vol. 45, pp. 399-431, Mar. 1999

상세보기
K. S. Andrews, S. Dolinar, C. R. Jones, F. Pollara and J. Harnkins, "The Development of Turbo and LDPC Codes for Deep-Space Applications," Proceedings of IEEE, Vol. 95, no. 11, Nov. 2007

상세보기
Joon-Sung Kim and Hong-Yeop Song, "Concatenated LDGM Codes with Single Decoder," IEEE Communimtions Letters, Vol. 10, no. 4, April. 2000
T. J. Richardson and R. L. Urbanke, "The Capacity of Low-Density Parity-Check Codes Under Message-Passing Decoding," IEEE Trans. Iriform Theory, Vol. 47, pp. 599-618, Feb. 2001

상세보기
Goddard Space Flight Center, GSFC-STD-9100, , Mar. 2008
Keshab K. Parhi, VLSI Digital Signal Processing Systems Design and Implementation, John Wliey&Sons, 1999
Daesun Oh and K. K. Parhi, "Low Complexity Decoder Architecture for Low-Density Parity-Check Codes," Journal of Signal Processing Systems, Apr. 2008

상세보기
A. J Blanksby and Chris J Howland, "A 600-mW 1-Gb/s 1024-b, Rate-1/2 Low-Density Parity-Check Code Decoder," IEEE Solid-State Circuits, Vol. 37, no. 3, Mar. 2002
Z. Wang and Z. Cui, "Low-Complexity High-Speed Design for Quasi-Cyclic LDPC Codes," IEEE Trans. VLSI Systems, Vol. 15, no. 1, Jan. 2007
Marjan Karkooti and Joseph R. Cavallaro, "Semi-Parallel Reconfigurable Architectures for Real-Time LDPC Decoding," in Proc. of IEEE conf. on Information Technology: Coding and Computing, Vol. 1, pp. 579-585, Apr. 2004

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증