Recursive Learning Madhurima Maddela, Student Member, IEEE Auburn University, Auburn, AL 36849, USA Abstract —Previous test generators for combinational and sequential circuits used a decision tree to systematically explore the search space while trying to generate a test vector. Recursive learning was introduced as an interesting alternative. Using recursive learning, sufficient depth of recursion during the test generation process guarantees that implications are performed precisely, i.e., all necessary assignments for fault detection are identified at every stage of the algorithm so that no backtracks can occur. But its applications were not just restricted to test vector generation. This method helped make significant progress in redundancy identification, logic verification, boolean satisfiability and logic synthesis to name a few areas. This paper attempts to describe the concept in detail and illustrate it with a few examples. Index Terms — Recursive Learning, Boolean satisfiability. I. INTRODUCTION Recursive learning can be understood as a general method to conduct a logic analysis deriving a maximum amount of information about a logical circuit in a minimum amount of time. First introduced in [1] and [2] and further developed in [3] and [4], learning is defined to mean the temporary injection of logic values at certain signals in the circuit to examine their logical consequences. By applying simple logic rules, certain information about the current situation of value assignments can be known. The problems of test generation, verification and optimization are inter-related [5] - [6] and NP complete [7]. Test generation for combinational circuits has been viewed as an implicit enumeration of an n-dimensional Boolean search space, where n is the number of primary input signals. Traditionally, a decision tree is used to branch and bound through the search space until a test vector has been generated or a fault has been proven redundant. However, it is the nature of this classical searching technique that it is often very inefficient for hard-to-detect and redundant faults; i.e. in those cases where only few or no solutions exist. Recursive learning presents a new technique that can handle these pathological cases in test generation much more efficiently than the traditional search. Boolean satisfiability (SAT) is intrinsic to many problems in Electronic Design Automation (EDA). In most cases, the problem formulation starts from a circuit description, for a given (circuit) property that needs to be validated for at least one primary input vector. The resulting circuit formulation, which may only be implicitly specified, is then mapped into an instance of SAT, in most cases using Conjunctive Normal Form (CNF) formulas. This allows the usage of existing and extensively validated algorithms instead of dedicated ones. But mapping can take up a good percentage of the running time and computed input patterns are in general over specified. These problems can be overcome using recursive learning. Section II describes the concept of recursive learning in good detail. Section III gives an insight into combinational test pattern generation with an example. Section IV describes an example to illustrate the use of recursive learning in CNF formulae. Section V briefly covers other different promising applications of recursive learning to verification and synthesis problems. II. OVERVIEW OF RECURSIVE LEARNING While performing logic synthesis of a circuit, some assignments of signal values are found to be necessary; i.e. those assignments can be implied in any way and therefore they must be satisfied for the given combination of value assignments. Other assignments are optional and their assignment represents a decision in the decision tree. Significant progress has been made especially in redundancy identification; however, all these techniques are limited in that they fail to produce all necessary assignments. Recursive learning can provide for this completeness. For example, traditional test generation is a search for one sufficient solution whereas recursive learning may be viewed as searching for those conditions that enable purging the non-solution area from the search space. Recursive learning is not restricted to any particular logic alphabet and can be used for any logic value system such as five-valued logic, nine-valued logic or sixteen-valued logic. Also, the learning routines can be called recursively and thus provide for completeness. The maximum recursion depth determines how much is learned about the circuit. The time complexity of this method is exponential in the maximum depth of recursion rmax. Memory requirements however grow linearly with rmax. As noted earlier, any methods that identify all necessary assignments must be exponential in time complexity because this problem is NP complete. Some formal definitions of terms are presented below. Def. 1 uses a common notation of a specified signal by which we understand a signal with a fixed value. In a five-valued logic,),,,1,0(5XDDB =, a signal is specified if it has one of the values 0, 1, D or D. It is unspecified if it has the value X. [4]2Def.1: Given a gate G that has at least one specified input or output signal. Gate G is called unjustified if there is at least one or several unspecified input or output signal combinations of G for which it is possible to find a combination of value assignments that yields a conflict at G. Otherwise G is called justified. The concept of unjustified gates can be used to give a definition of precise implications and necessary assignments. Def.2: For a given circuit and a given situation of value assignments, let f be an arbitrary but unspecified signal in the circuit and V be some logic value. If all consistent combinations of value assignments for which no unjustified gates are left in the circuit contain the assignment f = V, then the assignment f = V is called necessary for the given situation of value assignments. Implications are called precise or complete when they determine all necessary assignments for a given situation of value assignments. Unjustified gates describe the locations where learning has to be performed. The next definition determines what signal values have to be injected at the unjustified gates in order to perform learning. Def.3: A set of signal assignments, J = (f1=V1, f2=V2… fn=Vn), where f1, f1,… fn are unspecified input or