1. На главную
  2. Электронные версии
  3. Журнал вычислительной математики и математической физики
  4. T. 63, № 8, 2023

Журнал вычислительной математики и математической физики, 2023, T. 63, № 8, стр. 1241-1250

Обобщение быстрого преобразования Фурье с постоянной структурой

М. С. Беспалов 1, *

1 Владимирский гос. ун-т
600000 Владимир, ул. Горького, 87, Российская Федерация

* E-mail: bespalov@vlsu.ru

Поступила в редакцию 09.02.2023
После доработки 14.03.2023
Принята к публикации 28.04.2023

Аннотация

Широко популярны знаменитые быстрые алгоритмы Кули–Тьюки для дискретного преобразования Фурье составного основания, представленные в двух видах – классическом и с постоянной структурой. В статье предложено матричное представление этих алгоритмов в обозначениях двух видов тензорного произведения матриц: кронекерова произведения и $b$-произведения. Предложенное матричное представление указывает на идентичность структуры этих алгоритмов с двумя быстрыми алгоритмами Гуда для кронекеровой степени матрицы. Продемонстрирована методика построения матричной формы быстрых алгоритмов для дискретных преобразований: Фурье и Крестенсона с составным основанием, а также Виленкина. Показана предпочтительность использования алгоритма с постоянной структурой в случаях более сложных конструкций. Библ. 13.

Ключевые слова: дискретное преобразование Фурье, дискретное преобразование Уолша, быстрый алгоритм, кронекерово произведение матриц.

Список литературы

  1. 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.

  2. Залманзон Л.А. Преобразования Фурье, Уолша, Хаара и их приложения в управлении, связи и других областях. М. : Наука, 1989. 496 с.

  3. Беспалов М.С. О свойствах тензорного произведения матриц // Ж. вычисл. матем. и матем. физ. 2014. Т. 54. № 4. С. 547–561.https://doi.org/10.1134/S0965542514040046

  4. Good I.J. The interaction algorithm and practical Fourier analysis // J. Royal Stat. Soc. 1958. Ser. B. V. 20. P. 361–372.

  5. Малоземов В.Н., Машарский С.М. Основы дискретного гармонического анализа. СПб.: Лань, 2012. 304 с.

  6. Беспалов М.С. Новые разложения кронекеровой степени по Гуду // Проблемы передачи информации. 2018. Т. 54. № 3. С. 62–66.https://doi.org/10.1134/S0032946018030043

  7. Трахтман А.М., Трахтман В.А. Основы теории дискретных сигналов на конечных интервалах. М.: Сов. радио, 1975.

  8. Малоземов В.Н., Машарский С.М., Цветков К.Ю. Сигнал Франка и его обобщения // Проблемы передачи информации. 2001. Т. 37. № 2. С. 18–26.

  9. Малоземов В.Н., Машарский С.М. Обобщенные вейвлетные базисы, связанные с дискретным преобразованием Виленкина–Крестенсона // Алгебра и анализ. 2001. Т. 13. Вып. 1. С. 111–157.

  10. Машарский С.М. Быстрое преобразование Виленкуина – Крестенсона на основе факторизации Гуда // Ж. вычисл. матем. и матем. физ. 2002. Т. 42, № 6. с. 784–790.

  11. Беспалов М.С. Дискретные преобразования Крестенсона // Проблемы передачи информации. 2010. Т. 46. № 4. С. 91–115. https://doi.org/10.1134/S003294601004006X

  12. 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.

  13. Малоземов В.Н., Просеков О.В. Факторизация Кули–Тьюки матрицы Фурье // Избранные главы дискретного гармонического анализа и геометрического моделирования. Ч. I. Изд. 2-е. Под ред. проф. В. Н. Малоземова. СПб.: Изд-во ВВМ. 2014. С. 20–29.

Дополнительные материалы отсутствуют.

Инструменты

следующая статья выпуска содержание выпуска

Журнал вычислительной математики и математической физики

Архивы выпусков Информация о журнале Отправить рукопись в журнал