(14-15(02)) * << * >> * Russian * English * Content * All Issues

New discrete Fourier transform algorithm to base five
V.M. Chernov

 PDF, 2131 kB

Pages: 4-12.

Full text of article: Russian language.

Abstract:
When realizing the well-known and well-described [1,2] “combined” discrete Fourier transform (DFT) algorithms of real sequences with the even length N, the redundancy of input data in relation to the complex values of the basis transformation functions is used. More precisely, the transformation of a sequence with the length N reduces to the transformation of a complex sequence of length associated with the original one, and a certain (not very large) number of additional multiplications. Regardless of the matching scheme chosen, it is possible to apply this technique due to the presence of non-identical trivially realized automorphism in the field of complex numbers C. An attempt to synthesize fast multiple-matching DFT (FFT) algorithms realized in complex arithmetic encounters fundamental difficulties associated with the absence of a sufficient number of trivially realized automorphisms in field C. The synthesis of FFT with multiple matching in a different algebraic structure other than C was considered by the author in [3,4]. Compositional algebras [3] and cyclotomic extensions of the field of rational numbers we used as such structures .

Citation:
Chernov VM. New discrete Fourier transform algorithm to base five. Computer Optics 1995; 14-15(2): 4-12.

References:
  1. Krot AM. Discrete models of dynamical systems based on polynomial algebra; Minsk: Navuka i tekhnika; 1990.
  2. Vlasenko VA, Lappa YM, Yaroslavsky LP. Methods of synthesis of fast algorithms for signal convolution and spectral analysis; Moscow: Nauka Publisher; 1990; 160.
  3. Chernov VM. Arithmetic methods in the theory of discrete orthogonal transforms. Workshop on Digital Image Processing and Computer Graphics. Proceedings SPIE; 1994; V.2363.
  4. Chernov VM. The FFT algorithms with data representation in algebraic number fields. Automatic Control and Comp. Sci.; 1994; 4: 64-69.
  5. Blahut R. Fast algorithms of digital signal processing; Moscow: Mir Publisher; 1987; 448 .

© 2009, IPSI RAS
151, Molodogvardeiskaya str., Samara, 443001, Russia; E-mail: journal@computeroptics.ru ; Tel: +7 (846) 242-41-24 (Executive secretary), +7 (846) 332-56-22 (Issuing editor), Fax: +7 (846) 332-56-20