WO2002091221A3 - Address generator for fast fourier transform processor - Google Patents

Address generator for fast fourier transform processor Download PDF

Info

Publication number
WO2002091221A3
WO2002091221A3 PCT/US2002/014393 US0214393W WO02091221A3 WO 2002091221 A3 WO2002091221 A3 WO 2002091221A3 US 0214393 W US0214393 W US 0214393W WO 02091221 A3 WO02091221 A3 WO 02091221A3
Authority
WO
WIPO (PCT)
Prior art keywords
address generator
cascaded
adders
fourier transform
fast fourier
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/US2002/014393
Other languages
French (fr)
Other versions
WO2002091221A2 (en
Inventor
Marwan Jaber
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Jaber Associates LLC USA
Original Assignee
Jaber Associates LLC USA
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Jaber Associates LLC USA filed Critical Jaber Associates LLC USA
Priority to EP02734247A priority Critical patent/EP1436725A2/en
Publication of WO2002091221A2 publication Critical patent/WO2002091221A2/en
Anticipated expiration legal-status Critical
Publication of WO2002091221A3 publication Critical patent/WO2002091221A3/en
Ceased legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/10—Complex mathematical operations
    • G06F17/14—Fourier, Walsh or analogous domain transformations, e.g. Laplace, Hilbert, Karhunen-Loeve, transforms
    • G06F17/141—Discrete Fourier transforms
    • G06F17/142—Fast Fourier transforms, e.g. using a Cooley-Tukey type algorithm

Landscapes

  • Physics & Mathematics (AREA)
  • Mathematical Physics (AREA)
  • Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Computational Mathematics (AREA)
  • Mathematical Analysis (AREA)
  • Mathematical Optimization (AREA)
  • Pure & Applied Mathematics (AREA)
  • Data Mining & Analysis (AREA)
  • Theoretical Computer Science (AREA)
  • Discrete Mathematics (AREA)
  • Algebra (AREA)
  • Databases & Information Systems (AREA)
  • Software Systems (AREA)
  • General Engineering & Computer Science (AREA)
  • Complex Calculations (AREA)

Abstract

An address generator for use in conjunction with a fast Fourier transform processor includes an efficient architecture for computing the memory addresses of input data points, output data points and twiddle coefficients. In particular, multiplication operation in the calculation of memory addresses is minimized. Instead, a cascaded series of adders (32, 34, 36, 38) are used, in which the output of one adder is input to the next adder. At each stage of the cascaded adders, the same input variable is successively added. The cascaded adder structure is used in the writing address generator, the reading address generator and twiddle coefficient address generator. In addition, a plurality of modulo N circuits is used in series with the cascaded series of adders to generate the twiddle coefficient addresses.
PCT/US2002/014393 2001-05-07 2002-05-07 Address generator for fast fourier transform processor Ceased WO2002091221A2 (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
EP02734247A EP1436725A2 (en) 2001-05-07 2002-05-07 Address generator for fast fourier transform processor

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US28930201P 2001-05-07 2001-05-07
US60/289,302 2001-05-07

Publications (2)

Publication Number Publication Date
WO2002091221A2 WO2002091221A2 (en) 2002-11-14
WO2002091221A3 true WO2002091221A3 (en) 2004-04-29

Family

ID=23110932

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/US2002/014393 Ceased WO2002091221A2 (en) 2001-05-07 2002-05-07 Address generator for fast fourier transform processor

Country Status (3)

Country Link
US (1) US6993547B2 (en)
EP (1) EP1436725A2 (en)
WO (1) WO2002091221A2 (en)

Families Citing this family (17)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP1426872A3 (en) * 2002-12-03 2006-02-22 STMicroelectronics Ltd. Linear scalable FFT/IFFT computation in a multi-processor system
KR100492091B1 (en) * 2002-12-10 2005-06-01 삼성전자주식회사 The FFT Computation Circuits and Methods on Programmable Processors
EP1447752A3 (en) * 2003-02-17 2006-02-22 STMicroelectronics Pvt. Ltd Method and system for multi-processor FFT/IFFT with minimum inter-processor data communication
US7914543B2 (en) * 2003-10-14 2011-03-29 Satiety, Inc. Single fold device for tissue fixation
US20050128937A1 (en) * 2003-12-11 2005-06-16 Nokia Corporation Determination of correlation in the frequency domain
US20050278404A1 (en) * 2004-04-05 2005-12-15 Jaber Associates, L.L.C. Method and apparatus for single iteration fast Fourier transform
US7761495B2 (en) * 2004-04-05 2010-07-20 Jaber Associates, L.L.C. Fourier transform processor
US20060155795A1 (en) * 2004-12-08 2006-07-13 Anderson James B Method and apparatus for hardware implementation of high performance fast fourier transform architecture
DE102005045519A1 (en) * 2005-09-23 2007-03-29 Newlogic Technologies Ag Method and apparatus for FFT calculation
WO2008010598A1 (en) * 2006-07-18 2008-01-24 Nec Corporation Information communication processing device, information communication terminal, information communication system, function switching method, and function switching program
US7675847B2 (en) 2007-07-10 2010-03-09 Wipro Limited Hardware implementation of a programmable FFT based on a half length FFT core
US8370414B2 (en) * 2009-01-15 2013-02-05 Telefonaktiebolaget L M Ericsson (Publ) FFT-based parallel system with memory reuse scheme
US20130046806A1 (en) * 2010-02-16 2013-02-21 Ntt Docomo, Inc. Fast fourier transform circuit
US9002917B2 (en) * 2010-07-30 2015-04-07 National Instruments Corporation Generating filter coefficients for a multi-channel notch rejection filter
MY166267A (en) 2011-03-28 2018-06-22 Dolby Laboratories Licensing Corp Reduced complexity transform for a low-frequency-effects channel
CN105988973B (en) * 2015-02-13 2019-04-19 上海澜至半导体有限公司 Fast Fourier Transform (FFT)/Fast Fourier Transform (FFT) method and circuit
US20180373677A1 (en) * 2017-05-16 2018-12-27 Jaber Technology Holdings Us Inc. Apparatus and Methods of Providing Efficient Data Parallelization for Multi-Dimensional FFTs

Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5012441A (en) * 1986-11-24 1991-04-30 Zoran Corporation Apparatus for addressing memory with data word and data block reversal capability
US5091875A (en) * 1990-03-23 1992-02-25 Texas Instruments Incorporated Fast fourier transform (FFT) addressing apparatus and method
US5430667A (en) * 1992-05-22 1995-07-04 Nec Corporation Hardware arrangement for fast fourier transform having improved addressing techniques
US6035313A (en) * 1997-03-24 2000-03-07 Motorola, Inc. Memory address generator for an FFT

Family Cites Families (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
GB0001517D0 (en) * 2000-01-25 2000-03-15 Jaber Marwan Computational method and structure for fast fourier transform analizers
US6792441B2 (en) * 2000-03-10 2004-09-14 Jaber Associates Llc Parallel multiprocessing for the fast fourier transform with pipeline architecture

Patent Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5012441A (en) * 1986-11-24 1991-04-30 Zoran Corporation Apparatus for addressing memory with data word and data block reversal capability
US5091875A (en) * 1990-03-23 1992-02-25 Texas Instruments Incorporated Fast fourier transform (FFT) addressing apparatus and method
US5430667A (en) * 1992-05-22 1995-07-04 Nec Corporation Hardware arrangement for fast fourier transform having improved addressing techniques
US6035313A (en) * 1997-03-24 2000-03-07 Motorola, Inc. Memory address generator for an FFT

Also Published As

Publication number Publication date
WO2002091221A2 (en) 2002-11-14
US6993547B2 (en) 2006-01-31
US20030041080A1 (en) 2003-02-27
EP1436725A2 (en) 2004-07-14

Similar Documents

Publication Publication Date Title
He et al. A new approach to pipeline FFT processor
US6366936B1 (en) Pipelined fast fourier transform (FFT) processor having convergent block floating point (CBFP) algorithm
US7870176B2 (en) Method of and apparatus for implementing fast orthogonal transforms of variable size
US6081821A (en) Pipelined, high-precision fast fourier transform processor
US6629117B2 (en) Method for computing a fast fourier transform and associated circuit for addressing a data memory
US5091875A (en) Fast fourier transform (FFT) addressing apparatus and method
US5163017A (en) Pipelined Fast Fourier Transform (FFT) architecture
EP1281118A1 (en) Method and apparatus for performing computations using residue arithmetic
KR970008893A (en) A device comprising a floating-point multiplier with a reduced critical path delay
US4598266A (en) Modulo adder
US5491652A (en) Fast Fourier transform address generator
US6993547B2 (en) Address generator for fast fourier transform processor
US6317770B1 (en) High speed digital signal processor
US20050160127A1 (en) Modular pipeline fast fourier transform
Huang et al. A refined fast 2-D discrete cosine transform algorithm
KR101162649B1 (en) A method of and apparatus for implementing fast orthogonal transforms of variable size
US20080228845A1 (en) Apparatus for calculating an n-point discrete fourier transform by utilizing cooley-tukey algorithm
US20060288068A1 (en) Memory control method for storing operational result data with the data order changed for further operation
US20040128335A1 (en) Fast fourier transform (FFT) butterfly calculations in two cycles
US4588980A (en) Residue to analog converter
Takala et al. Scalable FFT processors and pipelined butterfly units
Kallapu et al. DRRA-based reconfigurable architecture for mixed-radix FFT
Takala et al. Butterfly unit supporting radix-4 and radix-2 FFT
El-Khashab et al. An architecture for a radix-4 modular pipeline fast Fourier transform
JP3962331B2 (en) Method, circuit arrangement and use thereof for performing a fast Fourier transform

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A2

Designated state(s): AL AM AT AU AZ BA BB BG BR BY CA CH CN CU CZ DE DK EE ES FI GB GD GE GH GM HR HU ID IL IN IS JP KE KG KP KR KZ LC LK LR LS LT LU LV MD MG MK MN MW MX NO NZ PL PT RO RU SD SE SG SI SK SL TJ TM TR TT UA UG UZ VN YU ZW

AL Designated countries for regional patents

Kind code of ref document: A2

Designated state(s): AT BE CH CY DE DK ES FI FR GB GR IE IT LU MC NL PT SE TR

121 Ep: the epo has been informed by wipo that ep was designated in this application
WWE Wipo information: entry into national phase

Ref document number: 2002734247

Country of ref document: EP

REG Reference to national code

Ref country code: DE

Ref legal event code: 8642

WWP Wipo information: published in national office

Ref document number: 2002734247

Country of ref document: EP

NENP Non-entry into the national phase

Ref country code: JP

WWW Wipo information: withdrawn in national office

Country of ref document: JP