Reformulated Partial-Inverse Algorithms for Time-Domain Reed–Solomon Codes With Hardware Considerations

Recently, a new approach to Reed–Solomon codes based on the partial-inverse (PI) problem and the PI algorithms (for solving the problem) was proposed, which includes the standard key equation for Reed–Solomon codes and new algorithms for error-decoding and joint error-and-erasure decoding of such codes. However, these algorithms are literally only suitable for software implementation. In this paper, we derive several reformulations of the PI algorithms, namely the rPI (reformulated PI), RPI, and ERPI (enhanced RPI) algorithms, that can be implemented in serial and parallel hardware architectures. The rPI algorithm combined with Horiguchi–Koetter (HK) interpolation has the advantage of low complexity in serial architectures, while the RPI and ERPI algorithms with Forney’s interpolation stand out in high-speed decoding applications. All these algorithms have an intrinsic early-stop property and they form a unified framework for hardware Reed–Solomon decoders. For decoding high-rate codes, the implementation results show that the RPI algorithm, combined with Forney’s algorithm in a $P$-parallel architecture, exhibits better hardware efficiency in NAND gate counts, latency, and power consumption, achieving approximately 20$\%$ efficiency improvement in Gbps/gate counts compared to the state-of-the-art ePIBMA plus HK design for an $\text{RS}(255,239)$ code at $P = 16$.