МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РЕСПУБЛИКИ КАЗАХСТАН
Казахский национальный технический университет им. К.И. Сатпаева
Геологоразведочный институт
Кафедра геофизики
Реферат.
Тема: Алгоритм быстрого преобразования Фурье.
Выполнил: ст. группы
ГФМ-03-2р Кирсанов А.
Проверила: Умирова Г. К.
Алматы 2005
Алгоритм быстрого преобразования Фурье (БПФ).
Быстрое преобразование Фурье позволяет свести число операций к минимуму. Идея его заключается в следующем. Пусть массив чисел sn содержит N=2q (q – целое число) отсчетов. Разобьем массив на две части, одна из которых включает все четные отсчеты, а вторая – нечетные:
sn′ = s2n, sn´´ = s2n+1, .
Число отсчетов в них равно N/2. Выполняя для каждого массива дискретное преобразование Фурье
(1)
получим спектры
(2)
также представленные половинным числом точек. Чтобы из них составить искомый спектр Sm как спектр суммы двух функций, нужно учесть, что точки второго массива сдвинуты относительно первого на один интервал дискретизации. По теореме запаздывания получим первую половину значений искомого спектра:
(3)
где 0 ≤ m ≤ N/2 – 1; .
Для получения второй половины воспользуемся тем, что промежуточные спектры и имеют период повторения, равный N/2 точек. Поэтому
(4)
так как .
Таким образом, затратив на вычисление двух промежуточных спектров (2) N2/4 операций, мы по формулам (3) и (4) вычислим все N точек искомого спектра, что потребует еще N операций (каждая состоит из одного умножения и одного сложения комплексных величин). Это создает уже заметную экономию.
Рассмотренный прием деления каждого массива на две части нужно продолжить, пока в каждой части останется всего по одной точке (это возможно, если исходный массив содержит N=2q точек). Но если в массиве останется лишь один отсчет (N = 1), то его дискретное преобразование (1) равно самому отсчету. Таким образом, вычисление спектра при БПФ сводится к последовательному вычислению по формулам (3) и (4) спектров промежуточных массивов по спектрам предыдущих половинных массивов, начиная с отсчетов sn. Формула дискретного преобразования явно не используется ни на одном этапе. Последовательность вычисления спектров при БПФ для массива N = 8 иллюстрирует рис. 1. Большие пунктирные квадраты содержат вычисления промежуточных спектров и для четных и нечетных отсчетов, а внутри них малые пунктирные квадраты содержат вычисления спектров более дробных массивов (по две точки), образованных делением каждого из промежуточных массивов и на четные и нечетные отсчеты. Сходящиеся стрелки указывают суммирование двух одноименных отсчетов промежуточных спектров (3). Причем числа, образующие второй член двучлена, обозначены у стрелки величинами ωm, на которые их нужно умножить. Для рассматриваемого размера массивов (N = 8) m = 0; 1; 2; …; 7.
Чтобы лучше уяснить схему расположения входных отсчетов, стрелок и коэффициентов ωm, нужно рассматривать чертеж справа налево, от выхода к входу. Правая коммутационная схема непосредственно соответствует формулам (3) и (4), где N = 8. Коммутационные схемы в больших квадратах строятся аналогично, но для N/2 = 4, а в малых квадратах – для N/4 = 2. Константы ω=ej2π/N должны быть на каждом этапе различны, что неудобно. Примем значение ω постоянным, вычисленным для максимального числа точек N = 8, тогда значения этих констант на промежуточных этапах равны ω2 и ω4 в соответствии с числом точек в промежуточных массивах.
Определим порядок задания последовательности входных отсчетов, получаемый в результате многократной сортировки на четные и нечетные номера элементов. Входная нумерация (0; 1; 2; 3; 4; 5; 6; 7) после первого деления массива на четные и нечетные номера дает (0; 2; 4; 6); (1; 3; 5; 7). Теперь, выделив четные и нечетные позиции, получим (0; 4;); (2; 6); (1; 5); (3; 7). Итак, для БПФ входные отсчеты нужно подавать в следующей последовательности: 0; 4; 2; 6; 1; 5; 3; 7. Запишем исходную нумерацию в двоичной форме: 000; 001; 010; 011; 100; 101; 110; 111. В двоичной форме номера подаваемых на вход отсчетов при БПФ выглядят следующим образом: 000; 100; 010; 110; 001; 101; 011; 111. Сравнивая почленно эти двоичные числа, легко увидеть, что во второй последовательности числа представляют собой комбинации единиц и нулей, располагающихся в обратном порядке, с переменой мест старших и младших разрядов. Сортировка входных отсчетов для БПФ путем изменения порядка следования двоичных разрядов в номерах отсчетов на обратный называется двоичной инверсией номеров отсчетов.
В рассматриваемом алгоритме Кули-Туки вычисления выполняются за q=log2N этапов; на каждом этапе по каждой паре комплексных чисел на входе вычисляется пара выходных комплексных чисел по графу «бабочка» (см. рис.1):
c = a + bωm ;
d = a + bωm+N/2 = a — bωm, (5)
включающему одно комплексное умножение и две операции типа комплексного сложения, т. е. четыре вещественных умножения и шесть вещественных сложений (вычитаний), всего 10 операций. Общее число арифметических операций при БПФ равно 5 N log2N (по сравнению с 8 N2 при ДПФ), выигрыш
ξ = 8N2/5N log2 N = 1,6N/log2N.
Например, при N = 1024 = 210 ε ≈ 160.
В алгоритме Кули-Туки выходные значения в каждой «бабочке» записываются в память на место входных, т. е. для входных данных, промежуточных значений и результатов можно использовать ячейки одного и того же массива. Поэтому данный алгоритм относится к алгоритмам БПФ с замещением. Экономия памяти достигается сравнительно сложной адресацией операндов.
Известны и другие алгоритмы БПФ, из которых наиболее прост по адресации алгоритм с однородной на всех этапах структурой. Данный алгоритм предназначен для памяти с последовательным доступом, т. е. с возможностью доступа к каждой ячейке памяти только после доступа к предыдущей.
