動量估測 (Motion Estimation) 是影像編碼系統中最主要的運算，是運算量最為密集的一個部分，也因為簡單性和規律性，區塊比對演算法被廣泛的應用在運動向量的計算上。而因現今VLSI 技術的進步，使得動量估測運算陣列得以整合到系統晶片 (SOC, System-on-a-chip) 上。然而，因為系統晶片的腳位有限，將會大大的降低其晶片測試的效率。為了解決這樣的問題，使測試能快速且有效的進行，因此必須對動量估測運算陣列進行可測試性與內建自我測試的硬體電路設計。基於C-testability關係，在位元階層下，將動量估測運算陣列之基本細胞 (cell) 之功能調整成具有 bijective 的特性。在模組階層下，由於它本身的輸入皆能由外部控制，輸出也都能傳到最主要的輸出端，故電路本身即具有可控制性與可觀測性。在內建自我測試的設計中，我們使用計數器作為測試向量產生器；在輸出響應分析器方面，則利用查驗總和的方式來驗證。在位元階層下，我們只需要32組的測試向量；在模組階層下，則需要2w組測試向量來完成。在內建自我測試的架構中，需要的額外硬體成本約為2%。另外由於在單一細胞下進行DFT設計時，其硬體成本較高，因此我們也提出模組化 (Scalable) 之可測試性技術，以期在測試向量數目與硬體成本間作取捨，我們也以動量估測陣列與快速傅立葉轉換器陣列來驗證我們的想法。

Motion estimation is the main computation used in video coding systems. It’s the most computation-intensive part. Because of the simplicity and regularity, the block matching algorithms are widely used for the computation of motion vectors. With the advance of VLSI technology, integration of the motion estimation computing array into a single chip or a system-on-chip (SOC) design is becoming possible. However, integrating a large number of processing elements (PEs) on a single chip or SOC will increase the logic-per-pin ratio, which drastically reduces the efficiency of testing the logic on the chip. In order to deal with these problems, design-for-testability and BIST techniques are proposed for motion estimation computing arrays. The bit-level or word-level cells (modules) in the array are made bijective to meet the C-testability conditions. The test pattern generator can be a simple binary and the output response analyzer is basically a checksum comparator. The number of test patterns is 32 and 2w for the bit-level and module-level designs, respectively. The hardware overhead of the BISTed motion estimation array is only 2 %. In order to tradeoff between the hardware overhead and the number of test patterns, a scalable DFT technique was also proposed in this thesis.

中文摘要‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ i
英文摘要‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ ii
致謝‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ iii
目錄‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ iv
表目錄‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ vi
圖目錄‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ vii
第一章 緒論‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 1
1.1 動機‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 1
1.2 論文架構‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 4
第二章 動量估測演算法與架構分析‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 5
2.1 固定區塊比對演算法‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 5
2.1.1 完全搜尋演算法‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 6
2.1.2 三步搜尋演算法‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 7
2.1.3 新三步搜尋法‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 8
2.2 可變式區塊比對演算法 ‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧9
2.3 區塊大小比對演算法之硬體架構設計‧‧‧‧‧‧‧‧‧‧‧‧‧10
2.3.1 固定式區塊大小比對演算法架構‧‧‧‧‧‧‧‧‧‧‧‧‧10
2.3.1.1 Komarek 和 Pirsch 的架構‧‧‧‧‧‧‧‧‧‧‧‧10
2.3.1.2 Yeo 和 Hu 的架構‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧11
2.3.2 可變式區塊大小比對演算法架構‧‧‧‧‧‧‧‧‧‧‧‧12
第三章 動態估測架構之可測試性設計回顧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 14
第四章 動量估測陣列之可測試性設計‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 17
4.1 C-testability 相關觀念回顧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 17
4.2 位元階層 (Bit Level) 之可測試性設計‧‧‧‧‧‧‧‧‧‧‧‧‧ 20
4.3 模組階層 (Module Level) 之可測試性設計‧‧‧‧‧‧‧‧‧‧‧ 25
第五章 動量估測陣列之內建自我測試性設計‧‧‧‧‧‧‧‧‧‧‧‧‧ 29
第六章 連續邏輯陣列的模組化可測試性設計‧‧‧‧‧‧‧‧‧‧‧‧‧‧34
6.1 主要目的‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 34
6.2 模組化架構設計‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧34
6.2.1 全加法器的模組化架構設計‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧36
6.2.2 動量估測陣列的模組化架構設計‧‧‧‧‧‧‧‧‧‧‧‧‧38
6.2.3 快速傅立葉轉換器 (FFT) 的模組化架構設計‧‧‧‧‧‧‧‧42
第七章 實驗結果‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 52
7.1 設計流程‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 52
7.2 模擬結果‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 55
7.3 失真機率‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧58
7.4 模組化比較‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧60
第八章 結論‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧62
8.1 結論‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 62

[1]ISO/IEC 11172-2, “Coding of Moving Pictures and Associated Audio for Digital Storage Media at up to About 1.5 Mbit/s: Part 2 - Video,” August 1993.
[2]Joan L. Mitchell, William B. Pennebaker, Chad E. Fogg, and Didier J. LeGall, MPEG Video Compression Standard, International Thomson Publishing, 1997.
[3]ISO/IEC JTC1/SC29/WG11 Draft CD 13818-2, “General Coding of Moving Pictures and Associated Audio,” 1994.
[4]MPEG Requirements Group, “MPEG-4 Overview Document,” Document ISO/IEC JTC1/SC29/WG11/N2725, March 1999.
[5]ITU-T Rec. H.261, “Video Coding for Audiovisual Services at p×64 kbits/s,” March 1993.
[6]ITU-T Rec. H.263, “Video Coding for Low Bit Rate Communication,” January 1998.
[7]Karel Rijkse, KPN Research, “H.263: Video Coding for Low-Bit-Rate Communication,” IEEE Communication Magazine, pp. 42-45,December 1996.
[8]Thomas Wiegand, Gary J. Sullivan, Gisle Bjontegaard, and Ajay uthra, “Overview of the H.264/AVC Video Coding Standard,” IEEE Trans. Circuits and Syst. for Video Technology, pp. 560-576, July 2003.
[9]Vasudev Bhaskaran and Konstantinos Konstantinides, Image and Video Compression Standards: Algorithms and Architectures, Kluwer, 1997.
[10]C. Cafforio and F. Rocca, “Methods for Measuring Small Displacements of Television Images,” IEEE Trans. Inform. Theory, vol. IT-22, no. 5, pp. 573-579, September 1976.
[11]H. G. Musmann, P. Pirsch, and H. J. Grallert, “Advances in Picture Coding,” in Proc. IEEE , vol. 73, pp. 523-548, April 1985.
[12] T. Koga, K. Iinuma, A. Hirano, Y. Iijima and T. Ishiguro, “Motion-Compensated Interframe Coding for Video Conferencing,” in Proc. Nat. Telecommunications Conf., pp. G 5.3.1-G 5.3.5, November-December 1981.
[13] Renxiang Li, Bing Zeng, and Ming L. Liou, “A New Threestep Search Algorithm for Block Motion Estimation,” IEEE Trans. on Circuits and Systems for Video Technology, vol. 4, no. 4, pp. 438-442, August 1994.
[14] C. Y. Chen, S. Y. Chien, Y. W. Huang, T. C. Chen, T. C. Wang, and L. G. Chen, “Analysis and Architecture Design of Variable Block-Size Motion Estimation for H.264/AVC,” IEEE Trans. on circuits and systems, vol. 53, no. 2, pp. 578-593, February 2006.
[15]S. K. Lu, J. S. shih and S. C. Huang, “Design-for-Testability and Fault-Tolerant Techniques for FFT Processors,” IEEE Trans. VLSI Syst., vol. 13, no. 6, pp. 732-741, June 2005.
[16]S. K. Lu, C. W. Wu and S. Y. Kuo, “Enhancing Testability of VLSI Arrays for Fast Fourier Transform,“ IEE Proc. Part E, vol. 140, no. 3, pp. 161-166, May 1993.
[17]C. W. Wu and P. R. Cappello, “Easily Testable Iterative Logic Arrays,” IEEE Trans. Comput., vol. C-31, no. 6, pp. 640-652, May 1990.
[18]W. H. Kautz, “Testing for Faults in Combinational Cellular Logic Arrays,” in Proc. 8th Annu. Symp. Switching, Automata Theory, pp. 161-174, 1967.
[19] P. R. Menon and A. D. Friedman, “Fault Detection in Iterative Arrays,” IEEE Trans. Comput., vol. C-20, pp. 524-535, May 1971.
[20] A. D. Friedman, “Easily Testable Iterative Systems,” IEEE Trans. Comput., vol. C-22, pp. 1061-1064, December 1973.
[21]S. K. Lu, J. C. Wang and C. W. Wu, “C-testable Design Techniques for Iterative Logic Arrays,” IEEE Trans. VLSI Syst., vol. 3, pp. 146-152, March 1995.
[22]T. Komarek and P. Pirsch, “Array Architectures for Block Matching Algorithms,” IEEE Trans. Circuits and Syst., vol. 36, no. 10, pp. 1301-1308, October 1989.
[23] H. Yeo, Y. H. Hu, “A Novel Modular Systolic Array Architecture for Full-search Block Matching Motion Estimation,” IEEE Trans. on Circuits and Systems for Video Technology. vol. 5, no. 5, pp.407-416, October 1995.
[24]W. P. Marnane and W. R. Moore, “Testing a Motion Estimator Array,” in Proc. Int’l Conf. Application Specific Array Processors, pp. 734-745, 1990.
[25] M. Y. Dong, S. H. Yang and S. K. Lu, “Design-for-Testability Techniques for Motion Estimation Computing Arrays,” ICCCAS Conf. on communications Circuits and Systems, pp. 1188-1191, May 2008.
[26] J. F. Li, S. K. Lu, S. Y. Huang, and C. W. Wu, “Easily Testable and Fault Tolerant FFT Butterfly Networks,” IEEE Trans. Circuits Syst. II, Analog Digit. Signal Process., vol. 47, no. 9, pp. 919-929, September 2000.
[27] S. K. Lu, J. S. Shih, and S. C. Huang, “Design-for-Testability and Fault-Tolerant Techniques for FFT Processors,” IEEE Trans. on VLSI Systems, vol. 13, no. 6,pp. 732-741, June 2005.