یادگیری طاس اندازی با استفاده از الگوریتم های ژنتیکی و اکتشافی برای سنتز منطق و به حداقل رساندن داده های ناقص مشخص شده با تعمیم اشکال رید مولر

This research applies a new heuristic combined with a genetic algorithm (GA) to the task of logic minimization for incompletely specified data, with both single and multi-outputs, using the Generalized Reed–Muller (GRM) equation form. The GRM equation type is a canonical expression of the Exclusive-Or Sum-of-Products (ESOPs) type, in which for every subset of input variables there exists not more than one term with arbitrary polarities of all variables. This AND–EXOR implementation has been shown to be economical, generally requiring fewer gates and connections than that of AND–OR logic. GRM logic is also highly testable, making it desirable for FPGA designs. The minimization results of this new algorithm tested on a number of binary benchmarks are given. This minimization algorithm utilizes a GA with a two-level fitness calculation, which combines human-designed heuristics with the evolutionary process, employing Baldwinian learning. In this algorithm, first a pure GA creates certain constraints for the selection of chromosomes, creating only genotypes (polarity vectors). The phenotypes (GRMs) are then learned in the environment and contribute to the GA fitness (which is the total number of terms of the best GRM for each output), providing indirect feedback as to the quality of the genotypes (polarity vectors) but the genotype chromosomes (polarity vectors) remain unchanged. In this process, the improvement in genotype chromosomes (polarity vectors) is the product of the evolutionary processes from the GA only. The environmental learning is achieved using a human-designed GRM minimization heuristic. As much previous research has presented the merit of AND–EXOR logic for its high density and testability, this research is the first application of the GRM (a canonical AND–EXOR form) to the minimization of incompletely specified data.

Natural systems are extremely well adapted to their environments. In nature the structure of all organisms has been designed to provide the capability of solving a multitude of complex problems for both survival and growth, through instinctual, experiential, and intellectual means. Over the millennia, it is these capabilities that have proven an effective method of sustaining the existence and propagation of natural organisms. Even as environmental conditions change, it is the continuous adaptation of natural organisms adjusting to their environment, through evolutionary processes, which sustains life. As nature itself has proven its development of robust system design, the biologically inspired evolutionary process is here applied to the minimization of incompletely specified digital hardware circuits in the Generalized Reed–Muller (GRM) form. Genetic Algorithm (GA) [15] techniques provide a means for applying the theory of evolution within an artificial system. The GA is a system that evolves problem parameters directly. Through a process of emergent intelligence, the GA formulates engineering solutions based on an accumulated knowledge of the problem and the merit of potential solutions. In recent years, the GA, as a machine learning technique, has been successfully applied to a wide range of engineering problems. However, with the realization of computer-designed algorithms, only limited research to date has applied these concepts to digital logic [11] and [13]. Our past experience has shown the GA application to logic minimization to have limitations of size, computation time, and solution optimality [7] and [8]. In comparison, several decades of research have contributed to the current human understanding and efficient implementation of systems for logic design and minimization. Most of the current human-aided design tools utilize AND–OR design implementations for both logic synthesis and minimization, for simplicity, readily available minimization tools, and because of historical reasons in the development of digital systems. However, since AND and EXOR components exist in most ASIC libraries, they can be employed either in a CLB of an FPGA or in a full custom VLSI design. While not as widely utilized for integrated circuit design as the AND–OR Sum-of-Product (SOP) logic, the Exclusive-Or Sum-of-Product (ESOP) form (the most general, unrestricted AND–EXOR logic form) compares favorably [40]: Functions realized by such circuits (ESOPs) can have fewer gates, fewer connections, and take up less area in VLSI and especially, FPGA realizations. They are also easily testable [14] and [28]. It was shown, both theoretically and experimentally [31], [33], [34], [35] and [38] that ESOPs have on average smaller numbers of terms for both `worst case' and `average' Boolean functions. It was also shown that ESOPs and all their sub-families have their counterparts in logic with multi-valued inputs… Additionally, recently two-level AND–EXOR realizations (ESOPs) have even been proposed for the combinational logic portions of finite state machines, as they have proven more testable and can yield less area than two-level AND–OR implementations [21]. Thus, it can be concluded that the AND–EXOR implementation is in many applications superior to the AND–OR logic, for both its testable and economical characteristics [21], [36], [37] and [39]. AND–EXOR logic already serves as a good alternative basis for FPGA designs, by achieving denser logic than AND–OR implementations. Because any function of a certain number of inputs can be realized in a logic block of an FPGA, for example, the costs of realizing a 5-input OR and a 5-input EXOR in Xilinx technology are the same. (Note that FPGAs may use logic look-up tables to realize AND–EXOR combinations in multi-level circuits, thus avoiding the architectural design restrictions imposed by other AND–OR-based logical devices [44]. However, this is at the expense of not employing the two-level, AND–EXOR physical hardware implementation, which realizes the high testability quality of this class.) AND–EXOR logic has also been used in full custom VLSI chip design of data path logic, arithmetic circuits, controllers with embedded counters and adders, and easily testable circuits. For several industrial applications, specialized AND–EXOR tools serve for such designs as preprocessors for standard factorization and decomposition in EDA tools from commercial companies. It is interesting to note that binary AND–EXOR logic represents a special case of Galois Field logic [1] and [41], GF(k), where the radix k=2. Thus, Galois logics can be viewed as a generalization or expansion of Boolean logic, as Galois Field mathematical operations are applicable for multi-valued logic values, over any finite field. Hence, in this manner, the minimization technique presented herein may be expanded, in the future, for a multi-valued logic hardware or data mining application. Further, as two-level AND–EXOR logic is the most highly testable of all digital logics [26], it is a good candidate for engineering design [12], [20], [21], [27], [29] and [32]. A testing method for ESOP circuits, which include the GRM, FPRM, and PPRM forms, is given by Kalay et al. [20] as: …a simple, universal test set which detects all single stuck-at faults in the internal lines and the primary inputs/outputs of the realization… (the) circuit realization requires only two extra inputs for controllability and one extra output for observability. The cardinality of our test set for an n input circuit is (n+6)… This test set can also be very successfully applied to Built-in Self-Test (BIST) applications. Further, Kalay et al. [19] have also devised a two-level design and minimal-universal test set for the more general Galois Field SOP (GFSOP) form GF(kr). The GFSOP is analogous to the ESOP as the most general functional representation of its type. Thus, for both the binary and multi-valued logic cases, it is evident that the two-level AND–EXOR logic family is highly testable with a very limited number of test vectors. Concluding, currently basic research and CAD tool application to the various AND–EXOR forms is increasingly at the forefront of the logical research and development frontier, both in industry and academia. The AND–EXOR form has been developed into a complete hierarchy of Reed–Muller (RM) expansions, using the Shannon, Positive Davio, and Negative Davio Expansions [37]. This hierarchy is described with logic equation forms, trees, and decision diagrams [37]. The GRM form is the focus of this research. The GRM logic is a canonical expression (exhibiting a regular structure) which is a subset of the ESOP expression, in which for every subset of input variables there exists at most one term with any polarities of variables. In other words, each term in the GRM is unique in both variable name and polarity. It is interesting to note that often GRM forms may produce results with the number of terms very close to that of exact minimum ESOPs [3], [25], [39] and [46]. GRM forms are also even more easily testable than the general-purpose ESOPs [36]. Herein an original automated technique of GRM form logic minimization for incompletely specified data is developed with evolutionary processes. But in this method, a multi-strategic approach is taken. Human expertise is combined with the genetic search mechanism, for the development of an efficient problem-solving expert system. The goal of using the GA for GRM minimization is simply to aid the human-designed logic minimization heuristic. Other research has shown the GRM equation form to be difficult to minimize for the case of completely specified data, both using heuristics [4] and [5] and GAs [7] and [8]. However, an application combining heuristics and GAs has not been previously applied to the GRM minimization problem. Also there have been no applications of the GRM equation form for the minimization of incompletely specified data. Hence, in summary, several concepts have contributed to this research. The GRM is a powerful form, for its canonical, economical (compact logic), and high testability properties. Several industrial companies are already using AND–EXOR logic (together with AND–OR logic). Thus, AND–EXOR logic should be applied not only to completely specified data, but to incompletely specified data as well, which is the more typical case for real-world applications. Logic synthesis and minimization with this form can be easily combined with the natural, evolutionary mechanisms employed by the simple (pure) GA. Together, all of these approaches are utilized by a logic minimization heuristic, which is based on human experience. This methodology is implemented with software and is the first application of the GRM form for the synthesis and minimization of incompletely specified data. This approach is applicable for traditional computer-automated digital design and synthesis, as well as off-line Evolvable Hardware. But, it is also notable that, as the minimization technique is equally applicable for a large number of don't cares (strongly unspecified data) and multi-valued logic, characteristic of real-world machine learning problems, it is also applicable to software applications such as Knowledge Discovery/Data Mining.

Herein a GA utilizing Baldwinian learning, to incorporate both a human-designed logic heuristic and a pure GA, is applied to illustrate iGRMMIN, the first algorithm that minimizes incompletely specified data with GRM forms. As the AND–EXOR logic is generally more economical than AND–OR logic, requiring fewer logic gates and interconnections, it is often a good alternative form for logic design. (Recall that modern EDA tools first decompose the circuit to AND–OR and AND–EXOR realizable blocks). The GRM forms were selected for this research since they are a good trade-off between cost and high testability [21]. The software implementation of the iGRMMIN minimization algorithm was tested over a number of benchmarks. Since incompletely specified benchmarks are not available, they were constructed. Starting with completely specified MCNC benchmarks, a given percentage of outputs were randomly selected for changing to don't cares. These new benchmarks are available from our research group's web site at www.ee.pdx.edu/polo/function/MCNC_incompletely_specified. Minimization test results are given for benchmarks containing 25%, 50%, 75%, and 95% don't cares. Since no other minimization software for incompletely specified data with GRMs exists, no comparisons are made. The future extension of this new algorithm to multi-valued logic, using Galois Field algebra [1] and [41], is possible. Additional methods for the improvement of the heuristic generation of GRMs are presented in [9]