head 1.1; branch 1.1.1; access ; symbols start:1.1.1.1 fftvtag:1.1.1; locks ; strict; comment @# @; 1.1 date 2001.07.29.12.30.35; author jdalton; state Exp; branches 1.1.1.1; next ; 1.1.1.1 date 2001.07.29.12.30.35; author jdalton; state Exp; branches ; next ; desc @@ 1.1 log @Initial revision @ text @ Derivation of the DeSpain Algorithm

Derivation of the DeSpain Algorithm

Definition of the Discrete Fourier Transform.

DFT: $X [k] = Σ_{n = 0}^{N - 1} x [n] e^{- j \frac{2 π}{N} n k}$

Inverse DFT: $x [n] = \frac{1}{N} Σ_{k = 0}^{N - 1} X [k] e^{j \frac{2 π}{N} n k}$

Where 'n' and 'k' are related to time and frequency respectively by:

$t = n . Δt = n . \frac{T}{N}$

$ω = k . Δω = k . \frac{2 π}{T}$

Derivation of the DeSpain Algorithm

Start with the Discrete Fourier Transform.

H [k] = Σ_{n = 0}^{N - 1} h [n] e^{- j \frac{2 π}{N} n k}

...(1)

Choose two integers 'P' and 'Q', such that

N = P . Q

...(2)

That is, 'P' and 'Q' are factors of 'N'.

Now let

n = p Q + q

...(3)

where $p = 0,..., P - 1$ ; $q = 0,..., Q - 1$ , and

k = b P + a

...(4)

where $b = 0,..., Q - 1$ ; $a = 0,..., P - 1$ .

Substitute equations (2), (3) and (4) into equation (1) to give:

H [b P + a] = Σ_{p Q + q = 0}^{P Q - 1} h [p Q + q] e^{- j \frac{2 π}{P Q} (p Q + q) (b P + a)}

...(5)

Now expand the exponent.

H [b P + a] = Σ_{p Q + q = 0}^{P Q - 1} h [p Q + q] . e^{- j 2 π p b} . e^{- j \frac{2 π}{P Q} a p Q} . e^{- j \frac{2 π}{P Q} b q P} . e^{- j \frac{2 π}{P Q} q a}

...(6)

Note that the left most exponent is always a multiple of $2 π$ , and cancel common fectors in the other exponents.

H [b P + a] = Σ_{p Q + q = 0}^{P Q - 1} h [p Q + q] . e^{- j \frac{2 π}{P} a p} . e^{- j \frac{2 π}{Q} b q} . e^{- j \frac{2 π}{P Q} q a}

...(7)

Now extract common factors from the sum, and break it into two separate sums, over orthogonal dimensions.

H [b P + a] = Σ_{q = 0}^{Q - 1} \{(Σ_{p = 0}^{P - 1} h [p Q + q] . e^{- j \frac{2 π}{P} p a}) . e^{- j \frac{2 π}{P Q} a q}\} . e^{- j \frac{2 π}{Q} q b}

...(8)

The structure of this expression can be more plainly seen by inroducing intermediate variables 'x' and 'y'.

$x [a, q] = Σ_{p = 0}^{P - 1} h [p Q + q] . e^{- j \frac{2 π}{P} p a}$	...(9a)
$y [a, q] = x [a, q] . e^{- j \frac{2 π}{P Q} a q}$	...(9b)
$H [b P + a] = Σ_{q = 0}^{Q - 1} y [a, q] . e^{- j \frac{2 π}{Q} q b}$	...(9c)

@ 1.1.1.1 log @First Release @ text @@