Verschil tussen FFT en DFT

Fast Fourier Transform (FFT) vs. Discrete Fourier-transformatie (DFT)

Technologie en wetenschap gaan hand in hand. En er is geen beter voorbeeld dan digitale signaalverwerking (DSP). Digital Signal Processing is het proces voor het optimaliseren van de nauwkeurigheid en efficiëntie van digitale communicatie. Alles is data - of het nu de beelden zijn van ruimtesondes in de ruimte of seismische trillingen en alles daartussenin. Het converteren van deze gegevens naar een voor mensen leesbaar formaat met behulp van computers is digitale signaalverwerking. Het is een van de krachtigste technologieën die zowel wiskundige theorie als fysieke implementatie combineert. De studie van DSP begon als een cursus op graduate-niveau in de elektrotechniek, maar na verloop van tijd is het een potentiële gamechanger op het gebied van wetenschap en techniek geworden. Het volstaat te zeggen dat zonder DSP ingenieurs en wetenschappers ophouden te bestaan.

Fourier-transformatie is een middel om een ​​signaal in het tijds- of ruimtedomein in het spectrum in het frequentiedomein in kaart te brengen. De tijd- en frequentiedomeinen zijn slechts alternatieve manieren om signalen weer te geven en de Fourier-transformatie is de wiskundige relatie tussen de twee weergaven. Een verandering van signaal in één domein zou ook het signaal in het andere domein beïnvloeden, maar niet noodzakelijk op dezelfde manier. Discrete Fourier-transformatie (DFT) is een transformatie zoals Fourier-transformatie die wordt gebruikt met gedigitaliseerde signalen. Zoals de naam al doet vermoeden, is het de discrete versie van de FT die zowel het tijdsdomein als het frequentiedomein als periodiek beschouwt. Fast Fourier Transform (FFT) is slechts een algoritme voor snelle en efficiënte berekening van de DFT.

Discrete Fourier-transformatie (DFT)

De Discrete Fourier-transformatie (DFT) is een van de belangrijkste hulpmiddelen bij digitale signaalverwerking die het spectrum van een signaal met een eindige duur berekent. Het is heel gebruikelijk om de informatie in de sinusoïden te coderen die een signaal vormen. In sommige toepassingen is de vorm van een tijddomeingolfvorm echter geen toepassing voor signalen, in welk geval signaalfrequentie-inhoud zeer bruikbaar wordt op andere manieren dan als digitale signalen. De weergave van een digitaal signaal in termen van zijn frequentiecomponent in een frequentiedomein is belangrijk. Het algoritme dat de tijdsdomeinsignalen naar de componenten van het frequentiedomein transformeert, staat bekend als de discrete Fourier-transformatie of DFT.

Fast Fourier Transform (FFT)

De Fast Fourier-transformatie (FFT) is een implementatie van de DFT die vrijwel dezelfde resultaten produceert als de DFT, maar is ongelooflijk veel efficiënter en veel sneller waardoor de rekentijd aanzienlijk korter wordt. Het is slechts een rekenalgoritme dat wordt gebruikt voor een snelle en efficiënte berekening van de DFT. Verschillende snelle DFT-berekeningstechnieken die gezamenlijk bekend staan ​​als de snelle Fourier-transformatie of FFT. Gauss was de eerste om de techniek voor te stellen voor het berekenen van de coëfficiënten in een trigonometrische van de baan van een asteroïde in 1805. Het was echter pas in 1965 dat een baanbrekend artikel door Cooley en Tukey de aandacht trok van de wetenschappelijke en technische gemeenschap, die ook de basis van de discipline digitale signaalverwerking.

Verschil tussen FFT en DFT

1. Betekenis van FFT en DFT

Discrete Fourier-transformatie, of eenvoudigweg aangeduid als DFT, is het algoritme dat de tijdsdomeinsignalen omzet naar de componenten van het frequentiedomein. DFT, zoals de naam al doet vermoeden, is echt discreet; discrete tijddomeingegevenssets worden getransformeerd in discrete frequentie-representatie. In eenvoudige bewoordingen stelt het een relatie tussen de tijdsdomeinrepresentatie en de representatie van het frequentiedomein vast. Fast Fourier Transform, of FFT, is een rekenalgoritme dat de rekentijd en complexiteit van grote transformaties vermindert. FFT is slechts een algoritme dat wordt gebruikt voor snelle berekening van de DFT.

2. Algoritme van FFT en DFT

Het meest gebruikte FFT-algoritme is het Cooley-Tukey-algoritme, dat is vernoemd naar J.W. Cooley en John Tukey. Het is een verdeel en heers algoritme voor de machineberekening van complexe Fourier-series. Het breekt de DFT in kleinere DFT's. Andere FFT-algoritmen omvatten het Rader-algoritme, Winograd Fourier-transformatie-algoritme, Chirp Z-transformatie-algoritme, etc. De DFT-algoritmen kunnen worden geprogrammeerd op digitale computers voor algemene doeleinden of direct worden geïmplementeerd door speciale hardware. Het FFT-algoritme wordt gebruikt om de DFT van een reeks of de inverse ervan te berekenen. Een DFT kan worden uitgevoerd als O (N²) in tijdcomplexiteit, terwijl FFT de tijdcomplexiteit in de volgorde van O (NlogN) vermindert.

3. Toepassingen van FFT en DFT

DFT kan in veel digitale verwerkingssystemen worden gebruikt voor verschillende toepassingen, zoals het berekenen van het frequentiespectrum van een signaal, het oplossen van partiële differentiële toepassingen, detectie van doelen van radarecho's, correlatieanalyse, berekenen van polynomiale vermenigvuldiging, spectrale analyse en meer. FFT is op grote schaal gebruikt voor akoestische metingen in kerken en concertzalen. Andere toepassingen van FFT omvatten spectrale analyse in analoge videometingen, grote integer en polynomiale vermenigvuldiging, filteralgoritmen, berekenen van isotopische distributies, berekenen van Fourier-reekscoëfficiënten, berekenen van convoluties, opwekken van laagfrequente ruis, ontwerpen van kinovormen, uitvoeren van dichte gestructureerde matrices, beeldverwerking, en meer.

FFT versus DFT: Vergelijkingstabel

Samenvatting van FFT Vs. DFT

In een notendop speelt de Discrete Fourier-transformatie een sleutelrol in de natuurkunde omdat deze kan worden gebruikt als een wiskundig hulpmiddel om de relatie tussen het tijdsdomein en de representatie van frequentiedomeinen van discrete signalen te beschrijven. Het is een eenvoudig maar vrij tijdrovend algoritme. Om echter de rekentijd en de complexiteit van grote transformaties te verminderen, kan een complexer maar minder tijdrovend algoritme zoals de Fast Fourier-transformatie worden gebruikt. FFT is een implementatie van de DFT die wordt gebruikt voor snelle berekening van de DFT. Kortom, FFT kan alles doen wat een DFT doet, maar efficiënter en veel sneller dan een DFT. Het is een efficiënte manier om de DFT te berekenen.