This paper addresses the problem of multiple multicast in WDM networks. It presents three efficient algorithms to construct an optimal/sub-optimal multicast tree for each multicast and minimise the network congestion on wavelengths. The first two algorithm achieve an optimal network congestion for a specific class of networks whose all wavelengths are globally accessible and convertible at a unit cost. The third algorithm produces an approximation solution for the general case of WDM networks.

In this paper, we present a simple codeword length generation algorithm and its hardware implementation. The proposed technique is based on the dividing the Huffman table as two parts; with leading 0'bits and following bits. The method is shown to be efficient in the memory requirement and searching speed since only logic gates are needed in the implementation and searching can be process parallel without looking up the memory table. The total equivalent gates for the implementation are about only 100 gates and critical path delay is 10 ns. The results of experiments show that the proposed algorithm has a very high speed and a good performance. The designed blocks are synthesized by Compass synthesis with 0.5 µm CMOS, 3.3V, technology.

A distributed computing system consists of processing elements, communication links, memory units, data files, and programs. These resources are interconnected via a communication network and controlled by a distributed operating system. The distributed program reliability (DPR) in a distributed computing system is the probability that a program which runs on multiple processing elements and needs to retrieve data files from other processing elements will be executed successfully. This reliability varies according to 1) the topology of the distributed computing system, 2) the reliability of the communication edges, 3) the data files and programs distribution among processing elements, and 4) the data files required to execute a program. In this paper, we show that computing the distributed program reliability on a star distributed computing system is #P-complete. A polynomially solvable case is developed for computing the distributed program reliability when some additional file distribution is restricted on the star topology. We also propose a polynomial time algorithm for computing the distributed program reliability with approximate solutions when the star topology has no the additional file distribution.

In this paper, by making good use of the parallel-transit-evaluation algorithm and sparsity of the connection between neurons, a pipeline structure is successfully introduced to the sequential Boltzmann machine processor. The novel structure speeds up nine times faster than the previous one, with only the 12% rise in hardware resources under 10,000 neurons. The performance is confirmed by designing it using 1.2 µm CMOS process standard cells and analyzing the probability of state-change.

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.

In this paper, the Lapped Orthogonal Transform (LOT) with unequal length basis function is considered. The proposed unequal length LOT (ULLOT) has both long basis of length 2M and short basis of length M, while the lengths of all bases of the conventional LOT are 2M. A new class of LOT can be constructed with some modifications of Malvar's Fast LOT. Therefore, the fast algorithm for the Discrete Cosine Transform (DCT) will surely facilitate the computation of the ULLOT. Although the computational complexity of the ULLOT is always lower than that of the LOT, there exist some cases where the coding gain of the ULLOT becomes slightly higher than that of the LOT. Its ability to reduce ringing artifacts is an attractive feature as well. The size-limited structure for the finite length signal is investigated and the ULLOTs are tested on image coding application. The simulation results confirm the validity of the proposed ULLOT.

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.

In this paper, a new multicast routing method for layered streams is proposed. This method is an extension of the weighted greedy algorithm (WGA) and uses two kinds of weight values to refine the link distance. It can cope with dynamic change in the group members without multicast tree re-construction. The method is compatible with the RSVP and can be utilized in existing shared tree type routing protocols such as CBT and PIM sparse mode. The network resources can be utilized efficiently; furthermore, the loss rate of member's requests to receive more layers can be reduced by this routing method when a sufficient number of nodes have the packet filtering function and a sufficient number of hops is permitted.

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 proposes a thresholding based segmentation method aided by Kleene Algebra. For a given image including some regions of interest (ROIs for short) with the coherent intensity level, assume that we can segment each ROI on applying thresholding technique. Three segmented states are then derived for every ROI: Shortage denoted by logic value 0, Correct denoted by 1 and Excess denoted by 2. The segmented states for every ROI in the image can be then expressed on a ternary logic system. Our goal is then set to find "Correct (1)" state for every ROI. First, unate function, which is a model of Kleene Algebra, based procedure is proposed. However, this method is not complete for some cases, that is, correctly segmented ratio is about 70% for three and four ROI segmentation. For the failed cases, Brzozowski operations, which are defined on De Morgan algebra, can accommodate to completely find all "Correct" states. Finally, we apply these procedures to segmentation problems of a human brain MR image and a foot CT image. As the result, we can find all "1" states for the ROIs, i. e. , we can correctly segment the ROIs.

This paper describes a high-power and low-distortion AlGaAs/GaAs HFET amplifier developed for digital cellular base station system. We proved experimentally that distortion characteristics such as IMD (Intermodulation Distortion) or NPR (Noise Power Ratio) are drastically degraded when the absolute value of the drain bias circuit impedance at low frequency are high. Based on the experimental results, we have designed the drain bias circuit not to influence the distortion characteristics. The developed amplifier employed two pairs of pre-matched GaAs chips mounted on a single package and the total output-power was combined in push-pull configuration with a microstrip balun circuit. The push-pull amplifier demonstrated state-of-the-art performance of 140 W output-power with 11.5 dB linear gain at 2.2 GHz. In addition, it exhibited extremely low distortion performance of less than 30 dBc at two-tone total output-power of 46 dBm. These results indicate that the design of the drain bias circuit is of great importance to achieve improved IMD characteristics while maintaining high power performance.

This paper proposes an adaptive microphone array using blind deconvolution. The method realizes an signal enhancement based on the combination of blind deconvolution, synchronized summation and DSA (Delay-and-Sum Array) method. The proposed method improves performance of estimation by the iterative operation of blind deconvolution using a cost-function based on the coherency function.

Recently, Miura introduced a construction method of one-point algebraic geometry codes on singular curves, which is regarded as a generalization of one on nonsingular curves, and enables us to construct codes on wider class of algebraic curves. However, it is still not clear whether there really exist singular curves on which we can construct good codes that are never obtained from nonsingular curves. In this paper, we show that for fixed designed minimum distance in a wide range, the dimension of codes on a singular curve is smaller than or equal to that of the codes on its normalization, and the number of check symbols of the former codes is larger than that of the latter codes. This implies the optimality of nonsingular curves for code construction.

A timing synchronization is required in the mobile station to determine the correct transmission timing of the mobile-to-base bursts. In this letter, a timing synchronization technique using the reliability check and smoothing algorithm is proposed for the GSM receiver. The reliability check scheme extends the usefulness of this algorithm into low SNR region. And also smoothing algorithm is carried out by a first-order filter with an asymmetric step size. Simulation results show that the proposed algorithm is adequate for timing recovery of GSM modem.

An optimun design for N(arbitrary)-sheet capacitive Jaumann elctromagnetic (EM) wave absorber, using genetic algorithm will be presented. This algorithm is a random optimization method based on the genetic relation in the human being. We show the bandwidth for two-sheet capacitive Jaumann absorber can be expanded even more than 108% showed by knott, by using this algorithm and without imposing the double-notch design criteria. We also show that our results approaches knott's results when we restrict the characteristic impedances and lengths of the lines to vary within a very short range. We also design one-sheet and three-sheet capacitive Jaumann absorbers. The only restriction used here is about the meaningful range for the design variables. The goal of this algorithm is that we can impose arbitrary restriction about the range of the variation of the variables. So we can see the performance behaviour with the range dimension of the variables, and we can obtain different optimum results for different ranges. Finally we obtain a 20-dB attenuation bandwidth more than 145% for one-sheet, 173% for two-sheet (compare with 108% obtained in [1]) and 193% for three-sheet capacitive Jaumann EM absorbers, with some acceptable short range for the variables. We design the one-sheet and two-sheet capacitive Jaumann absorbers at low frequency and the three-sheet at high frequency. The 20-dB attenuation bandwidth obtained for the one-sheet and two-sheet capacitive Jaumann absorbers are respectively, from 10 to 77 MHz and, from 4 to 61 MHz. For the three-sheet capacitive Jaumann absorber the 20-dB attenuation bandwidth obtained is, from 0.8 GHz to 280 GHz.

Effects of the model order estimation error in the TLS-ESPRIT algorithm were investigated. It was found that if the model order is overestimated true signal parameters are preserved even though spurious signals of which power values are negligibly small appear, whereas if the model order is underestimated some signals degenerate to each others, resulting in the erroneous estimates.

In this paper, we consider new and general models for imperfect sources of randomness, and show how to obtain quasi-random sequences from such sources. Intuitively, quasi-random sequences are sequences of almost unbiased elements over a finite set. Our model is as follows: Let A be a finite set whose number of elements is a power of 2. Let 1/|A| δ 1 be a constant. The source outputs an element on A with probability at most δ, depending on outputs made by itself so far. From the definition, our sources output at least two elements with nonzero probability. This model is very general, because the source may output only two elements of A with nonzero probability, and the other elements with probability 0. This ability becomes a big difficulty for generating quasi-random sequences. All the methods for the existing models such as PRB-models and δ-sources fail to generate quasi-random sequences from our models. We here give a new algorithms which generates almost unbiased elements over A from such models.

A trinary-phased array, in which a phase quantization unit of phase shifters is 120 degrees is examined. The phase quantization unit of 120 degrees is the roughest value in practical phased array applications. Despite its rough phase quantization, the sidelobe level of less than -9 dB is attained by a genetic algorithm approach.

In this paper, the authors present general views of computer vision and image processing based on optimization. Relaxation and regularization in both broad and narrow senses are used in various fields and problems of computer vision and image processing, and they are currently being combined with general-purpose optimization algorithms. The principle and case examples of relaxation and regularization are discussed; the application of optimization to shape description that is a particularly important problem in the field is described; and the use of a genetic algorithm (GA) as a method of optimization is introduced.

We apply two acceleration techniques for the backpropagation algorithm to an iterative gradient descent algorithm called the network inversion algorithm. Experimental results show that these techniques are also quite effective to decrease the number of iterations required for the detection of input vectors on the classification boundary of a multilayer perceptron.