臺灣博碩士論文加值系統

數位壓縮技術一直備受人們關注，而二維離散餘弦及反向餘弦轉換(2-D DCT/IDCT)廣泛地被認為是運用於影像壓縮上最有效的壓縮技術；雖有許多新的演算法不斷被提出，然而大部分的架構應用會花費相當大的成本。本文以短時間上市和低成本為導向，除了將設計IP化，並在晶片面積和速度的考量下，使用 VLSI 實現兩用型的 DCT/IDCT 單元。
雖然 2-D DCT/IDCT 大致分為行列分解演算法(Row-Column Decomposition)及非行列分解演算法(Not Row-Column Decomposition)，而且非行列分解演算法會比較有效率，但是硬體實現的複雜度相對提高，故一般採用行列分解演算法。所以本文設計的架構也是採用行列分解演算法，但是為了獲得較高的處理吞吐量，設計使用兩套 1-D DCT/IDCT 電路處理單元做平行計算，並利用改進後的移位求和來實現乘法邏輯，以平衡各個乘法路徑，並節省硬體資源，再加上管線(Pipeline)的概念，使本設計可以連續處理輸入資料。
最後，透過功能(Function)與時間(Timing)驗證，確保設計符合要求，並在後端(Back-End)設計中執行擺放和繞線(Placement and Routing)的動作，完成晶片佈局(Layout)，並且後續做實體驗證(Physical Verification)，如：LVS、DRC、ERC…等，確保晶片可以下線(Tape-Out)。

The digit compress technology is concerned by people extremely. The 2-D DCT and IDCT are widely used and the most effective compression technology in image compressing. There are also a lot of new algorithms being proposed all the time, but most structure application will spend too much cost. This paper takes the short time to market and low cost as the direction in design. We make the design to be an DCT/IDCT IP under the consideration of the area and speed of the chip.
Though 2-D DCT/IDCT roughly are divided into row-column decomposition (RCD) and not row-column decomposition (NRCD). NRCD is more efficient than RCD, but it is relatively too complex for hardware to be implemented. So the design structure of this thesis also uses RCD as usual. And in order to get higher throughput, it uses two 1-D DCT/IDCT circuit units to do parallel operation. It also uses the improved shift-and-add multiplication logic to balance each multiplication path and save hardware resource. Combined with the concept of pipeline, the design can deal with input data continually.
Finally, we can ensure the design reaching the requirements with the function and timing checking. Then we enforce placement and routing steps of back-end flow to finish the physical layout and make physical verifications to guarantee that the chip can be tape-outed.

誌謝 i
摘要 ii
ABSTRACT iii
目錄 iv
圖目錄 vii
第一章 緒論 1
1.1前言 1
1.2研究動機 4
1.3論文大綱 5
第二章 DCT/IDCT介紹 6
2.1 DCT/IDCT描述 6
2.2 相關研究 8
2.2.1非行列分解(Not Row-Column Decomposition)演算法 8
2.2.2 行列分解(Row-Column Decomposition)演算法 10
2.3 DCT/IDCT的圖像處理 11
2.4 DCT/IDCT在視訊壓縮系統的應用 14
第三章 DCT/IDCT演算法及結構設計 17
3.1 一維DCT/IDCT 17
3.2二維DCT/IDCT 18
3.3結構設計 20
3.3.1總體結構設計 21
3.3.2一維DCT/IDCT結構設計 22
3.3.3管線(Pipeline)的觀念 24
3.4使用Matlab模擬2-D DCT/IDCT 25
第四章 DCT/IDCT VLSI的邏輯設計 28
4.1 乘法邏輯設計 28
4.1.1 乘法器介紹 29
4.1.2 利用陣列乘法器實現乘法邏輯 32
4.1.3 乘法邏輯時序考慮 36
4.2 交叉選擇邏輯設計 37
4.3 累加器邏輯設計 40
4.4 轉置邏輯 42
4.5 控制邏輯 45
4.6 DCT/IDCT 轉換核心輸入輸出邏輯 47
第五章 合成與各層級模擬驗證 50
5.1 RTL 級功能模擬 50
5.1.1 對 DCT 轉換的邏輯功能模擬 50
5.1.2 對 IDCT 轉換的邏輯功能模擬 52
5.1.3 對控制信號的邏輯功能模擬 54
5.2 合成 54
5.3 閘級模擬驗證 57
5.4 即時性分析 58
5.5 計算精密度分析 58
第六章 自動佈局繞線 60
6.1 流程 60
6.2 資料準備 61
6.2.1 RAM_16X80 Astro Library 61
6.2.2 相關資料 62
6.3 建立DCT/IDCT Macro 63
6.3.1 建立步驟 64
6.3.2 佈局圖與實體面積分析 67
第七章 結論 69
參考文獻 71

[1]“H.261,” ITU-T Recommendation H.261, Mar.1994.
[2]G.K. Wallace, “The JPEG still picture compression standard,” IEEE Trans. on Consumer Electronics, vol. 38, no. 1, pp. 30-44, Feb. 1992.
[3]“Coding of moving pictures and associated audio information,” Committee Draft of Standard ISO 13818-2: ISO/MPEG, Feb. 2002.
[4]R. Hopkins, “Digital terrestrial HDTV for North America：the grand alliance HDTV system,” IEEE Trans. on Consumer Electronics, vol. 40, no. 3, pp. 185-198, Aug. 1994.
[5]N. Ahmed, T. Natarajan and K. R. Rao, “Discrete cosine transform,” IEEE Trans. on Communication, vol. COM-23, pp. 90-93, Jan. 1974.
[6]W.H. Chen, C.H. Smith and S.C. Fralic, “A fast computational algorithm for the discrete cosine transformation,” IEEE Trans. Communication, vol. COM-25, pp. 1004-1009, Sept. 1977.
[7]H.S. Hou, “A fast recursive algorithm for computing the discrete cosine transform,” in Proc. IEEE on International Conference on Acoustics, Speech and Signal Processing (ICASSP), vol. ASSP-35, no. 10, pp. 1445-1461, Oct. 1987.

[8] N.I. Cho and S.U. Lee, “Fast Algorithm and Implementation of 2-D Discrete Cosine Transform,” IEEE Trans. on Circuits and Systems, vol. 38, no. 3, pp. 297-305, Mar. 1991.
[9] E. Feig and S. Winograd, “Fast Algorithms for the Discrete Cosine Transform,” IEEE Trans. on Signal Processing, vol. 40, no. 9, pp. 2174-2193, Sep. 1992.
[10] M.A. Haque, “A two-dimensional fast cosine transform,” in Proc. IEEE on International Conference on Acoustics, Speech and Signal Processing (ICASSP), vol.33, no. 6, pp. 1532-1536, Dec. 1985.
[11] P. Duhamel and C. Gullemot, “Polynomial Transform Computation of the 2D-DCT,” in Proc. IEEE on International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 1515-1518, 1990.
[12] C.T. Chiu and K.J. Ray Liu, “Real-Time Parallel and Fully Pipelined Two-Dimensional DCT Lattice Structures with Application to HDTV Systems, ” IEEE Trans. on Circuits and Systems for Video Technology, vol. 2, no. 1, pp. 25-37, Mar. 1992.
[13] V. Srinivasan and K. J. Ray Liu, “VLSI Design of High-Speed Time-Recursive 2D DCT/IDCT Processor for Video Applications,” IEEE Trans. on Circuits and Systems for Video Technology, vol. 6, no. 1, pp. 87-96, Feb. 1996.
[14] J.F. Yan, B.L. Bai and S.C. Hsia, “An Efficient Two-Dimensional Inverse Discrete Cosine Transform Algorithm for HDTV Receivers,” IEEE Trans. on Circuits and Systems for Video Technology, vol. 5, no. 1, pp. 25-30, Feb. 1995
[15] T.S. Chang, C.S. Kung and C.W. Jen, “A Simple Processor Core for DCT/IDCT,” IEEE Trans. on Circuits and Systems for Video Technology, vol. 10, no. 3, pp. 439-447, Apr. 2000.
[16] 朱啟誠，”應用於即時數位視訊編解碼系統之高效能正反離散餘弦轉換架構與設
計方法及相關計算機輔助軟體設計，” 國立交通大學電子工程研究所碩士論文，1997。
[17] A. Artieri, E. Macrviak, F. Jutand and N. Demassieux, “A One Chip VLSI for Real Time Two-Dimensional Discrete Cosine Transform,” IEEE Trans. on Circuits and Systems, vol. 1, pp. 701-704, June 1988.
[18] W.P. Li, “A New Algorithm to Compute the DCT and Its Inverse,” IEEE Trans. on Signal Processing, vol. 39, no. 6, pp 1305-1311, June 1991.
[19] D. Slawecki and W.P. Li, “DCT/IDCT Processor Design for High Data Rate Image Coding,” IEEE Trans. on Circuits and Systems for Video Technology, vol.2, no. 2, pp. 135-145, June 1992.
[20] Arup K. Bhattacharya and Syed S. Haider, “A VLSI Architecture of an Inverse Discrete Cosine Transform,” in Proc. IEEE 7th Int’l Conf. on VLSI Design, Jan.1994.
[21] K. Kim and J.S. Koh, “An Area Efficient DCT Architecture for MPEG-2 Video Encoder,” IEEE Trans. on Consumer Electronics, vol.45, no. 1, pp. 62-67, Feb. 1999.
[22] M.T. Sun, T.C. Chen and A.M. Gottlieb, “VLSI Implementation of a 16x16 Discrete Cosine Transform,” IEEE Trans. on Circuits and Systems, vol. 36, no. 4,pp.610-617, Apr. 1989.
[23] M. Matsui et al., “A 200Mhz 13m2 2D DCT Macrocell Using Sense-Amplifying Pipeline Flip-Flop Scheme,” IEEE Journal of Solid-State Circuits, vol. 29, no. 12, pp.1482-1489, Dec. 1994.
[24] S. Uramoto et al., “A 100-MHz 2-D Discrete Cosine Transform Core Processor,” IEEE Journal of Solid-State Circuits, vol. 27, no. 4, pp. 492-499, Apr. 1992.
[25] T. Masaki et al., “VLSI Implementation of Inverse Discrete Cosine Transformer and Motion Compensator for MPEG2-HDTV Video Decoding,” IEEE Trans. on Circuits and Systems for Video Technology, vol. 5, pp. 387-395, Oct. 1995.
[26] C. Chen, T.S. Chang and C.W. Jen, “The IDCT Processor on the Adder-Based Distributed Arithmetic,” in IEEE Symposium on VLSI Circuits Digest of Technical Papers, pp. 36-37, 1996.
[27] Z.J. Mou et al., “A High-Speed Low-Cost DCT Architecture for HDTV Applications,” in Proc. IEEE International Symposium on Circuits and Systems (ISCAS), pp. 1153-1156, 1991.
[28] Y.F. Jang et al., “A 0.8μm 100Hz 2D DCT Core Processor,” IEEE Trans. on Consumer Electronics, vol. 40, no. 3, Aug. 1994.
[29] M.H. Sheu et al., “A High Throughput-Rate Architecture for 8x8 2-D DCT,” in Proc. IEEE International Symposium on Circuits and Systems (ISCAS), pp. 1587-1589, 1993.
[30] Avanindra Madisetti and Alan N. Willson, Jr., “A 100 MHz 2D 8x8 DCT/IDCT Processor for HDTV Applications,” IEEE Trans. on Circuits and Systems for Video Technology, vol. 5, no. 2, pp. 158-165, Apr. 1995.
[31] Y.T. Chang and C.L. Wang, “New Systolic Array Implementation of the 2-D Discrete Cosine Transform and Its Inverse,” IEEE Trans. on Circuits and Systems for Video Technology, vol. 5, no. 2, pp. 150-157, Apr. 1995.
[32] C.L. Wang and C.Y. Chen, “High-Throughput VLSI Architectures for the 1-D and 2-D Discrete Cosine Transforms,” IEEE Trans. on Circuits and Systems for Video Technology, vol. 5, no. 1, pp. 31-40, Feb. 1995.
[33] S.P. Kim and D.K. Pan, “Highy Modular and Concurrent 2-D DCT Chip,” in Proc. IEEE Int’l Symp. Circuits Syst., pp. 1081-1084, May 1992.
[34] C. Loeffler, A. Ligtenberg, and G.S. Moschytz, “Practical fast 1D DCT algorithms with 11 multiplications,” in Proc. IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), vol. 2, pp. 988-991, Feb. 1989.
[35] B.G. Lee, ”A New Algorithm to Compute the Discrete Cosine Transform," in Proc. IEEE on International Conference on Acoustics, Speech and Signal Processing (ICASSP), vol. ICASSP-32, no. 6, pp. 1243-1245, 1984.
[36] H.C. Karathanasis, ”A low ROM distributed arithmetic implementation of the forward/inverse DCT/DST using rotations,” IEEE Trans. on Consumer Electronics, vol. 41, no. 2, pp. 263-272, May 1995.
[37] J.S. Chiang and H.S. Huang, “New Architecture for High Throughput-rate Real-time 2-D DCT and the VLSI Design,” ASIC Conference and Exhibit, 1996, Proceedings, Ninth Annual IEEE International, 23-27, pp. 219-222, Sep. 1996.
[38] 簡椏珉，“離散餘弦轉換硬體架構之研究，” 國立中央大學通訊工程研究所
論文，2003。