Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

Одноэтапный алгоритм БПФ



Разделим исходную N - точечную последовательность на две - точечные (начальные условия одноэтапного алгоритма БПФ):

· четных отсчетов;

· нечетных отсчетов.

Рис. 13.1. Деление исходной последовательности

Рис. 13.2. Пример деления 8-точечной последовательности

После этого запишем ДПФ (12.17) в виде:

где отображает четные, а — нечетные значения .

Вынесем за знак второй суммы:

, (13.2)

представим в виде:

и представим ДПФ (13.2) в виде:

, ,

и далее, с учетом обозначений сумм:

, , (13.3)

где:

и

; (13.4)

. (13.5)

Вывод: при вычислении N-точечного ДПФ (13.3) и достаточно вычислить

Определим поворачивающей множитель на второй половине периода :

(13.6)

Вывод: при вычислении N-точечного ДПФ поворачивающий множитель достаточно вычислить

Вывод: N-точечное ДПФ (13.3) можно выразить через -точечные ДПФ и (на рис. 13.4 — это последний, -й этап):

(13.7)

Согласно (13.7), N-точечное ДПФ вычисляется:

и ;

и ;

…………………………….

и .

Размерность вычисляемого ДПФ соответствует нижнему индексу

Сокращение количества операций достигнуто за счет одновременного (параллельного) вычисления по верхней и нижней формулам!

Это оказалось возможным в результате

Одновременное вычисление по верхней и нижней формулам в (13.7) при фиксированном (одном) называют операцией «бабочка» — коротко «бабочкой» — и изображают в виде сигнального графа (рис. 13.3).

Рис. 13.3. Сигнальный граф операции «бабочка»

Для вычисления N -точечного по формуле (13.7) потребуется «бабочек».

Рис. 13.4. Поэтапное вычисление N -точечного ДПФ





Дата публикования: 2014-11-28; Прочитано: 226 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.007 с)...