Вам бонус- начислено 1 монета за дневную активность. Сейчас у вас 1 монета

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

Лекция



Привет, сегодня поговорим про бпф по основанию с прореживанием по времени, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое бпф по основанию с прореживанием по времени , настоятельно рекомендую прочитать все из категории Цифровая обработка сигналов.

Содержание
Введение
Разбиение исходной последовательности прореживанием по времени
Процедура объединения. Граф «Бабочка»
Граф алгоритма БПФ с прореживанием по времени. Двоично-инверсная перестановка
Поворотные коэффициенты
Вычислительная эффективность алгоритма БПФ с прореживанием по времени
Выводы

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

БПФ по основанию 2 с прореживанием по времени
Рисунок 1: Разбиение и объединение последовательностей при N = 8


Разбиение исходной последовательности прореживанием по времени
Для начала комплексную экспоненту в выражении (1) обозначим как:
БПФ по основанию 2 с прореживанием по времени (2)
Тогда выражение (1) принимает вид:
БПФ по основанию 2 с прореживанием по времени (3)
Прореживание по времени заключается в разбиении исходной последовательности отсчетов БПФ по основанию 2 с прореживанием по времениБПФ по основанию 2 с прореживанием по временина две последовательности длительности БПФ по основанию 2 с прореживанием по времени БПФ по основанию 2 с прореживанием по времени и БПФ по основанию 2 с прореживанием по времени , БПФ по основанию 2 с прореживанием по времени, таких что БПФ по основанию 2 с прореживанием по времени, аБПФ по основанию 2 с прореживанием по времениБПФ по основанию 2 с прореживанием по времени. Другими словами, последовательность БПФ по основанию 2 с прореживанием по времени содержит отсчеты последовательности БПФ по основанию 2 с прореживанием по времени с четными индексами, а БПФ по основанию 2 с прореживанием по времени - с нечетными. Прореживание по времени для N = 8 наглядно представлено на рисунке 2.

БПФ по основанию 2 с прореживанием по времени
Рисунок 2: Прореживание по времени для N=8

Рассмотрим ДПФ сигнала прореженного по времени:
БПФ по основанию 2 с прореживанием по времени (4)
Если рассмотреть только первую половину спектра БПФ по основанию 2 с прореживанием по времениБПФ по основанию 2 с прореживанием по времени, а также учесть что
БПФ по основанию 2 с прореживанием по времени, (5)
тогда (4) можно записать:
БПФ по основанию 2 с прореживанием по времени (6)
где БПФ по основанию 2 с прореживанием по времени и БПФ по основанию 2 с прореживанием по времени , БПФ по основанию 2 с прореживанием по времени – БПФ по основанию 2 с прореживанием по времени точечные ДПФ последовательностей «четной» БПФ по основанию 2 с прореживанием по времени и «нечетной» БПФ по основанию 2 с прореживанием по времениБПФ по основанию 2 с прореживанием по времени :
БПФ по основанию 2 с прореживанием по времени (7)
И что же мы получили? Прореживание по времени можно считать алгоритмом разбиения последовательности на две половинной длительности. Первая половина объединенного спектра есть сумма спектра «четной» последовательности и спектра «нечетной» последовательности, умноженного на коэффициенты БПФ по основанию 2 с прореживанием по времени, которые носят названия поворотных коэффициентов.

Процедура объединения. Граф «Бабочка»
Теперь рассмотрим вторую половину спектра БПФ по основанию 2 с прореживанием по времениБПФ по основанию 2 с прореживанием по времени:
БПФ по основанию 2 с прореживанием по времени (8)
Рассмотрим подробнее множитель
БПФ по основанию 2 с прореживанием по времени. (9)
Учтем что
БПФ по основанию 2 с прореживанием по времени, (10)
тогда выражение (10) справедливо для любого целого БПФ по основанию 2 с прореживанием по времени, тогда (9) можно записать с учетом (10):
БПФ по основанию 2 с прореживанием по времени. (11)
Рассмотрим теперь поворотный коэффициент в (8):
БПФ по основанию 2 с прореживанием по времени. (12)
Тогда выражение (8) с учетом (11) и (12) принимает вид:
БПФ по основанию 2 с прореживанием по времени (13)
Таким образом окончательно можно записать:
БПФ по основанию 2 с прореживанием по времени (14)
Выражение (14) представляет собой алгоритм объединения при прореживании по времени. Об этом говорит сайт https://intellect.icu . Данную процедуру объединения можно представить в виде графа (рисунок 3), который называется «Бабочка».

БПФ по основанию 2 с прореживанием по времени
Рисунок 3: Процедура объединения на основе графа « Бабочка »


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

БПФ по основанию 2 с прореживанием по времени
Рисунок 4: Граф алгоритма БПФ с прореживанием по времени при N=8

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

Поворотные коэффициенты
Рассмотрим подробнее поворотные коэффициенты БПФ по основанию 2 с прореживанием по времени.
На первом уровне (выражение (15)) требуется всего один поворотный коэффициент БПФ по основанию 2 с прореживанием по времени, это означает что на первом уровне расчета спектра операции умножения не требуются (умножения на БПФ по основанию 2 с прореживанием по времени называются тривиальными, так как при умножении на БПФ по основанию 2 с прореживанием по времени множитель остается неизменным или меняет свой знак на противоположный).
На втором уровне имеем два поворотных коэффициента:
БПФ по основанию 2 с прореживанием по времени (17)
Умножение на мнимую единицу также можно считать тривиальным, так как реальные и мнимые части комплексного числа просто меняются местами и изменяют свой знак.
На третьем уровне имеем уже 4 поворотных коэффициента:
БПФ по основанию 2 с прореживанием по времени (18)
Графически поворотные коэффициенты можно представить как векторы на комплексной плоскости:

БПФ по основанию 2 с прореживанием по времени
Рисунок 5: Поворотные коэффициенты алгоритма БПФ с прореживанием по времени при N=8

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

БПФ по основанию 2 с прореживанием по времени
Рисунок 6: Поворотные коэффициенты алгоритма БПФ с прореживанием по времени при N=16

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

Вычислительная эффективность алгоритма БПФ с прореживанием по времени
Алгоритм с прореживанием по времени на каждом уровне требует БПФ по основанию 2 с прореживанием по времени комплексных умножений и сложений. ПриБПФ по основанию 2 с прореживанием по времениколичество уровней разложения — объединения равно БПФ по основанию 2 с прореживанием по времени, таким образом общее количество операций умножения и сложения равно БПФ по основанию 2 с прореживанием по времени.
Рассмотрим во сколько раз алгоритм БПФ с прореживанием по времени эффективнее ДПФ. Для этого рассмотрим коэффициент ускорения БПФ по основанию 2 с прореживанием по времени отношение количества комплексных умножение и сложений при использовании ДПФ и БПФ, при этом учтем что БПФ по основанию 2 с прореживанием по времени:
БПФ по основанию 2 с прореживанием по времени раз. (19)
В таблице ниже приведено требуемое количество операций БПФ по основанию 2 с прореживанием по времени для алгоритма ДПФ при различном БПФ по основанию 2 с прореживанием по времени и при использовании БПФ с прореживанием по времени.

БПФ по основанию 2 с прореживанием по времени 4 6 8 10 12
БПФ по основанию 2 с прореживанием по времени 16 64 256 1024 4096
БПФ по основанию 2 с прореживанием по времени ДПФ 256 4096 65536 1048576 16777216
БПФ по основанию 2 с прореживанием по времени БПФ 64 384 2048 10240 49152
БПФ по основанию 2 с прореживанием по времени, раз 4 10,7 32 102,4 341

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

Выводы
Таким образом, для получения эффективного алгоритма БПФ по основанию 2 с прореживанием по времени, приБПФ по основанию 2 с прореживанием по времени необходимо:
  • Осуществить двоично-инверсную перестановку отсчетов входного сигнала, тем самым обеспечив разбиение последовательности.
  • Используя поворотные коэффициенты сделать N/2 операций «Бабочка» согласно выражению (14) для получения первого объединения
  • Повторить операцию «Бабочка» согласно выражению (14) для объединения на следующий уровень еще БПФ по основанию 2 с прореживанием по временираз, также используя поворотные коэффициенты.
На выходе получим ДПФ входной последовательности.

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

Из статьи мы узнали кратко, но содержательно про бпф по основанию с прореживанием по времени
создано: 2015-05-23
обновлено: 2021-03-13
132825



Рейтиг 9 of 10. count vote: 2
Вы довольны ?:


Найди готовое или заработай

С нашими удобными сервисами без комиссии*

Как это работает? | Узнать цену?

Найти исполнителя
$0 / весь год.
  • У вас есть задание, но нет времени его делать
  • Вы хотите найти профессионала для выплнения задания
  • Возможно примерение функции гаранта на сделку
  • Приорететная поддержка
  • идеально подходит для студентов, у которых нет времени для решения заданий
Готовое решение
$0 / весь год.
  • Вы можите продать(исполнителем) или купить(заказчиком) готовое решение
  • Вам предоставят готовое решение
  • Будет предоставлено в минимальные сроки т.к. задание уже готовое
  • Вы получите базовую гарантию 8 дней
  • Вы можете заработать на материалах
  • подходит как для студентов так и для преподавателей
Я исполнитель
$0 / весь год.
  • Вы профессионал своего дела
  • У вас есть опыт и желание зарабатывать
  • Вы хотите помочь в решении задач или написании работ
  • Возможно примерение функции гаранта на сделку
  • подходит для опытных студентов так и для преподавателей



Комментарии


Оставить комментарий
Если у вас есть какое-либо предложение, идея, благодарность или комментарий, не стесняйтесь писать. Мы очень ценим отзывы и рады услышать ваше мнение.
To reply

Цифровая обработка сигналов

Термины: Цифровая обработка сигналов