БПФ по основанию 2 с прореживанием по времени

Введение

Разбиение исходной последовательности прореживанием по времени

Процедура объединения. Граф «Бабочка»

Граф алгоритма БПФ с прореживанием по времени. Двоично-инверсная перестановка

Поворотные коэффициенты

Вычислительная эффективность алгоритма БПФ с прореживанием по времени

Выводы

Ранее были приведены выражения для ДПФ и схема процедуры разбиения-объединения. Они потребуются нам для дальнейшего изложения, поэтому приведем их без пояснений.

Выражение для ДПФ имеет вид:

Процедура разбиения-объединения представлена на рисунке 1.

Для начала комплексную экспоненту в выражении (1) обозначим как:

Тогда выражение (1) принимает вид:

Прореживание по времени заключается в разбиении исходной последовательности отсчетов , на две последовательности длительности   и  , , таких что , а, . Другими словами, последовательность  содержит отсчеты последовательности  с четными индексами, а  - с нечетными. Прореживание по времени для N = 8 наглядно представлено на рисунке 2.

Рассмотрим ДПФ сигнала прореженного по времени:

Если рассмотреть только первую половину спектра , , а также учесть что

И что же мы получили? Прореживание по времени можно считать алгоритмом разбиения последовательности на две половинной длительности. Первая половина объединенного спектра есть сумма спектра «четной» последовательности и спектра «нечетной» последовательности, умноженного на коэффициенты , которые носят названия поворотных коэффициентов.

Теперь рассмотрим вторую половину спектра , :

Рассмотрим подробнее множитель

Учтем что

Рассмотрим теперь поворотный коэффициент в (8):

Тогда выражение (8) с учетом (11) и (12) принимает вид:

Таким образом окончательно можно записать:

Выражение (14) представляет собой алгоритм объединения при прореживании по времени. Об этом говорит сайт https://intellect.icu . Данную процедуру объединения можно представить в виде графа (рисунок 3), который называется «Бабочка».

Представим в виде графа алгоритм БПФ с прореживанием по времени основанный на разбиении — объединении при (рисунок 1).

На первом этапе отсчеты входного сигнала переставляются местами и исходная последовательность делится на «четную» и «нечетную последовательности» (обозначены красными и синими стрелками). Потом «четная» и «нечетная» последовательности в свою очередь делятся на «четную» и «нечетную» последовательности. При  такое деление можно делать раз. В нашем случае . Данная процедура называется двоично-инверсной перестановкой, так можно выполнить перенумерацию отсчетов переписав номер отсчета в двоичной системе в обратном направлении. Например имеет индекс в десятичной системе счисления , если же  переписать справа налево то получим , то есть после разбиения на четные нечетные перед первой операцией «Бабочка» встанет на место, которая в свою очередь встанет на место . По аналогичному правилу поменяются местами все отсчеты, при этом некоторые останутся на месте, в частности , так как если  переписать справа налево то все равно останется , аналогично   и . Очень важно понять, что данный метод перенумерации должен применяться при записи числа в двоичной системе состоящей из  разрядов. В приведенном примере использовалось 3 разряда двоичного числа, но если же  (), то необходимо записать число при использовании 4 разрядов. В этом случае  и после переписывания получим , то есть при   не останется на месте, а поменяется местами с .

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

После двоично-инверсной перестановки получаем четыре 2-точечных ДПФ:

На основе четырех 2-точечных ДПФ формируются два 4-точечных ДПФ:

И на последнем уровне формируется полный спектр входного сигнала.

Рассмотрим подробнее поворотные коэффициенты .

На первом уровне (выражение (15)) требуется всего один поворотный коэффициент , это означает что на первом уровне расчета спектра операции умножения не требуются (умножения на  называются тривиальными, так как при умножении на  множитель остается неизменным или меняет свой знак на противоположный).

На втором уровне имеем два поворотных коэффициента:

Умножение на мнимую единицу также можно считать тривиальным, так как реальные и мнимые части комплексного числа просто меняются местами и изменяют свой знак.

На третьем уровне имеем уже 4 поворотных коэффициента:

Графически поворотные коэффициенты можно представить как векторы на комплексной плоскости:

Можно заметить что на всех уровнях объединения количество поворотных коэффициентов удваивается, причем все поворотные коэффициенты предыдущего уровня объединения присутствуют и на следующем уровне. Таким образом для того чтобы перейти на следующий уровень необходимо между поворотными коэффициентами текущего уровня вставить поворотные коэффициенты следующего. Графически для перехода на следующий уровень при N =16 необходимо дополнить рисунок 5 как это показано на рисунке 6. Серые вектора показывают поворотные коэффициенты которые будут присутствовать на последнем уровне при , которых нет при  .

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

Алгоритм с прореживанием по времени на каждом уровне требует  комплексных умножений и сложений. Приколичество уровней разложения — объединения равно , таким образом общее количество операций умножения и сложения равно .

Рассмотрим во сколько раз алгоритм БПФ с прореживанием по времени эффективнее ДПФ. Для этого рассмотрим коэффициент ускорения  отношение количества комплексных умножение и сложений при использовании ДПФ и БПФ, при этом учтем что :

В таблице ниже приведено требуемое количество операций  для алгоритма ДПФ при различном  и при использовании БПФ с прореживанием по времени.

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

Таким образом, для получения эффективного алгоритма БПФ по основанию 2 с прореживанием по времени, при необходимо:

На выходе получим ДПФ входной последовательности.