Fast fourier transform signal processing
OwnerGary Q. Jininventor
Life of this patent
Estimating the term…
Abstract
A method is disclosed for simplifying a Fast Fourier Transform operation on a signal that is real in the time domain, wherein advantage is taken of the symmetry in the frequency domain to reduce the number of butterfly operations required to derive the transform of the signal.
Claims13
A method of performing an Inverse Fast Fourier Transform operation on a signal that is symmetrical in the frequency domain and for which the following relationship holds:
- 12 x ( n ) = ∑ k = 0 N X ( k ) W N k = 2 Re { ∑ k = 0 N 2 - 1 X 1 ( k ) W N k } ( 2 )
- wherein X1(0)=(½)X(k), and X1(k)=X(k) for 0<k<N/2, comprising performing a series of butterfly operations using only input samples X(k), where k<N/2, to derive the inverse transform x(n) of the signal.
A method as claimed in claim 11, wherein N=8 and said input samples are arranged in order X(0), X(0), X(0), X(0), X(1), X(1), X(1), X(1).
A method of performing a Fast Fourier Transform operation on a signal that is symmetrical in the frequency domain and for which the following relationship holds:
- 13 x ( n ) = ∑ k = 0 N X ( k ) W N k = 2 Re { ∑ k = 0 N 2 - 1 X 1 ( k ) W N k } ( 2 )
- wherein X1(0)=(½)X(k), and X1(k)=X(k) for 0<k<N/2, and wherein the signal only occupies the low half of the Nyquist bandwidth, comprising performing a series of butterfly operations using the input samples in the time domain x(n) to produce pair of output samples X(p) and X(q) in the frequency domain, where p and q<N/2, and deriving inverse transform X(k) from said output samples X(p) and X(q).
Dependencies are inferred from the claim text.