# Improved Algorithm for ODCT Computation of a Running Data Sequence

Authors: S. Akhter; V. Karwal; R. C. Jain
Journal: Journal of Electrical and Computer Engineering
 (2012)

---

## Abstract

Fast windowed update algorithms capable of independently updating the odd discrete cosine transform (ODCT) and odd discrete sine transform (ODST) of a running data sequence are analytically developed. In this algorithm, to compute the ODCT coefficients of a real-time sequence, we do not require the ODST coefficients. Similarly, the ODST coefficients of the shifted sequence can be calculated without using ODCT coefficients. The running input data sequence is sampled using a rectangular window. However, this idea can be easily extended for other windows. The update algorithm derived herein can be used to compute the transform coefficients of the shifted sequence as new data points are available. The complexity of developed algorithm isO(N). The validity of algorithm is tested by MATLAB simulations.


---

## Body

## 1. Introduction

The DCT transform [1] has been extensively used in various digital image coding schemes and image compression standards. It is known that in most practical cases, the DCT-based schemes outperform in terms of compression ratio. In any real-time data processing system, a new data point is input at every sampling instant. One method to find the DCT can be to compute it for the entire data vector or data matrix. Although this looks easy, it is a cumbersome task. Another method is to reduce the dataset and then compute DCT coefficients for a smaller dataset. Hence, a part of incoming data stream is sampled using window of size N, and its transform coefficient is computed. An example is a tapped delay line adaptive filter [2].  In this case as new samples arrive, the transform of the updated data is computed. One computationally attractive method given by Yip and Rao [3] uses the shift property of the discrete transform wherein the transform of the shifted data can be obtained from respective transforms (both DCT and DST) of the unshifted data plus the data points shifting in, That is, the transform of the updated sequence is obtained without having to perform complete N-point transform at every instant of time. However, this scheme of Yip and Rao [3] had a drawback of dependency between DCT and DST coefficients.Update algorithm initially developed was limited to one-point update at a time [3, 4]. Later algorithms for r-point, 1≤r≤N-1, and update for DCT, and DST were developed [5, 6] but all these algorithms needed simultaneous update of DCT and DST coefficients, that is, to compute the updated DCT coefficients, the DST coefficients need to be calculated simultaneously and vice versa. Thereafter, independent update algorithms were developed in [5] based on second-order shift properties of DCT and DST coefficients, these algorithms were limited to one-point update for even discrete cosine transform (EDCT) and even discrete sine transform (EDST). This concept was extended to include r new points at a time for EDCT/EDST in [7–9]. The DCT and DST transforms of type I–IV form a group of-so-called even DCT/DST. These transforms are very well studied and a number of efficient implementation techniques exist in the literature.Another group of transforms, namely, DCT/DST V–VIII, are called “Odd” DCT/DST. Not much work has been reported in developing efficient implementation techniques for odd DCT/DST computation [10]. In this paper, we give an efficient algorithm for real-time computation of transform coefficients capable of independently updating odd DCT and odd DST coefficients. We have derived r-point independent update algorithm for independently processing ODCT and ODST coefficients in the presence of rectangular window. The algorithms are analytically derived and the results verified with MATLAB simulations for various different values of sequence length N and different data points. Our interest in this work is based on new application of odd DCT/DST-VI/VII transforms with a possible application in ISO/IEC/ITU-T high efficiency video coding (HEVC) standards [10].To compute the transform of an infinite input sequence, first a suitable sequence of lengthN is extracted. To calculate the effect of inclusion of r new points, update algorithms can be used for fast computation of transform coefficient of the updated sequence. In this paper, we have derived the update algorithms for ODCT type-II and ODST type-II that have the capability of independently updating the ODCT and ODST coefficients. These algorithms would be useful in applications where we need only the ODCT coefficients or only the ODST coefficients. These algorithms provide lower complexity implementation as compared to the previously available algorithms as we do not need to calculate and store values of both ODST and ODCT coefficients.The ODCT-II and ODST-II of input signalf(x) of length N is defined by
(1)C(k)=22N-1Pk∑x=0N-1Px+1f(x)cos2x+12N-1kπfork=0,1,…,N-1,S(k)=22N-1∑x=0N-2f(x)sin2x+12N-1kπfork=1,…,N-1,
where
(2)Pj=12,forj=0orN1,otherwise.C(k) and S(k) are the ODCT and ODST coefficients, respectively.Modifying the original equations of ODCT and ODST to include a sequence pointern [5], we get
(3)C(n,k)=22N-1Pk∑x=0N-1Px+1f(n-N+x)cos2x+12N-1kπ,(4)S(n,k)=22N-1∑x=0N-2f(n-N+x)sin2x+12N-1kπ.
The input data f(x) in the above expressions is indexed from f(n-N) to f(n-1).This paper is organized as follows. In Section2, the r-point independent update algorithm is derived analytically for the ODST independent ODCT-II, in the presence of rectangular window. ODCT independent ODST-II update algorithm can be derived similarly and results is given for brevity. In Section 3, MATLAB implementation is discussed followed by Section 4 where comparison of computational complexities is given in terms of number of multiplications and additions followed by Section 5 that lists the conclusion.


## 2. Derivation of ther-Point Update Algorithm for Independent ODCT-II

LetC(n+r,k) for k=0,1,…,N-1 represent the updated ODCT-II coefficients including the effect of r new data points. From (3), we get
(5)C(n+r,k)=22N-1Pk∑x=0N-1Px+1f(n-N+x+r)×cos2x+12N-1kπ.
Defining a=2/2N-1 and fragmenting the summation into two parts, x=0 to N-r-1 and x=N-r to N-1 yields,
(6)C(n+r,k)=aPk∑x=0N-1-rPx+1f(n-N+x+r)×cos2x+12N-1kπ+aPk∑x=N-rN-1Px+1f(n-N+x+r)×cos2x+12N-1kπ.
The term Px+1 is equal to unity in the first summation term for the given range. Substituting y=x+r in first term and i=x+r-N in the second term, we get
(7)C(n+r,k)=aPk∑y=rN-1f(n-N+y)cos(2(y-r)+12N-1kπ)+aPk∑i=0r-1Pi-r+N+1f(n+i)cos(2(i-r+N)+12N-1kπ).
Breaking the 1st term into two summations, we get
(8)C(n+r,k)=aPk∑y=0N-1f(n-N+y)cos(2(y-r)+12N-1kπ)-aPk∑y=0r-1f(n-N+y)cos(2(y-r)+12N-1kπ)+aPk∑i=0r-1Pi-r+N+1f(n+i)cos(2(i-r+N)+12N-1kπ).
Therefore,
(9)C(n+r,k)=aPk∑y=0N-2f(n-N+y)cos(2(y-r)+12N-1kπ)+aPk(-1)kf(n-1)cos2πrk2N-1-aPk∑y=0r-1f(n-N+y)cos(2(y-r)+12N-1kπ)+aPk∑i=0r-1Pi-r+N+1f(n+i)cos(2(i-r+N)+12N-1kπ).
Introducing term Py+1 in the first summation since it is equal to unity for the given range, we get
(10)C(n+r,k)=aPk∑y=0N-2Py+1f(n-N+y)cos(2(y-r)+12N-1kπ)+aPk(-1)kf(n-1)cos2πrk2N-1-aPk∑y=0r-1f(n-N+y)cos(2(y-r)+12N-1kπ)+aPk∑i=0r-1Pi-r+N+1f(n+i)cos(2(i-r+N)+12N-1kπ).
After modifying the 1st summation term, we have
(11)C(n+r,k)=aPk∑y=0N-1Py+1f(n-N+y)cos(2(y-r)+12N-1kπ)+aPk(-1)k(1-12)f(n-1)cos2πrk2N-1-aPk∑y=0r-1f(n-N+y)cos(2(y-r)+12N-1kπ)+aPk∑i=0r-1Pi-r+N+1f(n+i)cos(2(i-r+N)+12N-1kπ).
Expanding the first summation term yields
(12)C(n+r,k)=aPk∑y=0N-1Py+1f(n-N+y)cos(2y+1)kπ2N-1cos2rkπ2N-1+aPk∑y=0N-1Py+1f(n-N+y)sin(2y+1)kπ2N-1sin2rkπ2N-1+aPk(-1)k(1-12)f(n-1)cos2rkπ2N-1-aPk∑y=0r-1f(n-N+y)cos(2(y-r)+12N-1kπ)+aPk∑i=0r-1Pi-r+N+1f(n+i)cos(2(i-r+N)+12N-1kπ).
first term can be written as C(n,k)cos(2rkπ/(2N-1)). Modifying the 2nd term in summation from y=0 to N-1 as y=0 to N-2, we get
(13)C(n+r,k)=C(n,k)cos2rkπ2N-1+aPk∑y=0N-2Py+1f(n-N+y)×sin(2y+1)kπ2N-1sin2rkπ2N-1+aPk(-1)k(1-12)f(n-1)cos2πrk2N-1-aPk∑y=0r-1f(n-N+y)cos(2(y-r)+12N-1kπ)+aPk∑i=0r-1Pi-r+N+1f(n+i)cos(2(i-r+N)+12N-1kπ).
It can be observed in 2nd term that Py+1 is unity for y=0 to N-2. Using (4), this term can be rewritten as follows:
(14)C(n+r,k)=C(n,k)cos2rkπ2N-1+PkS(n,k)sin2rkπ2N-1+(-1)kaPk(1-12)f(n-1)cos2rkπ2N-1-aPk∑y=0r-1f(n-N+y)cos(2(y-r)+12N-1kπ)+aPk∑i=0r-1Pi-r+N+1f(n+i)cos(2(i-r+N)+12N-1kπ).
Replacing
(15)Ar=cos2rkπ2N-1,Br=sin2rkπ2N-1.
Putting y=r-x-1 in the 1st summation term, and i=r-x-1 in the 2nd summation term, we get
(16)C(n+r,k)=ArC(n,k)+BrPkS(n,k)+(-1)kaPkAr(1-12)f(n-1)-aPk∑x=0r-1f(n-N-1+r-x)cos2x+12N-1kπ+aPk(-1)k∑x=0r-1PN-xf(n-1+r-x)cos2xkπ2N-1.
Rewriting the last summation term from x=1 to r-1 and adding x=0th term, we get,
(17)C(n+r,k)=ArC(n,k)+BrPkS(n,k)+(-1)kaPkAr(1-12)f(n-1)-aPk∑x=0r-1f(n-N-1+r-x)cos2x+12N-1kπ+aPk(-1)k∑x=1r-1PN-xf(n-1+r-x)cos2xkπ2N-1.+aPk(-1)kPNf(n-1+r)PN-x in the 5th term is equal to unity for the given range of summation. Rewriting the 5th term with the summation limits changed from x=1 to r-1 as x=0 to r-1 and subtracting x=0th term, we get
(18)C(n+r,k)=ArC(n,k)+BrPkS(n,k)-aPk∑x=0r-1f(n-N-1+r-x)cos2x+12N-1kπ+aPk(-1)k∑x=0r-1f(n-1+r-x)cos2xkπ2N-1+(-1)kaPkAr(1-12)f(n-1)+(-1)kaPk(12-1)f(n-1+r).
The expression given in (18) shows that for finding ODCT coefficient of r-point updated signal, we require both ODCT and ODST coefficients of previous data points. We need a way to derive ODST independent update equation. For making independent ODCT update, we calculate C(n-r,k) as follows, which is ODCT coefficient of r-point update of previous data points:
(19)C(n-r,k)=22N-1Pk∑x=0N-1Px+1f(n-N+x-r)×cos2x+12N-1kπ.
Substituting y=x-r in the above equation yields
(20)C(n-r,k)=aPk∑y=-rN-r-1Py+r+1f(n-N+y)cos(2(y+r)+12N-1kπ).
Breaking the summation into two terms, we get
(21)C(n-r,k)=aPk∑y=0N-r-1Py+r+1f(n-N+y)cos(2(y+r)+12N-1kπ)+aPk∑y=-r-1Py+r+1f(n-N+y)cos(2(y+r)+12N-1kπ).
Changing the first summation limit to y=0 to N-r-2, and adding  y=(N-r-1)th term, we get,
(22)C(n-r,k)=aPk∑y=0N-r-2Py+r+1f(n-N+y)cos(2(y+r)+12N-1kπ)+aPk∑y=-r-1Py+r+1f(n-N+y)cos(2(y+r)+12N-1kπ)+aPk12f(n-r-1)(-1)k.Py+r+1 is unity in the range of 1st summation as well as in 2nd summation. Introducing Py+1 in the first term which is unity in the given range, we get,
(23)C(n-r,k)=aPk∑y=0N-r-2Py+1f(n-N+y)cos(2(y+r)+12N-1kπ)+aPk∑y=-r-1f(n-N+y)cos(2(y+r)+12N-1kπ)+aPk12f(n-r-1)(-1)k.
Changing the summation of the first term from y=0 to N-r-1 and subtract y=(N-r-1)th term, we get
(24)C(n-r,k)=aPk∑y=0N-r-1Py+1f(n-N+y)cos(2y+2r+12N-1kπ)+aPk∑y=-r-1f(n-N+y)cos(2(y+r)+12N-1kπ)+aPkf(n-r-1)(12-1)(-1)k.
Solving further yields
(25)C(n-r,k)=aPk∑y=0N-1Py+1f(n-N+y)cos2y+1+2r2N-1kπ-aPk∑y=N-rN-1Py+1f(n-N+y)cos(2(y+r)+12N-1kπ)+aPk∑y=-r-1f(n-N+y)cos(2(y+r)+12N-1kπ)+aPkf(n-r-1)(12-1)(-1)k.
Expanding 1st term, substituting y=N-x-1 in the 2nd term and y=-(1+x) in the 3rd term, we have
(26)C(n-r,k)=aPk∑y=0N-1Py+1f(n-N+y)cos2y+12N-1kπcos2rkπ2N-1-aPk∑y=0N-1Py+1f(n-N+y)sin2y+12N-1kπsin2rkπ2N-1-aPk∑x=0r-1PN-xf(n-1-x)×cos(2(N-1-x+r)+12N-1kπ)+aPk∑x=0r-1f(n-N-1-x)cos(2x+1-2r2N-1kπ)+aPkf(n-r-1)(12-1)(-1)k.
Using the definition of ODCT and ODST as given in (3) and (4) and substituting Ar=cos(2rkπ/(2N-1)),Br=sin(2rkπ/(2N-1))yields(27)C(n-r,k)=ArC(n,k)-PkBrS(n,k)+aPkf(n-r-1)(12-1)(-1)k-(-1)kaPk∑x=0r-1PN-xf(n-1-x)×(Arcos2xkπ2N-1+Brsin2xkπ2N-1)+aPk∑x=0r-1f(n-N-1-x)×(Arcos2x+12N-1kπ+Brsin2x+12N-1kπ).
Adding (18) and (27) results in
(28)C(n+r,k)=2ArC(n,k)-C(n-r,k)+aPk(-1)k(12-1)×[f(n-1-r)-f(n-1)Ar+f(n-1+r)]+aPk∑x=0r-1[f(n-N-1-x)Ar-f(n-N-1+r-x)]×cos2x+12N-1kπ+aPk(-1)k×∑x=0r-1[f(n-1+r-x)-PN-xf(n-1-x)Ar]×cos2xkπ2N-1-aPkBr(-1)k∑x=0r-1PN-xf(n-1-x)sin2xkπ2N-1+aPkBr∑x=0r-1f(n-N-1-x)sin2x+12N-1kπfork=0,1,…,N-1,
where C(n-r,k) represent the ODCT coefficients of the previous time-step sequence, C(n,k) represents the ODCT coefficients in the current time step sequence, and C(n+r,k) represents ODCT coefficients of r-point updated sequence.Equation (28) yields ODCT-II independent update equation that is independent of the ODST coefficients hence it can be used for fast computation of ODCT coefficients in the presence of r new data points. The above derived algorithm can be used to compute the ODCT transform for any value of sequence length N and value of r ranging from 1 to N-1. From (28), it can be easily seen that while computing the ODCT coefficients of updated sequence, we require ODCT coefficients of the two previous times-step sequence.Therefore, there will be two stages for computing coefficients for updated sequence. One is the preprocessing stage where we calculate coefficients of two previous time-step data points using the conventional definition of the transform, and the second is the update stage where update algorithm is used to calculate coefficients of the shifted sequence. Once the pre-processing stage is over, the algorithm enters into update stage and the last two time-step coefficients are saved inC(n-r,k) and C(n,k). The algorithm remains in update stage thereafter. The conventional definitions are to be used only once in pre-processing stage and thereafter update algorithm is used each time new data points are shifted in the input sequence.The signal pointf(n-N-1-x) represents the oldest data points shifted out and f(n-N-1+r-x) represents recent data shifted out. The signal point f(n-1+r-x) indicates the newest data points shifted in and f(n-1-x) shows earlier data entered into. Analogous ODCT-II independent ODST-II fast update algorithms in the presence of r new data points for 1≤r≤N-1 can be similarly derived and the final result is listed below. The detailed derivation of ODST-II fast update algorithm is excluded for brevity as
(29)S(n+r,k)=2ArS(n,k)-S(n-r,k)-a(-1)kBrf(n-1)+a∑x=0r-1[f(n-N-1+r-x)+f(n-N+x-r)]×sin2x+12N-1kπ-a(-1)k∑x=1r-1[f(n-1+r-x)+f(n-1-r+x)]×sin2xkπ2N-1fork=1,…,N.S(n-r,k) is the ODST coefficients of the previous time-step sequence, S(n,k) is the ODST coefficients in the current time step, and S(n+r,k) represents the updated ODST coefficients in the presence of r-points shifted in. In (29), the signal points f(n-N-1+r-x) represent recent data shifted out and f(n-N-r+x) represent the oldest data points shifted out. The signal point f(n-1+r-x) indicates data point shifted in the previous time-step and f(n-1-r+x) indicates newest data point shifted in.Steps for computing ODCTr-point independent update are given in Figure 1. Signal f(x-r)represents the initial data points, f(x) is the signal after r-point shift and f(x+r)represents the signal after another r-point shift.Figure 1
Flow chart of independent update algorithm.Independent update algorithm can be implemented in two major steps: one is the pre-processing step wherein we use the conventional ODCT definitions to compute the transforms and once we have the transform of two time steps then we can use the independent update algorithm, analytically derived earlier in this section. The pre-processing step is used only once to compute the two time-step transforms then the algorithm enters the update stage and remains in this stage thereafter.(a) Preprocessing Step
Compute the ODCT coefficients values off(x-r) and f(x) from the definition and save these values as Cold(k) and C(k), respectively.(b) Update Step
This involves the computation of ODCT coefficients ofr-point shifted data, f(x+r), using update algorithm listed in (28).Step 1.
Using the values ofCold(k) and C(k) (computed in part (a)) and the new data pointed shifting in, we compute the ODCT coefficients of the new r-point shifted data using (28) and save it as Cnew(k).Step 2.
OverwriteCold(k) with C(k), and C(k) with Cnew(k).Repeat the update step for each time newr-point data is entered.The flow chart for this algorithm is given in Figure1. Similarly, the ODCT independent ODST independent update algorithm can be implemented in the presence of rectangular window.


## 3. MATLAB Implementation

The independent update algorithms derived in (28) and (29) for ODCT and ODST, respectively, were tested in MATLAB for different values of N and r. The code snippet is given in Algorithm 1 for r=2 and N=8.Algorithm 1
r
oot2 = sqrt(2.0);N = 8,r = 2,sign = −1;
root_2N = sqrt(2.0 * N − 1.0);a = 2.0/root_2N;
for k = 0: N − 1;
if
(mod
(
k, N
)==0)
pk = 1.0/root2;
else
pk = 1.0;
end;
M = N + N − 1;
theta = 2 * r * k * pi/M;Ar = cos(theta);Br = sin(theta);
sign = −sign;
p1 = 0.0;p2 = 0.0;p3 = 0.0;p4 = 0.0;p5 = 0.0
for  x = 0 : r − 1;
angle1 = (x + x + 1) * k * pi/M;
angle2 = (x + x) * k * pi/M;
sin
1 = sin(angle1);
sin
2 = sin(angle2);
cos
1 = cos(angle1);
cos
2 = cos(angle2);
if
(x==0)
pk1 = 1.0/root2;
else
pk1 = 1.0;
end;
p1 = p1 + pk1  * (fnew(r − x)) * sin2;
p2 = p2 + (fold(r − x)) * sin1;
p3 = p3 + (−fold(2 *  r − x) + Ar * fold(r − x)) * cos1;
p4 = p4 + (fnew(2 *  r − x) − pk1  * Ar * fnew(r − x)) * cos2;
end;
p5 = (1.0/sqrt(2.0) − 1) * sign * (f(N) − fnew(r) * Ar + fnew(2 * r));
term1 = a  *  pk  * (−sign * Br * p1 + Br * p2 + p3 + sign * p4 + p5);
C
NEW
(k + 1) = 2 * Ar * C(k + 1) − Cold(k + 1) + term1
end;In the program shown in Algorithm1 program Cold(k) represents the oldest ODCT coefficient of input signal say F=[12345678]. Two new data points “9” and “10” are shifted in, are the modified data array becomes F=[345678910] and its coefficients are denoted by C(k). This is the pre-processing stage. When two new data points “11” and “12” are shifted in, the coefficients Cnew(k) of the shifted sequence are calculated using the update algorithm derived in (28). Array “fold” is used for storing the four data points shifting out and array “fnew” is used for storing the four new data point shifting in.After simulating the program shown in Algorithm1, CNEW value calculated using the update algorithm is found to be the same as that computed from definition of ODCT for the shifted sequence F=[56789101112]. This verifies the algorithm.Similarly, the code for ODST-II independent update algorithm was written to test the correctness of the derived algorithm.


## 4. Performance Analysis

The computation of running ODCT and ODST based on independent update algorithm is expected to provide certain advantages over simultaneous update algorithm proposed by Murthy and Swamy [2], and Sherlock and Kakad [6] for EDCT/EDST. The comparison is done on the basis of total number of operations (multiplications and additions) used for the computation of transform coefficients for r-point updated data. If ODCT-II is to be computed for N=8 using basic definition as given by (3), then it requires 46 multiplication and 56 addition operations. Similarly for ODST-II computation from definition requires 33 multiplication and 38 addition operations.The expression for simultaneous update of ODST-II is given below(30)S(n+r,k)=ArS(n,k)-BrC(n,k)+a∑x=0r-1f(n-N-1+r-x)sin2x+12N-1kπ-a(-1)k∑x=0r-1f(n-1+r-x)sin2xkπ2N-1fork=1toN-1.
Computation of ODST coefficients of the updated sequence, for sample length N=8, using simultaneous update algorithm requires 14r+7 multiplications and 14r additions. The above values are computed after expanding (30) for different values of r. We have done analysis for r=1 and 2, and it can be extended for other values of r also.Forr=1,
(31)S(n+1,k)=A1S(n,k)-BrC(n,k)+af(n-N)sinπk2N-1.
Computing the ODST coefficients S(1) to S(7) using (31) requires 21 multiplication and 14 addition operations. Similarly for r=2, we have
(32)S(n+2,k)=A2S(n,k)-B2C(n,k)+a[f(n-N+1)sinπk2N-1+f(n-N)sin3πk2N-1]-a(-1)kf(n)sin2πk2N-1.
Computing the ODST coefficients S(1) to S(7) using (32) requires 35 multiplication and 28 addition operations. In general we require 14r+7 multiplication and 14r addition operation for computing all ODST coefficients for any value of r.Similarly, computational requirement for simultaneous ODCT-II coefficients computation using (18) can be derived and analysis for r=1 and 2 are discussed below.Forr=1,
(33)C(n+1,k)=A1C(n,k)+B1PkS(n,k)-aPkf(n-N)cosπk2N-1+(-1)kaPk12f(n)+(-1)kaPk(1-12)f(n-1)A1.
For computing the ODCT coefficients C(0) to C(7) using (33), we require 37 multiplication and 32 addition operations. Similarly for r=2, we have
(34)C(n+2,k)=A2C(n,k)+B2PkS(n,k)-aPkf(n-N+1)×cosπk2N-1+(-1)kaPk12f(n+1)+(-1)kaPkf(n)cos2πk2N-1+(-1)kaPk(1-12)f(n-1)A2-aPkf(n-N)×cos3πk2N-1.
Computing the ODCT coefficients C(0) to C(7) using (34) requires 51 multiplication and 48 addition operations. In general, for computing ODCT coefficients, we require 14r+23 multiplication and 16r+16 addition operation. It is to be noted that simultaneous update requires both ODCT and ODST coefficients to be updated simultaneously, so overall requirement is 28r+30 multiplications and 30r+16 additions plus multiplications and additions operations that are required during the pre-processing stage.Multiplication and addition operation required for ODCT-II independent update algorithm are given below.Forr=1,
(35)C(n+1,k)=2A1C(n,k)-C(n-1,k)+aPk(-1)k12f(n)+aPk(-1)k(12-1)f(n-2)-aPk(-1)k×(2-1)f(n-1)A1+aPkcoskπ2N-1[f(n-N-1)-f(n-N)]fork=0,1,…,N-1.
In general, we require 14r+25 multiplications and 32r+16 additions for independent update algorithm for ODCT computation.The comparative analysis for power consumption for different approaches for ODCT/ODST computation is given below. To compute ODCT-II coefficient ofr-point shifted data using the definition requires using 46 multiplications and 56 additions operation, r times. For example, to compute ODCT coefficient for N=8 data point using conventional definition for 7 time shifted data points requires 46 multiplications and 56 additions, eight times. If power consumption by one multiplication operation is Pcm and that by one addition operation is Pca, then total power consumed by multiplications is 368Pcm and that by additions is 448Pca.For the same sample length ofN=8 and for the same set of ODCT/ODST coefficient computation, r=7 and hence simultaneous update algorithm require using 121 multiplications and 128 additions for ODCT update and 105 multiplications and 98 additions for ODST update. Additional 79 multiplications and 94 additions are required during the pre-processing stage for calculating the ODCT/ODST coefficients from definition. Hence power consumed by multiplications is 305Pcm and that by additions is 320Pca.Similarly, for the same sample length ofN=8 and for the same set of ODCT coefficient computation r=6, independent update algorithm requires 201 multiplications and 320 additions. Hence power consumed by multiplications is 201Pcm and that by additions is 320Pca. Table 1 shows the power consumed during addition and multiplication operation, for N=8 and r=7. The computation of running ODCT and ODST based on independent update algorithm provides advantage over the simultaneous update for different value of r. Comparison for computational burden between independent update algorithm and simultaneous update algorithm for different value of r-point update is given in Table 2.Table 1
Comparison of power consumption.
Type
Multiplications (Pcm)
Additions (Pca)
From definition
368
448
From simultaneous update algorithm
305
320
From independent update algorithm
201
320Table 2
Comparison of multiplication operations required.
r
Simultaneous update
Independent update algorithm
1
8
N
5
N
2
12
N
7
N
3
16
N
9
NFrom (31), for r=1, ODST computation requires 3N multiplication and 2N addition operation. Similarly from (33), for r=1, ODCT computation requires 5N multiplication and 4N addition operations. So we can say that simultaneous update algorithm requires total 8N multiplication and 6N addition operations. Similarly from (35), we can see that ODCT independent update algorithm for r=1 requires 5N multiplication and 6N addition operations. In general, the simultaneous update algorithm requires (4r + 4)N multiplication operations while independent update algorithm requires (2r + 3)N multiplication operations, whereas the additions operation requirement for both algorithms are (4r + 2)N. From Table 2, it can be seen that independent update algorithm requires less number of multiplications as compared to those required for simultaneous update algorithm, and hence we have less power consumption. Next we consider the memory requirement. Memory is needed in both the algorithms to store the following:(a)
the coefficients of the recursive equations,(b)
transform result,(c)
input signal samples.Table 3 shows the memory requirement for both the update algorithms. It can be seen that simultaneous update requires more storage as compared to that required in independent update, since in simultaneous update algorithm both ODCT as well as ODST coefficients are to be stored. Thus it can be concluded that independent update algorithm is better in terms of storage requirement as compared to simultaneous update algorithm.Table 3
Comparison of memory requirement.
r
Coefficient
Input sequence
Transform domain data
Total memory requirement
Simultaneous update
Independent update
Simultaneous update
Independent update
Simultaneous update
Independent update
Simultaneous update
Independent update
1
6
N
5
N
N
+
1
N
+
2
2
N
2
N
9
N
+
1
8
N
+
2
2
10
N
7
N
N
+
2
N
+
4
2
N
2
N
13
N
+
2
10
N
+
4
3
14
N
9
N
N
+
3
N
+
6
2
N
2
N
17
N
+
3
12
N
+
6


## 5. Conclusion

The use of recursive method is very appropriate for machine-based computation. The shift properties of DCT and DST transforms gives a set of recursive equations that can be used for updating DCT and DST coefficient of a running data sequence. We have given an efficient algorithm for computation of ODST-II and ODCT-II coefficients in the presence of rectangular window. In the given algorithm, the computation of ODCT coefficients does not require simultaneous computation of ODST coefficients. The recursive equations are analytically derived and tested using MATLAB. The algorithms developed in this paper are an improvement over existing update algorithms as it provides independence between ODCT and ODST coefficient’s computation, thereby reducing computation and memory requirement. The algorithm derived is tested for different values of sample lengthN and r. The complexity of the analytically derived independent update algorithms is of the order of O(N).



---

*Source: 879626-2012-12-13.xml*