Design And Application Of Fast Number Theoretic Transform In Digital Signal Processing

Number theoretic transform (NTT) can be applied to calculate the correlation and convolution.In the process, NTT will not introduce additional noise because it can be calculated without truncation and approximate.Variety of NTT fast algorithm (FNTT) is still demanded to reduce the computational complexity.The emphasis is how to use the NTT algorithm in the application which is the research of scholars nowadays.Firstly, this paper studies the relationship between the modulus, auditing and transform length in the NTT and research the Fast NTT which is the combination of fast algorithm and NTT. For the purpose to reduce the computational complexity of Winograd number theoretic transform algorithm, the new Winograd number theoretic transform algorithm with constant multiplier matrix structure is proposed. The computational complexity of the new algorithm was dicussed and analyzed, and was validated by FPGA. Meanwhile, this paper proposes a new Mersenne transform fast algorithm called Walsh-new Mersenne number transform. The Walsh Hadamard matrix is used to convert new Mersense number transform matrix into a new matrix which is required a less amount of calculation. The simulation results showed the algorithm have a excellent performance when the transform length is less than or equal to 16.The paper improves the Remainder Theorem-based image compression which can increase the rate of the compression. The new image compression algorithm which is the combination of Remainder Theorem and JPEG still image compression algorithm is prosposed. The Matlab simulation results show the new algorithm has higher compression ratio when the loss of quality of the new algorithm is the same to JPEG still image compression algorithm.Finally, the NTT in the application of the block cipher algorithm is studied in this paper. A new block cipher algorithm which is called Safer-Fermat algorithm is proposed. The Fermat number transform is considered as the diffusion layer so that the encryption and decryption complexity of the algorithm is less than Safer++. Then, the test is made for the randomized capabilities and security of the new algorithm shows the crack difficulty of the new algorithm is the same with Safer++.