[논문]병렬 CRC 생성 방식을 활용한 BCH 코드 복호기 설계

갈홍주; 문현찬; 이원영

doi:10.13067/jkiecs.2018.13.2.333

병렬 CRC 생성 방식을 활용한 BCH 코드 복호기 설계
Design of BCH Code Decoder using Parallel CRC Generation 원문보기

한국전자통신학회 논문지 = The Journal of the Korea Institute of Electronic Communication Sciences, v.13 no.2, 2018년, pp.333 - 340

갈홍주 (서울과학기술대학교 전자IT미디어공학과) , 문현찬 (서울과학기술대학교 전자IT미디어공학과) , 이원영 (서울과학기술대학교 전자IT미디어공학과)

초록
AI-Helper

본 논문은 병렬 CRC 생성 방식을 적용한 BCH 코드 복호기를 소개한다. 기존에 사용되는 병렬 신드롬 생성기로 LFSR(: Linear Feedback Shift Register)을 변형한 방식을 사용하면 짧은 길이의 코드에 적용하는 데 많은 면적을 차지한다. 제안하는 복호기는 짧은 길이 코드워드의 복호화를 위해 병렬 CRC(: Cyclic Redundancy Check)에서 체크섬을 계산하는 데 사용되는 방식을 활용하였다. 이 방식은 병렬 LFSR과 비교해 중복된 xor연산을 제거해 최적화된 조합회로로 크기가 작고 짧은 전파지연을 갖는다. 시뮬레이션 결과 기존 방식 대비 최대 2.01ns의 지연시간 단축 효과를 볼 수 있다. 제안하는 복호기는 $0.35-{\mu}m$ CMOS 공정을 이용하여 설계하고 합성되었다.

Abstract ▼ AI-Helper

This paper introduces a BCH code decoder using parallel CRC(: Cyclic Redundancy Check) generation. Using a conventional parallel syndrome generator with a LFSR(: Linear Feedback Shift Register), it takes up a lot of space for a short code. The proposed decoder uses the parallel CRC method that is widely used to compute the checksum. This scheme optimizes the a syndrome generator in the decoder by eliminating redundant xor operation compared with the parallel LFSR and thus minimizes chip area and propagation delay. In simulation results, the proposed decoder has accomplished propagation delay reduction of 2.01 ns as compared to the conventional scheme. The proposed decoder has been designed and synthesized in $0.35-{\mu}m$ CMOS process.

주제어

AI 본문요약
AI-Helper

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

문제 정의

본 논문에서는 CRC에서 체크섬을 구하기 위한 병렬 회로 설계 방식을 차용해 쉽게 BCH 복호기 중 병렬 신드롬 생성기를 구성하는 방식을 제안한다. 짧은 코드워드를 갖는 BCH 코드에서 병렬 LFSR 방식을 이용한다면 상쇄되는 불필요한 연산이 포함되기 때문에 크기가 크고 속도가 느린 반면, 병렬 CRC 생성 방식을 활용하면 병렬 입력에 대한 가장 최적화된 회로를 구성할 수 있다.
이러한 문제를 해결하기 위해서 본 논문에서는 병렬 CRC 생성 방식을 사용한 병렬 복호기를 제안하고 있다. 본문의 2장에서 BCH 코드의 기본적인 설명과 병렬 CRC 생성 방식을 적용한 예시를 통해 짧은 코드워드의 병렬 신드롬 생성기를 만들어보고 긴 코드 워드에 적용해 LFSR 기반의 신드롬 생성기를 변형시키는 방식을 제안한다.

가설 설정

4. 오류위치의 오류를 정정한다.

제안 방법

4단계, 매트릭스를 토대로 각 레지스터별 출력에 영향을 주는 것을 확인하여 병렬 CRC 방정식을 작성한다. 3 비트 입력에 대한 병렬 CRC 방정식은 식 (4)와 같이 작성할 수 있다.
최대 8개의 병렬 입력을 받아 13개의 레지스터를 통해 처리하는 구조에 대해 병렬 CRC 생성 방식을 이용해서 매트릭스를 작성한다. LFSR 구조 생성기의 입력에 따른 레지스터 출력 값을 정리하고, 초기 레지스터 상태에 따른 레지스터 출력 값의 변화를 계산한다. 입력 값과 레지스터 초기 값에 대한 LFSR 연산 결과 값을 바탕으로 선형적인 특징을 이용하여 병렬 CRC 방정식을 작성한다.
병렬 LFSR 방식과 CRC 생성 방식 구현한 신드롬 생성기의 전파 지연 특성을 비교하기 위해서 회로를 verilog로 디자인하고 0.35μm CMOS 공정 라이브러리를 이용하여 합성했다.
이러한 문제를 해결하기 위해서 본 논문에서는 병렬 CRC 생성 방식을 사용한 병렬 복호기를 제안하고 있다. 본문의 2장에서 BCH 코드의 기본적인 설명과 병렬 CRC 생성 방식을 적용한 예시를 통해 짧은 코드워드의 병렬 신드롬 생성기를 만들어보고 긴 코드 워드에 적용해 LFSR 기반의 신드롬 생성기를 변형시키는 방식을 제안한다. 3장에서는 실험을 통해 얻은 내용에 대해 논의하고, 4장에서 결론을 맺는다.
CRC(: Cyclic Redundancy Check)는 간단한 오류 확인 방법으로써 전송하는 데이터에 대한 CRC 계산 값인 체크섬을 데이터에 붙여 송신한다. 수신기에서는 수신된 데이터의 데이터 비트에 대한 체크섬 값을 다시 계산하여 기존의 CRC값과 차이가 있는지 확인해 오류가 생겼는지 확인 한다. 이러한 CRC를 계산하는 방식은 LFSR을 주로 이용하지만, 데이터를 순서대로 입력되는 방식이 아닌 데이터 전체를 병렬 입력을 받아 체크섬을 계산할 경우, 최적화된 조합 논리회로를 통해 기존 대비 빠른 시간 내에 CRC 계산이 가능하다[7-8].
긴 코드워드를 갖는 BCH코드에서 병렬 LFSR 방식은 신드롬 레지스터 수만큼의 병렬 입력만을 사용할 수 있다. 이를 해결하기 위해 CRC 생성 방식을 이용하여 병렬 입력의 수를 늘렸다. 이처럼 CRC 생성 방식을 이용하면 자유롭게 병렬 계수를 설정하고 쉽게 최적화된 논리를 구성할 수 있다.
LFSR 구조 생성기의 입력에 따른 레지스터 출력 값을 정리하고, 초기 레지스터 상태에 따른 레지스터 출력 값의 변화를 계산한다. 입력 값과 레지스터 초기 값에 대한 LFSR 연산 결과 값을 바탕으로 선형적인 특징을 이용하여 병렬 CRC 방정식을 작성한다. 출력이 M[0]부터 M[12]이므로 식 (6)과 같이 총 13개의 방정식이 생성된다.
LFSR에 활용되는 최소 다항식은 x⁴+x¹+1이다. 제안하는 BCH 복호기 구조는 LFSR 회로를 사용한 CRC회로를 병렬 CRC회로로 변경하는 방식을 적용함으로써 기존 LFSR를 이용한 신드롬 생성기와 동일한 출력 값을 유지하면서 병렬데이터 처리가 가능케 하였다. 예로, 그림 3과 같이 16자리 코드워드를 5자리 최소 다항식으로 나눌 경우 총 1비트씩 12번의 입력이 들어가게 된다.
이 같이 긴 연산 시간을 단축하기 위해 병렬 CRC 생성 방식을 사용하여 신드롬 생성기를 만들 수 있다. 최대 8개의 병렬 입력을 받아 13개의 레지스터를 통해 처리하는 구조에 대해 병렬 CRC 생성 방식을 이용해서 매트릭스를 작성한다. LFSR 구조 생성기의 입력에 따른 레지스터 출력 값을 정리하고, 초기 레지스터 상태에 따른 레지스터 출력 값의 변화를 계산한다.

대상 데이터

한 페이지는 4224바이트이고 그중 4096바이트는 정보데이터를 저장하는 데이터 영역이고 128바이트는 부호화된 페리티를 저장하는 여분 영역이다. 정보데이터는 512바이트의 섹터로 나눠지며 이 섹터에 대해 오류 검사를 실시한다. 즉, ECC로 한 섹터 내 2개의 오류를 수정할 수 있는 BCH (4122,4096,2)가 가장 간단한 오류정정 모델이다.

이론/모형

제안하는 BCH 복호기에서는 BCH 코드를 복호화 하는데 필요한 신드롬을 계산하기 위해 병렬 CRC 생성 방식을 적용하였다. CRC(: Cyclic Redundancy Check)는 간단한 오류 확인 방법으로써 전송하는 데이터에 대한 CRC 계산 값인 체크섬을 데이터에 붙여 송신한다.

질의응답

핵심어	질문	논문에서 추출한 답변
	BCH 코드는 주로 어디에 사용되는가?	저장매체나 통신회로 내 정보량이 증가함에 따라 신뢰성 확보를 위해 hamming 코드와 같이 단일 오류 정정에 중점을 둔 방식에 비해 BCH 코드가 ECC(: Error Correction Circuit)에 활용되고 있다. 예컨대 BCH 코드는 플래시 메모리, 이동통신, 암호화(stegnography), SRAM 등에 주로 사용된다[5-6]. 그 중 단일 통신회로를 이용하는 회로는 직렬 방식의 복호기를 사용하는 데 주로 LFSR(: Linear Feedback Shift Register)방식이 쓰인다.
	BCH 코드는 어떤 능력을 갖는가?	데이터 통신에는 다양한 방식의 오류 비트 정정 방식이 존재한다[1-4]. 다양한 방식의 오류 비트 정정 코드 중 BCH(: Bose-Chaudhuri-Hocquenghem) 코드는 두 개 이상의 다중 오류를 정정할 수 있는 부호로 뛰어난 정정 능력을 갖는다. 저장매체나 통신회로 내 정보량이 증가함에 따라 신뢰성 확보를 위해 hamming 코드와 같이 단일 오류 정정에 중점을 둔 방식에 비해 BCH 코드가 ECC(: Error Correction Circuit)에 활용되고 있다.
	LFSR방식의 단점은?	그 중 단일 통신회로를 이용하는 회로는 직렬 방식의 복호기를 사용하는 데 주로 LFSR(: Linear Feedback Shift Register)방식이 쓰인다. 그러나 모든 정보데이터가 직렬로 입력되어 복호화에 많은 시간이 소요되는 단점이 있다. 만약 정보데이터가 병렬로 입력되어 병렬 회로를 통해 처리하는 방식을 이용할 수 있다면 복호화 시간을 줄일 수 있다.

참고문헌 (10)

E. Jang, "LDPC Coding for image data and FPGA Implementation of LDPC Decoder," J. of the Korea institute of Electronic Communication Science, vol. 12, no. 4, 2017, pp. 569-574.
J. Jung, Y. Lee, and H. Shin, "A Study on Forward Error Correction of Long-Distance Submarine Optical Communication Systems," J. of the Korea institute of Electronic Communication Science, vol. 3, no. 3, 2008, pp. 170-176.
A. Doniyor and H. Suh, "An Efficient Algorithm for finding Optimal Spans to determine R1/2 Rate Systematic Convolutional Self-Doubly Orthogonal Codes," J. of the Korea institute of Electronic Communication Science, vol. 10, no. 11, 2015, pp. 1239-1244.

원문보기 상세보기
S. Lin and D. J. Costello, Error Control Coding, Saddle River: Prentice Hall, 2004.
Y. Wang and X. Zhang, "Research on the Steganography Robustness Method of BCH Single Coefficient," The Open Automation and Control Systems J., vol. 7, no. 1, 2015, pp. 910-915.
H. Wei, X. Cui, Q. Zhang, and Y. Jin, "An Enhanced Decoder for Multiple-bit Error Correcting BCH Codes," In Proc. IEEE 11th Int. Conf. on ASIC, Chengdu, China, Nov. 2015.
E. Stavinov, "A Practical Parallel CRC Generation Method," Circuit Cellar, Issue 234, no. 1, Jan. 2010, pp. 38-45.
G. Albertengo and R. Sisto, "Parallel CRC Generation," IEEE Micro, vol. 10, no. 5, Oct. 1990, pp. 63-71.

상세보기
W. Choi, J. Lee, and W. Sung "Design of High-performance Parallel BCH Decoder for Error Collection in MLC Flash Memory," J. of the Korea Contents Association, vol. 16, no. 3, Mar. 2016, pp. 91-101.
J. Zhang, Z. Wang, Q. Hu, and J. Xiao, "Optimized Design for High-speed Parallel BCH Encoder," In Proc. 2005 IEEE Int. Workshop on VLSI Design and Video Technology, Suzhou, China, May 2005.

저자의 다른 논문 :

LOADING...

표제어: 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

연합인증