Seongbae EUN Seung Ryoul MAENG Jung Wan CHO
The integration of both real-time systems and fault-tolerant systems has been emerged as one of the greatest challenges of this decade. It is called a responsive system, which has the objective to optimeze both timeliness and reliability. The performance measure in responsive systems is responsiveness that tells how probable a system executes correctly on time with faults occurred. While there have been some achievements in communication protocols and specification, we believe that scheduling problems in responsive systems are not understood deeply and sufficiently, yet. In this paper, we discuss the scheduling problem in responsive systems. At first, we investigate the issues in the scheduling and propose the precise definition of the responsiveness. We also suggest a scheduling algorithm called Responsive Earliest Deadline First (REDF) for preemptive aperiodic tasks in a uniprocessor system. We show that REDF is optimal to obtain the maximum responsiveness, and the time complexity is analyzed to be
Klaus-Robert MÜLLER Jens KOHLMORGEN Klaus PAWELZIK
We present a framework for the unsupervised segmentation of time series. It applies to non-stationary signals originating from different dynamical systems which alternate in time, a phenomenon which appears in many natural systems. In our approach, predictors compete for data points of a given time series. We combine competition and evolutionary inertia to a learning rule. Under this learning rule the system evolves such that the predictors, which finally survive, unambiguously identify the underlying processes. The segmentation achieved by this method is very precise and transients are included, a fact, which makes our approach promising for future applications.
Ryuichi MATSUKURA Motomitsu ADACHI Soichi OKADA Kyoko KAMIKURA Yasuhide MATSUMOTO Tsuneo KATSUYAMA
Information capture is a very desirable and important function in portable computers. The "Multimedia Notebook" is a portable tool for capturing information in multimedia format, which includes photos, voice, and handwritten memos. Recent portable units, sometimes called PDA (Personal Digital Assistants) or Communicators, have PIM (Personal Information Manager) software and some communication facility. Their purpose is to enlarge the desktop environment to follow the user outside the office. This is one application of portable equipment, however we felt that hand-held equipment can also be used for more general information capture. In the past, information capture was limited, because people had to carry bulky equipment to the information source. Recent portable computers that have the capability to handle still and motion pictures, voice, and handwritten drawings allow the implementation of more information capture capabilities. Capture of handwritten notes has already been implemented on portable equipment like PDAs. However, this application doesn't make the most of its potential. We feel that the Multimedia Notebook should integrate handwritten memos with pictures and voice. The advantage is that users can capture what they watch and hear easily in a variety of media for later review. The information in each medium complements the others. When arranging the recorded information, it is easy to use each medium efficiently. We have examined the human interface and designed it for user-friendliness and to be comparable to pen and paper. The prototypes also have a capture buffer which can operate continuously to capture voice and pictures that would otherwise be lost because of the user's delay in starting to record.
Masamitsu ASAI Jiro YAMAKITA Shinnosuke SAWA Junya ISHII
We present a 44 matrix-based analysis of scattering form a two-dimensional rectangular resistive plane gratings placed on an anisotropic dielectric slab. The solution procedure used is formulated by extending the 44 matrix approach. The fields are expanded in terms of two-dimensional Floquet modes. Total fields can be given as sum of primary and secondary fields whose expression are obtained through eigenvalue problem of coupled wave matrix. Unknown currents on resistive patches are determined by applying Galerkin's method to the resistive boundary condition on resistive grating. Results are compared with other numerical examples available in the literature for isotropic cases. Further, numerical calculation are performed in the case of gratings with polar-type anisotropic slab.
Katsuya MANABE Yasumitsu MIYAZAKI
A numerical scheme to analyze a three-dimensional perfectly conducting body that has edges and corners is presented. The geometry of the body can be arbitrary. A new formulation using boundary element method has been developed. This formulation allows that a scatterer has edges and corners, where the behavior of the electromagnetic fields become singular.
In this paper, we present for the first time two three-dimensional analytical electrostatic Green's functions for shielded and open arbitrarily multilayered medium structures. The analytical formulas for the Green's functions are simply expressed in the form of Fourier series and integrals, and are applicable to the arbitrary number of dielectric layers. In combination with the complex image charge method, we demonstrate an efficient application to analyze microstrip discontinuities in a three-layered dielectric structure. Numerical results for the capacitance associated with on open-end discontinuity show good agreement with those from a previous paper and the effectiveness of using the analytical Green's functions to analyze three-dimensional electrostatic problems.
The radiation and scattering characteristics of a metal-strip grating of finite extent printed on the surface of a dielectric waveguide are analyzed within a two-dimensional model. The diffraction properties are obtained from a solution to the problem of surface mode scattering by a finite number of metal strips, taking into account their mutual couplings. The analysis is based on the electromotive force technique which does not require a grating to be periodic. Obtained results concern the antenna applications of radiating gratings excited by the dominant TE or TM surface mode of the wavegude. The proposed approach can be applied not only to the design of radiators but also filters based on periodic strip gratings.
Supot TIARAWUT Tadao SAITO Hitoshi AIDA
This paper proposes a new multistage switch architecture for large-scale multicast ATM switching. The proposed architecture uses routing schemes both at the connection level and the cell level. This results in the reduction of the memory capacity required in the trunk number translators of the copy network modules. If Connection Splitting algorithm is used, a nonblocking switch can be constructed under the same nonblocking condition as that of point-to-point Clos network. It is shown that the memory requirements in the new switching network are less than the previous architectures.
Tetsuhiko FUJII Akira YAMAMOTO Naoya TAKAHASHI Minoru YOSHIDA
This paper proposes a masked data transferring method for the write-back controlled disk cache system employing a fixed-length recording disk drive, enabling data transfer of discontinuous sectors on the same track between the cache and the disk. This paper also evaluates the method. In write-back controlled disk cache sytems, random write requests cause dirty data (write-pending data on a cache) on discontinuous areas on the cache. It is likely that several sectors on the same track become dirty. These dirty sectors must be written onto the disk according to the cache management scheme. In conventional data transferring methods between a disk cache and a disk drive, plural sectors can be transferred in one single operation when the sectors are adjacent, but discrete sectors must be transferred by individual operations. In the methods, an address of the head sector and number of sectors to be transferred are given to the transfer unit. For example, when two sectors on the same track are located closely but not adjacently, and data transfer is requested for those two sectors, the transfer operation for the second sector must be prepared after the first transfer had completed and before the second sector arrives under the disk head. Although the time for the head to pass by the uninterested sector is often too short for the software overhead for the first transfer to be completed and the second transfer to be prepared, which leads to an unwanted extra rotation of the disk. With the masked transferring method proposed in this paper, the micro program creates a bit-map specifying the target sectors to be transferred and passes it to the data transfer unit, enabling to transfer the discontinuous sectors without latency. The method was evaluated using OLTP warkloads. Results show an improvement in random I/O throughput of between 8% and 27%. The masked transferring method is adopted in Hitachi's A-6521 disk subsytems, shipped since December 1993.
Dennis P. NYQUIST David J. INFANTE
Discrete higher-order modes of stripline, both proper and leaky, as well as its continuous spectrum are conceptualized and quantified by a full-wave integral operator formulation through complex analysis in the axial Fourier-transform plane. Poles associated with the parallel-plate background environment lead to branch points in the axial transform plane. A criterion for choice of associated branch cuts to restrict the migration of poles in the transverse transform plane is identified. The higher-order discrete modes are both bound (proper), with a low-frequency cutoff, and leaky (improper). The higher-order proper mode has a propagation constant very nearly equal to that for the TM parallel-plate mode. Distributions of the continuous-spectrum currents appear to consist of a smooth transition from those of the highest propagating proper discrete mode, as might be expected physically. The continuous spectrum is dominated by the propagating portions associated with any TM background modes (poles) which are above cutoff, and in fact by spectral points in a region very near to the branch point.
Wei-Dong WANG Minoru ABE Toshio SEKIGUCHI
An exact solution of the propagation constant of a cylindrical waveguide has been obtained in the event of the conductivity of the waveguide-composing conductor being finite. The said analysis has been reduced to a problem to solve a transcendental equation concerning an eigenvalue of the individual modes of the in-guide electromagnetic wave, and calculation of Jn-1(z)/Jn(z) by using of Bessel function becomes necessary. With a large conductivity the absolute value of the complex number z becomes excessively large, and none of calculation method with high accuracy has been found with the aid of a computer. This paper has solved the problem by using a continued fraction for the calculation with regard to which a recurrence formula is utilized. With the TE01 wave that has conventionally been used as a millimeter-wave guide, it is cleared that it is sufficient to select the number of the calculation terms of the continued fraction to the extent of approximately 1000 in the accuracy in accordance with this calculation method. It is also cleared that the approximation solution obtained by a method of perturbation coincides with the exact solution for the conductivity σ 102 [S/m].
In this paper, we study the following node-to-node fault tolerant routing problem: In the presence of up to n-1 faulty nodes, find a fault-free path which connects any two non-faulty nodes s and t in an n-connected graph. For node-to-node fault tolerant routing in n-dimensional hypercubes Hn, we give an algorithm which finds a fault-free path s t of length at most in O(n) time, where d(s, t) is the distance between s and t. We also show that a fault-free path s t in Hn of length at most d(s, t)2i, 1i, can be found in time. For node-to-node fault tolerant routing in n-dimensional star graphs Gn, we give an algorithm which finds a fault-free path s t of length at most min{d(Gn)3, d(s, t)6} in O(n) time, where is the diameter of Gn. It is previously known that, in Hn, a fault-free path s t of length at most d(s, t) for d(s, t)n and at most d(s, t)2 for d(s, t)n can be found in O(d(s, t)n) time, and in Gn, a fault-free path s t of length at most min{d(Gn)1, d(s, t)4}can be found in O(d(s, t)n) time. When the time efficiency of finding the routing path is more important than the length of the path, the algorithms in this paper are better than the previous ones.
Mesa structures have been investigated to optimize a buried-heterostructure (BH) for a GaInAsP/InP surface-emitting (SE) laser regrown by metalorganic chemical vapor deposition (MOCVD), and it has been found that a square mesa top pattern of which the sides are at an angle of 45 to the 011 orientation is suitable. A 1.3-µm GaInAsP/InP square buried heterostructure (SBH) SE laser with this mesa structure has been demonstrated and low-threshold CW oscillation (threshold current Ith=0.45 mA) at 77 K and low-threshold room-temperature pulsed oscillation (Ith=12 mA) have been obtained.
In this paper, a description of the Hopfield/Tank model used for the telecommunication network routing problem is given at first. And then through the "static" (i.e. the eigenvalue and the eigenspace of the connection matrix) and the dynamic analysis of the model, it has been found that the model has the faster rate to converge to the optimal or sub-optimal solutions from an initial value. Therefore the quality of the final solutions can be guaranteed. The influence of the initial value to the final solutions is also concerned in this paper. The simulation results are given at the end of this paper.
Kazuhiko SEKI Shuji KUBOTA Shuzo KATO
This paper proposes a novel phase ambiguity resolver with combining a very low power Viterbi decoder employing a scarce state transition scheme to realize cost effective receivers for the PCM sound broadcasting satellite service. The theoretical analyses on phase decision performance show that the proposed resolver achieves the symbol-by-symbol phase detection and decides correctly phases of the demodulated data even if the bit error probability of 710-2. The resolver also reduces the phase decision time to below 1/1000 of that of the conventional resolver. Furthermore, experimental results of the power consumption estimate that the prototype Viterbi decoder consumes only 60mW at the data rate of 24.576Mbit/s.
Feng BAO Yoshihide IGARASHI Keiko KATANO
We study all-to-all broadcasting in hypercubes with randomly distributed Byzantine faults. We construct an efficient broadcasting scheme BC1-n-cube running on the n-dimensional hypercube (n-cube for short) in 2n rounds, where for communication by each node of the n-cube, only one of its links is used in each round. The scheme BC1-n-cube can tolerate (n-1)/2 Byzantine faults of nodes and/or links in the worst case. If there are exactly f Byzantine faulty nodes randomly distributed in the n-cabe, BC1-n-cube succeeds with a probability higher than 1(64nf/2n) n/2. In other words, if 1/(64nk) of all the nodes(i.e., 2n/(64nk) nodes) fail in Byzantine manner randomly in the n-cube, then the scheme succeeds with a probability higher than 1kn/2. We also consider the case where all nodes are faultless but links may fail randomly in the n-cube. Broadcasting by BC1-n-cube is successful with a probability hig her than 1kn/2 provided that not more than 1/(64(n1)k) of all the links in the n-cube fail in Byzantine manner randomly. For the case where only links may fail, we give another broadcasting scheme BC2-n-cube which runs in 2n2 rounds. Broadcasting by BC2-n-cube is successful with a high probability if the number of Byzantine faulty links randomly distributed in the n-cube is not more than a constant fraction of the total number of links. That is, it succeeds with a probability higher than 1nkn/2 if 1/(48k) of all the links in the n-cube fail randomly in Byzantine manner.
Michinari SHIMODA Tokuya ITAKURA Yuko YAMADA
The two-dimensional scattering problem of electromagnetic waves by a perfectly conducting wedge is analyzed by means of the Wiener-Hopf technique together with the formulation using the partition of scatterers. The Wiener-Hopf equations are derived on two complex planes. Investigating the mapping between these complex planes and introducing the appropriate functions which satisfy the edge condition of the wedge, the solutions of these equations are obtained by the decomposition procedure of functions. By deforming the integration path of the Fourier inverse transform, it is found that the representation of the scattered wave is in agreement with the integral representation using the Sommerfeld contours.
This paper proposes a new class of error locating codes which corrects random single-bit errors and indicates a location of an erroneous b-bit byte which includes e-bit errors, where 2 e b, called SECSe/bEL codes. This type of codes is very suitable for an application to memory systems constructed from byte-organized memory chips because this corrects random single-bit errors induced by soft-errors and also indicates the position of the faulty memory chips. This paper also gives a construction method of the proposed codes using tensor product of the two codes, i.e., the single b-bit byte error correcting codes and the single-bit error correcting and e-bit error detecting codes. This clarifies lower bounds and error control capabilities of the proposed codes.
Masanobu WATANABE Toru YAMANOUCHI Masahiko IWAMOTO Satoru FUJITA
This paper describes, from a system architectural viewpoint, how knowledge-based technologies have been utilized in developing EXLOG (an LSI circuit synthesis system) and SOFTEX (a software synthesis system) inside the authors' projects. Although the system architectures for EXLOG and SOFTEX started from the same production systems, consisting of transformation rules in the middle of the 1980's, both branched off in different directions in the 1990's. Based on experiences with EXLOG and SOFTEX, the differences between LSI and software design models are discussed, and the future directions are indicated for the knowledge-based design system architectures.
Cong-Kha PHAM Munemitsu IKEGAMI Mamoru TANAKA
This paper described discrete time Cellular Neural Networks (DT-CNN) with two types of neuron circuits for image coding from an analog format to a digital format and their VLSI implementations. The image coding methods proposed in this paper have been investigated for a purpose of transmission of a coded image and restoration again without a large loss of an original image information. Each neuron circuti of a network receives one pixel of an input image, and processes it with binary outputs data fed from neighboring neuron circuits. Parallel dynamics quantization methods have been adopted for image coding methods. They are performed in networks to decide an output binary value of each neuron circuit according to output values of neighboring neuron circuits. Delayed binary outputs of neuron circuits in a neighborhood are directly connected to inputs of a current active neuron circuit. Next state of a network is computed form a current state at some neuron circuits in any time interval. Models of two types of neuron circuits and networks are presented and simulated to confirm an ability of proposed methods. Also, physical layout designs of coding chips have been done to show their possibility of VLSI realizations.