A motion compensation LSI for realtime MPEG1/H.261 video encoding has been developed. This LSI employs a compact motion estimator that consists of vector search array processors. Furthermore, an efficient motion vector search strategy that enables bidirectioanl searches with a -16.0/+15.5 pels range is adopted to maintain encoded picture quality. The adopted strategy takes two steps. The first step is the full search for 2-pel precision vectors within the range of 16 pels. A 4-to-1 sub-sampling technique with a low pass filter is employed in this step. The second step is the full search for half-pel precision vectors within a 1.0 pels search range centered on the location pointed by the best 2-pel precision vectors. This strategy is compared with the exhaustive-search strategy. It is shown that the number of operations and external memory access cycles are reduced to 1/11 and 1/2, respectively, while differences of the signal to noise ratios obtained by simulation are within 0.2 dB. Those reductions contribute to lowering power dissipation. The array processors calculate the values of distortion. They accumulate the absolute differences between current and reference data with a feedback loop to keep the number of processor elements equal to the number of pels in a row of the current block. Multiple reference data buses and a delay line in the feedback loop have been introduced for efficient calculation. In addition, cascade connection of the array processors is studied to shorten calculation periods. This LSI controls input frames reordering buffers and reference frames buffers. It generates the prediction and the prediction error blocks as well as the motion vectors. AC power of current blocks and the values of distortion are obtained for the bit rate control. This LSI is fabricated using 0.8 µm 2-level metal CMOS technology and dissipates 2.0 W from 5 V supply at 36 MHz.

A fast pitch search algorithm using the skipping technique is proposed to reduce the computation time in CELP vocoder. Based on the characteristics of the correlation function of speech signal, the proposed algorithm skips over certain ranges in the full pitch search range in a simple way. Though the search range is reduced, high speech quality can be maintained since those lags having high correlation values are not skipped over and are used for search by closed-loop analysis. To improve the efficiency of the proposed method, we develop three variants of the skipping technique. The experimental results show that the proposed and the modified algorithm can reduce the computation time in the pitch search considerably, over 60% reduction compared with the traditional full search method.

Generalizations of the classical ngram indexing techique provide a powerful tool for the fast retrieval of tree structures. We investigate the special case of binary trees, which are heavily used, for example, in computer linguistics: Given a database T{t1,...,tn} of labeled binary trees and a query tree q, find efficiently all trees t T that contain q as subtree. For supporting queries of this type, we propose an indexing technique that covers the database trees t T with smaller trees of a fixed calss. Thus, each index record represents a subtree that is contained in at least one database tree. To answer a given query q, the database trees of T that contain all of q's cover trees are preselected as candidates, which in turn are tested rigorously for containment of q. We present results from two test suites: one with databases of 10,000 randomly generated binary trees each and one with the 29,394 most extensive phrase structure trees found in the morphosyntactical analysis of the Old Testament's Hebrew texts Genesis, Exodus,and Leviticus.

For a complex object model, a form of range restriction, called specialization constraint (SC), has been studied. On the other hand, very few models have been proposed that support selective inheritance. In this paper, the following consideration is taken into SCs for a complex object medel suppoorting selective inheritance. A polynomial-time algorithm is given for deciding if a given database schema is well-formed. A sound and complete axiomatization for SCs is presented. A polynomial-time algorithm is given that decides if an SC is a logical consequence of a set of SCs. Finally, another polynomial-time algorithm is given, which decides if there exists a database that contains a given path from a given class.

The disturbance-rejection problem is to find a feedback control law for linear control systems such that the influence of disturbances is completely rejected from the output. In 1970 Wonham and Morse first studied this problem in the framework of the so-called geometric approach. On the other hand, in 1985 Ghosh studied parameter insensitive disturbance-rejection problems with state feedback and with dynamic compensator. In this paper we study the parameter insensitive disturbance-rejection problem with static incomplete-state feedback for linear multivariable systems in the framework of the geometric approach from the mathematical point of view. Necessary conditions and/or sufficient conditions for this problem to be solvable are presented. Finally an illustrative example is presented.

A 2-switch node network is one of the most fundamental structure among communication nets such as telephone networks and local area networks etc. In this letter, we prove that a problem of designing a 2-switch node network satisfying capacity conditions of switch nodes and their link, which we call 2-switch node network problem, is NP-complete.

This paper proposes a distributed built-in self-test (BIST) technique and its test design platform for VLSIs. This BIST has lower hardware overhead pattern generators, compressors and controller. The platform cuts down on the number of complicated operations needed for the BIST insertion and evaluation, so the BIST implementation turn-around-time (TAT) is dramatically reduced. Experimental results for the 110 k-gate arithmetic execution blocks of an image-processing LSI show that using this BIST structure and platform enables the entire BIST implementation within five days. The implemented BIST has a 1% hardware overhead and 96% fault coverage. This platform will significantly reduce testing costs for time-to-market and mass-produced LSIs.

A soft magnetic force microscope (MFM) tip was used to evaluate the magnetic recording characteristics of compositionally separated Co-Cr perpendicular media. Small magnetic bits were recorded on thick (350 nm). and thin (100 nm) films, focusing on the fineness of compositionally separated microstructures. MFM images showed bit marks 230 and 150 nm in diameter, measured at full-width at half maximum (FWHM) for the thick and thin films, respectively. These results verify that the recordable bit size can be decreased by using a thinner film with a finer compositionally separated microstructure. Simulation was used to clarify the relationship between the actual sizes of the recorded bits and the sizes of their MFM images. The recorded bit size was found to closely correspond to the FWHM of the MFM bit images.

In this paper a priori estimation method is presented for calculating solution of convex optimization problems (COP) with some equality and/or inequality constraints by so-called Newton type homotopy method. The homotopy method is known as an efficient algorithm which can always calculate solution of nonlinear equations under a certain mild condition. Although, in general, it is difficult to estimate a priori computational complexity of calculating solution by the homotopy method. In the presented papers, a sufficient condition is considered for linear homotopy, under which an upper bound of the complexity can be estimated a priori. For the condition it is seen that Urabe type convergence theorem plays an important role. In this paper, by introducing the results, it is shown that under a certain condition a global minimum of COP can be always calculated, and that computational complexity of the calculation can be a priori estimated. Suitability of the estimation for analysing COP is also discussed.

A new algorithm for multiple-precision modular multiplication is proposed. It is fast and uses a small amount of main memory, and hence, is useful for application of a public-key cryptosystem to small computers, such as card computers.

The integration of both real-time systems and fault-tolerant systems has been emerged as one of the greatest challenges of this decade. It is called a responsive system, which has the objective to optimeze both timeliness and reliability. The performance measure in responsive systems is responsiveness that tells how probable a system executes correctly on time with faults occurred. While there have been some achievements in communication protocols and specification, we believe that scheduling problems in responsive systems are not understood deeply and sufficiently, yet. In this paper, we discuss the scheduling problem in responsive systems. At first, we investigate the issues in the scheduling and propose the precise definition of the responsiveness. We also suggest a scheduling algorithm called Responsive Earliest Deadline First (REDF) for preemptive aperiodic tasks in a uniprocessor system. We show that REDF is optimal to obtain the maximum responsiveness, and the time complexity is analyzed to be (N 2N). By illustrating a contradictory example, it is shown that REDF can be enhanced if a constraint on tasks is released.

We propose a new high-performance message router for k-ary n-cube multicomputer systems, called the Tokky router. The router utilizes a small number of queues at the outputs of its communication ports to allow fully adaptive routing, misrouting to prevent deadlocks and randomization to prevent livelock. Uncongeste network performance is improved by the inclusion of the packet expressway. Accurate models are developed to predict the switch and buffer performance of routers for varying radix and dimension and these models can be used in the design of routers for networks other than those investigated here. The simulated performance of the router exceeds that of published results for oblivious routers and is equal to or exceeds those reported for other adaptive routers. These performance predictions are especially encouraging when the simplicity of the control structures required to implement the router are taken into consideration.

We present a framework for the unsupervised segmentation of time series. It applies to non-stationary signals originating from different dynamical systems which alternate in time, a phenomenon which appears in many natural systems. In our approach, predictors compete for data points of a given time series. We combine competition and evolutionary inertia to a learning rule. Under this learning rule the system evolves such that the predictors, which finally survive, unambiguously identify the underlying processes. The segmentation achieved by this method is very precise and transients are included, a fact, which makes our approach promising for future applications.

In this paper, we present for the first time two three-dimensional analytical electrostatic Green's functions for shielded and open arbitrarily multilayered medium structures. The analytical formulas for the Green's functions are simply expressed in the form of Fourier series and integrals, and are applicable to the arbitrary number of dielectric layers. In combination with the complex image charge method, we demonstrate an efficient application to analyze microstrip discontinuities in a three-layered dielectric structure. Numerical results for the capacitance associated with on open-end discontinuity show good agreement with those from a previous paper and the effectiveness of using the analytical Green's functions to analyze three-dimensional electrostatic problems.

This paper proposes a new algorithm called the fast Projection algorithm, which reduces the computational complexity of the Projection algorithm from (p+1)L+O(p3) to 2L+20p (where L is the length of the estimation filter and p is the projection order.) This algorithm has properties that lie between those of NLMS and RLS, i.e. less computational complexity than RLS but much faster convergence than NLMS for input signals like speech. The reduction of computation consists of two parts. One concerns calculating the pre-filtering vector which originally took O(p3) operations. Our new algorithm computes the pre-filtering vector recursively with about 15p operations. The other reduction is accomplished by introducing an approximation vector of the estimation filter. Experimental results for speech input show that the convergence speed of the Projection algorithm approaches that of RLS as the projection order increases with only a slight extra calculation complexity beyond that of NLMS, which indicates the efficiency of the proposed fast Projection algorithm.

One of the major open issues in neural network research includes a Network Designing Problem (NDP): find a polynomial-time procedure that produces minimal structures (the minimum intermediate size, thresholds and synapse weights) of multilayer threshold feed-forward networks so that they can yield outputs consistent with given sample sets of input-output data. The NDP includes as a sub-problem a Network Training Problem (NTP) where the intermediate size is given. The NTP has been studied mainly by use of iterative algorithms of network training. This paper, making use of both rate distortion theory in information theory and linear algebra, solves the NDP mathematically rigorously. On the basis of this mathematical solution, it furthermore develops a mathematical solution Procedure to the NDP that computes the minimal structure straightforwardly from the sample set. The Procedure precisely attains the minimum intermediate size, although its computational time complexity can be of non-polynomial order at worst cases. The paper also refers to a polynomial-time shortcut to the Procedure for practical use that can reach an approximately minimum intermediate size with its error measurable. The shortcut, when the intermediate size is pre-specified, reduces to a promising alternative as well to current network training algorithms to the NTP.

Information capture is a very desirable and important function in portable computers. The "Multimedia Notebook" is a portable tool for capturing information in multimedia format, which includes photos, voice, and handwritten memos. Recent portable units, sometimes called PDA (Personal Digital Assistants) or Communicators, have PIM (Personal Information Manager) software and some communication facility. Their purpose is to enlarge the desktop environment to follow the user outside the office. This is one application of portable equipment, however we felt that hand-held equipment can also be used for more general information capture. In the past, information capture was limited, because people had to carry bulky equipment to the information source. Recent portable computers that have the capability to handle still and motion pictures, voice, and handwritten drawings allow the implementation of more information capture capabilities. Capture of handwritten notes has already been implemented on portable equipment like PDAs. However, this application doesn't make the most of its potential. We feel that the Multimedia Notebook should integrate handwritten memos with pictures and voice. The advantage is that users can capture what they watch and hear easily in a variety of media for later review. The information in each medium complements the others. When arranging the recorded information, it is easy to use each medium efficiently. We have examined the human interface and designed it for user-friendliness and to be comparable to pen and paper. The prototypes also have a capture buffer which can operate continuously to capture voice and pictures that would otherwise be lost because of the user's delay in starting to record.

We have developed a 15-Gbit/s 96-gate Si-bipolar gate array using 0.5-µm Si-bipolar technology, a sophisticated internal cell design, an I/O buffer design suitable for high-speed operation and high-frequency package technology. The decision circuit and 4 : 1 multiplexer fabricated on the gate array operate up to 15-Gbit/s and above 10-Gbit/s respectively. The data input sensitivity and the phase margin of the decision circuit are 53 mVpp and 288 at 10-Gbit/s operation. This gate array promises to be useful in shortening the development period and lowering cost of 10-Gbit/s class IC's.

Information systems to support cooperative work among people should be first designed to help humam communication. However, there are few systems based on the analysis of human communication. Standing on this situation, we propose a meeting support system for the participants' understandings by indicating the suitable information about the topic of the scene". Our system provides only useful information by monitoring each statement without complex methods. To show something useful multi-media information for members, we propose the following structure of the meeting on the basis of the analysis of communication. Each statement is classified into two levels, either; a statement about the progress" of the meeting (context-level utterances) or, a statement about objects" (content-level utterances). Further, content-level utterances are classified into two types, position utterances and argument utterances. Using this classification of statements, the proceeding of the meeting is represented as the tree model which is called a context-tree". If the structure of meetings is fixed, it is possible to select only useful information from all shared information for members by analyzing each content-level utterance. The system introduced in this paper shows appropriate multi-media information about the topic of the scene" by using the above model. We have implemented a prototype system based on the above ideas. Moreover, we have mode some experiments to show the effectiveness of this system. Those results show that our method is effective to improve the productivity" of meetings.

A 0.5 µm CMOS embedded function type gate array family with high speed modules was developed. This family has: an effective basic cell; high speed, compiled type metallized and diffused RAMs; PLL (Phase Locked Loop); and GTL (Gunning Transceiver Logic) to realize operation of over 100 MHz at 3.3 V. This paper describes the basic cell architecture and the compiled type metallized RAM. A divided MOS transistor type basic cell is effective for metallized modules such as metallized RAM and internal logic circuits. The appropriate basic cell size (height) can be decided from the viewpoints of the relationship between the number of usable basic cells and the basic cell height, and the logic circuit speed. Propagation delay time of the 2-input NAND is 200 ps at a standard load of fan out=2 and metal length=1.4 mm. For the universal ASIC, the compiled RAM is indispensable. Single port and multi-port metallized RAMs which are structured by using the basic cells are discussed. The new single port memory cell circuit which has a differential write and single end read operating method is introduced. This memory cell circuit can be realized using one basic cell. The diffused layer region of the NMOS transfer gates for the read operation is shared between neighbor memory cells. So, the capacitance of the bit line becomes smaller, and a high speed access time can be achieved. The measured access time of 1 kbits is 4.2 ns. The new multi-port memory cell circuits which have a single end write and single end read operating method are introduced. The read operating method is the same as that of the single port memory cell circuit. The access time shows very high speed operation comparable to that of the single port memory. This 3F (Flexible, Fast, and Friendly) ASIC family can be applied to high speed processors in workstations and graphics equipment.