Fft processor utilizing variable length shift registers

Claim 2

In a digital spectral analyzer containing a fast Fourier transform unit utilizing the Cooley-Tukey algorithm for computing the Fourier transform coefficients from a number N of digitized samples of an input signal and including an arithmetic unit controlled by a clock actuated trigonometric function generator, said arithmetic unit receiving at first and second input terminals respectively a pair of signals A and B each comprising N/2 digitized values and on reiterative passes P performing rotation Z in rectangular co-ordinates and complex addition on said pair of signals to produce first and second output signals A'' A + B exp (- J2 pi Z/N) and B'' A - B exp (- j2 pi Z/N) the improvement comprising: first and second shift register means having input and output terminals and having lengths which vary according to the relationship N/4P, said first register means input terminal connected to receive the second output signal B'' of said arithmetic unit, said second register means output terminal connected to the first input of said arithmetic unit, third shift register means of fixed length equal to N/2having an input and output terminal said output terminal connected to the second input of said arithmetic unit, and switching means alternately operable between a first and second condition at a rate according to the relationship N/4P, having a first input terminal connected to receive the first output signal A'' of said arithmetic unit, having a second input terminal connected to said first shift register means output terminal and having a first output terminal connected to said second shift register means input terminal, having a second output terminal connected to said third shift register means input terminal, said switching means being such that in said first condition said first and second input terminals are connected respectively to said first and second output terminals and in said alternate second condition said first input terminal is connected to said second output terminal and said second input terminal is connected to said first output terminal, said shift registers having lengths such that in said first switch condition the length of said secOnd shift register means equals the combined lengths of said first and third shift register means, whereby said digitized values are staggered in time and are placed in order for a next reiterative pass through said arithmetic unit.

Claim 3

In a digital spectral analyzer containing a fast Fourier transform unit utilizing the Cooley-Tukey algorithm for computing the Fourier transform coefficients from a number N of digitized samples of an input signal and including an arithmetic unit controlled by a clock actuated trigonometric function generator, said arithmetic unit receiving at first and second input terminals respectively a pair of signals A and B each comprising N/2 digitized values and on reiterative passes P performing rotation Z in rectangular coordinates and complex addition on said pair of signals to produce first and second output signals A'' A + B exp (- j2 pi Z N) Z/NB'' A - B exp ( -j290 Z/N) the improvement comprising: first shift register means having input and output terminals and having a length given by the relationship N/2, said output terminal being connected to the first input terminal of said arithmetic unit, second and third shift register means each having input and output terminals and each having a length equal to one-eighth the length of said first register means, the input terminal of said second register means being connected to receive the second output signal B'' of said arithmetic unit, fourth shift register means having input and output terminals and having a length equal to one-fourth the length of said first register means, fifth shift register means having input and output terminals and having a length equal to one-half the length of said first register means, the output terminal of said fifth register means being connected to the second input terminal of said arithmetic unit, and switching means having first, second, third and fourth input terminals and first, second, third and fourth output terminals and being operable among first, second, third and fourth switch conditions at a rate N/4P and in the condition sequence: first, second, first, third, first, fourth, first, the first, second, third and fourth input terminals of said switching means being connected respectively to the first output terminal of said arithmetic unit, the output terminal of said fourth register means, the output terminal of said third register means, and the output terminal of said second register means, the first, second, third and fourth output terminals of said switching means being connected respectively to the input terminal of said first register means, the input terminal of said fifth register means, the input terminal of said fourth register means, and the input terminal of said third register means, in said first switch condition said first, second, third and fourth switch input terminals being connected respectively to said first, second, third and fourth switch output terminals, in said second switch condition said first and second switch input terminals being connected respectively to said second and first switch output terminals and said third and fourth switch input terminals being connected respectively to said third and fourth switch output terminals, in said third switch condition said first and third switch input terminals being connected respectively to said third and first switch output terminals and said second and fourth switch input terminals being connected respectively to said second and fourth switch output terminals, in said fourth switch condition said first and fourth switch input terminals being connected respectively to said fourth and first switch output terminals and said second and third switch input terminals being connected respectively to said second and third switch output terminals.

Claim 4

In a digital spectral analyzer containing a fast Fourier transform unit utilizing the Cooley-Tukey algorithm for computing the Fourier transform coefficients from a number N of digitized samples of an input signal and including an arithmetic unit controlled by a clock actuated trigonometric function generator, said arithmetic unit receiving at first and second input terminals respectively a pair of signals A and B each comprising N/2 digitized values and on reiterative passes P performing rotation Z in rectangular coordinates and complex addition on said pair of signals to produce first and second output signals A'' A + B exp (- j2 pi Z N) Z/NB'' A - B exp ( -j290 Z/N) the improvement comprising: first shift register means having input and output terminals and having a length given by the relationship N/2, said output terminal being connected to the first input terminal of said arithmetic unit, second and third shift register means each having input and output terminals and each having a length equal to one-eighth the length of said first register means, the input terminal of said second register means being connected to receive the second output signal B'' of said arithmetic unit, fourth shift register means having input and output terminals and having a length equal to one-fourth the length of said first register means, fifth shift register means having input and output terminals and having a length equal to one-half the length of said first register means, the output terminal of said fifth register means being connected to the second input terminal of said arithmetic unit, and switching means having first, second, third and fourth input terminals and first, second, third and fourth output terminals and being operable among first, second, third and fourth switch conditions at a rate N/4P and in the condition sequence: first, second, first, third, first, fourth, first, the first, second, third and fourth input terminals of said switching means being connected respectively to the first output terminal of said arithmetic unit, the output terminal of said fourth register means, the output terminal of said third register means, and the output terminal of said second register means, the first, second, third and fourth output terminals of said switching means being connected respectively to the input terminal of said first register means, the input terminal of said fifth register means, the input terminal of said fourth register means, and the input terminal of said third register means, in said first switch condition said first, second, third and fourth switch input terminals being connected respectively to said first, second, third and fourth switch output terminals, in said second switch condition said first and second switch input terminals being connected respectively to said second and first switch output terminals and said third and fourth switch input terminals being connected respectively to said third and fourth switch output terminals, in said third switch condition said first and third switch input terminals being connected respectively to said third and first switch output terminals and said second and fourth switch input terminals being connected respectively to said second and fourth switch output terminals, in said fourth switch condition said first and fourth switch input terminals being connected respectively to said fourth and first switch output terminals and said second and third switch input terminals being connected respectively to said second and third switch output terminals.