WikiDer > Дискретное преобразование Фурье

Discrete Fourier transform
Преобразования Фурье
Непрерывное преобразование Фурье
Ряд Фурье
Дискретное преобразование Фурье
Дискретное преобразование Фурье
Дискретное преобразование Фурье над кольцом
Анализ Фурье
Связанные преобразования
Связь между (непрерывным) преобразование Фурье и дискретное преобразование Фурье. Левая колонка: Непрерывная функция (вверху) и ее преобразование Фурье (внизу). Центральная левая колонка: Периодическое суммирование исходной функции (вверху). Преобразование Фурье (внизу) равно нулю, за исключением дискретных точек. Обратное преобразование представляет собой сумму синусоид, называемых Ряд Фурье. Центральный правый столбец: Исходная функция дискретизируется (умножается на Гребень Дирака) (верх). Его преобразование Фурье (внизу) представляет собой периодическое суммирование (DTFT) исходного преобразования. Правый столбец: DFT (внизу) вычисляет дискретные выборки непрерывного DTFT. Обратное ДПФ (вверху) представляет собой периодическое суммирование исходных отсчетов. В БПФ Алгоритм вычисляет один цикл ДПФ, и его обратный результат - один цикл обратного ДПФ.
Изображение преобразования Фурье (вверху слева) и его периодического суммирования (DTFT) в левом нижнем углу. Спектральные последовательности в (a) верхнем правом и (b) нижнем правом углу соответственно вычисляются из (a) одного цикла периодического суммирования s (t) и (b) одного цикла периодического суммирования последовательности s (nT) . Соответствующие формулы: (а) Ряд Фурье интеграл и (б) DFT суммирование. Его сходство с исходным преобразованием S (f) и относительная простота вычислений часто являются мотивацией для вычисления последовательности ДПФ.

В математика, то дискретное преобразование Фурье (DFT) преобразует конечную последовательность равноотстоящих образцы из функция в последовательность одинаковой длины из равноотстоящих выборок преобразование Фурье с дискретным временем (DTFT), который является комплексный функция частоты. Интервал, с которым выполняется выборка DTFT, обратно пропорционален длительности входной последовательности. Обратное ДПФ - это Ряд Фурье, используя образцы DTFT в качестве коэффициентов сложный синусоиды на соответствующих частотах ДВПФ. Он имеет те же значения выборки, что и исходная входная последовательность. Таким образом, ДПФ называется частотная область представление исходной входной последовательности. Если исходная последовательность охватывает все ненулевые значения функции, ее ДВПФ является непрерывным (и периодическим), а ДПФ обеспечивает дискретные выборки одного цикла. Если исходная последовательность представляет собой один цикл периодической функции, ДПФ предоставляет все ненулевые значения одного цикла ДВПФ.

ДПФ - самый важный дискретное преобразование, используется для выполнения Анализ Фурье во многих практических приложениях.[1] В цифровая обработка сигналов, функция - это любое количество или сигнал который меняется со временем, например, давление звуковая волна, а радио сигнал, или ежедневно температура показания, снятые за конечный интервал времени (часто определяемый оконная функция[2]). В обработка изображений, выборками могут быть значения пиксели вдоль строки или столбца растровое изображение. ДПФ также используется для эффективного решения уравнения в частных производных, а также для выполнения других операций, таких как извилины или умножение больших целых чисел.

Поскольку он имеет дело с ограниченным объемом данных, его можно реализовать в компьютеры к численные алгоритмы или даже посвященный аппаратное обеспечение. Эти реализации обычно используют эффективные быстрое преобразование Фурье (БПФ) алгоритмы;[3] настолько, что термины «БПФ» и «ДПФ» часто используются как синонимы. До текущего использования "БПФ" инициализм могло также использоваться для двусмысленного термина "конечное преобразование Фурье".

Определение

В дискретное преобразование Фурье преобразует последовательность из N сложные числа в другую последовательность комплексных чисел, который определяется

 

 

 

 

(Уравнение 1)

где последнее выражение следует из первого следующим образом: Формула Эйлера.

Преобразование иногда обозначают символом , как в или же или же .[A]

Мотивация

Уравнение 1 также могут быть оценены вне домена , и эта расширенная последовательность -периодический. Соответственно, другие последовательности иногда используются индексы, например (если четный) и (если является нечетным), что означает замену левой и правой половин результата преобразования местами.[4]

Уравнение 1 могут интерпретироваться или выводиться различными способами, например:

  • Он полностью описывает преобразование Фурье с дискретным временем (DTFT) -периодическая последовательность, состоящая только из дискретных частотных составляющих. (Использование DTFT с периодическими данными)
  • Он также может обеспечивать равномерно распределенные выборки непрерывного ДВПФ последовательности конечной длины. (§ Выборка DTFT)
  • Это взаимная корреляция из Вход последовательность, , и комплексная синусоида на частоте . Таким образом, он действует как согласованный фильтр для этой частоты.
  • Это дискретный аналог формулы для коэффициентов при Ряд Фурье:

     

     

     

     

    (Уравнение 2)

    что также -периодический. В доменеп ∈ [0, N − 1], это обратное преобразование из Уравнение 1. В этой интерпретации каждый представляет собой комплексное число, которое кодирует как амплитуду, так и фазу комплексной синусоидальной составляющей функции Синусоиды частота является k циклов на N образцы. Его амплитуда и фаза:

    куда atan2 является двухаргументной формой арктан функция. В полярной форме куда СНГ мнемоника для cos +я грех.

Коэффициент нормализации, умножающий DFT и IDFT (здесь 1 и ), а знаки показателей просто условности, и различаются некоторыми методами лечения. Единственные требования этих соглашений состоят в том, чтобы ДПФ и IDFT имели экспоненты разного знака и чтобы произведение их коэффициентов нормализации было . Нормализация как для ДПФ, так и для IDFT, например, делает преобразования унитарными. Дискретный импульс, в п = 0 и 0 в противном случае; может превратиться в для всех k (используйте коэффициент нормализации 1 для ДПФ и для IDFT). Сигнал постоянного тока, в k = 0 и 0 в противном случае; может обратно преобразоваться в для всех (использовать для DFT и 1 для IDFT), что соответствует просмотру ОКРУГ КОЛУМБИЯ как среднее среднее сигнала.

Пример

Позволять и

Здесь мы демонстрируем, как вычислить ДПФ с помощью Уравнение 1:

Обратное преобразование

Дискретное преобразование Фурье обратимо, линейное преобразование

с обозначающий набор сложные числа. Его обратное преобразование известно как обратное дискретное преобразование Фурье (IDFT). Другими словами, для любого , N-мерный комплексный вектор имеет ДПФ и ОДПФ, которые в свою очередь -мерные комплексные векторы.

Обратное преобразование дается выражением:

 

 

 

 

(Уравнение 3)

Характеристики

Линейность

ДПФ является линейным преобразованием, т.е. если и , то для любых комплексных чисел :

Реверс времени и частоты

Изменение времени вспять (т. Е. Замена к )[B] в соответствует изменению частоты (т. е. к ).[5]:стр.421 Математически, если представляет вектор Икс тогда

если
тогда

Спряжение во времени

Если тогда .[5]:стр.423

Реальная и мнимая часть

В этой таблице показаны некоторые математические операции над во временной области и соответствующие эффекты на его ДПФ в частотной области.

СвойствоОбласть времени
Частотный диапазон
Реальная часть времени
Воображаемая часть времени
Действительная часть частоты
Мнимая часть частоты

Ортогональность

Векторы для мужчин ортогональный базис по набору N-мерные комплексные векторы:

куда это Дельта Кронекера. (На последнем шаге суммирование тривиально, если , где это 1 + 1 + ⋅⋅⋅ =N, а в противном случае - геометрическая серия которые можно явно просуммировать для получения нуля.) Это условие ортогональности можно использовать для вывода формулы для IDFT из определения DFT, и оно эквивалентно свойству унитарности, приведенному ниже.

Теорема Планшереля и теорема Парсеваля

Если и являются ДПФ и соответственно тогда Теорема Парсеваля состояния:

где звездочка обозначает комплексное сопряжение. Теорема Планшереля является частным случаем теоремы Парсеваля и утверждает:

Эти теоремы также эквивалентны приведенному ниже условию унитарности.

Периодичность

Периодичность можно показать прямо из определения:

Точно так же можно показать, что формула IDFT приводит к периодическому расширению.

Теорема сдвига

Умножение по линейная фаза для некоторого целого числа м соответствует круговой сдвиг выхода : заменяется на , где нижний индекс интерпретируется по модулю N (т.е. периодически). Точно так же круговой сдвиг входа соответствует умножению выхода линейной фазой. Математически, если представляет вектор Икс тогда

если
тогда
и

Теорема круговой свертки и теорема взаимной корреляции

В теорема свертки для преобразование Фурье с дискретным временем (DTFT) указывает, что свертка двух последовательностей может быть получена как обратное преобразование продукта отдельных преобразований. Важное упрощение происходит, когда одна из последовательностей является N-периодической, обозначенной здесь как потому что отлична от нуля только на дискретных частотах (см. DTFT § Периодические данные), а значит, и его произведение на непрерывную функцию Это приводит к значительному упрощению обратного преобразования.

куда это периодическое суммирование из последовательность:  

Обычно суммирование ДПФ и обратного ДПФ выполняется по области Определение этих ДПФ как и результат:

На практике последовательность обычно имеет длину N или меньше, и является периодическим продолжением N-длины -последовательность, которая также может быть выражена как круговая функция:

Тогда свертку можно записать как:

что приводит к интерпретации как круговой свертка и [6][7] Его часто используют для эффективного вычисления их линейной свертки. (видеть Круговая свертка, Алгоритмы быстрой свертки, и Сохранение с перекрытием)

Точно так же взаимная корреляция из и дан кем-то:

Двойственность теоремы свертки

Также можно показать, что:

что является круговой сверткой и .

Тригонометрический интерполяционный полином

В тригонометрический интерполяционный полином

где коэффициенты Иксk даются ДПФ Иксп выше, удовлетворяет свойству интерполяции за .

Даже для Nобратите внимание, что Компонент Найквиста обрабатывается специально.

Эта интерполяция не уникальный: aliasing подразумевает, что можно добавить N к любой из частот комплексной синусоиды (например, изменение к ) без изменения свойства интерполяции, но давая разные ценности между точки. Однако вышеприведенный выбор типичен, поскольку он обладает двумя полезными свойствами. Во-первых, он состоит из синусоид, частоты которых имеют наименьшие возможные величины: интерполяция ограниченный диапазон. Во-вторых, если настоящие числа, тогда тоже реально.

Напротив, наиболее очевидным полиномом тригонометрической интерполяции является тот, в котором частоты находятся в диапазоне от 0 до (вместо примерно к как указано выше), аналогично обратной формуле ДПФ. Эта интерполяция делает нет минимизировать наклон, и нет как правило, с реальной стоимостью ; его использование - распространенная ошибка.

Унитарный ДПФ

Другой способ взглянуть на ДПФ - отметить, что в приведенном выше обсуждении ДПФ можно выразить как Матрица ДПФ, а Матрица Вандермонда, представил Сильвестр в 1867 г.,

куда примитивный Nй корень единства.

Обратное преобразование затем дается обратной матрицей указанной выше:

С унитарный константы нормализации , ДПФ становится унитарное преобразование, определяемый унитарной матрицей:

куда это детерминант функция. Определитель - это произведение собственных значений, которые всегда равны или же как описано ниже. В реальном векторном пространстве унитарное преобразование можно рассматривать как просто жесткое вращение системы координат, и все свойства жесткого вращения можно найти в унитарном ДПФ.

Ортогональность ДПФ теперь выражается как ортонормальность условие (которое возникает во многих областях математики, как описано в корень единства):

Если Икс определяется как унитарное ДПФ вектора Икс, тогда

и Теорема Парсеваля выражается как

Если мы рассматриваем ДПФ как просто преобразование координат, которое просто определяет компоненты вектора в новой системе координат, то приведенное выше является просто утверждением, что скалярное произведение двух векторов сохраняется при унитарном преобразовании ДПФ. Для особого случая , это означает, что длина вектора также сохраняется - это просто Теорема Планшереля,

Следствие теорема круговой свертки состоит в том, что матрица ДПФ F диагонализирует любой циркулянтная матрица.

Выражение обратного ДПФ через ДПФ

Полезное свойство ДПФ состоит в том, что обратное ДПФ может быть легко выражено в терминах (прямого) ДПФ с помощью нескольких хорошо известных "приемов". (Например, в вычислениях часто бывает удобно реализовать только быстрое преобразование Фурье, соответствующее одному направлению преобразования, а затем получить другое направление преобразования из первого.)

Во-первых, мы можем вычислить обратное ДПФ, изменив все входные данные, кроме одного (Дюамель и другие., 1988):

(Как обычно, индексы интерпретируются по модулю N; таким образом, для , у нас есть .)

Во-вторых, можно также сопрягать входы и выходы:

В-третьих, вариант этого трюка сопряжения, который иногда предпочтительнее, поскольку он не требует модификации значений данных, включает в себя замену реальной и мнимой частей (что может быть выполнено на компьютере, просто изменив указатели). Определять в качестве поменяв местами его реальную и мнимую части - то есть, если тогда является . Эквивалентно, равно . потом

То есть обратное преобразование такое же, как и прямое преобразование, при этом реальная и мнимая части меняются местами как для ввода, так и для вывода, с точностью до нормализации (Дюамель и другие., 1988).

Уловку сопряжения можно также использовать для определения нового преобразования, тесно связанного с ДПФ, т. Е. инволютивный- то есть противоположное самому себе. Особенно, явно обратный: . Тесно связанная инволютивная трансформация (с коэффициентом (1 + я)/2) является , поскольку факторы в отменить 2. Для реальных входов , реальная часть не что иное, как дискретное преобразование Хартли, что тоже инволютивно.

Собственные значения и собственные векторы

В собственные значения матрицы ДПФ просты и хорошо известны, тогда как собственные векторы сложны, не уникальны и являются предметом постоянных исследований.

Рассмотрим унитарную форму определенное выше для ДПФ длины N, куда

Эта матрица удовлетворяет матричный полином уравнение:

Это видно из обратных свойств выше: работа дважды дает исходные данные в обратном порядке, поэтому четыре раза возвращает исходные данные и, таким образом, единичная матрица. Это означает, что собственные значения удовлетворяют уравнению:

Следовательно, собственные значения четвертые корни единства: равно +1, −1, +я, или -я.

Поскольку для этого есть только четыре различных собственных значения матрица, у них есть множественность. Кратность дает количество линейно независимый собственные векторы, соответствующие каждому собственному значению. (Есть N независимые собственные векторы; унитарная матрица никогда не дефектный.)

Проблема их множественности была решена McClellan и Parks (1972), хотя позже было показано, что она эквивалентна проблеме, решаемой с помощью Гаусс (Дикинсон и Стейглиц, 1982). Кратность зависит от значения N по модулю 4, и приводится в следующей таблице:

Кратности собственных значений λ унитарной матрицы ДПФ U как функция размера преобразования N (в виде целого числа м).
размер 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 и другие., 2000; Ханна и другие., 2004; Гуревич, Хадани, 2008).

Прямой подход заключается в дискретизации собственной функции непрерывного преобразование Фурье, из которых самым известным является Функция Гауссапериодическое суммирование функции означает дискретизацию ее частотного спектра, а дискретизация означает периодическое суммирование спектра, дискретизированная и периодически суммируемая функция Гаусса дает собственный вектор дискретного преобразования:

  • .

Выражение в замкнутой форме для ряда может быть выражено как Тета-функции Якоби в качестве

  • .

Два других простых аналитических собственных вектора в замкнутой форме для специального периода ДПФ N были обнаружены (Kong, 2008):

На период ДПФ N = 2L + 1 = 4K + 1, где K является целым числом, следующий собственный вектор ДПФ:

На период ДПФ N = 2L = 4K, куда K является целым числом, следующий собственный вектор ДПФ:

Выбор собственных векторов матрицы ДПФ стал важным в последние годы для определения дискретного аналога матрицы дробное преобразование Фурье- матрицу ДПФ можно преобразовать в дробные степени, возведя в степень собственные значения (например, Rubio and Santhanam, 2005). Для непрерывное преобразование Фурье, естественными ортогональными собственными функциями являются Функции Эрмита, поэтому различные их дискретные аналоги использовались в качестве собственных векторов ДПФ, такие как Полиномы Кравчука (Атакишиев, Вольф, 1997). Однако «лучший» выбор собственных векторов для определения дробного дискретного преобразования Фурье остается открытым вопросом.

Принципы неопределенности

Принцип вероятностной неопределенности

Если случайная величина Иксk сдерживается

тогда

можно рассматривать как дискретный функция массы вероятности из п, с ассоциированной функцией массы вероятности, построенной на основе преобразованной переменной,

В случае непрерывных функций и , то Принцип неопределенности Гейзенберга утверждает, что

куда и различия и соответственно, причем равенство достигается при подходящем нормированном Гауссово распределение. Хотя дисперсии могут быть определены аналогично для ДПФ, аналогичный принцип неопределенности бесполезен, потому что неопределенность не будет инвариантной относительно сдвига. Тем не менее, Массар и Спиндель ввели осмысленный принцип неопределенности.[8]

Однако Хиршман энтропийная неопределенность будет полезный аналог для случая ДПФ.[9] Принцип неопределенности Хиршмана выражается через Энтропия Шеннона двух функций вероятности.

В дискретном случае энтропии Шеннона определяются как

и

и энтропийная неопределенность принцип становится[9]

Равенство получается при равны переводам и модуляциям соответственно нормализованного Гребень Кронекера периода куда любой точный целочисленный делитель . Функция массы вероятности тогда будет пропорционально переведенному соответствующим образом Гребень Кронекера периода .[9]

Принцип детерминированной неопределенности

Существует также хорошо известный принцип детерминированной неопределенности, который использует разреженность сигнала (или количество ненулевых коэффициентов).[10] Позволять и быть количеством ненулевых элементов временной и частотной последовательностей и , соответственно. Потом,

Как непосредственное следствие неравенство средних арифметических и геометрических, также есть . Было показано, что оба принципа неопределенности являются строгими для специально выбранных последовательностей «пикет-забор» (дискретные последовательности импульсов) и находят практическое применение для приложений восстановления сигнала.[10]

ДПФ реальных и чисто мнимых сигналов

  • Если находятся действительные числа, как это часто бывает в практических приложениях, то ДПФ является даже симметричный:
, куда обозначает комплексное сопряжение.

Отсюда следует, что для даже и являются действительными, а остальная часть ДПФ полностью определяется просто сложные числа.

  • Если являются чисто мнимыми числами, то ДПФ является нечетно симметричный:
, куда обозначает комплексное сопряжение.

Обобщенное ДПФ (сдвинутая и нелинейная фаза)

Можно сдвинуть дискретизацию преобразования во временной и / или частотной области на некоторые реальные сдвиги. а и б, соответственно. Иногда это называют обобщенное ДПФ (или же GDFT), также называемый сдвинутый ДПФ или же смещение ДПФ, и имеет свойства, аналогичные обычному ДПФ:

Чаще всего смены (половина выборки). В то время как обычное ДПФ соответствует периодическому сигналу как во временной, так и в частотной областях, производит сигнал, который является антипериодическим в частотной области () и наоборот для Таким образом, частный случай известен как нечетное время нечетная частота дискретное преобразование Фурье (или O2 Такие сдвинутые преобразования чаще всего используются для симметричных данных, чтобы представить различные граничные симметрии, а для вещественно-симметричных данных они соответствуют разным формам дискретных данных. косинус и синус трансформирует.

Еще один интересный выбор , который называется центрированный ДПФ (или же CDFT). Центрированное ДПФ обладает тем полезным свойством, что при N кратно четырем, все четыре его собственных значения (см. выше) имеют равную кратность (Rubio and Santhanam, 2005)[11]

Термин GDFT также используется для нелинейных фазовых расширений DFT. Следовательно, метод GDFT обеспечивает обобщение для ортогональных блочных преобразований с постоянной амплитудой, включая линейные и нелинейные типы фазы. GDFT - это структура для улучшения свойств традиционной DFT во временной и частотной области, например авто / кросс-корреляции, путем добавления правильно разработанной функции формирования фазы (нелинейной, в общем) к исходным линейным функциям фазы (Akansu and Agirman-Tosun, 2010).[12]

Дискретное преобразование Фурье можно рассматривать как частный случай z-преобразование, вычисляемая на единичной окружности в комплексной плоскости; более общие z-преобразования соответствуют сложный сдвиги а и б над.

Многомерное ДПФ

Обычное ДПФ преобразует одномерную последовательность или множество это функция ровно одной дискретной переменной п. Многомерное ДПФ многомерного массива это функция d дискретные переменные за в определяется:

куда как указано выше и d выходные индексы запускаются из . Более компактно это выражается в вектор обозначение, где мы определяем и в качестве d-мерные векторы индексов от 0 до , который мы определяем как :

где разделение определяется как выполняется поэлементно, а сумма обозначает набор вложенных суммирований выше.

Обратное к многомерному ДПФ аналогично одномерному случаю определяется следующим образом:

Поскольку одномерный ДПФ выражает ввод как суперпозиция синусоид, многомерное ДПФ выражает входные данные как суперпозицию плоские волны, или многомерные синусоиды. Направление колебаний в пространстве . Амплитуды . Это разложение имеет большое значение для всего от цифровая обработка изображений (двумерный) к решению уравнения в частных производных. Решение разбивается на плоские волны.

Многомерное ДПФ можно вычислить с помощью сочинение последовательности одномерных ДПФ по каждому измерению. В двумерном случае то независимых ДПФ строк (т. е. вдоль ) сначала вычисляются для формирования нового массива . Тогда независимых ДПФ у по колоннам (по ) вычисляются для формирования окончательного результата . В качестве альтернативы можно сначала вычислить столбцы, а затем строки. Порядок несущественен, потому что вложенные суммирования выше ездить.

Таким образом, алгоритм вычисления одномерного ДПФ достаточен для эффективного вычисления многомерного ДПФ. Этот подход известен как строка столбец алгоритм. Есть также по сути многомерные алгоритмы БПФ.

Многомерное ДПФ с реальным вводом

Для исходных данных состоящий из действительные числа, выходы ДПФ имеют сопряженную симметрию, аналогичную одномерному случаю выше:

где звездочка снова означает комплексное сопряжение, а -й нижний индекс снова интерпретируется по модулю (за ).

Приложения

ДПФ широко используется в большом количестве полей; мы только набросаем несколько примеров ниже (см. также ссылки в конце). Все приложения ДПФ в решающей степени зависят от наличия быстрого алгоритма для вычисления дискретных преобразований Фурье и их обратных, a быстрое преобразование Фурье.

Спектральный анализ

Когда ДПФ используется для спектральный анализ сигналов, то последовательность обычно представляет собой конечный набор равномерно распределенных временных отсчетов некоторого сигнала. , куда представляет время. Преобразование непрерывного времени в отсчеты (дискретное время) изменяет базовый преобразование Фурье из в преобразование Фурье с дискретным временем (DTFT), что обычно влечет за собой искажение, называемое сглаживание. Выбор подходящей частоты дискретизации (см. Курс Найквиста) является ключом к минимизации этого искажения. Точно так же преобразование очень длинной (или бесконечной) последовательности в управляемый размер влечет за собой тип искажения, называемый утечка, что проявляется в потере детализации (или разрешения) в DTFT. Выбор подходящей длины подпоследовательности является первичным ключом к минимизации этого эффекта. Когда доступных данных (и времени на их обработку) больше, чем количество, необходимое для достижения желаемого разрешения по частоте, стандартным методом является выполнение нескольких ДПФ, например, для создания спектрограмма. Если желаемый результат представляет собой спектр мощности, а в данных присутствует шум или случайность, усреднение составляющих величины нескольких ДПФ является полезной процедурой для уменьшения отклонение спектра (также называемый периодограмма в контексте); два примера таких методов: Метод Велча и Бартлетт метод; общий предмет оценки спектра мощности зашумленного сигнала называется спектральная оценка.

Последний источник искажения (или, возможно, иллюзия) является самим ДПФ, потому что это просто дискретная выборка ДВПФ, которая является функцией непрерывной частотной области. Это можно уменьшить, увеличив разрешение ДПФ. Эта процедура проиллюстрирована на § Выборка DTFT.

  • Процедуру иногда называют заполнение нулями, которая является конкретной реализацией, используемой вместе с быстрое преобразование Фурье (БПФ) алгоритм. Неэффективность выполнения умножения и сложения с нулевыми «выборками» более чем компенсируется внутренней эффективностью БПФ.
  • Как уже говорилось, утечка накладывает ограничение на собственное разрешение ДПФ, поэтому существует практический предел преимуществ, которые можно получить от мелкозернистого ДПФ.

Банк фильтров

Видеть § Банки фильтров БПФ и § Выборка DTFT.

Сжатие данных

Область цифровой обработки сигналов в значительной степени зависит от операций в частотной области (то есть от преобразования Фурье). Например, несколько с потерями Методы сжатия изображения и звука используют дискретное преобразование Фурье: сигнал разрезается на короткие сегменты, каждый преобразуется, а затем коэффициенты Фурье высоких частот, которые считаются незаметными, отбрасываются. Декомпрессор вычисляет обратное преобразование на основе этого уменьшенного числа коэффициентов Фурье. (Приложения сжатия часто используют специализированную форму ДПФ, дискретное косинусное преобразование или иногда модифицированное дискретное косинусное преобразование.) Однако некоторые относительно недавние алгоритмы сжатия используют вейвлет-преобразования, которые дают более равномерный компромисс между временной и частотной областями, чем полученный путем разделения данных на сегменты и преобразования каждого сегмента. В случае JPEG2000, это позволяет избежать ложных функций изображения, которые появляются, когда изображения сильно сжаты с исходным JPEG.

Уравнения с частными производными

Дискретные преобразования Фурье часто используются для решения уравнения в частных производных, где снова ДПФ используется как приближение для Ряд Фурье (которое восстанавливается в пределе бесконечного N). Преимущество этого подхода в том, что он расширяет сигнал в комплексные экспоненты. , которые являются собственными функциями дифференцирования: . Таким образом, в представлении Фурье дифференцирование выполняется просто - мы просто умножаем на . (Однако выбор не уникален из-за алиасинга; чтобы метод был сходимым, выбор аналогичен выбору в тригонометрическая интерполяция следует использовать раздел выше.) A линейное дифференциальное уравнение с постоянными коэффициентами превращается в легко решаемое алгебраическое уравнение. Затем используется обратное ДПФ для преобразования результата обратно в обычное пространственное представление. Такой подход называется спектральный метод.

Полиномиальное умножение

Предположим, мы хотим вычислить полиномиальное произведение c(Икс) = а(Икс) · б(Икс). Обычное произведение для коэффициентов c включает линейную (ациклическую) свертку, при которой индексы не «зацикливаются». Это можно переписать как циклическую свертку, взяв векторы коэффициентов для а(Икс) и б(Икс) с постоянным членом сначала, затем добавляя нули так, чтобы результирующие векторы коэффициентов а и б иметь размер d > град (а(Икс)) + град (б(Икс)). Потом,

Где c - вектор коэффициентов при c(Икс), а оператор свертки определяется так

Но свертка становится умножением под ДПФ:

Здесь векторное произведение берется поэлементно. Таким образом, коэффициенты полинома произведения c(Икс) - это просто члены 0, ..., deg (а(Икс)) + град (б(Икс)) вектора коэффициентов

С быстрое преобразование Фурье, результирующий алгоритм принимает O (N бревноN) арифметические операции. Благодаря своей простоте и скорости Алгоритм Кули – Тьюки БПФ, который ограничен составной sizes, часто выбирается для операции преобразования. В этом случае, d следует выбирать как наименьшее целое число, большее суммы степеней входного полинома, которое можно разложить на небольшие простые множители (например, 2, 3 и 5, в зависимости от реализации БПФ).

Умножение больших целых чисел

Самый быстрый из известных алгоритмы для умножения очень больших целые числа используйте метод полиномиального умножения, описанный выше. Целые числа можно трактовать как значение многочлена, вычисляемого специально по числовой базе, с коэффициентами многочлена, соответствующими цифрам в этой базе (например, ). После полиномиального умножения, относительно несложный этап распространения переноса завершает умножение.

Свертка

Когда данные свернутый с функцией с широкой поддержкой, например, для понижающей дискретизации с большим коэффициентом дискретизации, из-за Теорема свертки и алгоритм БПФ, может быть быстрее преобразовать его, поточечное умножение на преобразование фильтра и затем обратное преобразование. В качестве альтернативы хороший фильтр получается путем простого усечения преобразованных данных и повторного преобразования сокращенного набора данных.

Некоторые пары дискретных преобразований Фурье

Некоторые пары ДПФ
Примечание
Теорема о сдвиге частоты
Теорема о сдвиге во времени
Реальный ДПФ
от геометрическая прогрессия формула
от биномиальная теорема
прямоугольный оконная функция из W точки сосредоточены на п= 0, где W является нечетное целое число, и это грех-подобная функция (в частности, это Ядро Дирихле)
Дискретность и периодическое суммирование масштабных Гауссовы функции за . Поскольку либо или же больше единицы и, следовательно, гарантирует быструю сходимость одного из двух рядов для больших вы можете вычислить частотный спектр и преобразовать его во временную область с помощью дискретного преобразования Фурье.

Обобщения

Теория представлений

ДПФ можно интерпретировать как комплекснозначный представление конечного циклическая группа. Другими словами, последовательность комплексные числа можно рассматривать как элемент -мерное сложное пространство или, что то же самое, функция из конечной циклической группы порядка к комплексным числам, . Так это функция класса на конечной циклической группе, и поэтому может быть выражена как линейная комбинация неприводимых характеров этой группы, которые являются корнями из единицы.

С этой точки зрения можно обобщить ДПФ на теорию представлений в целом или, в более узком смысле, на теорию представлений. теория представлений конечных групп.

Еще более узко, можно обобщить ДПФ, либо изменив цель (принимая значения в поле, отличном от комплексных чисел), либо домен (группа, отличная от конечной циклической группы), как подробно описано в дальнейшем.

Другие поля

Многие свойства ДПФ зависят только от того, что это первобытный корень единства, иногда обозначается или же (так что ). Такие свойства включают в себя полноту, ортогональность, свойства Планшереля / Парсеваля, периодичности, сдвига, свертки и унитарности, указанные выше, а также многие алгоритмы БПФ. По этой причине дискретное преобразование Фурье можно определить, используя корни из единицы в поля кроме комплексных чисел, и такие обобщения обычно называют теоретико-числовые преобразования (NTTs) в случае конечные поля. Для получения дополнительной информации см. теоретико-числовое преобразование и дискретное преобразование Фурье (общее).

Другие конечные группы

Стандартный ДПФ действует на последовательность Икс0, Икс1, ..., ИксN−1 комплексных чисел, которые можно рассматривать как функцию {0, 1, ..., N − 1} → C. Многомерное ДПФ действует на многомерные последовательности, которые можно рассматривать как функции

Это наводит на мысль об обобщении Преобразования Фурье на произвольных конечных группах, которые действуют на функции граммC куда грамм это конечная группа. В этой структуре стандартное ДПФ рассматривается как преобразование Фурье на циклическая группа, а многомерное ДПФ - преобразование Фурье на прямой сумме циклических групп.

Кроме того, преобразование Фурье может выполняться на смежных классах группы.

Альтернативы

Существуют различные альтернативы DFT для различных приложений, среди которых выделяются вейвлеты. Аналогом ДПФ является дискретное вейвлет-преобразование (DWT). С точки зрения частотно-временной анализ, ключевым ограничением преобразования Фурье является то, что оно не включает место расположения информация, только частота информации, и поэтому трудно представить переходные процессы. Поскольку вейвлеты имеют не только частоту, но и местоположение, они лучше могут представлять местоположение за счет большей сложности с представлением частоты. Подробнее см. сравнение дискретного вейвлет-преобразования с дискретным преобразованием Фурье.

Смотрите также

Примечания

  1. ^ Как линейное преобразование на конечномерное векторное пространство, выражение DFT также может быть записано в терминах Матрица ДПФ; при соответствующем масштабировании становится унитарная матрица и Иксk таким образом, можно рассматривать как коэффициенты при Икс в ортонормированный базис.
  2. ^ Реверс времени для ДПФ означает замену к и нет к чтобы избежать отрицательных показателей.

Рекомендации

  1. ^ Стрэнг, Гилберт (май – июнь 1994 г.). «Вейвлеты». Американский ученый. 82 (3): 250–255. JSTOR 29775194. Это самый важный числовой алгоритм нашей жизни ...
  2. ^ Sahidullah, Md .; Саха, Гоутам (февраль 2013 г.). «Новый метод оконного управления для эффективного вычисления MFCC для распознавания говорящего». Письма об обработке сигналов IEEE. 20 (2): 149–152. arXiv:1206.2437. Bibcode:2013ISPL ... 20..149S. Дои:10.1109 / LSP.2012.2235067.
  3. ^ Дж. Кули, П. Льюис и П. Велч (1969). «Конечное преобразование Фурье». IEEE Transactions по аудио и электроакустике. 17 (2): 77–85. Дои:10.1109 / TAU.1969.1162036.CS1 maint: несколько имен: список авторов (связь)
  4. ^ «Сдвинуть нулевую частотную составляющую к центру спектра - MATLAB fftshift». mathworks.com. Натик, Массачусетс, 01760: The MathWorks, Inc. Получено 10 марта 2014.CS1 maint: location (связь)
  5. ^ а б Proakis, John G .; Манолакис, Дмитрий Г. (1996), Цифровая обработка сигналов: принципы, алгоритмы и приложения (3-е изд.), Верхняя Сэдл-Ривер, Нью-Джерси: Prentice-Hall International, Bibcode:1996dspp.book ..... P, ISBN 9780133942897, sAcfAQAAIAAJ
  6. ^ Оппенгейм, Алан В.; Шафер, Рональд В.; Бак, Джон Р. (1999). Обработка сигналов в дискретном времени (2-е изд.). Река Аппер Сэдл, Нью-Джерси: Prentice Hall. п.571. ISBN 0-13-754920-2. Также доступно на https://d1.amobbs.com/bbs_upload782111/files_24/ourdev_523225.pdf
  7. ^ McGillem, Clare D .; Купер, Джордж Р. (1984). Анализ непрерывных и дискретных сигналов и систем (2-е изд.). Холт, Райнхарт и Уинстон. С. 171–172. ISBN 0-03-061703-0.
  8. ^ Massar, S .; Шпиндель, П. (2008). "Соотношение неопределенности для дискретного преобразования Фурье". Письма с физическими проверками. 100 (19): 190401. arXiv:0710.0723. Bibcode:2008ПхРвЛ.100с0401М. Дои:10.1103 / PhysRevLett.100.190401. PMID 18518426.
  9. ^ а б c ДеБруннер, Виктор; Havlicek, Joseph P .; Пшебинда, Томаш; Озайдин, Мурад (2005). "Меры неопределенности на основе энтропии для , и С оптимальным преобразованием Хиршмана для " (PDF). Транзакции IEEE при обработке сигналов. 53 (8): 2690. Bibcode:2005ITSP ... 53.2690D. Дои:10.1109 / TSP.2005.850329. Получено 2011-06-23.
  10. ^ а б Donoho, D.L .; Старк, П. Б. (1989). «Принципы неопределенности и восстановление сигнала». Журнал SIAM по прикладной математике. 49 (3): 906–931. Дои:10.1137/0149053. S2CID 115142886.
  11. ^ Сантханам, Балу; Сантханам, Таланаяр С. "Дискретные функции Гаусса-Эрмита и собственные векторы центрированного дискретного преобразования Фурье"[постоянная мертвая ссылка], Труды 32-го IEEE Международная конференция по акустике, речи и обработке сигналов (ICASSP 2007, SPTM-P12.4), т. III, стр. 1385-1388.
  12. ^ Акансу, Али Н .; Агирман-Тосун, Ханьдань "Обобщенное дискретное преобразование Фурье с нелинейной фазой", IEEE Транзакции по обработке сигналов, т. 58, нет. 9. С. 4547–4556, сентябрь 2010 г.

дальнейшее чтение

внешняя ссылка