論文

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.

Summary form only given, as follows. A neural network model for traffic controls in multistage interconnection networks is discussed. The goal of the neural network model is to find conflict-free traffic flows to be transmitted among given I/O traffic demands in order to maximize the network throughput. The model requires n2 processing elements for the traffic control in an n × n multistage interconnection network. The model runs not only on a sequential machine but also on a parallel machine with maximally n2 processors. The model was verified by solving ten 32 × 32 network problems.

Summary form only given. A novel scheduling approach has been developed based on the deterministic Hopfield model for high-level synthesis. The model uses a four-dimensional neural network architecture to schedule the operations of a dataflow graph and maps them to specific functional units. Neural network-based scheduling is achieved by formulating the scheduling problem in terms of an energy function and by using the motion equation corresponding to the variation of energy. The algorithm searches the scheduling space in parallel and finds the optimal schedule. The main contribution of the present work is an efficient scheduling algorithm under time and resource constraints. The algorithm is based on moves in the scheduling space, which correspond to moves towards the equilibrium point (lowest energy state) in the dynamic system space. The neurons' motion equation is the heart of this guided movement mechanism and guarantees that the state of the system always converges to the lowest energy state.

This paper presents a general purpose algorithm for solving the Unfriendly Beehive Game. The proposed algorithm will utilize an artificial neural network to solve the problem. The neural network will use a simple partial differential (motion) equation expressed in terms of its natural constraints. Each constraint within the equation represents a simple connection to an artificial neuron. Each connection strength (or synaptic strength) is weighted by multiplicative constants and summed together. The result is an input that is adjusted in the direction that decreases the error or conflict. Using this information, the system derives a simple binary state output in an attempt to solve the puzzle. Given an overall time slot in which to resolve all conflicts, the system iteratively strives to arrive at the state of the global minimum. The proposed algorithm will be able to solve a variety of real-world problems, including: facility layouts for maximizing productivity and safety, classroom assignment for minimizing pupil conflict, crop and plant placement for maximizing yields, and chemical placement within shipping boxes to reduce the possibility of chemical interactions.

A parallel algorithm for finding Ramsey numbers is presented where analog/digital CMOS circuits for the hysteresis McCulloch-Pitts binary neuron are described. The hysteresis McCulloch-Pitts binary neuron model is used in order to suppress the oscillatory behaviors of neural dynamics so that the convergence time is shortened. The proposed algorithm using the hysteresis McCulloch-Pitts binary neuron found five Ramsey numbers. The analog CMOS sigmoid circuit with variable gain controls has been fabricated and tested using the SAC data acquisition board interfaced with a TMS 32010 processor. Hysteresis can be implemented by the positive feedback in the fabricated CMOS analog circuit.

The purpose of this research was to develop a noise tolerant and faster processing approach for in vivo and in vitro spectrophotometric applications where distorted spectra are difficult to interpret quantitatively. A PC based multilayer neural network with a sigmoid activation function and a generalized delta learning rule was trained with a two component (protonated and unprotonated form) pH-dependent spectrum generated from microspectrophotometry of the vital dye neutral red (NR). The network makes use of the digitized absorption spectrum between 375 and 675 nm. The number of nodes in the input layer was determined by the required resolution. The number of output nodes determined the step size of the quantization value used to distinguish the input spectra (i.e. defined the number of distinct output steps). Mathematic analysis provided the conditions for which this network is guaranteed to converge. Simulation results showed that features of the input spectrum were successfully identified and stored in the weight matrix of the input and hidden layers. After convergent training with typical spectra, a calibration curve was constructed to interpret the output layer activity and therefore, predict interpolated pH values of unknown spectra. With its built-in redundant presentation, this approach needed no preprocessing procedures (baseline correction or intensive signal averaging) normally used in multicomponent analyses. The identification of unknown spectra with the activities of the output layer is a one step process using the convergent weight matrix. After learning from examples, real time applications can be accomplished without solving multiple linear equations as in the multiple linear regression method. This method can be generalized to pattern oriented sensory information processing and multi-sensor data fusion for quantitative measurement purposes.

A maximum neuron model is proposed in order to force the state of the system to converge to the solution in neural dynamics. The state of the system is always forced in a solution domain. The artificial maximum neural network is used for the module orientation problem and the bipartite subgraph problem. The usefulness of the maximum neural network is empirically demonstrated by simulating randomly generated massive nstances (examples) in both problems. In randomly generated more than one thousand instances our system always converges to the solution within one hundred iteration steps regardless of the problem size. Our simulation results show the effectiveness of our algorithms and support our claim that one class of NP-complete problems may be solvable in a polynomial time.

The application of the Hopfield neural network for the multispectral unsupervised classification of MR images is reported. Winner-take-all neurons were used to obtain a crisp classification map using proton density-weighted and T2-weighted images in the head. The preliminary studies indicate that the number of iterations needed to reach 'good' solutions was nearly constant with the number of clusters chosen for the problem.

A system architecture and a network computational approach compatible with the goal of devising a general-purpose artificial neural network computer are described. The functionalities of supervised learning and optimization are illustrated, and cluster analysis and associative recall are briefly mentioned.

Neural network parallel computing for balanced incomplete block design (BIBD) problems is presented. A design in which all the blocks contain the same number of varieties, and all the varieties occur in the same number of blocks, is called a block design. A block is said to be incomplete if it does not contain all the varieties. If a design is balanced, it is called a balanced incomplete block design. Two methods for BIBD problems have been proposed. One uses the notion of the finite fields, and the other uses the notion of the difference sets. In general, the conventional algorithms are only able to solve the problems that satisfy an affine plane or a finite projective plane. The proposed algorithm is able to solve BIBD problems regardless of the condition of an affine plane or a finite projective plane. The proposed algorithm was verified by simulation runs. The simulation results demonstrated that the number of iteration steps for the system to converge to the solution increases slightly with the problem size.

A new parallel processing algorithm for solving string search problems is presented. The proposed algorithm uses O(m × n) processors where n is the length of a text and m is the length of a pattern. It requires two and only two iteration steps to find the pattern in the text, while the best existing parallel algorithm needs the computation time O(loglog n).

Several neuron models and artificial neural networks have been intensively studied since McCulloch and Pitts proposed the simplified neuron model in 1943. In this paper a generalized maximum neural network for parallel computing is introduced to solve the module orientation problem which belongs to the class of NP-complete problems. The goal of the module orientation problem in VLSI circuits or printed circuit boards is to minimize the total wire length by flipping each module with respect to its vertical and/or horizontal axes of symmetry. The circuit diagram of the generalized maximum neural network is shown and compared with the best known algorithm proposed by Libeskind-Hadas and Liu. The theoretical/empirical convergence analysis is discussed where a massive number of simulation runs were performed using more than one thousand instances. As far as we have observed the behavior of the proposed system, it converges within O(1) time regardless of the problem size and it performs better than the best known algorithm in terms of the solution quality and the computation time.

A parallel algorithm based on a neural network model for solving clique vertex-partition problems in arbitrary non-directed graphs is presented in this paper. A clique of a graph G = (V, E) with a set of vertices V and a set of edges E is a complete subgraph of G where any pair of vertices is connected with an edge. A clique vertex-partition problem of a graph G is to partition every vertex in V into a set of disjointed cliques of G. The clique vertex-partition problem with the minimum number of cliques in an arbitrary graph is known to be NP-complete. The algorithm requires nm processing elements for the n vertex m partition problem. A total of 10 different problems with 8 vertex to 300 vertex graphs were examined where the algorithm found a solution in nearly constant time. The circuit diagram of the neural network model is also proposed in this paper.

The authors propose the first parallel improvement algorithm using the maximum neural network model for the bipartite subgraph problem. The goal of this NP-complete problem is to remove the minimum number of edges in a given graph such that the remaining graph is a bipartite graph. A large number of instances have been simulated to verify the proposed algorithm, with the simulation result showing that the algorithm finds a solution within 200 iteration steps and the solution quality is superior to that of the best existing algorithm. The algorithm is extended for the K-partite subgraph problem where no algorithm has been proposed.

In manufacturing memory chips, Redundant Random Access Memory (RRAM) technology has been widely used because it not only provides repair of faulty cells but also enhances the production yield. RRAM has several rows and columns of spare memory cells which are used to replace the faulty cells. The goal of our algorithm is to find a spare allocation which repairs all the faulty cells in the given faulty-cell map. The parallel algorithm requires In processing elements for the n x n faulty-cell map problem. The algorithm is verified by many simulation runs. Under the simulation the algorithm finds one of the near-optimum solutions in a nearly constant time with 0(n) processors. The simulation results show the consistency of our algorithm. The algorithm can be easily extended for solving rectangular or other shapes of fault map problems. Reader Aids - Purpose: Present a new algorithm Special math needed for explanations: Probability Special math needed to use results: None Results useful to: Reliability theoreticians and analysts.

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.

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 × n2 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.

A neural network model for broadcasting scheduling in multihop packet radio networks is presented. The problem of broadcast scheduling with a minimum number of time slots is NP-complete. The proposed neural network model finds a broadcasting schedule with a minimal number of time slots where it requires n processing elements for an n-node radio network. Fifteen different radio networks were examined where the neural network model found an m-time-slot solution in O(m) time with n processors.

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 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.