Synthesis of fast-operating devices for digital signal processing based on the number­theoretic transforms

Abstract

The selection of special-form moduli and their corresponding primitive roots have been proposed, which provide for a simplified structure of arithmetic devices using number-theoretic transforms. A method for determining moduli has been developed that ensures a minimum number of arithmetic operations when performing the modulo addition and multiplication operations. The structures of special-form modulo adders have been developed and modeled, which make it possible to perform the addition operation as quickly as possible. The modulo adders for the Fermat, Mersenne, and Golomb numbers have been synthesized and tested, which could be used in the arithmetic units of high-speed correlators and filters. Real-time correlation and convolution calculation become a rather time-consuming task in the case of long input sequences. To solve this task, it is advisable to apply the so-called fast algorithms. However, this requires the high-performance calculators of convolution and correlation, which often exceed the capabilities of modern computer equipment, Therefore, the proposed procedure for determining the modulus, as well as the designed structural circuits for special-form modulo adders, make it possible to accelerate the computation of correlations and convolutions using number-theoretic transforms. Since the operation of modulo multiplication is performed using the addition and shift operations, the complexity of calculating the number-theoretic transformations largely depends on the number of unities in the binary representation of the degrees of the primitive root. The operation of multiplication is typically reduced to the multiple addition of numbers, which is why the complexity and speed performance of arithmetic devices for numeric-theoretic transformations is determined by the characteristics of the modulo adders. The proposed method for designing computing moduli for the digital devices that calculate correlation and convolution, based on rapid theoretical-numerical transformations, provides the simplified hardware and software implementation of these structures, resulting in high-speed processing of signals and images.