Dengyun LEI Weijun LU Yanbin ZHANG Dunshan YU
Due to low signal-to-carrier ratio and high dynamic, the frequency deviation affects the bit synchronization in GNSS receiver. This paper proposes a balance differential coherent bit synchronization algorithm, which uses the differential coherent method to eliminate the influence of the frequency deviation. By enlarging the differential distance, the proposed algorithm achieves higher bit synchronization rates. Combining two complementary differential coherent parts, the proposed algorithm avoids the unbalance problem and the attenuation of accumulation. Furthermore, a general architecture is presented to reduce the system complexity. Experimental results show that the proposed algorithm improves the sensitivity of bit synchronization by 3∼7dB compared with the previous method.
Tomomi ENDOU Shunta SAKAI Takeo FUJII
Recently, the growing concepts that information communication technologies apply to social infrastructures have caused deep interests with wireless sensor networks (WSNs). WSNs can be used for various application areas such as home, health, factory and so on. For the different application areas, there are different technical issues (e.g., security, reliability, real time gathering, long life time, scalability). Efficient information gathering can be potentially obtained if we take a suitable information gathering method with considering the requirements of each WSN application. Thus, we have not persisted all information gathering perfectly and have proposed one of simple information gathering methods in response to the requirements of WSN applications in this paper. In the proposed method, the information is converted to physical-layer parameters of wireless communications, such as frequency and time. Also, simulations are performed to validate the effectiveness of the proposed method in real time gathering and estimating with high precision.
Kazuki MARUTA Jun MASHINO Takatoshi SUGIYAMA
This paper proposes a novel blind adaptive array scheme with subcarrier transmission power assignment (STPA) for spectrum superposing in cognitive radio networks. The Eigenvector Beamspace Adaptive Array (EBAA) is known to be one of the blind adaptive array algorithms that can suppress inter-system interference without any channel state information (CSI). However, EBAA has difficulty in suppressing interference signals whose Signal to Interference power Ratio (SIR) values at the receiver are around 0dB. With the proposed scheme, the ST intentionally provides a level difference between subcarriers. At the receiver side, the 1st eigenvector of EBAA is applied to the received signals of the subcarrier assigned higher power and the 2nd eigenvector is applied to those assigned lower power. In order to improve interference suppression performance, we incorporate Beamspace Constant Modulus Algorithm (BSCMA) into EBAA (E-BSCMA). Additionally, STPA is effective in reducing the interference experienced by the primary system. Computer simulation results show that the proposed scheme can suppress interference signals received with SIR values of around 0dB while improving operational SIR for the primary system. It can enhance the co-existing region of 2 systems that share a spectrum.
Hisashi ARAKI Toshihiro FUJITO Shota INOUE
Suppose one of the edges is attacked in a graph G, where some number of guards are placed on some of its vertices. If a guard is placed on one of the end-vertices of the attacked edge, she can defend such an attack to protect G by passing over the edge. For each of such attacks, every guard is allowed either to move to a neighboring vertex, or to stay at where she is. The eternal vertex cover number τ∞(G) is the minimum number of guards sufficient to protect G from any length of any sequence of edge attacks. This paper derives the eternal vertex cover number τ∞(G) of such graphs constructed by replacing each edge of a tree by an arbitrary elementary bipartite graph (or by an arbitrary clique), in terms of easily computable graph invariants only, thereby showing that τ∞(G) can be computed in polynomial time for such graphs G.
Tatsuhiko HATANAKA Takehiro ITO Xiao ZHOU
We study the problem of transforming one list (vertex) coloring of a graph into another list coloring by changing only one vertex color assignment at a time, while at all times maintaining a list coloring, given a list of allowed colors for each vertex. This problem is known to be PSPACE-complete for bipartite planar graphs. In this paper, we first show that the problem remains PSPACE-complete even for bipartite series-parallel graphs, which form a proper subclass of bipartite planar graphs. We note that our reduction indeed shows the PSPACE-completeness for graphs with pathwidth two, and it can be extended for threshold graphs. In contrast, we give a polynomial-time algorithm to solve the problem for graphs with pathwidth one. Thus, this paper gives sharp analyses of the problem with respect to pathwidth.
Yizhong LIU Tian SONG Yiqi ZHUANG Takashi SHIMAMOTO Xiang LI
This paper proposes a novel greedy algorithm, called Creditability-Estimation based Matching Pursuit (CEMP), for the compressed sensing signal recovery. As proved in the algorithm of Stagewise Orthogonal Matching Pursuit (StOMP), two Gaussian distributions are followed by the matched filter coefficients corresponding to and without corresponding to the actual support set of the original sparse signal, respectively. Therefore, the selection for each support point is interpreted as a process of hypothesis testing, and the preliminarily selected support set is supposed to consist of rejected atoms. A hard threshold, which is controlled by an input parameter, is used to implement the rejection. Because the Type I error may happen during the hypothesis testing, not all the rejected atoms are creditable to be the true support points. The creditability of each preliminarily selected support point is evaluated by a well-designed built-in mechanism, and the several most creditable ones are adaptively selected into the final support set without being controlled by any extra external parameters. Moreover, the proposed CEMP does not necessitate the sparsity level to be a priori control parameter in operation. In order to verify the performance of the proposed algorithm, Gaussian and Pulse Amplitude Modulation sparse signals are measured in the noiseless and noisy cases, and the experiments of the compressed sensing signal recoveries by several greedy algorithms including CEMP are implemented. The simulation results show the proposed CEMP can achieve the best performances of the recovery accuracy and robustness as a whole. Besides, the experiment of the compressed sensing image recovery shows that CEMP can recover the image with the highest Peak Signal to Noise Ratio (PSNR) and the best visual quality.
Hiroshi FUJIWARA Takuya NAKAMURA Toshihiro FUJITO
A binary tree is regarded as a prefix-free binary code, in which the weighted sum of the lengths of root-leaf paths is equal to the expected codeword length. Huffman's algorithm computes an optimal tree in O(n log n) time, where n is the number of leaves. The problem was later generalized by allowing each leaf to have its own function of its depth and setting the sum of the function values as the objective function. The generalized problem was proved to be NP-hard. In this paper we study the case where every function is a unit step function, that is, a function that takes a lower constant value if the depth does not exceed a threshold, and a higher constant value otherwise. We show that for this case, the problem can be solved in O(n log n) time, by reducing it to the Coin Collector's problem.
Yu ZHOU Lin WANG Weiqiong WANG Xiaoni DU
The global avalanche characteristics measure the overall avalanche properties of Boolean functions, an n-variable balanced Boolean function of the sum-of-square indicator reaching σƒ=22n+2n+3 is an open problem. In this paper, we prove that there does not exist a balanced Boolean function with σƒ=22n+2n+3 for n≥4, if the hamming weight of one decomposition function belongs to the interval Q*. Some upper bounds on the order of propagation criterion of balanced Boolean functions with n (3≤n≤100) variables are given, if the number of vectors of propagation criterion is equal and less than 7·2n-3-1. Two lower bounds on the sum-of-square indicator for balanced Boolean functions with optimal autocorrelation distribution are obtained. Furthermore, the relationship between the sum-of-squares indicator and nonlinearity of balanced Boolean functions is deduced, the new nonlinearity improves the previously known nonlinearity.
In this paper, the multicell distributed beamforming (MDBF) design problem of suppressing intra-cell interference (InCI) and inter-cell interference (ICI) is studied. To start with, in order to decrease the InCI and ICI caused by a user, we propose a gradient-iteration altruistic algorithm to derive the beamforming vectors. The convergence of the proposed iterative algorithm is proved. Second, a metric function is established to restrict the ICI and maximize cell rate. This function depends on only local channel state information (CSI) and does not need additional CSIs. Moreover, an MDBF algorithm with the metric function is proposed. This proposed algorithm utilizes gradient iteration to maximize the metric function to improve sum rate of the cell. Finally, simulation results demonstrate that the proposed algorithm can achieve higher cell rates while offering more advantages to suppress InCI and ICI than the traditional ones.
Yun-Ki HAN Jae-Woo LEE Han-Sol LEE Woo-Jin SONG
We propose a novel bias-free adaptive beamformer employing an affine projection algorithm with the optimal regularization parameter. The generalized sidelobe canceller affine projection algorithm suffers from a bias of a weight vectors under the condition of no reference signals for output of an array in the beamforming application. First, we analyze the bias in the algorithm and prove that the bias can be eliminated through a large regularization parameter. However, this causes slow convergence at the initial state, so the regularization parameter should be controlled. Through the optimization of the regularization parameter, the proposed method achieves fast convergence without the bias at the steady-state. Experimental results show that the proposed beamformer not only removes the bias but also achieves both fast convergence and high steady-state output signal-to-interference-plus-noise ratio.
Dandan LI Qiaoyan WEN Jie ZHANG Liying JIANG
The linear complexity of binary sequences plays a fundamental part in cryptography. In the paper, we construct more general forms of generalized cyclotomic binary sequences with period 2pm+1qn+1. Furthermore, we establish the formula of the linear complexity of proposed sequences. The results reveal that such sequences with period 2pm+1qn+1 have a good balance property and high linear complexity.
Nguyen Ngoc BINH Pham Van HUONG Bui Ngoc HAI
Optimizing embedded software is a problem having scientific and practical signification. Optimizing embedded software can be done in different phases of the software life cycle under different optimal conditions. Most studies of embedded software optimization are done in forward engineering and these studies have not given an overall model for the optimization problem of embedded software in both forward engineering and reverse engineering. Therefore, in this paper, we propose a new approach to embedded software optimization based on reverse engineering. First, we construct an overall model for the embedded software optimization in both forward engineering and reverse engineering and present a process of embedded software optimization in reverse engineering. The main idea of this approach is that decompiling executable code to source code, converting the source code to models and optimizing embedded software under different levels such as source code and model. Then, the optimal source code is recompiled. To develop this approach, we present two optimization techniques such as optimizing power consumption of assembly programs based on instruction schedule and optimizing performance based on alternating equivalent expressions.
Joon-young JUNG Dong-oh KANG Jang-ho CHOI Changseok BAE Dae-young KIM
In this paper, we propose an error-correction low-pass filter (EC-LPF) algorithm for estimating the wireless distance between devices. To measure this distance, the received signal strength indication (RSSI) is a popularly used method because the RSSI of a wireless signal, such as Wi-Fi and Bluetooth, can be measured easily without the need for additional hardware. However, estimating the wireless distance using an RSSI is known to be difficult owing to the occurrence of inaccuracies. To examine the inaccuracy characteristics of Bluetooth RSSI, we conduct a preliminary test to discover the relationship between the actual distance and Bluetooth RSSI under several different environments. The test results verify that the main reason for inaccuracy is the existence of measurement errors in the raw Bluetooth RSSI data. In this paper, the EC-LPF algorithm is proposed to reduce measurement errors by alleviating fluctuations in a Bluetooth signal with responsiveness for real-time applications. To evaluate the effectiveness of the EC-LPF algorithm, distance accuracies of different filtering algorithms are compared, namely, a low-pass filer (LPF), a Kalman filter, a particle filter, and the EC-LPF algorithm under two different environments: an electromagnetic compatibility (EMC) chamber and an indoor hall. The EC-LPF algorithm achieves the best performance in both environments in terms of the coefficient of determination, standard deviation, measurement range, and response time. In addition, we also implemented a meeting room application to verify the feasibility of the EC-LPF algorithm. The results prove that the EC-LPF algorithm distinguishes the inside and outside areas of a meeting room without error.
Hung V. LE Capsoni CARLO Nebuloni ROBERTO Luini LORENZO Takuichi HIRANO Toru TANIGUCHI Jiro HIROKAWA Makoto ANDO
Dense millimeter-wave networks are a promising candidate for next-generation cellular systems enabling multiple gigabit-per-second data rates. A major disadvantage of millimeter-wave systems is signal disruption by rain, and here we propose a novel method for rain sensing using dual-frequency measurements at 25 and 38GHz from a small-scale Tokyo Institute of Technology (Tokyo Tech) millimeter-wave network. A real-time algorithm is developed for estimating the rain rate from attenuation using both ITU-R relationships and new coefficients that consider the effects of the rain Drop Size Distribution (DSD). The suggested procedure is tested on measured data, and its performance is evaluated. The results show that the proposed algorithm yields estimates that agree very well with rain gauge data.
Xu CHENG Nijun LI Tongchi ZHOU Zhenyang WU Lin ZHOU
In this paper, we propose an efficient tracking method that is formulated as a multi-task reverse sparse representation problem. The proposed method learns the representation of all tasks jointly using a customized APG method within several iterations. In order to reduce the computational complexity, the proposed tracking algorithm starts from a feature selection scheme that chooses suitable number of features from the object and background in the dynamic environment. Based on the selected feature, multiple templates are constructed with a few candidates. The candidate that corresponds to the highest similarity to the object templates is considered as the final tracking result. In addition, we present a template update scheme to capture the appearance changes of the object. At the same time, we keep several earlier templates in the positive template set unchanged to alleviate the drifting problem. Both qualitative and quantitative evaluations demonstrate that the proposed tracking algorithm performs favorably against the state-of-the-art methods.
Xiang YIN Masaki SATO Seiya KASAI
We investigate the origin of non-ideal transfer characteristics in graphene-based three-branch nano-junction (TBJ) devices. Fabricated graphene TBJs often show asymmetric nonlinear voltage transfer characteristic, although symmetric one should appear ideally. A simple model considering the contact resistances in two input electrodes is deduced and it suggests that the non-ideal characteristic arises from inequality of the metal-graphene contact resistances in the inputs. We fabricate a graphene TBJ device with electrically equal contacts by optimizing the contact formation process and almost ideal nonlinear characteristic was successfully demonstrated.
A renal biopsy is a procedure to get a small piece of kidney for microscopic examination. With the development of tissue sectioning and medical imaging techniques, microscope renal biopsy image sequences are consequently obtained for computer-aided diagnosis. This paper proposes a new context-based segmentation algorithm for acquired image sequence, in which an improved genetic algorithm (GA) patching method is developed to segment different size target. To guarantee the correctness of first image segmentation and facilitate the use of context information, a boundary fusion operation and a simplified scale-invariant feature transform (SIFT)-based registration are presented respectively. The experimental results show the proposed segmentation algorithm is effective and accurate for renal biopsy image sequence.
Appearance changes conform to certain rules for a same person,while for different individuals the changes are uncontrolled. Hence, this paper studies the age progression rules to tackle face verification task. The age progression rules are discovered in the difference space of facial image pairs. For this, we first represent an image pair as a matrix whose elements are the difference of a set of visual words. Thereafter, the age progression rules are trained using Support Vector Machine (SVM) based on this matrix representation. Finally, we use these rules to accomplish the face verification tasks. The proposed approach is tested on the FGnet dataset and a collection of real-world images from identification card. The experimental results demonstrate the effectiveness of the proposed method for verification of identity.
Prachya BOONKWAN Thepchai SUPNITHI
Developing a practical and accurate statistical parser for low-resourced languages is a hard problem, because it requires large-scale treebanks, which are expensive and labor-intensive to build from scratch. Unsupervised grammar induction theoretically offers a way to overcome this hurdle by learning hidden syntactic structures from raw text automatically. The accuracy of grammar induction is still impractically low because frequent collocations of non-linguistically associable units are commonly found, resulting in dependency attachment errors. We introduce a novel approach to building a statistical parser for low-resourced languages by using language parameters as a guide for grammar induction. The intuition of this paper is: most dependency attachment errors are frequently used word orders which can be captured by a small prescribed set of linguistic constraints, while the rest of the language can be learned statistically by grammar induction. We then show that covering the most frequent grammar rules via our language parameters has a strong impact on the parsing accuracy in 12 languages.
Jianzhang CHEN Jianping LI Yuanyuan HUANG
Nonprimitive non-narrow-sense BCH codes have been studied by many scholars. In this paper, we utilize nonprimitive non-narrow-sense BCH codes to construct a family of asymmetric quantum codes and two families of quantum convolutional codes. Most quantum codes constructed in this paper are different from the ones in the literature. Moreover, some quantum codes constructed in this paper have good parameters compared with the ones in the literature.