Составители:
Вычисления всех и ci требуют O(N) действий, три преобразования Фурье требуют O(Nlog(N)) действий,
перемножение результатов преобразований Фурье требует O(N) действий, вычисление всех bi зная значения
свертки требует O(N) действий. Итого для дискретного преобразования Фурье требуется O(Nlog(N)) действий
для любого N.
Этот алгоритм быстрого преобразования Фурье может работать над кольцом только когда известны
первообразные корни из единицы степеней 2N и 2k.
2.4 Принцип работы Быстрого преобразования Фурье
БПФ работает с разложением N-точечного временного промежутка сигнала на N временных сигнальных
промежутков, каждый из которых состоял из одной точки. Второй шаг заключается в расчете N частотных
спектров, соответствующего этим временным сигнальным промежуткам. После этого, на основе N спектров
синтезируется единый частотный спектр.
Рисунок 10.1 Процедура разбиения сигналапоказывает пример разделения временной области с
использованием БПФ
. В этом примере 16-ти точечный сигнал разлагается на четыре отдельные компоненты.
Первый этап заключается в разбиения 16-ти точечного сигнала на два сигнала по 8 точек. На втором этапе
происходит разложение данных сигналов на четыре сигнала по 4 точки. Данная процедура продолжается до
тех пор, пока не будет сформировано N сигналов состоящих из одной
точки. Чересстрочное разложения
используется при разделении выборки сигнала на две выборки. Сигнал разделяется как при четном, так и при
нечетном количестве отсчетов в выборке. В системе проводится 2N этапов в разложении, т.е. на 16–ти
точечный сигнал (24) предусматривает 4 этапа, 512 точки (27) требует 7 этапов, 4096 точки (212)
предусматривает 12 этапов и т.д. Запомним, это значение - оно
будет много раз встречаться в этой главе.
Рисунок 10.1 Процедура разбиения сигнала
Теперь, когда понятна структура разложения, ее можно значительно упростить. Разложения является не более
чем перераспределение отсчетов сигнала. Это иллюстрирует Рисунок 10.2 Процедура перераспределения
отсчетов сигнала Слева представлены номера отсчетов первоначального сигнала, вместе с их двоичными
эквивалентами. Справа, измененные номера, а также их двоичные эквиваленты. Идея состоит в том, что
двоичные числа являются
инверсией друг друга. Например, отсчёт №3 (0011) можно получить из отсчёта №12
(1100). Отсчёт № 14 (1110) получается из отсчета № 7 (0111), и так далее. Разбиение временной области в
БПФ обычно, проводится с использование алгоритма сортировки инвертированных бит. Это предполагает
изменение N временных областей, с подсчетом в двоичном виде и переворачиванием бит слева на право.
Рисунок 10.2 Процедура перераспределения отсчетов сигнала !!!
Следующим шагом алгоритма БПФ является нахождение частоты спектров одноточечного сигналов,
определенного во временной области. Это делается элементарно: спектр одноточечного сигнала равен самому
себе. Это означает, что на этом шаге ничего не надо. Хотя не стоит забывать, что каждый из одноточечных
сигналов теперь представляет собой спектр частот, а не сигнал во временной
области
Страницы
- « первая
- ‹ предыдущая
- …
- 149
- 150
- 151
- 152
- 153
- …
- следующая ›
- последняя »
