The outputs of all gates in a circuit are assumed to be observable unber the highly observable condition, which is mainly based on the use of E-beam testers. When using the E-beam tester, it is desirable that the test set for a circuit is small and the test vectors in the test set can be applied in a successive and repetitive manner. For a combinational circuit, these requirements can be satisfied by modifying the circuit into a k-UCP circuit, which needs only a small number of tests for diagnosis. For a sequential circuit, however, even if the combinational portion has been modified into a k-UCP circuit, it is impossible that the test vectors for the combinational portion can always be applied in a successive and repetitive manner because of the existence of feedback loops. To solve this problem, the concept of k-UCP scan circuits is proposed in this paper. It is shown that the test vectors for the combinational portion in a k-UCP scan circuit can be applied in a successive and repetitive manner through a specially constructed scan-path. An efficient method of modifying a sequential circuit into a k-UCP scan circuit is also presented.

This paper presents a destributed algorithm that uses weak copy consistency to create mutual exclusion in a distributed computer system. The weak copy consistency is deduced from the uncertainty of state which occurs due to the finite and unpredictable communication delays in a distributed environment. Also the method correlates outdated state information to current state. The average number of messages to enter critical section in the algorithm is n/2 to n messages where n is the number of sites. We show that the algorithm achieves mutual exclusion and the fairness and liveness of the algorithm is proven. We study the performance of the algorithm by simulation technique.

This paper deals with an adaptive credit assignment algorithm to select strategies having higher capabilities in the learning classifier system (LCS) based upon the genetic algorithm (GA). We emulate a kind of prizes and incentives employed in the economies with imperfect information. The compensation scheme provides an automatic adjustment in response to the changes in the environment, and a comfortable guideline to incorporate the constraints. The learning process in the LCS based on the GA is realized by combining a pair of most capable strategies (called classifiers) represented as the production rules to replace another less capable strategy in the similar manner to the genetic operation on chromosomes in organisms. In the conventional scheme of the learning classifier system, the capability s(k, t) (called strength) of a strategy k at time t is measured by only the suitableness to sense and recognize the environment. But, we also define and utilize the prizes and incentives obtained by employing the strategy, so as to increase s(k, t) if the classifier provide good rules, and some amount is subtracted if the classifier k violate the constraints. The new algorithm is applied to the portfolio management. As the simulation result shows, the net return of the portfolio management system surpasses the average return obtained in the American securities market. The result of the illustrative example is compared to the same system composed of the neural networks, and related problems are discussed.

Very high resolution images with more than 2,000*2.000 pels will play a very important role in a wide variety of applications of future multimedia communications ranging from electronic publishing to broadcasting. To make communication of very high resolution images practicable, we need to develop image coding techniques that can compress very high resolution images efficiently. Taking the channel capacity limitation of the future communication into consideration, the requisite compression ratio will be estimated to be at least 1/10 to 1/20 for color signals. Among existing image coding techniques, the sub-band coding technique is one of the most suitable techniques. With its applications to high-fidelity compression of very high resolution images, one of the major problem is how to encode high frequency sub-band signals. High frequency sub-band signals are well modeled as having approximately memoryless probability distribution, and hence the best way to solve this problem is to improve the quantization of high frequency sub-band signals. From the standpoint stated above, the work herein first compares three different scalor quantization schemes and improved permutation codes, which the authors have previously developed extending the concept of permutation codes, from the aspect of quantization performance for a memoryless probability distribution that well approximates the real statistical properties of high frequency sub-band signals, and thus demonstrates that at low coding rates improved permutation codes outperform the other scalor quatization schemes and that its superiority decreases as its coding rate increases. Moreover, from the results stated above, the work herein, develops a rate-adaptive quantization technique where the number of bits assigned to each subblock is determined according to the signal variance within the subblock and the proper quantization scheme is chosen from among different types of quantization schemes according to the allocated number of bits, and applies it to the high-fidelity encoding of sub-band signals of very high resolution images to demonstrate its usefulness.

To describe the state of visual communications in the U.S., two words come to mind: digital and anticipation. Although compressed, digital video has been used in teleconferencing systems for at least ten years, it is only recently that a broad consensus has developed among diverse industries anticipating business opportunities, value, or both in digital video. The drivers for this turning point are: advances in digital signal processing, continued improvement in the cost, complexity, and speed of VLSI, maturing international standards and their adoption by vendors and end users, and a seemingly insatiable consumer demand for greater diversity, accessibility, and control of communication systems.

Despite its potential to realize image communication at extremely low rates, model-based coding (analysis-synthesis coding) still has problems to be solved for any practical use. The main problems are the difficulty in modeling unknown objects and the presence of analysis errors. To cope with these difficulties, we incorporate waveform coding into model-based coding (model-based/waveform hybrid coding). The incorporated waveform coder can code unmodeled objects and cancel the artifacts caused by the analysis errors. From a different point of view, the performance of the practically used waveform coder can be improved by the incorporation of model-based coding. Since the model-based coder codes the modeled part of the image at extremely low rates, more bits can be allocated for the coding of the unmodeled region. In this paper, we present the basic concept of model-based/waveform hybrid coding. We develop a model-based/MC-DCT hybrid coding system designed to improve the performance of the practically used MC-DCT coder. Simulation results of the system show that this coding method is effective at very low transmission rates such as 16kb/s. Image transmission at such low rates is quite difficult for an MC-DCT coder without the contribution of the model-based coder.

Efficient probabilistic decision trees are required in various application areas such as character recognition. This paper presents a polynomial-time approximate algorithm for designing a probabilistic decision tree. The obtained tree is near-optimal for the cost, defined as the weighted sum of the expected test execution time and expected loss. The algorithm is advantageous over other reported heuristics from the viewpoint that the goodness of the solution is theoretically guaranteed. That is, the relative deviation of the obtained tree cost from the exact optimum is not more than a positive constant ε, which can be set arbitrarily small. When the given loss function is Hamming metric, the time efficiency is further improved by using the information theoretical lower bound on the tree cost. The time efficiency of the algorithm and the accuracy of the solutions were evaluated through computational experiments. The results show that the computing time increases very slowly with an increase in problem size and the relative error of the obtained solution is much less than the upper bound ε for most problems.

Transient responses by a dielectric sphere have been analyzed here for a dipole source located at the center. The formulation has been constructed first in the frequency domain, then transformed into the time domain to obtain for an impulsive response by two analytical methods, namely the Singularity Expansion Method and the Wavefront Expansion Method. While the former method collects the contributions around the singularities in the complex frequency domain, the latter gives us a result which is a summation of each successive wavefront arrivals. A Gaussian pulse has been introduced to simulate an impulse response result. The Gaussian pulse response is analytically formulated by convolving Gaussian pulse with the corresponding impulse response. Numercal inversion results are also calculated by Fast Fourier Transform Algorithm. Numerical examples are shown here to compare the results obtained by these three methods and good agreement are obtained between them. Comments are often made in connection with the corresponding two dimensional cylindrical case.

This paper reviews the capability of the three layer neural network (TLNN) with one output neuron. The input set is restricted to a finite subset S of En, and the TLNN implements a function F such as F : S I={1, -1}, i,e., F is a dichotomy of S. How many functions (dichotomies) can it compute by appropriately adjusting parameters in the TLNN? Brief historical review, some theorems on the subject obtained so far, and related topics are presented. Several open problems are also included.

Applications of neural networks are prevailing in speech recognition research. In this paper, first, suitable role of neural network (mainly back-propagation based multi-layer type) in speech recognition, is discussed. Considering that speech is a long, variable length, structured pattern, a direction, in which neural network is used in cooperation with existing structural analysis frameworks, is recommended. Activities are surveyed, including those intended to cooperatively merge neural networks into dynamic programming based structural analysis framework. It is observed that considerable efforts have been paid to suppress the high nonlinearity of network output. As far as surveyed, no experiment in real field has been reported.

In recent years, the digitalization of transmission links, such as optical fibre cables, satellite links, and terrestrial microwave links, has been progressed rapidly in many countries. In addition, many types of digital studio equipment have been developed and TV programs can be produced or edited without any picture quality degradation by using such equipment, for example, digital VTR. A high-efficiency bit-reduction coding system is the most promising and effective means for this situation in terms of reducing the cost of digital transmission of TV programs with high picture quality. Considering this background, a new digital coding system has been developed, which makes it possible to transmit up to 4 NTSC TV programs simultaneously over a single DS3 45Mbps link including two high quality sound channels and one 64kbps ancillary data channel for each TV program. The principal bit-reduction technique employed is 2 dimensional intraframe WHT (Walsh Hadamard Transform) coding, which gives higher coding performance for composite TV signals than DCT (Discrete Cosine Transform) coding. In order to attain high picture quality at around 8Mbps for 4 channel transmission, a 3 dimensional adaptive quantization cube which reflects human visual perception sufficiently is employed in the intraframe WHT coding scheme. The hardware has been made compact like a home use VTR. In this paper, first, the algorithm of the coding scheme developed for the coding system is presented, and then the system configuration and its basic coding performance are described.

This paper attempts to account for intelligibility of practices-based learning (so-called 'learning control') for skill refinement from the viewpoint of Newtonian mechanics. It is shown from an axiomatic approach that an extended notion of passivity for the residual error dynamics of robots plays a crucial role in their ability of learning. More precisely, it is shown that the exponentially weighted passivity with respect to residual velocity vector and torque vector leads the robot system to the convergence of trajectory tracking errors to zero with repeating practices. For a class of tasks when the endpoint is constrained geometrically on a surface, the problem of convergence of residual tracking errors and residual contact-force errors is also discussed on the basis of passivity analysis.

A new error rate formula for narrowband Differential Quaternary Phase Shift Keyed system in a Rayleigh fading channel is obtained in closed-form. The formula predicts a non-zero error probability for noiseless reception. As predicted, the computed error rates approach some constant or floor values as the signal-to-noise ratio is increased beyond a certain limit. In the presence of various Doppler frequency shifts, an IF filter bandwidth of about one times the symbol rate is found to lead to a minimum error probability prior to the appearence of the error rate floor.

High-speed digital land mobile communications suffer from frequency-selective fading due to a long delay difference. Several techniques have been proposed to overcome the multipath propagation problem. Among them, an adaptive array antenna is suitable for very high-speed transmission because it can suppress the multipath signal of a long delay difference significantly. This paper describes the LMS adaptive array antenna for frequency-selective fading reduction and a new diversity technique. First, we propose a method to generate a reference signal in the LMS adaptive array. At the beginning of communication, we use training codes for the reference signal, which are known at a receiver. After the training period, we use detected codes for the reference signal. We can generate the reference signal modulating a carrier at the receiver by those codes. The carrier is oscillated independently of the incident signal. Then, the carrier frequency of the reference signal is in general different from that of the incident signal. However, the LMS adaptive array works in such a way that the carrier frequency of the array output coincides with that of the reference signal. Namely, the frequency difference does not affect the performance of the LMS adaptive array. Computer simulations show the proper behavior of the LMS adaptive array with the above reference signal generator. Moreover, we present a new multipath diversity technique using the LMS adaptive array. The LMS adaptive array reduces the frequency-selective fading by suppressing the multipath components. This means that the transmitted power is not used sufficiently. We propose a multiple beam antenna with the LMS adaptive array. Each antenna pattern receives one of the multipath components, and we combine them adjusting the timing. Then, we realize the multipath diversity. In addition to the multipath fading reduction, we can improve a signal-to-noise ratio by the diversity technique.

An organization may suffer large losses if its computer service is interrupted. For protection, it can purchase computer backup service from the outside market which temporarily provides service replacement from a central facility. A dynamic probabilistic model is developed which describes such a computer backup service system. The parties involved have conflicting motivations. The supplier is interested in optimizing his expected profits subject to a given set of parameters while the subscriber will evaluate the service contract to his own best interest. This paper analyzes how the economic interests of the supplier and subscribers interact based on a dynamic reliability analysis of their respective computer systems. Assuming all physical parameters fixed, the supplier's optimal value in terms of economic parameters is determined. An algorithmic procedure is developed for computing such values. Some numerical examples are presented in order to gain insights into the system.

A theoretical conjecture on fractal dimensions of a dendrite distribution in neural networks is presented on the basis of the dendrite tree model. It is shown that the fractal dimensions obtained by the model are consistent with the recent experimental data.

Quantization of the impulse response coefficients due to finite word length causes the moments to deviate from their ideal values. This deviation is found to have a linear variation with the output roundoff noise of the filter realized in direct form. Since the zeros and poles of a given filter also move away from their designed locations due to quantization, we show a relation between the zeros and poles and the moments of the impulse response.

Artificial neurons and neural networks have been shown to perform Principal Component Analysis (PCA) when gradient ascent learning rules are used, which are related to the constrained maximization of statistical objective functions. Due to their parallelism and adaptivity to input data, such algorithms and their implementations in neural networks are potentially useful in feature extraction and data compression. In the companion paper(9), two such learning rules were derived from two criteria, the Subspace Criterion and the Weighted Subspace Criterion. It was shown that the only solutions to the latter problem are dominant eigenvectors of the data covariance matrix, which are the basis vectors of PCA. It was suggested by a simulation that the corresponding learning algorithm converges to these eigenvectors. A homogeneous neural network implementation was proposed for the algorithm. The learning algorithm is analyzed here in detail and it is shown that it can be approximated by a continuous-time differential equation that is obtained by averaging. It is shown that the asymptotically stable limits of this differntial equation are the eigenvectors. The neural network learning algorithm is further extended to a case in which each neuron has a sigmoidal nonlinear feedback activity function. Then no parameters specific to each neuron are needed, and the learning rule is fully homogeneous.

Principal Component Analysis (PCA) is a useful technique in feature extraction and data compression. It can be formulated as a statistical constrained maximization problem, whose solution is given by unit eigenvectors of the data covariance matrix. In a practical application like image compression, the problem can be solved numerically by a corresponding gradient ascent maximization algorithm. Such on-line algoritms can be good alternatives due to their parallelism and adaptivity to input data. The algorithms can be implemented in a local and homogeneous way in learning neural networks. One example is the Subspace Network. It is a regular layer of parallel artificial neurons with a learning rule that is completely homogeneous with respect to the neurons. However, due to the complete homogeneity, the learning rule does not converge to the unique basis given by the dominant eigenvectors, but any basis of this eigenvector subspace is possible. In many applications like data compression, the subspace is not sufficient but the actual eigenvectors or PCA coefficient vectors are needed. A new criterion, called the Weighted Subspace Criterion, is proposed, which makes a small symmetry-breaking change to the Subspace Criterion. Only the true eigenvectors are solutions. Making the corresponding change to the learning rule of the Subspace Network gives a modified learning rule, which can be still implemented on a homogeneous network architecture. In learning, the weight vectors will tend to the true eigenvectors.

This paper discusses the design, implementation, and performance of a bus-connected multiprocessor, called Presto, for a Rete-based production system. To perform a match, which is a major phase of a production system, a Presto match scheme exploits the subnetworks that are separated by the top two-input nodes and the token flow control at these nodes. Since parallelism of a production system can only increase speed 10-fold, the aim is to do so efficiently on a low-cost, compact bus-connected multi-processor system without shared memory or cache memory. The Presto hardware consists of up to 10 processisng elements (PEs), each comprising a commercial microprocessor, 4 Mbytes of local memory, and two kinds of newly developed ASIC chips for memory control and bus control. Hierarchical system software is provided for developing interpreter programs. Measurement with 10 PEs shows that sample programs run 5-7 times faster.