Next: References
Up: Discrete Fourier transform
Previous: Examples of 2-D FT
A basic building block in the
fast Fourier transform is called
``doubling.''
Given a series
and its sampled Fourier transform
,and another series
and its sampled Fourier transform
,there is a trick to find easily
the transform of the interlaced double-length series
| ![\begin{displaymath}
z_t \eq (x_0, y_0, x_1, y_1, \ldots , x_{N - 1}, y_{N-1})\end{displaymath}](img95.gif) |
(20) |
The process of doubling is used many times
during the computing of a fast Fourier transform.
As the word ``doubling" might suggest,
it will be convenient to suppose that
N is an integer formed by raising 2 to
some integer power.
Suppose N = 8 = 23.
We begin by dividing our eight-point series
into eight separate series, each of length one.
The Fourier transform of each of the one-point series is just the point.
Next, we use doubling four times
to get the transforms of the four different two-point series
(x0, x4), (x1, x5), (x2, x6), and (x3, x7).
We use doubling twice more to get the transforms
of the two different four-point series
(x0, x2, x4, x6) and (x1, x3, x5, x7).
Finally, we use doubling once more
to get the transform of the original eight-point series
.It remains to look into the details of the doubling process.
Let
| ![\begin{eqnarray}
V & = & e^{i2\pi/2N} = W^{1/2}
\ V^N & = & e^{i\pi} = -1\end{eqnarray}](img97.gif) |
(21) |
| (22) |
By definition, the transforms of two N-point series are
| ![\begin{eqnarray}
X_k &= & \sum^{N- 1}_{j = 0} x_j V^{2jk} \quad (k = 0, 1, \ldot...
...& \sum^{N- 1}_{j = 0} y_j V^{2jk} \quad (k = 0, 1, \ldots , N -1) \end{eqnarray}](img98.gif) |
(23) |
| (24) |
Likewise, the transform of the interlaced series
is
| ![\begin{displaymath}
Z_k \eq \sum^{2N- 1}_{l = 0} z_l V^{lk} \quad (k = 0, 1, \ldots , 2N -1)\end{displaymath}](img100.gif) |
(25) |
To make Zk from Xk and Yk, we require two separate formulas,
one for k = 0, 1,
, N -1,
and the other for k = N, N + 1,
, 2N - 1.
Start from the sum
| ![\begin{displaymath}
Z_k \eq \sum^{2N- 1}_{l = 0} z_l V^{lk} \quad (k = 0, 1, \ldots , N -1)\end{displaymath}](img102.gif) |
(26) |
and then split the sum into two parts,
noting that xj multiplies even powers of V,
and yj multiplies odd powers:
| ![\begin{eqnarray}
Z_k &= & \sum^{N- 1}_{j = 0} x_j V^{2jk} + V^k \sum^{N - 1}_{j = 0} y_j V^{2jk}
\ &= & X_k + V^k Y_k\end{eqnarray}](img103.gif) |
(27) |
| (28) |
We obtain the last half of the Zk by
| ![\begin{eqnarray}
Z_k &= & \sum^{2N- 1}_{l = 0} z_l V^{lk} \quad (k = N, N + 1, \...
...= & X_{k-N} - V^{k-N} Y_{k-N} \quad (k = N, N + 1, \ldots , 2N -1)\end{eqnarray}](img104.gif) |
(29) |
| (30) |
| (31) |
| (32) |
| (33) |
| (34) |
| (35) |
The subroutine ftu()
does not follow this analysis in detail.
If you would like some industrial grade FFT programs,
search the web for "prime factor FFT".
Next: References
Up: Discrete Fourier transform
Previous: Examples of 2-D FT
Stanford Exploration Project
10/21/1998