The polymer matrix for the number of N in-puts/outputs, N stages and 2x2-switches is denoted as the 1-D Spanke-Benes (SB) network. Throughout the paper, the 1-D SB-network, which equals the diamond cellular array, is extended to arbitrary dimensions by a mathematical transformation (a 1-D network provides the interconnection of 1-D data). This transformation determines the multistage architecture completely by providing size, location, geometry and wiring of the switches as well as it preserves properties of the networks, e.g., the capability of sorting. The SB-networks of dimension 3 are analysed and sorting is applied.

Very-low-voltage 1.2-V mixed-signal CMOS technology is a device/circuit solution aimed at ultra-low-power portable systems such as digital cellular terminals and PDAs. We have developed an experimental 1.2-V mixed analog and digital LSI circuit/device technology. This technology is based on a new transistor structure that has a 0.3-µm gate length and a low Vth of 0.4 V, and that suppresses the short-channel effect. In this paper, we will mainly discuss low-voltage analog circuit design that uses this technology. We show that low Vth is essential not only to digital circuits, but also to 1.2-V analog amplifier, A/D converter and analog switch designs. To achieve high-conversion rate A/D converters, a pipeline architecture is used for low-voltage operation. To increase the attainable gain-bandwidth of the operational amplifier of the converter, a feedforward phase-compensated three-stage amplifier is proposed. The addition of a feedforward capacitor allows a high frequency signal to pass directly to the second stage, which optimizes use of the second stage bandwidth. Pole-zero canceling is used to achieve a fast settling of the amplifier. Although gain precision is degraded by the positive feedback through the feedforward capacitor, this can be offset by increasing the equivalent second-stage gain with an inner feedforward compensated amplifier. The gain-bandwidth of the proposed double feedforward amplifier is two to three times wider than with the conventional Miller compensation. With these techniques, we used 1.2-V mixed-signal CMOS technology to create a basic logic gate with a 400-ps delay and 0.4-µW/MHz power, and a 9-bit 2-Msample/s pipeline A/D converter with power dissipation of only 4 mW.

A mechanism of an integrated switching system architecture where PS, CS, and ATM switching functions are integrated based on a hierarchical memory system concept is discussed. A packet buffering control mechanism, and practical random time-slot assignment mechanism for CS traffic, which are composed of multiple bearer rate data traffic are then described. The feasibility of the random time-slot assignment mechanism is also confirmed by a practical experimental system using VLSI technology, particularly, content addressable memory (CAM) technology. The required queuing delay between the nodes for the corresponding call set up procedure is also shown and its application is clarified. For practical digital networks that provide various types of data communications including voice, data, and video services, it is highly desirable to evaluate the transmission efficiency of integrating packet switching (PS) type non-real time traffic and circuit switching (CS) type real time traffic. Transmission line utilization improvement is expected when the random time-slot assignment and the movable boundary scheme on a TDM (Time Division Multiplexing) data frame are adopted. The corresponding control procedure by signaling between switching nodes is also examined.

A very simple but general scheme has been developed to calculate burst error occurrences due to cycle slip in clock recovery on frequency-selective Nakagami-Rice fading channels. The scheme, which we call the "Equivalent Transmission-Path Model," plays a role in connecting "wave propagation" with "digital transmission characteristics" in a general manner. First computer simulations assuming various types of delay profiles identify the "key parameters in Nakagami-Rice fading" that principally dominate the occurrence of cycle slips. Following this a simple method is developed to calculate the occurrence frequency of cycle slips utilizing the nature of the key parameters. Then, the accuracy of the scheme is confirmed through comparison between calculated values and simulation results. Finally, based on the scheme, calculated results on cycleslip occurrences are presented in line-of-sight fading environments.

We describe low supply voltage analog circuit techniques for voice- and audio-band interfaces. These techniques can lower the supply voltage to 1 V, which is the voltage of a one-NiCd-cell battery. We have applied them in a swingsuppression noise-shaping method, and using this method, have fabricated A/D and D/A converters for the voice and audio bands. These converters operate with a 1 V power supply and have 13-bit and 17-bit accuracy in the audio-band and power consumption of about 1 mW. This performance proves that our techniques are sufficient for baseband analog interfaces.

Preliminary experiments on non-destructive quantitative analysis of water vapor density in halogen lamps have been carried out. A working curve showing a relation between absorbance and water vapor density was successfully obtained by using frequency-stabilized InGaAsP/InP semiconductor laser spectrometric system.

This paper deals with the synthesis of Petri nets. Partial languages adequately represent the concurrent behaviors of Petri nets. We first propose a construction problem for Petri nets, in which the objective is to synthesize a Petri net to exhibit the desired behavior specified as a partial language. We next discuss the solvability of this problem and last present the cutline of a solution technique.

In this paper, a multiuser receiver using a Hopfield network (Hopfield network receiver) for asynchronous codedivision multiple-access systems is proposed. We derive a novel likelihood function for the optimum demodulation of a data subsequence whose length is far shorter than that of the entire transmitted data sequence. It is shown that a novel Hopfield network receiver can be derived by exploiting the likelihood function, and the derived receiver leads to a low complexity receiver. The structure of the proposed receiver consists of a bank of correlators and a Hopfield network where the number of units is proportional to both the number of users and the length of a data sequence demodulated at a time. Computer simulation results are presented to compare the performance of the proposed receiver with those of the conventional multiuser detectors. It is shown that the proposed receiver significantly outperforms the correlation receiver, decorrelating detector and multistage detector, and provides suboptimum performnace.

A 3V-50 MHz analog CMOS current-mode continuous-time active filter with a negative resistance load (NRL) is proposed. In order to design a current-mode current integrator, a modified basic current mirror with a NRL to increase the output resistance is employed. The inherent circuit structure of the designed NRL current integrator, which minimizes the internal circuit nodes and enhances the gain bandwidth product, is capable of making the filter operate at the high frequency. The third order Butterworth low pass filter utilizing the designed NRL current integrator is synthesized and simulated with a 1.5 µm CMOS n-well process. Simulation result shows the cutoff frequency of 50 MHz and power consumption of 2.4mW/pole with a 3V power supply.

A direct-mapped cache takes less time for accessing data than a set-associative cache because the time needed for selecting a cache line among the set is not necessary. The hit ratio of a direct-mapped cache, however, is lower due to the conflict misses caused by mapping multiple addresses to the same cache line. Addressing cache memory by virtual addresses reduces the cache access time by eliminating the time needed for address translation. The synonym problem in virtual cache necessitates an additional field in the cache tag to denote the process to which cache line belongs. In this paper, we propose a new virtual cache architecture whose average access time is almost the same as the direct-mapped caches while the hit ratio is the same as the set-associative cashes. A victim for cache replacement is selected from those that belong to a process which is most remote from being scheduled. The entire cache memory is divided into n banks, and each process is assigned to a bank. Then, each process runs on the assigned bank, and the cache behaves like a direct-mapped cache. Trace-driven simulations confirm that the new scheme removes almost as many conflict misses as does the set-associative cache, while cache access time is similar to a direct-mapped cache.

The quality of a modular software system depends on the reliabilities of the software modules and the software operational profile. When the software is designed for multiple customers having different operational profiles, different customers may experience different software quality. It is important to ensure that no customer will suffer from a poor software quality. In this paper, we formulate and solve three reliability allocation problems for modular software system designed for multiple customers. In these reliability allocation problems, we consider the software operational profile of every customer while fulfilling such practical constraints as cost budget and software quality requirement. The numerical results show that when the operational profiles of the customers are more skewed, it is more beneficial to take their operational profiles into account.

This paper reports on a high-speed silicon bipolar transistor with an fT and fMAX of over 40 GHz, we call it the Advanced Boro-silicated-glass Self-Aligned (A-BSA) transistor. In basic BSA technology, a CVD-BSG film is used not only as a diffusion source to form the intrinsic base and the link base regions but also as a sidewall spacer between the emitter and the base polysilicon electrodes. An A-BSA transistor offers three advancements to this technology: (1) a graded collector profile underneath the intrinsic base region to suppress the Kirk effect; (2) an optimized design of the link base region to prevent the frade-off effect between fT and base resistance; and (3) a newly developed buried emitter electrode structure, consisting of an N++-polysilicon layer, a platinum silicide layer, and a CVD tungsten plug, to prevent the emitter plug effect. Furthermore, our transistor uses a BPSG filled trench isolation to reduce parasitic capacitance and improve circuit performance. In this paper, we describe device design, process technology and characterization of the A-BSA transistor, with it we have performed several application ICs, operating at 10Gb/s and above. The A-BSA transistor achieved an fT of 41 GHz and an fMAX of 44 GHz under optimized conditions.

Memory Sharing Processor Array (MSPA) architecture has been developed as an effective array processing architecture for both reduced data storages and increased processor cell utilization efficiency [1]. In this paper, the MSPA design methodology is extended to the VLSI synthesis of a serial input processor array (Pa). Then, a new bit-serial input multiplier and a new data serial input matrix multiplier are derived from the new PA. These multipliers are superior to the conventional multipliers by their smaller number of logic-gate count.

Recently, various efficient algorithms for solving combinatorial optimization problems using BDD-based set manipulation techniques have been developed. Minato proposed O-suppressed BDDs (ZBDDs) which is suitable for set manipulation, and it is utilized for various search problems. In terms of practical limits of space, however, there are still many search problems which are solved much better by using conventional branch-and-bound techniques than by using BDDs or ZBDDs, while the ability of conventional branch-and-bound approaches is limited by computation time. In this paper, an extension of APPLY operation, named APPRUNE (APply + PRUNE) operation, is proposed, which performs APPLY operation (ZBDD construction) and pruning simultaneously in order to reduce the required space for intermediate ZBDDs. As a prototype, a specific algorithm of APPRUNE operation is shown by assuming that the given condition for pruning is a threshold function, although it is expected that APPRUNE operation will be more effective if more sophisticated condition are considered. To reduce size of ZBDDs in intermediate steps, this paper also pay attention to the number of cared variables. As an application, an exact-minimization algorithm for generalized Reed-Muller expressions (GRMs) is implemented. From experimental results, it is shown that time and memory usage improved 8.8 and 3.4 times, respectively, in the best case using APPRUNE operation. Results on generating GRMs of exact-minimum number of not only product terms but also literals is also shown.

In this paper, we consider the protein structure alignment problem, which is a very important problem in molecular biology. Since an outline of protein structure is represented by a sequence of points in three-dimensional space, this problem is defined as the following geometric pattern matching problem: given two point sequences P and Q in three-dimensions and a real number δ > 0, find a maximum-cardinality set of point pairs such that the distance between each pair is at most δ under the condition that any translation and rotation can be applied to P. Since it is very difficult to solve this problem exactly, we consider algorithms that solve it approximately. We propose three algorithms: BASICALIGN, RANDALIGN and FRAGALIGN whose worst case time complexities are O(n8), O((n7/k3) polylog(n)) and O(n4) respectively, where n denotes the size of larger input structure and k denotes the minimum size of the alignment to be obtained. All of these have the following common framework: a series of initial superpositions are computed; for each of such superpositions, a rough alignment is first computed using a dynamic programming technique, and then it is refined through an iterative improvement procedure which also uses dynamic programming; the best alignment among them is selected as an output. The difference among three algorithms lies in the methods of finding initial superpositions. BASICALIGN, RANDALIGN and FRAGALIGN use exhaustive search, random sampling technique and fragment-based search, respectively. We prove guaranteed approximation ratios (in the sense of distances between point pairs) for theoretical versions of BASICALIGN and RANDALIGN. Practical versions of RANDALIGN and FRAGALIGN were implemented and compared with a previous algorithm using real protein structure data. The experimental results show that FRAGALIGN is best among them and it outputs good alignments quickly.

In this paper, we introduce a parallel algorithm for parsing context-free languages. Our algorithm can handle arbitrary context-free grammars since it is based on Earley's algorithm. Our algorithm can operate on any loosely coupled multiprocessor which can provide a topology of a one-way ring. Our algorithm uses p processors to parse an input string of length n where 1 p n. It is shown that our algorithm requires O(n3/p) time. The algorithm uses a simple job allocation strategy. However, it achieves high load balancing and uses the processors efficiently.

This paper describes an N-type and a P-type MOS cascode circuit based on the square-law characteristics of an MOS transistor in saturation region. The transconductance parameter ratios of an upper and a lower MOS transistor are set to be 1: n2 for the N-type MOS cascode circuit and n2: 1 for the P-type MOS cascode circuit. The N and P-type MOS cascode circuits are divided to four types by the difference of connections of input terminals. We consider the input-output relations of each type circuit. The second-order effects of the circuit such as channel length modulation effect, mobility reduction effect and device mismatch are analyzed. As applications, an analog voltage adder and a VT level shifter using MOS cascode circuits are presented. All of the proposed circuits are very simple and consist of only the N and P-type MOS cascode circuits. The proposed circuits aer confirmed by SPICE simulation with MOSIS 1.2µm CMOS process parameters.

In this paper stochastic aradient adaptive filters using the Sign or Sign-Sign Algorithm are analyzed based upon general assumptions on the reference signal, additive noise and particularly jointly distributed tap errors. A set of difference equations for calculating the convergence process of the mean and covariance of the tap errors is derived with integrals involving characteristic function and its derivative of the tap error distribution. Examples of echo canceller convergence with jointly Gaussian distributed tap errors show an excellent agreement between the empirical results and the theory.

In this paper, we propose a clustering based linear ordering algorithm which consists of global ordering and local ordering. In the global ordering, the algorithm forms clusters from n given vertices and orders the clusters. In the local ordering, the elements in each cluster are linearly ordered. The linear order, thus produced, is used to obtain optimal κ-way partitioning based on scaled cost objective function. When the number of cluster is one, the proposed algorithm is exactly the same as MELO [2]. But the proposed algorithm has more global partitioning information than MELO by clustering. Experiment with 11 benchmark circuits for κ-way (2 κ 10) partitioning shows that the proposed algorithm yields an average of 10.6% improvement over MELO [2] for the κ-way scaled cost partitioning.

In outdoor fields such as construction, mining and agriculture, there is an increasing demand for autonomous vehicles to reduce labor costs. Also, a positioning system is one key technology required for autonomous vehicle systems. For the purpose of expanding the potential of millimeter-wave applications, we have developed a positioning system in the 77-79 GHz frequency band, using the hyperbolic radio navigation method. This system operates in a restricted area with a radius of about a few hundred meters. A spread spectrum with a PN code is used as the ranging signals. We realized about 0.1 m in positioning accuracy.