- Висновок перетворення з дискретного [ правити | правити код ]
open wikipedia design.
Швидке перетворення Фур'є (БПФ, FFT) - алгоритм прискореного обчислення дискретного перетворення Фур'є , Що дозволяє отримати результат за час, менший ніж O (N 2) {\ displaystyle O (N ^ {2})} 
(Необхідного для прямого, поформульного обчислення). Іноді під швидким перетворенням Фур'є розуміється один з алгоритмів, званий алгоритмом проріджування по частоті - часу, який має складність O (N log (N)) {\ displaystyle O (N \ log (N))} 
.
Алгоритм можна застосувати до будь комутативним асоціативним кільцям з одиницею, частіше застосовують до полю комплексних чисел (C ε = e 2 π i / n {\ displaystyle \ varepsilon = e ^ {2 \ pi i / n}} 
) І до кільцям відрахувань (Яким, зокрема, є комп'ютерний цілий тип ).
При застосуванні основного алгоритму дискретне перетворення Фур'є може бути виконано O (N (p 1 + ⋯ + p n)) {\ displaystyle O (N (p_ {1} + \ cdots + p_ {n}))} 
дій при N = p 1 p 2 ⋯ p n {\ displaystyle N = p_ {1} p_ {2} \ cdots p_ {n}} 
, Зокрема, при N = 2 n {\ displaystyle N = 2 ^ {n}} 
знадобиться O (N log (N)) {\ displaystyle O (N \ log (N))} дій.
Дискретне перетворення Фур'є перетворює набір чисел a 0, ..., a n - 1 {\ displaystyle a_ {0}, \ dots, a_ {n-1}} 
в набір чисел b 0, ..., b n - 1 {\ displaystyle b_ {0}, \ dots, b_ {n-1}} 
, Такий, що b i = Σ j = 0 n - 1 a j ε i j {\ displaystyle b_ {i} = \ sum _ {j = 0} ^ {n-1} a_ {j} \ varepsilon ^ {ij}} 
, Де ε {\ displaystyle \ varepsilon} 
- первісний корінь з одиниці , Тобто ε n = 1 {\ displaystyle \ varepsilon ^ {n} = 1} 
і ε k ≠ 1 {\ displaystyle \ varepsilon ^ {k} \ neq 1} 
при 0 <k <n {\ displaystyle 0 <k <n} 
. Основний крок алгоритму полягає в зведенні задачі для N {\ displaystyle N} 
чисел до задачі з меншим числом. Для N = p q, p> 1, q> 1 {\ displaystyle N = pq, p> 1, q> 1} 
над полем комплексних чисел вводяться: ε ν = e 2 π i / ν {\ displaystyle \ varepsilon _ {\ nu} = e ^ {2 \ pi i / \ nu}} 
, Ε ν ν = 1 {\ displaystyle \ varepsilon _ {\ nu} ^ {\ nu} = 1} 
, Де ν {\ displaystyle \ nu} 
- будь-яке число. Дискретне перетворення Фур'є може бути представлено у вигляді bi = Σ k = 0 p - 1 Σ j = 0 q - 1 akq + j ε N (kq + j) i {\ displaystyle b_ {i} = \ sum _ {k = 0 } ^ {p-1} \ sum _ {j = 0} ^ {q-1} a_ {kq + j} \ varepsilon _ {N} ^ {(kq + j) i}} 
. (Ці вирази можуть бути легко отримані, якщо вихідну суму розбити на менше число сум з меншим числом доданків, а після отримані суми привести до однакового виду шляхом зсуву індексів і їх подальшого переобозначеніе).
Таким чином:
bi = Σ k = 0 p - 1 Σ j = 0 q - 1 akq + j ε N (kq + j) i = Σ j = 0 q - 1 ε N ij (Σ k = 0 p - 1 akq + j ε N kiq) {\ displaystyle b_ {i} = \ sum _ {k = 0} ^ {p-1} \ sum _ {j = 0} ^ {q-1} a_ {kq + j} \ varepsilon _ {N } ^ {(kq + j) i} = \ sum _ {j = 0} ^ {q-1} \ varepsilon _ {N} ^ {ij} (\ sum _ {k = 0} ^ {p-1} a_ {kq + j} \ varepsilon _ {N} ^ {kiq})} 
.
З урахуванням того, що ε N k i q = ε N / q k i {\ displaystyle \ varepsilon _ {N} ^ {kiq} = \ varepsilon _ {N / q} ^ {ki}} 
і N / q = p {\ displaystyle N / q = p} 
, Остаточна запис:
bi = Σ j = 0 q - 1 ε N ij (Σ k = 0 p - 1 akq + j ε pki) {\ displaystyle b_ {i} = \ sum _ {j = 0} ^ {q-1} \ varepsilon _ {N} ^ {ij} (\ sum _ {k = 0} ^ {p-1} a_ {kq + j} \ varepsilon _ {p} ^ {ki})} 
.
Далі обчислюється кожне b i {\ displaystyle b_ {i}} 
, Де i = 0, p - 1 ¯ {\ displaystyle i = {\ overline {0, p-1}}} 
, Тут як і раніше потрібно зробити O (N) {\ displaystyle O (N)} 
дій, тобто на цьому етапі проводиться p ⋅ O (N) = O (N p) {\ displaystyle p \ cdot O (N) = O (Np)} 
операцій.
Далі вважається b i + m p {\ displaystyle b_ {i + mp}} 
, Де i = 0, p - 1 ¯, m = 1, q - 1 ¯ {\ displaystyle i = {\ overline {0, p-1}}, m = {\ overline {1, q-1}}} 
. При заміні i ⟼ i + m p {\ displaystyle i \ longmapsto i + mp} 
в останній формулі, висловлювання, які стоять в дужках, залишилися незмінними, а так як вони вже були пораховані на попередньому кроці, то на обчислення кожного з них буде потрібно тільки O (q) {\ displaystyle O (q)} 
дій. Всього p (q - 1) = Np {\ displaystyle p (q-1) = Np} 
чисел. Отже, операцій на цьому кроці (Np) ⋅ O (q) = O ((N - 1) q) ≅ O (N q) {\ displaystyle (Np) \ cdot O (q) = O ((N- 1) q) \ cong O (Nq)} 
. Останнє з хорошою точністю вірно при будь-яких N {\ displaystyle N} .
Алгоритм швидкого перетворення Фур'є логічно застосовувати для N »1 {\ displaystyle N \ gg 1} 
, Тому як при малому числі відліків він дає невеликий виграш в швидкості по відношенню до прямого розрахунку дискретного перетворення Фур'є. Таким чином, для того щоб повністю перейти до набору чисел b 0, ..., b N - 1 {\ displaystyle b_ {0}, \ dots, b_ {N-1}} 
, Необхідно O (N p) + O (N q) {\ displaystyle O (Np) + O (Nq)} 
дій. Отже, немає різниці, на які два числа розбивати N {\ displaystyle N} - відповідь від цього сильно не буде змінюватися. Зменшено ж число операцій може бути тільки подальшим розбиттям N {\ displaystyle N} .
Швидкість алгоритму (N = p q) {\ displaystyle (N = pq)} 
:
- p »q ⟶ O (N p) {\ displaystyle p \ gg q \ longrightarrow O (Np)}
- p ~ q ⟶ O (N q) {\ displaystyle p \ sim q \ longrightarrow O (Nq)}
- p «q ⟶ O (N q) {\ displaystyle p \ ll q \ longrightarrow O (Nq)}
Тобто число операцій при будь-якому розбитті N {\ displaystyle N} на два числа, є O (N c) {\ displaystyle O (Nc)} 
, Де c = m a x (p, q) {\ displaystyle c = max (p, q)} 
.
Для зворотного перетворення Фур'є можна застосовувати алгоритм прямого перетворення Фур'є - потрібно лише використовувати ε - 1 {\ displaystyle \ varepsilon ^ {- 1}} 
замість ε {\ displaystyle \ varepsilon} (Або застосувати операцію комплексного сполучення спочатку до вхідних даних, а потім до результату, отриманого після прямого перетворення Фур'є), і остаточний результат поділити на N {\ displaystyle N} .
Загальний випадок може бути зведений до попереднього. Для 4 N> 2 k ≥ 2 N {\ displaystyle 4N> 2 ^ {k} \ geq 2N} 
має місце:
bi = ε - i 2/2 Σ j = 0 N - 1 ε (i + j) 2/2 ε - j 2/2 aj {\ displaystyle b_ {i} = \ varepsilon ^ {- i ^ {2} / 2} \ sum _ {j = 0} ^ {N-1} \ varepsilon ^ {(i + j) ^ {2} / 2} \ varepsilon ^ {- j ^ {2} / 2} a_ {j}} 
.
Позначаючи a ¯ i = ε - i 2/2 ai, b ¯ i = ε i 2/2 bi, ci = ε (2 N - 2 - i) 2/2 {\ displaystyle {\ bar {a}} _ { i} = \ varepsilon ^ {- i ^ {2} / 2} a_ {i}, {\ bar {b}} _ {i} = \ varepsilon ^ {i ^ {2} / 2} b_ {i}, c_ {i} = \ varepsilon ^ {(2N-2-i) ^ {2} / 2}} 
виходить:
b ¯ i = Σ j = 0 2 N - 2 - ia ¯ jc 2 N - 2 - i - j {\ displaystyle {\ bar {b}} _ {i} = \ sum _ {j = 0} ^ {2N -2-i} {\ bar {a}} _ {j} c_ {2N-2-ij}} 
,
якщо покласти a ¯ i = 0 {\ displaystyle {\ bar {a}} _ {i} = 0} 
при i ≥ N {\ displaystyle i \ geq N} 
.
Таким чином задача зведена до обчислення згортки , Але це можна зробити за допомогою трьох перетворень Фур'є для 2 k {\ displaystyle 2 ^ {k}} 
елементів: виконується пряме перетворення Фур'є для {a ¯ i} i = 0 i = 2 k - 1 {\ displaystyle \ {{\ bar {a}} _ {i} \} _ {i = 0} ^ {i = 2 ^ {k} -1}} 
і {c i} i = 0 i = 2 k - 1 {\ displaystyle \ {c_ {i} \} _ {i = 0} ^ {i = 2 ^ {k} -1}} 
, Поелементно перемножуються результати, і виконується зворотне перетворення Фур'є.
Обчислення всіх a ¯ i {\ displaystyle {\ bar {a}} _ {i}} 
і c i {\ displaystyle c_ {i}} 
вимагають O (N) {\ displaystyle O (N)} дій, три перетворення Фур'є вимагають O (N log (N)) {\ displaystyle O (N \ log (N))} дій, множення результатів перетворень Фур'є вимагає O (N) {\ displaystyle O (N)} дій, обчислення всіх b i {\ displaystyle b_ {i}} знаючи значення згортки вимагає O (N) {\ displaystyle O (N)} дій. Разом для дискретного перетворення Фур'є потрібно O (N log (N)) {\ displaystyle O (N \ log (N))} дій для будь-якого N {\ displaystyle N} .
Цей алгоритм швидкого перетворення Фур'є може працювати над кільцем тільки коли відомі первісні корені з одиниці ступенів 2 N {\ displaystyle 2N} 
і 2 k {\ displaystyle 2 ^ {k}} .
Висновок перетворення з дискретного [ правити | правити код ]
Найбільш поширеним алгоритмом швидкого перетворення Фур'є є алгоритм Кулі - Тьюки ( англ. Cooley-Tukey FFT algorithm ), При якому дискретне перетворення Фур'є від N = N 1 N 2 {\ displaystyle N = N_ {1} N_ {2}} 
виражається як сума дискретних перетворень Фур'є менших розмірностей N 1 {\ displaystyle N_ {1}} 
і N 2 {\ displaystyle N_ {2}} 
рекурсивно для того, щоб досягти складність O (N log (N)) {\ displaystyle O (N \ log (N))} . Елементарний крок зчленування менших перетворень Фур'є в цьому алгоритмі називається « метелик ». В обчислювальній техніці найбільш часто використовується рекурсивне розкладання перетворень надвоє, тобто з повним правом 2 (хоча може бути використано будь-яку підставу), а кількість вхідних відліків є ступенем двійки. Для випадків, коли дискретне перетворення вважається від кількості відліків, які є простими числами, можуть бути використані алгоритми Блуштайна і Райдера.
Наприклад, для обчислення швидкого перетворення Фур'є за алгоритмом Кулі - Тьюки з основою 2 для вектора x → {\ displaystyle {\ vec {x}}} 
, Що складається з N {\ displaystyle N} елементів:
X → = A ^ x → {\ displaystyle {\ vec {X}} = {\ hat {A}} {\ vec {x}}} 
,
з елементами A ^ {\ displaystyle {\ hat {A}}} 
виду:
a N m n = e - 2 π i N m n {\ displaystyle a_ {N} ^ {mn} = e ^ {- {\ frac {2 \ pi i} {N}} mn}} 
дискретне перетворення можна виразити як суму двох частин: суму парних індексів m = 2 n {\ displaystyle m = {2n}} 
і суму непарних індексів m = 2 n + 1 {\ displaystyle m = {2n + 1}} 
:
X m = Σ n = 0 N - 1 xna N mn = Σ n = 0 N / 2 - 1 x 2 na N 2 nm + Σ n = 0 N / 2 - 1 x 2 n + 1 a N (2 n + 1) m {\ displaystyle x_ {m} = \ sum _ {n = 0} ^ {N-1} x_ {n} a_ {N} ^ {mn} = \ sum _ {n = 0} ^ {N / 2-1} x_ {2n} a_ {N} ^ {2nm} + \ sum _ {n = 0} ^ {N / 2-1} x_ {2n + 1} a_ {N} ^ {(2n + 1) m}} 
.
Коефіцієнти a N 2 n m {\ displaystyle a_ {N} ^ {2nm}} 
і a N (2 n + 1) m {\ displaystyle a_ {N} ^ {(2n + 1) m}} 
можна переписати таким чином:
a N 2 nm = e (- 2 π i 2 mn N) = e (- 2 π imn N / 2) = a N / 2 nm {\ displaystyle a_ {N} ^ {2nm} = e ^ {\ left ( -2 \ pi i {\ frac {2mn} {N}} \ right)} = e ^ {\ left (-2 \ pi i {\ frac {mn} {N / 2}} \ right)} = a_ { N / 2} ^ {nm}} 
a N (2 n + 1) m = e (- 2 π im N) a N / 2 nm {\ displaystyle a_ {N} ^ {(2n + 1) m} = e ^ {\ left (-2 \ pi i {\ frac {m} {N}} \ right)} a_ {N / 2} ^ {nm}} 
В результаті:
X m = Σ n = 0 N / 2 - 1 x 2 na N / 2 nm + e - 2 π i N m Σ n = 0 N / 2 - 1 x 2 n + 1 a N / 2 nm {\ displaystyle X_ {m} = \ sum _ {n = 0} ^ {N / 2-1} x_ {2n} a_ {N / 2} ^ {nm} + e ^ {- {\ frac {2 \ pi i} {N }} m} \ sum _ {n = 0} ^ {N / 2-1} x_ {2n + 1} a_ {N / 2} ^ {nm}} 
Обчислення цього виразу можна спростити, використовуючи:
В результаті спрощень, позначивши дискретне перетворення Фур'є парних індексів x 2 m {\ displaystyle x_ {2m}} 
через E m {\ displaystyle E_ {m}} 
і перетворення непарних індексів x 2 m + 1 {\ displaystyle x_ {2m + 1}} 
через O m {\ displaystyle O_ {m}} 
, Для 0 ⩽ m <N 2 {\ displaystyle 0 \ leqslant m <{\ frac {N} {2}}} 
виходить:
X m = E m + e - 2 π i N m O m X m + N 2 = E m - e - 2 π i N m O m {\ displaystyle {\ begin {matrix} X_ {m} & = & E_ { m} + e ^ {- {\ frac {2 \ pi i} {N}} m} O_ {m} \\ X_ {m + {\ frac {N} {2}}} & = & E_ {m} -e ^ {- {\ frac {2 \ pi i} {N}} m} O_ {m} \ end {matrix}}} 
Даний запис є базою алгоритму Кулі - Тьюки з основою 2 для обчислення швидкого перетворення Фур'є, тобто дискретне перетворення від вектора, що складається з N {\ displaystyle N} відліків, приведено до лінійної комбінації двох дискретних перетворень Фур'є від N 2 {\ displaystyle {\ frac {N} {2}}} 
відліків, і, якщо для початкової задачі потрібно N 2 {\ displaystyle N ^ {2}} 
операцій, то для отриманої композиції - N 2 2 {\ displaystyle {\ frac {N ^ {2}} {2}}} 
(За рахунок повторного використання проміжних результатів обчислень E m {\ displaystyle E_ {m}} і O m {\ displaystyle O_ {m}} ). Якщо N {\ displaystyle N} є ступенем двох, то цей поділ можна продовжувати рекурсивно до тих пір, поки не доходить до двухточечного перетворення Фур'є, яке обчислюється за такими формулами:
{X 0 = x 0 + x 1 X 1 = x 0 - x 1 {\ displaystyle {\ begin {cases} X_ {0} = x_ {0} + x_ {1} \\ X_ {1} = x_ {0 } -x_ {1} \ end {cases}}} 
При рекурсивном розподілі дискретного перетворення Фур'є від N {\ displaystyle N} вхідних значень на суму 2 дискретних перетворень по N / 2 {\ displaystyle N / 2} 
вхідних значень складність алгоритму стає рівною O (N log (N)) {\ displaystyle O (N \ log (N))} .
- Нуссбаумер Г. Швидке перетворення Фур'є і алгоритми обчислення згорток. - М.: Радио и связь, 1985.
