Systolic and Non-Systolic Scalable Modular Designs of Finite Field Multipliers for Reed#x2013;Solomon Codec

摘要

In this paper, we present efficient algorithms for modular reduction to derive novel systolic and non-systolic architectures for polynomial basis finite field multipliers over $GF(2^{m})$ to be used in Reed#x2013;Solomon (RS) codec. Using the proposed algorithm for unit degree reduction and optimization of implementation of the logic functions in the processing elements (PEs), we have derived an efficient bit-parallel systolic design for finite field multiplier which involves nearly two-thirds of the area-complexity of the existing design having the same time-complexity. The proposed modular reduction algorithms are also used to derive efficient non-systolic serial/parallel designs of field multipliers over $GF(2^{8})$ with different digit-sizes, where the critical path and the hardware-complexity are further reduced by optimizing the implementation of modular reduction operations and finite field accumulations. The proposed bit-serial design involves nearly 55 of the minimum of area, and half the minimum of area-time complexity of the existing bit-serial designs. Similarly, the proposed digit-serial/parallel designs involve significantly less area, and less area-time complexities compared with the existing designs of the same digit-size. By parallel modular reduction through multiple degrees followed by appropriate logic-level sub-expression sharing; a hardware-efficient regular and modular form of a balanced-tree bit-parallel non-systolic multiplier is also derived. The proposed bit-parallel non-systolic pipelined design involves less than 65 of the area and nearly two-thirds of the area-time complexity of the existing bit-parallel design for a RS codec, while the non-pipelined form offers nearly 25 saving of area with less time-complexity.