# A Unified Algorithm for Subband-Based Discrete Cosine Transform

Authors: Lu-Ting Ko; Jwu-E Chen; Hsi-Chin Hsin; Yaw-Shih Shieh; Tze-Yun Sung
Journal: Mathematical Problems in Engineering
 (2012)

---

## Abstract

Discrete cosine transform (DCT) and inverse DCT (IDCT) have been widely used in many image processing systems and real-time computation of nonlinear time series. In this paper, the unified DCT/IDCT algorithm based on the subband decompositions of a signal is proposed. It is derived from the data flow of subband decompositions with factorized coefficient matrices in a recursive manner. The proposed algorithm only requires(4(log2n)−1−1) and (4(log2n)−1−1)/3 multiplication time for n-point DCT and IDCT, with a single multiplier and a single processor, respectively. Moreover, the peak signal-to-noise ratio (PSNR) of the proposed algorithm outperforms the conventional DCT/IDCT. As a result, the subband-based approach to DCT/IDCT is preferable to the conventional approach in terms of computational complexity and system performance. The proposed reconfigurable architecture of linear array DCT/IDCT processor has been implemented by FPGA.


---

## Body

## 1. Introduction

The discrete cosine transform (DCT) first proposed by Ahemd et al. [1] is a Fourier-like transform. While the Fourier transform decomposes a signal into sine and cosine functions, DCT only makes use of cosine functions with the property of high energy compaction. As DCT is preferable for a trade-off between the optimal decorrelation known as the Karhunen-Loève transform and computational simplicity [2], it has been extensively used in many applications [3–14]. In particular, two-dimensional (2D) DCT, such as 8×8 DCT, has been adopted in some international standards such as JPEG, MPEG, and H.264 [15]. In MP3 audio codec, the subband analysis and synthesis filter banks requires the use of 32-point DCT/integer DCT to expedite computation [16]. Other audio compression standards, for example, the Dolby Digital AC-3 codec, utilize a modified DCT with 256 or 512 data points.Many algorithms have been proposed for DCT/IDCT [17–21]. In which, the transportation matrix is factorized into products of simpler matrices. It is noted that, however, the factorized matrices are no longer as regular as the fast Fourier transform (FFT); thus, these algorithms can only achieve moderate computational speed. Specifically, the dedicated data paths deduced from the signal flow graphs (SFGs) of the above algorithms need to be optimized for performance enhancement, which is computationally intensive, and the custom-designed DCT is often complicated and cannot be easily scalable for variable data points.In this paper, we propose a novel linear-array architecture based on the subband decomposition of a signal for scalable DCT/IDCT. The remainder of this paper proceeds as follows. First, the subband-based 8-point DCT/IDCT algorithm [22] is reviewed in Section 2. Its extension to n-point DCT/IDCT called the unified subband-based algorithm is proposed in Section 3. Section 4 presents the analysis of system complexity. The reconfigurable architecture of linear-array DCT/IDCT processor implemented by FPGA (field programmable gate array) is proposed in Section 5, and the conclusion can be found in Section 6.


## 2. The Subband-Based 8-Point DCT/IDCT Algorithm

The discrete cosine transform (DCT) of an 8-point signal,[8], is defined as(2.1)c[k]=α[k]∑n=07x[n]cos⁡[(2n+1)kπ16],k=0,1,…,7,
where α[0]=1/(22), and α[k]=1/2 for k>0. It can be rewritten in the following matrix form:(2.2)c8=D8⋅x8,
where c8=[c[0]⋯c[7]]T, x8=[x[0]⋯x[7]]T,  and the transformation matrix D8 is as follows:(2.3)D8=18⋅[11111111acdf-f-d-c-abe-e-b-b-eebc-f-a-ddaf-c1-1-111-1-11d-afc-c-fa-de-bb-e-eb-bef-dc-aa-cd-f],
where a=2cos(π/16),b=2cos(2π/16),c=2cos(3π/16),d=2cos(5π/16),e=2cos(6π/16), and f=2cos(7π/16).LetxL[n] and xH[n] denote the low-frequency and high-frequency subband signals of x[n], respectively [22], which can be obtained by(2.4)xL[n]=12{x[2n]+x[2n+1]},xH[n]=12{x[2n]-x[2n+1]},
where n=0,1,2,3. As one can see, the DCT of x[8] can be rewritten as(2.5)c[k]=∑n=03α[k]x[2n]cos⁡((4n+1)kπ16)+∑n=03α[k]x[2n+1]cos⁡((4n+3)kπ16)=2cos⁡(πk16)∑n=03α[k]xL[n]cos⁡((2n+1)kπ8)︸cL[k]+2sin(πk16)∑n=03α[k]xH[n]sin((2n+1)kπ8)︸sH[k],
where cL[k] and sH[k] are the subbands DCT and DST (discrete sine transform) of x[n], respectively. Its vector form is as follows:(2.6)c8=[TSB_DCT,8TSB_DCT,8]8×8⋅M8⋅x8=[TSB_DCT,8TSB_DCT,8]8×8⋅[xLxH]8×1=TSB_DCT,8⋅xL︸ĉL,8+TSB_DST,8⋅xH︸ŝH,8,
where TSB_DCT,8 and TSB_DST,8 denote the 8×4 matrices of the subband DCT and DST, respectively, xL=[xL[0]⋯xL[3]]T, xH=[xH[0]⋯xH[3]]T and c8=[c[0]⋯c[7]]T. According to (2.4), the 8-point matrix M8 can be written as(2.7)M8=[0.50.5000000000.50.5000000000.50.5000000000.50.50.5-0.5000000000.5-0.5000000000.5-0.5000000000.5-0.5].
Due to the orthogonality between TSB_DCT,8 and TSB_DST,8, xL[n] and xH[n] can be obtained from c[k] by(2.8)xL[n]=∑n=07α[k]cos⁡(πk16)c[k]cos⁡((2n+1)kπ8),n=0,…,7,xH[n]=∑n=07α[k]sin(πk16)c[k]sin((2n+1)kπ8),n=0,…,7.
In [22], the multistage subband decomposition is as follows. cL,4 and cH,4 denote the DCTs of xL and xH, respectively, which can be obtained by cL,4=D4·xL and cH,4=D4·xH, where D4 is the transformation matrix(2.9)D4=14⋅[11112cos⁡π82cos⁡3π8-2cos⁡3π8-2cos⁡π81-1-112cos⁡3π8-2cos⁡π82cos⁡π8-2cos⁡3π8].
We have(2.10)ĉL,8=TSB_DCT,8⋅D4-1⋅cL,4=[1.41200001.387000001.306600001.17590000000-0.785700-0.541200-0.275900]⋅cL,4,ŝH,8=TSB_DST,8⋅D4-1⋅cH,4=[00000.25490-0.1056000.50-0.20710.300700.7259000.541201.30660.450001.0864001.20710-0.51.28150-0.53080]⋅cH,4.
Similarly, the 4-point DCT computations of cL,4 and cH,4 can be obtained by(2.11)cL,4=[TSB_DCT,4TSB_DCT,4]4×4⋅M4⋅xL=TSB_DCT,4⋅xLL︸ĉLL,4+TSB_DST,4⋅xLH︸ŝLH,4,(2.12)cH,4=[TSB_DCT,4TSB_DCT,4]4×4⋅M4⋅xH=TSB_DCT,4⋅xHL︸ĉHL,4+TSB_DST,4⋅xHH︸ŝHH,4,
where xLL=[xLL[0]xLL[1]]T, xLH=[xLH[0]xLH[1]]T, xHL=[xHL[0]xHL[1]]T, xHH=[xHH[0]xHH[1]]T, and
(2.13)xLL[n]=12{xL[2n]+xL[2n+1]},(2.14)xLH[n]=12{xL[2n]-xL[2n+1]},(2.15)xHL[n]=12{xH[2n]+xH[2n+1]},(2.16)xHH[n]=12{xH[2n]-xH[2n+1]}
for n=0,1.The 4-point distributed matrixM4, can be defined as(2.17)M4=[0.50.500000.50.50.5-0.500000.5-0.5].
Let cLL,2, cLH,2, cHL,2, and cHH,2 be the 2-point DCT of xLL, xLH, xHL, and xHH, respectively, which can be computed by using the following 2-point transformation matrix, D2:(2.18)D2=12⋅[111-1].
We have
(2.19)ĉLL,4=TSB_DCT,4⋅xLL=TSB_DCT,4⋅D2-1⋅cLL,2=[1.4142001.3066000-0.5412]⋅cLL,2,(2.20)ĉHL,4=TSB_DCT,4⋅xHL=TSB_DCT,4⋅D2-1⋅cHL,2=[1.4142001.3066000-0.5412]⋅cHL,2,(2.21)ŝLH,4=TSB_DST,4⋅xLH=TSB_DST,4⋅D2-1⋅cLH,2=[000.5412001.41421.30660]⋅cLH,2,(2.22)ŝHH,4=TSB_DST,4⋅xHH=TSB_DST,4⋅D2-1⋅cHH,2=[000.5412001.41421.30660]⋅cHH,2.
For the 2-point DCT computations of cLL,2, cLH,2, cHL,2, and cHH,2, let
(2.23)xLLL[n]=12{xLL[2n]+xLL[2n+1]},(2.24)xLLH[n]=12{xLL[2n]-xLL[2n+1]},(2.25)xLHL[n]=12{xLH[2n]+xLH[2n+1]},(2.26)xLHH[n]=12{xLH[2n]-xLH[2n+1]},(2.27)xHLL[n]=12{xHL[2n]+xHL[2n+1]},(2.28)xHLH[n]=12{xHL[2n]-xHL[2n+1]},(2.29)xHHL[n]=12{xHH[2n]+xHH[2n+1]},(2.30)xHHH[n]=12{xHH[2n]-xHH[2n+1]},
where n=0, we then have
(2.31)cLL,2=[TSB_DCT,2TSB_DCT,2]2×2⋅M2⋅xLL=TSB_DCT,2⋅xLLL︸ĉLLL,2+TSB_DST,2⋅xLLH︸ŝLLH,2,(2.32)cLH,2=[TSB_DCT,2TSB_DCT,2]2×2⋅M2⋅xLH=TSB_DCT,2⋅xLHL︸ĉLHL,2+TSB_DST,2⋅xLHH︸ŝLHH,2,(2.33)cHL,2=[TSB_DCT,2TSB_DCT,2]2×2⋅M2⋅xHL=TSB_DCT,2⋅xHLL︸ĉHLL,2+TSB_DST,2⋅xHLH︸ŝHLH,2,(2.34)cHH,2=[TSB_DCT,22TSB_DCT,2]2×2⋅M2⋅xHH=TSB_DCT,2⋅xHHL︸ĉHHL,2+TSB_DST,2⋅xHHH︸ŝHHH,2.M2 is a 2-point matrix defined as(2.35)M2=[0.50.50.5-0.5].
Finally, according to equations (2.6)~(2.33) together with (2.4), we have(2.36)c8=K̃⋅K̂⋅M8⋅M̂8⋅M̃8⋅x8,
where (2.37)K̃=[(TSB_DCT,8⋅D4-1)8×4(TSB_DCT,8⋅D4-1)8×4]8×8,K̂=[(TSB_DCT,4⋅D2-1)4×2(TSB_DCT,4⋅D2-1)4×204×204×204×204×2(TSB_DCT,4⋅D2-1)4×2(TSB_DCT,4⋅D2-1)4×2]8×8.
The following matrix, M̂8, can derived from (2.12)~(2.15).(2.38)M̂8=[0.50.5000000000.50.500000.5-0.5000000000.5-0.5000000000.50.5000000000.50.500000.5-0.5000000000.5-0.5].
Similarly, the following matrix, M̃8, can be derived from (2.21)~(2.28)(2.39)M̃8=[0.50.50000000.5-0.5000000000.50.50000000.5-0.5000000000.50.50000000.5-0.5000000000.50.50000000.5-0.5].
The decomposition matrix R8 can be defined as(2.40)R8=8⋅M8⋅M̂8⋅M̃8=[111111111111-1-1-1-111-1-111-1-111-1-1-1-1111-11-11-11-11-11-1-11-111-1-111-1-111-1-11-111-1]
and the coefficient matrix F8 can be defined as (2.41)F8=[1000000000.90610.375300.180200-0.07470000.923900.3827000-0.31820.768200.2126000.51330000001000.2126-0.513300.3182000.7682000-0.382700.9239000-0.1802-0.074710.906100-0.3753].
According to (2.34), (2.38), and (2.39), we have(2.42)c8=24⋅F8⋅R8⋅x8.
The coefficient matrix F8 can be represented by the reordered coefficient matrix F̂8, prepermutation matrix T̂8 and post-permutation matrix T̃8, and can be written as(2.43)F8=T̂8⋅F̂8⋅T̃8,
where the matrices F̂8, T̂8, and T̃8 can be defined as(2.44)F̂8=[1000000001000000000.92380.3826000000-0.38260.9238000000000.90610.18020.3753-0.07460000-0.18020.9061-0.0746-0.375300000.21260.3181-0.51320.76820000-0.31810.21260.76820.5132],T̂8=[1000000000001000001000000000000101000000000000100001000000000100],T̃8=[1000000000000010000100000000010001000000000010000010000000000001].
The reordered coefficient matrix F̂8 can be represented as(2.45)F̂8=[I0000A0000BC00DE].
The computation of sub-coefficient matrix A can be written as(2.46)[y1y2]=A⋅[x1x2]=[ab-ba]⋅[x1x2],
where a=0.9239 and b=0.3827. The above can be rewritten as [20](2.47)y1=(b-a)⋅x2+a⋅(x1+x2),(2.48)y2=-(a+b)⋅x1+a⋅(x1+x2).
Thus, the number of multiplications can be reduced to 3 for matrix A; this technique can also be applied to matrices B, C, D, and E. As a result, the total number of multiplications of the subband-based 8-point DCT is only 15.Based on (2.40) and (2.41), the corresponding subband-based IDCT can be obtained by(2.49)x8=22⋅R8-1⋅T̃8-1⋅F̂8-1⋅T̂8-1⋅c8,
where R8-1 is the inverse decomposition matrix. As the decomposition matrix R8 is orthonormal, R8-1 can be derived from the transportation of R8(2.50)R8-1=R8T=[111111111111-1-1-1-111-1-111-1-111-1-1-1-1111-11-11-11-11-11-1-11-111-1-111-1-111-1-11-111-1].F̂8-1 is the inverse reordered coefficient matrix, T̂8-1 is the inverse prepermutation matrix and T̃8-1 is the inverse post-permutation matrix. Since the reordered coefficient matrix F̂8, prepermutation matrix T̂8 and post-permutation matrix T̃8 are all orthonormal, three matrices F̂8-1, T̂8-1, and T̃8-1 can be written as
(2.51)F̂8-1=F̂8T=[1000000001000000000.9238-0.38260000000.38260.9238000000000.9061-0.18020.2126-0.318100000.18020.90610.31810.212600000.3753-0.0746-0.51320.76820000-0.0746-0.37530.76820.5132],(2.52)T̂8-1=T̂8T=[1000000000001000001000000000001001000000000000010000010000010000],(2.53)T̃8-1=T̃8T=[1000000000001000000000100010000000000100000100000100000000000001].
The inverse reordered coefficient matrix F̂8-1 can be represented as (2.54)F̂8-1=[I0000AT0000BTDT00CTET].
As a result, the total number of multiplications of the subband based 8-point IDCT is only 15.


## 3. The Unified Subband-Basedn-Point DCT/IDCT Algorithm

The subband-based DCT algorithm [22] can be unified for n-point DCT/IDCT due to the inherent regular pattern. For an n-point signal, xn, the unified subband-based discrete cosine transform can be defined as(3.1)cn=nn⋅T̂n⋅F̂n⋅T̃n⋅Rn⋅xn,
where n={2m|m=3,4,5,…}, Rn is the decomposition matrix, F̂n is the reordered coefficient matrix, T̂n is the pre-permutation matrix, and T̃n is the post-permutation matrix. The unified decomposition matrix Rn can be written as(3.2)Rn=n⋅Mn,n×n⋅[Mn/2,(n/2)×(n/2)0(n/2)×(n/2)0(n/2)×(n/2)Mn/2,(n/2)×(n/2)]n×n⋅[Mn/4,(n/4)×(n/4)0(n/4)×(n/4)0(n/4)×(n/4)0(n/4)×(n/4)0(n/4)×(n/4)Mn/4,(n/4)×(n/4)0(n/4)×(n/4)0(n/4)×(n/4)0(n/4)×(n/4)0(n/4)×(n/4)Mn/4,[(n/4)×(n/4)]0(n/4)×(n/4)0(n/4)×(n/4)0(n/4)×(n/4)0(n/4)×(n/4)Mn/4,(n/4)×(n/4)]n×n⋅⋯⋅[M2,2×202×2⋯02×202×2M2,2×2⋮⋮⋱02×202×2⋯02×2M2,2×2]n×n,
where the basic 2×2 matrix, M2, consists of two submatrices, M2,1×2′ and M2,1×2′′(3.3)M2=[0.50.50.5-0.5]=[M2,1×2′M2,1×2′′].
As noted, M4 can be represented by the sub-matrices of M2, or sub-matrices, M4,2×4′ and M4,2×4′′ as follows:(3.4)M4=[0.50.500000.50.50.5-0.500000.5-0.5]=[M′2,1×201×201×2M2,1×2′M′′2,1×201×201×2M2,1×2′′]=[M4,2×4′M4,2×4′′].According to (3.1) and (3.2), the unified distributed matrix Mn can be derived as(3.5)Mn=[Mn/2,(n/4)×(n/2)′0(n/4)×(n/2)0(n/4)×(n/2)Mn/2,(n/4)×(n/2)′Mn/2,(n/4)×(n/2)′′0(n/4)×(n/2)0(n/4)×(n/2)Mn/2,(n/4)×(n/2)′′]=[Mn,(n/2)×n′Mn,(n/2)×n′′].
According to (2.2) and (2.40), we have (3.6)Fn=Dn⋅Rn-1.
The 4-point reordered coefficient matrix F̂4 can be derived as(3.7)F̂4,4×4=[10000100000.92390.382700-0.38270.9239]=[F̂2,2×202×202×2F̂4,2×2′].
According to (3.5), the 8-point reordered coefficient matrix F̂8 can be derived as(3.8)F̂8,8×8=[F̂2,2×202×202×402×2F̂4,2×2′02×404×204×2F̂8,4×4′]=[F̂4,4×404×404×4F̂8,4×4′].
Hence, the unified reordered coefficient matrix can be written as(3.9)F̂n,n×n=[F̂2,2×202×2⋯02×n02×2F̂4,2×2′⋮⋮⋱0(n/2)×n0n×2⋯0n×(n/2)F̂n,(n/2)×(n/2)′]=[F̂n/2,(n/2)×(n/2)0n/2,(n/2)×(n/2)0n/2,(n/2)×(n/2)F̂n,(n/2)×(n/2)′].
The 4-point pre-permutation matrix T̂4 and post-permutation matrix T̃4 can be written as
(3.10)T̂4=[1000001001000001]=[T̂41,4×1T̂42,4×1T̂43,4×1T̂44,4×1],T̃4=[1000001000010100]=[T̃41,4×1T̃42,4×1T̃43,4×1T̃44,4×1].
According to (2.50), (2.51), (3.8), and (3.9), the 8-point pre- and post-permutation matrices can be written as (3.11)T̂8=[T̂41,4×104×1T̂42,4×104×1T̂43,4×104×1T̂44,4×104×104×1T̂81,4×1′04×1T̂82,4×1′04×1T̂83,4×1′04×1T̂84,4×1′],T̃8=[T̃41,4×104×1T̃42,4×104×1T̃43,4×104×1T̃44,4×104×104×1T̃81,4×1′04×1T̃82,4×1′04×1T̃83,4×1′04×1T̃84,4×1′].
Hence, the unified pre- and post-permutation matrices can be represented as(3.12)T̂n=[T̂(n/2)1,A0AT̂(n/2)2,A0AT̂(n/2)3,A0AT̂(n/2)4,A0A0AT̂n1,A′0AT̂n2,A′0AT̂n3,A′0AT̂n4,A′],T̃n=[T̃(n/2)1,A0AT̃(n/2)2,A0AT̃(n/2)3,A0AT̃(n/2)4,A0A0(n/2)×(n/8)T̃(n/2)1,A′0AT̃(n/2)2,A′0AT̃(n/2)3,A′0AT̃(n/2)4,A′].where 𝒜 denotes (n/2)×(n/8).According to (2.47) and (2.53), the unified subband-based IDCT can be obtained.(3.13)xn=nn⋅Rn-1⋅T̃n-1⋅F̂n-1⋅T̂n-1⋅cn,
where Rn-1 is the inverse decomposition matrix, F̂n-1 is the inverse coefficient matrix, T̂n-1 is the inverse pre-transportation matrix,  and T̃n-1 is the inverse post-transportation matrix. Note that the decomposition matrix, reordered coefficient matrix, pre- and post-permutation matrices are all orthonormal. Hence, we have(3.14)Rn-1=RnT,F̂n-1=F̂nT,T̂n-1=T̂nT,T̃n-1=T̃nT.


## 4. Analysis of Computation Complexity and System Performance

Based on the 8-point subband-based DCT and IDCT algorithm, the data flow of parallel-pipelined processing for 8-point DCT and IDCT are described as follows. The data flow of the subband-based 8-point DCT with six pipelined stages is shown in Figure1. In which, y8=R8·x8, z8=T̂8·F̂8·T̃8·y8 and c8=(2/4)·z8, the matrix-vector multiplication of R8·x8 in the first stage, takes one simple-addition time for each element of y8. The preshuffle performs the prepermutation matrix T̃8 operation in the second stage. The matrix-vector multiplication is used to compute F̂8·y8 in the third and fourth stages. In the fifth stage, the postshuffle is used for the post-permutation matrix T̂8. The final stage is to compute (2/4)·z8 by using simple shift operation with the Booth recoded algorithm.Figure 1
Data flow of the subband-based 8-point DCT with six pipelined stages.Similarly, Figure2 shows the data flow of the subband-based 8-point IDCT with seven pipelined stages.Figure 2
Data flow of the subband-based 8-point IDCT with seven pipelined stages.In which,u8=(2/4)·c8, w8=F̂8-1·T̂8-1·u8, v8=T̃8-1·w8, and x8=R8-1·v8, it performs u8=(2/4)·c8 by using shift operation with the Booth recoded algorithm in the first stage. The preshuffle performs the pre-permutation matrix T̂8-1 operation in the second stage. The matrix-vector multiplication is used to compute w8 in the third and fourth stages. In the fifth stage, the post-shuffle performs the post-permutation matrix T̃8-1. The sixth and seventh stages are to perform R8-1·v8 with simple addition. Both of the subband-based DCT and IDCT algorithms need one multiplication operation with parallel-pipelined processing, in comparison to [23] using linear array, which needs five multiplication operations.Recall that the DCT of a signal,xn, can be represented as cn=(n/n)·T̂n·F̂n·T̃n·Rn·xn. The multiplication time of the unified subband-based algorithm can be derived as(4.1)TM=3⋅(40+41+42+⋯+4(log2n)-2)=4(log2n)-1-1,
where n={2m∣m=3,4,5,…}.The log plot of the subband-based DCT computations versus the number of DCT points is shown in Figure3.Figure 3
Log plot of the number of multiplications versus the number of DCT points.The multiplication time of the unified subband-based DCT with single processor can be derived as follows [23]:(4.2)TM=40+41+42+⋯+4(log2n)-2=(4(log2n)-1-1)3.The left side of Figures4(a), 4(b), 4(c), 4(d), and 4(e) show the original 512×512 Lena, Baboon, Barbara, Peppers, and Boat images, respectively. The reconstructed Lena, Baboon, Barbara, Peppers and boat image shown in the right side of Figures 4(a), 4(b), 4(c), 4(d), and 4(e), respectively, are obtained by using the proposed subband based 8-point DCT/IDCT algorithm with 32-bit fixed-point operands; the peak signal-to-noise ratios (PSNRs) of Lena, Baboon, Barbara, Peppers, and Boat images are 149.67 dB, 142.12 dB, 143.08 dB, 143.36 dB, and 140.79 dB, respectively.The original image (left side) and the reconstructed image (right side).
(a)
Lena(b)
Baboon(c)
Barbara(d)
Peppers(e)
BoatThe PSNR curves of Lena, Baboon, Barbara, Peppers, and Boat images obtained by using the conventional 8-point DCT and the proposed subband-based 8-point DCT at various word lengths are shown in Figure5. Figures 6(a), 6(b), 6(c), 6(d), and 6(e) show the PSNR curves of Lena, Baboon, Barbara, Peppers, and Boat images obtained by using the conventional DCT and the proposed subband-based DCT with 32-bit operand at various DCT points. As one can see, the subband-based DCT is preferable.The PSNR curves of (a) Lena, (b) Baboon, (c) Barbara, (d) Peppers, and (e) Boat images obtained by using the conventional 8-point DCT and the proposed subband-based 8-point DCT at various word lengths.
(a)
Lena(b)
Baboon(c)
Barbara(d)
Peppers(e)
BoatPSNR comparisons of  (a) Lena, (b) Baboon, (c) Barbara, (d) Peppers, and (e) Boat images using the conventional DCT and the subband-based DCT with 32-bit operand at various DCT points.
(a)
Lena(b)
Baboon(c)
Barbara(d)
Peppers(e)
Boat


## 5. FPGA Implementation of the Reconfigurable Linear-Array DCT/IDCT Processor

The reconfigurable architecture of the fast 8-, 16-, 32- and 64-point DCT and IDCT processors based on the subband-based 8-point DCT is proposed in this section.


### 5.1. The Proposed 8-Point DCT/IDCT Processor

According to the data flow of the subband-based 8-point DCT with six pipelined stages (Figure1), the architecture of the proposed 8-point DCT processor is shown in Figure 7. In which, the adder array (AA) with three CSA(4,2)s performing the matrix-vector multiplication of R̂8·x8 is shown in Figure 8. Figure 9 shows the multiplier array (MA) performing three types of operation, which are needed to compute the subcoefficient matrix computation of F̂8. The control signals of swap and inv determine the types of operation. The functions determined by swap and inv are shown in Table 1. Figure 10 shows the hardwired shifters used for performing (2/4)·z8 by the Booth recoded algorithm [23]. Figure 11 shows the proposed 8-point IDCT processor with seven pipelined stages. In which, the fast adder arrays, shuffle, multiplier array, CLA, and hardwired shifters for DCT architecture can also be used for performing IDCT. The latch array for retiming the input data is shown in Figure 12.Table 1
The functions determined byswap and inv.
Type 1Type 2Type 3swap010inv001Figure 7
The proposed 8-point DCT Processor with six pipelined stages.Figure 8
Adder array (AA) for the matrix-vector multiplication ofR8·x8.Figure 9
Multiplier array (MA) for computing the subcoefficient matrix ofF̂8.Figure 10
The proposed hardwired shifters used for performing(2/4)·z8.Figure 11
The proposed 8-point IDCT processor with seven pipelined stages.Figure 12
The latch array for retiming the input data.The hardware complexity of the proposed subband-based IDCT architecture is the same as that of the proposed subband-based DCT architecture. Figure13 shows the proposed integrated 8-point DCT/IDCT processor.Figure 13
The integrated 8-point DCT/IDCT processor.


### 5.2. The Proposed Reconfigurable DCT/IDCT Processor

According to the integrated 8-point DCT/IDCT processor (Figure13), the proposed reconfigurable 8-, 16-, 32-, and 64-point DCT/IDCT processor is shown in Figure 14. In which, the integrated adder array (IAA) for the fast computation of 8-, 16-, 32-, and 64-point DCT/IDCT is shown in Figure 15. The modified hardwired shifter (MHS) for multiplication by n/n (where n=8,16,32,64) using the Booth recoded algorithm is shown in Figure 16.Figure 14
The reconfigurable 8-, 16-, 32-, and 64-point DCT/IDCT processor.Figure 15
Integrated adder array (IAA) for 8-, 16-, 32-, and 64-point DCT/IDCT processor.Figure 16
The modified hardwired shifter (MHS) for multiplication byn/n (where n=8,16,32,64) using the Booth recoded algorithm.In order to improve the computation efficiency, the number of multiplier arrays should be increased. The log plot of computation cycles versus number of multiplier arrays is shown in Figure17.Figure 17
Log plot of number of multiplier array versus computation cycles.


### 5.3. FPGA Implementation of the Reconfigurable 2D DCT/IDCT Processor

TheN×N DCT is defined as [29](5.1)Z[u,v]=2⋅α[u]⋅α[v]N⋅∑m=0N-1∑n=0N-1x[m,n]⋅cos⁡(2m+12Nuπ)⋅cos⁡(2n+12Nvπ),0≤u,v≤N-1,
where  α[k]=1/2 for k=0, and α[k]=1 for k>0. It can be rewritten as(5.2)Z[u,v]=2Nα[u]∑m=0N-1[2Nα[v]∑n=0N-1x(m,n)⋅cos⁡(2n+12Nvπ)]⋅cos⁡(2m+12Nuπ),0≤u,v≤N-1.
Thus, the separable 2-D DCT can be obtained by using 1-D DCT as follows:(5.3)2-DDCT(X)=1-DDCT((1-DDCT(X))T).
Similarly, the separable 2-D IDCT can be obtained by using 1-D IDCT as follows:(5.4)2-DIDCT(Z)=1-DIDCT((1-DIDCT(Z))T).
As a result, the architecture of 2D DCT/IDCT can be implemented by using two successive 1D DCT/IDCT processors with only one transpose memory [29]. The proposed architecture of 2-D DCT and IDCT is shown in Figure 18. In which, the control signals provided by the finite state machine (FSM) controller are used to manage the data flow and the operation timing for the DCT/IDCT and transpose memory; the transpose memory allows simultaneous read and write operations between the two processors while performing matrix transposition. The data read and written timing diagram for 8×8 DCT/IDCT system is shown in Figure 19. In comparison with the conventional two transpose memories based 2-D DCT/IDCT architectures, the proposed architecture utilizes only one transpose memory.Figure 18
The proposed architecture of 2-D DCT and IDCT (FSM: finite state machine).Figure 19
Data read and written timing diagram for8×8 DCT/IDCT system.The platform for architecture development and verification has been designed as well as implemented in order to evaluate the development cost. The architecture has been implemented on the Xilinx FPGA emulation board [30]. The Xilinx Spartan-3 FPGA has been integrated with the microcontroller (MCU) and I/O interface circuit (USB 2.0) to form the architecture development and verification platform. Figure 20 depicts block diagram and circuit board of the architecture development and evaluation platform. In which, the microcontroller reads data and commands from PC and writes the results back to PC by USB 2.0; the Xilinx Spartan-3 FPGA implements the proposed 2-D DCT/IDCT processor. The hardware code written in Verilog is for PC with the ModelSim simulation tool [31] and Xilinx ISE smart compiler [32]. It is noted that the throughput can be improved by using the proposed architecture while the computation accuracy is the same as that obtained by using the conventional one with the same word length. Thus, the proposed programmable DCT/IDCT architecture is able to improve the power consumption and computation speed significantly. The proposed processor for 8-, 16-, 32-, and 64-point DCT/IDCT is an extension of the 8-point DCT/IDCT processor. Moreover, the reusable intellectual property (IP) DCT/IDCT core has also been implemented in Verilog for the hardware realization. All the control signals are internally generated on chip. The proposed DCT/IDCT processor provides both high throughput and low gate count.Figure 20
Block diagram and circuit board of the architecture development and verification platform.


## 5.1. The Proposed 8-Point DCT/IDCT Processor

According to the data flow of the subband-based 8-point DCT with six pipelined stages (Figure1), the architecture of the proposed 8-point DCT processor is shown in Figure 7. In which, the adder array (AA) with three CSA(4,2)s performing the matrix-vector multiplication of R̂8·x8 is shown in Figure 8. Figure 9 shows the multiplier array (MA) performing three types of operation, which are needed to compute the subcoefficient matrix computation of F̂8. The control signals of swap and inv determine the types of operation. The functions determined by swap and inv are shown in Table 1. Figure 10 shows the hardwired shifters used for performing (2/4)·z8 by the Booth recoded algorithm [23]. Figure 11 shows the proposed 8-point IDCT processor with seven pipelined stages. In which, the fast adder arrays, shuffle, multiplier array, CLA, and hardwired shifters for DCT architecture can also be used for performing IDCT. The latch array for retiming the input data is shown in Figure 12.Table 1
The functions determined byswap and inv.
Type 1Type 2Type 3swap010inv001Figure 7
The proposed 8-point DCT Processor with six pipelined stages.Figure 8
Adder array (AA) for the matrix-vector multiplication ofR8·x8.Figure 9
Multiplier array (MA) for computing the subcoefficient matrix ofF̂8.Figure 10
The proposed hardwired shifters used for performing(2/4)·z8.Figure 11
The proposed 8-point IDCT processor with seven pipelined stages.Figure 12
The latch array for retiming the input data.The hardware complexity of the proposed subband-based IDCT architecture is the same as that of the proposed subband-based DCT architecture. Figure13 shows the proposed integrated 8-point DCT/IDCT processor.Figure 13
The integrated 8-point DCT/IDCT processor.


## 5.2. The Proposed Reconfigurable DCT/IDCT Processor

According to the integrated 8-point DCT/IDCT processor (Figure13), the proposed reconfigurable 8-, 16-, 32-, and 64-point DCT/IDCT processor is shown in Figure 14. In which, the integrated adder array (IAA) for the fast computation of 8-, 16-, 32-, and 64-point DCT/IDCT is shown in Figure 15. The modified hardwired shifter (MHS) for multiplication by n/n (where n=8,16,32,64) using the Booth recoded algorithm is shown in Figure 16.Figure 14
The reconfigurable 8-, 16-, 32-, and 64-point DCT/IDCT processor.Figure 15
Integrated adder array (IAA) for 8-, 16-, 32-, and 64-point DCT/IDCT processor.Figure 16
The modified hardwired shifter (MHS) for multiplication byn/n (where n=8,16,32,64) using the Booth recoded algorithm.In order to improve the computation efficiency, the number of multiplier arrays should be increased. The log plot of computation cycles versus number of multiplier arrays is shown in Figure17.Figure 17
Log plot of number of multiplier array versus computation cycles.


## 5.3. FPGA Implementation of the Reconfigurable 2D DCT/IDCT Processor

TheN×N DCT is defined as [29](5.1)Z[u,v]=2⋅α[u]⋅α[v]N⋅∑m=0N-1∑n=0N-1x[m,n]⋅cos⁡(2m+12Nuπ)⋅cos⁡(2n+12Nvπ),0≤u,v≤N-1,
where  α[k]=1/2 for k=0, and α[k]=1 for k>0. It can be rewritten as(5.2)Z[u,v]=2Nα[u]∑m=0N-1[2Nα[v]∑n=0N-1x(m,n)⋅cos⁡(2n+12Nvπ)]⋅cos⁡(2m+12Nuπ),0≤u,v≤N-1.
Thus, the separable 2-D DCT can be obtained by using 1-D DCT as follows:(5.3)2-DDCT(X)=1-DDCT((1-DDCT(X))T).
Similarly, the separable 2-D IDCT can be obtained by using 1-D IDCT as follows:(5.4)2-DIDCT(Z)=1-DIDCT((1-DIDCT(Z))T).
As a result, the architecture of 2D DCT/IDCT can be implemented by using two successive 1D DCT/IDCT processors with only one transpose memory [29]. The proposed architecture of 2-D DCT and IDCT is shown in Figure 18. In which, the control signals provided by the finite state machine (FSM) controller are used to manage the data flow and the operation timing for the DCT/IDCT and transpose memory; the transpose memory allows simultaneous read and write operations between the two processors while performing matrix transposition. The data read and written timing diagram for 8×8 DCT/IDCT system is shown in Figure 19. In comparison with the conventional two transpose memories based 2-D DCT/IDCT architectures, the proposed architecture utilizes only one transpose memory.Figure 18
The proposed architecture of 2-D DCT and IDCT (FSM: finite state machine).Figure 19
Data read and written timing diagram for8×8 DCT/IDCT system.The platform for architecture development and verification has been designed as well as implemented in order to evaluate the development cost. The architecture has been implemented on the Xilinx FPGA emulation board [30]. The Xilinx Spartan-3 FPGA has been integrated with the microcontroller (MCU) and I/O interface circuit (USB 2.0) to form the architecture development and verification platform. Figure 20 depicts block diagram and circuit board of the architecture development and evaluation platform. In which, the microcontroller reads data and commands from PC and writes the results back to PC by USB 2.0; the Xilinx Spartan-3 FPGA implements the proposed 2-D DCT/IDCT processor. The hardware code written in Verilog is for PC with the ModelSim simulation tool [31] and Xilinx ISE smart compiler [32]. It is noted that the throughput can be improved by using the proposed architecture while the computation accuracy is the same as that obtained by using the conventional one with the same word length. Thus, the proposed programmable DCT/IDCT architecture is able to improve the power consumption and computation speed significantly. The proposed processor for 8-, 16-, 32-, and 64-point DCT/IDCT is an extension of the 8-point DCT/IDCT processor. Moreover, the reusable intellectual property (IP) DCT/IDCT core has also been implemented in Verilog for the hardware realization. All the control signals are internally generated on chip. The proposed DCT/IDCT processor provides both high throughput and low gate count.Figure 20
Block diagram and circuit board of the architecture development and verification platform.


## 6. Conclusion

With the advantages of the subband decomposition of a signal, a high-efficiency algorithm with pipelined stages has been proposed for fast DCT/IDCT computations. It is noted that the proposed DCT/IDCT algorithm not only simplifies computation complexity but also improves system performance. The PSNR and system complexity of the proposed algorithm is better than those of the previous algorithms [33–36]. Table 2 shows comparisons between the proposed algorithm and architecture and other commonly used algorithms and architectures [24–28]. Thus, the proposed subband-based DCT/IDCT algorithm is suitable for the real-time signal processing applications. The proposed DCT/IDCT processor provides both high throughput and low gate count and has been applied to various images with great satisfactions.Table 2
Comparisons between the proposed algorithm and architecture and other commonly used algorithms and architectures.
DCT/IDCTJeong et al. [24]Gong et al. [25]Dimitrov et al. [26]Alam et al. [27]Hsiao and Tseng [28]This Work 2011Computation complexityO(N-log2N+1)O(N-log2N+1)O(N-log2N+1)O(N-log2N+1)O(logN)O(1)Hardware complexityO(2N)O(2N)O(2N)O(2N)O(NlogN)O(4log2N-1-13)PipelinabilitynononononogoodScalabilitypoorpoorpoorpoorgoodbetter



---

*Source: 912194-2011-08-28.xml*