Research on Error Diagnosis Method in Circuit Based on Symbolic Simulation

　　Error diagnosis is a very important stage in the later stage of integrated circuit verification. It helps designers predict the error points in an error chip, thus reducing the workload of the entire debugging process. After many years of research, error diagnosis of combinational circuits is becoming mature and practical. These methods are mainly divided into two categories: simulation-based methods and symbolic methods. In the simulation-based method, the area containing error points is gradually limited by filtering out non-error points in the simulation of each error vector on the circuit. Symbolic methods do not need to explicitly list error vectors, but mainly rely on binary decision diagrams (BDDs) and propose sufficient and necessary conditions for locating error sources. Based on this sufficient and necessary condition, the error point can be directly located. Since this method uses BDD technology, there is a hidden danger of memory explosion.

　　Boppana proposed a generalized region-based model for error diagnosis, which can be extended to locate multiple errors and can be used to solve the error diagnosis of sequential circuits. Shi-Yu Huang proposed using symbolic simulation to optimize the process of Byzantine error diagnosis. Boppana introduced a diagnosis algorithm based on Xlists simulation. N. Sridhar proposed a diagnosis technique that eliminates error candidate areas through distinguishable Xs. Li Guanghui introduced an error diagnosis method based on verification technology, which combines three-value simulation with SAT technology to reduce the error space and improve the diagnosis results.

　　Here, a method using symbolic simulation technology to optimize the regional model-based error diagnosis process is proposed. The method first uses the circuit partitioning method in the regional model-based error diagnosis method to divide the circuit to be diagnosed into regions, and then uses symbolic simulation technology on this basis and uses two measurement criteria to rank the suspiciousness of each region. The more suspicious the region is, the more likely it is to contain an error point. Since the symbolic simulation technology is used, there is no need to explicitly list the vector space, so the proposed method is time-efficient.

　　1 Definition

　　Here, the specification and implementation are represented as C1 and C2, respectively, where the implementation is represented as a combined gate-level circuit. The main input (PI) signals of the specification and implementation are both represented as {x1, x2, …, xm), where m represents the number of main inputs. The main output (PO) signals of the specification and implementation are represented as {S1, S2, …, Sn} and {I1, I2, …In}, respectively, where n represents the number of main outputs. In addition, assume that the set of pre-generated test vectors is T = {v1, v2, …, vt}.

　　Definition 1 (Si, Ii) is called an output pair, where 1≤i≤n.

　　Definition 2 If there is an input test vector v such that when v simulates the specification and the implementation circuit respectively, the output Ii of the implementation circuit is different from the value of the corresponding output Si in the specification, Ii is called an error output or mismatch output, and (Si, Ii) is a mismatch output pair.

　　Definition 3 If an input vector can cause a mismatch between any output pair, the input vector is called an error input vector.

　　Definition 4 The processing of a mismatch output Ii involves a mechanism that injects binary values ​​into certain signals in the implementation to make the response of Ii the same as the output response corresponding to it in the specification.

　　Error diagnosis is based on a concept called curability. In the process of searching for error candidates, in order to rank the suspicion of each signal, two measurements are required for each signal: the number of treatable outputs and the number of treatable vectors.

　　Definition 5 Assume that the i-th main output of the implemented circuit is a mismatched output under the simulation of the error input vector v. Let A be a region with k outputs {a1, a2, ..., ak}. If the mismatch at the main output Ii can be corrected by an injection combination at {a1, a2, ..., ak}, then Ii is called a curable output of the region A under the simulation of v, and is symbolically represented by Ii∈region_curable_output(A, v).

　　This definition shows that the mismatched output appearing in C2 can be corrected by processing a regional output. The processing method here is to inject certain binary values ​​at the regional output point. It is known from experience that the more curable outputs a region has, the more likely it is to be a region containing error points, because changes to the output values ​​of this region will affect more mismatched outputs. In addition, in addition to this measurement standard, a measurement standard called the curable vector can be used to further effectively check the error points.

　　Definition 6 If each mismatched output generated by the implementation circuit C2 under the simulation of an error input vector v can be corrected by an injection combination at the output {a1, a2, ..., ak} of region A at the same time, and no new mismatched output will be generated, then this error input vector v is called a curable vector of region A, and is symbolically represented by Ii∈region_curable_vector(A). If such an injection exists, it is called a curable injection of region A.

　　Based on these two measurement criteria, combined with the sorting criterion, the suspicion of each region is ranked. The sorting criterion is as follows: the region with more curable vectors has a greater suspicion of becoming a candidate for error. For regions with the same number of curable vectors, their number of curable outputs is considered, that is, the curable vector is used as the first-level measurement criterion and the curable output is considered as the second-level measurement criterion.

　　2 Introduction to regional model

　　Definition 7 The distance between any gate element g in a circuit and its direct fan-in gate or direct fan-out gate is called a structural distance.

　　Definition 8 Given d as a fixed structural distance and g as any gate element of the circuit, the region with g as the center and d as the radius is the set D(g) = {h|dis(g, h) ≤ d}.

　　For example, the region with radius 1 around gate g includes g, g's direct fan-out and its direct fan-in. Each gate in the circuit can form a region, so there are as many overlapping regions as there are gates in the circuit. The regional model-based diagnosis method introduced in reference [3] is that during the simulation process, all output nodes in the region are first set to unknown values ​​X to mask any errors occurring in the region. If for a given vector v, no X can propagate to a primary output, it can be determined that vector v cannot detect any errors in the region; otherwise, it means that there is an error in the region and the region is taken as an error candidate.
　3 Symbolic simulation optimization process

　　Next, we will introduce how to apply symbolic simulation technology to the regional model and calculate whether v is a treatable vector in region A when the error input vector v is simulated for the specification and implementation circuits. In addition, it is necessary to determine how many treatable outputs the region has under the simulation of v. The calculation is divided into four main steps: error-free logic simulation, symbol injection, symbol propagation and curability check.

　　Error-free logic simulation simply establishes the error-free logic value of each signal line under the simulation of the input vector v. The other three steps discussed below are proposed for the regional model hierarchy.

　　3.1 Symbol injection

　　First, the output of the region to be considered is disconnected from the connection between the regions, then these output signal lines are extracted, and each of them is regarded as a pseudo-primary input. Finally, a symbol variable xj is injected into each output terminal aj, where 1≤j≤k, k is the number of outputs of region A. Note: Every signal in the fan-out area of ​​A output will be affected by the injected variable. Figure 1 shows the basic situation of the circuit before and after the symbol injection.

　3.2 Symbol Propagation

　　The role of symbol injection is to assign values ​​to the signals in the fan-out area output by area A by propagating the function toward the main output direction. The process of symbol propagation is similar to the process of error simulation, except that the value of a signal in symbol propagation is no longer a logical value 0/1, but a Boolean function represented by the injected Boolean variable {x1, x2, ..., xk}. Figure 2 shows the symbol propagation process.


Two techniques can be used to speed up the symbol propagation process. One is the use of ordered binary decision diagrams (OBDDs), and the other is event-driven simulation. The use of BDDs may cause memory explosion, but here the above memory explosion problem is avoided because the diagnostic process does not require the global function of the characterized circuit. In event-driven simulation, many gate elements do not need to be re-simulated because they are not affected by symbol injection. Therefore, in a single run of symbol propagation, the CPU processing time will not increase rapidly due to the increase in circuit size.

　　3.3 Treatable Check

　　At the end of the symbol propagation process, a Boolean function can be obtained for each major output of the implemented circuit, called the action function. An action function contains information about how it reacts to an injection of the region output {a1, a2, …, ak}. By obtaining this information, the number of treatable inputs and treatable outputs in the region can be calculated.

　　Definition 9 Let Ii be the i-th major output. v is an error input vector, and A is an error candidate region to be checked. After vector v simulates the implementation circuit and performs symbol injection and symbol propagation processes on the output of region A, the action function of Ii is expressed as Reacti(v, a, X), where X is the set of Boolean variables {x1, x2, …, xk} used when performing symbol injection.

　　Proposition 1 The error input vector v is a treatable vector of region A if and only if the following equation holds. Si(v) represents the i-th output response of the norm under the simulation of vector v, and n is the total number of outputs.

　
It is proved that if there exists an injection combination of {x1, x2, ..., xk}, so that after injection, for each primary output index i, the response of the implemented circuit Reacti(v, a, X) is the same as the response value of the specification Si(v), then the injection combination is called a regionally treatable injection. It is also proved that the combination injected at the output of region A makes the error input vector v no longer cause any mismatch between output pairs, that is, v is no longer an error input vector of the implemented circuit.

　　If there exists an injection combination that makes the logical value of a mismatched output become exactly the same as its corresponding value, then the mismatched output is called a regionally treatable output (rule of regionally treatable output): If the following conditions are met, then for vector v, a mismatched output Zic is called a treatable output through the regional output signal a.


For example (Region Treatable Injection) Consider the specification and implementation in the figure. Under the simulation of an input vector v, the output response of the specification is (0, O, 0, 0, 0), while the implemented response is (0, 0, 0, 1, 1). The fourth and fifth outputs are mismatched outputs. By performing symbol injection and propagation, the set of each main output action function is {0, 0, x3, x1, (x1x2)'}.

　　The first two output pairs are matched, so only the treatability check of the last three outputs is performed. In order to check the treatable vector, the injection must satisfy (x3=0), (x1=0) and [(x1x2)'=0]. Because the second and third conditions conflict with each other, it can be concluded that region A cannot be treated with erroneous input vector v by injection.

　
On the other hand, each action function is checked for the treatable output. Before injection, only the 4th and 5th mismatched outputs need to be focused on. The action function of the 4th output is x1. Only by making x1 0 during injection can the output change from 1 to 0, that is, the mismatch problem of the 4th output is solved by this method, so the 4th output is a treatable output. Similarly, the 5th output is also a treatable output. Therefore, there are two treatable outputs in this area A. In this example, the two mismatched outputs can be treated and corrected independently; however, when treating the last output, a new mismatch problem will inevitably be introduced at the 3rd output point, which is why the given error input vector cannot be treated and corrected through area A. Symbolic simulation technology can be used to optimize the process of error diagnosis based on regional models. According to the two measurement criteria of regional treatable vector and regional treatable output, the candidate regions are ranked according to the suspicious level of containing error points. The higher the suspicious level, the more likely it is that the region contains an error point.

　　4 Experimental Results and Conclusions

　　Here, several simple combinational circuits are selected, and a gate permutation error is randomly injected into each circuit. Symbolic simulation technology is used to perform error diagnosis on each circuit. From the perspective of the CPU time of the method execution, the optimization method proposed here does not always run faster than the original regional model-based method, but overall, because the optimization method greatly reduces the number of candidate regions to be processed, the total running time is still relatively ideal.

　　Here, a new method is proposed to apply symbolic simulation technology to the error diagnosis method based on the regional model. This method uses symbolic simulation technology to process the candidate regions, including three steps: symbol injection, symbol propagation, and treatability check. In addition, part of the processing information obtained after processing the region by symbolic simulation can be applied to the subsequent error correction process, which is not available in the original regional model-based method. The error diagnosis method using symbolic simulation can also be extended to circuits with multiple errors, but further research and implementation are needed.