Email this article Generalization of the Fast Fourier Transform with a Constant Structure
- Authors: Bespalov M.S.1
-
Affiliations:
- Vladimir State University
- Issue: Vol 63, No 8 (2023)
- Pages: 1241-1250
- Section: ОБЩИЕ ЧИСЛЕННЫЕ МЕТОДЫ
- URL: https://journals.rcsi.science/0044-4669/article/view/136178
- DOI: https://doi.org/10.31857/S0044466923080033
- EDN: https://elibrary.ru/WRXNSJ
- ID: 136178
Cite item
Open Access
Access granted
Subscription Access
Abstract
The widely popular famous fast Cooley–Tukey algorithms for the discrete Fourier transform of mixed radix are presented in two forms: classical and with a constant structure. A matrix representation of these algorithms is proposed in terms of two types of tensor product of matrices: the Kronecker product and the b-product. This matrix representation shows that the structure of these algorithms is identical to two fast Good algorithms for a Kronecker power of a matrix. A technique for constructing matrix-form fast algorithms for the discrete Fourier and Chrestenson transforms with mixed radix and for the discrete Vilenkin transform is demonstrated. It is shown that the constant-structured algorithm is preferable in the case of more sophisticated constructions
About the authors
M. S. Bespalov
Vladimir State University
Author for correspondence.
Email: bespalov@vlsu.ru
600000, Vladimir, Russia
References
- Cooley J.W., Tukey J.W. An algorithm for the machine calculation of complex Fourier series // Math. Comput. 1965. V. 19 (90). P. 297–301.
- Залманзон Л.А. Преобразования Фурье, Уолша, Хаара и их приложения в управлении, связи и других областях. М. : Наука, 1989. 496 с.
- Беспалов М.С. О свойствах тензорного произведения матриц // Ж. вычисл. матем. и матем. физ. 2014. Т. 54. № 4. С. 547–561.https://doi.org/10.1134/S0965542514040046
- Good I.J. The interaction algorithm and practical Fourier analysis // J. Royal Stat. Soc. 1958. Ser. B. V. 20. P. 361–372.
- Малоземов В.Н., Машарский С.М. Основы дискретного гармонического анализа. СПб.: Лань, 2012. 304 с.
- Беспалов М.С. Новые разложения кронекеровой степени по Гуду // Проблемы передачи информации. 2018. Т. 54. № 3. С. 62–66.https://doi.org/10.1134/S0032946018030043
- Трахтман А.М., Трахтман В.А. Основы теории дискретных сигналов на конечных интервалах. М.: Сов. радио, 1975.
- Малоземов В.Н., Машарский С.М., Цветков К.Ю. Сигнал Франка и его обобщения // Проблемы передачи информации. 2001. Т. 37. № 2. С. 18–26.
- Малоземов В.Н., Машарский С.М. Обобщенные вейвлетные базисы, связанные с дискретным преобразованием Виленкина–Крестенсона // Алгебра и анализ. 2001. Т. 13. Вып. 1. С. 111–157.
- Машарский С.М. Быстрое преобразование Виленкуина – Крестенсона на основе факторизации Гуда // Ж. вычисл. матем. и матем. физ. 2002. Т. 42, № 6. с. 784–790.
- Беспалов М.С. Дискретные преобразования Крестенсона // Проблемы передачи информации. 2010. Т. 46. № 4. С. 91–115. https://doi.org/10.1134/S003294601004006X
- Johnson J., Johnson R.W., Rodriguez D., Tolimieri R. A methodology for designing, modifying and implementing Fourier transform algorithms on various architectures // Circuits, Systems and Signal Proctssing. 1990. V. 9. № 4. P. 449–500.
- Малоземов В.Н., Просеков О.В. Факторизация Кули–Тьюки матрицы Фурье // Избранные главы дискретного гармонического анализа и геометрического моделирования. Ч. I. Изд. 2-е. Под ред. проф. В. Н. Малоземова. СПб.: Изд-во ВВМ. 2014. С. 20–29.
