An efficient VLSI linear array for DCT/IDCT using subband decomposition algorithm.(Research Article)(Report)

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(log 2N + 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 Section 2, 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 an N-point signal, x[n], the discrete cosine transform (DCT)[28] is defined as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2.1)

where k = 0, ..., N - 1, [alpha][0] = 1/[square root of N], and [alpha][k] = [square root of 2/N] for k> 0. Let [x.sub.L][n] and [x.sub.H][n] denote the low-frequency and high-frequency subband signals of x[n], respectively, which are defined as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2.2)

where n = 0, 1, 2, ..., (N/2)-1. The original signal x[n] can be obtained from [x.sub.L][n] and [x.sub.H] [n] as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2.3)

As one can see, the DCT of x[n] can be rewritten as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2.4)

where [C.sub.L][k] and [S.sub.H][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

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2.5)

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] denote the 8 x 4 matrices of subband DCT and subband DST, respectively, which can form orthonormal bases for the two orthogonal subspaces of [R.sup.8]. Notice that, due to the orthogonality between [T.sub.SB_DCT,8] and [T.sub.SB_DST/8], [x.sub.L][n] and [x.sub.H][n] can be obtained from C[k] as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2.6)

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

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2.7)

[FIGURE 1 OMITTED]

where n = 0, 1. And let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2.8)

where n = 0. Based on subband decompositions using (2.2), (2.7), and (2.8), data flow of computing the 2-point subband DCT: [C.sub.LL/2] and subband DST: [C.sub.LH/2] for the 8-point DCT is shown in Figure 1. As one can see, data flow of computing [C.sub.HL/2] and [C.sub.HH/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

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2.9)

Thus, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2.10)

where [x.sub.8] = [[x[0] ... x[7]].sup.T] is the original signal, and

[MATHEMATICAL EXPRESSION NOT …