Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-08-17
2002-07-16
Ngo, Chuong Dinh (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S409000
Reexamination Certificate
active
06421696
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the field of digital signal processing, and more specifically, to a system and method for performing forward and inverse discrete Fourier transforms in a microprocessor-based processing environment.
DESCRIPTION OF THE RELATED ART
Digital signal processing (DSP) is fundamental to a variety of modern technologies. Improvements in DSP algorithms are rapidly incorporated into new products and devices, and serve as a motive force behind the modem telecommunications industry. This is especially true for improvements in transformation algorithms such as the Fast Fourier Transform.
As with other types of processing, digital signal processing may be accomplished in a batch mode or a real-time mode. Batch-mode processing involves (a) reading input data from memory, (b) performing a number DSP operations, and (c) storing the resultant output data to memory. One disadvantage of batch-mode processing is that the storage-capacity requirement for the memory may be prohibitively high. For example, if the input data represents frames of a video signal, a large amount of memory may be consumed to store a few minutes worth of video frames.
On the other hand, real-time processing involves receiving an input data stream from a data source, operating on the input data stream (i.e. applying a DSP algorithm) to generate an output data stream, and providing the output data stream to a data sink, where the data rate of the input data stream and/or the output data stream are specified. For example, the data source may be a video camera which generates video frames at a fixed rate, and the data sink may be a video monitor. Real-time processing requires that the average rate of throughput of the DSP algorithm must be greater than or equal to the specified data rate. The input and output data streams are generally buffered. The size of the input buffer and the specified data rate determine a maximum time for the DSP algorithm to process the input buffer contents.
Real-time processing generally implies less of a necessity for data storage since the output data stream is consumed (i.e. used) by the data sink shortly after it is generated by the DSP algorithm. However, the computational throughput requirement of real-time processing typically places a severe demand on the efficiency of the DSP algorithm and the speed of the processor used to implement it.
DSP theory provides a host of tools for the analysis and representation of signal data. Among these tools, the Fourier Transform is one of the most important. The Fourier Transform operates on an input function in order to generate a resultant function. FFTs operate upon a block of data extracted from this input function, either sequential blocks or overlapping blocks. There are real and complex-valued input and output versions of the FFT, in-place and not-in-place computational forms. The complex value of the resultant function at a given frequency represents the amplitude and phase of a sinusoidal component of the input function. Thus, the Fourier Transform is said to perform a conversion between the time domain and the frequency domain. The Fourier Transform just described is generally referred to as the forward Fourier transform to distinguish it from the inverse Fourier transform. The inverse Fourier Transform inverts (i.e. reverses) the forward Fourier transform. Thus, the inverse Fourier Transform operates on functions of frequency and generates corresponding functions of time.
By use of the forward and inverse Fourier Transforms, a signal may be converted between a time-domain representation and a frequency-domain representation. The forward Fourier transform is said to perform a spectral analysis of a time-domain signal because it computes the amplitude and phase of all the sinusoidal components of the time-domain signal. The inverse Fourier transform is said to perform a spectral synthesis of a time-domain signal because the formula for the inverse transform describes the time-domain signal as a linear combination (albeit infinite combination) of the spectral components.
Fourier transforms are inherently continuous mathematical transformations. Since computers are constrained to operate on discrete data, a special discretized form of the Fourier transform is used for computer implementations, i.e. the so called Discrete Fourier Transform (DFT). The Discrete Fourier Transform may be used in a wide variety of applications and allows an arbitrary input array size. However, the straightforward DFT algorithm is often prohibitively time-consuming.
In 1965, Cooley and Tukey disclosed an efficient algorithm for performing the Discrete Fourier Transform. This algorithm, known as the Fast Fourier Transform, exploits symmetries inherent in DFTs of order 2
K
for any integer K. The order of a DFT may be defined as the size of its input array. The structure of the FFT algorithm allows one complex multiplication factor e
jw
to be used for all the butterflies in a group rather than having to recalculate complex-valued multiplication factors for each butterfly.
In addition, the FFT algorithm uses either (a) a natural ordering to access input operands and a special interleaved order to write output operands, or (b) the special interleaved order to access input operands and natural ordering to write output operands. The special interleaved ordering is then used either at the input or the output but not both. For clarity of discussion, suppose the input operands are accessed in the interleaved order. Furthermore, suppose that the input array comprises eight samples of a signal X. Thus, the eight samples may be represented as X(
000
), X(
001
), X(
010
), X(
011
), X(
100
), X(
101
), X(
110
) and X(
111
) in the order they appear in the input array. The FFT algorithm accesses these input values in the order X(
000
), X(
100
), X(
010
), X(
110
), X(
001
), X(
101
), X(
011
) and X(
111
). Coley and Tukey realized that the addresses of samples in the access order and the memory order were effectively bit reversed. Another way to interpret the special access order is in terms of a reverse carry bit from an address calculation adder. Carries are propagated from left to right rather than the more typical right-to-left direction.
In many processor architectures used for Digital Signal Processing, such as the popular Harvard architecture, the throughput of a processing algorithm is determined primarily by the total number of data multiplies and additions. Data moves and branching operations (such as, e.g., those which implement a loop construct) may require significantly lower overhead than multiplies and additions in many architectures. Consequently, a reasonable estimate of the computational complexity of a processing algorithm may be obtained by counting the number of data multiplies as a function of the number of data points in the input buffer. An N-point DFT requires N
2
multiplies. For large array sizes (which correspond to fine frequency resolution), the number of arithmetic operations then becomes extremely large. In contrast, the number of multiplies for an N-point FFT is N·log
2
(N). Thus, the FFT exhibits a greatly reduced complexity relative to the DFT especially for larger array sizes.
The Fast Fourier Transform algorithm, because of its greatly reduced computational complexity, allowed more sophisticated signal processing algorithms to be implemented in real-time applications than are possible with the DFT. For example, FFTs are one key component of interactive speech-recognition algorithms, so faster FFTs enable better and more complete analysis of speech.
Traditional x86 processors are not well adapted for the types of calculations used in signal processing. Thus, signal processing software applications on traditional x86 processors have lagged behind what was realizable on other processor architectures. There are been various attempts to improve the signal processing performance of x86-based systems. For example, microcontrollers optimized for signal processing computations (DSPs) have been provid
Advanced Micro Devices , Inc.
Conley Rose & Tayon PC
Kivlin B. Noë
Ngo Chuong Dinh
LandOfFree
System and method for high speed execution of Fast Fourier... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for high speed execution of Fast Fourier..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for high speed execution of Fast Fourier... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2826848