Architecture for two dimensional fast fourier transform

Details Architecture for two dimensional fast fourier transform Architecture for two dimensional fast fourier transform

1983-10-06

1986-07-15

Malzahn, David H.

Boots, shoes, and leggings

G06F 15332

Patent

active

046010068

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.

REFERENCES:
patent: 3777131 (1973-12-01), Llewellyn
patent: 3952186 (1976-04-01), Speiser et al.
patent: 4092723 (1978-05-01), Picquendar et al.
patent: 4159528 (1979-06-01), Perry
patent: 4328555 (1982-05-01), Nussbaumer
Stone, "Parallel Processing with the Perfect Shuffle", IEEE Trans. on Computers, vol. C-20, No. 2, Feb. 1971, pp. 153-161.
Joshi et al., "A Video Rate Two Dimensional FFT Processor", ICASSP 80 Proceedings IEEE International Conference on Acoustics, Speech & Signal Processing, Denver, Co., Apr. 9-11, 1980, pp. 774-777.

Affiliated with

Also associated with

Rating

Architecture for two dimensional fast fourier transform does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Architecture for two dimensional fast fourier transform, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Architecture for two dimensional fast fourier transform will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1744037