As to the method of multi-layer testing, up to now, the testing system (called PROVES) which testes effectively each N-layer protocol implement of SUT (System Under Test) using the functions of derail-points located between N-layer and (N+1)-layer protocol implements in a test system has been proposed. The test logic programs, which are embedded in the derail-points of the test system, play an important role to realize the protocol error test sequences in the test system. Namely, they modify, add, or delete the correct protocol commands/responses output from the protocol implement part of the lest system, sends these erroneous commands/responses to SUT and observes the output from SUT. This paper proposes the method of validating the correctness of test logic program using the structural properties of Petri nets without coding the test logic programs, where correctness means that the desired output can be obtained by sending or receiving the commands/responses within a constant time under the initial conditions determined uniquely by the test system and SUT. According to our experiment, it is seen that almost all of the logical errors included in the test logic programs used for the experiment can be detected by this method.

A modified deformable model is presented for constructing bijective topology preserving feature maps. The algorithm can solve the optimization problem in the input space as well as that in the output space. A saturating distance function alternative to the Euclid norm is employed to obtain compact space filling maps.

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) γ(S, c) and the coefficient (S, c) are returned: Such a word c is called a counterexample for the query. For each execution step of the algorithm, the execution time consumed from the initial step to the current step is O(mN 4M), where N is the dimension of a reduced linear representation of S, M is the maximum time consumed by a single fundamental operation (addition, subtraction, multiplication or division), and m is the maximum length of counterexamples as answers to equivalence queries returned until that step.

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.

This paper describes an image synthesis method based on an estimation of camera parameters. In order to acquire high quality images using image synthesis, we take some constraints into account, which include angle of view, synchronization of change of scale and change of viewing direction. The proposed method is based on an investigation that any camera operation containing a change of scale and a pure 3D rotation can be represented by a 2D geometric transformation. The transformation can explain all the synthesis procedure consisting of locating, synchronizing, and operating images. The procedure is described based on a virtual camera which is constituted of a virtual viewing point and a virtual image plain. The method can be efficiently implemented in such a way that each image to be synthesized undergoes the transformation only one time. The parameters in the image transformation are estimated from image sequence. The estimation scheme consists of first establishing correspondence and then estimating the parameters by fitting the correspondence data to the transformation model. We present experimental results and show the validity of the proposed method.

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.

In this paper, we present new algorithms to calculate the reverse distance transformation and to extract the skeleton based upon the Euclidean metric for an arbitrary binary picture. The presented algorithms are applicable to an arbitrary picture in all of n-dimensional spaces (n2) and a digitized picture sampled with the different sampling interval in each coordinate axis. The reconstruction algorithm presented in this paper is resolved to serial one-dimensional operations and efficiently executed by general purpose computer. The memory requirement is very small including only one picture array and single one-dimensional work space array for n-dimensional pictures. We introduce two different definitions of skeletons, both of them allow us to reconstruct the original binary picture exactly, and present algorithms to extract those skeltons from the result of the squared Euclidean distance transformation.

An annoying problem encountered in automatic seal imprint verification is that for seal imprints may have a lot of variations, even if they are all produced from a single seal. This paper proposes a new automatic seal imprint verification system which adds an imprint quality assessment function to our previous system in order to solve this problem, and also examines the verification performance of this system experimentally. This system consists of an imprint quality assessment process and a verification process. In the imprint quality assessment process, an examined imprint is first divided into partial regions. Each partial region is classified into one of three quality classes (good quality region, poor quality region, and background) on the basis of characteristics of its gray level histogram. In the verification process, only good quality partial regions of an examined imprint are verified with registered one. Finally, the examined imprint is classified as one of two types: a genuine and a forgery. However, as a result of quality assessment, if the partial regions classified as poor quality are too many, the examined imprint is classified as ambiguous" without verification processing. A major advantage of this verification system is that this system can verify seal imprints of various qualities efficiently and accurately. Computer experiments with real seal imprints were performed by using this system, previous system (without image quality assessment function) and document examiners of a bank. The results of these experiments show that this system is superior in the verification performance to our previous system, and has a similar verification performance to that of document examiners (i.e., the experimental results show the effectiveness of adding the image quality assessment function to a seal imprint verification system).

We propose a method which can construct LOTOS specifications of communication systems from temporal properties described in Extended branching time temporal logic (EBTL) in this paper. Description of LOTOS, one of Formal Description Techniques, is based on behaviors of systems so that LOTOS permits strict expression. However, it is difficult to express temporal properties explicitly. On the other hand, Temporal logic is based on properties of systems. Thus temporal logic permits direct expression of temporal properties which can be understood intuitively. Accordingly, temporal logic is more useful than FDTs on the first step of systems specification. This method is effective in this point of view. Specifications obtained using this method can have a structured style. When temporal properties are regarded as constraints about temporal order among actions of systems, those specification can have a constraint oriented style. This method is based on sequential composition of Labelled Transition Systems (LTSs) which are semantics of LOTOS. EBTL is also defined on LTSs. In general, many LTSs satisfy the same temporal property. To obtain such the minimal LTS, the standard form of LTSs corresponding to EBTL operators are defined. Those standard LTSs are mainly tailored to the field of communication protocol. We also show conditions that original temporal properties are preserved in case of sequential composition of standard LTSs. In addition, applying this method to the Abracadabra Protocol, we show that this method can construct specifications of concrete protocols effectively.

An encoder of a trellis coded modulation (TCM) is composed of a linear convolutional encoder followed by a mapper to channel signals. A new condition, under which the performance evaluation of the TCM is possible based on the 2ν state error state transition diagram, is proposed, where ν is the number of delay elements in the convolutional encoder. There have been proposed three similar methods. This paper points out the restriction of the previous methods, and proposes a new method. The condition, under which the previous method is useful, is called nuiformity, such as, the error weight profile is independent from the encoder state. When uniformity does not hold, we discuss to divide an error state into substates based on the coset decomposition of output vectors of the convolutional encoder. The coset is determined by the vector called coset selector. If the condition defined as equal dividing holds, the subdivided states can be merged and the performance can be evaluated based on the 2ν state transition diagram, even for the codes without uniformity. When the row rank of the transformation matrix, from the input vector of the encoder to the coset selector vector, is full, the equal dividing condition holds under the assumption of equally probable i.i.d. (independently identically distributed) input sequence. For TCM schemes without uniformity (in the case, previous methods can not be applied), upper bounds of the bit error rate are evaluated by the proposed method and compared with the simulation results. The difference is less than 10% in the range of bet error rate 10-4.

Learning correctly from queries" is a formal learning model proposed by Angluin. In this model, for a class Γ of language representations, a learner asks queries to a teacher of an unknown language Lq which can be represented by some GqΓ, and eventually outputs a language representation GΓ which represents Lq and halts. An algorithm (leaner) A is said to learn a class of languages represented by Γ in the weak definition if the time complexity of A is some polynomial of n and m, where n is the minimum size of the lagunage representations in Γ which represent Lq, and m is the maximum length of the counterexamples returned in an execution. On the other band, A is said to learn represented by Γ in the strong definition if at any point τ of the execution, the time consumed up to τ is some polynomial of n and m, where n is the same as above, and m is the maximum length of the counterexamples returned up to τ. In this paper, adequacy of the model is examined, and it is shown that both in the weak and strong definitions, there exist learners which extract a long counterexample, and identify Lq by using equivalence queries exhaustively. For example, there exists a learner which learns the class CFL of context-free languages represented by the class CFG of context-free grammars in the weak definition using only equivalence queries. Next, two restrictions concerning with learnability criteria are introduced. Proper termination condition is that when a teacher replies with yes" to an equivalence query, then the learner must halt immediately. The other condition, called LBC-condition, is that in the weak/strong definition, the time complexity must be some polynomial of n and log m. In this paper, it is shown that under these conditions, there still exist learners which execute exhaustive search. For instance, there exists a learner which learns CFL represented by CFG in the weak definition using membership queries and equivalence queries under the proper termination condition, and there also exists a learner that learns CFL represented by CFG in the strong definition using subset queries and superset queries under LBC-condition. These results suggest that the weak definition is not an adequate learning model even if the proper termination condition is assumed. Also, the model becomes inadequate in the strong definition if some combination of queries, such as subset queries and superset queries, is used instead of equivalence queries. Many classes of languages become learnable by our extracting long counterexample" technique. However, it is still open whether or not CFL represented by CFG is learnable in the strong definition from membership queries and equivalence queries, although the answer is known to be negative if at least one of (1) quadratic residues modulo a composite, (2) inverting RSA encryption, or (3) factoring Blum integers, is intractable.

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.

The issue about document structure recognition and document understanding is today one of interesting subjects from a viewpoint of practical applications. The research objective is to extract the meaningful data from document images interpretatively and also classify them as the predefined item data automatically. In comparison with the traditional image-processing-based approaches, the knowledge-based approaches, which make use of various knowledge in order to interpret structural/constructive features of documents, have been currently investigated as more flexible and applicable methods. In this paper, we propose a totally integrated paradigm for understanding table-form documents from a viewpoint of the architectural framework.

This paper presents a discrete Fourier analyzer using analog VLSI technology. An analog current-mode technique is employed for implementing it by a regular array structure based on the straight-forward discrete Fourier transform (DFT) algorithm. The basic components are 1-dimensional (1-D) analog current-mode multiplier array for fixed coefficient multiplication, two-dimensional (2-D) analog switch array and wired summations. The proposed scheme can process speedily N-point DFT in a time proportional to N. Possibility of the realization of the analog DFT VLSI based on 1 µm technology is discussed from the viewpoints of precision, speed, area, and power dissipation. In the case of 1024-point DFT, the standard deviation of the total error is estimated to be about 2%, the latency, or processing time is about 110 µs, and the signal sample rate based on a pipeline manner is about 4.7 MHz. A prototype MOS integrated circuit of the 16-point multiplier array has been implemented and a typical operation using the multiplier array has been confirmed.

An adaptive LMS filtering system is proposed for computing the Discrete Walsh Transform (DWT). The signal to be transformed serves as the 'desired signal' for the adaptive filter, while a set of periodic Walsh sequences serve as the input signal vector for the adaptive filter. The weights of the adaptive filter provide the DWT. The given approach is more efficient in terms of the required computations and memory locations compared with the direct approach. In contract with existing Fast DWT algorithm, the proposed solution provides more flexibility as far as the signal block length is concerned. In other words, the proposed approach is not restricted to a block length N to be of power 2.

Finite state translation systems (fsts') are a widely studied computational model in the area of tree automata theory. In this paper, the string generating capacities of fsts' and their subclasses are studied. First, it is shown that the class of string languages generated by deterministic fsts' equals to that of parallel multiple context-free grammars, which are an extension of context-free grammars. As a corollary, it can be concluded that the recognition problem for a deterministic fsts is solvable in O(ne1)-time, where n is the length of an input word and e is a constant called the degree of the deterministic fsts'. In contrast to the latter fact, it is also shown that nondeterministic monadic fsts' with state-bound 2 can generate an NP-complete language.

A new efficient waveform relaxation technique based on dynamically overlapped partitioning scheme is presented. This overlapped partitioning method enables the application of waveform relaxation technique to bipolar VLSI circuits. Instead of fixed overlapping, we select the depth of overlapping dynamically based on the sensitivity criteria. By minimizing the overlapped area, we could reduce the additional computational overhead which results from overlapping the partitions. This overlapped waveform relaxation method has better convergence properties due to smaller error introduced at each step compared with standard relaxation techniques. When overlapped partitioning is used in the case of digital circuits, the waveforms obtained after first iteration are nearly accurate. Therefore, by using these waveforms as initial guess waveforms for the second iterations we can reduce Newton-Raphson iterations at each time point.

This paper describes the relaxation-based algorithms with the dynamic partitioning technique for bipolar circuit analysis. In this technique, a circuit is partitioned dynamically based on the consideration of the operating region of specified bipolar devices. This technique has been used already in the waveform relaxation method. In this paper, the dynamic circuit partitioning technique is implemented in the Iterated Timing Analysis (ITA). First, the dynamic partitioning method and its validity are described. Next, the present ITA is applied to the transient simulation of several digital bipolar circuits and compared with the waveform relaxation method.

Many metrics between trees have been proposed. However, there is no research on a graph metric that can be applied to molecular graphs. And most of the reports on tree metrics have dealt with rooted and ordered trees. As the first step defining a graph metric for molecular graphs, this paper proposes a tree metric between unrooted and unordered trees. This metric is based on a mapping between trees that determines a transformation from one tree to another. The metric is the minimum weight among the weights of all possible transformations. The characteristics of the mapping are investigated. A top-down computing method is proposed using the characteristics of the mapping. The time and space complexities are OT(N 2aN 2b(N 3aN 3b)) and Os(N 2aN 2b), respectively, where Na and Nb are the numbers of vertices of the two trees. If the degrees of all vertices of the trees are bounded by a constant, the time complexity of the method is O (N 3aN 3b). The computing time to obtain the distance between a pair of molecular graphs using a computer (SUN SparcStation ELC) is 0.51 seconds on average for all the pairs of 111 molecular graphs that have 12.0 atoms on average. This methic can be applied to the clustering of molecular graphs.

In the band-limited signal space, the mutual relation between continuous time signal and discrete time signal is expressed by the sampling theorem of Whittaker-Someya-Shannon. This theorem consists of an orthonormal expansion formula using sinc functions. In that formula, the expansion coefficients are identical to the sample values of signals. In general, the bandlimited signal space is not always suited to model the signals in nature. The authors have proposed a new model for signal processing based on finite times continuously differentiable functions. This paper aims to complete the sampling theorem for the spline signal spaces, which corresponds to the sampling theorem of Whittaker-Someya-Shannon in the band-limited signal space. Since the obtained sampling theorem gives the simplest representation of signals, it is considered to be the most fundamental characterization of spline functions used for signal processing. The biorthonormal basis derived in this paper is considered to be a system of delta functions at sampling points with some continuous differentiability.