Быстрое преобразование Фурье (БПФ) и дискретное преобразование Фурье (ДПФ). Дискретное преобразование Фурье (ДПФ)
Технологии и наука идут рука об руку. И нет лучшего примера этому, чем цифровая обработка сигналов (ЦОС). Цифровая обработка сигналов — это процесс оптимизации точности и эффективности цифровых коммуникаций. Все есть данные — будь то изображения с космических зондов или сейсмические колебания и все, что между ними. Преобразование этих данных в человекочитаемый формат с помощью компьютеров — это и есть цифровая обработка сигналов. Это одна из самых мощных технологий, которая сочетает в себе как математическую теорию, так и физическую реализацию. Изучение ЦОС началось с курса электротехники для аспирантов, но со временем она стала потенциальным игроком в области науки и техники. Достаточно сказать, что без ЦОС инженеры и ученые могли бы перестать существовать.
Преобразование Фурье — это способ преобразования сигнала во временной или пространственной области в его спектр в частотной области. Временная и частотная области — это просто альтернативные способы представления сигналов, а преобразование Фурье — это математическая связь между этими двумя представлениями. Изменение сигнала в одной области также повлияет на сигнал в другой области, но не обязательно одинаковым образом. Дискретное преобразование Фурье (ДПФ) — это преобразование, подобное преобразованию Фурье, используемое с оцифрованными сигналами. Как следует из названия, это дискретная версия ДПФ, которая рассматривает и временную, и частотную области как периодические. Быстрое преобразование Фурье (БПФ) — это просто алгоритм для быстрого и эффективного вычисления ДПФ.
Дискретное преобразование Фурье (ДПФ)
Дискретное преобразование Фурье (ДПФ) — один из важнейших инструментов в цифровой обработке сигналов, который вычисляет спектр сигнала конечной длительности. Очень часто информация кодируется в синусоидах, образующих сигнал. Однако в некоторых приложениях форма сигнала во временной области не является прикладной для сигналов, и в этом случае частотное содержание сигнала становится очень полезным не только в виде цифровых сигналов. Представление цифрового сигнала в терминах его частотной составляющей в частотной области является важным. Алгоритм, который преобразует сигналы временной области в компоненты частотной области, известен как дискретное преобразование Фурье, или ДПФ.
Быстрое преобразование Фурье (БПФ)
Быстрое преобразование Фурье (БПФ) — это реализация ДПФ, которая дает почти те же результаты, что и ДПФ, но она невероятно эффективнее и намного быстрее, что часто значительно сокращает время вычислений. Это просто вычислительный алгоритм, используемый для быстрого и эффективного вычисления ДПФ. Различные методы быстрого вычисления ДПФ известны под общим названием быстрого преобразования Фурье, или БПФ. Гаусс был первым, кто предложил эту технику для вычисления коэффициентов в тригонометрии орбиты астероида в 1805 году. Однако только в 1965 году внимание научной и инженерной общественности привлекла фундаментальная статья Кули и Тьюки, которая также заложила основу дисциплины цифровой обработки сигналов.
Разница между БПФ и ДПФ
Значение БПФ и ДПФ
Дискретное преобразование Фурье, или просто ДПФ, — это алгоритм, который преобразует сигналы временной области в компоненты частотной области. ДПФ, как следует из названия, действительно дискретно; дискретные наборы данных временной области преобразуются в дискретное частотное представление. Проще говоря, оно устанавливает связь между представлением временной области и представлением частотной области. Быстрое преобразование Фурье, или БПФ, — это вычислительный алгоритм, который сокращает время вычислений и сложность больших преобразований. БПФ — это просто алгоритм, используемый для быстрого вычисления ДПФ.
Алгоритм БПФ и ДПФ
Наиболее часто используемым алгоритмом БПФ является алгоритм Кули-Тьюки, который был назван в честь Дж.В. Кули и Джона Тьюки. Это алгоритм «разделяй и властвуй» для машинного вычисления комплексных рядов Фурье. Он разбивает ДПФ на более мелкие ДПФ. Другие алгоритмы ДПФ включают алгоритм Радера, алгоритм преобразования Фурье Винограда, алгоритм Z-трансформации Чирпа и т.д. Алгоритмы ДПФ могут быть либо запрограммированы на цифровых компьютерах общего назначения, либо реализованы непосредственно на специальном оборудовании. Алгоритм ДПФ используется для вычисления ДПФ последовательности или ее обратной величины. ДПФ может быть выполнено как O(N2) по временной сложности, тогда как БПФ уменьшает временную сложность на порядок O (NlogN).
Применение БПФ и ДПФ
ДПФ может использоваться во многих системах цифровой обработки в различных приложениях, таких как вычисление частотного спектра сигнала, решение частных дифференциальных задач, обнаружение целей по эхосигналу радара, корреляционный анализ, вычисление полиномиального умножения, спектральный анализ и многое другое. БПФ широко используется для акустических измерений в церквях и концертных залах. Другие применения БПФ включают спектральный анализ в аналоговых видео измерениях, умножение больших целых чисел и полиномов, алгоритмы фильтрации, вычисление изотопных распределений, вычисление коэффициентов ряда Фурье, вычисление сверток, генерирование низкочастотного шума, проектирование киноформ, выполнение плотных структурированных матриц, обработка изображений и многое другое.
Резюме БПФ vs. DFT
В двух словах, дискретное преобразование Фурье играет ключевую роль в физике, поскольку оно может быть использовано как математический инструмент для описания взаимосвязи между представлением дискретных сигналов во временной и частотной областях. Это простой, но достаточно трудоемкий алгоритм. Однако для сокращения времени вычислений и сложности больших преобразований можно использовать более сложный, но менее трудоемкий алгоритм, такой как быстрое преобразование Фурье. БПФ — это реализация ДПФ, используемая для быстрого вычисления ДПФ. Короче говоря, БПФ может делать все, что делает ДПФ, но более эффективно и намного быстрее, чем ДПФ. Это эффективный способ вычисления ДПФ.