# US 4,393,457 A · Method and apparatus for sequencing addresses of a fast Fourier transform array > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 4,393,457 A - Document ID: US4393457A - Status: Granted - Kind: A - Application number: 06/247,676 - Filed: 1981-03-26 - Granted: 1983-07-12 - Earliest claimed: 1981-03-26 - Assignees: Advanced Micro Devices, Inc. - Inventors: Bernard J. New - Web page: https://patentgrep.com/patent/US4393457A ## CPC - G06F 17/142: {Fast Fourier transforms, e.g. using a Cooley-Tukey type algorithm} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract An apparatus and method for generating a specific sequence of addresses of values of an array stored in a digital memory. The addresses are generated by a first counter which generates a seed value and a second counter which generates a control value, the control value controlling a bit inserter and a programmable shifter to set, respectively, the bit place position of bit insertion and the amount of shift. The output of the bit inserter is the row position of related addresses for butterfly operation of a fast Fourier transform array. The output of the shifter is the address of coefficients associated with the complex rotation of the butterfly operation. The apparatus is an integrated circuit intended for use as a modular integrated circuit in connection with digital memory means and central processing means including a digital multiplying means. ## Claims ### Claim 1 For use in a digital signal processor, an intergrated circuit apparatus operative in response to signals from clock means, said clock means establishing a clock cycle, for generating signals representative of nonconsecutive sequence of output position values for data addresses according to a preselected pattern in order to read and write related data of an array in 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 inserting at least one preselected binary value signal in a preselected bit position of each seed value signal at each clock signal, said preselected bit place position determined by a control value signal, in order to generate in a nonconsecutive value sequence said output position value signals. ### Claim 2 (depends on 1) The apparatus according to claim 1 wherein said first counting means comprises a first sequential counter having means for presetting an initial column or step count value. ### Claim 3 (depends on 2) The apparatus according to claim 2 wherein said second counting means comprises a second sequential counter having means for presetting an initial row count value, said second counting means also being coupled to an input of said first counting means to provide a signal indicating carry for incrementing said first sequential counter. ### Claim 4 (depends on 1) The apparatus according to claim 1 wherein said inserting means comprises means for shifting a portion of said seed value signal at said preselected bit place position at least one bit place position toward a more significant position. ### Claim 5 (depends on 4) The apparatus according to claim 4 wherein said inserting means comprises means for providing said at least one preselected binary value signal between said shifted portion and unshifted portion of said seed value signal, said preselected bit place position being determined by said control value signal. ### Claim 6 (depends on 5) The apparatus according to claim 5 wherein said inserting means further includes means for converting said control value signal to a binary number signal, said binary number consisting of a sequence of consecutive zeros and a sequence of consecutive ones appended to said consecutive zeros' sequence at a transition point, the number of zeros and the transition point being determined by said control value signal, said transition point defining said preselected bit place position. ### Claim 7 (depends on 5) The apparatus according to claim 5 wherein said inserting means further includes means for selecting the number of bit place positions for shifting said seed value signal portion and the number of binary value signals to be inserted at said preselected bit place position. ### Claim 8 (depends on 4) The apparatus according to claim 4 wherein said inserting means further includes means for converting said control value signal to a binary number signal, said binary number signal consisting of a sequence of consecutive zeros and a sequence of consecutive ones appended to said consecutive zeros at a transition point, the number of zeros and said transition point being determined by said control value signal, said transition point defining said preselected bit place position, and wherein said inserting means further includes means for providing said at least one preselected binary value signal at said preselected bit place position of said seed value signal, said preselected bit place position being determined by said binary number, wherein said control value signal corresponds to a count generated by said first counting means initialized to a value defining a first column position of at least one address in said memory means of a fast Fourier transform array, and wherein a first one of said seed value signals corresponds to a count generated by second counting means initialized to a value defining a first column position of at least one address in said memory means for a fast Fourier transform. ### Claim 9 (depends on 4) The apparatus according to claim 4 further comprising means for shifting the entire portion of said seed value signal positions in a preselected number of bit place positions toward a more significant position, the number of bit place positions of said shift being determined by said control value signal. ### Claim 10 (depends on 9) The apparatus according to claim 9 wherein said entire portion shifting means further includes means for truncating selected most significant bit place positions of said shifted seed value signal. ### Claim 11 (depends on 10) The apparatus according to claim 10 further comprising means coupled to said inserting means and said entire portion shifting means for generating a plurality of said output position values signals. ### Claim 12 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. ### Claim 13 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).