Быстрое преобразование Фурье

Быстрое преобразование Фурье (БПФ) - это алгоритм вычисления преобразования Фурье для дискретного случая. В отличие от простейшего алгоритма, который имеет сложность порядка O(N2 ), БПФ имеет сложность всего лишь O(Nlog2 N). Алгоритм БПФ был впервые опубликован в 1965 году в статье Кули (Cooly) и Тьюки (Tukey).
Данное пособие содержит исходный код работающей программы для вычисления БПФ, подробное объяснение принципа ее работы и теоретическое обоснование. Все это можно найти и на других ресурсах, но трудно найти именно в таком комплекте: и программа, и объяснения, и теория, и на русском языке.
Если у вас нет времени и желания разбираться с теорией, то можете сразу скопировать текст программы на C++. Здесь находится заголовочный файл fft.h и исходник fft.cpp для быстрого преобразования Фурье для числа отсчетов, равного степени двойки. Вызывать надо функцию fft. А здесь находится заголовочный файл и исходник для произвольного (!) числа отсчетов. Он чуть медленнее, но скорость там тоже порядка Nlog2 N. Вызывать надо функцию universal_fft.
Определение 1 .
Дана конечная последовательность x0 , x1 , x2 ,...,xN-1 (в общем случае комплексных). Дискретное преобразование Фурье (ДПФ) заключается в поиске другой последовательности X0 , X1 , X2 ,...,XN-1 элементы которой вычисляются по формуле:
(1).
Определение 2 .
Дана конечная последовательность X0 , X1 , X2 ,...,XN-1 (в общем случае комплексных). Обратное дискретное преобразование Фурье (ДПФ) заключается в поиске другой последовательности x0 , x1 , x2 ,...,xN-1 элементы которой вычисляются по формуле:
(2).
Основным свойством этих преобразований (которое доказывается в соответствующих разделах математики) является тот факт, что из последовательности {x} получается (при прямом преобразовании) последовательность {X}, а если потом применить к {X} обратное преобразование, то снова получится исходная последовательность {x}.
Определение 3 .
Величина
называется поворачивающим множителем .
Рассмотрим ряд свойств поворачивающих множителей, которые нам понадобятся в дальнейшем.
Верхняя цифра в поворачивающем множителе не является индексом, это - степень. Поэтому, когда она равна единице, мы не будем ее писать:
Прямое преобразование Фурье можно выразить через поворачивающие множители. В результате формула (1) примет вид:
(3).
Эти коэффициенты действительно оправдывают свое название. Нарисуем на комплексной плоскости любое комплексное число, в виде вектора, исходящего из начала координат. Представим это комплексное число в показательной форме: rejφ , где r - модуль числа, а φ - аргумент. Модуль соответствует длине вектора, а аргумент - углу поворота:
Теперь возьмем какой-нибудь поворачивающий множитель . Его модуль равен единице, а фаза - 2π/N. Как известно, при умножении комплексных чисел, представленных в показательной форме, их модули перемножаются, а аргументы суммируются. Тогда умножение исходного числа на поворачивающий множитель не изменит длину вектора, но изменит его угол. То есть, произойдет поворот вектора на угол 2π/N (см. предыдущий рисунок).
Если теперь посмотреть на формулу (3), то станет ясен геометрический смысл преобразования Фурье: он состоит в том, чтобы представить N комплексных чисел-векторов из набора {x}, каждое в виде суммы векторов из набора {X}, повернутых на углы, кратные 2π/N.
Теорема 0 .
Если комплексное число представлено в виде e j2πN , где N - целое, то это число e j2πN = 1.
Доказательство :
По формуле Эйлера, и ввиду периодичности синуса и косинуса:
e j2 π N = cos(2πN) + j sin(2πN) = cos 0 + j sin 0 = 1 + j0 = 1
Теорема 1 .
Величина периодична по k и по n с периодом N. То есть, для любых целых l и m выполняется равенство:
(4).
Доказательство :
(5)
Величина -h = -(nl+mk+mlN) - целая, так как все множители целые, и все слагаемые целые. Значит, мы можем применить Теорему 0:
Что и требовалось доказать по (4).
Теорема 2 .
Для величины справедлива формула:
Доказательство :
Алгоритм быстрого преобразования Фурье (БПФ) - это оптимизированный по скорости способ вычисления ДПФ. Основная идея заключается в двух пунктах.
Необходимо разделить сумму (1) из N слагаемых на две суммы по N/2 слагаемых, и вычислить их по отдельности. Для вычисления каждой из подсумм, надо их тоже разделить на две и т.д.
Необходимо повторно использовать уже вычисленные слагаемые.
Применяют либо "прореживание по времени" (когда в первую сумму попадают слагаемые с четными номерами, а во вторую - с нечетными), либо "прореживание по частоте" (когда в первую сумму попадают первые N/2 слагаемых, а во вторую - остальные). Оба варианта равноценны. В силу специфики алгоритма приходится применять только N, являющиеся степенями 2. Рассмотрим случай прореживания по времени.
Теорема 3 .
Определим еще две последовательности: {x[even] } и {x[odd] } через последовательность {x} следующим образом:
x[even]n = x2n ,
x[odd]n = x2n+1 , (6)
n = 0, 1,..., N/2-1
Пусть к этим последовательностям применены ДПФ и получены результаты в виде двух новых последовательностей {X[even] } и {X[odd] } по N/2 элементов в каждой.
Утверждается, что элементы последовательности {X} можно выразить через элементы последовательностей {X[even] } и {X[odd] } по формуле:
(7).
Доказательство :
Начинаем от формулы (2), в которую подставляем равенства из (6):
(8)
Теперь обратим внимание на то, что:
(9)
Подставляя (9) в (8) получаем:
(10)
Сравним с формулами для X[even]k и X[odd]k при k = 0,1,…,N/2-1:
(11)
Подставляя (11) в (10) получим первую часть формулы (7):
Это будет верно при k = 0,1,…,N/2-1.
Согласно теореме 1:
(12)
Подставим (12) в (10), и заменим по теореме 2:
(13)
Для k = N/2,…,N-1 по формуле (2):
(14)
Подставляем (14) в (13):
Эта формула верна для k = N/2,…,N-1 и, соответственно, (k - N/2) = 0,1,…,N/2-1 и представляет собой вторую и последнюю часть утверждения (7), которое надо было доказать.
Формула (7) позволяет сократить число умножений вдвое (не считая умножений при вычислении X[even]k и X [odd]k ), если вычислять Xk не последовательно от 0 до N - 1, а попарно: X0 и XN/2 , X1 и XN/2+1 ,..., XN/2-1 и XN . Пары образуются по принципу: Xk и XN/2+k .
Теорема 4 .
ДПФ можно вычислить также по формуле:
(15)
Доказательство :
Согласно второй части формулы (7), получим:
Это доказывает второе равенство в утверждении теоремы, а первое уже доказано в теореме 3.
Также по этой теореме видно, что отпадает необходимость хранить вычисленные X[even]k и X[odd]k после использования при вычислении очередной пары и одно вычисление можно использовать для вычисления двух элементов последовательности {X}.
На этом шаге будет выполнено N/2 умножений комплексных чисел. Если мы применим ту же схему для вычисления последовательностей {X[even] } и {X[odd] }, то каждая из них потребует N/4 умножений, итого еще N/2. Продолжая далее в том же духе log2 N раз, дойдем до сумм, состоящих всего из одного слагаемого, так что общее количество умножений окажется равно (N/2)log2 N, что явно лучше, чем N2 умножений по формуле (2).
Рассмотрим БПФ для разных N. Для ясности добавим еще один нижний индекс, который будет указывать общее количество элементов последовательности, к которой этот элемент принадлежит. То есть X{R}k - это k-й элемент последовательности {X{R} } из R элементов. X{R}[even]k - это k-й элемент последовательности {X{R}[even] } из R элементов, вычисленный по четным элементам последовательности {X{2R} }. X{R}[odd]k - это k-й элемент последовательности {X{R}[odd] }, вычисленный по нечетным элементам последовательности {X{2R} }.
В вырожденном случае, когда слагаемое всего одно (N = 1) формула (1) упрощается до:
,
Поскольку в данном случае k может быть равно только 0, то X{1}0 = x{1}0 , то есть, ДПФ над одним числом дает это же самое число.
Для N = 2 по теореме 4 получим:
Для N = 4 по теореме 4 получим:
Отсюда видно, что если элементы исходной последовательности были действительными, то при увеличении N элементы ДПФ становятся комплексными.
Для N = 8 по теореме 4 получим:
Обратите внимание, что на предыдущем шаге мы использовали степени W4 , а на этом - степени W8 . Лишних вычислений можно было бы избежать, если учесть тот факт, что
Тогда формулы для N=4 будут использовать те же W-множители, что и формулы для N=8:
Подведем итог:
В основе алгоритма БПФ лежат следующие формулы:
(16)
Теперь рассмотрим конкретную реализацию БПФ. Пусть имеется N=2T элементов последовательности x{N} и надо получить последовательность X{N} . Прежде всего, нам придется разделить x{N} на две последовательности: четные и нечетные элементы. Затем точно так же поступить с каждой последовательностью. Этот итерационный процесс закончится, когда останутся последовательности длиной по 2 элемента. Пример процесса для N=16 показан ниже:
Итого выполняется (log2 N)-1 итераций.
Рассмотрим двоичное представление номеров элементов и занимаемых ими мест. Элемент с номером 0 (двоичное 0000) после всех перестановок занимает позицию 0 (0000), элемент 8 (1000) - позицию 1 (0001), элемент 4 (0100) - позицию 2 (0010), элемент 12 (1100) - позицию 3 (0011). И так далее. Нетрудно заметить связь между двоичным представлением позиции до перестановок и после всех перестановок: они зеркально симметричны. Двоичное представление конечной позиции получается из двоичного представления начальной позиции перестановкой битов в обратном порядке. И наоборот.
Этот факт не является случайностью для конкретного N=16, а является закономерностью. На первом шаге четные элементы с номером n переместились в позицию n/2, а нечетные из позиции в позицию N/2+(n-1)/2. Где n=0,1,…,N-1. Таким образом, новая позиция вычисляется из старой позиции с помощью функции:
ror(n,N) = [n/2] + N{n/2}
Здесь как обычно [x] означает целую часть числа, а {x} - дробную.
В ассемблере эта операция называется циклическим сдвигом вправо (ror) , если N - это степень двойки. Название операции происходит из того факта, что берется двоичное представление числа n, затем все биты, кроме младшего (самого правого) перемещаются на 1 позицию вправо. А младший бит перемещается на освободившееся место самого старшего (самого левого) бита.

рис. 1
Дальнейшие разбиения выполняются аналогично. На каждом следующем шаге количество последовательностей удваивается, а число элементов в каждой из них уменьшается вдвое. Операции ror подвергаются уже не все биты, а только несколько младших (правых). Старшие же j-1 битов остаются нетронутыми (зафиксированными), где j - номер шага:

рис. 2
Что происходит с номерами позиций при таких последовательных операциях? Давайте проследим за произвольным битом номера позиции. Пусть этот бит находился в j-м двоичном разряде, если за 0-й разряд принять самый младший (самый правый). Бит будет последовательно сдвигаться вправо на каждом шаге до тех пор, пока не окажется в самой правой позиции. Это случится после j-го шага. На следующем, j+1-м шаге будет зафиксировано j старших битов и тот бит, за которым мы следим, переместится в разряд с номером T-j-1. После чего окажется зафиксированным и останется на месте. Но именно такое перемещение - из разряда j в разряд T-j-1 и необходимо для зеркальной перестановки бит. Что и требовалось доказать.
Теперь, мы убедились в том, что перестановка элементов действительно осуществляется по принципу, при котором в номерах позиций происходит в свою очередь другая перестановка: зеркальная перестановка двоичных разрядов. Это позволит нам получить простой алгоритм:
for(I = 1; I = J) // пропустить уже переставленные conitnue; S = x[I]; x[I] = x[J]; x[J] = S; // перестановка элементов xI и xJ}
Некоторую проблему представляет собой операция обратной перестановки бит номера позиции reverse(), которая не реализована ни в популярной архитектуре Intel, ни в наиболее распространенных языках программирования. Приходится реализовывать ее через другие битовые операции. Ниже приведен алгоритм функции перестановки T младших битов в числе I:
unsigned int reverse(unsigned int I, int T){ int Shift = T - 1; unsigned int LowMask = 1; unsigned int HighMask = 1 << Shift; unsigned int R; for(R = 0; Shift >= 0; LowMask <<= 1, HighMask >>= 1, Shift -= 2) R |= ((I & LowMask) << Shift) | ((I & HighMask) >> Shift);return R;}
Пояснения к алгоритму. В переменных LowMask и HighMask хранятся маски, выделяющие два переставляемых бита. Первая маска в двоичном представлении выглядит как 0000…001 и в цикле изменяется, сдвигая единицу каждый раз на 1 разряд влево:
0000...0010000...0100000...100...
Вторая маска (HighMask) принимает последовательно значения:
1000...0000100...0000010...000...,
каждую итерацию сдвигая единичный бит на 1 разряд вправо. Эти два сдвига осуществляются инструкциями LowMask <<= 1 и HighMask >>= 1.
Переменная Shift показывает расстояние (в разрядах) между переставляемыми битами. Сначала оно равно T-1 и каждую итерацию уменьшается на 2. Цикл прекращается, когда расстояние становится меньше или равно нулю.
Операция I & LowMask выделяет первый бит, затем он сдвигается на место второго (<<Shift). Операция I & HighMask выделяет второй бит, затем он сдвигается на место первого (>>Shift). После чего оба бита записываются в переменную R операцией "|".
Вместо того чтобы переставлять биты позиций местами, можно применить и другой метод. Для этого надо вести отсчет 0,1,2,…,N/2-1 уже с обратным следованием битов. Опять-таки, ни в ассемблере Intel, ни в распространенных языках программирования не реализованы операции над обратным битовым представлением. Но алгоритм приращения на единицу известен, и его можно реализовать программно. Вот пример для T=4.
I = 0;J = 0;for(J1 = 0; J1 < 2; J4++, J ^= 1)for(J2 = 0; J2 < 2; J3++, J ^= 2) for(J4 = 0; J4 < 2; J4++, J ^= 4) for(J8 = 0; J8 < 2; J8++, J ^= 8) { if (I < J){ S = x[I]; x[I] = x[J]; x[J] = S; // перестановка элементов xIи xJ } I++; }
В этом алгоритме используется тот общеизвестный факт, что при увеличении числа от 0 до бесконечности (с приращением на единицу) каждый бит меняется с 0 на 1 и обратно с определенной периодичностью: младший бит - каждый раз, следующий - каждый второй раз, следующий - каждый четвертый и так далее.
Эта периодичность реализована в виде T вложенных циклов, в каждом из которых один из битов позиции J переключается туда и обратно с помощью операции XOR (В C/C++ она записывается как ^=). Позиция I использует обычный инкремент I++, уже встроенный в язык программирования.
Данный алгоритм имеет тот недостаток, что требует разного числа вложенных циклов в зависимости от T. На практике это не очень плохо, поскольку T обычно ограничено некоторым разумным пределом (16..20), так что можно написать столько вариантов алгоритма, сколько нужно. Тем не менее, это делает программу громоздкой. Ниже я предлагаю вариант этого алгоритма, который эмулирует вложенные циклы через стеки Index и Mask.
int Index[MAX_T];int Mask[MAX_T];int R;for(I = 0; I < T; I++){ Index[I] = 0; Mask[I] = 1 << (T - I - 1);}J = 0;for(I = 0; I < N; I++){ if (I < J){ S = x[I]; x[I] = x[J]; x[J] = S; // перестановка элементов xI и xJ} for(R = 0; R < T; R++) { J ^= Mask[R]; if (Index[R] ^= 1) // эквивалентно Index[R] ^= 1; if (Index[R] != 0)break; }}
Величина MAX_T определяет максимальное значение для T и в наихудшем случае равна разрядности целочисленных переменных ЭВМ. Этот алгоритм, может быть, чуть медленнее, чем предыдущий, но дает экономию по объему кода.
И, наконец, последний алгоритм. Он использует классический подход к многоразрядным битовым операциям: надо разделить 32-бита на 4 байта, выполнить перестановку в каждом из них, после чего переставить сами байты.
Перестановку бит в одном байте уже можно делать по таблице. Для нее нужно заранее приготовить массив reverse256 из 256 элементов. Этот массив будет содержать 8-битовые числа. Записываем туда числа от 0 до 255 и переставляем в каждом порядок битов.
Теперь этот массив применим для последней реализации функции reverse:
unsigned int reverse(unsigned int I, int T){ unsigned int R; unsigned char *Ic = (unsigned char*) &I; unsigned char *Rc = (unsigned char*) &R; Rc[0] = reverse256[Ic[3]]; Rc[1] = reverse256[Ic[2]]; Rc[2] = reverse256[Ic[1]]; Rc[3] = reverse256[Ic[0]];R >>= (32 - T); Return R;}
Обращения к массиву reverse256 переставляют в обратном порядке биты в каждом байте. Указатели Ic и Ir позволяют обратиться к отдельным байтам 32-битных чисел I и R и переставить в обратном порядке байты. Сдвиг числа R вправо в конце алгоритма устраняет различия между перестановкой 32 бит и перестановкой T бит. Ниже приводится наглядная геометрическая иллюстрация алгоритма, где стрелками показаны перестановки битов, байтов и сдвиг.

рис. 3
Оценим сложность описанных алгоритмов. Понятно, что все они пропорциональны N с каким-то коэффициентом. Точное значение коэффициента зависит от конкретной ЭВМ. Во всех случаях мы имеем N перестановок со сравнением I и J, которое предотвращает повторную перестановку некоторых элементов. Рядом присутствует некоторый обрамляющий код, применяющий достаточно быстрые операции над целыми числами: присваивания, сравнения, индексации, битовые операциии и условные переходы. Среди них в архитектуре Intel наиболее накладны переходы. Поэтому я бы рекомендовал последний алгоритм. Он содержит всего N переходов, а не 2N как в алгоритме со вложенными циклами или их эмуляцией и не NT как в самом первом алгоритме.

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать полную версию