Cryptography and Coding Theory are closely related in many respects. Recently, the problem of "decoding Reed Solomon codes" (also known as "polynomial reconstruction") was suggested as an intractability assumption to base the security of protocols on. This has initiated a line of cryptographic research exploiting the rich algebraic structure of the problem and its variants. In this paper we give a short overview of the recent works in this area as well as list directions and open problems in Polynomial Reconstruction Based Cryptography.

Recently, low-density parity-check (LDPC) codes have attracted much attention. LDPC codes can achieve the near Shannon limit performance like turbo codes. For the LDPC codes, the reduced complexity decoding algorithms referred to as uniformly most powerful (UMP) BP- and normalized BP-based algorithms were proposed for BPSK on an additive white Gaussian noise (AWGN) channel. The conventional BP and BP-based algorithms can be applied to BPSK modulation. For high bit-rate transmission, multilevel modulation is preferred. Thus, the BP algorithm for multilevel modulations is proposed in . In this paper, we propose the BP algorithm with reduced complexity for multilevel modulations, where the first likelihood of the proposed BP algorithm is modified to adjust multilevel modulations. We compare the error rate performance of the proposed algorithm with that of the conventional algorithm on AWGN and flat Rayleigh fading channels. We also propose the UMP BP- and normalized BP-based algorithms for multilevel modulations on AWGN and flat Rayleigh fading channels. We show that the error rate performance of the proposed BP algorithm is almost identical to that of the algorithm in, where the decoding complexity of the proposed BP algorithm is less than that of the algorithm in. We also show that the proposed BP-based algorithms can achieve the good trade-off between the complexity and the error rate performance.

In the CNN problem, a "scene" appears on the two-dimensional plane, at different positions sequentially, and a "camera crew" has to shoot the scene whenever it appears. If a scene appears at some position, the camera crew does not have to move to the position exactly, but has only to move to a point that lies in the same horizontal or vertical line with the scene. Namely it is enough to move either to the same row or to the same column. The goal is to minimize the total moving distance of the camera crew. This problem has been quite popular in the last decade but it is still open whether or not there is a competitive algorithm, i.e., an algorithm with competitive ratio bounded by a constant. In this paper we study this problem under a natural restriction that the server can move only along the X-axis and the Y-axis. It is shown that there exists a competitive algorithm for this restricted version, namely there is an online algorithm for this "axis-bound CNN" with competitive ratio 9.0.

A 2-dimensional cylindrical k-within-consecutive-(r, s)-out-of-(m, n):F system consists of m n components arranged on a cylindrical grid. Each of m circles has n components, and this system fails if and only if there exists a grid of size r s within which at least k components are failed. This system may be used into reliability models of "Feelers for measuring temperature on reaction chamber," "TFT Liquid Crystal Display system with 360 degree wide area" and others. In this paper, first, we propose an efficient algorithm for the reliability of a 2-dimensional cylindrical k-within-consecutive-(r, s)-out-of-(m, n):F system. The feature of this algorithm is calculating their system reliabilities with shorter computing time and smaller memory size than Akiba and Yamamoto. Next, we show some numerical examples so that our proposed algorithm is more effective than Akiba and Yamamoto for systems with large n.

The efficient squaring algorithm is an important role in large integer arithmetic. All multiplication algorithms can be used for squaring large integers, but their performance can be greatly improved by using the standard squaring algorithm. The standard squaring algorithm is quite well-known, but unfortunately there is an improper carry handling bug in it. Recently, Guajardo and Paar proposed a modified squaring algorithm to fix the bug in the standard squaring algorithm. In this paper, we first point out that there is still an error-indexing bug in the Guajardo-Paar squaring algorithm. Then, we propose a new efficient squaring algorithm that not only avoids the bugs in both the standard squaring algorithm and the Guajardo-Paar squaring algorithm but also improves the performance in squaring computation. Our analyses and our simulations indicate that the proposed squaring algorithm is about 2.5 times faster in comparison with the standard multiplication algorithm in Pentium Series CPU. The performance of 1024-bit RSA cryptosystem can be saved 34.3% by using the proposed squaring algorithm to replace the standard multiplication.

The notion of k-wise independent permutations has several applications. From the practical point of view, it often suffices to consider almost (i.e., ε-approximate) k-wise independent permutation families rather than k-wise independent permutation families, however, we know little about how to construct families of ε-approximate k-wise independent permutations of small size. For any n > 0, let Sn be the set of all permutations on {0,1,..., n - 1}. In this paper, we investigate the size of families of ε-approximate k-wise independent permutations and show that (1) for any constant ε 0, if a family Sn of permutations is ε-approximate k-wise independent, then || n(n - 1) (n - k + 1) if ε< 1; || {n(n - 1) (n - k + 1)}/(1 +ε) otherwise; (2) for any constant 0< ε 1, there exists a family Sn of ε-approximate k-wise independent permutations such that || = ; (3) for any constant ε> 0 and any n = pm - 1 with p prime, it is possible to construct a polynomial time samplable family Sn of ε-approximate pairwise independent permutations such that || = O(n(n - 1)/ε); (4) for any constant ε> 0 and any n = pm with p prime, it is possible to construct a polynomial time samplable family Sn of ε-approximate 3-wise independent permutations such that || = O(n(n - 1)(n - 2)/ε). Our results are derived by combinatorial arguments, i.e., probabilistic methods and linear algebra methods.

A variety of real-time multicast applications such as video conferences, remote lectures, and video-on-demand have become in commonplace with the expansion of broadband Internet services. Due to nontrivial problems in the IP multicast technology, the peer-to-peer multicast technology (P2P-multicast) has emerged as a practical implementation, although its network resource utilization is less efficient. A multihome network has the potential of alleviating this inefficiency by providing flexibility in communication path selections for each host with multiple gateways to the Internet. This paper has first formulated the P2P-multicast routing problem in the multihome network, and has proved the NP-completeness of its decision problem. Then, a two-stage heuristic algorithm called P2PMM_router has been presented for this P2P Multicast Multihome-network routing problem. The first stage constructs an initial multicast routing tree from an optimum spanning tree by Prim algorithm, through satisfying the constraints. The second stage improves the tree by repeating partial modifications and constraint satisfactions. The extensive simulation results using random network instances support the effectiveness of our P2PMM_router.

This paper proposes the constraint availability and bandwidth shortest path (CABSP) selection algorithm and the extension of the adaptive modulation scheme to the CABSP (CABSP-AM) selection algorithm in the millimeter-wave (MMW) broadband entrance network for wireless heterogeneous systems. The CABSP algorithm considers the availability denoted as the quality of the MMW which is severely affected by the rainfall. The CABSP-AM algorithm, moreover, is proposed to further make more efficient use of bandwidth resources by considering the QoS requirements of each class of service in multimedia communication. As the results, the CABSP algorithm yields higher throughput performance than the conventional constraint shortest path (CSP) selection algorithm, but lower than the CABSP-AM algorithm. The spectrum efficiency improvements of the CABSP-AM over the CABSP are about 1.36 and 1.48 fold in case of error sensitive and non-sensitive classes respectively.

The issues of comparing the similarity or dissimilarity (distance) between structures have been studied. Especially, several distances between trees and their efficient algorithms have been proposed. However, all of the tree distances are defined based on mapping between vertices only, and they are helpless to compare the tree structures whose vertices and edges hold information. In this paper, we will propose a mapping between rooted and unordered trees based on vertex translation and edge translation, and then define a distance based on proposed mapping, and develop an efficient algorithm for computing proposed distance. Proposed distance can be used to compare the similarity or distance between two natural language sentences.

In this letter, we propose a packet scheduling algorithm to support both real-time voice and video traffic for wireless multimedia data service in orthogonal frequency division multiple access (OFDMA) system. Our design objective is to maximize the number of real-time service users that can be supported in the system subject to QoS requirement of packet loss rate (PLR). Both time slots and subcarriers are taken into account as the basic resource allocation unit in OFDMA/FDD system. The simulation results show that our proposed algorithm can dramatically increase the number of users satisfying the underlying QoS requirement for the real-time service, as compared to the existing algorithm.

Learning behaviors of hierarchically structured stochastic automata operating in a general nonstationary multiteacher environment are considered. It is shown that convergence with probability 1 to the optimal path is ensured by a new learning algorithm which is an extended form of the relative reward strength algorithm. Several computer simulation results confirm the effectiveness of the proposed algorithm.

In this paper we propose a new blind adaptive compensator associated with the inverse QRD-RLS (IQRD-RLS) algorithm to adaptively estimate the parameters, related to the effects of gain/phase imbalance and DC offsets occur in the Quadrature demodulator, for compensation. In this new approach the power measurement of the received signal is employed to develop the blind adaptation algorithm for compensator, it does not require any reference signal transmitted from the transmitter and possess the fast convergence rate and better numerical stability. To verify the great improvement, in terms of reducing the effects of the imbalance and offset, over existing techniques computer simulation is carried out for the coherent 16 PSK-communication system. We show that the proposed blind scheme has rapidly convergence rate and the smaller mean square error in steady state.

In this letter we verify that a blind adaptive algorithm operating at a low intermediate frequency (Low-IF) can be applied to a system where carrier phase synchronization has not been achieved. We consider a quadrature amplitude shift keyed (QPSK) signal as the transmitted signal, and assume that the orthogonal low intermediate sinusoidal frequency used to generate the transmitted signal is well known. The proposed algorithm combines two algorithms: Namely, the least mean square (LMS) algorithm which has a cost function with unique minimum, and the constant modulus algorithm (CMA), which was first proposed by Godard. By doing this and operating the equalizer at a rate greater than the symbol rate, we take advantage of the variable amplitude of the sub-carriers and the fast convergence of LMS algorithm, so as to achieve a faster convergence speed. When the computer simulation results of the proposed algorithm are compared with the constant modulus algorithm (CMA) and the modified CMA (MCMA), we observed that the proposed algorithm exhibited a faster convergence speed.

Turbo codes are of particular use in applications of wireless communication systems, where various types of communication are required and the data rate must be changed, depending on the situation. In such applications, adaptation of turbo coding specifications is required in terms of coding block size, data speed, parity bit arrangement or configuration of a convolutional coder, as well as the need for real time processing. We present new ideas to provide these capabilities for a low power decoder circuit by focusing on the configuration of a convolutional decoding algorithm, which occupies a significant proportion of the hardware circuit. We utilize the Soft Output Viterbi Algorithm (SOVA) for the base algorithm, produced by adding the concept of a soft output to the Viterbi Algorithm (VA). The Maximum A Posteriori (MAP) algorithm and its simplified version of MAX-LOG-MAP are also widely known. MAP is recognized as a means of achieving very good bit error rate (BER) characteristics. On the other hand SOVA has been regarded as a method which can be simply implemented with less computational resources, but at a cost of higher degradation. However, in many of recent systems we combine turbo coding with some other method such as Automatic Repeat Request (ARQ) to maintain a good error correction performance and we only have to pay attention to the performance in the range of low carrier-to-noise ratio (CNR), where SOVA has fairly satisfactory BER characteristics. This makes the SOVA approach attractive for a low power programmable IP macro solution, when the fundamental advantage of SOVA is fully utilized in the implementation of an LSI circuit. We discuss the processing algorithm and circuit configuration and show that about 40% reduction in power consumption can be achieved. It is also shown that the IP macro can handle 1.5 Mbps information decoding at 100 MHz clock rate.

A number of on-line and off-line algorithms for load balancing on multiple paths for MPLS (MultiProtocol Label Switching) traffic engineering have now been proposed, in which it is always assumed that sets of LSPs (Label Switched Path) have already been established between node pairs. While how to choose these paths is an important issue in traffic engineering, it has not been well studied yet. In this paper, we attempt to fill in this gap. As the shortest paths are always preferred in routing problems, we evaluate several k shortest path algorithms from the viewpoint of bandwidth use efficiency and the number of the found paths. Extensive simulations have been performed in different kinds of topologies to factor out effects of network characteristics on these algorithms' path calculation performances. It is found out that the performances of the evaluated algorithms are limited in some cases and the design of new algorithms for the path calculation problem is worth studying in the future.

Adaptive antenna array is a promising technique to increase the link capacity in mobile radio communications systems by suppressing multiple access interference (MAI). In the mobile radio, the received signal consists of discrete paths, each being a cluster of many irresolvable paths arriving from different directions. For large arrival angle spread of each cluster of irresolvable paths, antenna array cannot form a beam pattern that sufficiently suppresses MAI even in the presence of single interference signal and hence, the transmission performance may degrade. In this situation, the use of antenna diversity may be a better solution. It is an interesting question as to which can achieve a better performance, antenna diversity reception or adaptive antenna array. In this letter, we study the impact of the arrival angle spread on the DS-CDMA transmission performances achievable with adaptive antenna array and antenna diversity reception. It is pointed out that the arrival angle spread is an important parameter to determine the performances of adaptive antenna array and antenna diversity.

The capabilities of reliable computations in one-dimensional cellular automata are investigated by means of the Early Bird Problem. The problem is typical for situations in massively parallel systems where a global behavior must be achieved by only local interactions between the single elements. The cells that cause the misoperations are assumed to behave as follows. They run a self-diagnosis before the actual computation once. The result is stored locally such that the working state of a cell becomes visible to its neighbors. A non-working (defective) cell cannot modify information but is able to transmit it unchanged with unit speed. We present an O(n log (n) log (n))-time fault-tolerant solution of the Early Bird Problem.

Fast algorithms for computing the running type-I discrete sine transform (DST-I) and type-III discrete sine transform (DST-III) are proposed. The algorithms are based on a recursive relationship between three subsequent local discrete sine spectra. The computational complexity of the algorithms is compared with that of fast DST-I and DST-III algorithms. Fast inverse algorithms for signal processing in the running discrete sine transform domains are also proposed.

This paper describes a method of test data compression for a given test set using statistical encoding. In order to maximize the effectiveness of statistical encoding, the method first converts some specified input values in the test set to unspecified ones without losing fault coverage, and then reassigns appropriate logic values to the unspecified inputs. Experimental results for ISCAS-89 benchmark circuits show that the proposed method can on the average reduce the test data volume to less than 25% of that required for the original test set.

The number and location of the inventory centers play an important role in the material distribution process since residents and inventory centers may be in dispersed regions. In this paper, we view the problem of finding the better locations for the inventory centers as an optimization problem, and propose a nested genetic algorithm (NGA) approach to design an optimal material distribution system. We demonstrate the feasibility of the proposed approach by numerical experiments.