Method and apparatus for sequencing addresses of a fast Fourier transform array

For use in a digital signal processor, an apparatus operative in response to signals from clock means, which establish a clock cycle, for generating signals representative of nonconsecutive output address values, said address values being generated according to a preselected pattern, in order to read and write related data of a multidimensional array in a digital memory means, said apparatus comprising:

• first counting means for sequentially generating consecutive signals representing control values;
• second counting means for sequentially generating consecutive signals representing binary seed values;
• means coupled to said first counting means and to said second counting means for modifying at least one place position signal of each seed value at each clock cycle in response to said control value signals in order to generate a first output position value signal;
• means coupled to said first counting means and to said second counting means for shifting all bits of each seed value by a number of place positions in response to the value of said control value signal at each clock cycle for generating a second output position value signal;
• whereby said first output position value signal and said second outut position value signal correspond to output address values of said memory means.

A method for generating a sequence of digital address signals for a fast Fourier transform array processor comprising:

• (a) generating a first binary value in a first digital counting means as a control value;
• (b) generating a second binary value in a second digital counting means as a seed value;
• (c) generating, in response to said control value, a first output position value signal for addressing a digital memory means, said first output position value signal being generated from said seed value by inserting at least one binary bit at a position in said seed value specified by said control value;
• (d) generating, in response to said control value, a second output position value signal for addressing a digital memory means, said second output position value signal being generated from said seed value by shifting said seed value by an amount specified by said control value;
• (e) incrementing in response to a clock signal said first binary value and repeating steps (c) and (d) until said first binary value achieves a first preselected value;
• (f) upon achieving said first preselected value, incrementing in response to a clock signal said second binary value and reinitializing said first counting means to said first binary value;
• and
• (g) repeating steps (a) through (f) until said second binary value achieves a second preselected value;
• (h) upon achieving said second preselected value, reinitializing said first counting means to said first binary value, reinitializing said second counting means to said second binary value for repeating steps (a) through (g).