The baby-step giant-step algorithm, BSGS for short, was proposed by Shanks in order to compute the class number of an imaginary quadratic field. This algorithm is at present known as a very useful tool for computing with respect to finite groups such as the discrete logarithms and counting the number of the elements. Especially, the BSGS is normally made use of counting the rational points on the Jacobian of a hyperelliptic curve over a finite field. Indeed, research on the practical improvement of the BSGS has recently received a lot of attention from a cryptographic viewpoint. In this paper, we explicitly analyze the modified BSGS, which is for non-uniform distributions of the group order, proposed by Blackburn and Teske. More precisely, we refine the Blackburn-Teske algorithm, and also propose a criterion for the decision of the effectiveness of their algorithm; namely, our proposed criterion explicitly shows that what distribution is needed in order that their proposed algorithm is faster than the original BSGS. That is, we for the first time present a necessary and sufficient condition under which the modified BSGS is effective.

In this paper, we describe a technique for optimizing the algebraic method that is applied to higher order differential attack. The higher order differential attack is a well-known attack on block ciphers, in which we derive an attack equation to determine a round key from a property of a higher order differential of a target block cipher. The algebraic method is a linearization of the attack equation and determines the true key by a method such as Gaussian elimination. Our technique is based on linear dependency and can reduce the complexity of that method. We also describe a technique that allows the algebraic method to be used as an attack equation that holds probabilistically. We demonstrate this method by attacking a five-round MISTY1 and show that it needs 221.6 chosen plaintexts and 228.0 encryption times. The computer simulation took about two minutes to complete.

In this paper, a novel methodology for designing and analyzing high performance sigma-delta leapfrog modulators for ultra-high resolution analog-to-digital (A/D) converters is presented. The less sensitive topology, the leapfrog topology, in component variations is analyzed by considering the noise transfer function (NTF). By using theoretical analysis, the loop coefficients are constrained to a small, clear and definite range called the stable region (SR). With the output voltage limited within 2 V, an absolutely stable region (ASR) is obtained. A program that analyzes and generates the required coefficients is constructed for easily designing this topology. For a 256 over-sampling ratio (OSR) and the coefficients from ASR, the signal to noise ratio (SNR) and dynamic range (DR) are 105 dB and 100 dB, respectively. In accordance with the behavior simulation results, the system is not only stable and efficient but also suitable for high-resolution applications.

The recent development of network technology has enabled us to access various information sources easily, and their integration has been studied intensively by the data engineering research community. Although technological advancement has made it possible to integrate existing heterogeneous information sources, we still have to deal with information sources of a new kind--dissemination-based information sources. They actively and autonomously deliver information from server sites to users. Integration of dissemination-based information sources is one of the popular research topics. We have been developing an information integration system in which we employ ECA rules to enable users to define new information delivery services integrating multiple existing dissemination-based information sources. However, it is not easy for users to directly specify ECA rules and to verify them. In this paper, we propose a scheme to specify new dissemination-based information delivery services using the framework of relational algebra. We discuss some important properties of the specification, and show how we can derive ECA rules to implement the services.

In this paper, we present the results of a comparative analysis of Atomic Broadcast algorithms. The analysis was done by using an analytical method to compare the performance of five different classes of Atomic Broadcast algorithms. The five classes of Atomic Broadcast algorithms are determined by the mechanisms used by the algorithms to define the delivery order. To evaluate the performance of algorithms, the analysis relies on contention-aware metrics to provide a measure for both their latency and their throughput. The results thus obtained yield interesting insight into the performance tradeoffs of different Atomic Broadcast algorithms, thus providing helpful information to algorithms and systems designers.

The IEEE 802.11 WLAN standards adopt CSMA/CA protocol with a backoff algorithm as medium access control technique. When the number of stations which attempt to access a network increases, the throughput efficiency of the standard goes down. In this paper, we propose a modified backoff algorithm which adaptively selects the Contention Window (CW) size according to the variation of the number of contending stations and present the results of simulation analysis.

The High-Low Water Mark destage (HLWM) algorithm is widely used to enable cached RAID5 to flush dirty data from its write cache to disks due to the simplicity of its operations. It starts and stops a destaging process based on the two thresholds that are configured at the initialization time with the best knowledge of its underlying storage performance capability and its workload pattern which includes traffic intensity, access patterns, etc. However, each time the current workload varies from the original, the thresholds need to be re-configured with the changed workload. This paper proposes an efficient destage algorithm which automatically re-configures its initial thresholds according to the changed traffic intensity and access patterns, called adaptive thresholding. The core of adaptive thresholding is to define the two thresholds as the multiplication of the referenced increasing and decreasing rates of the write cache occupancy level and the time required to fill and empty the write cache. We implement the proposed algorithm upon an actual RAID system and then verify the ability of the auto-reconfiguration with synthetic workloads having a different level of traffic intensity and access patterns. Performance evaluations under well-known traced workloads reveal that the proposed algorithm reduces disk IO traffic by about 12% with a 6% increase in the overwrite ratio compared with the HLWM algorithm.

A burnt pancake graph is a variant of Cayley graphs and its topology is suitable for massively parallel systems. However, for a burnt pancake graph, there is much room for further research. Hence, in this study, we focus on n-burnt pancake graphs and propose an algorithm to obtain n disjoint paths from a source node to n destination nodes in polynomial order time of n, n being the degree of the graph. In addition, we estimate the time complexity of the algorithm and the sum of path lengths. We also give a proof of correctness of the algorithm. Moreover, we report the results of computer simulation to evaluate the average performance of the algorithm.

We propose an efficient algorithm for making multi-layered neural networks (MLN) fault-tolerant to all multiple weight faults in a multi-dimensional interval by injecting intentionally two extreme multi-dimensional values in the interval into the weights of the selected multiple links in a learning phase. The degree of fault-tolerance to a multiple weight fault is measured by the number of essential multiple links. First, we analytically discuss how to choose effectively the multiple links to be injected, and present a learning algorithm for making MLNs fault tolerant to all multiple (i.e., simultaneous) faults in the interval defined by two multi-dimensional extreme points. Then it is proved that after the learning algorithm successfully finishes, MLNs become fault tolerant to all multiple faults in the interval. It is also shown that the time in a weight modification cycle depends little on multiplicity of faults k for small k. These are confirmed by simulation.

Given an edge-weighted graph G, the minimum maximal matching problem asks to find a minimum weight maximal matching. The problem is known to be NP-hard even if the graph is planar and unweighted. In this paper, we consider the problem in planar graphs. First, we prove a strong inapproximability for the problem in weighted planar graphs. Second, in contrast with the first result, we show that a polynomial time approximation scheme (PTAS) for the problem in unweighted planar graphs can be obtained by a divide-and-conquer method based on the planar separator theorem. For a given ε > 0, our scheme delivers in time a solution with size at most (1 + ε) times the optimal value, where n is the number of vertices in G and α is a constant number.

Because most link-state routing protocols, such as OSPF and IS-IS, calculate routes using the Dijkstra algorithm, which poses scalability problems, implementors often introduce an artificial delay to reduce the number of route calculations. Although this delay directly affects IP packet forwarding, it can be acceptable when the network topology does not change often. However, when the topology of a network changes frequently, this delay can lead to a complete loss of IP reachability for the affected network prefixes during the unstable period. In this paper, we propose the Cached Shortest-path Tree (CST) approach, which speeds up intra-domain routing convergence without extra execution of the Dijkstra algorithm, even if the routing for a network is quite unstable. The basic idea of CST is to cache shortest-path trees (SPTs) of network topologies that appear frequently, and use these SPTs to instantly generate a routing table when the topology after a change matches one in the caches. CST depends on a characteristic that we found from an investigation of routing instability conducted on the WIDE Internet in Japan. That is, under unstable routing conditions, both frequently changing Link State Advertisements (LSAs) and their instances tend to be limited. At the end of this paper, we show CST's effectiveness by a trace-driven simulation.

A new algorithm for the LogMAP decoding of linear block codes is considered. The decoding complexity is evaluated analytically and by computer simulation. The proposed algorithm is an improvement of the recursive LogMAP algorithm proposed by the authors. The recursive LogMAP algorithm is more efficient than the BCJR algorithm for low-rate codes, but the complexity grows considerably large for high-rate codes. The aim of the proposed algorithm is to solve the complexity explosion of the recursive LogMAP algorithm for high-rate codes. The proposed algorithm is more efficient than the BCJR algorithm for well-known linear block codes.

This paper presents a unified representation of fast addition algorithms based on Counter Tree Diagrams (CTDs). By using CTDs, we can describe and analyze various adder architectures in a systematic way without using specific knowledge about underlying arithmetic algorithms. Examples of adder architectures that can be handled by CTDs include Redundant-Binary (RB) adders, Signed-Digit (SD) adders, Positive-Digit (PD) adders, carry-save adders, parallel counters (e.g., 3-2 counters and 4-2 counters) and networks of such basic adders/counters. This paper also discusses the CTD-based analysis of carry-propagation-free adders using various number representations.

In this letter, iterative sequence estimation technique based on expectation-maximization (EM) algorithm is considered for quadrature amplitude modulation (QAM)-orthogonal frequency division multiplexing (OFDM) signals. For QAM-OFDM signaling, the optimal EM algorithm requires high computational complexity due to the inversion of complex matrix executed at each iteration. To avoid this problem, we propose a sub-optimal iterative sequence estimation algorithm with some approximations, which results in reduced computational complexity for QAM-OFDM signals. Moreover, we use two different approaches to obtain initial estimate for beginning iteration of proposed algorithm. One is for less time-dispersive but fast fading channel and the other is for highly time-dispersive but relatively slow fading channel. The bit error rate (BER) performances of the proposed algorithm are evaluated using computer simulations. The results show that the proposed algorithm performs nearly as well as the optimal EM algorithm.

This paper proposes a new algorithm to control an adaptive duplexer for multiband software radio. It uses a wideband low isolation device combined with a two-tap/two-loop adjustable canceller to eliminate the need for multiple switched high isolation duplexers. The taps are adjusted to provide isolation peaks in the transmit and receive bands. The algorithm is based on the superposition of squared errors and achieved 66 dB isolation of the transmit signal and a 37 dB cancellation of the transmitter noise in the receiver band.

This letter presents the advantages of a cascaded algebraic codebook structure at relatively high bit-rates. The cascaded structure that consists of two stages provides flexible pulse combinations due to an additional gain term in the second stage. The perceptual quality of the cascaded structure can be further improved by using a gain re-estimation scheme. Experiments confirm that the cascaded structure has a big advantage in terms of quality and complexity as the bit-rate becomes higher.

One conventional technique for source localization is to utilize the time-difference-of-arrival (TDOA) measurements of a signal received at spatially separated sensors. A simple TDOA-based location algorithm that combines the advantages of two efficient positioning methods is developed. It is demonstrated that the proposed approach can give optimum performance in geolocation via satellites at different noise conditions.

A tree 3-spanner T of a graph G is a spanning tree of G such that the distance between any two vertices in T is at most 3 times of their distance in G. Madanlal et al. have presented an O(n + m) time algorithm for finding a tree 3-spanner of a permutation graph. However, the complexity of their algorithm is not optimal, and their algorithm can not be easily parallelized. In this paper, we will propose an improved algorithm to solve the same problem in O(n) time. Moreover, our algorithm can be easily parallelized so that a tree 3-spanner of a permutation graph can be found in O(log n) time with processors on the EREW PRAM computational model.

Turbo coding is a powerful coding technique that can provide highly reliable data transmission at extremely low signal-to-noise ratios. Owing to the computational complexity of the employed decoding algorithm, the realization of turbo decoders usually takes a large amount of memory space and potentially long decoding delay. Therefore, an efficient memory management strategy becomes one of the key factors toward successfully implementing turbo decoders. This paper focuses on the development of general structures for efficient memory management of turbo decoders employing the sliding-window (Log-) MAP algorithm. Three different structures and the associated mathematic representations are derived to evaluate the required memory size, average decoding rate, and latency based on the speed and the number of the adopted processors. Comparative results show the dependency of the resulting performance based on a set of parameters; thus provide useful and general information on practical implementations of turbo decoders.

In this letter, we propose the Low-Density Parity-Check (LDPC) coded Orthogonal Frequency Division Multiplexing (OFDM) systems to improve the error rate performance of OFDM. We also evaluate the iterative decoding performance on both an AWGN and a frequency-selective fading channels. We show that when the energy per information bit to the noise power spectral density ratio Eb/N0 is not small, the LDPC coded OFDM (LDPC-COFDM) systems have the good error rate performance with a small number of iterations. We also show that when the Eb/N0 is small, the BER of the LDPC-COFDM systems is worse than that of the Turbo coded OFDM (TCOFDM) systems, while when the Eb/N0 is not small, the BER of the LDPC-COFDM systems is better with a small number of iterations.