This paper discusses the generalized mutual exclusion problem defined by H. Kakugawa and M. Yamashita. A set of processes shares a set of resources of an identical type. Each resource must be accessed by at most one process at any time. Each process may have different accessible resources. If two processes have no common accessible resource, it is reasonable to ensure a condition in resource allocation, which is called allocation independence in this paper, i. e. , resource allocation to those processes must be performed without any interference. In this paper, we define a new structure, sharing structure coterie. By using a sharing structure coterie, the resource allocation algorithm proposed by H. Kakugawa and M. Yamashita ensures the above condition. We show a necessary and sufficient condition of the existence of a sharing structure coterie. The decision of the existence of a sharing structure coterie for an arbitrary distributed system is NP-complete. Furthermore, we show a resource allocation algorithm which guarantees the above requirement for distributed systems whose sharing structure coteries do not exist or are difficult to obtain.

This paper describes the error probability of the second order BAM estimated by a computer simulation and an analytical calculation method. The computer simulation suggests that the iterations to retrieve a library pattern almost converge within four times and the difference between once and twice is much larger than that between twice and four times. The error probability at the output of the second iteration is estimated by the analytical method. The effect of the noise bits is also estimated using the analytical method. The BAM with larger n is more robust for the noise. For example, the noise bits of 0.15n cause almost no degradation of the error probability when n is larger than 100. If the error probability of 10-4 is allowable, the capacity of the second order BAM can be increased by about 40% in the presence of 0.15n noise bits when n is larger than 500.

The formulation of the wall admittance of a circular microstrip antenna by the spectral domain method is presented. The circular microstrip antenna is calculated using the cavity model. The electromagnetic fields within the antenna cavity are determined from the impedance boundary condition at the side aperture. The contribution from the region outside the antenna is taken into account by the wall admittance. The wall admittance is defined by the magnetic field produced by the equivalent magnetic current at the aperture. The magnetic field is calculated by the spectral domain method. The wall admittances obtained by this method are compared with the results calculated by Shen. The calculated input impedances of the microstrip antenna agree fairly well with the experimental data for the substrate thickness of up to 0.048λg. The formulation of wall admittance presented here is easily applicable to arbitrarily shaped microstrip antennas.

Frequency chirping induced in an electorabsorption (EA) modulator can degrade transmission performance because of the chromatic dispersion of fiber. This letter studies the frequency chirping in an EA modulator from the viewpoint of the influence of the modulation bandwidth. Both simulations and experiments, in which fiber transmission was carried out applying modulation signals of different bandwidths to an EA modulator, show that a large bandwidth causes small degradation in the transmission performance. This result is attributed to the short chirping time that occurs when a large bandwidth signal is applied.

We are concerned with a CDMA cellular system with unbalanced traffic environment such that a cell with high traffic should be assigned a frequency additional to the common one shared with its neighboring cells. To remove quality-dropping inter-cell hard handoffs, the cell with high traffic was first partitioned into three regions. Then, the common frequency is assigned in the outermost region, and the additional frequency is operated in the innermost region, whereas both the common frequency and the additional frequency are operated in the middle region. This frequency assignment strategy is shown not only to remove inter-cell hard handoffs without requiring extra hardware, but also to reduce intra-cell hard handoffs.

In this paper, we propose an efficient method of constructing states in bottom-up tree pattern matching with dynamic programming technique for optimal code generation. This method can be derived from precomputing the analysis which is needed for constructing states. The proposed scheme is more efficient than other scheme because we can avoid unfruitful tests in constructing states at compile time. Furthermore, the relevant analyses needed for this proposal are largely achieved at compile-compile time, which secures actual efficiency at compile time.

This paper proposes a new distortion analysis method for frequency-dependent FET amplifiers, which uses a novel Frequency-Dependent Complex Power Series (FDCPS) model. This model consists of a frequency-independent nonlinear amplifier represented by an odd-order complex power series and frequency-dependent input and output filters. The in-band frequency characteristics of the saturation region are represented by the frequency-dependent output filter, while the in-band frequency characteristics of the linear region are represented by the frequency-dependent input and output filters. In this method, the time-domain analysis is carried out to calculate the frequency-independent nonlinear amplifier characteristics, and the frequency-domain analysis is applied to calculate the frequency-dependent input and output filter characteristics. The third-order intermodulation (IM3) calculated by this method for a GaAs MESFET amplifier is in good agreement with the numerical results obtained by the Harmonic Balance (HB) method. Moreover, the IM3 calculated by this method also agrees well with the measured data for an L-band 3-stage GaAs MESFET amplifier. It is shown that this method is effective for calculating frequency-dependent distortion of a nonlinear amplifier with broadband modulation signals.

The magnetic shielding performance of the high-Tc superconducting (HTS) plate in a mixed state has been investigated numerically. By taking account of the crystallographic anisotropy of the HTS plate, the axisymmetric shielding plate is assumed to have a multiple thin-layer structure. Under the assumptions, the governing equations of the shielding current density can be expressed in terms of a scalar function. The numerical code to integrate the equation has been developed and, by use of the code, the shielding current density and the damping coefficient are calculated for the axisymmetric HTS plate in a mixed state. The results of computations show that the shielding current density localizes around the edge under the high-frequency magnetic field. With an increasing frequency of the applied magnetic field, the localization becomes remarkable and the shielding current density becomes larger until the flux flow occurs. In addition, the magnetic shielding performance of the HTS plate drastically changes with time under the low-frequency magnetic field below 100 Hz, whereas it is almost time-independent under the high-frequency magnetic field. Moreover, it turns out that the HTS plate can shield ac magnetic fields with a high frequency even if it remains in a mixed state.

Speeding up modular inversion is one of the most important subjects in the field of information security. Over the elliptic curve -- on the prime finite field in particular goals -- public-key cryptosystems and digital signature schemes frequently use modular inversion if affine coordinates are selected. In the regular computer environment, most data transmission via networks and data storage on memories as well as the operation set of processors are performed in multiples of eight bits or bytes. A fast modular multiplication algorithm that matches these operation units for DSP was proposed to accelerate the Montgomery method by Dusse and Kaliski. However, modular inversion algorithms were developed using bit by bit operation and so do not match the operation unit. This paper proposes two techniques for modular inversion that suits any arbitrary processing unit. The first technique proposes a new extended GCD procedure without any division. It can be constructed by the shifting, adding and multiplying operations, all of which a Montgomery modular arithmetic algorithm employs. The second technique can reduce the delay time of post processing in the modular inversion algorithm. In particular, it is of great use for the modular inversion defined in the Montgomery representation. These proposed techniques make modular inversion about 5. 5 times faster.

This paper introduces an alternating rebound Turing machine and investigates some fundamental properties of it. Let DRTM (NRTM,ARTM) denote a deterministic (nondeterministic and alternating) rebound Turing machine, and URTM denote an ARTM with only universal states. We first investigate a relationship between the accepting powers of rebound machines and ordinary machines, and show, for example, that (1) there exists a language accepted by a deterministic rebound automaton, but not accepted by any o(log n) space-bounded alternating Turing machine, (2) alternating rebound automata are equivalent to two-way alternating counter automata, and (3) deterministic rebound counter automata are more powerful than two-way deterministic counter automata. We next investigate a relationship among the accepting powers of DRTM's, NRTM's, URTM's and ARTM's, and show that there exists a language accepted by alternating rebound automata, but not accepted by any o(logn) space-bounded NRTM (URTM). Then we show that there exists an infinite space hierarchy for DRTM's (NRTM's, URTM's) with spaces below log n. Furthermore, we investigate a relationship between the strong and weak modes of space complexity, and finally show that the classes of languages accepted by o(logn) space-bounded DRTM's (NRTM's, URTM's) are not closed under concatenation and Kleene .

We propose two fault-tolerant broadcasting schemes in star graphs. One of the schemes can tolerate up to n2 faults of the crash type in the n-star graph. The other scheme can tolerate up to (n3d1)/2 faults of the Byzantine type in the n-star graph, where d is the smallest positive integer satisfying nd!. Each of the schemes is designed for the single-port mode, and it completes the broadcasting in O(n log n) time. These schemes are time optimal. For the former scheme we analyze the reliability in the case where faults of the crash type are randomly distributed. It can tolerate (n!)α faults randomly distributed in the n-star graph with a high probability, where α is any constant less than 1.

A binary moment diagram, which was proposed for arithmetic circuit verification, is a directed acyclic graph representing a function from binary-vectors to integers (f : {0,1}n Z). A multiplicative binary moment diagram is an extension of a binary moment diagram with edge weights attached. A multiplicative binary moment diagram can represent addition, multiplication and many other functions with polynomial numbers of vertices. Lower bounds for division, however, had not been investigated. In this paper, we show an exponential lower bound on the number of vertices of a multiplicative binary moment diagram representing a quotient function or a remainder function.

Two algorithms for minimum cut linear arrangement of a class of graphs called p-q dags are proposed. A p-q dag represents the connection scheme of an adder tree, such as Wallace tree, and the VLSI layout problem of a bit slice of an adder tree is treated as the minimum cut linear arrangement problem of its corresponding p-q dag. One of the two algorithms is based on dynamic programming. It calculates an exact minimum solution within nO(1) time and space, where n is the size of a given graph. The other algorithm is an approximation algorithm which calculates a solution with O(log n) cutwidth. It requires O(n log n) time.

All-terminal reliability is one of the measurements to evaluate the reliability for network systems. Since it may need exponential time of the network size to compute the exact value of all-terminal reliability, it is important to calculate its tight approximate value, especially its lower bound, at a moderate calculation time. Ramanathan and Colbourn have proposed approaches for lower bounds of all-terminal reliability by using arc-packings but their approaches are not detailed enough to construct concrete algorithms and they have just evaluated their approaches for a particular network. In this paper, we construct concrete algorithms based on their approaches and suggest new algorithms. We also execute computational experiments for general networks in order to evaluate the lower bounds by the algorithms and show the effectiveness of our new algorithms.

This paper presents a new approach to designing arithmetic circuits by using a graph-based evolutionary optimization technique called Evolutionary Graph Generation (EGG). The key idea of the proposed method is to introduce a higher level of abstraction for arithmetic algorithms, in which arithmetic circuit structures are modeled as data-flow graphs associated with specific number representation systems. The EGG system employs evolutionary operations to transform the structure of graphs directly, which makes it possible to generate the desired circuit structure efficiently. The potential capability of EGG is demonstrated through an experiment of generating constant-coefficient multipliers.

A novel combinatorial optimization algorithm called "Gradual neural network (GNN)" is presented for NP-complete broadcast scheduling problems in packet radio (PR) networks. A PR network provides data communications services to a set of geographically distributed nodes through a common radio channel. A time division multiple access (TDMA) protocol is adopted for conflict-free communications, where packets are transmitted in repetition of fixed-length time-slots called a TDMA cycle. Given a PR network, the goal of GNN is to find a TDMA cycle with the minimum delay time for each node to broadcast packets. GNN for the N-node-M-slot TDMA cycle problem consists of a neural network with N M binary neurons and a gradual expansion scheme. The neural network not only satisfies the constraints but also maximizes transmissions by two energy functions, whereas the gradual expansion scheme minimizes the cycle length by gradually expanding the size of the neural network. The performance is evaluated through extensive simulations in benchmark instances and in geometric graph instances with up to 1000 vertices, where GNN always finds better TDMA cycles than existing algorithms. The result in this paper supports the credibility of our GNN algorithm for a class of combinatorial optimization problems.

This paper presents an efficient algorithm to compute the characteristic polynomial of a polynomial matrix. We impose the following condition on given polynomial matrix M. Let M0 be the constant part of M, i. e. M0 M ( mod (y,,z)), where y,,z are indeterminates in M. Then, all eigenvalues of M0 must be distinct. In this case, the minimal polynomial of M and the characteristic polynomial of M agree, i. e. the characteristic polynomial f(x,y,,z) | x E M | is the minimal degree (w. r. t. x) polynomial satisfying f(M,y,,z) 0. We use this fact to compute f(x,y,,z). More concretely, we determine the coefficients of f(x,y,,z) little by little with basic matrix operations, which makes the algorithm quite efficient. Numerical experiments are given to compare the algorithm with conventional ones.

In this paper, we focus on the evaluation of the Erlang capacity for multimedia DS-CDMA systems supporting the multi-class services with different transmission rates, bit error rates, traffic activity factors in the reverse link. The number of concurrent users of the corresponding service group is modeled as a K-dimension Markov chain. Then, the Erlang capacity for the multimedia system can be found based on a K-dimension M/M/m loss system. For an IS-95 type DS-CDMA system, supporting voice/data services, the capacity bounds are depicted in conjunction with the 2-dimensional Markov chain. Furthermore, it is observed that the Erlang capacity with respect to the each service group should be balanced to enhance the total system Erlang capacity. Finally, the channel reservation scheme is considered to increase the total system Erlang capacity.

We propose an H-plane manifold-type triplexer with closely arranged junctions. Broadband characteristics for each bands are obtained by arranging filters closely near the end of the common waveguide. Three fundamental and sufficient parameters are introduced for numerical optimizations to determine the configuration of the broadband triplexer. The configuration including closely arranged junctions requires an generalized scattering matrix (GS matrix) of an asymmetric cross junction to simulate and design. We expand the mode matching technique (MMT) to be able to analyze this kind of discontinuities by joining two asymmetric steps discontinuities to a symmetric cross junction. This is suitable expressions for numerical calculations. The characteristics of the whole triplexer are obtained by cascading GS matrices of the corresponding discontinuities. The experimental results of the fabricated triplexer were compared with the simulated data, and the results agree well with the simulated one. The characteristics of the fabricated triplexer satisfy the request of the broad band operation and high power-handling capability.

In this paper, a new hierarchical block matching algorithm using mean and difference pyramids is presented. The detection of motion vectors at each level of the pyramid is accomplished by selectively eliminating the candidate motion vectors that cannot provide the best match at the next lower level. The remaining motion vectors at each level are propagated and used as the initial motion vectors at the next lower level. Therefore, the possibility of falling into local minima can be significantly reduced. The simulation results show that the proposed method has excellent performance with reduced computational complexity.