Method of and arrangement for calculating the discrete Fourier transform by means of two circular convolutions

Claim 3

A process for performing a discrete Fourier transformation on an input array of N input signal values a(k), k=0, 1, 2, . . . , N-1, wherein N is a prime, to derive an output array of at most N output signal values representative of the frequency transformation of said input array, said processor comprising: means for separating the input signal value a(0) from said input array of N input signal values to generate a modified input array of N-1 input signal values consisting of the input signal values a(1), a(2), . . . a(N-1); permuting circuit for permuting the N-1 input signal values of the modified input array to produce a permuted array of N-1 permutation signal values b(i), i=1, 2, . . . , N-1, each such permutation signal value b(i) being equal to an input signal value a(g N-1 mod N), wherein g is a positive integer which is equal to a primititive root of a field consisting of the numbers 1, 2, 3, . . . N-1; an intermediate processing circuit for adding and subtracting first and second permutation signal values selected from said permuted array to produce first and second intermediate arrays of M intermediate first and second signal values b 1 (q) and b 2 (q) respectively, wherein M=(N-1)2 q=1, 2, 3, . . . M b.sub.1 (q)=b(q)+b(M+q) b.sub.2 (q)=b(q)-b(M+q) a first conversion circuit for converting the first intermediate array of M intermediate first signal values b 1 (q) into a first auxiliary array of M auxiliary first signal values y 1 (p), p-1, 2, 3, . . . M, wherein the relation between each auxiliary first signal value y 1 (p) and the M intermediate first signal values b 1 (q) is given by the expression: ##EQU22## in which α represents a constant; a second conversion circuit for converting the second intermediate array of M intermediate second signal values b 2 (q) into a second auxiliary array of M auxiliary second signal values y 2 (p), wherein the relation between each auxiliary second signal value y 2 (p) and the M intermediate second signal values b 2 (q) is given by the expression: ##EQU23## in which β represents a constant and wherein j=√-1; an output processing circuit for adding to each auxiliary first signal value y 1 (p) a weighted version of a selected one of the auxiliary second signal values y 2 (p) to produce an output array of N-1 output signal values z(n)-Aa(0), n-1, 2, 3, . . . N-1 which are each proportional to the discrete Fourier transform of the input array of N input signal values and which satisfy the expression: z(n)-Aa(0)=y.sub.1 (p)+(-1).sup.S y.sub.2 (p) wherein S=+1 for n=g P mod N S=0 for n=g M+p mod N A being a constant.

Claim 4

A process for performing a discrete Fourier transformation on an input array of N input signal values a(k), k=0, 1, 2, . . . , N-1, wherein N is a prime, to derive an output array of at most N output signal values representative of the frequency transformation of said input array, said processor comprising: means for separating the input signal value a(0) from said input array of N input signal values to generate a modified input array of N-1 input signal values consisting of the input signal values a(1), a(2), . . . a(N-1); permuting circuit for permuting the N-1 input signal values of the modified input array to produce a permuted array of N-1 permutation signal values b(i), i=1, 2, . . . , N-1, each such permutation signal value b(i) being equal to an input signal value a(g N-1 mod N), wherein g is a positive integer which is equal to a primititive root of a field consisting of the numbers 1, 2, 3, . . . N-1; an intermediate processing circuit for adding and subtracting first and second permutation signal values selected from said permuted array to produce first and second intermediate arrays of M intermediate first and second signal values b 1 (q) and b 2 (q) respectively, wherein M=(N-1)2 q=1, 2, 3, . . . M b.sub.1 (q)=b(q)+b(M+q) b.sub.2 (q)=b(q)-b(M+q) a first conversion circuit for converting the first intermediate array of M intermediate first signal values b 1 (q) into a first auxiliary array of M auxiliary first signal values y 1 (p), p-1, 2, 3, . . . M, wherein the relation between each auxiliary first signal value y 1 (p) and the M intermediate first signal values b 1 (q) is given by the expression: ##EQU22## in which α represents a constant; a second conversion circuit for converting the second intermediate array of M intermediate second signal values b 2 (q) into a second auxiliary array of M auxiliary second signal values y 2 (p), wherein the relation between each auxiliary second signal value y 2 (p) and the M intermediate second signal values b 2 (q) is given by the expression: ##EQU23## in which β represents a constant and wherein j=√-1; an output processing circuit for adding to each auxiliary first signal value y 1 (p) a weighted version of a selected one of the auxiliary second signal values y 2 (p) to produce an output array of N-1 output signal values z(n)-Aa(0), n-1, 2, 3, . . . N-1 which are each proportional to the discrete Fourier transform of the input array of N input signal values and which satisfy the expression: z(n)-Aa(0)=y.sub.1 (p)+(-1).sup.S y.sub.2 (p) wherein S=+1 for n=g P mod N S=0 for n=g M+p mod N A being a constant.

Claim 5

An arrangement as claimed in claim 2, characterized in that each of the first and the second conversion circuits comprises a circular discrete filter having an impulse response of length M.