Real time serial fourier transformation circuit

Claim 1

In digital processing apparatus for processing a time series of N complex digital numbers, where ''''N'''' equals 2r and ''''r'''' is an even positive integer, successively to derive each one of the N coefficients of the discrete Fourier Transform of such time series, each one of such coefficients being a different combination of the partial sums and weighted partial differences of the N complex digital numbers, such apparatus including r/2 pairs of successive processing stages, each one of such stages being adapted first to produce partial sums and partial differences between selected ones of the N complex digital numbers and then to weight the partial differences serially to produce, at the output of the last one of the successive processing stages, the desired N coefficients, the improvement comprising: a. r/2 weighting means, each including a digital multiplier disposed in circuit between the processing stages in each one of the r/2 pairs thereof, for weighting the partial differences out of each one of the successive processing stages; and b. r/2 control means, each one operative on the Second processing stage in each one of the r/2 pairs thereof, for delaying selected ones of the partial differences from such processing stage until the partial differences from the associated first processing stage have been passed through the associated digital multiplier.