The facility layout problem is one of the most fundamental quadratic assignment problems in operations research. In this paper, we present an improved genetic algorithm for solving the facility layout problem. In our computational model, we propose several improvements to the basic genetic procedures including conditional crossover and mutation. The performance of the proposed method is evaluated on some benchmark problems. Computational results showed that the improved genetic algorithm is capable of producing high-quality solutions.

In this paper, we propose a new algorithm for calculating the exact poles of the admittance matrix of RLCG interconnects. After choosing dominant poles and corresponding residues, each element of the exact admittance matrix is approximated by partial fraction. A procedure to obtain the residues that guarantee the passivity is also provided, based on experimental studies. In the procedure the residues are calculated by using the least squares method so that the partial fraction matches each element of the exact admittance matrix in the frequency-domain. From the partial fraction representation, the asymptotic equivalent circuit models which can be easily simulated with SPICE are synthesized. It is shown that an efficient model-order reduction is possible for short-length interconnects.

In this paper, we propose an adaptive algorithm based on accumulated signal processing, which could be applicable to Post-FFT-type OFDM adaptive array antennas. Proposed scheme calculates the weight of each element at a particular instant t, by considering both post- and pre-received symbols. Because of the use of additional forthcoming information on channel behavior in the weight calculation scheme, one can expect an improved performance in fast fading conditions by using the proposed adaptive algorithm. This paper also discusses the application of the proposed adaptive algorithm to OFDM adaptive array. In OFDM application, a few subchannels are being used to transmit pilot symbols, and at the receiver, the proposed adaptive algorithm is applied to those pilot subchannels, and interpolates the weights for the data subchannels which are allocated between the pilot subchannels. Finally, the system performance improvement with the application of the proposed adaptive algorithm is verified by computer simulation.

In this paper, an efficient architecture for an adaptive Reed-Solomon decoder is presented, where the block length n and the message length k can be varied from their minimum allowable values up to their selected values. This eliminates the need of inserting zeros before decoding shortened RS codes. And the error-correcting capability t can be changed adaptively to channel state at every codeword block. The decoder allows efficient decoding in both burst mode and continuous mode, and it permits 3-step pipelined processing based on the modified Euclid's algorithm. Each step in decoding is designed to be clocked by a separate clock. Thus, each step can be efficiently pipelined with no help of multiplexing. Also, it makes it possible to employ no additional buffer even when the decoder input and output clocks are different. The adaptive RS decoder over GF(28) having the error-correcting capability of upto 10 has been designed in VHDL, and successfully synthesized in an FPGA chip. It can be used in a wide range of applications because of its versatility.

We discuss a typical profile of the k-error linear complexity for balanced binary exponent periodic sequences and the number of periodic distinct sequences by their profiles. A numerical example with period 16 is also shown.

We consider the multicast routing problem for large-scale wavelength division multiplexing (WDM) optical networks where transmission requests are established by point-to-multipoint connections. To realize multicast routing in WDM optical networks, some nodes need to have light (optical) splitting capability. A node with splitting capability can forward an incoming message to more than one output link. We consider the problem of minimizing the number of split-capable nodes in the network for a given set of multicast requests. The number of wavelengths is fixed and given a priori. We propose a genetic algorithm that exploits the combination of alternative shortest paths for the given multicast requests in order to minimize the number of required split-capable nodes. This algorithm is examined for two realistic networks constructed based on the locations of major cities in Ibaraki Prefecture and those in Kanto District in Japan. Our experimental results show that the proposed algorithm can reduce more than 10% of split-capable nodes compared with other routing algorithms whereby the optimization for the split-capable node placement is not taken into account.

In this work we give an extension of Kauffman's NK-Landscapes to multiobjective MNK-Landscapes in order to study the effects of epistasis on the performance of multiobjective evolutionary algorithms (MOEAs). This paper focuses on the development of multiobjective random one-bit climbers (moRBCs). We incrementally build several moRBCs and analyze basic working principles of state of the art MOEAs on landscapes of increased epistatic complexity and number of objectives. We specially study the effects of Pareto dominance, non-dominance, and the use of memory and a population to influence the search. We choose an elitist non-dominated sorting multiobjective genetic algorithm (NSGA-II) as a representative of the latest generation of MOEAs and include its results for comparison. We detail the behavior of the climbers and show that population based moRBCs outperform NSGA-II for all values of M and K.

In this study, we construct balanced Boolean functions with a high nonlinearity and an optimum algebraic degree for both odd and even dimensions. Our approach is based on modifying functions from the Maiorana-McFarland's superclass, which has been introduced by Carlet. A drawback of Maiorana-McFarland's function is that their restrictions obtained by fixing some variables in their input are affine. Affine functions are cryptographically weak functions, so there is a risk that this property will be exploited in attacks. Due to the contribution of Carlet, our constructions do not have the potential weakness that is shared by the Maiorana-McFarland construction or its modifications.

We evaluate the exact number of gates for circuits of Shor's factoring algorithm. We estimate the running time for factoring a large composite such as 576 and 1024 bit numbers by appropriately setting gate operation time. For example, we show that on the condition that each elementary gate is operated within 50 µsec, the running time for factoring 576 bit number is 1 month even if the most effective circuit is adopted. Consequently, we find that if we adopt the long gate operation-time devices or qubit-saving circuits, factorization will not be completed within feasible time on the condition that a new efficient modular exponentiation algorithm will not be proposed. Furthermore, we point out that long gate operation time may become a new problem preventing a realization of quantum computers.

Cowen gave a universal compact routing algorithm with a stretch factor of three and table-size of O(n2/3log4/3n) based on a simple and practical model. (The table-size is later improved to O(n1/2log3/2n).) This paper considers, using the same model, how the necessary table-size differs if the stretch factor must be less than three. It is shown that: (i) There is a routing algorithm with a stretch factor of two whose table-size is (n -+ 2)log n. (ii) There is a network for which any routing algorithm that follows the model and with a stretch factor of less than three needs a table-size of (n - 2)log n in at least one node. Thus, we can only reduce roughly an additive log n (i.e., table-entries) from the trivial table-size of n log n which obviously enables shortest-path routing. Furthermore it turns out that we can reduce only an additive log n (i.e., only one table-entry) from the trivial n log n if we have to achieve a stretch factor of less than two. Thus the algorithm (i) is (roughly) tight both in its stretch factor and in its table-size.

This paper proposes a reduced-complexity signal detection scheme for Orthogonal Frequency Division Multiplexing with Space Division Multiplexing (OFDM/SDM) systems that utilize Zero-Forcing (ZF) and K-best algorithms. It is known that Maximum Likelihood Detection (MLD) with exhaustive search achieves mathematically optimal performance for SDM signal detection. However, it also suffers from exponential computational complexity against the number of transmit antennas and modulation order. In order to reduce the computational complexity of MLD, we apply the K-best algorithm for signal detection. It is known that the K-best algorithm itself inherently reduces the computational complexity of MLD because it avoids exhaustive search. In this paper, we propose the modified K-best algorithm, which exploits the ZF algorithm for initial symbol estimation. This initial symbol estimation improves the decoding accuracy of the original K-best algorithm. We evaluate the performance of the proposed scheme through computer simulations. The computer simulation results show that the performance degradation from the MLD algorithm is suppressed to just 1 dB or so in terms of the required Eb/N0 for packet error rate (PER) = 10-2, When either 16 Quadrature Amplitude Modulation (16QAM) or 64QAM is applied with three transmit and three receive antennas. In these cases, 87% and 99% fewer metric computations are required than the MLD algorithm. It is confirmed that the proposed MLD algorithm offers a significant reduction in the computational complexity from the MLD algorithm while suppressing the performance degradation.

In this letter, a method to construct good binary and quaternary error correcting codes, called complex Hadamard codes, based on a complex Hadamard matrix is presented. The related properties of the codes are analyzed. In addition, through the operation in Z4 domain, a new simplex soft-decision decoding algorithm for the complex Hadamard codes is also proposed.

This paper presents a computer-aided design procedure of simulated annealing algorithm to optimize dual-wideband microstrip line filters with symmetrical at least 500 MHz bandwidths respectively. This method demonstrates the superiority of designing microstrip line dual-band filters. The value of characteristic impedances and electrical lengths of transmission lines synthesizing 2.4 GHz and 5.2 GHz dualband filters with a single input and a single output are adjusted to the annealing process by the optimization algorithm. The fabricated dual-wideband spectral transmittance and reflectance curves of these filters applying this method all effectively achieved desired high performances and resulted in a lower cost dual-band filters and open the way to commercial mass production. The method is applicable not only in 2.4 GHz and 5.2 GHz, but can be applied to any other multi-frequency bands.

Genus 3 hyperelliptic curve cryptosystems are capable of fast-encryption on a 64-bit CPU, because a 56-bit field is enough for their definition fields. Recently, Kuroki et al. proposed an extension of the Harley algorithm, which had been known as the fastest addition algorithm of divisor classes on genus 2 hyperelliptic curves, on genus 3 hyperelliptic curves and Pelzl et al. improved the algorithm. This paper shows an improvement of the Harley algorithm on genus 3 hyperelliptic curves using Toom's multiplication. The proposed algorithm takes only I + 70M for an addition and I + 71M for a doubling instead of I + 76M and I + 74M respectively, which are the best possible of the previous works, where I and M denote the required time for an inversion and a multiplication over the definition field respectively. This paper also shows 2 variations of the proposed algorithm in order to adapt the algorithm to various platforms. Moreover this paper discusses finite field arithmetic suitable for genus 3 hyperelliptic curve cryptosystems and shows implementation results of the proposed algorithms on a 64-bit CPU. The implementation results show a 160-bit scalar multiplication can be done within 172 µs on a 64-bit CPU Alpha EV68 1.25 GHz.

In the key recovery variant of the interpolation attack, exhaustive search is required to find the last round key Km. Therefore, this attack is almost impractical if the size of Km is too large. In this paper, we show that Km can be very efficiently obtained if F(K,x) can be approximated by a low degree polynomial gx(K) in K for any fixed x, where F is a round function of Feistel type block ciphers.

A plane graph is a planar graph with a fixed embedding. In a no-bend orthogonal drawing of a plane graph, each vertex is drawn as a point and each edge is drawn as a single horizontal or vertical line segment. A planar graph is said to have a no-bend orthogonal drawing if at least one of its plane embeddings has a no-bend orthogonal drawing. In this paper we consider a class of planar graphs, called subdivisions of planar triconnected cubic graphs, and give a linear-time algorithm to examine whether such a planar graph G has a no-bend orthogonal drawing and to find one if G has.

Given a graph G, we give a fast algorithm for approximating the vertex connectivity κ of G. Our algorithm delivers a minimum vertex cut of G if κ δ/2, and returns a message "κ > δ/2" otherwise, where δ denotes the minimum degree of G. The algorithm runs in O(n2(1 + min {κ2, κ/δ)) time and O(n + m) space, where n and m denote the numbers of vertices and edges in G, respectively.

This paper introduces an efficient affine projection algorithm (APA) using iterative hyperplane projection. The inherent effectiveness against the rank deficient problem has led APA to be the preferred algorithm to be employed for various applications over other variety of fast converging adaptation algorithms. However, the amount of complexity of the conventional APA could not be negligible because of the accomplishment of sample matrix inversion (SMI). Another issue is that the "shifting invariance property," which is typically exploited for single channel case, does not hold ground for space-time decision-directed equalizer (STDE) application deployed in single-input-multi-output (SIMO) systems. Therefore, fast adaptation schemes, such as fast traversal filter based APA (FTF-APA), becomes impossible to utilize. The motivation of this paper deliberates on finding an effective algorithm on the basis of APA, which yields low complexity while sustaining fast convergence as well as excellent tracking ability. The performance of the proposed method is evaluated under wireless SIMO channel in respect to bit error rate (BER) behavior and computational complexity, and upon completion, the validity is confirmed. The performance of the proposed method is evaluated under wireless SIMO channel in respect to bit error rate (BER) behavior and computational complexity, and upon completion, the validity is confirmed.

In this paper, we consider a data mining problem for semi-structured data. Modeling semi-structured data as labeled ordered trees, we present an efficient algorithm for discovering frequent substructures from a large collection of semi-structured data. By extending the enumeration technique developed by Bayardo (SIGMOD'98) for discovering long itemsets, our algorithm scales almost linearly in the total size of maximal tree patterns contained in an input collection depending mildly on the size of the longest pattern. We also developed several pruning techniques that significantly speed-up the search. Experiments on Web data show that our algorithm runs efficiently on real-life datasets combined with proposed pruning techniques in the wide range of parameters.

CDN (Content Delivery Networks) improves end-user performance by replicating web contents on a group of geographically distributed servers. However, repeatedly keeping the entire replica of the original objects into many content servers consumes too much server resource. This problem becomes more serious for the large-sized objects such as streaming media, e.g. high quality video. In this paper, we therefore propose an efficient replication method for layered video streams in CDN, which can reduce user response delays and storage costs simultaneously. Based on an analytical formulation of the cooperative replication of layers and segments of each video stream, we derive a replication algorithm which solves next three problems quantitatively. (1) How many servers should be selected to replicate a given video stream? (2) For a single video stream, how many layers and segments should be stored in a given server? (3) After selecting a group of servers for each video stream, how do we allocate the replication priority (i.e. order) to each server? Simulation results verify that the proposed algorithm efficiently resolves the above problems and provides much better performance than conventional methods.