量子逻辑电路中控制点失效错误的定位  

Fault Localization for Broken Control in Quantum Circuits

作　　者：肖芳英[1] 陈汉武[1] 

机构地区：[1]东南大学计算机科学与工程学院,南京210096

出　　处：《计算机研究与发展》2009年第2期321-328,共8页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(60572071);江苏省自然科学基金项目(BK2007104);东南大学优秀博士论文基金项目(YBJJ0820)~~

摘　　要：确保可逆电路的正确性与可靠性,错误检测必不可少,错误定位难度更高.通过分析发现当可逆电路中规模为k的可逆门发生控制点失效时仅对2n-k个输入向量的输出产生影响,据此给出了一种把当前错误集分成若干个子集的方法生成控制点失效错误定位树.传统的错误定位方法都是通过生成真值表和错误表来产生错误定位树;该方法不需要生成和存储真值表以及错误表就能够有效定位电路中控制点失效错误.与Rfault算法相比,空间复杂度和时间复杂度更小,算法效率更高,能应用于更大规模的电路.Reversible circuit is the basis of quantum computation, low-power COMS, and nanotechnology. To ensure the validity and liability of the reversible circuits, fault detection and fault localization are necessary. And fault localization is more difficult than fault detection. Discussed in this paper is broken control faults （BCFs） localization in reversible circuits. By analyzing the influence of BCFs on the outputs of reversible circuit, it is found that the broken control fault of a gate with size k just changes the outputs of 2n-k inputs of the reversible circuit. According to this, the authors presents a method to construct fault localization tree to locate BCFs, which divides the current fault set into several subsets and constructs the sub fault localization tree for each subset recurrently. The method doesn＇t need any truth table and fault table when constructing the fault localization tree which are necessary for the traditional fault localization method. The height of the fault location tree （FLT） is short and can be used to locate BCFs efficiently. It has less time and space complexity than the BCFs localization methods called Rfault, so it can be applied to larger circuits. This method can also be applied to locate other kinds of fault models, such as missing gate fault.

关 键 词：可逆电路 量子电路 控制点失效 错误定位 错误定位树 

分 类 号：TP387[自动化与计算机技术—计算机系统结构] TP301.6[自动化与计算机技术—计算机科学与技术]