Восток Маркетинг


Статьи

WikiZero - Швидке перетворення Фур'є

  1. Висновок перетворення з дискретного [ правити | правити код ]

open wikipedia design.

Швидке перетворення Фур'є (БПФ, FFT) - алгоритм прискореного обчислення дискретного перетворення Фур'є , Що дозволяє отримати результат за час, менший ніж O (N 2) {\ displaystyle O (N ^ {2})} Швидке перетворення Фур'є (БПФ, 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}} Алгоритм можна застосувати до будь комутативним асоціативним   кільцям   з одиницею, частіше застосовують до полю   комплексних чисел   (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}))} При застосуванні основного алгоритму дискретне перетворення Фур'є може бути виконано 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))}   дій дій при 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}} Дискретне перетворення Фур'є перетворює набір чисел a 0, в набір чисел 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})} 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 k i q = ε N / q k i {\ displaystyle \ varepsilon _ {N} ^ {kiq} = \ varepsilon _ {N / q} ^ {ki}}   і N / q = p {\ displaystyle N / q = p}   , Остаточна запис: і 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})} 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}} Далі обчислюється кожне 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)}   операцій , Де 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}} Далі вважається 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 = 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} Алгоритм швидкого перетворення Фур'є логічно застосовувати для 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)} Швидкість алгоритму (N = p q) {\ displaystyle (N = pq)}   : :

  1. p »q ⟶ O (N p) {\ displaystyle p \ gg q \ longrightarrow O (Np)}
  2. p ~ q ⟶ O (N q) {\ displaystyle p \ sim q \ longrightarrow O (Nq)}
  3. p «q ⟶ O (N q) {\ displaystyle p \ ll q \ longrightarrow O (Nq)}

Тобто число операцій при будь-якому розбитті N {\ displaystyle N} Тобто число операцій при будь-якому розбитті N {\ displaystyle N}   на два числа, є O (N c) {\ displaystyle O (Nc)}   , Де c = m a x (p, q) {\ displaystyle c = max (p, q)} на два числа, є O (N c) {\ displaystyle O (Nc)} , Де c = m a x (p, q) {\ displaystyle c = max (p, q)} .

Для зворотного перетворення Фур'є можна застосовувати алгоритм прямого перетворення Фур'є - потрібно лише використовувати ε - 1 {\ displaystyle \ varepsilon ^ {- 1}} Для зворотного перетворення Фур'є можна застосовувати алгоритм прямого перетворення Фур'є - потрібно лише використовувати ε - 1 {\ displaystyle \ varepsilon ^ {- 1}}   замість ε {\ displaystyle \ varepsilon}   (Або застосувати операцію комплексного сполучення спочатку до вхідних даних, а потім до результату, отриманого після прямого перетворення Фур'є), і остаточний результат поділити на N {\ displaystyle N} замість ε {\ 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}} 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}} Позначаючи 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}} 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} якщо покласти a ¯ i = 0 {\ displaystyle {\ bar {a}} _ {i} = 0}   при i ≥ N {\ displaystyle i \ geq N} при i ≥ N {\ displaystyle i \ geq N} .

Таким чином задача зведена до обчислення згортки , Але це можна зробити за допомогою трьох перетворень Фур'є для 2 k {\ displaystyle 2 ^ {k}} Таким чином задача зведена до обчислення   згортки   , Але це можна зробити за допомогою трьох перетворень Фур'є для 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} 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}} Обчислення всіх 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)}   дій і 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 N {\ displaystyle 2N}   і 2 k {\ displaystyle 2 ^ {k}} і 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}}} Наприклад, для обчислення швидкого перетворення Фур'є за алгоритмом Кулі - Тьюки з основою 2 для вектора x → {\ displaystyle {\ vec {x}}}   , Що складається з N {\ displaystyle N}   елементів: , Що складається з N {\ displaystyle N} елементів:

X → = A ^ x → {\ displaystyle {\ vec {X}} = {\ hat {A}} {\ vec {x}}} X → = A ^ x → {\ displaystyle {\ vec {X}} = {\ hat {A}} {\ vec {x}}}   , ,

з елементами A ^ {\ displaystyle {\ hat {A}}} з елементами 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}} 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 {\ displaystyle m = {2n}}   і суму непарних індексів m = 2 n + 1 {\ displaystyle m = {2n + 1}}   : і суму непарних індексів 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}} 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 m {\ displaystyle a_ {N} ^ {2nm}}   і a N (2 n + 1) m {\ displaystyle a_ {N} ^ {(2n + 1) m}}   можна переписати таким чином: і 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 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}} 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 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}} В результаті спрощень, позначивши дискретне перетворення Фур'є парних індексів 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}}}   виходить: через 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}}} 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} Даний запис є базою алгоритму Кулі - Тьюки з основою 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 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}}} {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} При рекурсивном розподілі дискретного перетворення Фур'є від N {\ displaystyle N}   вхідних значень на суму 2 дискретних перетворень по N / 2 {\ displaystyle N / 2}   вхідних значень складність алгоритму стає рівною O (N log ⁡ (N)) {\ displaystyle O (N \ log (N))} вхідних значень на суму 2 дискретних перетворень по N / 2 {\ displaystyle N / 2} вхідних значень складність алгоритму стає рівною O (N log ⁡ (N)) {\ displaystyle O (N \ log (N))} .

  • Нуссбаумер Г. Швидке перетворення Фур'є і алгоритми обчислення згорток. - М.: Радио и связь, 1985.

также можем предложить:
печать бланков и прайс-листов | печать визитных карточек (визиток)
изготовление папок и меню | изготовление блокнотов
печать листовок

Связаться с менеджером для оформления заказа:
тел.: +38 (062) 349-56-15, 348-62-20
моб.: +38 (095) 811-22-62, +38 (093) 665-38-06,
+38 (067) 17 44 103
факс: +38 (062) 332-28-98
e-mail: [email protected]
г. Донецк, ул. Артема, 41

   2010 © Восток Маркетинг Яндекс.Метрика