Параметрический вариант быстрого преобразования Фурье: многомерный случай

Быстрые алгоритмы играют важную роль при обработке дискретных периодических сигналов, особенно в многомерном случае. Наиболее популярным и но-прежнему востребованным является быстрое преобразование Фурье (БПФ). Отметим, что теория БПФ далеко не проста [2, 3, 6, 9, 24]. Хороший обзор её развития дан в [40]. Ключевой работой в теории БПФ явилась работа Кули и Тьюки 1965 года [38]. Немаловажную роль в то время сыграло развитие вычислительных средств. В [38] приводится время работы реализации трёхмерпого БНФ на «новых» тогда ЭВМ IBM 7094. С тех пор интерес к БНФ не угасает. В известном обзорном отчёте Барраса 1997 года [36] упоминается более 3400 работ, но БНФ. Большая часть из них это работы, связанные с вычислительными аспектами БНФ и вопросами реализации БНФ на различных архитектурах ЭВМ. Вопрос о быстродействии стоит очень остро в связи с обработкой сигналов в реальном времени, а дискретное преобразовапие Фурье (ДНФ) является базовой операцией для других алгоритмов, и быстродействие системы в целом сильно зависит от эффективной реализации БНФ. Типичные приложения это цифровые устройства связи, аудиои видеоустройства. С развитием микроэлектроники появилось множество микропроцессоров с сильно различаюп-ейся архитектурой. В связи с этим встал вопрос об универсальном подходе к реализации БНФ. Самой известпой работой в этой области является система FFTW, разработанная Фриго и Джонсоном [42]. Система анализирует вычислительные графы БНФ и адантирует их для конкретной 3 вычислительной архитектуры ЭВМ. Для большинства длин нериодов и большинства ЭВМ это самая быстрая реализация БПФ на сегодня. Другой не менее известной работой является нроект SPIRAL [48], в котором реализуется новый нодход к дискретным нреобразованиям, основанный на теории нредставлений. Несмотря на то, что эффективные алгоритмы БПФ суш, ествуют для нрактически любых длин нериодов, длина, равная стенени двойки, остаётся самой нонулярной. В этом случае ВПФ достаточно легко реализуется, и основной вычислительный модуль «бабочка» задаётся всего несколькими инструкциями. Более сложный, но реализации, но более эффективный алгоритм БПФ «split-radix» [39, 51] нозволяет сократить число веш, ественных арифметических онераций на 20%, а алгоритм, онисанный в новой работе [41], еш, ё нримерно на 6%. Различные алгоритмы БПФ зависят от арифметических свойств длины нериода сигнала. Если эта длина число составное, то применим алгоритм Кули-Тьюки. Описание различных вариантов алгоритма Кули-Тьюки можно найти в [37]. В случае, когда длина сигнала может быть нредставлена в виде нроизведения понарно взаимно простых чисел, применим алгоритм нростых множителей, разработанный Гудом в 1958 году [8]. В вычислительном отношении алгоритм нростых множителей нрош, е алгоритма Кули-Тьюки. Если длина сигнала является простым числом, то можно воснользоваться алгоритмом Рейдера [31]. В этом случае задача вычисления ДПФ сводится к задаче вычисления циклической свёртки. Эффектное применение этой идеи нашёл Виноград для вычисления ДПФ небольшой длины [4]. Задача быстрого вычисления циклической свёртки решается с помон], ыо полиномиальной тех1шки. По сути, метод Винограда даёт разложение матрицы Фурье малого норядка в нроизведение трёх матриц матрицы предсложений, диагональной матрицы и матрицы постсложений. Такое разложение имеет целью мннимизировать число умножений. Сложения оптимизируются вручную. Алгоритмы Винограда малых длин эффективно иснользуются в алгоритмах БПФ для составных длин. Идея факторизации матрицы Фурье представляется наиболее перспективной. Обш, ий подход к построепию быстрых алгоритмов связап с разложением матрицы Фурье в произведение слабо заполпенпых матриц. Поскольку такие разложения не единственны, возникает возможность выбора наилучших в некотором смысле разложений. Впервые на базе кронекерова умножения матриц факторизация матрицы Фурье была нолучена в работе 1968 года [47]. В этой статье рассматривался вонрос о параллельных вычислениях. Позже в [46] были получены факторизации матрицы Фурье, ориентированные на векторные вычисления. Паиболее нолно техника факторизации матриц представлена в обзорной статье [45]. В ней нодробно рассмотрены варианты реализации БПФ па различных архитектурах ЭВМ. Педавно был разработан новый подход к формировапию вейвлет-пакетов, основанный на построении последовательности ортогопальных базисов в пространстве сигналов [И, 12, 23]. Это значительно расширяет возможности цифровой обработки сигналов. Вейвлет-пакеты позволяют получать детальные частотно-временные нортреты сигналов, варьируя разрешение (масштабность) но времени и частоте. В этом смысле анализ сигналов с помощью вейвлет-пакетов можно рассматривать как мон], ное донолнение к традиционному анализу Фурье. В теории быстрых ортогональных преобразовапий важную роль играют перестановки. Обычно перестаповки особым образом изменяют порядок входпых или выходных отсчётов сигнала. Это не всегда удобно. Алгоритмы, не требуюш, ие перестановки данных до или носле преобразования, получили название «self-sorting». Впервые такой алгоритм БПФ был нолучен Стокхемом и описан в [37]. Другой алгоритм, основанный на факторизации матрицы Фурье, был разработан Глассмапом [43]. Детально такие алгоритмы рассмотрены в работе [50]. Особенно эффективно идея БПФ работает в многомерном случае. Традиционно иснользуют нострочно-столбцевой метод [24, с. 94]. В этом методе для каждой размерности нрименяется соответствуюищй одномерный алгоритм БПФ. Более эффективный двумерный алгоритм, нохожий на алгоритм Кули-Тьюки, предложил Райворд[49]. Обобщение этого алгоритма было нолучено в работе [44]. Использовать полиномиальные преобразования для вычисления ДПФ предложили Нуссбаумер и Квенделл [24]. Другой алгоритм с похожими характеристиками был получен в работе [35]. Варианты БПФ основываются на разных представлениях (кодировании) индексов сигнала. Смешанный код иснользуется в методе Кули-Тьюки (если длина нериода равна степени двойки, то это бинарный код). Китайский и руритаский коды в методе простых множителей. М. Б. Свердлик в своих работах [32−34] предложил обобщённое представление индексов, связанное с введепием вектора параметров. Это послужило основой для параметрической факторизации матрицы Фурье. Целью диссертационной работы является: 1) Исследование различных вариантов факторизации матрицы Фурье на базе кронекерова умнооюения матриц. 2) Разработка общего подхода к вычислению ДПФ, основанного на параметрическом кодировавши индексов. 3) Построение параметрического алгоритма БПФ в многомерном случае. 4) Получение более детальной факторизации матриц Фурье малых порядков. Данная работа носит теоретический характер. Построена параметрическая теория БПФ. С практической точки зрения все полученные результаты ориентированны на параллельные и векторные вычисления, что особенно актуально в связи с развитием современных технологий. Приведём краткий обзор содержания диссертации. Работа состоит из девяти нараграфов, одной таблицы, одного рисунка, сниска литературы и одного приложения. Порядок ссылок на теоремы и формулы онределяется двумя числами: первое число указывает номер

1. Ахмед Н., Рао К. Р. Ортогональные преобразования при обработке цифровых сигналов. М.: Связь, 1980. 248 с.

2. Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов. М.: Мир, 1989. 448 с.

3. Виноград С. О вычислении дискретного преобразования Фурье / В кн. 9. с. 117−136.

4. Власенко В. А., Лаппа Ю. М. Матричный подход к построению быстрых алгоритмов многомерного ДПФ // Изв. вузов. Радиоэлектроника. 1986. Т. 29. № 1. С. 86−89.

5. Власенко В. А., Лаппа Ю. М., Ярославский Л. П. Методы синтеза быстрых алгоритмов свёртки и спектрального анализа сигналов. М.: Наука, 1990. 180 с.

6. Воеводин В. В., Кузнецов Ю. А. Матрицы и вычисления. М.: Наука, 1984. 320 с.

7. Гуд И. Дж. О взаимоотношении между двумя быстрыми преобразованиями Фурье / В кн. 9. с. 136−147.

8. Макклеллан Дж. X., Рейдер Ч. М. Применение теории чисел в цифровой обработке сигналов. М.: Радио и связь, 1983. 264 с.

9. Малозёмов В. Н. Параметрическое кодирование индексов // Семинар по дискретному гармоническому анализу и геометрическому моделированию (DHA & CAGD). Избранные доклады. 19 мая 2004 г. http://www.dha.spb.ru/reps04.shtml#0519).

10. Малозёмов В. H., Машарский С. М. Основы дискретного гармонического анализа. Части 1−3. СПб.: НИИММ, 2003. 320 с.

11. Малозёмов В. Н., Машарский С. М. Формула Глассмапа, быстрое преобразование Фурье и вейвлетпые разложения // Труды С.-Петербургского Матем. Общества. 2001. Т. 9. С. 97−119.

12. Малозёмов В. Н., Просеков О. В. О быстром преобразовании Фурье малых порядков // Вестник СПбГУ. Сер. 1. 2003. Вып. 1 (№ 1). С. 36−45.

13. Малозёмов В. Н., Просеков О. В. Общий подход к вычислению ДПФ // Семинар по дискретному гармоническому анализу и геометрическому моделированию (DHA k CAGD). Избранные доклады. 12 сентября 2006 г. (http://www.dha.spb.ru/reps06.shtml#0912).

14. Малозёмов В. H., Просеков О. В. Параметрическая факторизация матрицы Фурье // Электронный архив препринтов С.-Петербургского матем. общества. Препринт 2007;06.http://www.mathsoc.spb.ru/preprint/2007/index.html#06).

15. Малозёмов В. H., Просеков О. В. Параметрический вариант метода простых множителей // Электронный архив препринтов С.-Петербургского матем. общества. Препринт 2007;05.http://www.mathsoc.spb.ru/preprint/2007/index.html#05).

16. Малозёмов В. H., Просеков О. В. Факторизация Гуда матрицы Фурье // Семинар по дискретному гармоническому анализу и геометрическому моделированию (DHA & CAGD). Избранные доклады. 5 мая 2004 г. (http://www.dha.spb.ru/reps04.shtml#0505).

17. Малозёмов В. H., Просеков О. В. Факторизация Кули-Тыоки матрицы Фурье // Семинар по дискретному гармоническому анализу и геометричсскому моделированию (DHA k CAGD). Избранные доклады. 14 апреля 2004 г. (http: //www. dha. spb. ru/reps04. shtml#0414).

18. Малозёмов В. H., Просеков О. В. Факторизация матриц реверсных перестановок // Электронный архив препринтов С.-Петербургского матем. общества. Препринт 2007;04.http://www.mathsoc.spb.ru/preprint/2007/index.html#04).

19. Малозёмов В. H., Третьяков А. А. Новый подход к алгоритму Кули-Тьюки // Вестник СПбГУ. Сер. 1. 1997. Вып. 3 (№ 15). С. 57−60.

20. Нуссбаумер Г. Быстрое преобразование Фурье и алгоритмы вычисления свёрток. М.: Радио и связь, 1985. 248 с.

21. Пахомов С. Н., Просеков О. В. Вычислительные аспекты быстрого преобразования Фурье II Вестник СПбГУ. Сер. 1. 2004. Вып. 4 С. 44−50.

22. Просеков О. В. Алгоритмы быстрого преобразования Фурье для нетрадиционного числа точек // Труды седьмой международной конференции «Прикладные технологии гидроакустики и гидрофизики». 8−10 июня 2004 г. Санкт-Петербург. С. 394−399.

23. Просеков О. В. Быстрое преобразование Фурье малых порядков // Семинар по дискретному гармоническому анализу и геометрическому моделированию (DHA & CAGD). Избранные доклады. 6 декабря 2005 г. http://www.dha.spb.ru/reps05.shtml#1206).

24. Просеков О. В. Параметрический вариант многомерного быстрого преобразования Фурье // Электронный архив препринтов С.-Петербургского матем. общества. Препринт 2007;07.http://www.mathsoc.spb.ru/preprint/2007/index.html#07).

25. Просеков О. В. Разработка алгоритма БПФ для нетрадиционного числа точек // Сборник докладов I научно-технической конференции молодых специалистов «ЦНИИ «Морфизприбор». 22−25 апреля 2003 г. Санкт-Петербург. С. 116−121.

26. Рейдер Ч. М. Дискретное преобразование Фурье, когда число отсчётов простое / В кн. 9. с. 89−91.

27. Свердлик М. Б. Матричная интерпретация алгоритма БПФ для взаимно простых сомножителей // Радиотехника и электроника. 1983. № 10. С. 1931;1938.

28. Свердлик М. Б. Матричная интерпретация и вычислительная эффективность алгоритмов БПФ // Радиотехника и электроника. 1984. № 2. С. 265−274.

29. Свердлик М. Б., Троянский А. В. Обобщённое матричное описание алгоритма БПФ II Радиоэлектроника. 1995. № 7. С. 27−33.

30. Auslander L., Feig Е., Winograd S. New algorithms for the multidimensional Fourier transform // IEEE Transactions on Acoustics, Speech, and Signal Processing. 1983. V. ASSP-31. No. 2. P. 338−403.

31. Burrus C. S. Notes on the FFT // Department of Electrical and Computer Engineering, Rice University, Houston, TX 77 251−1892, September 29,1997.

32. Cooley J. W., Tukey J. W. An algorithm for the machine calculation of complex Fourier series // Mathematics of Computation. 1965. V. 19. No. 90. P. 297−301.

33. Duhamel P., Hollmann H. Split-radix FFT algorithm // Electronics Letters. 1984. V. 20. No. 1. P. 14−16.

34. Duhamel P., Vetterli M. Fast Fourier transforms: a tutorial review and a state of the art // Signal Processing. April 1990. V. 19. No. 4. P. 259−299.

35. Frigo M., Johnson S. G. A modified split-radix FFT with fewer arithmetic operations // IEEE Transactions on Signal Processing. 2007. V. 55 No. 1. P. 111−119.

36. Frigo M., Johnson S. G. The design and implementation of FFTW3 // Proceedings of the IEEE, special issue on «Program Generation, Optimization, and Adaptation». 2005. V. 93. No. 2. P. 216−231.http://www.fftw.org/).

37. Glassman J. A. A generalization of the fast Fourier transform // IEEE Transactions on Computers. 1970. V. C-19. No. 2. P. 105−116.

38. Harris D., McClellan J., Chan D., Schuessler H. Vector radix fast Fourier transform // IEEE International Conference on Acoustics, Speech, and Signal Processing. 1977. V 2. P. 548−551.

39. Johnson J., Johnson R. W., Rodriguez D., Tolimieri R. A methodology for designing, modifying and implementing Fourier transform algorithms on various architectures // Journal of Circuits, Systems, and Signal Processing. 1990. V. 9. No. 4. P. 449−500.

40. Korn D. G., Lambiotte J. J. Jr. Computing the fast Fourier transform on a vector computer // Mathematics of Computation. 1979. V. 33. No. 147. P. 977−992.

41. Pease M. C. An adaptation of the fast Fourier transform for parallel processing // Journal of the Association for Computing Machinery. 1968. V. 15. No. 2. P. 252−264.

42. Rivard G. E. Direct fast Fourier transform of bivariant functions // IEEE Transactions on Acoustics, Speech, and Signal Processing. 1977. V. 25. No. 3. P. 250−252.

43. Temperton C. Self-sorting mixed-radix fast Fourier transforms // Journal of Computational Physics. 1983. V. 52. No. 1. P. 1−23.

44. Yavne R. An economical method for calculating the discrete Fourier transform // Proceedings of the Fall Joint Computer Conference. 1968. V. 33. P. 115−125.