This paper proposes an enhanced method for multiple description coding (MDC) using whitening transform. The MDC using correlating transform is an error resilient coding technique that explicitly adds correlation between two descriptions to enable the estimation of one set from the other when one set is dropped in channel. This paper proposes a method to overcome practical problems that decoder must know statistics of original image in the conventional correlating transform method. The MDC using whitening transform does not need additional statistical information to reconstruct a image because the coefficients whitening transformed have uni-variance statistics. Our experimental results show that the proposed method achieves a good trade-off between the coding efficiency and the reconstruction quality. We obtain that PSNR of image reconstructed from two descriptions is about 0.93 dB higher at the 1.0BPP and PSNR from only one description is about 1.88 dB higher than conventional method at the same rate of 'Lena' image.
In recent years, sliding electric contacts came to be often used under very severe conditions such as high temperature, extremely low temperature, high vacuum, etc. Conventionally, solid lubricants having excellent properties in lubricating performance are generally used compositely with a metal of high electric conductivity, because of their high electrical resistivity. In the present study, we proved that more excellent sliding electrical contacts can be produced with a design made by controlling the distribution on contact surface of a solid lubricant having excellent lubricating performance and of a metal with high electric conductivity through expansion of Greenwood's theory.
This paper deals with a design problem of a robust controller which achieves not only robust stability but also a performance robustness for linear systems with structured uncertainties satisfying matching condition. The performance robustness means that comparing the transient behavior of the uncertain system with a desired one generated by the nominal system, the deterioration of control performance is suppressed. In this approach, the control law consists of a state feedback with the fixed gain designed by using the nominal system, a state feedback with an adaptive gain determined by a parameter adjustment law and a compensation input for the purpose of keeping transient behavior as closely as possible to the desirable one. We show the parameter adjustment law in order to guarantee robust stability and that the condition for the existence of the compensation input is equivalent to the Riccati equation for the standard linear quadratic control problem. Finally, numerical examples are presented.
Chiao-Chan HUANG Zhi-Feng HUANG Ann-Chen CHANG
A minor component analysis approach based on the generalized sidelobe canceler is presented to realize the blind suppression of multiple-access interference in multicarrier code division multiple access systems. With a rough user-code and timing estimations, this proposed method of less computation performs the same as minimum mean square error detectors and outperforms existing blind detectors. Simulation results illustrate the effectiveness of the blind multiuser detection.
Masahiro OKUDA Kyoko NAGATOMO Masaaki IKEHARA Shin-ichi TAKAHASHI
Due to the rapid development of computer and information technology, 3D modeling and rendering capabilities are becoming increasingly important in many applications, including industrial design, architecture, CAD/CAM, video games, and medical imaging. Since 3D mesh models often have huge amounts of the data, it is time-consuming to retrieve from a storage device or to download from the network. Most 3D viewing applications need to obtain the entire file of a 3D model in order to display the model, even when the user is interested only in a low-resolution version of the model. Therefore, progressive coding that enables multiresolution transmission of 3D models is desired. In this paper, we propose the progressive coding scheme of 3D meshes with texture, in which we convert irregular meshes to semi-regular using texture coordinates, map them on planes, and apply 2D image coding algorithm to mesh compression. As our method uses the wavelet transform, the encoded bitstream has a progressive nature. We gain high compression rate with the same visual quality as original models.
Osamu WATANABE Mitsuyuki ASHIDA Tetsuro ITAKURA Shoji OTAKA
A linear-in-dB VGA of the current-divider type is fabricated in 0.25 µm CMOS technology. Two gain compensation techniques are proposed in order to compensate the gain deviations due to a MOSFET which has a square-law characteristic or an exponential-law characteristic determined by its current density. Temperature compensation techniques are also proposed. Measure results obtained at 380 MHz are a gain range of 80 dB, a gain error of 3 dB, and an NF of 11 dB.
Kunihiko SADAKANE Norito SUGAWARA Takeshi TOKUYAMA
We discuss applications of quantum computation to geometric data processing. Especially, we give efficient algorithms for intersection problems and proximity problems. Our algorithms are based on Brassard et al. 's amplitude amplification method, and analogous to Buhrman et al. 's algorithm for element distinctness. Revealing these applications is useful for classifying geometric problems, and also emphasizing potential usefulness of quantum computation in geometric data processing. Thus, the results will promote research and development of quantum computers and algorithms.
Jacir L. BORDIM Yasuaki ITO Koji NAKANO
The main contribution of this paper is to present an FPGA-based implementation of an instance-specific hardware which accelerates the CKY (Cocke-Kasami-Younger) parsing for context-free grammars. Given a context-free grammar G and a string x, the CKY parsing determines whether G derives x. We have developed a hardware generator that creates a Verilog HDL source to perform the CKY parsing for any given context-free grammar G. The generated source is embedded in an FPGA using the design software provided by the FPGA vendor. We evaluated the instance-specific hardware, generated by our hardware generator, using a timing analyzer and tested it using the Altera FPGAs. The generated hardware attains a speed-up factor of approximately 750 over the software CKY parsing algorithm.
The main contribution of this paper is to present an image retrieval system using FPGAs. Given a template image T and a database of a number of images I1, I2,, our system lists all images that contain a subimage similar to T. More specifically, a hardware generator in our system creates the Verilog HDL source of a hardware that determines whether Ii has a similar subimage to T for any image Ii and a particular template T. The created Verilog HDL source is compiled and embedded in an FPGA using the design tool provided by the FPGA vendor. Since the hardware embedded in the FPGA is designed for a particular template T, it is an instance-specific hardware that allows us to achieve extreme acceleration. We evaluate the performance of our image matching hardware using a PCI-connected Xilinx FPGA and a timing analyzer. Since the generated hardware attains up to 3000 speed-up factor over the software solution, our approach is promising.
Shuichi ICHIKAWA Shoji YAMAMOTO
Although the subgraph isomorphism problem has various important applications, it is generally NP-complete and difficult to solve. Though a custom computing circuit can reduce the execution time substantially, it requires considerable hardware resources and is inapplicable to large problems. This paper examines the feasibility of data dependent designs, which are particularly suitable to a Field Programmable Gate Array (FPGA). The data dependent approach drastically reduces hardware requirements. For graphs of 32 vertices, the average logic scale of data dependent circuits is only 5% of the corresponding data independent circuit. The data dependent circuit is estimated to be maximally 460 times faster than the software. Even if the circuit generation time is included, a data dependent circuit is estimated to be 2.04 times faster than software for graphs of 32 vertices. The performance gain would increase for larger graphs.
Takanori HAYASHIDA Kazuaki MURAKAMI
Online profiling methodologies are studied for exploiting dynamic optimization. On a dynamic optimizable system with online profilers, it has to get accurate profile in early step of the program execution for effective execution. However, for getting more effective profile by online profiling, it has to satisfy "Rapidness" and "Accuracy". They are conflicted requirements. Therefore, it has to choose trade-off point at implementation. We focused into online Hot Instruction Sequence (HIS) profiler to exploit reconfigurable functional units. To circumstantiate the effectiveness of online HIS profiling, we build some evaluation models for experimental evaluation. Our profiler models are SC/DM, SC/FA and JC/DM. These models have different policy of event counting and table lookup. Our event counting policies are simple-counting or jumble-counting. On the other hand, table lookup policies are direct-map or full-associative. In our experimental evaluation, SC/FA and JC/DM models scored higher accuracy than SC/DM. The JC/DM model is able to implement by lower cost for table lookup, but it scored high accuracy comparable to SC/FA.
Md. RUKONUZZAMAN Mutsuo NAKAOKA
A novel signal processing technique using adaptive neural network algorithm is applied for the on-line detection of harmonic current components generated by nonlinear current loads in the single-phase diode bridge rectifier and it can efficiently determine the harmonic current components in real time. The validity of this active filtering processing system to compensate current harmonics is proved on the basis of simulation results.
Jun MURAMATSU Hiroki KOGA Takafumi MUKOUCHI
The achievable rate region related to the problem of generating mutually independent random sequences is determined. Furthermore, it is proved that the output distribution of lossless source encoders with correlated side information is asymptotically independent of the side information. Based on this, we can realize a random number generator that produces mutually asymptotically independent random sequences from random sequences emitted from correlated sources.
Shintaro ITAGAKI Masahiro MAMBO Hiroki SHIZUYA
The strong RSA assumption is an assumption that the following problem is hard to solve: Given an RSA modulus and a ciphertext, find a pair of plaintext and exponent corresponding to them. It differs from the standard RSA assumption in a sense that in the strong version, no exponent is given as an input. The strong RSA assumption is considered to be stronger than the RSA assumption, but their exact relationship is not known. We investigate the strength of the strong RSA assumption and show that the strong RSA assumption restricted to low exponents is equivalent to the assumption that RSA problem is intractable for any low exponent. We also show that in terms of algebraic computation, the strong RSA assumption is properly stronger than the RSA assumption if there exists an RSA modulus n such that gcd((n),3)=1 and RSA problem is intractable.
Lin and Jan recently proposed a new automatic signature scheme using a compiler in distributed systems. The proposed scheme adopts a digital signature scheme to detect the change of computer programs, thus it allows computer programs prevent from the infection of computer viruses. However, this article will present a forgery signature attack on their scheme. Moreover, the author also points out one restriction in their scheme. It is impractical for most application programs.
Katsumi TAKAHASHI Hiroai ASAMI Katsuto NAKAJIMA Masahiro IIDA
We designed an FPGA-based parallel machine called "RASH"(Reconfigurable Architecture based on Scalable Hardware) for high speed and flexible signal/data processing. Cryptanalysis is one of the killer applications for FPGA-based machines because huge amounts of logical and/or simple arithmetic operations are required and FPGA is suitable for this. One of the well-known activities in cryptanalysis is the DES (Data Encryption Standard) cracking contest conducted by RSA Data Security. TMTO (Time-Memory Trade-Off) Cryptanalysis is a practical method to dramatically shorten the time for key search when plaintext is given in advance. A string of ASCII characters is used as the key much like a password. The ASCII character is 7-bit character and is changed to 96 kinds of value. The 56-bit DES key is given with a string of 8 ASCII characters. Although the DES key has 64 trillion(=256) possibilities, the key that is given with a string has only 6.4 trillion(=968) possibilities. Therefore, we improve TMTO cryptanalysis so that we search only the limited key by ASCII characters and reduce the quantity of computation. In this paper, we demonstrate how TMTO cryptanalysis for limited key is well suited to our FPGA-based RASH machine. By limiting the key to a string, DES key will be found at 80% probability within 45 minutes after ciphertext is given on 10 units of RASH. The precomputation before starting key search takes 3 weeks on the same RASH configuration.
Takuya OKAMOTO Takafumi YUASA Tomonori IZUMI Takao ONOYE Yukihiro NAKAMURA
A configurable device "PCA-Chip2" implements the concept of Plastic Cell Architecture, which is an extension of programmable logic devices. This paper presents basic design tools for the PCA-Chip2 as the first step to develop the total design environment. Given a C description of a target function, configuration data for PCA-Chip2 is automatically generated by the tools. Trial designs by the tools are also presented to demonstrate the practicability of the proposed approach.
The Another Solution Problem (ASP) of a problem is the following problem: for a given instance x of and a solution s to it, find a solution to x other than s. The notion of ASP as a new class of problems was first introduced by Ueda and Nagao. They also pointed out that parsimonious reductions which allow polynomial-time transformation of solutions can derive the NP-completeness of ASP of a certain problem from that of ASP of another. In this paper we consider n-ASP, the problem to find another solution when n solutions are given, and formalize it to investigate its characteristics. In particular we consider ASP-completeness, the completeness with respect to the reductions satisfying the properties mentioned above. The complexity of ASPs has a relation with the difficulty of designing puzzles. We prove the ASP-completeness of three popular puzzles: Slither Link, Cross Sum, and Number Place. Since ASP-completeness implies NP-completeness, these results can be regarded as new results of NP-completeness proof of puzzles.
Xiang-Yan ZENG Yen-Wei CHEN Zensho NAKAO Hanqing LU
We propose a novel pixel pattern-based approach for texture classification, which is independent of the variance of illumination. Gray scale images are first transformed into pattern maps in which edges and lines, used for characterizing texture information, are classified by pattern matching. We employ principal component analysis (PCA) which is widely applied to feature extraction. We use the basis functions learned through PCA as templates for pattern matching. Using PCA pattern maps, the feature vector is comprised of the numbers of the pixels belonging to a specific pattern. The effectiveness of the new feature is demonstrated by applications to the image retrievals of the Brodatz texture database. Comparisons with multichannel and multiresolution features indicate that the new feature is quite time saving, free of the influence of illumination, and has comparable accuracy.
Yukiko KUBO Shigetoshi NAKATAKE Yoji KAJITANI Masahiro KAWAKITA
One of the difficulties in routing problem is in wirability which is to guarantee a physical connection of a given topological route. Wirability often fails since the width of a wire is relatively large compared with the size of modules. As a possible solution, this paper proposes an incremental wiring algorithm which generates wires net-by-net without overlapping other pre-placed circuit elements. The idea is to divide a wire into a series of rectangles and handles them as modules with additional constraints to keep the shape of the wire. The algorithm was implemented and experimented on a small instance to show its promising performance.