ABSTRACT
Transforms that maps integers to integers have advantagesnot available for floating point transforms. Integercomputations are faster and free from round off errors(integer transforms are widely used for lossless coding). Thepaper presents an algorithm of Integer Fast FourierTransform (intFFT) based on lifting factorization. IntegerDiscrete Cosine Transform (intDCT) is also computed as anexample of intFFT application.
1. INTRODUCTION
Great interest in the topic of integer transforms can beobserved in literature during last few years. Most of dataprocessed in computers come from sampling of continuoussystems and thus poses integer values (with range boundedby A/D converter). For those integer data integer toolsseems to be natural. Two significant advances of integertransforms are: no rounding of errors during computationsand faster computations. Integer transforms are widely usedfor lossless transform coding (especially for biomedicalsignals). The breakthrough in integer transforms designingwas lifting introduced by I. Daubechies and W. Sweldens[1]. In the paper lifting scheme is used for computations ofInteger Fast Fourier Transform (intFFT). Factorization ofcomplex multiplications is based on the method presented in[2]. In contrary to [2] presented intFFT is based onsimplified butterfly computations with division in time (oneand not two complex multiplications). Presented intFFTalgorithm is based on lifting 'do' 'undo' methodology. Anexample of Integer Discrete Cosine Transform is given aspossible use of intFFT.
2. FORWARD AND INVERSE INTFFT
Lifting structure is presented in Fig.1. The signal in upper(lower) branch is modified by functions fn and the signalfrom the opposite branch. Regardless of function fn thelifting is always revertible. Inverse transform is simpleundoing steps from the forward transform. If the input signalis integer valued and functions fn return integers the overalltransform maps integers to integers and the reconstructionerror is exactly equal to zero.Discrete Fourier Transform of a discrete signal x(n) ,x(n) 0, for n 0 and n N −1 is defined as:Figure 1: Lifting scheme, f1, f2 ... - arbitrary functions.−−10( ) ( ) , 0, 1,..., 1NnknN X k x n W k N ,knNjknN W e2−(1)Equation (1) represents multiplication and addition of twocomplex numbers and the absolute value of knN W equals 1. Inpaper [2] lifting factorization for complex multiplication isproposed. The lifting scheme for complex multiplication incase of integer valued computations is presented in Fig.2. Zstands for analyzed (input) complex signal, knN W value isdetermined by vertical branches in the structure. In case ofknN W angle equals to 0,/ 2,factorization is not necessaryand Z is multiplied by +/-1 or +/-j. Steps from Fig.2a,b can beeasily undo which results in integer division by knN W (ormultiplication by conjugate knN W ) without rounding offerrors.Implementation of intFFT is based on lifting 'do' 'undo'property in three levels: 1) complex multiplication by twiddlefactor WN in the way that multiplication by conjugate twiddlefactor returned original value, 2) butterfly structure thatallows computation in inverse (or synthesis) butterfly seeFig.1, and 3) computing intIFFT by undoing steps fromintFFT.


download full report
http://eurasipProceedings/Eusipco/Eusipco2004/defevent/papers/cr1295.pdf