Computing multidimensional DFTs in FPGA
US6073154A · kind A · utility
Assignee
Inventor
Key dates
| Filing date | Jun 26, 1998 |
| Grant date | Jun 6, 2000 |
| Priority date | — |
| Expiry date | Jun 26, 2018 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F17/141
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
An FPGA configured for computation of an N.times.N discrete Fourier transform (DFT) using polynomial transforms defined in modified rings of transforms, comprising a first buffer for ordering a set of polynomial data in a two dimensional matrix, a multiplier for multiplying each element of the two dimensional matrix by .omega..sup.-n.sbsp.2 (where .omega.=e.sup.-j.pi./N, e is a constant (ln(e)=1), j=.sqroot.-1, n.sub.2 =the column index number in the matrix, and N=the transform length) to produce a premultiplication product, a polynomial transform circuit for performing a polynomial transform (PT) modulo (z.sup.N +1), size N, root z.sup.2 on the premultiplication product to produce a polynomial transform result, where z represents the unit delay operator, a reduced DFT calculator for performing N reduced DFTs of N terms on the polynomial transform result to produce a permuted output, and an address generator for reordering the permuted output to a natural order.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.