Yoko UWATE Yoshifumi NISHIO Akio USHIDA
In this study, a modeling method of the intermittency chaos using the Markov chain is proposed. The performances of the intermittency chaos and the Markov chain model are investigated when they are injected to the Hopfield Neural Network for a quadratic assignment problem or an associative memory. Computer simulated results show that the proposed modeling is good enough to gain similar performance of the intermittency chaos.
The alternating variant of the shrinking two-pushdown automaton of Buntrock and Otto (1998) is introduced. It is shown that the class of languages accepted by these automata is contained in the class of deterministic context-sensitive languages, and that it contains a PSPACE-complete language. Hence, the closure of this class of languages under log-space reductions coincides with the complexity class PSPACE.
Guangyi LIU Yang YANG Xiaokang LIN
A number of on-line and off-line algorithms for load balancing on multiple paths for MPLS (MultiProtocol Label Switching) traffic engineering have now been proposed, in which it is always assumed that sets of LSPs (Label Switched Path) have already been established between node pairs. While how to choose these paths is an important issue in traffic engineering, it has not been well studied yet. In this paper, we attempt to fill in this gap. As the shortest paths are always preferred in routing problems, we evaluate several k shortest path algorithms from the viewpoint of bandwidth use efficiency and the number of the found paths. Extensive simulations have been performed in different kinds of topologies to factor out effects of network characteristics on these algorithms' path calculation performances. It is found out that the performances of the evaluated algorithms are limited in some cases and the design of new algorithms for the path calculation problem is worth studying in the future.
Hirohisa AMAN Kenji YAMASAKI Hiroyuki YAMADA Matu-Tarow NODA
Cohesion is an important software attribute, and it is one of significant criteria for assessing object-oriented software quality. Although several metrics for measuring cohesion have been proposed, there is an aspect which has not been supported by those existing metrics, that is "cohesive-part size." This paper proposes a new metric focusing on "cohesive-part size," and evaluates it in both of qualitative and quantitative ways, with a mathematical framework and an experiment measuring some Java classes, respectively. Through those evaluations, the proposed metric is showed to be a reasonable metric, and not redundant one. It can collaborate with other existing metrics in measuring class cohesion, and will contribute to more accurate measurement.
Kugan VIVEKANANDARAJAH Thambipillai SRIKANTHAN Christopher T. CLARKE Saurav BHATTACHARYYA
Energy dissipation in cache memories is becoming a major design issue for embedded microprocessors. Predictive filter cache based instruction cache hierarchy has been shown to effectively reduce the energy-delay product. In this paper, a simplified pattern prediction algorithm is proposed for the filter cache hierarchy. The prediction scheme relies on the static nature of the hit or miss pattern of the instruction access streams. The static patterns are maintained in a small 32x1-bit wide Static Pattern Table (SPT). Our investigations show that the proposed prediction algorithm is superior to that based on Next Fetch Prediction Table (NFPT) for all the benchmarks simulated. With the proposed approach, energy delay product reduction of up to 6.79% was evident when compared with that using NFPT. Moreover, since the prediction scheme is based on the static assignment of patterns, it lends well for area and power efficient implementation than that employs dynamic pattern prediction although it is marginally inferior (i.e. 0.69%) in term of energy delay product.
Kun-Lin TSAI Shanq-Jang RUAN Chun-Ming HUANG Edwin NAROSKA Feipei LAI
Circuit partition, retiming and state reordering techniques are effective in reducing power consumption of circuits. In this paper, we propose a partition architecture and a methodology to reduce power consumption when designing low power IP, named PRC (Partition and Reordering Circuit). The circuit reordering synthesis flow consists of three phases: first, evenly partition the circuit based on the Shannon expansion; secondly encode the output vectors of each partition to build an equivalent functional logic. Finally, apply reordering algorithm to reorganize the logic function to reduce power consumption and decrease area cost. The validity of our architecture is proven by applying it to MCNC benchmark with simulation environment.
Yusuke SUZUKI Eisuke KUDOH Fumiyuki ADACHI
Adaptive antenna array is a promising technique to increase the link capacity in mobile radio communications systems by suppressing multiple access interference (MAI). In the mobile radio, the received signal consists of discrete paths, each being a cluster of many irresolvable paths arriving from different directions. For large arrival angle spread of each cluster of irresolvable paths, antenna array cannot form a beam pattern that sufficiently suppresses MAI even in the presence of single interference signal and hence, the transmission performance may degrade. In this situation, the use of antenna diversity may be a better solution. It is an interesting question as to which can achieve a better performance, antenna diversity reception or adaptive antenna array. In this letter, we study the impact of the arrival angle spread on the DS-CDMA transmission performances achievable with adaptive antenna array and antenna diversity reception. It is pointed out that the arrival angle spread is an important parameter to determine the performances of adaptive antenna array and antenna diversity.
This paper presents a Quiet-Noisy scan technique for low power delay fault testing. The novel scan cell design provides both the quiet and noisy scan modes. The toggling of scan cell outputs is suppressed in the quiet scan mode so the power is saved. Two-pattern tests are applied in the noisy scan mode so the delay fault testing is possible. The experimental data shows that the Quiet-Noisy scan technique effectively reduces the test power to 56% of that of the regular scan. The transition fault coverage is improved by 19.7% compared to an existing toggle suppression low power technique. The presented technique requires very minimal changes in the existing MUX-scan Design For Testability (DFT) methodology and needs virtually no computation. The penalties are area overhead, speed degradation, and one extra control in test mode.
Guo-rui FENG Ling-ge JIANG Chen HE
A watermarking system is secure as long as it satisfies Kerckhoffs principle according to the cryptography. In this letter, two novel techniques named the encrypted orthogonal transformation and its improved scheme as useful preprocessing methods are presented to apply to the watermarking field, which can enhance the security of the watermarking scheme. Compared to discrete cosine transform watermarking algorithms, this method has similar robustness but higher security.
Yoko UWATE Yoshifumi NISHIO Tetsushi UETA Tohru KAWABE Tohru IKEGUCHI
In this paper, performance of chaos and burst noises injected to the Hopfield Neural Network for quadratic assignment problems is investigated. For the evaluation of the noises, two methods to appreciate finding a lot of nearly optimal solutions are proposed. By computer simulations, it is confirmed that the burst noise generated by the Gilbert model with a laminar part and a burst part achieved the good performance as the intermittency chaos noise near the three-periodic window.
Noriyuki MINEGISHI Ken-ichi ASANO Keisuke OKADA Masahiko YOSHIMOTO
A single chip processor suitable for various multimedia communication products has been developed. This chip achieves real-time bi-directional encoding/decoding for CIF resolution video at a frame rate of 30 fr/s, and meets such standards, as H.320 and H.324. The chip is composed of a video-processing unit for MPEG-4 and H.26X standards, a DSP unit for speech codec and multiplex processes, and a RISC unit for managing the whole chip. By heterogeneous multiple processor architecture, careful study of task sharing for each processing unit and bus configuration, a single chip solution can be achieved with reasonable operation speed and low-power consumption suitable for consumer products. Moreover, by applying an original video processing unit architecture, this chip achieves real-time bi-directional encoding/decoding for CIF-resolution video at a frame rate of 30 fr/s. An original video bus was developed to provide high performance and low-power consumption while sharing one external memory which is necessary for various video processes and graphics functions. This shared memory also has the effect of minimizing die size and I/O ports. This chip has been fabricated with 4-metal 0.18 µm CMOS technology to produce a chip area of 10.510.5 mm2 with 1.2 W power dissipation including I/O power, at 1.8 V for internal supply and 3.3 V for I/O power supply.
This letter presents a novel quandtree-based image authentication technique especially suitable for the content authentication of high quality required digital images. The host image and the hiding marks generate quadtrees which record the information of host images. Any malicious tamper to the image is reflected from the recovered marks. Compared to other authentication schemes based on the fragile watermarking technique, the host image is not at all modified and the detection to malicious tamper is sensitive.
Keiichi KATAMINE Masanobu UMEDA Isao NAGASAWA Masaaki HASHIMOTO
The modeling of an application domain and its specific knowledge description language are important for developing knowledge-based systems. A rapid-prototyping approach is suitable for such developments since in this approach the modeling and language development are processed simultaneously. However, programming languages and their supporting environments which are usually used for prototyping are not necessarily adequate for developing practical applications. We have been developing an integrated development environment for knowledge-based systems, which supports all the development phases from the early prototyping phase to final commercial development phase. The environment called INSIDE is based on a Prolog abstract machine, and provides all of the functions required for the development of practical applications in addition to the standard Prolog features. This enables the development of both prototypes and practical applications in the same environment. Moreover, their efficient development and maintenance can be achieved. In addition, the effectiveness of INSIDE is described by examples of its practical application.
Yusuke KANNO Hiroyuki MIZUNO Nobuhiro OODAIRA Yoshihiko YASU Kazumasa YANAGISAWA
A power-aware interconnect circuit design--called µI/O architecture--has been developed to provide low-cost system solutions for System-on-Chip (SoC) and System-in-Package (SiP) technologies. The µI/O architecture provides a common interface throughout the module enabling hierarchical I/O design for SoC and SiP. The hierarchical I/O design allows the driver size to be optimized without increasing design complexity. Moreover, it includes a signal-level converter for integrating wide-voltage-range circuit blocks and a signal wall function for turning off each block independently--without invalid signal transmission--by using an internal power switch.
Comparison of intelligent and random testing in data inputting is still under discussion. Little is also known about testing for the whole software and empirical testing methodology when random testing used. This study research not only for data inputting testing, but also operation of software (called transitions) in order to test the whole GUI software by intelligent and random testing. Methodology of this study is that we attempt to research efficiency of random and intelligent testing by Chinese postman problem. In general, random testing is considered straightforward but not efficient. Chinese postman problem testing is complicated but efficient. The comparison between random and intelligent testing would give further recommendation for software testing methodology.
Masaki KUREMATSU Takamasa IWADE Naomi NAKAYA Takahira YAMAGUCHI
In this paper, we describe how to exploit a machine-readable dictionary (MRD) and domain-specific text corpus in supporting the construction of domain ontologies that specify taxonomic and non-taxonomic relationships among given domain concepts. In building taxonomic relationships (hierarchical structure) of domain concepts, some hierarchical structure can be extracted from a MRD with marked subtrees that may be modified by a domain expert, using matching result analysis and trimmed result analysis. In building non-taxonomic relationships (specification templates) of domain concepts, we construct concept specification templates that come from pairs of concepts extracted from text corpus, using WordSpace and an association rule algorithm. A domain expert modifies taxonomic and non-taxonomic relationships later. Through case studies with "the Contracts for the International Sales of Goods (CISG)" and "XML Common Business Library (xCBL)", we make sure that our system can work to support the process of constructing domain ontologies with a MRD and text corpus.
Hiroshi KAZATO Minoru TAKAISHI Takashi KOBAYASHI Motoshi SAEKI
Refactoring is one of the promising techniques for improving software design by means of behavior-preserving structural transformation, and is widely taken into practice. In particular, it is frequently applied to design models represented with UML such as class diagrams. However, since UML design models includes multiple diagrams which are closely related from various views, to get behavior-preserving property, we should get the other types of design information and should handle with the propagation of the change on a diagram to the other diagrams. For example, to refactor a class diagram, we need behavioral information of methods included in the class and should also refactor diagrams which represent the behavior, such as state diagrams, activity diagrams. In this paper, we introduce refactoring on design models as transformations of a graph described by UML class diagram and action semantics. First, we define basic transformations of design models that preserve the behavior of designed software, and compose them into refactoring operations. We use Object Constraint Language (OCL) to specify when we can apply a refactoring operation. Furthermore we implement our technique on a graph transformation system AGG to support the automation of refactoring, together with evaluation mechanism of OCL expressions. Some illustrations are presented to show its effectiveness. The work is the first step to handle with refactoring on UML design models in integrated way.
Masayuki MIYAZAKI Hidetoshi TANAKA Goichi ONO Tomohiro NAGANO Norio OHKUBO Takayuki KAWAHARA
A vibration-to-electric energy converter as a power generator through a variable-resonating capacitor is theoretically and experimentally demonstrated as a potential on-chip battery. The converter is constructed from three components: a mechanical-variable capacitor, a charge-transporter circuit and a timing-capture control circuit. An optimum design methodology is theoretically described to maximize the efficiency of the vibration-to-electric energy conversion. The energy-conversion efficiency is analyzed based on the following three factors: the mechanical-energy to electric-energy conversion loss, the parasitic elements loss in the charge-transporter circuit and the timing error in the timing-capture circuit. Through the mechanical-energy conversion analysis, the optimum condition for the resonance is found. The parasitic elements in the charge-transporter circuit and the timing management of the capture circuit dominate the output energy efficiency. These analyses enable the optimum design of the energy-conversion system. The converter is fabricated experimentally. The practical measured power is 0.12 µW, and the conversion efficiency is 21%. This efficiency is calculated from a 43% mechanical-energy conversion loss and a 63% charge-transportation loss. The timing-capture circuit is manually controlled in this experiment, so that the timing error is not considered in the efficiency. From our result, a new system LSI application with an embedded power source can be explored for the ubiquitous computing world.
Yuichiro MIYAOKA Nozomu TOGAWA Masao YANAGISAWA Tatsuo OHTSUKI
This paper proposes a hardware/software cosynthesis algorithm for processors with heterogeneous registers. Given a CDFG corresponding to an application program and a timing constraint, the algorithm generates a processor configuration minimizing area of the processor and an assembly code on the processor. First, the algorithm configures a datapath which can execute several DFG nodes with data dependency at one cycle. The datapath can execute the application program at the least number of cycles. The branch and bound algorithm is applied and all the number of functional units and memory banks are tried. For an assumed number of functional units and memory banks, an appropriate number of heterogeneous registers and connections to functional units and registers are explored. The experimental results show effectiveness and efficiency of the algorithm.
Hirohisa GAMBE Kazuhisa OHBUCHI Teruo ISHIHARA Takaaki ZAKOJI Kiyomichi ARAKI
Turbo codes are of particular use in applications of wireless communication systems, where various types of communication are required and the data rate must be changed, depending on the situation. In such applications, adaptation of turbo coding specifications is required in terms of coding block size, data speed, parity bit arrangement or configuration of a convolutional coder, as well as the need for real time processing. We present new ideas to provide these capabilities for a low power decoder circuit by focusing on the configuration of a convolutional decoding algorithm, which occupies a significant proportion of the hardware circuit. We utilize the Soft Output Viterbi Algorithm (SOVA) for the base algorithm, produced by adding the concept of a soft output to the Viterbi Algorithm (VA). The Maximum A Posteriori (MAP) algorithm and its simplified version of MAX-LOG-MAP are also widely known. MAP is recognized as a means of achieving very good bit error rate (BER) characteristics. On the other hand SOVA has been regarded as a method which can be simply implemented with less computational resources, but at a cost of higher degradation. However, in many of recent systems we combine turbo coding with some other method such as Automatic Repeat Request (ARQ) to maintain a good error correction performance and we only have to pay attention to the performance in the range of low carrier-to-noise ratio (CNR), where SOVA has fairly satisfactory BER characteristics. This makes the SOVA approach attractive for a low power programmable IP macro solution, when the fundamental advantage of SOVA is fully utilized in the implementation of an LSI circuit. We discuss the processing algorithm and circuit configuration and show that about 40% reduction in power consumption can be achieved. It is also shown that the IP macro can handle 1.5 Mbps information decoding at 100 MHz clock rate.