SYSTOLIC ARRAY IMPLEMENTATION OF EUCLID ALGORITHM FOR INVERSION AND DIVISION IN GF(2(M))

This paper presents two new systolic arrays to realize Euclid's algori thm for computing inverses and divisions in finite fields GF(2(m)) wit h the standard basis representation. One of these two schemes is paral lel-in parallel-out, and the other is serial-in serial-out. The former employs O(m(2)) area complexity to provide the maximum throughput in the sense of producing one result every clock cycle, while the latter achieves a throughput of one result per m clock cycles using O(m.log(2 )m) area complexity. Both of the proposed architectures are highly reg ular and, thus, well suited to VLSI implementation. As compared to exi sting related systolic architectures with the same throughput performa nce, the proposed parallel-in parallel-out scheme reduces the hardware complexity (and, thus, the area-time product) by a factor of O(m) and the proposed serial-in serial-out scheme by a factor of O(m/log(2)m).