Masaya OHTA Kazumichi MATSUMIYA Akio OGIHARA Shinobu TAKAMATSU Kunio FUKUNAGA
This article analyzes dynamics of the chaotic neural network and minimum searching principle of this network. First it is indicated that the dynamics of the chaotic newral network is described like a gradient decent, and the chaotic neural network can roughly find out a local minimum point of a quadratic function using its attractor. Secondly It is guaranteed that the vertex corresponding a local minimum point derived from the chaotic neural network has a lower value of the objective function. Then it is confirmed that the chaotic neural network can escape an invalid local minimum and find out a reasonable one.
Shiho MORIAI Kazumaro AOKI Kazuo OHTA
It is important to find the best linear expression to estimate the vulnerability of cryptosystems to Linear Cryptanalysis. This paper shows the results of the best linear expressions search of FEAL-N (N32) and discusses the security of FEAL against Linear Cryptanalysis. We improve Matsui's search algorithm which determines the best linear expressions, and apply it to FEAL. The improved search algorithm finds all the best linear expression of FEAL-N (N32) much faster than the original; the required time is decreased from over three months to about two and a half days. We find the best linear expressions of FEAL-7, FEAL-15, and FEAL-31 with deviations of 1.152-8, 1.482-20, and 1.992-41, respectively. These linear expressions have higher deviations than those derived from Bi-ham's 4-round iterative linear approximations. Using these data we calculated the number of known plaintexts required to attack FEAL-8, FEAL-16, and FEAL-32. It is proved that FEAL-32 is secure against Linear Cryptanalysis.
Nguyen Ngoc BINH Masaharu IMAI Akichika SHIOMI Nobuyuki HIKICHI
This paper proposes a new method to design an optimal pipelined instruction set processor using formal HW/SW codesign methodology. A HW/SW partitioning algorithm for selecting an optimal pipelined architecture is introduced. The codesign task addressed in this paper is to find a set of hardware implemented operations to achieve the highest performance of an ASIP with pipelined architecture under given gate count and power consumption constraints. The problem formalization as well as the proposed algorithm can be considered as an extension of our previous work toward a pipelined architecture. The experimental results show that the proposed method is quite effective and efficient.
JooHun LEE MyungJin BAE Souguil ANN
A fast pitch search algorithm using the skipping technique is proposed to reduce the computation time in CELP vocoder. Based on the characteristics of the correlation function of speech signal, the proposed algorithm skips over certain ranges in the full pitch search range in a simple way. Though the search range is reduced, high speech quality can be maintained since those lags having high correlation values are not skipped over and are used for search by closed-loop analysis. To improve the efficiency of the proposed method, we develop three variants of the skipping technique. The experimental results show that the proposed and the modified algorithm can reduce the computation time in the pitch search considerably, over 60% reduction compared with the traditional full search method.
Guangyi BAI Akifumi MAKINOUCHI
In this paper, we describe a distributed paged-object server to efficiently support the storage management for new generation database management systems. This storage server is based on distributed client/server architecture, and allows clients to directly map database files onto distributed shared virtual memory (DSVM). In this architecture, there is a server at each site and the server only supports the clients in the same site. This improves performance utilizing client machine resources and offloading the shared resourcer server machine and the network. Therefore, this architecture may avoid drawbacks such as bottleneck in a traditional centralized client/server architecture, and also may reduces network traffic and improve performance efficiency of remote file access using Net File System (NFS). Moreover, this architecture allows distributed shared objects to reside and execute anywhere and to be used by any clients on the network. A prototype system (called WAKASHI/D) is implemented under the Mach operating system. The distributed, shared, and transactional virtual memory that the system supports is either volatile or persistent and they can be accessed by user applications in a uniform way. This paper also presents a performance evaluation and analysis of WAKASHI/D to compare its centralized version WAKASHI/C and demonstrates that the distributed server has substantial performance benefits.
Hideki SAWAGUCHI Wataru SAKURAI
The performance of decision-feedback equalization combined with maximum-likelihood detection (DFE/ML) using the fixed-delay-tree-search/decision feedback (FDTS/DF) algorithm was estimated analytically in terms of the length of the feedback-filter and the depth of the ML-detector. Performance degradation due to error propagation in the feedback-loop and in the ML-detector was taken into account by using a Markov process analysis. It was quantitatively shown that signal-to-noise-ratio (SNR) performance in high-density magnetic recording channels can be improved by combining an ML-detector with a feedback-filter and that the error propagation in the DFE channel can be reduced by using an ML-detector. Finally, it was found that near-optimum performance with regard to channel SNR and error propagation can be achieved, over the channel density range from 2 to 3, by increasing the sum of the feedback-filter length and the ML-detector depth to six bits.
Portable terminals have the potential of providing information and communication services not only to computer experts at their offices but also to many users being in a variety of daily life situations. The current user interfaces (UIs) of portable terminals are not suitable for a novice user of computers; they require some knowledge on computers from a user. To overcome this problem, the authors tried to implement their knowledge on the daily life in the design of a UI for novice users. As a result, two UI mechanisms, called Novice Interface and Graphical Metaphor Interface, which provide operations, expressions, and data structures in a way similar to those usually used in daily life are proposed. Novice Interface is to provide easy to use environment. It adopts a direct manipulation device with three buttons and a model of data structures, called Small World Model, that limits the number of functions and the depth of hierarchical menu. Graphical Metaphor Interface, being an extension of Novice Interface, is to provide services with a display screen that makes them well-understandable for any user. The proposed UI mechanisms were implemented in a prototype terminal and its software platform. The former offers several applications of the information services (like teleshopping, home banking, or database retrieval) and the communication services (like pen-based image mail, software fax, or telewriting); the latter enables those application programs to provide a consistent UI.
The organization of the proposed file and algorithms for search and maintenance of the file are simpler than those of a similar key search file based on B+-tree. An experiment using 230,188 keys with length 1-16 shows the good performance of the file. The storage utilization of the file is about 68%.
Object-oriented programming requires different skills from those of traditional structured programming. Thus, a good interactive environment for beginners of object-oriented programming should be provided. We have designed and implemented a visual environment of object-oriented programming for beginners. If a programmer draws a diagram of the tree of the hierarchy of classes visually by using our tool, the relationship between superclasses and subclasses are automatically established. Moreover, in order to prevent careless mistakes to override methods, the prototype environment in the Smalltalk language checks written methods. We conducted an experiment with our tool and evaluated its usefulness.
Hiroyuki KAWAI Yoshitsugu INOUE Rebert STREITENBERGER Masahiko YOSHIMOTO
This paper presents a newly developed architecture for a highly parallel DSP suited for realtime image reaognition. The programmable DSP was designed for a variety of image recognition systems, such as computer vision systems, character recognition systems and others. The DSP consists of functional units suited for image recognition: a SIMD processing core, a hierarchical bus, an Address Generation Unit, Data Memories, a DMA controller, a Link Unit, and a Control Unit. The high performance of 3.2GOPS is realized by the eight-parallel SIMD core with a optimized pipeline structure for image recognition algorithms. The DSP supports flexible data transfers including an extraction of lacal images from raster scanned image data, a table-loop-up, a data-broadcasting, and a data-shifting among processing units in the SIMD core, for effective execution of various image processing algorithms. Hence, the DSP can process a 55 spatial filtering for 512512 images within 13.1 msec. Adopting the DSP to a Japanese character recognition system, the speed of 924 characters/sec can be achieved for feature extractions and feature vectors matchings. The DSP can be integrated in a 14.514.5 mm2 single-chip, using 0.5 µm CMOS technology. In this paper, the key features of the architecture and the new techniques enabling efficient operation of the eight parallel processing units are described. Estimation of the performance of the DSP is also presented.
Nobutaro SHIBATA Mayumi WATANABE
Low-power circuit techniques for size-configurable SRAM macrocells with wide range of operating frequency are presented. Synchronous specification is employed to drastically reduce the power dissipation for low-frequency applications. Dynamic circuits applied to bitliness and sense circuits contribute to the reduction of power dissipation. To enhance the high-end limitation of operating frequency, a latch-type fast sense circuit and an accurate activation-timing control technique for size-configurable memory macrocells are proposed, and a special CMOS-level input buffer is devised to enable the minimum cycle time of fast synchronous memory macrocells to be evaluated with conventional LSI-test systems. A memory macrocell using these techniques was fabricated with 0.5-µm CMOS technology. Its power consumption strongly depends on the operating frequency, and at 3-MHz suitable for codeless telephone applications is less than 5% that of an asynchronous SRAM designed with full-static CMOS circuits. Its maximum operating frequency at 3.3-V in 100-MHz.
Hiroshi SUGAWARA Toshio TAKESHIMA Hiroshi TAKADA Yoshiaki S. HISAMUNE Kohji KANAMORI Takeshi OKAZAWA Tatsunori MUROTANI Isao SASAKI
A 3.3 V single power-supply 64 Mb flash memory with a DBL programming scheme has been developed and fabricated with 0.4 µm CMOS technology. 50 ns access time and 256 b erase/programming unit-capacity have been achieved by using hierarchical word- and bit-line structures and DBL programming scheme. Furthermore in order to lower operating voltage the HiCR cell is used. The chip size is 19.3 mm13.3 mm.
This paper describes a flexible point-to-multipoint access protocol for the fiber-optic passive double star (PDS) system. To provide various types of services, and permit flexibility in changing transport capacity, a time division multiple access (TDMA) scheme for the PDS system is considered. Dynamic time slot multiplexing based on TDMA is proposed to provide required time slots efficiently according to service changes. The effectiveness of dynamic time slot multiplexing is calculated and compared to fixed time slot multiplexing for telephony services. A TCM/TDMA frame structure and an access protocol enabling dynamic time slot multiplexing are proposed. ONU bandwidth is dynamically assigned by using a set of pointers. The ONU access protocol causes no interruption to operating ONUs on the same PDS system during the configuration or reconfiguration of an ONU. The access time is analyzed to estimate the performance of the access protocol. The probability density of access time is calculated for the number of ONUs connected. The calculation results indicate that a PDS system can accommodate up to around 60 ONUs within the maximum access time specified by ITU-T. The experimental results also agree fairly well with the theoretical values.
A new approach is presented for the detection and computation of a two-dimensional motion field in image sequences. This computational model has a multi-channel motion detector and an optimal motion selector. In the motion detector, each channel has an inherent spatial resolution. The detector computes a two-dimensional motion field by the gradient-based method in parallel. The motion selector compares those candidates of the motion field by a correlation value of the intensity patterns hierarchically arranged from low to high resolution. It then determines the most probable motion for each image point. Experimental results are shown for synthetic images. This model can detect more reliable motion fields than the conventional one-chanel model.
Kouichi YAMAGUCHI Harald SINGER Shoichi MATSUNAGA Shigeki SAGAYAMA
This paper describes a novel speaker-independent speech recognition method, called speaker-consistent parsing", which is based on an intra-speaker correlation called the speaker-consistency principle. We focus on the fact that a sentence or a string of words is uttered by an individual speaker even in a speaker-independent task. Thus, the proposed method searches through speaker variations in addition to the contents of utterances. As a result of the recognition process, an appropriate standard speaker is selected for speaker adaptation. This new method is experimentally compared with a conventional speaker-independent speech recognition method. Since the speaker-consistency principle best demonstrates its effect with a large number of training and test speakers, a small-scale experiment may not fully exploit this principle. Nevertheless, even the results of our small-scale experiment show that the new method significantly outperforms the conventional method. In addition, this framework's speaker selection mechanism can drastically reduce the likelihood map computation.
Yoshihiro KANEKO Koichi SUZUKI Shoji SHINODA Kazuo HORIUCHI
A problem of synthesizing an optimal file transfer on a file transmission net N is to consider how to distribute, with a minimum total cost, copies of a file J with some information from source vertex set S to all vertices of N by the respective vertices' copy demand numbers. The case of |S| =1 has been studied so far. This paper deals with N such that |S|1, where a forest-type file transfer is defined. This paper proposes a polynomial time algorithm to synthesize an optimal forest-type file transfer on such N satisfying SM U, where M and U are mother vertex set and positive demand vertex set of N, respectively.
Hyung Chul KIM Seung Ryoul MAENG Jung Wan CHO
Motion estimation is a major part of the video coding, which traces the motion of moving objects in video sequences. Among various motion estimation algorithms, the Hierarchical Block-Matching Algorithm (HBMA) that is a multilayered motion estimation algorithm is attractive in motion-compensated interpolation when accurate motion estimation is required. However, parallel processing of HBMA is necessary since the high computational complexity of HBMA prevents it from operating in real-time. Further, the repeated updates of vectors naturally lead to pipelined processing. In this paper, we present a pipelined architecture for HBMA. We investigate the data dependency of HBMA and the requirements of the pipeline to operate synchronously. Each pipeline stage of the proposed architecture consists of a systolic array for the block-matching algorithm, a bilinear interpolator, and a latch mechanism. The latch mechanism mainly resolves the data dependency and arranges the data flow in a synchronous way. The proposed architecture achieves nearly linear speedup without additional hardware cost over a non-pipelined one. It requires the clock of 2.70 ns to process a large size of frame (e.q. HDTV) in real-time, which is about to be available under the current VLSI technology.
Shin'ichi SATOH Hiroshi MO Masao SAKAUCHI
This letter presents a new method to efficiently extract closed loops as primitive symbols in line drawings. Our method uses a graph search technique for efficiency and exhaustibility, and also incorporates feasibility criteria of symbols. Experiments clearly demonstrated the method's effectiveness.
Computational approaches to concept formation often share a top-down, incremental, hill-climbing classification, and differ from each other in the concept representation and quality criteria. Each of them captures part of the rich variety of conceptual knowledge and many are well suited only when the object-attribute distribution is not sparse. Formal concept analysis is a set-theoretic model that mathematically formulates the human understanding of concepts, and investigates the algebraic structure, Galois lattice, of possible concepts in a given domain. Adopting the idea of representing concepts by mutual closed sets of objects and attributes as well as the Galois lattice structure for concepts from formal concept analysis, we propose an approach to concept formation and develop OSHAM, a method that forms concept hierarchies with high utility score, clear semantics and effective even with sparse object-attribute distributions. In this paper we describe OSHAM, and in an attempt to show its performance we present experimental studies on a number of data sets from the machine learning literature.
A Hierarchical Cubic Network (HCN) is a hierarchical hypercube network proposed by Ghose. The HCN is topologically superior to many other similar networks, in particular, the hypercube. It has a considerably lower diameter than a comparable hypercube and is realized using almost half the number of links per node as a comparable hypercube. In this paper, we propose the shortest routing algorithm in HCN(n, n) and show that the diameter of HCN(n, n) with 22n nodes is n(n1)/31 which is about 2/3 of that of a comparable hypercube. We also propose the optimal routing algorithm in HCN(m, n) where mn and obtain that its diameter is n(m1)/31. Typical parallel algorithms run in HCN(m, n) with the same time complexity as a hypercube and the hypercube topology can be emulated with O(1) time complexity in it.