Timing-driven logic restructuring for nano-hybrid circuits

As the feature size of the integrated circuits (ICs) scales down, the future of nano-hybrid circuit looks bright in extending Moore's Law. However, mapping a circuit to a nano-fabric structure is vexing due to connectivity constraints. A mainstream methodology is that a circuit is transformed into a nano-fabric preferred structure by buffer insertion to high fan-out gates. However, it may result in timing degradation. Logic replication is a traditional way to split high fan-out gates in logic synthesis but may not be suitable for high fan-out gates with high fan-ins. In this article, a timing-driven logic restructuring framework at the gate level is proposed. The proposed framework identifies the high fan-out gates from a given gate netlist according to the fan-out threshold, following by the restructuring of high fan-out gates through the application of logic replication and buffer insertion. To improve circuit timing from a global perspective, latent critical edges are identified to avoid entrapping critical paths during the restructuring. Experimental results on ISCAS benchmarks indicate that 8.51% timing improvement and 6.13% CPU time reduction can be obtained traded with 4.16% area increase on an average.     

Exact synthesis of three-qubit quantum circuits from non-binary quantum gates

Because of recent nano-technological advances, nano-structured systems have become highly ordered, making it quantum computing schemas possible. We propose an approach to optimally synthesise quantum circuits from non-permutative quantum gates such as controlled-square-root-of-not (i.e., controlled-V). Our approach reduces the synthesis problem to multiple-valued optimisation and uses group theory. We devise a novel technique that transforms the quantum logic synthesis problem from a multi-valued constrained optimisation problem to a permutable representation. The transformation enables us to use group theory to exploit the symmetric properties of the synthesis problem. Assuming a cost of one for each two-qubit gate, we found all reversible circuits with quantum costs of 4, 5, 6, etc., and give another algorithm to realise these reversible circuits with quantum gates. The approach can be used for both binary permutative deterministic circuits and probabilistic circuits such as controlled random-number generators and hidden Markov models.     

Logic decomposition of speed-independent circuits

Logic decomposition is a well-known problem in logic synthesis, but it poses new challenges when targeted to speed-independent circuits. The decomposition of a gate into smaller gates must preserve not only the functional correctness of a circuit but also speed independence, i.e., hazard freedom under unbounded gate delays. This paper presents a new method for logic decomposition of speed-independent circuits that solves the problem in two major steps: (1) logic decomposition of complex gates and (2) insertion of new signals that preserve hazard freedom. The method is shown to be more general than previous approaches and its effectiveness is evaluated by experiments on a set of benchmarks     

The use of threshold logic in character recognition

The fact that many complex counting and decision functions can be realized quite simply with threshold gates suggests that they may be used to considerable advantage in problems of character recognition. A simplified recognition problem is considered involving the identification of any one of 12 letters when it is superimposed on an m × n matrix. Translation, stretching, and compression of the letter are permitted. It is shown that the number of threshold gates required increases linearly as do the dimensions of the matrix with about 300 gates being necessary for a 20 × 20. On such a matrix, several hundred thousand configurations of the 12 letters can be correctly identified with each pattern being insensitive to varying degrees of "noise." A threshold gate having the necessary fan power for this application is described together with its implementation in a small experimental model. Extensions of the methods to include rotation and magnification are discussed.     

基于新型量子逻辑门库的最优NCV三量子电路快速综合算法

许多量子电路综合算法由于指数级时间与空间复杂度,只能用可逆逻辑门综合3量子逻辑电路,仅有少数算法实现用量子非门,控制非门,控制V门与控制V⁺门(NCV)综合3量子逻辑电路,主要方法是将电路综合问题简化为四值逻辑综合问题.本文提出用NCV门构造新型量子逻辑门库,该库与NCV门库在综合最优3量子逻辑电路上等价,因此又可将四值逻辑综合问题进一步简化为更易求解的二值逻辑综合问题,使用基于完备Hash函数的3量子电路快速综合算法,快速生成全部最优的3量子逻辑电路,以最小代价综合电路的平均速度是目前最好结果Maslov 2007的近127倍.     

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

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

Static hazards in combinational threshold logic networks†

The possibility of transitory false outputs in conventional digital logic circuits is well known, such output ‘ spikes ’ being the result of different propagation times through the logic network from inputs to output. The usual solution to such ‘ Static hazards ’ is also well known, being the incorporation of additional gates in the system to cover such input transitions. This paper shows that the application of threshold logic gates to logic synthesis has attractions in very easily eliminating such hazards, in many cases without the need for any additional covering gates in the network.     

Disturbance localisation in linear time-invariant multivariable systems

A simple algebraic approach is used to derive necessary and sufficient conditions for the existence of a state feedback matrix to localise disturbances and which some of the closed-loop-system eigenvectors must satisfy for disturbance localisation. This latter result provides valuable insight as to how the state feedback matrix may be synthesised.     

An Efficient Map Method for Processing Multistate Logic Trees

A comterm map method permits machine computation of the probability of occurrence of the event associated with the output for each logic gate of a multistate logic tree. The method is general and applies to any tree configuration, except where feedback occurs from higher to lower gates. Any state of two or more mutually exclusive component states may be used one or more times as primary inputs to the logic gates. The method usually requires much less memory than a minterm or Karnaugh map method by providing map space for only those selected components called ``common.'     

Synthesis of Fredkin-Toffoli reversible networks

Reversible logic has applications in quantum computing, low power CMOS, nanotechnology, optical computing, and DNA computing. The most common reversible gates are the Toffoli gate and the Fredkin gate. We present a method that synthesizes a network with these gates in two steps. First, our synthesis algorithm finds a cascade of Toffoli and Fredkin gates with no backtracking and minimal look-ahead. Next we apply transformations that reduce the number of gates in the network. Transformations are accomplished via template matching. The basis for a template is a network with m gates that realizes the identity function. If a sequence of gates in the network to be reduced matches a sequence of gates comprising more than half of a template, then a transformation that reduces the gate count can be applied. We have synthesized all three input, three output reversible functions and here compare our results to the optimal results. We also present the results of applying our synthesis tool to obtain networks for a number of benchmark functions.     

Solving the gate packing problem using a concurrent network

The layout problem of gate matrices and one-dimensional logic arrays is composed of two major tasks: to find a permutation of gates which minimises the number of tracks required and to layout/pack gates based on the ordering. A parallel algorithm is presented which can pack n gates within O(1) time, whereas the conventional near-optimum algorithm needs O(n/sup 2/) time. The simulation results show that the increase of the problem size does not degrade the solution quality.<>     

线性最近邻量子电路状态分析及最优逻辑综合

综合量子电路时必须考虑量子电路实现时的约束与限制.某些量子技术中只允许物理上相邻的量子比特有相互作用,实现时必须采用线性最近邻架构.通常通过添加交换门使任意一个量子门的控制位与目标位相近邻,并保证电路的功能不受影响.在分析电路中量子比特状态的基础上,提出了一种新的线性最近邻量子电路构造方法.结果表明:对于所有40320个三比特量子电路,提出方案比已有方案的量子代价优化了约30％.     

A cubical logic circuit modelling for reliability studies

A deeper insight into the problem of reliability analysis for combinational logic circuits is presented. Reliability is defined as the probability that the logic circuit correctly processes a given set of inputs. While the straightforward approach to this evaluation requires a formidable amount of computations, the presented approach is fast, easy to implement, memory efficient and applicable to circuits of any size and complexity. This is due to a new concept for logic circuit modelling, which allows the covering of all possible faults in a circuit by a relatively small number of sets of logically equivalent faults.For modelling purposes the excitations of inputs and the states of terminals in logic gates are presented in the form of a state vector. The logically equivalent state vectors are merged to form highest-order cubes which are mapped onto a gate equivalent graph (GEG). According to the connections among gates in the logic circuit this graphical model is extended to the circuit equivalent graph (CEG), which comprises the highest-order cubes for a circuit in the form of appropriate subgraphs, the so called state graphs (SGs).     

Computational analysis and comparison of reversible gates for design and test of logic circuits

Quantum computing is one of the most significant anticipation towards the accomplishment of interminable consumer demands of small, high speed, and low-power operable electronics devices. As reversible logic circuits have direct applicability to quantum circuits, design and synthesis of these circuits are finding grounds for emerging nano-technologies of quantum computing. Multiple Controlled Toffoli (MCT) and Multiple Controlled Fredkin (MCF) are the fundamental reversible gates that playing key role in this phase of development. A number of special reversible gates have also been presented so far, which were claimed superior for providing certain purposes like logic development and testing. This paper critically analyses a range of these gates to procure an optimal solution for design, synthesis and testing of reversible circuits. The experimentation is facilitated at three subsequent levels, i.e. gates properties, quantum cost and design & testability. MCT and MCF gates are found up to 50% more cost-effective than special gates at design level and 34.4% at testability level. Maximum reversibility depth (MRD) is included as a new measurement parameter for comparison. Special gates exhibit MRD up to 7 which ideally should be 1 for a system to be physically reversible as that of MCT and MCF gates.     

The synthesis method of logic circuits based on the iMemComp gates

The iMemComp is a family of logic gates based on RRAM devices. It has potential advantage on the design of high-performance logic circuits, since the NAND, AND, NOT and transmission iMemComp gates only consume single cycle, respectively. However, the synthesis method of logic circuits based on the iMemComp gates has not been systematically studied before. This work proposes the synthesis method of the row-oriented logic circuits based on the multi-input single-cycle iMemComp gates. The synthesis results show that the circuits generated from the proposed method outperform most of those RRAM based counterparts generated from the previous methods. Furthermore, the synthesis method of the array-oriented iMemComp logic circuits is proposed. The proposed array-oriented method generates the relatively high-performance logic circuits since both the row-based and the column-based single-cycle iMemComp gates are applied, and the generated circuits are relatively area-efficient because the intra-row and inter-row redundancies are utilized in the circuit mapping.     

Logic synthesis of race-free asynchronous CMOS circuits

A synthesis method for generating race-free asynchronous CMOS circuits that are independent of the internal and output delays is presented. The design method is based on the properties of the negative gates. An inertial delay is associated with each negative gate in a CMOS circuit. Such a gate model is quite realistic. The basic principle of the method presented is to augment and to modify the original flow table in such a way that the obtained logic diagram contains only negative gates. In addition, the synthesis method is capable of avoiding any race, and consequently any critical race or hazard. The method minimizes the number of internal variables and therefore the number of gates, providing new simple cells for fast and low-power integrated circuits     

Co-RAM: combinational logic synthesis applied to softwarepartitions for mapping to a novel memory device

We introduce the application of current techniques for hardware synthesis of combinational logic blocks to large-scale software partitions for eventual implementation of these partitions in a novel memory device called "Co-RAM." The novelty of our approach is based upon the observation that a wide variety of largescale software functionality can be considered "stateless" by conventional hardware synthesis tools and so may be realized as combinational logic. By limiting the functions placed in memory to combinational functions, we eliminate conventional synchronization overhead associated with coprocessors. A significant aspect of Co-RAM is that it is a system design concept that inherently merges hardware and software design styles at the system level, impacting programming styles, system build approaches, and the programmer's view of the underlying machine. A direct consequence of viewing the functionality as combinational is that the system state is not partitioned with the tasks. By Considering Co-RAM functionality to be stateless with respect to system state, Co-RAM functionality is inlined around the advancement of effectively unpartitioned system state. The rules for procedural combinational logic synthesis are shown to apply to a wide variety of software partitions. Results of our investigation project speedups of 8× to 1000× for a range of algorithms of varying problem size and for projected devices ranging from conventional field programmable gate arrays (FPGAs) to highly specific combinational logic devices     

Improvement of cascaded semiconductor optical amplifier gates byusing holding light injection

The cascadability of semiconductor optical amplifier (SOA) gates by using holding light injection is numerically and experimentally investigated. Our experimental results show that the signal bit error rate after two cascaded SOA gates will be larger than 10^-9 without holding light injection; however 11 SOA gates can be cascaded with holding light injection. The results show that the number of cascaded SOA gates by using holding light injection can be strongly increased     

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

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