A Large Width Arithmetic Multiplier Design With 256-bit Based On Toom-Cook-4 Algorithm

In recent years,various communication networks have developed rapidly.In order to make data transmission more secure,people have gradually begun to use larger bit-width encryption methods in various network terminal devices.The large bit width multiplication is the core calculation step of the encryption algorithm.The large bit width multiplier with small design area and low power consumption plays an important role in data encryption of various battery-powered small terminal devices.The Toom-Cook algorithm has a lower multiplication calculation complexity than other large number split classification algorithms,but due to the complexity of the middle calculation process and the need to perform division operations,it is rare in hardware calculations,which wastes the advantages of the Toom-Cook algorithm.For this reason,this paper designs a 256-bit wide integer multiplier based on the Toom-Cook-4 algorithm,which provides support for the hardware implementation of the Toom-Cook multiplier.The main work of this paper has the following aspects:(1)Research the large number multiplication algorithm,analyze the resource consumption of the classic Karatsuba,Toom-Cook-4,and Toom-Cook-5 algorithms in the large number classification algorithm under 256-bit width,and use the high-level description language Py RTL After describing and synthesizing it,it is found that the Toom-Cook-4 algorithm has better area performance.(2)The hardware implementation design of the Toom-Cook-4 algorithm is carried out,and the coefficient matrix is solved by using the optimal column principal element elimination solution step to achieve the lowest calculation step requirement and the least intermediate variable generation;propose a use of resource reuse The calculation method of the structure finely arranges the calculation sequence and hardware resource allocation of each calculation step,and reduces the resource consumption of the algorithm due to the complicated intermediate calculation process.(3)Aiming at the Toom-Cook-4 algorithm's division calculation problem,it is proposed to use the remainder theorem to construct a remainder bypass circuit,which breaks the dependency between the front and back iterations of the remainder in the division calculation,so that all parts of the division can be calculated in parallel,which doubles the calculation time;Design a dedicated division unit circuit and tree compression circuit to further shorten the critical path of the divider and improve calculation efficiency.This paper presents the calculation reference model for the hardware design of the Toom-Cook-4 algorithm,and performs functional verification,synthesis and implementation of the 256-bit multiplier designed in this paper,using an area of 0.1mm~2 to achieve a running speed of 160MHz.The results show that the Toom-Cook-4 multiplier designed in this paper,compared with other similar researches that have not implemented the division calculation,does not produce the huge area and delay consumption caused by the introduction of division as described.At the same time,compared with the Karatsuba algorithm,the area-time product is reduced by 35%,showing the hardware computing advantages of the Toom-Cook algorithm.