Multiplex communications – Generalized orthogonal or special mathematical techniques – Fourier transform
Utility Patent
1997-12-15
2001-01-02
Kizou, Hassan (Department: 2738)
Multiplex communications
Generalized orthogonal or special mathematical techniques
Fourier transform
C370S480000, C375S222000, C324S076210
Utility Patent
active
06169723
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the use of the discrete Fourier transform (DFT) and the inverse discrete Fourier transform (IDFT) in a wide variety of signal processing applications. In particular, the invention presents more efficient and less complex methods for computing the DFT and IDFT.
BACKGROUND AND SUMMARY OF THE INVENTION
Orthogonal transforms and transform properties are extraordinarily useful in solving new technological problems. Such transforms permit analysis of most signals given some knowledge of its constituent parts. The Fourier transform in particular has become a powerful tool in increasingly diverse fields including linear systems, communications systems, image processing applications, etc. to name just a few.
The discrete Fourier transform (DFT) is the counterpart of the Fourier transform in the discrete time domain. In general, the DFT may be defined as follows:
X
k
=
∑
n
=
0
N
-
1
x
n
W
N
kn
k
=
0
,
1
…
,
N
-
1
(
1
)
and the inverse DFT (IDFT) is expressed as:
x
n
=
1
/
N
∑
k
=
0
N
-
1
X
k
W
N
-
kn
k
=
0
,
1
…
,
N
-
1
(
2
)
where W
N
k
=e
−j2&pgr;k/N
. In equations (1) and (2), X
n
is the sample value in the time domain, and X
k
is the sample value in the frequency domain.
Direct calculation of the DFT and the IDFT is computationally intensive and requires N
2
complex multiplications and N(N−1) complex additions. Such computational overhead is quite burdensome in terms of reduced signal processing speed, increased power consumption, and higher expense. One important tool in modern digital signal processing applications that helps to reduce that overhead is the Fast Fourier Transform (FFT). The FFT computes the DFT by mapping an N-point complex sequence to its corresponding N-point complex frequency spectrum and vice versa for the IFFT and IDFT.
Although FFT algorithms are typically designed to compute the DFT of a complex sequence, in many applications, the sequence to be transformed is real valued. But even for real value sequence applications, the FFT/IFFT requires multiple complex multiplications and additions. Thus, there is an ongoing need to reduce the number of FFT/IFFT computations, and in particular the number of complex multiplications, that must be performed in order to more efficiently compute the FFT and the IFFT.
The present invention meets this need and significantly reduces the number of complex computations that must be performed in computing the DFT and IDFT of real value sequences. The computational reduction increases signal processing speed and decreases power consumption, both of which are highly desirable in virtually every DFT/IDFT application. The present invention achieves these goals by taking advantage of various symmetries and regularities of processed data sequences.
A pattern is identified in an original data sequence and is used to modify the data sequence in order to reduce the length of the FFT. A DFT (or IDFT) is then performed on the modified input data sequence to generate a transformed sequence. The transformed data sequence is then manipulated to generate an output sequence that corresponds to the DFT (or IDFT) of the original input data sequence without having to actually calculate the DFT (or IDFT) of the entire, original input data sequence. Moreover, the IDFT may then be determined using the complex-conjugate of the already-calculated DFT rather than independently calculating the IDFT (and vice versa).
The pattern in the original data sequence may include a particular symmetry. Three symmetrical patterns, corresponding to three example embodiments of the present invention, are used to simplify and render more efficient DFT and IDFT computations: Hermite symmetry, index-reversed complex-conjugate symmetry, and mirror symmetry. In the Hermite and mirror symmetry example embodiments, the modified data sequence is substantially shorter than the original data sequence, e.g., one-half the length of the original data sequence, one-fourth of the length of the original data sequence, etc. In all three embodiments, the number of complex multiplications required to perform the DFT (or IDFT) of the modified data sequence is considerably less than the number of complex multiplications required to calculate the DFT (or IDFT) of the original input data sequence.
In the Hermite symmetry example embodiment, an original, N-point input data sequence is efficiently transformed using either a DFT (or an IDFT). From the original, N-point Hermite symmetric input data sequence, an N/2 sequence of complex numbers is defined. A DFT (or an IDFT) is executed on the N/2 sequence to generate a transformed data sequence. The real part of the transformed sequence is output as the even numbered samples and the imaginary part as the odd numbered samples of the output sequence corresponding to the DFT (or the IDFT) of the original, N-point, Hermite symmetric input data sequence.
In the index-reversed, complex-conjugate symmetry example embodiment, first and second input data sequences are defined. A DFT (or IDFT) is executed on the first input data sequence to generate a transformed data sequence. The DFT (or IDFT) of the second input data sequence is then determined using the DFT (or IDFT) of the first input data sequence. In other words, the DFT (or IDFT) of the second input data sequence is determined without formally calculating the DFT (or IDFT) of the second input data sequence. This computational saving is achieved as a result of the first and second sequences being index-reversed, complex-conjugate sequences. More specifically, the DFT (or IDFT) of the second input data sequence is determined by complex-conjugating the DFT (or IDFT) of the first input data sequence and multiplying by a complex number.
The third example embodiment of the present invention takes advantage of mirror symmetric data sequences, i.e., a sequence of length N where the elements starting with index N/2 through N−1 are the complex-conjugate of the elements with index 0 through N/2−1 in reverse order. A mirror symmetric input data sequence is split into first and second sub-sequences. The first sub-sequence includes the even components of the mirror symmetric input data sequence, and the second sub-sequence includes the odd components of the mirror symmetric input data sequence. The DFT (or IDFT) is executed on the first sub-sequence to generate a transformed data sequence. A first half of the DFT (or IDFT) of the input data sequence is then determined using the DFT (or IDFT) of the first sub-sequence and adding its complex-conjugated sequence multiplied by a twiddle factor. The second remaining half of the DFT (or IDFT) of the input data sequence is determined using the DFT (or IDFT) of the first sub-sequence and subtracting its complex-conjugate sequence multiplied by a twiddle factor.
One practical application of the present invention is to digital modems where one information sequence to be transmitted is modulated onto discrete multi-tone (DMT) carriers using an inverse fast Fourier transform (IFFT) and the received sequence is demodulated by using a fast Fourier transform (FFT). A pre-transform processor modifies an original sequence based upon an identified pattern in that sequence to reduce the number of samples. Transform circuitry then performs an IFFT on the modified data sequence to modulate the DMT carriers to be transmitted in a transmit direction and an FFT to demodulate DMT carriers received in the receive direction. A transform processor manipulates the transformed data sequence to generate an output sequence corresponding to the FFT or the IFFT of the original data sequence. In one example embodiment of a DMT system, even numbered DMT carriers are employed in the transmit direction and odd numbered DMT carriers are employed in the receive direction. The number of DMT carriers in both directions can be substantially the same (symmetric communication), o
Fertner Antoni
Hyll Mattias
{umlaut over (O)}rling Anders
Kizou Hassan
Nixon & Vanderhye P.C.
Pezzlo John
Telefonaktiebolaget LM Ericsson
LandOfFree
Computationally efficient analysis and synthesis of real... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Computationally efficient analysis and synthesis of real..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computationally efficient analysis and synthesis of real... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2471368