доклад по специальному семенару. Специальный семинар доклад. "Вычисление дпф любой длины"
![]()
|
![]() ФЕДЕРАЛЬНОЕ АГЕНСТВО МОРСКОГО И РЕЧНОГО ТРАНСПОРТА Федеральное государственное бюджетное образовательное учреждение высшего образования “Государственный университет морского и речного флота имени адмирала С.О. Макарова” ![]() Институт водного транспорта Кафедра прикладной математики РЕФЕРАТ по дисциплине: Специальный семинар На тему “Вычисление ДПФ любой длины” Выполнил: Студент гр. ИП-31, Устюжанина Н.Н. ________________ (подпись) Проверил: Доцент кафедры ПМ, д.т.н., Васин А.В. _________________ (оценка, подпись) Санкт-Петербург 2022 г. Дискретное преобразование Фурье (ДПФ) – это отображение ![]() ![]() ![]() ![]() Определение 1. Сигнал ![]() ![]() ![]() Определение 2. Быстрое преобразование Фурье (БПФ) представляет собой алгоритм, который вычисляет дискретное преобразование Фурье (ДПФ) последовательности, или его обратного. Одним из вариантов быстрого преобразования Фурье является алгоритм Кули-Тьюки с прореживанием по времени. Алгоритм чтобы быстро вычисляет ДПФ длины, равной степени двойки. Рассмотрим этот алгоритм. В пространстве ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Для определения коэффициентов ![]() ![]() Теорема 1. (устанавливает, что система сигналов (2) образует ортогональный базис в пространстве ![]() При каждом ![]() ![]() ортогональна и ![]() ![]() Согласно этой теореме получаем ![]() ![]() В частности: ![]() Домножая равенства скалярно на ![]() ![]() Аналогично ![]() Таким образом переходим к рекуррентной схеме: ![]() ![]() ![]() ![]() По этой схеме вычисляются коэффициенты разложения сигнала ![]() ![]() ![]() ![]() Таким образом, коэффициенты ![]() ![]() Вычисления по формулам (4) требуют: умножений: ![]() сложений: ![]() Схема (4) является одним из вариантов быстрого преобразования Фурье при ![]() Формулы (4) допускают обращение: ![]() ![]() ![]() ![]() По формулам (5) спустимся до ![]() ![]() ![]() ![]() Тем самым указан быстрый алгоритм восстановления сигнала ![]() ![]() ![]() Однако, довольно часто на практике оказывается, что это достаточно неудобное ограничение. Ниже покажем, что вычисление ДПФ любой длины ![]() ![]() Замечание 1. Вычисление спектра ![]() ![]() в ![]() ![]() на вектор ![]() Как было показано в замечании 1, ДПФ сигнала, определяемое формулой ![]() ![]() ![]() ![]() Определение 3. Матрица ![]() Определение 4. Правоциркулянтная матрица – это квадратная матрица, каждая строка которой, начиная со второй, получается сдвигом предыдущей вправо на один элемент; тот элемент, что при этом сдвиге “выходит” за пределы матрицы, переставляется в начало строки. В ![]() ![]() и симметричную теплицеву матрицу ![]() Справедливо следующее равенство Лемма 1. ![]() Доказательство. Запишем очевидное равенство ![]() С другой стороны ![]() Введем обозначения ![]() ![]() ![]() З ![]() на вектор х. Вложим ![]() ![]() ![]() ![]() ![]() Нулей поставлено столько, чтобы длина строки равнялась M. из строки (7) с помощью циклических сдвигов вправо формируется квадратная матрица ![]() ![]() т ![]() По построению матрица ![]() ![]() ![]() ![]() где ![]() Из (6) и (8) получаем ![]() Введем следующие обозначения: ![]() Через ![]() ![]() ![]() ![]() В правой части равенства (10) по определению стоит циклическая свёртка ![]() Теорема 2 (о свертке). Пусть ![]() ![]() где справа стоит покомпонентное произведение спектров. По теореме 2 (о свёртке) имеем ![]() Заметим, что спектр ![]() ![]() Таким образом, приходим к следующему алгоритму вычисления спектра ![]() Шаг 1. Формируем вектор ![]() ![]() Шаг 2. Вычисляем ![]() Шаг 3. Вычисляем вектор ![]() ![]() Шаг 4. Вычисляем ![]() Шаг 5. Находим компоненты спектра ![]() ![]() Замечание 3. Самыми «плохими» для вышеприведенного алгоритма являются N вида ![]() ![]() Список используемой литературыУчебное пособие «Математические методы цифровой обработки сигналов», авторы Поздняков С.Н., Рыбин С.В. |