Shin'ichi NAGANO Yoshiaki KAKUDA Tohru KIKUNO
Verification of responsive communication protocols is to determine whether they can recover to a normal state within a predetermined time, even when they enter an abnormal state due to any fault. In this paper, we propose a new verification method for responsive communication protocols using virtual system states, each of which represents several system states. Next, in order to evaluate the effectiveness of the new method, we develop a verification tool based on the proposed method. Then we apply the tool to a broadcasting protocol and measure several metrics on the tool. The experimental results show that (1) the number of system states, (2) the amount of memory used by the tool, and (3) the execution time of the tool, can be drastically reduced.
Unfolding originally introduced by McMillan is gaining ground as a partial-order based method for the verification of concurrent systems without state space explosion. However, it can be exposed to redundancy which may increase its size exponentially. So far, there have been trials to reduce such redundancy resulting from conflicts by improving McMillan's cut-off criterion. In this paper, we show that concurrency is also another cause of redundancy in unfolding, and present an algorithm to reduce such redundancy in live, bounded and reversible Petri nets which is independent of any cut-off algorithm.
Kaoru TAKAHASHI Toshihiko ANDO Toshihisa KANO Goichi ITABASHI Yasushi KATO
In a distributed concurrent system such as a computer communication network, the system components communicate with each other via communication links in order to accomplish a desired distributed application. If the links are dynamically established among the components, the system configuration as well as its behavior becomes complex. In this paper, we give formal specification of such a dynamically reconfigurable system in which the components are modeled by communicating finite state machines executed concurrently with the communication links which are dynamically established and disconnected. We also present an algorithm to validate the safety and link-related properties in the specified behavior. Finally, we design and implement a simulator and a validator that enables execution and validation of the given specification, respectively.
Shyh-Jong CHEN Rung-Ji SHANG Xian-June HUANG Shang-Jang RUAN Feipei LAI
By treating each different output pattern as a state, we propose a low power architecture for pipelined circuits using bipartition. It is possible that the output of a pipelined circuit transit mainly among some of different states. If some few states dominate most of the time, we could partition the combinational portion of a pipelined circuit into two blocks: one that contains the few states with high activity is small and the other that contains the remainder with low activity is big. The original pipelined circuit is bipartitioned into two individual pipelined circuits. An additional combination logic block is introduced to control which of the two partitioned blocks to work. Power reduction is based on the observation that most time the small block is at work and the big one is at idle. In order to minimize the power consumption of this architecture, we present an algorithm that can improve the efficiency of this additional control block. Experiments with MCNC benchmarks show high percentage of power saving by using our new architecture for low power pipelined circuit design.
Takuji KOUSAKA Hiroshi KAWAKAMI Tetsushi UETA
In this article, we propose a square wave generator whose switching threshold values are switched by external inputs. This circuit is designed to simulate the synchronized luminescence of coupled fireflies. We investigate the behavior of the solutions in two coupled oscillators. The dynamics are demonstrated by a linear autonomous equation piecewisely, therefore, a one-dimensional return map is derived. We also prove the existence of stable in-phase synchronization in the coupled oscillator by using the return map, and we show the existence of regions of periodic solutions within a parameter space. Some theoretical results are confirmed by laboratory measurements.
Osamu MIZUNO Shinji KUSUMOTO Tohru KIKUNO Yasunari TAKAGI Keishi SAKAMOTO
In this paper, we consider a simple development process consisting of design and debug phases, which is derived from actual concurrent development process for embedded software at a certain company. Then we propose two-phase project control that examines the initial development plan at the end of design phase, updates it to the current status of the development process and executes the debug phase under the new plan. In order to show the usefulness, we define three imaginary projects based on actually executed projects in a certain company: the project that executes debug phase under initial plan, the project that applies the proposed approach, and the project that follows a uniform plan. Moreover, to execute these projects, we use the project simulator, which has already been developed based on GSPN model. Judging from the number of residual faults in all products, we found that project B is the best among them.
Hiroyuki KITAJIMA Yuji KATSUTA Hiroshi KAWAKAMI
In this paper, we study bifurcations of equilibrium points and periodic solutions observed in a resistively coupled oscillator with voltage ports. We classify equilibrium points and periodic solutions into four and eight different types, respectively, according to their symmetrical properties. By calculating D-type of branching sets (symmetry-breaking bifurcations) of equilibrium points and periodic solutions, we show that all types of equilibrium points and periodic solutions are systematically found. Possible oscillations in two coupled oscillators are presented by calculating Hopf bifurcation sets of equilibrium points. A parameter region in which chaotic oscillations exist is also shown by obtaining a cascade of period-doubling bifurcation sets.
Haruo KOBAYASHI Toshiya MIZUTA Kenji UCHIDA Hiroyuki MATSUURA Akira MIURA Tsuyoshi YAKIHARA Sadaharu OKA Daisuke MURATA
This paper describes the design and performance of a high-speed 6-bit ADC using SiGe HBT for measuring-instrument applications. We show that the Gummel-Poon model suffices for SiGe HBT modeling and then we describe that the folding/interpolation architecture as well as simple, differential circuit design are suitable for ADC design with SiGe HBT. Measured results show that the nonlinearity of the ADC is within 1/2 LSB, and the effective bits are 5. 2 bits at an input frequency of 100 MHz and 4. 2 bits at 200 MHz with 768 MS/s. We also describe some design issues for folding/interpolation ADC.
Yen-Wei CHEN Hiroshi ARAKAWA Zensho NAKAO Katsumi YAMASHITA Ryosuke KODAMA
Penumbral imaging is a technique which uses the facts that spatial information can be recovered from the shadow or penumbra that an unknown source casts through a simple large circular aperture. The technique is based on a linear deconvolution. In this paper, a two-step method is proposed for decoding penumbral images. First a local-statistic filter based on adaptive windowing is applied to smooth the noise; then, followed by the conventional linear deconvolution. The simulation results show that the reconstructed image is dramatically improved in comparison to that without the noise-smoothing filtering, and the proposed method is also applied to real experimental X-ray imaging.
Masahide ABE Masayuki KAWAMATA
In this paper, we compare the performance of evolutionary digital filters (EDFs) for IIR adaptive digital filters (ADFs) in terms of convergence behavior and stability, and discuss their advantages. The authors have already proposed the EDF which is controlled by adaptive algorithm based on the evolutionary strategies of living things. This adaptive algorithm of the EDF controls and changes the coefficients of inner digital filters using the cloning method or the mating method. Thus, the adaptive algorithm of the EDF is of a non-gradient and multi-point search type. Numerical examples are given to demonstrate the effectiveness and features of the EDF such that (1) they can work as adaptive filters as expected, (2) they can adopt various error functions such as the mean square error, the absolute sum error, and the maximum error functions, and (3) the EDF using IIR filters (IIR-EDF) has a higher convergence rate and smaller adaptation noise than the LMS adaptive digital filter (LMS-ADF) and the adaptive digital filter based on the simple genetic algorithm (SGA-ADF) on a multiple-peak surface.
We show that under some conditions an attacker can break the public-key cryptosystem proposed by J. Schwenk and J. Eisfeld at Eurocrypt '96 which is based on the difficulty of factoring over the ring Z/nZ [x], even though its security is as intractable as the difficulty of factoring a rational integer. We apply attacks previously reported against RSA-type cryptosystems with a low exponent to the Schwenk-Eisfeld cryptosystem and show a method of breaking the Schwenk-Eisfeld signature with a low exponent.
Ashraf A. M. KHALAF Kenji NAKAYAMA
Time series prediction is very important technology in a wide variety of fields. The actual time series contains both linear and nonlinear properties. The amplitude of the time series to be predicted is usually continuous value. For these reasons, we combine nonlinear and linear predictors in a cascade form. The nonlinear prediction problem is reduced to a pattern classification. A set of the past samples x(n-1),. . . ,x(n-N) is transformed into the output, which is the prediction of the next coming sample x(n). So, we employ a multi-layer neural network with a sigmoidal hidden layer and a single linear output neuron for the nonlinear prediction. It is called a Nonlinear Sub-Predictor (NSP). The NSP is trained by the supervised learning algorithm using the sample x(n) as a target. However, it is rather difficult to generate the continuous amplitude and to predict linear property. So, we employ a linear predictor after the NSP. An FIR filter is used for this purpose, which is called a Linear Sub-Predictor (LSP). The LSP is trained by the supervised learning algorithm using also x(n) as a target. In order to estimate the minimum size of the proposed predictor, we analyze the nonlinearity of the time series of interest. The prediction is equal to mapping a set of past samples to the next coming sample. The multi-layer neural network is good for this kind of pattern mapping. Still, difficult mappings may exist when several sets of very similar patterns are mapped onto very different samples. The degree of difficulty of the mapping is closely related to the nonlinearity. The necessary number of the past samples used for prediction is determined by this nonlinearity. The difficult mapping requires a large number of the past samples. Computer simulations using the sunspot data and the artificially generated discrete amplitude data have demonstrated the efficiency of the proposed predictor and the nonlinearity analysis.
Yasutoshi KURIHARA Tsuneo ENDOH
Solder joint reliability was studied for hybrid ICs, in which chip components such as FETs, resistors and capacitors were mounted with Sn-Sb solder on an insulated Al substrate and transfer-molded with epoxy resin. Suitable resin selection for molding was also studied. The structure was estimated to have a lifetime of more than ten thousand cycles in the thermal cycling test under the condition of -55/150, for FETs and passive elements. Equivalent plastic strains generated in the soldering layer for the non-molded structure were 4. 6% for the FETs and 3.5% for the passive elements. But, these strains were approximately 1/3 to 1/2 and 1/10 for the molded structure, respectively. This was the main reason for high reliability of the molded structure. Resins with a wide range of thermal expansion coefficient(8-26 ppm/)could be put to practical use, because of the higher reliability of the molded structure. However, a thermal expansion coefficient of about 15 ppm/ was prefered to decrease stress at the interface between the substrate and the molding resin.
Jenn-Huei Jerry LIN Jyh-Shan CHANG Tzi-Dar CHIUEH
Noise cancelation and system identification have been studied for many years, and adaptive filters have proved to be a good means for solving such problems. Some neural networks can be treated as nonlinear adaptive filters, and are thus expected to be more powerful than traditional adaptive filters when dealing with nonlinear system problems. In this paper, two new heterogeneous recurrent neural network (HRNN) architectures will be proposed to identify some nonlinear systems and to extract a fetal electrocardiogram (ECG), which is corrupted by a much larger noise signal, Mother's ECG. The main difference between a heterogeneous recurrent neural network (HRNN) and a recurrent neural network (RNN) is that a complete neural network is used for the feedback path along with an error back-propagation (BP) neural network as the feedforward one. Different feedback neural networks can be used to provide different feedback capabilities. In this paper, a BP neural network is used as the feedback network in the architecture we proposed. And a self-organizing feature mapping (SOFM) network is used next as an alternative feedback network to form another heterogeneous recurrent neural network (HRNN). The heterogeneous recurrent neural networks (HRNN) successfully solve these two problems and prove their superiority to traditional adaptive filters and BP neural networks.
Hiroyuki SEKI Yasunori ISHIHARA Hiroki DODO
Method schemas were proposed as a formal model of object-oriented languages. A method schema S is called consistent if, for each method invocation during the execution of S, a method definition to be bound to the invoked method name is uniquely determined. However, the consistency testing problem is known to be undecidable in general. This paper presents an algorithm which analyzes the consistency of a given method schema. The algorithm decides the consistency problem in polynomial time for monadic method schemas. We also provide an incremental algorithm for testing consistency after updates of a method schema.
Masanori HAMAMURA Shin'ichi TACHIKAWA
Vehicular speed response phase locked loop (VSR-PLL) is a novel circuit to remove a steady-state frequency offset which arises in the receiver with directive antenna. In this paper, the circuit is applied to Ricean fading environment. For the application of VSR-PLL to Ricean statistics channel, the Doppler shift information of direct wave must be obtained because the self-oscillation frequency of VCO is controlled by using the information. This paper describes an estimation method for the Doppler shift of the direct wave, and shows the several results of the performance analysis for the estimation method and proposed VSR-PLL with the method. As a result, we found that the proposed VSR-PLL could reduce the irreducible bit-error rate for QPSK system from about 10-2 to 10-3 on several conditions.
This paper describes key technologies for implementing ATM internode signalling. The reliability of a multimedia handling network can be improved by setting multiple virtual paths(VPs)between two nodes and setting signalling links over each internode VP. A software structure appropriate for handling the signalling protocol(MTP3b)within this framework is proposed. We also propose a cost-effective and reliable way to set a signalling route between a node and the service control point(SCP), based on the associate mode structure. Evaluation by implementing a node system shows that it requires only 15% more dynamic program steps for one sending/receiving sequence of the VP signalling than the existing method for circuit-related information. Thus, we could attain highly reliable and cost-effective signalling for ATM multimedia networks.
Kaoru WATANABE Masakazu SENGOKU Hiroshi TAMURA Shoji SHINODA
The lower-bounded p-collection problem is the problem where to locate p sinks in a flow network with lower bounds such that the value of a maximum flow is maximum. This paper discusses the cover problems corresponding to the lower bounded p-collection problem. We consider the complexity of the cover problem, and we show polynomial time algorithms for its subproblems in a network with tree structure.
Masanari TANIGUCHI Miyataka KANAZAWA Tasuku TAKAGI
Surface damage of the electrical contact is a primary cause of failure in many electronic devices which use sliding contacts. Therefore, the quantitative observation of the contact surface is one of the most important subjects for improvement of contact reliability. In this study, in order to clarify the relationship between the contact resistance and the damage on the contact surface, a digital image measuring system (DIMS) was developed. A shadow image processing technique (SIPT) was applied to the damage analysis on the sliding contact surface. The damage width on the contact surface and the damaged image could be obtained with a 3-D graphic image by applying both DIMS and SIPT. Part of the relationship between the damage on the contact surface and the contact resistance could be obtained in the case when Cu is used for the moving contact and Cu and Ni are used for the static contact.
Shuichi YUNOKI Toshinori YOSHINO Takashi TANABE Tetsuji UEDA Takeshi OKI
We developed a glass ferrule fiber optic connector. During development, we also studied wear-resistant coating technology for preventing scratches on the surface of a glass ferrule. The method of coating was sputtering, and the material was alumina. We confirmed that a thin uniform coating could be formed on the ferrule surface to improve the durability of glass ferrule connectors.