A digit-recurrence algorithm for cube rooting is proposed. In cube rooting, the digit-recurrence equation of the residual includes the square of the partial result of the cube root. In the proposed algorithm, the square of the partial result is kept, and the square, as well as the residual, is updated by addition/subtraction, shift, and multiplication by one or two digits. Different specific versions of the algorithm are possible, depending on the radix, the digit set of the cube root, and etc. Any version of the algorithm can be implemented as a sequential (folded) circuit or a combinational (unfolded) circuit, which is suitable for VLSI realization.
Jong Kwon KIM Ho Chul JI Hwan Seok CHUNG Chul Han KIM Seung Kyun SHIN Duck Hwa HYUN Yun Chur CHUNG
We report on the demonstration of a fast restorable all-optical WDM network. This network consisted of four 44 optical cross-connects (OXC's) and four in-line optical amplifiers. These OXC's monitored not only the status of various network elements and quality of optical signals but also the optical path of each channel continuously. Thus, this network could automatically identify the causes of most network failures. For the fast restoration, we implemented these OXC's by using thermo-optic polymer switches (switching time: < 1.5 ms) and used hardware interrupt when LOS was detected. In addition, we used a pre-planned routing table made by using a simple heuristic routing and wavelength assignment algorithm. The results show that this network could be restored from any single link failure within 6 ms even when the restoration path was 400 km.
Takahiro ASAI Tadashi MATSUMOTO
This paper presents the outline of the systolic array recursive least-squares (RLS) processor prototyped primarily with the aim of broadband mobile communication applications. To execute the RLS algorithm effectively, this processor uses an orthogonal triangularization technique known in matrix algebra as QR decomposition for parallel pipelined processing. The processor board comprises 19 application-specific integrated circuit chips, each with approximately one million gates. Thirty-two bit fixed-point signal processing takes place in the processor, with which one cycle of internal cell signal processing requires approximately 500 nsec, and boundary cell signal processing requires approximately 80 nsec. The processor board can estimate up to 10 parameters. It takes approximately 35 µs to estimate 10 parameters using 41 known symbols. To evaluate signal processing performance of the prototyped systolic array processor board, processing time required to estimate a certain number of parameters using the prototyped board was comapred with using a digital signal processing (DSP) board. The DSP board performed a standard form of the RLS algorithm. Additionally, we conducted minimum mean-squared error adaptive array in-lab experiments using a complex baseband fading/array response simulator. In terms of parameter estimation accuracy, the processor is found to produce virtually the same results as a conventional software engine using floating-point operations.
Shougo SHIMIZU Yasunori ISHIHARA Junji YOKOUCHI Minoru ITO
Method invocation mechanism is one of the essential features in object-oriented programming languages. This mechanism contributes to data encapsulation and code reuse, but there is a risk of runtime type errors. In the case of object-oriented databases (OODBs), a runtime error causes rollback. Therefore, it is desirable to ensure that a given OODB schema is consistent, i.e., no runtime error occurs during the execution of queries under any database instance of the OODB schema. This paper discusses the computational complexity of the type-consistency problem. As a model of OODB schemas, we adopt update schemas introduced by Hull et al., which have all of the basic features of OODBs such as class hierarchy, inheritance, complex objects, and so on. The type-consistency problem for update schemas is known to be undecidable. We introduce a subclass of update schemas, called acyclic schemas, and show that the type-consistency problem for acyclic schemas is in coNEXPTIME. Furthermore, we show that the problem for recursion-free acyclic schemas is coNEXPTIME-hard and the problem for retrieval acyclic schemas is PSPACE-complete.
Nozomu TOGAWA Masayuki IENAGA Masao YANAGISAWA Tatsuo OHTSUKI
This paper proposes an area/time optimizing algorithm in a high-level synthesis system for control-based hardwares. Given a call graph whose node corresponds to a control flow of an application program, the algorithm generates a set of state-transition graphs which represents the input call graph under area and timing constraint. In the algorithm, first state-transition graphs which satisfy only timing constraint are generated and second they are transformed so that they can satisfy area constraint. Since the algorithm is directly applied to control-flow graphs, it can deal with control flows such as bit-wise processes and conditional branches. Further, the algorithm synthesizes more than one hardware architecture candidates from a single call graph for an application program. Designers of an application program can select several good hardware architectures among candidates depending on multiple design criteria. Experimental results for several control-based hardwares demonstrate effectiveness and efficiency of the algorithm.
Takashi SUGIHARA Kazuyuki ISHIDA Kenkichi SHIMOMURA Katsuhiro SHIMIZU Yukio KOBAYASHI
Using the chirped grating with temperature control, we demonstrated the adaptive dispersion compensation at 40 Gbit/s RZ transmission. The simple monitoring of the 40 GHz frequency component enables us to automatic control of the adaptive dispersion compensator.
Tatsuya HAGIWARA Hiroki DOI Hideki TODE Hiromasa IKEDA
Recent studies on traffic measurement analysis in the various networks (LAN, MAN, WAN) have shown that packet traffic exhibits Self-Similarity. The packet traffic represents some behavior quite different from what it has been assumed. Some papers reported that Self-Similarity degrades the network performance, such as buffer overflow and network congestion. Thus, we need new network control scheme considering Self-Similar properties. The control scheme requires high-speed calculation method of Hurst Parameter. In this paper, we propose high-speed calculation method of Hurst Parameter based on the Variance-Time Plot method, and show its performance. Furthermore, we try to apply this method to the simple network control, in order to show effectiveness of the network control with Self-Similarity.
Rieko SATO Toshio ITO Katsuaki MAGARI Akira OKADA Manabu OGUMA Yasumasa SUZAKI Yoshihiro KAWAGUCHI Yasuhiro SUZUKI Akira HIMENO Noboru ISHIHARA
We fabricated a 1.55-µm polarization insensitive Michelson interferometric wavelength converter (MI-WC). The MI-WC consists of a two-channel spot-size converter integrated semiconductor optical amplifier (SS-SOA) on a planar lightwave circuit (PLC) platform. Clear eye opening and no power penalty in the back-to-back condition were obtained at 10 Gb/s modulation. We also confirmed the polarization insensitive operation on the input signal. Moreover, for an application of the MI-WC to DWDM networks, we demonstrated the selective wavelength conversion of 2.5 G/s optical packets from Fabry-Perot laser diode (FP-LD) light to four ITU-T grid wavelengths. We confirmed the good feasibility of this technique for use in DWDM networks. The wavelength conversion we describe here is indispensable for future all-optical networks, in which optical signal sources without wavelength control will be used at user-end terminals.
Timothy A. BIRKS Jonathan C. KNIGHT Brian J. MANGAN Philip St. J. RUSSELL
A photonic crystal fibre has an array of microscopic air holes running along its length. The periodicity of the array is broken by a deliberate "defect" that acts as a waveguide core. Light is confined to this core by the holes. Although some designs of photonic crystal fibre guide light by total internal reflection and so can be considered analogues of conventional optical fibres, their properties can be strikingly different. Other designs guide light by photonic bandgap confinement and represent a totally new type of fibre.
Reina YOSHIKAWA Shimin GUO Kazuhiro MOTEGI Yoshihide IGARASHI
We propose the problem of how to transmit an information-theoretically secure bit using random deals of cards among players in hierarchical groups and a computationally unlimited eavesdropper. A player in the highest group wants to send players in lower groups a secret bit which is secure from the eavesdropper and some other players. We formalize this problem and design protocols for constructing secret key exchange spanning trees on hierarchical groups. For each protocol we give sufficient conditions to successfully construct a secret key exchange spanning tree for the hand sizes of the players and the eavesdropper.
Jong Kwon KIM Ho Chul JI Hwan Seok CHUNG Chul Han KIM Seung Kyun SHIN Duck Hwa HYUN Yun Chur CHUNG
We report on the demonstration of a fast restorable all-optical WDM network. This network consisted of four 44 optical cross-connects (OXC's) and four in-line optical amplifiers. These OXC's monitored not only the status of various network elements and quality of optical signals but also the optical path of each channel continuously. Thus, this network could automatically identify the causes of most network failures. For the fast restoration, we implemented these OXC's by using thermo-optic polymer switches (switching time: < 1.5 ms) and used hardware interrupt when LOS was detected. In addition, we used a pre-planned routing table made by using a simple heuristic routing and wavelength assignment algorithm. The results show that this network could be restored from any single link failure within 6 ms even when the restoration path was 400 km.
Lee J. RICHARDSON Wladek FORYSIAK Nick J. DORAN Keith J. BLOW
We demonstrate, through numerical simulations, the possibility of trans-oceanic single channel transmission at 160 Gbit/s with no active control. This was achieved using short period dispersion management, which supports short pulse propagation at practical map strengths. We demonstrate that through careful selection and optimisation of the system parameters the performance of this system can be extended. We also define the tolerable limits of the system to the residual dispersion slope and polarisation mode dispersion.
Akihiko MATSUURA Kazushige YONENAGA Yutaka MIYAMOTO Akihide SANO Hiromu TOBA Mikio YONEYAMA
We investigated the characteristics of optical duobinary signals in achieving high fiber input power transmission focusing on the idea of optimum residual dispersion equalization. We confirm through calculations and experiments that setting the total link dispersion at a non-zero value allows high fiber launched power (+18 dBm) and large dispersion tolerance (350 ps/nm) at 10 Gbit/s. We demonstrate repeaterless 250-km single mode fiber (SMF) transmission with a 10-Gbit/s optical duobinary signal. We also demonstrate high-speed complete optical duobinary coding and transmit synchronous digital hierarchy (SDH) frames over optical duobinary signals for the first time.
In this paper, we consider the net assignment problem in the logic emulation system. This problem is also known as the board-level-routing problem. There are field programmable logic arrays (FPGAs) and crossbars on an emulator board. Each FPGA is connected to each crossbar. Connection requests between FPGAs are called nets, and FPGAs are interconnected through crossbars. We are required to assign each net to the suitable crossbar. This problem is known to be NP-complete in general. A polynomial time algorithm is known for a certain restricted case, in which we treat only 2-terminal nets. In this paper we propose a new polynomial time algorithm for this case.
Ming-Huei CHEN Bih-Hwang LEE Chwan-Chia WU
This paper conducts performance evaluation and performs simulation for a code division multiple access (CDMA) system when channel bands of multiple neighboring CDMA/DSSS are overlapped in time domain. It is assumed that all systems adopt direct-sequence spread-spectrum (DSSS) technique and are BPSK modulated by the different carrier frequencies. Automatic power control (APC) is also applied in the interfered system such that the receiver gets the same power from all users. Without loss generality, an additive white Gaussian noise (AWGN) channel is also assumed during analysis. In this paper, the analytic solution of the signal to noise ratio (SNR) is first derived in which both CDMA systems are modulated by different carrier frequencies. We have the results by simulation with Δ f = 0 and Δ f = 1 MHz, respectively. This analysis is good for general cases; and the results show an excellent computational performance. In particular, the result is very close to Pursley's result, when the systems have the same code length with no carrier difference.
Kengo R. AZEGAMI Atsushi TAKAHASHI Yoji KAJITANI
We improve the algorithm to obtain the min-cut graph of a hyper-graph and show an application to the sub-network extraction problem. The min-cut graph is a directed acyclic graph whose directed cuts correspond one-to-one to the min-cuts of the hyper-graph. While the known approach trades the exactness of the min-cut graph for some speed improvement, our proposed algorithm gives an exact one without substantial computation overhead. By using the exact min-cut graph, an exhaustive algorithm finds an optimal sub-circuit that is extracted by a min-cut from the circuit. By experiments with the industrial data, the proposing method showed a performance enough for practical use.
Yoshiyuki SHINKAWA Masao J. MATSUMOTO
Adaptation of software components to the requirements is one of the key concerns in Component Based Software Development (CBSD). In this paper, we propose a formal approach to compose component based systems which are adaptable to the requirements. We focus on the functional aspects of software components and requirements, which are expressed in S-sorted functions. Those S-sorted functions are transformed into Colored Petri Nets (CPN) models in order to evaluate connectivity between the components, and to evaluate adaptability of composed systems to the requirements. The connectivity is measured based on colors or data types in CPN, while the adaptability is measured based on functional equivalency. We introduce simple glue codes to connect the components each other. The paper focuses on business applications, however the proposed approach can be applied to any other domains as far as the functional adaptability is concerned.
Kensaku FUJII Mitsuji MUNEYASU Takao HINAMOTO Yoshinori TANAKA
The normalized least mean square (NLMS) algorithm has the drawback that the convergence speed of adaptive filter coefficients decreases when the reference signal has high auto-correlation. A technique to improve the convergence speed is to apply the decorrelated reference signal to the calculation of the gradient defined in the NLMS algorithm. So far, only the effect of the improvement is experimentally examined. The convergence property of the adaptive algorithm to which the technique is applied is not analized yet enough. This paper first defines a cost function properly representing the criterion to estimate the coefficients of adaptive filter. The name given in this paper to the adaptive algorithm exploiting the decorrelated reference signal, 'normalized least mean EE' algorithm, exactly expresses the criterion. This adaptive algorithm estimates the coefficients so as to minimize the product of E and E' that are the differences between the responses of the unknown system and the adaptive filter to the original and the decorrelated reference signals, respectively. By using the cost function, this paper second specifies the convergence condition of the normalized least mean EE' algorithm and finally presents computer simulations, which are calculated using real speech signal, to demonstrate the validity of the convergence condition.
Insoo KOO Eunchan KIM Kiseon KIM
In this paper, we propose a Call Admission Control (CAC) scheme for the Direct Sequence-Code Division Multiple Access (DS-CDMA) systems supporting voice and data services and analyze the Erlang capacity under the proposed CAC scheme. Service groups are classified by Quality of Service (QoS) requirements such as the required Bit Error Rate (BER) and information bit rate, and Grade of Service (GoS) requirement such as required call blocking probability. Different traffics require different system resources based on their QoS requirements. In the proposed CAC scheme, some system resources are reserved exclusively for handoff calls to have high priority over new calls. Additionally, the queueing is allowed for both new and handoff data traffics that are not sensitive to delay. As a performance measure of the suggested CAC scheme, Erlang capacity is introduced. For the performance analysis, a four-dimensional Markov chain model is developed. As a numerical example, Erlang capacity of an IS-95B type system is depicted, and optimum values of system parameters such as the number of reservation channels and queue lengths are found. Finally, it is observed that Erlang capacity is improved more than 2 times by properly selecting the system parameters with the proposed CAC scheme. Also, the effect of handoff parameters on the Erlang capacity is observed.
In this letter, the bandwidth adaptation of an adaptive IIR multiline enhancer is explored. In addition to the problem of bias cancellation of the main structure, different aspects of the proposed filter such as noise equivalent bandwidth and optimal bandwidth are considered and compared with the half power bandwidth of the adaptive multiline enhancer. Since the center frequency of the multiple sinusoids of the input signal is estimated with no bias, with the assumption that the center frequency of the incoming signal is accurately adapted, the error surface of the algorithm is calculated analytically as a function of the filter bandwidth. Computer simulations are used to compare optimum and adapted bandwidths.