Various reconfiguration schemes against faults of mesh-connected processor arrays have been proposed. As one of them, the mesh-connected processor arrays model based on single-track switches was proposed in [1]. The model has an advantage of its inherent simplicity of the routing hardware. Furthermore, the 2 track switch model [2] and the multiple track switch model [3] were proposed to enhance yields and reliabilities of arrays. However, in these models, Simplicity of the routing hardware is somewhat lost because multiple tracks are used for each row and column. In this paper, we present a builtin self-reconstruction approach for mesh-connected processor arrays which are partitioned into sub-arrays each using single-track switches. Spare PEs which are located on the boundaries of the sub-arrays compensate faulty PEs in these sub-arrays. First, we formulate a reconfigulation algorithm for partitioned mesh-arrays using a Hopfield-type neural network, and then its performance for reconfigulation in terms of survival rates and reliabilities of arrays and processing time are investigated by computer simulations. From the results, we can see that high reliabilites are achieved while processing time is a little and hardware overhead (links and switches) required for reconstruction is as same as that for the track switch model. Next, we present a hardware implementation of the neural algorithm so that a built-in self-reconfigurable scheme may be realized.

This paper considers the estimation of speech parameters and their enhancement using an approach based on the estimation-maximization (EM) algorithm, when only noisy speech data is available. The distribution of the excitation source for the speech signal is assumed as a mixture of two Gaussian probability distribution functions with differing variances. This mixture assumption is experimentally valid for removing the residual excitation signal. The assumption also is found to be effective in enhancing noise-corrupted speech. We adaptively estimate the speech parameters and analyze the characteristics of its excitation source in a sequential manner. In the maximum likelihood estimation scheme we utilize the EM algorithm, and employ a detection and an estimation step for the parameters. For speech enhancement we use Kalman filtering for the parameters obtained from the above estimation procedure. The estimation and maximization procedures are closely coupled. Simulation results using synthetic and real speech vindicate the improved performance of our algorithm in noisy situations, with an increase of about 3 dB in terms of output SNR compared to conventional Gaussian assumption. The proposed algorithm also may be noteworthy in that it needs no voiced/unvoiced decision logic, due to the use of the residual approach.

Efficient parallel algorithms for several problems on proper circular arc graphs are presented in this paper. These problems include finding a maximum matching, partitioning into a minimum number of induced subgraphs each of which has a Hamiltonian cycle (path), partitioning into induced subgraphs each of which has a Hamiltonian cycle (path) with at least k vertices for a given k, and adding a minimum number of edges to make the graph contain a Hamiltonian cycle (path). It is shown here that the above problems can all be solved in logarithmic time with a linear number of EREW PRAM processors, or in constant time with a linear number of BSR processors. A more important part of this work is perhaps the extension of basic BSR to allow simultaneous multiple BROADCAST instructions.

A deterministic pushdown automaton (dpda) having just one stack symbol is called a deterministic restricted one-counter automaton (droca). A deterministic one-counter automaton (doca) is a dpda having only one stack symbol, with the exception of a bottom-of-stack market. The class of languages accepted by droca's is a proper subclass of the class of languages accepted by doca's. Valiant has shown that the regularity problem for doca's is decidable in a single exponential worst-case time complexity. In this paper, we prove that the class of languages accepted by droca's which accept by final state is incomparable with the class of languages accepted by droca's which accept by empty stack (strict droca's), and that the intersection of them is equal to the class of strict regular languages. In addition, we present a new direct branching algorithm for checking the regularity for not only a strict droca but also a real-time droca which accepts by final state. Then we show that the worst-case time complexity of our algorithm is polynomial in the size of each droca.

In this paper, the real-time scheduling mechanism which could support multimedia retrieval services more efficiently is investigated. In order to support multimedia service, the MEDF (modified earliest deadline first) algorithm that takes advantage of the priority queue and the virtual deadline mechanism is proposed. Additionally, its performance is analyzed and compared with conventional RR (round robin), FCFS (first come first serve), SS (sporadic server), MRF (minimum remained-time first), and EDF (earliest deadline first) algorithms. According to the simulation results, the proposed MEDF algorithm shows better performance than other scheduling algorithms in the multimedia environments.

In this paper, we show that the conventional BCH codes can be better than the AG codes when the number of check symbols is relatively small. More precisely, we consider an AG code on Cab whose number of check symbols is less than min {g+a, n-g}, where n and g denote the code length and the genus of the curve, respectively. It is shown that there always exists an extended BCH code, (i) which has the same designed distance as the Feng-Rao designed distance of the AG code and the code length and the rate greater than those of the AG code, or (ii) which has the same number of check symbols as that of the AG code, the designed distance not less than that of the AG code and the code length longer than that of the AG code.

A 2V/120 ns flash EEPROM embedded in a microcontroller has been fabricated in 0.8 µm double-metal CMOS process technology with a simple stacked gate memory cell. To achieve low voltage and high speed operation, novel circuit technology and architecture; (a) PMOS-precharging NMOS-self-boost word line circuit with a higher voltage selector, (b) new erase algorithm for reverse operation, (c) column gate boost circuit, (d) hard-verify mode for replacing weak cells, (e) efficient redundancy of row and column lines, have been developed. A 512 kb flash EEPROM core chip incorporating these circuit techniques and architecture operate at 1.8 V and accesses data in 120 ns at 2 V and 70.

When a natural language specification is translated into a formal one, it is important for objects and operations appearing in the natural language specification to be appropriately classified according to the framework of data types in the formal specification. In this paper, we propose a semi-automatic method of constructing a context-free grammar (cfg) representing an assignment of data types to words in a given natural language specification. In our method, a cfg is mechanically constructed from sample sentences in a natural language specification, where the cfg represents type declarations of expressions and type hierarchy. Then, the cfg is appropriately modified by adding nonterminals/production rules that represent type inclusion relations. In this modification process, candidates for the productions to be added are presented to the user. Finally, the cfg is simplified based on structural equivalence. The result of applying this method to a part of the OSI session protocol specification (39 sentences) is also presented. There was an example in which ambiguity of anaphoric bindings was solved by type checking based on the resulting cfg.

The MU radar of Japan is one of important candidates for providing accurate ground truth for the TRMM precipitation radar. It can provide the dropsize distribution data together with the background atmospheric wind data with high accuracy and high spatial resolution. Special observation scheme developed for TRMM validation using the MU radar is described, and preliminary results from its test experiment are shown. The high-resolution MU radar data are also used in numerical simulations to validate the rain retrieval algorithm for the TRMM PR data analysis. Among known sources of errors in the rain retrieval, the vertical variability of the dropsize distribution and the partial beam-filling effect are examined in terms of their significance with numerical simulations based on the MU radar data. It is shown that these factors may seriously affect the accuracy of the TRMM rain retrieval, and that it is necessary to establish statistical means for compensation. However, suggested means to improve the conventional α-adjustment method require careful treatment so that they do not introduce new sources of errors.

A blind equalization algorithm which makes use of the Stop" region of the Stop-and-Go algorithm is proposed. By adaptively updating the tap weights at the Stop region as well, it is intended to improve the convergence property of the Stop-and-Go algorthm. The performance of the proposed algorithm is compared with the conventional Stop-and-Go algorithm using various communication channels. Simulation results indicate the improvement of the convergence speed while maintaining or possibly lowering the residual error.

This paper describes advances in the study of handwritten Kanji character recognition mainly performed in Japan. The research focus has shifted from the investigation of the possibility of recognition by the stroke structure analysis method to the study of the feasibility of recognition by the feature matching methods. A great number of features and their extraction methods have been proposed according to this approach. On the other hand, studies on pattern matching methods of recognizing Kanji characters using the character pattern itself have been made. The research efforts based on these two approaches have led to the empirical fact that handwritten Kanji character recognition would become more effective by paying greater attention to the feature of directionality. Furthermore, in an effort to achieve recognition with higher precision, active research work has been carried out on pre-processing techniques, such as the forced reshaping of input pattern, the development of more effective features, and nonlinear flexible matching algorithms. In spite of these efforts, the current character recognition techniques represent only a skill of guessing characters" and are still on an insufficient technical level. Subsequent studies on character recognition must address the question of how to understand characters".

In ths letter, we suggest a collision resolution algorithm when the packet length is random, and analyze its throughput and delay performance. Here, three different packet length distributions and two feedback schemes (ternary and binary success/failure feedback) are considered.

The problem of genetic algorithm's efficiency has been attracting the attention of genetic algorithm community. Over the last decade, considerable researches have focused on improving genetic algorithm's performance. However, they are generally under the framework of natural evolutionary mechanism and the major genetic operators, crossover and mutation, are activated by the prior probabilities. An operator based on a prior probability possesses randomness, that is, the unexpected individuals are frequently operated, but the expected individuals are sometimes not operated. Moreover, as the evaluation function is the link between the genetic algorithm and the problem to be solved, the evaluation function provides the heuristic information for evolutionary search. Therefore, how to use this kind of heuristic information (present and past) is influential in the efficiency of evolutionary search. This paper, as an attempt, presents a eugenics-based genetic algorithm (EGA) -- a genetic algorithm that reflects the human's decision will (eugenics), and fully utilizes the heuristic information provided by the evaluation function for the decisions. In other words, EGA = evolutionary mechanisms + human's decision will + heuristic information. In EGA, the ideas of the positive eugenics and the negative eugenics are applied as the principle of selections and the selections are not activated by the prior probabilities but by the evaluation values of individuals. A method of genealogical chain-based selection for mutation is proposed, which avoids the blindness of stochastic mutation and the disruptive problem of mutation. A control strategy of reasonable competitions is proposed, which brings the effects of crossover and mutation into full play. Three examples, the minimum problem of a standard optimizing function--De Jong's test function F2, a typical combinatorial optimization problem--the traveling salesman problem, and a problem of identifying nonlinear system, are given to show the good performance of EGA.

AlGaAs/GaAs power HBTs for digital cellular phones have been developed. A three-dimensional thermal analysis taking the local-temperature dependence of the collector current into account was applied to the thermal design of the HBTs. The HBTs were fabricated using the hetero-guardring fully selfaligned transistor technique. The HBT with 220µm2 60 emitters produced a 31.7 dBm CW-output power and 46% poweradded efficiency with an adjacent channel leakage power of -49 dBc at the 50kHz offset bands for a 948 MHz π/4-shifted QPSK modulated signal at a low collector-emitter voltage of 3V. Through comparison with the conventional GaAs power FETs, it has been shown that AlGaAs/GaAs power HBTs have a great advantage in reducing the chip size.

A new adaptive AR spectral estimation method is proposed. While conventional least-squares methods use a single windowing function to analyze the linear prediction error, the proposed method uses a different window for each frequency band of the linear prediction error to define a cost function to be meinemized. With this approach, since time and frequency resolutions can be traded off throughout the frequency spectrum, an improvement on the precision of the estimates is achieved. In this paper, a wavelet-like time-frequency resolution grid is used so that low-frequency components of the linear prediction error are analyzed through long windows and high-frequency components are analyzed through short ones. To solve the optimization problem for the new cost function, special properties of the correlation matrix are used to derive an RLS algorithm on the order of M2, where M is the number of parameters of the AR model. Computer simulations comparing the performance of conventional RLS and the proposed methods are shown. In particular, it can be observed that the wavelet-based spectral estimation method gives fine frequency resolution at low frequencies and sharp time resolution at high frequencies, while with conventional methods it is possible to obtain only one of these characteristics.

There are some results indicating that a quantum computer seems to be more powerful than ordinary computers. In fact, P.W. Shor showed that a quantum computer can find discrete logarithms and factor integers in polynomial time with bounded error probability. No polynomial time algorithms to find them using ordinary computers are known. In this paper, we show that the cycles in some kinds of periodic functions, e.g., functions proposed as pseudo-random generators, can be found in polynomial time with bounded error probability on a quantum Turing machine. In general, it is known that ordinary computers take exponential time to find the cycles in periodic functions.

This letter proposes a new shaping algorithm (CRSA: CDV Reduction Shaping Algorithm) that can freely reduce the maximum CDV value of a cell stream to any predetermined value. There is a trade off between shaping delay and the maximum CDV value reduction achieved when using CRSA. The shaper using CRSA (CR-shaper) output satisfies the Peak Cell Rate Reference Algorithm set with the CR-shaper parameters.

This paper presents a parallel move generation of a Chess machine system for achieving the purpose of reducing the number of move generation cycles. The parallel system is composed of five move generation modules which share the move generating cycles to reduce the time of building a game tree. Simulation results show that the proposed parallel move generation architecture takes about half of the number of move generation cycles to build a game tree that is the same as the one built by a sequential move generation module.

We propose a parallel parsing algorithm based on Earley's method, which works in O(log2n) time using O(n4.752) processors on CREW PRAM. This algorithm runs with less number of precessors compared with previously proposed W. Rytter's algorithm.

A new superresolution technique is proposed for high-resolution estimation of the scattering analysis. For complicated multipath propagation environment, it is not enough to estimate only the delay-times of the signals. Some other information should be required to identify the signal path. The proposed method can estimate the frequency characteristic of each signal in addition to its delay-time. One method called modified (Root) MUSIC algorithm is known as a technique that can treat both of the parameters (frequency characteristic and delay-time). However, the method is based on some approximations in the signal decorrelation, that sometimes make problems. Therefore, further modification should be needed to apply the method to the complicated scattering analysis. In this paper, we propose to apply a time-domain null filtering scheme to reduce some of the dominant signal components. It can be shown by a simple experiment that the new technique can enhance estimation accuracy of the frequency characteristic in the Root-MUSIC algorithm.