2M-point discrete Fourier transform calculator comprising a pre- processor for twice performing extraction of conjugate symmetric and/or antisymmetric components

摘要

An N-point DFT (discrete Fourier transform) calculator comprises a pre- processor responsive to N-point complex input data F.sub. k (k=0 to N-1) for producing N/2-point complex intermediate data G.sub.p (p=0 to N/2-1) and an N/2-point DFT calculating circuit supplied with the intermediate data as N/2-point complex input data for producing in a known manner real and imaginary parts g.sub.q.sup.R and g.sub.q.sup.I of DFT's or IDFT's (inverse DFT) g.sub.q (q=0 to N/2-1) of the latter input data G.sub.p as either real or imaginary parts f.sub.n.sup.R or f.sub.n. sup.I (n=0 to N-1) of even and odd numbered DFT's or IDFT's f.sub.2n' and f.sub.2n'+1 (n'=0 to N/2-1) of the original input data F.sub.k. The pre- processor extracts from the input data F.sub.k a truncated sequence of conjugate symmetric or antisymmetric components H.sub.m, N/2+1 in number, extracts from the truncated sequence conjugate symmetric and antisymmetric components A.sub. p and B.sub.p, N/4!+1 in number where the brackets are the Gauss' notation, and calculates complex products of ones of the latter components A.sub.p or B.sub.p and factors, such as jexp(-j 2&pgr;/N!p) for DFT's or jexp(j 2&pgr;/N!p) for IDFT's, sums of the products and the others of the latter components B.sub.p or A.sub.p, differences between the products and the others B.sub.p or A.sub.p, and conjugate complex data of the differences. For the real parts f.sub.n.sup. R, the sums and the conjugate complex data provide the intermediate data. For the imaginary parts f.sub.n.sup.I, the differences are used instead of the sums. For factors exp(-j 2&pgr;/N!p) or exp(j 2&pgr;/N!p), each of the other components B.sub.p or A.sub.p should include a factor j.