This paper describes the waveform relaxation (WR) algorithm with the under relaxation method based on the virtual state formulation (VSF) technique and the effect of multirate behavior in this algorithm. First, we present the virtual state relaxation method using VSF technique. Next, we introduce the VSF method into WR algorithm in order to exploit the multirate behavior. Furthermore, we construct the relaxation-based circuit simulator DESIRE2 and apply this simulator to the transient analysis of MOS circuits. Finally, we show that the present technique enables to use efficiently the multirate integration method in VSR and reduce the total simulation time without losing the waveform accuracy.

The optimal coding strategy for signal detection in the correlated gaussian noise is established for the distributed sensors system with essentially zero transmission rate constraint. Specifically, we are able to obtain the same performance as in the situation of no restriction on rate from each sensor terminal to the fusion center. This simple result contrasts with the previous ad hoc studies containing many unnatural assumptions such as the independence of noises contaminating received signal at each sensor. For the design of optimal coder, we can use the classical Levinson-Wiggins-Robinson fast algorithm for block Toeplitz matrix to evaluate the necessary weight vector for the maximum-likelihood detection.

A dual transformation incorporating the frequency-dependent scaling factor with the impedance dimension is proposed to synthesize the current-mode counterpart of a voltage-mode original. A general class of current-mode active-RC biquadratic filters and a switched-capacitor low-pass biquad are derived to demonstrate the synthesis procedure. Their simulation and test results show that the current transfer functions are the same as the voltage transfer functions of the originals, and thus confirm the validity of the procedure. The dual trasformation described herein is general in that with the scaling factor chosen appropriately it can meet a wide variety of circuit transformation, and thus useful also for circuit classification and identification.

An Interlace Coding System (ICS) involving data compression code, data encryption code and error correcting code is proposed and its error performance on additive white Gaussian noise (AWGN) channel with quadrature phase shift keying (QPSK) is analyzed. The proposed system handles data compression, data encryption and error correcting processes together, i.e. adds error correcting redundancy to the block lists of the dictionary in which compression system constructs to reduce source redundancy. Each block list is encoded by Ziv-Lempel code and Data Encryption Standard (DES). As the catastrophic condition determined by the data compression procedure is not negligible, error correcting redundancy should be added so as to avoid catastrophic condition. We found that the catastrophic condition depends only on the size of the dictionary for our proposed system. Thus, by employing a large dictionary, good error performance can be applied by the proposed system and the catastrophic condition can be avoided.

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.

Information geometry is a new powerful method of information sciences. Information geometry is applied to manifolds of neural networks of various architectures. Here is proposed a new theoretical approach to the manifold consisting of feedforward neural networks, the manifold of Boltzmann machines and the manifold of neural networks of recurrent connections. This opens a new direction of studies on a family of neural networks, not a study of behaviors of single neural networks.

The problems of cache coherency in multiprocessor systems are directly related to their architectural structures. Small scale multiprocessor systems have focused on the use of bus based memory interconnection networks using centrally shared memory and a sequential consistency model for coherency. This has limited scalability to but a few tens of processors due to the limited bus bandwidth used for both coherency updates and memory traffic. Recently, large scale multiprocessor systems have been proposed that use general interconnection networks and distributed shared memory. These architectures have been proposed using weak consistency models and various directory map schemes to hide the overhead for coherency maintenance within the memory hieratchy, interconnection network or process context switch latencies. The coherency and memory traffic are still maintained over the same interconnection network. In this paper, we present the architecture of a new general purpose medium scale multiprocessor system. This Cache Coherent Multiprocessor System (C2MP), supports distributed shared memory using a general memory interconnection network for memory traffic and a separate bus based coherency interconnection network for coherency maintenance. Through the use of a special directory based coherency protocol and cache oriented distributed coherency controllers, direct cache-to-cache coherency maintenance is performed over the dedicated coherency bus. This minimizes coherency updates to only those processor nodes needing coherency maintenance. An aggressive sequential coherncy model is used, which reduces the hardware penalty to support an ideal sequential consistency programmers model. The system can scale up to 256-512 processors depending on the degree of shared data and is expected to have higher per processor utilization in this range than currently proposed medium and large scale multiprocessor systems. The C2MP system is analyzed utilizing a Generalized Timed Petri-Net model of a processor node. A stochastic model for internode interactions over the general memory interconnection network and coherency bus are used . The model of the proposed architecture is analyzed under steady-state conditions for varying system work load parameters.

Lingas developed an NC algorithm for subgraph isomorphism for connected graphs of bounded separator and bounded valence. We present an NC algorithm for computing canonical forms of graphs of bounded separator by using the similar technique.

It is sometimes required to change the frequency characteristics of a digital filter during its operation. In this paper a new synthesis of variable even-order IIR digital filters is proposed. The cut-off frequency of the filter can be changed by a single parameter. The fundamental filter structure is a cascade of second-order sections. The multiplier coefficients of each section are determined by using the Taylor series expansion of the lowpass to lowpass frequency transformation. For this method any second-order section can be used as a prototype, but here in this paper only the direct form and the lattice form are described. Unlike the conventional method, any transfer functions can be used for the proposed method. Finally a designed example shows that the proposed filter has wider tuning range than the conventional filter, and the advantage of the proposed filters is confirmed.

LOTOS is a language developed within ISO for the formal description of communication protocols and distributed systems. In LOTOS, requirements for a distributed system are called a "service specification". Each node exchanges synchronization messages to ensure the temporal ordering for the execution of events in a service specification. The actions of each node are described as a "protocol specification". This paper gives a survey for a method to derive protocol specifications from a service specification written in a LOTOS based language. In order to derive the protocol specifications, we make the syntax tree of a given service specification and give some attributes for each node in the tree. The protocol specifications are derived automatically by evaluating these attributes. The derived protocol specifications satisfy the given service specification. We also explain a LOTOS simulator for the execution of derived protocol specifications. The related works are also summarized.

Since Vendler classified aspect into four categories, state, achievement, activity, and accomplishment, much effort has been made to define the notion of aspect logically. It is commonly agreed that aspect represents the general temporal characteristics of events and states. However, there still remains a considerable amount of disagreement about its formal treatment. One of the major problems is that the aspect of a sentence shifts by certain types of sentence construction. For instance, adding time adverbials to a sentence modifies the original aspect, taking the progressive form of the verb changes the aspect, and so on. These phenomena are known as the aspect shifts. The other is the problem known as the imperfective paradox. The imperfective paradox is a problem of the truth definition of the progressives. The truth condition of the progressive form of the sentence is defined at an internal subinterval of the temporal range of the corresponding non-progressive sentence. If the truth condition of the progressive form of the sentence is defined using the truth condition of the non-progressive form of the sentence, there are logical contradictions of truth definition in a sentence such as "Max was building a house, but he never built it". These problems cause much confusion (1) in the truth definition of aspects, (2) in the definition of aspect operations, such as initiative, terminative, progressive, perfective, etc., and also (3) in the definition of adding time adverbials. This paper reviews the semantic problems with respect to aspect, and presents a consistent mechanism of aspect interpretation in order to settle all these semantic puzzles at once. For the sake of logical clarity, we construct a formal language, Lt, where every meaningful formula is a pair of a meaningful sentence and its aspect. The syntax of Lt describes the phenomenology of aspect shifts. The semantics of Lt defines temporal interpretation for all the meaningful sentences of Lt, with assuming the temporal interpretations of three inherent aspects, state, achievement, and activity. The proposed aspect interpretation gives a reasonable account for aspect shifts, and solves the imperfective paradox by asssuming the time structure to be backwards linear.

This paper describes a new approach towards the performance-driven layout for analog LSIs. Based on our approach, we developed an automatic performance-driven layout system LIBRA. The performance-driven layout has an advantage that numerical evaluations of performance requirements may exactly specify layout requirements so that a better layout result will be expected with regard to both the size and the performances. As the first step to the final goal, we only concern with the DC characteristics of analog circuits affected by the placement and routing. First of all, LIBRA performs the sensitivity analysis with respect to process parameters and wire parasitics, which are major causes for DC performance deviations of analog LSIs, so as to describe every perfomance deviation by its first order approximation. Based on the estimations of those performance deviations, LIBRA designs the placement of devices. The placement approach here is the simulated annealing method driven by their circuit performance specification. The routing of inter-cell wires is performed according to the priority of the larger total wire sensitivities in the net by the maze router. Then, the simple compaction eliminates the empty space as much as possible. After that, the power lines optimization is performed so as to minimize the ferformance deviations. Finally, an advantage of the performance improvement by our approach is demonstrated by showing a layout result of a practical bipolar circuit and its excellent performance evaluations.

Networks in this paper consist of non-commensurate transmission lines with branches and branching resistors at junctions. When signals on a transmission line are divided multiple ways at the junctions of branched lines, multiple reflection waves occur by the impedance mismatching. For the analysis of multiple reflections and network design, lattice diagrams have been used so far. However, the expansions of network transfer functions provide an easier way for the same purpose as in the case of lattice diagram. The output transient responses can be directly calculated from the expansions of network transfer functions or can be numerically calculated by software such as the fast Laplace transform. Therefore, once the network transfer functions are given, calculation of transient responses can be carried out quite easily. In this paper, the expansions of network transfer functions have been derived with respect to delay elements ξi=exp(-sτi) by formularizing the propagation of multiple reflection waves, and then the multi-variable rational network transfer functions have been obtained from the expansions. As an example, a 3-port transmission line network with normalized characteristic impedances 1, 1, 6 and normalized branching resistors 1/23, 1/23, 126/23 has been taken up. As the terminal resistances at output ports can be determined from the relation of the first arriving wave to the steady state, the design of 3-port transmission line networks which will furnish output waveforms similar to the waveform of the input within given tolerances has been considered. The output waveforms have been calculated for pure terminal resistances and for the pure terminal resistances plus parasitic parallel capacitances.

Proposed here is an internal representation and mapping method for multimedia information in which retrieval is based on the impression documents desired to make. A user interface design for a system using this method is also proposed. The proposed internal representation and mapping method represents each desired document impression as an axis in a semantic space. Documents are represented as points in the space. Queries are represented as subspaces. The proposed user interface design employs a method of visual presentation of the semantic space. Pictorial examples are given to illustrate the range of impressions represented by the axes. The relations between the axes are represented by dispersion diagrams for the documents stored in the document base. With this method, the user can intuitively decide the appropriate subspace for his needs and can specify it directly. For evaluation purposes, a prototype system has been developed. An image retrieval experiment shows that the proposed internal representation and mapping method and the user interface design provide effective tools for information retrieval.

We review the role of optics in interconnects, analog processing, neural networks, and digital computing. The properties of low interference, massively parallel interconnections, and very high data rates promise extremely high performance for optical information processing systems.

We review the role of optics in interconnects, analog processing, neural networks, and digital computing. The properties of low interference, massively parallel interconnections, and very high data rates promise extremely high performance for optical information processing systems.

The VSTEP concept and its practical application in the form of an LED-type pnpn-VSTEP demonstrating low power consumption through electro-photonic operational modes are both shown. Further, with focus primarily on the new laser-mode VSTEP with high-intensity light output and narrow optical beam divergence, the design features such as threshold gain and optical absorptivity, device fabrication, and characteristics are explained. The possibility of ultimate performance based mainly on electrical to optical power conversion efficiency, important from the application viewpoint of optical interconnection, are also discussed. Also, as two examples of functional optical interconnection achieved by VSTEP, serial-to-parallel data conversion and optical self-routing switches are shown. Finally, future opto-electronic technologies to be developed for two-dimensionally integrable surface-type optical semiconductor devices, including the VSTEP, are discussed.

The VSTEP concept and its practical application in the form of an LED-type pnpn-VSTEP demonstrating low power consumption through electro-photonic operational modes are both shown. Further, with focus primarily on the new laser-mode VSTEP with high-intensity light output and narrow optical beam divergence, the design features such as threshold gain and optical absorptivity, device fabrication, and characteristics are explained. The possibility of ultimate performance based mainly on electrical to optical power conversion efficiency, important from the application viewpoint of optical interconnection, are also discussed. Also, as two examples of functional optical interconnection achieved by VSTEP, serial-to-parallel data conversion and optical self-routing switches are shown. Finally, future opto-electronic technologies to be developed for two-dimensionally integrable surface-type optical semiconductor devices, including the VSTEP, are discussed.

We describe two information disseminating schemes, t-disseminate and t-Rdisseminate in a computer network with N processors, where each processor can send a message to t-directions at each round. If no processors have failed, these schemes are time optimal. When at most t processors have failed, for t1 and t2 any of these schemes can broadcast information within any consecutive logt+1N2 rounds, and for an arbitrary t they can broadcast information within any consecutive logt+1N3 rounds.

Multiple context-free grammars (mcfg's) are a subclass of generalized context-free grammars introduced by Pollard in order to describe the syntax of natural languages. First, this paper shows that the universal recognition problem for mcfg's is EXP-POLY time-complete, where the universal recognition problem is the one to decide whether G generates w for a given grammar G and string w. Next, it is shown that the problem for linear context-free rewriting systems introduced by Vijay-Shanker et al., which is a proper subclass of mcfg's, is PSPACE-complete.