A nearly equitable edge-coloring of a multigraph is a coloring such that edges incident to each vertex are colored equitably in number. This problem was solved in O(kn2) time, where n and k are the numbers of the edges and the colors, respectively. The running time was improved to be O(n2/k + n|V|) later. We present a more efficient algorithm for this problem that runs in O(n2/k) time.

Recent advances in measurement techniques for microwave active devices and circuits are reviewed in this paper. The R&D activities have been devoted aggressively how to characterize nonlinear performance of high power devices and circuits. They are pulsed I-V, a variety of load-pull measurements, probing, sampling, and sensing techniques, supported by the recent significant advances in DSP (Digital Signal Processing), RF components, semiconductor devices, etc. The recent advances in vector network analyzers are of our great interest. They are (a) multi-port vector network analyzers for characterizing mixers, differential devices, packaged components, electronic package characterization, and multi-layer transmission lines, and (b) EO (Electro-Optic) modulated vector network analyzers for characterizing electronic performance of EO devices with the aid of EO modulators and photonic probes. In addition, probing, sampling, and sensing techniques have made great progress to directly measure electromagnetic field, time-domain voltage waveform, and temperature in small spot areas. In this paper, some topics related to these measurement techniques are briefly reviewed. Then the existing and future issues for characterization and measurement techniques of microwave active devices and circuits are discussed.

A band-pass delta-sigma modulator (BPDSM) is a key building block to implement a digital intermediate frequency (IF) receiver in a wireless communication system. This paper proposes a time-interleaved (TI) switched-capacitor (SC) BPDSM architecture that consists of 5-stage TI blocks with recursive loop. The proposed TI BPDSM provides reduction in the clock frequency requirement by a factor of 5 and relaxes the settling time requirement to one-fourth of conventional approach. The test chip was designed and fabricated for a 30-MHz IF system with a 0.35-µm CMOS process. The measured peak SNR for a 200-kHz bandwidth is 63 dB while dissipating 75 mW from a 3.3-V supply and occupying 1.3 mm2.

A K-band monolithic driver amplifier with equalizer circuits has been developed. It is necessary for the equalizer circuit to be low losses in the high-frequency range and for its S21 values to increase as the operation frequency increases. In order to realize these features, it is desirable for the equalizer to have element location considering high-frequency current flows. In this paper, we present a novel low-loss, high-pass equalizer circuit layout that has superior characteristics in the high-frequency range. We used a high-pass filter as the equalizer circuit and performed a detailed evaluation of the high-frequency characteristics of the filter circuit test element groups (TEGs) for three layout types. It was found that the best filter circuit layout for the three types consisted of two capacitors and one resistor, placed with parallel connections. The resistor is located at the center and the capacitors are located at both sides of the resistor. This filter is called the CRC-type in this paper. An MMIC test sample, a K-band monolithic amplifier with CRC-type filter circuits, was fabricated. The amplifier had a gain of 21.6 dB, a Rollett stability factor K of 28.9, an input VSWR of 1.63, an output VSWR of 1.92, and a 1 dB compressed output power of 22.6 dBm at 26 GHz.

A hybrid method-of-moments (MoM) and immittance approach for efficient and accurate analysis of printed slots and strips of arbitrary shape in layered waveguide for various applications has been proposed. An impedance-type MoM is formulated from the electric field integral equation (EFIE) for printed strip case and an admittance-type MoM is formulated from the magnetic field integral equation (MFIE) for the printed slot case, using the Galerkin's technique. Immittance approach has been used to calculate spectral dyadic Green's functions for the layered waveguide. For efficient analysis of large and complex structures, equivalent circuit parameters of a block are first extracted and complete structure is analyzed through cascaded ABCD matrices. The equivalent circuit characterization of printed strip and slot in layered waveguide has been done for the first time. Finite periodic structure loaded with printed strips has been investigated and it shows the electromagnetic bandgap (EBG) behavior. The electromagnetic (EM) program hence developed is checked for its numerical accuracy and efficiency with results generated with High-frequency structure simulator (HFSS) and shows good performance.

Finite-ground microstrip line (FGMSL) open-end discontinuities are characterized via a self-calibrated method of moments (MoM) as a unified circuit model with a fringing capacitance and radiation conductance. By integrating the short-open calibration (SOC) procedure into a determinant MoM, the model parameters are extracted without needing the alternative port impedance. Regardless of non-ideal voltage sources, extracted parameters are observed to achieve a stable convergence as the feeding line is sufficiently extended. After extracted capacitance of a FGMSL open-end with equal strip and finite-ground widths are validated against its traditional MSL counterpart with infinite ground, extensive results are given to originally demonstrate that the capacitance increases as a decelerated function of the finite-ground width and length while the conductance is negligibly small as compared with its imaginary part.

A power-aware interconnect circuit design--called µI/O architecture--has been developed to provide low-cost system solutions for System-on-Chip (SoC) and System-in-Package (SiP) technologies. The µI/O architecture provides a common interface throughout the module enabling hierarchical I/O design for SoC and SiP. The hierarchical I/O design allows the driver size to be optimized without increasing design complexity. Moreover, it includes a signal-level converter for integrating wide-voltage-range circuit blocks and a signal wall function for turning off each block independently--without invalid signal transmission--by using an internal power switch.

Circuit partition, retiming and state reordering techniques are effective in reducing power consumption of circuits. In this paper, we propose a partition architecture and a methodology to reduce power consumption when designing low power IP, named PRC (Partition and Reordering Circuit). The circuit reordering synthesis flow consists of three phases: first, evenly partition the circuit based on the Shannon expansion; secondly encode the output vectors of each partition to build an equivalent functional logic. Finally, apply reordering algorithm to reorganize the logic function to reduce power consumption and decrease area cost. The validity of our architecture is proven by applying it to MCNC benchmark with simulation environment.

Finding DC operating points of transistor circuits is an important and difficult task. The Newton-Raphson method adopted in SPICE-like simulators often fails to converge to a solution. To overcome this convergence problem, homotopy methods have been studied from various viewpoints. For efficiency of globally convergent homotopy methods, it is important to give an appropriate initial solution as a starting point. However, there are few studies concerning such initial solution algorithms. In this paper, initial solution problems in homotopy methods are discussed, and an effective initial solution algorithm is proposed for globally convergent homotopy methods, which finds DC operating points of transistor circuits efficiently. Numerical examples using practical transistor circuits show the effectiveness of the proposed algorithm.

A new multiple-valued current-mode (MVCM) logic circuit using substrate bias control is proposed for low-power VLSI systems at higher clock frequency. Since a multi-level threshold value is represented as a threshold voltage of an MOS transistor, a voltage comparator is realized by a single MOS transistor. As a result, two basic components, a comparator and an output generator in the MVCM logic circuit can be merged into a single MOS differential-pair circuit where the threshold voltages of MOS transistors are controlled by substrate biasing. Moreover, the leakage current is also reduced using substrate bias control. As a typical example of an arithmetic circuit, a radix-2 signed-digit full adder using the proposed circuit is implemented in a 0.18- µm CMOS technology. Its dynamic and static power dissipations are reduced to about 79 percent and 14 percent, respectively, in comparison with those of the corresponding binary CMOS implementation at the supply voltage of 1.8 V and the clock frequency of 500 MHz.

We have developed a high-efficiency charge-pump power supply circuit with large output current capability for mobile equipment. However, during the commercialization phase, we found that the large inrush current of 270 mA at charge-pump circuit startup-time could cause problems. In this paper we analyze the mechanism that causes this inrush current, and we propose circuitry to reduce it. We show SPICE simulation and measurement results for our proposed circuitry that confirm its effectiveness. By incorporating this circuitry, startup-time inrush current was reduced to 30 mA.

A new power-down circuit scheme using data-preserving complementary pass transistor flip-flop circuit for low-power, high-performance Multi-Threshold voltage CMOS (MTCMOS) LSI is presented. The proposed circuit can preserve a stored data during power-down period while maintaining low leakage current without any extra circuit and complex timing design. The flip-flop provides 24% improved delay and 30% less silicon area compared to conventional MTCMOS flip-flop circuit. A 16-bits DSP processor core using the proposed circuit and 0.18 µ m CMOS technology was designed. The DSP chip was successfully operated at 120 MHz, 1.65 V and its total leakage current in power-down mode was four orders smaller than conventional DSP chip.

A silicon (Si) wire waveguiding system fabricated on silicon-on-insulator (SOI) substrates is one of the most promising platforms for highly-integrated, ultra-small optical circuits, or microphotonics devices. The cross-section of the waveguide's core is about 300-nm-square, and the minimum bending radius are a few micrometers. Recently, crucial problems involving propagation losses and in coupling with external circuits have been resolved. Functional devices using silicon wire waveguides are now being tested. In this paper, we describe our recent progress and future prospects on the microphotonics devices based on the silicon-wire waveguiding system.

When LSIs that are designed and manufactured for low power dissipation are tested, test vectors that make the power dissipation low should be applied. If test vectors that cause high power dissipation are applied, incorrect test results are obtained or circuits under test are permanently damaged. In this paper, we propose a method to generate test sequences with low power dissipation for sequential circuits. We assume test sequences generated by an ATPG tool are given, and modify them while keeping the original stuck-at fault coverages. The test sequence is modified by inverting the values of primary inputs of every test vector one by one. In order to keep the original fault coverage, fault simulation is conducted whenever one value of primary inputs is inverted. We introduce heuristics that perform fault simulation for a subset of faults during the modification of test vectors. This helps reduce the power dissipation of the modified test sequence. If the fault coverage by the modified test sequence is lower than that by the original test sequence, we generate a new short test sequence and add it to the modified test sequence.

When a feedback bridging fault occurs in a combinational circuit and it is activated, logical oscillation may occur in the circuit. In this paper, some electrical conditions are proposed to identify whether a feedback bridging fault occurs logical oscillation. Also, it is proposed how to estimate the oscillation frequency. They are based on piece linearlized models and do not require circuit simulation of large size of circuits. They are evaluated by some experiments. In the experiments, all of the feedback bridging faults occurring logical oscillation are identified. Also, oscillation frequencies larger than the ones obtained by SPICE simulation are derived by the proposed estimation method in the experiments. It promises us that the methods will be used for identifying such bridging faults and estimating the oscillation frequencies.

In this paper, we analyze behaviors of bridging faults in CMOS synchronous sequential circuits based on transient analysis. From analysis results, we expose dynamic and analog behaviors of the circuit caused by the bridging faults, which are oscillation, asynchronous sequential behavior, IDDT failure and IDDQ failure as well as logic error. In order to detect this kind of fault, we show that not only IDDQ testing but also IDDT testing and logic testing which guarantees correct state transitions are required.

In this paper, test time reduction for IDDQ testing is discussed. Although IDDQ testing is known to be effective to detect faults in CMOS circuit, test time of IDDQ testing is larger than that of logic testing since supply current is measured after a circuit is in its quiescent state. It is shown by simulation that test time of IDDQ test mostly depends on switching current. A procedure to modify test vectors and a procedure to arrange test vectors are presented for reducing the test time of IDDQ testing. A test sequence is modified such that switching current quickly disappears. The procedure utilizes a unit delay model to estimate the time of the last transition of logic value from L to H in a circuit. Experimental results for benchmark circuits show the effectiveness of the procedure.

We describe new architectures for micro-fabrication of large-scale PBG materials. A universal approach to embedding optical circuitry within a planar defect layer is illustrated for the square spiral and inverse opal PBG materials.

In this paper we describe a method for the automated design of analog circuits. The method simultaneously sizes the different components (transistors, capacitors, etc.) in a pre-defined circuit topology and places them according to a pre-defined slicing tree. The method is based on formulating the circuit physical and electrical behavior in a special convex form. More specifically, we cast the design problem as a geometric program, a special type of convex optimization problem. Therefore, all design constraints are formulated as posynomial inequality or monomial equality constraints. Very efficient numerical algorithms are then used to solve the resulting geometric program and to create the design that meets the desired specifications. The formulation is hierarchical and modular, allowing easy topology re-use and process porting. The synthesis method is fast, and determines the globally optimal design; in particular the final solution is completely independent of the starting point, and infeasible specifications are unambiguously detected. After a brief overview of current analog design automation solutions, we describe our method and provide some design examples for op-amps and analog-to-digital converters.

A switched capacitor DC-DC voltage converter that has an arbitrary conversion ratio of rational number is presented. A given voltage conversion ratio is systematically expanded to construct a switched capacitor circuit that operates with a two-phase switching clock. The conversion ratio is completely free from capacitance values and ratios under the assumption that there is no charge transfer between the two switching phases. This means that the converter cannot supply any power to the load. This restricts the application of the converters to a very limited area such as a voltage reference generator that only provides a reference voltage and no power to a circuit. The conditions for the convergence of the output voltage and the stray capacitor effects are discussed. The output voltage error and required switching frequency are also discussed when the converter is used as a DC voltage supply source that provides power to a load.