A topological book embedding of a graph is an embedding in a book that carries the vertices in the spine of the book and the edges in the pages so that edges are allowed to cross the spine. Recently, the author has shown that for an arbitrary graph G with n vertices there exists a d+1-page book embedding of G in which each edge crosses the spine logd n times. This paper improves the result for the case of bipartite graphs and shows that there exists a d+1-page book embedding of a bipartite graph Gn1,n2 having two partite sets with n1 and n2 vertices respectively (n1 ≥ n2) in which each edge crosses the spine logd n2 -1 times.

We consider a watermark application to assist in the integrity maintenance and verification of the associated images. There is a great benefit in using WM in the context of authentication since it does not require any additional storage space for supplementary metadata, in contrast with cryptographic signatures, for instance. However there is a fundamental problem in the case of exact authentication: How to embed a signature into a cover message in such a way that it would be possible to restore the watermarked cover image into its original state without any error? There are different approaches to solve this problem. We use the watermarking method consisting of modulo addition of a mark and investigate it in detail. Our contribution lies in investigating different modified techniques of both watermark embedding and detection in order to provide the best reliability of watermark authentication. The simulation results for different types of embedders and detectors in combination with the pictures of watermarked images are given.

In this paper, we study the layout problem of the supercube by embedding-in-book technique. The supercube, a generalization of the hypercube, can be constructed for an arbitrary system size. Moreover, it has the same diameter and connectivity of the corresponding hypercube. Embedding a graph in book is to place nodes along the spine of the book and to draw the edges such that edges residing in a page do not cross. An n-dimensional hypercube is regular because the degree of each node is n. The corresponding supercube with N nodes, where 2n-1 < N 2n and N ≠ 32n-2, is irregular because the degree of each node ranges from 2n - 2 to n - 1. Although Chung et al. have shown that an n-dimensional hypercube can be embedded with n - 1 pages, to lay out the supercube remains a challenging problem owing to its higher degree and irregular structure. In this paper, we show that a supercube of N nodes, where 2n-1 < N 2n, can also be embedded with n - 1 pages and book width N - 2n-2 for 2n-1 < N < 32n-2, and 2n-1 for 32n-2 N 2n.

Machine learning and data mining algorithms are increasingly being used in the intrusion detection systems (IDS), but their performances are laggard to some extent especially applied in network based intrusion detection: the larger load of network traffic monitoring requires more efficient algorithm in practice. In this paper, we propose and design an anomaly intrusion detection (AID) system based on the vector quantization (VQ) which is widely used for data compression and high-dimension multimedia data index. The design procedure optimizes the performance of intrusion detection by jointly accounting for accurate usage profile modeling by the VQ codebook and fast similarity measures between feature vectors to reduce the computational cost. The former is just the key of getting high detection rate and the later is the footstone of guaranteeing efficiency and real-time style of intrusion detection. Experiment comparisons to other related researches show that the performance of intrusion detection is improved greatly.

A speaker identification system based on wavelet transform (WT) derived from codebook design using fuzzy c-mean algorithm (FCM) is proposed. We have combined FCM and the vector quantization (VQ) algorithm to avoid typical local minima for speaker data compression. Identification accuracies of 94% were achieved for 100 Mandarin speakers.

A topological book embedding of a graph is an embedding in a book that carries the vertices in the spine of the book and the edges in the pages; edges are allowed to cross the spine. Enomoto showed that for any graph G having n vertices, there exists a three-page book embedding of G in which each edge crosses the spine log n times. This paper generalizes the result and shows that for any graph G having n vertices, there exists a d + 1-page book embedding of G in which each edge crosses the spine logd n times.

The switchable dual-wavelength and wavelength-con-verted nonreturn-to-zero-to-return-to-zero (NRZ-to-RZ) data transformation is demonstrated by externally seeding a synchronously sinusoidal-modulated laser diode with an optical pseudorandom bit sequence data at 1 Gbps. A maximum wavelength tuning range of 30 nm with an SMSR of greater than 36 dB is obtained. 1 Gbps on/off keying of single-mode RZ data pulse-train generated by externally seeding synchronously sinusoidal-modulated laser diode is demonstrated.

This paper presents an approach of logic mapping into LUT-Array-Based PLD where Boolean functions in the form of the sum of generalized complex terms (SGCTs) can be mapped directly. While previous mapping approach requires predetermined variable ordering, our approach performs mapping and variable reordering simultaneously. For the purpose, we propose a directed acyclic graph based on the multiple-valued decision diagram (MDD) and an algorithm to construct the graph. Our algorithm generates candidates of SGCT expressions for each node in a bottom-up manner and selects the variables in the current level by evaluating the sizes of SGCT expressions directly. Experimental results show that our approach reduces the number of terms maximum to 71 percent for the MCNC benchmark circuits.

In this paper, we present the condition for the effective wire addition in Look-Up-Table-based (LUT-based) field programmable gate array (FPGA) circuits, and an optimization procedure utilizing the effective wire addition. Each wire has different characteristics, such as delay and power dissipation. Therefore, the replacement of one critical wire for the circuit performance with many non-critical ones, i.e., many-addition-for-one-removal (m-for-1) is sufficiently useful. However, the conventional logic optimization methods based on sets of pairs of functions to be distinguished (SPFDs) for LUT-based FPGA circuits do not make use of the m-for-1 manipulation, and perform only simple replacement and removal, i.e., the one-addition-for-one-removal (1-for-1) manipulation and the no-addition-for-one-removal (0-for-1) manipulation, respectively. Since each LUT can realize an arbitrary internal function with respect to a specified number of input variables, there is no sufficient condition at the logic design level for simple wire addition. Moreover, in general, simple addition of a wire has no effects for removal of another wire, and it is important to derive the condition for non-simple and effective wire addition. We found the SPFD-based condition that wire addition is likely to make another wire redundant or replaceable, and developed an optimization procedure utilizing this effective wire addition. According to the experimental results, when we focused on the delay reduction of LUT-based FPGA circuits, our method reduced the delay by 24.2% from the initial circuits, while the conventional SPFD-based logic optimization and the enhanced global rewiring reduced it by 14.2% and 18.0%, respectively. Thus, our method presented in this paper is sufficiently practical, and is expected to improve the circuit performance.

Building next generation routers with the capability of forwarding multiple millions of packets per second is required for the increasing demand for high bandwidth on the Internet. Reducing the required memory size of the forwarding table is a possible solution since small forwarding table can be integrated into the application specific integrated circuit (ASIC). In this paper a hash technique is developed to reduce the size of the IP forwarding table. The proposed data structure is a compressed 8-8-8-8 multibit trie that is based on hash tables of 4-bit addresses. Two optimization techniques are also proposed to further improve the performance of the proposed schemes. Our experimental results show that the proposed hashing-based schemes are better than the Small Forwarding Table scheme both in memory size and lookup latency.

The most important function of a router is to perform IP lookup that determines the output ports of incoming IP packets by their destination addresses. Hence, IP lookup is one of the main issues in implementing high-speed routers. The IP lookup algorithm implemented in IQ2200 Chipset with two-level table architecture can efficiently use memory. However, it wastes processor resource for full re-construction of the forwarding tables whenever every route insertion/deletion is requested. In order to improve the utilization of processor resource, we propose an IP lookup algorithm with three-level table architecture for high-speed routers. We evaluate the performance of the proposed algorithm in terms of the memory size required for storing lookup information and the number of memory access in constructing forwarding tables. Being compared with the IQ2200 scheme, the proposed scheme can reduce the number of memory access up to 99% even though it needs about 16% more memory.

The AMR wideband speech codec was recently developed for high-quality wideband speech communications. Although it has an excellent performance due to expanded bandwidth of speech signal, it requires a huge amount of computation especially in codebook search. To solve this problem, this paper proposes an efficient codebook search method for AMR wideband codec. Starting from a poorly performing initial codevector, the proposed method enhances the performance of the codevector iteratively by exchanging the worst pulse in the codevector with a better one after evaluating the role of each pulse. Simulations show that the AMR wideband codec adopting the proposed codebook search method provides better performance with much less computational load than that using the standard method.

Many algorithms have been introduced to obtain giga-bit routing performance by reducing searching time. As most of them, however, have not considered the importance of update time and memory requirement seriously, they couldn't work well in real networks. We propose a flexible and fast IP lookup algorithm, named FFILA, considering these factors and compare the performance of our scheme with that of the conventional scheme of Patricia trie.

Novel designs of multiple-valued logic (quaternary) half adder, full adder, and carry-lookahead adder are introduced. The proposed circuits are static and operate in voltage-mode. Moreover, there is no current flow in steady states, and thus, no static power dissipation. Although the comparison in transistor count shows that the proposed quaternary circuits are larger than two respective binary ones, benefits in parallel addition arise from the use of multiple-valued logic. Firstly, the ripple-carry additions are faster because the number of carries is half compared to binary ones and the propagation delay from the input carry through the output carry is relatively small. Secondly, the carry-lookahead scheme exhibits less complexity, which leads to overall reduction in transistor count for addition with large number of bits.

This paper presents some effective methods for improving the performance of a speaker identification system. Based on the multiresolution property of the wavelet transform, the input speech signal is decomposed into various frequency subbands in order not to spread noise distortions over the entire feature space. For capturing the characteristics of the vocal tract, the linear predictive cepstral coefficients (LPCC) of the lower frequency subband for each decomposition process are calculated. In addition, a hard threshold technique for the lower frequency subband in each decomposition process is also applied to eliminate the effect of noise interference. Furthermore, cepstral domain feature vector normalization is applied to all computed features in order to provide similar parameter statistics in all acoustic environments. In order to effectively utilize all these multiband speech features, we propose a modified vector quantization as the identifier. This model uses the multilayer concept to eliminate the interference among the multiband speech features and then uses the principal component analysis (PCA) method to evaluate the codebooks for capturing a more detailed distribution of the speaker's phoneme characteristics. The proposed method is evaluated using the KING speech database for text-independent speaker identification. Experimental results show that the recognition performance of the proposed method is better than those of the vector quantization (VQ) and the Gaussian mixture model (GMM) using full-band LPCC and mel-frequency cepstral coefficients (MFCC) features in both clean and noisy environments. Also, a satisfactory performance can be achieved in low SNR environments.

This paper presents a new technique to implement a convolutional codec in VLSI. The code is used in the Trellis Code Modulation. The technique aims to reduce hardware complexity and increase throughput to decode the convolutional code using Viterbi algorithm. To simplify decoding algorithm and calculation, branch cost distances are pre-calculated and stored in a Distance Look Up Table (DLUT). By using the DLUT to get each branch cost in the algorithm, the hardware implementation of the algorithm does not require any calculation circuits. Furthermore, based on the trellis diagram, an Output Look-Up-Table (OLUT) is also constructed for decoding output generation. This table reduces the amount of storage in the algorithm. The use of look-up tables reduces hardware complexity and increases throughput of the decoder. Using this technique, a 16-states, radix-4 TCM codec with 2-D and 4-D was designed and implemented in both FPGA and ASIC after mathematically simulated. The tested ASIC has a core area of 1.1 mm2 in 0.18 µm CMOS technology and yields a decoding speed over 500 Mbps. Implementation results have shown that LUT can be used to decrease hardware requirement and to increase decoding speed. The designed codec can be used as an IP core to be integrated into system-on-chip applications and the technique can be explored to use to decode the turbo code.

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.

This paper presents a low-power implementation scheme of interpolation FIR filters using distributed arithmetic (DA). The key idea of the proposed scheme involves look-up tables generating only nonnegative values. Thus, the proposed scheme can minimize the dynamic power consumption of interpolation FIR filters using DA without additional hardware. When used for implementing a pulse shaping filter for CDMA2000 mobile stations, the proposed filter not only has almost the same hardware complexity as the conventional one; it also has approximately 43% reduced power consumption.

We propose multibits/sequence-period optical code division multiple access (MS-OCDMA) systems with double optical hardlimiters (DHL) in the presence of APD noise, thermal noise, and channel interference. We apply Reed-Solomon (RS) codes to MS-OCDMA to further improve the error rate performance. We show that the MS-OCDMA receiver with DHL improves the bit error probability of MS-OCDMA systems when the received laser power is large. We also show that the performance of RS coded MS-OCDMA system is better than that of on-off keying OCDMA (OOK-OCDMA) system at the same bit rate and at the same chip rate, respectively.

The virtual memory functions in real-time operating systems have been used in embedded systems. Recent RISC processors provide virtual memory supports through software-managed Translation Lookaside Buffer (TLB) in software. In real-time aspects of the embedded systems, managing TLB entries is the most important because overhead at TLB miss time gives a great effect to overall performance of the system. In this paper, we propose several TLB management algorithms in MIPS processors. In the algorithms, a replaced TLB entry is randomly chosen or managed. We analyze the algorithms by comparing overheads at task switching times and TLB miss times.