Fast DCT-I, DCT-III, and DCT-IV via Moments
- PDF / 758,460 Bytes
- 8 Pages / 600 x 792 pts Page_size
- 80 Downloads / 258 Views
Fast DCT-I, DCT-III, and DCT-IV via Moments J. G. Liu Key Laboratory of Education Ministry for Image Processing and Intelligence Control, Institute for Pattern Recognition and Artificial Intelligence, Huazhong University of Science & Technology, Wuhan 430074, China Email: [email protected]
Y. Z. Liu Department of Computer Science and Engineering, China University of Geosciences, Wuhan 430074, China Email: [email protected]
G. Y. Wang Key Laboratory of Education Ministry for Image Processing and Intelligence Control, Institute for Pattern Recognition and Artificial Intelligence, Huazhong University of Science & Technology, Wuhan 430074, China Email: [email protected] Received 3 December 2003; Revised 16 October 2004; Recommended for Publication by Wan-Chi Siu This paper presents a novel approach to compute DCT-I, DCT-III, and DCT-IV. By using a modular mapping and truncating, DCTs are approximated by linear sums of discrete moments computed fast only through additions. This enables us to use computational techniques developed for computing moments to compute DCTs efficiently. We demonstrate this by applying our earlier systolic solution to this problem. The method can also be applied to multidimensional DCTs as well as their inverses. Keywords and phrases: discrete cosine transforms, moment, fast transform, systolic array.
1.
INTRODUCTION
Discrete cosine transforms (DCTs) are widely used in speech coding and image compression. They resemble KarhunenLoeve transform for first-order Markov stationary random data and are classified into four groups [1]. Finding fast computational algorithms for DCTs has been a rather active subject [2, 3, 4, 5, 6]. These methods all tried to reduce the amount of multiplications. It is very important to low-power implementations of DCTs on mobile devices that no floating multiplications or less multiplications are needed. At the same time, the parallel hardware methods also have been developed for designing fast DCT processors [7, 8, 9, 10, 11, 12, 13, 14, 15]. Among them the systolic array methods have been given more attentions due to their easy VLSI implementation [7, 8, 9, 10, 11, 12]. Chang and Wang [7] proposed a systolic array approach that only used log2 N multipliers for N-point DCT (i.e., N transform samples). It is superior to other systolic array approaches used N or more multipliers [8, 9, 10, 11, 12]. Its disadvantage is that N should be a power of two. This limits the application of the method. We proposed a novel approach to DCTII [16], which exploited the idea of moment-based all-adder approximation of DCT-II. It could be implemented by both software and systolic array and could be applied to any size
N-point DCT-II. There are only O(log2 N/ log2 log2 N) multipliers in the systolic arrays. Now we extend our method to DCT-I, DCT-III, and DCT-IV. In this paper, first the relationship between DCTs and discrete moments is set up and then a moment-based algorithm and a systolic array to perform DCT-III are presented, followed by a complexity analysis. Finally our concl
Data Loading...
