Arrayable modular FFT processor

Claim 2

A modular, arrayable, FFT processor for performing a preselected N-point FFT algorithm, comprising: input memory means for receiving and storing data from a plurality of input lines and for storing products and summations; Direct Fourier Transformation (DFT) means connected to receive data from said input memory means for selectively performing R-pint direct Fourier transformations on said data according to said FFT algorithm, where R is less than eight; arithmetic logic means connected at a first input with an output of said DFT means for performing multiplications and for accumulating complex data and multiplication products for forming positive and negative summations according to said FFT algorithm and having an output connected to said input memory for storage of intermediate products and summations for the FFT algorithm; adjusted twiddle factor storage means connected to a second input of said arithmetic logic means for providing phase adjusting twiddle-factor coefficients for implementation of said FFT algorithm, which coefficients are preselected according to a desired size of the Fourier transformation being performed and a relative array position of the arrayable FFT processor in an array of z such processors; and output means connected to an output of said arithmetic logic means for transferring results of said FFT algorithm to a plurality of output lines.

Claim 3

The FFT processor of claim 1 wherein said DFT is configured to selectively alter R between 2, 3, 4, and 6 depending upon a preselected FFT point size.

Claim 4

The FFT processor of claim 1 wherein said DFT is configured to selectively alter R between 2 and 4 depending upon a preselected FFT point size.

Claim 5

The FFT processor of claim 1 wherein said DFT is configured to selectively alter R between 3 and 6 depending upon a preselected FFT point size.

Claim 6

The FFT processor of claim 1 wherein said adjusted, twiddle-factor storage means comprises: basic twiddle-factor coefficient memory containing coefficient values required to compute mixed n power-of-two, m power-of-three, p power-of-four, and q power-of-six FFT's, where N=2 n 3 m 4 p 6 q and has a predetermined maximum value less than or equal to 64; incremental twiddle-factor coefficient memory containing coefficients required to incrementally adjust said basic coefficients through multiplication to generate coefficients necessary to compute all mixed power-of-two, power-of-three, power-of-four, and power-of-six FFTs up to a predetermined maximum-size FFT point value T, where T≧N; multiplication means connected to receive coefficients from both said basic and incremental twiddle-factor coefficient memories for generating the product thereof; and synergist twiddle-factor storage means for storing said product as synergistic twiddle-factors.

Claim 7

The FFT processor of claim 5 wherein T is the product of all N z where N is the preselected FFT point size for each of z such processors in an array of processors.

Claim 8

The processor of claim 5 wherein the processor is configured to perform 1 through 64/N N-point-FFT computations.

Claim 9

The FFT processor of claim 5 wherein p=q=O and N=2 n 3 m .

Claim 10

The FFT processor of claim 1 wherein said arithmetic logic means comprises: multiplication means connected in series with an output of said DFT means for performing multiplications according to said FFT algorithm, and accumulation means connected in series with said multiplication means for accumulating complex data and multiplication products for forming positive and negative summations and according to said FFT algorithm.

Claim 11

The FFT processor of claim 9 further comprising selection means disposed in series between outputs of both said DFT and twiddle-factor storage means and an input of said multiplication means for selectively coupling one of said outputs at a time to said multiplication means input.

Claim 12

The processor of claim 1 further comprising control means for providing clock signals for said input memory, Direct Fourier Transformation, arithmetic logic, adjusted twiddle-factor storage, and output means so as to synchronize their operations and set data input/output rates for said processor to interface with other apparatus, and for providing control signals which select desired values for N, R, and T.

Claim 13

The processor of claim 11 wherein said control signals comprise a series of control bits for setting said DFT means to a selected one of said R-point FFTs and control bits for selecting correct ones of said adjusted twiddle-factors associated with the value of T.

Claim 14

The processor of claim 12 wherein said control means further comprises: parameter storage means for storing a plurality of control bit patterns useful in setting said predetermined values for N, R, and T; and selection means connected to said parameter storage means having programmable input pins capable of being electrically interconnected to select desired ones of said control bit patterns.

Claim 15

The processor of claim 12 wherein at least one of said control bit patterns comprises an initialization control pattern which activates said basic and incremental twiddle-factor selection and generation of products thereof at an initialization stage for said processor.

Claim 16

The processor of claim 1 wherein said input and output means are configured to transfer input data and output data in a complex 32-bit 2's-complement format comprising 16 real and 16 imaginary bits.

Claim 17

The processor of claim 1 wherein said input memory means comprises an M-word ping-pong input buffer and scratchpad memory.

Claim 18

The processor of claim 1 wherein said plurality of input and output lines comprise 64 signal-input lines and 64 signal-output lines.

Claim 19

The processor of claim 1 further comprising input formatting means connected in series with said plurality of signal-input lines for converting input data into a predetermined parallel format.

Claim 20

The processor of claim 1 further comprising an output formatting means connected in series with said plurality of signal-output lines for converting output data from parallel format to a predetermined serial format.

Claim 21

The processor of claim 1 further comprising scaling means connected in series with said arithmetic logic means for selectively applying block floating point, divide-by-two and divide-by-four scaling.

Claim 22

A programmable, arrayable, signal-processing device useful for computing N-point FFT algorithms in an array of z such devices, with 64 signal-input lines and 64 signal output lines, comprising: an input formatting register connected in series with said signal-input lines being configured for converting received data into a predetermined parallel format; a 64-word plus 64-word ping-pong type input memory connected in series with said input formatting register; Direct Fourier Transformation means connected to receive data from said input memory means for performing 2-point direct Fourier transformations on said data according to said FFT algorithm; a 16-bit by 16 2's-bit complement, fully parallel modified Booth multiplier with true rounding connected to receive data from said Direct Fourier Transformation means; a basic 64-point transform twiddle-factor coefficient memory containing coefficient values necessary to compute all power-of-two FFT's from an 8-point FFT up to a 64-point FFT; an incremental-twiddle-factor coefficient memory containing coefficients required to incrementally adjust said basic coefficients through multiplication to generate synergist-twiddle-factor coefficients which are necessary to compute all mixed power-of-two FFT up to a maximum T-point size, where T≦4096; transfer means connected to outputs for both said basic and incremental coefficient memories and an input of said multiplier for transferring coefficients to said multiplier; a complex accumulator connected in series with said multiplier and having an output connected to one of said ping-pong memories for transferring FFT-butterfly computations thereto; a 64-word plus 64-word ping-pong type output memory connected to receive data from said accumulator; an output formatting register configured to selectively format parallel format output data to predetermined serial or parallel formats; and control means connected to each of said input formatting register, input memory, multiplier, basic twiddle-factor storage, adjusted twiddle-factor storage, complex accumulator, transfer means, output memory and output formatting register for providing clock signals thereto for synchronizing their operations and controlling data input/output rates for said processor to interface with other apparatus, and for providing control signals which select desired values for N.

Claim 23

A programmable, arrayable, signal-processing device useful for computing N-point FFT algorithms in an array of z such devices, with 64 signal-input lines and 64 signal output lines, comprising: an input formatting register connected in series with said signal-input lines being configured for converting received data into a predetermined parallel format; a 64-word plus 64-word ping-pong type input memory connected in series with said input formatting register; Direct Fourier Transformation means connected to receive data from said input memory means for performing 2-point direct Fourier transformations on said data according to said FFT algorithm; a 16-bit by 16 2's-bit complement, fully parallel modified Booth multiplier with true rounding connected to receive data from said Direct Fourier Transformation means; a basic 64-point transform twiddle-factor coefficient memory containing coefficient values necessary to compute all power-of-two FFT's from an 8-point FFT up to a 64-point FFT; an incremental-twiddle-factor coefficient memory containing coefficients required to incrementally adjust said basic coefficients through multiplication to generate synergist-twiddle-factor coefficients which are necessary to compute all mixed power-of-two FFT up to a maximum T-point size, where T≦4096; transfer means connected to outputs for both said basic and incremental coefficient memories and an input of said multiplier for transferring coefficients to said multiplier; a complex accumulator connected in series with said multiplier and having an output connected to one of said ping-pong memories for transferring FFT-butterfly computations thereto; a 64-word plus 64-word ping-pong type output memory connected to receive data from said accumulator; an output formatting register configured to selectively format parallel format output data to predetermined serial or parallel formats; and control means connected to each of said input formatting register, input memory, multiplier, basic twiddle-factor storage, adjusted twiddle-factor storage, complex accumulator, transfer means, output memory and output formatting register for providing clock signals thereto for synchronizing their operations and controlling data input/output rates for said processor to interface with other apparatus, and for providing control signals which select desired values for N.

Claim 24

The device of claim 21 wherein said multiplier and said accumulator are selectively connected to said input buffer/ping-pong memory and said DFT means so as to perform mixed radix-2 and computations in executing said N-point FFT computation.

Claim 25

The device of claim 21 wherein said multiplier and said accumulator are selectively connected to said input buffer/ping-pong memory and said DFT means so as to perform all integral sub-multiples of mixed power-of-two and FFT computations in executing said N-size FFT computation.

Claim 26

The device of claim 21 wherein said multiplier and said accumulator are selectively connected to said input buffer/ping-pong memory and said DFT means so as to perform 1 through 32 2-point-FFT computations.

Claim 27

The processor of claim 21 wherein said control means further comprises: parameter storage means for storing a plurality of control bits useful in setting predetermined values for N, and T; and selection means connected to said parameter storage means having programmable input pins capable of being electrically interconnected to select desired ones of said control bits.

Claim 28

The processor of claim 25 wherein at least one of said control bit patterns comprises an initialization control pattern which activates said basic and incremental twiddle-factor selection and generation of products thereof at an initialization stage for said processor.

Claim 29

The device of claim 21 further comprising selection means disposed in series between an output of both said input and twiddle-factor coefficient memories and an input of said multiplier for selectively coupling one of said outputs at a time to said multiplication means input.

Claim 30

The device of claim 21 further comprising scaling means connected in series with said accumulator for selectively applying block floating point, divide-by-two and divide-by-four scaling.

Claim 31

The device of claim 21 wherein said input and output memories and formatting means are configured to transfer input data and output data in a complex 32-bit 2's-complement format comprising 16 and 16 imaginary bits.

Claim 34

The method of claim 30 wherein the step of adjusting comprises the step of providing incremental-twiddle-factor coefficients to incrementally adjust said basic coefficients through multiplication to generate synergistic-twiddle-factor coefficients necessary to compute all mixed power-of-two and power-of-three FFTs up to a maximum T-point size, with T≦4096.

Claim 35

The method of claim 30 wherein N≦64.

Claim 36

The method of claim 30 further comprising the step of selectively connecting the multiplier and accumulator to an input buffer/ping-pong memory which receives the data so as to perform all integral sub-multiples of mixed power-of-two and power-of-three FFT computations in performing said N-point FFT computation.

Claim 37

The method of claim 33 further comprising configuring said multiplier and said accumulator to perform mixed radix-2, radix-3, radix-4, and radix-6 computations in executing said integral sub-multiples of mixed power-of-two and power-of-three FFT computations.

Claim 38

The method of claim 34 further comprising the steps of: performing said power-of-two computations in sequence on orthogonal complex-coordinate-system data; performing internal coordinate-system transformation to a (1, W 3 ) coordinate system; and performing said power-of-three and power-of-six computations in sequence on data which is in the (1, W 3 ) coordinate system.

Claim 39

The method of claim 35 comprising the step of converting the output from the (1, W 3 ) coordinate system back to said orthogonal coordinate system.

Claim 40

The method of claim 34 further comprising the steps of: performing said power-of-three and power-of-six computations in sequence on data which is in a (1, W 3 ) coordinate system; performing internal coordinate-system transformation of these results to the orthogonal coordinate system; and performing said power-of-two and power-of-four computations in sequence on the orthogonal complex-coordinate-system data.

Claim 41

The method of claim 37 further comprising the step of converting input data from an orthogonal coordinate system, to an internal (1, W 3 ) coordinate system prior to performing said FFT computations.

Claim 42

The method of claim 30 where the step of providing twiddle factor coefficients further comprises the steps of: providing basic twiddle-factor coefficient values required to compute mixed power-of-four and power-of-six FFT's; providing incremental twiddle-factor coefficients required to incrementally adjust said basic coefficients to generate those coefficient necessary to compute all mixed power-of-two, power-of-three, power-of-four, and power-of-six FFTs up to a predetermined maximum-size FFT point value T, where T≧N.

Claim 43

The apparatus of claim 37 wherein T is less than or equal to four thousand and ninety-six.