This paper presents an exact minimization algorithm for AND-OR-EXOR three-level networks, where a single two-input exclusive-OR (EXOR) gate is used. The network realizes an EXOR of two sum-of-products expressions (EX-SOP), where the two sum-of-products expressions (SOP) can share products. The objective is to minimize the total number of different products in the two SOPs. An algorithm for the exact minimization of EX-SOPs with up to five variables are shown. Up to five variables, EX-SOPs for all the representative functions of NP-equivalence classes were minimized. For five-variable functions, we confirmed that minimum EX-SOPs require up to 9 products. For n-variable functions, minimum EX-SOPs require at most 92n-5 (n6) products.

Our basic idea of generating random benchmark circuits, i.e., not generating them directly but applying random transformations to initial circuits was presented at DAC'94. In this paper we make the two major improvements towards the goal of random benchmarking: i.e., increasing the generality, the naturality, the security of random circuits: One is controlling fan-ins of logic gates in the random circuits, and the other is producing the initial circuit also at random but under some control of its on-set size and complexity. Experimental data claiming merits of those improvements are also given.

This work is targeted to understand the operating principle of the feedback type echo canceller for use in an FM broadcasting receiver and to study its compensating features and the effects of the practical operating environment on its performance. The effects of the tap interval and the compensation performance in the presence of an echo with excess delay 0 - 15 µs are examined. The results show that the tap interval should be selected according to the observable bandwidth of the channel transfer function and the performance of a feedback type echo canceller has a wavelike curve with respect to the excess delay of the echo. To improve the performance of the feedback type echo canceller, an adaptive echo canceller operating with CM algorithm is proposed and examined with computer simulation. The results show that the compensation performance is improved.

A neural network of massively interconnected digital neurons is presented for the total coloring problem in this paper. Given a graph G (V, E), the goal of this NP-complete problem is to find a color assignment on the vertices in V and the edges in E with the minimum number of colors such that no adjacent or incident pair of elements in V and E receives the same color. A graph coloring is a basic combinatorial optimization problem for a variety of practical applications. The neural network consists of (N+M) L neurons for the N-vertex-M-edge-L-color problem. Using digital neurons of binary outputs and range-limited non-negative integer inputs with a set of integer parameters, our digital neural network is greatly suitable for the implementation on digital circuits. The performance is evaluated through simulations in random graphs with the lower bounds on the number of colors. With a help of heuristic methods, the digital neural network of up to 530, 656 neurons always finds a solution in the NP-complete problem within a constant number of iteration steps on the synchronous parallel computation.

In this paper, we discuss an emergent behavior of a multi-elevator system. The system includes multiple elevators in an office building and the Poisson arrival of passengers as its input. Elevators move up and down to serve calls and carry passengers according to given working rules. The system is a representative discrete event dynamic system, and is a nonlinear complex system. When people leave a building at the closing time, the down-peak traffic of passengers occurs. We show numerically that (1) this causes a jamming effect, which reduces the transportation efficiency, (2) there exists a threshold in the arrival rate of passengers, at which the traffic rate starts decreasing, and (3) this jamming effect is due to the synchronization of elevators. Then we propose a dispatching control that prevents elevators from synchronizing. This control is applied to each elevator as an anxiliary working rule. We can remove the jamming effect and recover the transportation efficiency by the control.

A new current-mode sampled-data chaos circuit is proposed. The proposed circuit is composed of an operation block, a parameter block, and a delay block. The nonlinear mapping functions of this circuit are generated in the neuro-fuzzy based operation block. And these functions are determined by supervised learning. For the proposed circut, the dynamics of the learning and the state of the chaos are analyzed by computer simulations. The design conditions concerning the bifurcation diagram and the nonlinear mapping function are presented to clarify the chaos generating conditions and the effect of nonidealities of the proposed circuit. The simulation results showed that the nonlinear mapping functions can be realized with the precision of the order of several percent and that different kinds of bifurcation modes can be generated easily.

In order to construct fuzzy systems automatically, there are many studies on combining fuzzy inference with neural networks. In these studies, fuzzy models using self-organization and vector quantization have been proposed. It is well known that these models construct fuzzy inference rules effectively representing distribution of input data, and not affected by increment of input dimensions. In this paper, we propose a destructive fuzzy modeling using neural gas network and demonstrate the validity of a proposed method by performing some numerical examples.

This peper proposes a simplified model of the well-known two-neuron neural oscillator. By eliminating one of the two positive feedback synapses in the neural oscillator, learning for the in-phase control of the oscillator is shown to be achievable via a very simple learning rule. The learning rule is devised in such a way that only the plasticity of two synaptic weights are required. We demonstrate some examples of the synchronization learning to validate the efficiency of the learning rule, and finally by illustrating the dynamics of the synchronization learning and by using computer simulation, we show the convergence behavior and the stability of the learning rule for the two-neuron simple neural oscillator.

This paper presents a new multi-clustering network for the purpose of intelligent data classification. In this network, the first layer is a self-organized clustering layer and the second layer is a restricted clustering layer with a neighborhood mechanism. A new clustering algorithm is developed in this system for the efficiently use of parallel processors. This parallel algorithm enables the nodes of this network to be independently processed in order to minimize data communication load among processors. Using the parallel processors, the quite low calculation cost can be realized among the conventional networks. For example, a 4-processor parallel computing system has shown its ability to reduce the time taken for data classification to 26.75% of a single processor system without declining its performance.

Based on a new search strategy using circuit simulation and simulated annealing with local search, a design tool is proposed to automate design or tuning process for CMOS operational amplifiers. A special-purpose circuit simulator and some heuristics are used to accomplish the design within reasonable time. For arbitrary circuit topology and specifications, the discrete optimization of cost function is performed by global and local search. Through the comparision of design results and the design of a low-power high-speed CMOS operational amplifier usable in 10-b 25-MHz pipelined A/D converters, it has been demonstrated that this tool can be used for designing high-performance operational amplifiers with less design knowledge and effort.

The dipole-dipole interaction among excitons is shown to give rise to an intrinsic nonlinearity, which yields a localized mode in a forbidden band, providing a coherent state for quantum computation. Employing this mode, a quantum XOR (exclusive OR) gate is proposed. A block structure of quantum dot arrays is also proposed, to implement quantum circuits comprising the quantum XOR gates for computation.

In fully connected Multilayer perceptron (MLP), all the hidden units are activated by samples from the whole input space. For complex problems, due to interference and cross coupling of hidden units' activations, the network needs many hidden units to represent the problem and the error surface becomes highly non-linear. Searching for the minimum is then complex and computationally expensive, and simple gradient descent algorithms usually fail. We propose a network, where the input space is partitioned into local sub-regions. Subsequently, a number of smaller networks are simultaneously trained by overlapping subsets of the input samples. Remarkable improvement of training efficiency as well as generalization performance of this combined network are observed through various simulations.

Time decay of magnetic properties in perpendicular magnetic recording media was studied. It was suggested that magnetization in media with a low energy ratio, KV/kT, of 50 is thermally stable in the absence of a demagnetizing field while coercivity exhibits a large time dependence. Magnetization in perpendicular recording media exhibited an appreciable time decay even for films with a large energy ratio of 300. The decay is attributed to the small perpendicular squareness due to a large perpendicular demagnetizing field acting in the media. The recording density dependence of the time decay in the output was explained in terms of the change in the demagnetizing field with the density. It is concluded that the use of media with large squareness as well as large energy ratio effectively reduces time decay in the output.

For the solutions of linear systems of equations with unsymmetric coefficient matrices, we propose an improved version of the quasi-minimal residual (IQMR) method by using the Lanczos process as a major component combining elements of numerical stability and parallel algorithm design. For Lanczos process, stability is obtained by a coupled two-term procedure that generates Lanczos vectors scaled to unit length. The algorithm is derived such that all inner products and matrixvector multiplications of a single iteration step are independent and communication time required for inner product can be overlapped efficiently with computation time. Therefore, the cost of global communication on parallel distributed memory computers can be significantly reduced. The resulting IQMR algorithm maintains the favorable properties of the Lanczos process while not increasing computational costs. The efficiency of this method is demonstrated by numerical experimental results carried out on a massively parallel distributed memory computer, the Parsytec GC/PowerPlus.

The graph partitioning problem is a famous combinatorial problem and has many applications including VLSI circuit design, task allocation in distributed computer systems and so on. In this paper, a novel neural network for the m-way graph partitioning problem is proposed where the maximum neuron model is used. The undirected graph with weighted nodes and weighted edges is partitioned into several subsets. The objective of partitioning is to minimize the sum of weights on cut edges with keeping the size of each subset balanced. The proposed algorithm was compared with the genetic algorithm. The experimental result shows that the proposed neural network is better or comparable with the other existing methods for solving the m-way graph partitioning problem in terms of the computation time and the solution quality.

Let L be any class of languages, L' be one of the classes of context-free, context-sensitive and recursively enumerable languages, and Σ be any alphabet. In this paper, we show that if the following statement (1) holds, then the statement (2) holds. (1) For any language L in L over Σ, there exist an alphabet Γ including Σ, a homomorphism h:Γ*Σ* defined by h(a)=a for aΣ and h(a)=λ (empty word) for aΓ-Σ, a Dyck language D over Γ, and a language L1 in L' over Γ such that L=h(DL1). (2) For any language L in L over Σ, there exist an alphabet of k pairs of matching parentheses Xk, Dyck reduction Red over Xk, and a language L2 in L' over ΣXk such that L=Red(L2)Σ*. We also give an application of this result.

We previously proposed a robust hybrid edge detector which relaxes the trade off between robustess against noise and accurate localization of the edges. This hybrid detector separates the tasks of localization and noise suppresion between two sub-detectors. In this paper, we present an extension to this hybrid detector to determine its optimal parameters, independently of the scene. This extension defines a probabilistic cost function using for criteria the probability of missing an edge buried in noise and the probability of detecting false edges. The optimization of this cost function allows the automatic selection of the parameters of the hybrid edge detector given the height of the minimum edge to be detected and the variance of the noise, σ2n. The results were applied to the 2D case and the performance of the adaptive hybrid detector was compared to other detectors.

In this paper, we prove that for a class of nonsymmetric neural networks with connection matrices T having nonnegative off-diagonal entries, -T is an M-matrix is a necessary and sufficient condition for absolute exponential stability of the network belonging to this class. While this result extends the existing one of absolute stability in Forti, et al., its proof given in this paper is simpler, which is completed by an approach different from one used in Forti, et al. The most significant consequence is that the class of nonsymmetric neural networks with connection matrices T satisfying -T is an M-matrix is the largest class of nonsymmetric neural networks that can be employed for embedding and solving optimization problem with global exponential rate of convergence to the optimal solution and without the risk of spurious responses. An illustrating numerical example is also given.

In this paper, a new trial for the signal processing is proposed along the same line as a previous study on the extended regression analysis based on the Bayes' theorem. This method enables us to estimate a response probability property of complicated systems in an actual case when observation values of the output response are roughly observed due to the quantization mechanism of measuring equipment. More concretely, the main purpose of this research is to find the statistics of the joint probability density function before a level quantization operation which reflects every proper correlation informations between the system input and the output fluctuations. Then, the output probability distribution for another kind of input is predicted by using the estimated regression relationship. Finally, the effectiveness of the proposed method is experimentally confirmed by applying it to the actually observed input-output data of the acoustic system.

A new compression algorithm for fingerprint images is introduced. A modified wavelet packet scheme which uses a fixed decomposition structure, matched to the statistics of fingerprint images, is used. Based on statistical studies of the subbands, different compression techniques are chosen for different subbands. The decision is based on the effect of each subband on reconstructed image, taking into account the characteristics of the Human Visual System (HVS). A noise shaping bit allocation procedure which considers the HVS, is then used to assign the bit rate among subbands. Using Lattice Vector Quantization (LVQ), a new technique for determining the largest radius of the Lattice and its scaling factor is presented. The design is based on obtaining the smallest possible Expected Total Distortion (ETD) measure, using the given bit budget. At low bit rates, for the coefficients with high-frequency content, we propose the Positive-Negative Mean (PNM) algorithm to improve the resolution of the reconstructed image. Furthermore, for the coefficients with low-frequency content, a lossless predictive compression scheme is developed. The proposed algorithm results in a high compression ratio and a high reconstructed image quality with a low computational load compared to other available algorithms.