Fast Fourier transform address generator
AssigneeUnited Microelectronics Corp.
InventorsWenzhe Luo, Jiasheng Xu
Life of this patent
Estimating the term…
Abstract
A for Fast Fourier Transform (FFT) address generator utilizes a butterfly counter to count a butterfly count for each butterfly stage of FFT in numerical sequence; and a stage counter to count a stage count for the butterfly stage of FFT in bit-shifting manner. A data address logic is coupled to the butterfly counter and the stage counter to receive the butterfly count and the stage count, and to generate a data address according to a first regularized logic function. A twiddle factor address logic is coupled to the butterfly counter and the stage counter to receive the butterfly count and the stage count, and to generate a twiddle factor address according to a second regularized logic function.
Claims6
An address generator for a 2.sup.m -point FFT comprising:
- a butterfly counting mechanism for counting a butterfly count (B.sub.m-2 B.sub.m-3 . . . B.sub.0) for each butterfly stage of FFT in numerical sequence;
- a stage counting mechanism for counting a stage count (R.sub.m-1 R.sub.m-2 . . . R.sub.0) for the butterfly stage of FFT in bit-shifting manner;
- a data address logic mechanism, coupled to said butterfly counting mechanism and said stage counting mechanism, for receiving said butterfly count (B.sub.m-2 B.sub.m-3 . . . B.sub.0) and said stage count (R.sub.m-1 R.sub.m-2 . . . R.sub.0), and for generating a data address (A.sub.m-1 A.sub.m-2 . . . A.sub.0) according to a first predetermined logic function:
- ##EQU4## wherein S is a select signal for the upper/lower data addresses in a butterfly of FFT;
- and
- a twiddle factor address logic mechanism, coupled to said butterfly counting mechanism and said stage counting mechanism for receiving said butterfly count (B.sub.m-2 B.sub.m-3 . . . B.sub.0) and said stage count (R.sub.m-1 R.sub.m-2 . . . R.sub.0), and for generating a twiddle factor address (C.sub.m-2 C.sub.m-3 . . . C.sub.0) according to a second predetermined logic function:
- (C.sub.m-2 C.sub.m-3 . . . C.sub.0)=R.sub.0 (000 . . . 0)+R.sub.1 (B.sub.0 00 . . . 0)+R.sub.2 (B.sub.1 B.sub.0 0 . . . 0) +. . . +R.sub.m-1 (B.sub.m-2 B.sub.m-3 B.sub.m-4 . . . B.sub.0)
Dependencies are inferred from the claim text.