The detection probability computation of single stuck-at-faults in general combinational circuits

The detection probability problem of single faults at specified signal lines of a general combinational circuit C merits special interest. In this paper, a method is developed for such a purpose. The method has a computational complexity of O(2^N), with N being the number of the non-fanout primary inputs plus the specified signal lines at the highest level of C. The applicability of the simple chain rule in the probability domain, whenever possible, is shown to reduce the computational time complexity. Moreover, all signal lines and gates within any subcircuit C_i of C with redundant output lines are shown to be redundant as well, excluding those subcircuits C_js of C_i having fanout stems as output lines, provided that such stems do not converge in C_i     

Output probability from a general combinational network

In this paper, we present the method which calculates the probability of the output of a general combinational network being 1, when the probabilities is given for each input being 1. Also we present the method which derives the output probability expression in terms of a given set of input probabilities.The method is based on a basic probability axiom and Binary Decision Diagrams. A Boolean function for a combinational network is transformed into a Binary Decision Diagram and the output probability expression is derived from it. Therefore a derivation of the output probability for a combinational network can be straightforward. Some examples are showed that the method using Binary Decision Diagrams is simple and efficient. We can see a variation of the output probability for a combinational network according to the given set of input probabilities.     

Fast algorithm for computing the reliability of a communication network

This paper presents a fast algorithm for computing the reliability of a communication network when each link has the same probability of success. The computational complexity of existing algorithms increases exponentially as the number of links increases. Our algorithm is based on combinatorics and we conclude, for the case when links have the same survival probabilities, that the computational complexity grows subexponentially as the number of links increases. Furthermore, the algorithm is mostly algebraic in nature.     

The probability of error detection in sequential circuits using random test vectors

In this article a method is presented for evaluating the probability of detecting (PD) a single stuck-fault in a sequential circuit as a function of the number of random input test vectors. A discrete parameter Markov-model is used in the analysis to obtain closed-form expressions for PD. The circuit is partitioned into three parts, the input and output combinational logic and the memory. The analysis is based upon the stationary-state transition matrix associated with a circuit, and the probability that a fault in one of the partitions produces an error at the output of that partition when a random input vector is applied. Results are presented to show how this problem can be reduced to that of testing an equivalent combinational circuit.     

A novel design of a combinational network to facilitate fault detection

This letter describes a novel design of a combinational network to facilitate the single stuck-at fault detection problem. The design makes use of EXCLUSIVE-OR modules as control elements and the observability has been increased by providing an additional observable output which is the output of an additional AND gate in the network. Such a design of a combinational network with n primary input variables will require only (n + 1) predefined test input patterns belonging to the set T = {11...11,011...11,101 ...11, ........., 11 ... 110} for the detection of stuck-at single s-a-0 and s-a-1 fault on a line of the network. As a result, the extremely difficult task of test generation can be easily dispensed with.     

A Kernel‐Based Partitioning Algorithm for Low‐Power,Low‐Area Overhead Circuit Design Using Don't‐Care Sets

This letter proposes an efficient kernel‐based partitioning algorithm for reducing area and power dissipation in combinational circuit designs using don't‐care sets. The proposed algorithm decreases power dissipation by partitioning a given circuit using a kernel extracted from the logic. The proposed algorithm also reduces the area overhead by minimizing duplicated gates in the partitioned sub‐circuits. The partitioned subcircuits are further optimized utilizing observability don't‐care sets. Experimental results for the MCNC benchmarks show that the proposed algorithm synthesizes circuits that on the average consume 22.5% less power and have 12.7% less area than circuits generated by previous algorithms based on a precomputation scheme.     

Switching activity estimation of VLSI circuits using Bayesian networks

Switching activity estimation is an important aspect of power estimation at circuit level. Switching activity in a node is temporally correlated with its previous value and is spatially correlated with other nodes in the circuit. It is important to capture the effects of such correlations while estimating the switching activity of a circuit. In this paper, we propose a new switching probability model for combinational circuits that uses a logic-induced directed-acyclic graph (LIDAG) and prove that such a graph corresponds to a Bayesian network (BN), which is guaranteed to map all the dependencies inherent in the circuit. BNs can be used to effectively model complex conditional dependencies over a set of random variables. The BN inference schemes serve as a computational mechanism that transforms the LIDAG into a junction tree of cliques to allow for probability propagation by local message passing. The proposed approach is accurate and fast. Switching activity estimation of ISCAS and MCNC circuits with random and biased input streams yield high accuracy (average mean error=0.002) and low computational time (average elapsed time including CPU, memory access and I/O time for the benchmark circuits=3.93 s).     

EDA-Based Scheduling of Users in the MIMO Multiple Access Channel

In this paper, we address a user scheduling (selection) problem in the uplink multiuser multiple input multiple output (MIMO) wireless communication system. For this problem, the computational complexity of exhaustive search grows exponentially with the number of users. We present an iterative, low-complexity, sub-optimal algorithm for this problem. We apply an Estimation of Distribution Algorithm (EDA) for the user scheduling problem. An EDA is an evolutionary algorithm and updates its chosen population at each iteration on the basis of the probability distribution learned from the population of superior candidate solutions chosen at the previous iterations. The proposed EDA has a low computational complexity and can find a nearly optimal solution in real time for the user scheduling problem. Beyond applying the general EDA to user scheduling, we also present specific improvements that reduce computation for obtaining an acceptable solution. These improvements include the idea of generating an initial population by cyclically shifting a candidate solution. The simulation results show that our proposed algorithm performs better than other scheduling algorithms with comparable complexity.     

A distributed algorithm for fault simulation of combinatorial and asynchronous sequential digital designs, utilizing circuit partitioning, on loosely-coupled parallel processors

Fault simulation constitutes an indispensable tool in ensuring the correctness and quality of manufactured digital designs. Traditional uniprocessor based algorithms for fault simulation have been observed to be agonizingly slow for today's large and complex digital designs. More recently, a few researchers introduce an approach, as evident in the literature, wherein the fault set is partitioned and the digital design fault simulated for each of the fault subset on separate processors of a parallel processor system. The approach is limited in that it continues to utilize the traditional uniprocessor-based algorithm and the performance results are not encouraging. This paper introduces, perhaps for the first time, a distributed algorithm that is capable of fault simulating both combinational and asynchronous sequential digital designs on parallel processors. An underlying assumption of the algorithm is that the digital design, under fault simulation, is partitioned by the user. In this approach, referred to as NODIFS in this paper, every component in the circuit is modeled as an asynchronous, concurrent, entity that is fault simulated as soon as appropriate signal transitions and fault lists are asserted at its input ports. The circuit partitioning is such that components of every partition are allocated to a unique processor of the parallel processor system. Consequently, a number of components may be concurrently fault simulated on multiple processors in NODIFS implying significant increase in throughput. This approach promises (i) very high throughput because of its ability, in principle, to utilize the maximal inherent parallelism, and (ii) scalability. The algorithm is novel in that the overall task of decision-making i.e., fault simulation of the circuit, is distributed into a number of natural, independent, and concurrent entities that execute asynchronously to utilize maximal parallelism. NODIFS's success is the result of the asynchronous distributed discrete-event simulation algorithm, YADDES, and a new approach to fault simulation. The notion of scalability implies that where the problem size increases, the algorithm continues to apply and, by increasing the number of computational engines proportionately, the performance of the algorithm will continue to increase. Furthermore, NODIFS is a natural choice for fault simulation of digital designs at the behavior-level — an eventual reality, wherein the ratio of the computational to communication load for the behavior models may approach a significantly large value. This paper also reports on an implementation of NODIFS on both the ARMSTRONG parallel processor system at Brown University and the performance results indicate significant increase in the speedup for a few representative example digital designs. It is stressed that the representative digital designs serve to support the mathematical validity of the algorithm along with the proof of correctness and not to demonstrate a high-performance, commercial, industrial-quality fault simulator.     

Energy minimization and design for testability

The problem of fault detection in general combinational circuits is NP-complete. The only previous result on identifying easily testable circuits is due to Fujiwara who gave a polynomial time algorithm for detecting any single stuck fault inK-bounded circuits. Such circuits may only contain logic blocks with no more thanK input lines and the blocks are so connected that there is no reconvergent fanout among them. We introduce a new class of combinational circuits called the (k, K)-circuits and present a polynomial time algorithm to detect any single or multiple stuck fault in such circuits. We represent the circuit as an undirected graphG with a vertex for each gate and an edge between a pair of vertices whenever the corresponding gates have a connection. For a (k, K)-circuit,G is a subgraph of ak-tree, which, by definition, cannot have a clique of size greater thank+1. Basically, this is a restriction on gate interconnections rather than on the function of gates comprising the circuit. The (k, K)-circuits are a generalization of Fujiwara'sK-bounded circuits. Using the bidirectional neural network model of the circuit and the energy function minimization formulation of the fault detection problem, we present a test generation algorithm for single and multiple faults in (k, K)-circuits. This polynomial time aggorithm minimizes the energy function by recursively eliminating the variables.     

Fast EMI Analysis via Transverse Partitioning and Waveform Relaxation

High-speed interconnects are increasingly becoming susceptible to electromagnetic interference (EMI). Hence, there is a growing need for fast simulation of interconnect lines in the presence of incident field coupling using circuit simulators such as SPICE. However, the presence of a large number of coupled lines in modern interconnect structures is a serious limiting factor in these simulations. In order to simultaneously address these difficulties, a new algorithm is presented in this paper for EMI analysis of large number of coupled interconnects. The new method exploits the recently developed waveform relaxation (WR) and transverse partitioning algorithms for fast EMI analysis. The same WR sources that are computed for multiconductor transmission line analysis are also employed for EMI analysis. The computational complexity of the proposed EMI analysis grows only linearly with the number of lines. In addition, the algorithm lends itself to parallel implementation leading to further reduction in CPU time.      

Reliability evaluation of logic circuits using probabilistic gate models

Logic circuits built using nanoscale technologies have significant reliability limitations due to fundamental physical and manufacturing constraints of their constituent devices. This paper presents a probabilistic gate model (PGM), which relates the output probability to the error and input probabilities of an unreliable logic gate. The PGM is used to obtain computational algorithms, one being approximate and the other accurate, for the evaluation of circuit reliability. The complexity of the approximate algorithm, which does not consider dependencies among signals, increases linearly with the number of gates in a circuit. The accurate algorithm, which accounts for signal dependencies due to reconvergent fanouts and/or correlated inputs, has a worst-case complexity that is exponential in the numbers of dependent reconvergent fanouts and correlated inputs. By leveraging the fact that many large circuits consist of common logic modules, a modular approach that hierarchically decomposes a circuit into smaller modules and subsequently applies the accurate PGM algorithm to each module, is further proposed. Simulation results are presented for applications on the LGSynth91 and ISCAS85 benchmark circuits. It is shown that the modular PGM approach provides highly accurate results with a moderate computational complexity. It can further be embedded into an early design flow and is scalable for use in the reliability evaluation of large circuits.     

基于SOR-PCG的低复杂度信号检测算法研究

针对最小均方误差信号检测算法复杂度随着天线数量增加呈指数增长的问题,提出低复杂度的预处理共轭梯度信号检测算法.该算法通过灵活调整松弛因子,运用预处理技术降低矩阵条件数,从而加快共轭梯度信号检测算法的收敛速度.仿真结果显示,该算法在小数量的迭代中能够达到和最小均方误差检测算法相似的误码率,算法复杂度下降了一个数量级.通过选择适当的松弛因子,相比直接用共轭梯度法,能够更快收敛到最佳值.     

The effect of DON'T CARES on the complexity of combinational circuits

This letter provides an interesting analysis of the number of DON'T CARES required to reduce the complexity of combinational circuits. An equation relating the number of ones in the output of a combinational function and the number of DON'T CARES required to reduce circuit complexity by 10 percent is given.     

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.     

一种降低接收机复杂度的差分空时调制方案

基于对角信号的差分酉空时调制技术不需要信道估计并能实现满天线分集,但接收机的计算复杂度与发射天线数和数据率成指数关系。该文针对发射天线数为偶数的系统,提出了一种降低接收机计算复杂度的差分空时调制方案。该方案将发射天线分成相等数目的两组并在每一组天线上分别进行对角酉空时调制,接着构造差分编码矩阵使得两个对角信号的最大似然检测可以分开进行,从而大大降低了接收机的计算复杂度。理论分析和仿真表明,该方案仍实现了满天线分集,并且对于某些应用环境能提供比对角信号更好的误比特率性能。     

Resynthesis of combinational logic circuits for improved path delayfault testability using comparison units

We propose a resynthesis method that modifies a given circuit to reduce the number of paths in the circuit and thus improve its path delay fault testability. The resynthesis procedure is based on replacing subcircuits of the given circuit by structures called comparison units. A subcircuit can be replaced by a comparison unit if it implements a function belonging to the class of comparison functions defined here. Comparison units are fully testable for stuck-at faults and for path delay faults. In addition, they have small numbers of paths and gates. These properties make them effective building blocks for resynthesis to improve the path delay fault testability of a circuit. Experimental results demonstrate considerable reductions in the number of paths and increased path delay fault testability. These are achieved without increasing the number of gates, or the number of gates along the longest path in the circuit. The random pattern testability for stuck-at faults remains unchanged     

基于关键链路预测的动态路由和波长分配算法

 光网络中的路由和波长分配 （RWA）算法是NP难问题. 目前的解决方案大多是基于启发式算法或图论的,其计算复杂度往往随着网络规模的增加呈指数增长,而且链路阻塞概率建模也十分困难. 本文提出了一种基于“关键链路”预测机制的RWA算法,并综合考虑跳数和空闲波长数的因素,不仅通过链路层面,而且也从网络层面来解决RWA问题. 实验结果表明我们的算法可以实现很好的流量负载均衡和低的阻塞率,具有较小的计算复杂度.     

A low-complexity sequential Monte Carlo algorithm for blind detection in MIMO systems

In statistical signal processing, the sequential Monte Carlo (SMC) method is powerful and can approach the theoretical optima. However, its computational complexity is usually very high, especially in multiple-input multiple-output (MIMO) systems. This paper presents a new low-complexity SMC (LC-SMC) algorithm for blind detection in MIMO systems, the main idea of which is to shrink the sampling space via channel estimation which is initialized using the first differentially modulated symbol and then updated using the Monte Carlo samples. Since the a posteriori probability of the transmitted symbols can be calculated separately by each transmit antenna, the proposed LC-SMC algorithm is not only computationally efficient, as compared to the original SMC whose complexity grows exponentially with the number of transmit antennas, but also makes blind turbo receiver more feasible for multilevel/phase modulations. Simulation results are presented to demonstrate the effectiveness of the LC-SMC algorithm.