Analyzing Circuit with Noisy Gates

From The Circuits and Biology Lab at UMN

1 Analyzing Circuit with Unreliable Gates

Analyzing Circuit with Unreliable Gates

The problem with nanometer-scale devices

As nanometer-scale CMOS device continues to shrink, there will be many challenges brought by the future devices, which are not encountered today. One of the challenges is the reliability of the circuit built with future devices. The shrinking of nanometer-scale devices will make them suffer from more errors than the classical silicon devices used today. Generally, the errors of devices can be split into permanent and transient errors. Permanent errors may be introduced by manufacturing process and occur during the lifetime of the system. Transient errors will occur because future devices are much more sensitive to external influences, such as cosmic radiation, electromagnetic interference, thermal fluctuations, etc.

Modeling different kinds of device error

In general, there are three major types of device error. Assume that a gate $g i$ should compute the function $f i (x, y)$ if no error occurs. The three types of error are:

The output of the gate is the complement of the expected value (termed a flip fault) : $g_i(x,y) = \bar{f_i}(x,y)$ .
The output of the gate is a fixed value (termed a stuck-at fault): $g_i(x,y) = v\,$ for some $v \in \{0, 1\}$ .
The output of the gate is the value of one of its inputs (termed a pass fault): $g_i(x,y) = x\,$

Suppose the probaiblity of the occurrence of error is $\varepsilon$ . We can model each type of error by introducing an extra gate and a control signal $p i$ with probability $1-\varepsilon$ to be logical 1. Without loss of generality, suppose that our circuit consists of NAND gates. For flip faults, we introduce an extra XOR gate, as shown in Figure 1. For stuck-at faults, we include $p i$ directly in the NAND gate, as shown in Figure 2. For pass faults, we introduce an extra MUX gate, as shown in Figure 3. When $p i = 1$ , the gate outputs correctly. Otherwise, it fails.

Image:Prob-flip.tiff

Figure 1: Modeling a flip fault.

Image:Prob-stuck-at.tiff

Figure 2: Modeling a stuck-at 1 fault.

Image:Prob-pass.tiff

Figure 3: Modeling a pass fault.

Analyzing the Reliability of Circuit built with Unreliable Gates

When circuit is built with unreliable gates, the output of the circuit will not always be the expected correct value. We can use the probability of the circuit output to be correct as a measure of the reliability of the circuit. There are many different circuits implementing a given Boolean function, but their reliability may differ greatly. Therefore, in the future design, the reliability of the circuit is another important factor to be considered, besides traditional consideration on circuit area, timing, power dissipation, etc.

Our research is on how to analyze the reliability of a given combinational circuit. To simplify the problem, we only consider flip fault. Besides, we suppose that each gate has the same probability $\varepsilon$ to fail and fails independently.

The calculation of reliability is done in two step. First, we calculate the probability of the circuit output to be logical 1, based on the modeling of flip fault. We first replace each gate in the circuit with the block modeling the flip fault shown in Figure 1 and build a transformed circuit. In the transformed circuit, each gate is perfect--i.e., always behaves correctly, but the input signals are stochastically to be logical 1. The block control signal $p i$ has probability of $1-\varepsilon$ to be logical 1. The original input signals are determined either to be logical 1 or 0, and correspondingly, they have probability of either 1 or 0 to be logical 1. Then, the problem of calculating output probability to be 1 is essentially a problem to obtain the expression computed by a stochastic logic system. Using the method proposed to analyze stochastic logic system, we can obtain the symbolic expression of the probability of the output of the faulty circuit to be 1.

In the second step, we add the output of the original perfect circuit and the output of the transformed circuit to a XNOR gate. Then the probability of the output of the faulty circuit to be correct (i.e., reliability) is equal to the probability of the XNOR gate to be 1. Again, we can use the method proposed to analyze stochastic logic system to get the expression of the reliability with arguments of primary inputs and control inputs $p i$ . Finally, we set each $p i$ as $1-\varepsilon$ and get the symbolic expression of the reliablity with arguments of primary inputs of the circuit.

An improved method

In the previous method, the number of arguments in the expression equals to number of primary inputs plus the number of gates in the circuit. A more efficient way to calculate the reliability is achieved by reducing the number of arguments in the expression. In this method, we get the expression which is the result of the first step in an output to input direction, serially replacing each argument $g i$ in function with $\varepsilon + (1-2\varepsilon) F(a,b)$ (here $F (a, b)$ is the function computed by single gate whose output is $g i$ ) and normalizing it until the function has all of its arguments as primary inputs.