# US 2002/0178194 A1 · Method for computing a fast fourier transform and associated circuit for addressing a data memory

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2002/0178194 A1
- Document ID: US20020178194A1
- Status: Published application
- Kind: A1
- Application number: 10/126,602
- Filed: 2002-06-05
- Published: 2002-11-28
- Earliest claimed: 1998-05-18
- Assignees: GlobespanVirata, Inc.
- Inventors: Yair Aizenberg; Yue-Peng Zheng
- Web page: https://patentgrep.com/patent/US20020178194A1

## 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

The present invention is generally directed to a novel method of computing a fast Fourier transform (FFT), and an associated circuit that controls the addressing of a data memory of the FFT processing circuit. The novel method operates by computing all complex butterfly operations in a given stage of computations, before computing any of the complex butterfly operations in a subsequent stage. Further, and within any given computation stage, the method performs by computing all other complex butterfly operations in a given stage of computations having a twiddle factor equal to the first twiddle value of that stage, before computing any other complex butterfly operations in the given stage of computations. Thereafter, subsequent computations are performed in the same way. More particularly, after computing a first set of complex butterfly operations (each having the same twiddle value) in a given computation stage, a first complex butterfly operation (having a different twiddle value) of a second set of complex butterfly operations, is computed in that stage. Thereafter, all remaining complex butterfly operations (having the same value) in that stage will be computed. This methodology will be repeated until all butterfly operations are calculated in each stage. An addressing circuit is also provided for addressing a data memory in a system for computing a FFT, the system having a data memory for storing data values and a coefficient memory for storing coefficient values.

## Claims

### Claim 1

In a system for computing a fast Fourier transform having a data memory for storing data values and a coefficient memory for storing coefficient values, a circuit for addressing the data memory comprising:
a multiplexer having an output for addressing the data memory, a first input of the multiplexer defining a data memory read address and a second input of the multiplexer defining a data memory write address; and
a write FIFO disposed in communication with the second input of the multiplexer, the write FIFO having an input that is connected to the first input of the multiplexer.

### Claim 2 (depends on 1)

The circuit as defined in claim 1, wherein the write FIFO is a four-deep FIFO, configured to store four addresses, before delivering the first stored address to the second input of the multiplexer.

### Claim 3 (depends on 1)

The circuit as defined in claim 1, further including a pointer register that is configured to contain and output an address value for the data memory.

### Claim 4 (depends on 3)

The circuit as defined in claim 3, further including a control circuit that is configured to load a value into the pointer register.

### Claim 5 (depends on 4)

The circuit as defined in claim 4, further including a second multiplexer having an output that is in communication with an input of the pointer register, the second multiplexer having a first input that is in communication with the control circuit.

### Claim 6 (depends on 5)

The circuit as defined in claim 5, further including a modulo adder having an output that is disposed in communication with a second input of the second multiplexer.

### Claim 7 (depends on 6)

The circuit as defined in claim 6, further a step size register, having an input in communication with the control circuit and configured to store and output a data memory address step size.

### Claim 8 (depends on 7)

The circuit as defined in claim 7, further including a carry adder disposed to add the output of the step size register and the output of the pointer register, the carry adder having an output disposed in communication with the input of the modulo adder.

### Claim 9 (depends on 8)

The circuit as defined in claim 8, further including an exclusive OR circuit having two sets of inputs, the first set of inputs disposed to receive the output of the pointer register and the second set of inputs disposed to receive the output of the step size register.

### Claim 10 (depends on 9)

The circuit as defined in claim 9, wherein the exclusive OR circuit further has a set of outputs electrically connected to the input of the write FIFO and the first input of the multiplexer.

### Claim 11 (depends on 4)

The circuit as defined in claim 4, wherein the control circuit includes a processor for executing instructions.

### Claim 12

A method for computing a fast Fourier transform of a series of data values comprising the steps of:
(a) computing all complex butterfly operations in a first stage of computation;
(b) computing a first complex butterfly operation in a next stage of computation, wherein the first complex butterfly operation includes a twiddle factor having a first value;
(c) computing all remaining complex butterfly operations in the said next stage of computation having twiddle factors equal to the first value, skipping intervening butterfly computations having values different than the first value;
(d) computing a previously uncomputed next complex butterfly operation in the said next state of computation, wherein the said next complex butterfly operation includes a twiddle factor having a second value, said second value being different than the first value; and
(e) computing all remaining complex butterfly operations in the said next stage of computation having twiddle factors equal to the second value, skipping intervening butterfly computations having values different than the second value.

### Claim 13 (depends on 12)

The method as defined in claim 12, further including the step of: (f) repeating steps (d) and (e) until all complex butterfly operations in the said next stage of computations have been computed.

### Claim 14 (depends on 13)

The method as defined in claim 13, further including the step of: (g) repeating steps (b) through (f) until all stages of computations have been computed.

### Claim 15 (depends on 12)

The method as defined in claim 12, wherein the steps of computing complex butterfly operations include the step reading two data values from two memory locations to use in the computation of the complex butterfly operation, and writing computed values back to the two memory locations, thereby overwriting the data values previously stored in those locations.

### Claim 16 (depends on 12)

The method as defined in claim 12, wherein step (b) further includes the step of reading the twiddle value having a first value from a first address within a coefficient memory.

### Claim 17 (depends on 12)

The method as defined in claim 12, wherein step (d) further includes the step of reading the twiddle value having a second value from a second address within the coefficient memory.

### Claim 18

A method for computing a fast Fourier transform of a series of data values comprising the steps of:
computing all complex butterfly operations in a given stage of computations, before computing any of the complex butterfly operations in a subsequent stage; and
computing all other complex butterfly operations in the given stage of computations having a twiddle factor equal to the first value before computing any other complex butterfly operations in the given stage of computations, after computing a first complex butterfly operation in a given stage of computations, wherein the first complex butterfly operation utilizes a twiddle factor having a first value.

### Claim 19

In a system for computing a fast Fourier transform having a data memory for storing data values and a coefficient memory for storing coefficient values, a circuit for addressing the data memory comprising:
a read address generating circuit configured to point to addresses within the data memory for reading data values therefrom, the read address generating circuit having an output in communication with the data memory;
a write address storage circuit configured to receive and store values from the output of the read address generating circuit, the write address storage circuit configured to point to address within the data memory for writing data values thereto; and
a selector circuit having an output in direct communication with the data memory, the output of the selector circuit configured to select the address of the data memory for reading data therefrom and writing data thereto, the selector circuit having a first input in communication with the output of the read address generating circuit, the selector circuit further having a second input in communication with the output of the write address storage circuit.

### Claim 20 (depends on 19)

The circuit as defined in claim 19, wherein the selector circuit includes a multiplexer.
