Element rearrangement method for fast Fourier transform
AssigneeNEC Corporation
InventorShouichirou Yamada
Life of this patent
Estimating the term…
Abstract
In a Fast Fourier Transform method, the elements of Fast Fourier Transform are arranged as a two-dimensional square and stored in areas of an array whose number of lines is twice that of columns. Positions of the columns having bit reversed column numbers are exchanged and the elements are linear vector stored so that the initial element of a column is always one position lower than the previous one. Then, the elements of such linear vector stored array are rearranged through exchange of columns having elements with bit reversed numbers and movement of the columns fully upward to made them flush.
Claims5
An element rearrangement method for a Fast Fourier Transform, comprising the steps of:
- (a) rearranging a plurality of elements of Fast Fourier transform constituting an original array by exchanging columns having the elements with bit reversed numbers and symmetrical positioning of the columns with respect to an oblique axis;
- and
- (b) rearranging the elements of the array generated in the above step by exchanging columns having the elements with bit reversed numbers.
An element rearrangement method for a Fast Fourier Transform, comprising the steps of:
- (a) storing a plurality of elements of Fast Fourier Transform arranged as a two-dimensional square in the areas of an array whose number of lines is twice the number of columns, the columns in said array having bit reversed column numbers exchanged and the elements being linear vector stored to said array areas so that the initial element of a column is always one position lower than the previous one;
- and
- (b) rearranging said linear vector stored array by exchanging columns having elements with bit reversed column numbers and the initial elements of the columns being flush.
Dependencies are inferred from the claim text.