State space explosion is a serious problem in analyzing discrete event systems that allow concurrent occurring of events. A new method is proposed for generating reduced state spaces of systems. This method is an improvement of Valmari's stubborn set method. The generated state space preserves liveness, livelocks, and terminal states of the ordinary state space. Petri nets are used as a model of systems, and a method is shown for generating a reduced state space from a given Petri net.
Zhuan-Ke CHEN Keisuke ARAI Koichiro SAWA
The former experimental results have already shown that it is oxide films formed on contact surface causing the contact resistance to degrade in dc. breaking arcs for Ag and Pd materials. In order to understand the detailed information about it, the experiments are performed to break dc. inductive load at 20 V, 0.5 A and 1.0 A in nitrogen gas with different oxygen concentrations. The contact surface morphology and surface contamination are evaluated by SEM and AES, respectively. The tested results demonstrate that, for Ag contact, the severe oxidation occurs with increasing oxygen concentration, and the critical value of oxygen concentration is found to be about 10% and 5% in 0.5 A and 1.0 A, respectively, above those values the contact resistance degrades due to the oxide films formed on the contact surface, especially on the anode surface. While, for Pd contacts, a remarkable contact resistance degradation is not found even at 1.0 A in oxigen. Evidence shows that the arc duration, in particular the gaseous phase arc duration affects the anode oxidation, which in turn causes the significant fluctuation of contact resistance.
Supot TIARAWUT Tadao SAITO Hitoshi AIDA
It is desirable to design an ATM switch that is nonblocking at the connection level by using simple connection admission control (CAC) schemes. To accomplish this goal, it is necessary to consider the relationships between CAC, cell-level quality-of-services (QOS), and the structure of multistage switches as well as switch modules. In this paper, we formulate a framework to design a multistage nonblocking ATM switch. We show that if a switch has the property of the Sufficiency of Knowledge of External Loads (SKEL), i.e., the property that its cell-level performance is robust to the distribution of incoming traffic among all inputs, then the switch is also nonblocking at the connection-level by using a simplified CAC that guarantees QOS of a connection by controlling the aggregate loads on outputs. Furthermore, we show that a Clos three-stage network using SKEL switch modules and Multipath Self-Routing (MPSR) also has the SKEL property and is a nonblocking switching network that needs CAC only at its outputs. We also demonstrate a design of multistage nonblocking ATM switches with Knockout switch modules.
Takumi NITTONO Koichi NAGATA Yoshiki YAMAUCHI Takashi MAKIMURA Hiroshi ITO Osaake NAKAJIMA
This paper describes small AlGaAs/GaAs HBT's for low-power and high-speed integrated circuits. The device fabrication is based on a new bridged base electrode technology that permits emitter width to be defined down to 1 µm. The new technology features oxygen-ion implantation for emitter-base junction isolation and zinc diffusion for extrinsic base formation. The oxygen-ion implanted emitter-base junction edge has been shown to provide a periphery recombination current much lower than that for the previous proton implanted edgs, the result being a much higher current gain particularly in small devices. The zinc diffusion offers high device yield and good uniformity in device characteristics even for a very thin (0.04 µm) base structure. An HBT with emitter dimensions of 12.4 µm2 yields an fT of 103 GHz and an fmax of 62 GHz, demonstrating that the new technology has a significant advantage in reducing the parasitic elements of small devices. Fabricated one-by-eight static frequency dividers and one-by-four/one-by-five two-modulus prescalers operate at frequencies over 10 GHz. The emitters of HBT's used in the divider are 12.4 µm2 in size, which is the smallest ever reported for AlGaAs/GaAs HBT IC's. These results indicate that the bridged base electrode technology is promising for developing a variety of high-speed HBT IC's.
Manabu YOSHIKAWA Kazuyuki KAMEDA
Mode separation of a multiplex mode in a mode-division multiplexing system is studied. The clear, desired single-mode pattern, which is separated from the multiplex mode by using a holographic filter, is observed in the experiment.
In this paper, we first discuss on a framework for a 3D image display system which is the combination of passive sensing and active display technologies. The passive sensing enables to capture real scenes under natural condition. The active display enables to present arbitrary views with proper motion parallax following the observer's motion. The requirements of passive sensing technology for 3D image displays are discussed in comparison with those for robot vision. Then, a new stereo algorithm, called SEA (Stereo by Eye Array), which satisfies the requirements is described in detail. The SEA uses nine images captured by a 33 camera array. It has the following features for depth estimation: 1) Pixel-based correspondence search enables to obtain a dense and high-spatial-resolution depth map. 2) Correspondence ambiguity for linear edges with the orientation parallel to a particular baseline is eliminated by using multiple baselines with different orientations. 3) Occlusion can be easily detected and an occlusion-free depth map with sharp object boundaries is generated. The feasibility of the SEA is demonstrated by experiments by using real image data.
Seiichiro DAN Toshiyasu NAKAO Tadahiro KITAHASHI
We can understand and recover a scene even from a picture or a line drawing. A number of methods have been developed for solving this problem. They have scarcely aimed to deal with scenes of multiple objects although they have ability to recognize three-dimensional shapes of every object. In this paper, challenging to solve this problem, we describe a method for deciding configurations of multiple objects. This method employs the assumption of coplanarity and the constraint of occlusion. The assumption of coplanarity generates the candidates of configurations of multiple objects and the constraint of occlusion prunes impossible configurations. By combining this method with a method of shape recovery for individual objects, we have implemented a system acquirig a three-dimensional information of scene including multiple objects from a monocular image.
Ee-Taek LEE Young-Kyu CHOI Kyu Ho PARK
This paper addresses a method for constructing surface representation of 3D structures from a sequence of cross-sectional images. Firstly, we propose cell-boundary representation, which is a generalization of PVP method proposed by Yun and Park, and develop an efficient surface construction algorithm from a cell-boundary. Cell-boundary consists of a set of boundary cells with their 1-voxel configurations, and can compactly describe binary volumetric data. Secondly, to produce external surface from the cell-boundary representation, we define 19 modeling primitives (MP) including volumetric, planar and linear groups. Surface polygons are created from those modeling primitives using a simple table look-up operation. Since a cell-boundary can be obtained using only topological information of neighboring voxels, there is no ambiguity in determining modeling primitives which may arise in PVP method. Since our algorithm has data locality and is very simple to implement, it is very appropriate for parallel processing.
A Wavelength Division Multiaccess (WDMA) network with buffer sharing among stations is studied. All stations in the network are connected to a passive optical star coupler and each station has a different fixed wavelength laser for transmitting packets. Each station in the network reports its packet backlog to a scheduler which computes and then broadcasts a transmission schedule to all the stations through a control channel in each time slot. A transmission schedule includes two types of assignments: 1) assign a maximum number of stations for conflict-free transmissions, and 2) assign the relocation of packets from congested stations to uncongested relaying stations through idling transceivers for distributed buffer sharing. The first assignment aims at maximizing throughput and the second assignment aims at minimizing packet loss. Simulation results show that as much as 75% of the buffers can be saved with the use of buffer sharing when 50% of the packets are of the non-sequenced type.
Toshiyuki YOSHIDA Akinori NISHIHARA Nobuo FUJII
This paper discusses a new design method for 2-D variable FIR digital filters, which is an extension of our previous work for 1-D case. The method uses a 3-D prototype FIR filter whose cross-sections correspond to the desired characteristics of 2-D variable FIR filters. A 2-D variable-angle FIR fan filter is given as a design example.
Yukuo HAYASHIDA Masaharu KOMATSU
Go-Back-N automatic repeat request (GBN ARQ) and Stop-and wait (SW) ARQ schemes are one of fundamental and widely used error control procedures for data communication and computer communication systems. The throughput and delay performances of these ARQ schemes have been analyzed for a random error channel, which could not applicable for a radio channel, for example. In this paper, considering the correlated, noisy channel, we derive the exact formula for the delay of a frame in GBN and SW ARQ schemes. First, the delay formula for the discrete time M[x]/G/1 queueing system with starter. Next, the virtual service time of a frame is found in terms of the decay factor of a two-state Markov chain. As a result, it is shown that the performance of the delay is improved with the larger decay factor.
Mamoru TANAKA Kenneth R. CROUNSE Tamás ROSKA
This paper describes highly parallel analog image coding and decoding by cellular neural networks (CNNs). The communication system in which the coder (C-) and decoder (D-) CNNs are embedded consists of a differential transmitter with an internal receiver model in the feedback loop. The C-CNN encodes the image through two cascaded techniques: structural compression and halftoning. The D-CNN decodes the received data through a reconstruction process, which includes a dynamic current distribution, so that the original input to the C-CNN can be recognized. The halftoning serves as a dynamic quantization to convert each pixel to a binary value depending on the neighboring values. We approach halftoning by the minimization of error energy between the original gray image and reconstructed halftone image, and the structural compression from the viewpoints of topological and regularization theories. All dynamics are described by CNN state equations. Both the proposed coding and decoding algorithms use only local image information in a space inveriant manner, therefore errors are distributed evenly and will not introduce the blocking effects found in DCT-based coding methods. In the future, the use of parallel inputs from on-chip photodetectors would allow direct dynamic quantization and compression of image sequences without the use of multiple bit analog-to-digital converters. To validate our theory, a simulation has been performed by using the relaxation method on an 150 frame image sequence. Each input image was 256256 pixels whth 8 bits per pixel. The simulated fixed compression rate, not including the Huffman coding, was about 1/16 with a PSNR of 31[dB]35[dB].
Naohiko SHIMIZU Gui-Xin CHENG Munemitsu IKEGAMI Yoshinori NAKAMURA Mamoru TANAKA
This paper describes a pipelining universal system of discrete time cellular neural networks (DTCNNs). The new relaxation-based algorithm which is called a Pipelining Gauss Seidel (PGS) method is used to solve the CNN state equations in pipelining. In the systolic system of N processor elements {PEi}, each PEi performs the convolusional computation (CC) of all cells and the preceding PEi-1 performs the CC of all cells taking precedence over it by the precedence interval number p. The expected maximum number of PE's for the speeding up is given by n/p where n means the number of cells. For its application, the encoding and decoding process of moving images is simulated.
Noboru NAKASAKO Mitsuo OHTA Hitoshi OGAWA
A specific signal in most of actual environmental systems fluctuates complicatedly in a non-Gaussian distribution form, owing to various kinds of factors. The nonlinearity of the system makes it more difficult to evaluate the objective system from the viewpoint of internal physical mechanism. Furthermore, it is very often that the reliable observation value can be obtained only within a definite domain of fluctuating amplitude, because many of measuring equipment have their proper dynamic range and the original random wave form is unreliable at the end of amplitude fluctuation. It becomes very important to establish a new signal processing or an evaluation method applicable to such an actually complicated system even from a functional viewpoint. This paper describes a new trial for the signal processing along the same line of the extended regression analysis based on the Bayes' theorem. This method enables us to estimate the response probability property of a complicated system in an actual situation, when observation values of the output response are saturated due to the dynamic range of measuring equipment. This method utilizes the series expansion form of the Bayes' theorem, which is applicable to the non-Gaussian property of the fluctuations and various kinds of correlation information between the input and output fluctuations. The proposed method is newly derived especially by paying our attention to the statistical information of the input-output data without the saturation operation instead of that on the resultantly saturated observation, differing from the well-known regression analysis and its improvement. Then, the output probability distribution for another kind of input is predicted by using the estimated regression relationship. Finally, the effectiveness of the proposed method is experimentally confirmed too by applying it to the actual data observed for indoor and outdoor sound environments.
Hirokazu TANAKA Tomoto K. MATSUSHIMA
In this paper, trellis coded modulation with bandwidth expansion is examined. The proposed scheme is a modified Symbol-rate-increased TCM [3]-[5], which allows the bandwidth expansion ratio to be varied to an arbitrary value. The Symbol-rate-increased TCM has been shown to be a particular case of the proposed scheme. Simulation results have clarified that the proposed scheme achieves a significant improvement over an uncoded scheme in an AWGN channel.
We compare interfaces of Nb/AlOx-Al/Nb and Nb/ZrOx-Zr/Nb junctions using secondary ion mass spectroscopy and cross-sectional transmission electron microscopy. We have clarified that an interface of the Nb/AlOx-Al/Nb junction is drastically different from that of the Nb/ZrOxZr/Nb junction. An adsorbed water vapor layer plays an important role in suppressing grain boundary diffusion between Nb and Al at the interface of the Nb/AlOxAl/Nb junction. In depositing Nb and Al at low power and cooling the substrate, it is important to control the formation of the adsorbed water vapor layer for fabricating Nb/AlOx-Al/Nb junctions exhibiting excellent current-voltage characteristics.
Seishi SASAKI Ichiro MATSUMOTO Osamu WATANABE Kenzo URABE
Personal Handy Phone (PHP), the Japanese digital cordless telephone system is being developed. The 32kbits/s ADPCM (Adaptive Differential Pulse Code Modulation) codec has been standardized for PHP. This paper describes firstly, the advanced algorithms of a Voice Activity Detection (VAD) function that reduces power dissipation of a digital cordless telephone terminal, secondly, a comfort noise generator operates in conjunction with the VAD and finally, a transmission error control based on the use of the prediction coefficients generated in the ADPCM codec. These proposed algorithms function in the low signal-to-noise ratio (SNR) environment of personal radio communications. The quality of the reconstructed speech after the process is influenced by the VAD decision errors (false detection when no voice is present, or no detection when voice is present) , the similarity of the generated comfort noise to the actual background noise, and the transmission quality. The simulation results of the performance achieved by these algorithms are shown and required loading of the computation are also given.
Luigi RAFFO Silvio P. SABATINI Giacomo INDIVERI Giovanni NATERI Giacomo M. BISIO
The paper describes the architecture and the simulated performances of a memory-based chip that emulates human cortical processing in early visual tasks, such as texture segregation. The featural elements present in an image are extracted by a convolution block and subsequently processed by the cortical chip, whose neurons, organized into three layers, gain relational descriptions (intelligent processing) through recurrent inhibitory/excitatory interactions between both inter-and intra-layer parallel pathways. The digital implementation of this architecuture directly maps the set of equations determining the status of the cortical network to achieve an optimal exploitation of VLSI technology in neural computation. Neurons are mapped into a memory matrix whose elements are updated through a programmable computational unit that implements synaptic interconnections. By using 0.5 µm-CMOS technology, full cortical image processing can be attained on a single chip (2020 mm2 die) at a rate higher than 70 frames/second, for images of 256256 pixels.
Kiyoshi KOBAYASHI Tomoaki KUMAGAI Shuzo KATO
This paper proposes a group demodulator that employs multi-symbol chirp Fourier transform to demodulate pulse shaped and time asynchronous signals without degradation; this is not possible with conventional group demodulators based on chirp Fourier transform. Computer simulation results show that the bit error rate degradation of the proposed group demodulator at BER=10-3 is less than 0.3dB even when a root Nyquist (α=0.5) filter is used as the transmission pulse shaping filter and the symbol timing offset between the desired channel and the chirp sweep is half the symbol period.
This paper presents a new line extraction method to capture vectors based on contours and skeletons from line drawing raster images in which the lines are touched by characters or other lines. Conventionally, two line extraction methods have generally been used. One is a thinning method. The other is a medial line extraction method based on parallel pairs of contours. The thinning method tends to distort the extracted lines, especially at intersections and corners. On the other hand, the medial line extraction method has a poor capability as regards capturing correct lines at intersections. Contours are able to maintain edge shapes well, while skeletons preserve topological features; thus, a combination of these features effectively leads to the best fitting line. In the proposed method, the line which best fits the original image is selected from among various candidate lines. The candidates are created from several merged short skeleton fragments located between pairs of short contour fragments. The method is also extended to circular arc fitting. Experimental results show that the proposed line fitting method is effective.