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.

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.

In this paper we describe a new framework of feature compensation for robust speech recognition, which is suitable especially for small devices. We introduce Delta-cepstrum Normalization (DCN) that normalizes not only cepstral coefficients, but also their time-derivatives. Cepstral Mean Normalization (CMN) and Mean and Variance Normalization (MVN) are fast and efficient algorithms of environmental adaptation, and have been used widely. In those algorithms, normalization was applied to cepstral coefficients to reduce the irrelevant information from them, but such a normalization was not applied to time-derivative parameters because the reduction of the irrelevant information was not enough. However, Histogram Equalization (HEQ) provides better compensation and can be applied even to the delta and delta-delta cepstra. We investigate various implementation of DCN, and show that we can achieve the best performance when the normalization of the cepstra and the delta cepstra can be mutually interdependent. We evaluate the performance of DCN using speech data recorded by a PDA. DCN provides significant improvements compared to HEQ. It is shown that DCN gives 15% relative word error rate reduction from HEQ. We also examine the possibility of combining Vector Taylor Series (VTS) and DCN. Even though some combinations do not improve the performance of VTS, it is shown that the best combination gives the better performance than VTS alone. Finally, the advantage of DCN in terms of the computation speed is also discussed.

This paper describes a VLSI-oriented motion estimation algorithm using a steepest descent method (SDM) applied to MPEG-4 visual communication with a mobile terminal. The SDM algorithm is optimized for QCIF or CIF resolution video and VLSI implementation. The SDM combined with a subblock search method is developed to enhance picture quality. Simulation results show that a mean PSNR drop of the SDM algorithm processing QCIF 15 fps resolution video in comparison with a full search algorithm is -0.17 dB. Power consumption of a VLSI based on the SDM algorithm assuming 0.18 µm CMOS technology is estimated at 2 mW. The VLSI attains higher picture quality than that based on the other fast motion estimation algorithm, and is applicable to mobile video applications.

In this paper, we describe a feed-forward dynamic voltage/clock-frequency control method enabling low power MPEG4 on multi-regulated voltage CPU with combining the characteristics of the CPU and the video encoding processing. This method theoretically achieves minimum low power consumption which is close to the hardware-level power consumption. Required processing performance for MPEG4 visual encoding totally depends on the activity of the sequence, and high motion sequence requires high performance and low motion sequence requires low performance. If required performance is predictable, lower power consumption can be achieved with controlling the adequate voltage and clock-frequency dynamically at every frame. The proposed method in this paper is predicting the required processing performance of a future frame using our unique feed-forward analysis method and controlling a voltage and frequency dynamically at every frame along with the forward analysis value. The simulation results indicate that the proposed feed-forward analysis method adequately predicts the required processing performance of every future frame, and enables to minimize power consumption on software basis MPEG4 visual encoding processing. In the case that CPU has Frequency-Voltage characteristics of 1.8 V @400 MHz to 1.0 V @189 MHz, the proposed method reduces the power consumption approximately 37% at high motion sequences or 65% at low motion sequences comparing with the conventional software video encoding method.

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.

A low-power microcontroller has been developed with 0.10 µm bulk compatible body-tied SOI technology. For this work, only two new masks are required. For the other layers, existing masks of a prior work developed with 0.18 µm bulk CMOS technology can be applied without any changes. With the SOI technology, the high-speed operation of over 600 MHz has been achieved at a supply voltage of 1.2 V, which is 1.5 times faster than prior work. Also, a five times improvement in the power-delay product has been achieved at a supply voltage 0.8 V. Moreover, the compatibility of the SOI technology with bulk CMOS has been verified, because all circuit blocks of the chip, including logic, memory, analog circuit, and PLL, are completely functional, even though only two new masks are used.

Watermarking schemes have been extensively discussed and developed recently. People are usually facing the dilemma of two factors, robustness and transparency. To achieve these requirements, embedding the watermark message in the transform domain or the spatial domain is usually considered. In this paper, we will propose a blind image watermarking scheme based on vector quantization. By exploiting a modified binary tree splitting method, a stable codebook could be generated so that the watermark message could be novelly embedded and survive the JPEG compression and the Gaussian noise addition. The embedded message could be extracted without referring the host image. It makes the scheme more practical.

A sequentially and linearly constrained minimum variance beamformer (SLCMV), based on a split polarity transformation (SPT) and, called an SPT-SLCMV beamformer, is proposed to minimize the degree of freedom loss, steering error, and a desired signal elimination phenomenon under coherent interferences. The SPT-SLCMV beamformer reduces the degree of freedom loss, which is inevitable in the conventional SPT-LCMV beamformer, by successively applying sub-constraint matrices. Sub-constraint matrices are derived from a complete constraint matrix to remove the correlation between the desired signal and interferences. In addition, the SPT-SLCMV beamformer is combined with the iterative steering error correction method to reduce the steering error between the look direction of the beamformer and the incident angle of the desired signal. As a result, the proposed beamformer reduces the number of array elements while maintaining the performance of an exactly steered SPT-LCMV beamformer having sufficient array elements under coherent interferences.

Scenarios that describe concrete situations of software operation play an important role in software development and especially in requirements engineering. Scenario details should vary in content when described from different viewpoints, but this presents a difficulty, because an informal scenario from one viewpoint can not easily be transformed into a scenario from another viewpoint with consistency and assurance. This paper describes (1) a language for describing scenarios in which simple action traces are embellished to include typed frames based on a simple case grammar of actions, and (2) a method to accomplish the transformation between scenarios from different viewpoints based on the scenario description language.

Goal-oriented analysis and use case analysis are well known requirements analysis methods and are putting into practice. Roughly speaking, goal-oriented methods are suitable for eliciting constraints to a system and use case analysis methods elicit concrete system behavior. Thus these methods are complementary and their integration into a new method allows us to get a more powerful requirements elicitation method. This paper proposes a new method where both of the methods are amalgamated. In our method, constraints to the system are refined by goal-oriented style, while system behavior are described with hierarchical use cases. Since a use case is made relate to goals during our elicitation processes, the decomposition of goals and use cases are complementally supported. Furthermore we applied our method to a couple of development projects and assessed its effectiveness.

A new high-speed and low-power digital signal processor (DSP) core, C55x, was developed for next generation applications such as 3G cellular phone, PDA, digital still camera (DSC), audio, video, embedded modem, DVD, and so on. To support such MIPS-rich applications, a packet size of an instruction fetch increased from 16-bit to 32-bit comparing with the world's most popular C54x DSP core, while maintaining complete software compatibility with the legacy DSP code. An on-chip instruction buffer queue (IBQ) automatically unpacks the packets and issues multiple instructions in parallel for the efficient use of circuit resources. The efficiency of the parallelism has been further improved by additional hardwares such as second 1717-bit MAC, a 16-bit ALU, and three temporary registers that can be used for simple computations. Four 40-bit accumulators make it possible to execute more operation per cycle with dramatically reduced overall power consumption. These new architecture allows two times efficiency of instruction per cycle (IPC) than the previous DSP core on typical applications at the same MHz. The new DSP core was designed for TI's two 130 nm technologies, one with high-VT for low-leakage and middle-performance operation at 1.5 V, and the other with low-VT for high-performance and low-VDD operation at 1.2 V, to provide best choices for any applications with a single layout data base. With the low-leakage process, the DSP core operates at over 200 MHz with 188 µA/MHz (at 75% Dual MAC + 25% ADD) active power and less than 1.63 µA standby current. The high-performance process provides it with 300 MHz with 169 µA/MHz active power and less than 680 µA standby current. The new core was designed by a semi-custom approach (ASIC + custom library) using 5-level Cu metal system with low-k dielectric material of fluorosilicate glass (FSG), and about one million transistors are contained in the core. The total balance of its power, performance, area, and leakage current (PPAL) is well suitable to most of next generation applications. In this paper, we will discuss features of the new DSP core, including circuit design techniques for high-speed and low-power, and present an example product.

This letter presents a novel quandtree-based image authentication technique especially suitable for the content authentication of high quality required digital images. The host image and the hiding marks generate quadtrees which record the information of host images. Any malicious tamper to the image is reflected from the recovered marks. Compared to other authentication schemes based on the fragile watermarking technique, the host image is not at all modified and the detection to malicious tamper is sensitive.

In this paper, an area efficient VLSI architecture of decision feedback equalizer is derived accommodating 64/256 QAM modulators. This architecture is implemented efficiently in VLSI structure using EDA tools due to its regular structure. The method is to employ a time-multiplexed design scheme, so-called Folding, which executes multiple operation on a single functional unit. In addition, we define a new folding set by grouping the adjacent filter taps with data transfer having the same processing sequence between blocks and perform the internal data-bit optimization. By doing so, the computational complexity is reduced by performance optimization and also silicon area is reduced by using a shared operator. Moreover, through the performance and convergence time comparison of the various LMS (e.g. LMS, data signed LMS, error signed LMS, signed-signed LMS) ) coefficient updating algorithms, we identify an optimum LMS algorithm scheme suitable for the low complexity, high performance and high order (64 and 256) QAM applications for the presented Fractionally Spaced Decision Feedback Equalizer. We simulated the proposed design scheme using SYNOPSYSTM and SPWTM.

There exists a class of nonlinear systems which fail to have a well-defined relative degree but have a robust relative degree. We have removed the full relative degree assumption which the previous results required, and have provided a local state observer for nonlinear systems that have robust relative degree γ n and have detectability property in some sense. The proposed observer utilizes the coordinate change which transforms the system into an approximate normal form. Using the proposed method, we constructed an observer for the ball and beam system on a vibrating frame. Simulation results reveal that substantial improvement in the performance is achieved compared with other local observers.

As the Internet grows, various types of traffic, such as voice, video and data, are transmitted. Therefore, the Internet should provide the Quality of Service (QoS) required by each type of traffic as well as end-to-end connectivity, and routing decisions should be based on the utilization of links/routers and/or the application types of traffic. This kind of routing is called Traffic Engineering (TE), and its objective is to improve such performance factors as flow loss probability for users and the utilization of links for networks, simultaneously. Some studies claim that the Multi-Protocol Label Switching (MPLS) technique can easily implement TE. So far, some experimental results show that TE is effective on a MPLS network; however, its performance has not been theoretically and quantitatively analyzed. Thus, in this paper, we will investigate the basic and preliminary performance of MPLS networks with TE by analyzing flow loss probability and Smoothness index of link utilization in the queueing system.

In this paper, we propose a preemptive test scheduling technique (a test can be interrupted and later resumed) for core-based systems with the objective to minimize the test application time. We make use of reconfigurable core test wrappers in order to increase the flexibility in the scheduling process. The advantage with such a wrapper is that it is not limited to a single TAM (test access mechanism) bandwidth (wrapper chain configuration) at each core. We model the scheduling problem as a Bin-packing problem, and we discuss the transformation: number of TAM wires (wrapper-chains) versus test time in combination with preemption, as well as the possibilities and the limitations to achieve an optimal solution in respect to test application time. We have implemented the proposed preemptive test scheduling algorithm, and we have through experiments demonstrated its efficiency.

Channel estimation is one of the key technologies in mobile communications. Channel estimation is critical in providing high data rate services and to overcome fast fading in very high-speed mobile communications. This paper presents a novel channel estimation based on hybrid spreading of I and Q signals (CEHS). Simulation results show that it can effectively mitigate the influence of fast fading and enable to provide high data rates for very high speed mobile systems.

FEC (Forward Error Correction) can repair the damage to communication quality due to packet loss. The growing requirement of FEC for high-quality video transmission is inevitable on broadband networks. We have designed and implemented FEC, and integrated it to our developed video transmission system named "mpeg2ts." Our goal is to make it possible to deploy this system on the broadband Internet. However, the problem with constant redundancy of FEC is that weakness to fluctuation of network condition. To resolve this problem, in this paper, we propose and evaluate an efficient FEC method for high-quality video transmission. The proposed mechanisms can provide robustness as well as saving of processing load and optimization of bandwidth consumption. Moreover, we integrate it into a system to deploy it on the real broadband Internet. Transmission experiment demonstrates availability of developed system deployed on the network.

This paper deals with the statistical modeling of a Time-Frequency Series of Speech (TFSS), obtained by Short-Time Fourier Transform (STFT) analysis of the speech signal picked up by a linear microphone array with two elements. We have attempted to find closer match between the distribution of the TFSS and theoretical distributions like Laplacian Distribution (LD), Gaussian Distribution (GD) and Generalized Gaussian Distribution (GGD) with parameters estimated from the TFSS data. It has been found that GGD provides the best models for real part, imaginary part and polar magnitudes of the time-series of the spectral components. The distribution of the polar magnitude is closer to LD than that of the real and imaginary parts. The distributions of the real and imaginary parts of TFSS correspond to strongly LD. The phase of the TFSS has been found uniformly distributed. The use of GGD based model as PDF in the fixed-point Frequency Domain Independent Component Analysis (FDICA) provides better separation performance and improves convergence speed significantly.