A number-theoretic transform for signal processing

Abstract

We describe a new transform for signal processing applications, and explain its basis using multiplicative number theory. Applying this transform, any signal can be resolved into its transformed spectrum in less than 2N(1 + logeN) computations, where N is the number of signal samples. Re-synthesis of the signal from the transformed spectrum also takes about the same number of computations. We also discuss the likely applications of this new transform and outline recommendations for further research.