Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-06-17
2002-03-12
Malzahn, David H. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06356926
ABSTRACT:
FIELD OF INVENTION
The present invention relates to a method of calculating Fast Fourier Transform (FFT) and to a device for carrying out the method, and in particular to the interconnection of and the coaction between the calculating unit and the memory of said device.
BACKGROUND OF THE INVENTION
The Discrete Fourier Transform (DFT) of a sequence f(n) is defined as:
X
(
k
)
=
∑
n
=
0
N
-
1
x
(
n
)
W
kn
(
n
=
0
,
1
,
…
,
N
-
1
)
where the weight coefficient W=e
−12&pgr;/N
.
The inverse to the Discrete Fourier Transform is defined as
x
(
n
)
=
1
N
∑
k
=
0
N
-
1
X
(
k
)
W
kn
(
k
=
0
,
1
,
…
,
N
-
1
)
where the weight coefficient W=e
−12&pgr;/N
.
If X(k) or x(n) is calculated directly in accordance with the definitions, the number of additions will be N(N−1) and the number of multiplications will be generally in the order of magnitude of N
2
.
In 1965, Cooley and Tukey introduced a novel method of calculating X(k) and x(n) respectively, resulting in a much shorter calculation time. The method was designated Fast Fourier Transform (FFT) and utilizes the circumstance that the same calculations reoccur at several positions. The number of additions and multiplications can be reduced to the order of log
2
N when N is a two-power.
In brief, the method is based on a number of successive calculations with a series or column of values, where each pair of calculations is called a butterfly.
This gives a new column of N number of values. These are used for new, similar calculations and give, in turn, a new column of N number of values and so on, until log
2
N columns have been calculated, the answer being given by the last series. This method can be varied in a number of different ways.
The old series is no longer required each time a new series is calculated. This enables the memory, or store, in which the previous series is stored to be reused, this being referred to as calculating inplace. Thus, the method can be carried out with a memory of size N, disclosed in GB 1 546 173 and GB 2 006 485, for instance. The drawback with this is that memory accesses are always made to the same memory, which is not particularly effective.
FFT can also be implemented with the use of two memories of size N, as disclosed in the technical report “An Energy-Efficient FFT Processor Architecture” (NGT-70340-1994-1), Department of Electrical Engineering, Stanford University, Stanford, Calif., U.S.A. Data is read from one memory, processed and then written into the other memory. This method is faster than calculating inplace, since writing and reading can take place simultaneously. The drawback with this method is that it requires twice as much memory as the FFT to be calculated.
SUMMARY OF THE INVENTION
The present invention addresses the problem of FFT calculations requiring either a great deal of time or a large amount of memory space.
The object of the present invention is to provide a solution to this problem by organizing the interconnection and coaction between the calculating unit and memory, so as to enable two butterfly calculations to be commenced simultaneously. This is achieved by reading the input values from memory positions in the memories and intermediately storing these input values in a register in the calculating unit after reading, and/or by storing the output values to be written into memory positions in the memory intermediately in a register in the calculating unit prior to writing-in said values. The values are conveniently allocated or distributed so that each memory will contain essentially the same number of values. This enables, for instance, two memories to be used to a maximum, by reading from and writing into memory positions in the two memories simultaneously. Alternatively, values can be read from one memory at the same time as values are written into the other memory.
One advantage afforded by the present invention is that the memories are utilized to a maximum, therewith enabling the memory space to be minimized to half the memory space required by the known solution that utilizes two memories. Another advantage is that the time required in this respect can be reduced in comparison with the time required by the known solution that utilizes a single memory.
The invention will now be described in more detail with reference to preferred embodiments thereof and also with reference to the accompanying drawings. In the following text, a butterfly designates a group of least two calculations, where each calculation includes at least one calculation step.
REFERENCES:
patent: 3617720 (1971-11-01), Gentleman
patent: 3673399 (1972-06-01), Hancke et al.
patent: 3704826 (1972-12-01), Constaintin
patent: 4899301 (1990-02-01), Nishitani et al.
patent: 5430667 (1995-07-01), Takano
patent: 5751616 (1998-05-01), Hegland et al.
Burns Doane Swecker & Mathis L.L.P.
Malzahn David H.
Telefonaktiebolaget LM Ericsson (publ)
LandOfFree
Device and method for calculating FFT does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Device and method for calculating FFT, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Device and method for calculating FFT will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2840749