Jiaxin WU Bing LI Li ZHAO Xinzhou XU
Maaki SAKAI Kanon HOKAZONO Yoshiko HANADA
Xuecheng SUN Zheming LU
Yuanhe WANG Chao ZHANG
Jinfeng CHONG Niu JIANG Zepeng ZHUO Weiyu ZHANG
Xiangrun LI Qiyu SHENG Guangda ZHOU Jialong WEI Yanmin SHI Zhen ZHAO Yongwei LI Xingfeng LI Yang LIU
Meiting XUE Wenqi WU Jinfeng LUO Yixuan ZHANG Bei ZHAO
Rong WANG Changjun YU Zhe LYU Aijun LIU
Huijuan ZHOU Zepeng ZHUO Guolong CHEN
Feifei YAN Pinhui KE Zuling CHANG
Manabu HAGIWARA
Ziqin FENG Hong WAN Guan GUI
Sungryul LEE
Feng WANG Xiangyu WEN Lisheng LI Yan WEN Shidong ZHANG Yang LIU
Yanjun LI Jinjie GAO Haibin KAN Jie PENG Lijing ZHENG Changhui CHEN
Ho-Lim CHOI
Feng WEN Haixin HUANG Xiangyang YIN Junguang MA Xiaojie HU
Shi BAO Xiaoyan SONG Xufei ZHUANG Min LU Gao LE
Chen ZHONG Chegnyu WU Xiangyang LI Ao ZHAN Zhengqiang WANG
Izumi TSUNOKUNI Gen SATO Yusuke IKEDA Yasuhiro OIKAWA
Feng LIU Helin WANG Conggai LI Yanli XU
Hongtian ZHAO Hua YANG Shibao ZHENG
Kento TSUJI Tetsu IWATA
Yueying LOU Qichun WANG
Menglong WU Jianwen ZHANG Yongfa XIE Yongchao SHI Tianao YAO
Jiao DU Ziwei ZHAO Shaojing FU Longjiang QU Chao LI
Yun JIANG Huiyang LIU Xiaopeng JIAO Ji WANG Qiaoqiao XIA
Qi QI Liuyi MENG Ming XU Bing BAI
Nihad A. A. ELHAG Liang LIU Ping WEI Hongshu LIAO Lin GAO
Dong Jae LEE Deukjo HONG Jaechul SUNG Seokhie HONG
Tetsuya ARAKI Shin-ichi NAKANO
Shoichi HIROSE Hidenori KUWAKADO
Yumeng ZHANG
Jun-Feng Liu Yuan Feng Zeng-Hui Li Jing-Wei Tang
Keita EMURA Kaisei KAJITA Go OHTAKE
Xiuping PENG Yinna LIU Hongbin LIN
Yang XIAO Zhongyuan ZHOU Mingjie SHENG Qi ZHOU
Kazuyuki MIURA
Yusaku HIRAI Toshimasa MATSUOKA Takatsugu KAMATA Sadahiro TANI Takao ONOYE
Ryuta TAMURA Yuichi TAKANO Ryuhei MIYASHIRO
Nobuyuki TAKEUCHI Kosei SAKAMOTO Takuro SHIRAYA Takanori ISOBE
Shion UTSUMI Kosei SAKAMOTO Takanori ISOBE
You GAO Ming-Yue XIE Gang WANG Lin-Zhi SHEN
Zhimin SHAO Chunxiu LIU Cong WANG Longtan LI Yimin LIU Zaiyan ZHOU
Xiaolong ZHENG Bangjie LI Daqiao ZHANG Di YAO Xuguang YANG
Takahiro IINUMA Yudai EBATO Sou NOBUKAWA Nobuhiko WAGATSUMA Keiichiro INAGAKI Hirotaka DOHO Teruya YAMANISHI Haruhiko NISHIMURA
Takeru INOUE Norihito YASUDA Hidetomo NABESHIMA Masaaki NISHINO Shuhei DENZUMI Shin-ichi MINATO
Zhan SHI
Hakan BERCAG Osman KUKRER Aykut HOCANIN
Ryoto Koizumi Xiaoyan Wang Masahiro Umehira Ran Sun Shigeki Takeda
Hiroya Hachiyama Takamichi Nakamoto
Chuzo IWAMOTO Takeru TOKUNAGA
Changhui CHEN Haibin KAN Jie PENG Li WANG
Pingping JI Lingge JIANG Chen HE Di HE Zhuxian LIAN
Ho-Lim CHOI
Akira KITAYAMA Goichi ONO Hiroaki ITO
Koji NUIDA Tomoko ADACHI
Yingcai WAN Lijin FANG
Yuta MINAMIKAWA Kazumasa SHINAGAWA
Sota MORIYAMA Koichi ICHIGE Yuichi HORI Masayuki TACHI
Sendren Sheng-Dong XU Albertus Andrie CHRISTIAN Chien-Peng HO Shun-Long WENG
Zhikui DUAN Xinmei YU Yi DING
Hongbo LI Aijun LIU Qiang YANG Zhe LYU Di YAO
Yi XIONG Senanayake THILAK Yu YONEZAWA Jun IMAOKA Masayoshi YAMAMOTO
Feng LIU Qian XI Yanli XU
Yuling LI Aihuang GUO
Mamoru SHIBATA Ryutaroh MATSUMOTO
Haiyang LIU Xiaopeng JIAO Lianrong MA
Ruixiao LI Hayato YAMANA
Riaz-ul-haque MIAN Tomoki NAKAMURA Masuo KAJIYAMA Makoto EIKI Michihiro SHINTANI
Kundan LAL DAS Munehisa SEKIKAWA Tadashi TSUBONE Naohiko INABA Hideaki OKAZAKI
This article discusses on PDM (Petri net based Development Methodology) which integrates approaches, modeling methods, design methods and analysis methods in a coherent manner. Although various development techniques based on Petri nets have demonstrated advantages over conventional techniques, those techniques are rather ad hoc and lack an overall picture on entire development process. PDM anticipates to provide a refernce process model to develop distributed systems with various Petri net based development methods. Behavioral properties of distrbuted systems can be an appropriate application domain of PDM.
kazuhito OHMAKI Yutaka SATO Ichiro OGATA Kokichi FUTATSUGI
We often use data flow diagrams or state transition diagrams to design software systems with concurrency. We call those diagrams as nets in this paper. Semantics of any methods to describe such software systems should be defined in some formal ways. There would be no doubts that any nets should be supported by appropriate theoretical frameworks. In this paper, we use CCS as a typical algebraic approach of using formulas to express concurrent behaviors and point out the different features of CCS from Petri nets. Any approaches should be not only theoretically beautiful but also practically useful. We use a specification language LOTOS as such example which has two features, CCS and ADT, and is designed to specify practical communication protocols. Algebraic approaches of using formulas, like LOTOS, can be considered as a compact way to express concurrent behaviors. We explore our discussions of net-oriented approaches into UIMS research fields. After mentioning state transition models of UIMS, we exemplify a practically used example, VIA-UIMS, which has been developed by one of authors. VIA-UIMS employs a net-oriented architecture. It has been designed to reconstuct tools which have already been widely used in many sites.
Tomohiro MURATA Kenzou KURIHARA Ayako ASHIDA
Reactive systems respond to internal or external stimuli and act in an event-driven manner. It is generally difficult to specify a complex reactive systems' behavior using conventional state machine formalism. One reason is that actual reactive systems are usually formed by combining plural state-machince that behave concurretly. This paper presents the State Diagram Matrix (SDM) which is a visual and hierarchical formalism of such a reactive system's behavior. SDM has two concepts. The first is matrix plane description on which 3-dimensional state space is projected. The second is state abstraction for hierarchical state-machine definition. Understandability and reliability of control software was improved as a consequence of adopting SDM for specifying disk-subsystem control requirements. The development support functions of SDM using a workstation are also described.
Yoichi NAGAO Hironobu URABE Shinichi NAKANO Sadatoshi KUMAGAI
We describe K-NET, a support system for development of sequence control programs. The K-NET description model is based on the colored Petri net and timed Petri net. K-NET concisely expresses sequence control flow including synchronization, interlock and concurrence, and provides high-level data processing by being combined with a conventional procedural language. K-NET has an editor, simulator, generator, reporter and monitor to support the control program development procedure ranging from basic and detail design to programming and testing. We have added a new function to K-NET so it assists development of control programs for programmable controllers, and have applied it to an automatic bolt supplying system. The operation results are satisfactory.
Kiyoshi MIKAMI Hiroshi TAMURA Masakazu SENGOKU Yoshio YAMAGUCHI
The synchronic distance is a fundamental concept in a Petri net. Marked graphs form a subclass of Petri nets. Given a matrix D, we are interested in the problem of finding a marked graph whose synchronic distance matrix is D. It is wellknown that the synchronic disrance matrix of a marked graph is a distance matrix. In this letter, we give a matrix D such that D is a distance matrix and there does not exist a marked graph whose synchronic distance matrix is D.
Gy Bum KIM Gang Soo LEE Jung Mo YOON
In this paper, we show that Petri nets can be applied practically to design and analysis of concurrent, parallel and embedded mode systems such as a lift system that is familiar to our daily life. Modeling behavioral characteristics of the lift, we extend a standard Petri net by constant timed transition, faultable transition, stochastic transition and condition transition concepts. Likewise, we prsesnt some results of design and analysis of the system. This method can be applied to design and analysis of another concurrent systems.
Winfried HAHN Takeshi YOSHIMURA
Toshiaki MIYAZAKI Mitsuo IKEDA
We propose a high-level synthesis method that uses data path information given by a designer. The main purpose of this method is to generate a control unit, one of the most difficult aspects of hardware design. In general, designers can specify data paths easily. Therefore, we believe that basing a method on specified data path information is the best way to synthesize hardware that more closely satisfies the designer's requirements. Moreover, a datapath-constrained scheduling algorithm can perform both "scheduling" and "resource allocation" at the same time. In particular, the resource allocation explicitly decides used paths as well as functional modules in each execution state. This cannot be done with previously reported algorithms.
Tomohiko OHTSUKA Nobuyuki KUROSAWA Hiroaki KUNIEDA
The paper presents the improvement of out new approach to optimize the process parameter variation, device heat and wire parasitics for analog LSI design by explicitly incorporating various performance estimations into objective functions for placement and routing. To minimize these objective functions, the placement by the simulated annealing method, and maze routing are effectively modified with the perfomance estimation. The improvement results in the excellent performance driven layout for the large size of analog LSIs.
Tetsushi KOIDE Shin'ichi WAKABAYASHI Noriyoshi YOSHIDA
This paper presents a linear time optimal algorithm to a channel pin assignment problem for hierarchical building-block layout design. The channel pin assignment problem is to determine positions of the pins of nets on the top and the bottom sides of a channel, which are partitioned into several intervals, and the pins are permutable within their associated intervals. The channel pin assignment problem has been shown NP-hard in general. We present a linear time optimal algorithm for an important special case of the problem, in which there is at most one pin of a net within each interval in the channel. The proposed algorithm is optimal in a sense that it can minimize both the channel density and the total wire length of the channel. We also disscuss how to apply our algorithm to the pin assignment in the L-shaped and staircase channels. Experimental results indicate that substantial reduction in both channel density and estimated total wire length can be obtained by permuting pins in each interval. Combining the proposed algorithm with a conventional channel router, results of channel routing also achieve large amount of reduction of the number of tracks, total wire length, and the number of vias.
Shoichiro YAMADA Shunichi NAKAYAMA
We propose a new multiple folding algorithm for the gate matrix layout, and apply it to generation of rectangular blocks with flexible size. The algorithm consists of two phases, the net partitioning and the gate arangement, and both algorithms are based on the multi-way mini-cut technique. In the first and second phases, the width and height of the multiple folded gate matrix block are directly minimized, resperctively, such that the area is minimized and desired aspect ratio of the block is obtained. The features of the present algorithm are as hollows: (1) Dead space on the gate matrix block can be minimized, (2) the aspect ratio can be controlled finely, (3) since polar graphs are successfully used in the second phase, the efficiency of the algorithm can be much improved. The experimental results show the effectiveness of our algorithm.
In this paper, an exact algorithm for finding minimum test set which detects all testable stuck-at faults of a given combinational circit is presented. So far several heuristic algorithms for this problem are proposed, but no efficient exact algorithms are known. To solve this exactly, minimum test set problem is formalized as a minimum set covering problem, and then implicit manipulation technique using binary decision diagrams(BDDs) is applied. The algorithm presented in the paper has two contributions. One is utilization of maximal compatible fault set, which can drastically reduce the number of candidates for minimum test set. A new BDD based algorithm for extracting all maximal compatible fault sets is shown. The other is a new implicit manipulation technique handling with huge covering matrix. Actually, the algorithm using this technique can handle minimum set covrering problem with over ten thousand columns in a few minutes. Experiments using ISCAS benchmark circuits show that the algorithm is quite efficient for small(100-300 gates) circuits. A computational complexith of minimum test set problen is much higher than that of ordinary test pattern generation problem, so that practical signifcance of this method is not high. But the algorithm is still useful for evaluation of other heuristic algorithms. furthermore, this implicit manipulation technique can also be applied to other minimumset covering problems.
Since, in a VLSI circuit, the number of transistors and the clock frequency are constantly increasing, it is important to analyze the voltage drop and current density on a full chip's power networks. We propose a new hierarchical power analysis system named XPOWER. A new reduction algorithm for the resistance and current source network is used in this system. The algorithm utilizes the design hierarchy in nature and is independent of network topology. Networks at each level are reduced into small and equivalent networks, and this reduction is performed recursively from the bottom levels of the design hierarchy. At each step of the reduction, the network under consideration consists of two kinds of objects: (1) reduced child networks, and (2) the interconnection between child networks. After all networks have been reduced, circuit equationa are solved recursively from the top. This allows to decrease the size of the matrix to be solved and to reduce the execution time. Experimental results show that the factor of reduction in matrix size is from 1/10 to 1/40 and execution is six times faster than with flat analysis. The power networks of a 16 bit digital signal processor was analyzed within 15 minutes using XPOWER.
This paper prsesnts a reduced swing signal data transmission method for the bus architectures in VLSIs, which consists of small size bus drivers of inverters, dual rail transmission lines, termination resistors and sense amplifiers for regenerating signal swing. The optimum value of signal swing and driving capacity of sense amplifier are given as functions of transmission line capacitance based on a criterion of area
Hiroyuki HIGUCHI Kiyoharu HAMAGUCHI Shuzo YAJIMA
Full scan design of sequential circuits results in greatly reducing the cost of their test generation. However, it introduces the extra expense of many test clocks to control and observe the values of flip-flops because of the need to shift values for the flip-flops into the scan panh. In this paper we propose a new method of generating compact test sequences for scan-based sequential circuits on the assumption that the number of shift clocks is allowed to vary for each test vector. The method is based on Boolean function manipulation using a shared binary decision diagram (SBDD). Although the test generation algorithm is basically for general sequential circuits, the computational cost is much lower for scan-based sequential circuits than for non-scanbased sequential circuits because the length of a test sequence for each fault is limited. Experimental results show that, for all the tested circuits, test sequences generated by the method require much smaller number of test clocks than compact or minimum test sets for combinational logic part of scan-based sequential circuits. The reduction rate was 48% on the average in the experiments.
A hardware accelerator for a raster-based design-rule checking called BITDRC for a bit-mapping CAD system is described. BITDRC is a special-purpose hardware accelerator which performs design-rule checking for the Manhattan layout style VLSI circuis, much faster than the software checking which belonged to the bit-mapping CAD system before. The bit-mapping CAD system had effectively been developed for both of educational and VLSI design purposes, and just needs only a personal computer as a compact working environment. The proposed hardware architecture is rather simply and characterized by the bit-mapping CAD system where it works on. The hardware architecture and checking algorithm have been confirmed by implementing a bread-board prototype using discrete components. As a result, the processing time of BITDRC is speeded up as much as 500 times faster than the original software and takes only 4 seconds for checking every rule on a(1500
Mototaka KURIBAYASHI Masaaki YAMADA Takashi MITSUHASHI Nobuyuki GOTO
A fast and efficient heuristic hierarchical global router for Sea-of-Gates(SOG) with embedded macro-blocks is described. The key point in the method is carry out a new optimal domain decomposition scheduling at every hierarchical level. This scheduling is intended to avoid macro-block-through wirings and to reduce wiring congestion near macro-blocks which may occur at lower levels. The new global router yielded superior results compared with previous hierarchical routers and a non-hierarchical maze router by evaluating with several actual SOG circuits including a 300K gate master chip and benchmark data supplied from MCNC. Overflows were reduced to one-half or one-quarter for macro-block embedded data compared with previous hierarchical routers. Concerning the running time, the router remarkably outperformed the non-hierarchical maze router, which took more than 390 times longer time for the tested large data.
Nasahiro TOMITA Naoaki SUGANUMA Kotaro HIRANO
This paper presents a Reconfigurable Machine (RM). capable of efficiently implementing a wide range of computationlly complex algorithms. Its highly flexble architecture combining FPGA's with RAM's supports a wide range of applications. Since its "gate-level programmability" allows us to implement various kinds of parallel processing techniques, RM provides a perfomance comparable to exising "special-purpose" engines. The in-circuit reconfiguration capability of FPGA's is used to reload several kinds of configuration data during power on. Thus, RM behaves itself like a general-purpose computer applicable to various kinds of applications by loading programs. A Reconfigurable Machine-
Alauddin Y. ALOMARY Masaharu IMAI Nobuyuki HIKICHI
One of the most interesting and most analyzed aspects of the CPU design is the instruction set design. How many and which operations to be provided by hardware is one of the most fundamental issues relaing to the instruction set design. This paper describes a novel method that formulates the instruction set design of ASIP (an Application Specific Integrated Processor) using a combinatorial appoach. Starting with the whole set of all possible candidata instructions that represesnt a given application domain, this approach selects a subset that maximizes the performance under the constraints of chip area, power consumption, and functional module sharing relation among operations. This leads to the efficient implementation of the selected instructions. A branch-and-bound algorithm is used to solve this combinatorial optimization problem. This approach selects the most important instructions for a given application as well as optimizing the hardware resources that implement the selected instructions. This approach also enables designers to predict the perfomance of their design before implementing them, which is a quite important feature for producing a quality design in reasonable time.
Recently, there has been a lot of research on solving combinatorial problems using Binary Decision Diagrams (BDDs), which are very efficient representations of Boolean functions. We have already developed a Boolean Expression Manipulator, which calculates and reduces Boolean expressions quickly based on BDD techniques. This greatly aids our works on developing VLSI CAD systems and solving combinatorial problems. Any combinatorial problem can be described in Boolean expressions; however, arithmetic operations, such as addition, subraction, multiplication, equality and inequality, are also used for describing many practical problems. Arithmetic operations provide simple descriptions of problems in many cases. In this paper, we present an arithmetic Boolean expression manipulator (BEM-
Yoshinobu HIGAMI Seiji KAJIHARA Kozo KINOSHITA
In this paper we present a method to generate test sequences for stuck-at faults in sequential circuits which have distinguishing sequences. Since the circuit may have no distinguishing sequence, we use two design techniques for circuits which have distinguishing sequences. One is at state transition level and the other is at gate level. In our proposed method complete test sequence can be generated. The sequence consists of test vectors for the combinational part of the circuit, distinguishing sequences and transition sequences. The test vectors, which are generated by a combinational test generator, cause faulty staes or faulty output responses for a fault, and disinguishing sequences identify the differences between faulty states and fault free states. Transition sequences are necessary to make the state in the combinational vectors. And the distinguishing sequence and the transition sequence are used in the initializing sequence. Some techniques for shortening the test sequence is also proposed. The basic ideas of the techniques are to use a short initializing sequence and to find the order in concatenating sequences. But fault simulation is conducted so as not to miss any faults. The initializing sequence is obtained by using a distinguishing sequence. The efficiency of our method is shown in the experimental results for benchmark circuits.
Xingzhao LIU Akio SAKAMOTO Takashi SHIMAMOTO
Evolution programs have been shown to be very useful in a variety of search and optimization problems, however, until now, there has been little attempt to apply evolution programs to channel routing problem. In this paper, we present an exolution program and identify the key points which are essential to successfully applying evolution programs to channel routing problem. We also indicate how integrating heuristic information related to the problem under consideration helps in convergence on final solutions and illustrate the validity of out approach by providing experimental results obtained for the benchmark tests. compared with the optimal solutions.
Yoichi SHIRAISHI Jun'ya SAKEMI Kazuyuki FUKUDA
A global routing problem is formulated as a multi-commodity network flow problem. The formulation gives no restriction over the shape of a routing pattern and makes it possible to obtain the optimal solution by using a mathematical programming method. Moreover, it can be naturally extended to the problem even optimizing routing length objectives for net delay and clock skew perfomances by using the goal programming method. An approximation algorithm solving the multi-commodity network flow problem is proposed by adding a merge step of wires whose source-sink pairs are exactly the same and a step restricting an area for searching routes. Experimental results show that this global routing algorithm connected with a line-search detailed router can generate a complete routing for interblock routing problems with more than 2400 wires in two industrial chips. The total amount of procassing time for both problems is about 90 minutes on a mainframe computer.
Shinji KIMURA Shunsuke TSUBOTA Hiromasa HANEDA
The discrete time analysis of logic circuits is usually more efficient than the continuous time analysis, but the preciseness of the discrete time analysis is not guaranteed. The paper shows a method to decide a unit time for a logic circuit under which the analysis result is the same as the result based on the continuous time. The delay time of an element is specified with an interval between the minimum and maximum delay times, and we assume an analysis method which enumerates all possible delay cases under the deisrete time. Our main theorem is as follows: refine the unit time by a factor of 1/2, and if the analysis result with a unit time u and that with a unit time u/2 are the same, then u is the expected unit time.
Hiroki AKABOSHI Hiroto YASUURA
A modern architect can not design high performance computer architecture without thinking all factors of performance from hardware level (logic/layout design) to system level (application programs, operating systems, and compilers). For computer architecture design, there are few practical CAD tools, which support design activities of the architect. In this paper, we propose a CAD tool, called COACH, for computer architecture design. COACH supports architecture design from hardware level to system level. To make a high-performance general purpose computer system, the architect evaluates system performance as well as hardware level performance. To evaluate hardware level performance accurately, logic/layout synthesis tools and simulator are used for evaluation. Logic/layout synthesis tools translate the architecture design into logic circuits and layout pattern and simulator is used to get accurate information on hardware level performance which consists of clock frequency, the number of transistors, power consumption, and so on. To evaluate system level performance, a compiler generator is introducd. The compiler generator generates a compiler of a programming language from the desripition of architecture design. The designed architecture is simulated in the behavior level with programs compiled by the compiler, and the architect can get information on system level performance which consists of program execution steps, etc. From both hardware level performance and system level performance, the architect can evaluate and revise his/her architecture, considering the architecture from hardware level to system level. In this paper, we propose a new design methodology which uses (
Hoyong CHOI Hironori MAEDA Takashi KOHARA Nagisa ISHIURA Isao SHIRAKAWA Akira MOTOHARA
This letter presents an algorithm named SPM which generates test patterns for single stuck-at faults in synchronous sequential circuits based on a product machine traversal method. The new idea presented in this letter is partitioned image computation combined with a mixed breadth-first/depth-first search. Image computation is carried out in partitioned manner by substituting constant logical values to some input variables. This brings about significant reduction in storage requirement during image computation. A test generator based on SPM achieved 100% fault efficiency for the ISCAS'89 benchmark circuits with not more than 32 flip-flops.
Saed SAMADI Akinori NISHIHARA Nobuo FUJII
In practical applications of digital filters it is more realistic to treat multiplier coefficients as finite intervals than restricting them to infinite or very long word-length representations. However, this can not be done it the frequency response performance under interval assumption is difficult to analyze. In this paper, it is proved that stable lattice allpass filters possess bounded continuous phase response when lattice parameters vary in bounded intervals. It is shown that sharp bounds on the interval phase response can be computed easily at an arbitrary frequency using a simple recursive procedure. Application of this property to the problem of finite word-length lattice allpass filter design is also discussed. By formulating this problem as an interval design it is possible to solve it efficiently independent of the number system used to represent multiplier coefficients.
Masaharu KOMATSU Kozo KINOSHITA
In this paper, we will clarify the problem of consecutively lost customer due to buffer overflow in an IPP, M/M/l/K queueing system including an M1, M2/M/l/K queueuing system as a special case. We define a length of a consecutive loss as the number of customers consecutively lost due to buffer overflow. And, we obtain individual distributions of the lengths of consecutive losses for the IPP- and Markov-sources. From analytical and numerical results, it is shown that either they are geometrical or they can be approximated by a geometric distribution. Also, from numerical examples, we show some properties of the length of consecutive customer loss.
Sangyoub KIM Iickho SONG Sun Yong KIM
When orignal signals are contaminated by both additive and signal-dependent noise components, the test statistics of locally optimum detector are obtained for detection of weak composite signals based on the generalized Neyman-Pearson lemma. In order to consider the non-additive noise as well as purely-additive noise, a generalized observation model is used in this paper. The locally optimum detector test statisics are derived for all different cases according to the relative strengths of the known signal, random signal, and signal-dependent noise components. Schematic diagrams of the structures of the locally optimum detector are also included. The finite sample-size performance characteristics of the locally optimum detector are compared with those of other common detectors.
High speed simulation of neural networks can be achieved through parallel implementations capable of exploiting their massive inherent parallelism. In this paper, we show how this inherent parallelism can be effectively exploited on parallel data-driven systems. By using these systems, the asynchronous parallelism of neural networks can be naturally specified by the functional data-driven programs, and maximally exploited by pipelined and scalable data-driven processors. We shall demonstrate the suitability of data-driven systems for the parallel simulation of neural networks through a parallel implementation of the widely used back propagation networks. The implementation is based on the exploitation of the network and training set parallelisms inherent in these networks, and is evaluated using an image data compression network.
An efficient algorithm is presented for finding all solutions of piecewise-linear resistive circuits. In this algorithm, a simple sign test is performed to eliminate many linear regions that do not contain a solution. Therefore, the number of simultaneous linear equations to be solved is substantially decreased. This test, in its original form, requires O(Ln2) additions and comparisons in the worst case, where n is the number of variables and L is the number of linear regions. In this paper, an effective technique is proposed that reduces the computational complexity of the sign test to O(Ln). Some numerical examples are given, and it is shown that all solutions can be computed very efficiently. The proposed algorithm is simple and can be easily programmed by using recursive functions.
Kazuhiro MOTEGI Shigeyoshi WATANABE
Many simulators in several fields use the finite difference method and they must solve the large sparse linear equations related. Particularly, if we use the direct solution method because of the convergency problem, it is necessary to adopt a method that can reduce the CPU time greatly. The Multi-Step Diakoptics (MSD) method is proposed as a parallel computation method with a direct solution which is based on Diakoptics, that is, a tearing-based parallel computation method for the sparse linear equations. We have applied the MSD algorithm for one, two and three dimensional finite difference methods. We require a parallel schedule that automatically partitions the desired object's region for study, assigns the processor elements to the partitioned regions according to the MSD method, and controls communications among the processor elements. This paper describes a parallel scheduling that was extended from a one dimensional case to a three dimensional case for the MSD method, and the evaluation of the algorithm using a massively parallel computer with distribuled memory(AP1000).
A systematic theory of the optimum sub-band interpolation using parallel wavelet filter banks presented with respect to a family of n-dimensional signals which are not necessarily band-limited. It is assumed that the Fourier spectrums of these signals have weighted L2 norms smaller than a given positive number. In this paper, we establish a theory that the presented optimum interpolation functions satisfy the generalized discrete orthogonality and minimize the wide variety of measures of error simultaneously. In the following discussion, we assume initially that the corresponding approximation formula uses the infinite number of interpolation functions having limited supports and functional forms different from each other. However, it should be noted that the resultant optimum interpolation functions can be realized as the parallel shift of the finite number of space-limited functions. Some remarks to the problem of distinction of images is presented relating to the generalized discrete orthogonality and the reciprocal property for the proposed approximation.
Alauddin Y. ALOMARY Masaharu IMAI Jun SATO Nobuyuki HIKICHI
The performance of ASIPs (Application Specific Integrated Processors) is heavily affected by the design of their instruction set architecture. In order to maximize the performance of ASIP, it is essential to design an architecture that has an optimum instruction set. This paper descibes a new method that automates the design of optimum instruction set of ASIP. This method solves the Instruction set implementation Method Selection Problem(IMSP). IMSP is to be solved in the instruction set architecture design. Frse, the IMSP is formalized as an integer programming problem, which is to maximize the perfomance of the CPU under the constraints of chip area and power consumption. Then, a branch-and-bound algorithm to solve IMSP is described. According to the experimental results, the proposed algorithm is quite effective and efficient in solving the IMSP. The presented method automates a complex part of the ASIP chip design and is also a good design tool that enables designer to predict the performance of their design before completion.
Takehiko ASHIYA Masao NAKAGAWA
In the future, it will be necessary that robot technology or environmental technology has an auditory function of recognizing sound expect for speech. In this letter, we propose a recognition system for the species of birds receiving birdcalls, based on network technology. We show the first step of a recognition system for the species of birds, as an application of a recognition system for environmental sound.
Kazuhiko IMANO Daitaro OKUYAMA Noriyoshi CHUBACHI
A new system of measuring the thickness of thin filn or paper using 40 kHz ultrasonic wave in air is described. The thickness of samples measured is smaller by a factor of sevreal hundreds than the wavelength of sound. Experinents with polymer and metal films and paper are described to demonstrate the measurement possibilities.
We propose a third-order low-pass notch filter realized by a single operational amplifier and a minimum number of equal-valued capacitors. As a design example we realize a Chebyshev filter with a ripple of 0.5 dB and it is shown that the experiment result is very good.
This letter presents a new method for adaptive control of nonminimum phase discrete-time systems with disturbances based on the technique of pole-zero placement. The long division method is used to decompose apolynomial into a stable polynomial and an unstable one. Finally, the results of computer simulation are presented to illustrate the effectiveness of the proposed method.
As a new method to generate a homogeneous, random, binary image with a rational power spectrum, this paper proposes a discrete-valued auto-regressive equation, of which random coefficients and white noise excitation are all discrete-valued. The average and spectrum of the binary image are explicitly obtained in terms of the random coefficients. Some computer results are illustrated in figures.
Tsutomu MORIUCHI Kyoki IMAMURA
This paper presents a new method to derive the phase difference between n-tuples of an m-sequence over GF(p) of period pn-1. For the binary m-sequence of the characteristic polynomial f(x)=xn+xd+1 with d=1,2c or n-2c, the explicit formulas of the phase difference from the initial n-tuple are efficiently derived by our method for specific n-tuples such as that consisting of all 1's and that cosisting of one 1 and n-1 0's, although the previously known formula exists only for that consisting of all 1's.
Joarder KAMRUZZAMAN Yukio KUMAGAI Hiromitsu HIKITA
We present an extension of the previously proposed 3-layer feedforward network called a cascaded network. Cascaded networks are trained to realize category classification employing binary input vectors and locally represented binary target output vectors. To realize a nonlinearly separable task the extended cascaded network presented here is consreucted by introducing high order cross producted inputs at the input layer. In the construction of the cascaded network, two 2-layer networks are first trained independently by delta rule and then cascaded. After cascading, the intermediate layer can be understood as a hidden layer which is trained to attain preassigned saturated outputs in response to the training set. In a cascaded network trained to categorize binary image patterns, saturation of hidden outputs reduces the effect of corrupted disturbances presented in the input. We demonstrated that the extended cascaded network was able to realize a nonlinearly separable task and yielded better generalization ability than the Backpropagation network.