Дискретное преобразование Фурье: различия между версиями
Miron1 (обсуждение | вклад) |
Miron1 (обсуждение | вклад) |
||
(не показаны 44 промежуточные версии этого же участника) | |||
Строка 1: | Строка 1: | ||
− | Дискретное преобразование Фурье — это одно из преобразований Фурье, широко применяемых в алгоритмах цифровой обработки сигналов, а также в других областях, связанных с анализом частот в дискретном сигнале. Дискретное преобразование Фурье требует в качестве входа дискретную функцию. Такие функции часто создаются путём дискретизации (выборки значений из непрерывных функций). Дискретные преобразования Фурье помогают решать дифференциальные уравнения в частных производных и выполнять такие операции, как свёртки. Дискретные преобразования Фурье также активно используются в статистике, при анализе временных рядов. Существуют многомерные дискретные преобразования Фурье. | + | Дискретное преобразование [https://ru.wikipedia.org/wiki/Фурье,_Жан-Батист_Жозеф Фурье] — это одно из [https://ru.wikipedia.org/wiki/Преобразование_Фурье преобразований Фурье], широко применяемых в алгоритмах цифровой обработки сигналов, а также в других областях, связанных с анализом частот в дискретном сигнале. Дискретное преобразование Фурье требует в качестве входа дискретную функцию. Такие функции часто создаются путём дискретизации (выборки значений из непрерывных функций). Дискретные преобразования Фурье помогают решать [https://ru.wikipedia.org/wiki/Дифференциальное_уравнение_в_частных_производных дифференциальные уравнения в частных производных] и выполнять такие операции, как свёртки. Дискретные преобразования Фурье также активно используются в статистике, при анализе временных рядов. Существуют многомерные дискретные преобразования Фурье. |
== Определение == | == Определение == | ||
− | Пусть имеется последовательность $$ {f_k}_{k=0}^ | + | Пусть имеется последовательность чисел $$ \{\,f_k\,\}_{k=0}^{N-1}$$. |
− | === | + | <br> |
+ | '''Дискретным преобразованием Фурье''' такой последовательности называется: | ||
+ | \[ | ||
+ | \{F_n\}_{n=0}^{N-1} : F_n = \sum\limits_{k=0}^{N-1}f_kW_N^{kn} \quad,\\ | ||
+ | W_N = e^{\frac{-2\pi i}{N}}. | ||
+ | \] | ||
+ | == Свойства == | ||
+ | # Линейность: <br /> \(\alpha \, f_k + \beta g_k \longleftrightarrow \alpha F_n + \beta G_n\) | ||
+ | # Сдвиг: <br /> \(f_{(k-m)mod \, N} \longleftrightarrow F_ne^{\scriptsize\frac{-2\pi i}{N}nm}\) | ||
+ | # Симметрия: <br /> \(f_k \longleftrightarrow F_n \\ | ||
+ | f_{(k-m)mod \, N} \longleftrightarrow F_n e^{\frac{-2\pi inm}{N}} \) | ||
+ | # Формула обращения: <br /> \(f_k = \frac{1}{N} \sum\limits_{n=0}^{N-1}F_nW_N^{-kn}\) | ||
+ | # Свёртка: <br /> \(f_k * g_k = \sum\limits_{l=0}^{N-1}f_{(k-l)\scriptsize mod \, N}g_{\scriptsize l}\) | ||
+ | # Формула Парсеваля: <br /> \(\sum\limits_{k=0}^{N-1}f_k \overline g_k = \frac{1}{N}\sum\limits_{n=0}^{N-1}F_n \overline G_n\) | ||
+ | |||
+ | == Многомерный случай == | ||
+ | * '''Прямое преобразование''': <br /> \(F_{n_1,...,n_m} = \sum\limits_{k_1=0}^{\small N_1 - 1}...\sum\limits_{k_m=0}^{\small N_m - 1}f_{k_1,...,k_m}W_{\small N_1}^{k_1 n_1}\cdot ... \cdot W_{\small N_m}^{k_m n_m} \, \\ | ||
+ | W_{\small N_i} = e^{\frac{-2\pi i}{N_i}}, \quad {\small i = 1,...,m} \) , | ||
+ | |||
+ | * '''Обратное преобразование''': <br /> \(f_{k_1,...,k_m} = \frac{1}{N_1...N_m}\sum\limits_{n_1=0}^{\small N_1 - 1}...\sum\limits_{n_m=0}^{\small N_m - 1}F_{n_1,...,n_m}W_{\small N_1}^{-k_1 n_1}\cdot ... \cdot W_{\small N_m}^{-k_m n_m} \, \\ | ||
+ | W_{\small N_i} = e^{\frac{-2\pi i}{N_i}}, \quad {\small i = 1,...,m} \) , | ||
− | === | + | == Быстрое преобразование Фурье == |
+ | Быстрое преобразование Фурье (БПФ, FFT) — алгоритм ускоренного вычисления дискретного преобразования Фурье, позволяющий получить результат за время, меньшее чем $$O(N^2)$$ | ||
+ | (требуемого для прямого, поформульного вычисления). Иногда под быстрым преобразованием Фурье понимается один из алгоритмов, называемый алгоритмом прореживания по частоте — времени, имеющий сложность $$(N\log N)$$. | ||
+ | ===Вывод преобразования=== | ||
+ | Пусть N $$-$$ чётное. <br \> | ||
+ | \( F_n = \sum\limits_{k=0}^{N-1}f_ke^{\frac{-2 \pi ink}{N}} = \{W_N = e^{\frac{-2 \pi i}{N}}\} = \sum\limits_{k=0}^{N-1}f_kW_{\scriptsize N}^{nk} = \sum\limits_{k=0}^{\frac{N}{2}-1}\left(f_{2k}W_{\scriptsize N}^{2nk} + f_{2k+1}W_{\scriptsize N}^{n(2k+1)}\right) = \\ = \sum\limits_{k=0}^{\frac{N}{2}-1}\left(f_{2k}W_{\scriptsize N/2}^{nk} + f_{2k+1}W_{\scriptsize N}^{n}W_{\scriptsize N/2}^{nk}\right) = \left(\sum\limits_{k=0}^{\frac{N}{2}-1}f_{2k}W_{\scriptsize N/2}^{nk}\right) + W_{\scriptsize N}^{n}\left(\sum\limits_{k=0}^{\frac{N}{2}-1}f_{2k+1}W_{\scriptsize N/2}^{nk}\right)\) | ||
+ | <br \> | ||
+ | Количество сложений: \(\: N(N-1) = N^2 - N\) | ||
+ | <br \> | ||
+ | Количество умножений: \(\: \frac{N}{2}\cdot \frac{N}{2} + N + \frac{N}{2}\cdot \frac{N}{2}= \frac{N^2}{2} + N\) | ||
+ | <br \> | ||
+ | Оценка сложности: \(\: o \, (N\log N)\) | ||
− | == | + | ====Соответствующие функции в MatLab:==== |
+ | * $$\texttt{Y = fft(X)}$$ возвращает дискретное преобразование Фурье вектора X, вычисленное с помощью алгоритма быстрого преобразования Фурье. | ||
+ | ** Если X-вектор, то $$\texttt{fft(X)}$$ возвращает преобразование Фурье вектора. | ||
+ | ** Если X-матрица, то $$\texttt{fft(X)}$$ возвращает преобразование Фурье каждого столбца матрицы. | ||
+ | ** Если X-многомерный массив, то $$\texttt{fft(X)}$$ обрабатывает значения первого измерения массива, размер которого не равен 1, как векторы и возвращает преобразование Фурье каждого вектора. | ||
+ | * $$\texttt{Y = fft(X,n)}$$ возвращает n-мерное быстрое преобразование Фурье. Если значение не указано, то Y имеет тот же размер, что и X. | ||
+ | ** Если X - вектор, и его размерность меньше n, то X дополняется конечными нулями до размерности n. | ||
+ | ** Если X - вектор, и его размерность больше n, то X усекается до размерности n. | ||
+ | ** Если X-матрица, то каждый столбец рассматривается как в векторном случае. | ||
+ | ** Если X-многомерный массив, то первое измерение массива, размер которого не равен 1, обрабатывается так же, как и в векторном случае. | ||
+ | * $$\texttt{Y = fft(X,n,dim)}$$ возвращает преобразование Фурье вдоль измерения dim. | ||
+ | Более подробное описание функции $$\texttt{fft}$$ можно найти по [https://www.mathworks.com/help/matlab/ref/fft.html ссылке]. | ||
+ | * $$\texttt{X = ifft(Y)}$$ вычисляет обратное дискретное преобразование Фурье для Y с использованием алгоритма быстрого преобразования Фурье. X - той же размерности, что и Y. | ||
+ | ** Функции: $$\texttt{ifft(Y,n), ifft(Y,n,dim)}$$ - работают так же, как соответсвующие функции прямого преобразования. | ||
+ | * $$\texttt{X = ifft (___ , symflag)}$$ задает симметрию Y. | ||
+ | Более подробное описание функции $$\texttt{ifft}$$ можно найти по [https://www.mathworks.com/help/matlab/ref/ifft.html ссылке]. | ||
+ | * $$\texttt{Y = fft2(X)}$$ возвращает двумерное дискретное преобразование Фурье X, вычисленное с помощью алгоритма быстрого преобразования Фурье. Y имеет тот же размер, что и X. | ||
+ | * $$\texttt{Y = fft2(X,m,n)}$$ усекает X или дополняет X нулями, чтобы создать массив размера $$m \times n$$ перед выполнением преобразования. Результат получается размера $$m \times n$$. | ||
+ | Более подробное описание функции $$\texttt{fft2}$$ можно найти по [https://www.mathworks.com/help/matlab/ref/fft2.html ссылке]. | ||
+ | * $$\texttt{Y = fftshift(X)}$$ перестраивает выходные сигналы $$\texttt{fft, fft2,}$$ перемещая компоненты, имеющие нулевую частоту, в центр массива. Это полезно для визуализации преобразования Фурье с нулевой частотной составляющей в середине спектра. | ||
+ | Более подробное описание функции $$\texttt{fftshift}$$ можно найти по [https://www.mathworks.com/help/matlab/ref/fftshift.html ссылке]. |
Текущая версия на 01:49, 20 декабря 2020
Дискретное преобразование Фурье — это одно из преобразований Фурье, широко применяемых в алгоритмах цифровой обработки сигналов, а также в других областях, связанных с анализом частот в дискретном сигнале. Дискретное преобразование Фурье требует в качестве входа дискретную функцию. Такие функции часто создаются путём дискретизации (выборки значений из непрерывных функций). Дискретные преобразования Фурье помогают решать дифференциальные уравнения в частных производных и выполнять такие операции, как свёртки. Дискретные преобразования Фурье также активно используются в статистике, при анализе временных рядов. Существуют многомерные дискретные преобразования Фурье.
Содержание
Определение
Пусть имеется последовательность чисел $$ \{\,f_k\,\}_{k=0}^{N-1}$$.
Дискретным преобразованием Фурье такой последовательности называется:
\[
\{F_n\}_{n=0}^{N-1} : F_n = \sum\limits_{k=0}^{N-1}f_kW_N^{kn} \quad,\\
W_N = e^{\frac{-2\pi i}{N}}.
\]
Свойства
- Линейность:
\(\alpha \, f_k + \beta g_k \longleftrightarrow \alpha F_n + \beta G_n\) - Сдвиг:
\(f_{(k-m)mod \, N} \longleftrightarrow F_ne^{\scriptsize\frac{-2\pi i}{N}nm}\) - Симметрия:
\(f_k \longleftrightarrow F_n \\ f_{(k-m)mod \, N} \longleftrightarrow F_n e^{\frac{-2\pi inm}{N}} \) - Формула обращения:
\(f_k = \frac{1}{N} \sum\limits_{n=0}^{N-1}F_nW_N^{-kn}\) - Свёртка:
\(f_k * g_k = \sum\limits_{l=0}^{N-1}f_{(k-l)\scriptsize mod \, N}g_{\scriptsize l}\) - Формула Парсеваля:
\(\sum\limits_{k=0}^{N-1}f_k \overline g_k = \frac{1}{N}\sum\limits_{n=0}^{N-1}F_n \overline G_n\)
Многомерный случай
- Прямое преобразование:
\(F_{n_1,...,n_m} = \sum\limits_{k_1=0}^{\small N_1 - 1}...\sum\limits_{k_m=0}^{\small N_m - 1}f_{k_1,...,k_m}W_{\small N_1}^{k_1 n_1}\cdot ... \cdot W_{\small N_m}^{k_m n_m} \, \\ W_{\small N_i} = e^{\frac{-2\pi i}{N_i}}, \quad {\small i = 1,...,m} \) ,
- Обратное преобразование:
\(f_{k_1,...,k_m} = \frac{1}{N_1...N_m}\sum\limits_{n_1=0}^{\small N_1 - 1}...\sum\limits_{n_m=0}^{\small N_m - 1}F_{n_1,...,n_m}W_{\small N_1}^{-k_1 n_1}\cdot ... \cdot W_{\small N_m}^{-k_m n_m} \, \\ W_{\small N_i} = e^{\frac{-2\pi i}{N_i}}, \quad {\small i = 1,...,m} \) ,
Быстрое преобразование Фурье
Быстрое преобразование Фурье (БПФ, FFT) — алгоритм ускоренного вычисления дискретного преобразования Фурье, позволяющий получить результат за время, меньшее чем $$O(N^2)$$ (требуемого для прямого, поформульного вычисления). Иногда под быстрым преобразованием Фурье понимается один из алгоритмов, называемый алгоритмом прореживания по частоте — времени, имеющий сложность $$(N\log N)$$.
Вывод преобразования
Пусть N $$-$$ чётное.
\( F_n = \sum\limits_{k=0}^{N-1}f_ke^{\frac{-2 \pi ink}{N}} = \{W_N = e^{\frac{-2 \pi i}{N}}\} = \sum\limits_{k=0}^{N-1}f_kW_{\scriptsize N}^{nk} = \sum\limits_{k=0}^{\frac{N}{2}-1}\left(f_{2k}W_{\scriptsize N}^{2nk} + f_{2k+1}W_{\scriptsize N}^{n(2k+1)}\right) = \\ = \sum\limits_{k=0}^{\frac{N}{2}-1}\left(f_{2k}W_{\scriptsize N/2}^{nk} + f_{2k+1}W_{\scriptsize N}^{n}W_{\scriptsize N/2}^{nk}\right) = \left(\sum\limits_{k=0}^{\frac{N}{2}-1}f_{2k}W_{\scriptsize N/2}^{nk}\right) + W_{\scriptsize N}^{n}\left(\sum\limits_{k=0}^{\frac{N}{2}-1}f_{2k+1}W_{\scriptsize N/2}^{nk}\right)\)
Количество сложений: \(\: N(N-1) = N^2 - N\)
Количество умножений: \(\: \frac{N}{2}\cdot \frac{N}{2} + N + \frac{N}{2}\cdot \frac{N}{2}= \frac{N^2}{2} + N\)
Оценка сложности: \(\: o \, (N\log N)\)
Соответствующие функции в MatLab:
- $$\texttt{Y = fft(X)}$$ возвращает дискретное преобразование Фурье вектора X, вычисленное с помощью алгоритма быстрого преобразования Фурье.
- Если X-вектор, то $$\texttt{fft(X)}$$ возвращает преобразование Фурье вектора.
- Если X-матрица, то $$\texttt{fft(X)}$$ возвращает преобразование Фурье каждого столбца матрицы.
- Если X-многомерный массив, то $$\texttt{fft(X)}$$ обрабатывает значения первого измерения массива, размер которого не равен 1, как векторы и возвращает преобразование Фурье каждого вектора.
- $$\texttt{Y = fft(X,n)}$$ возвращает n-мерное быстрое преобразование Фурье. Если значение не указано, то Y имеет тот же размер, что и X.
- Если X - вектор, и его размерность меньше n, то X дополняется конечными нулями до размерности n.
- Если X - вектор, и его размерность больше n, то X усекается до размерности n.
- Если X-матрица, то каждый столбец рассматривается как в векторном случае.
- Если X-многомерный массив, то первое измерение массива, размер которого не равен 1, обрабатывается так же, как и в векторном случае.
- $$\texttt{Y = fft(X,n,dim)}$$ возвращает преобразование Фурье вдоль измерения dim.
Более подробное описание функции $$\texttt{fft}$$ можно найти по ссылке.
- $$\texttt{X = ifft(Y)}$$ вычисляет обратное дискретное преобразование Фурье для Y с использованием алгоритма быстрого преобразования Фурье. X - той же размерности, что и Y.
- Функции: $$\texttt{ifft(Y,n), ifft(Y,n,dim)}$$ - работают так же, как соответсвующие функции прямого преобразования.
- $$\texttt{X = ifft (___ , symflag)}$$ задает симметрию Y.
Более подробное описание функции $$\texttt{ifft}$$ можно найти по ссылке.
- $$\texttt{Y = fft2(X)}$$ возвращает двумерное дискретное преобразование Фурье X, вычисленное с помощью алгоритма быстрого преобразования Фурье. Y имеет тот же размер, что и X.
- $$\texttt{Y = fft2(X,m,n)}$$ усекает X или дополняет X нулями, чтобы создать массив размера $$m \times n$$ перед выполнением преобразования. Результат получается размера $$m \times n$$.
Более подробное описание функции $$\texttt{fft2}$$ можно найти по ссылке.
- $$\texttt{Y = fftshift(X)}$$ перестраивает выходные сигналы $$\texttt{fft, fft2,}$$ перемещая компоненты, имеющие нулевую частоту, в центр массива. Это полезно для визуализации преобразования Фурье с нулевой частотной составляющей в середине спектра.
Более подробное описание функции $$\texttt{fftshift}$$ можно найти по ссылке.