Reducing the latency of Lee-O'Sullivan interpolation through modified initialization

Low-rate Reed-Solomon (RS) codes can be adopted in biometric encryption and digital communication systems to achieve high error-correcting capability. The interpolation step of RS decoding can be solved by the Lee-O'Sullivan (LO) algorithm, which converts an initial basis of polynomials to a Gro¨bner basis. This paper proposed a modified basis initialization for the LO algorithm for low-rate codes. The proposed modification leads to significant reduction on the degree of the polynomials and the number of clock cycles needed in the conversion process. Hardware implementation architectures are also developed in this paper. Compared to architectures using the original initialization, the proposed design can achieve 44% higher efficiency in terms of speed-over-area ratio for a (30,9) RS code over GF(2 16 ).