Ievads ātrai Furjē pārveidošanai

Statistical Programming with R by Connor Harris (Jūlijs 2019).

$config[ads_text] not found
Anonim

Ievads ātrai Furjē pārveidošanai


Šajā rakstā tiks apskatīti decimācijas laika FFT algoritmu pamati.

Diskretizētā Furjē transformācija (DFT) ir viens no spēcīgākajiem ciparu signālu apstrādes instrumentiem. DFT ļauj mums ērti analizēt un projektēt sistēmas frekvences jomā; tomēr DFT daudzpusības daļa ir saistīta ar faktu, ka ir efektīvi algoritmi, lai aprēķinātu secības DFT. Šo algoritmu klase tiek saukta par ātro Furjē pārveidošanu (FFT). Šajā rakstā vispirms tiks apskatīta skaitļošanas sarežģītība, tieši aprēķinot DFT, un pēc tam tā apspriedīs, kā FFT algoritmu klase, ti, laika nobīde FFT algoritmos, ievērojami samazina aprēķinu skaitu.

DPA tiešā aprēķina aprēķina sarežģītība

Kā iepriekš minēts, N-punkta DFT vienādojumu ierobežotas ilguma secībai, $ $ x (n) $ $, sniedz

$$ X (k) = \ sum \ limits_ (n = 0) ^ (N-1) {x (n) {{e} ^ {- j \ tfrac {2 \ pi} {N} kn}}} $

1. vienādojums

Apskatīsim, cik reizinājumu un papildinājumu ir nepieciešams, lai aprēķinātu secības DFT, izmantojot iepriekšminēto vienādojumu. Par katru DFT koeficientu $ $ X (k) $ $ mums vajadzētu aprēķināt $ $ N $ $ nosacījumus, tostarp $$ x (0) {{e} ^ {- j \ tfrac {2 \ pi} {N} k \ reizes 0}} $ $, $ $ x (1) {{e} ^ {- j \ tfrac {2 \ pi} {N} k \ reizes 1}} $ $, …, $ $ x (N- 1) {{e} ^ {- j \ tfrac {2 \ pi} {N} k \ times (N-1)}} $ $ un tad aprēķiniet summu. $ $ x (n) $ $ ir komplekss numurs kopumā, un tāpēc katram DFT produkcijas apjomam ir nepieciešami aptuveni $ $ N $ $ kompleksie reizinājumi un $ $ N-1 $ $ kompleksie papildinājumi. Vienai kompleksai reizināšanai pati ir nepieciešamas četras reālās reizināšanas un divi reāli papildinājumi. To var vienkārši pārbaudīt, ņemot vērā $$ d_1 = a_1 + jb_1 $$ reizinājumu ar $ $ d_2 = a_2 + jb_2 $$, kas noved pie

$ $ d_1d_2 = (a_1a_2-b_1b_2) + j (b_1a_2 + a_1b_2) $$

Turklāt kompleksai pievienošanai ir vajadzīgi divi reāli papildinājumi. Tāpēc katram DFT koeficientam nepieciešami $ $ 4N $ $ reālie reizināšanas un $ 2N + 2 (N-1) = 4N-2 $$ reāli papildinājumi. Lai iegūtu visus DFT koeficientus, mums ir jāaprēķina 1. līmenis visiem $ $ N $ $ vērtībām $$ k $ $, tādēļ N-punkta DFT analīzei ir nepieciešami $ $ 4N ^ 2 $ $ reālie reizinājumi un $ $ N ( 4N-2) $ $ reāli papildinājumi. Svarīgi ir tas, ka N-punkta DFT aprēķinu skaits ir proporcionāls $ $ N ^ 2 $ $, un tas var strauji pieaugt ar $ $ N $ $. 1. attēlā attēlota reālo reizinājumu skaits pret DFT garumu $ $ N $ $. Lai atrisinātu šo problēmu, ir izstrādāti vairāki algoritmi. Nākamajā iedaļā tiks iegūts viens no pamata aprēķināšanas algoritmiem.

1. attēlā redzamais reālais reizinājumu skaits N-punkta DFT.

FFT algoritmu decimēšana-in-time

FFT algoritmu galvenā ideja ir sadalīt N-punkta DFT mazāku garumu pārveidojumos. Piemēram, ja mēs izstrādājam hipotētisku algoritmu, kas var sadalīt 1024 punktu DFT divos 512 punktu DFT, mēs varam samazināt reālo reizinājumu skaitu no $ 4, 194, 304 $ $ līdz $ 2, 097, 152 $ $. Tas ir uzlabojums divreiz. Pārējā šī raksta ietvaros mēs pārskatīsim vienu no šiem algoritmiem, ko sauc par decimācijas laika FFT algoritmu.

Apskatīsim, kā mēs varam pārformulēt N-punkta DFT mazāka garuma DFT. Lai iegūtu labāku ieskatu algoritmā, mēs izskaidrosim procedūru, piemēram, izmantojot astoņu punktu DFT.

Astoņu punktu DFT izpēte

Pieņemsim, ka $ $ x (n) $ $ ir astoņu garuma secība. Izmantojot 1. vienādojumu, mēs varam atrast astoņu punktu DFT no $ $ x (n) $ $ kā

($) $ X \ left (k \ right) = x (0) {{e} ^ {- j \ tfrac {2 \ pi} {8} k \ times0}} + x (1) {{e} ^ j \ tfrac {2 \ pi} {8} k \ times1}} + x (2) {{e} ^ {- j \ tfrac {2 \ pi} {8} k \ times2}} + \ dots + x 7) {{e} ^ {- j \ tfrac {2 \ pi} {8} k \ times7}} $ $

2. vienādojums

Mūsu mērķis ir pārbaudīt iespēju pārrakstīt šo astoņu punktu DFT divu mazāku garumu DFT. Mēs redzam, ka DFT garums, $ $ N = 8 $ $ šajā gadījumā, tiek parādīts kā saucējs sarežģītajos eksponentos. Tas mūs noved pie domām, ka, ja mēs izvēlamies un grupē dažus vienādojuma nosacījumus tādā veidā, kas ļauj vienkāršot frakcijas $ $ - \ tfrac {j2 \ pi} {8} kn $$. Tādā veidā mēs varam izvilkt no mazāka garuma DFT no 2. vienādojuma. Piemēram, tā kā mūsu gadījumā $ $ N $ $ ir vienāds numurs, mēs pārbaudām visu terminu izvēli ar vienmērīgu izlases indeksu, ti, $ $ x (0) $ $, $ $ x (2) $$, $$ x (4) $ $ un $$ x (6) $ $. Tādējādi mums ir

$$ G \ left (k \ right) = x (0) {{e} ^ {- j \ tfrac {2 \ pi} {8} k \ times0}} + x (2) {{e} ^ j \ tfrac {2 \ pi} {8} k \ times2}} + x (4) {{e} ^ {- j \ tfrac {2 \ pi} {8} k \ times4}} + x (6) { {e} ^ {- j \ tfrac {2 \ pi} {8} k \ times6}} $ $

3. vienādojums

Pēc vienkāršotajām daļām kompleksos eksponentiālos iegūstam

$$ G \ left (k \ right) = x (0) {{e} ^ {- j \ tfrac {2 \ pi} {4} k \ times0}} + x (2) {{e} ^ j \ tfrac {2 \ pi} {4} k \ times1}} + x (4) {{e} ^ {- j \ tfrac {2 \ pi} {4} k \ times2}} + x (6) { {e} ^ {- j \ tfrac {2 \ pi} {4} k \ times3}} $ $

4. vienādojums

Salīdzinot 4. vienādojumu ar 1. vienādojumu, mēs novērojam, ka $ $ G (k) $ $ ir četrpunktu DFT no $ $ x (0) $$, $$ x (2) $$, $$ x (4) $ $ un $ $ x (6) $ $. Līdz šim mēs esam parādījuši, ka pusi no aprēķiniem 2. līmenī var aizstāt ar četru punktu DFT. Bet kā mēs varam vienkāršot pārējos aprēķinus. Pārējos terminus, kas atbilst nepāra indeksa paraugiem, norāda

$$ H_ {1} \ left (k \ right) = x (1) {{e} ^ {- j \ tfrac {2 \ pi} {8} k \ times1}} + x (3) {{e} ^ {- j \ tfrac {2 \ pi} {8} k \ times3}} + x (5) {{e} ^ {- j \ tfrac {2 \ pi} {8} k \ times5}} + x 7) {{e} ^ {- j \ tfrac {2 \ pi} {8} k \ times7}} $ $

5. vienādojums

Lai vienkāršotu frakcijas $ $ - \ tfrac {j2 \ pi} {8} kn $ $, varam vienkārši aprēķināt $ $ e ^ {- j \ tfrac {2 \ pi} {8} k} $ $ un iegūt

(X) (1) {{e} ^ {{e} ^ {{e} (3) {{e} ^ {- j \ tfrac {2 \ pi} {8} k \ times2}} + x (5) {{e} ^ {- j \ tfrac {2 \ pi} {8} k \ times4}} + x (7) {{e} ^ {- j \ tfrac {2 \ pi} {8} k \ times6} } \ labi) $ $

6. vienādojums

Tādējādi mums ir

(X) (1) {{e} ^ {{e} ^ {{e} (3) {{e} ^ {- j \ tfrac {2 \ pi} {4} k \ times1}} + x (5) {{e} ^ {- j \ tfrac {2 \ pi} {4} k \ times2}} + x (7) {{e} ^ {- j \ tfrac {2 \ pi} {4} k \ times3} } \ labi) $ $

7. vienādojums

Atkal, salīdzinot ar 1. vienādojumu, mēs novērojam, ka $ $ H_ {1} (k) $ $ iegūst, reizinot $ $ e ^ {- \ tfrac {j2 \ pi} {8} k} $ $ ar četrpunktu DFT no $ $ x (1) $ $, $ $ x (3) $ $, $ $ x (5) $ $ un $$ x (7) $ $. Tādējādi mēs esam sasnieguši mērķi sadalīt astoņu punktu DFT divos četru punktu punktos. Definēt

$$ H \ left (k \ right) = x (1) {{e} ^ {- j \ tfrac {2 \ pi} {4} k \ times0}} + x (3) {{e} ^ j \ tfrac {2 \ pi} {4} k \ times1}} + x (5) {{e} ^ {- j \ tfrac {2 \ pi} {4} k \ times2}} + x (7) { {e} ^ {- j \ tfrac {2 \ pi} {4} k \ times3}} $ $

8. vienādojums

Mēs iegūstam gala rezultātu kā

$$ X \ left (k \ right) = G \ left (k \ right) + {{e} ^ {- j \ tfrac {2 \ pi} {8} k \ times1}} H \ left (k \ right ) $ $

9. vienādojums

kur $ $ G (k) $ $ un $ $ H (k) $$ atbilst četrpunktu DFT. Mēs drīz apspriedīsim šī sadalījuma plūsmas diagrammu, bet ir viens neskaidrs punkts, kas nav izskaidrojams: kā iepriekš minētā procedūra var samazināt multiplikāciju skaitu, kamēr $ $ G (k) + e ^ {- \ tfrac {j2 \ pi} {8 } k \ times 1} H (k) $ $ ir nepieciešams gandrīz tāds pats reizinājumu skaits kā $$ X (k) $$, kas dota 2. variantā. Mēs esam tikai pārkārtojuši noteikumus un mainījuši reizināšanas koeficientus, taču mēs neesam iztērējuši reizināšanu. Lai atrisinātu šo acīmredzamo pretrunu, mums ir jāpievērš trīs punkti: pirmkārt, diskrētais komplekss eksponenciāls, $ $ e ^ {- \ tfrac {j2 \ pi} {N} kn} $ $, ir periodiska $$ k $ $ funkcija ar periodu N. Otrkārt, $ $ k $ $ diapazons mūsu diskusijā ir no $ $ 0 $ $ līdz $ $ 7 $ $. Treškārt, lai gan 2. vienādojums ir saistīts ar sarežģītiem exponentials ar periodu $ $ 8 $ $, ti, $ $ e ^ {- j \ tfrac {2 \ pi} {8} kn} $ $, vienādojums 9 būtībā ir četri punktu DFT, $ $ G (k) $ $ un $ $ H (k) $ $, kas ir sarežģītu exponentials summēšana ar periodu $ $ 4 $ $. Šī periodiskā uzvedība ļauj samazināt kopējo skaitļošanas sarežģītību, aprēķinot visus DFT koeficientus. Piemēram, aprēķinot gan $ $ X (k) $ $, gan $ $ X (k + 4) $ $, mums ir divreiz jāizvērtē 2. vienādojuma noteikumi; tomēr, pamatojoties uz 9. vienādojumu, iegūstam šādus vienādojumus:

$$ X \ left (k \ right) = G \ left (k \ right) + {{e} ^ {- j \ tfrac {2 \ pi} {8} k \ times1}} H \ left (k \ right ) $ $

10. vienādojums

un

$ K = 4) \ times1) $ $ X \ left (k + 4 \ right) = G \ left (k + 4 \ right) + {{e} ^ {- j \ tfrac {2 \ pi} {8} } H \ left (k + 4 \ right) $ $

11. vienādojums

Tā kā $ $ G (k) $ $ un $ $ H (k) $ $ ir periodiski ar $ $ 4 $ $, 11. vienādojums dod

$$ X \ left (k + 4 \ right) = G \ left (k + right) + {{e} ^ {- j \ tfrac {2 \ pi} {8} \ left (k + 4 \ right) \ reizes1}} H \ left (k \ right) $ $

12. vienādojums

Salīdzinot 12. Vienādojumu ar 10. vienādojumu, paskaidrots, kā astoņu punktu DFT sadalīšana divos četru punktu DFT ļauj mums izmantot gandrīz tādus pašus aprēķinus gan $ $ X (k) $ $, gan $ $ X (k + 4) $ $ un ievērojami samazinot aprēķinu skaitu, izmantojot periodiskuma īpašumu.

2. attēlā tiek izmantota iepriekš aprakstītā diskusija, lai iegūtu plūsmas diagrammu, sadalot astoņu punktu DFT divos četru punktu punktos. Ņemiet vērā, ka šajā attēlā $ $ N = 8 $ $ un $ $ W_ (N) ^ (k) = e ^ {- j \ tfrac {2 \ pi} {N} k} $ $.

2. attēls . Plūsmas grafiks astoņu punktu DFT sadalīšanai divos četru punktu punktos. Image pieklājīgi no diskrēta laika signālu apstrādes.

Lai gan, izmantojot DFT definīciju, mums ir jāveic $$ 4N ^ 2 = 256 $$ reālās reizinātas 8 punktu DFT, apspriežamajam algoritam ir jāveic divi četru punktu DFT kopā ar $ $ N $ $ kompleksu multiplikācijas (sk. 2. attēlu). Diviem četru punktu DFT, mums ir jāveic kopējais reālais reizinājumu skaits $ $ 2 \ times 4 \ times (\ tfrac {N} {2}) ^ 2 = 2 \ times 4 \ times 4 ^ 2 = 128 $ $. $$ N $ $ papildu sarežģītajai reizināšanai nepieciešams $ $ 4N = 4 \ times 8 = 32 $ $ reālais reizinājums. Tādējādi iepriekšminētajam algoritmam nepieciešami $ $ 160 $ ​​$ reālās reizināšanas reizinājums, kas ir daudz mazāks nekā tiešās skaitļošanas metodes.

Tas ir ievērojams uzlabojums, bet vai mēs varam panākt turpmāku vienkāršošanu, izmantojot apskatīto metodi četrpunktu DFT, kas parādīti 2. attēlā. "" Src = "// www.allaboutcircuits.com/uploads/articles/Figure3m8232017.png" />

3. attēls . Plūsmas diagramma četrpunktu DFT sadalīšanai divās divpunktu līnijās. Image pieklājīgi no diskrēta laika signālu apstrādes.

4. tabulā norādot četrpunktu DFT ar diagrammu, kas parādīts 3. attēlā, mēs iegūstam struktūru 4. attēlā. Ievērojiet, ka 4.attēls aizstāj $ 3 $ W_ {\ tfrac {N} {2}} $ $ koeficientus, kas parādīti 3. attēlā. ar $ $ W_ {N} ^ (2) $ $, jo $ $ e ^ {- j \ tfrac {2 \ pi} {(\ tfrac {N} {2})}} = e ^ {- j \ tfrac { 2 \ pi} {N} \ reizes 2} $ $.

4. attēls . Plūsmas diagramma, lai aprēķinātu astoņu punktu DFT ar četriem divpunktu skaitļiem. Image pieklājīgi no diskrēta laika signālu apstrādes.

Visbeidzot, mēs varam aizstāt divu punktu DFT, kas parādīti 4. attēlā, ar plūsmas diagrammu, kas parādīta 5. attēlā, un iegūt galīgo struktūru, kas dota 6. attēlā.

5. attēls . Plūsmas diagramma, ko izmanto, lai aprēķinātu augšējo divpunktu DFT 4. attēlā. Image ar diskrētu laika signālu apstrādi.

6. attēls . Decimācijas laika pamatā esošā struktūra, lai aprēķinātu astoņu punktu DFT. Image pieklājīgi no diskrēta laika signālu apstrādes.

Pārrunātais piemērs parāda, ka, lai atkārtoti izmantotu šo paņēmienu, līdz mēs paliekam ar divpunktu DFT, mums sākotnējais DFT garums ir jāizvēlas kā divu jauda, ​​ti, $ $ N = 2 ^ (\ nu } $ $. Šajā gadījumā pēc $$ log_ (2) (N) $ $ atkārtojumiem mēs sasniegsim divpunktu DFT. Kā redzams 6. attēlā, katram algoritma posmam nepieciešams N komplekss reizinājums un līdz ar to kopējais komplekso reizinājumu skaits būs $ $ Nlog_ (2) (N) $ $. Astoņu punktu DFT piemērā mums būs $ $ 8log_ (2) (8) = 24 $ $ kompleksa reizināšanas. Tad, lai gan tiešais aprēķins astoņu punktu DFT prasa $ $ 256 $ $ reālo reizināšanu, decimācijas laika metode prasa tikai $ $ 24 \ times 4 = 96 $ $ reālo pavairošanu. Lasītājs var viegli pārliecināties, ka skaitļošanas ietaupījums būs ļoti dramatisks lieliem DFT.

Kā pēdējo piezīmi jāatceras, ka joprojām ir iespējams izmantot 6. attēlā redzamo komplekso koeficientu simetriju un periodiskumu un samazināt sarežģīto reizinājumu skaitu par diviem faktoriem. Sīkāka šī vienkāršošanas skaidrojuma sk. Šīs grāmatas 729. lappusē.