This paper deals with the problem of assigning tasks to the processors of a multiprocessor system such that the sum of execution and communication costs is minimized. If the number of processors is two, this problem can be solved efficiently using the network flow approach pioneered by Stone. This problem is, however, known to be NP-complete in the general case, and thus intractable for systems with a large number of processors. In this paper, we propose a network flow approach for the task assignment problem in homogeneous hypercube networks, i.e., hypercube networks with functionally identical processors. The task assignment problem for an n-dimensional homogeneous hypercube network of N (=2n) processors and M tasks is first transformed into n two-terminal network flow problems, and then solved in time no worse than O(M3 log N) by applying the Goldberg-Tarjan's maximum flow algorithm on each two-terminal network flow problem.

Multiple-site diversity systems are foreseen for earth to satellite paths operating at frequencies above 10GHz in localities with high rain-induced attenuation. In some severe cases double-site protection can be proved to be inadequate and consequently triple-site diversity becomes indispensable. In the present paper, an approach for the prediction of the triple-site diversity performance based on an appropriate three-dimensional gamma distribution is proposed. The model is oriented for application to earth-space paths located in Japan and other locations with similar climatic conditions. Numerical results are compared with the only available set of experimental data taken from some parts of the United States. Some useful conclusions are deduced.

A photonic switching system is expected to have advantages over a conventional electronic switching system in exchanging broadband signals. Extensive studies have recently done on various photonic switching systems. State-of-art technology in photonic switching systems is surveyed in this paper. Small-capacity space-division switching systems using waveguide optical matrix switches are most practical and expected to be introduced to broadband local-area network in the near future. Wavelength division switching technology is important in extending switching capacity to large value. Application of photonic switching technology for ATM switching systems is also recently extensively studied to achieve switching throughput larger than that of electronic ATM switches.

This paper presents a high-speed low power ac-coupled complementary push-pull ECL (AC-PP-ECL) circuit. The circuit utilizes two capacitors to couple a transient voltage pulse from the common-emitter node of the switching transistors to the base of a pair of complementary p-n-p/n-p-n push-pull transistors to provide a large transient current during switching. In addition to a reduction of the power consumption and improvement in the pull-up and pull-down capability of the output stage, the circuit scheme completely decouples the collector load resistor Rc from the delay path, thus allowing a very small switching current to be used for the logic (current switch) stage without degrading the performance. Based on a 0.8-µm double-poly self-aligned complementary bipolar process at a power consumption of 0.5 mW/gate, the circuit offers 2.1 improvement in both the speed and load driving capability for a loaded gate compared with the conventional ECL circuit. The design and scaling considerations of the circuit are discussed.

This paper describes a new biasing scheme for sensing circuits, namely an automated bias control (ABC) circuit, for high-performance VLSI's. The ABC circuit can automatically gear the output level of sensing circuits to the input threshold voltage of the succeeding CMOS converters. The sensing performance can be accelerated with the ABC circuit either by reducing excessive signal level margin between the sensing circuits and the CMOS converters or by reducing extra stage of signal amplification. Since feedback control of the ABC circuit ensures a correct dc biasing even under large process deviation and circuit condition changes, wider operation margin can also be obtained. Three successful applications of the ABC circuit are reported: a sense amplifier, an address transition detector (ATD), and an ECL-CMOS input buffer. A 64-kb BiCMOS SRAM employing the proposed sense amplifier and the ATD has been fabricated with a 0.8-µm 9-GHz BiCMOS technology. The SRAM has an address access time of 4.5 ns.

In intelligent robots capable of autonomous work, the development of a high-performance special-purpose VLSI processor for collison detection will become very important for automatic motion planning. Conventionally, this kind of processing is performed by general-purpose processors. In this paper, a first collision detection VLSI processor is proposed to achieve ultrahigh-performance processing with an ideal parallel processing scheme. A large number of coordinate transformations and memory accesses to the obstacle memory are fully utilized in the processing algorithm, so that direct collision detection can be executed with a VLSI-oriented regular data flow. The structure of each processing element (PE) is very simple because a PE mainly consists of a COordinate Rotation DIgital Computer (CORDIC) arithmetic unit for the coordinate transformation and memories for the storage of manipulator and obstacle information. When 100 PE's are used to make parallel processing, the performance is about 10 000 times faster than that of conventional approaches using a single general-purpose microprocessor.

An application of wavelength conversion laser diodes (WCLDs) to a photonic cross-connect system using wavelength-division (WD) technology is presented. We propose a novel WD photonic cross-connect node architecture with multiwavelength selective filters. By using the filters, we can construct a nonblocking cross-connect switch by 2-stage connection. Next we describe the requirements to the optical devices in our switch, especially to the wavelength conversion devices in configuring a multistage connection of our switch. Finally, we have conducted the wavelength switching experiments using our wavelength conversion laser diode at a bit rate of 125Mb/s and shown its applicability to a WD photonic cross-connect system with over 3,000 channels.

A frame-installed lightwave synthesizer is constructed for optical frequency-division-multiplexing (FDM) communication. The synthesizer consists of two DFB diode lasers, electrical feedback loops, and an HCN gas cell used as a frequency reference at v0=192,843GHz (1.55459µm in wave-length). Output frequency can be stabilized at anywhere within v0(220) GHz. The beat note observed between the synthesizer and another HCN-stabilized DFB laser is constant within 2MHz over 100 hours. Frequency stability better than 410-10 (80kHz, without normalization) is obtained for an averaging time of 200s.

This paper presents a simple method for avoiding both numerical errors and degeneracy in an incremental-type algorithm for constructing the Voronoi diagram with respect to points on a plane. It is assumed that the coordinates of the given points are represented with a certain fixed number of bits. All the computations in the algorithm are carried out in four times higher precision, so that degeneracy can be discerned precisely. Every time degeneracy is found, the points are perturbed symbolically according to a very simple rule and thus are reduced to a nondegenerate case. The present technique makes a computer program simple in the sense that it avoids all numerical errors and requires no exceptional branches of processing for degenerate cases.

A high-gain wide-band amplifier IC module is needed for high-speed communication systems. However, it is difficult to expand bandwidth and maintain stability. This is because small parasitic influences, such as bonding-wire inductance or the capacitance of the package, become large at high frequencies, thus degrading performance or causing parasitic oscillation. In this paper, a new design procedure is proposed for the high-gain and wide-band IC module, using stability analysis and a unified design methodology for IC's and packages. A multichip structure is developed using stability analysis and the requirements for stable operation are determined for each IC chip, package, and interface condition between them. Furthermore, to reduce the parasitic influences, several improvements in the interface and package design are clarified, such as wide-band matching and LC resonance damping. IC design using effective feedback techniques for enlarging the bandwidth are also presented. The IC's are fabricated using 0.2-µm GaAs MESFET IC technology. To verify the validity of these techniques, an equalizer IC module for 10-Gb/s optical communication systems was fabricated achieving a gain of 36 dB and a bandwidth of 9 GHz.

Two high-speed sensing techniques suitable for ultrahigh-speed SRAM's are proposed. These techniques can reduce a 64-kb SRAM access time to 71 89% of that of conventional high-speed bipolar SRAM's. The techniques use a small CMOS memory cell instead of the bipolar memory cell that has often been used in conventional bipolar SRAM's for cache and control memories of mainframe computers. Therefore, the memory cell size can also be reduced to 26 43% of conventional cells. A 64-kb SRAM with one of the sensing techniques is fabricated using 0.5-µm BiCMOS technology and achieves a 1.5-ns access time with a 78-µm2 memory cell size. The techniques are especially useful in the development of both ultrahigh-speed and high-density SRAM's, which have been used as cache and control memories of mainframe computers.

The subject of the paper is to analyze time complexity of the minimum modification problem in the Horn clause propositional logic. Given a set H of Horn clauses and a query Q in propositional logic, we say that Q is provable over H if and only if Q can be shown to be true by repeating Modus Ponens among clauses of H. Suppose that Q is not provable over H, and we are going to modify H and Q into H and Q , respectively, such that Q is provable over H . The problem of making such modification by minimum variable deletion (MVD), by minimum clause addition (MCA) or by their combination (MVDCA) is considered. Each problem is shown to be NP-complete, and some approximation algorithms with their experimental evaluation are given.

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.

Relaxation-type monolithic silicon bipolar voltage-controlled oscillators (VCO's) with center frequencies ranging from 1.5 to 5 GHz are described. The maximum oscillating frequency achieved is 7.4 GHz. The VCO's dissipate about 70 mW from a 3.6-V supply, including the output buffer and voltage-to-current converter stages. Two types of on-chip timing capacitor structures and various configurations used in achieving these results are described. A wide tuning range has been achieved which is sufficient to cover the normal process tolerances and supply variations expected in a practical environment. The circuits are fabricated in an advanced 0.8-µm double-poly self-aligned bipolar technology.

A new type of optical frequency domain reflectometry is demonstrated. Optical carrier frequency is swept so that a phase of the backscattered light is shifted. Then, an interference output of the backscattered light is Fourier transformed. The farther the scattering point locates, the faster the phase of the backscattered light changes. Hence, the Fourier spectrum of the interference output displays the fault distribution along a wave-guide. In the present scheme, the theoretical resolution is inversely proportional to the frequency sweeping range of the optical source and is given by z=c/2nf, where f is the frequency sweeping range of the optical source. In a preliminary experiment, a Michelson type interferometer in which a target fiber of 20cm length is inserted in a probing arm. The reference arm is adjusted to be longer than the probing arm by about 1.8m. This is because the interference term between the backscattering light and the reference light should be separated from the interference term formed by the backscattering light itself. A LD pumped Nd: YAG ring laser whose frequency sweeping range is 20GHz is used as a variable wavelength source. The calculated resolution is 5mm for n=1.5 in fiber. A resultant spectrum in which the two peaks correspond to the reflections at both the fiber ends is obtained.

Conventionally, ultrahigh-speed 2:1 multiplexers and 1:2 demultiplexers have been demonstrated with HBT's, MESFET's, and Si BJT's. Multiplexers and demultiplexers with a high number of bits are desirable to simplify a system. An 8:1 multiplexer and a 1:8 demultiplexer operating at 6 Gb/s and a 16:1 multiplexer and a 1:16 demultiplexer operating at 10 Gb/s were realized by HBT's and MESFET's, respectively. This paper describes Si bipolar circuits and package design technology for a 5-Gb/s 8:1 multiplexer and a 4.2-Gb/s demultiplexer. These multigigabit LSI's have been mainly achieved by switching current optimization within the limit of keeping a maximum unity unilateral gain frequency (fmax), by careful circuit and layout design considering accurate parasitic capacitance modeling, and by using a high-speed Si bipolar technology. These LSI's are housed in a newly developed 56-pin six-layer ceramic package with chip resistors for ECL termination and chip capacitors for good RF grounding.

An ECL circuit with an active pull-down device, operated from a CMOS supply voltage, is described as a high-speed digital circuit for a 0.25-µm BiCMOS technology. A pair of ECL/CMOS level converters with build-in logic capability is presented for effective intermixing of ECL with CMOS circuits. Using a 2.5-V supply and a reduced-swing BiNMOS buffer, the ECL circuit has reduced power dissipation, while still providing good speed. A design example shows the implementation of complex logic by emitter and collector dottings and the selective use of ECL circuits to achieve high performance.

A 512-kb flash EEPROM developed for microcontroller applications will be reported. Many process and performance constraints associated with the conventional flash EEPROM have been eliminated through the development of a new flash EEPROM cell and new circuit techniques. Design of the 512-kb flash EEPROM, which is programmable for different array sizes, has been evaluated from 256- and 384-kb arrays embedded in new 32-b microcontrollers. The 512-kb flash EEPROM has incorporated the newly developed source-coupled split-gate (SCSG) flash EEPROM cell, Zener-diode controlled programming voltages, internally generated erase voltage, and a new differential sense amplifier. It has eliminated overerase and program disturb problems without relying on tight process controls and on critical operational sequences and timings, such as intelligent erase, intelligent program, and preprogram before erase. A modular approach was used for chip design to minimize development time and for processing technology to achieve high manufacturability and flexibility.

The discrete cosine transform (DCT) has been recognized as one of the standard techniques in image compression. Therefore, a core processor which rapidly computes DCT has become a key component in image compression VLSI's. This paper describes a 100-MHz two-dimensional DCT core processor which is applicable to the real-time processing of HDTV signals. An excellent architecture utilizing a fast DCT algorithm and multiplier accumulators based on distributed arithmetic have contributed to reducing the hardware amount and to enhancing the speed performance. A layout scheme with a column-interleaved memory and a new ROM circuit are introduced for the efficient implementation of memory-based signal processing circuits. Furthermore, mean values of errors generated in the core were minimized to enhance the computational accuracy with the word-length constraints. Consequently, it features the fastest operating speed and the smallest area with its sufficient accuracy satisfying the specifications in CCITT recommendation H.261. The core integrates about 102K transistors, and occupies 21 mm2 using 0.8-µm double-metal CMOS technology.

A family of user-programmable peripherals, utilizing an integration strategy based on a programmable system device (PSD) concept, is described. Specifically, PSD is an efficient and highly configurable integration of high-density memory and LSI level logic blocks. The configurability is derived by providing programmable logic and programmable interconnect. PSDX is the first PSD family of programmable microcontroller peripherals; it integrates 256 kb to 1 Mb of EPROM, 16 kb of SRAM, a 28-input by 42-product term programmable logic device (PLD), and flexible I/O ports. This family is primarily targeted for embedded microcontroller applications. Using one PSD device it is possible to replace all the core peripherals in the system and, as a result, achieve a reduction in components, power dissipation, and overall system cost. The flexible architecture is achieved by providing 46 configuration options, which allows the PSD to interface with virtually any 8- or 16-b microcontroller. The integration is made possible by developing a special configurability and testability scheme. These parts are realized on a 1.2-µm CMOS EPROM process which includes an NVM module that provides the dedicated cells for the EPROM (10.6 µm2), PLD, and the configuration bits. The die size is 46 mm2 (for PSD2, which contains 512-kb EPROM) and is housed in a 44-pin package. Memory access time through the PLD is 120 ns and the PLD pin-to-pin delay is 35 ns at 4.5 V and 75.