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.
БПФ – это

13.2. БПФ Кули-Тьюки
В алгоритме БПФ Кули-Тьюки длина последовательности должна быть равна:
13 EMBED Equation.3 1415. (13.1)
(Другое название – алгоритмом БПФ по основанию 2).
Имеется две версии алгоритма БПФ:
с прореживанием по времени;
с прореживанием по частоте.
По умолчанию под «БПФ» будем подразумевать алгоритм БПФ с прореживанием по времени.
Основная идея БПФ Кули-Тьюки – вычисление ДПФ через ДПФ вдвое меньшей последовательности за 13 EMBED Equation.DSMT4 1415 этапов.
13.3. Одноэтапный алгоритм БПФ
Начальные условия алгоритма (рис. 13.1–13.2).
Исходная N-точечная последовательность делится на две равные части:
13 EMBED Equation.3 1415 четных отсчетов (в порядке следования, считая от нуля);
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 141513 EMBED Equation.DSMT4 1415, (13.2)
где 13 EMBED Equation.DSMT4 1415 отображает четные, а 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
и перепишем (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)
Из этого следует, что 13 EMBED Equation.DSMT4 1415 и 13 EMBED Equation.DSMT4 1415 достаточно вычислить


Определим 13 EMBED Equation.DSMT4 1415:
13 EMBED Equation.DSMT4 1415    (13.6)
Из этого следует, что 13 EMBED Equation.DSMT4 1415 и 13 EMBED Equation.DSMT4 1415 достаточно вычислить

Что из этого следует, что 13 EMBED Equation.DSMT4 1415 достаточно вычислить

С учетом этого, вычисление ДПФ 13 EMBED Equation.DSMT4 1415на периоде N можно выполнять параллельно (одновременно) на первой половине периода и второй (верхняя и нижняя формулы):
13 EMBED Equation.3 1415 (13.7)
Формула (13.7) описывает алгоритм вычисления ДПФ через ДПФ вдвое меньшей размерности!

На рис. 13.3 это соответствует периоду.
Нижний индекс поворачивающего множителя совпадает с размерностью...

Сокращение количества операций достигнуто за счет

Это получено в результате

13 EMBED Visio.Drawing.11 1415
Рис. 13.3. Вычисление N-точечного ДПФ
13.4. Операция «бабочка»
Одновременное вычисление по верхней и нижней формулам (13.7) при фиксированном k называют операцией «бабочка» или коротко «бабочкой» (рис. 13.4).
13 EMBED Visio.Drawing.5 1415
Рис. 13.4. Сигнальный граф операции «бабочка»
Для вычисления N-точечного по формуле (13.7) потребуется «бабочек».
13.5. Двухэтапный алгоритм БПФ
Формирование начальных условий: каждая из двух 13 EMBED Equation.3 1415-точечных последовательностей делится на две части – чет и нечет (см. рис.13.1–13.2).
Первый этап (см. рис. 13.3):
Вычисляются 13 EMBED Equation.3 1415-точечные ДПФ 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
Для вычисления каждой ДПФ 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.3 1415 (13.8)
13 EMBED Equation.3 1415 (13.9)
Для вычислений на первом этапе потребуется «бабочек»:

Второй этап (см. рис. 13.3) – N-точечное ДПФ 13 EMBED Equation.DSMT4 1415 вычисляется по формуле ( ).
Самостоятельно поясните действия в трехэтапном алгоритме БПФ:
начальные условия:

первый этап:


второй этап:


третий этап:


13.6.
·-этапныйй алгоритм БПФ
Начальные условия:
Процесс деления исходной последовательности продолжается до тех пор, пока не будет получено -точечных последовательностей, в которой один отсчет 13 EMBED Equation.3 1415 – , а второй 13 EMBED Equation.3 1415– (см. рис.13.1–13.2).
Первый этап (см. рис. 13.3):
Вычисляется 13 EMBED Equation.3 1415 2-точечных ДПФ, каждое из них непосредственно по 2-точечной последовательности.
Для этого потребуется формул типа ( ), в каждой из которых 13 EMBED Equation.DSMT4 1415
Одна из формул имеет общий вид (подставьте конкретные значения 13 EMBED Equation.DSMT4 1415 и 13 EMBED Equation.DSMT4 1415):
13 EMBED Equation.3 1415
Окончательно:
13 EMBED Equation.3 1415 (13.10)
Для вычислений на первом этапе потребуется «бабочек».
На втором этапе вычисляется

На третьем этапе вычисляется

На предпоследнем этапе вычисляется

На последнем этапе (
·-м) вычисляется
13.7. Эффективность БПФ Кули-Тьки
Определим количество арифметических операций с комплексными числами в БПФ:
количество этапов –
на каждом этапе выполняется бабочек –
для каждой бабочки требуется:
13 EMBED Equation.DSMT4 1415
ИТОГО – операций.
Порядок вычислительной сложности относительно длины N:
13 EMBED Equation.DSMT4 1415.
Самостоятельно определить выигрыш в количестве операции в БПФ по сравнению с ДПФ (12.17) при 13 EMBED Equation.DSMT4 1415 1024.
13.8. Расстановка отсчетов исходной последовательности
Рассмотреть на примере 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.3 1415:
13 EMBED Equation.3 1415.








13PAGE 15


13PAGE 14915




Root EntrypEquation NativeEquation 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 NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeMT 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 18814248
    Размер файла: 631 kB Загрузок: 0

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