Lek 13

Лекция 13. Быстрое преобразование Фурье (БПФ)
БПФ Кули-Тьюки.
Одноэтапный алгоритм БПФ.
Двухэтапный алгоритм БПФ.

·-этапныйй алгоритм БПФ.
Эффективность алгоритма БПФ.
Формирование начальных условий в алгоритме БПФ.
Вычисление ОДПФ с помощью БПФ.
13.1. БПФ Кули-Тьюки
В ДПФ (12.17):
13 EMBED Equation.3 1415, (12.17)
где
13 EMBED Equation.3 1415 , (12.19)
определим количество арифметических операций с комплексными числами:
при 13 EMBED Equation.3 1415
всего, при 13 EMBED Equation.DSMT4 1415
Порядок вычислительной сложности относительно длины последовательности N:
13 EMBED Equation.DSMT4 1415.
БПФ это

БПФ Кули-Тьюки (БПФ по основанию 2) длина исходной последовательности:
13 EMBED Equation.3 1415. (13.1)
Основная идея поэтапное вычисление ДПФ через ДПФ вдвое меньшей последовательности. Всего 13 EMBED Equation.DSMT4 1415 этапов.
13.3. Одноэтапный алгоритм БПФ
Разделим исходную N-точечную последовательность на две 13 EMBED Equation.3 1415-точечные (начальные условия одноэтапного алгоритма БПФ):
четных отсчетов;
нечетных отсчетов.
13 EMBED Visio.Drawing.11 1415
Рис. 13.1. Деление исходной последовательности
13 EMBED Visio.Drawing.11 1415
Рис. 13.2. Пример деления 8-точечной последовательности

После этого запишем ДПФ (12.17) в виде:
13 EMBED Equation.3 1415
где 13 EMBED Equation.DSMT4 1415 отображает четные, а 13 EMBED Equation.DSMT4 1415 нечетные значения 13 EMBED Equation.DSMT4 1415.
Вынесем 13 EMBED Equation.DSMT4 1415 за знак второй суммы:
13 EMBED Equation.3 1415 , (13.2)
представим 13 EMBED Equation.DSMT4 1415 в виде:
13 EMBED Equation.DSMT4 1415
и представим ДПФ (13.2) в виде:
13 EMBED Equation.3 1415, 13 EMBED Equation.DSMT4 1415,
и далее, с учетом обозначений сумм:
13 EMBED Equation.3 1415, 13 EMBED Equation.DSMT4 1415, (13.3)
где:
13 EMBED Equation.DSMT4 1415
13 EMBED Equation.DSMT4 1415
13 EMBED Equation.DSMT4 1415 и 13 EMBED Equation.DSMT4 1415
13 EMBED Equation.DSMT4 1415; (13.4)
13 EMBED Equation.DSMT4 1415. (13.5)
Вывод: при вычислении N-точечного ДПФ 13 EMBED Equation.DSMT4 1415 (13.3) 13 EMBED Equation.DSMT4 1415 и 13 EMBED Equation.DSMT4 1415 достаточно вычислить
Определим поворачивающей множитель на второй половине периода 13 EMBED Equation.DSMT4 1415:
13 EMBED Equation.DSMT4 1415    (13.6)
Вывод: при вычислении N-точечного ДПФ 13 EMBED Equation.DSMT4 1415 поворачивающий множитель 13 EMBED Equation.DSMT4 1415 достаточно вычислить
Вывод: N-точечное ДПФ 13 EMBED Equation.DSMT4 1415 (13.3) можно выразить через 13 EMBED Equation.3 1415-точечные ДПФ 13 EMBED Equation.DSMT4 1415 и 13 EMBED Equation.DSMT4 1415 (на рис. 13.4 это последний,13 EMBED Equation.DSMT4 1415-й этап):
13 EMBED Equation.3 1415 (13.7)
Согласно (13.7), N-точечное ДПФ 13 EMBED Equation.DSMT4 1415 одновременно вычисляются:
13 EMBED Equation.DSMT4 1415 13 EMBED Equation.DSMT4 1415 и 13 EMBED Equation.DSMT4 1415;
13 EMBED Equation.DSMT4 1415 13 EMBED Equation.DSMT4 1415 и 13 EMBED Equation.DSMT4 1415;
.
13 EMBED Equation.DSMT4 1415 13 EMBED Equation.DSMT4 1415 и 13 EMBED Equation.DSMT4 1415.
Размерность вычисляемого ДПФ соответствует нижнему индексу
Сокращение количества операций достигнуто за счет одновременного (параллельного) вычисления по верхней и нижней формулам!
Это оказалось возможным в результате
Одновременное вычисление по верхней и нижней формулам в (13.7) при фиксированном (одном) 13 EMBED Equation.DSMT4 1415 называют операцией «бабочка» коротко «бабочкой» и изображают в виде сигнального графа (рис. 13.3).
13 EMBED Visio.Drawing.5 1415
Рис. 13.3. Сигнальный граф операции «бабочка»
Для вычисления N-точечного по формуле (13.7) потребуется «бабочек».

13 EMBED Visio.Drawing.11 1415
Рис. 13.4. Поэтапное вычисление N-точечного ДПФ
13.5. Двухэтапный алгоритм БПФ
Продолжим процесс разделения исходной последовательности (на рис. 13.113.2 это второй этап): каждую из 13 EMBED Equation.3 1415-точечных последовательностей разделим на две 13 EMBED Equation.3 1415-точечные последовательности (начальные условия двухэтапного алгоритма БПФ):
четных отсчетов (в порядке следования, считая от нуля);
нечетных отсчетов (в порядке следования, считая от нуля).
В этом случае формула (13.7) может быть использована для вычисления двух 13 EMBED Equation.3 1415-точечных ДПФ 13 EMBED Equation.DSMT
·4 1415 и 13 EMBED Equation.DSMT4 1415, каждая через 13 EMBED Equation.3 1415-точечные ДПФ (на рис. 13.4 это предпоследний,13 EMBED Equation.DSMT4 1415-й этап):
13 EMBED Equation.3 1415 (13.8)
13 EMBED Equation.3 1415 (13.9)
Т. о., количество формул, подобных (13.7), , а размерность вычисляемого ДПФ в каждой из них
Размерность вычисляемого ДПФ соответствует нижнему индексу
Для вычисления ДПФ 13 EMBED Equation.DSMT4 1415 и 13 EMBED Equation.DSMT4 1415 потребуется «бабочек».
Значения 13 EMBED Equation.3 1415-точечных ДПФ 13 EMBED Equation.DSMT4 1415 и 13 EMBED Equation.DSMT4 1415 далее используются для вычисления N-точечного ДПФ 13 EMBED Equation.DSMT4 1415 по формуле (13. ) (на рис. 13.4 это последний,13 EMBED Equation.DSMT4 1415-й этап).
13.6.
·-этапныйй алгоритм БПФ
Продолжим процесс разделения исходной последовательности (сохраняя принцип чет и нечет) до тех пор, пока не будет получено групп, каждая из которых содержит , один из которых , а второй
Это начальные условия 13 EMBED Equation.DSMT4 1415-этапного алгоритма БПФ (на рис. 13.113.2 это последний 13 EMBED Equation.DSMT4 1415-й этап).
В этом случае формула (13.7) может быть использована для вычисления -точечных ДПФ, каждая через (на рис. 13.4 это первый этап).
Т. о., количество формул, подобных (13.7), будет равно , а размерность ДПФ каждой из них равна
Запишем одну из этих формул, используя условные обозначения 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415 четный и нечетный отсчеты, а 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415 отсчеты 2-точечного ДПФ:
13 EMBED Equation.3 1415 (13.10)
Для вычисления 2-точечных ДПФ потребуется «бабочек».
Дальнейшие этапы представлены на рис. 13.113.2 (снизу вверх).
На последнем 13 EMBED Equation.DSMT4 1415-м этапе будет вычислено N-точечное ДПФ 13 EMBED Equation.DSMT4 1415.
На каждом их этапов выполняется «бабочек».
Сигнальный граф алгоритма 8-точечного БПФ представлен на рис. 13.5.
13 EMBED Visio.Drawing.11 1415
Рис. 13.3. Сигнальный граф 8-точечного БПФ

13.7. Эффективность алгоритма БПФ
Определим количество арифметических операций с комплексными числами в БПФ:
количество этапов
количество бабочек на одном этапе
количество арифметических операций с комплексными числами для одной бабочки:
13 EMBED Equation.DSMT4 1415
ИТОГО операций.
Порядок вычислительной сложности относительно длины последовательности N:
13 EMBED Equation.DSMT4 1415.
Определить выигрыш в количестве операции по сравнению с ДПФ для 13 EMBED Equation.DSMT4 1415 1024.
13.8. Формирование начальных условий в алгоритме БПФ
Формирование начальных условий в заключается в расстановке отсчетов исходной последовательности в 13 EMBED Equation.DSMT4 1415-этапном алгоритме БПФ прореживании последовательности.
Рассмотрим на примере 8-точечного БПФ (рис. 13.2) и результаты обобщим.
Исходная последовательность
Прореженная последовательность для БПФ

Отсчеты


Отсчеты

13 EMBED Equation.3 1415


13 EMBED Equation.3 1415

13 EMBED Equation.3 1415


13 EMBED Equation.3 1415

13 EMBED Equation.3 1415


13 EMBED Equation.3 1415

13 EMBED Equation.3 1415


13 EMBED Equation.3 1415

13 EMBED Equation.3 1415


13 EMBED Equation.3 1415

13 EMBED Equation.3 1415


13 EMBED Equation.3 1415

13 EMBED Equation.3 1415


13 EMBED Equation.3 1415

13 EMBED Equation.3 1415


13 EMBED Equation.3 1415


Вывод: Для алгоритма БПФ отсчеты исходной последовательности должны быть расставлены

13.9. Вычисление ОДПФ с помощью БПФ
ОДПФ (12.18):
13 EMBED Equation.3 1415. (12.18)
Вычисляется следующим образом:
обе части равенства умножаются на 13 EMBED Equation.3 1415 и выполняется операция их комплексного сопряжения (символ *):
13 EMBED Equation.3 1415;
правая часть равенства N-точечное ДПФ последовательности 13 EMBED Equation.DSMT4 1415 вычисляется с помощью БПФ;
выполняется операция комплексного сопряжения обеих частей полученного равенства и они делятся на 13 EMBED Equation.3 1415:
13 EMBED Equation.3 1415.








13PAGE 15


13PAGE 14815




Root EntrypEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeMT EXTRA
·
·@
MT ExtraTIMES NEW ROMAN
Times New RomanMT ExtraTIMES NEW ROMAN
Times New RomanMT ExtTIMES NEW ROMAN
Times New RomanTimes New RomanTIMES NEW ROMAN
Times New RomanTimes New RomanTimes 15w RomanTIMES NEW ROMAN
Times New RomanTimes New RomanTimes 15w RomanTIMES NEW ROMAN
Times New RomanTimes New RomanTimes 15w RomanTIMES NEW ROMAN
Times New RomanTimes New RomanTimes 15w RomanTIMES NEW ROMAN
Times New RomanTimes New RomanTimes 15w RomanTIMES NEW ROMAN
Times New RomanTimes New RomanTimes 15w RomanTIMES NEW ROMAN
Times New RomanTimes New RomanTimes 15w RomanTIMES NEW ROMAN
Times New RomanTimes New RomanTimes 15w RomanTIMES NEW ROMAN
Times New RomanTimes New RomanTimes 15w RomanTIMES NEW ROMAN
Times New RomanTimes New RomanTimes 15w RomanTIMES NEW ROMAN
Times New RomanTimes New RomanTimes 15w RomanДеление последовательности
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·Times New RomanTimes 15w RomanДеление последовательности Times 15w RomanTIMES NEW ROMAN
Times New RomanTIMES NEW ROMAN
Times New RomanTimes New RomanTIMES NEW ROMAN
Times New RomanTimes New RomanTimes 15w RomanTIMES NEW ROMAN
Times New RomanTimes New RomanTimes 15w RomanTIMES NEW ROMAN
Times New RomanTimes New RomanTimes 15w RomanTIMES NEW ROMAN
Times New RomanTimes New RomanTimes 15w RomanTIMES NEW ROMAN
Times New RomanTimes New RomanTimes 15w RomanTimes New RomanTimes 15w RomanTimes 15w RomanTIMES NEW ROMAN
Times New RomanTIMES NEW ROMAN
Times New RomanTimes New Roman 
·
·
·
·
·я
·Н
·
·
·
·!Ђ
·
·
·
·
·
·3
·T Ex
·
·
·
·
·
·
·
·TIMES NEW ROMAN
Times New RomanTimes New RomanДеление точечной Times 15w Roman) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) TIMES NEW ROMAN
Times New RomanTimes New RomanTimes 15w Roman 
·
·
·
·
·я
·Н
·
·
·
·!Ђ
·
·
·
·
·
·3
·Equation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativekEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation Native 
·
·
·
·
·я
·Н
·
·
·
·!Ђ
·
·
·
·
·
·3
·MT EXTRA
·
·@
MT ExtraMT ExtraPазмерность
MT ExtTIMES NEW ROMAN
Times New RomanTimes New RomanMT EXTRA
·
·@
MT ExtraTimes 15w RomanНачальные условия
·
·
·
·
·
·
·
·
·
·
·
·Ђ
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·MT ExtraНачальные условияTimes New RomanTimes New RomanTimes New RomanTimes New RomanTimes New RomanTimes New RomanTimes New RomanTimes New RomanTimes New RomanTimes New RomanTimes New RomanTimes New RomanTimes New RomanTimes New RomanTimes New RomanTimes New RomanTimes New RomanTimes New RomanTimes New RomanTimes New RomanTimes New RomanTimes New RomanTimes New RomanTimes New RomanTimes New RomanTimes New RomanTimes New RomanTimes New RomanTimes New RomanTimes New RomanTimes New RomanTimes New RomanTimes New RomanTimes New RomanTimes New RomanTimes New RomanTimes New RomanTimes New RomanTimes New RomanTimes New RomanTimes New RomanTimes New RomanTimes New RomanTimes New RomanTimes New RomanTimes New Roman 
·
·
·
·
·я
·Н
·
·
·
·!Ђ
·
·
·
·
·
·3
·ые у
·
·ови
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·'
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·>
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·љ
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·ю
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·С
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·џ
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·tE
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·t
·
·
·
·
·
·
·
·m
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·Џ
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·Я
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·я
·
·
·
·
·
·
·
·
·
·бБ
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·A
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·4
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·Р
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

Приложенные файлы

  • doc 18814211
    Размер файла: 965 kB Загрузок: 0

Добавить комментарий