Efficient regressive structures for implementation of forward (DST-II) and inverse discrete sine transform (IDST-II) are developed. The proposed algorithm not only minimizes the arithmetic complexity compared to the existing algorithms (Wany (1990), Hupta and Rao (1990), Yip and Rao (1987), Murthy and Swamy (1992)) but also provides hardware savings over the algorithm (Jain et al. (2008)) by the same authors. The naturally ordered input sequence makes the new algorithms suitable for on-line computation. 1. Introduction Discrete sine transform (DST) and discrete cosine transform (DCT) are used as key functions in many signal and image processing applications, for example, block filtering, transform domain adaptive filtering, digital signal interpolation, adaptive beam forming, image resizing, speech enhancement [1–6] and so forth, due to their near optimal transform coding performance. Both DST and DCT are good approximations to the statistically optimal Karhunen-Loeve transform [7, 8]. It is found that in case of image with high correlation coefficient, DCT-based coding results in better performance but for low correlation image, DST gives lower bit rate [8]. Since both DCT and DST are computationally intensive, many efficient algorithms have been proposed to improve the performance of their implementation [9–12]; however most of these are only good software solutions. Chiang and Liu [13] suggested a regressive structure for DCT-IV and DST-IV using second order digital filters. This paper is aimed at developing a similar regressive filter structure for DST-II/IDST-II that provides considerable hardware saving compared to the existing algorithm [14] and also reduces the computation complexity in terms of number of operation (multiplication and addition) as compared to the existing algorithms [15–18]. The advantage of this implementation is that no permutation is required for the input/output sequences, and therefore it is especially suitable for on-line computation. 2. Regressive Formulas of DST-II/IDST-II and Realization through Filter Structure The DST of a sequence and its inverse are given by [14] where and Replacing by in (1a), by in (2), and after some algebraic manipulations, we obtain DST-II/IDST-II in the form Let ; and . Further we define We may rewrite (3) in the form Further, we can write as or Equation (9) can be represented by a sinusoidal recursive formula as In the same manner, we derive the sinusoidal formula for (5) as In (6) and (7), we define Using the sinusoidal recursive formula given in (10) and the fact that, ; and , (12) can be
References
[1]
Z. Wang, G. A. Jullien, and W. C. Miller, “Interpolation using the discrete sine transform with increased accuracy,” Electronics Letters, vol. 29, no. 22, pp. 1918–1920, 1993.
[2]
S. A. Martucci and R. M. Mersereau, “New approaches to block filtering of images using symmetric convolution and the DST or DCT,” in Proceedings of IEEE International Symposium on Circuits and Systems (ISCAS '93), pp. 259–262, May 1993.
[3]
F. Beaufays, “Transform-domain adaptive filters: an analytical approach,” IEEE Transactions on Signal Processing, vol. 43, no. 2, pp. 422–431, 1995.
[4]
Y. S. Park and H. W. Park, “Arbitrary-ratio image resizing using fast DCT of composite length for DCT-based transcoder,” IEEE Transactions on Image Processing, vol. 15, no. 2, pp. 494–500, 2006.
[5]
L. Xueyao, X. Hua, and C. Bailing, “Noisy speech enhancement based on discrete sine transform,” in Proceedings of the 1st International Multi-Symposiums on Computer and Computational Sciences (IMSCCS '06), pp. 199–202, April 2006.
[6]
S. C. Lim, D. Y. Kim, and Y. L. Lee, “Alternative transform based on the correlation of the residual signal,” in Proceedings of the 1st International Congress on Image and Signal Processing (CISP '08), pp. 389–394, May 2008.
[7]
R. J. Clarke, “Relation between the Karhunen Loeve and Sine transform,” Electronics Letters, vol. 20, no. 1, pp. 12–13, 1984.
[8]
A. K. Jain, “Fast Karhunen-Loeve transform for a class of stochastic processes,” IEEE Transactions on Communications, vol. 24, no. 9, pp. 1023–1029, 1976.
[9]
V. Kober, “Fast algorithms for the computation of sliding discrete sinusoidal transforms,” IEEE Transactions on Signal Processing, vol. 52, no. 6, pp. 1704–1710, 2004.
[10]
D. Püschel and J. M. F. Moura, “Algebraic signal processing theory: cooley-Tukey type algorithms for DCTs and DSTs,” IEEE Transactions on Signal Processing, vol. 56, no. 4, pp. 1502–1521, 2008.
[11]
P. K. Meher and M. N. S. Swamy, “New systolic algorithm and array architecture for prime-length discrete sine transform,” IEEE Transactions on Circuits and Systems II, vol. 54, no. 3, pp. 262–266, 2007.
[12]
P. K. Meher, A. P. Vinod, J. C. Patra, and M. N. S. Swamy, “Reduced-complexity concurrent systolic implementation of the discrete sine transform,” in Proceedings of IEEE Asia Pacific Conference on Circuits and Systems (APCCAS '06), pp. 1535–1538, December 2006.
[13]
H. C. Chiang and J. C. Liu, “A regressive structure for on-line computation of arbitrary length DCT-IV and DST-IV transforms,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 6, no. 6, pp. 692–695, 1996.
[14]
P. Jain, B. Kumar, and S. B. Jain, “Discrete sine transform and its inverse—realization through recursive algorithms,” International Journal of Circuit Theory and Applications, vol. 36, no. 4, pp. 441–449, 2008.
[15]
Z. Wang, “Fast discrete sine transform algorithms,” Signal Processing, vol. 19, no. 2, pp. 91–102, 1990.
[16]
A. Gupta and K. R. Rao, “Fast recursive algorithm for the discrete sine transform,” IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. 38, no. 3, pp. 553–557, 1990.
[17]
P. Yip and K. R. Rao, “On the shift properties of DCT’s and DST’s,” IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. 35, no. 3, pp. 404–406, 1987.
[18]
N. R. Murthy and M. N. S. Swamy, “On the computation of running discrete cosine and sine transform,” IEEE Transactions on Signal Processing, vol. 40, no. 6, pp. 1430–1437, 1992.
