Shin-ichi NAKAYAMA Shigeru MASUYAMA
Given a graph G=(V,E) where V and E are a vertex and an edge set, respectively, specified with a subset VNT of vertices called a non-terminal set, the spanning tree with non-terminal set VNT is a connected and acyclic spanning subgraph of G that contains all the vertices of V where each vertex in a non-terminal set is not a leaf. In the case where each edge has the weight of a nonnegative integer, the problem of finding a minimum spanning tree with a non-terminal set VNT of G was known to be NP-hard. However, the complexity of finding a spanning tree on general graphs where each edge has the weight of one was unknown. In this paper, we consider this problem and first show that it is NP-hard even if each edge has the weight of one on general graphs. We also show that if G is a cograph then finding a spanning tree with a non-terminal set VNT of G is linearly solvable when each edge has the weight of one.
Jingsong SHAN Jianxin LUO Guiqiang NI Yinjin FU Zhaofeng WU
Estimating the cardinality of flows over sliding windows on high-speed links is still a challenging work under time and space constrains. To solve this problem, we present a novel data structure maintaining a summary of data and propose a constant-time update algorithm for fast evicting expired information. Moreover, a further memory-reducing schema is given at a cost of very little loss of accuracy.
Mengzhe CHEN Jielin PAN Qingwei ZHAO Yonghong YAN
Multi-task learning in deep neural networks has been proven to be effective for acoustic modeling in speech recognition. In the paper, this technique is applied to Mandarin-English code-mixing recognition. For the primary task of the senone classification, three schemes of the auxiliary tasks are proposed to introduce the language information to networks and improve the prediction of language switching. On the real-world Mandarin-English test corpus in mobile voice search, the proposed schemes enhanced the recognition on both languages and reduced the relative overall error rates by 3.5%, 3.8% and 5.8% respectively.
The most commonly used scattering parameters (S parameters) are normalized to a real reference resistance, typically 50Ω. In some cases, the use of S parameters normalized to some complex reference impedance is essential or convenient. But there are different definitions of complex-referenced S parameters that are incompatible with each other and serve different purposes. To make matters worse, different simulators implement different ones and which ones are implemented is rarely properly documented. What are possible scenarios in which using the right one matters? This tutorial-style paper is meant as an informal and not overly technical exposition of some such confusing aspects of S parameters, for those who have a basic familiarity with the ordinary, real-referenced S parameters.
Zhongshan ZHANG Yuning CHEN Yuejin TAN Jungang YAN
This paper presents a non-crossover and multi-mutation based genetic algorithm (NMGA) for the Flexible Job-shop Scheduling problem (FJSP) with the criterion to minimize the maximum completion time (makespan). Aiming at the characteristics of FJSP, three mutation operators based on operation sequence coding and machine assignment coding are proposed: flip, slide, and swap. Meanwhile, the NMGA framework, coding scheme, as well as the decoding algorithm are also specially designed for the FJSP. In the framework, recombination operator crossover is not included and a special selection strategy is employed. Computational results based on a set of representative benchmark problems were provided. The evidence indicates that the proposed algorithm is superior to several recently published genetic algorithms in terms of solution quality and convergence ability.
Abdel MARTINEZ ALONSO Masaya MIYAHARA Akira MATSUZAWA
This paper introduces a novel Direct Digital Frequency Synthesizer based on Complementary Dual-Phase Latch-Based sequencing method. Compared to conventional Direct Digital Frequency Synthesizer using Flip-Flop as synchronizing element, the proposed architecture allows to double the data sampling rate while trading-off area and Power Efficiency. Digital domain modulations can be easily implemented by using a Direct Digital Frequency Synthesizer. However, due to performance limitations, CMOS-based applications have been almost exclusively restricted to VHF, UHF and L bands. This work aims to increase the operation speed and extend the applicability of this technology to Multi-band Multi-standard wireless systems operating up to 2.7 GHz. The design features a 24 bits pipelined Phase Accumulator and a 14x10 bits Phase to Amplitude Converter. The Phase to Amplitude Converter module is compressed by using Quarter Wave Symmetry technique and is entirely made up of combinational logic inserted into 12 Complementary Dual-Phase Latch-Based pipeline stages. The logic is represented in the form of Sum of Product terms obtained from a 14x10 bits sinusoidal Look-Up-Table. The proposed Direct Digital Frequency Synthesizer is designed and simulated based on 65nm CMOS standard-cell technology. A maximum data sampling rate of 6.8 GS/s is expected. Estimated Spurious Free Dynamic Range and Power Efficiency are 61 dBc and 22 mW/(GS/s) respectively.
Naoki HASEGAWA Naoki SHINOHARA Shigeo KAWASAKI
The high performance GaN power amplifier circuit operating at 7.1 GHz was demonstrated for potential use such as in a space ground station. First, the GaN HEMT chips were investigated for the high power amplifier circuit design. And next, the designed amplifier circuits matching with the load and source impedance of the non-linear models were fabricated. From measurement, the AB-class power amplifier circuit with the four-cell chip showed the power added efficiency (PAE) of 42.6% and output power with 41.7dBm at -3dB gain compression. Finally, the good performance of the power amplifier was confirmed in a 20-way radial power combiner with the PAE of 17.4% and output power of 52.6 dBm at -3dB gain compression.
Zhigang CHEN Xiaolei ZHANG Hussain KHURRAM He HUANG Guomei ZHANG
In this letter, a novel channel impulse response (CIR)-based fingerprinting positioning method using kernel principal component analysis (KPCA) has been proposed. During the offline phase of the proposed method, a survey is performed to collect all CIRs from access points, and a fingerprint database is constructed, which has vectors including CIR and physical location. During the online phase, KPCA is first employed to solve the nonlinearity and complexity in the CIR-position dependencies and extract the principal nonlinear features in CIRs, and support vector regression is then used to adaptively learn the regress function between the KPCA components and physical locations. In addition, the iterative narrowing-scope step is further used to refine the estimation. The performance comparison shows that the proposed method outperforms the traditional received signal strength based positioning methods.
Satoshi TAYU Toshihiko TAKAHASHI Eita KOBAYASHI Shuichi UENO
The 3-D channel routing is a fundamental problem on the physical design of 3-D integrated circuits. The 3-D channel is a 3-D grid G and the terminals are vertices of G located in the top and bottom layers. A net is a set of terminals to be connected. The objective of the 3-D channel routing problem is to connect the terminals in each net with a Steiner tree (wire) in G using as few layers as possible and as short wires as possible in such a way that wires for distinct nets are disjoint. This paper shows that the problem is intractable. We also show that a sparse set of ν 2-terminal nets can be routed in a 3-D channel with O(√ν) layers using wires of length O(√ν).
Hiroki YAMAOKA Toshimichi SAITO
A digital map is a simple dynamical system that is related to various digital dynamical systems including cellular automata, dynamic binary neural networks, and digital spiking neurons. Depending on parameters and initial condition, the map can exhibit various periodic orbits and transient phenomena to them. In order to analyze the dynamics, we present two simple feature quantities. The first and second quantities characterize the plentifulness of the periodic phenomena and the deviation of the transient phenomena, respectively. Using the two feature quantities, we construct the steady-versus-transient plot that is useful in the visualization and consideration of various digital dynamical systems. As a first step, we demonstrate analysis results for an example of the digital maps based on analog bifurcating neuron models.
Zhigang CHEN Lei WANG He HUANG Guomei ZHANG
A novel virtual sensors-based positioning method has been presented in this paper, which can make use of both direct paths and indirect paths. By integrating the virtual sensor idea and Bayesian state and observation framework, this method models the indirect paths corresponding to persistent virtual sensors as virtual direct paths and further reformulates the wireless positioning problem as the maximum likelihood estimation of both the mobile terminal's positions and the persistent virtual sensors' positions. Then the method adopts the EM (Expectation Maximization) and the particle filtering schemes to estimate the virtual sensors' positions and finally exploits not only the direct paths' measurements but also the indirect paths' measurements to realize the mobile terminal's positions estimation, thus achieving better positioning performance. Simulation results demonstrate the effectiveness of the proposed method.
Kyohei YAMADA Naoki SAKAI Takashi OHIRA
Internal power losses in lumped-element impedance matching circuits are formulated by means of Q factors of the elements and port impedances to be matched. Assuming that Q factors are relatively high, the above mentioned loss is expressed by a simple formula containing only the tangents of the impedances. The formula is a powerful tool for such applications that put emphasis on power efficiency as wireless power transfer. As well as the formulation, we illustrate some design examples with the derived formula: design of the least lossy L-section circuit and two-stage low-pass ladder. The examples provide ready-to-use knowledge for low-loss matching design.
Lin GAO Jian HUANG Wen SUN Ping WEI Hongshu LIAO
The cardinality balanced multi-target multi-Bernoulli (CBMeMBer) filter has emerged as a promising tool for tracking a time-varying number of targets. However, the standard CBMeMBer filter may perform poorly when measurements are coupled with sensor biases. This paper extends the CBMeMBer filter for simultaneous target tracking and sensor biases estimation by introducing the sensor translational biases into the multi-Bernoulli distribution. In the extended CBMeMBer filter, the biases are modeled as the first order Gauss-Markov process and assumed to be uncorrelated with target states. Furthermore, the sequential Monte Carlo (SMC) method is adopted to handle the non-linearity and the non-Gaussian conditions. Simulations are carried out to examine the performance of the proposed filter.
Yu ZHAO Xihong CHEN Lunsheng XUE Jian LIU Zedong XIE
In this paper, we present the channel estimation (CE) problem in the orthogonal frequency division multiplexing system with offset quadrature amplitude modulation (OFDM/OQAM). Most CE methods rely on the assumption of a low frequency selective channel to tackle the problem in a way similar to OFDM. However, these methods would result in a severe performance degradation of the channel estimation when the assumption is not quite inaccurate. Instead, we focus on estimating the channel impulse response (CIR) itself which makes no assumption on the degree of frequency selectivity of the channels. After describing the main idea of this technique, we present an iterative CE method that does not require zero-value guard symbols in the preamble and consequently improves the spectral efficiency. This is done by the iterative estimation of the unknown transmitted data adjacent to the preamble. Analysis and simulation results validate the efficacy of the proposed method in multipath fading channels.
A novel method for illumination-invariant face representation is presented based on the orthogonal decomposition of the local image structure. One important advantage of the proposed method is that image gradients and corresponding intensity values are simultaneously used with our decomposition procedure to preserve the original texture while yielding the illumination-invariant feature space. Experimental results demonstrate that the proposed method is effective for face recognition and verification even with diverse lighting conditions.
Yumei WANG Jiawei LIANG Hao WANG Eiji OKI Lin ZHANG
In 3GPP (3rd Generation Partnership Project) LTE (Long Term Evolution) systems, when HARQ (Hybrid Automatic Repeat request) retransmission is invoked, the data at the transmitter are retransmitted randomly or sequentially regardless of their relationship to the wrongly decoded data. Such practice is inefficient since precious transmission resources will be spent to retransmit data that may be of no use in error correction at the receiver. This paper proposes an incremental redundancy HARQ scheme based on Error Position Estimating Coding (ePec) and LDPC (Low Density Parity Check Code) channel coding, which is called ePec-LDPC HARQ. The proposal is able to feedback the wrongly decoded code blocks within a specific MAC (Media Access Control) PDU (Protocol Data Unit) from the receiver. The transmitter gets the feedback information and then performs targeted retransmission. That is, only the data related to the wrongly decoded code blocks are retransmitted, which can improve the retransmission efficiency and thus reduce the retransmission overload. An enhanced incremental redundancy LDPC coding approach, called EIR-LDPC, together with a physical layer framing method, is developed to implement ePec-LDPC HARQ. Performance evaluations show that ePec-LDPC HARQ reduces the overall transmission resources by 15% compared to a conventional LDPC HARQ scheme. Moreover, the average retransmission times of each MAC PDU and the transmission delay are also reduced considerably.
Sotheara SAY Mohamad Erick ERNAWAN Shigeru SHIMAMOTO
Sensor networks are often used to understand underlying phenomena that are reflected through sensing data. In real world applications, this understanding supports decision makers attempting to access a disaster area or monitor a certain event regularly and thus necessary actions can be triggered in response to the problems. Practitioners designing such systems must overcome difficulties due to the practical limitations of the data and the fidelity of a network condition. This paper explores the design of a network solution for the data acquisition domain with the goal of increasing the efficiency of data gathering efforts. An unmanned aerial vehicle (UAV) is introduced to address various real-world sensor network challenges such as limited resources, lack of real-time representative data, and mobility of a relay station. Towards this goal, we introduce a novel cooperative path selection framework to effectively collect data from multiple sensor sources. The framework consists of six main parts ranging from the system initialization to the UAV data acquisition. The UAV data acquisition is useful to increase situational awareness or used as inputs for data manipulation that support response efforts. We develop a system-based simulation that creates the representative sensor networks and uses the UAV for collecting data packets. Results using our proposed framework are analyzed and compared to existing approaches to show the efficiency of the scheme.
This article presents efficient strategies for evacuating from an unknown affected area in a plane. Evacuation is the process of movement away from a threat or hazard such as natural disasters. Consider that one or n(n ≥ 3) agents are lost in an unknown convex region P. The agents know neither the boundary information of P nor their positions. We seek competitive strategies that can evacuate the agent from P as quickly as possible. The performance of the strategy is measured by a competitive ratio of the evacuation path over the shortest path. We give a 13.812-competitive spiral strategy for one agent, and prove that it is optimal among all monotone and periodic strategies by showing a matching lower bound. Also, we give a new competitive strategy EES for n(n ≥ 3) agents and adjust it to be more efficient with the analysis of its performance.
Takashi YANAGI Toru FUKASAWA Hiroaki MIYASHITA
In this paper, a measurement method for the impedance and mutual coupling of multi-antennas that we have proposed is summarized. Impedance and mutual coupling characteristics are obtained after reducing the influence of the coaxial cables by synthesizing the measured S-parameters under the condition that unbalanced currents on the outside of the coaxial cables are canceled at feed points. We apply the proposed method to two closely positioned monopole antennas mounted on a small ground plane and demonstrate the validity and effectiveness of the proposed method by simulation and experiment. The proposed method is significantly better in terms of the accuracy of the mutual coupling data. In the presented case, the errors at the resonant frequency of the antennas are only 0.5dB in amplitude and 1.8° in phase.
Ding XIAO Rui WANG Lingling WU
With the surge of social media platform, users' profile information become treasure to enhance social network services. However, attributes information of most users are not complete, thus it is important to infer latent attributes of users. Contemporary attribute inference methods have a basic assumption that there are enough labeled data to train a model. However, in social media, it is very expensive and difficult to label a large amount of data. In this paper, we study the latent attribute inference problem with very small labeled data and propose the SRW-COND solution. In order to solve the difficulty of small labeled data, SRW-COND firstly extends labeled data with a simple but effective greedy algorithm. Then SRW-COND employs a supervised random walk process to effectively utilize the known attributes information and link structure of users. Experiments on two real datasets illustrate the effectiveness of SRW-COND.