Spiral hashing is a well known dynamic hashing algorithm. Traditional analysis of this search algorithm has been proposed under the assumption that all keys are uniformly accessed. In this paper, we present a discrete analysis of the average search cost in consideration of the frequency of access on each key for this spiral hashing algorithm. In the proposed discrete analysis, the number of probes itself is regarded as a random variable and its probability distribution is derived concretely. The evaluate formulae derived from the proposed analysis can exactly evaluate the average and variance of the search cost in conformity with any probability distribution of the frequency of access.

For efficient use of limited electromagnetic wave resource, the assignment of communication channels to call requests is very important in a cellular network. This task has been formulated as an NP-hard combinatorial optimization problem named the channel assignment problem (CAP). Given a cellular network and a set of call requests, CAP requires to find a channel assignment to the call requests such that three types of interference constraints between channels are not only satisfied, but also the number of channels (channel span) is minimized. This paper presents an iterative search approximation algorithm for CAP, called the Quasi-solution state evolution algorithm for CAP (QCAP). To solve hard CAP instances in reasonable time, QCAP evolutes quasi-solution states where a subset of call requests are assigned channels and no more request can be satisfied without violating the constraint. QCAP is composed of three stages. The first stage computes the lower bound on the channel span for a given instance. After the second stage greedily generates an initial quasi-solution state, the third stage evolutes them for a feasible channel assignment by iteratively generating best neighborhoods, with help of the dynamic state jump and the gradual span expansion for global convergence. The performance of QCAP is evaluated through solving benchmark instances in literature, where QCAP always finds the optimum or near-optimum solution in very short time. Our simulation results confirm the extensive search capability and the efficiency of QCAP.

Precise interconnect analysis is strongly required for giga-scale integration the operation frequency of which is excess 10 GHz. In this study, detailed and accurate analyses of a coaxial interconnect and an actual rectangular interconnect have been performed by the direct evaluation of Maxwell's equations and the finite element method, respectively. It has been revealed that there are two propagation modes for LSI interconnects: skin depth limited propagation mode and interconnect induced slow wave mode. In a miniaturized interconnect, the propagation mode is the interconnect induced slow wave mode; therefore, we cannot obtain the light-speed propagation due to such an interconnect-induced effect. In order to overcome this speed limitation or to improve signal integrity, it is essential to introduce a short interconnect for a miniaturized structure, and a much larger interconnect than the skin depth. We propose a gas-isolated interconnect as a candidate for an ultimately low-k structure in order to increase the signal-propagation speed. By the introduction of such structures, the performance of miniaturized devices in the deep submicron region will be effectively enhanced.

Cutoff frequencies and the modal fields in hollow conducting waveguides of arbitrary cross section are frequently calculated by the method of solving integral equations. This paper presents some improvements for the method by the integral equations. The improved method can calculate the cutoff frequencies and the modal fields only by using the real number, and this method can remove extraneous roots when calculating the cutoff frequencies. The former method calculates the cutoff frequency and the fields only at the cutoff frequency, but the improved method can calculate the fields at arbitrary phase constants.

In this paper, we propose an efficient dual-tree-based multicasting scheme with three destination-switch partition strategies on irregular switch-based networks. The dual-tree-based routing scheme supports adaptive, distributed, and deadlock-free multicast on irregular networks with double channels. We first describe a dual-tree structure constructed from the irregular networks and prove that the multicasting based on such a structure is deadlock-free. Then, an efficient multicast routing algorithm with three destination-switch partition strategies: source-switch-based partition, destination-switch-based partition, and all-switches-based partition, is proposed. Finally, we perform simulations to evaluate our proposed algorithm under various impact parameters: system size, message length, and startup time. The experimental results show that the improved tree-based multicasting scheme outperforms the usual tree-based multicasting scheme. The dual-tree-based multicasting scheme with destination-switch-based partition is shown to be the best for all situations.

With increasing Internet traffic congestion, the provision of reliable transmission and packet loss recovery continues to be of substantial importance. In this paper, we analyze a new recovery method using punctured convolutional codes, demonstrating the simplicity and efficiency of the proposed method for the recovery of lost packets. The analysis provides a method for determining the recoverability and the post-reconstruction receiving rate for a given convolutional code. The exact expressions for calculating the recovery rate are derived for a number of convolutional codes and the (2, 1, m) punctured convolutional code. Where packet loss probabilities are in the range typically found in Internet transmissions, the convolutional code-based method delivers superior performance over the traditional parity method with the same redundancy.

In this letter, we propose a spatially adaptive image restoration algorithm, using local statistics. The local variance, mean and maximum value are utilized to constrain the solution space. These parameters are computed at each iteration step using partially restored image. A parameter defined by the user determines the degree of local smoothness imposed on the solution. The resulting iterative algorithm exhibits increased convergence speed when compared with the non-adaptive algorithm. In addition, a smooth solution with a controlled degree of smoothness is obtained. Experimental results demonstrate the capability of the proposed algorithm.

In this letter, we present an output feedback controller design technique for uncertain discrete time systems with multiple time-delays. Based on Lyapunov second method, a sufficient condition for the robust stability of the system with a dynamic controller is derived in terms of the linear matrix inequality (LMI) with respect to design variables. The solutions of the LMIs can be easily obtained using existing efficient convex optimization techniques.

We developed a method for analysis of boron penetration and gate depletion using N+ and P+ dual-gate PMOSFETs. An N+ gate PMOSFETs, which is immune to boron penetration and gate depletion, exhibited the threshold voltage shifts and fluctuation in P+ gate PMOSFETs fabricated using identical N- substrates. We showed the importance of Vth fluctuation analysis and found that the Vth fluctuation in N+ gate PMOSFETs was negligible, but, the Vth fluctuation in P+ gate PMOSFETs was significant, indicating that the Vth fluctuation in P+ gate PMOSFETs was dominated by boron penetration. It was also shown, for the first time, that boron penetration occurred with gate depletion, and gate depletion must be very strong to suppress boron penetration. The dual-gate PMOSFET method makes it possible to select high-performance G-bit DRAM fabrication processes that are robust against Vth fluctuation.

A VLSI algorithm for division in GF(2m) with the canonical basis representation is proposed. It is based on the extended Binary GCD algorithm for GF(2m), and performs division through iteration of simple operations, such as shifts and bitwise exclusive-OR operations. A divider in GF(2m) based on the algorithm has a linear array structure with a bit-slice feature and carries out division in 2m clock cycles. The amount of hardware of the divider is proportional to m and the depth is a constant independent of m.

This paper describes a new circuit technique for performing clock recovery and data re-timing functions for high-speed source synchronous data communications, such as in burst-mode data transmission. The new clock recovery circuit is fully digital, non-PLL-based, and is capable of retiming the output clock with the received data within one data transition. The absence of analog filters or other analog blocks makes its area much smaller than conventional circuitry. It can also be described by any hardware description language, simulated, and synthesized into any digital process. This enables it to be ported from one technology to another and support system on a chip (SOC) designs. The design concept is demonstrated with T-Spice(R) simulations using a 0.25 µm digital CMOS technology. Static performance was evaluated in terms of supply and temperature dependent skews. The shifts in output clock due to these static conditions were within 40 pS. Also dynamic behaviours such as jitter generation and jitter transfer were evaluated. The circuit generates a jitter of 68 pS in response to a supply noise of 250 mV amplitude and 100 MHz frequency. Input data jitter transfer is within 0.1 dB up to a jitter frequency of 150 MHz.

In this paper, a time-to-digital converter in which the digital output is obtained without delay time is proposed. The circuit consists of a time-to-voltage converter, voltage-to-frequency converter, and counter. In the time-to-voltage converter, a capacitor is charged with a constant current during the input time interval. The change in the capacitor voltage is proportional to the input time and the capacitor voltage can be converted into a pulse signal with the voltage-to-frequency converter. The frequency of the pulse signal is directly proportional to the peak capacitor voltage and the pulse signals are counted to obtain the digital output. In the proposed circuit, the input time interval can be easily controlled and the resolution of the digital output can be improved by controlling the passive devices such as the capacitor and resistor.

We propose two novel blind LMS algorithms, called exponential step size LMS algorithms (ES-LMS), for adaptive array antennas with fast convergence speeds. Both of the proposed algorithms are much better at tracking signal sources than the conventional LMS algorithms. In addition, they require neither spatial knowledge nor reference signals since they use the finite symbol property of digital signal. Computer simulations verify performances of the two proposed algorithms.

Verb phrases are sometimes omitted in natural language (ellipsis). It is necessary to resolve the verb phrase ellipses in language understanding, machine translation, and dialogue processing. This paper describes a practical way to resolve verb phrase ellipses by using surface expressions and examples. To make heuristic rules for ellipsis resolution we classified verb phrase ellipses by checking whether the referent of a verb phrase ellipsis appears in the surrounding sentences or not. We experimented with the resolution of verb phrase elipses on a novel and obtained a recall rate of 73% and a precision rate of 66% on test sentences. In the case when the referent of a verb phrase ellipsis appeared in the surrounding sentences, the accuracy rate was high. But, in the case when the referent of a verb phrase ellipsis did not appear in the surrounding sentences, the accuracy rate was not so high. Since the analysis of this phenomena is very difficult, it is valuable to propose a way of solving the problem to a certain extent. When the size of corpus becomes larger and the machine performance becomes greater, the method of using corpus will become effective.

A new method of error concealment for MPEG videos, in which motion vectors are hidden in an MPEG bitstream as a watermark, is proposed in this paper. Several conventional methods conceal error regions by using motion vectors, which are re-estimated in a decoding process. These methods, however, have two problems: (1) The accuracy of a re-estimated motion vector is lower than that of an estimated motion vector in an encoding process. (2) A large amount of calculation is required to re-estimate motion vectors. The proposed method overcomes these problems by using hidden accurate motion vectors. That is, it hides several bits in each 88 DCT block of all frames and, simultaneously, inhibits the image degradation caused by hiding motion vectors. In addition, it has upward compatibility with a standard MPEG decoder and can be combined with conventional methods. Simulation results show that the accuracy of error concealment by the new method is higher than that of the conventional methods.

The effectiveness and possible applications of all-optical wavelength conversion using optical fibers are described. Several types of ultra-broad and ultra-fast wavelength conversion using highly-nonlinear fiber are shown. Over 70 nm conversion band by four-wave mixing, 500-fs pulse trains conversion by cross-phase-modulation-based nonlinear optical loop mirror and time-based optical add-drop multiplexing for 160 Gbit/s signal using wavelength conversion by supercontinuum are successfully demonstrated.

This paper discusses solutions that provide forward link power allocation based on 3GPP (FDD) standardization reports and that meet the Eb/No required for forward link channels. In addition, we determine the forward link user capacity under a mixed service environment. Cell coverage is derived using the solutions from the forward link user capacity problem and an urban propagation model. These results are achieved with the introduction of various factors, such as the number of users, service types, macro/microcell environments, and others. Our study shows that for IMT-2000 systems offering a mixed service environment, forward link power should be carefully allocated depending on the ratio of users occupied by each service type if one is to achieve optimal cell planning.

In this paper, we describe design considerations for inverse dispersion fiber (IDF) whose chromatic dispersion is designed to compensate for that of conventional 1.3 µm zero-dispersion single-mode fiber (SMF). We clarify the appropriate structural parameters for W-type, triple-clad-type and ring-type refractive index profiles to realize a hybrid transmission line composed of SMF and IDF taking into consideration the bending sensitivity and the available wavelength bandwidth that achieves an average chromatic dispersion of below 1 ps/nm/km in the 1.55 µm region. We also show that, when the launched power is less than 0 dBm/ch, a hybrid transmission line composed of SMF and IDF provides better 40 Gbps 8 ch dense wavelength division multiplexing (DWDM) transmission performance than a conventional dispersion compensation scheme with a dispersion compensating fiber (DCF) module.

The Bach compiler is a behavioral synthesis tool, which synthesizes RT-level circuits from behavioral descriptions written in the Bach C language. It shortens the design period of LSI and helps designers concentrate on algorithm design and refinement. In this paper, we propose methods for optimizing the area and performance of algorithms described in Bach C. In our experiments, we optimized a Viterbi decoder algorithm using our proposed methods and synthesized the circuit using the Bach compiler. The conclusion is that the circuit produced using Bach is both smaller and faster than the hand-coded register transfer level (RTL) design. This proves that the Bach compiler produces high-quality results and the Bach C language is effective for describing the behavior of hardware at a high-level.

Optical disk systems have been used in a wide range of applications and the performance of these systems has been improving rapidly. The optical integration is one of the important technologies of the progress of the optical pickup head in the system. It can make the optical pickup head miniature, light sized, ease to assemble, cost reduced and reliable during long time operation. In this paper, at first, merits and features of the optical integration for optical disk systems are briefly reviewed. Then, our activities on the development of the various hybrid-integrated optical devices, "Laser Couplers" are reported. Especially, the most recent results on the "Two-wavelength-beam Laser Coupler," are described in detail. It has two-wavelength laser emission/detection functions and easily realizes an ultimate solution of the optical pickup head for the DVD/CD system, now being used in "PlayStaion2. " To simplify the structure and the fabrication of this device, a new monolithic-integrated two-wavelength laser diode, called a visible and infrared laser diode, has been developed, which can be easily fabricated using only two steps of metal organic chemical vapor deposition. The structures and characteristics of this device are reported. Lastly, other recent technologies of the optical integration, including monolithically integration, near field optics and so on, are reviewed.