This paper describes a preconstrained compaction method and its application to the direct design-rule conversion of CMOS layouts. This approach can convert already designed physical patterns into compacted layouts that satisfy user-specified design rules. Furthermore, preconstrained compaction can eliminate unnecessarily extended diffusion areas and polysilicon wires which tend to be created with conventional longest path based compactions. Preconstrained compaction can be constructed by combining a longest path algorithm with forward and backward slack processes and a preconstraint generation process. This contrasts with previously proposed approaches based on longest path algorithms followed by iterative improvement processes, which include applications of linear programming. The layout styles in those approaches are usually limited to a model where fixed-shaped rectilinear blocks are moved so as to minimize the total length of rectilinear interconnections among the blocks. However, preconstrained compaction can be applied to reshaping polygonal patterns such as diffusion and channel areas. Thus, this compaction method makes it possible to reuse CMOS leaf and macro cell layouts even if design rules change. The proposed preconstrained compaction approach has been applied to direct design-rule conversion from 0.8-µm to 0.5-µm rules of CMOS layouts containing from several to 10,195 transistors. Experimental results demonstrate that a 10.6% reduction in diffusion areas can be achieved without unnecessary extensions of polysilicon wires with a 39% increase in processing times compared with conventional approaches.

In a distributed system, the protocol entities must exchange some data values and synchronization messages in order to ensure the temporal ordering of the events described in a service specification for the distributed system. It is desirable that a correct protocol specification can be derived automatically from a given service specification. In this paper, we propose an algorithm which synthesizes automatically a correct protocol specification from a service specification described as a Marked Graph with Registers (MGR) model and resources (registers and gates) allocation information. This model has a finite control modeled as a marked graph. Therefore, parallel events can be described. In our method, to minimize the number of the exchanged messages, we use a procedure to calculate an optimum solution for 0-1 integer linear programming problems. The number of the steps which each protocol entity needs to simulate one transition in the service specification is also minimized. Ways to avoiding conflict of registers are also described. Our approach has the following advantages. First, parallel events can be described in a service specification. Secondly, many practical systems can be described in the MGR model. Finally, at the protocol specification level, we can understand what events can be executed in parallel.

Given a sorted set S of n points in the plane, the prefix convex hulls problem of S is to compute the convex hull for every prefix set of S. We present a parallel algorithm for this problem. Our algorithm runs in O(logn) time using n/logn processors in the CREW PRAM computational model. The algorithm is shown to be time and cost optimal. One of the techniques we adopt to achieve these optimal bounds is the use of a new parallel data structure Array-Tree.

A W-graph is a partially known graph which contains wild-components. A wild-component is an incompletely defined connected subgraph having p vertices and p-1 unspecified edges. The informations we know on a wild-component are which has a vertex set and between any two vertices there is one and only one path. In this paper, we discuss the properties of circuits in a W-graph (called W-circuits). Although a W-graph has unspecified edges, we can obtain some important properties of W-circuits. We show that the W-ring sum of W-circuits is also a W-circuit in the same W-graph. The following (1) and (2) are proved: (1) A W-circuit Ci of a W-graph can be transformed into either a circuit or an edge disjoint union of circuits, denoted by Ci*, of a graph derived from the W-graph, (2) if W-circuits C1, C2, , Cn are linearly independent, then C1*, C2*, , Cn* obtained in (1) are also linearly independent.

This paper describes a newly developed 22 liquid crystal optical switch for 1.3µm single-mode fiber use. This switch state can be freely set at either the cross or the bar state. The measured performance of two prototype 22 liquid crystal optical switches is given. Tests confirm that the 3 values are a maximum insertion loss of 1.5dB, a crosstalk attenuation of more than 26.1dB, and a return loss of more than 28.9dB. Requirements for optical switches for fault isolation are theoretically clarified from a LAN system view point.

High-speed pulse propagation, up to several hundred Mbps or higher, will play an important role in telecommunication systems for B-ISDN. High-performance packaging, especially high-speed, high-throughput interconnection, is strongly required. For advanced telecommunication systems, giga-bit signal transmission has been developed at the multi-chip module level, and 300 to 600 Mbps signal transmission has been reached at the printed circuit board level. Electrical inter-cabinet interconnections of 150 to 300 Mbps have been achieved for up to several tens of meters. High-speed, high-throughput connectors are the key to achieving high-performance telecommunication packaging systems. Two technologies are extremely important. One is for high-density, high-pin-count connectors, and the other is for high-speed signal transmission connectors. The requirements for the connectors needed for advanced high-performance telecommunication systems are described. Several high-density, high-bandwidth connectors developed for high-performance packaging system are introduced.

We analyze the effect of overlapping technique on differential pulse position modulation (DPPM) in optical direct-detection channel when the pulsewidth and the average power of the channel are constrained. We refer to the modulation scheme employing an overlapping technique in DPPM as differential overlapping PPM (DOPPM). To avoid frame synchronization problems, we analyze the performance of DOPPM under the window scheme that results in lower bounds on the capacity and the cutoff rate of DOPPM but is easy to analyze. Under this scheme, we analyze the lower bounds on the capacity and the cutoff rate of DOPPM. It is shown that DOPPM with the window scheme has higher capacity and cutoff rate than PPM and DPPM, and also than OPPM when the average received number of photons per slot is somewhat large. The overlapping technique is thus shown to be effective on DPPM under the pulsewidth constraint when the average received number of photons per slot is somewhat large.

The sidelobe canceler in radar systems is a highly computational demanding problem. It can be efficiently tackled by resorting to the QR decomposition mapped onto a systolic array processor. The paper reports several mapping strategies by using massive parallel computers available on the market. MIMD as well as SIMD machines have been used, specifically MEIKO Computing Surface, nCUBE2, Connection Machine CM-200, and MasPar MP-1. The achieved data throughput values have been measured for a number of operational situations of practical interest.

In the conventional protocol synthesis, it is generally assumed that primitives in service specifications cannot be executed simultaneously at different Service Access Points (SAPs). Thus if some primitives are executed concurrently, then protocol errors of unspecified receptions occur. In this paper, we try to extend a class of service specifications from which protocol specifications are synthesized by the previous methods. We first introduce priorities into primitives in protocol specification so that it always selects exactly one primitive of the highest priority from a set of primitives that can be executed simultaneously, and executes it. Then, based on this execution ordering, we propose a new protocol synthesis method which can avoid protocol errors due to message collisions, communication competitions and so on. By applying the proposed synthesis method, we can automatically synthesize a protocol specifications from a given service specification which includes an arbitraty number of processes and allows parallel execution of primitives.

A new optical path cross-connect system architecture (OPXC) based on delivery and coupling matrix switches is described. This OPXC provides the maximum compatibility for a wavelength path (WP) network and a virtual wavelength path (VWP) network. In other words, the proposed architecture easily evolves from WP-OPXC to VWP-OPXC. This salient feature can not been achieved with conventional OPXCs. Another attractive feature of this OPXC is its high modularity for OPXC capacity expansion.

Several distances between trees have been proposed. However, most of the reports on distances have dealt with rooted and ordered trees. This paper proposes two distances between unrooted and cyclically ordered trees (CO-trees) and their computing methods. A CO-tree is a tree embedded in a plane. These distances are defined based on Tai's mapping (TM) and a strongly structure preserving mapping (SSPM) between CO-trees. The time complexities to compute the distances between two CO-trees Ta and Tb are OT (N 2aN 2b) for the distance based on a TM and OT(mambNaNb) for that on an SSPM, respectively, where ma(mb) and Na(Nb) are the largest degree of a vertex and the number of vertices of Ta(Tb), respectively. The space complexities of both methods are Os(NaNb). Those distances can be applied to the clustering of CO-trees.

Many methods, based on the concept of key-lock-pair have been proposed for access control in computer protection systems. However, the proposed methods still either lack of dynamic ability or need quite a lot of computation in performing requests of deleting users/files, inserting users/files, or updating access rights of users to files. In this paper we propose a two-key-lock-pair access control method that is based on the unique factorization theorem and a time stamp mechanism. Our method is dynamic and needs a minimum amount of computation in the sense that it only updates at most one key/lock for each access request, which has not been achieved before.

The classical supervised learning algorithms for optimizing multi-layered feedforward neural networks, such at the original back-propagation algorithm, suffer from several weaknesses. First, they have the possibility of being trapped at local minima during learning, which may lead to failure in finding the global optimal solution. Second, the convergence rate is typically too slow even if the learning can be achieved. This paper introduces a new learning algorithm which employs a genetic-type search during the learning phase of back-propagation algorithm so that the above problems can be overcome. The basic idea is to evolve the network weights in a controlled manner so as to jump to the regions of smaller mean squared error whenever the back-propagation stops at a local minimum. By this, the local minima can always be escaped and a much faster learning with global optimal solution can be achieved. A mathematical framework on the weight evolution of the new algorithm in also presented in this paper, which gives a careful analysis on the requirements of weight evolution (or perturbation) during learning in order to achieve a better error performance in the weights between different hidden layers. Simulation results on three typical problems including XOR, 3-bit parity and the counting problem are described to illustrate the fast learning behaviour and the global search capability of the new algorithm in improving the performance of back-propagated network.

This paper is concerned with the data compression and interpolation of multi-view image set. In this paper, we propose a novel disparity compensation scheme based on geometric relationship. We first investigate the geometric relationship between a point in the object space and its projection onto view images. Then, we propose the disparity compensation scheme which utilize the geometric constraints between view images. This scheme is used to compress the multi-view image into the structure of the triangular patches and the texture data on the surface of patches. This scheme not only compresses the multi-view image but also synthesize the view images from any viewpoints in the viewing zone. Also, this scheme is fast and have compatibility with 2-D interframe coding. Finally, we report the experiment, where two sets multi-view image were used as original images and the amount of data was reduced to 1/19 and 1/20 with SNR 34 dB and 20 dB, respectively.

In this paper we estimate the number of permutations realizable in fault-tolerant multistage interconnection networks designed to tolerate faults on any switching element. The Parallel Omega network and the INDRA network are representative types of fault-tolerate multistage interconnection networks designed to tolerate a single fault. In order to evaluate the enhancement in the function of network by preparing the hardware redundancy for fault-tolerance, we estimate the number of permutations realizable in fault-tolerant networks. This result enables us to set up a standard to evaluate the hardware redundancy required to tolerate multifaults from the viewpoint of the enhancement of network function. This paper concludes that in the case where the number of inputs is up to 32 the increase ratio of the number of realizable permutations is no more than 1/0.73 even if the tolerance to multifaults is prepared instead of the tolerance to a single fault.

In this paper we propose an effective Peak Rate Spacer (PRS) which can guarantee the negotiated peak cell rate almost perfectly even though contention of cells in the output link of the spacer occurs. We also propose a state-dependent Mean cell Rate Policer-Spacer (MRPS) which can manage the cell loss rate properly by controlling the buffer read rate according to the buffer state. As the MRPS has a cell buffer, it intrinsically has a traffic shaping function. Simulation results clearly show effectiveness of our PRS and MRPS.

The static and dynamic characteristics of the lateral IGBT on the SOI film when the collector voltage of the IGBT is applied to the substrate are invesigated for its application to the high side switch. The measurements on the blocking capability and the switching characteristics under an inductive load are carried out with varying the thickness of the SOI film. The 260 V IGBT can be fabricated on the 5 µm thick SOI film without the special device structure. It is confirmed that the switching speed depends strongly on the SOI film thickness, not on the substrate bias. The dynamic latch-up current during the turn-off transient increases with the decrease in the SOI film thickness. This is caused by the large transient substrate current. This paper exhibits that applying the collector voltage of the IGBT to the substrate makes it possible to improve the characteristics of the IGBT on the thin SOI film.

This paper proposes an adaptive modulation/TDMA scheme to achieve high capacity personal multi-media communication systems. TDMA is employed to cope with various bit rate for multi-media services. The modulation scheme is selected from 1/4-rate QPSK, 1/2-rate QPSK, QPSK, 16QAM and 64QAM according to the received C/IC (power ratio of the desired signal to the co-channel interference) and the delay spread. The spectral efficiency is evaluated by using the simulated bit error rate (BER) performance as well as the cumulative distribution of the C/IC with parameters of cell configurations. The results show that the spectral efficiency of the proposed scheme is 3.5 times higher than that of the conventional QPSK systems at the outage probability of 10%, and the effect is more remarkable at lower outage probability. The results also show that the proposed adaptive modulation is effective in improving delay spread immunity.

In this paper, a fault model for multiple-valued programmable logic arrays (MV-PLAs) is proposed and the equivalences of faults of MV-PLA's are discussed. In a supposed multiple-valued NOR/TSUM PLA model, it is shown that multiple-valued stuck-at faults, multiple-valued bridging faults, multiple-valued threshold shift faults and other some faults in a literal generator circuit are equivalent or subequivalent to a multiple crosspoint fault in the NOR plane or a multiple fault of weights in the TSUM plane. These results lead the fact that multiple-valued test vector set which indicates all multiple crosspoint fault and all multiple fault of weights also detects above equivalent or subequivalent faults in a MV-PLA.

This paper describes an image synthesis method based on an estimation of camera parameters. In order to acquire high quality images using image synthesis, we take some constraints into account, which include angle of view, synchronization of change of scale and change of viewing direction. The proposed method is based on an investigation that any camera operation containing a change of scale and a pure 3D rotation can be represented by a 2D geometric transformation. The transformation can explain all the synthesis procedure consisting of locating, synchronizing, and operating images. The procedure is described based on a virtual camera which is constituted of a virtual viewing point and a virtual image plain. The method can be efficiently implemented in such a way that each image to be synthesized undergoes the transformation only one time. The parameters in the image transformation are estimated from image sequence. The estimation scheme consists of first establishing correspondence and then estimating the parameters by fitting the correspondence data to the transformation model. We present experimental results and show the validity of the proposed method.