File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Error analysis and efficient realization of the multiplier-less FFT-like transformation (ML-FFT) and related sinusoidal transformations

TitleError analysis and efficient realization of the multiplier-less FFT-like transformation (ML-FFT) and related sinusoidal transformations
Authors
KeywordsDiscrete Cosine Transform (Dct)
Discrete Fourier Transform (Dft)
Discrete W Transform (Dwt)
Error Analysis
Implementation
Multiplier-Less Approximation
Radix-P Fast Fourier Transform (Fft)
Real-Valued
Sum-Of-Powers-Of-Two (Sopot)
Issue Date2006
PublisherSpringer New York LLC. The Journal's web site is located at http://springerlink.metapress.com/openurl.asp?genre=journal&issn=0922-5773
Citation
Journal Of VLSI Signal Processing Systems For Signal, Image, And Video Technology, 2006, v. 44 n. 1-2, p. 97-115 How to Cite?
AbstractThis paper studies the round-off analysis, design and implementation, and applications of the multiplier-less Fast Fourier Transform-like (ML-FFT) transformation proposed by Chan et al. [1, 2]. The ML-FFT parameterizes the twiddle factors in the conventional FFT algorithm as certain rotation-like matrices and approximates the associated parameters inside these matrices by the sum-of-power-of-two (SOPOT) or canonical signed digits representations, hence avoiding expensive multiplications. The error due to the SOPOT approximation is called the coefficient round-off error and it has been studied in [1, 2]. This paper studies the signal round-off error arising from internal rounding and develops a recursive noise model for ML-FFT. Using this model, a random search algorithm is proposed to minimize the hardware resources for realizing the ML-FFT subject to a prescribed output bit accuracy. To address the irregular structure of the ML-FFT due to the varying number of SOPOT terms used, a framework for its software implementation is also developed. The resulting algorithm has a regular implementation structure and is shown to offer a good performance similar to their floating-point counterpart. Finally, a new ML-FFT for real-valued input, called the ML-RFFT, is proposed. Because of the symmetry in the algorithm, it only requires about half the number of additions as required by the ML-FFT. Using the mappings between the DFT and the DCTs and DWTs, new ML-FFT-based transformations called ML-DCTs and ML-DWTs are derived. Design examples are given to demonstrate the usefulness of the proposed methods. © 2006 Springer Science + Business Media, LLC.
Persistent Identifierhttp://hdl.handle.net/10722/155332
ISSN
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorTsui, KMen_US
dc.contributor.authorChan, SCen_US
dc.date.accessioned2012-08-08T08:32:56Z-
dc.date.available2012-08-08T08:32:56Z-
dc.date.issued2006en_US
dc.identifier.citationJournal Of VLSI Signal Processing Systems For Signal, Image, And Video Technology, 2006, v. 44 n. 1-2, p. 97-115en_US
dc.identifier.issn1387-5485en_US
dc.identifier.urihttp://hdl.handle.net/10722/155332-
dc.description.abstractThis paper studies the round-off analysis, design and implementation, and applications of the multiplier-less Fast Fourier Transform-like (ML-FFT) transformation proposed by Chan et al. [1, 2]. The ML-FFT parameterizes the twiddle factors in the conventional FFT algorithm as certain rotation-like matrices and approximates the associated parameters inside these matrices by the sum-of-power-of-two (SOPOT) or canonical signed digits representations, hence avoiding expensive multiplications. The error due to the SOPOT approximation is called the coefficient round-off error and it has been studied in [1, 2]. This paper studies the signal round-off error arising from internal rounding and develops a recursive noise model for ML-FFT. Using this model, a random search algorithm is proposed to minimize the hardware resources for realizing the ML-FFT subject to a prescribed output bit accuracy. To address the irregular structure of the ML-FFT due to the varying number of SOPOT terms used, a framework for its software implementation is also developed. The resulting algorithm has a regular implementation structure and is shown to offer a good performance similar to their floating-point counterpart. Finally, a new ML-FFT for real-valued input, called the ML-RFFT, is proposed. Because of the symmetry in the algorithm, it only requires about half the number of additions as required by the ML-FFT. Using the mappings between the DFT and the DCTs and DWTs, new ML-FFT-based transformations called ML-DCTs and ML-DWTs are derived. Design examples are given to demonstrate the usefulness of the proposed methods. © 2006 Springer Science + Business Media, LLC.en_US
dc.languageengen_US
dc.publisherSpringer New York LLC. The Journal's web site is located at http://springerlink.metapress.com/openurl.asp?genre=journal&issn=0922-5773en_US
dc.relation.ispartofJournal of VLSI Signal Processing Systems for Signal, Image, and Video Technologyen_US
dc.subjectDiscrete Cosine Transform (Dct)en_US
dc.subjectDiscrete Fourier Transform (Dft)en_US
dc.subjectDiscrete W Transform (Dwt)en_US
dc.subjectError Analysisen_US
dc.subjectImplementationen_US
dc.subjectMultiplier-Less Approximationen_US
dc.subjectRadix-P Fast Fourier Transform (Fft)en_US
dc.subjectReal-Valueden_US
dc.subjectSum-Of-Powers-Of-Two (Sopot)en_US
dc.titleError analysis and efficient realization of the multiplier-less FFT-like transformation (ML-FFT) and related sinusoidal transformationsen_US
dc.typeArticleen_US
dc.identifier.emailTsui, KM:kmtsui@eee.hku.hken_US
dc.identifier.emailChan, SC:scchan@eee.hku.hken_US
dc.identifier.authorityTsui, KM=rp00181en_US
dc.identifier.authorityChan, SC=rp00094en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1007/s11265-006-7510-9en_US
dc.identifier.scopuseid_2-s2.0-33746432171en_US
dc.identifier.hkuros140408-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-33746432171&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume44en_US
dc.identifier.issue1-2en_US
dc.identifier.spage97en_US
dc.identifier.epage115en_US
dc.identifier.isiWOS:000239323300006-
dc.publisher.placeUnited Statesen_US
dc.identifier.scopusauthoridTsui, KM=7101671591en_US
dc.identifier.scopusauthoridChan, SC=13310287100en_US
dc.identifier.citeulike843298-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats