請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/41868
標題: | 量子布林電路可測試性之研究 Research on the Testability of Quantum Boolean Circuits |
作者: | Yao-Hsin Chou 周耀新 |
指導教授: | 郭斯彥 |
關鍵字: | 量子計算,量子電路,可逆電路,電路檢測,反覆邏輯陣列,常數可測性,最小可測性,壹可測試性,可測試性設計,內建自我測試, Quantum Computing,Quantum Circuits,Reversible Circuit,Circuit Testing,Iterative logic array (ILA),C-testable,M-testable,design for testability (DFT),1-testable,Built-in Self-Test (BIST), |
出版年 : | 2009 |
學位: | 博士 |
摘要: | 隨著科學技術的演進,對於布林電路測試領域及其產業的研究已經超過四十五年了,其間也衍生了許多可觀的挑戰。尤其現代電子產品的電路越做越複雜,測試這些電子線路的成本也就隨著電子晶片的複雜度一同迅速的提升。
依據國際半導體技術準則協會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. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/41868 |
全文授權: | 有償授權 |
顯示於系所單位: | 電機工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-98-1.pdf 目前未授權公開取用 | 880.41 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。