# An Efficient VLSI Linear Array for DCT/IDCT Using Subband Decomposition Algorithm

Authors: Tze-Yun Sung; Yaw-Shih Shieh; Hsi-Chin Hsin
Journal: Mathematical Problems in Engineering
 (2010)

---

## 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, a novel lineararray of DCT and IDCT is derived from the data flow of subband decompositions representing the factorized coefficient matrices in the matrix formulation of the recursive algorithm. For increasing the throughput as well as decreasing the hardware cost, the input and output data are reordered. The proposed 8-point DCT/IDCT processor with four multipliers, simple adders, and less registers and ROM storing the immediate results and coefficients, respectively, has been implemented on FPGA (field programmable gate array) and SoC (system on chip). The linear-array DCT/IDCT processor with the computation complexityO(5N/8) and hardware complexity O(5N/8) is fully pipelined and scalable for variable-length DCT/IDCT computations.


---

## Body

## 1. Introduction

With rapid growth of modern communication applications and computer technologies, image compression and real-time computation of nonlinear time series continues to be in great demand. Discrete Cosine transform (DCT) is one of the major operations in various image/video compression standards [1] and nonlinear time series applications [2–8]. Though fast Fourier transform (FFT) can be used to implement DCT, it requires complex-valued computations; and moreover, N-point DCT by FFT contains O(log2N+1) stages. The conventional DCT architectures using distributed arithmetic involve complex hardware with a great number of registers [9–19]. Other commonly used DCT architectures with matrix formulation and distributed memory [20–27] are however not suited for VLSI implementation because the hardware complex is proportional to the length of DCT, which leads to the scalability problem of variable-length DCT computations. In this paper, we propose the novel linear-array architecture for scalable DCT/IDCT implementation.The remainder of this paper proceeds as follows. In Section2, we propose the fast DCT/IDCT computation based on subband decomposition algorithm. In Section 3, the reconfigurable FPGA-based and programmable SoC implementations with low hardware cost are proposed for the fast DCT/IDCT computation. The performance comparison with conclusions can be found in Section 4.


## 2. Proposed Fast DCT/IDCT Computation

For anN-point signal, x[n], the discrete cosine transform (DCT) [28] is defined as
(2.1)C[k]=α[k]∑n=0N-1x[n]cos[(2n+1)kπ2N],
where k=0,…,N-1,α[0]=1/N, and α[k]=2/N for k>0. Let xL[n] and xH[n] denote the low-frequency and high-frequency subband signals of x[n], respectively, which are defined as(2.2)xL[n]=12{x[2n]+x[2n+1]},xH[n]=12{x[2n]-x[2n+1]},
where n=0,1,2,…,(N/2)-1. The original signal x[n] can be obtained from xL[n] and xH[n] as follows:
(2.3)x[2n]=xL[n]+xH[n],x[2n+1]=xL[n]-xH[n].
As one can see, the DCT of x[n] can be rewritten as(2.4)C[k]=∑n=0(N/2)-1α[k]x[2n]cos((4n+1)kπ2N)+∑n=0(N/2)-1α[k]x[2n+1]cos((4n+3)kπ2N)=2cos(πk2N)∑n=0(N/2)-1α[k]xL[n]cos((2n+1)kπN)︸CL[k]+2sin(πk2N)∑n=0(N/2)-1α[k]xH[n]sin((2n+1)kπN)︸SH[k],
where CL[k] and SH[k] are the subband DCT and DST (discrete sine transform) of x[n], respectively.


### 2.1. Fast DCT Computation Based on Subband Decomposition Algorithm

Without loss of generality, the 8-point fast DCT based on subband decomposition algorithm is proposed for the widely used JPEG and MPEG-1/2 standards, which can be easily extended to variable-length DCT computations. The vector form of 8-point DCT can be written as(2.5)C8=[TSB_DCT,8TSB_DST,8]8×8·[xLxH]8×1,
where C8=[C[0]⋯C[7]]T, xL=[xL[0]⋯xL[3]]T, xH=[xH[0]⋯xH[3]]T, and TSB_DCT,8  and TSB_DST,8 denote the 8×4 matrices of subband DCT and subband DST, respectively, which can form orthonormal bases for the two orthogonal subspaces of R8. Notice that, due to the orthogonality between TSB_DCT,8 and TSB_DST,8, xL[n] and xH[n] can be obtained from C[k] as follows:
(2.6)xL[n]=∑n=0N-1α[k]cos(πk2N)C[k]cos((2n+1)kπN),xH[n]=∑n=0N-1α[k]sin(πk2N)C[k]sin((2n+1)kπN),
where n=0,1,2,…,N/2-1, and N=8.The proposed fast DCT algorithm is a subband decomposition-based multistage algorithm. Specifically, let(2.7)xLL[n]=12{xL[2n]+xL[2n+1]},xLH[n]=12{xL[2n]-xL[2n+1]},xHL[n]=12{xH[2n]+xH[2n+1]},xHH[n]=12{xH[2n]-xH[2n+1]},
where n=0,1. And let(2.8)xLLL[n]=12{xLL[2n]+xLL[2n+1]},xLLH[n]=12{xLL[2n]-xLL[2n+1]},xLHL[n]=12{xLH[2n]+xLH[2n+1]},xLHH[n]=12{xLH[2n]-xLH[2n+1]},xHLL[n]=12{xHL[2n]+xHL[2n+1]},xHLH[n]=12{xHL[2n]-xHL[2n+1]},xHHL[n]=12{xHH[2n]+xHH[2n+1]},xHHH[n]=12{xHH[2n]-xHH[2n+1]},
where n=0. Based on subband decompositions using (2.2), (2.7), and (2.8), data flow of computing the 2-point subband DCT: CLL,2 and subband DST: CLH,2 for the 8-point DCT is shown in Figure 1. As one can see, data flow of computing CHL,2 and CHH,2 can be obtained in a similar way, and therefore is not shown in Figure 1. All of the 2-point subband DCTs and DSTs are given by(2.9)CLL,2=[TSB_DCT,2TSB_DST,2]2×2·[xLLLxLLH]2×1=TSB_DCT,2·xLLL︸ĈLLL,2+TSB_DST,2·xLLH︸ŜLLH,2,CLH,2=[TSB_DCT,2TSB_DST,2]2×2·[xLHLxLHH]2×1=TSB_DCT,2·xLHL︸ĈLHL,2+TSB_DST,2·xLHH︸ŜLHH,2,CHL,2=[TSB_DCT,2TSB_DST,2]2×2·[xHLLxHLH]2×1=TSB_DCT,2·xHLL︸ĈHLL,2+TSB_DST,2·xHLH︸ŜHLH,2,CHH,2=[TSB_DCT,2TSB_DST,2]2×2·[xHHLxHHH]2×1=TSB_DCT,2·xHHL︸ĈHHL,2+TSB_DST,2·xHHH︸ŜHHH,2.
Thus, we have
(2.10)[CLL,2CLH,2CHL,2CHH,2]=R8·x8,
where x8=[x[0]⋯x[7]]T is the original signal, and(2.11)R8=28·[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].Figure 1
Data flow of computing the 2-point subband DCT:CLL,2 and subband DST: CLH,2 (for the 8-point DCT of the input signal: x8) based on subband decomposition.Similarly, we have the following:(2.12)CL,4=[TSB_DCT,4TSB_DST,4]4×4·[xLL,2xLH,2]4×1=TSB_DCT,4·xLL,2︸ĈLL,4+TSB_DST,4·xLH,2︸ŜLH,4,CH,4=[TSB_DCT,4TSB_DST,4]4×4·[xHL,2xHH,2]4×1=TSB_DCT,4·xHL,2︸ĈHL,4+TSB_DST,4·xHH,2︸ŜHH,4.
Figure 2 depicts the relationship between ĈLL,4 and CLL,2, which can be obtained by the following:(2.13)ĈLL,4=TSB_DCT,4·xLL,2,(2.14)CLL,2=T2·xLL,2,
where T2 is the 2×2 transform matrix of the conventional 2-point DCT. Hence, (2.13) can be rewritten as(2.15)ĈLL,4=TSB_DCT,4·T2-1·CLL,2=[1.4142001.3066000-0.5412]·CLL,2.
The relationship between ŜLH,4 and CLH,2 shown in Figure 3 is based on the following:(2.16)ŜLH,4=TSB_DST,4·xLH,2,CLH,2=T2·xLH,2.
Thus, we have(2.17)ŜLH,4=TSB_DST,4·T2-1·CLH,2=[000.5412001.41421.30660]·CLH,2.Figure 2
Data flow of computingĈLL,4 and CLL,2 based on subband decomposition.Figure 3
Data flow of computingCLH,2 and ŜLH,4 based on subband decomposition.Similarly, based on (2.5) and the following equations:(2.18)CL,4=T4·xL,4,CH,4=T4·xH,4,
where T4 is the 4×4 transform matrix of the conventional 4-point DCTs, we have(2.19)ĈL,8=TSB_DCT,8·xL,4=TSB_DCT,8·T4-1·CL,4=[1.41200001.387000001.306600001.17590000000-0.785700-0.541200-0.275900]·CL,4,(2.20)ĈH,8=TSB_DST,8·xH,4=TSB_DST,8·T4-1·CH,4=[00000.25490-0.1056000.50-0.20710.300700.7259000.541201.30660.450001.0864001.20710-0.51.28150-0.53080]·CH,4.
Figure 4 depicts data flow of computing CL,4 and CH,4 using 4-point subband DCT and DST. Figure 5 depicts data flow of computing ĈL,8 and CL,4 based on subband decomposition. Data flow of computing ŜH,8 and CH,4 based on subband decomposition is shown in Figure 6. Data flow of computing C8 using 8-point subband DCT and DST is shown in Figure 7. In other words, C8 can be obtained by(2.21)C8=ĈL,8+ŜH,8.
Base on (2.12), (2.15), (2.17), (2.19) and (2.20), we have(2.22)C8=F8·[CLL,2TCLH,2TCHL,2TCHH,2T]T,
where(2.23)F8=[K3K4]8×8·[[K1K2]4×400[K1K2]4×4]8×8,(2.24)K1=[1.4142001.3066000-0.5412],(2.25)K2=[000.5412001.41421.30660],(2.26)K3=[1.41200001.387000001.306600001.17590000000-0.785700-0.541200-0.275900],(2.27)K4=[00000.25490-0.1056000.50-0.20710.300700.7259000.541201.30660.450001.0864001.20710-0.51.28150-0.53080].
According to (2.24)–(2.27), we have(2.28)F8=[2000000001.81230.750700.360500-0.14930001.847800.7654000-0.63641.536400.4252001.02660000002000.4252-1.026600.6364001.5364000-0.765401.8478000-0.3605-0.149301.812300-0.7507].
Finally, the proposed 8-point DCT computation based on subband decomposition is as follows:(2.29)C8=F̂8·R8·x8,
where(2.30)F̂8=2·[1000000001000000000.92390.3827000000-0.38270.9239000000000.90620.37540.1802-0.07460000-0.1802-0.07460.9062-0.37540000-0.31820.76820.21260.513300000.2126-0.51330.31820.7682].
Figure 8 shows block diagram of the proposed DCT computation; one of the advantages is that R8 is orthogonal, and all of the submatrices of F̂8 are orthonormal.Figure 4
Data flow of computingCL,4 and CH,4 using 4-point subband DCT and DST.Figure 5
Data flow of computingĈL,8 and CL,4 based on subband decomposition.Figure 6
Data flow of computingŜH,8 and CH,4 based on subband decomposition.Figure 7
Data flow of computingC8 using 8-point subband DCT and DST.Figure 8
Block diagram of the proposed (8-point) fast DCT algorithm based on subband decomposition.


### 2.2. Fast IDCT Computation Based on Subband Decomposition Algorithm

According to (2.29), IDCT can be obtained by(2.31)x8=R8-1·F̂8-1·C8,
where(2.32)R8-1=82[111111111111-1-1-1-111-1-111-1-111-1-1-1-1111-11-11-11-11-11-1-11-111-1-1111-1-11-1-11-111-1],F̂8-1=12·[1000000001000000000.9239-0.38270000000.38270.9239000000000.9062-0.1802-0.31820.212600000.37540.37540.7682-0.513300000.18020.18020.21260.31820000-0.0746-0.07460.51330.7682].
As R8 is orthogonal and all of the submatrices of F̂8 are orthonormal, the inverse of R8 and F̂8 can be obtained easily. In addition, it takes only twenty multiplication operations for both DCT and IDCT.


## 2.1. Fast DCT Computation Based on Subband Decomposition Algorithm

Without loss of generality, the 8-point fast DCT based on subband decomposition algorithm is proposed for the widely used JPEG and MPEG-1/2 standards, which can be easily extended to variable-length DCT computations. The vector form of 8-point DCT can be written as(2.5)C8=[TSB_DCT,8TSB_DST,8]8×8·[xLxH]8×1,
where C8=[C[0]⋯C[7]]T, xL=[xL[0]⋯xL[3]]T, xH=[xH[0]⋯xH[3]]T, and TSB_DCT,8  and TSB_DST,8 denote the 8×4 matrices of subband DCT and subband DST, respectively, which can form orthonormal bases for the two orthogonal subspaces of R8. Notice that, due to the orthogonality between TSB_DCT,8 and TSB_DST,8, xL[n] and xH[n] can be obtained from C[k] as follows:
(2.6)xL[n]=∑n=0N-1α[k]cos(πk2N)C[k]cos((2n+1)kπN),xH[n]=∑n=0N-1α[k]sin(πk2N)C[k]sin((2n+1)kπN),
where n=0,1,2,…,N/2-1, and N=8.The proposed fast DCT algorithm is a subband decomposition-based multistage algorithm. Specifically, let(2.7)xLL[n]=12{xL[2n]+xL[2n+1]},xLH[n]=12{xL[2n]-xL[2n+1]},xHL[n]=12{xH[2n]+xH[2n+1]},xHH[n]=12{xH[2n]-xH[2n+1]},
where n=0,1. And let(2.8)xLLL[n]=12{xLL[2n]+xLL[2n+1]},xLLH[n]=12{xLL[2n]-xLL[2n+1]},xLHL[n]=12{xLH[2n]+xLH[2n+1]},xLHH[n]=12{xLH[2n]-xLH[2n+1]},xHLL[n]=12{xHL[2n]+xHL[2n+1]},xHLH[n]=12{xHL[2n]-xHL[2n+1]},xHHL[n]=12{xHH[2n]+xHH[2n+1]},xHHH[n]=12{xHH[2n]-xHH[2n+1]},
where n=0. Based on subband decompositions using (2.2), (2.7), and (2.8), data flow of computing the 2-point subband DCT: CLL,2 and subband DST: CLH,2 for the 8-point DCT is shown in Figure 1. As one can see, data flow of computing CHL,2 and CHH,2 can be obtained in a similar way, and therefore is not shown in Figure 1. All of the 2-point subband DCTs and DSTs are given by(2.9)CLL,2=[TSB_DCT,2TSB_DST,2]2×2·[xLLLxLLH]2×1=TSB_DCT,2·xLLL︸ĈLLL,2+TSB_DST,2·xLLH︸ŜLLH,2,CLH,2=[TSB_DCT,2TSB_DST,2]2×2·[xLHLxLHH]2×1=TSB_DCT,2·xLHL︸ĈLHL,2+TSB_DST,2·xLHH︸ŜLHH,2,CHL,2=[TSB_DCT,2TSB_DST,2]2×2·[xHLLxHLH]2×1=TSB_DCT,2·xHLL︸ĈHLL,2+TSB_DST,2·xHLH︸ŜHLH,2,CHH,2=[TSB_DCT,2TSB_DST,2]2×2·[xHHLxHHH]2×1=TSB_DCT,2·xHHL︸ĈHHL,2+TSB_DST,2·xHHH︸ŜHHH,2.
Thus, we have
(2.10)[CLL,2CLH,2CHL,2CHH,2]=R8·x8,
where x8=[x[0]⋯x[7]]T is the original signal, and(2.11)R8=28·[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].Figure 1
Data flow of computing the 2-point subband DCT:CLL,2 and subband DST: CLH,2 (for the 8-point DCT of the input signal: x8) based on subband decomposition.Similarly, we have the following:(2.12)CL,4=[TSB_DCT,4TSB_DST,4]4×4·[xLL,2xLH,2]4×1=TSB_DCT,4·xLL,2︸ĈLL,4+TSB_DST,4·xLH,2︸ŜLH,4,CH,4=[TSB_DCT,4TSB_DST,4]4×4·[xHL,2xHH,2]4×1=TSB_DCT,4·xHL,2︸ĈHL,4+TSB_DST,4·xHH,2︸ŜHH,4.
Figure 2 depicts the relationship between ĈLL,4 and CLL,2, which can be obtained by the following:(2.13)ĈLL,4=TSB_DCT,4·xLL,2,(2.14)CLL,2=T2·xLL,2,
where T2 is the 2×2 transform matrix of the conventional 2-point DCT. Hence, (2.13) can be rewritten as(2.15)ĈLL,4=TSB_DCT,4·T2-1·CLL,2=[1.4142001.3066000-0.5412]·CLL,2.
The relationship between ŜLH,4 and CLH,2 shown in Figure 3 is based on the following:(2.16)ŜLH,4=TSB_DST,4·xLH,2,CLH,2=T2·xLH,2.
Thus, we have(2.17)ŜLH,4=TSB_DST,4·T2-1·CLH,2=[000.5412001.41421.30660]·CLH,2.Figure 2
Data flow of computingĈLL,4 and CLL,2 based on subband decomposition.Figure 3
Data flow of computingCLH,2 and ŜLH,4 based on subband decomposition.Similarly, based on (2.5) and the following equations:(2.18)CL,4=T4·xL,4,CH,4=T4·xH,4,
where T4 is the 4×4 transform matrix of the conventional 4-point DCTs, we have(2.19)ĈL,8=TSB_DCT,8·xL,4=TSB_DCT,8·T4-1·CL,4=[1.41200001.387000001.306600001.17590000000-0.785700-0.541200-0.275900]·CL,4,(2.20)ĈH,8=TSB_DST,8·xH,4=TSB_DST,8·T4-1·CH,4=[00000.25490-0.1056000.50-0.20710.300700.7259000.541201.30660.450001.0864001.20710-0.51.28150-0.53080]·CH,4.
Figure 4 depicts data flow of computing CL,4 and CH,4 using 4-point subband DCT and DST. Figure 5 depicts data flow of computing ĈL,8 and CL,4 based on subband decomposition. Data flow of computing ŜH,8 and CH,4 based on subband decomposition is shown in Figure 6. Data flow of computing C8 using 8-point subband DCT and DST is shown in Figure 7. In other words, C8 can be obtained by(2.21)C8=ĈL,8+ŜH,8.
Base on (2.12), (2.15), (2.17), (2.19) and (2.20), we have(2.22)C8=F8·[CLL,2TCLH,2TCHL,2TCHH,2T]T,
where(2.23)F8=[K3K4]8×8·[[K1K2]4×400[K1K2]4×4]8×8,(2.24)K1=[1.4142001.3066000-0.5412],(2.25)K2=[000.5412001.41421.30660],(2.26)K3=[1.41200001.387000001.306600001.17590000000-0.785700-0.541200-0.275900],(2.27)K4=[00000.25490-0.1056000.50-0.20710.300700.7259000.541201.30660.450001.0864001.20710-0.51.28150-0.53080].
According to (2.24)–(2.27), we have(2.28)F8=[2000000001.81230.750700.360500-0.14930001.847800.7654000-0.63641.536400.4252001.02660000002000.4252-1.026600.6364001.5364000-0.765401.8478000-0.3605-0.149301.812300-0.7507].
Finally, the proposed 8-point DCT computation based on subband decomposition is as follows:(2.29)C8=F̂8·R8·x8,
where(2.30)F̂8=2·[1000000001000000000.92390.3827000000-0.38270.9239000000000.90620.37540.1802-0.07460000-0.1802-0.07460.9062-0.37540000-0.31820.76820.21260.513300000.2126-0.51330.31820.7682].
Figure 8 shows block diagram of the proposed DCT computation; one of the advantages is that R8 is orthogonal, and all of the submatrices of F̂8 are orthonormal.Figure 4
Data flow of computingCL,4 and CH,4 using 4-point subband DCT and DST.Figure 5
Data flow of computingĈL,8 and CL,4 based on subband decomposition.Figure 6
Data flow of computingŜH,8 and CH,4 based on subband decomposition.Figure 7
Data flow of computingC8 using 8-point subband DCT and DST.Figure 8
Block diagram of the proposed (8-point) fast DCT algorithm based on subband decomposition.


## 2.2. Fast IDCT Computation Based on Subband Decomposition Algorithm

According to (2.29), IDCT can be obtained by(2.31)x8=R8-1·F̂8-1·C8,
where(2.32)R8-1=82[111111111111-1-1-1-111-1-111-1-111-1-1-1-1111-11-11-11-11-11-1-11-111-1-1111-1-11-1-11-111-1],F̂8-1=12·[1000000001000000000.9239-0.38270000000.38270.9239000000000.9062-0.1802-0.31820.212600000.37540.37540.7682-0.513300000.18020.18020.21260.31820000-0.0746-0.07460.51330.7682].
As R8 is orthogonal and all of the submatrices of F̂8 are orthonormal, the inverse of R8 and F̂8 can be obtained easily. In addition, it takes only twenty multiplication operations for both DCT and IDCT.


## 3. VLSI Implementation of an Efficient Linear-Array DCT/IDCT Processor

Based on the proposed approach to fast DCT computation shown in Figure8, an efficient architecture for implementing the fast DCT/IDCT processor is thus presented in this section. Recall that the DCT of a signal, x8, can be efficiently obtained by C8=F̂8·R8·x8. Let y8=R8·x8, then we have C8=F̂8·y8. Figure 9 shows the matrix-vector multiplication of R8·x8, in which six CSA(3,2)s (carry-save-adder (3,2)) and one CSA (carry-save-adder) [29, 30] are utilized, and therefore four simple-addition time and one CSA computation time is required to compute each element of y8. Figures 10 and 11 show the Multiplier array (MA) consisted of four multipliers and the CSA array (CA) consisted of eight CSAs, respectively, which are used to compute the matrix-vector computation of F̂8·y8; thus, only one multiplication time with one CSA computation time is needed to compute each element of C8, that is, the DCT coefficient. Table 3 depicts data flow of the proposed fast DCT processor with pipelined linear-array architecture [31]. As a result, only five multiplication cycles with five addition cycles are needed to compute 8-point DCT. In general, for N-point DCT, the computation time and hardware complexity of the proposed fast DCT processor are O(5N/8) and O(N/2), respectively.Figure 9
Fast adder (FA) for the matrix-vector multiplication ofR8·x8. (Note: The width of buses is 32-bit.)Figure 10
Multiplier array (MA) consisted of four multipliers. (Note: The width of buses is 32-bit.)Figure 11
CSA array (CA) consisted of eight CSAs. (Note: The width of buses is 32-bit.)Table4 shows data flow of the proposed fast IDCT algorithm [31],  where C8 is the DCT of an 8-point signal x8; z8=F̂8-1·C8, and x8=R8-1·z8. Figure 12 shows the so-called full CSA(4,2) (FCSA(4,2)) consisted of two CSA(3,2) and one CSA for the computation of z8 [29, 30]. It is noted that the CSA array consisted of eight CSAs shown in Figure 11 can also be used for the computation of x8. As shown in Table 4, only five multiplication cycles with three addition cycles are needed to compute 8-point IDCT. As one can see, the computation time and hardware complexity of the proposed fast IDCT architecture are the same as that of the proposed fast DCT architecture. In addition, only 16-word RAM/registers and 10-word ROM are required to store the intermediate results and constants, respectively; and the latency time is only 5-multiplication-cycle.Figure 12
Full CSA(4,2) consisted of two CSA(3,2) and one CSA.Figure13 shows system block diagram of the proposed fast DCT/IDCT architecture. The platform for architecture development and verification has been designed as well as implemented in order to evaluate the development cost. Figure 14 depicts block diagram of the platform, in which the 8051 microcontroller reads data from PC via DMA channel and writes the result back to PC by USB 2.0 bus; the Xilinx XC2V6000 FPGA chip implements the proposed DCT processor [32]. The architecture development and verification board shown in Figure 15 are to verify and evaluate the proposed DCT/IDCT architecture. Moreover, the reusable intellectual property (IP) DCT/IDCT core has also been implemented in Matlab for functional simulations. The hardware code written in Verilog is running on a workstation with the ModelSim simulation tool and Xilinx ISE smart compiler. In addition, the FPGA platform shown in Figure 14 is to verify and evaluate the proposed DCT architecture. 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.Figure 13
System block diagram of the proposed DCT/IDCT architecture (FA: fast-adder-array, MA: Multiplier array, FCSA(4,2): full CSA(4,2), and CA: CSA- array).Figure 14
Block diagram of the architecture development and verification platform for the proposed DCT/IDCT processor.Figure 15
The architecture development and verification board.The SoC is synthesized by the TSMC 0.18μm 1P6M CMOS cell libraries [33]. The physical circuit is synthesized by the Astro tool. The circuit is evaluated by DRC, LVS, and PVS [34]. Figure 16 shows the cell-based design flow. The layout view of the 8-point DCT/IDCT processor with 32-bit operand is shown in Figure 17. The core areas are obtained by the Synopsys design analyzer. The power consumptions are obtained by the PrimePower.The reported core size of the implemented the proposed processor is 1520×1520μm2 and the power dissipation is 102.2 mW at 1.8 V with clock rate of 1 GHz. Thus, the proposed programmable DCT/IDCT architecture is able to improve the power consumption and computation speed significantly. All the control signals are internally generated on-chip. The proposed DCT/IDCT processor provides both high-throughput and low gate count.Figure 16
Cell-based design flow.Figure 17
The layout view of the proposed 8-point DCT/IDCT processor with 32-bit operand.The proposed reconfigurable DCT/IDCT processor used to compute8/16/32/64-point DCT/IDCT on FPGA are composed mainly of the 8-point DCT/IDCT core; the computation complexity using a single 8-point DCT/IDCT core is O(5N/8) for extending N-point DCT/IDCT computation. Note that the transform matrices used for the proposed linear array with 8-point DCT core can be extended to a variety of different sizes. Thus, the proposed architecture is highly scalable.The linear-array architecture with use of hardware resources has been proposed for trade offs of performance, chip area and power consumption. As a result, it has the advantage of balancing the need for power saving with computation speed.


## 4. Conclusion

By taking advantage of subband decomposition, a high-efficiency architecture with pipelined structures is proposed for fast DCT/IDCT computation. Specifically, the proposed DCT/IDCT architecture not only improves throughput by more than two times that of the conventional architectures [9–11, 15–19], but also saves memory space significantly [1, 9–22]. Table 1 shows comparisons between the proposed architecture and the conventional architectures [1, 9–14] (with dual memory banks), and [15–19]. Table 2 shows comparisons with other commonly used architectures [1, 12–14, 20–24]. For 8×8 DCT, the algorithm proposed by Feig requires 54 multiplications and 462 additions [27]; the proposed method requires 25 multiplications and 100 additions. Thus, the performance of this work is superior to that of the Feig algorithm. In addition, the proposed fast DCT/IDCT architecture is highly regular, scalable, and flexible. The DCT/IDCT processor designed by using the portable and reusable Verilog is a reusable IP, which can be implemented in various processes; combined with efficient use of hardware resources for tradeoffs of performance, area and power consumption; and therefore is much suited to the JPEG and MPEG-1/2 applications.Table 1
Comparisons between the proposed architecture and the conventional architectures.
8-point DCT/IDCTThe conventional architecturesThe conventional pipelined architecturesThe proposed high- efficient architectureThe single-processor architectures [9–11]The parallel architectures with single memory-bank [15–19]The pipelined architectures with single memory-bank [1, 9–14]This work(Sung, Shieh and Hsin, 2010)Processors185 (CORDIC)—Real multipliers21604Real adders3181826RAM (Registers)64646416ROM66610Hardware complexityO(1)O(N-log2N+1)O(N-log2N)O(N/2)Computation complexityO(N2)O(2N)O(N)O(5N/8)Latency641685PipelinabilitynonoyesyesScalabilitypoorpoorgoodbetterPower consumptionpoorpoorgoodbetterTable 2
Comparisons of the proposed architecture and other commonly used architectures.
8-pointLee et al. [20]Chang and Wang [21]Hsiao and Shiue [22]Hsiao and Tseng [23]Hou  [24]Sung [1, 9–14]This workDCT/IDCTDCT/IDCTDCT/IDCTDCTDCT/IDCTDCT/IDCTDCT/IDCTDCT/IDCTReal multipliers2864————4CORDIC processors————35—Real adders13488910141826Complex multipliers——33——Delay elements (Words)256114—171———Memory (Words)~384~200~370——7026Hardware complexityO(NlogN)O(N2)O(logN)O(logN)O(logN)O(N-logN)O(N/2)Computation complexityO(logN)O(N)O(NlogN)O(NlogN)O(NlogN)O(N)O(5N/8)PipelinabilitynonononoyesyesyesScalabilitypoorpoorgoodgoodgoodgoodbetterTable 3
Data flow of the proposed fast DCT processor with pipelined linear-array architecture (Add.-cycle: addition-cycle and  Mul.-cycle: multiplication-cycle).
ProcessorFAMACAAdd.-cycle_1y[0]—C[0]Add.-cycle_2y[1]—C[1]Add.-cycle_3y[2]——Mul.-cycle_1y[3]y[2]·0.9239, y[2]·(-0.3827)—y[3]·0.3827, y[3]·(0.9239)Add.-cycle_4y[4]—C[2], C[3]Mul.-cycle_2y[5]y[4]·0.9062, y[4]·(-0.1802), y[4]·(-0.3182), y[4]·0.2126—Mul.-cycle_3y[6]y[5]·0.3754, y[5]·(-0.0746), y[5]·0.7682, y[5]·0.5133—Mul.-cycle_4y[7]y[6]·0.1802, y[6]·0.9062, y[6]·0.2126, y[6]·0.3182—Mul.-cycle_5—y[7]·(-0.0746), y[7]·(-0.3754), y[7]·0.5133, y[7]·0.7682—Add.-cycle_5—C[4], C[5], C[6], C[7]Table 4
Data flow of the proposed fast IDCT processor with pipelined linear-array architecture (Add.-cycle: addition-cycle and Mul.-cycle: multiplication-cycle).
ProcessorMAFCSA(4,2)CAMul.-cycle_1C[2]·0.9239, C[3]·(-0.3827)C[2]·0.3827, C[3]·0.92393z[0], z[1]—Mul.-cycle_2C[4]·0.9062, C[5]·(-0.1802), C[6]·(-0.3182), C[7]·0.2126z[2], z[3]C_0+C_1=C_01Mul.-cycle_3C[4]·0.3754, C[5]·0.3754, C[6]·0.7682, C[7]·(-0.5133)z[4]C_01+C_2=C_02Mul.-cycle_4C[4]·(-0.3182), C[5]·0.7682, C[6]·0.2126, C[7]·0.5144z[5]C_02+C_3=C_03Mul.-cycle_5C[4]·0.2126, C[5]·(-0.5133), C[6]·0.3182, C[7]·0.7682z[6]C_03+C_4=C_04Add.-cycle_1—z[7]C_04+C_5=C_05Add.-cycle_2——C_05+C_6=C_06Add.-cycle_3——C_06+C_7=C_07x[0], x[1],  x[2], x[3], x[4], x[5], x[6],  x[7]



---

*Source: 185398-2010-05-23.xml*