|Article title||TRUNCATION ERRORS OF THE RESULTS OF FIXED-POINT ARITHMETIC OPERATIONS IN THE FFT ALGORITHMS|
|Authors||O.V. Yershova, A.V. Chkan, E.V. Kirichenko, E.A. Semernikov|
|Section||SECTION II. MATHEMATICAL AND SOFTWARE OF SUPERCOMPUTERS|
|Month, Year||12, 2014 @en|
|Abstract||The errors of decimation-in-frequency fast Fourier transform (DIF FFT) calculation (without scaling) caused by limitations of the length fixed-point results of arithmetic operations depending on the FFT size, the number of the spectrum component and the method of brining the result to the system word length (truncation or rounding) are considered. Analytic expressions of root-mean-square (RMS) errors of spectrum calculation both for truncation and rounding of the results of multiplication in the DIF FFT algorithm (without scaling) depending on the FFT size and the number of the spectrum component were obtained. It is shown that in the range of low frequency it is possible to use the dependence of the module of mathematical expectation of truncation errors from the number of a spectral sample for approximate estimation of the noise level caused by truncation of the results of arithmetic operations for the DIF FFT. The mathematical experiment was performed to calculate errors of arithmetic operations of FFT for a white Gaussian noise as the input process. The graphics of RMS value of truncation and rounding errors depending on the number of spectral component are presented. It is shown that the dependence of RMS value of truncation errors of arithmetic operations on the number of spectral component has asymmetrical behavior and lead to the significant spectrum distortions in the range of low frequency. The computational modeling has proved the matching of experimental and theoretical noise levels.|
|Keywords||The effect of the accumulation of errors; the fast fourier transform; error analysis; numerical modeling; digital signal processing.|
|References||1. Rabiner L., Gould B. Teoriya i primenenie tsifrovoy obrabotki signalov [Theory and application of digital signal processing]. Moscow: Mir, 1978, 848 p.
2. Medvedev S.Yu., Perov M.Yu., Yakimov A.V. Tochnost' tsifrovoy otsenki spektra signala [The accuracy of the digital spectrum estimation], Trudy 1-go soveshchaniya po proektu NATO SfP-973799
Semiconductors [Proceedings of the 1st meeting of the NATO project SfP-973799 Semiconductors]. Nizhny Novgorod, 2001. Available at: http://www.rf.unn.ru/NATO/1ws/SfP_Project_R.pdf.
3. Pyatkin A.K. Otsenka razryadnosti tselochislennogo vychislitelya BPF dlya zadannogo urovnya sootvetstvuyushchikh poter' v otnoshenii signal/shum [Evaluation bit integer calculator FFT for a given level of the corresponding losses in the signal-to-noise], Tsifrovaya
obrabotka signalov [Digital signal processing], 2005, No. 1, pp. 46-49.
4. Aksenov O.Yu., Borisov Yu.I. K razryadnosti vychislitelya BPF pri ego realizatsii na protsessore L1879VM1 (NM6403) [To the capacity of the FFT calculator during its implementation on the processor LVM (NM6403)], Tsifrovaya obrabotka signalov [Digital signal processing], 2004, No. 2, pp. 40-43.
5. LogiCORE IP Fast. Fourier Transform v9.0. Product Guide for Vivado. Design Suite. PG109 December 18, 2013.
6. Available at: http://www.xilinx.com/support/documentation/ ipdocumentation/xfft/v90/pg109-xfft.pdf.
7. Kaneko T. and Liu B. Accumulation of roundoff errors in fast Fourier transforms, J. Ass. Comput. Mach., 1970, Vol. 17, pp. 537–654.
8. Ayficher E., Dzhervis B. Tsifrovaya obrabotka signalov. Prakticheskiy podkhod [Digital signal processing. A practical approach]. Moscow–St. Petersburg: K., Vil'yams, 2004, 992 p.
9. Spravochnik po teorii veroyatnostey i matematicheskoy statistike [Handbook of probability theory and mathematical statistics]. Moscow: Nauka. Glavnaya redaktsiya fizikomatematicheskoy literatury, 1985, 264 p.