Let l be a positive integer, and let G be a graph with nonnegative integer weights on edges. Then a generalized vertex-coloring, called an l-coloring of G, is an assignment of colors to the vertices of G in such a way that any two vertices u and v get different colors if the distance between u and v in G is at most l. In this paper we give an algorithm to find an l-coloring of a given graph G with the minimum number of colors. The algorithm takes polynomial time if G is a partial k-tree and both l and k are bounded integers.

This paper proposes a new self-healing scheme that differentiates the bandwidth requirement for each network service on ATM networks. First, we show the necessity of our proposed scheme. In the future network, we must satisfy two demands, rapid restoration from failure and differentiated bandwidth requirements. The conventional restoration scheme, called the self-healing scheme, realizes rapid restoration, but does not support bandwidth differentiation; the new self-healing scheme proposed herein does. We also show that the proposed scheme reduces the spare resources required for backup. The scheme can be realized as a simple extension of the conventional self-healing scheme. Finally, simulations show that the proposed scheme requires fewer spare resources while offering comparable restoration time to the conventional approach against any demand pattern.

Low voltage (LV) analog circuit design techniques are addressed in this tutorial. In particular, (i) technology considerations; (ii) transistor model capable to provide performance and power tradeoffs; (iii) low voltage implementation techniques capable to reduce the power supply requirements, such as bulk-driven, floating-gate, and self-cascode MOSFETs; (iv) basic LV building blocks; (v) multi-stage frequency compensation topologies; and (vi) fully-differential and fully-balanced systems.

To provide QoS guarantees for each connection, efficient scheduling algorithms, such as WFQ, have been proposed. These algorithms assume a certain amount of buffer is allocated for each connection to provide loss free transmission of packets. This buffer allocation policy, however, requires much buffer space especially when many connections are sharing a link. In this paper we propose the use of partial buffer sharing (PBS) policy combined with usage parameter control (UPC) for efficient buffer management and flexible QoS control in ATM switches. We evaluate the feasibility of the proposed method by solving a Markov model. We also show that using the proposed method, we can control the cell loss ratio (CLR) independently of the delay. Numerical evaluations are presented, which indicates the PBS combined with UPC significantly reduces the buffer size required to satisfy given cell loss ratios.

The abilities of fuzzy inference methods in modeling of complicated systems are implemented to electromagnetics for the first time. The very popular and well known monopole antenna is chosen as a general example and a fast, simple and accurate fuzzy model for its input impedance is made by introducing a new point of view to impedance basic parameters. It is established that a surprisingly little number of input data points is sufficient to make a full model and also the system behavior (dominant rules) are saved as simple membership functions. The validity of the derived rules is confirmed through applying them to the case of thin-angled monopole antenna and comparing the results with the measured. Finally using the spatial membership function context, input impedance of thick-angled monopole antenna is predicted and a novel view point to conventional electromagnetic parameters is discussed to generalize the modeling method.

We propose an untraceable electronic money system. Our system uses the partially blind signature based on the discrete logarithm problem, and applies secret key certificates to the payment protocol.

We explain three random sampling techniques that are simple but widely applicable for various problems involving huge data sets. The first technique is an immediate application of large deviation bounds. The second and the third ones are sequential sampling or adaptive sampling techniques. We fix one simple problem and explain these techniques by demonstrating algorithms for this problem and discussing their correctness and efficiency.

Interpolation attack was presented by Jakobsen and Knudsen at FSE'97. Interpolation attack is effective against ciphers that have a certain algebraic structure like the PURE cipher which is a prototype cipher, but it is difficult to apply the attack to real-world ciphers. This difficulty is due to the difficulty of deriving a low degree polynomial relation between ciphertexts and plaintexts. In other words, it is difficult to evaluate the security against interpolation attack. This paper generalizes the interpolation attack. The generalization makes easier to evaluate the security against interpolation attack. We call the generalized interpolation attack linear sum attack. We present an algorithm that evaluates the security of byte-oriented ciphers against linear sum attack. Moreover, we show the relationship between linear sum attack and higher order differential attack. In addition, we show the security of CRYPTON, E2, and RIJNDAEL against linear sum attack using the algorithm.

In this paper, the Linear Exponential Quadratic Gaussian with Loop Transfer Recovery (LEQG/LTR) methodology is employed for the design of high performance induction motor servo systems. In addition, we design a speed sensorless induction motor vector controlled driver with both the extended Kalman filter and the LEQG/LTR algorithm. The experimental realization of an induction servo system is given. Compared with the traditional PI and LQG/LTR methods, it can be seen that the system output sensitivity for parameter variations and the rising time for larger command input of the proposed method can be significantly reduced.

The explicit formula for the coefficients of maximally linear digital differentiators is derived by the use of Taylor series. A modification in the formula is proposed to extend the effective passband of the differentiator with the same number of coefficients.

In various digital wireless communication systems, it is known that turbo coding provides an error rate performance within a few tenths of a dB of the theoretical Shannon limit. The error correcting capability of turbo coding is attractive for a recording code in a digital magnetic recording system. The performance of a partial response maximum-likelihood (PRML) system with any recording code is degraded by many undesirable factors such as linear and nonlinear distortions. For improving the performance of the PRML system, it is useful to adopt a high-order PRML system or high rate code in general. In this paper, the two-track recording system using turbo coding which can increase the coding rate over 1 and improve the performance is proposed. Turbo-coding provides a near-ML performance by the suboptimum symbol-by-symbol maximum a posteriori probability (MAP) decoding algorithm. Our proposed turbo-coded class 4 partial response (PR4) systems use the rate 4/6, 8/10 and 16/18 turbo codes for high-density two-track digital magnetic recording. The error rate performance is obtained by computer simulation, taking account of the partial erasure which is a prominent nonlinear distortion in high-density recording. As a result, the proposed systems are hardly affected by partial erasure and maintains good performance compared with the conventional NRZ coded PR4ML system.

The complexity of designing communication protocols has lead researchers to develop various techniques for designing and verifying protocols. One of the most important techniques is a compositional technique. Using a compositional technique, a large and complex protocol is designed and verified by composing small and simple protocols which are easy to handle, design and verify. Unlike the other compositional approaches, we propose compositional techniques for simultaneously composing service specifications and protocol specifications based on Formal Description Techniques (FDTs) called LOTOS. The proposed techniques consider alternative, sequential, interrupt and parallel composition of service specifications and protocol specifications. The composite service specification and the composite protocol specification preserve the original behaviour and the correctness properties of individual service specifications and protocol specifications. We use the weak bisimulation equivalence (), to represent the correctness properties between the service specification and the protocol specification. When a protocol specification is weak bisimulation equivalent to a service specification, the protocol satisfies all the logical properties of a communication protocol as well as provides the services that are specified in the service specification.

This paper presents an improved method of speaker verification using the sequential probability ratio test (SPRT), which can treat the correlation between successive feature vectors. The hidden Markov model with the mean field approximation enables us to consider the correlation in the SPRT, i. e. , using the mean field of previous state, probability computation can be carried out as if input samples were independent each other.

Recently, it is widely known that the partial response maximum-likelihood (PRML) system has attracted much attention as one of indispensable signal processing technique for achieving high density digital magnetic recording. But, the performance of PRML system is degraded by many undesirable causes in recording channel. For improving the performance, it is desirable to use any high order PRML system or high rate code. Our proposed two-track recording method increases the coding rate over 1, and contributes to decrease these degradation effects. The recording code in our system adopts a turbo code which provides a substantial near-ML performance by the suboptimum iterative decoding algorithm. In this paper, the turbo coded class four partial response (PR4) systems using the rate 4/6, 8/10 and 16/18 codes for high density two track digital magnetic recording are proposed. The error rate performance of the proposed system is obtained by computer simulation taking account of the partial erasure, which is one of nonlinear distortions at high densities. The performance of our system is compared with that of the conventional NRZ coded PR4ML system. The result shows that the proposed system is hardly affected by partial erasure and keeps good performance in high density recording. In especial, the proposed system using the rate 16/18 turbo code can achieve a bit error rate of 10-4 with SNR of approximately 12.2 dB less than the conventional NRZ coded PR4ML systems at a normalized linear density of 3.

With the knowledge of the syndromes Sa,b, 0a,b q-2, the exact error values cannot be determined by using the conventional (q-1)2-point discrete Fourier transform in the decoding of a plane algebraic-geometric code over GF(q). In this letter, the inverse q-point 1-dimensional and q2-point 2-dimensional affine Fourier transform over GF(q) are presented to be used to retrieve the actual error values, but it requires much computation efforts. For saving computation complexity, a modification of the affine Fourier transform is derived by using the property of the rational points of the plane Hermitian curve. The modified transform, which has almost the same computation complexity of the conventional discrete Fourier transform, requires the knowledge of syndromes Sa,b, 0 a,b q-2, and three more extended syndromes Sq-1,q-1, S0,q-1, Sq-1,0.

This paper shows the method of theoretical analysis for the bit error probability of the trellis-coded partial response continuous phase modulation (TCM-PR-CPM) over the correlated Rician fast frequency nonselective fading channel. In the analysis, the fading correlation of the channel and the effect due to finite interleaver are taken into account. By applying the method to the rate 1/2 (7, 2) trellis code with the raised cosine pulse of length 2 (2RC) partial response signaling, we show that the tighter upper bounds of the bit error rate are obtained than those in the preceding report.

A new UEP technique for image transmission using trellis code based on Hamming distance criterion has been proposed. The simulation results comparing the image quality and bit-rate for UEP and EEP have been provided. The results show that UEP performs better than EEP in terms of bit-rate without any significant depreciation in image quality.

This paper deals with a method of estimating the parameters and the order of a linear system using differential digital filters and the resultant. From the observed signals of the input and output of an objective system, we extract the differential signals from the zero order to an appropriate high order with the same phase characteristics, using several digital filters. On the assumption that the system order is known, we estimate the parameters of the transfer function and evaluate the estimation error bounds. We propose a criterion function generated by the product of the highest order coefficients and the resultant of the numerator and denominator of the estimated transfer function. Applying this criterion function, we can estimate the order of the objective system. The threshold corresponding to this criterion function is evaluated from the deviation in the frequency characteristics of the used differential filters and the error bound of the estimated parameters. In order to demonstrate the propriety of the proposed method, some numerical simulations are presented.

We analyze the dynamics of self-organizing cortical maps under the influence of external stimuli. We show that if the map is a contraction, then the system has a unique equilibrium which is globally asymptotically stable; consequently the system acts as a stable encoder of external input stimuli. The system converges to a fixed point representing the steady-state of the neural activity which has as an upper bound the superposition of the spatial integrals of the weight function between neighboring neurons and the stimulus autocorrelation function. The proposed theory also includes nontrivial interesting solutions.

Recently, many on-line control methods of partially observed discrete event systems(DES's) have been proposed. This paper proposes an algorithm for on-line control based on a supervisor under complete observation. It is shown that DES's controlled by the proposed on-line controller generate maximally controllable and observable sublanguages which include the supremal normal sublanguages. Moreover, computational complexity of the proposed algorithm is polynomial with respect to the numbers of the unobservable events and the state of the supervisor under complete observation.