We show teachability of a subclass of simple deterministic languages. The subclass we define is called stack uniform simple deterministic languages. Teachability is derived by showing the query learning algorithm for this language class. Our learning algorithm uses membership, equivalence and superset queries. Then, it terminates in polynomial time. It is already known that simple deterministic languages are polynomial time query learnable by context-free grammars. In contrast, our algorithm guesses a hypothesis by a stack uniform simple deterministic grammar, thus our result is strict teachability of the subclass of simple deterministic languages. In addition, we discuss parameters of the polynomial for teachability. The “thickness” is an important parameter for parsing and it should be one of parameters to evaluate the time complexity.

In this paper, we propose a synthesizable LDPC decoder IP core for the WiMAX system with high parallelism and enhanced error-correcting performance. By taking the advantages of both layered scheduling and fully-parallel architecture, the decoder can fully support multi-mode decoding specified in WiMAX with the parallelism much higher than commonly used partial-parallel layered LDPC decoder architecture. 6-bit quantized messages are split into bit-serial style and 2bit-width serial processing lines work concurrently so that only 3 cycles are required to decode one layer. As a result, 12∼24 cycles are enough to process one iteration for all the code-rates specified in WiMAX. Compared to our previous bit-serial decoder, it doubles the parallelism and solves the message saturation problem of the bit-serial arithmetic, with minor gate count increase. Power synthesis result shows that the proposed decoder achieves 5.83pJ/bit/iteration energy efficiency which is 46.8% improvement compared to state-of-the-art work. Furthermore, an advanced dynamic quantization (ADQ) technique is proposed to enhance the error-correcting performance in layered decoder architecture. With about 2% area overhead, 6-bit ADQ can achieve the error-correcting performance close to 7-bit fixed quantization with improved error floor performance.

Heterogeneous multi-core architectures with CPUs and accelerators attract many attentions since they can achieve power-efficient computing in various areas from low-power embedded processing to high-performance computing. Since the optimal architecture is different from application to application, finding the most suitable accelerator is very important. In this paper, we propose an FPGA-based heterogeneous multi-core platform with custom accelerators for power-efficient computing. Using the proposed platform, we evaluate several applications and accelerators to identify many key requirements of the applications and properties of the accelerators. Such an evaluation is very important to select and optimize the most suitable accelerator according to the requirements of an application to achieve the best performance.

A recursive construction of (k+1)-ary error-correcting signature code is proposed to identify users for MAAC, even in the presence of channel noise. The recursion is originally from a trivial signature code. In the (j-1)-th recursion, from a signature code with minimum distance of 2j-2, a longer and larger signature code with minimum distance of 2j-1 is obtained. The decoding procedure of signature code is given, which consists of error correction and user identification.

With the rapid development of multi-view video coding (MVC) and light field rendering (LFR), Free-View Television (FTV) has emerged as new entrainment equipment, which can bring more immersive and realistic feelings for TV viewers. In FTV broadcasting system, the TV-viewer can freely watch a realistic arbitrary view of a scene generated from a number of original views. In such a scenario, the ownership of the multi-view video should be verified not only on the original views, but also on any virtual view. However, capacities of existing watermarking schemes as copyright protection methods for LFR-based FTV are only one bit, i.e., presence or absence of the watermark, which seriously impacts its usage in practical scenarios. In this paper, we propose a robust multi-bit watermarking scheme for LFR-based free-view video. The direct-sequence code division multiple access (DS-CDMA) watermark is constructed according to the multi-bit message and embedded into DCT domain of each view frame. The message can be extracted bit-by-bit from a virtual frame generated at an arbitrary view-point with a correlation detector. Furthermore, we mathematically prove that the watermark can be detected from any virtual view. Experimental results also show that the watermark in FTV can be successfully detected from a virtual view. Moreover, the proposed watermark method is robust against common signal processing attacks, such as Gaussian filtering, salt & peppers noising, JPEG compression, and center cropping.

The main target of compressed sensing is recovery of one-dimensional signals, because signals more than two-dimension can also be treated as one-dimensional ones by raster scan, which makes the sensing matrix huge. This is unavoidable for general sensing processes. In separable cases like discrete Fourier transform (DFT) or standard wavelet transforms, however, the corresponding sensing process can be formulated using two matrices which are multiplied from both sides of the target two-dimensional signals. We propose an approximate message passing (AMP) algorithm for the separable sensing process. Typically, we suppose DFT for the sensing process, in which the measurements are complex numbers. Therefore, the formulation includes cases in which both target signal and measurements are complex. We show the effectiveness of the proposed algorithm by computer simulations.

In this paper, joint transmit/receive frequency-domain equalization (FDE) is proposed for analog network coded (ANC) single-carrier (SC) bi-directional multi-antenna relay. In the proposed scheme, diversity transmission using transmit FDE is performed at relay station (RS) equipped with multiple antennas while receive FDE is carried out at base station (BS) and mobile terminal (MT) both equipped with single antenna. The transmit and receive FDE weights are jointly optimized so as to minimize the end-to-end mean square error (MSE). We evaluate, by computer simulation, the throughput performance and show that the joint transmit/receive FDE obtains the spatial and frequency diversity gains and accordingly achieve better throughput performance compared to either the transmit FDE only or the receive FDE only. It is also shown that ANC SC bi-directional multi-antenna relay can extend the communication coverage area for the given required throughput compared to conventional direct transmission.

Multi-operand adders that calculate the summation of more than two operands usually consist of compressor trees, which reduce the number of operands to two without any carry propagation, and carry-propagate adders for the two operands in the ASIC implementation. Compressor trees that consist of full adders and half adders cannot be implemented efficiently on LUT-based FPGAs, and carry-chains or dedicated structures have been utilized to produce multi-operand adders on FPGAs. Recent studies indicate that compressor trees can be implemented efficiently on LUTs using Generalized Parallel Counters (GPCs) as the building blocks of compressor trees. This paper addresses the problem of synthesizing compressor trees based on GPCs. Based on the observation that characteristics such as the area, power, and delay correlate roughly to the total number and the maximum level of GPCs, the target problem can be regarded as a minimization problem for the total number of GPCs and the maximum levels of the GPCs, for which an ILP-based approach is proposed. The key point of our formulation is not to model the problem based on the structures of compressor trees like the existing approach, but instead the compression process itself is used to reduce the number of variables and constraints in the ILP formulation. The experimental results demonstrate the advantage of our formulation in terms of the quality and runtime.

A probing front end circuit (PFE) senses and digitizes voltage noises at in-circuit locations on such as power supply wiring and substrate taps in a chip, with the simplest circuit construction only with a source follower or a unity gain buffer, followed by a latch comparator. The PFE with 2.5V I/O transistors in a 65nm CMOS technology node demonstrates 9.0 ENOB and 60.7dB SFDR in equivalent sampling at 1.0Gs/s, for a sinusoidal waveform of 10MHz with 200mV peak-to-peak amplitude. Behavioral modeling of an entire waveform acquisition system using PFEs includes the statistical variations of reference voltage and sampling timing. The simulation quantitatively explains the measured dynamic properties of on-chip noise monitoring, such as the AC response in SNDR and digitizing throughputs, with the clear dependency on the frequency and amplitude of input waveforms.

Recognizing human action in complex scenes is a challenging problem in computer vision. Some action-unrelated concepts, such as camera position features, could significantly affect the appearance of local spatio-temporal features, and therefore the performance of low-level features based methods degrades. In this letter, we define the action-unrelated concept: the position of camera as high-level features. We observe that they can serve as a prior to local spatio-temporal features for human action recognition. We encode this prior by modeling interactions between spatio-temporal features and camera position features. We infer camera position features from local spatio-temporal features via these interactions. The parameters of this model are estimated by a new max-margin algorithm. We evaluate the proposed method on KTH, IXMAS and Youtube actions datasets. Experimental results show the effectiveness of the proposed method.

In the literature, many resource allocation schemes have been proposed for multi-hop networks. However, the analyses provided focus mainly on the single cell case. Inter-cell interference severely degrades the performance of a wireless mobile network. Therefore, incorporating the analysis of inter-cell interference into the study of a scheme is required to more fully understand the performance of that scheme. The authors of this paper have proposed a parallel relaying scheme for a 2-hop OFDMA virtual cellular network (VCN). The purpose of this paper is to study a new version of that scheme which considers a multi-cell environment and evaluate the performance of the VCN. The ergodic channel capacity and outage capacity of the VCN in the presence of inter-cell interference are evaluated, and the results are compared to those of the single hop network (SHN). Furthermore, the effect of the location and number of wireless ports in the VCN on the channel capacity of the VCN is investigated, and the degree of fairness of the VCN relative to that of the SHN is compared. Using computer simulations, it is found that in the presence of inter-cell interference, a) the VCN outperforms the SHN even in the interference dominant transmission power region (when a single cell is considered, the VCN is better than the SHN only in the noise dominant transmission power region), b) the channel capacity of the VCN remains greater than that of the SHN even if the VCN is fully loaded, c) an optimal distance ratio for the location of the wireless ports can be found in the interval 0.2∼0.4, d) increasing the number of wireless ports from 3 to 6 can increase the channel capacity of the VCN, and e) the VCN can achieve better outage capacity than the SHN.

An improved genetic algorithm is employed to optimize the structure of (C60)N (N≤25) fullerene clusters with the lowest energy. First, crossover with variable precision, realized by introducing the hamming distance, is developed to provide a faster search mechanism. Second, the bit string mutation and feedback mutation are incorporated to maintain the diversity in the population. The interaction between C60 molecules is described by the Pacheco and Ramalho potential derived from first-principles calculations. We compare the performance of the Improved GA (IGA) with that of the Standard GA (SGA). The numerical and graphical results verify that the proposed approach is faster and more robust than the SGA. The second finite differential of the total energy shows that the (C60)N clusters with N=7, 13, 22 are particularly stable. Performance with the lowest energy is achieved in this work.

This paper addresses a high-level synthesis (HLS) using dual-edge-triggered flip-flops (DETFFs) as memory elements. In DETFF-based HLS, the duty cycle becomes a manageable resource to improve the timing performance. To utilize the duty cycle radically, a programmable duty cycle (PDC) mechanism is built into this HLS, and captured by a new HLS task named PDC scheduling. As a first step toward DETFF-based HLS with PDC, the execution time minimization problem is formulated for given results of operation scheduling. A linear program is presented to solve this problem in polynomial time. As a next step, simultaneous operation scheduling and PDC scheduling problem for the same objective is tackled. A mixed integer linear programming-based (MILP) approach is presented to solve this problem. The experimental results show that the MILP can reduce the execution time for several benchmarks.

Our prior papers proposed a traffic engineering scheme to further localize traffic in peer-assisted content delivery networks (CDNs). This scheme periodically combines the content files and allows them to obtain the combined content files while keeping the price unchanged from the single-content price in order to induce altruistic clients to download content files that are most likely to contribute to localizing network traffic. However, the selection algorithm in our prior work determined which and when content files should be combined according to the cache states of all clients, which is a kind of unrealistic assumption in terms of computational complexity. This paper proposes a new concept of virtual local server to reduce the computational complexity. We could say that the source server in our mechanism has a virtual caching network inside that reflects the cache states of all clients in the ‘actual’ caching network and combines content files based on the virtual caching network. In this paper, without determining virtual caching network according to the cache states of all clients, we approximately estimated the virtual caching network from the cache states of the virtual local server of the local domain, which is the aggregated cache state of only altruistic clients in a local domain. Furthermore, we proposed a content selection algorithm based on a virtual caching network. In this paper, we used news life-cycle model as a content model that had the severe changes in cache states, which was a striking instance of dynamic content models. Computer simulations confirmed that our proposed algorithm successfully localized network traffic.

Temporal Decorrelation source SEParation (TDSEP) is a blind separation scheme that utilizes the time structure of the source signals, typically, their periodicities. The advantage of TDSEP over non-Gaussianity based methods is that it can separate Gaussian signals as long as they are periodic. However, its shortcoming is that separation performance (SEP) heavily depends upon the values of the time shift parameters (TSPs). This paper proposes a method to automatically and blindly estimate a set of TSPs that achieves optimal SEP against periodic Gaussian signals. It is also shown that, selecting the same number of TSPs as that of the source signals, is sufficient to obtain optimal SEP, and adding more TSPs does not improve SEP, but only increases the computational complexity. The simulation example showed that the SEP is higher by approximately 20dB, compared with the ordinary method. It is also shown that the proposed method successfully selects just the same number of TSPs as that of incoming signals.

To achieve high recording density in a bit-patterned media recording system, the spacing between data bit islands in both the along-track and the across-track directions must be decreased, thus leading to the increase of two-dimensional (2D) interference. One way to reduce the 2D interference is to apply a 2D coding scheme on a data sequence before recording; however, this method usually requires many redundant bits, thus lowering a code rate. Therefore, we propose a novel 2D coding scheme referred to as a recorded-bit patterning (RBP) scheme to mitigate the 2D interference, which requires no redundant bits at the expense of using more buffer memory. Specifically, an input data sequence is first split into three tracks in which will then be rotated to find the best 3-track data pattern based on a look-up table before recording, such that the shifted data tracks yield the least effect of 2D interference in the readback signal. Numerical results indicate that the proposed RBP scheme provides a significant performance improvement if compared to a conventional system (without 2D coding), especially when the recording density is high and/or the position jitter noise is large.

This paper presents a real-time and memory-efficient arrhythmia detection system with binary classification that uses antidictionary coding for the analysis and classification of electrocardiograms (ECGs). The measured ECG signals are encoded using a lossless antidictionary encoder, and the system subsequently uses the compression rate to distinguish between normal beats and arrhythmia. An automated training data procedure is used to construct the automatons, which are probabilistic models used to compress the ECG signals, and to determine the threshold value for detecting the arrhythmia. Real-time computer simulations with samples from the MIT-BIH arrhythmia database show that the averages of sensitivity and specificity of the proposed system are 97.8% and 96.4% for premature ventricular contraction detection, respectively. The automatons are constructed using training data and comprise only 11 kilobytes on average. The low complexity and low memory requirements make the system particularly suitable for implementation in portable ECG monitors.

Text sentiment classification aims to automatically classify subjective documents into different sentiment-oriented categories (e.g. positive/negative). Given the high dimensionality of features describing documents, how to effectively select the most useful ones, referred to as sentiment-bearing features, with a lack of sentiment class labels is crucial for improving the classification performance. This paper proposes an unsupervised sentiment-bearing feature selection method (USFS), which incorporates sentiment discriminant analysis (SDA) into sentiment strength calculation (SSC). SDA applies traditional linear discriminant analysis (LDA) in an unsupervised manner without losing local sentiment information between documents. We use SSC to calculate the overall sentiment strength for each single feature based on its affinities with some sentiment priors. Experiments, performed using benchmark movie reviews, demonstrated the superior performance of USFS.

Relay selection is a promising technique with which to achieve remarkable gains in multi-relay cooperative networks. Opportunistic relaying (OR) and selection cooperation (SC) are two major relay selection schemes for dual-hop decode-and-forward cooperative networks; they have been shown to be globally outage-optimal under an aggregate power constraint. However, due to channel fluctuations, the channel state information (CSI) used in the selection process may become outdated and differ from the CSI during the actual transmission of data. In this work, we study the effect of outdated CSI on OR and threshold-based SC (TSC) schemes under independent but not necessarily identically distributed Rayleigh fading channels. The source can possibly cooperate with the best relay for data transmission, with the destination performing maximal ratio combining of the signals from the source and the relay. In particular, we analyze the average symbol error probability (ASEP) of OR and TSC with outdated CSI by deriving approximate but tight closed-form expressions for the moment generating function of the end-to-end signal-to-noise ratio. We also investigate the asymptotic behavior of the ASEP. The results show that the diversity orders of OR and TSC reduce to one and two, respectively, due to the outdated CSI. However, TSC achieves full spatial diversity order when the relay-to-destination CSI is perfect. Finally, to verify the analytical results Monte Carlo simulations are performed, in which OR attains better ASEP than TSC in a perfect CSI scenario, while TSC is less susceptible to outdated CSI.

This paper proposes an improved color barycenter model (CBM) and its separation for automatic road sign (RS) detection. The previous version of CBM can find out the colors of RS, but the accuracy is not high enough for separating the magenta and blue regions and the influence of number with the same color are not considered. In this paper, the improved CBM expands the barycenter distribution to cylindrical coordinate system (CCS) and takes the number of colors at each position into account for clustering. Under this distribution, the color information can be represented more clearly for analyzing. Then aim to the characteristic of barycenter distribution in CBM (CBM-BD), a constrained clustering method is presented to cluster the CBM-BD in CCS. Although the proposed clustering method looks like conventional K-means in some part, it can solve some limitations of K-means in our research. The experimental results show that the proposed method is able to detect RS with high robustness.