Xiangdong HUANG Jingwen XU Jiexiao YU Yu LIU
To optimize the performance of FIR filters that have low computation complexity, this paper proposes a hybrid design consisting of two optimization levels. The first optimization level is based on cyclic-shift synthesis, in which all possible sub filters (or windowed sub filters) with distinct cycle shifts are averaged to generate a synthesized filter. Due to the fact that the ripples of these sub filters' transfer curves can be individually compensated, this synthesized filter attains improved performance (besides two uprushes occur on the edges of a transition band) and thus this synthesis actually plays the role of ‘natural optimization’. Furthermore, this synthesis process can be equivalently summarized into a 3-step closed-form procedure, which converts the multi-variable optimization into a single-variable optimization. Hence, to suppress the uprushes, what the second optimization level (by Differential Evolution (DE) algorithm) needs to do is no more than searching for the optimum transition point which incurs only minimal complexity . Owning to the combination between the cyclic-shift synthesis and DE algorithm, unlike the regular evolutionary computing schemes, our hybrid design is more attractive due to its narrowed search space and higher convergence speed . Numerical results also show that the proposed design is superior to the conventional DE design in both filter performance and design efficiency, and it is comparable to the Remez design.
Naoki HAYASHI Masaaki NAGAHARA
This paper proposes a novel distributed proximal minimization algorithm for constrained optimization problems over fixed strongly connected networks. At each iteration, each agent updates its own state by evaluating a proximal operator of its objective function under a constraint set and compensating the unbalancing due to unidirectional communications. We show that the states of all agents asymptotically converge to one of the optimal solutions. Numerical results are shown to confirm the validity of the proposed method.
Yang GAO Yong-juan WANG Qing-jun YUAN Tao WANG Xiang-bin WANG
We propose a new method of differential fault attack, which is based on the nibble-group differential diffusion property of the lightweight block cipher MIBS. On the basis of the statistical regularity of differential distribution of the S-box, we establish a statistical model and then analyze the relationship between the number of faults injections, the probability of attack success, and key recovering bits. Theoretically, time complexity of recovering the main key reduces to 22 when injecting 3 groups of faults (12 nibbles in total) in 30,31 and 32 rounds, which is the optimal condition. Furthermore, we calculate the expectation of the number of fault injection groups needed to recover 62 bits in main key, which is 3.87. Finally, experimental data verifies the correctness of the theoretical model.
Satoshi TAOKA Toshimasa WATANABE
The k-edge-connectivity augmentation problem for a specified set of vertices (kECA-SV for short) is defined by “Given a graph G=(V, E) and a subset Γ ⊆ V, find a minimum set E' of edges such that G'=(V, E ∪ E') has at least k edge-disjoint paths between any pair of vertices in Γ.” Let σ be the edge-connectivity of Γ (that is, G has at least σ edge-disjoint paths between any pair of vertices in Γ). We propose an algorithm for (σ+1)ECA-SV which is done in O(|Γ|) maximum flow operations. Then the time complexity is O(σ2|Γ||V|+|E|) if a given graph is sparse, or O(|Γ||V||BG|log(|V|2/|BG|)+|E|) if dense, where |BG| is the number of pairs of adjacent vertices in G. Also mentioned is an O(|V||E|+|V|2 log |V|) time algorithm for a special case where σ is equal to the edge-connectivity of G and an O(|V|+|E|) time one for σ ≤ 2.
Nobuyoshi KIKUMA Kousuke YONEZU Kunio SAKAKIBARA
MU-MIMO (Multi-User Multiple Input and Multiple Output) has been considered as a fundamental technology for simultaneous communications between a base station and multiple users. This is because it can generate a large virtual MIMO channel between a base station and multiple user terminals with effective utilization of wireless resources. As a method of implementing MU-MIMO downlink, Block Diagonalization (BD) was proposed in which the transmission weights are determined to cancel interference between multiple user terminals. On the other hand, Block Maximum Signal-to-Noise ratio (BMSN) was proposed which determines the transmission weights to enhance the gain for each user terminal in addition to the interference cancellation. As a feature, BMSN has a pseudo-noise for controlling the null depth to the interference. In this paper, to enhance further the BMSN performance, we propose the BMSN algorithm that has the pseudo-noise determined according to receiver SNR. As a result of computer simulation, it is confirmed that the proposed BMSN algorithm shows the significantly improved performance in evaluation of bit error rate (BER) and achievable bit rate (ABR).
Andrey LYULYAKIN Iakov CHERNYAK Motoyuki SATO
In order to improve an imaging performance of a sparse array radar system we propose an optimization method to find a new antenna array layout. The method searches for a minimum of the cost function based on a 3D point spread function of the array. We found a solution for the simulated problem in a form of the new layout for the antenna array with more sparse middle-point distribution comparing with initial one.
Dynamic linear feedback shift registers (DLFSRs) are a scheme to transfer from one LFSR to another. In cryptography each LFSR included in a DLFSR should generate maximal-length sequences, and the number of switches transferring LFSRs should be small for efficient performance. This corresponding addresses on searching such conditioned DLFSRs. An efficient probabilistic algorithm is given to find such DLFSRs with two or four switches, and it is proved to succeed with nonnegligible probability.
A parallel phrase matching (PM) engine for dictionary compression is presented. Hardware based parallel chaining hash can eliminate erroneous PM results raised by hash collision; while newly-designed storage architecture holding PM results solved the data dependency issue; Thus, the average compression speed is increased by 53%.
Seiji MIYOSHI Yoshinobu KAJIKAWA
We analyze the behaviors of the FXLMS algorithm using a statistical-mechanical method. The cross-correlation between a primary path and an adaptive filter and the autocorrelation of the adaptive filter are treated as macroscopic variables. We obtain simultaneous differential equations that describe the dynamical behaviors of the macroscopic variables under the condition that the tapped-delay line is sufficiently long. The obtained equations are deterministic and closed-form. We analytically solve the equations to obtain the correlations and finally compute the mean-square error. The obtained theory can quantitatively predict the behaviors of computer simulations including the cases of both not only white but also nonwhite reference signals. The theory also gives the upper limit of the step size in the FXLMS algorithm.
This letter proposes a novel speech enhancement system based on the ‘L’ shaped triple-microphone. The modified coherence-based algorithm and the first-order differential beamforming are combined to filter the spatial distributed noise. The experimental results reveal that the proposed algorithm achieves significant performance in spatial filtering under different noise scenarios.
Shijie LIN Chen DONG Zhiqiang WANG Wenzhong GUO Zhenyi CHEN Yin YE
A Lévy search strategy based chaotic artificial bee colony algorithm (LABC) is proposed in this paper. The chaotic sequence, global optimal mechanism and Lévy flight mechanism were introduced respectively into the initialization, the employed bee search and the onlooker bee search. The experiments show that the proposed algorithm performed better in convergence speed, global search ability and optimization accuracy than other improved ABC.
Ryo SHIBATA Gou HOSOYA Hiroyuki YASHIMA
Racetrack memory (RM) has attracted much attention. In RM, insertion and deletion (ID) errors occur as a result of an unstable reading process and are called position errors. In this paper, we first define a probabilistic channel model of ID errors in RM with multiple read-heads (RHs). Then, we propose a joint iterative decoding algorithm for spatially coupled low-density parity-check (SC-LDPC) codes over such a channel. We investigate the asymptotic behaviors of SC-LDPC codes under the proposed decoding algorithm using density evolution (DE). With DE, we reveal the relationship between the number of RHs and achievable information rates, along with the iterative decoding thresholds. The results show that increasing the number of RHs provides higher decoding performances, although the proposed decoding algorithm requires each codeword bit to be read only once regardless of the number of RHs. Moreover, we show the performance improvement produced by adjusting the order of the SC-LDPC codeword bits in RM.
Deng TANG Shaojing FU Yang YANG
Semi-bent functions have very high nonlinearity and hence they have many applications in symmetric-key cryptography, binary sequence design for communications, and combinatorics. In this paper, we focus on studying the additive autocorrelation of semi-bent functions. We provide a lower bound on the maximum additive autocorrelation absolute value of semi-bent functions with three-level additive autocorrelation. Semi-bent functions with three-level additive autocorrelation achieving this bound with equality are said to have perfect three-level additive autocorrelation. We present two classes of balanced semi-bent functions with optimal algebraic degree and perfect three-level additive autocorrelation.
In this letter, we consider several optimization problems associated with the configuration of grouping-based framed slotted ALOHA protocols. Closed-form formulas for determining the optimal values of system parameters such as the process termination time and confidence levels for partitioned groups are presented. Further, we address the maximum group size required for meaningful grouping gain and the effectiveness of the grouping technique in light of signaling overhead.
WenJie KANG PeiDong ZHU JieXin ZHANG JunYang ZHANG
Critical nodes identification is of great significance in protecting power grids. Network efficiency can be used as an evaluation index to identify the critical nodes and is an indicator to quantify how efficiently a network exchanges information and transmits energy. Since power grid is a heterogeneous network and can be decomposed into small functionally-independent grids, the concept of the Giant Component does not apply to power grids. In this paper, we first model the power grid as the directed graph and define the Giant Efficiency sub-Graph (GEsG). The GEsG is the functionally-independent unit of the network where electric energy can be transmitted from a generation node (i.e., power plants) to some demand nodes (i.e., transmission stations and distribution stations) via the shortest path. Secondly, we propose an algorithm to evaluate the importance of nodes by calculating their critical degree, results of which can be used to identify critical nodes in heterogeneous networks. Thirdly, we define node efficiency loss to verify the accuracy of critical nodes identification (CNI) algorithm and compare the results that GEsG and Giant Component are separately used as assessment criteria for computing the node efficiency loss. Experiments prove the accuracy and efficiency of our CNI algorithm and show that the GEsG can better reflect heterogeneous characteristics and power transmission of power grids than the Giant Component. Our investigation leads to a counterintuitive finding that the most important critical nodes may not be the generation nodes but some demand nodes.
Xuewan ZHANG Wenping GE Xiong WU Wenli DAI
Sparse code multiple access (SCMA) based on the message passing algorithm (MPA) for multiuser detection is a competitive non-orthogonal multiple access technique for fifth-generation wireless communication networks Among the existing multiuser detection schemes for uplink (UP) SCMA systems, the serial MPA (S-MPA) scheme, where messages are updated sequentially, generally converges faster than the conventional MPA (C-MPA) scheme, where all messages are updated in a parallel manner. In this paper, the optimization of message scheduling in the S-MPA scheme is proposed. Firstly, some statistical results for the probability density function (PDF) of the received signal are obtained at various signal-to-noise ratios (SNR) by using the Monte Carlo method. Then, based on the non-orthogonal property of SCMA, the data mapping relationship between resource nodes and user nodes is comprehensively analyzed. A partial codeword transmission of S-MPA (PCTS-MPA) with threshold decision scheme of PDF is proposed and verified. Simulations show that the proposed PCTS-MPA not only reduces the complexity of MPA without changing the bit error ratio (BER), but also has a faster convergence than S-MPA, especially at high SNR values.
Adaptive noise cancellation using adaptive filters is a known method for removing noise that interferes with signal measurements. The adaptive noise canceller performs filtering based on the current situation through a windowing process. The shape of the window function determines the tracking performance of the adaptive noise canceller with respect to the fluctuation of the property of the unknown system that noise (reference signal) passes. However, the shape of the window function in the field of adaptive filtering has not yet been considered in detail. This study mathematically treats the effect of the window function on the adaptive noise canceller and proposes an optimization method for the window function in situations where offline processing can be performed, such as biomedical signal measurements. We also demonstrate the validity of the optimized window function through numerical experiments.
Kazuo AOYAMA Kazumi SAITO Tetsuo IKEDA
This paper presents an efficient acceleration algorithm for Lloyd-type k-means clustering, which is suitable to a large-scale and high-dimensional data set with potentially numerous classes. The algorithm employs a novel projection-based filter (PRJ) to avoid unnecessary distance calculations, resulting in high-speed performance keeping the same results as a standard Lloyd's algorithm. The PRJ exploits a summable lower bound on a squared distance defined in a lower-dimensional space to which data points are projected. The summable lower bound can make the bound tighter dynamically by incremental addition of components in the lower-dimensional space within each iteration although the existing lower bounds used in other acceleration algorithms work only once as a fixed filter. Experimental results on large-scale and high-dimensional real image data sets demonstrate that the proposed algorithm works at high speed and with low memory consumption when large k values are given, compared with the state-of-the-art algorithms.
Takuya HABARA Keiichi MIZUTANI Hiroshi HARADA
In this paper, we propose an IEEE 802.15.10-based layer 2 routing (L2R) method with a load balancing algorithm; the proposal considers fairness in terms of the cumulative number of sending packets at each terminal to resolve the packet concentration problem for the IEEE 802.15.4-based low-power consumption wireless smart utility network (Wi-SUN) systems. The proposal uses the accumulated sending times of each terminal as a weight in calculating each path quality metric (PQM) to decide multi-hopping routes with load balancing in the network. Computer simulation of the mesh network with 256 terminals shows that the proposed routing method can improve the maximum sending ratio (MSR), defined as the ratio of the maximum sending times to the average number of sending times in the network, by 56% with no degradation of the end-to-end communication success ratio (E2E-SR). The proposed algorithm is also experimentally evaluated by using actual Wi-SUN modules. The proposed routing method also improves the MSR by 84% with 70 terminals. Computer simulations and experiments prove the effectiveness of the proposed method in terms of load balancing.
Chao WU Yuan'an LIU Fan WU Suyan LIU
The energy efficiency of Internet of Things (IoT) could be improved by RF energy transfer technologies.Aiming at IoT applications with a mobility-constrained mobile sink, a double-sourced energy transfer (D-ET) scheme is proposed. Based on the hierarchical routing information of network nodes, the Simultaneous Wireless Information and Power Transfer (SWIPT) method helps to improve the global data gathering performance. A genetic algorithm and graph theory are combined to analyze the node energy consumption distribution. Then dedicated charger nodes are deployed on the basis of the genetic algorithm's output. Experiments are conducted using Network Simulator-3 (NS-3) to evaluate the performance of the D-ET scheme. The simulation results show D-ET outperforms other schemes in terms of network lifetime and data gathering performance.