WikiDer > Cooley-Tukey FFT algoritmi

The Kuli-Tukey algoritminomi bilan nomlangan J. V. Kuli va Jon Tukey, eng keng tarqalgan tez Fourier konvertatsiyasi (FFT) algoritmi. Bu qayta ifodalaydi diskret Furye konvertatsiyasi (DFT) o'zboshimchalik bilan kompozit hajmi N = N₁N₂ xususida N₁ kichik DFT o'lchamlari N₂, rekursiv, hisoblash vaqtini O ga kamaytirish (N jurnal N) yuqori kompozitsion uchun N (silliq raqamlar). Algoritm muhimligi sababli, quyida tavsiflanganidek, o'ziga xos variantlar va amalga oshirish uslublari o'z nomlari bilan tanilgan.

Cooley-Tukey algoritmi DFTni kichik DFTlarga ajratganligi sababli, uni DFT uchun boshqa har qanday algoritm bilan o'zboshimchalik bilan birlashtirish mumkin. Masalan, Rader yoki Bluesteinniki algoritmidan Cooley-Tukey tomonidan buzib bo'lmaydigan katta asosiy omillarni boshqarish uchun foydalanish mumkin asosiy omil algoritmi ajratishda yuqori samaradorlik uchun foydalanish mumkin nisbatan asosiy omillar.

Algoritm, uning rekursiv qo'llanilishi bilan birga, tomonidan ixtiro qilingan Karl Fridrix Gauss. Kuli va Tukey 160 yildan keyin mustaqil ravishda uni qayta kashf etdilar va ommalashtirdilar.

Tarix

Ushbu algoritm, shu jumladan uning rekursiv qo'llanilishi, 1805 yilgacha ixtiro qilingan Karl Fridrix Gauss, traektoriyalarini interpolatsiya qilishda kim foydalangan asteroidlar Pallas va Juno, lekin uning ishi keng e'tirof etilmadi (faqat vafotidan keyin va keyin nashr etilgan) neo-lotin).^[1][2] Biroq, Gauss asimptotik hisoblash vaqtini tahlil qilmadi. 19-asr va 20-asr boshlarida turli xil cheklangan shakllar ham bir necha bor qayta kashf etildi.^[2] FFTlar keyinchalik ommalashib ketdi Jeyms Kuli ning IBM va Jon Tukey ning Prinston algoritmni ixtiro qilgan va uni kompyuterda qanday qilib qulay tarzda bajarishni tavsiflovchi maqolani 1965 yilda nashr etdi.^[3]

Xabarlarga ko'ra, Tukey ushbu g'oyani Prezident Kennedining Ilmiy maslahat qo'mitasining yig'ilish paytida aniqlash yo'llarini muhokama qilish paytida paydo bo'lgan. yadroviy qurol sinovlari ichida Sovet Ittifoqi mamlakat tashqarisida joylashgan seysmometrlardan foydalanish orqali. Ushbu datchiklar seysmologik vaqt qatorlarini yaratadi. Shu bilan birga, ushbu ma'lumotlarni tahlil qilish DFTni hisoblash uchun tezkor algoritmlarni datchiklar soni va vaqt davomiyligi talab qiladi. Ushbu vazifa yadroviy sinovlarni taqiqlash to'g'risidagi taklifni ratifikatsiya qilish uchun juda muhim edi, shuning uchun har qanday qonunbuzarliklar sovet muassasalariga tashrif buyurmasdan kerak bo'lganda aniqlanishi mumkin edi.^[4][5] Ushbu uchrashuvning yana bir ishtirokchisi, Richard Garvin IBM kompaniyasi ushbu usulning potentsialini tan oldi va Tukeyni Kuli bilan aloqada qildi, ammo Kuli asl maqsadini bilmasligiga ishonch hosil qildi. Buning o'rniga Kuliga bu 3-o'lchovli kristaldagi spin yo'nalishlarining davriyligini aniqlash uchun zarur ekanligini aytdi. Geliy-3. Keyinchalik Cooley va Tukey o'zlarining qo'shma maqolalarini nashr etdilar va bir vaqtning o'zida ishlab chiqilganligi sababli tezda qabul qilindi Analog-raqamli konvertorlar 300 kHz gacha bo'lgan tezlikda namuna olish imkoniyatiga ega.

Gauss xuddi shu algoritmni ta'riflagani (asimptotik narxini tahlil qilmasdan bo'lsa ham) Kuli va Tukeyning 1965 yilgi maqolasidan bir necha yil o'tgach amalga oshirildi.^[2] Ularning qog'ozi faqat ilhom manbai sifatida ko'rsatilgan I. J. Yaxshi hozirda nima deyiladi asosiy omil FFT algoritmi (PFA);^[3] Goodning algoritmi dastlab Cooley-Tukey algoritmiga teng deb hisoblangan bo'lsa-da, PFA bu juda boshqacha algoritm ekanligi tezda anglandi (faqat o'lchamdagi o'lchamlarda ishlaydi) nisbatan asosiy omillarga bog'liq va Xitoyning qoldiq teoremasi, Cooley-Tukey-da har qanday kompozit o'lchamlarni qo'llab-quvvatlashdan farqli o'laroq).^[6]

Radix-2 DIT ishi

A radix-2 o'z vaqtida yo'q qilish (DIT) FFT - Cooley-Tukey algoritmining eng sodda va eng keng tarqalgan shakli, ammo yuqori darajada optimallashtirilgan Cooley-Tukey dasturlari odatda quyida tavsiflangan algoritmning boshqa shakllaridan foydalanadi. Radix-2 DIT hajmi DFT ni ajratadi N o'lchamdagi ikkita DFTga (shu sababli "radix-2" nomi berilgan) N/ 2 har bir rekursiv bosqich bilan.

Diskret Furye konvertatsiyasi (DFT) quyidagi formula bilan aniqlanadi:

${ displaystyle X_ {k} = sum _ {n = 0} ^ {N-1} x_ {n} e ^ {- { frac {2 pi i} {N}} nk},}$

qayerda ${ displaystyle k}$ dan iborat bo'lgan butun son hisoblanadi ${ displaystyle 0}$ ga ${ displaystyle N-1}$.

Dastlab Radix-2 DIT juft indeksli kirishlarning DFTlarini hisoblab chiqadi${ displaystyle (x_ {2m} = x_ {0}, x_ {2}, ldots, x_ {N-2})}$va toq-indeksli kirishlar ${ displaystyle (x_ {2m + 1} = x_ {1}, x_ {3}, ldots, x_ {N-1})}$, so'ngra ikkita ketma-ketlikning DFTini hosil qilish uchun ushbu ikkita natijani birlashtiradi. Keyinchalik bu g'oyani amalga oshirish mumkin rekursiv umumiy ish vaqtini O ga kamaytirish (N jurnal N). Ushbu soddalashtirilgan shakl buni nazarda tutadi N a ikkitasining kuchi; namunaviy ochkolar soni N odatda dastur tomonidan erkin tanlanishi mumkin (masalan, namuna tezligini yoki oynani o'zgartirish, nolga to'ldirish va hk), bu ko'pincha muhim cheklov emas.

Radix-2 DIT algoritmi funksiyaning DFT-ni qayta tuzadi ${ displaystyle x_ {n}}$ ikki qismga bo'linadi: juft raqamli ko'rsatkichlar bo'yicha yig'indisi ${ displaystyle n = {2m}}$ va toq sonli ko'rsatkichlar bo'yicha yig'indisi ${ displaystyle n = {2m + 1}}$:

${ displaystyle { begin {matrix} X_ {k} & = & sum limitlar _ {m = 0} ^ {N / 2-1} x_ {2m} e ^ {- { frac {2 pi i } {N}} (2m) k} + sum limitlar _ {m = 0} ^ {N / 2-1} x_ {2m + 1} e ^ {- { frac {2 pi i} {N }} (2m + 1) k} end {matrix}}}$

Umumiy multiplikatorni omil qilish mumkin ${ displaystyle e ^ {- { frac {2 pi i} {N}} k}}$ quyidagi tenglamada ko'rsatilgandek, ikkinchi yig'indidan. Shunda aniqki, ikkala yig'indilar juft indekslangan qismning DFT hisoblanadi ${ displaystyle x_ {2m}}$ va toq indeksli qismning DFT-si ${ displaystyle x_ {2m + 1}}$ funktsiyasi ${ displaystyle x_ {n}}$. DFT-ni belgilang Even-indekslangan yozuvlar ${ displaystyle x_ {2m}}$ tomonidan ${ displaystyle E_ {k}}$ va DFT Odd-indekslangan yozuvlar ${ displaystyle x_ {2m + 1}}$ tomonidan ${ displaystyle O_ {k}}$ va biz quyidagilarni olamiz:

${ displaystyle { begin {matrix} X_ {k} = underbrace { sum limit _ _ m = 0} ^ {N / 2-1} x_ {2m} e ^ {- { frac {2 pi i} {N / 2}} mk}} _ { mathrm {DFT ; of ; even-indexed ; part ; of ;} x_ {n}} {} + e ^ {- { frac { 2 pi i} {N}} k} underbrace { sum limitlar _ {m = 0} ^ {N / 2-1} x_ {2m + 1} e ^ {- { frac {2 pi i } {N / 2}} mk}} _ { mathrm {DFT ; of ; tod-indexed ; part ; of ;} x_ {n}} = E_ {k} + e ^ {- { frac {2 pi i} {N}} k} O_ {k}. end {matrix}}}$

Rahmat kompleks eksponentning davriyligi, ${ displaystyle X_ {k + { frac {N} {2}}}}$ dan ham olinadi ${ displaystyle E_ {k}}$ va ${ displaystyle O_ {k}}$:

${ displaystyle { begin {aligned} X_ {k + { frac {N} {2}}} & = sum limit _ {m = 0} ^ {N / 2-1} x_ {2m} e ^ { - { frac {2 pi i} {N / 2}} m (k + { frac {N} {2}})} + e ^ {- { frac {2 pi i} {N}} ( k + { frac {N} {2}})} sum limitlar _ {m = 0} ^ {N / 2-1} x_ {2m + 1} e ^ {- { frac {2 pi i} {N / 2}} m (k + { frac {N} {2}})} & = sum limitlar _ {m = 0} ^ {N / 2-1} x_ {2m} e ^ { - { frac {2 pi i} {N / 2}} mk} e ^ {- 2 pi mi} + e ^ {- { frac {2 pi i} {N}} k} e ^ { - pi i} sum limitlar _ {m = 0} ^ {N / 2-1} x_ {2m + 1} e ^ {- { frac {2 pi i} {N / 2}} mk} e ^ {- 2 pi mi} & = sum limitlar _ {m = 0} ^ {N / 2-1} x_ {2m} e ^ {- { frac {2 pi i} {N / 2}} mk} -e ^ {- { frac {2 pi i} {N}} k} sum limitlar _ {m = 0} ^ {N / 2-1} x_ {2m + 1} e ^ {- { frac {2 pi i} {N / 2}} mk} & = E_ {k} -e ^ {- { frac {2 pi i} {N}} k} O_ {k} end {hizalangan}}}$

Qayta yozishimiz mumkin ${ displaystyle X_ {k}}$ kabi:

${ displaystyle { begin {matrix} X_ {k} & = & E_ {k} + e ^ {- { frac {2 pi i} {N}} {k}} O_ {k} X_ {k + { frac {N} {2}}} & = & E_ {k} -e ^ {- { frac {2 pi i} {N}} {k}} O_ {k} end {matrix}}}$

Uzunlik DFT ni ifodalovchi bu natija N ikki DFT o'lchamlari bo'yicha rekursiv ravishda N/ 2, radix-2 DIT tez Fourier konvertatsiyasining yadrosi. Algoritm bir nechta DFT natijalarini hisoblash uchun oraliq hisoblash natijalarini qayta ishlatib, tezligini oshiradi. Yakuniy natijalar +/− kombinatsiyasi orqali olinishini unutmang ${ displaystyle E_ {k}}$ va ${ displaystyle O_ {k} exp (-2 pi ik / N)}$, bu shunchaki hajmi-2 DFT (ba'zan a deb ham nomlanadi kelebek shu nuqtai nazardan); bu quyida keltirilgan kattaroq radikallarga umumlashtirilganda, hajmi-2 DFT o'rniga kattaroq DFT (uning o'zi FFT bilan baholanishi mumkin) bilan almashtiriladi.

Uchun ma'lumotlar oqimi diagrammasi N= 8: o'z vaqtida rad etilgan radix-2 FFT uzunlikni buzadi -N DFT ikki uzunlikka -N/ 2 DFT, so'ngra "butterfly" operatsiyalari deb nomlangan ko'p o'lchamdagi 2 DFTlardan tashkil topgan birlashma bosqichi (ma'lumotlar oqimi diagrammasi shakli tufayli shunday deyilgan).

Bu jarayon umumiy texnikaning namunasidir algoritmlarni ajratish va yutish; ko'pgina an'anaviy dasturlarda aniq rekursiyadan qochishadi va buning o'rniga hisoblash daraxtini bosib o'tishadi kenglik - birinchi moda.

Yuqoridagi o'lchamning qayta ifodasiN DFT ikki o'lchovliN/ 2 DFT ba'zida Danielson–Lanczos lemma, chunki 1942 yilda bu ikki muallif tomonidan shaxsiyat qayd etilgan^[7] (ta'sirlangan Runge 1903 ish^[2]). Ular o'zlarining lemmalarini "orqaga" rekursiv usulda takroriy ravishda qo'lladilar ikki baravar transformatsiya spektri yaqinlashguncha DFT kattaligi (garchi ular buni anglamagan bo'lsa ham chiziqli [ya'ni, buyurtma N jurnalN] ular erishgan asimptotik murakkablik). Danielson-Lanczos ishi keng tarqalishini oldindan belgilab qo'ygan mexanik yoki elektron hisoblash mashinalari va talab qilinadi qo'lda hisoblash (ehtimol kabi mexanik yordam bilan qo'shish mashinalari); ular 64 DFT hajmdagi hisoblash uchun 140 daqiqa hisoblash vaqti haqida xabar berishdi haqiqiy kirish 3-5 ta muhim raqamga. Cooley and Tukey ning 1965 yildagi maqolasida 2048 o'lchamdagi DFT kompleksi uchun 0,02 minut ish vaqti ko'rsatilgan. IBM 7094 (ehtimol 36-bitda) bitta aniqlik, ~ 8 ta raqam).^[3] Vaqtni operatsiyalar soniga qarab hisoblab chiqsak, bu taxminan 800,000 tezlashtirish koeffitsientiga to'g'ri keladi. (Qo'lni hisoblash uchun vaqtni istiqbolli qilib qo'yish uchun 64-o'lchov uchun 140 minut o'rtacha suzuvchi nuqta operatsiyasiga o'rtacha 16 soniya to'g'ri keladi, ularning 20% ​​ko'paytiriladi).

Psevdokod

Yilda psevdokod, quyidagi protsedura yozilishi mumkin:^[8]

X0,...,N−1 ← ditfft2(x, N, s):             DFT ning (x0, xs, x2s, ..., x(N-1)s):    agar N = 1 keyin        X0 ← x0                                      ahamiyatsiz o'lcham-1 DFT tayanch qutisi    boshqa        X0,...,N/2−1 ← ditfft2(x, N/2, 2s)             DFT ning (x0, x2s, x4s, ...)        XN/2,...,N−1 ← ditfft2(x+ s, N/2, 2s)           DFT ning (xs, xs+2s, xs+4s, ...)        uchun k = 0 dan N/2−1 qil                        ikki yarimning DFTlarini to'liq DFTga birlashtiring:            t ← Xk            Xk ← t + exp (-2πmen k/N) Xk+N/2            Xk+N/2 ← t - exp (−2π.)men k/N) Xk+N/2        uchun tugatish    tugatish agar

Bu yerda, ditfft2(x,N, 1), hisoblab chiqadi X= DFT (x) joydan tashqarida radix-2 DIT FFT tomonidan, bu erda N tamsayı kuchi 2 va s= 1 bu qadam kirish x qator. x+s bilan boshlangan qatorni bildiradi x_s.

(Natijalar to'g'ri tartibda X va bundan keyin yo'q bit-teskari almashtirish zarur; tez-tez aytib o'tilgan alohida bitni qaytarish bosqichining zaruriyati faqat quyida tavsiflangan ba'zi bir algoritmlar uchun paydo bo'ladi.)

Yuqori samaradorlikdagi FFT dasturlari ushbu oddiy psevdokod bilan taqqoslaganda, bunday algoritmni amalga oshirishda ko'plab o'zgartirishlarni amalga oshiradi. Masalan, dan kattaroq tayanch kassadan foydalanish mumkin N= 1 dan amortizatsiya rekursiya uchun qo'shimcha xarajatlar twiddle omillari ${ displaystyle exp [-2 pi ik / N]}$ oldindan hisoblash mumkin va undan kattaroq radislar ko'pincha ishlatiladi kesh sabablar; shu va boshqa optimallashtirishlar birgalikda ishlash ko'rsatkichlarini kattaroq tartibda yaxshilashi mumkin.^[8] (Ko'pgina o'quv qo'llanmalarida chuqurlik birinchi rekursiya butunlay noreursiv foydasiga yo'q qilinadi kenglik - birinchi yondashuv, ammo chuqurlik bo'yicha birinchi rekursiya yaxshiroq ekanligi ta'kidlangan xotira joyi.^[8][9]) Ushbu fikrlarning bir nechtasi quyida batafsilroq tavsiflangan.

Fikr

Cooley-Tukey FFT-ning umumiy faktorizatsiya qilishning asosiy bosqichi 1-darajali DFTni 2-darajali DFTga o'xshash narsa sifatida qayta izohlash sifatida qaralishi mumkin. Uzunlikning 1 o'lchovli qatori N = N₁N₂ 2d sifatida qayta talqin qilinadi N₁×N₂ matritsa saqlangan ustunli buyurtma. Ulardan biri kichik o'lchamdagi DFTlarni bajaradi N₂ yo'nalishi (qo'shni bo'lmagan yo'nalish), so'ngra fazaviy omillarga ko'paytiriladi (twiddle omillari) va nihoyat 1d DFTlarni N₁ yo'nalish. Transpozitsiya bosqichi o'rtada, bu erda ko'rsatilgandek yoki boshida yoki oxirida amalga oshirilishi mumkin. Bu kichikroq transformatsiyalar uchun rekursiv ravishda amalga oshiriladi.

Qator va ustunli buyruqlar tasviri

Umuman olganda, Cooley-Tukey algoritmlari kompozitsion kattalikdagi DFTni rekursiv ravishda qayta ifodalaydi N = N₁N₂ kabi:^[10]

1. Amalga oshirish N₁ DFT o'lchamlari N₂.
2. Kompleks bo'yicha ko'paytiring birlikning ildizlari (ko'pincha twiddle omillari).
3. Amalga oshirish N₂ DFT o'lchamlari N₁.

Odatda, ham N₁ yoki N₂ kichik omil (emas albatta bosh), deb nomlangan radix (bu rekursiya bosqichlari o'rtasida farq qilishi mumkin). Agar N₁ radiks bo'lib, u a deb nomlanadi o'z vaqtida yo'q qilish (DIT) algoritmi, agar shunday bo'lsa N₂ radiks, u shunday chastotada parchalanish (DIF, shuningdek, Sande-Tukey algoritmi deb ataladi). Yuqorida keltirilgan versiya radix-2 DIT algoritmi edi; yakuniy ifodada, g'alati konvertatsiyani ko'paytirish fazasi twiddle faktor va +/- kombinatsiyasi (kelebek) juft va toq transformatsiyalarning kattaligi-2 DFT. (Radiksning kichik DFT-si ba'zan a deb nomlanadi kelebek, shakli tufayli deb nomlangan ma'lumotlar oqimining diagrammasi radix-2 holati uchun.)

O'zgarishlar

Cooley-Tukey algoritmida boshqa ko'plab farqlar mavjud. Aralash radiusli dasturlar kompozit o'lchamlarni O (odatda har doim ham emas) ishlatadigan ikkitadan tashqari turli xil (odatda kichik) omillar bilan ishlaydi.N²) rekursiyaning asosiy asosiy holatlari algoritmi (bundan tashqari N jurnalN kabi asosiy asosiy holatlar algoritmi Raderyoki Bluesteinalgoritmi). Split radix radix 2 ning birinchi konvertatsiyasi hech qanday burilish omilini talab qilmasligini ishlatib, ikkita kuchning o'lchamlari bo'yicha ma'lum bo'lgan eng past arifmetik operatsiya soniga erishish uchun 2 va 4 radikallarni birlashtiradi,^[10] garchi so'nggi o'zgarishlarning soni pastroq bo'lsa ham.^[11][12] (Hozirgi kompyuterlarda ishlash ko'proq belgilanadi kesh va CPU quvuri qat'iy operatsiyalarni hisoblashdan ko'ra mulohazalar; yaxshi optimallashtirilgan FFT dasturlari ko'pincha katta hajmdagi radikallar va / yoki qattiq kodlangan bazaviy konvertlarni qo'llaydi.^[13]).

Cooley-Tukey algoritmiga qarashning yana bir usuli bu uning hajmini qayta ifodalashidir N sifatida bir o'lchovli DFT N₁ tomonidan N₂ chiqish matritsasi bo'lgan ikki o'lchovli DFT (ortiqcha dubllar) ko'chirildi. Ushbu barcha transpozitsiyalarning aniq natijasi radix-2 algoritmi uchun kirish (DIF) yoki chiqish (DIT) indekslarining biroz teskari tomoniga to'g'ri keladi. Agar kichkina radiusdan foydalanish o'rniga, taxminan radius ishlatilsa √N va aniq kirish / chiqish matritsasi transpozitsiyalari, a deb nomlanadi to'rt bosqichli algoritm (yoki olti bosqichli, transpozitsiyalar soniga qarab), dastlab xotira joyini yaxshilash uchun taklif qilingan,^[14][15] masalan. keshni optimallashtirish uchun yoki yadrodan tashqari operatsiya bo'lib, keyinchalik u eng maqbul ekanligi ko'rsatildi keshni unutadigan algoritm.^[16]

Umumiy Cooley-Tukey faktorizatsiyasi indekslarni qayta yozadi k va n kabi ${ displaystyle k = N_ {2} k_ {1} + k_ {2}}$ va ${ displaystyle n = N_ {1} n_ {2} + n_ {1}}$navbati bilan, qaerda indekslar k_a va n_a 0 dan boshlash ..N_a-1 (uchun a 1 yoki 2). Ya'ni, bu kirishni qayta indekslaydi (n) va chiqish (k) kabi N₁ tomonidan N₂ ikki o'lchovli massivlar katta-mayor va asosiy tartibnavbati bilan; bu indekslashlar orasidagi farq - yuqorida aytib o'tilganidek, transpozitsiya. Ushbu qayta indeksatsiya DFT formulasiga almashtirilganda nk, ${ displaystyle N_ {1} n_ {2} N_ {2} k_ {1}}$ o'zaro bog'liqlik yo'qoladi (uning eksponentligi birlik), qolgan terminlar beradi

${ displaystyle X_ {N_ {2} k_ {1} + k_ {2}} = sum _ {n_ {1} = 0} ^ {N_ {1} -1} sum _ {n_ {2} = 0 } ^ {N_ {2} -1} x_ {N_ {1} n_ {2} + n_ {1}} e ^ {- { frac {2 pi i} {N_ {1} N_ {2}}} cdot (N_ {1} n_ {2} + n_ {1}) cdot (N_ {2} k_ {1} + k_ {2})}}$

${ displaystyle = sum _ {n_ {1} = 0} ^ {N_ {1} -1} chap [e ^ {- { frac {2 pi i} {N_ {1} N_ {2}} } n_ {1} k_ {2}} o'ng] chap ( sum _ {n_ {2} = 0} ^ {N_ {2} -1} x_ {N_ {1} n_ {2} + n_ {1 }} e ^ {- { frac {2 pi i} {N_ {2}}} n_ {2} k_ {2}} o'ng) e ^ {- { frac {2 pi i} {N_ { 1}}} n_ {1} k_ {1}}}$

${ displaystyle = sum _ {n_ {1} = 0} ^ {N_ {1} -1} chap ( sum _ {n_ {2} = 0} ^ {N_ {2} -1} x_ {N_ {1} n_ {2} + n_ {1}} e ^ {- { frac {2 pi i} {N_ {2}}} n_ {2} k_ {2}} o'ng) e ^ {- { frac {2 pi i} {N_ {1} N_ {2}}} n_ {1} (N_ {2} k_ {1} + k_ {2})}}$.

bu erda har bir ichki summa o'lchamdagi DFT N₂, har bir tashqi yig'indisi hajmi DFT N₁, va [...] qavsli muddat twiddle omilidir.

Ixtiyoriy radius r Kuli ham, Tukey ham ko'rsatganidek (shuningdek, aralash radikallar) ishlatilishi mumkin^[3] shuningdek Gauss (radix-3 va radix-6 qadamlariga misollar keltirgan).^[2] Kuli va Tukey dastlab radikal kapalak uchun O (r²) ishlaydi va shuning uchun radius uchun murakkablikni hisobladi r O bo'lishr² N/r jurnal_rN) = O (N jurnal₂(N) r/ log₂r); ning qiymatlarini hisoblashdan r/ log₂r ning tamsayı qiymatlari uchun r 2 dan 12 gacha optimal radius 3 (eng yaqin butun son) ga teng e, bu esa minimallashtiradi r/ log₂r).^[3][17] Ammo bu tahlil noto'g'ri edi: radix-butterfly ham DFT bo'lib, F (FFT) algoritmi orqali O (r jurnal r) operatsiyalar, shuning uchun radix r aslida O murakkabligida bekor qilinadi (r log (r) N/r jurnal_rN) va optimal r yanada murakkab mulohazalar bilan belgilanadi. Amalda juda katta r (32 yoki 64), masalan, samarali foydalanish uchun muhimdir. ko'p sonli protsessor registrlari zamonaviy protsessorlarda,^[13] va hatto cheksiz radius r=√N shuningdek, O ga erishadi (N jurnalN) murakkablik va katta uchun nazariy va amaliy afzalliklarga ega N yuqorida aytib o'tilganidek.^[14][15][16]

Ma'lumotlarni qayta tartiblash, bitlarni almashtirish va joyidagi algoritmlar

Yuqoridagi DFT-ning mavhum Kuli-Tukey faktorizatsiyasi ba'zi shakllarda algoritmning barcha tatbiq etilishlariga taalluqli bo'lsa-da, FFTning har bir bosqichida ma'lumotlarni buyurtma qilish va ularga kirish usullarida juda xilma-xillik mavjud. An-ni yaratish muammosi alohida qiziqish uyg'otadi joyidagi algoritm bu faqat O (1) yordamchi xotiradan foydalangan holda, kirish ma'lumotlarini chiqish ma'lumotlari bilan yozib qo'yadi.

Eng taniqli qayta tartiblash texnikasi aniq o'z ichiga oladi bitni qaytarish joyidagi radix-2 algoritmlari uchun. Bitni qaytarish bo'ladi almashtirish bu erda indeksdagi ma'lumotlar n, yozilgan ikkilik raqamlar bilan b₄b₃b₂b₁b₀ (masalan, uchun 5 ta raqam N= 32 kirish), teskari raqamlar bilan indeksga o'tkaziladi b₀b₁b₂b₃b₄ . Yuqorida keltirilgan radix-2 DIT algoritmining so'nggi bosqichini ko'rib chiqing, bu erda chiqish kirish joyida yoziladi: qachon ${ displaystyle E_ {k}}$ va ${ displaystyle O_ {k}}$ hajmi-2 DFT bilan birlashtirilib, ushbu ikkita qiymat natijalar ustiga yoziladi. Biroq, ikkita chiqish qiymati birinchi va ikkinchisiga to'g'ri kelishi kerak yarmi ga mos keladigan chiqish massivining eng muhim bit b₄ (uchun N= 32); Holbuki, ikkita kirish ${ displaystyle E_ {k}}$ va ${ displaystyle O_ {k}}$ ga mos keladigan juft va toq elementlarda o'zaro bog'langan kamida muhim bit b₀. Shunday qilib, mahsulotni to'g'ri joyda olish uchun, b₀ o'rnini egallashi kerak b₄ va indeks bo'ladi b₀b₄b₃b₂b₁. Va keyingi rekursiv bosqich uchun ushbu eng kam 4 ta bit bo'ladi b₁b₄b₃b₂, Agar siz radix-2 DIT algoritmining barcha rekursiv bosqichlarini qo'shsangiz, barchasi bitlarni teskari aylantirish kerak va shu sababli kirishni oldindan qayta ishlash kerak (yoki tartibda ishlab chiqarilgan mahsulotni olish uchun biroz teskari aylantirish bilan). (Agar har bir o'lcham-N/ 2 subtransform - bu qo'shni ma'lumotlar, DIT ustida ishlash kiritish bit-reversal orqali oldindan qayta ishlanadi.) Shunga mos ravishda, agar siz barcha bosqichlarni teskari tartibda bajaradigan bo'lsangiz, siz keyingi ishlov berishda bitni teskari aylantirish bilan radix-2 DIF algoritmini olasiz (yoki mos ravishda oldindan qayta ishlash).

Ushbu algoritmda ishlatiladigan logaritma (log) asosiy 2-logaritma hisoblanadi.

Quyida bit-reversal permutation yordamida amalga oshirilgan takrorlanadigan radix-2 FFT algoritmi uchun psevdokod mavjud.^[18]

algoritm iterative-fft bu    kiritish: Array a ning n murakkab qiymatlar, bu erda n 2 kuchga ega. chiqish: Array A a ning DFT. bit-teskari nusxa (a, A) n ← a. uzunlik uchun s = 1 ga log (n) qil        m ← 2s        ωm ← exp (-2π.)men/m)         uchun k = 0 ga n-1 tomonidan m qil            ω ← 1            uchun j = 0 ga m/2 – 1 qil                t ← ω A[k + j + m/2]                siz ← A[k + j]                A[k + j] ← siz + t                A[k + j + m/2] ← siz – t                ω ← ω ωm       qaytish A

Bit-teskari nusxa ko'chirish protsedurasi quyidagicha amalga oshirilishi mumkin.

algoritm bit-teskari nusxa (a,A) bu    kiritish: Array a ning n murakkab qiymatlar, bu erda n 2 kuchga ega. chiqish: Array A hajmi n.    n ← a. uzunlik uchun k = 0 ga n – 1 qil        A[rev (k)]: = a[k]

Shu bilan bir qatorda, ba'zi bir dasturlar (masalan, konvolyutsiya) bit-teskari ma'lumotlarda bir xil darajada ishlaydi, shuning uchun tabiiy tartibda yakuniy natijalarni olish uchun oldinga o'zgartirishni, ishlov berishni va keyin teskari o'zgartirishni hammasini bitni teskari o'zgartirmasdan amalga oshirish mumkin.

Biroq, ko'plab FFT foydalanuvchilari tabiiy buyurtma natijalarini afzal ko'rishadi va bitni qaytarishning alohida, aniq bosqichi hisoblash vaqtiga beparvo ta'sir ko'rsatishi mumkin,^[13] bitni almashtirish O da bajarilishi mumkin bo'lsa ham (N) vaqt va ko'plab tadqiqotlarning predmeti bo'lgan.^[19][20][21] Shuningdek, almashtirish radix-2 holatida biroz teskari bo'lsa-da, odatda, aralash radiusli ish uchun o'zboshimchalik bilan (aralash bazali) raqamli teskari bo'ladi va almashtirish algoritmlarini amalga oshirish yanada murakkablashadi. Bundan tashqari, ko'plab apparat arxitekturalarida FFT algoritmining oraliq bosqichlarini ketma-ket (yoki hech bo'lmaganda lokalizatsiya qilingan) ma'lumotlar elementlarida ishlashlari uchun qayta buyurtma qilish maqsadga muvofiqdir. Shu maqsadda, Cooley-Tukey algoritmi uchun bitning alohida o'zgarishini talab qilmaydigan va / yoki oraliq bosqichlarda qo'shimcha almashtirishlarni o'z ichiga oladigan bir qator muqobil dasturlar ishlab chiqilgan.

Agar shunday bo'lsa, muammo juda soddalashtirilgan joydan tashqarida: chiqish massivi kirish massividan farq qiladi yoki unga teng ravishda teng o'lchamdagi yordamchi massiv mavjud. The Stokxem avtomatik saralash algoritm^[22][23] FFTning har bir bosqichini joyidan tashqarida bajaradi, odatda ikki qator orasida oldinga va orqaga yozib, har bir bosqich bilan indekslarning bitta "raqamini" o'tkazadi va ayniqsa mashhur bo'lgan SIMD me'morchilik.^[23][24] SIMD uchun yanada katta potentsial afzalliklar (ketma-ket kirish imkoniyatlari) taklif qilingan Pease algoritm,^[25] shuningdek, har bir bosqichda o'z o'rnini o'zgartiradi, ammo bu usul alohida bit / raqamli o'zgarishni va O (N jurnal N) saqlash. Bundan tashqari, Cooley-Tukey faktorizatsiya ta'rifini to'g'ridan-to'g'ri aniq (chuqurlik birinchi) rekursiya va mayda radikallar, ular tabiiy ravishda joyidan chiqib ketishni ishlab chiqaradilar, bu alohida almashtirish bosqichisiz (yuqoridagi psevdokodda bo'lgani kabi) va shunday bo'lishi mumkin keshni unutish tizimlari bo'yicha mahalliy imtiyozlar ierarxik xotira.^[9][13][26]

Yordamchi omborxonasiz va alohida raqamli teskari o'tishsiz joyida algoritmlar uchun odatiy strategiya oraliq bosqichlarda kichik matritsali transpozitsiyalarni (individual juft raqamlarni almashtiradigan) o'z ichiga oladi, bu radius kapalaklari bilan birlashtirib, o'tish sonini kamaytirish uchun. ma'lumotlar.^{[13][27][28][29][30]}

Adabiyotlar

Tashqi havolalar

• "Tez Fourier konvertatsiyasi - FFT". Cooley-Tukey texnikasi. Maqola. 10. C ++ da oddiy, pedagogik radix-2 algoritmi
• "KISSFFT". GitHub. S-da oddiy aralash radiusli Kuli-Tukey dasturi
• Dsplib kuni GitHub
• "FFT algoritmining vaqtdagi radiks-2 dekimatsiyasi". Arxivlandi asl nusxasi 2017 yil 31 oktyabrda. "Algoritm BPF po osnovaniyu dva s prorejivaniem po vremeni" (rus tilida).
• "Frequency FFT algoritmidagi Radix-2 dekimatsiyasi". Arxivlandi asl nusxasi 2017 yil 14-noyabrda. "Algoritm BPF po osnovaniyu dva s prorejivaniem po chastote" (rus tilida).