# Regressive Structures for Computation of DST-II and Its Inverse

Authors: Priyanka Jain; Anamika Jain
Journal: ISRN Electronics
 (2012)

---

## Abstract

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.


---

## Body

## 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 sequencey(n),n=1,2,…,N and its inverse are given by [14] (1a)Y[k]=γk∑n=1Ny(n)sin[(n-12)kπN],k=1,2,…,N,
where
(1b)γk=2Nεk,εk={12k=N1k=1,2,…,N-1,
and(2)y(n)=2N∑k=1NεkY[k]sin[(n-12)kπN],n=1,2,…,N.
Replacing n by N-nin (1a), k by N-kin (2), and after some algebraic manipulations, we obtain DST-II/IDST-II in the form
(3)Y[k]=(-1)k+1γk∑n=0N-1y(N-n)sin[(n+12)kπN],k=1,2,…,N,y(n)=(-1)n2N∑k=0N-1εkY[N-k]cos[(n-12)kπN],n=1,2,…,N.
Let θk=kπ/N; θn=(n-1/2)(π/N) and xn=cosθn.Further we define(4)Vn[xk]=sin(n+1/2)θksin(θk/2),k=1,2,…,N,(5)Uk[xn]=coskθncosθn,n=1,2,…,N.
We may rewrite (3) in the form
(6)Y[k]=(-1)k+1sinθk2γk∑n=0N-1y(N-n)Vk[xk],k=1,2,…,N,(7)y[n]=(-1)ncosθn2N∑k=0N-1εkY[N-k]Uk[xn],n=1,2,…,N.
Further, we can write  Vn+1[xk] as
(8)Vn+1[xk]=sin(n+3/2)θksin(θk/2),k=1,2,…,N,
or
(9)Vn+1[xk]=2sin(n+1/2)θkcosθk-sin(n-1/2)θksin(θk/2),k=1,2,…,N.
Equation (9) can be represented by a sinusoidal recursive formula as
(10)Vn+1[xk]=2cosθkVn-Vn-1,k=1,2,…,N.
In the same manner, we derive the sinusoidal formula for (5) as
(11)Uk+1[xn]=2cosθkUk-Uk-1,n=1,2,…,N.
In (6) and (7), we define
(12)SN(k)=∑n=0N-1y(N-n)Vn[xk],(13)PN(k)=∑k=0N-1Y[N-k]Uk[xn].
Using the sinusoidal recursive formula given in (10) and the fact that, V0=1; V-1=-1 and U0=cosθn, (12) can be written as
(14)SN(k)=y(N)V0+∑n=1N-1y(n-n)Vn[xk]=y(N)+∑n=0N-2y(N-n-1)Vn+1[xk]=y(N)+∑n=0N-2y(N-n-1)[2cosθkVn-Vn-1]=y(N)+2cosθkSN-1(k)-y(N-1)V-1-SN-2(k).
Similarly, (13) is written as
(15)PN(k)=Y[N]U0+∑k=1N-1Y[N-k]Uk[xn]=Y[N]cosθn+∑k=0N-2Y[N-k-1]Uk+1[xn]=Y[N]cosθn+2cosθkPN-1(k)-Y[N-1]-PN-2(k),
where U-1=1. Using (6) and (12), the DST-II can be expressed as
(16)Y[k]=(-1)k+1γksinθk2SN(k),k=1,2,…,N.
Similarly, using (7) and (13), the IDST expression is
(17)y(n)=(-1)nγkcosθnPN(k),n=1,2,…,N.
From (16) and (17), DST-II/IDST-II can be implemented with the second order filter structure shown in Figures 1 and 2.Figure 1
Regressive structure for computation of DST-II.Figure 2
Regressive structure for computation of IDST-II.


## 3. Performance

The proposed algorithm has been presented with the aim of realizing the DST/IDST of any length for on-line computation. It can be seen from the regressive structure for DST-II shown in Figure1 that only one real multiplication per sample is required to bring the system in a state from which SN(k) can be computed. Similarly the regressive structure shown in Figure 2 for IDST shows that two real multiplications are required for PN(k) computation. The constant multiplication by (-1)k+1γksin(θk/2) or (-1)nγkcosθn at the output need not be performed at every iteration of the difference equation but it is to be multiplied after the Nth step. Hence the total real multiplications for DST computation are (N+1) and for IDST computation are (2N+1). The number of additions for DTS as well as for IDST is 3N. In Table 1 the number of multipliers, adders and latches required by the present algorithm is compared with those required in algorithms [14]. It can be seen from Table 1 that the new recursive algorithm is efficient in terms of saving the number of multipliers, adder, and  latches compared to algorithm [14]. Both of the algorithms compute the DST/IDST of an N point real sequence. Although the proposed algorithm does not optimize the number of computational cycle, but has advantage in terms of hardware compared to previous approach [14]. Further, the filter structure is numerically stable, as it involves no division at all. Algorithm [14] needs addition and subtraction of input sequence whereas the input sequence for the present algorithm is in the natural order, which makes the proposed approach suitable for on-line computation. Table 2 shows the comparison of   computational complexity of the proposed algorithm with the other algorithms [15–18]. It can be seen that the proposed algorithm not only reduces the number of multiplication significantly but also reduces the total number of operations.Table 1
Hardware comparison for implementing DST-II/IDST-II coefficient.
S. No.
Comparison
Proposed
[14]
DST
IDST
DST
IDST
1
Latches
2
2
4
4
2
Real multiplier
2
3
4
4
3
Adder
3
3
6
8
4
Complex multiplier
0
0
0
0
5
Computation cycles
N
N
N/2
N/2Table 2
Comparison of algorithms for computing DST in terms of addition and multiplication.
Algorithms
Number of addition
Number of multiplication
N
=
2
M
N
=
2
M
Fast DST, [15, 16]
3
M
N
/
2
-
N
+
1
M
N
/
2
+
1
[17]
4N + 2
6N
[18]
5N + 2
5N
The proposed design
3N
(N + 1)


## 4. Conclusion

The proposed regressive algorithm has been derived mathematically and realized for kernels of DST and its inverse. This algorithm is effective for realization using software and hardware techniques. This algorithm provides substantial savings in actual number of multipliers, adders, and latches in the hardware implementation required to perform the DST/IDST and reduces the arithmetic complexity compared to the existing algorithms. The proposed regressive algorithm has simple, regular, and modular filter structure and is particularly suitable for on-line computation.



---

*Source: 537469-2012-11-21.xml*