Реферат на тему: Алгоритм быстрого преобразования Фурье

Тема: Алгоритм быстрого преобразования Фурье

         Быстрое преобразование Фурье позволяет свести число операций к минимуму. Идея его заключается в следующем. Пусть массив чисел s_n содержит N=2^q (q – целое число) отсчетов. Разобьем массив на две части, одна из которых включает все четные отсчеты, а вторая – нечетные:

s_n^′ = s_2n,      s_n^´´ = s_2n+1,     .

Число отсчетов в них равно N/2. Выполняя для каждого массива дискретное преобразование Фурье

(1)

получим спектры

(2)

также представленные половинным числом точек.  Чтобы из них составить искомый спектр S_m как спектр суммы двух функций, нужно учесть, что точки второго массива сдвинуты относительно первого на один интервал дискретизации. По теореме запаздывания получим первую половину значений искомого спектра:

                                  (3)

где 0 ≤ m ≤ N/2 – 1; .

Для получения второй половины воспользуемся тем, что промежуточные спектры  и   имеют период повторения, равный N/2 точек. Поэтому

(4)

так как .

Таким образом, затратив на вычисление двух промежуточных спектров (2) N²/4 операций, мы по формулам (3) и (4) вычислим все N точек искомого спектра, что потребует еще N операций (каждая состоит из одного умножения и одного сложения комплексных величин). Это создает уже заметную экономию.

Рассмотренный прием деления каждого массива на две части нужно продолжить, пока в каждой части останется всего по одной точке (это возможно, если исходный массив содержит N=2^q точек). Но если в массиве останется лишь один отсчет (N = 1), то его дискретное преобразование (1) равно самому отсчету. Таким образом, вычисление спектра при БПФ сводится к последовательному вычислению по формулам (3) и (4) спектров промежуточных массивов по спектрам предыдущих половинных массивов, начиная с отсчетов s_n. Формула дискретного преобразования явно не используется ни на одном этапе. Последовательность вычисления спектров при БПФ для массива N = 8 иллюстрирует рис. 1. Большие пунктирные квадраты содержат вычисления промежуточных спектров  и  для четных и нечетных отсчетов, а внутри них малые пунктирные квадраты содержат вычисления спектров более дробных массивов (по две точки), образованных делением каждого из промежуточных массивов  и на четные и нечетные отсчеты. Сходящиеся стрелки указывают суммирование двух одноименных отсчетов промежуточных спектров (3). Причем числа, образующие второй член двучлена, обозначены у стрелки величинами ω^m, на которые их нужно умножить. Для рассматриваемого размера массивов (N = 8) m = 0; 1; 2; …; 7.

Чтобы лучше уяснить схему расположения входных отсчетов, стрелок и коэффициентов ω^m, нужно рассматривать чертеж справа налево, от выхода к входу. Правая коммутационная схема непосредственно соответствует формулам (3) и (4), где N = 8. Коммутационные схемы в больших квадратах строятся аналогично, но для N/2 = 4, а в малых квадратах – для N/4 = 2. Константы ω=e^j2π/N должны быть на каждом этапе различны, что неудобно. Примем значение ω постоянным, вычисленным для максимального числа точек N = 8, тогда значения этих констант на промежуточных этапах равны ω² и ω⁴ в соответствии с числом точек в промежуточных массивах.

Определим порядок задания последовательности входных отсчетов, получаемый в результате многократной сортировки на четные и нечетные номера элементов. Входная нумерация (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=log₂N этапов; на каждом этапе по каждой паре комплексных чисел на входе вычисляется пара выходных комплексных чисел по графу «бабочка» (см. рис.1):

c = a + bω^m ;

                                             d = a + bω^m+N/2 = a — bω^m,                                         (5)

включающему одно комплексное умножение и две операции типа комплексного сложения, т. е. четыре вещественных умножения и шесть вещественных сложений (вычитаний), всего 10 операций. Общее число арифметических операций при БПФ равно 5 N log₂N (по сравнению с 8 N² при ДПФ), выигрыш

ξ = 8N²/5N log₂ N = 1,6N/log₂N.

Например, при N = 1024 = 2¹⁰ ε ≈ 160.

В алгоритме Кули-Туки выходные значения в каждой «бабочке» записываются в память на место входных, т. е. для входных данных, промежуточных значений и результатов можно использовать ячейки одного и того же массива. Поэтому данный алгоритм относится к алгоритмам БПФ с замещением. Экономия памяти достигается сравнительно сложной адресацией операндов.

Известны и другие алгоритмы БПФ, из которых наиболее прост по адресации алгоритм с однородной на всех этапах структурой. Данный алгоритм предназначен для памяти с последовательным доступом, т. е. с возможностью доступа к каждой ячейке памяти только после доступа к предыдущей.