This paper studies the problem of embedding a graph into a book with nodes on a line along the spine of the book and edges on the pages in such a way that no edge crosses another. Atneosen as well as Bernhart and Kainen has shown that every graph can be embedded into a 3-page book when each edge can be embedded in more than one page. The time complexity of Bernhart and Kainen's method is Ω(ν(G)), where ν(G) is the crossing number of a graph G. A new 0(mn) algorithm is derived in this paper for embedding a graph G=(V, E), where m=│E│ and n= │V│ . The number of points at which edges cross over the spine in embedding a complete graph into a 3-page book is also investigated.

A C1 interpolation scheme for constructing surface patch on n-sided region (n5, 6) is presented. The constructed surface patch matches the given boundary curves and cross-boundary slopes on the sides of the n-sided region (n5, 6). This scheme has relatively simple construction, and offers one degree of freedom for adjusting interior shape of the constructed interpolation surface. The polynomial precision set of the scheme includes all the polynomials of degree three or less. The experiments for comparing the proposed scheme with two schemes proposed by Gregory and Varady respectively and also shown.

This paper describes the current implementation and experimental results of a hardware/software codesign system for ASIP (Application Specific Integrated Processor) development： the PEAS-I System. The PEAS-I system accepts a set of application programs written in C language, associated data set, module database, and design constraints such as chip area and power consumption. The system then generates an optimized CPU core design in the form of an HDL as well as a set of application program development tools such as a C compiler, an assembler and a simulator. Another important feature of the PEAS-I system is that the system is able to give accurate estimations of chip area and performance before the detailed design of the ASIP is completed. According to the experimental results, the PEAS-I system has been found to be highly effective and efficient for ASIP development.

The scope of this paper is the realization of FIR digital filters with an emphasis on linear phase and maximally flat cases. The transfer functions of FIR digital filters are polynomials and polynomial evaluation algorithms can be utilized as realization schemes of these filters. In this paper we investigate the application of a class of polynomial evaluation algorithms called "recursive triangles" to the realization of FIR digital filters. The realization of an arbitrary transfer function using De Casteljau algorithm, a member of the recursive triangles used for evaluating Bernstein polynomials, is studied and it is shown that in some special and important cases it yields efficient modular structures. Realization of two dimensional filters based on Bernstein approximation is also considered. We also introduce recursive triangles for evaluating the power basis representation of polynomials and give a new multiplier-less maximally flat structure based on them. Finally, we generalize the structure further and show that Chebyshev polynomials can also be evaluated by the triangles. This is the triangular counterpart of the well-known Chebyshev structure. In general,the triangular structures yield highly modular digital filters that can be mapped to an array of concurrent processors resulting in high speed and effcient filtering specially for maximally flat transfer functions.

This paper deals with the size of switching functions in Exclusive-OR sum-of-products expressions (ESOPs). The size is the number of products in ESOP. There are no good algorithms to find an exact minimum ESOP. Since the exact minimization algorithms take a time in double exponential order, it is almost impossible to minimize ESOPs for an arbitrary n-variable functions with n5. Then,it is necessary to study the size of some concrete functions. These concrete functions are useful for testing heuristic minimization algorithms. In this paper we present the lower bounds on size of periodic functions in ESOPs. A symmetric function is said to be periodic when the vector of weights of inputs X such that f(X)1 is periodic. We show that the size of a 2t+1-periodic function with rank r is proportional to n2t+r, where t0 and 0r2t, i.e., in polynomial order,and thet the size of a (2s+1)2t-periodic function with s0 and t0 is greater than or equal to (3/2)n-(2s+1)2t, i.e., in exponential order. The concrete function the size of which is greater than or equal to 32(3/2)n-8 is presented. This function requires the largest size among the concrete functions the sizes of which are known. Some results for non-periodic symmetric functions are also given.

In this paper, an efficient and robust circuit parameter determination method suitable for analog circuit synthesis is presented. The method uses block diagram representation of circuits as implicit design knowledge. Circuit parameter determination is carried out by propagating known values along signal flow in the block diagram. The circuit parameter determination using signal propagation performs successfully when unknown circuit parameters can be solved in one way. However, when the block diagram involves implicit calculation, the propagation stops before all unknown parameters are determined. In order to cope with this problem, we introduced a method that employs a symbolic analysis technique combined with a numerical method. When the propagation of known values stops, one of unknown signals is selected, a unique symbol is assigned to the selected signal, and the signal propagation is restarted. This operation is repeated until there is no unknown signal. When the symbol propagation reaches the signal where the signal value is already set, one nonlinear equation for the signal is obtained by equating both signal values. It can be solved by a numerical method, such as Newton's method. The parameter determination method using procedural description is superior to the optimization based method because it is straightforward to incorporate design knowhow in the description. However, it is burdensome for designers to develop design procedures for each circuit to be synthesized. Because the block diagram based calculation method can be used as subroutine calls during the design procedure development, it simplifies the design procedural description and lowers the burden of designers. The method was applied to the element value determination of bias circuits to demonstrate its effectiveness.

This paper describes a segment driver IC for high-quality liquid-crystal-displays (LCDs). Major design issues in the segment driver IC are a wide signal bandwidth and excessive output-offset variation both within a chip and between chips. After clarifying the trade-off relation between the signal bandwidth and the output-offset variation originated from conventional sample-and-hold (S/H) circuits, two wide-band S/H circuits with low output-offset variation have been introduced. The basic ideas for the proposed S/H circuits are to improve timing of the sampling pulses applied to MOS analog switches and to prevent channel charge injection onto a storage capacitor when the switches turn off. The inter-chip offset-cancellation technique has been also introduced by using an additional S/H circuit. Two test chips were implemented using the above S/H circuits for demonstration purposes. The intra-chip output-offset standard deviation of 9.5 mVrms with a 3dB bandwidth of 50 MHz was achieved. The inter-chip output-offset standard deviation was reduced to 5.1 mVrms by using the inter-chip offset-cancellation technique. The evaluation of picture quality of an LCD using the chips shows the applicability of the proposed approaches to displays used for multimedia applications.

The requirement of structural boundedness or passivity leads to important classes of digital filters among which are the wave digital (WD) filters and the LBR cascade structures having low coefficient sensitivity. Contrary to the WD filters, the LBR filters are directly synthesized in z-domain and several authors presented different approaches for a better understanding of the synthesis procedure especially for complex transfer functions. Some tentatives were also made to give parallels between passive analog and digital filters (i.e. WD or LBR filters). A general approach to LBR synthesis with transmission zeros not necessarily on the unit circle is presented along with some explicit expressions for the LBR (and the generalized complex counterpart LBC) filter parameters for the realization of an input transfer function. The results can be of interest in automated procedures for low sensitivity digital filter design.

We investigated the impact of velocity overshoot effect on collector signal delay of bipolar devices by using Monte Carlo simulation method. We found that insertion of an i-layer (lightly doped, intrinsic layer) between base and collector can increase the delay, but the strength of this effect is a function of the i-layer thickness. When the i-layer becomes thinner, the problem of increasing delay seems to disappear. This recovery of delay is realised with a mechanism which is completely different from that in drift-diffusion model.

We have developed a novel method of numerical synthesis of optical waveguides, which consists of the endless loop of the random sampling of waveguide parameters, numerical analysis and the judgment of calculated result. This loop is repeated until some objective solutions satisfying required characteristics are discovered. When the structural condition is almost unknown and there is no clue to search it, this method is useful for discovering new-type waveguides, and this concept is applicable to any other devices. We applied this method to the search of new waveguide structures having multilayer claddings, and obtained many types of low loss single mode waveguides, including ARROW-type waveguides, waveguide-type polarizers and a very narrow band wavelength filter.

This paper points out that there are two types of claw free families with respect to a level of claw freeness. We formulate them as weak claw free families and strong claw free families. Then, we present sufficient conditions for each type of claw free families. (A similar result is known for weak claw free families.) They are represented as some algebraic forms of one way functions. A new example of strong claw free families is also given.

This paper presents an improved current-mode circuit for implementation of a chaotic neuron model. The proposed circuit uses a switched-current integrator and a nonlinear output function circuit, which is based on an operational transconductance amplifier, as building blocks. Is is shown by SPICE simulations and experiments using discrete elements that the proposed circuit well replicates the behavior of the chaotic neuron model.

This paper describes the current situations and future directions of intelligent CAI researches/development in Japan. Then necessity of intelligence in CAIs/Educational systems are thought over corresponding to the model of teaching and the cognitive model of human learning like the situated learning, knowledge construction and so on. Originally, the main aims of ITSs/ICAIs are to tealize the high level environment of individual teaching/learning. So it is the most important to incorporate the intellectual function of teaching into the system. Whatever kinds of teaching purposes ITSs have, they have the quite complex structure which consists of the domain knowledge base (Expert system), student model, the tutoring knowledge base, the powerful human interface, and sophisticated inference engine with plural functions by artificial intelligence technology. In this paper, the technological and educational points of view are discussed, surveyed and summarized based on intelligent teaching functions of ITSs/ICAIs. Moreover, the meaning of new paradigm from ITSs to ILE are mentioned under the new technology of networking and multi-media.

An efficient algorithm is presented for finding all solutions of piecewise-linear resistive circuits. In this algorithm, a simple sign test is performed to eliminate many linear regions that do not contain a solution. This makes the number of simultaneous linear equations to be solved much smaller. This test, in its original form, is applied to each linear region; but this is time-consuming because the number of linear regions is generally very large. In this paper, it is shown that the sign test can be applied to super-regions consisting of adjacent linear regions. Therefore, many linear regions are discarded at the same time, and the computational efficiency of the algorithm is substantially improved. The branch-and-bound method is used in applying the sign test to super-regions. Some numerical examples are given, and it is shown that all solutions are computed very rapidly. The proposed algorithm is simple, efficient, and can be easily programmed.

It is often desired to change the cutoff frequencies of digital filters in some applications like digital electronic instruments. This paper proposes a design of variable lowpass digital filters with wider ranges of cutoff frequencies than conventional designs. Wave digital filters are used for the prototypes of variable filters. The proposed design is based on the frequency scaling in the s-domain, while the conventional ones are based on the z-domain lowpass-to-lowpass transformations. The first-order approximation by the Taylor series expansion is used to make multiplier coefficients in a wave digital filters obtained from a frequency-scaled LC filter become linear functions of the scaling parameter, which is similar to the conventional design. Furthermore this paper discusses the reduction of the approximation error. The curvature is introduced as the figure of the quality of the first-order approximation. The use of the second-order approximation to large-curvature multiplier coefficients instead of the first-order one is proposed.

This paper considers the subliminal channel, hidden in an identification scheme, for transferring signatures. We observe the direct parallelization of the Fiat-Shamir identification scheme has a subliminal channel for the transmission of the digital signature. A positive aspect of this hidden channel supplies us how to transfer signatures without secure channels. As a formulation of such application, we introduce a new notion called privately recordable signature. The privately recordable signature is generated in an interactive protocol between a signer and a verifier, and only the verifier can keep the signatures although no third adversary can record the signatures. ln this scheme, then the disclosure of the verifier's private coin turns the signer's signature into the ordinary digital signature which is verified by anybody with the singer's public key. The basic idea of our construction suggests the novel primitive that a transferring securely signatures without secret channels could be constructed using only one-way function (without trapdoor).

This paper presents an equation capable of briefly evaluating the length of white noise sequence to be sent as a training signal. The equation is formulated by utilizing the formula describing the convergence property, which has been derived from the IIR filter expression of the NLMS algorithm. The result revealed that the length is directly proportional to I/[K(2-K)] where K is a step gain and I is the number of the adaptive filter taps.

This paper gives a systematic approach to generate a Markov chain by a discrete-valued auto-regressive equation, which is a a nonlinear auto-regressive equation having a discrete-valued solution. The power spectrum, the correlation function and the transition probability are explicitly obtained in terms of the discrete-valued auto-regressive equation. Some computer results are illustrated in figures.

In a previous article, an optical array imaging system has been presented. In this system, first, a set of array data is collected by repeatedly illuminating the object with laser light from each array element, detecting the reflected light as interferogram, and extracting the reflected wave field based on the spatial heterodyne detection. Then, an eigenvalue analysis is applied to the data to derive the wave field that would backpropagate and focus at a single point on the object; in this case, the iterative algorithm is used which indicates that the object point may have the largest reflectivity. It was shown experimentally that the single-point-focusing was attained for objects having several such parts with almost the same reflectivities. A preliminary study by computer simulation, however, indicates that the probability with which the wave focuses at multiple object points would not be small enough, resulting in a degraded image with ghost image components. In this paper, the array data within subaperture regions are selectively used to attain the single-point-focusing and obtain a good image for any object. First, it is shown analytically that the change in the dimension or center position of the aperture is effective to change the eigenvector so that it attains the single-point-focusing. Then, a procedure to find the optimum subapertures and a measure evaluating the degree of single-point-focusing for the eigenvector are presented. The method is examined in detail using experimentally obtained array data, and the results show that the method is effective in obtaining good images for any objects without sacrificing image resolution. When we compare the imaging system to an automatic focusing camera, it may be said that the additional processings enhance the capability of automatic focusing to a great degree.

In the present paper, we focus ourselves on the turning point (TP) algorithm proposed by Mueller and evaluate its performance when applied to a Gaussian signal with definite covariance function. Then the ECG wave is modeled by Gaussian signals: namely, the ECG is divided into two segments, the baseline segment and the QRS segment. The baseline segment is modeled by a Gaussian signal with butterworth spectrum and the QRS one by a narrow-band Gaussian signal. Performance of the TP algorithm is evaluated and compared when it is applied to a real ECG signal and its Gaussian model. The compression rate (CR) and the normalized mean square error (NMSE) are used as measures of performance. These measures show good coincidence with each other when applied to Gaussian signals with the mentioned spectra. Our results suggest that performance evaluation of the compression algorithms based on the stochastic-process model of ECG waves may be effective.