Быстрое преобразование Фурье

Материал из MachineLearning.

(Различия между версиями)

Версия 05:16, 18 июля 2026

Содержание

1 Быстрое преобразование Фурье
2 Определение и вычислительная сложность
3 Алгоритм Кули — Тьюки
4 Другие алгоритмы БПФ
5 Приложения в анализе данных
6 Смотрите также
7 Примечания

Быстрое преобразование Фурье

Быстрое преобразование Фурье (БПФ, Fast Fourier Transform, FFT) — класс алгоритмов, позволяющих вычислить дискретное преобразование Фурье (ДПФ) и обратное к нему за время $O(N \log N)$ . Прямое вычисление ДПФ по определению требует $O(N^2)$ арифметических операций, что делает БПФ незаменимым инструментом в задачах цифровой обработки сигналов, спектрального анализа, вычисления свёрток и умножения многочленов.

Определение и вычислительная сложность

Пусть задана последовательность комплексных чисел $x_0, x_1, \dots, x_{N-1}$ . Её дискретное преобразование Фурье определяется как

$X_k = \sum_{n=0}^{N-1} x_n W_N^{nk}, \qquad k = 0, 1, \dots, N-1,$

где $W_N = e^{-i 2\pi / N}$ — комплексный корень из единицы, называемый поворачивающим множителем. Обратное дискретное преобразование Фурье (ОДПФ) задаётся аналогично с заменой $W_N$ на $W_N^{-1}$ и нормировкой $1/N$ .

Непосредственное вычисление всех $N$ коэффициентов $X_k$ требует $N^2$ комплексных умножений и $N(N-1)$ сложений, т. е. имеет временную сложность $O(N^2)$ . При больших $N$ (порядка $10^5$ – $10^6$ , типичных в приложениях) такое количество операций неприемлемо.

Быстрым преобразованием Фурье называют любой алгоритм, понижающий сложность до $O(N \log N)$ . Наиболее распространённым является алгоритм Кули — Тьюки, основанный на методе «разделяй и властвуй». Далее основное внимание уделяется случаю $N = 2^m$ как наиболее простому и эффективному для изложения, хотя современные библиотеки (FFTW, Intel MKL) активно используют смешанные основания для достижения максимальной производительности.

Алгоритм Кули — Тьюки

Алгоритм Кули — Тьюки^[1] был опубликован в 1965 г., хотя его идеи восходят к Гауссу. Ключевая идея состоит в рекурсивном сведении вычисления ДПФ длины $N$ к двум ДПФ длины $N/2$ и последующем объединении результатов с помощью $N/2$ комплексных умножений и $N$ сложений. Алгоритм эксплуатирует алгебраические свойства корней из единицы, в частности периодичность и симметрию. Для случая $N = 2^m$ это приводит к временной сложности $O(N \log N)$ .

Существуют две симметричные формы алгоритма — с прореживанием по времени и по частоте. Ниже подробно разбирается вариант с прореживанием по времени, который наиболее наглядно демонстрирует принцип «разделяй и властвуй».

Прореживание по времени (Decimation in Time, DIT)

Пусть $N$ чётно. Разобьём исходную последовательность $x_n$ на две подпоследовательности половинной длины, выбирая отсчёты с чётными и нечётными индексами:

$x_n^{(e)} = x_{2n},$ $x_n^{(o)} = x_{2n+1},$ $n = 0, \dots, N/2 - 1.$

Обозначим через $E_k$ и $O_k$ их $N/2$ -точечные ДПФ:

$E_k = \sum_{n=0}^{N/2-1} x_{2n} W_{N/2}^{nk}, \qquad O_k = \sum_{n=0}^{N/2-1} x_{2n+1} W_{N/2}^{nk}.$

Теперь выразим искомое ДПФ $X_k$ через $E_k$ и $O_k$ . Для любого $k = 0, \dots, N-1$ справедливо:

$X_k = \sum_{n=0}^{N-1} x_n W_N^{nk} = \sum_{n=0}^{N/2-1} x_{2n} W_N^{2nk} + \sum_{n=0}^{N/2-1} x_{2n+1} W_N^{(2n+1)k} = \sum_{n=0}^{N/2-1} x_n^{(e)} W_{N/2}^{nk} + W_N^k \sum_{n=0}^{N/2-1} x_n^{(o)} W_{N/2}^{nk}.$

В последнем переходе использовалось тождество $W_N^{2nk} = W_{N/2}^{nk}$ , которое следует из определения поворачивающего множителя: $W_N^{2nk} = e^{-i 2\pi \cdot 2nk / N} = e^{-i 2\pi nk / (N/2)} = W_{N/2}^{nk}$ .

Таким образом, для первой половины выходных индексов ( $k = 0, \dots, N/2 - 1$ ) получаем:

$X_k = E_k + W_N^k O_k.$

Для второй половины ( $k = N/2, \dots, N-1$ ) воспользуемся периодичностью ДПФ половинной длины: $E_{k+N/2} = E_k$ , $O_{k+N/2} = O_k$ , и тем, что $W_N^{k+N/2} = -W_N^k$ . Подстановка даёт:

$X_{k+N/2} = E_k - W_N^k O_k, \qquad k = 0, \dots, N/2 - 1.$

Два последних соотношения

$X_k = E_k + W_N^k O_k, \qquad X_{k+N/2} = E_k - W_N^k O_k$

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

Рекурсивно применяя ту же процедуру к подзадачам длины $N/2$ , а затем к $N/4$ и так далее, мы в конечном итоге дойдём до ДПФ длины 1, которое является просто тождественным отображением ( $X_0 = x_0$ ). Глубина рекурсии составляет $\log_2 N$ . На каждом уровне рекурсии выполняется $N/2$ бабочек, каждая из которых содержит одно комплексное умножение и два сложения.

Формально время работы удовлетворяет рекуррентному соотношению $T(N) = 2T(N/2) + \Theta(N)$ , $T(1) = 0$ . По основной теореме о рекуррентности это даёт $T(N) = \Theta(N \log N)$ , то есть общее число комплексных умножений — $(N/2) \log_2 N$ , сложений — $N \log_2 N$ .

Прореживание по частоте (Decimation in Frequency, DIF)

В альтернативном подходе исходная последовательность $x_n$ делится на две половины: $x_n$ и $x_{n+N/2}$ для $n = 0,\dots,N/2-1$ . Вместо рекурсивного вычисления ДПФ чётных и нечётных индексов здесь сначала с помощью бабочек формируются две промежуточные последовательности, после чего вычисляются $N/2$ -точечные ДПФ для получения чётных и нечётных частот. Вычислительная сложность остаётся такой же — $O(N \log N)$ .

Итеративная реализация и бит-реверсивная перестановка

Прямая рекурсивная реализация требует дополнительной памяти порядка $O(N \log N)$ для хранения промежуточных массивов. На практике используют итеративный алгоритм, работающий «на месте» ( $in\text{-}place$ ) с $O(1)$ дополнительной памяти (не считая массива входных данных). Алгоритм состоит из двух фаз.

Бит-реверсивная перестановка. Входной массив переупорядочивается так, что элемент с индексом $j$ переносится в позицию, двоичное представление которой является обратным к двоичному представлению $j$ (длина двоичных слов равна $m = \log_2 N$ ). Например, для $N=8$ индекс $1 \; (001_2)$ переходит в $4 \; (100_2)$ . После этой перестановки рекурсивные подзадачи оказываются расположенными в памяти последовательно, что позволяет выполнять слияние снизу вверх.
Послойное вычисление бабочек. Пусть номер слоя $s$ пробегает значения от $1$ до $m = \log_2 N$ . На слое $s$ размер блока ДПФ равен $B = 2^s$ , а полублока — $H = B/2$ . Для каждого блока с индексом $j = 0, \dots, N/B - 1$ и для каждого элемента внутри полублока $k = 0, \dots, H-1$ выполняется бабочка над парой элементов с индексами $p = jB + k$ и $q = jB + k + H$ :

$u = x_p, \quad v = W_B^k \cdot x_q, \quad x_p = u + v, \quad x_q = u - v.$

Здесь $W_B^k = e^{-i 2\pi k / B}$ — предвычисленный поворачивающий множитель. Внешний цикл идёт по слоям $s$ , затем по блокам, и наконец по позициям внутри полублока. После завершения последнего слоя массив $x$ содержит коэффициенты ДПФ в естественном порядке.

Итеративная схема лежит в основе большинства высокопроизводительных библиотек, включая FFTW и Intel MKL.

Другие алгоритмы БПФ

Помимо алгоритма Кули — Тьюки для степеней двойки, существует ряд методов, ориентированных на произвольные длины $N$ .

Составное $N$ и гнездовые алгоритмы — обобщение Кули — Тьюки на случай $N = N_1 N_2$ , в том числе для смешанного основания. Рекурсивно сводят ДПФ к ДПФ меньших длин, возможно, разных. Пример — алгоритм Синглтона^[1].
Алгоритм Гуда — Томаса (алгоритм простых множителей) — применяется, когда $N = N_1 N_2$ со взаимно простыми $N_1, N_2$ . Использует китайскую теорему об остатках для переиндексации, сводя ДПФ к двумерному без дополнительных поворачивающих множителей.
Алгоритм Винограда (WFTA) — использует свёрточную структуру ДПФ для простых длин и тензорное произведение для составных. Минимизирует число умножений ценой усложнения адресации^[1].
Алгоритм Блюстейна (Chirp Z-Transform) — позволяет вычислить ДПФ произвольной длины $N$ , сводя его к вычислению линейной свёртки, которая затем эффективно вычисляется с помощью БПФ. Для этого используется БПФ длины $L$ , где $L$ — наименьшая степень двойки, не меньшая $2N-1$ ^[1].
БПФ для действительных данных — использует симметрию спектра действительного сигнала ( $X_{N-k} = \overline{X_k}$ ), что позволяет вдвое сократить память и вычисления. Широко распространены упакованные форматы хранения (Hermitian-symmetric).

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

Приложения в анализе данных

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

Анализ временных рядов и спектральные признаки

В задачах прогнозирования и классификации временных рядов часто бывает полезно представить сигнал через его частотные компоненты. БПФ позволяет:

Выделять периодические тренды. Амплитудный спектр $|X_k|$ мгновенно выявляет доминирующие частоты, что используется для обнаружения сезонностей, циклических паттернов в финансовых, метеорологических и сенсорных данных.
Формировать спектральные признаки. На основе БПФ строятся такие признаки, как энергия в заданных частотных полосах, спектральный центроид, спад спектра, коэффициенты кепстра. Они широко применяются в задачах распознавания активности по акселерометру, мониторинга состояния промышленного оборудования и анализа биомедицинских сигналов (ЭЭГ, ЭКГ).
Детекция аномалий с помощью спектральных остатков. Метод Spectral Residual^[1] использует БПФ для выделения «неожиданных» компонент во временном ряде, что позволяет эффективно находить выбросы и аномалии в потоковых данных без обучения.

Быстрая свёртка в машинном обучении

Свёрточные операции — основа архитектур свёрточных нейронных сетей (CNN). Для больших ядер свёртки или при работе с одномерными сигналами высокой размерности прямые вычисления становятся затратными. БПФ даёт альтернативный путь: дополнив последовательности нулями до длины $N \ge L+M-1$ (где $L,\;M$ — длины исходных векторов), линейную свёртку можно вычислить как

$y = \text{IFFT}\left( \text{FFT}(x_{zp}) \odot \text{FFT}(h_{zp}) \right),$

где $x_{zp},\;h_{zp}$ — дополненные нулями сигналы, а $\odot$ — поэлементное умножение. Это не только ускоряет вычисления на CPU и GPU (особенно с помощью таких библиотек, как cuFFT), но и позволяет реализовать свёртку с очень большим рецептивным полем, что полезно в задачах обработки аудио и длинных последовательностей. Аналогично, взаимная корреляция через БПФ используется для быстрого сопоставления шаблонов, например, при поиске объекта на изображении.

Признаки для аудио- и речевой аналитики

Практически все стандартные признаки в обработке речи и музыки опираются на БПФ:

Мел-частотные кепстральные коэффициенты (MFCC). Вычисление мел-спектрограммы и последующего дискретного косинусного преобразования начинается с БПФ коротких кадров сигнала. Эти коэффициенты служат входом для систем распознавания речи, идентификации диктора и музыкальных рекомендательных систем.
Спектрограммы как изображения. Во многих нейросетевых подходах (например, SoundNet, VGGish) аудиосигнал преобразуется в логарифмическую мел-спектрограмму, которая затем подаётся на вход CNN. Сама спектрограмма строится с помощью БПФ, и её качество напрямую влияет на точность классификации.

Обработка изображений и компьютерное зрение

Двумерное БПФ, получаемое последовательным одномерным БПФ по строкам и столбцам, — мощный инструмент в арсенале дата-сайентиста:

Фильтрация и улучшение изображений. Частотная фильтрация (низкочастотная для подавления шума, высокочастотная для выделения контуров) выполняется элементарным умножением спектра на маску, после чего применяется обратное БПФ. Это стандартный этап предобработки в задачах распознавания.
Ускорение глубоких сетей. Некоторые исследовательские работы предлагают переносить свёртки внутрь нейросетей в частотную область, что может снизить вычислительную сложность для слоёв с большими фильтрами^[1].
Поиск по образцу и регистрация. Фазовая корреляция, основанная на БПФ, позволяет находить сдвиг между двумя изображениями с субпиксельной точностью, что используется при совмещении снимков, отслеживании объектов и в задачах оптического потока.

Другие направления

Умножение многочленов и больших чисел. Умножение многочленов степени $d$ эквивалентно свёртке коэффициентов и выполняется за $O(d \log d)$ с помощью БПФ. Это находит применение в алгоритмах длинной арифметики и криптографии, а также при вычислении ядерных методов (полиномиальные ядра).
Решение уравнений в частных производных. Спектральные методы на основе БПФ являются основным инструментом для моделирования турбулентности, прогноза погоды и физических симуляций, где требуется быстрое решение периодических задач.
Беспроводная связь. OFDM-модуляция в Wi-Fi, LTE, 5G реализуется с помощью БПФ/ОБПФ, что обеспечивает эффективную передачу данных, однако это скорее область передачи данных, чем их анализа.

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

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

Примечания

Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%BE%D0%B5_%D0%BF%D1%80%D0%B5%D0%BE%D0%B1%D1%80%D0%B0%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%A4%D1%83%D1%80%D1%8C%D0%B5»

@@ Строка 1: / Строка 1: @@
 == Быстрое преобразование Фурье ==
-'''Быстрое преобразование Фурье''' (БПФ, {{lang-en|Fast Fourier Transform, FFT}}) — класс алгоритмов, позволяющих вычислить [[Дискретное преобразование Фурье|дискретное преобразование Фурье]] (ДПФ) и обратное к нему за время <tex>O(N \log N)</tex>. Прямое вычисление ДПФ по определению требует <tex>O(N^2)</tex> арифметических операций, что делает БПФ незаменимым инструментом в задачах [[Цифровая обработка сигналов|цифровой обработки сигналов]], спектрального анализа, вычисления [[Свёртка|свёрток]] и умножения многочленов.
+'''Быстрое преобразование Фурье''' (БПФ, Fast Fourier Transform, FFT) — класс алгоритмов, позволяющих вычислить [[Дискретное преобразование Фурье|дискретное преобразование Фурье]] (ДПФ) и обратное к нему за время <tex>O(N \log N)</tex>. Прямое вычисление ДПФ по определению требует <tex>O(N^2)</tex> арифметических операций, что делает БПФ незаменимым инструментом в задачах [[Цифровая обработка сигналов|цифровой обработки сигналов]], спектрального анализа, вычисления [[Свёртка|свёрток]] и умножения многочленов.
 == Определение и вычислительная сложность ==
@@ Строка 27: / Строка 27: @@
 Пусть <tex>N</tex> чётно. Разобьём исходную последовательность <tex>x_n</tex> на две подпоследовательности половинной длины, выбирая отсчёты с чётными и нечётными индексами:
-<tex>
+<tex> x_n^{(e)} = x_{2n}, </tex>
-x_n^{(e)} = x_{2n}, \quad x_n^{(o)} = x_{2n+1}, \qquad n = 0, \dots, N/2 - 1.
+<tex> x_n^{(o)} = x_{2n+1}, </tex>
-</tex>
+<tex> n = 0, \dots, N/2 - 1.</tex>
 Обозначим через <tex>E_k</tex> и <tex>O_k</tex> их <tex>N/2</tex>-точечные ДПФ:
 <tex>
-E_k = \sum_{n=0}^{N/2-1} x_{2n} W_{N/2}^{nk}, \quad
+E_k = \sum_{n=0}^{N/2-1} x_{2n} W_{N/2}^{nk}, \qquad O_k = \sum_{n=0}^{N/2-1} x_{2n+1} W_{N/2}^{nk}.
-O_k = \sum_{n=0}^{N/2-1} x_{2n+1} W_{N/2}^{nk}.
 </tex>
@@ Строка 41: / Строка 40: @@
 <tex>
-X_k = \sum_{n=0}^{N-1} x_n W_N^{nk}
+X_k = \sum_{n=0}^{N-1} x_n W_N^{nk} = \sum_{n=0}^{N/2-1} x_{2n} W_N^{2nk} + \sum_{n=0}^{N/2-1} x_{2n+1} W_N^{(2n+1)k} = \sum_{n=0}^{N/2-1} x_n^{(e)} W_{N/2}^{nk} + W_N^k \sum_{n=0}^{N/2-1} x_n^{(o)} W_{N/2}^{nk}.
-    = \sum_{n=0}^{N/2-1} x_{2n} W_N^{2nk} + \sum_{n=0}^{N/2-1} x_{2n+1} W_N^{(2n+1)k}
-    = \sum_{n=0}^{N/2-1} x_n^{(e)} W_{N/2}^{nk} + W_N^k \sum_{n=0}^{N/2-1} x_n^{(o)} W_{N/2}^{nk}.
 </tex>

Быстрое преобразование Фурье

Материал из MachineLearning.

Версия 05:16, 18 июля 2026

Содержание

Быстрое преобразование Фурье

Определение и вычислительная сложность

Алгоритм Кули — Тьюки

Прореживание по времени (Decimation in Time, DIT)

Прореживание по частоте (Decimation in Frequency, DIF)

Итеративная реализация и бит-реверсивная перестановка

Другие алгоритмы БПФ

Приложения в анализе данных

Анализ временных рядов и спектральные признаки

Быстрая свёртка в машинном обучении

Признаки для аудио- и речевой аналитики

Обработка изображений и компьютерное зрение

Другие направления

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

Примечания

Просмотры

Личные инструменты

Навигация

Поиск

Инструменты