武藤 佳恭

The circuit of the maximum neural network based on the switched capacitor technique is proposed. The performance of the proposed circuit was derived from SPICE simulation. The bipartite subgraph problem is solved by using the proposed circuit. The SPICE simulation result confirms the function of the network. Because the complexity of the proposed analog circuit is so small, it is possible to fabricate an optimization system in a single chip.

A novel computational model for large-scale maximum clique problems is proposed and tested. The maximum clique problem is first formulated as an unconstrained quadratic zero-one programming and it is solved by minimizing the weight summation over the same partition in a newly constructed graph. The proposed maximum neural network has the following advantages: (1) coefficient-parameter tuning in the motion equation is not required in the maximum neural network while the conventional neural networks suffer from it; (2) the equilibrium state of the maximum neural network is clearly defined in order to terminate the algorithm, while the existing neural networks do not have the clear definition; and (3) the maximum neural network always allows the state of the system to converge to the feasible solution, while the existing neural networks cannot guarantee it. The proposed parallel algorithm for large-size problems outperforms the best known algorithms in terms of computation time with much the same solution quality where the conventional branch-and-bound method cannot be used due to the exponentially increasing computation time.

The max cut problem, one of the NP-complete problems, was chosen to test the capability of an artificial neural network. The algorithm based on the maximum neural network was tested by 1000 randomly generated examples, including up to 300 vertex problems. The simulation result shows that the proposed parallel algorithm using the maximum neural network generates better solutions than Hsu's algorithm within one hundred iteration steps, regardless of the problem size.

A PC-based multilayer neural network with sigmoid activation function, generalized delta learning rule and error back-propagation was trained with two individual components (protonated and unprotonated form) of pH dependent spectra between 400 and 700 nm generated from microspectrophotometry of Neutral Red (NR). The NR spectrum changes from one resembling the acid to one resembling the base as the solution's pH changes from acid to base. The number of nodes in the input layer was based on the degree of resolution required. The number of hidden layer units was related to the storage capacity and could be a function of maximum connection weight between input and the hidden layer. The number of output nodes determined the step size used to distinguish the input spectrum. Teaching patterns are binary encoded to compare to the activity in the output layer. Simulation results show that after successful convergence with the training spectra features of the input spectrum are separated and stored in the weight matrix of the input and hidden layers. A calibration curve can be constructed to interpret the output layer activity and therefore allow prediction of the pH. With its intrinsically redundant presentation, this novel approach to spectrophotometry needs no preprocessing procedures (baseline correction and extensive signal averaging) for spectral identification. Spectral distortion, e.g. due to light scattering effects, such as between phosphate buffer solutions and brain homogenates do not affect the outcome. This method was applied to the in vitro hippocampal slice preparation to measure anoxic pHi changes. The method can be generalized to adapt to any pattern oriented sensory information processing and multi-sensor fusion for quantitative measurement.

This article points out that our parallel algorithm provides the maximum planar subgraph and it is compared with the maximal planar subgraph provided by Jayakumar et al. in the above paper. The space-time product complexity is also compared. © 1991 IEEE

A parallel algorithm for solving the 'Hip' games based on an artificial neural network model is presented in this paper. The game of 'Hip' is named because of the hipster's reputed disdain for 'squares'. The rule of the game is to place the counters on a checkerboard so that four of them do not mark the corners of a square. The square may be of any size and be tipped at any angle. Normally this game is played by two players, where the game on a six-by-six checkerboard is the maximum size for the solution. The solution means that every player can place all the counters on the checkerboard without violations. In other words, the goal of our algorithm is to find the pattern of a draw game between players where they should not mark the corners of a square. In order to enlarge the size of the checkerboard where a solution exists, we modified the game as n/2 players play on an n-by-n checkerboard where n is an even number. The proposed parallel algorithm requires m × n processing elements for the m-player-n-by-n-checkerboard game to find the solution of the 'Hip' games. The algorithm is verified by solving six games where the size of the checkerboard is varied from 4 to 12. © 1991. 2

A new neural network parallel algorithm for sorting problems is presented in this paper. The proposed algorithm using O(n2) processors requires two and only two steps, not depending on the size of the problem, while the conventional parallel sorting algorithm using O(n) processors proposed by Leighton needs the computation time Oog/i). A set of simulation results substantiates the proposed algorithm. The hardware system based on the proposed parallel algorithm is also presented in this paper. © 1990 IEEE

A parallel algorithm for estimating the secondary structure of an RNA molecule is presented in this paper. The mathematical problem to compute an optimal folding based on free-energy minimization is mapped onto a graph planarization problem. In the planarization problem we want to maximize the number of edges in a plane with no two edges crossing each other. To solve a sequence of n bases, n(n - 1)/2 processing elements are used in our algorithm. © 1990 Springer-Verlag.

A parallel algorithm based on neural networks for solving sorting problems is presented. The proposed algorithm uses O(n ) processing elements called binary neurons, where n is the number of unsorted elements. It requires two and only two iteration steps, while the conventional parallel sorting algorithm using (On) processors proposed by F. T. Leighton (1984) requires the computation time O(log n). A set of simulation results substantiates the proposed algorithm. The hardware system based on the proposed parallel algorithm is also presented. 2

A parallel algorithm for finding a near-maximum independent set in a circle graph is presented. An independent set in a graph is a set of vertices, no two of which are adjacent. A maximum independent set is an independent set whose cardinality is the largest among all independent sets of a graph. The algorithm is modified for predicting the secondary structure in ribonucleic acids (RNA). The proposed system, composed of an n neural network array (where n is the number of edges in the circle graph or the number of possible base pairs) not only generates a near-maximum independent set but also predicts the secondary structure of ribonucleic acids within several hundred iteration steps. Our simulator discovered several solutions which are more stable structures, in a sequence of 359 bases from the potato spindle tuber viroid (PSTV), than the formerly proposed structures. The simulator was tested in solving other problems. © 1990 IEEE

A McCulloch-Pitts neuron is the simplified neuron model which has been successfully used for many optimisation problems. The neural network with the hysteresis property can suppress the oscillatory behaviours of neural dynamics so that the convergence time is shortened. In this paper, digital CMOS layout design of the hysteresis McCulloch- Pitts neuron is presented. Based on simulation results using the hysteresis McCulloch-Pitts binary neuron model, a 6-bit fixed point 2's complement arithmetic was adopted for the calculation of the input U of each neuron. Each neuron needs 204 transistors and requires a 399 λ x 368 λ layout area using the MOSIS scalable CMOS/bulk (SCMOS) VLSI technology with 2μm rule of P well, double level metal. Layout design of the hysteresis McCulloch-Pitts neuron chip was completed, and fabrication of the chip and the design for the test circuit for the fabricated CMOS VLSI chip are underway at present. © 1990, The Institution of Electrical Engineers. All rights reserved.

A parallel algorithm for tiling with polyominoes is presented in this paper. The tiling problem is to pack polyominoes in a finite checkerboard. The algorithm using 1 x m x n processing elements requires O (1) time where l is the number of different kinds of polyominoes on an m x n checkerboard. The algorithm can be used for placement of components or cells in a very large scale integrated circuit (VLSI) chip, designing and compacting printing circuit boards, and solving a variety of 2-D or 3-D packing problems. © 1990 IEEE

A parallel and stochastic version of Hopfield-like neural networks is presented. Cauchy color noise is assumed. The specific noise is desirable for fast convergence to a fixed point representing a neighborhood minimum. It can be quickly quenched at each iteration according to a proven cooling schedule in generating random states on the energy landscape. An exact Cauchy acceptance criterion is analytically derived for hill-climbing capability. The improvement is twofold: a faster cooling schedule (the inversely linear cooling schedule characterized by the Cauchy simulated annealing) and parallel executions of all neurons. Such a Cauchy machine can be electronically implemented, and the design is given.

Summary form only given, as follows. A new parallel distributed processing architecture called an entropy machine (EM) is proposed. This machine, which is based on an artificial neural network composed of massive neurons and interconnections, is used for solving a variety of NP-complete optimization problems. The EM performs either the parallel distributed gradient descent method or gradient ascent method to search for minima or maxima.

A near-optimum parallel planarization algorithm is presented. The planarization algorithm, which is designed to embed a graph on a plane, uses a large number of simple processing elements called neurons. The proposed system, composed of an N×N neural network array (where N is the number of vertices), not only generates a near-maximal planar subgraph from a nonplanar graph or a planar graph but also embeds the subgraph on a single plane within 0(1) time. The algorithm can be used in multiple-layer problems such as designing printed circuit boards and routing very-large-scale integration circuits.

Fuzzy inference engines based on the existing fuzzy theory are inadequate to perform reliable decision making. Besides requiring the fuzzy sets and data to be normalized, the inference engine is also sensitive to noise in observational data. Inaccurate conclusions are produced if noise is present and also when the fuzzy sets are not normalized. In this paper, a new term 'similarity' (σ) and the method to compute σ to enhance the capability of fuzzy set theory for application in expert systems is introduced. Even though the complexity of the hardware engine is slightly increased, it actually reduces the overhead of computation by eliminating the need for normalization of fuzzy data. With reliable fuzzy data manipulation, it is easy to extend to a multi-dimensional membership function which has a wider scope of applications. To To implement the Very Large Scale Integration fuzzy inference engine, two general schemes of the hardware architecture that van be easily reconfigured to satisfy given performance requirements are discussed. © 1989.

A statistical learning model called the multinomial conjunctoid is reviewed. Multinomial conjunctoids are based on a well-developed, statistical-decision-theory framework, which guarantees that conjunctoid learning will converge to optimal states over learning trials and the learning will be fast during these trials. In addition, a prototype multinomial conjunctoid module based on CMOS VLSI technology is introduced.

Neural networks have been studied for many years with the hope of achieving human-like performance in such fields as speech and image recognition. A recent resurgence has resulted from VLSI advances, neural network models, and learning algorithms. Neural networks are also very suitable in certain areas such as NP-complete constraint and satisfaction problems, due to the nature of parallel and distributed processing. Neural network models are composed of a mass of fairly simple computational elements and rich interconnections between the elements. Neural networks operate in a parallel and distributed fashion which may resemble biological neural networks. Behaviors of neurons and the strengths of synaptic interconnections are simulated by operational amplifiers and resistors respectively. Several examples are presented, including how to build neural network components based on analog circuits for simulating neural networks and conventional logic circuits.

An application of neural networks is presented for solving job-shop scheduling, an NP-complete optimization problem with constaint satisfaction. In particular, the authors introduce a neural computation architecture based on a stochastic Hopfield neural-network model. First, the job-shop problem is mapped into a two-dimensional matrix representation of neurons similar to those for solving the traveling salesman problem (TSP). Constant positive and negative current biases are applied to specific neurons as excitations and inhibitions, respectively, to enforce the operation precedence relationships. At the convergence of neural network, the solution to the job-shop problem is represented by a set of cost function trees encoded in the matrix of stable states. Each node in the set of trees represents a job, and each link represents the interdependency between jobs. A computation circuit computes the total completion times (costs) of all jobs, and the cost difference is added to the energy function of the stochastic neural network. Using a simulated annealing algorithm, the temperature of the system is slowly decreased according to an annealing schedule until the energy of the system is at a local or global minimum. By choosing an appropriate annealing schedule, near-optimal and optimal solutions to job-shop problems can be found.

The authors introduce a neural computation architecture based on a stochastic Hopfield neural network model for solving job-shop scheduling. A computation circuit computes the total completion times (costs) of all jobs, and the cost difference is added to the energy function of the stochastic neural network. Using a simulated annealing algorithm, the temperature of the system is slowly decreased according to an annealing schedule until the energy of the system is at a local or global minimum. By choosing an appropriate annealing schedule, near-optimal and optimal solutions to job-shop problems can be found. The architecture of the system is diagrammed at both the functional and circuit levels. Simulation results are presented.

This paper describes analog and digital multinomial conjunctoid modules that are currently under silicon fabrication using a MOSIS program based on CMOS technology. The digital multinomial conjunctoid module is featured, but digital and analog modules are compared as well. The feasibility of large scale multinomial machines are discussed. Designs for parameter estimation modules and indispensable digital components are also given.

In this paper a rule-based Lisp dialect translator using paramodulation is presented as an example of a general purpose program translator application where the knowledge about the translation is embedded in rules. The advantage of using a rule-based system is to allow the user to supply his own rules for translation, thus the translator can be considered as a general purpose converter. Also, the rule-based LDT has the ability to test individual rules for correctness to aid in rule development. The translation being used for development is Franz to Common Lisp. © 1988.

A general family of fast and efficient neural network learning modules for binary events is introduced. The family subsumes probabilistic as well as functional event associations; subsumes all levels of input/output association; yields truly parallel learning processes; provides for optimal parameter estimation; points toward a workable description of optimal model performance; and yields procedures that are simple and fast enough to be serious candidates for reflecting both neural functioning and real time machine learning. Examples as well as operational details are provided. © 1988.

In its first 40 years the neural network learning (NNL) movement has produced an impressive array of learning models. We introduce a general family of fast and efficient NNL learning modules for binary events called 'conjunctoids', which employ an appropriate framework from probability theory; adapt a class of recently developed conjunctive models from psychometric theory; tailor sound statistical estimation and evaluation schemes to fit NNL learning needs; and allow VLSI implementations.

We explore the applications of binary neurons with analog conductance or communication links in solving large-scale NP-complete optimization problems such as the classical traveling salesperson problems (TSP) and job-shop scheduling. In particular, the energy function of J.J. Hopfield and D.W. Tank neural network model is reformulated so that the network is likely to converge to a proportional number of valid solutions as the size of problem scales up. G.V. Wilson and G.S. Pawley identified the reasons for failure on the Hopfield and Tank computation algorithm in their attempts to solve a 10-city TSP. K. Sheff and H. Szu proposed a necessary and sufficient condition based on binary neurons and traceless energy for a Hopfield and Tank network to converge to stable states. In this paper, we study the effectiveness of this fast neural network convergent scheme through two case studies: an n-job m-machine job-shop problem and an N-city TSP.

An error-correcting system based on neural circuit techniques is presented. This system is expected to perform significantly faster than conventional error-correcting systems based on logic gate designs. Two example circuits demonstrate how the neural error-correcting system works.

A simple example of (7,4) codes for one-bit error correction is shown. However the proposed neural model can be expanded to multiple-bit error correction. Generally an (N,K) neural decoder of this type will require 2**k op amps, an N multiplied by 2**k resistor network, 2**k comparators, and an N multiplied by 2**k diode network. This error-correction model is effective in a severe environment such as control or military equipment's.

A neural-based scheme for pattern recognition and construction of three-dimensional images from partial cues is presented. Clusters of neural nets operating concurrently are used to learn and recall patterns at X, Y, Z planes. Simulations are performed based on a Hopfield-like network to investigate the effect of learning trials and firing percentage of nodes per cycle. A method for computing the common features of input patterns is given. Results showed that maximum parallel processing can be achieved.

A general-purpose cross assembler named gpca using Franz Lisp on a VAX11/750 with Berkeley Unix BSD4. 2 was developed. All the user has to do is to provide rule lists to a rule-database for code generation. The rule-based technique used in the gpca can enhance the productivity for developing cross assemblers for 4-, 8-, 16-, and 32-bit microprocessors in a short period of time through the rule independency. The implemented cross-assembler is composed of database management routines, lexical pattern matching routines, and a few other routines. The cross assembler, which is small enough to be understood completely by the user, has a flexibility and an expandability in terms of user extensible pseudo-operations and macro functions.

Authors propose parallel/pipelined and parallel/iterative spanning tree generators for directed and undirected graphs based on graph theory algorithms using adjacency matrices. A generator employing iterative logic circuits with high regularity suitable for VLSI implementation can be realized with O(n**2) gates where n is the number of nodes in a given graph. This generator can compute a spanning tree of an nXn adjacency matrix within O(n**2) gate delays. The organizations of spanning tree generators are discussed.

The yield of chips tends to decrease with the degree of integration of memory chips, which is presently a serious problem. A method is proposed to utilize the fault chips being discarded to produce a normal chip, increasing the apparent yield. The relation between the yield and the reliability of the fault memory chip system is discussed. Using the proposed method, the yield of 10% can be improved up to 40% without substantially decreasing the reliability of the fault chip memory system from that of a normal memory chip. The method was implemented using fault 16 K RAM, and the effectiveness of the method was verified.

This paper presents a design scheme that supplies logic circuits with very high reliability by providing redundancy to gate function logic using conventional gates. The basic redundant logic circuits are called Fault-Tolerant Gates (FTGs). The construction and design of FTGs, such as AND, OR, NOT, NAND, NOR and Exclusive OR gates, are described. The improved reliability of these FTGs is evaluated in comparison with conventional gates.