The paper proposes a combined delay model to manipulate the variance of the delay time of logic elements and a new timing verification method based on the theory of regular expressions. With the delay time of logic elements such as TTL SN7400, the minimum delay time (dm), the maximum delay time (dM), and the typical delay time are specified in the manual, and the delay time of an element is one in the interval between dm and dM. Here we assume a discrete time, and we manipulate the variance of the delay time as a set of output strings corresponding to each delay time. We call the model as the combined delay model. Since many output strings are generated with a single input string, the usual timing simulation method cannot be applied. We propose a timing verification method using a behavior extraction method of logic circuits with respect to a time string set: with respect to the specified input set, the method extracts the output string set of each element in the circuit. We devised (1) a mechanism to keep the correspondence between a primary input string and an output string with respect to the primary input string, (2) a mechanism to manipulate the nondeterminism included in the combined delay model, and (3) an event-driven like data compaction method in representing finite automata. We focused on the hazard detection problem and the verification of asynchronous circuits, and show the effectiveness of our method with medium sized circuit with 100 elements or so. The method includes the state explosion, but the data compaction method and the extraction for only the specified input set are useful to control the state explosion.

The purpose of this paper is to propose a technique to simplify the communications software descriptions written in a procedural language in order to enhance their comprehensibility. Although such a technique was not much studied and discussed in the past, this technique is important to realize high productivity and high quality of the communications software by reducing the complexity of the software description. This paper firstly systematically presents various simplification methods with their principles for the descriptions of the communications software from the viewpoints of their layout, syntactical structures etc. Then, it describes a simplification support system based on these principles for the software specifications written in SDL. Lastly, this paper demonstrates the usefulness and effectiveness of the proposed simplification technique by analyzing the evaluation results of the simplification system.

This paper deals with the sub-problems of generating a mask pattern from the logical description of a large-scale CMOS circuit. The large-scale layout can be generated in divide-and-conquer style: divide a given circuit into a set of sub-circuits, generate the layout of each sub-circuit, and merge the resulting layouts to create the whole layout. This paper proposes a layout synthesis algorithm for a sub-circuit with physical constraints for the synthesis scheme above. The physical constraints considered here are the relative placement of logic cells (sets of logic gates) and the routing constraint based on the costs of wiring layers and vias. These constraints will be given by the global optimizer in a two-dimensional layout synthesis routine, and they should be kept at the subsequent one-dimensional layout synthesis for a sub-circuit. The latter is also given for enhancing the circuit performance by limiting the usage of wiring layers and vias for special net such as a clock net. The placement constraint is maintained using PQ-tree, a tree structure representing a set of restricted permutations of elements. One-dimensional layout synthesis determines the placement of transistors by the enhanced pairwise exchanging method under the PQ-tree representation. The routing constraints is considered in the newly developed line-search routing method using a cost-based searching. Experimental results for practical standard cells, including up to 200 transistors, prove that the algorithms can produce the layouts comparable to handcrafted cells. Also on a two-dimensional layout synthesis using the algorithms, the results for benchmark circuits of Physical Design Workshop 1989, i.e., MCNC benchmark circuits, are superior to the best results exhibited at Design Automation Conference 1990.

An autonatic layout scheme dedicated to bipolar analog modules is described. A layout model is settled in such a way that the VCC/GND line is laid out on top/bottom edge of a rectangular region, within which the whole elements are placed and interconnected. According to this simple modeling, a layout scheme can be constructed of a series of the following algorithms: First clustering is executed for partitioning a given circuit into clusters, each having connections with VCC and GND lines, and then linear ordering is applied to clusters so as to be placed in a one-dimensional array. After a relative placement of circuits elements in each cluster, a block compactor is implemented by means of packing blocks in each cluster into an idle space, and then a detailed router is conducted to attain 100% interconnection. Finally a layout compactor is invoked to pack all layout patterns into a rectangle of the minimum possible area. A number of implementation results are also shown to reveal the practicability of the proposed analog module generator.

In recent VLSI design of digital data paths, significantly more area is occupied by interconnect elements than by functional units and registers. Nevertheless, until recently most work in data path synthesis has been concentrated on trying to reduce the area of functional units and registers, without paying much attention to the interconnect area. Lately, research that addresses reducing the area of interconnection and of functional units and registers is increasing, but in them, most algorithms for assigning interconnect elements are not efficient enough to optimize the interconnect area. In most current research, algorithms for interconnect element assignment are used to calculate the cost functions during the scheduling and/or allocation steps. This makes it impossible to use efficient optimization algorithms that may consume long time. This paper presents some new algorithms used to assign interconnect elements in data paths. The algorithms minimize the number of multiplexer inputs after the scheduling and operator/register allocations have been made. The algorithms have two characteristics. First, we use a branch and bound method for small problems. We confirmed that exact solutions in practical time can be obtained with this method for rather large problems, when the solutions are restricted to a one-level multiplexer model. Second, we use a certain heuristic method for larger problems. The algorithms have been implemented in C on an Apollo Domain Series 10000.

We developed a 32-bit pseudorandom number generator (RNG) operating at liquid nitrogen temperature based on HEMT ICs. It generates maximum-length-sequence codes whose primitive polynomial is X47+X42+1 with the period of 247-1 clock cycle. We designed and fabricated three kinds of cryogenic HEMT IC for this system: A 1306-gate controller IC, a 3319-gate pseudorandom number generator (RNG) IC, and a buffer IC containing a 4-kb RAM and 514 gates. We used 0.6-µm gate-length Se-doped GaAlAs/GaAs HEMTs. Interconnects were Al for the first layer and Au/Pt/Ti for the second layer with a SiON insulator between them. The HEMT ICs have direct-coupled FET logic (DCFL) gates internally and emitter-coupled logic (ECL) compatible input-putput buffers. The unloaded basic delay of the DCFL gate was 17 ps/gate with a power consumption of 1.4 mW/gate at liquid nitrogen temperature. We used an automatic cryogenic wafer probe we developed and an IC tester for function tests, and used a high-speed performance measuring system we also developed with a bandwidth of more than 20 GHz for high-speed performance tests. Power dissipations were 3.8 W for the controller IC, 4.5 W for the RNG IC, and 3.0 W for the buffer IC. The RNG IC, the largest of the three HEMT ICs, had a maximum operating clock rate of 1.6 GHz at liquid nitrogen temperature. We submerged a specially developed zirconium ceramic printed circuit board carrying the HEMT ICs in a closed-cycle cooling system. The HEMT ICs were flip-chip-packaged on the board with bumps containing indium as the principal component. We confirmed that the RNG system operates at liquid nitrogen temperature and measured a minimum system clock period of 1.49 ns.

A process of mixing viscous fluids, such as oil-based paints is applied to generate marble patterns. It is difficult to get the exact flow function of the viscous fluid, then we express the flow in terms of velocity vectors derived from simplified flow phenomena, in which the viscous liquid is supposed to be a collection of finite liquid elements. The position change of each element is calculated as the function of time and several examples of the obtained marble patterns are illustrated.

A novel harmonic retrieval algorithm is proposed in this paper based on Hopfield's neural network. Frequencies can be retrieved with high accuracy and high resolution under low signal to noise ratio (SNR). Amplitudes and phases in harmonic signals can also be estimated roughly by an energy constrained linear projection approach as proposed in the algorithm. Only no less than 2q neurons are necessary in order to detect harmonic siglnals with q different frequencies, where q denotes the number of different frequencies in harmonic signals. Experimental simulations show fast convergence and stable solution in spite of low signal to noise ratio can be obtained using the proposed algorithm.

This article proposes, given an independently-and-identically distributed binary source, an arithmetic code-like variable-to-variable length source code whose compression efficiency achieves nearly the rate function in a range of small distortion. Inheriting advantages of arithmetic codes, the proposed code requires neither large memory capacity nor large computation time for management of messages and codewords. The Elias code, which can be regarded as an antecedent of arithmetic codes, is defined originally in terms of the first-in-first-out (FIFO) coding form. The proposed code corresponds to an extension from the Elias code refined in terms of the last-in-first-out (LIFO) coding form into one considered a fidelity criterion.

We have fabricated superconducting microwave passive components such as resonators, bandpass filters and delay lines with YBCO thin film conductors deposited on MgO substrates. Considerably high unloaded Q values of 12000 at 5.5 GHz was obtained with the YBCO microstrip resonator at 77 K, which indicated that the surface resistance of the YBCO thin film was 0.79 mΩ at that frequency and temperature. Excellent microwave properties were also demonstrated with the bandpass filter and the delay line. Considerably low insertion loss of about 1 dB was obtained with the 10 GHz YBCO bandpass filters at 77 K which have a various bandwidth from 0.5% to 10%. Also excellent microwave propagation was obtained with a 1.3 nsec YBCO coplanar delay line. Its insertion loss was less than 1 dB for the frequencies up to 4 GHz.

This paper describes the properties of non-dispersive and dispersive delay lines fabricated using EuBaCuO superconducting films. The 24 cm long stripline non-dispersive delay line showed a very low loss of 0.3 dB/nsec at 77 K and 10 GHz, and no dispersion at a delay time of 2.3 nsec at frequencies below 20 GHz. The 14 cm long microstrip dispersive delay line with modal dispersion exhibited a relative delay time of approximately 120 psec in the 118 GHz frequency range. The 26 cm long stripline dispersive delay line with structural dispersion due to coupling provided a relative delay time of 230 psec in the above frequency range and roughly the same loss as a non-dispersive delay line.

The effects of changing system parameters on job scheduling policies are studied for load balancing of multi-class jobs in a distributed computer system that consists of heterogeneous host computers connected by a single-channel communications network. A job scheduling policy decides which host should process the arriving jobs. We consider two job scheduling policies. The one is the overall optimal policy whereby jobs are scheduled so as to minimize the overall mean job response time. Tantawi and Towsley obtained the algorithm that gives the solution of the policy in the single class job environment and Kim and Kameda extended it to the multiple job class environment. The other is the individually optimal policy whereby jobs are scheduled so that every job may feel that its own expected response time is minimized. We can consider three important system parameters in a distributed computer system: the communication time of the network, the processing capacity of each node, and the job arrival rate of each node. We examine the effects of these three parameters on the two load balancing policies by numerical experiment.

This paper proposes an efficient design method of three-dimensional (3-D) recursive digital filters for video signal processing via decomposition of magnitude specifications. A given magnitude specification of a 3-D digital filter is decomposed into specifications of 1-D digital filters with three different (horizontal, vertical, and temporal) directions. This decomposition can reduce design problems of 3-D digital filters to design problems of 1-D digital filters, which can be designed with ease by conventional methods. Consequently, design of 3-D digital filters can be efficiently performed without complicated tests for stability and large amount of computations. In order to process video signal in real time, the 1-D digital filters with temporal direction must be causal, which is not the case in horizontal and vertical directions. Since the proposed method can approximate negative magnitude specifications obtained by the decomposition with causal 1-D R filters, the 1-D digital filters with temporal direction can be causal. Therefore the 3-D digital filters designed by the proposed method is suitable for real time video signal processing. The designed 3-D digital filters have a parallel separable structure having high parallelism, regularity and modularity, and thus is suitable for high-speed VLSI implementation.

In this paper, subband image coding with symmetric biorthogonal wavelet filters is studied. In order to implement the symmetric biorthogonal wavelet basis, we use the Laplacian Pyramid Model (LPM) and the trigonometric polynomial solution method. These symmetric biorthogonal wavelet basis are used to form filters in each subband. Also coefficients of the filter are optimized with respect to the coding efficiency. From this optimization, we show that the values of a in the LPM generating kernel have the best coding efficiency in the range of 0.7 to 0.75. We also present an optimal bit allocation method based on considerations of the reconstruction filter characteristics. The step size of each subband uniform quantizer is determined by using this bit allocation method. The coding efficiency of the symmetric biorthogonal wavelet filter is compared with those of other filters: QMF, SSKF and Orthonormal wavelet filter. Simulation results demonstrate that the symmetric biorthogonal wavelet filter is useful as a basic means for image analysis/synthesis filters and can give better coding efficiency than other filters.

We investigate the relationship between two different notions of reducibility among prediction (learning) problems within the distribution-free learning model of Valiant (PAC learning model). The notions of reducibility we consider are the analogues for prediction problems of the many-one reducibility and of the Turing reducibility. The former is the notion of prediction preserving reducibility developed by Pitt and Warmuth, and its generalization. Concerning these two notions of reducibility, we show that there exist a pair of prediction problems A and B, whose membership problems are polynomial time solvable, such that A is reducible to B with respect to the Turing reducibility, but not with respect to the prediction preserving reducibility. We show this result by making use of the notion of a class of polynomially sparse variants of a concept representation class. We first show that any class A of polynomially sparse variants of another class B is reducible to B with respect to the Turing reducibility'. We then prove the existence of a prediction problem R and a class R of polynomially sparse variants of R, such that R does not reduce to R with respect to the prediction preserving reducibility.

Optimal static load balancing problems in open BCMP queueing networks with state-independent arrival and service rates are studied. Their examples include optimal static load balancing in distributed computer systems and static routing in communication networks. We refer to the load balancing policy of minimizing the overall mean response (or sojourn) time of a job as the overall optimal policy. We show the conditions that the solutions of the overall optimal policy satisfy and show that the policy uniquely determines the utilization of each service center, the mean delay for each class and each path class, etc., although the solution, the utilization for each class, the mean delay for all classes at each service center, etc., may not be unique. Then we give tha linear relations that characterize the set whose elements are the optimal solutions, and discuss the condition wherein the overall optimal policy has a unique solution. In parametric analysis and numerical calculation of optimal values of performance variables we must ensure whether they can be uniquely determined.

The elementary formal system (EFS, for short) is a kind of logic program which directly manipulates character strings. This paper outlines in brief the authors' studies on algorithmic learning theory developed in the framework of EFS's. We define two important classes of EFS's and a new hierarchy of various language classes. Then we discuss EFS's as logic programs. We show that EFS's form a good framework for inductive inference of languages by presenting model inference system for EFS's in Shapiro's sense. Using the framework we also show that inductive inference from positive data and PAC-learning are both much more powerful than they have been believed. We illustrate an application of our theoretical results to Molecular Biology.

A lossless image compression method based on two-dimensional (2D) linear prediction with variable coefficients is proposed. This method employs a space varying autoregressive (AR) model. To achieve a higher compression ratio, the method introduces new ideas in three points: the level conversion, the fast recursive parameter estimation, and the switching method for coding table. The level conversion prevents an AR model from predicting gray-level which does not exist in an image. The fast recursive parameter estimation algorithm proposed here calculates varying coefficients of linear prediction at each pixel in shorter time than conventional one. For encoding, the mean square error between the predicted value and the true one is calculated in the local area. This value is used to switch the coding table at each pixel to adapt it to the local statistical characteristics of an image. By applying the proposed method to "Girl" and "Couple" of IEEE monochromatic standard images, the compression ratios of 100 : 46 and 100 : 44 have been achieved, respectively. These results are superior to the best results (100 : 61 and 100 : 57) obtained by the approach under JPEG recommendations.

Logarithmic number systems (LNS) provide a very fast computational method. Their exceptional speed has been demonstrated in signal processing and then in computer graphics. But the precision problem of LNS in computer graphics has not been fully examined. In this paper analysis is made for the problem of LNS in picture generation, in particular for circle drawing. Theoretical error analysis is made for the circle drawing. That is, some expressions are developed for the relative error variances. Then they are examined by simulation experiments. Some comparisons are also done with floating point arithmetic with equivalent word length and dynamic range. The results show that the theory and the experiments agree reasonably well and that the logarithmic arithmetic is superior to or at least comparable to the corresponding floating point arithmetic with equivalent word length and dynamic range. Those results are also verified by visual inspections of actually drawn circles. It also shows that the conversion error (from integer to LNS), which is inherent in computer graphics with LNS, does not make too much influence on the total computational error for circle drawing. But it shows that the square-rooting makes the larger influence.

Parallel multiple context-free grammars (pmcfg's) and multiple context-free grammars (mcfg's) were introduced as extensions of context-free grammars to describe the syntax of natural languages. Pmcfg's and mcfg's deal with tuples of strings, and it has been shown that the universal recognition problem for mcfg's is EXP-POLY time-complete where the universal recognition problem is the problem to decide whether G generates w for a given grammar G and string w. In this paper, the universal recognition problems for the class of pmcfg's and for the subclass of pmcfg's with the information-lossless condition are shown to be EXP-POLY time-complete and PSPACE-complete, respectively. It is also shown that the problems for pmcfg's and for mcfg's with a bounded dimension are both -complete and those for pmcfg's and for mcfg's with a bounded degree are both -complete. As a corollary, the problem for modified head grammars introduced by Vijay-Shanker, et al. to define the syntax of natural languages is shown to be in deterministic polynomial time.