Abstract Affine equivalence of Boolean functions has various applications in computer science and modern cryptography, such as circuit design and S-boxes. Existing methods for detecting affine equivalence of Boolean functions work in some cases but not when the truth table of a Boolean function is sparse. To improve previous methods and overcome this limitation, we propose a method by transforming the Boolean function to a function with the property that its function values at the orthonormal basis are all equal to 1 or 0, which narrows down the search space of affine transformations. Our first algorithm has the advantage of getting a smaller search space than previous methods and is especially useful for sparse functions. Specifically, when the Boolean functions are sparse, the search space can be reduced exponentially in average and experiments show the efficiency of our first algorithm. We then present another algorithm to transform one circuit into its equivalent affine circuit by synthesizing a reversible circuit and inserting it in front of the original circuit. To our knowledge, this is the first work to automatically synthesize an affine equivalent circuit for any given circuit and the first to do this by combining reversible circuit and non-reversible circuit.

This paper describes a CMOS-memristive programmable logic device connected to CMOS XOR gates (mPLD-XOR) for realizing multioutput functions well suited for two-level {NAND, AND, NOR, OR}-XOR-based design. This structure is a generalized form of AND–XOR logic where any combination of NAND, AND, NOR, and OR, and literals can replace the and level. For mPLD-XOR, the computational delay, which is measured as the number of clock cycles, equals the maximum number of inputs to any output XOR gate of a function assuming that the number of XOR gates is large enough to calculate the outputs of the function simultaneously. The input levels of functions are implemented with novel programmable diode gates, which rely on the diode-like behavior of self-rectifying memristors, and the output levels of functions are realized with CMOS modulo-two counters. As an example, the circuit implementation of a 3-bit adder and a 3-bit multiplier are presented. The size and performance of the implemented circuits are estimated and compared with those of the equivalent circuits realized with stateful logic gates. Adding a feedback circuit to the mPLD-XOR allows the implementation of a multilevel XOR logic network with any combination of sums, products, XORs, and literals at the input of any XOR gate. The mPLD-XOR with feedback can reduce the size and number of computational steps (clock cycles) in realizing logic functions, which makes it well suited for use in communication and parallel computing systems where fast arithmetic operations are demanding.

This paper formulates the generic Machine Learning (ML) problem into finding the simplest spectral transform form (i.e. one having as many zero coefficients as possible) for an (in)complete binary function. The classical binary logic synthesis problem can be modeled to minimize a single output Boolean function with a two-level structure consisting of an exclusive-OR (EXOR) of ANDs of literals. The innovative approach in this paper is to build and simulate an accelerator that reduces learning to find the exact minimum expression of all 3n Kronecker Reed Muller (KRO) forms of a Boolean function with n input variables. This is in contrast to the previously studied quantum algorithm for the Fixed Polarity Reed-Muller forms (FPRM) which only selects from 2n possible forms. The algorithm, based on repeated application of a ternary Grover's Quantum Search algorithm, was simulated to find the minimum KRO form using a hybrid ternary/binary quantum oracle. This hybrid quantum system was simulated in Matlab and proved to be correct. The method can be also used as a future Quantum EDA Tool for exact minimization of AND/EXOR circuits, including reversible and quantum circuits.

A novel algorithm is proposed in this study for improving the accuracy and robustness of human biometric identification using electrocardiograms (ECG) from mobile devices. The algorithm combines the advantages of both fiducial and non-fiducial ECG features and implements a fully automated, two-stage cascaded classification system using wavelet analysis coupled with probabilistic random forest machine learning. The proposed algorithm achieves a high identification accuracy of 99.43% for the MIT-BIH Arrhythmia database, 99.98% for the MIT-BIH Normal Sinus Rhythm database, 100% for the ECG data acquired from an ECG sensor integrated into a mobile phone, and 98.79% for the PhysioNet Human-ID database acquired from multiple tests within a 6-month span. These results demonstrate the effectiveness and robustness of the proposed algorithm for biometric identification, hence supporting its practicality in applications such as remote healthcare and cloud data security.

In this paper we present improvements to the cost of quantum circuits implemented with 2n-lines circuit implementation. The 2n-line circuit implementation is intended for the linear nearest neighbor quantum circuits and implements any quantum circuits in such manner that they can be directly mapped to quantum implementations. In this paper we propose a replacement strategy for 2- and 3-qubit patterns detected on the control lines. It is demonstrated that application of this strategy leads to a considerable reduction of circuit cost.

The paper presents new logic synthesis methods for single-output incomplete multi-level binary circuits using Memristor-based material implication gates. The first method follows Lehtonen's assumption of using only two working memristors. The algorithm minimizes the number of implication (IMPLY) gates, which corresponds to minimizing the number of pulses or the delay time. This greedy search method uses essential and secondary essential primes, does not require solving the covering problem, is fast, and produces high quality results. We compare it to other synthesis methods, such as the modified SOP and Exclusive-Or Sum of Products (ESOP) with minimum number of working memristors. We analyze the problem of reduction in IMPLY gate count by adding more working memristors and introduce Imply Sequence Diagrams, a new notation, similar to one used in reversible logic.

This article presents an algorithm which can quickly find the exact minimum solution to almost all of 4-bit reversible functions. We assume minimization of quantum cost (MQC). This algorithm is designed in the most memory-efficient way, or it will quickly run out of memory. Therefore, we construct the shortest coding of permutations, the topological compression and flexible data structures for the memory savings. First, hash tables are used for all 8-gate 4-bit circuits with the minimization of gate count (MGC) by using the GT library (with NOT, CNOT, Toffoli and Toffoli-4 gates). Second, we merge and split the hash tables, thus generating a single longer hash table for high-performance. Third, we synthesize these circuits with MQC by using the GTP library (with GT, Peres, and Inverted Peres gates) based on the hash table. Finally, according to the comparison of the QC of circuits, the algorithm can quickly converge for any 4-bit reversible circuit with MQC. By synthesizing all benchmark functions, in comparison with Szyprowski and Kerntopf [2011], the running time and QC are reduced up to 99.95% and 18.2%, respectively.

The design of state machines for quantum algorithms remains a largely unexplored topic. The abstract models for quantum computation proposed by Feynman [1], Deutsch [2] etc have been related to the theory of Quantum Turing Machines (QTM) and the work was later expanded by Bernstein and Vazirani [3] to lay the foundations of quantum complexity theory. However, no papers deal with the following problem: “how to realize the quantum state machine in hardware as an operational quantum circuit that the internal states of which can be measured and used as inputs in a system of such machines”. This is an equivalent to the fundamental problem of “structural synthesis of FSM”. This paper creates models of quantum state machines that are useful from an engineering perspective. The objective of the paper is to propose models that can be used for circuit-level implementation. We restrict our study to binary logic realized in quantum, the so-called binary permutative quantum circuits; the “permutative machines”. The presented synthesis procedure is analogous to classical logic circuits synthesis and is a necessary step in the entire design procedure of quantum automata. Thus state minimization, state assignment and excitation function realization aspects are also of interest and some preliminary experimental results are presented.

It has been experimentally proven that realizing universal quantum gates using higher-radices logic is practically and technologically possible. We developed a Parallel Genetic Algorithm that synthesizes Boolean reversible circuits realized with a variety of quantum gates on qudits with various radices. We describe the experiments that we conducted using GPU programming. Various approaches to fitness function formulation were applied to obtain various realizations of well known universal Boolean reversible quantum gates.

In this paper, we propose the concepts that apply quantum circuits to model Fuzzy Sets, thereby creating a new method to model behaviors for a humanoid robot. It is similar to the standard fuzzy sets from two points of view -1) of measured probabilities of state |1〉, and 2) that of the normalized measurement in a quantum ensemble computer. However, one can also look at the internal quantum states created by the operators of the new model. This extends fuzzy sets from [0, 1] interval to some other domain, similar to complex fuzzy logic, but also brings superposed, entangled and parallel quantum behaviors. The standard fuzzy logic aspect (external) of the new model maps the numbers in interval [0,1] to points on one meridian of the Bloch Sphere and after measurement, the results map back to numbers from interval [0,1]. However, the other, more important, aspect of this model (internal) is the operation on arbitrary quantum states, and the realization of additional states via phase measurements. We discuss and illustrate how this model can be used to represent a hidden state of reasoning agents or an emotional state of a humanoid robot.

Reversible logic has many applications such as Quantum computing, low power CMOS circuit design, Optical computing. Hence reversible logic synthesis has attracted attention especially in quantum computing community. A logic function is reversible if it is a one-to-one mapping between input and output vectors. In this paper we present a new approach to synthesis of reversible circuits using Kronecker Functional Lattice Diagrams. Unlike other contemporary algorithms for synthesis of reversible function that use n × n Toffoli gates, our method invariably synthesizes functions using only 3×3 Toffoli gates, Feynman gates and NOT gates. This reduces the quantum cost. Our method adds small cost by adding extra ancilla bits. Moreover, our circuits are always (4-neighbors) regular, which is an asset when they are mapped to 2-Dimensional arrays in Ion Trap (quantum) technology.

This paper investigates the synthesis of quantum networks built to realize hybrid switching circuits in the absence of ancilla qudits. We prove that all hybrid reversible circuits can be constructed by hybrid Not and Multiple-Controlled-Not gates. We also prove that any hybrid reversible circuit with only 1 or 2 binary qudits and arbitrary number of other qudits, can be constructed by hybrid Not and Controlled-Not gates. We present two construction-based algorithms to synthesize hybrid reversible circuits without ancilla qudits. The algorithms use hybrid Not and Multiple-Controlled-Not gates or hybrid Not and `1'-Controlled-Not gates, which are exponentially lower than breadth-first search based synthesis algorithms with respect to the input number.

In this paper we present an evolutionary approach to the quantum symbolic logic synthesis. We use a genetic algorithm to synthesize quantum circuits from examples, allowing to synthesize functions that are both completely and incompletely specified. The symbolic synthesis is implemented in the GA so as to verify our approach. The Occam Razor principle, fundamental to inductive learning as well as to logic synthesis, is satisfied in this approach by seeking circuits of reduced complexity. The GA is tested on a set of benchmark functions representing single output quantum circuits as well as multiple entangled-qubit state generators.

Reversible circuits play an important role in quantum computing, which is one of the most promising emerging technologies. In this paper, we investigate the problem of optimally synthesizing 4-bit reversible circuits. We present an enhanced bi-directional synthesis approach. Owing to the exponential nature of the memory and run-time complexity, all existing methods can only perform four steps for the Controlled-Not gate NOT gate, and Peres gate library. Our novel method can achieve 12 steps. As a result, we augment the number of circuits that can optimally be synthesized by over 5 × 106 times. We synthesized 1000 random 4-bit reversible circuits. The statistical analysis result supports our estimation. The quantum cost of our result is also better than the quantum cost of other approaches. The promising experimental results demonstrate the effectiveness of our approach.

Recent research in generalizing quantum computation from 2-valued qudits to d-valued qudits has shown practical advantages for scaling up a quantum computer. A further generalization leads to quantum computing with hybrid qudits where two or more qudits have different finite dimensions. In both cases, a quantum computation is performed when a unitary evolution operator, acting as a quantum logic gate, transforms the state of qudits in a quantum system. Unitary operators can be represented by unitary matrices, and therefore for a quantum system consists of multiple qudits, a gate may be synthesized by matrix decomposition techniques such as QR factorization and the Cosine-sine Decomposition (CSD). In this article, we present a CSD based synthesis method for n qudit hybrid and d-valued quantum circuits.

This paper presents a constructive synthesis algorithm for any n-qubit reversible function. Given any n-qubit reversible function, there are N distinct input patterns different from their corresponding outputs, where N les 2n, and the other (2n- N) input patterns will be the same as their outputs. We show that this circuit can be synthesized by at most 2nldrN '(n - 1)'-CNOT gates and 4n2ldr N NOT gates. The time complexity of our algorithm has asymptotic upper bound O(n ldr 4n). The space complexity of our synthesis algorithm is also O(n ldr 2n). The computational complexity of our synthesis algorithm is exponentially lower than the complexity of breadth-first search based synthesis algorithm.

This paper proposes an approach to optimally synthesize quantum circuits by symbolic reachability analysis, where the primary inputs and outputs are basis binary and the internal signals can be nonbinary in a multiple-valued domain. The authors present an optimal synthesis method to minimize quantum cost and some speedup methods with nonoptimal quantum cost. The methods here are applicable to small reversible functions. Unlike previous works that use permutative reversible gates, a lower level library that includes nonpermutative quantum gates is used here. The proposed approach obtains the minimum cost quantum circuits for Miller gate, half adder, and full adder, which are better than previous results. This cost is minimum for any circuit using the set of quantum gates in this paper, where the control qubit of 2-qubit gates is always basis binary. In addition, the minimum quantum cost in the same manner for Fredkin, Peres, and Toffoli gates is proven. The method can also find the best conversion from an irreversible function to a reversible circuit as a byproduct of the generality of its formulation, thus synthesizing in principle arbitrary multi-output Boolean functions with quantum gate library. This paper constitutes the first successful experience of applying formal methods and satisfiability to quantum logic synthesis.

We present fast algorithms to synthesize exact minimal reversible circuits for various types of gates and costs. By reducing reversible logic synthesis problems to group theory problems, we use the powerful algebraic software GAP to solve such problems. Our algorithms are not only able to minimize for arbitrary cost functions of gates, but also orders of magnitude faster than the existing approaches to reversible logic synthesis. In addition, we show that the Peres gate is a better choice than the standard Toffoli gate in libraries of universal reversible gates.

We propose an approach to optimally synthesize quantum circuits from non-permutative quantum gates such as controlled-square-root-of-not (i.e., controlled-V). Our approach reduces the synthesis problem to multiple-valued optimization and uses group theory. We devise a novel technique that transforms the quantum logic synthesis problem from a multi-valued constrained optimization problem to a group permutation problem. The transformation enables us to utilize group theory to exploit the properties of the synthesis problem. Assuming a cost of one for each two-qubit gate, we find all reversible circuits with quantum costs of 4, 5, 6, etc, and give another algorithm to realize these reversible circuits with quantum gates.

Ternary quantum circuits have recently been introduced to help reduce the size of multi-valued logic for multi-level quantum computing systems. However, synthesizing these quantum circuits is not easy. We describe a new genetic algorithm based synthesizer for ternary quantum circuits. Our results show some of the synthesized circuits use fewer gates than previously published methods.

Reversible quantum logic plays an important role in quantum computing. In this paper, we propose an approach to optimally synthesize quantum circuits by symbolic reachability analysis where the primary inputs are purely binary. we use symbolic reachability analysis, a technique most commonly used in model checking (a way of formal verification), to synthesize the optimum quantum circuits. We present an exact synthesis method with optimal quantum cost and a speedup method with non-optimal quantum cost. Both our methods guarantee the synthesizeability of all reversible circuits. Unlike previous works which use permutative reversible gates, we use a lower level library which includes non-permutative quantum gates. For the first time, problems in quantum logic synthesis have been reduced to those of multiple-valued logic synthesis thus reducing the search space and algorithm complexity. We synthesized quantum circuits for gate, half-adder, full-adder, etc. with the smallest cost.. Our approach obtains the minimum cost quantum circuits for Miller's gate, half-adder, and full-adder, which are better than previous results. In addition, we prove the minimum quantum cost (using our elementary quantum gates) for Fredkin, Peres, and Toffoli gates. Our work constitutes the first successful experience of applying satisfiability with formal methods to quantum logic synthesis.

For Part I, see 2nd NASA/DoD Workshop on Evolvable Hardware, pp.183-193 (July 2000). Describes an advanced self-testing, self-repair architecture and methodology for Lattice Logic Corp.'s GAL (generic array logic) devices, which are EPLDs (electrically programmable logic devices) that are used in high-security and safety applications, such as aerospace systems, military systems or medical instruments. We describe a new "column re-use" method that, if possible, exchanges a faulty GAL column with a column that needs the same programming as supplied by the faulty column and then reprograms the freed column to replace the faulty one. In contrast, our former self-repairing methodology, called the "column replacement method with extra columns", described Part I, just discarded each faulty column and replaced it with an extra column. Our evaluation methodology shows that the lifetime of a GAL that uses the 'column re-use' method is longer than the lifetime of a GAL that uses just the 'column replacement' method or the 'no self-repair' method. Our results also give information on how many extra columns a GAL needs to reach a lifetime goal, in terms of the simulation looping time, until the GAL is not useful any more. Our system is also applicable to other devices, such as FPGAs (field programmable gate arrays).

We propose a new BDD-based method for decomposition of multi-output incompletely specified logic functions into netlists of two-input logic gates. The algorithm uses the internal don't-cares during the decomposition to produce compact well-balanced netlists with short delay. The resulting netlists are provably non-redundant and facilitate test pattern generation. Experimental results over MCNC benchmarks show that our approach outperforms SIS and other BDD-based decomposition methods in terms of area and delay of the resulting circuits with comparable CPU time.

Reversible logic is of increasing importance to many future computer technologies. We introduce a regular structure to realize symmetric functions in binary reversible logic. This structure, called a 2*2 net structure, allows for a more efficient realization of symmetric functions than the methods introduced by the other authors. Our synthesis method allows us to realize arbitrary symmetric function in a completely regular structure of reversible gates with relatively little "garbage". Because every Boolean function can be made symmetric by repeating input variables, our method is applicable to arbitrary multi-input multi-output Boolean functions and realizes such arbitrary function in a circuit with a relatively small number of additional gate outputs. The method can also be used in classical logic. Its advantages in terms of numbers of gates and inputs/outputs are especially seen for symmetric or incompletely specified functions with many outputs.

A testable EXOR-Sum-of-Products (ESOP) circuit realization and a simple, universal test set which detects all single stuck-at faults in the internal lines and the primary inputs/outputs of the realization are given. Since ESOP is the most general form of AND-EXOR representations, our realization and test set are more versatile than those described by other researchers for the restricted GRM, FPRM, and PPRM forms of AND-EXOR circuits. Our 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). For Built-in Self-Test (BIST) applications, we show that our test set can be generated internally as easily as a pseudorandom pattern and that it provides 100 percent single stuck-at fault coverage. In addition, our test set requires a much shorter test cycle than a comparable pseudoexhaustive or pseudorandom test set.

This paper presents two new functional decomposition partitioning algorithms that use multivalued decision diagrams (MDDs). MDDs are an exceptionally good representation for generalized decomposition because they are canonical and they can represent very large functions. Algorithms developed in this paper are for Boolean/multivalued input and output, completely/incompletely specified functions with application to logic synthesis, machine learning, data mining and knowledge discovery in databases. We compare the run-times and decision diagram sizes of our algorithms to existing decomposition partitioning algorithms based on decision diagrams. The comparisons show that our algorithms are faster and do not result in exponential diagram sizes when decomposing functions with small bound sets.

Finding the minimum column multiplicity for a bound set of variables is an important problem in Curtis decomposi-tion. To investigate this problem, we compared two graph-coloring programs: one exact, and another one based on heuristics which can give, however, provably exact results on some types of graphs. These programs were incorporated into the multi-valued decomposer MVGUD. We proved that the exact graph coloring is not necessary for high-quality functional decomposers. Thus we improved by orders of magnitude the speed of the column multiplicity problem, with very little or no sacrifice of decomposition quality. Comparison of our experimental results with competing de-composers shows that for nearly all benchmarks our solu-tions are best and time is usually not too high.

In this paper we present a new data structure for representing multiple-valued relations (functions in particular) both completely and incompletely specified. The same format can be used for non-deterministic state machines (deterministic in particular). Relations are represented by labeled rough partitions, a structure similar to rough partitions, but storing the full information about relations and allowing for dynamic optimization of both memory requirements and processing time. We present experimental results from comparison of our data structure to Binary Decision Diagrams (BDDs) on binary functions (MCNC benchmarks) showing its superiority in terms of memory requirements in 73% cases. The new representation can be used to a large class of multiple-valued, completely and incompletely specified functions and relations, typical for Machine Learning (ML) and complex FSM controller optimization applications.

Generalized partially-mixed-polarity Reed-Muller (GPMPRM) expansion, a canonical subfamily of exclusive sum of products (ESOP), is presented. An efficient algorithm in two-dimensional data flow is proposed for computation of the GPMPRM forms. MCNC benchmark experimental results show that the minimal GPMPRM forms of these functions, on the average, have similar number of terms to their sum of products (SOP) counterparts while there are many functions for which the GPMPRM circuits are much smaller.

This paper presents a new operation (exorlink) and an algorithm to minimize Exclusive-OR Sum-of-Products expressions (ESOPs) for multiple valued input, two valued output, incompletely specified functions. Exorlink is a more powerful operation than any other existing one for this problem. Evaluation on benchmark functions is given and it proves the superiority of the program to those known from the literature.

This paper presents a concept and an implementation of a current-mode integrator based on the Miller effect. The circuit has a highly linear, no feedback, current path, implemented using a Gilbert amplifier cell, and a voltage feedback path with capacitors, realizing integration. A bipolar transistor array process with devices with an f/sub T/ of 8 GHz has been used for the circuit simulation. Phase response of -90/spl plusmn/0.5/spl deg/ has been obtained in the frequency range of 1 MHz to 670 MHz (the low-frequency pole can be tuned electronically down to about 3 Hz). Excess phase can be compensated electronically to obtain exactly -90/spl deg/ for any frequency in the entire useful range. The gain of the circuit can be tuned electronically over at least 40 dB. THD for 1 MHz is better than 0.052% for an output current of 2.8 mA/sub pp/, which represents 93% of the output tail current. DC gain of the circuit can be turned up to over 90 dB.

An efficient package for construction of and operation on ordered Kronecker Functional Decision Diagrams (OKFDD) is presented. OKFDDs are a generalization of OBDDs and OFDDs and as such provide a more compact representation of the functions than either of the two decision diagrams. In this paper basic properties of OKFDDs and their efficient representation and manipulation are presented. Based on the comparison of the three decision diagrams for several benchmark functions, a 25% improve ment in size over OBDDs is observed for OKFDDs.

This paper introduces a new design approach that combines logic and layout synthesis for Cellular-Architecture (CA) FPGAs. The comprehensive design method starts from a Boolean function, specified as SOP or ESOP, and produces a rectangularly-shaped multi-level structure of (mostly) locally connected cells. This twodimensional array of logic cells is well suited for CA-type FPGA realization. Two stages: restricted factorization and technology folding are discussed in more details. The architecture constraints and the implementation are presented for ATMEL6000 series architecture. 1.

The introduction of the multiplexer-based Actel FPGA series ACT resulted in an increased interest in multiplexer circuits. This paper introduces a level-by-level top-down minimization algorithm for them. The concept of a local transform is applied for the generalization of the ratio parameter method for M(1) multiplexer synthesis having one data select input and a spectral method for M(2) multiplexer synthesis to determine redundant multiplexer inputs for M(k) multiplexer circuits. The algorithm developed for multilevel synthesis of M(k) multiplexer circuits for incompletely specified multioutput Boolean functions takes advantage of the combination of spectral and Boolean methods. The obtained multiplexer circuit can be directly realized with FPGA's like the Actel ACT series or the CLi 6000 series from Concurrent Logic. A simple heuristic is applied to map an M(1) multiplexer circuit to the Actel ACT1 family.>

A quasi-minimal algorithm for canonical restricted mixed polarity (CRMP) AND/XOR forms is presented. These forms, which include the consistent and inconsistent generalized Reed-Muller (GRM) forms, are both very easily testable and, on average, have smaller numbers of terms than sum-of-product (SOP) expressions. The set of test vectors for detecting stuck-at and bridging faults of a function realized in CRMP forms, like that of consistent (GRM) forms, is independent of the function. This test can be of order (n+4)r, where n is the number of variables in the function and r is the number of component consistent GRMs in the CRMP. The experimental results confirm the compactness of CRMPs as compared to SOP expressions.>

A theory has been developed to calculate the Rademacher-Walsh transform from a cube array specification of incompletely specified Boolean functions. The importance of representing Boolean functions as arrays of disjoint ON- and DC-cubes has been pointed out, and an efficient new algorithm to generate disjoint cubes from nondisjoint ones has been designed. The transform algorithm makes use of the properties of an array of disjoint cubes and allows the determination of the spectral coefficients in an independent way. The programs for both algorithms use advantages of C language to speed up the execution. The comparison of different versions of the algorithm has been carried out. The algorithm and its implementation provide the fastest and most comprehensive program (having many options) known to the authors for the calculation of the Rademacher-Walsh transform. It successfully overcomes all drawbacks in the calculation of the transform from the design automation system based on spectral method-the SPECSYS system from Drexel University, which uses fast Walsh transform.>

An approach to automatic prediction and detection of ovulation is described. It is based on the application of image processing techniques to the cervical mucus fern test, a popular clinical diagnostic method. The sequence of histogram equalization, filtering, edge detection, binarization, labeling, thinning, Hough transform, and automatic pattern recognition in a feature space is applied to microscopic images of the ferning patterns. This method permits decisions to be made based on quantitative data instead of the subjective evaluations that are presently used.>

A program for the minimization of multi-output three-level Boolean networks from NAND gates of unlimited fan-in is described. This model includes don't care states. The algorithm is fast and creates good-quality approximate solutions, and its efficiency increases with the percentage of don't cares. It has been tried on about 40 Boolean functions of not more than 14 inputs, and yielded correct results. The realized circuits (on PLH501 and PLH502 PLDs) required up to 68% (on the average 35%) less gates than the corresponding PLAs. The program can consider tradeoffs between the solution-cost and the processing speed by using various type of the source data.>

A method for the minimization of multiple-valued input Boolean functions is presented. It is based on the reduction of logic minimization problem to graph coloring, applied to the graph of incompatibility of implicants. In this approach, two NP-complete problems encountered in the minimization of Boolean functions, i.e. the generation of prime implicants and the covering problem, are reduced to a single, and better understood, graph coloring problem. A special type of implicants, called minimally split product implicants, is generated from an arbitrary set of input cubes that allow optimum results to be obtained. An important result of this method is that it is analytical, rather than heuristic, and gives more insight into a larger class of logic synthesis problems, such as input encoding and Boolean decomposition.>