Hiroyuki OHNISHI Hiroyuki SEKI Tadao KASAMI
Recognizable series is a model of a sequential machine. A recognizable series S is represented by a triple (λ,µ,γ), called a linear representation of S, where λ is a row vector of dimension n specifying the initial state, γ is a column vector of dimension n specifying the output at a state, and µ is a morphism from input words to nn matrices specifying the state transition. The output for an input word w is defined as λ(µw) γ, called the coefficient of w in S, and written as (S,w). We present an algorithm which constructs a reduced linear representation of an unknown recognizable series S, with coefficients in a commutative field, using coefficient queries and equivalence queries. The answer to a coefficient query, with a word w, is the coefficient (S, w) of w in S. When one asks an equivalence query with a linear representation (λ,µ,γ), if (λ,µ,γ) is a linear representation of S, yes is returned, and otherwise a word c such that λ (µc) γ
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.
Hiroshi MASUYAMA Tetsuo ICHIMORI
In this paper we estimate the number of permutations realizable in fault-tolerant multistage interconnection networks designed to tolerate faults on any switching element. The Parallel Omega network and the INDRA network are representative types of fault-tolerate multistage interconnection networks designed to tolerate a single fault. In order to evaluate the enhancement in the function of network by preparing the hardware redundancy for fault-tolerance, we estimate the number of permutations realizable in fault-tolerant networks. This result enables us to set up a standard to evaluate the hardware redundancy required to tolerate multifaults from the viewpoint of the enhancement of network function. This paper concludes that in the case where the number of inputs is up to 32 the increase ratio of the number of realizable permutations is no more than 1/0.73 even if the tolerance to multifaults is prepared instead of the tolerance to a single fault.
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.
Mineo KANEKO Hiroyuki MIYAUCHI
In this paper, we present Branching Oriented System Equation based on-line error correction scheme for recursive digital signal processing. The target digital signal processing is linear and time-invariant, and the algorithm includes multiplications with constant coefficient, additions and delays. The difficulties of the algorithm-level fault tolerance for such algorithm without structural regularity include error distribution problem and right timing of error correction. To escape the error distribution problem, multiple fan-out nodes in an algorithm are specified as the nodes at which error corrections are performed. The Branching Oriented Graph and Branching Oriented System Equation are so introduced to formulate on-line correction schemes based on this strategy. The Branching Oriented Graph is treated as the collection of computation sub-blocks. Applying checksum code independently to each sub-block is our most trivial on-line error correction scheme, and it results in, with appropriate selection of error identification process, TMR in sub-block level. One of the advantages of our method is in the reduction of redundant operations performed by merging some computation sub-blocks. On the other hand, the schedulability of the system is an important issue for our method since our on-line error correction mechanism induces additional data dependencies. In this paper, the schedulability condition and some modifications on the scheme are also discussed.
Takashi SUEMASU Yoshifumi KOHNO Nobuhiro SUZUKI Masahiro WATANABE Masahiro ASADA
The transistor action with negative differential resistance (NDR) of a nanometer-thick metal (CoSi2)/insulator (CaF2) resonant tunneling transistor is discussed for two transistor structures. These transistors are composed of metal-insulator (M-I) heterostructures with two metallic (CoSi2) quantum wells and three insulator (CaF2) barriers grown on an n-Si (lll) substrate. One of the two structures has the base terminal connected to one of the quantum wells next to the collector, and the other, to one next to the emitter. Although base resistance is high maybe due to the damage caused during the fabrication process, the two transistors show different characteristics, as expected theoretically. Transfer efficiency α (= IC/IE) close to unity was obtained at 77 K for electrons through the resonant levels in M-I heterostructures.
Shu-Hung LEUNG Andrew LUK Sin-Chun NG
The classical supervised learning algorithms for optimizing multi-layered feedforward neural networks, such at the original back-propagation algorithm, suffer from several weaknesses. First, they have the possibility of being trapped at local minima during learning, which may lead to failure in finding the global optimal solution. Second, the convergence rate is typically too slow even if the learning can be achieved. This paper introduces a new learning algorithm which employs a genetic-type search during the learning phase of back-propagation algorithm so that the above problems can be overcome. The basic idea is to evolve the network weights in a controlled manner so as to jump to the regions of smaller mean squared error whenever the back-propagation stops at a local minimum. By this, the local minima can always be escaped and a much faster learning with global optimal solution can be achieved. A mathematical framework on the weight evolution of the new algorithm in also presented in this paper, which gives a careful analysis on the requirements of weight evolution (or perturbation) during learning in order to achieve a better error performance in the weights between different hidden layers. Simulation results on three typical problems including XOR, 3-bit parity and the counting problem are described to illustrate the fast learning behaviour and the global search capability of the new algorithm in improving the performance of back-propagated network.
Kumar and Billinton have presented a new technique for obtaining the steady-state probabilities from a flow graph based on Markov model. By examining the graph and choosing suitable input and output nodes, the steady-state probabilities can be obtained directly by using the flow graph. In this paper this graphical technique is applied for a k-out-of-n: G repairable system. Consequently a new derivation way of the formulae for the steady-state availability and MTBF is obtained.
Yasunori NAGATA Masao MUKAIDONO
In this paper, a fault model for multiple-valued programmable logic arrays (MV-PLAs) is proposed and the equivalences of faults of MV-PLA's are discussed. In a supposed multiple-valued NOR/TSUM PLA model, it is shown that multiple-valued stuck-at faults, multiple-valued bridging faults, multiple-valued threshold shift faults and other some faults in a literal generator circuit are equivalent or subequivalent to a multiple crosspoint fault in the NOR plane or a multiple fault of weights in the TSUM plane. These results lead the fact that multiple-valued test vector set which indicates all multiple crosspoint fault and all multiple fault of weights also detects above equivalent or subequivalent faults in a MV-PLA.
For a complex object model, a form of range restriction called specialization constraint (SC), has been proposed, which is associated not only with the properties themselves but also with property value paths. The domain and range of an SC, however, were limited to single classes. In this paper, SCs are generalized to have sets of classes as their domains and ranges. Let Σ be a set of SCs, where each SC in Σ has a set of classes as its domain and a non-empty set of classes as its range. It is proved that an SC is a logical consequence of Σ if and only if it is a finite logical consequence of Σ. Then a sound and complete axiomatization for SCs is presented. Finally, a polynomial-time algorithm is given, which decides whether or not an SC is a logical consequence of Σ.
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.
A new steepest descent linear adaptive algorithm, called the proportion-sign algorithm (PSA), is introduced and its performance analysis is presented when the signals are from zero-mean jointly stationary Gaussian processes. The PSA improves the convergence speed over the least mean square (LMS) algorithm without overly degrading the steady-state error performance and has the robustness to impulsive interference occurring in the desired response by adding a minimal amount of computational complexity. Computer simulations are presented that show these advantages of the PSA over the LMS algorithm and demonstrate a close match between theoretical and empirical results to verify our analysis.
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.
Gate-controlled negative differential resistance (NDR) due to interband tunneling has been observed at room temperature in a Surface Tunnel Transistor (STT). The STT consists of a highly degenerate p+-drain, an n+-doped channel with an insulated gate, and an n+-source connected to the channel. To demonstrate application as a functional device, a bistable circuit consisting of only one STT and one load resistor was organized and its operation was confirmed. The obtained valley current in the NDR characteristics of the STT, however, is relatively large and limits the device performance. In order to clarify the origin of the valley current, we fabricated p+-n+ tunnel diodes in which growth interruption was done at the pn junction, and investigated the dependence of the NDR characteristics on both the impurity concentration at the regrown interface and the temperature. These measurements indicate that the valley current is mainly caused by the excess tunneling current through traps formed by the residual oxygen at the regrown interface.
Carlos J. PANTALEÓN-PRIETO Aníbal R. FIGUEIRAS-VIDAL
In this paper we introduce the Piecewise Linear Radial Basis Function Model (PWL-RBFM), a new nonlinear model that uses the well known RBF framework to build a PWL functional approximation by combining an l1 norm with a linear RBF function. A smooth generalization of the PWL-RBF is proposed: it is obtained by substituting the modulus function with the logistic function. These models are applied to several time series prediction tasks.
Kiyoshi NISHIKAWA Hitoshi KIYA
A new gradient type adaptive algorithm is proposed in this paper. It is formulated based on the least squares criteria while the conventional gradient algorithms are based on the least mean square criteria. The proposed algorithm has two variable parameters and by changing them we can adjust the characteristic of the algorithm from the RLS to the LMS depending on the environment. This capability of adjustment achieves the possibility of providing better solutions. However, not only it provides better solutions than the conventional algorithms under some conditions but also it provides a very interesting theoretical view point. It provides a unified view point of the adaptive algorithms including the conventional ones, i.e., the LMS or the RLS, as limited cases and it enables us to analyze the bounds for those algorithms.
Takashi SEKIGUCHI Tetsuo KIRIMOTO
We present a method of extracting the digital inphase (I) and quadrature (Q) components from oversampled bandpass signals using narrow-band bandpass Hilbert transformers. Down-conversion of the digitized IF signals to baseband and reduction of the quantization noise are accomplished by the multistage decimator with the complex coefficient bandpass digital filters (BPFs), which construct the bandpass Hilbert transformers. Most of the complex coefficient BPFs in the multistage decimator can be replaced with the lowpass filters (LPFs) under some conditions, which reduces computational burden. We evaluate the signal to quantization noise ratio of the I and Q components for the sinusoidal input by computer simulation. Simulation results show that the equivalent amplitude resolution of the I and Q components can be increased by 3 bits in comparison with non-oversampling case.
Todor COOKLEV Akinori NISHIHARA
The relation between computing part of the FFT spectrum and the so-called generalized FFT (GFFT) is clarified, leading to a new algorithm for performing partial FFTs. The method can be applied when only part of the output is required or when the input data sequence contains many zeros. Such cases arize for example in decimation and interpolation and also in computing linear convolutions. The technique consists of decomposing the DFT into several generalized DFTs. Efficient algorithms for these generalized DFTs exist. The computational complexity of the new approach is roughly equal to the complexity of previous techniques, but the structure is superior, because only one type of butterfly is used and a few lines of code are sufficient. The theoretical properties of the GDFT are given. The case of multidimensional signals, defined on arbitrary sampling lattices is also considered.
Takashi WATANABE Hitoshi SUZUKI Sumio TANBA Ryuzo YOKOYAMA
Contextual classification of multispectral image data in remote sensing is discussed and concretely two improved contextual classifiers are proposed. The first is the extended adaptive classifier which partitions an image successively into homogeneously distributed square regions and applies a collective classification decision to each region. The second is the accelerated probabilistic relaxation which updates a classification result fast by adopting a pixelwise stopping rule. The evaluation experiment with a pseudo LANDSAT multispectral image shows that the proposed methods give higher classification accuracies than the compound decision method known as a standard contextual classifier.
Iulian B. PETRESCU-PRAHOVA Manuela BUDA Theo G. van de ROER
A design of a high power laser structure is presented which is based on an increase of the cavity length as well as a maximization of the stripe width. This requires a low value for the modal attenuation coefficent and a low optical confinement factor. A model is presented from which the modal gain, the confinement factor, the active region thickness, the stripe width, the length and the reflection coefficients can be calculated. A variant for all design parameters needed to reach 1 W emission in the fundamental lateral mode is given. These values are used to design the epitaxial structure.