Pipelined fast fourier transform (FFT) processor having...

Details Pipelined fast fourier transform (FFT) processor having... Pipelined fast fourier transform (FFT) processor having...

1999-05-03

2002-04-02

Ngo, Chuong Dinh (Department: 2121)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

C708S406000, C708S408000

Reexamination Certificate

active

06366936

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a pipelined FFT (fast Fourier transform) construction, and more particularly, to an improved FFT processor having a CBFP (convergent block floating point) algorithm.
2. Description of the Background Art
A fast Fourier transform is one of the most significant algorithms in a DSP (digital signal processing) field and it is a general term representing DFT (discrete Fourier transform).
The FFT algorithm is implemented in integrated circuits of one or more physical devices so as to process a signal at real time. The fast Fourier transform operation is performed by a software implemented in a programmable DSP or by an FFT-exclusive processor. The most significant part in the FFT processor hardware system is a butterfly processor performing arithmetic operation. A FFT butterfly calculation is implemented by a &ggr;-point data operation. Here, &ggr; refers to radix.
N-point FFT employs N/&ggr; butterfly units per stage (block) for log
&ggr;
N stage (hereinafter, “stage”). At this time, the operation result of a single butterfly stage is applied to a subsequent butterfly stage.
With regard to an N-point direct DFT (discrete Fourier transform), a basic equation is as follows.
X
⁡
(
K
)
=
∑
n
=
0
N
-
1
⁢
x
⁡
(
n
)
⁢
W
N
nk
,
K
=
0
,
1
,
…
⁢
 
,
N
-
1
(
1
)
wherein, n denotes time index, k denotes frequency index, N denotes point, and W
N
(=e
−j(2&pgr;/N)
) denotes twiddle factor.
FIG. 1
shows a basic construction of radix-2 butterfly unit expressing equation 1 by butterfly. The relations between input and output are as follows.
X[k]=x[n]+x[n+N/
2
]W
N
k
X[k+N/
2
]=x[n]−x[n+N/
2
]W
N
k
FIG. 2
is a signal flow chart illustrating a 16-point radix-2 FFT processor. The butterfly operation of the 16-point FFT is implemented by 4 butterfly stages (blocks) I, II, III, IV and each stage includes 8 butterflies.
Also,
FIG. 3
is a signal flow chart illustrating a radix-4 butterfly unit implementing equation 1 by butterfly, and
FIG. 4
is a signal flow chart illustrating a 16-point radix-4 FFT processor. The butterfly calculation of the 16-point FFT is performed by 2 butterfly stages and each stage includes 4 butterflies.
Such a butterfly operation using a Cooley-Tukey algorithm uses a “drive and conquer” method so that the calculation process can be decreased to N log N. However, when implementing the same in hardware, it becomes difficult to apply thereto a flexibility, regularity and in-place computation.
FIG. 5
is a schematic block diagram illustrating a conventional FFT processor having a single butterfly unit. As shown therein, RAM
10
serves to relocate an input data Data_in, RAM
13
stores therein an operation result of a butterfly unit
11
. The RAMs
10
,
13
respectively include an N-word RAM. The butterfly unit
11
includes complex number multipliers (4 multipliers and 2 adders) and 4 adders. ROM
12
stores therein a twiddle element W
N
k
, and a controller
14
controls access operation of the RAMs
10
,
13
and the butterfly operation of the butterfly unit
11
.
Therefore, the butterfly unit
11
employs the access data of the RAM and the twiddle element read from the ROM
12
to perform a butterfly operation of N-point FFT, and the operation result is temporarily stored in the RAM
13
. When all the butterfly operation is completed, the final output data Data_out is outputted from the RAM
13
in accordance with the control of the controller
14
.
Here, although the conventional FFT processor is appropriate to a small point FFT operation, it is not suitable to a large point FFT calculation. This is because there are required number (N/&ggr;)log
&ggr;
N of radix-&ggr; butterfly units for N-point FFT calculation and number 2N of RAMs for storing the intermediate data as a major factor determining a chip area during FFT processor fabrication. Also, there is required 2N log
&ggr;
N times of read/write access with regard to number 2N of RAMs. Accordingly, during the large point FFT fabrication and calculation the conventional FFT processor leads to a speed decrease and an area increase and in a worse case it may be impossible to realize a hardware implementation.
FIG. 6
is a schematic block diagram illustrating a conventional pipelined FFT processor for a radix-4 butterfly operation as disclosed in U.S. Pat. No. 5,163,017.
The pipelined FFT processor includes a RAM
22
for appropriately relocating input data in correspondence to a butterfly operation, a controller
20
for controlling the RAM
22
and an address generator
21
, a coefficient ROM
24
for storing therein the twiddle element, a coefficient address generator
23
for controlling the coefficient ROM
24
and a pipelined data path block
25
for performing a butterfly operation. The pipelined FFT structure is provided such that a single butterfly calculation is implemented in a single pipelined cycle.
The operation of the thusly constituted conventional pipelined FFT processor will now be described.
The address generator
21
outputs a read/write address signal in accordance with a control signal from the controller
20
, and the coefficient address generator
23
outputs the coefficient address signal to the coefficient ROM
24
so as to read the twiddle coefficient.
The RAM
22
relocates the input data Data_in in accordance with the write address signal of the address generator
23
and outputs 4 data to the pipelined data path block
25
. The coefficient ROM
24
outputs two twiddle coefficients for the radix-4 butterfly operation in accordance with the coefficient address signal from the coefficient address generator
23
. Here, the coefficient ROM includes two storage ROMs so as to simultaneously read two twiddle coefficients and three ROMs may be employed in case of simultaneously reading three twiddle coefficients.
Therefore, the pipelined data path block
25
employs the data accessed from the RAM
22
and two twiddle coefficients read from the coefficient ROM
24
and implements a butterfly operation with the provision of 16 addition/subtractions and 3 complex number multiplications. At this time, 3 complex number twiddle coefficients read from the coefficient ROM
24
are employed for the complex number multiplication and the output data Data_in generated from the respective butterfly operations are stored in the RAM
22
.
As described above, the conventional pipelined FFT processor partially stores the input data Data_in and the output data Data_out in the RAM
22
so as to implement the butterfly operation. Accordingly, the above structure has an advantage for significantly saving memory (RAM) required to store the intermediate data when compared to the FFT processor as shown in FIG.
5
.
However, the conventional FFT processor additionally requires the RAM
22
and the address generator
21
to relocate the input data Data_in and includes a complicated pipelined data path block
25
for enabling the butterfly operation. Here, the detailed description of the pipelined datapath block
25
will be omitted for convenience' sake. Also, eight pipelines should be passed in order to implement a single butterfly in the datapath block
25
so that there disadvantageously occur a plurality of pipeline delays.
A block floating point algorithm advantageously processes a block data at high speed and it is widely employed in butterfly operation. Since a general butterfly processor includes fixed-point multipliers and adders, a data range increases in accordance with the operation of multiplication, addition and subtraction, thereby generating an overflow. Accordingly, the overflow should be detected in order to appropriately shift the overflowed data.
FIG. 7
is a schematic view illustrating a conventional block floating point mechanism. As shown therein, the block floating point mechanism includes a shifter
30
, a butterfly processor
31
connected to the shifter
30
and an ov

Affiliated with

Also associated with

Rating

Pipelined fast fourier transform (FFT) processor having... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Pipelined fast fourier transform (FFT) processor having..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pipelined fast fourier transform (FFT) processor having... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2844809