Razlika med FFT in DFT

Hitra Fourierjeva transformacija (FFT) vs. Diskretna Fourierova transformacija (DFT)

Tehnologija in znanost gresta z roko v roki. In ni boljšega primera tega kot digitalna obdelava signala (DSP). Digitalna obdelava signalov je postopek za optimizacijo natančnosti in učinkovitosti digitalnih komunikacij. Vse so podatki - naj bodo to slike iz vesoljskih sond ali potresne vibracije in kaj drugega vmes. Za pretvorbo teh podatkov v človeko berljiv format z računalniki je digitalna obdelava signalov. Gre za eno najmočnejših tehnologij, ki združuje tako matematično teorijo kot fizično izvedbo. Študij DSP se je začel kot podiplomski študij elektrotehnike, sčasoma pa je postal potencialni menjalnik iger na področju znanosti in tehnike. Dovolj je reči, da brez DSP inženirji in znanstveniki morda ne bi več obstajali.

Fourierova transformacija je sredstvo za preslikavo signala v časovni ali vesoljski domeni v njegov spekter v frekvenčni domeni. Časovne in frekvenčne domene so le alternativni načini predstavljanja signalov in Fourierjeva transformacija je matematični odnos med obema predstavitvama. Sprememba signala v eni domeni bi vplivala tudi na signal v drugi domeni, vendar ne nujno na enak način. Diskretna Fourierova transformacija (DFT) je transformacija, podobna Fourierovi transformaciji, ki se uporablja pri digitaliziranih signalih. Kot že ime pove, diskretna različica FT obravnava časovno in frekvenčno domeno kot periodično. Hitra Fourierjeva transformacija (FFT) je le algoritem za hitro in učinkovito računanje DFT.

Diskretna Fourierova transformacija (DFT)

Diskretna Fourierova transformacija (DFT) je eno najpomembnejših orodij pri digitalni obdelavi signalov, ki izračuna spekter signala s končnim trajanjem. Zelo pogosto je kodiranje informacij v sinusoide, ki tvorijo signal. Vendar v nekaterih aplikacijah oblika valovne oblike časovne domene ni uporaba za signale, v tem primeru postane vsebina frekvenc signala zelo uporabna na druge načine, kot digitalni signali. Pomembna je predstavitev digitalnega signala glede na njegovo frekvenčno komponento v frekvenčnem območju. Algoritem, ki pretvori signale časovne domene v komponente frekvenčne domene, je znan kot diskretna Fourierova transformacija ali DFT.

Hitra Fourierjeva transformacija (FFT)

Hitra Fourierjeva transformacija (FFT) je izvedba DFT, ki daje skoraj enake rezultate kot DFT, vendar je neverjetno bolj učinkovita in veliko hitrejša, kar pogosto bistveno skrajša čas računanja. To je le računski algoritem, ki se uporablja za hitro in učinkovito računanje DFT. Različne tehnike hitrega izračuna DFT, znane skupaj kot hitro Fourierovo preoblikovanje ali FFT. Gauss je prvi predlagal tehniko za izračun koeficientov v trigonometrični orbiti asteroida leta 1805. Vendar pa je šele leta 1965 seminarski Cooley in Tukey pritegnil pozornost znanstvene in inženirske skupnosti, ki je tudi postavila temelj discipline digitalne obdelave signalov.

Razlika med FFT in DFT

1. Pomeni FFT in DFT

Diskretna Fourierova transformacija ali preprosto imenovana DFT je algoritem, ki signale časovne domene pretvori v komponente frekvenčne domene. DFT je, kot že ime pove, resnično diskreten; diskretni nabori podatkov časovne domene se pretvorijo v diskretno predstavitev frekvence. Preprosto povedano, vzpostavi razmerje med predstavitvijo časovne domene in predstavitvijo frekvenčne domene. Hitra Fourierjeva transformacija ali FFT je računalniški algoritem, ki zmanjša čas računalništva in zahtevnost velikih pretvorb. FFT je le algoritem, ki se uporablja za hitro izračunavanje DFT.

2. Algoritem FFT in DFT

Najpogosteje uporabljeni algoritem FFT je algoritem Cooley-Tukey, ki je dobil ime po J. W. Cooleyju in Johnu Tukeyju. Gre za algoritem ločitve in osvajanja za strojni izračun kompleksnih Fourierjevih serij. DFT razbije na manjše DFT. Drugi algoritmi FFT vključujejo algoritem Rader, algoritem transformacije Winograd Fourier, algoritem Chirp Z-transformacije itd. Algoritmi DFT lahko programirajo na digitalnih računalnikih splošne namene ali jih neposredno izvaja posebna strojna oprema. Algoritem FFT se uporablja za izračun DFT zaporedja ali njegovega obratnega. DFT se lahko izvede kot O (N²) v časovni zapletenosti, medtem ko FFT časovno kompleksnost zmanjša v vrstnem redu O (NlogN).

3. Uporaba FFT in DFT

DFT je mogoče uporabiti v številnih sistemih digitalne obdelave v različnih aplikacijah, kot so izračunavanje frekvenčnega spektra signala, reševanje delnih diferencialnih aplikacij, odkrivanje ciljev iz radarskih odmevov, korelacijska analiza, računanje polinomskega množenja, spektralna analiza in drugo. FFT se pogosto uporablja za zvočne meritve v cerkvah in koncertnih dvoranah. Druge aplikacije FFT vključujejo spektralno analizo v analognih video meritvah, velikem celičnem in polinomskem množenju, filtrirnih algoritmih, računanju izotopskih porazdelitev, izračunu koeficientov serije Fourier, izračun konvolucij, ustvarjanju nizkofrekvenčnega hrupa, oblikovanju kinoform, izvajanju gosto strukturiranih matric, obdelavi slike in več.

FFT vs. DFT: Primerjalna tabela

Povzetek FFT Vs. DFT

Na kratko, diskretna Fourierjeva transformacija igra ključno vlogo v fiziki, saj se lahko uporablja kot matematično orodje za opis razmerja med časovno domeno in frekvenčno predstavitvijo diskretnih signalov. Gre za preprost, a dokaj zamuden algoritem. Za zmanjšanje računalniškega časa in zapletenosti velikih pretvorb pa je mogoče uporabiti bolj zapleten, a manj zamuden algoritem, kot je Hitra Fourierjeva transformacija. FFT je izvedba DFT, ki se uporablja za hitro računanje DFT. Skratka, FFT lahko naredi vse, kar počne DFT, vendar bolj učinkovito in veliko hitreje kot DFT. To je učinkovit način izračuna DFT.