The expected lengths of the parsed segments obtained by applying Lempel-Ziv incremental parsing algorithm for i.i.d. source satisfy simple recurrence relations. By extracting a combinatorial essence from the previous proof, we obtain a simpler derivation.
Yao-Lin JIANG Richard M. M. CHEN Zu-Lan HUANG
In this paper we study general complex eigenvalue problems in engineering fields. The eigenvalue problems can be transformed into the associated problems for solving large systems of nonlinear ordinary differential equations (dynamic equations) by optimization techniques. The known waveform relaxation method in circuit simulation can then be successfully applied to compute the resulting dynamic equations. The approach reported here, which is implemented on a message passing multi-processor system, can determine all eigenvalues and their eigenvectors for general complex matrices without any restriction on the matrices. The numerical results are provided to confirm the theoretical analysis.
Jianting CAO Noboru MURATA Shun-ichi AMARI Andrzej CICHOCKI Tsunehiro TAKEDA Hiroshi ENDO Nobuyoshi HARADA
Magnetoencephalography (MEG) is a powerful and non-invasive technique for measuring human brain activity with a high temporal resolution. The motivation for studying MEG data analysis is to extract the essential features from measured data and represent them corresponding to the human brain functions. In this paper, a novel MEG data analysis method based on independent component analysis (ICA) approach with pre-processing and post-processing multistage procedures is proposed. Moreover, several kinds of ICA algorithms are investigated for analyzing MEG single-trial data which is recorded in the experiment of phantom. The analyzed results are presented to illustrate the effectiveness and high performance both in source decomposition by ICA approaches and source localization by equivalent current dipoles fitting method.
Ikuo ARAI Yoshiyuki TOMIZAWA Masanobu HIROSE
The application of subsurface radar using electromagnetic waves in the VHF band is wide and includes surveying voids under the ground and archaeological prospecting. To achieve a wider application range, the survey depth must be deeper. In this paper, a method of pulse compression using a chirp signal as one of the methods to fulfill this requirement is described, and its advantages and problems are discussed. First, a delay correlation method is proposed as a processing method of pulse compression. It converts RF band chirp signal directly into a pulse. Moreover, the method improves the S/N ratio by over 40 dB compared with conventional pulse radar. Therefore, it has the same detection ability as conventional pulse radar even though it uses less transmitting power. Next, the influences of RF amplifier saturation and underground propagation characteristics on the chirp signal are discussed; both are shown to have little influence on the detection ability of the method.
We consider the problem of embedding complete binary trees into 2-dimensional tori with minimum (edge) congestion. It is known that for a positive integer n, a 2n-1-vertex complete binary tree can be embedded in a (2n/2+1)(2n/2+1)-grid and a 2n/2 2n/2-grid with congestion 1 and 2, respectively. However, it is not known if 2n-1-vertex complete binary tree is embeddable in a 2n/2 2n/2-grid with unit congestion. In this paper, we show that a positive answer can be obtained by adding wrap-around edges to grids, i.e., a 2n-1-vertex complete binary tree can be embedded with unit congestion in a 2n/2 2n/2-torus. The embedding proposed here achieves the minimum congestion and an almost minimum size of a torus (up to the constant term of 1). In particular, the embedding is optimal for the problem of embedding a 2n-1-vertex complete binary tree with an even integer n into a square torus with unit congestion.
Toru SATO Takuji NAKAMURA Koji NISHIMURA
Meteor storms and showers are now considered as potential hazard in the space environment. Radar observations of meteors has an advantage of a much higher sensitivity over optical observations. The MU radar of Kyoto University, Japan has a unique capability of very fast beam steerability as well as a high sensitivity to the echoes from ionization around the meteors. We developed a special observation scheme which enables us to determine the orbit of individual meteors. The direction of the target is determined by comparing the echo intensity at three adjacent beams. The Doppler pulse compression technique is applied to improve the signal-to-noise ratio of the echoes from the very fast target, and also to determine the range accurately. The developed scheme was applied to the observation made during the Leonid meteor storm on November 18, 1998 (JST). Estimated orbital distribution seems to suggest that the very weak meteors detected by the MU radar are dominated by sporadic meteors rather than the stream meteors associated with the Leonids storm.
Hiroyuki AOKI Mahmood R. AZIMI-SADJADI Yukio KOSUGI
This paper presents an application of Complex-Valued Associative Memory Model(CAMM) for image processing. An image association system applying CAMM, combined with a 2-dimensional discrete Fourier transform (2-D DFT) process is proposed. Discussed are how a gray level image can be expressed using CAMM, and the image association that can be performed by CAMM. In the proposed system, input images are transformed to phase matrices and the image association can be performed by making use of the phase information. Practical examples are also presented.
The constriction resistance of an electric contact has frequently been obtained using a model of only one circular contact spot of radius a. However, cases of a single contact spot are extremely rare as the interface of the electrical contact actually consists of numerous micro-contact spots. A contact is therefore regarded as the aggregate of several micro-contact spots, which are referred to collectively as a cluster. The constriction resistance of the cluster can be calculated as the sum of the self-resistance and mutual resistance of individual micro-contact spots. In the present study, this model is expanded slightly for practical application by normalizing a previous theoretical formula. In order to obtain the constriction resistance for contacts between composite materials and mating metals, EPMA analysis is applied so as to determine real micro-contact spots. Theoretical calculations of the constriction resistance of multiple contact spots is shown to be reasonably consistent with experimental results. In addition, the contact of a composite material and a mating metal is shown to be made up of multispots. The current was recognized experimentally to flow more easily at micro-contact spots in the cluster periphery. These experimental findings coincide with simulation results obtained by theoretical calculations.
Wen-Jyi HWANG Maw-Rong LEOU Shih-Chiang LIAO Chienmin OU
This paper presents a novel competitive learning algorithm for the design of variable-rate vector quantizers (VQs). The algorithm, termed variable-rate competitive learning (VRCL) algorithm, designs a VQ having minimum average distortion subject to a rate constraint. The VRCL performs the weight vector training in the wavelet domain so that required training time is short. In addition, the algorithm enjoys a better rate-distortion performance than that of other existing VQ design algorithms and competitive learning algorithms. The learning algorithm is also more insensitive to the selection of initial codewords as compared with existing design algorithms. Therefore, the VRCL algorithm can be an effective alternative to the existing variable-rate VQ design algorithms for the applications of signal compression.
Toshifumi MORIYAMA Yoshio YAMAGUCHI Hiroyoshi YAMADA
This paper presents a three-dimensional polarimetric detection result of targets buried in snowpack by synthetic aperture FM-CW radar system. Since the FM-CW radar is suitable for short range sensing and can be equipped with fully polarimetric capability, we further extended it to a polarimetric three-dimensional SAR system. A field experiment was carried out to image and detect targets in a natural snowpack of 280 cm deep. The polarimetric detection and identification schemes are the polarimetric filtering, three-component decomposition, and the power polarization anisotropy coefficient. These approaches to acquired data show the usefulness of three-dimensional polarimetric FM-CW SAR system.
Naofumi HOMMA Takafumi AOKI Tatsuo HIGUCHI
This paper presents an efficient graph-based evolutionary optimization technique called Evolutionary Graph Generation (EGG), and its application to the design of fast constant-coefficient multipliers using parallel counter-tree architecture. An important feature of EGG is its capability to handle the general graph structures directly in evolution process instead of encoding the graph structures into indirect representations, such as bit strings and trees. This paper also addresses the major problem of EGG regarding the significant computation time required for verifying the function of generated circuits. To solve this problem, a new functional verification technique for arithmetic circuits is proposed. It is demonstrated that the EGG system can create efficient multiplier structures which are comparable or superior to the known conventional designs.
Motohiko ISAKA Robert H. MORELOS-ZARAGOZA Marc P. C. FOSSORIER Shu LIN Hideki IMAI
In this paper, we investigate multilevel coding and multistage decoding for satellite broadcasting with moderate decoding complexity. An unconventional signal set partitioning is used to achieve unequal error protection capabilities. Two possibilities are shown and analyzed for practical systems: (i) linear block component codes with near optimum decoding, (ii) punctured convolutional component codes with a common trellis structure.
Motoyasu TAKEHARA Toshihiro KAMIYA Shinji KUSUMOTO Katsuro INOUE
This letter empirically evaluates the way how to calculate the complexity of methods, that is used in the definition of WMC(Weighted Method per Class), one of the Chidamber and Kemerer's metrics. With respect to the results of our experiment, Halstead's Software Science metric is the most appropriate one to evaluate the complexity of the methods.
Shinfeng D. LIN Shih-Chieh SHIE
In this article, an efficient vector quantization (VQ) scheme called side-match finite-state vector quantization with adaptive block classification is presented for image compression. It makes use of edge information contained in image in additional to the average values of blocks forming the image. In order to achieve low bit rate coding while preserving good quality images, neighboring blocks are utilized to predict the class of current block. Image blocks are mainly classified as edge blocks and non-edge blocks in this coding scheme. To improve the coding efficiency, edge blocks and non-edge blocks are further reclassified into different classes, respectively. Moreover, the number of bits for encoding an image is greatly reduced by foretelling the class of input block and applying small state codebook in corresponding class. The improvement of the proposed coding scheme is attractive as compared with other VQ techniques.
Ayako HARADA Shin-ichi HATTORI Tadashi KASEZAWA Hidenori SATO Tetsuya MATSUMURA Satoshi KUMAKI Kazuya ISHIHARA Hiroshi SEGAWA Atsuo HANAMI Yoshinori MATSUURA Ken-ichi ASANO Toyohiko YOSHIDA Masahiko YOSHIMOTO Tokumichi MURAKAMI
An MPEG-2 422P@HL encoder chip set composed of a preprocessing LSI, an encoding LSI, and a motion estimation LSI is described. This chip set realizes a two-type scalability of picture resolution and quality, and executes a hierarchical coding control in the overall encoder system. Due to its scalable architecture, the chip set realizes a 422P@HL video encoder with multi-chip configuration. This single encoding LSI achieves 422P@ML video, audio, and system encoding in real time. It employs an advanced hybrid architecture with a 162 MHz media processor and dedicated video processing hardware. It also has dual communication ports for parallel processing with multi-chip configuration. Transferring of reconstructed data and macroblock characteristic data between neighboring encoder modules is executed via these ports. The preprocessing LSI is fabricated using 0.25 micron three-layer metal CMOS technology and integrates 560 K gates in an area of 12.0 mm 12.0 mm . The encoding LSI is fabricated using 0.25 micron four-layer metal CMOS technology and integrates 11 million transistors in an area of 14.2 mm 14.2 mm . The motion estimation LSI is fabricated using 0.35 micron three-layer metal CMOS technology. It integrates 1.9 million transistors in an area of 8.5 mm 8.5 mm . This chip set makes various system configurations possible and allows for a compact and cost-effective video encoder with high picture quality.
Kamalanath Priyantha HEWAGAMAGE Masahito HIRAKAWA
Patterns exist in many contexts and can be considered the useful information for decision making. However, many patterns are not directly visible without careful presentation. Here, we describe an interactive visualization approach for browsing patterns in a history of interacting with a computer system. While a user is carrying out his/her business using computers, activities with respect to time and location are captured to determine the situational interactions. We first integrate the timeline and geographical map to create a structure to visualize spatiotemporal events in the interaction history. The spiral-based interactive visualization technique, presented in this paper, is then used to derive patterns according to the user-specified different spatial viewpoints on the map. In this study, we demonstrate how patterns can be used as visual statements for the analysis of a spatiotemporal data set in the information visualization.
Ali MANSOUR Allan Kardec BARROS Noboru OHNISHI
The blind separation of sources is a recent and important problem in signal processing. Since 1984, it has been studied by many authors whilst many algorithms have been proposed. In this paper, the description of the problem, its assumptions, its currently applications and some algorithms and ideas are discussed.
Rudolf STRASSER Siegfried SELBERHERR
We present a simulation system which meets the requirements for practical application of inverse modeling in a professional environment. A tool interface for the integration of arbitrary simulation tools at the user level is introduced and a methodology for the formation of simulation networks is described. A Levenberg-Marquardt optimizer automates the inverse modeling procedure. Strategies for the efficient execution of simulation tools are discussed. An example demonstrates the extraction of doping profile information on the basis of electrical measurements.
Matsuto OGAWA Takashi SUGANO Ryuichiro TOMINAGA Tanroku MIYOSHI
Simulation of multi-band quantum transport based on a non-equilibrium Green's functions is presented in resonant tunneling diodes (RTD's), where realistic band structures and space charge effect are taken into account. To include realistic band structure, we have used a multi-band (MB) tight binding method with an sp3s* hybridization. As a result, we have found that the multiband nature significantly changes the results of conventional RTD simulations specifically for the case with indirect-gap barriers.
Learning process is essential for good performance when a neural network is applied to a practical application. The backpropagation algorithm is a well-known learning method widely used in most neural networks. However, since the backpropagation algorithm is time-consuming, much research have been done to speed up the process. The block backpropagation algorithm, which seems to be more efficient than the backpropagation, is recently proposed by Coetzee in [2]. In this paper, we propose an efficient parallel algorithm for the block backpropagation method and its performance model in mesh-connected parallel computer systems. The proposed algorithm adopts master-slave model for weight broadcasting and data parallelism for computation of weights. In order to validate our performance model, a neural network is implemented for printed character recognition application in the TiME which is a prototype parallel machine consisting of 32 transputers connected in mesh topology. It is shown that speedup by our performance model is very close to that by experiments.