Adam Icarus IMORO Yoshihisa KANI Naoki INAGAKI Nobuyoshi KIKUMA
The valid region for the application of the conventional Improved Circuit Theory (ICT) in the analysis of wire antennas is established. To further extend the application of ICT to the analysis of much longer antennas, Tai's trial function is used to derive new formulas for the impedance matrix. Unlike the conventional ICT trial function, Tai's trial functions lead to input impedances which are finite irrespective of antenna length. Results of the new ICT impedance formulas are comparable in accuracy with the general method of moments. Moreover, since all the elements of the new formula have been expressed in closed-form, the resulting ICT algorithm is still superior in terms of computer running time with lesser storage requirement compared to other conventional methods like method of moments. This would enhance ICT applications in CAD/CAE systems.
Toshinori YAMASAKI Tetsuo HATTORI
We developed the computer calligraphy, that is, a computer formation of brush-written Kanji characters using calligraphic knowledge. The style of brush handwriting depends mainly on the way of using a writing brush. Brush writing skills include the direction of brush at the beginning, curvature and turning the brush, the brush-up at the termination point in a stroke. We make up the calligraphic knowledge base according to the above mentioned brush writing skills. For simulating real brush movement, we represent the brush contact form that is the brush shape on the writing plane as a brush-touch. The system can control the size and direction of this brush-touch during the brush simulation. The system simulates the real brush writing to move the brush-touch along the skeleton letter shape in the standard database. We get the brush written Kanji from the locus of the brush-touch movement. We can extend this system to the new on line training system for brush writing using the simulation of brushtouch movement modified by the pressure, speed and rotation of the writing brush, and the skeleton letters written by a learner from the tablet. This system is also useful for students learning how to write Japanese letters beautifully with brush.
Hironari NOZAKI Yukuo ISOMOTO Katsumi YOSHINE Naohiro ISHII
This paper proposes the concept of information retrieval for fine arts database system on the fuzzy set theory, especially concerning to sensitive impression and location data. The authors have already reported several important formulations about the data structure and information retrieval models based on the fuzzy set theory for multimedia database. The fuzzy models of the information retrieval are implemented in the fine arts database system, which has the following features: (1) The procedure of information retrieval is formulated in the fuzzy set theory; (2) This database can treat multimedia data such as document data, sensitive impression, location information, and imagedata. (3) It is possible to retrieve the stored data based on sensitive impression and the location data such as "joyful pictures which have a mountain in the center and there is a tree in the right"; (4) Users can input impression words as a retrieval condition, and estimate their grades such as "low," "medium," and "high"; (5) For the result of information retrieval, the satisfaction grade is calculated based on fuzzy retrieval model; and (6) The stored data are about 400 fine arts paintings which are inserted by the textbook of fine arts currently used at the junior high school and high school in Japan. These features of this system give an effects of the fine arts education, and should be useful for information retrieval of fine arts. The results of this study will become increasingly important in connection with development of multimedia technology.
Komain PIBULYAROJANA Shigetomo KIMURA Yoshihiko EBIHARA
Banyan networks are used in multiprocessor computer applications for an ATM switching. In this paper, we study the continuous blocking of the first n-stage which makes the performance of the banyan networks decrease. We use the 2-dilated banyan networks into the banyan networks to remove the continuous blocking of the first n-stage. We call the new networks as the hybrid dilated banyan networks. We explain how to analyze the throughput of this networks at each stage. Based on the analysis of input rate and output rate at each stage, we can design the hybrid dilated banyan networks with the desirable output rate. The result of analysis shows the hybrid dilated banyan networks have higher performance and feasibility than the banyan networks.
Yukuo HAYASHIDA Manabu IKEGAMI Nobuyuki SUGIMACHI
The DQDB MAC Protocol standardized by the IEEE 802.6 Committee is a single segment bandwidth reservation scheme that only reserves bandwidth for one segment in the distributed queue. Recently, multi-segment bandwidth reservation schemes that reserve bandwidth for not only one segment in the distributed queue but also a part of or all segments in the local node queue have been proposed. In this paper, we propose a new multi-segment bandwidth reservation protocol that can quickly react to changes in a node's traffic and can quickly allocate the bandwidth fairly and waste-free. We also evaluate the mean message transmission delay and throughput convergence performance by simulation. As a result, it is shown that the mean message transmission delay can be decreased and the throughput can be quickly converged to fair bandwidth allocation.
Jianliang XU Katsushi INOUE Yue WANG Akira ITO
This paper investigates the accepting powers of multi-inkdot two-way alternating pushdown automata (Turing machines) with sublogarithmic space and constant leaf-size. For each k1, and each m0, let weak-ASPACEm [L(n),k] denote the class of languages accepted by simultaneously weakly L(n) space-bounded and k leaf-bounded m-inkdot two-way alternating Turing machines, and let strong-2APDAm[L(n),k] denote the class of languages accepted by simultaneously strongly L(n) space-bounded and k leaf-bounded m-inkdot two-way alternating pushdown automata. We show that(1) strong-2APDAm [log log n,k+1]weak-ASPACEm[o(log n),k]φfor each k1 and each m1, and(2) strong-2APDA(m+1) [log log n,k]weak-ASPACEm[o(log n),k]φfor each k1 and each m0.
Shao-Chin SUNG Tetsuro NISHINO
In this paper, we show that a parity function with n variables can be computed by a threshold circuit of depth O((log n)/c) and size O((2clog n)/c), for all 1c [log(n+1)]-1. From this construction, we obtain an O(log n/log log n) upper bound for the depth of polylogarithmic size threshold circuits for parity functions. By using the result of Impagliazzo, Paturi and Saks[5], we also show an Ω (log n/log log n) lower bound for the depth of the threshold circuits. This is an answer to the open question posed in [11].
Masayoshi NAKAYAMA Manabu NAKAGAWA Youichi HASHIMOTO Kazunori TANAKA Hiroshi NAKASHIMA
Recently, computer communications, especially Internet services, have become popular and as a result, high-speed network access circuits are now desired. NTT has developed an economical and high-speed multimedia computer network, combining satellite and terrestrial circuits. The satellite circuit transmission rate is approximately 30-Mbit/s. To select IP packets from such high-speed satellite circuits, this system employs the asynchronous transfer mode (ATM) in the satellite section and we have developed a new economical satellite circuit receive adapter (SRA) for the satellite section. This paper describes the system configurations and the key network control technologies for multi-link routing, high speed processing and broadcasting.
Shinichiro YAMAGUCHI Tetsuaki NAKAMIKAWA Naoto MIYAZAKI Yuuichirou MORITA Yoshihiro MIYAZAKI Sakou ISHIKAWA
The fault tolerant computer (FTC) is applied as a communication or database server in the information service and computer aided process control fields. User requires of the FTC are to provide the current level of performance and software transparency needing no additional dedicated program for fault tolerance. To meet these requirements, we propose quadprocessor redundancy (QPR) architecture that combines dualRISC based duplicated CPUs integrating main memories, and duplicated I/O subsystems by using some additional hardware. Duplicated CPUs run under the instruction level synchronization (lock step operation) , and the duplicated I/O subsystems are managed by an operating system. When a fault is detected, the faulty CPU is isolated by hardware. User program is continuously executed by the remaining CPU. We applied the QPR to our UNIX servers, and achieved satisfactory levels of performance.
Minoru YAMADA Atsushi KANAMORI Seiryu TAKAYAMA
Mechanism of the noise generation caused by the optical feedback in semiconductor laser was experimentally determined. Two types of the mode competition phenomena were confirmed to be the generating mechanisms. Applicability of the self-sustained pulsation to be a noise reduction method was also discussed.
Hiraku OKADA Masato SAITO Takeshi SATO Takaya YAMAZATO Masaaki KATAYAMA Akira OGAWA
The one of the problems in the satellite packet communication system is the existence of a long time delay, which may cause an improper packet access control resulting in a great deal of degradation of the system performance. In this paper, we clarify the effect of long time delay on the performance of CDMA ALOHA systems and then propose a new access control protocol, called Modified Channel Load Sensing Protocol (MCLSP), for the CDMA ALOHA systems. As a result, we show that a significant improvement in the throughput performance was obtained with MCLSP even in the presence of a long time delay.
Discussed here is reduction of power dissipation for multi-media LSIs. First, both active power dissipation Pat and stand-by power dissipation Pst for both CMOS LSIs and GaAs LSIs are summarized. Then, general technologies for reducing Pat are discussed. Also reviewed are a wide variety of approaches (i.e., parallel and pipeline schemes, Chen's fast DCT algorithms, hierarchical search scheme for motion vectors, etc.) for reduction of Pat. The last part of the paper focuses on reduction of Pst. Reducing both Pat and Pst requires that both throughput and active chip areas be either maintained or improved.
Cheol-Hee LEE Jae-Yoon SIM Hong-June PARK
A current controlled CMOS output driver was designed by using a temperature-insensitive reference current generator. It eliminates the need for overdesign of the driver transistor size to meet the delay specification at high temperature. Comparison with the conventional CMOS output driver with the same transistor size showed that the ground bounce noise was reduced by 2.5 times and the delay time was increased by 1.4 times, at 25 for 50pF load. The temperature variations of the DC pull-up and pull-down currents of the new output driver were 4% within the temperature range from -15 to 125 compared to the variations of 40 and 60% for pull-up and pull-down respectively for the conventional output driver. The temperature insensitivity of the reference current generator was achieved by multiplying two current components. one which is proportional to mobility and the other which is inversely proportional to mobility, by using a CMOS square root circuit. The temperature variation of the DC output current of the reference current generator alone was 0.77% within the entire temperature range from -15 to 125.
In this paper, we consider the protein structure alignment problem, which is a very important problem in molecular biology. Since an outline of protein structure is represented by a sequence of points in three-dimensional space, this problem is defined as the following geometric pattern matching problem: given two point sequences P and Q in three-dimensions and a real number δ > 0, find a maximum-cardinality set of point pairs such that the distance between each pair is at most δ under the condition that any translation and rotation can be applied to P. Since it is very difficult to solve this problem exactly, we consider algorithms that solve it approximately. We propose three algorithms: BASICALIGN, RANDALIGN and FRAGALIGN whose worst case time complexities are O(n8), O((n7/k3) polylog(n)) and O(n4) respectively, where n denotes the size of larger input structure and k denotes the minimum size of the alignment to be obtained. All of these have the following common framework: a series of initial superpositions are computed; for each of such superpositions, a rough alignment is first computed using a dynamic programming technique, and then it is refined through an iterative improvement procedure which also uses dynamic programming; the best alignment among them is selected as an output. The difference among three algorithms lies in the methods of finding initial superpositions. BASICALIGN, RANDALIGN and FRAGALIGN use exhaustive search, random sampling technique and fragment-based search, respectively. We prove guaranteed approximation ratios (in the sense of distances between point pairs) for theoretical versions of BASICALIGN and RANDALIGN. Practical versions of RANDALIGN and FRAGALIGN were implemented and compared with a previous algorithm using real protein structure data. The experimental results show that FRAGALIGN is best among them and it outputs good alignments quickly.
Yue WANG Katsushi INOUE Akira ITO
In [2] Ibarra introduced a restricted version of one-way multihead pushdown automaton (PDA), called a simple one-way multihead PDA, and showed that such machines recognize only languages with semilinear property. The main result of this paper is that for each k 1, simple (sensing) one-way (k + 1)-head PDA's are more powerful than simple (sensing) one-way k-head PDA's. This paper also investigates closure properties for simple (sensing) one-way multihead PDA's
Kenjiroh YAMANAKA Seiichi KOMURA June KATO Haruhisa ICHIKAWA
This paper proposes a method for deriving protocol specifications in a communicating processes model, in which protocol specifications are modeled by finite automata communicating through the LOTOS multirendezvous mechanism. Message sequence charts (MSCs) are used for the derivation inputs. MSCs are graphical representations of traces of protocols and are suitable for defining requirements. Since an MSC usually covers only partial behavior, several mechanisms for composing a large number of MSCs from element MSCs have been proposed. These mechanisms, however, are not adequate: Either their input language for MSCs is not powerful enough, or they need some information on protocol specifications (i.e., implementation specifications). This paper proposes the use of regular expressions over MSCs to fully define protocols. The proposed language is powerful enough to describe protocols in the communicating processes model. A derivation algorithm based on a finite automata construction algorithm that accept sets expressed by regular expressions is presented. Because the derived protocols sometimes include unrequired behavior, an algorithm for detecting unrequired behavior is also presented.
Isao NAKANISHI Yoshio ITOH Yutaka FUKUI
For reduction of computational complexity in the IA algorithm, the thinned-out IA algorithm in which only one step size is updated every iteration is proposed and is complementarily switched with the HA algorithm according to the convergence. The switching is determined by using the gradient of the error signal power. These are investigated through the computer simulations.
Analog computation is a processing method that solves problems utilizing an analogy of a physical system to the problem. As it is based on actual physical effects and not on symbolic operations, it is therefore a promising architecture for quantum processors. This paper presents an idea for relating quantum structures with analog computation. As an instance, a method is proposed for solving an NP-complete (nondeterminis-tic polynomial time complete) problem, the three-color-map problem, by using a quantum-cell circuit. The computing process is parallel and instantaneous, so making it possible to obtain the solution in a short time regardless of the size of the problem.
Most of the existing analytical models for multistage ATM switching fabric are not accurate in the presence of a non-uniform traffic at the input of the switch. In this paper, we discuss the issues in modeling a multistage ATM switching fabric, and investigate the effect of independence assumptions in two previous analytical models. A highly accurate 4-state Markov chain model for evaluating the performance of ATM switching fabrics based on multistage switches with 22 finite output-buffered SEs is proposed. The proposed model correctly reflects the correlation of cell movements between two subsequent cycles and states of the buffers of two adjacent stages. By comparing the results obtained from the oroposed model, existing models and simulations, it has been shown that the proposed model is much more accurate than existing models in the presence of a non-uniform traffic in the switch. The results from the existing models are unsatisfactory in the presence of an increased blocking in the switch arising from a non-uniform traffic in the switch. On the contrary, the proposed model is very robust even under severe blocking in the switch.
Akira TAKAHASHI Ikuo ISHII Hideo MAKINO Makoto NAKASHIZUKA
In this paper, we propose a camera calibration method that estimates both intrinsic parameters (perspective and distortion) and extrinsic parameters (rotational and translational). All camera parameters can be determined from one or more images of planar pattern consists of parallelogramatic grid points. As far as the pattern can be visible, the relative relations between camera and patterns are arbitrary. So, we have only to prepare a pattern, and take one or more images changing the relative relation between camera and the pattern, arbitrarily; neither solid object of ground truth nor precise z-stage are required. Moreover, constraint conditions that are imposed on rotational parameters are explicitly satisfied; no intermediate parameter that connected several actual camera parameters are used. Taking account of the conflicting fact that the amount of distortion is small in the neighborhood of the image center, and that small image has poor clues of 3-D information, we adopt iterative procedure. The best parameters are searched changing the size and number of parallelograms selected from grid points. The procedure of the iteration is as follows: The perspective parameters are estimated from the shape of parallelogram by nonlinear optimizations. The rotational parameters are calculated from the shape of parallelogram. The translational parameters are estimated from the size of parallelogram by least squares method. Then, the distortion parameters are estimated using all grid points by least squares method. The computer simulation demonstrates the efficiency of the proposed method. And the results of the implementation using real images are also shown.