Monolithic fast Fourier transform circuit

Claim 2

A monolithic circuit for performing a fast Fourier transform (FFT), said circuit comprising: a fast multiplier circuit; a first adder circuit to combine products from said multiplier circuit; a read-only memory for storage of FFT twiddle factors; a two-port random access memory, having a read bus and a write bus, for storage of input data, intermediate results and output data; a data input register connectable to the write bus of said random access memory; a data output register connectable to the read bus of said random access memory; a second adder circuit to combine outputs from said first adder circuit with input and intermediate data from said random access memory; a stack of registers to provide temporary storage for data being transferred between said random access memory and either said multiplier circuit or said second adder circuit; and a control and timing circuit for generating signals to control transfer of data and operation of said multiplier circuit, said random access memory, said first and second adder circuits, and said stack of registers, to effect computation of the FFT of a set of input signals applied to said data input register.

Claim 3

A monolithic circuit as set forth in claim 1, wherein said control and timing circuit includes: an address comparator for comparing a chip selection address supplied to said monolithic circuit with a unique chip identifier, and generating an instruction enabling signal when a match is found; and an instruction decoder for receiving an instruction code indicative of specific circuit functions to be initiated, and an instruction enabling signal from said address comparator, to confirm that the instruction is intended for this particular circuit.

Claim 4

A monolithic circuit as set forth in claim 2, wherein said control and timing circuit further inincludes: a sequencing counter, the contents of which are advanced in response to clock signals; and a preceded logic array operative in response to signals received from said sequencing counter and said instruction decoder, to generate control signals directed to said multiplier circuit, said first and second adder circuits, said stack of registers and said data input and output registers, and address-selection signals to said read-only memory and said random access memory; and wherein the control signals and address-selection signals from said precoded logic array effect computation of the fast Fourier transform of data placed in said random access memory, in accordance with the decimation-in-time method.

Claim 5

A monolithic circuit as set forth in claim 3 1 , wherein: said instruction decoder is responsive to a first instruction code to load a sequence of input data from said input register to said random access memory and begin FFT computation, and a second instruction code to unload FFT coefficients from said random access memory to said output register.

Claim 6

A monolithic circuit as set forth in claim 2, wherein: said input register and said output register are connectable to data bus lines; chip selection address signals applied to said address comparator are supplied over a chip addressing bus; and said monolithic circuit can be conveniently connected to a common bus structure and other monolithic FFT circuits, to facilitate computation of a larger FFT than could be computed in a single monolithic FFT circuit.

Claim 7

A monolithic circuit as set forth in claim 1 or 2, wherein said fast multiplier circuit and said first adder circuit are combined for greater speed into a single multiplier-accumulator circuit.

Claim 8

A monolithic circuit as set forth in claim 6, wherein said stack of registers includes: a first register to hold the real component of a multiplicand; a second register to hold the imaginary component of a multiplicand; a third register to hold a quantity to be added to a product sum from said multiplier-accumulator circuit; and a fourth register to hold a result quantity from said second adder circuit.

Claim 9

A monolithic circuit as set forth in claim I or 2, wherein said fast multiplier circuit employs a modified version of Booth's algorithm.

Claim 10

A monolithic circuit as set forth in claim 8, wherein: the twiddle factors are stored in said read-only memory in a Booth-coded form compatible with the modified version of Booth's multiplication algorithm; and said multiplier circuit is configured to accept multiplier quantities in the Booth-coded form.

Claim 11

A monolithic circuit for performing a fast Fourier transform (FFT) by the decimation-in-time method, said circuit comprising: a read-only memory for storage of FFT twiddle factors; a fast multiplier circuit; a first fast adder circuit to combine products from said multiplier circuit; a second fast adder circuit for perforning butterfly computations in conjunction with said multiplier circuit and said first fast adder circuit; a random access memory having a read bus and a write bus, for initial storage of a sequence of input complex quantities derived from samples of a time-varying signal, and for storage of intermediate and final results in an in-place FFT operation; a register stack to act as a buffer for the transmission of data between said random access memory and said multiplier and adder circuits; a twiddle factor register to act as a buffer between said read-only memory and said multiplier circuit; an input register coupled to the write bus of said random access memory for input of samples of data; an output register coupled to the read bus of said random access memory for output of FFT coefficients; a read-only memory address decoder; a read address decoder for the random access memory; a write address decoder for the random access memory; and a control and timing circuit for generating signals to control transfer of data to and from said multiplier and adder circuits, and to control and operation of said multiplier and adder circuits, to effect computation of the FFT by repeated use of said multiplier and adder circuits to perform butterfly computations.

Claim 12

A monolithic circuit for performing a fast Fourier transform (FFT) by the decimation-in-time method, said circuit comprising: a read-only memory for storage of FFT twiddle factors; a fast multiplier circuit; a first fast adder circuit to combine products from said multiplier circuit; a second fast adder circuit for perforning butterfly computations in conjunction with said multiplier circuit and said first fast adder circuit; a random access memory having a read bus and a write bus, for initial storage of a sequence of input complex quantities derived from samples of a time-varying signal, and for storage of intermediate and final results in an in-place FFT operation; a register stack to act as a buffer for the transmission of data between said random access memory and said multiplier and adder circuits; a twiddle factor register to act as a buffer between said read-only memory and said multiplier circuit; an input register coupled to the write bus of said random access memory for input of samples of data; an output register coupled to the read bus of said random access memory for output of FFT coefficients; a read-only memory address decoder; a read address decoder for the random access memory; a write address decoder for the random access memory; and a control and timing circuit for generating signals to control transfer of data to and from said multiplier and adder circuits, and to control and operation of said multiplier and adder circuits, to effect computation of the FFT by repeated use of said multiplier and adder circuits to perform butterfly computations.

Claim 13

A monolithic circuit as set forth in claim 10, wherein said control and timing circuit includes: an address comparator for comparing a chip selection address supplied to said monolithic circuit with a unique chip identifier, and generating an instruction enabling signal when a match is found; and an instruction decoder for receiving an instruction code indicative of specific circuit functions to be initiated, and an instruction enabling signal from said address comparator, to confirm that the instruction is intended for this particular circuit.

Claim 14

A monolithic circuit as set forth in claim 11, wherein said control and timing circuit further includes: a sequencing counter, the contents of which are advanced in response to clock signals; and a precoded logic array operative in response to signals received from said sequencing counter and said instruction decoder, to generate control signals directed to said multiplier circuit, said first and second adder circuits, said stack of registers and said data input and output registers, and address-selection signals to said read-only memory and said random access memory and wherein the control signals and address-selection signals from said precoded logic array effect computation of the fast Fourier transform of data placed in said random access memory, in accordance with the decimation-in-time method.

Claim 15

A monolithic circuit as set forth in claim 12, wherein: said instruction decoder is responsive to a first instruction code to load a sequence of input data from said'input register to said random access memory and begin FFT computation, and a second instruction code to unload FFT coefficients from said random access memory to said output register.

Claim 16

A monolithic circuit as set forth in claim 11, wherein: said input register and said output register are connectable to data bus lines; chip selection address signals applied to said address comparator are supplied over a chip addressing bus; and sdid monolithic circuit can be conveniently connected to a common bus structure and other monolithic FFT circuits, to facilitate computation of a larger FFT than could be computed in a single monolithic FFT circuit.

Claim 17

A monolithic circuit as set forth in claim 10 or 11, wherein said fast multiplier circuit and said first fast adder circuit are combined for greater speed into a single multiplier-accumulator circuit.

Claim 18

A monolithic circuit as set forth in claim 15, wherein said register stack includes: a first register to hold the real component of a multiplicand; a second register to hold the imaginary component of a multiplicand; a third register to hold a quantity to be added to a product sum from said multiplier-accumulator circuit; and a fourth register to hold a result quantity from said second adder circuit.

Claim 19

A monolithic circuit as set forth in claim 16, wherein: said first and second registers are connected to receive data over the read bus of said random access memory and to transmit multiplicand data to said multiplier-accumulator circuit; said third register is connected to receive, data over the read bus of said random access memory and to transmit data to said second adder circuit; said fourth register is connected to receive sum data from said second adder circuit and to transmit data to the write bus of said random access memory.

Claim 20

A monolithic circuit as set forth in claim 10, wherein said multiplier-accumulator circuit employs a modified version of Booth's algorithm.

Claim 21

A monolithic circuit as set forth in claim 18, wherein: the twiddle factors are stored in said read-only memory in a Booth-coded form compatible with the modified version of Booth's multiplication algorithm; and said multiplier circuit is configured to accept multiplier quantities in the Booth-coded form.

Claim 22

A monolithic circuit as set forth in claim 19, wherein: said monolithic circuit functions to compute a 32-point FFT; said random access memory includes sixty-four words of storage for holding thirty-two complex quantities for in-place computation of the FFT; and said read-only memory includes forty-eight words of storage for holding sixteen complex quantities and their conjugates in Booth's code form, for computation of forward and inverse FFT's.

Claim 23

A large-scale N-point FFT circuit structure, comprising: a first random access storage matrix for holding N complex input quantities in an 1 x m array, where 1 x m = N; a first rank of monolithic FFT circuits coupled to receive input data column-by-column from said first random access storage matrix and to provide intermediate FFT coefficients; a pair of multiplier circuits and a pair of twiddle factor read-only memories to effect rotation of the intermediate FFT coefficients; a second random access storage matrix for Holding the rotated intermediate FFT coefficients; a second rank of monolithic FFT circuits coupled to receive input data row-by-row from said second random access storage matrix and to provide a final set of FFT coefficients; control means for selecting FFT operations on appropriate ones of said monolithic circuits for controlling transfer of data through said circuit structure; and wherein all of said monolithic FFT circuits are connected to a common bus structure and include chip addressing circuitry to permit initiation of appropriate FFT computation, by said control means.

Claim 24

A large-scale N-point FFT circuit structure, comprising: a first random access storage matrix for holding N complex input quantities in an 1 x m array, where 1 x m = N; a first rank of monolithic FFT circuits coupled to receive input data column-by-column from said first random access storage matrix and to provide intermediate FFT coefficients; a pair of multiplier circuits and a pair of twiddle factor read-only memories to effect rotation of the intermediate FFT coefficients; a second random access storage matrix for Holding the rotated intermediate FFT coefficients; a second rank of monolithic FFT circuits coupled to receive input data row-by-row from said second random access storage matrix and to provide a final set of FFT coefficients; control means for selecting FFT operations on appropriate ones of said monolithic circuits for controlling transfer of data through said circuit structure; and wherein all of said monolithic FFT circuits are connected to a common bus structure and include chip addressing circuitry to permit initiation of appropriate FFT computation, by said control means.

Claim 25

A circuit structure as set forth in claim 21, wherein each of said monolithic FFT circuits comprises: a read-only memory for storage of FFT twiddle factors in Booth-coded form; a fast multiplier-accumulator circuit employing a modified Booth's algorithm; a fast adder circuit for performing butterfly computations in conjunction with said multiplier-accumulator circuit; a random access memory having a read bus and a write bus, for initial storage of a sequence of input complex quantities derived from samples of a time-varying signal, and for storage of intermediate and final results in an in-place FFT operation; a register stack to act as a buffer for the transmission of data between said random access memory and said multiplier-accumulator and adder circuits; a twiddle factor register to act as a buffer between said read-only memory and said multiplier-accumulator circuit; an input register coupled to the write bus of said random access memory for input of data; an output register coupled to the read bus or said random access memory for output of FFT coefficients; a read-only memory address decoder; a read address decoder for the random access memory; a write address decoder for the random access memory; and a control and timing circuit for generating signals to control transfer of data to and from, and operation of said multiplier-accumulator and adder circuits, to effect computation of the FFT, by repeated use of said multiplier-accumulator and adder circuits to perform butterfly computations.