Let H be a graph with a designated vertex s, where edges are weighted by nonnegative reals. Splitting edges e={u,s} and e'={s,v} at s is an operation that reduces the weight of each of e and e' by a real δ>0 while increasing the weight of edge {u,v} by δ. It is known that all edges incident to s can be split off while preserving the edge-connectivity of H and that such a complete splitting is used to solve many connectivity problems. In this paper, we give an O(mn+n2log n) time algorithm for finding a complete splitting in a graph with n vertices and m edges.

The release of image processing techniques make image modification and fakery easier. Image fakery, here, is defined as a process to copy a region of source image and paste it onto the destination image, with some post processing methods applied, such as boundary smoothing, blurring, etc. to make it natural. The most important characteristic of image fakery is object copy and paste. In order to detect fake images, this letter introduces a blind detection scheme based on singular value decomposition (SVD). Experimental results also show the effectiveness of the proposed scheme.

For a property π on graphs, the edge-contraction problem with respect to π is defined as a problem of finding a set of edges of minimum cardinality whose contraction results in a graph satisfying the property π. This paper gives a lower bound for the approximation ratio for the problem for any property π that is hereditary on contractions and determined by biconnected components.

We first model the variants of OAEP and SAEP by changing a construction and position of a redundancy, and establish a universal proof technique in the random oracle model, the comprehensive event dividing tree. We then make a taxonomical security consideration of the variants of OAEP and SAEP, based on the assumptions of one-wayness and partial-domain one-wayness of the encryption permutation, by applying the tree. Furthermore, we demonstrate the concrete attack procedures against all insecure schemes; we insist that the security proof failure leads to some attacks. From the security consideration, we find that one of the variants leads to a scheme without the redundancy; the scheme is not PA (plaintext aware) but IND-CCA2 secure. Finally, we conclude that some of them are practical in terms of security tightness and short bandwidth.

This paper presents a synthesizable testbench architecture based on a defined instruction for standalone mode verification. A set of instructions describes transitions of a signal. The set of instructions can be changed easily to describe different signal transitions by loading the different set of instructions on emulator's memory. The proposed testbench enables a fast emulation and increases flexibility and reusability by using an instruction set. To prove the performance of instruction based synthesizable testbench, we verified Bluetooth and IEEE 802.11a PHY baseband systems and compared their performance with those of co-sim mode and modified co-sim mode emulation.

This paper deals with the diffraction of TM plane wave by a perfectly conductive periodic surface. Applying the Rayleigh hypothesis, a linear equation system determining the diffraction amplitudes is derived. The linear equation is formally solved by Cramer's formula. It is then found that, when the angle of incidence becomes a low grazing limit, the amplitude of the specular reflection becomes -1 and any other diffraction amplitudes vanish for any perfectly conductive periodic surfaces with small roughness and gentle slope.

A hybrid evolutionary neuro-fuzzy system (HENFS) is proposed in this paper, where the weighted Gaussian function (WGF) is used as the membership function for improved premise construction. With the WGF, different types of the membership functions (MFs) can be accommodated in the rule base of HENFS. A new hybrid algorithm of random optimization (RO) algorithm incorporated with the least square estimation (LSE) is presented. Based on the hybridization of RO-LSE, the proposed soft-computing approach overcomes the disadvantages of other widely used algorithms. The proposed HENFS is applied to chaos time series identification and industrial process modeling to verify its feasibility. Through the illustrations and comparisons the impressive performances for unknown system identification can be observed.

In software development, comprehensive software reviews and testings are important activities to preserve high quality and to control maintenance cost. However it would be actually difficult to perform comprehensive software reviews and testings because of a lot of components, a lack of manpower and other realistic restrictions. To improve performances of reviews and testings in object-oriented software, this paper proposes a novel model for detecting cost-prone classes; the model is based on Mahalanobis-Taguchi method--an extended statistical discriminant method merging with a pattern recognition approach. Experimental results using a lot of Java software are provided to statistically demonstrate that the proposed model has a high ability for detecting cost-prone classes.

In recent years, digital watermarking has become a popular technique for labeling digital images by hiding secret information which can protect the copyright. The goal of this paper is to develop a DCT-based watermarking algorithm for low power and high performance. Our energy-efficient technique focuses on reducing computation required on block-based permutation. Instead of using spacial coefficients proposed by Hsu and Wu's algorithm [1], we use DCT coefficients to pair blocks directly. The approach is implemented by C language and estimated power dissipation using Wattch toolset. The experimental results show that our approach not only reduces 99% energy consumption of pairing mechanism, but also increase the PSNR by 0.414 db for the best case. Moreover, the proposed approach is robust to a variety of signal distortions, such as JPEG, image cropping, sharpening, blurring, and intensity adjusting.

A time domain (TD) speech enhancement technique to improve SNR in noise-contaminated speech is proposed. Additional supplementary scheme is applied to estimate the degree of noise of noisy speech. This is estimated from a function, which is previously prepared as the function of the parameter of the degree of noise. The function is obtained by least square (LS) method using the given degree of noise and the estimated parameter of the degree of noise. This parameter is obtained from the autocorrelation function (ACF) on frame-by-frame basis. This estimator almost accurately estimates the degree of noise and it is useful to reduce noise. The proposed method is based on two-stage processing. In the first stage, subtraction in time domain (STD), which is equivalent to ordinary spectral subtraction (SS), is carried out. In the result, the noise is reduced to a certain level. Further reduction of noise and by-product noise residual is carried out in the second stage, where blind source separation (BSS) technique is applied in time domain. Because the method is a single-channel speech enhancement, the other signal is generated by taking the noise characteristics into consideration in order to apply BSS. The generated signal plays a very important role in BSS. This paper presents an adaptive algorithm for separating sources in convolutive mixtures modeled by finite impulse response (FIR) filters. The coefficients of the FIR filter are estimated from the decorrelation of two mixtures. Here we are recovering only one signal of interest, in particular the voice of primary speaker free from interfering noises. In the experiment, the different levels of noise are added to the clean speech signal and the improvement of SNR at each stage is investigated. The noise types considered initially in this study consist of the synthesized white and color noise with SNR set from 0 to 30 dB. The proposed method is also tested with other real-world noises. The results show that the satisfactory SNR improvement is attained in the two-stage processing.

This paper shows that the Surrounding Gate Transistor (SGT) can be scaled down to decananometer gate lengths by using an intrinsically-doped body and gate work function engineering. Strong gate controllability is an essential characteristics of the SGT. However, by using an intrinsically-doped body, the SGT can realize a higher carrier mobility and stronger gate controllability of the silicon body. Then, in order to adjust the threshold voltage, it is necessary to adopt gate work function engineering in which a metal or metal silicide gate is used. Using a three-dimensional (3D) device simulator, we analyze the short-channel effects and current characteristics of the SGT. We compare the device characteristics of the SGT to those of the Tri-gate transistor and Double-Gate (DG) MOSFET. When the silicon pillar diameter (or silicon body thickness) is 10 nm, the gate length is 20 nm, and the oxide thickness is 1 nm, the SGT shows a subthreshold swing of 63 mV/dec and a DIBL of -17 mV, whereas the Tri-gate transistor and the DG MOSFET show a subthreshold swing of 71 mV/dec and 77 mV/dec, respectively, and a DIBL of -47 mV and -75 mV, respectively. By adjusting the value of the gate work function, we define the off current at VG = 0 V and VD = 1 V. When the off current is set at 1 pA/µm, the SGT can realize a high on current of 1020 µA/µm at VG = 1 V and VD = 1 V. Moreover, the on current of the SGT is 21% larger than that of the Tri-gate transistor and 52% larger than that of the DG MOSFET. Therefore, the SGT can be scaled reliably toward the decananometer gate length for high-speed and low-power ULSI.

The k-edge-connectivity augmentation problem for a specified set of vertices of a graph with degree constraints, kECA-SV-DC, is defined as follows: "Given an undirected multigraph G = (V,E), a specified set of vertices S ⊆V and a function g: V → Z+ ∪{∞}, find a smallest set E' of edges such that (V,E ∪ E') has at least k edge-disjoint paths between any pair of vertices in S and such that, for any v ∈ V, E' includes at most g(v) edges incident to v, where Z+ is the set of nonnegative integers." This paper first shows polynomial time solvability of kECA-SV-DC and then gives a linear time algorithm for 2ECA-SV-DC.

In this paper, a practical clock-scheduling engine is introduced. The minimum feasible clock-period is obtained by using a modified Bellman-Ford shortest path algorithm. Then an optimum cost clock-schedule is obtained by using a bipartite matching algorithm. It also provides useful information to circuit synthesis tools. The experiment to a circuit with about 10000 registers and 100000 signal paths shows that a result is obtained within a few minutes. The computation time is almost linear to the circuit size in practice.

Software inspection is a widely acknowledged effective quality improvement method in software development by detecting defects involved in software artifacts and removing them. In research on software inspection, constructing computer supported inspection systems is a major topic in the field. A lot of systems have been reported. However few inspection support systems for model diagrams, especially UML diagrams, have been emerged. We identified four key requirements an inspection support system for UML diagrams should have. They are as follows: 1) direct annotations are given to model diagrams, 2) version management is provided so that evolution of artifacts can be managed, 3) the whole inspection process should be supported, 4) horizontal and vertical readings are supported. This paper describes design and implementation of our inspection support system for UML diagrams to realize the four requirements.

A recursive-type positive integer code is proposed. It prefixes the information about the length of the component of the codeword recursively. It is an asymptotically optimal code. The codeword length for a positive integer n is shorter than n bits in almost all of sufficiently large positive integers, where n is the log-star function.

We have proposed a neural network called the Lagrange programming neural network with polarized high-order connections (LPPH) for solving the satisfiability problem (SAT) of propositional calculus. The LPPH has gradient descent dynamics for variables and gradient ascent dynamics for Lagrange multipliers, which represent the weights of the clauses of the SAT. Each weight wr increases according to the degree of unsatisfaction of clause Cr. This causes changes in the energy landscape of the Lagrangian function, on which the values of the variables change in the gradient descent direction. It was proved that the LPPH is not trapped by any point that is not a solution of the SAT. Experimental results showed that the LPPH can find solutions faster than existing methods. In the LPPH dynamics, a function hr(x) calculates the degree of unsatisfaction of clause Cr via multiplication. However, this definition of hr(x) has a disadvantage when the number of literals in a clause is large. In the present paper, we propose a new definition of hr(x) in order to overcome this disadvantage using the "min" operator. In addition, we extend the LPPH to solve the constraint satisfaction problem (CSP). Our neural network can update all neurons simultaneously to solve the CSP. In contrast, conventional discrete methods for solving the CSP must update variables sequentially. This is advantageous for VLSI implementation.

In general, a corner model with best- and worst-case delay conditions is used in static timing analysis (STA). The best- and worst-case delays of a stage are defined as the fastest and slowest delays from a cell input to the next cell input. In this paper, we present a methodology for determining the parameters that yield the best- and worst-case delays when interconnect structural parameters have the minimum and maximum values with process variations. We also present analysis results of our circuit model using the methodology. The min and max conditions for the time constant are found to be (+Δw, +Δt, +Δh) & (-Δw, -Δt, -Δh), respectively. Here, +Δ or -Δ means the max or min corner value of each parameter variation, where w is the width, t is the interconnect thickness, and h is the height. Best and worst conditions for delay time are as follows: 1) given a circuit with an optimum driver, dense interconnects, and small branch capacitance, the best and worst conditions are respectively (-Δw, +Δt, +Δh) & (+Δw, +Δt, -Δh), 2) given driver and/or via resistances that are higher than the interconnect resistance, dense interconnects, and small branch capacitance, they are (-Δw, -Δt, +Δh) & (+Δw, +Δt, -Δh), and 3) for other conditions, they are (+Δw, +Δt, +Δh) & (-Δw, -Δt, -Δh). Moreover, if there must be only one condition each for the best- and worst-case delays, they are (+Δw, +Δt, +Δh) & (-Δw, -Δt, -Δh).

Since a human object is an important element of the moving pictures being processed by mobile terminals, establishing a human object extraction method encourages dissemination of new applications. In accordance with the requirement of mobile applications, this paper proposes a low-cost human object extraction method, which consists of a face object and a hair object extraction based on their color information and a simple body extraction utilizing the position information of the face object. In the proposed method, skin color and hair color are estimated through color space segmentation, and a human object is effectively extracted by using a radial active contour model. Simulation results of the human object extraction with the use of XScale processor claims that QCIF 15 fps video sequences can be processed in real time.

Rendering realistic trees is quite important for simulating a 3D natural scene. Separating the trunk from its background is the first step toward the 3D model construction of the tree. In this paper, a three-phase algorithm is developed to extract the trunk structure of the tree and hence segment the trunk from the image. Some experiments were conducted and results confirmed the feasibility of proposed algorithm.

Voice activity detection (VAD) determines whether a slice of waveform is voice or silence. The proposed VAD algorithm applying Elliptical Basis Function (EBF) neural networks uses k-means clustering and least mean square for the update algorithm. The error rates achieved by the EBF network have superior performance to those of G.729 Annex B and RBF.