Efficient Dft Calculation

Humbly Offered At AMMA’s Lotus Feet

Efficient DFT calculation: FFT T F D

N−1

1 ~ ck = ∑ s[n] ⋅ e N n =0

−j

2π k n N

Direct DFT calculation

WNn,k = twiddle factors

1 N−1 = s[n] ⋅ WNkn ∑ N n =0

k = 0,1 .. N-1 W85,k

redundancy

WNkn periodic function calculated many times.

Direct DFT calculation requires ~N2 complex multiplications. complexity O(N2)

D A B Y R E V

!

W86,k

W80,k

W84,k

W83,k

W87,k

W81,k W82,k

Algorithms (= Fast Fourier Transform) developed to compute N-points DFT with ~ Nlog2N multiplications (complexity O(Nlog2N) ).

FFT advantages Number of Operations

2000 1500

DFT ∝ N2

1000

FFT ∝ N log2N

500

N

DFT

Radix-2

4

16

4

32

1024

80

128

16384

448

1024

1048576

5120

0 0

10

20

30

Number of samples, N

40

DSPs & PLDs influenced algorithms design. ‘60s & ‘70s: multiplication counts was “quality factor”. Now: number of additions & memory access (s/w) and communication costs (h/w) also important. NB: Usually you don’t want to write an FFT algorithm, just to “borrow” it !!! Go “shopping” onto the web!

FFT philosophy General philosophy (to be applied recursively): divide & conquer.

Σcost(sub-problems) sub-problems + cost(mapping) mapping < cost(original problem) problem Different algorithms balance costs differently. time

(*)

frequency

Example: Decimation-in-time algorithm

Step 1: Time-domain decomposition. N-points signal → N, 1-point signals (interlace decomposition). Shuffled input data (bitreversal). log2N stages.

(*): only first decomposition shown. Step 2: 1-point input spectra calculation. (Nothing to do!) Step 3: Frequency-domain synthesis. N spectra synthesised into one.

FFT family tree Divide & conquer N : GCD(*)(N1,N2) = 1 N1, N2 co-prime. Ex: 240 = 16·3·5

Cost: SUB-PROBLEMS. SUB-PROBLEMS

N : GCD(N1,N2) <> 1 Ex: N = 2n

Cost: MAPPING. MAPPING

• No twiddle-factors calculations.

• Twiddle-factors calculations.

• Easier mapping (permutations).

• Easier sub-problems.

• Some algorithms:

• Some algorithms:

Good-Thomas, Kolba,

Cooley-Tukey,

Parks, Winograd.

Decimation-in-time / in-frequency Radix-2, Radix-4,

* GCD= Greatest Common Divisor

( )

Split radix.

(Some) FFT concepts & notes s[k]

s[k+N/2]

WN0

Butterfly: basic FFT calculation element.

WNN/2

• Decimation-in-time ⇒ time data shuffling.

Dual approach: data to be reordered in time or in frequency!

• Decimation-in-frequency ⇒ frequency data shuffling. • In-place computation: no auxiliary storage needed, allowed by most algorithms. • DFT pruning: only few bins needed or different from zero ⇒ only they get calculated (ex: Goertzel algorithm). • Real-data case: Mirroring effect in DFT coeffs. ⇒ only half of them calculated. • N power-of-two: Many common FFT algorithms work with power-of-two number of inputs. When they are not ⇒ pad inputs with zeroes.

Systems spectral analysis (hints) System analysis: measure input-output relationship. Linear Time Invariant

x[n]

DIGITAL LTI SYSTEM

δ[n]

y[n]

h[n]

x[n]

h[n]

1

0

n

DIGITAL LTI SYSTEM

h[n] 0

h[t] = impulse response y[n] = x[n] ∗ h[n] =

∞

∑ x[n − m] ⋅ h[m]

y[n] predicted from { x[n], h[t] }

m=0

X(f)

H(f)

n

Y(f) = X(f) · H(f)

H(f) : LTI transfer function

Transfer function can be estimated by Y(f) / X(f)

Estimating H(f) G xx (f) = X(f) ⋅ X * (f) G yx (f) = Y(f) ⋅ X* (f)

Power Spectral Density of x[t] (FT of autocorrelation).

Cross Power Spectrum of x[t] & y[t] (FT of cross-correlation).

Y(f) Y(f) ⋅ X * (f) G yx H(f) = = = * X(f) X(f) ⋅ X (f) G xx

C xy (f) =

(hints)

G yx (f)

2

G xx (f) ⋅ G yy (f)

Transfer Function (ex: beam !)

Coherence function - values in [0,1] - assess degree of linear relationship between x[t] & y[t].

It is a check on H(f) validity!

Aum Namah Sivaya