# US 8,787,422 B2 · Dual fixed geometry fast fourier transform (FFT) > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,787,422 B2 - Document ID: US8787422B2 - Status: Granted - Kind: B2 - Application number: 13/323,917 - Filed: 2011-12-13 - Published: 2013-06-13 - Granted: 2014-07-22 - Earliest claimed: 2011-12-13 - Assignees: QUALCOMM Incorporated - Applicants: Marc M. Hoffman; Ajay Anant Ingle; Mao Zeng - Inventors: Marc M. Hoffman; Ajay Anant Ingle; Mao Zeng - Web page: https://patentgrep.com/patent/US8787422B2 ## CPC - G06F 17/142: {Fast Fourier transforms, e.g. using a Cooley-Tukey type algorithm} - G06F 9/3001: {Arithmetic instructions} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A method includes executing a first instruction at a processor to perform a first fast Fourier transform (FFT) operation on a set of inputs in a time domain to produce data in a frequency domain, where the set of inputs is in a first order and where the data in the frequency domain is in a second order. The method also includes performing an operation on the data in the frequency domain to produce data in the frequency domain, where the data in the frequency domain is in the second order. The method includes executing a second instruction at the processor to perform a second FFT operation on the data in the frequency domain to produce data in the time domain, where the data in the time domain is in the first order. ## Claims ### Claim 1 A method comprising: executing a first instruction via a processor to perform a first fast Fourier transform (FFT) operation on a set of inputs in a time domain to produce first data in a frequency domain, wherein the set of inputs is in a first order and wherein the first data in the frequency domain is in a second order, wherein performing the first FFT operation includes use of a common data path of the processor in conjunction with a first input/output network, and wherein the first input/output network comprises one of a shuffle input/output network and a deal input/output network; performing an operation on the first data in the frequency domain to produce second data in the frequency domain, wherein the second data in the frequency domain is in the second order; and executing a second instruction via the processor to perform a second FFT operation on the second data in the frequency domain to produce third data in the time domain, wherein the third data in the time domain is in the first order, wherein the first order is one of a normal input order and a bit-reversed input order and the second order is the other of the normal input order and the bit-reversed input order, wherein performing the second FFT operation includes use of the common data path of the processor in conjunction with a second input/output network, and wherein the second input/output network comprises the other of the shuffle input/output network and the deal input/output network. ### Claim 2 (depends on 1) The method of claim 1, wherein the operation is a filtering operation. ### Claim 3 (depends on 1) The method of claim 1, further comprising iteratively executing the first instruction N times to implement a 2N-point FFT operation, performing a filtering operation, and iteratively executing the second instruction N times to implement the 2N-point FFT operation, wherein N is an integer greater than zero. ### Claim 4 (depends on 3) The method of claim 3, wherein the 2N-point FFT operation comprises at least one of a decimation in time (DIT) operation and a decimation in frequency (DIF) operation. ### Claim 5 (depends on 1) The method of claim 1, wherein the first FFT operation and the second FFT operation each comprise a radix-2 FFT operation that accepts two input samples at a time. ### Claim 6 (depends on 5) The method of claim 5, wherein the radix-2 FFT operation comprises a dual fixed geometry operation, wherein each computation stage of a plurality of computation stages of the first FFT operation and the second FFT operation is identical to each other computation stage of the plurality of computation stages. ### Claim 7 (depends on 1) The method of claim 1, wherein the first instruction and the second instruction are each executable to implement a fast Hadamard transform. ### Claim 8 (depends on 1) The method of claim 1, wherein the common data path is configured to: receive data from first multiplexing circuitry and second multiplexing circuitry; and send data to the first input/output network and the second input/output network. ### Claim 9 An apparatus comprising: a memory storing a first instruction and a second instruction; and a processor coupled to the memory, the processor comprising a common data path, a first input/output network, and a second input/output network and configured to perform operations comprising: executing the first instruction to perform a first fast Fourier transform (FFT) operation on a set of inputs in a time domain to produce first data in a frequency domain, wherein the set of inputs is in a first order and wherein the first data in the frequency domain is in a second order, wherein performing the first FFT operation includes use of the common data path in conjunction with the first input/output network, and wherein the first input/output network comprises one of a shuffle input/output network and a deal input/output network; performing an operation on the first data in the frequency domain to produce second data in the frequency domain, wherein the second data in the frequency domain is in the second order; and executing the second instruction to perform a second FFT operation on the second data in the frequency domain to produce third data in the time domain, wherein the third data in the time domain is in the first order, wherein the first order is one of a normal input order and a bit-reversed input order and the second order is the other of the normal input order and the bit-reversed input order, wherein performing the second FFT operation includes use of the common data path in conjunction with the second input/output network, and wherein the second input/output network comprises the other of the shuffle input/output network and the deal input/output network. ### Claim 10 (depends on 9) The apparatus of claim 9, wherein the processor is a single instruction multiple data (SIMD) processor. ### Claim 11 (depends on 9) The apparatus of claim 9, wherein the shuffle input/output network comprises a first input register, a second input register, a third input register, and an output register, wherein a pair of inputs is loaded from the first input register and the second input register, wherein a twiddle factor is loaded from the third input register, and wherein an output of a butterfly computation based on the pair of inputs and the twiddle factor is stored in the output register. ### Claim 12 (depends on 9) The apparatus of claim 9, wherein the deal input/output network comprises a first input register, a second input register, a third input register, and an output register pair, wherein a pair of inputs is loaded from the first input register and the second input register, wherein a twiddle factor is loaded from the third input register, and wherein a pair of outputs of a butterfly computation based on the pair of inputs and the twiddle factor is stored in the output register pair. ### Claim 13 (depends on 9) The apparatus of claim 9, wherein the common data path is configured to: receive data from first multiplexing circuitry and second multiplexing circuitry; and send data to the first input/output network and the second input/output network. ### Claim 14 An apparatus comprising: means for storing a first instruction and a second instruction; and means for processing the first instruction and the second instruction, wherein the means for processing comprises: a common data path; a first input/output network; a second input/output network; means for executing the first instruction to perform a first fast Fourier transform (FFT) operation on a set of inputs in a time domain to produce first data in a frequency domain, wherein the set of inputs is in a first order and wherein the first data in the frequency domain is in a second order, wherein performing the first FFT operation includes use of the common data path in conjunction with the first input/output network, and wherein the first input/output network comprises one of a shuffle input/output network and a deal input/output network; means for performing an operation on the first data in the frequency domain to produce second data in the frequency domain, wherein the second data in the frequency domain is in the second order; and means for executing the second instruction to perform a second FFT operation on the second data in the frequency domain to produce third data in the time domain, wherein the third data in the time domain is in the first order, wherein the first order is one of a normal input order and a bit-reversed input order and the second order is the other of the normal input order and the bit-reversed input order, wherein performing the second FFT operation includes use of the common data path in conjunction with the second input/output network, and wherein the second input/output network comprises the other of the shuffle input/output network and the deal input/output network. ### Claim 15 (depends on 14) The apparatus of claim 14, wherein the common data path is configured to: receive data from first multiplexing circuitry and second multiplexing circuitry; and send data to the first input/output network and the second input/output network. ### Claim 16 A non-transitory computer-readable medium including program code that, when executed by a processor comprising a common data path, a first input/output network, and a second input/output network, causes the processor to perform operations comprising: executing a first instruction at a processor to perform a first fast Fourier transform (FFT) operation on a set of inputs in a time domain to produce first data in a frequency domain, wherein the set of inputs is in a first order, and wherein the first data in the frequency domain is in a second order, wherein performing the first FFT operation includes use of the common data path in conjunction with the first input/output network, and wherein the first input/output network comprises one of a shuffle input/output network and a deal input/output network; performing an operation on the first data in the frequency domain to produce second data in the frequency domain, wherein the second data in the frequency domain is in the second order; and executing a second instruction at the processor to perform a second FFT operation on the second data in the frequency domain to produce third data in the time domain, wherein the third data in the time domain is in the first order, wherein the first order is one of a normal input order and a bit-reversed input order and the second order is the other of the normal input order and the bit-reversed input order, wherein performing the second FFT operation includes use of the common data path in conjunction with the second input/output network, and wherein the second input/output network comprises the other of the shuffle input/output network and the deal input/output network. ### Claim 17 (depends on 16) The non-transitory computer-readable medium of claim 16, wherein the common data path is configured to: receive data from first multiplexing circuitry and second multiplexing circuitry; and send data to the first input/output network and the second input/output network.