In this paper, we study a variant of the MINIMUM DOMINATING SET problem. Given an unweighted undirected graph G=(V,E) of n=|V| vertices, the goal of the MINIMUM SINGLE DOMINATING CYCLE problem (MinSDC) is to find a single shortest cycle which dominates all vertices, i.e., a cycle C such that for the set V(C) of vertices in C and the set N(V(C)) of neighbor vertices of C, V(G)=V(C)∪N(V(C)) and |V(C)| is minimum over all dominating cycles in G [6], [17], [24]. In this paper we consider the (in)approximability of MinSDC if input graphs are restricted to some special classes of graphs. We first show that MinSDC is still NP-hard to approximate even when restricted to planar, bipartite, chordal, or r-regular (r≥3). Then, we show the (lnn+1)-approximability and the (1-ε)lnn-inapproximability of MinSDC on split graphs under P≠NP. Furthermore, we explicitly design a linear-time algorithm to solve MinSDC for graphs with bounded treewidth and estimate the hidden constant factor of its running time-bound.

Concatenated zigzag (CZ) codes are classified as one kind of parallel-concatenated codes with powerful performance and low complexity. This kind of codes has flexible implementation methods and a good application prospect. We propose a modified turbo-type decoder and adaptive extrinsic information scaling method based on the Max-Log-APP (MLA) algorithm, which can provide a performance improvement also under the relatively low decoding complexity. Simulation results show that the proposed method can effectively help the sub-optimal MLA algorithm to approach the optimal performance. Some contrasts with low-density parity-check (LDPC) codes are also presented in this paper.

This paper presents a fully integrated 32-MHz relaxation oscillator (ROSC) capable of sub-1-µs start-up time operation for low-power intermittent VLSI systems. The proposed ROSC employs current mode architecture that is different from conventional voltage mode architecture. This enables compact and fast switching speed to be achieved. By designing transistor sizes equally between one in a bias circuit and another in a voltage to current converter, the effect of process variation can be minimized. A prototype chip in a 0.18-µm CMOS demonstrated that the ROSC generates a stable clock frequency of 32.6 MHz within 1-µs start-up time. Measured line regulation and temperature coefficient were ±0.69% and ±0.38%, respectively.

This paper proposes a classification method of second-language-learner utterances for interactive computer-assisted language learning systems. This classification method uses three types of bilingual evaluation understudy (BLEU) scores as features for a classifier. The three BLEU scores are calculated in accordance with three subsets of a learner corpus divided according to the quality of utterances. For the purpose of overcoming the data-sparseness problem, this classification method uses the BLEU scores calculated using a mixture of word and part-of-speech (POS)-tag sequences converted from word sequences based on a POS-replacement rule according to which words are replaced with POS tags in n-grams. Experiments of classifying English utterances by Japanese demonstrated that the proposed classification method achieved classification accuracy of 78.2% which was 12.3 points higher than a baseline with one BLEU score.

This paper presents a computationally efficient cyclostationarity detection based spectrum sensing technique in cognitive radio. Traditionally, several cyclostationarity detection based spectrum sensing techniques with a low computational complexity have been presented, e.g., peak detector (PD), maximum cyclic autocorrelation selection (MCAS), and so on. PD can be affected by noise uncertainty because it requires a noise floor estimation, whereas MCAS does not require the estimation. Furthermore, the computational complexity of MCAS is greater than that of PD because MCAS must compute some statistics for signal detection instead of the estimation unnecessary whereas PD must compute only one statistic. In the presented MCAS based techniques, only one statistic must be computed. The presented technique obtains other necessary statistics from the procedure that computes the statistic. Therefore, the computational complexity of the presented is almost the same as that of PD, and it does not require the noise floor estimation for threshold. Numerical examples are shown to validate the effectiveness of the presented technique.

Rough set theory is an important branch of data mining and granular computing, among which neighborhood rough set is presented to deal with numerical data and hybrid data. In this paper, we propose a new concept called inconsistent neighborhood, which extracts inconsistent objects from a traditional neighborhood. Firstly, a series of interesting properties are obtained for inconsistent neighborhoods. Specially, some properties generate new solutions to compute the quantities in neighborhood rough set. Then, a fast forward attribute reduction algorithm is proposed by applying the obtained properties. Experiments undertaken on twelve UCI datasets show that the proposed algorithm can get the same attribute reduction results as the existing algorithms in neighborhood rough set domain, and it runs much faster than the existing ones. This validates that employing inconsistent neighborhoods is advantageous in the applications of neighborhood rough set. The study would provide a new insight into neighborhood rough set theory.

We propose a policy UCB-SC for budgeted multi-armed bandits. The policy is a variant of recently proposed KL-UCB-SC. Unlike KL-UCB-SC, which is computationally prohibitive, UCB-SC runs very fast while keeping KL-UCB-SC's asymptotical optimality when reward and cost distributions are Bernoulli with means around 0.5, which are verified both theoretically and empirically.

Irreversible thermal paints or temperature sensitive paints are a kind of special temperature sensor which can indicate the temperature grad by judging the color change and is widely used for off-line temperature measurement during aero engine test. Unfortunately, the hot gases flow within the engine during measuring always make the paint color degraded, which means a serious saturation reduction and contrast loss of the paint colors. This phenomenon makes it more difficult to interpret the thermal paint test results. Present contrast enhancement algorithms can significantly increase the image contrast but can't protect the hue feature of the paint images effectively, which always cause color shift. In this paper, we propose a color restoration method for thermal paint image. This method utilizes the atmospheric scattering model to restore the lost contrast and saturation information, so that the hue can be protected and the temperature can be precisely interpreted based on the image.

The centralized controller of SDN enables a global topology view of the underlying network. It is possible for the SDN controller to achieve globally optimized resource composition and utilization, including optimized end-to-end paths. Currently, resource composition in SDN arena is usually conducted in an imperative manner where composition logics are explicitly specified in high level programming languages. It requires strong programming and OpenFlow backgrounds. This paper proposes declarative path composition, namely Compass, which offers a human-friendly user interface similar to natural language. Borrowing methodologies from Semantic Web, Compass models and stores SDN resources using OWL and RDF, respectively, to foster the virtualized and unified management of the network resources regardless of the concrete controller platform. Besides, path composition is conducted in a declarative manner where the user merely specifies the composition goal in the SPARQL query language instead of explicitly specifying concrete composition details in programming languages. Composed paths are also reused based on similarity matching, to reduce the chance of time-consuming path composition. The experiment results reflect the applicability of Compass in path composition and reuse.

In this paper, we study parallel join processing to improve the performance of the merge phase of sort-merge join by integrating all parallelism provided by mainstream CPUs. Modern CPUs support SIMD instruction sets with wider SIMD registers which allows to process multiple data items per each instruction. Thus, we devise an efficient parallel join algorithm, called Parallel Merge Join with SIMD instructions (PMJS). In our proposed algorithm, we utilize data parallelism by exploiting SIMD instructions. And we also accelerate the performance by avoiding the usage of conditional branch instructions. Furthermore, to take advantage of the multiple cores, our proposed algorithm is threaded in multi-thread environments. In our multi-thread algorithm, to distribute workload evenly to each thread, we devise an efficient workload balancing algorithm based on the kernel density estimator which allows to estimate the workload of each thread accurately.

This paper proposes an iterative scheme between human action classification and pose estimation in still images. Initial action classification is achieved only by global image features that consist of the responses of various object filters. The classification likelihood of each action weights human poses estimated by the pose models of multiple sub-action classes. Such fine-grained action-specific pose models allow us to robustly identify the pose of a target person under the assumption that similar poses are observed in each action. From the estimated pose, pose features are extracted and used with global image features for action re-classification. This iterative scheme can mutually improve action classification and pose estimation. Experimental results with a public dataset demonstrate the effectiveness of the proposed method both for action classification and pose estimation.

A grammar compression is a restricted context-free grammar (CFG) that derives a single string deterministically. The goal of a grammar compression algorithm is to develop a smaller CFG by finding and removing duplicate patterns, which is simply a frequent pattern discovery process. Any frequent pattern can be obtained in linear time; however, a huge working space is required for longer patterns, and the entire string must be preloaded into memory. We propose an online algorithm to address this problem approximately within compressed space. For an input sequence of symbols, a1,a2,..., let Gi be a grammar compression for the string a1a2…ai. In this study, an online algorithm is considered one that can compute Gi+1 from (Gi,ai+1) without explicitly decompressing Gi. Here, let G be a grammar compression for string S. We say that variable X approximates a substring P of S within approximation ratio δ iff for any interval [i,j] with P=S[i,j], the parse tree of G has a node labeled with X that derives S[l,r] for a subinterval [l,r] of [i,j] satisfying |[l,r]|≥δ|[i,j]|. Then, G solves the frequent pattern discovery problem approximately within δ iff for any frequent pattern P of S, there exists a variable that approximates P within δ. Here, δ is called the approximation ratio of G for S. Previously, the best approximation ratio obtained by a polynomial time algorithm was Ω(1/lg2|P|). The main contribution of this work is to present a new lower bound Ω(1/<*|S|lg|P|) that is smaller than the previous bound when lg*|S|

IEEE 802.11ah is a new wireless standard for large-scale wireless connectivity in IoT and M2M applications. One of the major requirements placed on IEEE 802.11ah is the energy-efficient communication of several thousand stations with a single access point. This is especially difficult to achieve during network initialization, because the several thousand stations must rely on the rudimentary approach of random channel access, and the inevitable increase in channel access contention yields a long association delay. IEEE 802.11ah has introduced an authentication control mechanism that classifies stations into groups, and only a small number of stations in a group are allowed to access the medium at a time. Although the grouping strategy provides fair channel access to a large number of stations, the presence of several thousand stations and limitation that only a group can use the channel at a time, causes the association time to remain excessive. In this paper, we propose a novel block association method that enables simultaneous association of all groups. Our experiments verify that our block association method decreases the total association time by many folds.

The conventional generalized spatial modulation (GSM) simultaneously activates multiple transmit antennas in order to improve the spectral efficiency of the original SM. In this letter, to lessen the hardware burden of the multiple RF chains, we provide a new scheme that is designed by combining the GSM scheme using only two active antennas with quaternary quasi-orthogonal sequences of a length of two. Compared with the other SM schemes, the proposed scheme has significant benefits in average error performances and/or their hardware complexities of the RF systems.

Deep neural network (DNN)-based speech synthesis can produce more natural synthesized speech than the conventional HMM-based speech synthesis. However, it is not revealed whether the synthesized speech quality can be improved by utilizing a multi-speaker speech corpus. To address this problem, this paper proposes DNN-based speech synthesis using speaker codes as a method to improve the performance of the conventional speaker dependent DNN-based method. In order to model speaker variation in the DNN, the augmented feature (speaker codes) is fed to the hidden layer(s) of the conventional DNN. This paper investigates the effectiveness of introducing speaker codes to DNN acoustic models for speech synthesis for two tasks: multi-speaker modeling and speaker adaptation. For the multi-speaker modeling task, the method we propose trains connection weights of the whole DNN using a multi-speaker speech corpus. When performing multi-speaker synthesis, the speaker code corresponding to the selected target speaker is fed to the DNN to generate the speaker's voice. When performing speaker adaptation, a set of connection weights of the multi-speaker model is re-estimated to generate a new target speaker's voice. We investigated the relationship between the prediction performance and architecture of the DNNs through objective measurements. Objective evaluation experiments revealed that the proposed model outperformed conventional methods (HMMs, speaker dependent DNNs and multi-speaker DNNs based on a shared hidden layer structure). Subjective evaluation experimental results showed that the proposed model again outperformed the conventional methods (HMMs, speaker dependent DNNs), especially when using a small number of target speaker utterances.

An optimal design method for a sub-ranging Analog-to-Digital Converter (ADC) based on stochastic comparator is demonstrated by performing theoretical analysis of random comparator offset voltages. If the Cumulative Distribution Function (CDF) of the comparator offset is defined appropriately, we can calculate the PDFs of the output code and the effective resolution of a stochastic comparator. It is possible to model the analog-to-digital conversion accuracy (defined as yield) of a stochastic comparator by assuming that the correlations among the number of comparator offsets within different analog steps corresponding to the Least Significant Bit (LSB) of the output transfer function are negligible. Comparison with Monte Carlo simulation verifies that the proposed model precisely estimates the yield of the ADC when it is designed for a reasonable target yield of >0.8. By applying this model to a stochastic comparator we reveal that an additional calibration significantly enhances the resolution, i.e., it increases the Number of Bits (NOB) by ∼ 2 bits for the same target yield. Extending the model to a stochastic-comparator-based sub-ranging ADC indicates that the ADC design parameters can be tuned to find the optimal resource distribution between the deterministic coarse stage and the stochastic fine stage.

Field-programmable gate array (FPGA) devices are applied for accelerating specific calculations and reducing power consumption in a wide range of areas. One of the challenges associated with FPGAs is reducing static power for enforcing their power effectiveness. We propose a method involving fine-grained reconfiguration of body biases of logic and net resources to reduce the static power of FPGA devices. In addition, we develop an FPGA device called Flex Power FPGA with SOTB technology and demonstrate its power reduction function with a 32-bit counter circuit. In this paper, we describe the construction of an experimental platform to precisely evaluate power consumption and the maximum operating frequency of the device under various operating voltages and body biases with various practical circuits. Using the abovementioned platform, we evaluate the Flex Power FPGA chip at operating voltages of 0.5-1.0 V and at body biases of 0.0-0.5 V. In the evaluation, we use a 32-bit adder, 16-bit multiplier, and an SBOX circuit for AES cryptography. We operate the chip virtually with uniformed body bias voltage to drive all of the logic resources with the same threshold voltage. We demonstrate the advantage of the Flex Power FPGA by comparing its performance with non-reconfigurable biasing.

A 2nd-order ΔΣAD modulator architecture is proposed to simplify the operation phase using ring amplifier and SAR quantizer. The proposed modulator architecture can guarantee the reset time for ring amplifier and relax the speed requirement on asynchronous SAR quantizer. The SPICE simulation results demonstrate the feasibility of the proposed 2nd-order ΔΣAD modulator in 90nm CMOS technology. Simulated SNDR of 95.70dB is achieved while a sinusoid -1dBFS input is sampled at 60MS/s for the bandwidth is BW=470kHz. The power consumption of the analog part in the modulator is 1.67mW while the supply voltage is 1.2V.

This paper proposes a circuit modeling technique for electrically-very-small devices, e.g. electrodes for intrabody communications, coils for wireless power transfer systems, high-frequency transformers, etc. The proposed technique is based on the method of moments and can be regarded as an improved version of the partial element equivalent circuit method.

This letter presents a 12-bit column-parallel hybrid two-step successive approximation register/single-slope analog-to-digital converter (SAR/SS ADC) for CMOS image sensor (CIS). For achieving a high conversion speed, a simple SAR ADC is used in upper 6-bit conversion and a conventional SS ADC is used in lower 6-bit conversion. To reduce the power consumption, a comparator is shared in each column, and a 6-bit ramp generator is shared by all columns. This ADC is designed in SMIC 0.18µm CMOS process. At a clock frequency of 22.7MHz, the conversion time is 3.2µs. The ADC has a DNL of -0.31/+0.38LSB and an INL of -0.86/+0.8LSB. The power consumption of each column ADC is 89µW and the ramp generator is 763µW.