Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Обозначим
|
|
где
.
Учтем, что,
Поэтому
Последнее соотношение описывает типовую операцию алгоритма БПФ с прореживанием во времени. Эта операция называется операцией «бабочка»
Графическое представление вычислительных операций приведено на рисунке.
Стрелочками представлены множители
Отсчеты S0, S1, S2, S3 получаются с использованием операции сложения, поэтому около них стоит знак “ + “, отсчеты S4, S5, S6, S7 находятся после выполнения операции вычитания и около них поставлен знак “ - “.
Определим операции над двухточечными последовательностями
При N=2
Совмещая рассмотренные выше бабочки получим графическое представление алгоритма БПФ с прореживанием во времени
Подсчитаем количество операций умножения, которые нужно выполнить, используя алгоритм БПФ. Для этого составим таблицу 4.1.
Таблица 4.1
| Номер шага разбиения | Количество умножений на постоянный коэффициент | Количество блоков ДПФ, подлежащих дальнейшему разбиению | Вид последовательности на входах оставшихся блоков |
| N / 2 | N / 2 | ||
| 2 (N / 4) = N / 2 | N / 4 | ||
| 4 (N / 8) = N / 2 | N / 8 | ||
| . . . | . . . | . . . | . . . |
| M -1 | N / 2 | 2 M -1 | N / 2 M -1 = 2 |
| M | N / 2 | - | - |
Из таблицы видно, что на каждом шаге разбиения выполняется N / 2 умножений, а количество шагов равно M = log 2 N. Следовательно, количество умножений равно
(N / 2) log2 N вместо N2 при ДПФ. Величина выигрыша при переходе от ДПФ к БПФ увеличивается с увеличением количества отсчетов N.
4.4. Алгоритм быстрого преобразования Фурье с прореживанием по
частоте
Вместо изложенной процедуры разбиения множества объектов на объекты с четны-
ми и нечетными номерами можно рассмотреть процедуру разбиения исходного множества на две половины: правую и левую. Последняя процедура и нашла применение в алгоритме БПФ, основанном на прореживании по частоте.
Пусть имеется исходная N - точечная последовательность xn, где N = 2M (рисунок 6.4). Разобьем члены этой последовательности на две группы. В первую включим первую половину членов исходной последовательности, а во вторую группу - вторую половину. Из первой группы образуем последовательность x1m, а из второй - последовательность x2m.
Рисунок 4.4 - Разбиение последовательности отсчетов x на две последовательности
x1 и x2, содержащие первую и вторую половину членов исходной
последовательности соответственно
Индексы последовательностей xn и x1m связаны соотношением n = m, а индексы по-
следовательностей xn и x2m - соотношением n = N/ 2 + m.
Тогда выражение для прямого ДПФ (6.3) можно представить в виде
.