DYNAMIC-RANGE ANALYSIS FOR THE IMPLEMENTATION OF FAST TRANSFORM

An optimal shortest word length implementation of the fast transform b ased upon mathematical analysis is presented in this research, The flo w graph of any fast transform can be expressed as the product of sever al sparse matrices, where each matrix represents a single pass butterf ly operation (i,e,, multiplication and accumulation). Each decomposed sparse matrix is analyzed to determine whether a butterfly operation w ould result in a bit overflow. Additional bits are allocated only to t he matrices in which an overflow is likely to occur so that the shorte st bit-length implementation is maintained. This methodology is applic able to the shortest bit-length implementation of any fast transform. The application of the proposed method to an existing FDCT algorithm i s demonstrated for fixed-point computation.