RFT : a simplified fast real-time sliding DFT algorithm
Claude Baumann, Director of the Boarding School “Convict Episcopal de Luxembourg
1
”, 5,
avenue Marie-Thérèse, m.b. 913, L-2019 Luxembourg
2
claude.baumann@education.lu
September 15
th
2005 (updated November 15
th
2005)
Abstract
This paper presents a variant of the Discrete Fourier Transform (DFT)
3
that is particularly
destined for the implementation in embedded applications, which are characterized by limited
resources in terms of memory and computing speed. Often these applications are highly
specialized and require therefore an optimal relationship between costs and performance. It
surely is of great interest to dispose of algorithms that may combine effectiveness, simplicity,
code-shortness and implementation ease. The presented table-based sliding algorithm has all
these qualities. As the name suggests, it executes the Fourier analysis on the single sample
rather than on an N-sized array of samples, drastically increasing the rate at which the Fourier
coefficients are produced in comparison to other DFT methods. This makes it an excellent
choice for real-time applications. The algorithm is based on a recursive interpretation of the
DFT equations. Furthermore, a look-up table with an astute indexing replaces the time-
intensive calls of trigonometric approximation functions. An optimal adaptation of the data
types guarantees highest precision and result stability.
1. Introduction
Probably the most frequently operated task in modern computers in any way is the Discrete
Fourier Transform (DFT). In signal processing the DFT is used to analyze discrete time
signals. Far from being trivial, the DFT is known to be quite complex both in program design
and execution. Of the numerous available algorithms the Cooley-Tukey Algorithm
4
is the
most commonly used. To express the execution efficiency, the algorithm is called the Fast
Fourier Transform (FFT).
If N designates the number of samples that the FFT is supposed to take into consideration, the
complexity O(N) may be expressed with Nlog
2
N as the result of a divide an conquer strategy.
Compared to the complexity N
2
of a non-optimized DFT, the gain is considerable. However
the disadvantage for real-time applications is the fact that the FFT must be applied to a whole
N-sized dataset, where N must be a power of 2. If no channel switching procedure is added,
the FFT coefficients are updated at a maximum speed of f
a
= f
s
/N, where f
s
is the sampling
frequency, regarded the supposition that the FFT computation has been achieved during 1/f
a
.
5
By contrast, the present simplified sliding algorithm -that we’d like to call Real-time Fourier
Transform (RFT)- has the particularity that the computing speed does not depend on N, but
only on the number of required harmonics. (Remember that in the FFT both values cannot be
separated!) The high-speed analysis is operated after each data-sample and considers nothing
else but the differences that are generated through the disappearance of the oldest data-value
and the incoming of the most recent value, which means that it is not necessary to wait for N
values to be read. If the short computation is faster than the data acquisition time of the signal
processing device, f
a
will equal f
s
. Furthermore the algorithm avoids recalculating
trigonometric functions all over again, which is one of the principal sources of execution
slow-down. Instead the program fixes once at start N cosine and sine values into a constant
look-up table (LUT). Finally a considerable speed gain can be obtained, if the choice of the
data types is made carefully in function of N, since only a finite number of trigonometric
