跳到主要內容

臺灣博碩士論文加值系統

(44.192.22.242) 您好!臺灣時間:2021/08/05 12:28
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:周耀新
研究生(外文):Yao-Hsin Chou
論文名稱:量子布林電路可測試性之研究
論文名稱(外文):Research on the Testability of Quantum Boolean Circuits
指導教授:郭斯彥郭斯彥引用關係
學位類別:博士
校院名稱:國立臺灣大學
系所名稱:電機工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2009
畢業學年度:97
語文別:英文
論文頁數:61
中文關鍵詞:量子計算量子電路可逆電路電路檢測反覆邏輯陣列常數可測性最小可測性壹可測試性可測試性設計內建自我測試
外文關鍵詞:Quantum ComputingQuantum CircuitsReversible CircuitCircuit TestingIterative logic array (ILA)C-testableM-testabledesign for testability (DFT)1-testableBuilt-in Self-Test (BIST)
相關次數:
  • 被引用被引用:0
  • 點閱點閱:192
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
隨著科學技術的演進,對於布林電路測試領域及其產業的研究已經超過四十五年了,其間也衍生了許多可觀的挑戰。尤其現代電子產品的電路越做越複雜,測試這些電子線路的成本也就隨著電子晶片的複雜度一同迅速的提升。
依據國際半導體技術準則協會2007年的報告,有關測試部分的成本將會在十年之內成為所有電子產品的總成本中最主要的部份。我們責無旁貸的必須在不增加太多額外成本的條件下,提供一些有效果且划算的新方法來控制這部份的成本。因為測試技術同時也是許多能改善產品可靠度的容錯科技裡面的主要關鍵技術,因此,持續發展有效且省成本的新測試方法是非常重要的。
因為現今所有我們所使用的電子裝置與產品都是由布林電路所組成的,所以本計劃希望能在將來的研究中利用量子計算的特性,提出一些新穎的邏輯測試方法來測試布林電路。此一目標若能達成,將來所有的布林電路都能被容易、快速且以低成本的方式測試完成。如此一來,在不遠的未來,人人都可以輕易擁有便宜又可靠的各式電子產品。
本計畫之所以計畫針對量子布林電路的測試領域來做相關研究,並希望可以提出非常新穎的想法,主要有兩個原因。首先第一,既然所有的傳統電子電路技術架構總是會越做越小,且摩爾定律也無法永遠持續下去,終將有碰到物理極限的一天,那麼吾人不如開始善加利用量子物理的特性,這是在物質縮小奈米尺寸時都會發生的特殊現象,如此一來,電腦硬體的演進也能夠持續的順利進行下去。
此外第二點,依據IBM公司藍道博士的理論,所有的量子邏輯閘的操作轉換在熱力學上都是一種可逆的過程,意思也就是說,吾人將可以使用奈米尺寸的元件打造一台通用型的量子電腦,而且這台電腦的所有運算都是可逆的並且理論上僅需要消耗任意微小的能量。這樣的兩個特點正好符合未來電子裝置小型微型化與省電低耗能的趨勢。
之前的研究論文已經證明過任意的傳統布林電路都有辦法可以轉換成對應的量子布林電路。在本計畫中,我們希望可以先將所有的量子布林電路安排成反覆邏輯陣列,並使其具有「壹可測性」,也就是說,對任意的量子布林電路或者是量子反覆邏輯陣列,測試樣本的數目與該陣列的大小無關且同時與輸入位元的長度無關。換句話說,我們只需要一個測試樣本就可以測試完畢任意長度與寬度(任意的輸入位元數)的任何一個量子布林電路或陣列。若能達成這個目標,容易、快速且低成本的布林電路測試就能達成,這將會是個非常重要的貢獻與研究成果。
Circuit testing is now over 45 years and poses many considerable challenges. The circuits of modern electrical appliances become more and more complicated and the cost of circuit testing is rapidly increasing along with the complexity of the chip. According to Inter/National Technology Roadmap for Semiconductors 2001/1997, test cost will become critical part of the total cost in ten years. It is indispensable to control these costs and provide a cost-effective solution. Therefore, it is important to develop efficient testing approaches. Testing is also the key to many fault tolerance approaches that improve product reliability.
Nowadays, every electronic device/electrical appliance we use is built by Boolean circuits. In this project, a novel method is proposed to perform logic testing for Boolean circuit by utilizing the quantum computation. In the future, any Boolean circuit can be tested easily, quickly, and cost-effectively, so that reliable and inexpensive products can be acquired by everyone.
It has been proved that any Boolean circuit can have its quantum version. In this project, we showed that quantum Boolean circuits can be arranged into a 1-testable quantum iterative logic array (QILA). Furthermore, with superposition, which is a nanoscale phenomenon in the quantum computation, any quantum Boolean circuit and any QILA can be tested in just a few steps for any given classical Boolean function. By utilizing nanotechnology, these methods provide a smooth migration to the next generation circuit design and may intrinsically change the IC design flow in the future.
Recently, a systematic procedure was proposed to derive a minimum input quantum circuit for any given classical logic with the generalized quantum Toffoli gate, which is universal in Boolean logic. Since quantum Boolean circuits are reversible, we can apply this property to build quantum iterative logic array (QILA). QILA can be easily tested in constant time (C-testable) if stuck-at fault model is assumed.
In this project, we try to use Hadamard and general CCN gates to make QILA 1-testable. That is, for any quantum Boolean circuit, the number of test patterns is independent of both the size of the array and the length of the inputs.
Nanotechnology has made the semiconductor industry to keep up with the growth of consumers'' performance--capacity demands. Sophisticated semiconductor fabrication techniques are used for the production of nanoscale structures. By nanometer technologies, there are more transistors fabricated on a single chip with increasing integration scale, thus reducing the cost per transistor.
However, nanometer-scale devices have much higher manufacturing fault rates and are more sensitive to failures of transistors and wires owing to many external factors. Consequently, the difficulty of testing each transistor increases as the complexity of devices increases. Testing such highly complex and dense circuits becomes very difficult and expensive.
On the other hand, when devices are getting smaller and smaller, the quantum effect appears. With nanoscale phenomenon such as superposition or entanglement, we can perform quantum computation to accomplish some tasks that are classically impossible. Some of these examples are Shor''s factorization and Grover''s search algorithm.
It is interesting to note that these nano-phenomena can be used to solve the circuit testing problem as well. Previous study showed that any classical circuit can be implemented by a straightforward replacement algorithm with auxiliary qubits as intermediate storage. Recently, a construction procedure of minimum input quantum Boolean circuit was proposed.
The constructed quantum Boolean circuits are reversible. Such circuits are of interest for several reasons. One of the important reasons is energy saving. Reversible circuits are information lossless and hence tend to dissipate relatively little energy. According to Landauer''s principle, it is possible to construct a computer using reversible circuits that can compute with arbitrarily small amounts of energy.
Another reversible circuit''s property of particular interest is that the Boolean function of a reversible circuit is bijective (one-to-one and onto); hence it can be used to form an iterative logic array (ILA), a system that consists of identical modules arranged in a geometrically regular interconnection pattern. ILA is well known to be easily testable.
In this project, we study the testing properties on quantum Boolean circuit and quantum iterative logic array (QILA). QILA consists of reversible quantum circuits constructed from a library of universal reversible gates, including quantum NOT, controlled-NOT (CNOT), generalized controlled-controlled-NOT (CCN), and Hadamard gates. Under stuck-at fault and cell fault model, we show that any QILA and quantum Boolean circuits are 1-testable. That is, the circuits can be tested with only one test pattern.
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix
List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi
Chapter 1 Introductions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
Chapter 2 Preliminaries and Notations . . . . . . . . . . . . . . . . . . . . 4
2.1 Testability and Fault Model . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Quantum Computation, Gate and Circuit . . . . . . . . . . . . . . . 6
Chapter 3 Testability of Quantum Boolean Circuits . . . . . . . . . . . . . 9
3.1 C- and M-Testabilities of Quantum Boolean Circuit . . . . . . . . . 9
3.2 The 1-Testability of Quantum Boolean Circuit . . . . . . . . . . . . . 18
Chapter 4 Fast Diagnosis and Built-in Self-Test for Quantum Boolean
Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.1 Improving Boolean Circuit Testing . . . . . . . . . . . . . . . . . . . 26
4.2 Fast Diagnosis by using Quantum Search . . . . . . . . . . . . . . . 29
4.3 QBIST: Quantum Built-In Self-Test . . . . . . . . . . . . . . . . . . . 34
Chapter 5 Fault Equivalency and Test Data Compression for Quantum
Boolean Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
5.1 Fault Equivalency of Elementary Quantum Boolean Gates . . . . . 39
5.2 Test Data Compression for Quantum Boolean Gates and Circuits . 43
5.2.1 Probabilistic Equivalency of Elementary Gates . . . . . . . . 44
5.2.2 Test Data Compression for Generalized CCN Gates . . . . . 51
5.2.3 Test Data Compression for any Quantum Boolean Circuit . 53
Chapter 6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
[1] P. Shor, “Algorithms for Quantum Computation: Discrete Logarithms and Factoring”, in Proceedings of 35th Annual IEEE Symposium on the Foundations of Computer Science (FOCS), pp. 124–134, 1994.
[2] L. Grover, “A Fast Quantum Mechanical Algorithm for Database Search”, in Proceedings of 28th Annual ACM Symposium on the Theory of Computing (STOC), pp. 212–219, 1996.
[3] T. Toffoli (ed. J. W. de Bakker and J. van Leeuwen), Automata, Languages and Programming, pp. 632. New York: Springer. 1980.
[4] A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. Smolin, and H. Weinfurter, “Elementary Gates for Quantum Computation”,
Phys. Rev. A, 52(5): 3457–3467, 1995.
[5] D. P. DiVincenzo, “Quantum Gates and Circuits”, Proc. Roy. Soc. Lond. A, 454, 261–276, 1998.
[6] M. Nielsen and I. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, 2000.
[7] I.-M. Tsai and S.-Y. Kuo, “An Algorithm for Quantum Boolean Circuit Construction”, in Proceedings of 2001 IEEE Conference on Nanotechnology, pp. 111–116, July 2001.
[8] I.-M. Tsai and S.-Y. Kuo, “An Algorithm for Minimum Space Quantum Boolean Circuits Construction”, Journal of Circuits, Systems, and Computers, 15(5): 719–738, October 2006.
[9] R. Landauer, “Irreversibility and Heat Generation in the Computing Process”, IBM Journal of Research and Development, 5(3): 183–191, 1961.
[10] W. H. Kautz, “Testing for Faults in Combinational Cellular Logic Arrays”, in Proceedings of 8th Annual Symposium on Switching Automata Theory, pp. 161–174, 1967.
[11] P. R. Menon and A.D. Friedman, “Fault Detection in Iterative Arrays”, IEEE Trans. on Computers, vol. C-20, pp. 524–535, May 1971.
[12] A. D. Friedman, “Easily Testable Iterative Systems”, IEEE Trans. on Computers, vol. C-22, pp. 1061–1064, Dec. 1973.
[13] S. K. Lu, J. C. Wang and C. W. Wu, “C-Testable Design Techniques for Iterative Logic Arrays”, IEEE Trans. on VLSI, vol. 3, no. 1, pp. 146–152, March 1995.
[14] M. A. Breuer, “Fault Detection in a Linear Cascade of Identical Machines”, in Proceedings of 9th Annual Symposium on Switching Automata Theory, pp. 235–243, 1968.
[15] C.-H. Sung, “Testable Sequential Cellular Arrays”, IEEE Trans. on Computers, vol. C-25, no. 1, pp. 11–18, Jan. 1976.
[16] C.Y. Su and C.W. Wu, “Testing Iterative Logic Arrays for Sequential Faults with a Constant Number of Patterns”, IEEE Trans. on Computers, vol. 43, no. 4, pp. 495–501, April 1994.
[17] H. Fujiwara and S. Toida, “The Complexity of Fault Detection Problems for Combinatioinal Logic Circuits”, IEEE Trans. on Computers, vol. C-31, pp. 555–560, June 1982.
[18] C. W. Wu and P. R. Cappello, “Easily Testable Iterative Logic Arrays”, IEEE Trans. on Computers, 39(5): 640–652, May 1990.
[19] X. Ma, J. Huang, C. Metra, F. Lombardi, “Testing Reversible 1D Arrays for Molecular QCA”, in Proceedings of IEEE Symposium on Defect and Fault Tolerance in VLSI Systems (DFT‘06), pp. 71–79, Oct. 2006.
[20] A. Chakraborty, “Synthesis of Reversible Circuits for Testing with Universal Test Set and C-Testability of Reversible Iterative Logic Arrays”, in Proceedings of 18th International Conference on VLSI Design (VLSID‘05), pp. 249–254, 2005. [21] D. M. Miller, D. Maslov and G. W. Dueck, “A Transformation Based Algorithm for Reversible Logic Synthesis”, in Proceedings of Design Automation Conference
(DAC-2003) pp. 318–323, June, 2003, Anaheim, Califonia, USA.
[22] K. Patel, J. Hayes and I. Markov, “Fault Testing for Reversible Circuits”, IEEE Trans. on Computer-Aided Design, vol. 23, no. 8, pp. 1220–1230, 2004.
[23] V. Shende, A. Prasad, I. Markov and J. Hayes, “Synthesis of Reversible Logic Circuits”, IEEE Trans. on Computer-Aided Design, 22(6): 710–722, 2003.
[24] P. Gupta, A. Agrawal, N. K. Jha, “An Algorithm for Synthesis of Reversible Logic Circuits” IEEE Trans. on Computer-Aided Design, 25(11): pp. 2317–2330, Nov. 2006.
[25] K. lwama, Y. Kambayashi and S. Yamashita, “Transformation Rules for Designing CNOT-based Quantum Circuits”, in Proceedings of Design Automation Conference (DAC-2002) pp. 419–424, June, 2002, New Orleans, Louisiana, USA.
[26] L. T. Wang, C. W. Wu and X. Wen, Design for Testability: VLSI Test Principles and Architectures, Elsevier (Morgan Kaufmann), San Francisco, 2006.
[27] I.-M. Tsai and S.-Y. Kuo, “Digital Switching in the Quantum Domain”, IEEE Trans. Nanotechnol., vol. 1, pp. 154–164, Sep. 2002.
[28] I.-M. Tsai, S.-Y. Kuo and D. S. L. Wei, “Quantum Boolean circuit approach for searching an unordered database”, In Proc. 2002 IEEE Conf. Nanotechnol, pages 315–318. IEEE, Aug. 2002.
[29] Y.-H. Chou, I.-M. Tsai and S.-Y. Kuo, “Quantum Boolean Circuit is 1-Testable”, In Proc. 2007 IEEE Conf. Nanotechnol (IEEE-NANO‘07), pages 1292–1295, Aug. 2007, Hong Kong, China.
[30] Y.-H. Chou, I.-M. Tsai and S.-Y. Kuo, “QBIST: Quantum Built-In Self-Test for any Boolean Circuit”, will appear in Proc. of 26th IEEE VLSI Test Symposium (VTS’08), San Diego, 2008.
[31] ITRS information can be download from http://www.itrs.net.
[32] L. T. Wang, C. W. Wu and X. Wen, Design for Testability: VLSI Test Principles and Architectures, Elsevier (Morgan Kaufmann), San Francisco, 2006.
[33] M. L. Bushnell and V. D. Agrawal, “Essentials of Electronic Testing for Digital Memory and Mixed-Signal VLSI Circuits”, Springer Science, New York, 2000.
[34] I.-M. Tsai and S.-Y. Kuo, “An Algorithm for Quantum Boolean Circuit Construction,”In Proc. 2001 IEEE Conf. Nanotechnol (IEEE-NANO’01), pages 111–116, July 2001.
[35] Y.-H. Chou, I.-M. Tsai and S.-Y. Kuo, “Quantum Boolean Circuit is 1-Testable”, In Proc. 2007 IEEE Conf. Nanotechnol (IEEE-NANO’07), pages 1292–1295, Aug. 2007.
[36] I.-M. Tsai, S.-Y. Kuo and D. S. L. Wei, “Quantum Boolean Circuit Approach for Searching an Unordered Database”, In Proc. 2002 IEEE Conf. Nanotechnol (IEEE-NANO’02), pages 315–318, Aug. 2002.
[37] C.-M. Yu, I.-M. Tsai, Y.-H. Chou and S.-Y. Kuo, “Improving the Network Flow Problem using Quantum Search”, In Proc. 2007 IEEE Conf. Nanotechnol (IEEE-NANO’07), pages 1126–1129, Aug. 2007.
[38] Y.-L. Ju, I.-M. Tsai and S.-Y. Kuo, ”Quantum Circuit Design and Analysis for Database Search Applications,” IEEE Trans. Circuits Syst. I: Regular Papers, Volume 54, Issue 11, pages 2552–2563, Nov. 2007.
[39] Y.-H. Chou, S.-Y. Kuo and I.-M. Tsai, “QBIST: Quantum Built-In Self-Test for any Boolean Circuit”, in Proc. of 26th IEEE VLSI Test Symposium (IEEE-VTS’08), pages 261–266, San Diego, May 2008.
[40] Y.-H. Chou, I.-M. Tsai, and S.-Y. Kuo, “Quantum Boolean Circuits are 1-Testable,” IEEE Transactions on Nanotechnology, Volume 7, Issue 4, Aug. 2008, Page(s): 484–493.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊