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


Статьи

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.

Новости

Методы арт терапии
Арт терапия возникла в 30-е годы нашего века. Первый урок применения арт терапии относится к попыткам коррекции эмоционально-личностных проблем детей, эмигрировавших в США из Германии во время второй

Minecraft on ubuntu
Minecraft хорошо работает не только лишь под Windows, да и под Linux, но установка тут будет несколько труднее и не привычнее чем обычно. Все деяния, которые буду описаны ниже, совершались на операционной

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

Что можно купить маме на новый
Охото поделиться с вами мыслями — как сделать подарок маме своими руками на денек рождения, на денек мамы, на 8 марта либо на хоть какой другой праздничек. Естественно, хотелось бы, чтобы все помнили

Mysql database free download
Используя материалы этой статьи, можно без заморочек установить сервер базы данных MySQL на компьютер под управлением Windows XP, Windows Vista, Windows 7. Запустив файл дистрибутива MySQL жмем кнопку

Штрафы гибдд узнать задолженность
Сервис Штрафов Нет работает более 3-х лет, за этот период времени он отыскал более 1 000 000 штрафов ГИБДД и

Как создать в майнкрафте портал
Ведро можно сделать из трёх железных слитков, а с поиском источников воды заморочек появиться не должно. Рамка портала в Рай создаётся по тому же принципу, что и портал в Ад, а потом вовнутрь заливается

Тц green
Здрасти! Мы рады приветствовать Вас на веб-сайте Торгового центра «ГРИН». Торговый центр «ГРИН» открыт в 2008 г. и за этот период времени отлично зарекомендовал себя у неизменных покупателей, живущих

Креативные свадебные платья
Свадьба для жены – это повод снова обворожить возлюбленного и блеснуть перед гостями и всеми окружающими собственной красотой. Но если в ваши планы заходит шокировать всех своим возникновением, в том

Юнкер 4 купить
Этот Юнкер, про который далее буду говорить, был приобретен на местном форуме в разделе Купля-продажа пневматики. Он совсем не «верный», но на данный момент у него нет утечек и после переделки он стал

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

Связаться с менеджером для оформления заказа:
тел.: +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 © Восток Маркетинг Яндекс.Метрика