В математике , то дискретное преобразование Фурье ( ДПФ ) преобразует конечную последовательность одинаково отстоящих друг от друга образцов одного функции в последовательности же длины , одинаково разнесенных выборок с дискретным временем преобразования Фурье (ДВПФ), который представляет собой -комплекснозначная функция частоты. Интервал, с которым выполняется выборка DTFT, обратно пропорционален длительности входной последовательности. Обратное ДПФ - это ряд Фурье , использующий выборки ДВПФ в качестве коэффициентов комплексных синусоид на соответствующих частотах ДВПФ. Он имеет те же значения выборки, что и исходная входная последовательность. Следовательно, ДПФ называетсяпредставление исходной входной последовательности в частотной области . Если исходная последовательность охватывает все ненулевые значения функции, ее ДВПФ является непрерывным (и периодическим), а ДПФ обеспечивает дискретные выборки одного цикла. Если исходная последовательность представляет собой один цикл периодической функции, ДПФ предоставляет все ненулевые значения одного цикла ДВПФ.
ДПФ - наиболее важное дискретное преобразование , используемое для выполнения анализа Фурье во многих практических приложениях. [1] При цифровой обработке сигналов функция - это любая величина или сигнал, который изменяется во времени, например давление звуковой волны , радиосигнал или ежедневные показания температуры , дискретизированные за конечный интервал времени (часто определяемый окном функция [2] ). При обработке изображений выборками могут быть значения пикселей в строке или столбце растрового изображения . ДПФ также используется для эффективного решения уравнений в частных производных и для выполнения других операций, таких как свертки или умножение больших целых чисел.
Поскольку он имеет дело с ограниченным объемом данных, он может быть реализован в компьютерах с помощью числовых алгоритмов или даже специального оборудования . Эти реализации обычно используют эффективные алгоритмы быстрого преобразования Фурье (БПФ); [3] настолько, что термины «БПФ» и «ДПФ» часто используются как синонимы. До его текущего использования инициализм «БПФ» также мог использоваться для неоднозначного термина « конечное преобразование Фурье ».
Определение
Дискретного преобразования Фурье преобразует последовательность из N комплексных чисел в другую последовательность комплексных чисел, который определяется
( Уравнение 1 )
где последнее выражение следует из первого по формуле Эйлера .
Преобразование иногда обозначают символом , как в или же или же . [A]
Мотивация
Уравнение 1 также может быть оценено вне области, и эта расширенная последовательность - периодический . Соответственно, другие последовательности иногда используются индексы, например (если четный) и (если является нечетным), что означает перестановку левой и правой половин результата преобразования. [4]
Уравнение 1 можно интерпретировать или вывести по-разному, например:
- Он полностью описывает дискретное преобразование Фурье (ДВПФ)-периодическая последовательность, состоящая только из дискретных частотных составляющих. ( Использование DTFT с периодическими данными )
- Он также может обеспечивать равномерно разнесенные выборки непрерывного ДВПФ последовательности конечной длины. ( § Выборка DTFT )
- Это кросс - корреляция из входной последовательности,, и комплексная синусоида на частоте . Таким образом, он действует как согласованный фильтр для этой частоты.
- Это дискретный аналог формулы для коэффициентов ряда Фурье :
( Уравнение 2 )
что также -периодический. В области п ∈ [0, N - 1] , это обратное преобразование из Eq.1 . В этой интерпретации каждый - комплексное число, которое кодирует как амплитуду, так и фазу сложной синусоидальной составляющей. функции . Синусоиды по частоте является K циклов в N выборок. Его амплитуда и фаза:
Коэффициент нормализации, умножающий DFT и IDFT (здесь 1 и ) и знаки экспонентов являются просто условностями и различаются в некоторых вариантах обработки. Единственные требования этих соглашений состоят в том, чтобы ДПФ и IDFT имели экспоненты разного знака и чтобы произведение их коэффициентов нормализации было. Нормализациякак для ДПФ, так и для IDFT, например, делает преобразования унитарными. Дискретный импульс,при n = 0 и 0 в противном случае; может превратиться вдля всех k (используйте коэффициент нормализации 1 для ДПФ идля IDFT). Сигнал постоянного тока,при k = 0 и 0 в противном случае; может обратно преобразоваться в для всех (использовать для DFT и 1 для IDFT), что согласуется с рассмотрением DC как среднего среднего сигнала.
Пример
Позволять а также
Здесь мы демонстрируем, как вычислить ДПФ используя уравнение 1 :
Обратное преобразование
Дискретное преобразование Фурье - это обратимое линейное преобразование
с участием обозначающий набор комплексных чисел . Его обратное преобразование известно как обратное дискретное преобразование Фурье (IDFT). Другими словами, для любого, N- мерный комплексный вектор имеет ДПФ и ОДПФ, которые, в свою очередь,-мерные комплексные векторы.
Обратное преобразование дается выражением:
( Уравнение 3 )
Характеристики
Линейность
ДПФ является линейным преобразованием, т. Е. Если а также , то для любых комплексных чисел :
Реверс времени и частоты
Обратное время (т. Е. Замена от ) [B] в соответствует изменению частоты (т. е. от ). [5] : с.421 Математически, еслипредставляет вектор x, тогда
- если
- тогда
Спряжение во времени
Если тогда . [5] : с.423
Реальная и мнимая часть
В этой таблице показаны некоторые математические операции над во временной области и соответствующие эффекты на его ДПФ в частотной области.
Имущество | Область времени | Частотный диапазон |
---|---|---|
Реальная часть времени | ||
Воображаемая часть времени | ||
Реальная часть частоты | ||
Мнимая часть частоты |
Ортогональность
Векторы образуют ортогональный базис над множеством N -мерных комплексных векторов:
где - дельта Кронекера . (На последнем шаге суммирование тривиально, если, где это 1 + 1 + = N , в противном случае это геометрический ряд, который можно явно просуммировать для получения нуля.) Это условие ортогональности можно использовать для вывода формулы для IDFT из определения DFT, и эквивалентен свойству унитарности ниже.
Теорема Планшереля и теорема Парсеваля
Если а также являются ДПФ а также соответственно, то теорема Парсеваля гласит:
где звездочка означает комплексное сопряжение . Теорема Планшереля является частным случаем теоремы Парсеваля и гласит:
Эти теоремы также эквивалентны приведенному ниже условию унитарности.
Периодичность
Периодичность можно показать прямо из определения:
Точно так же можно показать, что формула IDFT приводит к периодическому расширению.
Теорема о сдвиге
Умножение с помощью линейной фазы для некоторого целого числа m соответствует циклическому сдвигу вывода: заменяется на , где нижний индекс интерпретируется по модулю N (т.е. периодически). Аналогично круговой сдвиг входа соответствует умножению выхода линейной фазой. Математически, еслипредставляет вектор x, тогда
- если
- тогда
- а также
Теорема круговой свертки и теорема взаимной корреляции
Теорема о свертке для дискретного преобразования Фурье (DTFT) указывает, что свертка двух последовательностей может быть получена как обратное преобразование продукта отдельных преобразований. Важное упрощение происходит, когда одна из последовательностей является N-периодической, обозначенной здесь как так как отличен от нуля только на дискретных частотах (см. DTFT § Периодические данные ), и, следовательно, его произведение с непрерывной функцией Это приводит к значительному упрощению обратного преобразования.
где является периодическим суммированием изпоследовательность :
Обычно суммирование ДПФ и обратного ДПФ выполняется по области . Определение этих ДПФ как а также , результат :
На практике последовательность обычно имеет длину N или меньше, и является периодическим продолжением N-длины -последовательность, которая также может быть выражена как круговая функция :
Тогда свертку можно записать как :
что приводит к интерпретации как круговой свертки а также [6] [7] Он часто используется для эффективного вычисления их линейной свертки. (см. Круговая свертка , Алгоритмы быстрой свертки и Сохранение с перекрытием )
Аналогичным образом , кросс-корреляции из а также дается :
Двойственность теоремы свертки
Также можно показать, что :
- что представляет собой круговую свертку а также .
Тригонометрический интерполяционный полином
Тригонометрический интерполяционный полином
где коэффициенты X k задаются ДПФ x n выше, удовлетворяет свойству интерполяции для .
Обратите внимание, что для четного N компонент Найквиста обрабатывается специально.
Эта интерполяция не уникальна : наложение спектров подразумевает, что можно добавить N к любой из частот комплексной синусоиды (например, изменяя к ) без изменения свойства интерполяции, но давая разные значения междуточки. Однако вышеприведенный выбор типичен, поскольку он обладает двумя полезными свойствами. Во-первых, он состоит из синусоид, частоты которых имеют минимально возможные значения: интерполяция ограничена полосой пропускания . Во-вторых, если являются действительными числами, тогда тоже реально.
Напротив, наиболее очевидным полиномом тригонометрической интерполяции является тот, в котором частоты находятся в диапазоне от 0 до (вместо примерно к как указано выше), аналогично обратной формуле ДПФ. Эта интерполяция не минимизирует наклон и, как правило, не имеет действительного значения для реальных; его использование - распространенная ошибка.
Унитарный ДПФ
Другой способ смотреть на ДПФ, следует отметить , что в приведенном выше обсуждении, ДПФ может быть выражена в виде матрицы ДПФ , в матрицу Вандермонда , введенной Сильвестра в 1867 году,
где является примитивным корнем N- й степени из единицы .
Обратное преобразование затем дается обратной матрицей вышеупомянутой:
С унитарными нормировочными константами, ДПФ становится унитарным преобразованием , определяемым унитарной матрицей:
где - детерминантная функция. Определитель - это произведение собственных значений, которые всегда равны или же как описано ниже. В реальном векторном пространстве унитарное преобразование можно рассматривать как просто жесткое вращение системы координат, и все свойства жесткого вращения можно найти в унитарном ДПФ.
Ортогональность ДПФ теперь выражается как условие ортонормированности (которое возникает во многих областях математики, как описано в корне из единицы ):
Если X определяется как унитарное ДПФ вектора x , то
а теорема Парсеваля выражается как
Если мы рассматриваем ДПФ как просто преобразование координат, которое просто задает компоненты вектора в новой системе координат, то приведенное выше является просто утверждением, что скалярное произведение двух векторов сохраняется при унитарном преобразовании ДПФ. Для особого случая, это означает, что длина вектора также сохраняется - это просто теорема Планшереля ,
Следствием теоремы о круговой свертке является то, что матрица ДПФ F диагонализует любую циркулянтную матрицу .
Выражение обратного ДПФ через ДПФ
Полезное свойство ДПФ состоит в том, что обратное ДПФ может быть легко выражено в терминах (прямого) ДПФ с помощью нескольких хорошо известных "уловок". (Например, в вычислениях часто бывает удобно реализовать только быстрое преобразование Фурье, соответствующее одному направлению преобразования, а затем получить другое направление преобразования из первого.)
Во-первых, мы можем вычислить обратное ДПФ, изменив все входные данные, кроме одного (Duhamel et al. , 1988):
(Как обычно, индексы интерпретируются по модулю N ; таким образом, для, у нас есть .)
Во-вторых, можно также сопрягать входы и выходы:
В-третьих, вариант этого трюка сопряжения, который иногда предпочтительнее, поскольку он не требует модификации значений данных, включает в себя замену реальной и мнимой частей (что может быть выполнено на компьютере просто путем изменения указателей ). Определять в виде поменяв местами его реальную и мнимую части - то есть, если тогда является . Эквивалентно, равно . потом
То есть обратное преобразование такое же, как прямое преобразование с реальной и мнимой частями, замененными как для ввода, так и для вывода, с точностью до нормализации (Duhamel et al. , 1988).
Уловку сопряжения можно также использовать для определения нового преобразования, тесно связанного с ДПФ, которое является инволютивным, то есть являющимся его собственным обратным. В частности, явно обратный: . Близкое инволютивное преобразование (в (1 + i ) / √ 2 раз ) - это, поскольку факторы в отменить 2. Для реальных входов , реальная часть есть не что иное, как дискретное преобразование Хартли , которое также является инволютивным.
Собственные значения и собственные векторы
Собственные значения матрицы ДПФ просты и хорошо известны, в то время как собственные векторы сложны, а не уникальны и являются предметом постоянных исследований.
Рассмотрим унитарную форму определенное выше для ДПФ длины N , где
Эта матрица удовлетворяет матричному полиномиальному уравнению:
Это видно из обратных свойств выше: работа дважды дает исходные данные в обратном порядке, поэтому четыре раза возвращает исходные данные и, таким образом, является единичной матрицей . Это означает, что собственные значения удовлетворяют уравнению:
Следовательно, собственные значения четвертые корни единства :равно +1, −1, + i или - i .
Поскольку для этого есть только четыре различных собственных значения матрица, они имеют некоторую кратность . Кратность дает количество линейно независимых собственных векторов, соответствующих каждому собственному значению. (Существует N независимых собственных векторов; унитарная матрица никогда не бывает дефектной .)
Проблема их множественности была решена Макклелланом и Парксом (1972), хотя позже было показано, что она эквивалентна проблеме, решенной Гауссом (Дикинсон и Стейглиц, 1982). Кратность зависит от значения N по модулю 4 и приводится в следующей таблице:
размер N | λ = +1 | λ = −1 | λ = - я | λ = + я |
---|---|---|---|---|
4 мес. | м + 1 | м | м | м - 1 |
4 м + 1 | м + 1 | м | м | м |
4 м + 2 | м + 1 | м + 1 | м | м |
4 м + 3 | м + 1 | м + 1 | м + 1 | м |
Иначе говоря, то характеристический многочлен из является:
Простая аналитическая формула для общих собственных векторов неизвестна. Более того, собственные векторы не уникальны, потому что любая линейная комбинация собственных векторов для одного и того же собственного значения также является собственным вектором для этого собственного значения. Различные исследователи предлагали различные варианты собственных векторов, выбранных для удовлетворения таких полезных свойств, как ортогональность, и наличия «простых» форм (например, McClellan and Parks, 1972; Dickinson and Steiglitz, 1982; Grünbaum, 1982; Atakishiyev and Wolf, 1997; Candan et al. др. , 2000; Hanna et al. , 2004; Гуревич, Хадани, 2008).
Прямой подход заключается в дискретизации собственной функции непрерывного преобразования Фурье , наиболее известной из которых является функция Гаусса . Поскольку периодическое суммирование функции означает дискретизацию ее частотного спектра, а дискретизация означает периодическое суммирование спектра, дискретизированная и периодически суммируемая функция Гаусса дает собственный вектор дискретного преобразования:
Выражение замкнутой формы для ряда может быть выражено тета-функциями Якоби как
Были найдены два других простых аналитических собственных вектора в замкнутой форме для специального периода N ДПФ (Kong, 2008):
Для периода ДПФ N = 2 L + 1 = 4 K + 1, где K - целое число, следующий собственный вектор ДПФ:
Для периода ДПФ N = 2 L = 4 K , где K - целое число, следующий собственный вектор ДПФ:
Выбор собственных векторов матрицы ДПФ стал важным в последние годы для определения дискретного аналога дробного преобразования Фурье - матрицу ДПФ можно преобразовать в дробные степени, возведя в степень собственные значения (например, Rubio and Santhanam, 2005). Для непрерывного преобразования Фурье естественными ортогональными собственными функциями являются функции Эрмита , поэтому в качестве собственных векторов ДПФ использовались их различные дискретные аналоги, такие как полиномы Кравчука (Атакишиев и Вольф, 1997). Однако «лучший» выбор собственных векторов для определения дробного дискретного преобразования Фурье остается открытым вопросом.
Принципы неопределенности
Принцип вероятностной неопределенности
Если случайная величина X k ограничена
тогда
может быть рассмотрен для представления дискретной функции вероятности массовой из п , с соответствующей функцией вероятности массовой построенной из трансформированных переменных,
В случае непрерывных функций а также , принцип неопределенности Гейзенберга утверждает, что
где а также различия а также соответственно, с равенством, достигаемым в случае подходящим образом нормированного гауссова распределения . Хотя дисперсии могут быть определены аналогично для ДПФ, аналогичный принцип неопределенности бесполезен, потому что неопределенность не будет инвариантной к сдвигу. Тем не менее, Массар и Спиндель ввели осмысленный принцип неопределенности. [8]
Однако энтропийная неопределенность Хиршмана будет иметь полезный аналог для случая ДПФ. [9] Принцип неопределенности Хиршмана выражается через энтропию Шеннона двух функций вероятности.
В дискретном случае энтропии Шеннона определяются как
а также
и принцип энтропийной неопределенности становится [9]
Равенство получается при равны сдвигам и модуляциям соответственно нормализованной гребенки Кронекера периода где любой точный целочисленный делитель . Функция массы вероятноститогда будет пропорционально правильно переведенной гребенке Кронекера периода. [9]
Принцип детерминированной неопределенности
Существует также хорошо известный принцип детерминированной неопределенности, который использует разреженность сигнала (или количество ненулевых коэффициентов). [10] Пусть а также быть количеством ненулевых элементов временной и частотной последовательностей а также , соответственно. Потом,
Как непосредственное следствие неравенства средних арифметических и геометрических , мы также имеем. Было показано, что оба принципа неопределенности являются строгими для специально выбранных последовательностей «пикет-забор» (дискретные импульсные последовательности) и находят практическое применение для приложений восстановления сигнала. [10]
ДПФ реальных и чисто мнимых сигналов
- Если являются действительными числами , как это часто бывает в практических приложениях, то ДПФэто даже симметрично :
- , где обозначает комплексное сопряжение .
Отсюда следует, что для даже а также являются действительными, а остальная часть ДПФ полностью определяется просто комплексные числа.
- Если являются чисто мнимыми числами, то ДПФ является нечетным симметричным :
- , где обозначает комплексное сопряжение .
Обобщенное ДПФ (сдвинутая и нелинейная фаза)
Можно сдвинуть дискретизацию преобразования во временной и / или частотной области на некоторые реальные сдвиги a и b , соответственно. Это иногда называют обобщенным ДПФ (или GDFT ), также называемым ДПФ со сдвигом или ДПФ со смещением , и имеет свойства, аналогичные обычному ДПФ:
Чаще всего смены (половина выборки). В то время как обычное ДПФ соответствует периодическому сигналу как во временной, так и в частотной областях, производит сигнал, который является антипериодическим в частотной области () и наоборот для . Таким образом, частный случайизвестно как дискретное преобразование Фурье с нечетной частотой и нечетной частотой (или O 2 DFT). Такие сдвинутые преобразования чаще всего используются для симметричных данных, чтобы представить различные граничные симметрии, а для реально-симметричных данных они соответствуют различным формам дискретных косинусных и синусоидальных преобразований.
Еще один интересный выбор , который называется центрированным ДПФ (или CDFT ). Центрированное ДПФ обладает тем полезным свойством, что, когда N кратно четырем, все четыре его собственных значения (см. Выше) имеют равную кратность (Rubio and Santhanam, 2005) [11]
Термин GDFT также используется для нелинейных фазовых расширений DFT. Следовательно, метод GDFT обеспечивает обобщение для ортогональных блочных преобразований с постоянной амплитудой, включая линейные и нелинейные типы фазы. GDFT - это основа для улучшения свойств традиционного DFT во временной и частотной областях, например авто / кросс-корреляции, путем добавления правильно спроектированной функции формирования фазы (нелинейной в целом) к исходным линейным функциям фазы (Akansu и Агирман-Тосун, 2010). [12]
Дискретное преобразование Фурье можно рассматривать как частный случай z-преобразования , вычисляемого на единичной окружности в комплексной плоскости; более общие z-преобразования соответствуют сложным сдвигам a и b выше.
Многомерное ДПФ
Обычное ДПФ преобразует одномерную последовательность или массив это функция ровно одной дискретной переменной n . Многомерное ДПФ многомерного массиваэто функция d дискретных переменных для в определяется:
где как указано выше, а выходные индексы d начинаются с. Более компактно это выражается в векторных обозначениях, где мы определяем а также как d -мерные векторы индексов от 0 до, который мы определяем как :
где разделение определяется как выполняется поэлементно, а сумма обозначает набор вложенных суммирований выше.
Обратное к многомерному ДПФ аналогично одномерному случаю определяется выражением:
Поскольку одномерный ДПФ выражает ввод как суперпозиция синусоид многомерное ДПФ выражает входные данные как суперпозицию плоских волн или многомерных синусоид. Направление колебаний в пространстве. Амплитуды. Это разложение имеет большое значение для всего, от обработки цифровых изображений (двумерных) до решения уравнений в частных производных . Решение разбивается на плоские волны.
Многомерное ДПФ может быть вычислено путем композиции последовательности одномерных ДПФ по каждому измерению. В двумерном случае в независимых ДПФ строк (т. е. вдоль ) сначала вычисляются для формирования нового массива . Тогданезависимые ДПФ y вдоль столбцов (вдоль) вычисляются для формирования окончательного результата . В качестве альтернативы можно сначала вычислить столбцы, а затем строки. Порядок несущественен, потому что вложенные суммирования выше коммутируют .
Таким образом, алгоритма вычисления одномерного ДПФ достаточно для эффективного вычисления многомерного ДПФ. Этот подход известен как алгоритм " строка-столбец" . Существуют также по сути многомерные алгоритмы БПФ .
Многомерное ДПФ с реальным входом
Для исходных данных состоящие из действительных чисел , выходы ДПФ имеют сопряженную симметрию, аналогичную одномерному случаю, приведенному выше:
где звездочка снова обозначает комплексное сопряжение, а -й индекс снова интерпретируется по модулю (для ).
Приложения
ДПФ широко используется в большом количестве полей; мы только набросаем несколько примеров ниже (см. также ссылки в конце). Все приложения ДПФ в решающей степени зависят от наличия быстрого алгоритма для вычисления дискретных преобразований Фурье и их обратных, быстрого преобразования Фурье .
Спектральный анализ
Когда ДПФ используется для спектрального анализа сигнала , Последовательность обычно представляет собой конечный набор равномерно распределенных временных отсчетов некоторого сигнала. , где представляет время. Переход от непрерывного времени к образцам ( с дискретным временем) меняет лежащий в основе преобразования Фурье изв дискретное преобразование Фурье (DTFT), которое обычно влечет за собой тип искажения, называемый наложением спектров . Выбор подходящей частоты дискретизации (см. Частота Найквиста ) является ключом к минимизации этого искажения. Точно так же преобразование очень длинной (или бесконечной) последовательности в управляемый размер влечет за собой тип искажения, называемый утечкой , который проявляется в виде потери деталей (или разрешения) в DTFT. Выбор подходящей длины подпоследовательности является основным ключом к минимизации этого эффекта. Когда доступных данных (и времени на их обработку) больше, чем количество, необходимое для достижения желаемого частотного разрешения, стандартным методом является выполнение нескольких ДПФ, например, для создания спектрограммы . Если желаемый результат представляет собой спектр мощности, а в данных присутствует шум или случайность, усреднение составляющих амплитуды нескольких ДПФ является полезной процедурой для уменьшения дисперсии спектра (также называемой периодограммой в этом контексте); два примера таких методов являются метод Велч и метод Бартлетта ; Общий предмет оценки спектра мощности зашумленного сигнала называется спектральной оценкой .
Последним источником искажения (или, возможно, иллюзии ) является само ДПФ, потому что это всего лишь дискретная выборка ДВПФ, которая является функцией непрерывной частотной области. Это можно смягчить, увеличив разрешение ДПФ. Эта процедура проиллюстрирована в § Выборка ДВПФ .
- Процедуру иногда называют заполнением нулями , что является конкретной реализацией, используемой в сочетании с алгоритмом быстрого преобразования Фурье (БПФ). Неэффективность умножения и сложения с нулевыми «выборками» более чем компенсируется внутренней эффективностью БПФ.
- Как уже говорилось, утечка накладывает ограничение на собственное разрешение ДПФ, поэтому существует практический предел преимуществ, которые можно получить от мелкозернистого ДПФ.
Банк фильтров
См. § Банки фильтров БПФ и § Выборка ДВПФ .
Сжатие данных
Область цифровой обработки сигналов в значительной степени зависит от операций в частотной области (т. Е. От преобразования Фурье). Например, несколько методов сжатия изображения и звука с потерями используют дискретное преобразование Фурье: сигнал разрезается на короткие сегменты, каждый преобразуется, а затем коэффициенты Фурье высоких частот, которые считаются незаметными, отбрасываются. Декомпрессор вычисляет обратное преобразование на основе этого уменьшенного числа коэффициентов Фурье. (В приложениях сжатия часто используется специальная форма ДПФ, дискретное косинусное преобразование или иногда модифицированное дискретное косинусное преобразование .) Однако некоторые относительно недавние алгоритмы сжатия используют вейвлет-преобразования , которые дают более однородный компромисс между временной и частотной областями, чем полученный. путем разделения данных на сегменты и преобразования каждого сегмента. В случае JPEG2000 это позволяет избежать ложных характеристик изображения, которые появляются, когда изображения сильно сжаты с исходным JPEG .
Уравнения с частными производными
Дискретные преобразования Фурье часто используются для решения уравнений в частных производных , где снова ДПФ используется в качестве приближения для ряда Фурье (который восстанавливается в пределе бесконечного N ). Преимущество этого подхода в том, что он расширяет сигнал в комплексные экспоненты., которые являются собственными функциями дифференцирования: . Таким образом, в представлении Фурье дифференцирование выполняется просто - мы просто умножаем на. (Однако выборне уникален из-за алиасинга; чтобы метод был сходимым, следует использовать выбор, аналогичный тому, что был в предыдущем разделе тригонометрической интерполяции .) Линейное дифференциальное уравнение с постоянными коэффициентами преобразуется в легко решаемое алгебраическое уравнение. Затем используется обратное ДПФ, чтобы преобразовать результат обратно в обычное пространственное представление. Такой подход называется спектральным методом .
Полиномиальное умножение
Предположим, мы хотим вычислить полиномиальное произведение c ( x ) = a ( x ) · b ( x ). Обычное выражение произведения для коэффициентов c включает линейную (ациклическую) свертку, при которой индексы не «зацикливаются». Это можно переписать как циклическую свертку, взяв сначала векторы коэффициентов для a ( x ) и b ( x ) с постоянным членом, а затем добавив нули, чтобы результирующие векторы коэффициентов a и b имели размерность d > deg ( a ( x ) ) + град ( Ь ( х )) . Потом,
Где c - вектор коэффициентов для c ( x ), а оператор свертки определяется так
Но свертка становится умножением под ДПФ:
Здесь векторное произведение берется поэлементно. Таким образом, коэффициенты полинома произведения c ( x ) - это просто члены 0, ..., deg ( a ( x )) + deg ( b ( x )) вектора коэффициентов
С быстрым преобразованием Фурье результирующий алгоритм требует O ( N log N ) арифметических операций. Из-за его простоты и скорости алгоритм БПФ Кули-Тьюки , который ограничен составными размерами, часто выбирается для операции преобразования. В этом случае d следует выбирать как наименьшее целое число, большее суммы степеней входного полинома, которое может быть разложено на малые простые множители (например, 2, 3 и 5, в зависимости от реализации БПФ).
Умножение больших целых чисел
Самые быстрые известные алгоритмы умножения очень больших целых чисел используют метод полиномиального умножения, описанный выше. Целые числа можно трактовать как значение многочлена, вычисляемого специально по числовой базе, с коэффициентами многочлена, соответствующими цифрам в этой базе (например,). После полиномиального умножения, относительно несложный этап распространения переноса завершает умножение.
Свертка
Когда данные свертываются с помощью функции с широкой поддержкой, такой как понижающая дискретизация с большим коэффициентом дискретизации, из-за теоремы свертки и алгоритма БПФ может быть быстрее преобразовать их, умножить поточечно на преобразование фильтра и затем отменить преобразовать его. В качестве альтернативы хороший фильтр получается путем простого усечения преобразованных данных и повторного преобразования сокращенного набора данных.
Некоторые пары дискретных преобразований Фурье
Примечание | ||
---|---|---|
Теорема о сдвиге частоты | ||
Теорема о сдвиге во времени | ||
Реальный ДПФ | ||
из формулы геометрической прогрессии | ||
из биномиальной теоремы | ||
- прямоугольная оконная функция из W точек с центром на n = 0, где W - нечетное целое число , иявляется sinc- подобной функцией (в частности,является ядром Дирихле ) | ||
Дискретизация и периодическое суммирование масштабированных функций Гаусса для. Поскольку либо или же больше единицы и, таким образом, гарантирует быструю сходимость одного из двух рядов для больших вы можете вычислить частотный спектр и преобразовать его во временную область с помощью дискретного преобразования Фурье. |
Обобщения
Теория представлений
ДПФ можно интерпретировать как комплексное представление конечной циклической группы . Другими словами, последовательность комплексные числа можно рассматривать как элемент -мерное сложное пространство или, что то же самое, функция из конечной циклической группы порядка к комплексным числам, . Такявляется функцией класса на конечной циклической группе и, таким образом, может быть выражена как линейная комбинация неприводимых характеров этой группы, которые являются корнями из единицы.
С этой точки зрения можно обобщить ДПФ на теорию представлений в целом или более узко на теорию представлений конечных групп .
Еще более узко, можно обобщить ДПФ, либо изменив цель (принимая значения в поле, отличном от комплексных чисел), либо домен (группа, отличная от конечной циклической группы), как подробно описано в дальнейшем.
Прочие поля
Многие свойства ДПФ зависят только от того, что является примитивным корнем из единицы , иногда обозначается или же (чтобы ). К таким свойствам относятся указанные выше свойства полноты, ортогональности, Планшереля / Парсеваля, периодичности, сдвига, свертки и унитарности, а также многие алгоритмы БПФ. По этой причине дискретное преобразование Фурье может быть определено с помощью корней из единицы в полях, отличных от комплексных чисел, и такие обобщения обычно называются теоретико- числовыми преобразованиями (NTT) в случае конечных полей . Дополнительные сведения см. В разделах Теоретико-числовое преобразование и дискретное преобразование Фурье (общие) .
Другие конечные группы
Стандарт ДПФ действует на последовательность х 0 , х 1 , ..., х N -1 комплексных чисел, которые можно рассматривать как функцию {0, 1, ..., N - 1} → C . Многомерное ДПФ действует на многомерные последовательности, которые можно рассматривать как функции
Это предполагает обобщение на преобразования Фурье на произвольных конечных группах , которые действуют на функции G → C, где G - конечная группа . В этой структуре стандартное ДПФ рассматривается как преобразование Фурье циклической группы , а многомерное ДПФ - это преобразование Фурье прямой суммы циклических групп.
Кроме того, преобразование Фурье может выполняться на смежных классах группы.
Альтернативы
Существуют различные альтернативы ДПФ для различных приложений, среди которых выделяются вейвлеты . Аналогом ДПФ является дискретное вейвлет-преобразование (ДВП). С точки зрения частотно-временного анализа , ключевым ограничением преобразования Фурье является то, что оно не включает информацию о местоположении , а только частотную информацию, и, таким образом, затрудняет представление переходных процессов. Поскольку вейвлеты имеют местоположение, а также частоту, они лучше могут представлять местоположение за счет большей сложности с представлением частоты. Подробнее см. Сравнение дискретного вейвлет-преобразования с дискретным преобразованием Фурье .
Смотрите также
- Сопутствующая матрица
- Матрица ДПФ
- Быстрое преобразование Фурье
- FFTPACK
- FFTW
- Обобщения матриц Паули.
- Спектральный анализ методом наименьших квадратов
- Список преобразований, связанных с Фурье
- Многомерное преобразование
- Зак преобразовать
- Квантовое преобразование Фурье
Заметки
- ^ Как линейное преобразование в конечномерном векторном пространстве , выражение ДПФ также может быть записано в терминах матрицы ДПФ ; при соответствующем масштабировании она становится унитарной матрицей, и, таким образом, X k можно рассматривать как коэффициенты x в ортонормированном базисе .
- ^ Обратное время для ДПФ означает замену от и нет от чтобы избежать отрицательных показателей.
Рекомендации
- ^ Стрэнг, Гилберт (май – июнь 1994 г.). «Вейвлеты». Американский ученый . 82 (3): 250–255. JSTOR 29775194 .
Это самый важный численный алгоритм нашей жизни ...
- ^ Sahidullah, Md .; Саха, Гоутам (февраль 2013 г.). «Новый метод оконного управления для эффективного вычисления MFCC для распознавания говорящего». Письма об обработке сигналов IEEE . 20 (2): 149–152. arXiv : 1206,2437 . Bibcode : 2013ISPL ... 20..149S . DOI : 10,1109 / LSP.2012.2235067 . S2CID 10900793 .
- ^ Дж. Кули , П. Льюис и П. Велч (1969). «Конечное преобразование Фурье». IEEE Transactions по аудио и электроакустике . 17 (2): 77–85. DOI : 10.1109 / TAU.1969.1162036 .CS1 maint: несколько имен: список авторов ( ссылка )
- ^ «Сдвинуть нулевую частотную составляющую в центр спектра - MATLAB fftshift» . mathworks.com . Натик, MA 01760: The MathWorks, Inc . Проверено 10 марта 2014 .CS1 maint: location ( ссылка )
- ^ а б Proakis, John G .; Манолакис, Дмитрий Г. (1996), Цифровая обработка сигналов: принципы, алгоритмы и приложения (3-е изд.), Верхняя Сэдл-Ривер, Нью-Джерси: Prentice-Hall International, Bibcode : 1996dspp.book ..... P , ISBN 9780133942897, sAcfAQAAIAAJ
- ^ Оппенгейм, Алан В .; Шафер, Рональд В .; Бак, Джон Р. (1999). Дискретно-временная обработка сигналов (2-е изд.). Река Аппер Сэдл, штат Нью-Джерси: Prentice Hall. п. 571 . ISBN 0-13-754920-2. Также доступно на https://d1.amobbs.com/bbs_upload782111/files_24/ourdev_523225.pdf
- ^ McGillem, Clare D .; Купер, Джордж Р. (1984). Непрерывный и дискретный сигнал и системный анализ (2-е изд.). Холт, Райнхарт и Уинстон. С. 171–172. ISBN 0-03-061703-0.
- ^ Massar, S .; Шпиндель, П. (2008). "Соотношение неопределенности для дискретного преобразования Фурье". Письма с физическим обзором . 100 (19): 190401. arXiv : 0710.0723 . Bibcode : 2008PhRvL.100s0401M . DOI : 10.1103 / PhysRevLett.100.190401 . PMID 18518426 . S2CID 10076374 .
- ^ а б в ДеБруннер, Виктор; Havlicek, Joseph P .; Пшебинда, Томаш; Озайдин, Мурад (2005). "Меры неопределенности на основе энтропии для L 2 ( р п ) , ℓ 2 ( Z ) {\ Displaystyle L ^ {2} (\ mathbb {R} ^ {n}), \ ell ^ {2} (\ mathbb {Z})} , а также ℓ 2 ( Z / N Z ) {\ Displaystyle \ ell ^ {2} (\ mathbb {Z} / N \ mathbb {Z})} С оптимальным преобразованием Хиршмана для ℓ 2 ( Z / N Z ) {\ Displaystyle \ ell ^ {2} (\ mathbb {Z} / N \ mathbb {Z})} " (PDF) . IEEE Transactions по обработке сигналов . 53 (8): 2690. Bibcode : 2005ITSP ... 53.2690D . Дои : 10,1109 / TSP.2005.850329 . Проверено 2011-06-23 .
- ^ а б Донохо, DL; Старк, ПБ (1989). «Принципы неопределенности и восстановление сигнала». Журнал SIAM по прикладной математике . 49 (3): 906–931. DOI : 10.1137 / 0149053 . S2CID 115142886 .
- ^ Сантханам, Балу; Сантханам, Таланаяр С. « Дискретные функции Гаусса-Эрмита и собственные векторы центрированного дискретного преобразования Фурье » [ постоянная мертвая ссылка ] , Труды 32-й Международной конференции IEEE по акустике, речи и обработке сигналов (ICASSP 2007, SPTM-P12.4 ), т. III, стр. 1385-1388.
- ^ Акансу, Али Н .; Агирман-Тосун, Хандан « Обобщенное дискретное преобразование Фурье с нелинейной фазой » , IEEE Transactions on Signal Processing , vol. 58, нет. 9. С. 4547–4556, сентябрь 2010 г.
дальнейшее чтение
- Бригам, Э. Оран (1988). Быстрое преобразование Фурье и его приложения . Энглвуд Клиффс, Нью-Джерси: Prentice Hall. ISBN 978-0-13-307505-2.
- Смит, Стивен В. (1999). «Глава 8: Дискретное преобразование Фурье» . Руководство для ученых и инженеров по цифровой обработке сигналов (второе изд.). Сан-Диего, Калифорния: California Technical Publishing. ISBN 978-0-9660176-3-2.
- Кормен, Томас Х .; Чарльз Э. Лейзерсон ; Рональд Л. Ривест ; Клиффорд Штайн (2001). «Глава 30: Полиномы и БПФ». Введение в алгоритмы (второе изд.). MIT Press и McGraw-Hill. стр. 822 -848. ISBN 978-0-262-03293-3.особенно раздел 30.2: ДПФ и БПФ, стр. 830–838.
- П. Дюамель; Б. Пирон; Дж. М. Эчето (1988). «О вычислении обратного ДПФ». Транзакции IEEE по акустике, речи и обработке сигналов . 36 (2): 285–286. DOI : 10.1109 / 29.1519 .
- Дж. Х. Макклеллан; TW Парки (1972). «Собственные значения и собственные векторы дискретного преобразования Фурье». IEEE Transactions по аудио и электроакустике . 20 (1): 66–74. DOI : 10.1109 / TAU.1972.1162342 .
- Брэдли В. Дикинсон; Кеннет Стейглиц (1982). «Собственные векторы и функции дискретного преобразования Фурье» (PDF) . Транзакции IEEE по акустике, речи и обработке сигналов . 30 (1): 25–31. CiteSeerX 10.1.1.434.5279 . DOI : 10,1109 / TASSP.1982.1163843 .(Обратите внимание, что в этой статье есть очевидная опечатка в таблице кратностей собственных значений: столбцы + i / - i меняются местами. Правильная таблица может быть найдена в McClellan and Parks, 1972, и ее легко подтвердить численно.)
- Ф. А. Грюнбаум (1982). «Собственные векторы дискретного преобразования Фурье» . Журнал математического анализа и приложений . 88 (2): 355–363. DOI : 10.1016 / 0022-247X (82) 90199-8 .
- Натиг М. Атакишиев; Курт Бернардо Вольф (1997). «Дробное преобразование Фурье-Кравчука». Журнал Оптического общества Америки A . 14 (7): 1467–1477. Bibcode : 1997JOSAA..14.1467A . DOI : 10.1364 / JOSAA.14.001467 .
- К. Кандан; Кутай М.А. HMOzaktas (2000). «Дискретное дробное преобразование Фурье» (PDF) . Транзакции IEEE по обработке сигналов . 48 (5): 1329–1337. Bibcode : 2000ITSP ... 48.1329C . DOI : 10.1109 / 78.839980 . ЛВП : 11693/11130 .
- Магди Тауфик Ханна, Набила Филип Атталла Сейф и Валид Абд эль-Магуид Ахмед (2004 г.). «Подобные собственные векторы Эрмита-Гаусса матрицы дискретного преобразования Фурье на основе сингулярного разложения ее ортогональных проекционных матриц». IEEE Transactions on Circuits and Systems I: Regular Papers . 51 (11): 2245–2254. DOI : 10.1109 / TCSI.2004.836850 . S2CID 14468134 .CS1 maint: несколько имен: список авторов ( ссылка )
- Шамгар Гуревич; Ронни Хадани (2009). «О диагонализации дискретного преобразования Фурье». Прикладной и вычислительный гармонический анализ . 27 (1): 87–99. arXiv : 0808.3281 . DOI : 10.1016 / j.acha.2008.11.003 . S2CID 14833478 . препринт в.
- Шамгар Гуревич; Ронни Хадани; Нир Сохен (2008). «Конечный гармонический осциллятор и его приложения к последовательностям, связи и радарам». IEEE Transactions по теории информации . 54 (9): 4239–4253. arXiv : 0808.1495 . Bibcode : 2008arXiv0808.1495G . DOI : 10.1109 / TIT.2008.926440 . S2CID 6037080 . препринт в.
- Хуан Г. Варгас-Рубио; Балу Сантханам (2005). «О многоугольном центрированном дробно-дискретном преобразовании Фурье». Письма об обработке сигналов IEEE . 12 (4): 273–276. Bibcode : 2005ISPL ... 12..273V . DOI : 10,1109 / LSP.2005.843762 . S2CID 1499353 .
- FN Kong (2008). "Аналитические выражения двух дискретных сигналов Эрмита-Гаусса". IEEE Transactions on Circuits and Systems II: Express Briefs . 55 (1): 56–60. DOI : 10.1109 / TCSII.2007.909865 . S2CID 5154718 .
Внешние ссылки
- Интерактивное объяснение ДПФ
- Учебник Matlab по дискретному преобразованию Фурье
- Интерактивный флеш-урок по DFT
- Математика дискретного преобразования Фурье Джулиуса О. Смита III
- FFTW: Быстрая реализация DFT - написана на C и под Стандартной общественной лицензией (GPL)
- Универсальный пакет FFT: еще одна быстрая реализация DFT на C и FORTRAN, разрешающая лицензия
- Объяснение: дискретное преобразование Фурье
- Дискретное преобразование Фурье
- Индексирование и сдвиг дискретного преобразования Фурье
- Свойства дискретного преобразования Фурье
- Обобщенное дискретное преобразование Фурье (GDFT) с нелинейной фазой