This paper presents a heuristic algorithm called CLASSIC for the minimization of the control memory width in microprogrammed processors or the instruction memory width of application-specific VLIW (Very Long Instruction Word) processors. CLASSIC results in nearly optimal solutions with the time complexity of O(n2), where n denotes the number of microoperations. In this paper, we also propose the so-called incompleteness relations which are exploited for the minimization of the control memory width. Experiments using various examples have shown that CLASSIC always achieves smaller microprogram widths compared to the earlier techniques based on the maximal compatibility class or the minimal AND/OR set. The results show that CLASSIC can reduce the control memory width by 34.2% on average compared with a heuristic compatibility class algorithm.

This work presents a scalable and high performance prediction protocol for optical networks. In the proposed protocol, we develop a mathematical model to maintain the stability of a network system by prediction based on the traffic temporal locality property. All the critical factors, including transceiver tuning time, propagation delay, and processing time for dealing with control packets, are considered in the proposed prediction protocol. Furthermore, our protocol can resolve the bottlenecks attributed to control signaling and electronics processing. The performance evaluation reveals that the proposed scheme can yield the higher bandwidth efficiency and incur a lower packet delay than those of the TDM and conventional reservation schemes. Also, the proposed protocol can flexibly support any scaled network system such as MANs or LANs.

This paper studies the "usefulness" of initial conditions for distributed algorithms on anonymous networks. In the literature, several initial conditions such as making one vertex a leader, giving the number of vertex to each vertices, and so on, have been considered. In this paper, we study a relation between the initial condition by considering transformation algorithm from one initial condition to another. For such transformation algorithms, we consider in this paper, both deterministic and randomized distributed algorithms. For each deterministic and randomized transformation type, we show that the relation induces an infinite lattice structure among equivalence classes of initial conditions.

This paper proposes a fast method of calculating high-order backward Linear Prediction (LP) coefficients for wideband Code Excited LP (CELP) coders operating at around 16 kbit/s. The fast calculation is achieved by a recursive calculation for the high-order autocorrelation of the decoded signal. The recursive calculation can be employed thanks to a novel method of converting the autocorrelation of the decoded signal to that of the residual signal. High-order backward LP coefficients are computed from the autocorrelation of the residual signal using the Levinson-Durbin (LD) procedure. The conversion approximately performs inverse-filtering using LP coefficients representing a corresponding envelope spectrum. Due to the recursive calculation, the proposed fast calculation method achieves 30% to 45% reduction in computations to calculate the high-order backward LP coefficients compared to the conventional method. Subjective tests show that a wideband Multi-Pulse based CELP (MP-CELP) coder at 16 kbit/s with the proposed method achieves comparable coding quality to that with the conventional one with 35% reduction in computations needed for calculation of the backward LP coefficients.

This paper describes a jitter suppression technique for a clock multiplier IC that uses a phase-locked loop (PLL). It is shown that the jitter cutoff frequency of the jitter transfer function can be greatly improved by adding a surface acoustic wave (SAW) filter whose center frequency equals the input frequency. The jitter transfer function is mainly determined by the characteristics of the SAW filter. Therefore, the clock multiplier IC can be set at a high loop gain to minimize the jitter generation without increasing the jitter cutoff frequency. The use of a clock multiplier IC that was fabricated with Si bipolar technology and a SAW filter with the center frequency of 155.52 MHz and a quality (Q) factor of 1500 results in a very low jitter generation of 3.5 mUI rms and an extremely low jitter cutoff frequency of about 50 kHz when the clock multiplier converts a clock frequency of 155.52 MHz into a 2.48832-GHz signal.

Mathematical proof for the equivalent edge currents for physical optics (POEECs) is given for plane wave incidence and the observer in far zone; the perfect accuracy of POEECs for plane wave incidence as well as the degradation for the dipole source closer to the scatterer is clearly explained for the first time. POEECs for perfectly conducting plates are extended to those for impedance plates.

A min-wise independent permutation family is known to be an efficient tool to estimate similarity of documents. Toward good understanding of min-wise independence, we present a characterization of exactly min-wise independent permutation families by size uniformity, which represents certain symmetry of the string representation of a family. Also, we present a general construction strategy which produce any exactly min-wise independent permutation family using this characterization.

We studied Si and Mg doping characteristics in cubic GaN and fabricated a light emitting diode of cubic GaN on a GaAs substrate by metalorganic vapor-phase epitaxy. The diode structure consisted of undoped and Mg-doped GaN stacking layers deposited on Si-doped GaN and AlGaN layers. The electron-beam-induced-current signal and current injection characteristics of this diode structure were measured. There was a peak at the interface between the Mg-doped and undoped GaN in the electron-beam-induced-current signal. This shows successful growth of the p-n junction. Light emitting operation was achieved by currents injected through the conducting GaAs substrate of this diode at room temperature. We observed electroluminescence below the bandgap energy of cubic GaN with a peak at 2.6 eV.

This paper presents a non-interactive and optimally resilient distributed multiplication scheme. By non-interactive we mean that the players need to use outgoing communication channels only once without the need to synchronize with the other players as long as no disruption occurs. Our protocol withstands corrupt players up to less than the half of the players, so it provides optimal resiliency. Furthermore, the shared secrets are secure even against infinitely powerful adversaries. The security is proven under the intractability assumption of the discrete logarithm problem. Those properties are achieved by using an information theoretically secure non-interactive verifiable secret sharing as a kind of non-interactive proof system between a single prover and distributed verifiers. Compared to a former interactive solution in the same setting, the cost is an increase in local computation and communication complexity that is determined by the factor of the threshold used in the verifiable secret sharing.

We have developed a new efficient neural network-based algorithm for Alife application in a competitive world whereby the effects of interactions among organisms are evaluated in a weak form by exploiting the position of nearest food elements into consideration but not the positions of the other competing organisms. Two online learning algorithms, an instructive ASL (adaptive supervised learning) and an evaluative feedback-oriented RL (reinforcement learning) algorithm developed have been tested in simulating Alife environments with various neural network algorithms. The constructive compound neural network algorithm FuzGa guided by the ASL learning algorithm has proved to be most efficient among the methods experimented including the classical constructive cascaded CasCor algorithm of [18],[19] and the fixed non-constructive fuzzy neural networks. Adopting an adaptively selected best sequence of feedback action period Δα which we have found to be a decisive parameter in improving the network efficiency, the ASL-guided FuzGa had a performance of an averaged fitness value of 541.8 (standard deviation 48.8) as compared with 500(53.8) for ASL-guided CasCor and 489.2 (39.7) for RL-guided FuzGa. Our FuzGa algorithm has also outperformed the CasCor in time complexity by 31.1%. We have elucidated how the dimensionless parameter food availability FA representing the intensity of interactions among the organisms relates to a best sequence of the feedback action period Δα and an optimal number of hidden neurons for the given configuration of the networks. We confirm that the present solution successfully evaluates the effect of interactions at a larger FA, reducing to an isolated solution at a lower value of FA. The simulation is carried out by thread functions of Java by ensuring the randomness of individual activities.

We present efficient all-to-all personalized communication algorithms for a 2D torus in wormhole-routed networks. Our complete exchange algorithms reduce the number of start-up by a factor of up to 2, which is a good metric for network performance in wormhole networks. Our algorithms divide the whole network into 22 networks, giving two contention-free networks with N/2N/2. After specially designated nodes called master nodes have collected messages, whose destinations are the rest of the basic cells, only master nodes perform complete exchange with a reduced network size. When finished with this complete exchange among master nodes, these nodes distribute messages to the rest of the master nodes, which results in the desired complete exchange. Then, we present a modified algorithm that further reduces the data transmission time sacrificing the start-up time. After we present our new algorithms, we analyze time complexities and compare several algorithms. We show that our practical algorithm is efficient by a factor of 2 in the required start-up time which means that our algorithms are suitable for wormhole-routed networks.

This paper proposes a method of automatically eliciting knowledge which is used to detect feature interactions in telecommunication services. With conventional methods, the knowledge is provided manually. With the proposed method, the knowledge is automatically elicited as service constraints. In telecommunication systems, when a new service is added, new state transitions are created. In case of new service, the new state should be reached in the state transitions. On the other hand, some states of existing services should not be reached. These constraints can be considered as knowledge for detecting feature interactions. This paper also proposes a scenario for detecting feature interactions using elicited knowledge. This scenario was confirmed as effective.

This paper describes a scheme to capture a wide-view image using a camera setup with uncalibrated cameras. The setup is such that the optical axes are pointed in divergent directions. The direction of view of the resulting image can be chosen freely in any direction between these two optical axes. The scheme uses eight-parameter perspective transformations to warp the images, the parameters of which are obtained by using a relative orientation algorithm. The focal length and scale factor of the two images are estimated by using Powell's multi-dimensional optimization technique. Experiments on real images show the accuracy of the scheme.

There are the following three targets to be achieved in a software project from the three viewpoints of process management (or progress management), cost management, and quality management for software project to be successful: (a) drafting a software development plan based on accurate estimation, (b) early detection of risks that the project includes based on correct situation appraisal, (c) early avoidance of risks that the project includes. In this paper, the authors propose a method and facilities to project risks in a software project through Kepner-Tregoe program, and propose schedule re-planning by using genetic algorithm for avoiding the projected risks. Furthermore the authors show, from the results of execution of the system, that the system is effective in early avoidance of risks that the software project includes.

We consider the performance of hyperelliptic curve cryptosystems over the fields Fp vs. F2n. We analyze the complexity of the group law of the jacobians JC(Fp) and JC(F2n) and compare their performance taking into consideration the effectiveness of the word size (32-bit or 64-bit) of the applied CPU (Alpha and Pentium) on the arithmetic of the definition field. Our experimental results show that JC(F2n) is faster than JC(Fp) on an Alpha, whereas JC(Fp) is faster than JC(F2n) on a Pentium. Moreover, we investigate the algorithm of the jacobian and the definition-field arithmetic to clarify our results from a practical point of view, with theoretical analysis.

We consider the problem of finding a minimum weight k-connected spanning subgraph of a given edge-weighted graph G for k=3. The problem is known to be NP-hard for k 2, and there are an O(n2m) time 3-approximation algorithm due to Nutov and Penn and an O(n8) time 2-approximation algorithm due to Dinitz and Nutov, where n and m are the numbers of vertices and edges in G, respectively. In this paper, we present a 7/3-approximation algorithm which runs in O(n2m) time.

This note investigates the characterizing properties of the level sets of an M-convex function introduced by Murota.

Higher order delta-sigma (ΔΣ) modulator with one bit quantizer is known as one of the easiest method to gain a high resolution A/D converter without the need of accurately matched components. However, stability of higher order ΔΣ modulator is still a problem during the design and implementation process. Stabilizing higher order modulator requires the proper choice of integrator gains. In this paper, a new approach on ΔΣ modulator stability analysis which based on the system auto-correlation function is proposed, and equation of NTF power integration is derived out. The specification of equation related to input signal amplitude and output quantization level is discussed. Combining with system control theory, the stability of higher order modulator (2nd and 3rd order) is evaluated. Matlab simulation confirm the proposed method. It offers an evaluation method for the choice of the in-loop integrator gains which ensure the modulator operates under the stable status, and is able to be used for designing stable higher order ΔΣ analog-to-digital converters.

We first describe fundamental results about submodular functions and submodular flows, which lay a basis for devising efficient algorithms for submodular flows. We then give a comprehensive survey on algorithms for submodular flows and show some possible future research directions.

We review public-key cryptosystems from lattice problems, which are inspired by Ajtai's remarkable result, and consider their security from the point of view of both theory and practice. We also survey recent results on the power of the lattice reduction algorithm in cryptanalysis.