In this paper color image compression using a fuzzy Hopfield-model net based on rough-set reasoning is created to generate optimal codebook based on Vector Quantization (VQ) in Discrete Wavelet Transform (DWT). The main purpose is to embed rough-set learning scheme into the fuzzy Hopfield network to construct a compression system named Rough Fuzzy Hopfield Net (RFHN). First a color image is decomposed into 3-D pyramid structure with various frequency bands. Then the RFHN is used to create different codebooks for various bands. The energy function of RFHN is defined as the upper- and lower-bound fuzzy membership grades between training samples and codevectors. Finally, near global-minimum codebooks in frequency domain can be obtained when the energy function converges to a stable state. Therefore, only 32/N pixels are selected as the training samples if a 3N-dimensional color image was used. In the simulation results, the proposed network not only reduces the consuming time but also preserves the compression performance.
Tatsunori MORI Tomohiro OHTA Katsuyuki FUJIHATA Ryutaro KUMON
In this paper, we propose a method to introduce an A* search control into sentential matching mechanism for question-answering systems, in order to reduce the response time while the accuracy of the answer is preserved. The question answering is a new technology to retrieve not relevant documents but the answer(s) directly by combining several methodology including IR and IE. One of the essential processes is the sentential matching between the user's query and each sentence in documents. In general, in order to obtain matching score precisely in higher resolution, we need some processes with higher computational costs. We therefore introduce an A* search in which both the processing cost and the resolution of matching score are took into account simultaneously. According to the experiments in NTCIR3 QAC1 Task1, the system with the controlled search is 3.4-8.5 times faster than the system with no control.
Homayoon ORAIZI Gholam-Reza GABARANZAD GHADIM
In this paper the method of least squares is employed to design an axially symmetric contradirectional multisection coupled - line coupler together with the impedance matching of real generator and load impedances. An error function is constructed for the required coupling (C) based on the squared magnitude of the ratio of the coupler voltage to that at the incident port. Another algorithm based on the reflected and transmitted wave amplitudes is developed by the method of least squares for the design of a coupled - line coupler with impedance matching of different input and output complex impedances and arbitrary coupling and length. The error functions are minimized to determine the coupler geometry, namely the normalized strip conductor widths (u=w/h) and separation (g=s/h) and the coupler length, where h is the substrate thickness. A procedure is presented to provide the initial values of u and g. The computer implementation of the proposed method shows that a proper coupler design is possible for any given coupler length. This is particularly interesting where space limitations impose contraints on the coupler length. The results are favorably compared with available computer simulation softwares.
The bit error rate (BER) for an uplink multicell multicarrier code-division multiple-access (MC-CDMA) system in Nakagami-m fading channels is derived and expressed in the form of a single integral. The result is obtained without the approximation for the ratio of the interference power from other-cell to the power from the user-of-interest. Numerical results demonstrate the impacts of other-cell interference and power control errors on the BER.
Takayuki KUSUMI Kiyoshi YAMAKAWA Naoki HONDA Kazuhiro OUCHI
To develop ultra high density magnetic recording systems, a quasi-static system with a reciprocating medium motion against a stand still head was developed for a read/write tester. Double-layered perpendicular recording media and merged GMR heads assembled on a conventional head-gimbal assembly (HGA) were applied to evaluate the read/write performances. A smooth sliding contact motion was achieved, however, the head-to-medium spacing was varied depending on the head motion direction. The spacing in the reverse running direction of the conventional head slider seems to be smaller than that of the flying height in a high-speed spin stand. A merged ring head was suitable for perpendicular magnetic recording in the case of the reverse direction sliding.
The concept of an Ω-matrix was introduced by Nishi in order to estimate the number of solutions of a resistive circuit containing active elements. He gave a finite characterization by means of four conditions which are all satisfied if and only if the matrix under investigation is an Ω-matrix. In this note we show that none of the four conditions can be omitted.
Teiji FURUGORI Rihua LIN Takeshi ITO Dongli HAN
Described here is an automatic text summarization system for Japanese newspaper articles on sassho-jiken (murders and bodily harms). We extract the pieces of information from a text, inter-connect them to represent the scenes and participants involved in the sassho-jiken, and finally produce a summary by generating sentences from the information extracted. An experiment and its evaluation show that, while a limitation being imposed on the domain, our method works well in depicting important information from the newspaper articles and the summaries produced are better in adequacy and readability than those obtained by extracting sentences.
Finding DC operating points of nonlinear circuits is an important and difficult task. The Newton-Raphson method adopted in the SPICE-like simulators often fails to converge to a solution. To overcome this convergence problem, homotopy methods have been studied from various viewpoints. For the global convergence of homotopy methods, it is a necessary condition that a given initial solution is the unique solution to the homotopy equation. According to the conventional criterion, such an initial solution, however, is restricted in some very narrow region. In this paper, considering the circuit interpretation of homotopy equations, we prove theorems on the uniqueness of an initial solution for globally convergent homotopy methods. These theorems give new criteria extending the region wherein any desired initial solution satisfies the uniqueness condition.
Shinya FUKUMOTO Noritaka SHIGEI Michiharu MAEDA Hiromi MIYAJIMA
Neural networks for Vector Quantization (VQ) such as K-means, Neural-Gas (NG) network and Kohonen's Self-Organizing Map (SOM) have been proposed. K-means, which is a "hard-max" approach, converges very fast. The method, however, devotes itself to local search, and it easily falls into local minima. On the other hand, the NG and SOM methods, which are "soft-max" approaches, are good at the global search ability. Though NG and SOM exhibit better performance in coming close to the optimum than that of K-means, the methods converge slower than K-means. In order to the disadvantages that exist when K-means, NG and SOM are used individually, this paper proposes hybrid methods such as NG-K, SOM-K and SOM-NG. NG-K performs NG adaptation during short period of time early in the learning process, and then the method performs K-means adaptation in the rest of the process. SOM-K and SOM-NG are similar as NG-K. From numerical simulations including an image compression problem, NG-K and SOM-K exhibit better performance than other methods.
In this paper, a novel algorithm is presented for blind estimation of the symbol timing and frequency offset for OFDM systems. Time-varying frequency-selective Rayleigh fading multipath channel is considered, which is characterized by the power delay profile and time-varying scattering function and has high reliability for real-world mobile environment. The estimators exploit the intrinsic structures of OFDM signals and rely on the second-order moment rather than the probability distribution function of the received signals. They are totally optimum in sense of minimum mean-square-error and can be implemented easily. In addition, we have presented an improved approach which not only preserves the merits of previously proposed method, but also makes the estimation range of the frequency offset cover the entire subcarrier spacing of OFDM signals and the timing estimator be independent of the frequency offset.
Setsuo YAMAMOTO Hirofumi KUNIKI Hiroki KURISU Mitsuru MATSUURA
Co-containing ferrite thin-film/Mn-Zn ferrite thin-film double-layered perpendicular media were prepared using reactive ECR sputtering and magnetron sputtering methods, and their magnetic and structural properties and recording characteristics were studied. The Mn-Zn ferrite thin-film backlayer had saturation magnetization of 3.5 kG and coercivity of 60 Oe. Reproduced voltage for the Co-containing ferrite thin-film/Mn-Zn ferrite thin-film double-layered medium was about twice of that for the Co-containing ferrite single-layer medium.
Kazuhiko USHIO Hideaki FUJIMOTO
We show that the necessary and sufficient condition for the existence of a balanced bowtie decomposition of the complete multigraph λKn is n 5 and λ(n-1) 0 (mod 12). Decomposition algorithms are also given.
In most cases of distributed memory computations, node programs are executed on processors according to the owner computes rule. However, owner computes rule is not best suited for irregular application codes. In irregular application codes, use of indirection in accessing left hand side array makes it difficult to partition the loop iterations, and because of use of indirection in accessing right hand side elements, we may reduce total communication by using heuristics other than owner computes rule. In this paper, we propose a communication cost reduction computes rule for irregular loop partitioning, called least communication computes rule. We partition a loop iteration to a processor on which the minimal communication cost is ensured when executing that iteration. Then, after all iterations are partitioned into various processors, we give global vs. local data transformation rule, indirection arrays remapping and communication optimization methods. The experimental results show that, in most cases, our approaches achieved better performance than other loop partitioning rules.
Manabu OHTA Atsuhiro TAKASU Jun ADACHI
Optical Character Reader (OCR) incorrect recognition is a serious problem when searching for OCR-scanned documents in databases such as digital libraries. In order to reduce costs, this paper proposes fuzzy retrieval methods for English text containing errors in the recognized text without correcting the errors manually. The proposed methods generate multiple search terms for each input query term based on probabilistic automata which reflect both error-occurrence probabilities and character-connection probabilities. Experimental results of test-set retrieval indicate that one of the proposed methods improves the recall rate from 95.96% to 98.15% at the cost of a decrease in precision from 100.00% to 96.01% with 20 expanded search terms.
M.M. Hafizur RAHMAN Susumu HORIGUCHI
Interconnection networks usually suffer from Little's Law: low cost implies low performance and high performance is obtained high cost. However, hierarchical interconnection networks provide high performance at low cost by exploring the locality that exists in communication patterns of massively parallel computers. In this paper, we propose a new hierarchical interconnection network, called Hierarchical Torus Network (HTN). This network reduces the number of vertical links in 3D stacked implementation while maintaining good network features. This paper addresses the architectural details of the HTN, and explores aspects such as the network diameter, average distance, bisection width, peak number of vertical links, and VLSI layout area of the HTN as well as for several commonly used networks for parallel computers. It is shown that the HTN possesses several attractive features including small diameter, small average distance, small number of wires, a particularly small number of vertical links, and economic layout area.
Goo-Hyun PARK Daesik HONG Chang-Eon KANG
In this letter, a novel maximum Doppler spread estimation algorithm for mobile communication systems is proposed. The proposed method uses an average power spectrum of the received signal. The fast Fourier transform (FFT) of received pilot signal, which is related with the maximum Doppler frequency is used for obtaining an instantaneous power spectrum. The proposed algorithm shows a good performance over wide Doppler frequency in low signal-to-noise ratio (SNR<10 dB). Especially, in the proposed method, any other channel information such as SNR is not required.
Jiman HONG Sangsu KIM Yookun CHO
Forked checkpointing scheme is proposed to achieve low checkpoint overhead. When a process wants to take a checkpoint in the forked checkpointing scheme, it creates a child process and continues its normal computation. Two recovery models can be used for forked checkpointing when the parent process fails before the child process establishes the checkpoint. One is the pessimistic recovery model where the recovery process rolls back to the previous checkpoint state. The other is the optimistic recovery model where a recovery process waits for the checkpoint to be established by the child process. In this paper, we present the recovery models for forked checkpointing by deriving the expected execution time of a process with and without checkpointing and also show that the expected recovery time of the optimistic recovery model is smaller than that of the pessimistic recovery model.
In this paper, we give an algorithm for the node-to-set disjoint paths problem in pancake graphs with its evaluation results. The algorithm is of polynomial order of n for an n-pancake graph. It is based on recursion and divided into two cases according to the distribution of destination nodes in classes into which all the nodes in a pancake graph are categorized. The sum of lengths of paths obtained and the time complexity of the algorithm are estimated and the average performance is evaluated based on computer simulation.
Distributed configuration management involves maintaining a set of distributed storage and processing resources in such a way that they serve a community of users fairly, promptly, reliably and securely. Security has recently received much attention due to the general anxiety of hacking. Parallel computing systems such as clusters of workstations are no exception to this threat. This paper discusses experiments that measure the effect of employing randomisation in the scheduling of interdependent user and management tasks onto a distributed system such as clusters of workstations. Two attributes are investigated, namely performance and security. Performance is usually the prime objective in task scheduling. In this work the scheduling problem is viewed as a multi-objective optimisation problem where there is a subtle balance between efficient schedules and security. A schedule is secure if it is not vulnerable to malicious acts or inadvertent human errors. Further, the scheduling model should be hidden from unauthorised observers. The results of the study support the use of randomisation in the scheduling of tasks over an insecure network of processing nodes inhabited by malicious users.
Biplab KUMER SARKER Anil KUMAR TRIPATHI Deo PRAKASH VIDYARTHI Kuniaki UEHARA
A Distributed Computing System (DCS) contributes in proper partitioning of the tasks into modules and allocating them to various nodes so as to enable parallel execution of their modules by individual different processing nodes of the system. The scheduling of various modules on particular processing nodes may be preceded by appropriate allocation of modules of the different tasks to various processing nodes and then only the appropriate execution characteristic can be obtained. A number of algorithms have been proposed for allocation of tasks in a DCS. Most of the solutions proposed had simplifying assumptions. The very first assumption has been: consideration of a single task with their corresponding modules only; second, no consideration of the status of processing nodes in terms of the previously allocated modules of various tasks and third, the capacity and capability of the processing nodes. This work proposes algorithms for a realistic situation wherein multiple tasks with their modules compete for execution on a DCS dynamically considering their architectural capability. In this work, we propose two algorithms based on the two well-known A* and GA for the task allocation models. The paper explains the algorithms elaborately by illustrated examples and presents a comparative performance study among our algorithms and the algorithms for task allocation proposed in the various literatures. The results demonstrate that our GA based task allocation algorithm achieves better performance compared with the other algorithms.