高效容错可逆的汉明码编码和检测电路

为了检验传输过程中数据的可靠性,设计了容错可逆的汉明码电路。提出了一种新型的可逆逻辑门（FVG）,它是一种四变量奇偶保持门能容错,并且完成了FVG门等价的量子实现。利用FVG 门和现有的容错可逆门,实现了汉明码编码电路和检测电路。以(7,4)汉明码设计为实例,根据量子代价和延迟对其进行性能评估,结果证明该电路比现有电路的性能提高10% ? 20%,仿真实验结果显示,电路逻辑结构正确,性能可靠。     

非可逆逻辑门的量子可逆实现研究

逻辑关系可用逻辑函数表示,量子逻辑关系是可逆的,引入和定义了量子逻辑函数;通过引入辅助量子位,增添量子输出信号的区分位,完成对非可逆逻辑门的改造,使非可逆逻辑门在量子电路中得到可逆实现,并研究了一些有用的非可逆逻辑门的改造方法,给出可实现的优化后的量子电路。     

可逆电路中门失效错误的定位方法

可逆电路是量子计算科学,低能耗COMS以及纳米技术蜒究的基础.确保可逆电路的正确性和可靠性,错误检测和定位必不可少.本文通过分析可逆电路发生门失效错误时对电路的影响,给出了一种门失效模型的错误定位方法,即生成错误定位树的方法.本文生成的错误定位树中,根据输入向量的不同输出能把当前错误集划分成多个小的错误集,使得树的高度较小,定位错误较快.此外,在生成电路的错误定位树时不需要生成真值表和错误表,从而节省了大量的存储空间,所以能应用于大型的电路.     

基于改进遗传算法的量子可逆电路综合

针对可逆电路到量子电路的有效映射问题,提出了带禁忌表的大变异自适应遗传算法,用于量子可逆电路的综合.选取量子非门、控制非门、控制V门与控制V+门(NCV)构成量子门库,建立了量子电路计算模型.采用二进制串行编码方案,设计了适应度函数、进化算子及优化规则,实现了带禁忌表大变异自适应遗传算法的量子可逆电路综合,并用Revlib电路库进行了测试.结果表明该综合方法能同时得到多个功能解,且所生成电路的量子代价优于库中电路,验证了提出算法用于量子可逆电路综合的正确性和有效性.     

可逆逻辑门进化设计方法的CUDA实现

可逆逻辑门优化程度将直接影响可逆逻辑电路的整体优化,目前已有的优化方法难以实现全局最优。文中基于NCV门库,对遗传算法编码方案和适应度进行了改进,并将进化设计方法改造为CUDA架构下的并行算法应用到可逆逻辑门的优化。其不仅发挥了电路进化设计的全局优化能力,且在不增加硬件规模的前提下,明显提高了电路的搜索速度。     

基于变换的可逆逻辑电路量子代价优化方法

电路优化是可逆逻辑综合的关键问题。为解决可逆逻辑电路优化算法的复杂度高和可伸缩性差的问题,文中针对常见的以Toffoli为构件的可逆逻辑电路,分析归纳了其中相邻逻辑门的关系,提出了该类电路中子序列的移动和化简规则,进而给出了基于这些规则的可逆逻辑电路优化算法。并在此基础上,提出了利用模板匹配法对已被规则优化的电路进行深度优化的有效方法。通过Benchmark的电路测试,结果表明,该方法能够部分减少可逆电路的门数和控制位数,降低了构建可逆电路的代价。     

基于遗传算法的量子可逆逻辑电路综合方法研究

量子可逆逻辑电路综合主要是研究在给定的量子门和量子电路的约束条件及限制下,找到最小或较小的量子代价实现所需量子逻辑功能的电路。把量子逻辑门的功能用矩阵的数学模型表示,用遗传算法作全局搜索工具,将遗传算法应用于量子可逆逻辑电路综合,是一种全新的可逆逻辑电路综合方法,实现了合成、优化同步进行。四阶量子电路实验已取得了很好的效果,并进一步分析了此方法在高阶量子电路综合问题上的应用前景。     

基于ESOP最大加权输出相容类的可逆电路综合方法

充分挖掘乘积项在多个函数输出之间的共享因素来降低可逆电路的量子成本是基于积之异或和（Exclusive-Sums-Of-Products,ESOP）的可逆电路综合方法要解决的一个重要问题.提出一种基于最大加权输出相容类的可逆电路综合方法.该方法先借助零抑制多输出决策图对立方体集合进行输出等价类划分,并采用贪心策略计算最大加权输出相容类,然后对最大加权输出相容类进行综合,以使混合极性多控制Toffoli门以及可逆子电路在尽可能多的输出变量线之间共享.通过立方体聚类挖掘等价类中立方体间的结构相似性,并对文字数较多的立方体实施分解,进一步降低可逆电路的量子成本.使用RevLib多输出函数对所提出方法进行了验证,结果表明所提出方法可以很好地挖掘乘积项在多个函数输出之间的共享因素,能够降低由ESOP综合所得可逆电路的量子成本,并且具有较高的时间效率.     

一种通用的可逆比较器级联方法

可逆数值比较器是可逆计算机中诸多运算器中的重要组成部分。为了提升可逆比较器的通用性,进一步优化可逆比较器电路。分析了比较器的输入与输出的逻辑关系,提出并设计了一位可逆比较器(OBC)和一位可逆完全比较器(OBCC)。在此基础上将这两种器件进行级联,可以快速生成通用可逆比较器的级联电路.与相关文献对比,该级联方法有效的减少了常量输入和垃圾输出的同时,具有较低的量子代价,易于完成多位二进制数值在可逆电路中的比较。     

基于二分法量子可逆逻辑电路综合

 为了能以较小的代价自动高效地构造量子可逆逻辑电路,提出了一种新颖的量子可逆逻辑电路综合方法.该方法通过线拓扑变换和对换演算,利用递归思想,将n量子电路综合问题转换成单量子电路综合问题,从而完成电路综合,经过局部优化生成最终电路.该算法综合出全部的3变量可逆函数,未优化时平均需6.41个EGT门,优化后平均只需5.22个EGT门;理论分析表明,综合n量子电路最多只需要n2^n－1个EGT门.与同类算法相比,综合电路所用可逆门的数量大幅减少.同时该算法还避免了时空复杂度太大的问题,便于经典计算机实现.     

An Exact approach for Complete Test Set Generation of Toffoli-Fredkin-Peres based Reversible Circuits

Reversible logic has gained interest of researchers worldwide for its ultra-low power and high speed computing abilities in the future quantum information processing. Testing of these circuits is important for ensuring high reliability of their operation. In this work, we propose an ATPG algorithm for reversible circuits using an exact approach to generate CTS (Complete Test Set) which can detect single stuck-at faults, multiple stuck-at faults, repeated gate fault, partial and complete missing gate faults which are very useful logical fault models for reversible logic to model any physical defect. Proposed algorithm can be used to test a reversible circuit designed with k-CNOT, Peres and Fredkin gates. Through extensive experiments, we have validated our proposed algorithm for several benchmark circuits and other circuits with family of reversible gates. This algorithm produces a minimal and complete test set while reducing test generation time as compared to existing state-of-the-art algorithms. A testing tool is developed satisfying the purpose of generating all possible CTS’s indicating the simulation time, number of levels and gates in the circuit. This paper also contributes to the detection and removal of redundant faults for optimal test set generation.     

A Test Generation Framework for Quantum Cellular Automata Circuits

In this paper, we present a test generation framework for quantum cellular automata (QCA) circuits. QCA is a nanotechnology that has attracted recent significant attention and shows promise as a viable future technology. This work is motivated by the fact that the stuck-at fault test set of a circuit is not guaranteed to detect all defects that can occur in its QCA implementation. We show how to generate additional test vectors to supplement the stuck-at fault test set to guarantee that all simulated defects in the QCA gates get detected. Since nanotechnologies will be dominated by interconnects, we also target bridging faults on QCA interconnects. The efficacy of our framework is established through its application to QCA implementations of MCNC and ISCAS'85 benchmarks that use majority gates as primitives     

Circuit testable design and universal test sets for multiple-valued logic functions

The circuit testable realizations of multiple-valued functions are studied in this letter. First of all, it is shown that one vector detects all skew faults in multiplication modulo circuits or in addition modulo circuits, and n＋1 vectors detect all skew faults in the circuit realization of multiplevalued functions with n inputs. Secondly, min（max） bridging fault test sets with n＋2 vectors are presented for the circuit realizations of multiple-valued logic functions. Finally, a tree structure is used instead of cascade structure to reduce the delay in the circuit realization, it is shown that three vectors are sufficient to detect all single stuck-at faults in the tree structure realization of multiplevalued logic functions.     

Oscillation Ring Delay Test for High Performance Microprocessors

This paper proposes a new test scheme, oscillation ring test, and its associated test circuit organization for delay fault testing for high performance microprocessors. For this test scheme, the outputs of the circuit under test are connected to its inputs to form oscillation rings and test vectors which sensitize circuit paths are sought to make the rings oscillate. High speed transition counters or oscillation detectors can then be used to detect whether the circuit is working normally or not. The sensitizable paths of oscillation rings cover all circuit lines, detecting all gate delay faults, a large part of hazard free robust path delay faults and all the stuck-at faults. It has the advantage of testing the circuit at the working speed of the circuit. Also, with some modification, the scheme can also be used to measure the maximum speed of the circuit. The scheme needs minimal simple added hardware, thus ideal for testing, embedded circuits and microprocessors.     

Design of C-testable DCVS binary array dividers

Clocked differential cascode voltage switch (DCVS) circuits are dynamic CMOS circuits that have the advantage of being protected against test-set invalidation due to circuit delays and timing skews. The problem of testing nonrestoring and restoring DCVS binary array dividers is discussed. It is shown that a DCVS nonrestoring array divider can be made C-testable with only four or five vectors. These vectors detect all the detectable single stuck-at, stuck-open, and stuck-on faults in the circuit. The additional hardware required to achieve C-testability for an n×n nonrestoring array divider only consists of n-1 two-input XOR gates and one control input. It is also shown that a restoring DCVS binary array divider can be made C-testable with only six vectors, which also detect all the detectable single stuck-at, stuck-open, and stuck-on faults in the circuit. The hardware overhead required for the C-testable design of the n×n restoring array divider consists of n two-input XOR gates and one control input     

Sequential Circuits with Combinational Test Generation Complexity under Single-Fault Assumption

We show that the test generation problem for all single stuck-at faults in sequential circuits with internally balanced structures can be reduced into the test generation problem for single stuck-at faults in combinational circuits. In our previous work, we introduced internally balanced structures as a class of sequential circuits with the combinational test generation complexity. However, single stuck-at faults on some primary inputs, called separable primary inputs, corresponded to multiple stuck-at faults in a transformed combinational circuit. In this paper, we resolve this problem. We show how to generate a test sequence and identify undetectability for single stuck-at faults on separable primary inputs.     

Bilateral Testing of Nano-scale Fault-Tolerant Circuits

As the technology enters the nano dimension, the inherent unreliability of nanoelectronics is making fault-tolerant architectures increasingly necessary in building nano systems. Because fault-tolerant hardwares help to mask the effects caused by increased levels of defects, testing the functionality of the chip together with the embedded fault-tolerance becomes a tremendous challenge. In this paper, a new bilateral testing framework for nano circuits is proposed, where multiple stuck-at faults across different modules in a triple module redundancy (TMR) architecture are considered. In addition, a new test generator is presented for the bilateral testing that takes into account the enormous number of bilateral stuck-at faults possible with new types of guidance in the search, and it can generate a set of vectors that can test the TMR-based nano circuit as a single entity. Experimental results reported for ISCAS’85 and ITC99 circuits demonstrate that the bilateral testing can help to capture many more defects which the single stuck-at fault misses.     

Experimental Results for Self-Dual Multi-Output Combinational Circuits

In this short note, the possibilities and the limitations for the application of self-dual circuits with alternating inputs are experimentally investigated. The original circuit is assumed to be given as a netlist of gates. The necessary area overhead, the fault coverage for single stuck-at faults in test mode and the error detection probability in on-line mode due to internal stuck-at faults and stuck-at faults at the input lines are determined for MCNC benchmark circuits.     

False-Path Removal Using Delay Fault Simulation

Some false paths are caused by redundant stuck-at faults. Removal of those stuck-at faults automatically eliminates such false paths from the circuit. However, there are other false paths that are not associated with any redundant stuck-at fault. All segments of such a false path are shared with other testable paths. We focus on the elimination of this type of false paths. We use a non-enumerative path delay fault simulator based on the path status graph (PSG) data-structure, which duplicates selected gates to separate the detected and undetected path delay faults. The expanded circuit may contain new redundant stuck-at faults, corresponding to those undetected paths that are false. This happens because the expanded circuit has some new interconnects with only false paths passing through them. Such links become the sites for redundant stuck-at faults. Removal of these redundant faults eliminates false paths. The reported results show that the quality of the result may depend on the coverage of testable paths by the vectors that are simulated. When non-enumerative path delay simulation and implication-based redundancy removal techniques are used, the present procedure of false-path elimination can be applied to very large circuits.     

Testability and test generation for majority voting fault-tolerant circuits

The testability of majority voting based fault-tolerant circuits is investigated and sufficient conditions for constructing circuits that are testable for all single and multiple stuck-at faults are established. The testability conditions apply to both combinational and sequential logic circuits and result in testable majority voting based fault-tolerant circuits without additional testability circuitry. Alternatively, the testability conditions facilitate the application of structured design for testability and Built-In Self-Test techniques to fault-tolerant circuits in a systematic manner. The complexity of the fault-tolerant circuit, when compared to the original circuit can significantly increase test pattern generation time when using traditional automatic test pattern generation software. Therefore, two test pattern generation algorithms are developed for detecting all single and multiple stuck-at faults in majority voting based circuits designed to satisfy the testability conditions. The algorithms are based on hierarchical test pattern generation using test patterns for the original, non-fault-tolerant circuit and structural knowledge of the majority voting based design. Efficiency is demonstrated in terms of test pattern generation time and cardinality of the resulting set of test patterns when compared to traditional automatic test pattern generation software.