Architecture for two dimensional fast fourier transform

• US 4,601,006 A
• Filed: 10/06/1983
• Issued: 07/15/1986
• Est. Priority Date: 10/06/1983
• Status: Expired due to Fees

• Current Assignee: University of South Carolina
• Original Assignee: Research Corporation
• Inventors: Liu, Wentai
• Primary Examiner(s): Malzahn, David H.
• Application Number:
  US06/539,540
• Time in Patent Office: 1,013 Days
• Field of Search: 364/726
• US Class Current: 708/401
• CPC Class Codes: G06F 17/147 Discrete orthonormal transforms, e.g. discrete cosine transform, discrete sine transform, and variations therefrom, e.g. modified discrete cosine transform, integer transforms approximating the discrete cosine transform G06F17/145 takes precedence

Abstract

A novel architecture and circuitry for implementing a new fast fourier transform algorithm which does not require a very large core memory and also does not require a transpose of a matrix. A pipelined and parallel architecture implements the two dimensional fast fourier transform on an array of input data values, with the transformation being performed by a plurality of serially arranged pass stages. Each pass stage includes an input shuffle arrangement for receiving an ordered set of input data from a row or column of a two dimensional matrix of such input data values, and for performing a shuffle operation thereon to produce a shuffled order of the input data. Each pass stage further includes a plurality of identical switching circuits coupled in parallel to receive the shuffled order of input data. Each switching circuit includes an arithmetic logic unit which receives four input data values and performs four data transformations thereon to produce four output data values, with each of the four data transformations including a first operation of selective addition or subtraction of the four input data values, followed by a second operation of selective multiplication by an exponential multiplier.

Claims

1. A pipelined and parallel system for implementing a two dimensional fast fourier transform on an array of input data values, with the transformation being performed by a plurality of serially arranged pass stages, with each pass stage comprising,

a. shuffle means for receiving an ordered set of input data for that pass stage and for performing a shuffle operation thereon to produce a shuffled order of input data, with the first pass stage receiving an ordered set of input data from a row or column of a two dimensional matrix of such input data values, and pass stages subsequent to the first pass stage receiving an ordered set of input data from the preceding pass stage;

and

b. a plurality of identical switching circuit means coupled in parallel to receive the shuffled order of input data, each switching circuit means including an arithmetic logic unit with four inputs for receiving four input data values and including means for performing four data transformations of the four input data values to produce four output data values, said means for performing each of the four data transformations including a first means for performing a first operation of selective addition or subtraction of the four input data values, followed by a second means for performing a second operation of selective multiplication by an exponential multiplier.

2. A pipelined and parallel system for implementing a two dimensional fast fourier transform as claimed in claim 1, each arithmetic logic unit receiving four input data values a, b, c and d, and said first and second means combining the input data values by executing the following four data operations thereon to produce four output data values A, B, C and D,

3. A pipelined and parallel system for implementing a two dimensional fast fourier transform as claimed in claim 2, wherein, for a two dimensional array of N by N data values, the first pass stage performs window data operations on sets of data values arranged in window sizes N/2 by N/2, and the second pass stage performs window data operations on sets of data values arranged in window sizes N/2² by N/2², and the i^th pass stage performs window data operations on sets of data values arranged in window sizes N/2ⁱ by N/2ⁱ, and the last pass stage performing window data operations on sets of data values arranged in a 1 by 1 data window size, wherein the window data sizes in each pass stage are decreased in half in that pass stage, with the shuffle means in each pass stage decreasing the window data size in half in a first direction, and the switching circuit means in each pass stage decreasing the window data size in half in a second direction.

4. A pipelined and parallel system for implementing a two dimensional fast fourier transform as claimed in claim 3, wherein each switching circuit means includes two input data lines, a set of two synchronous delay lines, and a set of two input synchronous switches for switching input data on the two input data lines into either the arithmetic logic unit of that switching circuit means or into the set of two synchronous delay lines in that switching circuit means, two output data lines, and a set of two output synchronous switches, coupled to the arithmetic logic unit of that switching circuit means and further coupled to the set of two synchronous delay lines, for switching input data from the delay lines and from the arithmetic logic unit either to the two data output lines or as data inputs to the arithmetic logic unit.

5. A pipelined and parallel system for implementing a two dimensional fast fourier transform as claimed in claim 4, wherein for each switching circuit means in each i^th pass, the two synchronous delay lines therein have delays of N/2ⁱ, and further including means for simultaneously and synchronously switching the two input synchronous switches and two output synchronous switches after each delay of N/2ⁱ.

6. A pipelined and parallel system for implementing a two dimensional fast fourier transform as claimed in claim 1, wherein, for a two dimensional array of N by N data values, the first pass stage performs window data operations on sets of data values arranged in window sizes N/2 by N/2, and the second pass stage performs window data operations on sets of data values arranged in window sizes N/2² by N/2², and the i^th pass stage performs window data operations on sets of data values arranged in window sizes N/2ⁱ by N/2ⁱ, and the last pass stage performing window data operations on sets of data values arranged in a 1 by 1 data window size, wherein the window data sizes in each pass stage are decreased in half in that pass stage, with the shuffle means in each pass stage decreasing the window data size in half in a first direction, and the switching circuit means in each pass stage decreasing the window data size in half in a second direction.

7. A pipelined and parallel system for implementing a two dimensional fast fourier transform as claimed in claim 1, wherein each switching circuit means includes two input data lines, a set of two synchronous delay lines, and a set of two input synchronous switches for switching input data on the two input data lines into either the arithmetic logic unit of that switching circuit means or into the set of two synchronous delay lines in that switching circuit means, two output data lines, and a set of two output synchronous switches, coupled to the arithmetic logic unit of that switching circuit means and further coupled to the set of two synchronous delay lines, for switching input data from the delay lines and from the arithmetic logic unit either to the two data output lines or as data inputs to the arithmetic logic unit.

8. A pipelined and parallel system for implementing a two dimensional fast fourier transform as claimed in claim 7, wherein for each switching circuit means in each i^th pass, the two synchronous delay lines therein have delays of N/2ⁱ, and further including means for simultaneously and synchronously switching the two input synchronous switches and two output synchronous switches after each delay of N/2ⁱ.

9. A pipelined and parallel system for implementing a two dimensional fast fourier transform as claimed in claim 1, wherein said plurality of identical switching circuit means are synchronous switching circuits controlled by a common clock.

10. A circuit for implementing a two dimensional fast fourier transform on an array of N by N input data values, comprising:

a. a plurality of serially arranged pass stage circuits for performing the transformation, with each successive pass stage circuit performing window data operations on successively smaller data windows, in which the first pass stage circuit includes means for performing window data operations on sets of data values arranged in window sizes N/2 by N/2, and the second pass stage circuit includes means for performing window data operations on sets of data values arranged in window sizes N/2² by N/2², and the i^th pass stage circuit includes means for performing window data operations on sets of data values arranged in window sizes N/2ⁱ by N/2ⁱ, and the last pass stage circuit includes means for performing window data operations on data values arranged in a 1 by 1 data window; and

b. said means for performing in each pass stage circuit including a plurality of parallel arranged arithmetic logic units for performing data operations in parallel, each arithmetic logic unit having four input data lines for receiving four input data values for that pass stage circuit, with the first pass stage receiving an ordered set of input data from a row or column of a two dimensional matrix of such input data values, and pass stages subsequent to the first pass stage receiving an ordered set of input data from the preceding pass stage, and means for performing four data transformations on the four input data values to produce four output data values, said means for performing each of the four data transformations including a first means for performing a first operation of selective addition or subtraction of the four input data values, followed by a second means for performing a second operation of selective multiplication by an exponential multiplier.

11. A circuit for implementing a two dimensional fast fourier transform as claimed in claim 10, each arithmetic logic unit receiving four input data values a, b, c and d, and combining the input data values by executing the following four data operations thereon to produce four output data values A, B, C and D,

12. A pipelined and parallel system for implementing a two dimensional fast fourier transform as claimed in claim 11, wherein each switching circuit means includes two input data lines, a set of two synchronous delay lines, and a set of two input synchronous switches for switching input data on the two input data lines into either the arithmetic logic unit of that switching circuit means or into the set of two synchronous delay lines in that switching circuit means, two output data lines, and set of two output synchronous switches, coupled to the arithmetic logic unit of that switching circuit means and further coupled to the set of two synchronous delay lines, for switching input data from the delay lines and from the arithmetic logic unit either to the two data output lines or as data inputs to the arithmetic logic unit.

13. A pipelined and parallel architecture for implementing a two dimensional fast fourier transform as claimed in claim 12, wherein for each switching circuit means in each i^th pass, the two synchronous delay lines therein have delays of N/2ⁱ, and further including means for simultaneously and synchronously switching the two input synchronous switches and two output synchronous switches after each delay of N/2ⁱ.

14. A pipelined and parallel system for implementing a two dimensional fast fourier transform as claimed in claim 10, wherein each switching circuit means includes two input data lines, a set of two synchronous delay lines, and a set of two input synchronous switches for switching input data on the two input data lines into either the arithmetic logic unit of that switching circuit means or into the set of two synchronous delay lines in that switching circuit means, two output data lines, and a set of two output synchronous switches, coupled to the arithmetic logic unit of that switching circuit means and further coupled to the set of two synchronous delay lines, for switching input data from the delay lines and from the arithmetic logic unit either to the two data output lines or as data inputs to the arithmetic logic unit.