Mary INABA Naoki KATOH Hiroshi IMAI
In this paper we consider the k-clustering problem for a set S of n points pi=(xi) in the d-dimensional space with variance-based errors as clustering criteria, motivated from the color quantization problem of computing a color lookup table for frame buffer display. As the inter-cluster criterion to minimize, the sum of intra-cluster errors over every cluster is used, and as the intra-cluster criterion of a cluster Sj, |Sj|α-1 Σpi Sj ||xi - - x (Sj)||2 is considered, where |||| is the L2 norm and - x (Sj) is the centroid of points in Sj, i. e. , (1/|Sj|)Σpi Sj xi. The cases of α=1,2 correspond to the sum of squared errors and the all-pairs sum of squared errors, respectively. The k-clustering problem under the criterion with α = 1,2 are treated in a unified manner by characterizing the optimum solution to the k-clustering problem by the ordinary Euclidean Voronoi diagram and the weighted Voronoi diagram with both multiplicative and additive weights. With this framework, the problem is related to the generalized primary shatter function for the Voronoi diagrams. The primary shatter function is shown to be O(nO(kd)), which implies that, for fixed k, this clustering problem can be solved in a polynomial time. For the problem with the most typical intra-cluster criterion of the sum of squared errors, we also present an efficient randomized algorithm which, roughly speaking, finds an ε-approximate 2-clustering in O(n(1/ε)d) time, which is quite practical and may be used to real large-scale problems such as the color quantization problem.
Hideyuki USUI John P. VERBONCOEUR Charles K. BIRDSALL
For plasma simulations, we developed a one-dimensional (1d) Object-Oriented Particle-in-Cell code for X11-based Unix workstations (XOOPIC) by modifying the current two-dimensional version which was originally developed by PTSG (Plasma theory and simulation group) in the University of California at Berkeley. We implemented a simplified field solve and current deposition in the code. We retained three components of particle velocity, although the spatial variation for particle position and field components is limited to one dimension. To verify the function of the 1d code, we perform simulations with typical models such as the Child-Langmuir current model and electromagnetic wave propagation in plasma. In both cases, the simulation results quantitatively agree with the theory.
Cheng-Hao LI Shuenn-Shyang WANG
A new digital watermark approach based on fractal image coding is proposed in this letter. We present a way to use the fractal code as a means of embedding a watermark. The proposed approach has shown to be resistant to the JPEG lossy compression. Moreover, the digital watermark can be simply extracted from the watermarked image without resorting to the original image.
Khaled MAHMUD Kaiji MUKUMOTO Akira FUKUDA
A new type of Meteor Burst Communication (MBC) network is developed. Each unit of the network is based on a DSP board running a modem software. All the fundamental blocks and functions of a modem are implemented in software. Unlike hardware modems, this software modem has flexibility of system configuration and operation. The system implements adaptability in terms of modulation type (number of phases in MPSK) using a unique dynamic channel estimation scheme appropriate for MBC channel. An MBC network protocol is implemented within the modem software. Some preliminary experiments were carried out for differential BPSK and differential QPSK modulations over a practical meteor burst link, and the results are presented.
We report on a novel micromechanical photonic integrated circuits (PIC) for integrating free-space optical systems on a chip. Using polysilicon surface-micromachining technique, micro-optical elements, three-dimensional optomechanical structures, and microactuators are monolithically integrated on silicon substrate. We will discuss the basic building blocks of the micromechanical PIC, including XYZ micropositioners, 2-axis tilting micromirrors, scanning microlenses, and their integration with vertical cavity surface-emitting lasers. We will also discuss their applications in reconfigurable optical interconnect and active alignment in parallel free-space optical interconnect systems.
Sang-Woon KIM Jong-Woo LEE Yoshinao AOKI
The sign-language can be used as a communication means between avatars having no common language. As a trial to overcome the linguistic barrier, we have previously developed a 2D model-based sign-language chatting system between Korean and Japanese on the the Internet. In that system, there have been some problems to be solved for natural animation and real-time transmission. In this paper, we employ a 3D character model for stereoscopic gestures in the sign-language animation. We also utilize CG animation techniques which use the variable number of frames and a cubic spline interpolation in order to generate realistic gestures. For real-time communication, on the other hand, we make use of an intelligent communication method on a client-server architecture. We implement a preliminary communication system with Visual C++ 5.0 and Open Inventor on Windows platforms. Experimental results show a possibility that the system could be used for avatar communications between different languages.
Dae-Ho WOO Tae-Sung YOON Youn-Shik BYUN
The multiple access causes an interference problem in the direct-sequence code-division multiple access systems. An efficient adaptive algorithm should be used to suppress this interference for the improvement of system performance. In this paper, the new blind adaptive method is suggested using the constant modulus algorithm for the purpose of interference suppression. Simulation results show that the converged value of signal to interference ratio for the proposed method is approximately 6 [dB] larger than that of a conventional Blind-MOE receiver in the additive white Gaussian noise channel and channel with inter-symbol interference while the signal to interference ratio improvement is almost 4 [dB] better in the Rayleigh fading channel. The suggested method is also robust to the new user interference resulting the nearly 3 [dB] improvement of the SIR value comparing with the conventional receiver. Based on these results, it is shown that the BER of the proposed receiver is lower than that of any other conventional receiver. Therefore, using the newly suggested method, the considerable performance improvement can be obtained for the DS-CDMA systems.
Tattee KHAYIM Kyoji SHIBUYA Tetsuro KOBAYASHI
We report a new type of electrooptic deflector using lens effect which is able to scan a space in two dimensions. The proposed device was developed from a quasi-velocity-matched electrooptic phase modulator with periodic domain inversion, therefore, it can operate efficiently at a microwave frequency. In the experiments, the demonstration of its operation and applications to ultrafast light control was done at 16.25 GHz.
Hiroshi ISHII Hiroaki NISHIKAWA Yuji INOUE
This paper discusses and clarifies effectiveness of data-driven implementation of protocol handling system to access TINA (Telecommunications Information Networking Architecture) network and internet. TINA is a networking architecture that achieves networking services and management ubiquitously for users and networks. Many TINA related ACTS (Advanced Communication Technologies and Services) projects have been organized in Europe. In Japan, The TINA Trial (TTT) to achieve ATM network management and services based on TINA architectures was done by NTT and several manufactures from April 1997 to April 1999. In these studies and trials, much effort is devoted to development of software based on service architecture and network architecture being standardized in TINA-C (TINA Consortium). In order to achieve TINA environment universally in customers and network sides, we have to consider how to deploy TINA environment onto user side and how to use access transmission capacity as efficiently as possible. Recent technology can easily achieve application and environment downloading from the network side to user side by use of e. g. , JAVA. In accessing the network, there are several possible bottlenecks in information exchange in customer side such as PC processing capability, access protocol handling capability, intra-house wiring bandwidth. Authors, in parallel with TINA software architecture study, have been studying versatile requirements for hardware platform of TINA network. In those studies, we have clarified that the stream-oriented data-driven processor authors have been studying and developing have high reliability, high multiprocessing and multimedia information processing capability. Based on these studies, this paper first shows Von Neumann-based protocol handler is ineffective in case of multiprocessing through mathematical and emulation studies. Then, we show our data-driven protocol handling can effectively realize access protocol handling by emulation study. Then, we describe a result of first step of implementation of data-driven TCP/IP protocol handling. This result proves our TCP/IP hub based on data-driven processor is applicable not only for TINA/CORBA network but normal internet access. Finally, we show a possible customer premises network configuration which resolves bottleneck to access TINA network through ATM access.
In this letter we propose a new mode for block ciphers which uses an unknown random block as feedback. We show that the successful differential/linear cryptanalyses of DES under the mode require at least the complexity of the exhaustive key search. We also present the processing overhead of our scheme compared to that of ECB mode.
This article shows a Boolean Multivalued logical model of varying confirmation by observation of events in human inference and, as an introductory example, applies the model to solve Hempel's paradox of the ravens.
Yoshio KARASAWA Yukihiro KAMIYA Takashi INOUE Satoshi DENNO
A software antenna, which will be a key device realizing flexible and highly reliable wireless communications systems, is inherently matched with software defined radios (SDR). In this paper, first, key technologies on the software antenna are introduced. The technologies contain i) how to recognize the radio environment, ii) how to determine the optimum adaptive signal processing algorithm, and iii) how to reconfigure the digital beamforming circuit. Then, an image of a software antenna with reconfigurable eigenvector-beamspace configuration is presented. Finally, by assuming various propagation conditions, performance of the software antenna in terms of algorithm diversity is demonstrated.
In this paper, a new frequency transformation for complex analog filter design which is suitable for integration is discussed. Arbitrary specified passband and stopband edges are easily transformed into those of the normalized LPF by solving simultaneous equations with four unknowns. Different from previous methods, the proposed transformation provides better performance in active realization of complex filters.
The transmission performance of WDM transmission systems is influenced by many effects according to the type of optical fiber employed in the system. Japanese high-speed transmission systems use dispersion-shifted fiber (DSF). It is well known that the transmission distance of WDM systems employing DSF is restricted by fiber four-wave mixing (FWM). Unequally spaced channel allocation (USCA) was proposed to mitigate the FWM effect. However, if no FWM light is allowed to fall on any optical channel, the number of channels is limited. This paper proposes a new method to extend the number of USCA channels to more than 16 under the optical bandwidth limitation. This method determines channel allocation by considering the distribution of the zero-dispersion wavelength of the optical fiber. The transmission performance of a WDM transmission system employing the proposed USCA methodology is clarified by numerical simulation to confirm that the optical bandwidth requirements can be reduced without degrading transmission performance. As a result, for 16 2.5 Gbit/s, if the fiber input power ranges from -3 dBm/ch to 3 dBm/ch, the achievable transmission distance is 700 km; the fluctuation in zero-dispersion wavelength is assumed to have the standard deviation of 5 nm. For 16 10 Gbit/s, if the fiber input power ranges from 0 dBm/ch to 3 dBm/ch, the achievable transmission distance is 400 km.
Takafumi YAMAJI Akira YASUDA Hiroshi TANIMOTO Yasuo SUZUKI
An architecture for a digital-to-RF converter for a software defined radio (SDR) transmitter is proposed. The ideal hardware architecture for an SDR is a digital-signal to RF-signal direct conversion transmitter. However no conventional digital-to-analog converter (DAC) has converted over 1-GHz RF signal with enough resolution, in the present condition. In this paper, a digital-to-RF direct converter architecture using a ΔΣ modulation technique is proposed for the amplitude-phase modulated signal. The experimental results show that the proposed direct converter outputs a sufficiently accurate signal.
Ching-Te WANG Chin-Chen CHANG Chu-Hsing LIN
In this paper, we propose an idea of the generalization of threshold signature and authenticated encryption for group communications. The concept of the (t, n) threshold signature with (k, l) shared verification is implemented in group-oriented cryptosystems. In the system, any t members can represent a group to sign a message and any k verifiers can represent another group to authenticate the signature. By integrating the cryptographic techniques of data encryption, digital signature and message recovery, a group-oriented authenticated encryption scheme with (k, l) shared verification is also proposed. The message expansion and communication cost can also be reduced in our schemes.
Hiroyuki KAMATA Yohei UMEZAWA Masamichi DOBASHI Tetsuro ENDO Yoshihisa ISHIDA
This paper proposes a private communication system with chaos using fixed-point digital computation. When fixed-point computation is adopted, chaotic properties of the modulated signal should be checked carefully as well as calculation error problems (especially, overflow problems). In this paper, we propose a novel chaos modem system for private communications including a chaotic neuron type nonlinearity, an unstable digital filter and an overflow function. We demonstrate that the modulated signal reveals hyperchaotic property within 10,000 data point fixed-point computation, and evaluate the security of this system in view of the sensitivity of coefficients for demodulation.
This paper presents an efficient method to derive the first passage time of an extended stochastic Petri net by simple algebraic operations. The reachability graph is derived from an extended stochastic Petri net, and then converted to a timed stochastic state machine which is a semi-Markov process. The mean and the variance of the first passage time are derived by algebraic manipulations with the mean and the variance of the transition time, and the transition probability for each transition in the state machine model. For the derivation, three reduction rules are introduced on the transition trajectories in a well-formed regular expression. An efficient algorithm is provided to automate the suggested method.
Yuji WAIZUMI Nei KATO Kazuki SARUTA Yoshiaki NEMOTO
We propose a rough classification system using Hierarchical Learning Vector Quantization (HLVQ) for large scale classification problems which involve many categories. HLVQ of proposed system divides categories hierarchically in the feature space, makes a tree and multiplies the nodes down the hierarchy. The feature space is divided by a few codebook vectors in each layer. The adjacent feature spaces overlap at the borders. HLVQ classification is both speedy and accurate due to the hierarchical architecture and the overlapping technique. In a classification experiment using ETL9B, the largest database of handwritten characters in Japan, (it contains a total of 607,200 samples from 3036 categories) the speed and accuracy of classification by HLVQ was found to be higher than that by Self-Organizing feature Map (SOM) and Learning Vector Quantization methods. We demonstrate that the classification rate of the proposed system which uses multi-codebook vectors for each category under HLVQ can achieve higher speed and accuracy than that of systems which use average vectors.
Min-Sheng LIN Ming-Sang CHANG Deng-Jyi CHEN
A generalized class of consecutive-k-out-of-n:G systems, referred to as Con/k*/n:G systems, is studied. A Con/k*/n:G system has n ordered components and is good if and only if ki good consecutive components that originate at component i are all good, where ki is a function of i. Theorem 1 gives an O(n) time equation to compute the reliability of a linear system and Theorem 2 gives an O(n2) time equation for a circular system. A distributed computing system with a linear (ring) topology is an example of such system. This application is very important, since for other classes of topologies, such as general graphs, planar graphs, series-parallel graphs, tree graphs, and star graphs, this problem has been proven to be NP-hard.