Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1998-02-04
2001-05-08
Ngo, Chuong Dinh (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06230176
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a fast Fourier transform process. For example, this invention is used in a signal analysis of a voice signal or the like, and a modulation/demodulation process for a digital transmission.
In detail, the invention relates to a fast Fourier transform process that performs a fast Fourier transform process or its inverse transform process of variable sampling points to a series of discrete complex number input signals.
2. Description of the Related Art
Up to now, for example, in a signal analysis of a voice signal, a modulation/demodulation process for a digital transmission, or the like, a fast Fourier transform processing device has been used.
As such a fast Fourier transform processing device, for example, a device disclosed in “ISSCC89, Digest, pp166 to 167, 327, THPM12.5: A 200MIPS Single-Chip 1K FFT Processor” is known.
A fast Fourier transform processing device described in this reference literature performs a computing process by means of data paths composed of a 2-port RAM, a twiddle factor ROM, and plural computing elements.
And this device is provided with plural data paths and improves throughput of the internal computation by performing a parallel processing.
This data path is provided with a pipeline structure composed of a multiplier and an adder-subtracter which are disposed between register files, and performs a Fourier transform for transforming inputted complex number data from a time domain to a frequency domain or an inverse Fourier transform for transforming them from a frequency domain to a time domain by means of this pipeline process.
And this data path performs a fast Fourier transform on the basis of an algorithm of radix 4 in case the number of sampling points is 1024, 256,or 64.
However, since a former fast Fourier transform processing device as disclosed in the above-mentioned reference literature has a data path architecture using a fast Fourier transform algorithm of radix 4, it has a disadvantage that although it can perform a fast transform process when the number of sampling points in the fast Fourier transform is the nth power of 4(namely,4
n
), it is much deteriorated in processing efficiency if the number of sampling points is not 4
n
.
For example, if the number of sampling points is 512 (the 4th power of 4×2) or 128 (the 3rd power of 4×2), although it can perform a fast Fourier transform process itself, its processing speed is very slow since it cannot help but perform a very inefficient process.
And a former fast Fourier transform processing device can perform processing by means of plural devices connected in parallel with one another if its internal working memory is insufficient in capacity. However, in that case, a processing system must be built by adding newly a complex adder-subtracter, a complex multiplier, a working memory, and the like to this device as discrete components, and as a result this causes a disadvantage that the processing device comes to be very large in scale. For example, since the fast Fourier transform processing device disclosed in the above-mentioned reference literature cannot perform by itself a fast Fourier transform in which the number of sampling points is more than 1024, a new system as described above must be built, for example, if the number of sampling points is 2048 or 4096.
SUMMARY OF THE INVENTION
A first object of the present invention is to provide a fast Fourier transform processing device and a fast Fourier transform processing method, which can cope with both fast Fourier transform algorithms of radix 4 and 2.
A second object of the invention is to provide a fast Fourier transform processing system and a fast Fourier transform processing method, which can be performed by having plural chips connected without using additional discrete components if the number of sampling points is doubled.
The present invention attains the above-mentioned objects by means of the following compositions.
(1) A fast Fourier transform processing device according to the first invention comprises:
a working memory for storing complex number data in which the number of sampling points is 4
n
×2 or 4
n
(where n is a natural number), and the data are inputted from the outside and temporarily stored as one group, and
a computing means, which repeats n times a series of computing operations of dividing complex number data stored in said working memory into 4 groups A, B, C and D according to computation series and sampling point numbers, performing the following computations:
ai=
{(
Ai+Ci
)+(
Bi+Di
)}×Wi1 (1)
ci=
{(
Ai+Ci
)−(
Bi+Di
)}×Wi3 (2)
bi=
{(
Ai−Ci
)−
j
(
Bi−Di
)}×Wi2 (3)
di=
{(
Ai−Ci
)+
j
(
Bi−Di
)}×Wi4 (4),
using the ith complex number data Ai, Bi, Ci and Di belonging to these groups A, B, C and D and twiddle factors Wi1, Wi2, Wi3 and Wi4 in relation to every i, and storing the computation results ai, bi, ci and di into said working memory as Ai, Bi, Ci and Di; and in case that said number of sampling points is 4
n
×2, which said data path further performs at one time a process of performing the following computations:
ai=Ai+Bi
(5)
bi=Ai−Bi
(6)
ci=Ci+Di
(7)
di=Ci−Di
(8),
using the complex number data Ai, Bi, Ci and Di obtained by those computations in relation to every i, and storing the computation results ai, bi, ci and di into said working memory.
According to this invention, it is possible to provide by a simple composition a fast Fourier transform processing device capable of coping with both fast Fourier transform algorithms of radix 4 and 2.
(2) A fast Fourier transform processing device according to the second invention comprises;
a working memory for having complex number data in which the number of sampling points is the 4
n
×2 or the 4
n
(where n is a natural number) inputted from the outside and temporarily storing them as one group,
a first computing means which divides the groups of complex number data stored in said working memory into 16 groups AG
1
, BG
1
, CG
1
, DG
1
, AG
2
, BG
2
, CG
2
, DG
2
, AG
3
, BG
3
, CG
3
, DG
3
, AG
4
, BG
4
, CG
4
and DG
4
according to computation series and sampling point numbers, and performs the following computing operations in relation to each of the after-division group combinations {AG
1
, BG
1
, CG
1
, DG
1
}, {AG
2
, BG
2
, CG
2
, DG
2
}, {AG
3
, BG
3
, CG
3
, DG
3
} and {AG
4
, BG
4
, CG
4
, DG
4
}:
ai=
{(
Ai+Ci
)+(
Bi+Di
)}×Wi1 (1)
ci=
{(
Ai+Ci
)−(
Bi+Di
)}×Wi3 (2)
bi=
{(
Ai−Ci
)−
j
(
Bi−Di
)}×Wi2 (3)
di=
{(
Ai−Ci
)+
j
(
Bi−Di
)}×Wi4 (4),
using the ith complex number data Ai, Bi, Ci and Di belonging to the groups of each group combination and the twiddle factors Wi1, Wi2, Wi3 and Wi4,
a transposing means for inputting in four by four the computation results ai, bi, ci and di of said first data pass, forming a matrix of 4 rows and 4 columns, and then transposing said matrix, and after this, outputting column by column the complex number data forming the transposed matrix which have been obtained by these computing operations, and
a second computing means performing one after another said computing operations (1) to (4) using the complex number data inputted from said transposing means as Ai, Bi, Ci and Di, and storing the results ai, bi, ci and di of these computing operations one after another in said group combinations {AG
1
, AG
2
, AG
3
, AG
4
}, {BG
1
, BG
2
, BG
3
, BG
4
}, {CG
1
, CG
2
, CG
3
, CG
4
} and {DG
1
, DG
2
, DG
3
, DG
4
} in said working memory.
Ac
Ngo Chuong Dinh
Rabin & Champagne, P.C.
LandOfFree
Fast fourier transform processing device, 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 Fast fourier transform processing device, fast fourier..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast fourier transform processing device, fast fourier... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2554163