The multi-channel Hybrid Fiber Coaxial (HFC) network is essentially a shared medium with multi-channels. Its operation requires the use of a scheduling algorithm to manage the data transmission within each channel. The Data-Over-Cable Service Interface Specification (DOCSIS) protocol is an important standard for HFC networks. Since this protocol does not explicitly specify the scheduling algorithm to be used, many alternative algorithms have been proposed. However, none of these algorithms are applicable to the scheduling of non-Unsolicited Grant Service (UGS) data in multi-channel HFC networks. Accordingly, the present study develops a multi-channel scheduling algorithm which optimizes the scheduling delay time of each transmitted non-UGS request. This algorithm manages the amount of data transmission in each upstream channel according to the overall network load and the bandwidth available in each channel. This study constructs a mathematical model of the algorithm and then uses this model as the basis for a series of simulations in which the performance of the scheduling algorithm is evaluated.

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, 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.

This paper presents a new fast and robust circle extraction method that is capable of extracting circles from images with complicated backgrounds. It is not based on the Hough transform (HT) that requires a time-consuming voting process. The proposed method uses a least-squares circle fitting algorithm for extracting circles. The arcs are fitted by extended digital lines that are extracted by a fast line extraction method. The proposed method calculates accurate circle parameters using the fitted arcs instead of evidence histograms in the parameter space. Tests performed on various real-world images show that the proposed method quickly and accurately extracts circles from complicated and heavily corrupted images.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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 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.

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.

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.

We consider a rate control algorithm for elastic services to allocate bandwidth in a network subject to throughput and fairness constraints. Our algorithm achieves a max-min fair bandwidth allocation among contending elastic connections, and has desirable properties in that it can operate in a decentralized and asynchronous manner accounting in part for heterogeneity in round trip delays. The algorithm is simple and scalable in that, 1) the network links make local measurements of capacity and calculate local 'explicit rates' which are fed back to sources without requiring knowledge of the number of on-going connections, while 2) sources adjust their transmission rates so as not to exceed the received explicit rate indication. The algorithm is designed to track a "dynamic" network environment. We discuss its stability, convergence, and feasibility issues related to fair allocation and rate-based flow control. We also consider the role of sessions with priorities to differentiate among users with elastic services. Through rigorous analysis and simulations, we have shown that it has indeed desirable characteristics for networks with elastic services as well as other service types, which are expected to be common in future network environment.

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.