A new artificial fish swarm algorithm (AFSA) for solving the multiple knapsack problem (MKP) is introduced in this paper. In the proposed AFSA, artificial fish (AF) individuals are only allowed to search the region near constraint boundaries of the problem to be solved. For this purpose, several behaviors to be performed by AF individuals, including escaping behavior, randomly moving behavior, preying behavior and following behavior, were specially designed. Exhaustive experiments were implemented in order to investigate the proposed AFSA's performance. The results demonstrated the proposed AFSA has the ability of finding high-quality solutions with very fast speed, as compared with some other versions of AFSA based on different constraint-handling methods. This study is also meaningful for solving other constrained problems.

By the motivation to discover patterns in massive structured data in the form of graphs and trees, we study a special case of the k-subtree enumeration problem with a tree of n nodes as an input graph, which is originally introduced by (Ferreira, Grossi, and Rizzi, ESA'11, 275-286, 2011) for general graphs. Based on reverse search technique (Avis and Fukuda, Discrete Appl. Math., vol.65, pp.21-46, 1996), we present the first constant delay enumeration algorithm that lists all k-subtrees of an input rooted tree in O(1) worst-case time per subtree. This result improves on the straightforward application of Ferreira et al.'s algorithm with O(k) amortized time per subtree when an input is restricted to tree. Finally, we discuss an application of our algorithm to a modification of the graph motif problem for trees.

This paper reports on the image compression tolerability and high implementability of a novel proposed watermarking method that uses a morphological wavelet transform based on max-plus algebra. This algorithm is suitable for embedded low-power processors in mobile devices. For objective and unified evaluation of the capability of the proposed watermarking algorithm, we focus attention on a watermarking contest presented by the IHC, which belongs to the IEICE and investigate the image quality and tolerance against JPEG compression attack. During experiments for this contest, six benchmark images processed by the proposed watermarking is done to reduce the file size of original images to 1/10, 1/20, or less, and the error rate of embedding data is reduced to 0%. Thus, the embedded data can be completely extracted. The PSNR value is up to 54.66dB in these experiments. Furthermore, when the smallest image size is attained 0.49MB and the PSNR value become about 52dB, the proposed algorithm maintains very high quality with an error rate of 0%. Additionally, the processing time of the proposed watermarking can realize about 416.4 and 4.6 times faster than that of DCT and HWT on the ARM processor, respectively. As a result, the proposed watermarking method achieves effective processing capability for mobile processors.

We propose an improved design of a neuron circuit, using coupled SQUIDs gates, for a superconducting neural network. An activation function with step-like input vs. output characteristics is desirable for a neuron circuit to solve a combinatorial optimization problem. The proposed neuron circuit is composed of two coupled SQUIDs gates with a cascade connection, in order to obtain such characteristics. The designed neuron circuit is fabricated by a 2.5kA/cm2 Nb/AlOx/Nb process. The operation of a fabricated neuron circuit is experimentally demonstrated. Network performance of a neural network using proposed neuron circuits is also estimated by numerical dynamic simulations.

Attenuated and delayed versions of the pulse signal overlap in multipath propagation. Previous algorithms can resolve them only if signal sampling is ideal, but fail to resolve two counterparts with non-ideal sampling. In this paper, we propose a novel method which can resolve the general types of non-ideally sampled pulse signals in the time domain via Taylor Series Expansion (TSE) and estimate multipath signals' precise time delays and amplitudes. In combination with the CLEAN algorithm, the overlapped pulse signal parameters are estimated one by one through an iteration method. Simulation results verify the effectiveness of the proposed method.

The problem of resource allocation to minimize the outage probability for the secondary user (SU) groups in a cognitive radio (CR) multicast network is investigated. We propose a joint power and rate allocation scheme that provides significant improvement over the conventional scheme in terms of outage probability.

This paper studies the complexity of computing discrete logarithms over algebraic tori. We show that the order certified version of the discrete logarithm problem over general finite fields (OCDL, in symbols) reduces to the discrete logarithm problem over algebraic tori (TDL, in symbols) with respect to the polynomial-time Turing reducibility. This reduction means that if the prime factorization can be computed in polynomial time, then TDL is equivalent to the discrete logarithm problem over general finite fields with respect to the Turing reducibility.

In this paper, we clarify the relationship between an initial (final) state in a tail-biting error-trellis and the obtained syndromes. We show that a final state is dependent on the first M syndromes as well, where M is the memory length of the parity-check matrix. Next, we calculate the probability of an initial (final) state conditioned by the syndromes. We also apply this method to concrete examples. It is shown that the initial (final) state in a tail-biting error-trellis is well estimated using these conditional probabilities.

In this letter, we research the method of using face and gesture image sequences to deal with the video-based bimodal emotion recognition problem, in which both Harris plus cuboids spatio-temporal feature (HST) and sparse canonical correlation analysis (SCCA) fusion method are applied to this end. To efficaciously pick up the spatio-temporal features, we adopt the Harris 3D feature detector proposed by Laptev and Lindeberg to find the points from both face and gesture videos, and then apply the cuboids feature descriptor to extract the facial expression and gesture emotion features [1],[2]. To further extract the common emotion features from both facial expression feature set and gesture feature set, the SCCA method is applied and the extracted emotion features are used for the biomodal emotion classification, where the K-nearest neighbor classifier and the SVM classifier are respectively used for this purpose. We test this method on the biomodal face and body gesture (FABO) database and the experimental results demonstrate the better recognition accuracy compared with other methods.

In this paper, we propose a new trusted modeling approach based on state graphs. We introduce a novel method of deriving state-layer from a system call sequence in terms of probability and statistics theory, and we identify the state sequence with the help of Hidden Markov Model (HMM). We generate state transition graph according to software executing process and pruning rules. Then, we separate local function graphs according to software specific functions by semantic analysis. The state-layer is a bridge between the basic behaviors and the upper layer functions of software to compensate semantic faults. In addition, a pruning strategy of formulating state graphs is designed to precisely describe each piece of software functions. Finally, a detecting system based on our model is proposed, and a case study of RSS software reveals how our system works. The results demonstrate that our trusted model describes software behaviors successfully and can well detect un-trust behaviors, anomaly behaviors, and illegal input behaviors.

The exact power distribution of the inter-cell interference is obtained explicitly for cell edge users who are surrounded by circular guard zones. Compared with recent works, the underlying channel model is generalized from Rayleigh fading to a combination of Nakagami fading and Gamma shadowing. In addtion, asymptotic analysis shows that the mean power of intercell interference changes from infinite to finite with a guard zone. Based on this interference distribution, the average capacity at the cell edge is further obtained. Special case approximation indicates that the capacity scales proportionally to the exponential of the guard zone size. Analytical capacities are validated by Monte Carlo simulations.

In recent VLSIs, small-delay defects, which are hard to detect by traditional delay fault testing, can bring about serious issues such as short lifetime. To detect small-delay defects, on-chip delay measurement which measures the delay time of paths in the circuit under test (CUT) was proposed. However, this approach incurs high test cost because it uses scan design, which brings about long test application time due to scan shift operation. Our solution is a test application time reduction method for testing using the on-chip path delay measurement. The testing with on-chip path delay measurement does not require capture operations, unlike the conventional delay testing. Specifically, FFs keep the transition pattern of the test pattern pair sensitizing a path under measurement (PUM) (denoted as p) even after the measurement of p. The proposed method uses this characteristic. The proposed method reduces scan shift time and test data volume using test pattern merging. Evaluation results on ISCAS89 benchmark circuits indicate that the proposed method reduces the test application time by 6.89∼62.67% and test data volume by 46.39∼74.86%.

For battery based real-time embedded systems, high performance to meet their real-time constraints and energy efficiency to extend battery life are both essential. Real-Time Dynamic Voltage Scaling (RT-DVS) has been a key technique to satisfy both requirements. This paper presents EccEDF (Enhanced ccEDF), an efficient algorithm based on ccEDF. ccEDF is one of the most simple but efficient RT-DVS algorithms. Its simple structure enables it to be easily and intuitively coupled with a real-time operating system without incurring any significant cost. ccEDF, however, overlooks an important factor in calculating the available slacks for reducing the operating frequency. It calculates the saved utilization simply by dividing the slack by the period without considering the time needed to run the task. If the elapsed time is considered, the maximum utilization saved by the slack on completion of the task can be found. The proposed EccEDF can precisely calculate the maximum unused utilization with consideration of the elapsed time while keeping the structural simplicity of ccEDF. Further, we analytically establish the feasibility of EccEDF using the fluid scheduling model. Our simulation results show that the proposed algorithm outperforms ccEDF in all simulations. A simulation shows that EccEDF consumes 27% less energy than ccEDF.

In this paper, we propose a bitstream-level noise cancellation method for playback applications of damaged video. Most analog video data such as movies, news and historical research videos are now stored in a digital format after a series of conversion processes that include analog-to-digital conversion and compression. In many cases, noise such as blotches and line scratching remaining in analog media are not removed during the conversion process. On the other hand, noise is propagated in the compression stage because most media compression technologies use predictive coding. Therefore, it is imperative to efficiently remove or reduce the artifacts caused by noise as much as possible. In some cases, the video data with historical values are to be preserved without correcting the noise in order not to lose any important information resulting from the noise removal process. However, playback applications of such video data still need to undergo a noise reduction process to ensure picture quality for public viewing. The proposed algorithm identifies the candidate noise blocks at the bitstream-level to directly provide a noise reduction process while decoding the bitstream. Throughout the experimental results, we confirm the efficiency of the proposed method by showing RR and PR values of around 70 percent.

Tracking capsule endoscope location is one of the promising applications offered by implant body area networks (BANs). When tracking the capsule endoscope location, i.e., continuously localize it, it is effective to take the weighted sum of its past locations to its present location, in other words, to low-pass filter its past locations. Furthermore, creating an exact mathematical model of location transition will improve tracking performance. Therefore, in this paper, we investigate two tracking methods with received signal strength indicator (RSSI)-based localization in order to solve the capsule endoscope location tracking problem. One of the two tracking methods is finite impulse response (FIR) filter-based tracking, which tracks the capsule endoscope location by averaging its past locations. The other one is particle filter-based tracking in order to deal with a nonlinear transition model on the capsule endoscope. However, the particle filter requires that the particle weight is calculated according to its condition (namely, its likelihood value), while the transition model on capsule endoscope location has some model parameters which cannot be estimated from the received wireless signal. Therefore, for the purpose of applying the particle filter to capsule endoscope tracking, this paper makes some modifications in the resampling step of the particle filter algorithm. Our computer simulation results demonstrate that the two tracking methods can improve the performance as compared with the conventional maximum likelihood (ML) localization. Furthermore, we confirm that the particle filter-based tracking outperforms the conventional FIR filter-based tracking by taking the realistic capsule endoscope transition model into consideration.

Suppose that each arc in a digraph D = (V,A) has two costs of non-negative integers, called a spine cost and a leaf cost. A caterpillar is a directed tree consisting of a single directed path (of spine arcs) and leaf vertices each of which is incident to the directed path by exactly one incoming arc (leaf arc). For a given terminal set K ⊆ V, we study the problem of finding a caterpillar in D such that it contains all terminals in K and its total cost is minimized, where the cost of each arc in the caterpillar depends on whether it is used as a spine arc or a leaf arc. In this paper, we first show that the problem is NP-hard for any fixed constant number of terminals with |K| ≥ 3, while it is solvable in polynomial time for at most two terminals. We also give an inapproximability result for any fixed constant number of terminals with |K| ≥ 3. Finally, we give a linear-time algorithm to solve the problem for digraphs with bounded treewidth, where the treewidth for a digraph D is defined as the one for the underlying graph of D. Our algorithm runs in linear time even if |K| = O(|V|), and the hidden constant factor of the running time is just a single exponential of the treewidth.

In this paper, we design an efficient P2P based mobile social network to facilitate contents search over mobile ad hoc networks. Social relation is established by considering both the locations and interests of mobile nodes. Mobile nodes with common interests and nearby locations are recommended as friends and are connected directly in a mobile social network. Contents search is handled by using social relationships of the mobile social network rather than those of the whole network. Since each mobile node manages only neighboring nodes that have common interests, network management overhead is reduced. Results of experiments have shown that our proposed method outperforms existing methods.

Cross-view action recognition is a challenging research field for human motion analysis. Appearance-based features are not credible if the viewpoint changes. In this paper, a new framework is proposed for cross-view action recognition by topic based knowledge transfer. First, Spatio-temporal descriptors are extracted from the action videos and each video is modeled by a bag of visual words (BoVW) based on the codebook constructed by the k-means cluster algorithm. Second, Latent Dirichlet Allocation (LDA) is employed to assign topics for the BoVW representation. The topic distribution of visual words (ToVW) is normalized and taken to be the feature vector. Third, in order to bridge different views, we transform ToVW into bilingual ToVW by constructing bilingual dictionaries, which guarantee that the same action has the same representation from different views. We demonstrate the effectiveness of the proposed algorithm on the IXMAS multi-view dataset.

We describe a large-scale integrated circuit (LSI) design of rapid single-flux-quantum (RSFQ) circuits and demonstrate several reconfigurable data-path (RDP) processor prototypes based on the ISTEC Advanced Process (ADP2). The ADP2 LSIs are made up of nine Nb layers and Nb/AlOx/Nb Josephson junctions with a critical current density of 10kA/cm2, allowing higher operating frequencies and integration. To realize truly large-scale RSFQ circuits, careful design is necessary, with several compromises in the device structure, logic gates, and interconnects, balancing the competing demands of integration density, design flexibility, and fabrication yield. We summarize numerical and experimental results related to the development of a cell-based design in the ADP2, which features a unit cell size reduced to 30-µm square and up to four strip line tracks in the unit cell underneath the logic gates. The ADP LSIs can achieve ∼10 times the device density and double the operating frequency with the same power consumption per junction as conventional LSIs fabricated using the Nb four-layer process. We report the design and test results of RDP processor prototypes using the ADP2 cell library. The RDP processors are composed of many arrays of floating-point units (FPUs) and switch networks, and serve as accelerators in a high-performance computing system. The prototypes are composed of two-dimensional arrays of several arithmetic logic units instead of FPUs. The experimental results include a successful demonstration of full operation and reconfiguration in a 2×2 RDP prototype made up of 11.5k junctions at 45GHz after precise timing design. Partial operation of a 4×4 RDP prototype made up of 28.5k-junctions is also demonstrated, indicating the scalability of our timing design.

Infrastructure as a Service (IaaS), a form of cloud computing, is gaining attention for its ability to enable efficient server administration in dynamic workload environments. In such environments, however, updating the software stack or content files of virtual machines (VMs) is a time-consuming task, discouraging administrators from frequently enhancing their services and fixing security holes. This is because the administrator has to upload the whole new disk image to the cloud platform via the Internet, which is not yet fast enough that large amounts of data can be transferred smoothly. Although the administrator can apply incremental updates directly to the running VMs, he or she has to carefully consider the type of update and perform operations on all running VMs, such as application restarts. This is a tedious and error-prone task. This paper presents a technique for synchronizing VMs with less time and lower administrative burden. We introduce the Virtual Disk Image Repository, which runs on the cloud platform and automatically updates the virtual disk image and the running VMs with only the incremental update information. We also show a mechanism that performs necessary operations on the running VM such as restarting server processes, based on the types of files that are updated. We implement a prototype on Linux 2.6.31.14 and Amazon Elastic Compute Cloud. An experiment shows that our technique can synchronize VMs in an order-of-magnitude shorter time than the conventional disk-image-based VM method. Also, we discuss limitations of our technique and some directions for more efficient VM updates.