Clustering is almost essential in improving the performance of iterative partitioning algorithms. In this paper, we present a clustering algorithm based on the following observation: if a group of cells is assigned to the same partition in numerous local optimum solutions, it is desirable to merge the group into a cluster. The proposed algorithm finds such a group of cells from randomly generated local optimum solutions and merges it into a cluster. We implemented a multilevel bipartitioning algorithm (MBP) based on the proposed clustering algorithm. For MCNC benchmark netlists, MBP improves the total average cut size by 9% and the total best cut size by 3-4%, compared with the previous state-of-the-art partitioners.

In this paper, a new feature which is characterized by the extrema density of 2-D wavelet frames estimated at the output of the corresponding filter bank is proposed for texture segmentation. With and without feature selection, the discrimination ability of features based on pyramidal and tree-structured decompositions are comparatively studied using the extrema density, energy, and entropy as features, respectively. These comparisons are demonstrated with separable and non-separable wavelets. With the three-, four-, and five-category textured images from Brodatz album, it is observed that most performances with feature selection improve significantly than those without feature selection. In addition, the experimental results show that the extrema density-based measure performs best among the three types of features investigated. A Min-Min method based on genetic algorithms, which is a novel approach with the spatial separation criterion (SPC) as the evaluation function is presented to evaluate the segmentation performance of each subset of selected features. In this work, the SPC is defined as the Euclidean distance within class divided by the Euclidean distance between classes in the spatial domain. It is shown that with feature selection the tree-structured wavelet decomposition based on non-separable wavelet frames has better performances than the tree-structured wavelet decomposition based on separable wavelet frames and pyramidal decomposition based on separable and non-separable wavelet frames in the experiments. Finally, we compare to the segmentation results evaluated with the templates of the textured images and verify the effectiveness of the proposed criterion. Moreover, it is proved that the discriminatory characteristics of features do spread over all subbands from the feature selection vector.

It is an important problem in signal processing, system realization and system identification to find linear discrete-time systems which are consistent with given covariance parameters. This problem is formulated as a problem of finding discrete-time positive real functions which interpolate given covariance parameters. Various investigations have yielded several significant solutions to the problem, while there remains an important open problem concerning the McMillan degree. In this paper, we use more general input-output characteristics than covariance parameters and consider finding discrete-time positive real matrix functions which interpolate such characteristics. The input-output characteristics are given by the coefficients of the Taylor series at some complex points in the open unit disk. Thus our problem is a generalization of the interpolation problem of covariance parameters. We reduce the problem to a directional interpolation problem with a constraint and develop the solution by a state-space based new approach. The main results consist of the necessary and sufficient condition for the existence of the discrete-time positive real matrix function which interpolates the given characteristics and has a limited McMillan degree, and a parameterization of all such functions. These are a contribution to the open problem and a generalization of the previous result.

We have developed a low-latency, error-correcting-code-(ECC-)adaptable skew-compensation technique, which is needed for high-speed and long-distance parallel optical interconnections. A new frame-coding technique called shuffled mB1C encoding, which requires no clock-rate conversion circuit and no data buffering, and a new skew-measurement method which is suitable for ECC adaptation have been developed for the compensation. Full-digital skew-compensation circuits using these new techniques were able to compensate for a two-clock-cycle skew, even when one transmission channel was removed. The maximum latency for skew compensation was only five clock cycles.

We have developed a low-latency, error-correcting-code-(ECC-)adaptable skew-compensation technique, which is needed for high-speed and long-distance parallel optical interconnections. A new frame-coding technique called shuffled mB1C encoding, which requires no clock-rate conversion circuit and no data buffering, and a new skew-measurement method which is suitable for ECC adaptation have been developed for the compensation. Full-digital skew-compensation circuits using these new techniques were able to compensate for a two-clock-cycle skew, even when one transmission channel was removed. The maximum latency for skew compensation was only five clock cycles.

Precise plastic V-grooved alignment parts for connecting single-mode optical fiber arrays to multi-port optical devices were successfully molded with a thermosetting resin by using a highly productive injection molding technique. The molded parts are two types of V-grooved blocks that are compatible with the size of optical devices having eight or twelve optical ports. Their dimensional accuracy must be better than 1 µm over the whole length of the V-grooves for efficient optical coupling. This strict requirement was satisfied using precisely processed molding tools with a specially chosen resin under optimum molding conditions. The feasibility of the optical alignment parts was assured by an evaluation of their loss characteristics and reliability in coupling single-mode fibers to 18 power splitters, where the average optical loss was 0.2 dB and the change in loss was less than 0.2 dB under a temperature cycling test and also under a damp heat test. These results show that plastic molded parts can be used for precise coupling of single-mode optical devices, and will lead to a breakthrough in innovation in the field of optical packaging.

Precise plastic V-grooved alignment parts for connecting single-mode optical fiber arrays to multi-port optical devices were successfully molded with a thermosetting resin by using a highly productive injection molding technique. The molded parts are two types of V-grooved blocks that are compatible with the size of optical devices having eight or twelve optical ports. Their dimensional accuracy must be better than 1 µm over the whole length of the V-grooves for efficient optical coupling. This strict requirement was satisfied using precisely processed molding tools with a specially chosen resin under optimum molding conditions. The feasibility of the optical alignment parts was assured by an evaluation of their loss characteristics and reliability in coupling single-mode fibers to 18 power splitters, where the average optical loss was 0.2 dB and the change in loss was less than 0.2 dB under a temperature cycling test and also under a damp heat test. These results show that plastic molded parts can be used for precise coupling of single-mode optical devices, and will lead to a breakthrough in innovation in the field of optical packaging.

In this paper, a general formula of disparity estimation based on Bayesian Maximum A Posteriori (MAP) algorithm is derived and implemented with simplified probabilistic models. The formula is the generalized probabilistic diffusion equation based on Bayesian model, and can be implemented into some different forms corresponding to the probabilistic models in the disparity neighborhood system or configuration. The probabilistic models are independence and similarity among the neighboring disparities in the configuration. The independence probabilistic model guarantees the discontinuity at the object boundary region, and the similarity model does the continuity or the high correlation of the disparity distribution. According to the experimental results, the proposed algorithm had good estimation performance. This result showes that the derived formula generalizes the probabilistic diffusion based on Bayesian MAP algorithm for disparity estimation. Also, the proposed probabilistic models are reasonable and approximate the pure joint probability distribution very well with decreasing the computations to O(n()) from O(n()4) of the generalized formula.

A novel millimeter-wave on-wafer CAT(Computer-Aided-Testing ) system has been developed for measurement of S-parameters and NF ( Noise figure ). For the S-parameter test system, we have developed a holder setup and installed it in a semi-automatic wafer prober so that the waveguide-based T/R module can be directly connected to a probe-head through fixed waveguides, which feature low insertion loss of less than 2 dB, from 75 GHz to 98 GHz. The accuracy of the developed test system was confirmed by measuring, with this system, a co-planar offset short pattern then comparing measured and simulated results. A good agreement between the measured and calculated, in both return loss and return phase successfully demonstrated the superiority of the system. A W-band NF test system with a system noise of less than 8 dB has been also developed to provide an on-wafer NF measurement capability with an accuracy of 0.3 dB. These S-parameter and NF test systems possess great advantages to achieve high-speed automatic MMIC testing up to W-band.

When designing microwave amplifiers, it is the task to select values of the source (input generator) and load reflection coefficients for the transistor, to achieve certain amplifier performance requirements and ensure stability. For unconditionally stable transistors, simultaneous conjugate matching can be achieved using well-known design formulae. Under this condition, the gain is maximised, and the input and output ports are matched. On the other hand when the transistor is conditionally stable, source and load reflection coefficients are selected using graphical design methods, involving gain and stability circles. To eliminate the reliance on graphical techniques, this paper shows the derivation of explicit design formulae that ensure maximum gain for a minimum specified safety margin, with one port matched. In this work, the safety margin is the distance between the chosen source or load reflection coefficient and its respective stability circle. In a production environment, where the circuit and transistor parameters are subject to random variations, the safety margin therefore makes allowance for such variations. This paper shows that the design problem for conditionally stable transistors can be reduced from the selection of values for two complex variables (port terminations) to the selection of the value for just one scalar variable.

In this paper, by making good use of the parallel-transit-evaluation algorithm and sparsity of the connection between neurons, a pipeline structure is successfully introduced to the sequential Boltzmann machine processor. The novel structure speeds up nine times faster than the previous one, with only the 12% rise in hardware resources under 10,000 neurons. The performance is confirmed by designing it using 1.2 µm CMOS process standard cells and analyzing the probability of state-change.

This research presents a novel analytic model to predict the instruction execution rate of superscalar processors using the queuing model with finite-buffer size and synchronous operation mode. The proposed model is also able to analyze the performance relationship between cache and pipeline. The proposed model takes into account various kinds of architectural parameters such as instruction-level parallelism, branch probability, the accuracy of branch prediction, cache miss, and etc. To prove the correctness of the model, we performed extensive simulations and compared the results with the analytic model. Simulation results showed that the proposed model can estimate the average execution rate accurately within 10% error in most cases. The proposed model can explain the causes of performance bottleneck which cannot be uncovered by the simulation method only. The model is also able to show the effect of the cache miss on the performance of out-of-order issue superscalar processors, which can provide an valuable information in designing a balanced system.

Existing multimedia processors having millions of transistors are not suitable for portable multimedia services and existing fixed-point DSP chips having fixed data formats are not appropriate for multimedia applications. This paper proposes a multimedia fixed-point DSP (MDSP) chip for portable multimedia services and its chip implementation. MDSP employs parallel processing techniques, such as SIMD, vector processing, and DSP techniques. MDSP can handle 8-, 16-, 32- or 40-bit data and can perform two MAC operations in parallel. In addition, MDSP can complete two vector operations with two data movements in a cycle. With these features, MDSP can handle both 2-D video signal processing and 1-D signal processing. The prototype MDSP chip has 68,831 gates, has been fabricated, and is running at 30 MHz.

This paper discusses the implementation and cost- and performance- evaluations of a distributed processing network, called DONA-α, which is one of the possible physical networks mainly implementing connection-oriented public switched network functions corresponding to OSI layers 1 to 3. The first feature of the DONA-α network is that it separates a switching subsystem and a control subsystem of a conventional switching system and independently allocates them over distributed nodes as a switching node and a control node. Each DONA-α switching node is given a much smaller switching capacity than the switching subsystem of the conventional switching system and is located near subscribers. In contrast, each DONA-α control node has much higher performance than the control subsystem of the conventional switching system. This allows a large number of switching nodes to share the same control node, which controls their connection setups. This separation provides the network with greater flexibility and allows more effective utilization of network resources, such as control processors, switching fabrics, and transmission links, than ever before. The second feature of DONA-α is that it provides a network with network-wide distribution transparency. This allows network resources including software such as databases and application programs to be shared and therefore to be utilized in the network more easily and more efficiently. The results of a network performance simulation and cost calculation confirm the viability of the DONA-α network.

For given undirected graph G[V,E] and vertices s and t, a minimal s-t separating set denoted by Ec & Vc is a minimal set of elements (edges and/or vertices) such that deletion of the elements from G breaks all the paths between s and t, where Ec and Vc are sets of edges and vertices, respectively. In this paper, we consider a problem of generating all minimal s-t separating sets, and show that the problem can be solved in O(µ(mt(n,n))) time, where m|E|, n|V|, µ is the number of minimal s-t separating sets of G, and t(p,q) is the time needed for finding q lowest common ancestors for q pairs of vertices in a rooted tree with p vertices. Since t(n,n) can be O(n), we can generate all minimal s-t separating in linear time per s-t separating set. However, the linear time algorithm for finding the lowest common ancestors is complicated, so that it is not efficient for a moderate size graph. Therefore, we use an O(nα (n))-time algorithm for finding the lowest common ancestors, and propose an algorithm to generate all minimal s-t separating sets in O(mnα(n)) time per s-t separating set, where α(n) is the pseudo-inverse of Ackermann function.

A neuron-MOS transistor (νMOS) is applied to current-mode multi-valued logic (MVL) circuits. First, a novel low-voltage and low-power νMOS current mirror is presented. Then, a threshold detector and a quaternary T-gate using the proposed νMOS current mirrors are proposed. The minimum output voltage of the νMOS current mirror is decreased by VT (threshold voltage), compared with the conventional double cascode current mirror. The νMOS threshold detector is built on a νMOS current comparator originally composed of νMOS current mirrors. It has a high output swing and sharp transfer characteristics. The gradient of the proposed comparator output in the transfer region can be increased 6.3-fold compared with that in the conventional comparator. Along with improved operation of the novel current comparator, the discriminative ability of the proposed νMOS threshold detector is also increased. The performances of the proposed circuits are validated by HSPICE with Motorola 1.5 µm CMOS device parameters. Furthermore, the operation of a νMOS current mirror is also confirmed through experiments on test chips fabricated by VDEC*. The active area of the proposed νMOS current mirror is 63 µm 51 µm.

A variable partition duplex scheme on packet reservation multiple access protocol (VPD-PRMA) is analyzed in this paper. We assume a four-state speech model for a conversational pair and successfully obtain performance measures by approximate Markovian analysis. Analytical results show that they quite fit simulation results; and VPD-PRMA can get higher statistical multiplexing gain than fixed partition duplex (FPD)-PRMA, due to the trunking effect. We further investigate the effect of design parameters of permission probability and enlarged reservation duration on system performance by computer simulation. Simulation results shows that it exists appropriate values for these two design parameters so that the packet dropping probability can be minimized. The adjustment of permission probability can greatly improve the performance of uplink traffic with slight deterioration of the performance of downlink traffic; the provision of enlarged reservation duration scheme can enhance the system performance.

This paper proposes the UGLR parser as an extension of the GLR parser. A UGLR parser is powerful enough to parse deterministically any phrase structure language if it is in the class of recursive languages and can parse any context free language as fast as the conventional GLR parser. Natural language processing often requires a parser for languages belonging to classes larger than that of context free languages, and the proposed parser is useful for this purpose.

This paper presents a contact-less connector using proximity coupling through a parasitic element. For example, proximity coupling is used for interconnect of microstrip lines for DC-break structure. We also present a cross wiring structure using this interconnect.

The self-healing capability against network failure is one of indispensable features for the B-ISDN infrastructure. One problem in realizing such self-healing backbone network is the inefficient utilization of the large spare capacity designed for the failure-restoration purpose since it will be used only in the failure time that does not occur frequently. "Pool-capacity" is the concept that allows some VPs (virtual paths) to efficiently utilize this spare capacity part. Although the total capacity can be saved by using the "Pool Capacity," it is paid by less reliability of VPs caused by the emerging influence of indirect-failure. Thus, this influence of indirect-failure has to be considered in the capacity designing process so that network-designers can trade off the saving of capacity with the reliability level of VPs in their self-healing networks. In this paper, Damage Rate:DR which is the index to indicate the level of the influence caused by indirect-failure is defined and the pool-capacity design scheme with DR consideration is proposed. By the proposed scheme, the self-healing network with different cost (pool-capacity) can be designed according to the reliability level of VPs.