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.

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.

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.

This paper presents a new decoding framework for large vocabulary continuous speech recognition that can handle a static search network dynamically. Generally, a static network decoder can use a search space that is globally optimized in advance, and therefore it can run at high speed during decoding. However, its large memory requirement due to the large network size or the spatial complexity of the optimization algorithm often makes it impractical. Our new one-pass semi-dynamic network decoding scheme aims at incorporating such an optimized search network with memory efficiency, but without losing speed. In this framework, a complete search network is organized on the basis of self-structuring subnetworks and is nearly minimized using a modified tail-sharing algorithm. While the decoder runs, it caches subnetworks needed for decoding in memory, whereas static network decoders keep the complete network in memory. The subnetwork caching model is controlled by two levels of caches: local cache obtained by subnetwork caching operations and global cache obtained by subnetwork preloading operations. The model can also be controlled adaptively by using subnetwork profiling operations. Furthermore, it is made simple and fast with compactly designed self-structuring subnetworks. Experimental results on a 25 k-word Korean broadcast news transcription task show that the semi-dynamic decoder can run almost as fast as an equivalent static network decoder under various memory configurations by using the subnetwork caching model.

In this paper, we explore a method to the problem of spoken document categorization, which is the task of automatically assigning spoken documents into a set of predetermined categories. To categorize spoken documents, subword unit representations are used as an alternative to word units generated by either keyword spotting or large vocabulary continuous speech recognition (LVCSR). An advantage of using subword acoustic unit representations to spoken document categorization is that it does not require prior knowledge about the contents of the spoken documents and addresses the out of vocabulary (OOV) problem. Moreover, this method works in reliance on the sounds of speech rather than exact orthography. The use of subword units instead of words allows approximate matching on inaccurate transcriptions, makes "sounds-like" spoken document categorization possible. We also explore the performance of our method when the training set contains both perfect and errorful phonetic transcriptions, and hope the classifiers can learn from the confusion characteristics of recognizer and pronunciation variants of words to improve the robustness of whole system. Our experiments based on both artificial and real corrupted data sets show that the proposed method is more effective and robust than the word based method.

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.

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.

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

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.

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.

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.

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.

The IP routing lookup problem is equivalent to finding the longest prefix of a packet's destination address in a routing table. It is a challenging problem to design a high performance IP routing lookup architecture, because of increasing traffic, higher link speed, frequent updates and increasing routing table size. At first, increasing traffic and higher link speed require that the IP routing can be executed at wire speed. Secondly, frequent routing table updates require that the insertion and deletion operations should be simple and low delay. At last, increasing routing table size hopes that less memory is used in order to reduce cost. Although many schemes to achieve fast lookup exist, less attention is paid on the latter two factors. This paper proposed a novel pipelined IP routing lookup architecture using selective binary search on hash table organized by prefix lengths. The evaluation results show that it can perform IP lookup operations at a maximum rate of one lookup per cycle. The hash operation ratio for one lookup can be reduced to about 1%, less than two hash operations are needed for one table update and only 512 kbytes SRAM is needed for a routing table with about 43000 prefixes. It proves to have higher performance than the existing schemes.

One of the key issues in the next generation Internet is end-to-end Quality of Service (QoS) provisioning for real-time applications. The Differentiated Services (DiffServ) architecture offers a scalable alternative to provide QoS in the Internet. However, within this architecture, an efficient scheduling mechanism is still needed to ensure such QoS guarantees. In this paper, scheduling mechanism for supporting QoS differentiation among multiple traffic classes in IP differentiated services networks is studied. A scheduling algorithm called Multiclass Efficient Packet Fair Queueing (MEPFQ) is proposed that enables fair bandwidth sharing while supporting better bounds on end-to-end network delay for QoS-sensitive applications such as voice over IP (VoIP) within the DiffServ framework. The mechanism allows to create service classes and assign proportional weights to such classes efficiently according to their resource requirements. Besides, MEPFQ tries to ensure that packets from low priority class will not be starved even under extreme congestion cases. The results from the simulation studies show that the mechanism is able to ensure both the required end-to-end network delay bounds and bandwidth fairness for QoS-sensitive applications based on the specified service weights under various traffic and network conditions. Another important aspect of the MEPFQ algorithm is that the scheme has lower implementation complexity, along with scalability to accommodate the growing traffic flows at the core routers of high-speed Internet backbone.

In this paper, we propose two fast codebook generation algorithms for entropy-constrained vector quantization. The first algorithm uses the angular constraint to reduce the search area and to accelerate the search process in the codebook design. It employs the projection angles of the vectors to a reference line. The second algorithm has feature of using a suitable hyperplane to partition the codebook and image data. These algorithms allow significant acceleration in codebook design process. Experimental results are presented on image block data. These results show that our new algorithms perform better than the previously known methods.

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.

In this paper we study a classical firing squad synchronization problem on a model of fault-tolerant cellular automata that have possibly some defective cells. Several fault-tolerant time-efficient synchronization algorithms are developed based on a simple freezing-thawing technique. It is shown that, under some constraints on the distribution of defective cells, any cellular array of length n with p defective cell segments can be synchronized in 2n - 2 + p steps.