Systolic Formulation for Low-Complexity Serial-Parallel Implementation of Unified Finite Field Multiplication over GF(2{sup}m)

摘要

It presents a high-throughput hardware-efficient semi-systolic linear array for a serial-parallel implementation of finite field multiplier over GF(2{sup}m) using bidirectional modulo reduction technique. Necessary recurrence relations are formulated and a pair of dependence graphs (DG) are designed for least significant bit (LSB) and most significant bit (MSB) elimination algorithms for modular reduction. Both the DGs are merged together and mapped into a fully-pipelined linear array architecture consisting of m number of processing elements (PEs), which performs one field multiplication in every (m/2) cycles. The structure of each PE is optimized further to be implemented by a pair of AND gates, three XOR gates and a pair of latches. The duration of a cycle amounts to T = T{sub}A + T{sub}(X3) + T{sub}L, where T{sub}A, T{sub}(X3) and T{sub}L, are respectively the delays of a 2-input AND gate, a three-input XOR gate and a latch. The proposed design is found to have significantly low area-time complexity compared with the existing serial-parallel structures for finite filed multiplications. It is shown that the proposed multiplier can also be used for the Montgomery multiplication in binary field.