Two dimensional fast Fourier transform converter
First Claim
1. A digital fast Fourier transform converter, comprising:
- a two-dimensional halfway memory;
a plurality of one-dimensional fast Fourier transform processors connected in parallel to said halfway memory, each processor including means for converting one-dimensional data point sets into one-dimensional fast Fourier transformed data point sets;
data input means for supplying said processors, in sequence, one set at a time per processor, with said one-dimensional data point sets;
transformed data output means for transferring said one-dimensional fast Fourier transformed data point sets, one set at a time per processor, from said processors to said halfway memory to form a partially fast Fourier transformed data frame made up of said one-dimensional fast Fourier transformed data point sets; and
second dimension transform means for transforming said partially fast Fourier transformed data frame into a completely fast Fourier transformed data frame.
1 Assignment
0 Petitions
Accused Products
Abstract
A two-dimensional fast Fourier transform converter utilizes parallel digital fast Fourier transform processors and a frame serial processing path to convert two-dimensional images of large pixel count (512×512 or higher) and high dynamic range (16 bits of pixel intensity quantization) at a rate equal to or exceeding real time processing rate of 30 frames/second. The parallel processors are organized for performing the row and column transformations in a highly parallel and efficient manner. In one embodiment, a uni-directional processing path with segmented image data busses to streamline the data movement is used. In a second embodiment, a bi-directional processing path is utilized such that the fast Fourier transform processors perform row and column conversions sequentially, thus reducing by a factor of two the number of individual fast Fourier transform processors required. The converter includes three port SRAM working memories, toggled DRAM image frame storage memories, and a data transfer and sequence controller.
40 Citations
46 Claims
-
1. A digital fast Fourier transform converter, comprising:
-
a two-dimensional halfway memory; a plurality of one-dimensional fast Fourier transform processors connected in parallel to said halfway memory, each processor including means for converting one-dimensional data point sets into one-dimensional fast Fourier transformed data point sets; data input means for supplying said processors, in sequence, one set at a time per processor, with said one-dimensional data point sets; transformed data output means for transferring said one-dimensional fast Fourier transformed data point sets, one set at a time per processor, from said processors to said halfway memory to form a partially fast Fourier transformed data frame made up of said one-dimensional fast Fourier transformed data point sets; and second dimension transform means for transforming said partially fast Fourier transformed data frame into a completely fast Fourier transformed data frame. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
-
-
14. A digital fast Fourier transform converter, comprising:
-
a plurality of fast Fourier transform line processing means for performing fast Fourier transforms sequentially on a plurality of image data point sets to form a plurality of line-transformed image data point sets, each set representing one line of a two-dimensional image frame, in order to generate a line-transformed image frame made up of said line-transformed image data point sets; a plurality of working line memory means, each connected to one of said plurality of fast Fourier transform line processing means for storing one line of said image frame during processing of said line by a respective line processing means to which the line memory means is connected; line input means for supplying said working line memory means, sequentially, one line at a time per line processing means, with said image data point sets; halfway video frame memory means for storing said line-transformed image frame; line output means connected to said working line memory means and said halfway video frame memory means for receiving said line-transformed data point sets from said working line memory means and storing said line-transformed data point sets in said halfway video frame memory means; a plurality of fast Fourier transformed column processing means for performing fast Fourier transforms sequentially on a plurality of data point sets to form a plurality of column-transformed data point sets, each data point set representing one column of said line-transformed image frame in order to generate a complete two-dimensional Fourier transformed image frame made up of said column-transformed data point sets; a plurality of working column memory means, each connected to one of said plurality of fast Fourier transform column processing means for storing one column of said line-transformed image frame during processing by a respective column processing means to which the column memory means is connected; column input means for supplying said working column memory means, sequentially, one column at a time per column processing means, with image data point sets representing columns of said line-transformed image frame; two-dimensional video frame memory means for storing said Fourier transformed image frame; and column output means connected to said column memory means and said two-dimensional video frame memory means for receiving column transformed data point sets from said working column means and storing them in said two-dimensional video frame memory means. - View Dependent Claims (15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34)
-
-
35. A method of performing a fast Fourier transform conversion, comprising the steps of:
-
(a) supplying a plurality of fast Fourier transform line processors, sequentially, one line at a time per processor, with image data point sets each representing one line of a two-dimensional image frame until all lines of said image frame have been supplied; (b) performing a fast Fourier line transform on each of said image data point sets when they are supplied to said line processors to form a plurality of line-transformed image data point sets; (c) supplying said line-transformed image data point sets to a halfway video frame memory to form a line-transformed image frame; (d) supplying image data point sets representing columns of said line-transformed image frame from said halfway video frame memory, sequentially, one column at a time per processor, to a second plurality of fast Fourier transform column processors until all columns of said line-transformed image frame have been supplied; (e) performing a fast Fourier transform column conversion on each of said image data point sets representing columns when said image data point sets representing columns are supplied to said column processors. - View Dependent Claims (36, 37, 38, 39, 40)
-
-
41. A method of performing a fast Fourier transform conversion, comprising the steps of:
-
(a) supplying a plurality of fast Fourier transform processors, sequentially, one line at a time per processor, with image data point sets each representing one line of a two-dimensional image frame until all lines of said image frame have been supplied; (b) performing a fast Fourier line transform on each of said image data point sets when they are supplied to said processors to form a plurality of line-transformed image data point sets; (c) supplying said line-transformed image data point sets to a halfway video frame memory to form a line-transformed image frame; (d) supplying image data point sets representing columns of said line-transformed image frame from said halfway video frame memory, sequentially, one column at a time per processor, to said processors until all columns of said line-transformed image frame have been supplied; (e) performing a fast Fourier transform column conversion on each of said image data point sets representing columns when said image data point sets representing columns are supplied to said processors to form a plurality of column-transformed image data point sets. - View Dependent Claims (42, 43, 44)
-
-
45. A digital fast Fourier transform converter, comprising:
-
fast Fourier transform processing means including a plurality of one-dimensional fast Fourier transform processors for performing fast Fourier transforms sequentially on a plurality of image data point sets to form a plurality of line-transformed data point sets; working memory means comprising a plurality of working memories, each connected to one of said plurality of fast Fourier transform processors for storing one of said data point sets while a respective fast Fourier transform processor to which the respective working memory means is connected performs a fast Fourier transform on one of said data point sets; halfway video frame memory means for storing a line-transformed image frame; two-dimensional video frame memory means for storing a Fourier transformed image frame; a bi-directional internal data bus connected to said plurality of working memory means, said halfway video frame memory means, and said two-dimensional video frame memory means; line input means connected to said plurality of working memories for supplying said working memories, sequentially, one line at a time per working memory, with image data point sets, each representing one line of a two-dimensional image frame, for processing by the respective processors to which the working memories are connected; line output means for transferring said line-transformed data point sets from said working line memories to said halfway video frame memory means via said bi-directional internal data bus for storage in said halfway video frame memory means as a line-transformed image frame; column input means for supplying, via said bi-directional internal data bus, said working memories with image data point sets representing columns of said line-transformed image frame, one column at a time per processor, for processing by the respective processor to which the working memories are connected; and column output means connected to said working memories for receiving column transformed data point sets from said working memories and storing them in said two-dimensional video frame memory means in order to form a complete two-dimensional Fourier transformed image frame. - View Dependent Claims (46)
-
Specification