Fft processor with unique addressing

Claim 2

A fast Fourier transform digital processor for processing waveform samples according to the Cooley-Tukey algorithm comprising in combination: a digital calculator operable for simultaneously calculating the equations Ar Br + Wr Cr Ar n/2 Br - Wr Cr where Ar, Br, Cr and Wr are complex factors of said algorithm, said calculator having parallel output data channels; storage means connected to said data channels for storing sets of operands calculated by said calculator; and control means operatively connecting said calculator, said data channels and said storage means for controlling the storing of said operands by pairs produced by said calculator including addressing means selectively operable for simultaneously addressing predetermined sequences of paired storage locations of said storage means.

Claim 3

A fast Fourier transform digital processor in accordance with claim 1 in which said addressing means includes: means for generating a first storage address; means for generating a second storage address by complementing said first address; and means for simultaneously switching said first and second addresses to predetermined paired locations of said storage means.

Claim 4

A fast Fourier transform digital processor in accordance with claim 2 in which said storage means for calculated operands comprise dual storage devices; and said addressing means includes means for simultaneously addressing said first address location in one of said storage devices and said second address location in the other of said storage devices.

Claim 5

A fast fourier transform digital processor in accordance with claim 3 in which said addressing means further includes means for determining the parity of the address of said first address means; and means responsive to a parity determination for selectively controlling the sequential switching of said first and second addresses to said predetermined paired locations of said storage devices.

Claim 6

A fast Fourier transform digital processor in accordance with claim 3 in which said control means further includes means for reverse switching said first and second addresses for reverse pairing of said addresses of said storage devices for successive pairs of operands.

Claim 7

A fast Fourier transform digital processor in accordance with claim 2 in which said first address generator comprises binary counter means; said second address generator comprises means for complementing the address of said binary counter means to produce said second address.

Claim 8

A fast Fourier transform digital processor in accordance with claim 6 in which said address switch means comprises first and second address multiplexors; said first and second address generators being connected to said first and second address multiplexors for addressing said first and second storage devices; and means for selectively gating addresses simultaneously through said multiplexors from said first and second address generators to paired storage locations of said first and second storage devices.

Claim 9

A fast Fourier transform digital processor in accordance with claim 7 in which said selective gating means includes means for determining the parity of the binary address of said counter means; and means responsive to a parity signal from said parity determining means for selectively gating said first and second addresses to paired locations in said storage devices.

Claim 10

A fast Fourier transform digital processor in accordance with claim 8 in which said selective gating means further includes means for switching the parity signal responsive means to reverse the selective gating of said first and second addresses to corresponding paired storage locations in said storage devices.

Claim 11

A fast Fourier transform digital processor for processing waveform samples according to the Cooley-Tukey algorithm comprising in combination: a digital calculator for simultaneously performing the calculation of the equations Ar Br + Wr Cr and Ar n/2 Br - Wr Cr; where Ar, Br, Cr, and Wr are complex factors of said algorithm; means for supplying various roots of the unity coefficient Wr to said calculator; means for supplying a set of digital operands of a sampled waveform in predetermined order and sequence by operand pairs to said digital calculator in synchronism with the supply of said unity coefficient Wr; means for storing a set of operands processed by said calculator in performance of said simultaneous calculations; and control means operatively connected to said calculator, said coefficient supply means, said operand supply means, and said operand storage means for streaming said set of sampled waveform and calculated operands simultaneously by operand pairs in a plurality of successive passes through said calculator in synchronism with selectively varied roots of said unity coefficients and simultaneously restoring in said storage means by operand pairs the successively derived sets of operands produced by said calculator; said control means further including means for selectively ordering said operand pairs and said roots of the unity coefficient Wr as a function of the pass of said sets operand data through said calculator.

Claim 12

A fast Fourier transform digital processor for processing waveform samples according to the Cooley-Tukey algorithm comprising in combination: a digital calculator for simultaneously performing the calculation of the equations Ar Br + Wr Cr and Ar n/2 Br - Wr Cr; where Ar, Br, Cr, and Wr are complex factors of said algorithm; means for supplying various roots of the unity coefficient Wr to said calculator; means for supplying a set of digital operands of a sampled waveform in predetermined order and sequence by operand pairs to said digital calculator in synchronism with the supply of said unity coefficient Wr; means for storing a set of operands processed by said calculator in performance of said simultaneous calculations; and control means operatively connected to said calculator, said coefficient supply means, said operand supply means, and said operand storage means for streaming said set of sampled waveform and calculated operands simultaneously by operand pairs in a plurality of successive passes through said calculator in synchronism with selectively varied roots of said unity coefficients and simultaneously restoring in said storage means by operand pairs the successively derived sets of operands produced by said calculator; said control means further including means for selectively ordering said operand pairs and said roots of the unity coefficient Wr as a function of the pass of said sets operand data through said calculator.

Claim 13

A fast Fourier transform digital processor in accordance with claim 10 in which said storing means comprises dual storage devices operatively connected to said calculator to store calculated operand sets generated by said calculator; said means for streaming operand pairs of said operand sets includes means for simultaneously addressing paired storage locations in said dual storage devices in a predetermined sequence of paired addresses for each pass; and said means for selectively ordering said operand pairs in said predetermined sequence for streaming operand pairs through said calculator and to said storage devices includes control means for determining the pass condition of said calculator and means responsive to the pass determining means for selectively altering the simultaneously paired addressing sequences of said addressing means.

Claim 14

A fast Fourier transform digital processor in accordance with claim 11 in which said simultaneous addressing means comprises binary count means for generating a fiRst storage location address; means for complementing said storage location address of said binary count means for generating a second complementary storage location address paired with said first address; and means for selectively controlling the complementary addressing means as a function of the pass of said processor for ordering the operand pairs of said operand sets.

Claim 15

A fast Fourier transform digital processor in accordance with claim 12 in which said binary count means includes a multistage binary counter and means for incrementing said binary counter in ascending numerical order each pass of said processor and said complementary address means includes means for complementing said first binary address in descending order by bit as a function of the pass of said processor.

Claim 16

A fast Fourier transform digital processor in accordance with claim 13 in which said address generation means comprises: write address generation means for simultaneously addressing paired storage locations of said dual storage devices; read address generation means for simultaneously addressing paired storage locations of said dual storage devices; and control means for selectively operating said write and read address generation means sequentially to order the simultaneous addressing of said dual storage devices in an ''''in place'''' operation of said processor.

Claim 17

A fast Fourier transform digital processor in accordance with claim 14 in which said write and read addressing means comprise binary count means and complementing means operatively interconnected for generating primary and complementary storage addresses, respectively; and said control means includes means for selectively operating said count and said complementing means in timed relation with the operation of said processor.

Claim 18

A fast Fourier transform digital processor in accordance with claim 15 in which said supply means for said Wr coefficient is a read only storage device in which said unity coefficients are stored in locations in which the storage address corresponds with the numerical root designation of said coefficient.

Claim 19

A fast Fourier transform digital processor comprising, in combination: a digital calculator capable of simultaneously calculating the equations: Ar Br + Wr Cr (1) Ar n/2 Br - Wr Cr (2) where Ar, Br, Cr, and Wr are complex factors of the Cooley-Tukey algorithm; said calculator having parallel operand and coefficient input data channels and parallel operand output data channels; dual storage devices for storing operand data generated by said calculator; output switch means connecting said output operand data channels to said storage device; storage means for n/4 roots of the unity coefficient Wr; input switch means respectively connecting said dual storage devices to said operand input data channels and said coefficient storage means to said coefficient input data channel; control means operatively connecting said calculator, said coefficient and said operand storage devices for cycling a set of operand data from said storage device with coefficient data from said storage means through said calculator in a series of passes including means for controlling the input switch means for simultaneously switching operand data by operand pairs from said storage devices to said operand input channels of said calculator and for switching coefficient data from said storage means to said coefficient channel of said calculator; and means for controlling the output switch means of said output channels for simultaneously restoring computed operand pairs from said calculator into said dual storage devices.

Claim 20

A fast Fourier transform digital processor comprising, in combination: a digital calculator capable of simultaneously calculating the equations: Ar Br + Wr Cr (1) Ar n/2 Br - Wr Cr (2) where Ar, Br, Cr, and Wr are complex factors of the Cooley-Tukey algorithm; said calculator having parallel operand and coefficient input data channels and parallel operand output data channels; dual storage devices for storing operand data generated by said calculator; output switch means connecting said output operand data channels to said storage device; storage means for n/4 roots of the unity coefficient Wr; input switch means respectively connecting said dual storage devices to said operand input data channels and said coefficient storage means to said coefficient input data channel; control means operatively connecting said calculator, said coefficient and said operand storage devices for cycling a set of operand data from said storage device with coefficient data from said storage means through said calculator in a series of passes including means for controlling the input switch means for simultaneously switching operand data by operand pairs from said storage devices to said operand input channels of said calculator and for switching coefficient data from said storage means to said coefficient channel of said calculator; and means for controlling the output switch means of said output channels for simultaneously restoring computed operand pairs from said calculator into said dual storage devices.

Claim 21

A fast Fourier transform digital processor in accordance with claim 17 in which said control means includes means for simultaneously cross switching operand data pairs from said operand data storage devices to the operand data channels in predetermined sequences as a function of the pass of said processor.

Claim 22

A fast Fourier transform digital processor in accordance with claim 18 in which said control means includes means for altering the sequence of cross switching of said operand pairs to said operand channels as a function of the pass of said processor.

Claim 23

A fast Fourier transform digital processor in accordance with claim 19 in which said control means further includes means for altering the ordering of roots of the unity coefficient switched to said Wr input channel as a function of the pass of said processor.

Claim 24

A fast Fourier transform digital processor in accordance with claim 20 in which said control means for alterably cross switching the operands to said operand input channels from said dual storage device and for switching said roots of unity of said coefficient Wr to said coefficient input channel includes: means for generating a first switch control pulse every n/2P times in a pass and a second switch control pulse every n/2P 1 times in a pass where n equals the number of data operand pairs being processed in a pass by said processor and p equals the number of the pass.