A comparison of integer fast fourier transforms for lossless coding
The lifting scheme-based Integer Fast Fourier Transform (IntFFT), an integer approximation of the FFT, is reversible. When it is used for lossless coding applications, the computational complexity and approximation error increase due to realization of the trivial butter, ies by three lifting steps. Since the error appears as "noise . oor" and it limits the lossless coding ef. ciency, it is desirable to reduce not only the computational complexity but also the noise . oor level as much as possible. This survey presents two schemes to realize an improved IntFFT in terms of the number of arithmetic operations and the level of the noise . oor. The . rst scheme is based on employment of two/three lifting step schemes with combined rounding operations, and the second one is the multi-dimensional lifting (MDL) scheme. The improvement is shown by comparing the number of arithmetic operations and rounding operations to compute the IntFFT and also by comparing levels of the noise . oor. In addition, an improvement in lossless coding ef. ciency due to the reduced noise . oor can be predicted by observing the reduced estimated entropy of the IntFFT coef. cients.