ABOUT MODIFICATION OF ONE-DIMENSIONAL FAST FOURIER TRANSFORM ON ALGORITHM OF COOLEY-TUKEY

Full Text

Введение. Дискретное преобразование Фурье (ДПФ), одномерное и многомерное, имеет множество приложений в задачах цифровой обработки сигналов, например, ДПФ можно использовать для спектрального анализа многомерных сигналов, для обработки космоснимков. Общепринятый алгоритм, который лежит во всех стандартных пакетах обработки сигналов, представляет собой последовательное вычисление одномерного дискретного преобразования Фурье, так называемый алгоритм «по строкам, по столбцам». Существуют различные методы ускорения данного алгоритма - быстрое преобразование Фурье. Самой распространенной реализацией быстрого преобразования Фурье является алгоритм Кули-Тьюки. Модификации данного алгоритма позволяют сократить время выполнения вычислений быстрого преобразования Фурье. Увеличение скорости выполнения алгоритма можно получить путем изменения основания алгоритма Кули-Тьюки: вместо основания 2 берут 4, 8, 16 и т. д., а также использованием параллельных вычислений. В работе создана программа в среде MATLAB модифицированного алгоритма Кули-Тьюки для сигнала с числом отсчетов p · 2s, p, s N. Число операций в этом алгоритме меньше, чем при непосредственном вычислении дискретного преобразования Фурье, что позволило сократить время выполнения программы по сравнению со встроенным алгоритмом [1-3]. Быстрое преобразование Фурье на основе модифицированного алгоритма Кули-Тьюки. Дискретное преобразование Фурье периодического дискретного сигнала с периодом N определяется как (1) Функция является периодической функцией по аргументу k с периодом N. Дискретное преобразование Фурье представляет собой N отсчетов спектра, взятых на периоде с интервалом дискретизации по частоте, равным Для больших значений N прямое вычисление по выражению (1) требует выполнения весьма большого числа арифметических операций умножения и сложения, что затрудняет реализацию вычислений в реальном масштабе времени. Быстрым преобразованием Фурье называют набор алгоритмов, реализация которых приводит к существенному уменьшению вычислительной сложности дискретного преобразования Фурье [4]. Основная идея быстрого преобразования Фурье состоит в том, чтобы разбить исходный N-отсчетный сигнал x(n) на два более коротких сигнала, ДПФ которых могут быть скомбинированы таким образом, чтобы получить ДПФ исходного N-отсчетного сигнала. Так, если исходный N-отсчетный сигнал разбить на два -отсчетных сигнала, то для вычисления ДПФ каждого из них потребуется около комплексных умножений. Тогда для вычисления искомого N-отсчетного ДПФ потребуется порядка комплексных умножений, т. е. вдвое меньше по сравнению с прямым вычислением. Операцию разбиения можно повторить, вычисляя вместо -отсчетного ДПФ два -отсчетных ДПФ и сокращая тем самым объем вычислений еще в два раза. Существует большое количество алгоритмов БПФ, однако все они являются частными случаями единого алгоритма, базирующегося на задаче разбиения одного массива чисел на два. Наиболее распространенным алгоритмом является алгоритм Кули-Тьюки [5] и его аналоги [6-9]. Алгоритм Кули-Тьюки по основанию 2 работает следующим образом. В этом случае количество отсчетов в выборке функции должно быть кратно степени 2. Выборка делится пополам, далее каждая половина делится на две части. Продолжается данный процесс до тех пор, пока не останутся два элемента, для которых реализуется преобразование Фурье. Таким образом, при вычислении одномерного дискретного преобразования Фурье длиной N необходимо выполнить двухточечных ДПФ, каждое из которых требует одно комплексное умножение и два комплексных сложения. Двумерное разбиение по основанию 2 делит выборку N × N элементов на четыре выборки элементов и т. д. до тех пор, пока не останутся выборки 2 × 2 элементов (см. рисунок). Алгоритм двумерного ДПФ с разбиением на строки и столбцы требует проведения 2N-одномерных ДПФ, и вычислительная сложность его составляет комплексных умножений и комплексных сложений. Разработка различных модификаций алгоритма Кули-Тьюки в одномерном и многомерном случаях проводилась М. В. Носковым, А. В. Старовойтовым и другими исследователями в работах [10-13]. Все результаты работ направлены на уменьшение времени вычислений. Этого можно добиться путем уменьшения числа операций комплексного умножения и сложения, изменения основания алгоритма Кули-Тьюки или распараллеливая вычисления. Кроме того, само комплексное умножение можно вычислять различным образом - через 4 действительных умножения и 2 сложения или за 3 действительных умножения и 3 действительных сложения. Рассмотрим сигнал f, который является периодическим сигналом с периодом p · 2s (см., например, [14]). Отсчеты задаются как fk где Дискретное преобразование Фурье для данного сигнала f задается формулой Разобьем данную сумму на 2s сумм следующего вида Внешнюю сумму можно рассматривать как преобразование Фурье для сигнала с числом отсчетов 2s, для подсчета которого можно воспользоваться алгоритмом Кули-Тьюки, а внутреннюю сумму вычислить как ДПФ для сигнала с числом отсчетов р. Тогда общее число операций в полученном алгоритме составит комплексных сложений и комплексных умножений. Модифицированный одномерный алгоритм БПФ по аналогу Кули-Тьюки в MATLAB. Описанный алгоритм был реализован в виде программы в системе компьютерной математики MATLAB и протестирован на наборе, состоящем из 16384 отсчетов сигнала. Время выполнения программы сравнивалось со временем, потраченным на вычисление ДПФ с помощью встроенного алгоритма среды MATLAB. В таблице приведены данные выполнения модифицированного алгоритма и встроенной версии, программа тестировалась на виртуальной машине со следующими параметрами: AMD Phenom X2 3.2GHz, 2 Gb ОЗУ. Время выполнения сократилось в среднем на 20 %. Разработанная программа была зарегистрирована [15]. Заключение. Представлена реализация модифицированного алгоритма по аналогу Кули-Тьюки дискретного преобразования Фурье для одномерного сигнала с числом отсчетов p · 2s. Для данного алгоритма была разработана программа в системе компьютерной математики MATLAB. Авторы ставили перед собой задачу реализации модифицированного одномерного алгоритма БПФ по аналогу Кули-Тьюки именно в MATLAB, так как для реализации цифровой обработки сигналов радиоприемных устройств на практике часто используют программное обеспечение фирмы Xilinx (LogiCORE IP Fast Fourier Transform), где БПФ реализовано по алгоритму Кули-Тьюки в MATLAB. Схема прореживания двумерного ДПФ по основанию 2 Время выполнения модифицированного алгоритма и встроенного алгоритма Кули-Тьюки в MATLAB Модифицированный алгоритм Встроенный алгоритм 2,063 2,634 2,004 2,523 2,025 2,484 2,013 2,582 2,053 2,404 1,996 2,353 2,014 2,634

About the authors

T. V. Sidorova

Siberian Federal University, Institute of space and informatics technologies

26, Kirenskogo Str., Krasnoyarsk, 660079, Russian Federation

T. V. Zykova

Siberian Federal University, Institute of space and informatics technologies

Email: zykovatv@mail.ru
26, Kirenskogo Str., Krasnoyarsk, 660079, Russian Federation

K. V. Safonov

Reshetnev Siberian State Aerospace University

31, Krasnoyarsky Rabochy Av., Krasnoyarsk, 660037, Russian Federation

References

Supplementary files