In this paper, we devise new high-speed decoder architecture for Reed-Solomon codes using the Berlekamp-Massey (BM) algorithm. The speed bottleneck of the Reed-Solomon decoder is that the BM algorithm is needed to operate fixed 2t iterations to calculate error-locator polynomial and error-evaluator polynomial. In order to reduce iterative operations, we first present a new early stopping criterion for BM algorithm to reduce the number of iterations according to errors in the codeword. The derivative early stopping BM (ESBM) architecture is scalable systolic architecture in which a single array of processors computes both the error-locator polynomial and the discrepancy polynomial. We next concern critical path delay of the ESBM architecture. The ESBM architecture has long path delay, which is not appropriate high-speed RS decoders. Therefore, we second devise early stopping inversionless BM (ESiBM) architecture that effectively reduces critical path delay of the ESBM architecture. Furthermore, we lastly devise early stopping reformulated iBM (ESriBM) architecture to eliminate multiplexer delays of ESiBM architecture. In contrast to existing BM-based architecture, the ESriBM architecture has a smaller average latency due to the early stopping operation. Moreover, the ESriBM architecture has the same critical path delay and almost same hardware complexity as the state-of-the-art BM architecture.
본 논문에서는 Berlekamp-Massey (BM) 알고리즘을 사용하여 리드 솔로몬 코드에 대한 새로운 고속 복호기 아키텍처를 제안한다. Reed-Solomon 복호기 속도의 병목 현상은 오류 위치 다항식 및 오류 평가 다항식을 계산하기 위하여 고정 된 2t번의 반복을 연산하는 데 BM 알고리즘이 사용되기 때문에 발생합니다. 이를 해결하기 위하여 먼저 BM 알고리즘에 대한 새로운 조기 정지 기준을 정의하여 코드 워드의 오류에 개수에 따라 반복을 줄일 수 있는 방법을 제안합니다. 이를 통해 제안하는 ESBM 아키텍처는 통일된 구조의 프로세서가 오류 위치 다항식과 불일치 다항식을 계산할 수 있는 완전 수축 구조로 구현됩니다. 다음으로는 ESBM 아키텍처의 핵심 경로 지연에 대해 다룹니다. ESBM 아키텍처는 긴 경로 지연을 가지므로 고속 아키텍처에 적합하지 않습니다. 따라서 우리는 ESBM 아키텍처의 핵심 경로 지연을 효과적으로 줄이는 초기 정지 ESriBM 아키텍처를 제안합니다. 또한 ESiBM 아키텍처의 멀티플렉서의 지연을 없애기 위해 재구성된 ESriBM 아키텍처를 제안합니다. 그 결과 기존 BM 기반 아키텍처와 달리 ESriBM 아키텍처는 조기 정지 작업으로 인해 평균 대기 시간이 더 짧습니다. 또한 ESriBM 아키텍처는 가장 빠른 기존 BM 아키텍처와 동일한 주요 경로 지연 시간을 가지고, 거의 동일한 하드웨어 복잡성을 가지고 있습니다
