In this paper a method of recognizing waveform based on the Discrete Wavelet Transform (DWT) presented by us is applied to detecting the K-complex in human's EEG which is a slow wave overridden by fast rhythms (called as spindle). The features of K-complex are extracted in terms of three parameters: the local maxima of the wavelet transform modulus, average slope and the number of DWT coefficients in a wave. The 4th order B-spline wavelet is selected as the wavelet basis. Two channels at different resolutions are used to detect slow wave and sleep spindle contained in the K-complex. According to the principle of the minimum distance classification the classifiers are designed in order to decide the thresholds of recognition criteria. The EEG signal containing K-complexes elicited by sound stimuli is used as pattern to train the classifiers. Compared with traditional method of waveform recognition in time domain, this method has the advantage of automatically classifying duration ranks of various waves with different frequencies. Hence, it specially is suitable to recognition of signals which are the superimposition of waves with different frequencies. The experimental results of detection of K-complexes indicate that the method is effective.
Shigeru KAWAI Hisakazu KURITA Ichiro OGURA
Wavelength-division multiplexing (WDM) optical switching networks are one of most attractive technologies in optical interconnections. By combining with time-division multiplexing (TDM) and space-division multiplexing (SDM) technologies, remarkably high-throughput interconnections may be accomplished. In this paper, we propose WDM switching networks with time-division multiplexed optical signals by using free-space optics. We also propose novel WDM interconnections, including multiple-wavelength light-sources, optical fibers and wavelength-selectable detectors. We successfully confirmed basic principles for the WDM interconnections.
Sang Heon LEE Song Bai PARK Kyu Ho PARK
A simple method is presented to calculate the parasitic capacitance effect in the propagation delay of series-connected MOS (SCM) structures. This method divides SCM circuits into two parts and accurately calculates the contribution of each part to the difference from the delay without parasitic capacitances.
Zygmunt KRASISKI Takashi HINATA Shin-ichiro YAMASHITA Adam MAJEWSKI
The improved point-matching method with Mathieu function expansion for the accurate analysis of the W-type elliptical fiber with layers of any ellipticity is proposed. Results of our method are reliable, because we expand the electromagnetic fields by a sum of the complete set of wave functions in each layer of the fiber. Numerical results are presented for the highly-birefringent fibers with a hollow layer outside an elliptical core. It is found that such fibers can realize the large value of the modal birefringence as well as they can be suitable for the single-mode and single-polarization transmission. From the convergence tests, it is confirmed that the relative error of the modal birefringence is less than 0.01%. The comparison of our results with those by previously reported method is presented. The proposed method can be extended for analysis of the elliptical-core fibers with hollow pits and electromagnetic scattering by targets of the complex elliptical geometry.
Hiroyuki FUJIWARA Hirosuke YAMAMOTO Jinqiao REN
A new Hybrid-ARQ scheme with a convolutional code and the Viterbi decoding is proposed, which uses the packet combining technique and a retransmission criterion based on an estimated decoding error rate. The throughput and bit error rate are evaluated by theoretical bounds and computer simulations. It is shown that a given error rate tolerance can be attained with good throughput for any signal to noise ratio, i.e. for the slow time-varying channels. Furthermore, the throughput performance can be improved by retransmitting not all but a part of packet.
We developed a parallel bordered-block-diagonal (BBD) matrix solution for parallel circuit simulation. In parallel circuit sumulation on a MIMD parallel computer, a circuit is partitioned into as many subcircuits as the processors of a parallel computer. Circuit partition produce a BBD matrix. In parallel BBD matrix solution, diagonal blocks are easily solved separately in each processor. It is difficult, however, to solve the interconnection (IC) submatrix of a BBD matrix effectively in parallel. To make matters worse, the more a circuit is partitioned into subcircuits for highly parallel circuit simulation, the larger the size of an IC submatrix becomes. From an examination, we found that an IC submatrix is more dense (about 30% of all entries are non-zeros) than a normal circuit matrix, and the non-zeros per row in an IC submatrix are almost constant with the number of subcircuits. To attain high-speed circuit simulation, we devised a data structure for BBD matrix processing and an approach to parallel BBD matrix solution. Our approach solves the IC submatrix in a BBD matrix as well as the diagonal blocks in parallel using all processors. In this approach, we allocate an IC submatrix in block-wise order rather than in dot-wise order onto all processors. Thus, we balance the processor perfomance with the communication capacity of a parallel computer system. When we changed the block size of IC submatrix allocation from dot-wise order to 88 block-wise order, the 88 block-wise order allocation almost halved the matrix solution time. The parallel simulation of a sample circuit with 3277 transistors was 16.6 times faster than a single processor when we used 49 processors.
This paper proposes an electronic retail payment system to provide flexible and efficient funds transfers with adequate security, reliability, circulativity, and anonymity even in large-scale applications. Funds are represented by a portable intelligent device called a card issued by a supervising organization, the system provider. Funds can be transferred from a card to another at an intelligent terminal called a mediator. To update the balance of each card, two digital signatures are generated by a three-party protocol conducted by the cards and mediator, and are encoded and appended to a write-once separate memory in the card. Old signatures are simultaneously nullified. Through a wired or radio non-real-time link, the generated signatures are periodically reported to the system provider to systemically manage possible abuses.
Kiyotaka YAMAMURA Nobuo SEKIGUCHI
An efficient algorithm is presented for finding all solutions of piecewise-linear resistive circuits containing sophisticated transistor models such as the Gummel-Poon model or the Shichman-Hodges model. When a circuit contains these nonseparable models, the hybrid equation describing the circuit takes a special structure termed pairwise-separability (or tuplewise-separability). This structure is effectively exploited in the new algorithm. A numerical example is given, and it is shown that all solutions are computed very rapidly.
This paper discusses Boolean functions satisfying the propagation criterion (PC) and their balancedness. Firstly, we discuss Boolean functions with n variables that satisfy the PC with respect to all but three elements in {0,1}n-{(0,...,0)}. For even n4, a necessary and sufficient condition is presented for Boolean functions with n variables to satisfy the PC with respect to all but three elements in {0,1}n-{(0,...,0)}. From this condition, it is proved that all of these Boolean functions are constructed from all perfectly nonlinear Boolean functions with n-2 variables. For odd n3, it is shown that Boolean functions with n variables satisfying the PC with respect to all but three elements in {0,1}n-{(0,...,0)} satisfy the PC with respect to all but one elements in it. Secondly, Boolean functions satisfying the PC of degree n-2 and their balancedness are considered. For even n4, it is proved that an upper bound on the degree of the PC is n-3 for balanced Boolean functions with n variables. This bound is optimal for n=4,6. It is also proved that, for odd n3, balanced Boolean functions with n variables satisfying the PC of degree n-2 satisfy the PC with respect to all but one elements in {0,1}n-{(0,...,0)}.
Damgrd defined the notion of a collision intractable hash functions and showed that there exists a collection of collision intractable hash functions if there exists a collection of claw-free permutation pairs. For a long time, the necessary and sufficient condition for the existence of a collection of collision intractable hash functions has not been known, however, very recently Russell finally showed that there exists a collection of collision intractable hash functions iff there exists a collection of claw-free pseudo-permutation pairs. In this paper, we show an alternative necessary and sufficient condition for the existence of a collection of collision intractable hash functions, i.e., there exists a collection of collision intractable hash functions iff there exists a collection of distinction intractable pseudo-permutations.
This paper describes a new algorithm for calculating exact statistics on directional data and its application to pattern processing. Although information about directional characteristics is practically useful in image processing, e.g. texture analysis or color segmentation, dominant information is not always extracted as exact statistics on directional data. The main reason is concerned with periodicity inherent in directional data. For example, an expectation of a random variable X is defined as ∫xp(x)dx, where p(x) is a probability density function of X; therefore, when a random direction D is distributed only at 170[]and 170[] with same probability density, the expectation of D leads to 0[] if nothing about the periodicity is considered. We would, however, expect that the exact expectation of D should be 180[]. To overcome the problem, we, at first, define a directional distance in such a form that can introduce the periodicity. Then, we propose an idea of defining directional statistics by a problem of minimizing an arithmetic mean of squared directional distances to each sample direction. Because the periodicity is introduced to the directional distance definition, the directional statistics are calculated as the exact statistics on directional data. Although the introduced periodicity might cause the minimization to be complex, we can compensate the complexity by introducing recurrence formulas; consequently, dominant information can efficiently be extracted as the directional statistics from those data. Experiments on their applications to pattern processing show that the proposed algorithm works well in detecting (1) divergent points of distorted vector field patterns with noise and (2) moving directions from translational movement vector fields.
Makoto TSUJIGADO Teruo HIKITA Jun GINBAYASHI
In formal specification languages for parallel processes, such as CSP and LOTOS, algebraic laws for basic operators are provided that can be used to transform process expressions, and in particular, composition of processes can be calculated using these laws. Process composition can be used to simplify and improve the specification, and also to prove properties of the specification such as deadlock absence. We here test the practicality of process composition using CSP and suggest useful techniques, working in an example with nontrivial size and complexity. We emphasize that the size explosion of composed processes, caused by interleaving of the events of component processes, is a serious problem. Then we propose a technique, which we name two-way pipe, that can be used to reduce the size of the composed process, regarded as a program optimization at specification level.
Tetsuro NISHINO Jaikumar RADHAKRISHNAN
We exactly determine the number of negations needed to compute the parity functions and the complement of the parity functions. We show that with k NOT gates, parity can be computed on at most 2k+11 variables, and parity complement on at most 2k+12 variables. The two bounds are shown to be tight.
Jong Hwa LEE Su Won KANG Kyeong Ho YANG Choong Woong LEE
In a hybrid coder which employs motion compensation and discrete cosine transform (MC-DCT coder), up to 90% of bits are used to represent the quantized DCT blocks. So it is most important to represent them with as few bits as possible. In this paper, we propose an efficient method for encoding the quantized DCT blocks of motion compensated prediction (MCP) errors, which adaptively selects one of a few scanning patterns. The scanning pattern selection of an MCP error block is based on the motion compensated images which are always available at the decoder as well as at the encoder. No overhead information for the scanning patterns needs to be transmitted. Simulation results show that the average bit rate reduction amounts to 5%.
Kazunori ISOMOTO Yoshiyasu MIMASA Shin'ichi WAKABAYASHI Tetsushi KOIDE Noriyoshi YOSHIDA
The graph bisection problem is to partition a given graph into two subgraphs with equal size with minimizing the cutsize. This problem is NP-hard, and hence several heuristic algorithms have been proposed. Among them, the Kernighan-Lin algorithm and the Fiduccia-Mattheyses algorithm are well known, and widely used in practical applications. Since those algorithms are iterative improvement algorithms, in which the current solution is iteratively improved by interchanging a pair of two nodes belonging to different subgraphs, or moving one node from one subgraph to the other, those algorithms tend to fall into a local optimum. In this paper, we present a heuristic algorithm based on subgraph migration to avoid falling into a local optimum. In this algorithm, an initial solution is given, and it is improved by moving a subgraph, which is effective to reduce the cutsize. The algorithm repeats this operation until no further improvement can be achieved. Finally, the balance of the bisection is restored by moving nodes to get a final solution. Experimental results show that the proposed algorithm gets better solutions than the Kernighan-Lin and Fiduccia-Mattheyses algorithms.
Shohei SUGAWARA Gen SUZUKI Yoshio NAGASHIMA Michiaki MATSUURA Hiroya TANIGAWA Machio MORIUCHI
The many-user networked virtual world system InterSpace" is described. This system's main purpose is to enhance the user's communication activities. In InterSpace, the real world information is embedded in the shared virtual world as a combination of video and CG images. Users can ovserve and access this information by simply looking and approaching embedded images. The concept of InterSpace and a prototype system of this service are introduced.
Akio NISHIDA Kazurou HARADA Yoshiyuki ISHIHARA Toshiyuki TODAKA
This paper presents an analysis of the control characteristics of the series resonant converter with a parallel resonant circuit, especially under parallel resonant frequency. Operations of the circuit are classified into several modes. The control characteristics are calculated using the equations derived from equivalent circuits, and are verified by the experiments. From the analysis, the mechanism of a jumping phenomenon in the closed-loop control characteristics is clarified.
Takayuki MORISHITA Iwao TERAMOTO
Processing elements (PEs) with a dynamically reconfigurable pipeline architecture allow the high-speed calculation of widely used neural model which is multi-layer perceptrons with the backpropagation (BP) learning rule. Its architecture that was proposed for a single chip is extended to multiprocessors' structure. Each PE holds an element of the synaptic weight matrix and the input vector. Multi-local buses, a swapping mechanism of the weight matrix and the input vector, and transfer commands between processor elements allow the implementation of neural networks larger than the physical PE array. Estimated peak performance by the measurement of single processor element is 21.2 MCPS in the evaluation phase and 8.0 MCUPS during the learning phase at a clock frequency of 50 MHz. In the model, multi-layer perceptrons with 768 neurons and 131072 synapses are trained by a BP learning rule. It corresponds to 1357 MCPS and 512 MCUPS with 64 processor elements and 32 neurons in each PE.
Akira MATSUZAWA Shoichiro TADA
This paper describes the circuit design and experimental results of a video-rate 10-b analog-to-digital converter (ADC) suitable for consumer video products, such as high-definition TV sets. Triple-stage conversion scheme combined with two new conversion methods, "Dynamic Sliding Reference Method" and "Triangular Interpolation Method," and an internal Bi-CMOS Sample/Hold circuit have been developed. These conversion methods require no adjustment circuit to fit reference voltages between conversion stages and realize small active area. As a result, a maximum conversion frequency of 16 MHz, acceptable SNRs of 56 dB and 48 dB for 10 kHz and 8 MHz input frequency respectively and small DNLE of 0.75 LSB have been achieved. This ADC is fabricated with 1.2 µm Bi-CMOS technology and integrates very small number of bipolar transistors of 2 K on a small active area of 2.52.7 mm2 and consumes 350 mW.
Masahiko TOYONAGA Chie IWASAKI Yoshiaki SAWADA Toshiro AKINO
We present a new multi-layer over-the-cell channel router for standard cell layout design using simulated annealing. This new approach, STANZA-M consists of two key features. The first key feature of our router is a new scheme for simulated annealing in which we use a cost function to evaluate both the total net-length and the channel heights, and an effective simulated annealing process by a limited range to obtain an optimal chnnel wiring in practical time. The second feature of our router is a basic layer assignment procedure in which we assign all horizontal wiring inside a channel to feasible layers by considering the height of channel including cell region with a one dimensional channel compaction process. We implemented our three-layer cannel router in C language on a Solbourne Series 5 Work Station (22 MIPS). Experimental results for benchmarks such as Deutsch's Difficult Example and MCNC's PRIMARY1 channel routing problems indicate that STANZA-M can achieve superior results compared to the conventional routers, and the process times are very fast despite the use of simulated annealing.