臺灣博碩士論文加值系統

　　本論文主旨在有效率的實現影像系統當中的離散餘弦轉換。其中包含了兩個部分。在第一個部分當中，我們提出了一個不限長度的定係數離散轉換遞迴架構。經過規則的前置處理後，此架構可用無限脈衝響應濾波器(IIR)來實現。和先前的定係數架構相比，此架構只需要其一半的遞迴圈數並且能夠達到較佳的精確度。此架構可適用於多種的離散轉換，諸如：分頻合成濾波轉換(subband synthesis filtering)、改良型離散餘弦反轉換(IMDCT)以及各種的離散餘弦轉換(DCTs)。在第二部分當中，我們為H.264標準所訂定大小為4×4的轉換設計了一個高輸出率的硬體架構。此架構比傳統行列分解(row-column decomposition)的方式能夠達到更高的輸出率但卻只需要較小的面積來實現。此架構利用TSMC 0.35�慆的製程技術合成，其合成的結果顯示，在時脈速度為100 MHz的情況下，所提出的多功能轉換架構能夠達到800 M samples/sec的處理速度。

　　This thesis focuses on the efficient implementation of the transform coding in video coding systems. It consists of two parts. In the first part, we propose a unified fixed-coefficient recursive structure for computing the general length discrete transforms. After regular preprocessing, the general discrete transforms are realized in a second-order infinite-impulse response (IIR) filter. The proposed recursive structure only requires half the recursive cycles and achieves more accurate results than the existing ones. The proposed algorithm can be applied to many popular transforms, such as subband synthesis filtering, inverse modified discrete cosine transform (IMDCT) and all discrete cosine transform (DCT) types. In the second part, high throughput hardware architectures for fast computation of the 4×4 transforms suggested in H.264 advanced video coders (AVC) are proposed. The proposed architectures could provide higher throughput rate and realize in a smaller chip area than the conventional row-column approaches. The proposed architectures are synthesized with TSMC 0.35 �慆 technology. The synthesized multiple transform architecture could process 800 M samples/sec at 100 MHz for all three transforms.

Table of Contents i
Acknowledgement iii
Abstract v
Figure Captions vi
Table Captions viii
1 Introduction 1
1.1 Motivation 1
1.2 Organization for the Thesis 3
2 Basic Concepts for Video Coding and Discrete Cosine Transform 5
2.1 Basic Concepts for Video Coding 5
2.2 The Hybrid DPCM/DCT Video Coding System 8
2.3 Review of the DCT 11
2.4 Classification of the DCT Algorithms 17
3 Unified Selectable Fixed-Coefficient Recursive Structures for Computing DCT, IMDCT and Subband Synthesis Filtering 18
3.1 The Family of the DCTs 19
3.2 Proposed Fixed-Coefficient Structure 20
3.3 Selection of Filter Coefficients 27
3.4 Comparisons and Results 32
3.4 Summary 35
4 High Throughput 2-D Transform Architectures for H.264 Advanced Video Coders 36
4.1 Transform Coding in H.264 37
4.2 Proposed 4×4 Transform Architectures 41
4.2.1 4×4 Forward Transform 41
4.2.2 4×4 Inverse Transform 43
4.2.3 4×4 Hadamard Transform 45
4.3 Implementation and Discussion 46
4.4 Verification 49
4.4.1 Verification Environment 49
4.4.2 RAM-base Interface Connection 50
4.4.3 Simulations 51
4.5 Summary 55
5 Conclusions and Future Work 56
5.1 Conclusions 56
5.2 Future Work 57
References 59
Publications 62

[1] A. V. Oppenheim and R. W. Schafer, Discrete-Time Signal Processing. Englewood Cliffs, NJ: Prentice-Hall, 1989.

[2] G. Goertzel, “An algorithm for the evaluation of finite trigonometric series,” Amer. Math. Monthly, vol. 65, pp. 34-35, Jan. 1958.

[3] L. P. Chau and W. C. Siu, “Recursive algorithm for the discrete cosine transform with general length,” Electron. Lett., vol. 30, pp. 197-198, Feb. 1994.

[4] Z. Wang, G. A. Jullien and W. C. Miller, “Recursive algorithms for the forward and inverse discrete cosine transform with arbitrary length,” IEEE Signal Processing Lett., vol. 1, pp. 101-102, July 1994.

[5] Y. H. Chan, L. P. Chau, and W. C. Siu, “Efficient implementation of discrete cosine transform using recursive filter structure,” IEEE Trans. Circuits Syst. Video Technol., vol. 4, pp. 550-552, Dec. 1994.

[6] J. L. Wang, C. B. Wu, B. D. Liu, and J. F. Yang, “Implementation of the discrete cosine transform and its inverse by recursive structures,” in Proc. IEEE SiPS, Oct. 1999, pp. 120-130.

[7] J. F. Yang and C. P. Fan, “Compact recursive structures for discrete cosine transform,” IEEE Trans. Circuits Syst. II, vol. 47, pp. 314-321, Apr. 2000.

[8] J. F. Yang and C. P. Fan, “Recursive discrete cosine transforms with selectable fixed-coefficient filters,” IEEE Trans. Circuits Syst. II, vol. 46, pp. 211-216, Feb.
1999.

[9] C. H. Chen, B. D. Liu and J. F. Yang, “Recursive architectures for realizing modified discrete cosine transform and its inverse,” IEEE Trans. Circuits Syst. II, vol. 50, pp. 38-45, Jan. 2003.

[10] I. E. G. Richardson, H.264 and MPEG-4 video compression: Video Coding for Next Generation Multimedia. Chichester, UK: John Wiley & Sons, 2003.

[11] Draft ITU-T Recommendation and Final Draft International Standard of Joint Video Specification (ITU-T Rec. H.264 and ISO/IEC 14496-10 AVC), 2003.

[12] H. S. Malvar, A. Hallapuro, M. Karczewicz, and L. Kerofsky, “Low-complexity transform and quantization in H.264/AVC,” IEEE Trans. Circuits Systs. Video Technol., vol. 13, pp. 598-603, July 2003.

[13] A. Hallapuro, M. Karczewicz, and H. S. Malvar, “Low complexity transform and quantization,” in Joint Video Team (JVT) of ISO/IEC MPEG and ITU-T VCEG, Jan. 2002, Docs. JVT-B038 and JVT-039.

[14] A. Hallapuro and M. Karczewicz, “Low complexity (I)DCT,” in Joint Video Team (JVT) of ISO/IEC MPEG and ITU-T VCEG, Sept. 2001, Docs. VCEV-N43.

[15] H. S. Malvar, “Low-complexity length-4 transform and quantization with 16-bit arithmetic,” in ITU-T SG16, Sept. 2001, Docs. VCEG-N44.

[16] G. Bjontegaard, “Calculation of average PSNR differences between RD curves,” in Joint Video Team (JVT) of ISO/IEC MPEG and ITU-T VCEG, Mar. 2001, Docs. VCEG-M33.

[17] I. E. G. Richardson, Video CODEC Design: Developing Image and Video Compression Systems. Chichester, UK: John Wiley & Sons, 2003.

[18] K. R. Rao and P. Yip, Discrete Cosine Transform: Algorithms, Advantages, Applications. Boston, MA: Academic Press, 1990.

[19] V. Bhaskaran and K. Konstantinides, Image and Video Compression Standards: Algorithms and Architectures. Boston, MA: Kluwer Academic, 1997.

[20] R. C. Gonzalez and R. E. Woods, Digital Image Processing. Upper Saddle River, NJ: Prentice Hall, 2002.

[21] K. Sayood, Introduction to Data Compression. San Francisco, CA: Morgan Kaufmann Publishers, 2000.

[22] S. Wolter, D. Birreck, and R. laur, “Classification for 2D-DCTs and a new architecture with distributed arithmetic,” IEEE Trans. Circuits Syst., vol. 4, pp. 2204-2207, June 1991.

[23] B. G. LEE, “A new algorithm to compute the discrete cosine transform,” IEEE Trans. Acoust. Speech Signal Processing, vol. ASSP-32, no. 6, pp. 1243-1245, Dec. 1984.

[24] P. Duhamel and C. Guillemot, “Polynomial transform computation of the 2-D DCT,” in Proc. IEEE ICASSP, Apr. 1990, pp. 1515-1518.

[25] K. Konstantinides, “Fast subband filtering in MPEG audio coding,” IEEE Signal Processing, vol. 1, pp. 26-28, Feb. 1994.

[26] R. X. Yin and W. C. Siu, “A new fast algorithm for computing prime-length DCT through cyclic convolutions,” Signal Processing, vol. 81, pp. 895-906, May 2001.

[27] J. F. Yang and F. C. Chen, “Recursive discrete Fourier transform with unified IIR filter structures,” Signal Processing, vol. 82, pp. 31-41, Sept. 2002.

[28] D. Y. Chan, J. F. Yang and S. Y. Chen, “Regular implementation algorithms of time domain aliasing cancellation,” in Proc. IEE Vision, Image, Signal Processing, Dec. 1996, pp. 387-392.

[29] M. F. Aburdene, J. Zheng, and R. J. Kozick, “Computation of discrete cosine transform using Clenshaw’s recurrence formula,” IEEE Signal Processing Lett., vol. 2, Aug. 1995.

[30] IEEE standard specifications for the implementations of 8×8 inverse discrete cosine transform, IEEE Std. 1180-1990, Mar. 1991.

[31] T. C. Wang, Y. W. Huang, H. C. Fang, and L. G. Chen, “Parallel 4x4 2D transform and inverse transform architecture for MPEG-4 AVC/H.264,” in Proc. IEEE ISCAS, May 2003, pp. 800-803.