Recently, many researches on associative memories have been made a lot of neural network models have been proposed. Bidirectional Associative Memory (BAM) is one of them. The BAM uses Hebbian learning. However, unless the traning vectors are orthogonal, Hebbian learning does not guarantee the recall of all training pairs. Namely, the BAM which is trained by Hebbian learning suffers from low memory capacity. To improve the storage capacity of the BAM, Pseudo-Relaxation Learning Algorithm for BAM (PRLAB) has been proposed. However, PRLAB needs long learning epochs because of random initial weights. In this paper, we propose Quick Learning for BAM which greatly reduces learning epochs and guarantees the recall of all training pairs. In the proposed algorithm, the BAM is trained by Hebbian learning in the first stage and then trained by PRLAB. Owing to the use of Hebbian learning in the first stage, the weights are much closer to the solution space than the initial weights chosen randomly. As a result, the proposed algorithm can reduce the learning epocks. The features of the proposed algorithm are: 1) It requires much less learning epochs. 2) It guarantees the recall of all training pairs. 3) It is robust for noisy inputs. 4) The memory capacity is much larger than conventional BAM. In addition, we made clear several important chracteristics of the conventional and the proposed algorithms such as noise reduction characteristics, storage capacity and the finding of an index which relates to the noise reduction.

Genetic algorithms have been shown to be very useful in a variety of search and optimization problems. In this paper, we describe the implementation of genetic algorithms for channel routing problems and identify the key points which are essential to making full use of the population of potential solutions, that is one of the characteristics of genetic algorithms. Three efficient crossover techniques which can be divided further into 13 kinds of crossover operators have been compared. We also extend our previous work with ability to deal with dogleg case by simply splitting multi-terminal nets into a series of 2-terminal subnets. It routes the Deutsch's difficult example with 21 tracks without any detours.

This paper presents a linear time algorithm for testing whether or not there is a path ,vm> of an undiercted tree T (|V(T)|n) that coincides with a string ss1sm (i.e., label(v1)label(vm)s1sm). Since any path of the tree is allowed, linear time substring matching algorithms can not be directly applied and a new method is developed. In the algorithm, O(n/m) vertices are selected from V(T) such that any path pf length more than m 2 must contain at least one of the selected vertices. A search is performed using the selected vertices as 'bases' and two tables of size O(m) are constructed for each of the selected vertices. A suffix tree, which is a well-known-data structure in string matching, is used effectively in the algorithm. From each of the selected vertices, a search is performed with traversing the suffix tree associated with s. Although the size of the alphabet is assumed to be bounded by a constant in this paper, the algorithm can be applied to the case of unbounded alphabets by increasing the time complexity to O(n log m).

In a distributed-memory parallel-processing system, the overhead of data transfer among the processors is so large that it is important to reduce the data transfer. We consider the data transfer in evaluating an expression consisting of data distributed among the processors. We propose some algorithms which assign the operators in the expression to the processors so as to minimize the number or the cost of data transfers, on the condition that the data allocation to the processors is given. The basic algorithm is given at first, followed by some variations.

This paper proposes new algorithms for adaptive FIR filters. The proposed algorithms provide both fast convergence and small final misadjustment with an adaptive step size even under an interference to the error. The basic algorithm pays special attention to the interference which contaminates the error. To enhance robustness to the interference, it imposes a special limit on the increment/decrement of the step-size. The limit itself is also varied according to the step-size. The basic algorithm is extended for application to nonstationary signals. Simulation results with white signals show that the final misadjustment is reduced by up to 22 dB under severe observation noise at a negligible expense of the convergence speed. An echo canceler simulation with a real speech signal exhibits its potential for a nonstationary signal.

A sequence of nonnegative integers S=(s1, s2, , sn) is graphical if there is a graph with vertices v1,v2, ,vn such that deg(vi)=si for each i=1, 2, , n. The graphical degree sequence problem is： Given a sequence of nonnegative integers, determine whether it is graphical or not. In this paper, we consider several variations of the graphical degree sequence problem and give efficient algorithms.

This paper studies the problem of embedding a graph into a book with nodes on a line along the spine of the book and edges on the pages in such a way that no edge crosses another. Atneosen as well as Bernhart and Kainen has shown that every graph can be embedded into a 3-page book when each edge can be embedded in more than one page. The time complexity of Bernhart and Kainen's method is Ω(ν(G)), where ν(G) is the crossing number of a graph G. A new 0(mn) algorithm is derived in this paper for embedding a graph G=(V, E), where m=│E│ and n= │V│ . The number of points at which edges cross over the spine in embedding a complete graph into a 3-page book is also investigated.

The Minimum Covering Run (MCR) expression used for representing binary images has been proposed [1]-[3]. The MCR expression is an adaptation from horizontal and vertical run expression. In the expression, some horizontal and vertical runs are used together for representing binary images in which total number of them is minimized. It was shown that, sets of horizontal and vertical runs representing any binary image could be viewed as partite sets of a bipartite graph, then the MCR expression of binary images was found analogously by constructing a maximum matching as well as a minimum covering in the corresponding graph. In the original algorithm, the most efficient algorithm, proposed by Hopcroft, solving the graph-theoretical problems mentioned above, associated with the Rectangular Segment Analysis (RSA) was used for finding the MCR expression. However, the original algorithm still suffers from a long processing time. In this paper, we propose two new efficient MCR algorithms that are beneficial to a practical implementation. The new algorithms are composed of two main procedures; i.e., Partial Segment Analysis (PSA) and construction of a maximum matching. It is shown in this paper that the first procedure which is directly an improvement to the RSA, appoints well a lot of representative runs of the MCR expression in regions of text and line drawing. Due to the PSA, the new algorithms reduce the number of runs used in the technique of solving the matching problem in corresponding graphs so that satisfactory processing time can be obtained. To clarify the validity of new algorithms proposed in this paper, the experimental results show the comparative performance of the original and new algorithms in terms of processing time.

Finding DC solutions of nonlinear networks is one of the most difficult tasks in circuit simulation, and many circuit designers experience difficulties in finding DC solutions using Newton's method. Piecewise-linear analysis has been studied to overcome this difficulty. However, efficient piecewiselinear algorithms have not been proposed for nonlinear resistive networks containing the Gummel-Poon models or the Shichman-Hodges models. In this paper, a new piecewise-linear algorithm is presented for solving nonlinear resistive networks containing these sophisticated transistor models. The basic idea of the algorithm is to exploit the special structure of the nonlinear network equations, namely, the pairwise-separability. The proposed algorithm is globally convergent and much more efficient than the conventional simplical-type piecewise-linear algorithms.

We found degraded output power due to discoloration of an abnormal epitaxial layer caused by supercooling of residual melt in liquid phase epitaxy (LPE) process of AlGaAs/GaAs heteroface solar cells developed to improve conversion efficiency of solar cells for satellites. We studied the discoloration mechanism and found effective methods for obtaning a good epitaxial layer. Using these results, we manufactured about 80,000 pieces of solar cells and employed them in the Japanese domestic Communication Satellite-3 (CS-3) launched by National Space Development Agency of Japan (NASDA). Five years after launch, these solar cells are still supplying the output power than predicted. This paper describes reliability improvements for the surface of epitaxial layer and successful results aftes 5 years of space operation.

For improving the RSA cryptosystem, more desirable conditions on key structures have been intensively studied. Recently, M.J.Wiener presented a cryptanalytic attack on the use of small RSA secret exponents. To be secure against the Wiener's attack, the size of a secret exponent d should be chosen more than one-quarter of the size of the modulus n = pq (in bits). Besides, it is more desirable, in frequent cases, to make the public exponent e as small as possible. However if small d is chosen first, in such case as the digital signature system with smart card, the size of e is inevitably increased to that of n when we use the conventional key generation algorithm. This paper presents a new algorithm, Algorithm I, for generating of the secure RSA keys against Wiener's attack. With Algorithm I, it is possible to choose the smaller sizes of the RSA exponents under certain conditions on key parameters. For example, with Algorithm I, we can construct the RSA keys with the public exponent e of two-thirds and secret exponent d of one-third of the size of modulus n (in bits). Furthermore we present a modified version of Algorithm I, Algorithm II, for generating of the strong RSA keys having the difficulty of factoring n. Finally we analyze the performances of Algorithm I and Algorithm II.

This paper presents an equation capable of briefly evaluating the length of white noise sequence to be sent as a training signal. The equation is formulated by utilizing the formula describing the convergence property, which has been derived from the IIR filter expression of the NLMS algorithm. The result revealed that the length is directly proportional to I/[K(2-K)] where K is a step gain and I is the number of the adaptive filter taps.

In this paper, we propose a polynomial time algorithm for computing the expected maximum number of vertex-disjoint s-t paths in a probabilistic basically series-parallel directed graph and a probabilistic series-parallel undirected graph with distinguished source s and sink t(st), where each edge has a mutually independent failure probability and each vertex is assumed to be failure-free.

This paper presents a method of translating natural language specifications of communication protocols into algebraic specifications. Such a natural language specification specifies action sequences performed by the protocol machine (program). Usually, a sentence implicitly specifies the state of the protocol machine at which the described actions must be performed. The authors propose a method of analyzing the implicitly specified states of the protocol machine taking the OSI session protocol specification (265 sentences) as an example. The method uses the following properties: (a) syntactic properties of a natural language (English in this paper); (b) syntactic properties introduced by the target algebraic specifications, e.g., type constraints; (c) properties specific to the target domain, e.g., properties of data types. This paper also shows the result of applying this method to the main part of the OSI session protocol specification (29 paragraphs, 98 sentences). For 95 sentences, the translation system uniquely determines the states specified implicitly by these sentences, using only (a) and (b) described above. By using (c) in addition, each implicitly specified state in the remaining three sentences is uniquely determined.

This paper describes and analyzed several indices in assessing algorithms of data compression of electrocardiograms, such as the cross correlation (CC), the percent root mean square difference (PRD), and a new measure of standardized root mean square difference (SRD). Although these indices are helpful to objectively evaluate the algorithms, the visual examination of the reconstructed waveform is indispensable to decide the optimal compression ratio. This paper presents the clinical significance of selected waveforms which are prone to be distorted or neglected in the restored waveforms but are crucial for cardiologists to diagnose the patient. A database of electrocardiograms is also proposed for the comparative evaluation of compression algorithms.

A new superresolution technique is proposed for antenna pattern measurements. Unwanted reflected signals often impinge on the antenna when we measure it outdoors. A time-domain superresolution technique (a MUSIC algorithm) has been proposed to eliminate the unwanted signal for a narrow pass-band antenna. The MUSIC algorithm needs many snapshots to obtain a correlation matrix. This is not preferable for antenna pattern measurements because it takes a long time to obtain the data. In this paper, we propose to reduce a noise component (stochastic quantity) using the FFT and gating techniques before we apply the MUSIC. The new technique needs a few snapshots and saves the measurement time.

In the present paper, we focus ourselves on the turning point (TP) algorithm proposed by Mueller and evaluate its performance when applied to a Gaussian signal with definite covariance function. Then the ECG wave is modeled by Gaussian signals: namely, the ECG is divided into two segments, the baseline segment and the QRS segment. The baseline segment is modeled by a Gaussian signal with butterworth spectrum and the QRS one by a narrow-band Gaussian signal. Performance of the TP algorithm is evaluated and compared when it is applied to a real ECG signal and its Gaussian model. The compression rate (CR) and the normalized mean square error (NMSE) are used as measures of performance. These measures show good coincidence with each other when applied to Gaussian signals with the mentioned spectra. Our results suggest that performance evaluation of the compression algorithms based on the stochastic-process model of ECG waves may be effective.

This paper presents a parallel sorting algorithm which sorts n elements on O(n/w+n log n/p) time using p(n) processors arranged in a 1-dimensional grid with w(n1-ε) buses for every fixed ε>0. Furthermore, it is shown that np elements can be sorted in O(n/w+n log n/p) time on pp (pn) processors arranged in a 2-dimensional grid with w(n1-ε) buses in each column and in each row. These algorithms are optimal because their time complexities are equal to the lower bounds.

Evolution programs have been shown to be very useful in a variety of search and optimization problems, however, until now, there has been little attempt to apply evolution programs to channel routing problem. In this paper, we present an exolution program and identify the key points which are essential to successfully applying evolution programs to channel routing problem. We also indicate how integrating heuristic information related to the problem under consideration helps in convergence on final solutions and illustrate the validity of out approach by providing experimental results obtained for the benchmark tests. compared with the optimal solutions.

As RAMs become dense, their reliability reduces because of complex interactions between memory cells and soft errors due to alpha particle radiations. In order to rectify this problem, RAM manufacturers have started incorporating on-chip (built-in) ECC. In order to minimize the area overhead of on-chip ECC, the same technology is used for implementing the check bits and the information bits. Thus the check bits are exposed to the same failure modes as the information bits. Furthermore, faults in the check bits will manifest as uncorrectable multiple errors when a soft error occurs. Therefore it is important to test the check bits for all failure modes expected of other cells. In this paper, we formulate the problem of testing RAMs with on-chip ECC capability. We than derive necessary and sufficient conditions for testing the check bits for arbitrary and adjacent neighborhood pattern sensitive faults. We also provide an efficient solution to test a memory array of N bits (including check bits) for 5-cell neighborhood pattern sensitive faults in O (N) reads and writes, with the check bits also tested for the same fault classes as the information bits.