Methods for performing target transformations, acceleration hardware, and polynomial multipliers

Acceleration hardware for performing a target transformation, wherein the target transformation comprises transformation operations of N stages, the acceleration hardware comprises N circuit parts corresponding to the N stages, wherein an ith circuit part corresponding to any ith stage other than a first stage and a last stage comprises a controller, a processing engine, a memory, a first rearrangement unit, and a second rearrangement unit;

• and in the transformation operation of the ith stage:
• the controller is configured to respectively read a first data pair and a second data pair from a first read address and a second read address in the memory at an (i−1)th stage;
• the first rearrangement unit is configured to perform a first rearrangement operation on the first data pair and the second data pair, to sequentially output a third data pair and a fourth data pair;
• the processing engine is configured to sequentially perform a radix-2 butterfly operation on the third data pair and the fourth data pair, to sequentially output a first result pair and a second result pair;
• the second rearrangement unit is configured to perform a second rearrangement operation on the first result pair and the second result pair, to obtain a fifth data pair and a sixth data pair;
• and
• the controller is further configured to respectively write the fifth data pair and the sixth data pair into a first write address and a second write address in the memory at the ith stage.

A polynomial multiplier, receiving an n-point first input sequence and an n-point second input sequence, and outputting an n-point polynomial multiplication output sequence, wherein the polynomial multiplier comprises a first transformation module, a second transformation module, a pointwise multiplication hardware module, and a third transformation module, wherein the first transformation module, the second transformation module, and the third transformation module each comprise acceleration hardware for performing a target transformation, wherein the target transformation comprises transformation operations of N stages, the acceleration hardware comprises N circuit parts corresponding to the N stages, wherein an ith circuit part corresponding to any ith stage other than a first stage and a last stage comprises a controller, a processing engine, a memory, a first rearrangement unit, and a second rearrangement unit, and in the transformation operation of the ith stage:

• the controller is configured to respectively read a first data pair and a second data pair from a first read address and a second read address in the memory at an (i−1)th stage;
• the first rearrangement unit is configured to perform a first rearrangement operation on the first data pair and the second data pair, to sequentially output a third data pair and a fourth data pair;
• the processing engine is configured to sequentially perform a radix-2 butterfly operation on the third data pair and the fourth data pair, to sequentially output a first result pair and a second result pair;
• the second rearrangement unit is configured to perform a second rearrangement operation on the first result pair and the second result pair, to obtain a fifth data pair and a sixth data pair;
• and
• the controller is further configured to respectively write the fifth data pair and the sixth data pair into a first write address and a second write address in the memory at the ith stage;
• the first transformation module is configured to perform NTTP on the first input sequence in a DIF form, to output a first output sequence;
• the second transformation module is configured to perform NTTP on the second input sequence in a DIF form, to output a second output sequence;
• the pointwise multiplication hardware module is configured to perform pointwise multiplication on the first output sequence and the second output sequence, to output a third output sequence;
• and
• the third transformation module is configured to perform INTTP on the third output sequence in a DIT form, to output the n-point polynomial multiplication output sequence.