臺灣博碩士論文加值系統

摘要
數位影像及視訊在日常生活中的應用可以說是日漸普及。而其中，離散餘弦轉換是最廣泛被利用在數位影像及視訊壓縮編碼標準中的轉換編碼法。通常一個視訊編碼器完成視訊編碼工作需要大量的計算量，而離散餘弦轉換以及反離散餘弦轉換更是其中兩個計算密集度非常高的單元。
在這篇論文中，對於一個二維離散餘弦轉換的實現，我們採用了分散式算術架構的構想來排除對於乘法器的使用需求。而我們更進一步的改進了原本在分散式算術架構中的ROM-Accumulator架構，設法去解決ROM在硬體實現中的因難和它所須花費的硬體代價。在我們的修改型ROM-Accumulator架構中，對於原本用來產生運算中所須固定餘弦函數之係數的硬體ROM，在我們的架構中可以輕易的採用一些簡單邏輯閘所組成邏輯區塊來取代。整個二維離散餘弦轉換架構的實現，我們利用行-列分解的方式，來對二維的影像資料分別作行向量方向及列向量方向的一維離散餘弦轉換，如此的架構方式一般來說較為規則且適合硬體的實現。而對每個一維離散餘弦轉換的實現，我們提出一個奇-偶頻率分離並配合二次及三次收斂分解的演算法，如此可以進一步的減少一維離散餘弦轉換的計算複雜度。最後，針對行-列分解架構中所須的轉置記憶體，我們也提出一個新的單一方向轉置記憶體架構。利用這個新的轉置記憶體架構，對每筆資料我們可以比傳統轉置記憶體節省一半的轉置時間。我們所提出的整個二維離散餘弦轉換架構完全適合管線化操作，並具有規則化及低硬體成本的特性，非常適合硬體實現。

ABSTRACT
Several digital image and video applications are becoming more popular in our everyday lives. The discrete cosine transform (DCT) is at present the most widely used transformation in the image and video compression algorithm. Image and video encoder/decoder (codec) require huge amounts of computation since the DCT and the inverse DCT (IDCT) are two of the components that are very computationally intensive in video encoder.
In this thesis, we propose the multiplier-less distributed arithmetic (DA) architecture with the modified ROM-Accumulator (RAC) structures for the implementation of two-dimensional (2-D) DCT without any ROM area. In our modified RAC structures, the cosine function coefficients are generated by logical block which only need some logic gates instead of ROM area. We also use the row-column decomposition (RCD) method for computing the 2-D DCT so that our proposed structure has more regularity for hardware implementation. And, in the algorithm for computing each row-wise and each column-wise 1-D DCT, we use the even-odd frequency decomposition method with the second and third recursive iterations to further reduce the computational complexity. Final, we propose a new transposition memory architecture. In our proposed transposition memory architecture, half of the transposition time in the traditional architecture can be saved. The proposed two-dimensional DCT architecture is fully pipelining, keeps the regularity of the structure suitable for hardware implementation and has low hardware cost.

CONTENTS
ABSTRACT (IN CHINESE)…………………………………………………i
ABSTRACT (IN ENGLISH)……………………………………………………ii
ACKNOWLEDGMENT(IN CHINESE)………………………………………iv
CONTENTS………………………………………………………………………v
LIST OF ABBREVIATIONS…………………………………………………viii
LIST OF FIGURES……………………………………………………………ix
LIST OF TABLE……………………………………………………………………xiii
CHAPTER 1 INTRODUCTION……………………………………………1
1-1 Motivation……………………………………………………………1
1-2 Introduction to Distributed Arithmetic Architecture …………………4
1-2-1 Memory Reduction Technique with Offset Binary
Coding Method…………………………………………………7
1-2-2 Memory Reduction Technique with Partial Sum
Method……………………………………………….…….…8
1-3 Thesis Organizaions…………………………………….……………9

CHAPTER 2 DISCRETE COSINE TRANSFORM……………………….10
2-1 Theory………………………………………………………………....10
2-2 DCT in One Dimension………………………………………………....12
2-3 DCT in Two Dimension…………………………………………………16
2-4 Recursive Method for Simplify the DCT Matrix……………………….17
CHAPTER 3 THE DISTRIBUTED ARITHMETIC ARCHITECTURE
WITH MODIFIED RAC STRUCTURE FOR DCT
IMPLEMENTATION……………………………………….24
3-1 Even-Odd Frequency Decomposition with Recursive Iteration
Algorithm…………………………………………………………….24
3-2 The Distributed Arithmetic Architecture with Modified RAC
Structure For DCT Implementation………………………………….28
3-2-1 The Modified RAC Structure for Output Y(1), Y(3), Y(5)
and Y(7)………………………………………………………32
3-2-2 The Modified RAC Structure for Output Y(2) and Y(6)…..…...42
3-2-3 The Modified RAC Structure for Output Y(0) and Y(4)…..…...47

CHAPTER 4 HARDWARE REALIZAION FOR THE PROPOSED
TOW-DIMENSIONAL DCT ARCHITECTURE…………….51
4-1 Architecture Design for the Proposed 1-D DCT……………………….51
4-1-1 Datapath………………………………………………………51
4-1-2 Pre-Computing Part of the Proposed 1-D DCT …………………53
4-1-3 Kernel Part of the Proposed 1-D DCT Architecture…………….54
4-2 Architecture Design for Proposed Transposition Memory…………….57

CHAPTER 5 SIMULATION RESULTS AND ERROR ANALYSIS……….63
5-1 Simulation Results…………………………………………………….….63
5-2 Error Analysis……………………………………………………….70
CHAPTER 6 CONCLUSIONS AND FUTURE STUDIES…………………73
6-1 Conclusions……………………………………………………………73
6-2 Future Studies………………………………………….……………..74

REFERENCES…………………………………………………………………75
VITA…………………………………………………………………………….77

REFERENCES[1]N, Ahmed, T. Natarajan, and K. R. Rao, “Discrete cosine transform,” IEEE Trans. on Computers, vol. C-23, pp. 90-93, Jan. 1974.[2]N. Cho and S. Lee “Fast algorithm and implementation of 2D discrete cosine transform,” IEEE Trans. Circuits and Systems, vol. 38, pp. 297-305, Mar. 1991.[3]E. Feig and S. Winograd, “Fast algorithms for the discrete cosine transform,” IEEE Trans. Signal Processing, vol. 40, pp. 2174-2193, Sept. 1992.[4]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.[5]H. S. Hou, “A fast recursive algorithm for computing the discrete cosine transform,” IEEE Trans. Acoust., Speech, Signal Processing, vol. ASSp-35, no. 10, pp. 1455-1461, Oct. 1987.[6]S. I. Uramoto, Y. Inoue, A. Takabatake, J. Takeda, Y. Yamashita, H. Terane, and M. Yoshimoto, “A 100-MHz 2-D discrete cosine transform core processor,” IEEE J. Solid-State Circuits, vol. 27, pp. 492-499, Apr. 1992.[7]K. Kim, S. Jang, S. Kwon, and K. Son, “An improvement of VLSI architecture for 2-dimensional discrete cosine transform and its inverse,” Pro. SPIE, vol. 2772, pp. 1017-1026, 1996.[8]D. Stawecki and W. Li, “DCT/IDCT processor design for high data rate image coding,” IEEE Trans. Circuits and System, vol. 2, pp. 135-146, June 1992.[9]S. Yu and E. E. Swartzlander Jr., “A scaled DCT architecture with the CORDIC algorithm,” IEEE Trans. on Signal Processing, vol. 50, no. 1, pp. 160-167.[10]G. Kiryukhin and M. Celenk, “Implementation of 2-D DCT on XC4000 Series FPGA using DFT-base DSFG and DA architectures,” in Proc. 2001 IEEE Int. Conf. Image Processing, Oct. 2001, pp. 302-305.[11]S. Yu and E. E. Swartzlander Jr., “DCT Implementation with distributed arithmetic,” IEEE Trans. Computers, vol. 50, no. 9, pp. 985-991, Sept. 2001.[12]S. A. White, “Application of distributed arithmetic to digital signal procession: A tutorial review,” IEEE ASSP Magazine, vol. 6, pp. 4-19, July 1989.