Haichuan YANG Shangce GAO Rong-Long WANG Yuki TODO
In 2019, a completely new algorithm, spherical evolution (SE), was proposed. The brand new search style in SE has been proved to have a strong search capability. In order to take advantage of SE, we propose a novel method called the ladder descent (LD) method to improve the SE' population update strategy and thereafter propose a ladder spherical evolution search (LSE) algorithm. With the number of iterations increasing, the range of parent individuals eligible to produce offspring gradually changes from the entire population to the current optimal individual, thereby enhancing the convergence ability of the algorithm. Experiment results on IEEE CEC2017 benchmark functions indicate the effectiveness of LSE.
Shinobu KUDO Shota ORIHASHI Ryuichi TANIDA Seishi TAKAMURA Hideaki KIMATA
Recently, image compression systems based on convolutional neural networks that use flexible nonlinear analysis and synthesis transformations have been developed to improve the restoration accuracy of decoded images. Although these methods that use objective metric such as peak signal-to-noise ratio and multi-scale structural similarity for optimization attain high objective results, such metric may not reflect human visual characteristics and thus degrade subjective image quality. A method using a framework called a generative adversarial network (GAN) has been reported as one of the methods aiming to improve the subjective image quality. It optimizes the distribution of restored images to be close to that of natural images; thus it suppresses visual artifacts such as blurring, ringing, and blocking. However, since methods of this type are optimized to focus on whether the restored image is subjectively natural or not, components that are not correlated with the original image are mixed into the restored image during the decoding process. Thus, even though the appearance looks natural, subjective similarity may be degraded. In this paper, we investigated why the conventional GAN-based compression techniques degrade subjective similarity, then tackled this problem by rethinking how to handle image generation in the GAN framework between image sources with different probability distributions. The paper describes a method to maximize mutual information between the coding features and the restored images. Experimental results show that the proposed mutual information amount is clearly correlated with subjective similarity and the method makes it possible to develop image compression systems with high subjective similarity.
This paper deals with the problem of enumerating 3-edge-connected spanning subgraphs of an input plane graph. In 2018, Yamanaka et al. proposed two enumeration algorithms for such a problem. Their algorithm generates each 2-edge-connected spanning subgraph of a given plane graph with n vertices in O(n) time, and another one generates each k-edge-connected spanning subgraph of a general graph with m edges in O(mT) time, where T is the running time to check the k-edge connectivity of a graph. This paper focuses on the case of the 3-edge-connectivity in a plane graph. We give an algorithm which generates each 3-edge-connected spanning subgraph of the input plane graph in O(n2) time. This time complexity is the same as the algorithm by Yamanaka et al., but our algorithm is simpler than theirs.
Ryoma SENDA Yoshiaki TAKATA Hiroyuki SEKI
It is well-known that pushdown systems (PDS) effectively preserve regularity. This property implies the decidability of the reachability problem for PDS and has been applied to automatic program verification. The backward regularity preservation property was also shown for an extension of PDS by adding registers. This paper aims to show the forward regularity preservation property. First, we provide a concise definition of the register model called register pushdown systems (RPDS). Second, we show the forward regularity preservation property of RPDS by providing a saturation algorithm that constructs a register automaton (RA) recognizing $post^{ast}_calP(L(calA))$ where $calA$ and $calP$ are a given RA and an RPDS, respectively, and $post^{ast}_calP$ is the forward image of the mapping induced by $calP$. We also give an example of applying the proposed algorithm to malware detection.
Hiroshi FUJIWARA Yuta WANIKAWA Hiroaki YAMAMOTO
The performance of online algorithms for the bin packing problem is usually measured by the asymptotic approximation ratio. However, even if an online algorithm is explicitly described, it is in general difficult to obtain the exact value of the asymptotic approximation ratio. In this paper we show a theorem that gives the exact value of the asymptotic approximation ratio in a closed form when the item sizes and the online algorithm satisfy some conditions. Moreover, we demonstrate that our theorem serves as a powerful tool for the design of online algorithms combined with mathematical optimization.
Koichiro ITAKURA Akihiko HIRATA Masato SONODA Taiki HIGASHIMOTO Tadao NAGATSUMA Takashi TOMURA Jiro HIROKAWA Norihiko SEKINE Issei WATANABE Akifumi KASAMATSU
This paper presents a 120-GHz-band split ring resonator (SRR) bandstop filter whose insertion loss can be controlled by coupling another lattice pattern substrate. The SRR bandstop filter and lattice pattern substrate is composed of 200-µm-thick quartz substrate and 5-µm-thick gold patterns. S21 of the SRR bandstop filter is -37.8 dB, and its -10-dB bandwidth is 115-130 GHz. S21 of the SRR bandstop filter changes to -4.1 dB at 125 GHz by arranging the lattice pattern substrate in close proximity to the SRR stopband filter, because coupling between the SRR and the lattice pattern occurs when the SRR and lattice pattern are opposed in close proximity. It was found that 10 Gbit/s data transmission can be achieved by setting the lattice pattern substrate just above the SRR bandstop filter with a spacer thickness of 50 µm, even though data transmission is impossible when only the SRR bandstop filter is inserted between the transmitter and the receiver.
To reduce peak-to-average power ratio, we propose a method of choosing suitable vectors in a partial transmit sequence technique. Conventional approaches require that a suitable vector be selected from a large number of candidates. By contrast, our method does not include such a selecting procedure, and instead generates random vectors from the Gaussian distribution whose covariance matrix is a solution of a relaxed problem. The suitable vector is chosen from the random vectors. This yields lower peak-to-average power ratio than a conventional method.
The PCHS (Park-Chang-Hong-Seo) algorithm is a varied Karatsuba algorithm (KA) that utilizes a different splitting strategy with no overlap module. Such an algorithm has been applied to develop efficient hybrid GF(2m) multipliers for irreducible trinomials and pentanomials. However, compared with KA-based hybrid multipliers, these multipliers usually match space complexity but require more gates delay. In this paper, we proposed a new design of hybrid multiplier using PCHS algorithm for irreducible all-one polynomial. The proposed scheme skillfully utilizes redundant representation to combine and simplify the subexpressions computation, which result in a significant speedup of the implementation. As a main contribution, the proposed multiplier has exactly the same space and time complexities compared with the KA-based scheme. It is the first time to show that different splitting strategy for KA also can develop the same efficient multiplier.
Offset quadrature amplitude modulation based orthogonal frequency division multiplexing (OFDM/OQAM) is a promising multi-carrier modulation technique to achieve a low-sidelobe spectrum while maintaining orthogonality among subcarriers. However, a major shortcoming of OFDM/OQAM systems is the high peak-to-average power ratio (PAPR) of the transmit signal. To resolve the high-PAPR issue of traditional OFDM, a self-synchronized-scrambler-based selected-mapping has been investigated, where the transmit sequence is scrambled to reduce PAPR. In this method, the receiver must use a descrambler to recover the original data. However, the descrambling process leads to error propagation, which degrades the bit error rate (BER). As described herein, a partial scrambling overlapped selected mapping (PS-OSLM) scheme is proposed for PAPR reduction of OFDM/OQAM signals, where candidate sequences are generated using partial scrambling of original data. The best candidate, the one that minimizes the peak amplitude within multiple OFDM/OQAM symbols, is selected. In the proposed method, an overlap search algorithm for SLM is applied to reduce the PAPR of OFDM/OQAM signals. Numerical results demonstrate that our PS-OSLM proposal achieves better BER than full-scrambling overlapped SLM (FS-OSLM) in OFDM/OQAM systems while maintaining almost equivalent PAPR reduction capability as FS-OSLM and better PAPR than SLM without overlap search. Additionally, we derive a theoretical lower bound expression for OFDM/OQAM with PS-OSLM, and clarify the effectiveness of the proposed scheme.
Mikio HASEGAWA Hirotake ITO Hiroki TAKESUE Kazuyuki AIHARA
Recently, new optimization machines based on non-silicon physical systems, such as quantum annealing machines, have been developed, and their commercialization has been started. These machines solve the problems by searching the state of the Ising spins, which minimizes the Ising Hamiltonian. Such a property of minimization of the Ising Hamiltonian can be applied to various combinatorial optimization problems. In this paper, we introduce the coherent Ising machine (CIM), which can solve the problems in a milli-second order, and has higher performance than the quantum annealing machines especially on the problems with dense mutual connections in the corresponding Ising model. We explain how a target problem can be implemented on the CIM, based on the optimization scheme using the mutually connected neural networks. We apply the CIM to traveling salesman problems as an example benchmark, and show experimental results of the real machine of the CIM. We also apply the CIM to several combinatorial optimization problems in wireless communication systems, such as channel assignment problems. The CIM's ultra-fast optimization may enable a real-time optimization of various communication systems even in a dynamic communication environment.
Xiaoran CHEN Xin QIU Xurong CHAI
Orthogonal frequency division multiplexing (OFDM) technique has been widely used in communication systems in pursuit of the most efficient utilization of spectrum. However, the increase of the number of orthogonal subcarriers will lead to the rise of the peak-to-average power ratio (PAPR) of the waveform, thus reducing the efficiency of the power amplifiers. In this letter we propose a phase-changed PAPR reduction technique based on windowing function architecture for OFDM systems. This technique is based on the idea of phase change, which makes the spectrum of output signal almost free of regrowth caused by peak clipping. It can reduce more than 28dBc adjacent channel power ratio (ACPR) compared with the traditional peak windowing clipping methods in situation that peak is maximally suppressed. This technique also has low algorithm complexity so it can be easily laid out on hardware. The proposed algorithm has been laid out on a low-cost field-programmable gate array (FPGA) to verify its effectiveness and feasibility. A 64-QAM modulated 20M LTE-A waveform is used for measurement, which has a sampling rate of 245.67M.
Kazuhiro MURAKAMI Arata KAWAMURA Yoh-ichi FUJISAKA Nobuhiko HIRUMA Youji IIGUNI
In this paper, we propose a real-time BSS (Blind Source Separation) system with two microphones that extracts only desired sound sources. Under the assumption that the desired sound sources are close to the microphones, the proposed BSS system suppresses distant sound sources as undesired sound sources. We previously developed a BSS system that can estimate the distance from a microphone to a sound source and suppress distant sound sources, but it was not a real-time processing system. The proposed BSS system is a real-time version of our previous BSS system. To develop the proposed BSS system, we simplify some BSS procedures of the previous system. Simulation results showed that the proposed system can effectively suppress the distant source signals in real-time and has almost the same capability as the previous system.
The circuit satisfiability problem has been intensively studied since Ryan Williams showed a connection between the problem and lower bounds for circuit complexity. In this letter, we present a #SAT algorithm for synchronous Boolean circuits of n inputs and s gates in time $2^{nleft(1 - rac{1}{2^{O(s/n)}} ight)}$ if s=o(n log n).
Makoto NAKAMURA Hiroaki NISHIUCHI Jin NAKAZATO Konstantin KOSLOWSKI Julian DAUBE Ricardo SANTOS Gia Khanh TRAN Kei SAKAGUCHI
In this paper, a Proof-of-Concept (PoC) architecture is constructed, and the effectiveness of mmWave overlay heterogeneous network (HetNet) with mesh backhaul utilizing route-multiplexing and Multi-access Edge Computing (MEC) utilizing prefetching algorithm is verified by measuring the throughput and the download time of real contents. The architecture can cope with the intensive mobile data traffic since data delivery utilizes multiple backhaul routes based on the mesh topology, i.e. route-multiplexing mechanism. On the other hand, MEC deploys the network edge contents requested in advance by nearby User Equipment (UE) based on pre-registered context information such as location, destination, demand application, etc. to the network edge, which is called prefetching algorithm. Therefore, mmWave access can be fully exploited even with capacity-limited backhaul networks by introducing the proposed algorithm. These technologies solve the problems in conventional mmWave HetNet to reduce mobile data traffic on backhaul networks to cloud networks. In addition, the proposed architecture is realized by introducing wireless Software Defined Network (SDN) and Network Function Virtualization (NFV). In our architecture, the network is dynamically controlled via wide-coverage microwave band links by which UE's context information is collected for optimizing the network resources and controlling network infrastructures to establish backhaul routes and MEC servers. In this paper, we develop the hardware equipment and middleware systems, and introduce these algorithms which are used as a driver of IEEE802.11ad and open source software. For 5G and beyond, the architecture integrated in mmWave backhaul, MEC and SDN/NFV will support some scenarios and use cases.
Carlos MANSO Pol ALEMANY Ricard VILALTA Raul MUÑOZ Ramon CASELLAS Ricardo MARTÍNEZ
The need of telecommunications operators to reduce Capital and Operational Expenditures in networks which traffic is continuously growing has made them search for new alternatives to simplify and automate their procedures. Because of the different transport network segments and multiple layers, the deployment of end-to-end services is a complex task. Also, because of the multiple vendor existence, the control plane has not been fully homogenized, making end-to-end connectivity services a manual and slow process, and the allocation of computing resources across the entire network a difficult task. The new massive capacity requested by Data Centers and the new 5G connectivity services will urge for a better solution to orchestrate the transport network and the distributed computing resources. This article presents and demonstrates a Network Slicing solution together with an end-to-end service orchestration for transport networks. The Network Slicing solution permits the co-existence of virtual networks (one per service) over the same physical network to ensure the specific service requirements. The network orchestrator allows automated end-to-end services across multi-layer multi-domain network segments making use of the standard Transport API (TAPI) data model for both l0 and l2 layers. Both solutions will allow to keep up with beyond 5G services and the higher and faster demand of network and computing resources.
Kazuya TSUKAMOTO Hitomi TAMURA Yuzo TAENAKA Daiki NOBAYASHI Hiroshi YAMAMOTO Takeshi IKENAGA Myung LEE
In IoT era, the growth of data variety is driven by cross-domain data fusion. In this paper, we advocate that “local production for local consumption (LPLC) paradigm” can be an innovative approach in cross-domain data fusion, and propose a new framework, geolocation-centric information platform (GCIP) that can produce and deliver diverse spatio-temporal content (STC). In the GCIP, (1) infrastructure-based geographic hierarchy edge network and (2) adhoc-based STC retention system are interplayed to provide both of geolocation-awareness and resiliency. Then, we discussed the concepts and the technical challenges of the GCIP. Finally, we implemented a proof-of-concepts of GCIP and demonstrated its efficacy through practical experiments on campus IPv6 network and simulation experiments.
Akihito AIBA Minoru YOSHIDA Daichi KITAMURA Shinnosuke TAKAMICHI Hiroshi SARUWATARI
We studied an acoustic anomaly detection system for equipments, where the outlier detection method based on recorded sounds is used. In a real environment, the SNR of the target sound against background noise is low, and there is the problem that it is necessary to catch slight changes in sound buried in noise. In this paper, we propose a system in which a sound source extraction process is provided at the preliminary stage of the outlier detection process. In the proposed system, nonnegative matrix factorization based on generalized Gaussian distribution (GGD-NMF) is used as a sound source extraction process. We evaluated the improvement of the anomaly detection performance in a low-SNR environment. In this experiment, SNR capable of detecting an anomaly was greatly improved by providing GGD-NMF for preprocessing.
Narihiro NAKAMOTO Toru TAKAHASHI Toru FUKASAWA Naofumi YONEDA Hiroaki MIYASHITA
This paper proposes a dual linear-polarized open-ended waveguide subarray designed for use in phased array antennas. The proposed subarray is a one-dimensional linear array that consists of open-ended waveguide antenna elements and suspended stripline feed networks to realize vertical and horizontal polarizations. The antenna includes a novel suspended stripline-to-waveguide transition that combines double- and quad-ridge waveguides to minimize the size of the transition and enhance the port isolation. Metal posts are installed on the waveguide apertures to eliminate scan-blindness. Prototype subarrays are fabricated and tested in an array of 16 subarrays. The experimental tests and numerical simulations indicate that the prototype subarray offers a low reflection coefficient of less than -11.4dB, low cross-polarization of less than -26dB, and antenna efficiency above 69% in the frequency bandwidth of 14%.
Yu Min HWANG Isaac SIM Young Ghyu SUN Ju Phil CHO Jin Young KIM
In this letter, we study an interference scenario under a smart interferer which observes color channels and interferes with a visible light communication (VLC) network. We formulate the smart interference problem based on a Stackelberg game and propose an optimal response algorithm to overcome the interference by optimizing transmit power and sub-color channel allocation. The proposed optimization algorithm is composed with Lagrangian dual decomposition and non-linear fractional programming to have stability to get optimum points. Numerical results show that the utility by the proposed algorithm is increased over that of the algorithm based on the Nash game and the baseline schemes.
Ryousei TAKANO Kuniyasu SUZAKI
A conventional data center that consists of monolithic-servers is confronted with limitations including lack of operational flexibility, low resource utilization, low maintainability, etc. Resource disaggregation is a promising solution to address the above issues. We propose a concept of disaggregated cloud data center architecture called Flow-in-Cloud (FiC) that enables an existing cluster computer system to expand an accelerator pool through a high-speed network. FlowOS-RM manages the entire pool resources, and deploys a user job on a dynamically constructed slice according to a user request. This slice consists of compute nodes and accelerators where each accelerator is attached to the corresponding compute node. This paper demonstrates the feasibility of FiC in a proof of concept experiment running a distributed deep learning application on the prototype system. The result successfully warrants the applicability of the proposed system.