Novel Systolization of Subquadratic Space Complexity Multipliers Based on Toeplitz Matrix-Vector Product Approach

Systolic finite field multiplier over GF(2(m)), because of its superior features such as high throughput and regularity, is highly desirable for many demanding cryptosystems. On the other side, however, obtaining high-performance systolic multiplier with relatively low hardware cost is still a challenging task due to the fact that the systolic structure usually involves large area complexity. Based on this consideration, in this paper, we propose to carry out two novel coherent interdependent efforts. First, a new digit-serial multiplication algorithm based on polynomial basis over binary field (GF(2m)) is proposed. Novel Toeplitz matrix-vector product (TMVP)-based decomposition strategy is employed to derive an efficient subquadratic space complexity. Second, The proposed algorithm is then innovatively mapped into a low-complexity systolic multiplier, which involves less area-time complexities than the existing ones. A series of resource optimization techniques also has been applied on the multiplier which optimizes further the proposed design (it is the first report on digit-serial systolic multiplier based on TMVP approach covering all irreducible polynomials, to the best of our knowledge). The following complexity analysis and comparison confirm the efficiency of the proposed multiplier, that is, it has lower area-delay product (ADP) than the existing ones. The extension of the proposed multiplier for bit-parallel implementation is also considered in this paper.