Reed-Solomon code is a linear systematic block code based on finite field theory. The systematic format, the efficient encoding/decoding algorithm, and the powerful random/burst error correction capability of the code make it one of the most widely used error correction code in the industry.
In RS decoders, the throughput bottleneck is the key equation solver (KES) block. We have adopted the Berlekamp-Massey (BM) algorithm for solving the key equation because it leads to more efficient hardware and software implementation. Because of the presence of feed back signals in the original BM algorithm it is hard to pipeline this block to improve the speed.
We have proposed a retimed decomposed inversion less serial BM architecture that improves the speed and throughput by almost 76%. This improvement has been achieved at the expense of some extra registers. The key ideas include, the updating of the error locator polynomial and the discrepancy value computation in parallel in 2t + 2 cycles per iteration plus using the retiming technique to achieve a high speed architecture. In addition standard basis irregular fully parallel multiplier with separate partial product generation (PPG) and partial product reduction (PPR) stages has been used in our design, which leads to improved performance.
리드 솔로몬 코드는 finite field 이론에 기반을 둔 선형 시스템 블럭 코드이다. 체계적인 형식과 랜덤하고 연속적인 에러에 대한 탁월한 정정 능력으로 여러 분야에서 가장 많이 사용되는 코드 중의 하나이다.
리드솔로몬 디코더에서 성능의 핵심이 되는 부분은 key equation solver(KES) 블럭이다. 일반적으로 key equation을 풀기 위하여 Berlekamp-Massey(BM) 알고리즘을 사용하는데, 이는 하드웨어와 소프트웨어의 구현이 효유적이기 때문이다. 기존의 BM 알고리즘에는 피드백 신호가 있기 때문에 속도를 향상시키기 위하여 파이프라인을 하기가 상당히 까다롭다.
따라서 우리는 제안된 시간조정기법으로 속도와 throughput을 거의 76% 향상시킨 BM알고리즘을 제안하였다. 이러한 향상은 추가적인 register를 사용하여 구현된 것이다. 이 향상된 알고리즘은 고속의 구조를 얻기 위한 시간조정기법과 함께 반복 회수당 2t+2사이클 내에 병렬로 error locator polynomial을 갱신하고 discrepancy값을 계산하는 것을 포함한다. 게다가 성능을 향상시키기 위하여 분리된 partial product generation(PPG)으로 불규칙적인 병렬 곱셉기와 partial product reduction(PPR) 단계가 적용되었다.
