A Design of Modified Euclidean Algorithm using Finite State Machine
Sung-Jin Kang · Journal of the Korea Academia-Industrial cooperation Society · 2010
Abstract In this paper, an architecture for modified Euclidean(ME) algorithm is proposed, which is using finite-state machine(FSM) instead of degree computation. Since the proposed architecture does not have degree computation circuits, it is possible to reduce the hardware complexity of RS(Reed-Solomon) decoder, so that a very high-speed RS decoder can be implemented. RS(255,239) decoder with the proposed architecture is implemented using Verilog-HDL and requires about 13% fewer gate counts than conventional one. Key Words : Reed-Solomon, Modified Euclidean, RS decoder, FSM * 교신저자 : 강성진([email protected])접수일 10년 3월 29일 수정일 10년 04월 26일 게재확정일 10년 06월 18일 1. 서론 RS 부호는 연집 오류에 대하여 우수한 오류 정정 능력을 가지고 있어서, 광/자기 저장매체, 유무선 통신, 방송, 위성 통신 등 많은 통신시스템에서 널리 사용되고 있다 . 또한, 최근에는 NAND 플래시 메모리 분야에서도 오류 정정을 하기위한 연구가 활발히 진행되고 있다 .일반적인 RS(n,k,t) 부호에서 n은 전체 부호어(codeword)의 길이(심볼 개수), k는 정보 심볼의 개수를 의미하며, ⌊⌋ 는 RS 부호의 오류 정정 능력을 나타낸다[1,6]. RS부호에 대한 복호기는 그림 1과 같이 신드롬 연산(syndrome computation), 키 방정식 연산(Key Equation Solver, KES), Chien 탐색, Forney 알고리즘, 오류 정정 블록 및 FIFO(First Input First Output)로 구성된다[2-5]. 여기에서 KES 블록이 오류위치 다항식(error locator polynomial,