Method and apparatus for addressing FFT processor

Claim 3

sequentially addressing and storing one half of the data points in one data stream of the dual data stream from said FFT arithmetic unit during the first half of the iteration period for each iteration to first even numbered memory locations of said memory means,

Claim 4

sequentially addressing and storing one half of the data points in one data stream of the dual data stream from said FFT arithmetic unit during the first half of the iteration period for each iteration to first even numbered memory locations of said memory means,

Claim 5

sequentially addressing and storing one half of the data points in the other data stream of the dual data stream from said FFT arithmetic unit during said first half of the iteration period for each iteration simultaneously with said one data stream to first odd numbered memory locations of said memory means,

Claim 6

sequentially addressing and storing one half of the data points in the other data stream of the dual data stream from said FFT arithmetic unit during said first half of the iteration period for each iteration simultaneously with said one data stream to first odd numbered memory locations of said memory means,

Claim 7

The method of indexing as defined by claim 1 wherein the steps of addressing and storing the mutually corresponding one half of the data points in both said one and said other data stream comprises loading the data points in said one and said other data stream in consecutive even and odd numbered memory locations respectively of a first memory, and wherein said steps of addressing and storing the other half of the mutually corresponding data points during the second half of the iteration period comprises loading the data points in said one and said other data stream in consecutive even numbered and odd numbered memory locations respectively of a second memory unit.

Claim 8

The method of indexing as defined by claim 1 wherein said step of storing said one half of the data samples in said one data stream during the first half of each iteration period comprises addressing and storing said data points in consecutive even numbered memory locations, beginning from the first, of a first memory; said step of addressing and storing said one half of the data points in the other data stream during said first half of each iteration period comprises addressing and storing said data points in consecutive odd numbered memory locations, beginning from the first, of a second memory; said step of addressing and storing said other half of the data points in said one data stream during the second half of each iteration period comprises addressing and storing the data points in consecutive even numbered memory locations, beginning from the first, of said second memory; said step of addressing and storing said other half of the data points in said other data stream during the second half of each iteration period comprises addressing and storing said data points in consecutive odd numbered memory locations, beginning from the first, of said first memory; wherein said step of sequentially reading out pairs of complex data points comprises reading out mutually corresponding pairs of complex data points simultaneously in respective data streams from said first and second memory unit, beginning from the first stored point and continuing to the last; and wherein said step of feeding said dual data stream back to said FFT arithmetic unit and said step of sequentially reading out pairs of data points additionally includes interchanging the mutually corresponding odd numbered data points from one data stream to the other prior to input to the FFT arithmetic unit during successive intermediate iterations and during the final output of the data points following the last iteration period.

Claim 9

sequentially addressing and storing the other half of the data poiNts in said one data stream of the dual data stream from said FFT arithmetic unit during the second half of the iteration period for each iteration to second even numbered memory locations of said memory means, and

Claim 10

sequentially addressing and storing the other half of the data poiNts in said one data stream of the dual data stream from said FFT arithmetic unit during the second half of the iteration period for each iteration to second even numbered memory locations of said memory means, and

Claim 11

An FFT processor having calculated complex data points stored and retrieved in an in-place operation, comprising in combination: an FFT arithmetic unit operable in accordance with an externally applied selected trigonometric coefficient to accept consecutivE pairs of complex data points simultaneously inputted thereto in a dual data stream and provide consecutive pairs of intermediate output data points (Fourier coefficients) simultaneously in a dual data stream in successive iterations according to a predetermined FFT algorithm; input means coupled to said FFT arithmetic unit for supplying consecutive pairs of complex data points as an initial input thereto; first digital memory means having even and odd numbered memory locations selectively coupled to the output of said FFT arithmetic unit during first alternate iteration periods and including selectively controlled address means for selectively storing simultaneous pairs of intermediate output data points consecutively calculated and being operable during the first half of each of said first alternate iteration periods to consecutively address and store the first half of the data points appearing in one data stream of said dual data stream in a first plurality of even numbered memory locations and to consecutively address and store the first half of the mutually corresponding data points appearing in the other data stream of said dual data stream in a first plurality of odd numbered memory locations, and first means operable at the end of the first half of the respective iteration period to switch the data flow into said memory means from said FFT arithmetic unit and consecutively address and store the second half of the data points appearing in said one data stream in a second plurality of even numbered memory locations and to consecutively address and store the second half of the data points appearing in said other data stream in a second plurality of odd numbered memory locations, said means being operable at the end of the respective iteration period to switch the data flow back to its original state at the beginning of the next iteration period; first selectively controlled read-out means coupling said first digital memory means to the input of said arithmetic unit during the immediately succeeding iteration period following each first alternate iteration period and consecutively supplying the pairs of complex data as stored to the FFT arithmetic unit as another input dual data stream; second digital memory means, having even and odd numbered memory locations selectively coupled to the output of said FFT arithmetic unit during second alternate iteration periods relative to said first alternate iteration periods and including selectively controlled address means for selectively storing simultaneous pairs of intermediate output data points consecutively calculated and being operable during the first half of each of said second alternate iteration periods to consecutively address and store the first half of the data points appearing in said one data stream of said dual data stream in a first plurality of even numbered memory locations and to consecutively address and store the first half of the data points appearing in the other data stream in a first plurality of odd numbered memory locations, and second means operable at the end of the first half of the respective iteration period to switch the data flow into said second memory means from said FFT arithmetic unit and consecutively address and store the second half of the data points appearing in said one data stream in a second plurality of even numbered memory locations and to consecutively address and store the second half of the data points appearing in said other data stream in a second plurality of consecutive odd numbered memory locations, said second means being operable at the end of the respective iteration period to switch the data flow back to its original state at the beginning of the next iteration period; second selectively controlled read-out means coupling said second digital memory means to the input of said FFT arithmetic unit during the immediately succeeding iteration period following each second alternate iteration period and consecutively supplying the pairs of cOmplex data as stored to the FFT unit as still another input dual data stream; dual data stream output means selectively coupled to one of said first and second read-out means for providing an output dual data stream as consecutive pairs of complex data as stored after the final iteration period, having a data sequence identical to the sequence of the original input data stream.

Claim 12

An FFT processor having calculated complex data points stored and retrieved in an in-place operation, comprising in combination: an FFT arithmetic unit operable in accordance with an externally applied selected trigonometric coefficient to accept consecutivE pairs of complex data points simultaneously inputted thereto in a dual data stream and provide consecutive pairs of intermediate output data points (Fourier coefficients) simultaneously in a dual data stream in successive iterations according to a predetermined FFT algorithm; input means coupled to said FFT arithmetic unit for supplying consecutive pairs of complex data points as an initial input thereto; first digital memory means having even and odd numbered memory locations selectively coupled to the output of said FFT arithmetic unit during first alternate iteration periods and including selectively controlled address means for selectively storing simultaneous pairs of intermediate output data points consecutively calculated and being operable during the first half of each of said first alternate iteration periods to consecutively address and store the first half of the data points appearing in one data stream of said dual data stream in a first plurality of even numbered memory locations and to consecutively address and store the first half of the mutually corresponding data points appearing in the other data stream of said dual data stream in a first plurality of odd numbered memory locations, and first means operable at the end of the first half of the respective iteration period to switch the data flow into said memory means from said FFT arithmetic unit and consecutively address and store the second half of the data points appearing in said one data stream in a second plurality of even numbered memory locations and to consecutively address and store the second half of the data points appearing in said other data stream in a second plurality of odd numbered memory locations, said means being operable at the end of the respective iteration period to switch the data flow back to its original state at the beginning of the next iteration period; first selectively controlled read-out means coupling said first digital memory means to the input of said arithmetic unit during the immediately succeeding iteration period following each first alternate iteration period and consecutively supplying the pairs of complex data as stored to the FFT arithmetic unit as another input dual data stream; second digital memory means, having even and odd numbered memory locations selectively coupled to the output of said FFT arithmetic unit during second alternate iteration periods relative to said first alternate iteration periods and including selectively controlled address means for selectively storing simultaneous pairs of intermediate output data points consecutively calculated and being operable during the first half of each of said second alternate iteration periods to consecutively address and store the first half of the data points appearing in said one data stream of said dual data stream in a first plurality of even numbered memory locations and to consecutively address and store the first half of the data points appearing in the other data stream in a first plurality of odd numbered memory locations, and second means operable at the end of the first half of the respective iteration period to switch the data flow into said second memory means from said FFT arithmetic unit and consecutively address and store the second half of the data points appearing in said one data stream in a second plurality of even numbered memory locations and to consecutively address and store the second half of the data points appearing in said other data stream in a second plurality of consecutive odd numbered memory locations, said second means being operable at the end of the respective iteration period to switch the data flow back to its original state at the beginning of the next iteration period; second selectively controlled read-out means coupling said second digital memory means to the input of said FFT arithmetic unit during the immediately succeeding iteration period following each second alternate iteration period and consecutively supplying the pairs of cOmplex data as stored to the FFT unit as still another input dual data stream; dual data stream output means selectively coupled to one of said first and second read-out means for providing an output dual data stream as consecutive pairs of complex data as stored after the final iteration period, having a data sequence identical to the sequence of the original input data stream.

Claim 13

The FFT processor as defined by claim 4 wherein said first and second digital memory means each comprises a pair of serially indexed memories.

Claim 14

The FFT processor as defined by claim 5 wherein the respective first plurality of even numbered and second plurality of odd numbered memory locations of said first and second memory means are located in one memory of each said pair of memories and the respective second plurality of even numbered and first plurality of odd numbered memory locations are respectively located in the other memory of each said pair of memories.

Claim 15

The FFT processor as defined by claim 5 wherein respective said first plurality of even numbered memory locations and the second plurality of odd numbered memory locations are located in a first memory of each of said pair of memories and wherein respective first plurality of odd numbered locations and the second plurality of even numbered memory locations are located in a second memory of each of said pair of memories, and wherein said read-out means includes means operable to interchange the mutually corresponding odd numbered data points from one data stream to the other of said dual data stream.

Claim 16

The FFT processor as defined by claim 7 wherein said FFT arithmetic unit additionally includes first and second data line means for transmitting respective data streams of said dual data stream to said pairs of memories, respective digital multiplexor means coupling said first and second data line means to said pairs of memories, and first and second digital multiplexor means having respective output data line means coupled to the input of said FFT arithmetic unit and input data line means coupled to the output of each of said pairs of memories.

Claim 17

The FFT processor as defined by claim 8 wherein said first and second memory means additionally includes a respective memory address generator coupled to pairs of memories, said generators each having means for indexing consecutive odd or even memory locations upon selective command during a write mode and indexing sequential memory locations upon selective command during a read mode.