# US 2010/0169402 A1 · Fast fourier transform processor

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

- Number: US 2010/0169402 A1
- Document ID: US20100169402A1
- Status: Published application
- Kind: A1
- Application number: 12/400,794
- Filed: 2009-03-10
- Published: 2010-07-01
- Earliest claimed: 2008-12-31
- Assignees: Industrial Technology Research Institute
- Inventors: Hung-Lin Chen; Yu-Min Lin; Dar-Zu Hsu; Yuan Chen; Chen-Yi Lee
- Web page: https://patentgrep.com/patent/US20100169402A1

## 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 FFT processor is disclosed, which includes a first multi-pipelined MDC unit, a second multi-pipelined MDC unit and a switching network. The first multi-pipelined MDC unit and the second multi-pipelined MDC unit respectively employ a plurality of MDC circuits to change the positions of the delayers thereof in parallel way. By changing the operation time sequence of the signals in the first multi-pipelined MDC unit and the second multi-pipelined MDC unit, the first multi-pipelined MDC unit is able to directly send the operation results to the second multi-pipelined MDC unit through the switching network.

## Claims

### Claim 1

A Fast Fourier Transform (FFT) processor, comprising:
a first multi-pipelined multipath delay commutator (MDC) unit, for performing M radix-2N first butterfly operations in parallel way so as to output a plurality of first operation results, wherein M and N are integers greater than 1;
a switching network, coupled to the first multi-pipelined MDC unit for changing the relative positions of the first operation results; and
a second multi-pipelined MDC unit, coupled to the switching network for using the first operation results after changing the relative positions thereof to perform M radix-2N second butterfly operations in parallel way so as to output a plurality of second operation results.

### Claim 2 (depends on 1)

The FFT processor as claimed in claim 1, wherein the first multi-pipelined MDC unit comprises:
M multipath delay commutators, for respectively performing a radix-2N first butterfly operation, wherein the outputs of the multipath delay commutators serve as the first operation results.

### Claim 3 (depends on 2)

The FFT processor as claimed in claim 2, wherein one of the multipath delay commutators comprises:
a first butterfly operator, having a first input terminal, a second input terminal, a first output terminal and a second output terminal for performing a radix-2 butterfly operation according to the data of the first input terminal and the second input terminal thereof and outputting the operation results from the first output terminal and the second output terminal thereof, wherein the first input terminal and the second input terminal of the first butterfly operator respectively serve as the first input terminal and the second input terminal of the multipath delay commutator;
a first delayer, having an input terminal and an output terminal, wherein the input terminal is coupled to the second output terminal of the first butterfly operator to delay the received data by two time slots, following by outputting the delayed data from the output terminal thereof;
a first switch, having a first terminal, a second terminal, a third terminal and a fourth terminal for respectively electrically connecting the first terminal and the second terminal thereof to the third terminal and the fourth terminal thereof or to the fourth terminal and the third terminal thereof, wherein the first terminal and the second terminal of the first switch are respectively coupled to the first output terminal of the first butterfly operator and the output terminal of the first delayer;
a second delayer, having an input terminal and an output terminal, wherein the input terminal is coupled to the third terminal of the first switch to delay the received data by two time slots, following by outputting the delayed data from the output terminal thereof;
a second butterfly operator, having a first input terminal, a second input terminal, a first output terminal and a second output terminal for performing a radix-2 butterfly operation according to the data of the first input terminal and the second input terminal thereof and outputting the operation results from the first output terminal and the second output terminal thereof, wherein the first input terminal of the second butterfly operator is coupled to the output terminal of the second delayer and the second input terminal of the second butterfly operator is coupled to the fourth terminal of the first switch;
a third delayer, having an input terminal and an output terminal, wherein the input terminal is coupled to the second output terminal of the second butterfly operator to delay the received data by a time slot, following by outputting the delayed data from the output terminal thereof;
a second switch, having a first terminal, a second terminal, a third terminal and a fourth terminal for respectively electrically connecting the first terminal and the second terminal thereof to the third terminal and the fourth terminal thereof or to the fourth terminal and the third terminal thereof, wherein the first terminal and the second terminal of the second switch are respectively coupled to the first output terminal of the second butterfly operator and the output terminal of the third delayer;
a fourth delayer, having an input terminal and an output terminal, wherein the input terminal is coupled to the third terminal of the second switch to delay the received data by a time slot, following by outputting the delayed data from the output terminal thereof; and
a third butterfly operator, having a first input terminal, a second input terminal, a first output terminal and a second output terminal for performing a radix-2 butterfly operation according to the data of the first input terminal and the second input terminal thereof and outputting the operation results from the first output terminal and the second output terminal thereof, wherein the first input terminal of the third butterfly operator is coupled to the output terminal of the fourth delayer, the second input terminal of the third butterfly operator is coupled to the fourth terminal of the second switch and the first output terminal and the second output terminal of the third butterfly operator respectively serve as the first output terminal and the second output terminal of the multipath delay commutator.

### Claim 4 (depends on 2)

The FFT processor as claimed in claim 2, wherein one of the multipath delay commutators comprises:
a first butterfly operator, having a first input terminal, a second input terminal, a first output terminal and a second output terminal for performing a radix-2 butterfly operation according to the data of the first input terminal and the second input terminal thereof and outputting the operation results from the first output terminal and the second output terminal thereof, wherein the first input terminal and the second input terminal of the first butterfly operator respectively serve as the first input terminal and the second input terminal of the multipath delay commutator;
a first delayer, having an input terminal and an output terminal, wherein the input terminal is coupled to the second output terminal of the first butterfly operator to delay the received data by two time slots, following by outputting the delayed data from the output terminal thereof;
a first switch, having a first terminal, a second terminal, a third terminal and a fourth terminal for respectively electrically connecting the first terminal and the second terminal thereof to the third terminal and the fourth terminal thereof or to the fourth terminal and the third terminal thereof, wherein the first terminal and the second terminal of the first switch are respectively coupled to the first output terminal of the first butterfly operator and the output terminal of the first delayer;
a second delayer, having an input terminal and an output terminal, wherein the input terminal is coupled to the third terminal of the first switch to delay the received data by two time slots, following by outputting the delayed data from the output terminal thereof;
a second butterfly operator, having a first input terminal, a second input terminal, a first output terminal and a second output terminal for performing a radix-2 butterfly operation according to the data of the first input terminal and the second input terminal thereof and outputting the operation results from the first output terminal and the second output terminal thereof, wherein the first input terminal of the second butterfly operator is coupled to the output terminal of the second delayer and the second input terminal of the second butterfly operator is coupled to the fourth terminal of the first switch;
a third delayer, having an input terminal and an output terminal, wherein the input terminal is coupled to the first output terminal of the second butterfly operator to delay the received data by a time slot, following by outputting the delayed data from the output terminal thereof;
a second switch, having a first terminal, a second terminal, a third terminal and a fourth terminal for respectively electrically connecting the first terminal and the second terminal thereof to the third terminal and the fourth terminal thereof or to the fourth terminal and the third terminal thereof, wherein the first terminal and the second terminal of the second switch are respectively coupled to the output terminal of the third delayer and the second output terminal of the second butterfly operator;
a fourth delayer, having an input terminal and an output terminal, wherein the input terminal is coupled to the fourth terminal of the second switch to delay the received data by a time slot, following by outputting the delayed data from the output terminal thereof; and
a third butterfly operator, having a first input terminal, a second input terminal, a first output terminal and a second output terminal for performing a radix-2 butterfly operation according to the data of the first input terminal and the second input terminal thereof and outputting the operation results from the first output terminal and the second output terminal thereof, wherein the first input terminal of the third butterfly operator is coupled to the third terminal of the second switch, the second input terminal of the third butterfly operator is coupled to the output terminal of the fourth delayer and the first output terminal and the second output terminal of the third butterfly operator respectively serve as the second output terminal and the first output terminal of the multipath delay commutator.

### Claim 5 (depends on 2)

The FFT processor as claimed in claim 2, wherein one of the multipath delay commutators comprises:
a first butterfly operator, having a first input terminal, a second input terminal, a first output terminal and a second output terminal for performing a radix-2 butterfly operation according to the data of the first input terminal and the second input terminal thereof and outputting the operation results from the first output terminal and the second output terminal thereof, wherein the first input terminal and the second input terminal of the first butterfly operator respectively serve as the first input terminal and the second input terminal of the multipath delay commutator;
a first delayer, having an input terminal and an output terminal, wherein the input terminal is coupled to the first output terminal of the first butterfly operator to delay the received data by two time slots, following by outputting the delayed data from the output terminal thereof;
a first switch, having a first terminal, a second terminal, a third terminal and a fourth terminal for respectively electrically connecting the first terminal and the second terminal thereof to the third terminal and the fourth terminal thereof or to the fourth terminal and the third terminal thereof, wherein the first terminal and the second terminal of the first switch are respectively coupled to the output terminal of the first delayer and the second output terminal of the first butterfly operator;
a second delayer, having an input terminal and an output terminal, wherein the input terminal is coupled to the fourth terminal of the first switch to delay the received data by two time slots, following by outputting the delayed data from the output terminal thereof;
a second butterfly operator, having a first input terminal, a second input terminal, a first output terminal and a second output terminal for performing a radix-2 butterfly operation according to the data of the first input terminal and the second input terminal thereof and outputting the operation results from the first output terminal and the second output terminal thereof, wherein the first input terminal of the second butterfly operator is coupled to the third terminal of the first switch and the second input terminal of the second butterfly operator is coupled to the output terminal of the second delayer;
a third delayer, having an input terminal and an output terminal, wherein the input terminal is coupled to the first output terminal of the second butterfly operator to delay the received data by a time slot, following by outputting the delayed data from the output terminal thereof;
a second switch, having a first terminal, a second terminal, a third terminal and a fourth terminal for respectively electrically connecting the first terminal and the second terminal thereof to the third terminal and the fourth terminal thereof or to the fourth terminal and the third terminal thereof, wherein the first terminal and the second terminal of the second switch are respectively coupled to the output terminal of the third delayer and the second output terminal of the second butterfly operator;
a fourth delayer, having an input terminal and an output terminal, wherein the input terminal is coupled to the fourth terminal of the second switch to delay the received data by a time slot, following by outputting the delayed data from the output terminal thereof; and
a third butterfly operator, having a first input terminal, a second input terminal, a first output terminal and a second output terminal for performing a radix-2 butterfly operation according to the data of the first input terminal and the second input terminal thereof and outputting the operation results from the first output terminal and the second output terminal thereof, wherein the first input terminal of the third butterfly operator is coupled to the third terminal of the second switch, the second input terminal of the third butterfly operator is coupled to the output terminal of the fourth delayer and the first output terminal and the second output terminal of the third butterfly operator respectively serve as the second output terminal and the first output terminal of the multipath delay commutator.

### Claim 6 (depends on 2)

The FFT processor as claimed in claim 2, wherein one of the multipath delay commutators comprises:
a first butterfly operator, having a first input terminal, a second input terminal, a first output terminal and a second output terminal for performing a radix-2 butterfly operation according to the data of the first input terminal and the second input terminal thereof and outputting the operation results from the first output terminal and the second output terminal thereof, wherein the first input terminal and the second input terminal of the first butterfly operator respectively serve as the first input terminal and the second input terminal of the multipath delay commutator;
a first delayer, having an input terminal and an output terminal, wherein the input terminal is coupled to the first output terminal of the first butterfly operator to delay the received data by two time slots, following by outputting the delayed data from the output terminal thereof;
a first switch, having a first terminal, a second terminal, a third terminal and a fourth terminal for respectively electrically connecting the first terminal and the second terminal thereof to the third terminal and the fourth terminal thereof or to the fourth terminal and the third terminal thereof, wherein the first terminal and the second terminal of the first switch are respectively coupled to the output terminal of the first delayer and the second output terminal of the first butterfly operator;
a second delayer, having an input terminal and an output terminal, wherein the input terminal is coupled to the fourth terminal of the first switch to delay the received data by two time slots, following by outputting the delayed data from the output terminal thereof;
a second butterfly operator, having a first input terminal, a second input terminal, a first output terminal and a second output terminal for performing a radix-2 butterfly operation according to the data of the first input terminal and the second input terminal thereof and outputting the operation results from the first output terminal and the second output terminal thereof, wherein the first input terminal of the second butterfly operator is coupled to the third terminal of the first switch and the second input terminal of the second butterfly operator is coupled to the output terminal of the second delayer;
a third delayer, having an input terminal and an output terminal, wherein the input terminal is coupled to the second output terminal of the second butterfly operator to delay the received data by a time slot, following by outputting the delayed data from the output terminal thereof;
a second switch, having a first terminal, a second terminal, a third terminal and a fourth terminal for respectively electrically connecting the first terminal and the second terminal thereof to the third terminal and the fourth terminal thereof or to the fourth terminal and the third terminal thereof, wherein the first terminal and the second terminal of the second switch are respectively coupled to the first output terminal of the second butterfly operator and the output terminal of the third delayer;
a fourth delayer, having an input terminal and an output terminal, wherein the input terminal is coupled to the third terminal of the second switch to delay the received data by a time slot, following by outputting the delayed data from the output terminal thereof; and
a third butterfly operator, having a first input terminal, a second input terminal, a first output terminal and a second output terminal for performing a radix-2 butterfly operation according to the data of the first input terminal and the second input terminal thereof and outputting the operation results from the first output terminal and the second output terminal thereof, wherein the first input terminal of the third butterfly operator is coupled to the output terminal of the fourth delayer, the second input terminal of the third butterfly operator is coupled to the fourth terminal of the second switch and the first output terminal and the second output terminal of the third butterfly operator respectively serve as the first output terminal and the second output terminal of the multipath delay commutator.

### Claim 7 (depends on 1)

The FFT processor as claimed in claim 1, wherein the second multi-pipelined MDC unit comprises:
M multipath delay commutators, for respectively performing a radix-2N first butterfly operation, wherein the outputs of the multipath delay commutators serve as the second operation results.

### Claim 8 (depends on 7)

The FFT processor as claimed in claim 7, wherein one of the multipath delay commutators comprises:
a first butterfly operator, having a first input terminal, a second input terminal, a first output terminal and a second output terminal for performing a radix-2 butterfly operation according to the data of the first input terminal and the second input terminal thereof and outputting the operation results from the first output terminal and the second output terminal thereof, wherein the first input terminal and the second input terminal of the first butterfly operator respectively serve as the first input terminal and the second input terminal of the multipath delay commutator;
a first delayer, having an input terminal and an output terminal, wherein the input terminal is coupled to the second output terminal of the first butterfly operator to delay the received data by two time slots, following by outputting the delayed data from the output terminal thereof;
a first switch, having a first terminal, a second terminal, a third terminal and a fourth terminal for respectively electrically connecting the first terminal and the second terminal thereof to the third terminal and the fourth terminal thereof or to the fourth terminal and the third terminal thereof, wherein the first terminal and the second terminal of the first switch are respectively coupled to the first output terminal of the first butterfly operator and the output terminal of the first delayer;
a second delayer, having an input terminal and an output terminal, wherein the input terminal is coupled to the third terminal of the first switch to delay the received data by two time slots, following by outputting the delayed data from the output terminal thereof;
a second butterfly operator, having a first input terminal, a second input terminal, a first output terminal and a second output terminal for performing a radix-2 butterfly operation according to the data of the first input terminal and the second input terminal thereof and outputting the operation results from the first output terminal and the second output terminal thereof, wherein the first input terminal of the second butterfly operator is coupled to the output terminal of the second delayer and the second input terminal of the second butterfly operator is coupled to the fourth terminal of the first switch;
a third delayer, having an input terminal and an output terminal, wherein the input terminal is coupled to the second output terminal of the second butterfly operator to delay the received data by a time slot, following by outputting the delayed data from the output terminal thereof;
a second switch, having a first terminal, a second terminal, a third terminal and a fourth terminal for respectively electrically connecting the first terminal and the second terminal thereof to the third terminal and the fourth terminal thereof or to the fourth terminal and the third terminal thereof, wherein the first terminal and the second terminal of the second switch are respectively coupled to the first output terminal of the second butterfly operator and the output terminal of the third delayer;
a fourth delayer, having an input terminal and an output terminal, wherein the input terminal is coupled to the third terminal of the second switch to delay the received data by a time slot, following by outputting the delayed data from the output terminal thereof; and
a third butterfly operator, having a first input terminal, a second input terminal, a first output terminal and a second output terminal for performing a radix-2 butterfly operation according to the data of the first input terminal and the second input terminal thereof and outputting the operation results from the first output terminal and the second output terminal thereof, wherein the first input terminal of the third butterfly operator is coupled to the output terminal of the fourth delayer, the second input terminal of the third butterfly operator is coupled to the fourth terminal of the second switch and the first output terminal and the second output terminal of the third butterfly operator respectively serve as the second output terminal and the first output terminal of the multipath delay commutator.

### Claim 9 (depends on 7)

The FFT processor as claimed in claim 7, wherein one of the multipath delay commutators comprises:
a first butterfly operator, having a first input terminal, a second input terminal, a first output terminal and a second output terminal for performing a radix-2 butterfly operation according to the data of the first input terminal and the second input terminal thereof and outputting the operation results from the first output terminal and the second output terminal thereof, wherein the first input terminal and the second input terminal of the first butterfly operator respectively serve as the first input terminal and the second input terminal of the multipath delay commutator;
a first delayer, having an input terminal and an output terminal, wherein the input terminal is coupled to the second output terminal of the first butterfly operator to delay the received data by two time slots, following by outputting the delayed data from the output terminal thereof;
a first switch, having a first terminal, a second terminal, a third terminal and a fourth terminal for respectively electrically connecting the first terminal and the second terminal thereof to the third terminal and the fourth terminal thereof or to the fourth terminal and the third terminal thereof, wherein the first terminal and the second terminal of the first switch are respectively coupled to the first output terminal of the first butterfly operator and the output terminal of the first delayer;
a second delayer, having an input terminal and an output terminal, wherein the input terminal is coupled to the third terminal of the first switch to delay the received data by two time slots, following by outputting the delayed data from the output terminal thereof;
a second butterfly operator, having a first input terminal, a second input terminal, a first output terminal and a second output terminal for performing a radix-2 butterfly operation according to the data of the first input terminal and the second input terminal thereof and outputting the operation results from the first output terminal and the second output terminal thereof, wherein the first input terminal of the second butterfly operator is coupled to the output terminal of the second delayer and the second input terminal of the second butterfly operator is coupled to the fourth terminal of the first switch;
a third delayer, having an input terminal and an output terminal, wherein the input terminal is coupled to the first output terminal of the second butterfly operator to delay the received data by a time slot, following by outputting the delayed data from the output terminal thereof;
a second switch, having a first terminal, a second terminal, a third terminal and a fourth terminal for respectively electrically connecting the first terminal and the second terminal thereof to the third terminal and the fourth terminal thereof or to the fourth terminal and the third terminal thereof, wherein the first terminal and the second terminal of the second switch are respectively coupled to the output terminal of the third delayer and the second output terminal of the second butterfly operator;
a fourth delayer, having an input terminal and an output terminal, wherein the input terminal is coupled to the fourth terminal of the second switch to delay the received data by a time slot, following by outputting the delayed data from the output terminal thereof; and
a third butterfly operator, having a first input terminal, a second input terminal, a first output terminal and a second output terminal for performing a radix-2 butterfly operation according to the data of the first input terminal and the second input terminal thereof and outputting the operation results from the first output terminal and the second output terminal thereof, wherein the first input terminal of the third butterfly operator is coupled to the third terminal of the second switch, the second input terminal of the third butterfly operator is coupled to the output terminal of the fourth delayer and the first output terminal and the second output terminal of the third butterfly operator respectively serve as the first output terminal and the second output terminal of the multipath delay commutator.

### Claim 10 (depends on 1)

The FFT processor as claimed in claim 1, wherein the first operation results are O1(1)-O1(16), the input terminals of the second multi-pipelined MDC unit are I2(1)-I2(2), then, the switching network sends the first operation results O1(i) at a first time slot to the input terminals I2(2i−1−15div(i/9)) of the second multi-pipelined MDC unit, wherein I is an integer and 0<i<17.

### Claim 11 (depends on 10)

The FFT processor as claimed in claim 10, wherein the switching network respectively sends the first operation results O1(1)-O1(16) at a second time slot to the input terminals I2(5), I2(7), I2(1), I2(3), I2(13), I2(15), I2(9), I2(11), I2(6), I2(8), I2(2), I2(4), I2(14), I2(16), I2(10) and I2(12) of the second multi-pipelined MDC unit.

### Claim 12 (depends on 11)

The FFT processor as claimed in claim 11, wherein the switching network respectively sends the first operation results I1(1)-O1(16) at a third time slot to the input terminals I2(9), I2(11), I2(13), I2(15), I2(1), I2(3), I2(5), I2(7), I2(10), I2(12), I2(14), I2(16), I2(2), I2(4), I2(6) and I2(8) of the second multi-pipelined MDC unit.

### Claim 13 (depends on 12)

The FFT processor as claimed in claim 12, wherein the switching network respectively sends the first operation results O1(1)-O1(16) at a fourth time slot to the input terminals I2(13), I2(15), I2(9), I2(11), I2(5), I2(7), I2(1), I2(3), I2(14), I2(16), I2(10), I2(12), I2(6), I2(8), I2(2) and I2(4) of the second multi-pipelined MDC unit.

### Claim 14 (depends on 1)

The FFT processor as claimed in claim 1, further comprising a memory for providing the first multi-pipelined MDC unit with the required data and providing a memory space for the second multi-pipelined MDC unit to write the operation results into the memory space.