Patent ID: 6230176
Filing Date: 2001-05-08
Classification: G06F

Abstract:
A fast Fourier transform processing system, comprising:a working memory that stores input complex number data in which a number of sampling points is 2N (N=4.sup.n.times.2 or 4.sup.n, wherein n is a natural number); andcomputing means that performs the following:executing a series of computing processes including:dividing complex number data stored in said working memory into respective groups A1, B1, C1, D1, A2, B2, C2 and D2 according to computation series and sampling point numbers,performing the following computing operations for every i (i=1 to 2N),a1i={(A1i+C1i)+(B1i+D1i)}.times.W1i1 (1)c1i={(A1i+C1i)-(B1i+D1i)}.times.W1i3 (2)b1i={(A1i-C1i)-j(B1i-D1i)}.times.W1i2 (3)d1i={(A1i-C1i)+j(B1i-D1i)}.times.W1i4 (4)a2i={(A2i+C2i)+(B2i+D2i)}.times.W2i1 (5)c2i={(A2i+C2i)-(B2i+D2i)}.times.W2i3 (6)b2i={(A2i-C2i)-j(B2i-D2i)}.times.W2i2 (7)d2i={(A2i-C2i)+j(B2i-D2i)}.times.W2i4 (8),using the ith complex number data A1i, B1i, C1i, D1i, A2i, B2i, C2i and D2i belonging to the groups A1, B1, C1, D1, A2, B2, C2 and D2 and twiddle factors W1i1, W1i2, W1i3, W1i4, W2i1, W2i2, W2i3 and W2i4, andstoring the results a1i, b1i, c1i, d1i, a2i, b2i, c2i and d2i as complex number data A1i, B1i, C1i, D1i, A2i, B2i, C2i and D2i into said working memory;dividing the complex number data stored in said memory into 4 groups according to computation series and sampling point numbers, andrepeating (n-1) times a series of computing processes including:further dividing each of the groups of complex number data stored in said working memory into respective groups A, B, C and D according to computation series and sampling point numbers,performing the following computing operations for to every i (i=1 to 2N):ai={(Ai+Ci)+(Bi+Di)}.times.Wi1 (9)ci={(Ai+Ci)-(Bi+Di)}.times.Wi3 (10)bi={(Ai-Ci)-j(Bi-Di)}.times.Wi2 (11)di={(Ai-Ci)+j(Bi-Di)}.times.Wi4 (12),using the ith complex number data Ai, Bi, Ci and Di belonging to the groups A, B, C and D and the twiddle factors Wi1, Wi2, Wi3 and Wi4, andstoring the results ai, bi, ci and di as complex number data Ai, Bi, Ci and Di into said working memory, andwhen N=4.sup.n.times.2 executing the following computing operations for every i:ai=(Ai+Bi) (13)bi=(Ai-Bi) (14)ci=(Ci+Di) (15)di=(Ci-Di) (16),using the complex number data Ai, Bi, Ci and Di obtained by the additional computing operations, and storing the results a1i, b1i, c1i, a2i, b2i, c2i and d2i into said working memory.