Efficient VLSI architecture for interpolation decoding of hermitian codes

A fast, area efficient very large scale integration (VLSI) architecture is proposed for a unique decoding algorithm of Hermitian codes which was presented recently by Lee and O´Sullivan from an interpolation perspective. The algorithm iteratively computes the sent message through a majority voting procedure by using the Gröbner bases of interpolation modules. The algorithm has a regular structure which makes it suitable for VLSI implementation. The circuitry is simplified as the decoding algorithm directly gives the message word at the end of the decoding algorithm without separate steps like Chien search and Forney´s formula. In terms of hardware requirements, for the widely used high rate Hermitian codes, the Lee-O´Sullivan algorithm is q times faster than Kötters algorithm with the same space complexity of O(q⁴). Further speed improvements can be achieved by combining the main idea of Guruswami list decoding with the Lee-O´Sullivan algorithm. In terms of hardware, the addition of this concept, will further reduce the running time of the algorithm and make the circuitry about two times faster than the original Lee-O´Sullivan algorithm. The implementation results for both the Köetter and the Lee-O´Sullivan algorithms on Xilinx Virtex-5 shows that the proposed decoder can be operated at higher clock frequency with almost same area complexity.