Fill-a-Pix is a pencil-and-paper puzzle, which is popular worldwide since announced by Conceptis in 2003. It provides a rectangular grid of squares that must be filled in to create a picture. Precisely, we are given a rectangular grid of squares some of which has an integer from 0 to 9 in it, and our task is to paint some squares black so that every square with an integer has the same number of painted squares around it including the square itself. Despite its popularity, computational complexity of Fill-a-Pix has not been known. We in this paper show that the puzzle is NP-complete, ASP-complete, and #P-complete via a parsimonious reduction from the Boolean satisfiability problem. We also consider the fewest clues problem of Fill-a-Pix, where the fewest clues problem is recently introduced by Demaine et al. for analyzing computational complexity of designing “good” puzzles. We show that the fewest clues problem of Fill-a-Pix is Σ2P-complete.

Pseudo-random sequences with good statistical property, such as low autocorrelation, high linear complexity and 2-adic complexity, have been widely applied to designing reliable stream ciphers. In this paper, we explicitly determine the 2-adic complexities of two classes of generalized cyclotomic binary sequences with order 4. Our results show that the 2-adic complexities of both of the sequences attain the maximum. Thus, they are large enough to resist the attack of the rational approximation algorithm for feedback with carry shift registers. We also present some examples to illustrate the validity of the results by Magma programs.

We numerically investigate that optimal robust onion-like networks can emerge even with the constraint of surface growth in supposing a spatially embedded transportation or communication system. To be onion-like, moderately long links are necessary in the attachment through intermediations inspired from a social organization theory.

Joint transmit and receive antenna selection (JTRAS) for transceive spatial modulation (TRSM) is investigated in this paper. A couple of low-complexity and efficient JTRAS algorithms are proposed to improve the reliability of TRSM systems by maximizing the minimum Euclidean distance (ED) among all received signals. Specifically, the QR decomposition based ED-JTRAS achieves near-optimal error performance with a moderate complexity reduction as compared to the optimal ED-JTRAS method. The singular value decomposition based ED-JTRAS achieves sub-optimal error performance with a significant complexity reduction. Simulation results show that the proposed methods remarkably improve the system reliability in both uncorrelated and spatially correlated Rayleigh fading channels, as compared to the conventional norm based JTRAS method.

A variety of all-new systems such as a massive machine type communication (mMTC) system will be supported in 5G and beyond. Although each mMTC device occupies quite narrow bandwidth, the massive number of devices expected will generate a vast array of traffic and consume enormous spectrum resources. Therefore, it is necessary to proactively gather up and exploit fractional spectrum resources including guard bands that are secured but unused by the existing Long Term Evolution (LTE) systems. The guard band is originally secured as a margin for high out-of-band emission (OOBE) caused by the discontinuity between successive symbols in the cyclic prefix-based orthogonal frequency division multiplexing (CP-OFDM), and new-waveforms enabling high OOBE suppression have been widely researched to efficiently allocate narrowband communication to the frequency gap. Time-domain windowing is a well-known signal processing technique for reducing OOBE with low complexity and a universal time-domain windowed OFDM (UTW-OFDM) with a long transition duration exceeding the CP length has demonstrated its ability in WLAN-based systems. In this paper, we apply UTW-OFDM to the LTE downlink system and comprehensively evaluate its performance under the channel models defined by 3GPP. Specifically, we evaluate OOBE reduction and block error rate (BLER) by computer simulation and clarify how far OOBE can be reduced without degrading communication quality. Furthermore, we estimate the implementation complexity of the proposed UTW-OFDM, the conventional CP-OFDM, and the universal filtered-OFDM (UF-OFDM) by calculating the number of required multiplications. These evaluation and estimation results demonstrate that the proposed UTW-OFDM is a practical new-waveform applicable to the 5G and beyond.

Spectrum sensing is a fundamental requirement for cognitive radio, and it is a challenging problem in impulsive noise modeled by symmetric alpha-stable (SαS) distributions. The Gaussian kernelized energy detector (GKED) performs better than the conventional detectors in SαS distributed noise. However, it fails to detect the DC signal and has high computational complexity. To solve these problems, this paper proposes a more efficient and robust detector based on a Gaussian function (GF). The analytical expressions of the detection and false alarm probabilities are derived and the best parameter for the statistic is calculated. Theoretical analysis and simulation results show that the proposed GF detector has much lower computational complexity than the GKED method, and it can successfully detect the DC signal. In addition, the GF detector performs better than the conventional counterparts including the GKED detector in SαS distributed noise with different characteristic exponents. Finally, we discuss the reason why the GF detector outperforms the conventional counterparts.

In this paper, a reduction of the number of components included in direct simulation type active complex filter is proposed. The proposed method is achieved by sharing NIC's (Negative Impedance Converters) which satisfy some conditions. Compared with the conventional method, the proposed one has wide generality. As an example, a third-order complex elliptic filter is designed. The validity of the proposed method is confirmed through experiment.

In sparsity-based optimization problems for two dimensional (2-D) direction-of-arrival (DOA) estimation using L-shaped nested arrays, one of the major issues is computational complexity. A 2-D DOA estimation algorithm is proposed based on reconsitution sparse Bayesian learning (RSBL) and cross covariance matrix decomposition. A single measurement vector (SMV) model is obtained by the difference coarray corresponding to one-dimensional nested array. Through spatial smoothing, the signal measurement vector is transformed into a multiple measurement vector (MMV) matrix. The signal matrix is separated by singular values decomposition (SVD) of the matrix. Using this method, the dimensionality of the sensing matrix and data size can be reduced. The sparse Bayesian learning algorithm is used to estimate one-dimensional angles. By using the one-dimensional angle estimations, the steering vector matrix is reconstructed. The cross covariance matrix of two dimensions is decomposed and transformed. Then the closed expression of the steering vector matrix of another dimension is derived, and the angles are estimated. Automatic pairing can be achieved in two dimensions. Through the proposed algorithm, the 2-D search problem is transformed into a one-dimensional search problem and a matrix transformation problem. Simulations show that the proposed algorithm has better angle estimation accuracy than the traditional two-dimensional direction finding algorithm at low signal-to-noise ratio and few samples.

A low complexity channel estimation scheme using data-dependent superimposed training (DDST) is proposed in this paper, where the pilots are inserted in more than one block, rather than the single block of the original DDST. Comparing with the original DDST (which improves the performance of channel estimation at the cost of huge computational overheads), the proposed DDST scheme improves the performance of channel estimation with only a slight increase in the consumption of computation resources. The optimal precoder is designed to minimize the data distortion caused by the rank-deficient precoding. The optimal pilots and placement are also provided to improve the performance of channel estimation. In addition, the impact of power allocation between the data and pilots on symbol detection is analyzed, the optimal power allocation scheme is derived to maximize the effective signal-to-noise ratio at the receiver. Simulation results are presented to show the computational advantage of the proposed scheme, and the advantages of the optimal pilots and power allocation scheme.

This paper proposes a novel low complexity lattice reduction-aided iterative receiver for overloaded MIMO. Novel noise cancellation is proposed that increases an equivalent channel gain with a scalar gain introduced in this paper, which results in the improvement of the signal to noise power ratio (SNR). We theoretically analyze the performance of the proposed receiver that the lattice reduction raises the SNR of the detector output signals as the scalar gain increases, when the Lenstra-Lenstra-Lova's (LLL) algorithm is applied to implement the lattice reduction. Because the SNR improvement causes the scalar gain to increase, the performance is improved by iterating the reception process. Computer simulations confirm the performance. The proposed receiver attains a gain of about 5dB at the BER of 10-4 in a 6×2 overloaded MIMO channel. Computational complexity of the proposed receiver is about 1/50 as much as that of the maximum likelihood detection (MLD).

In this paper, new classes of binary generalized cyclotomic sequences of period 2pm+1qn+1 are constructed. These sequences are balanced. We calculate the linear complexity of the constructed sequences with a simple method. The results show that the linear complexity of such sequences attains the maximum.

This paper presents a 6th-order quadrature bandpass delta sigma AD modulator (QBPDSM) with 2nd-order image rejection using dynamic amplifier and noise coupling (NC) SAR quantizer embedded by passive adder for the application of wireless communication system. A novel complex integrator using dynamic amplifier is proposed to improve the energy efficiency of the QBPDSM. The NC SAR quantizer can realize an additional 2nd-order noise shaping and 2nd-order image rejection by the digital domain noise coupling technique. As a result, the 6th-order QBPDSM with 2nd-order image rejection is realized by two complex integrators using dynamic amplifier and the NC SAR quantizer. The SPICE simulation results demonstrate the feasibility of the proposed QBPDSM in 90nm CMOS technology. Simulated SNDR of 76.30dB is realized while a sinusoid -3.25dBFS input is sampled at 33.3MS/s and the bandwidth of 2.083MHz (OSR=8) is achieved. The total power consumption in the modulator is 6.74mW while the supply voltage is 1.2V.

Multiuser massive multi-input multi-output (MU massive MIMO) is considered as a promising technology for the fifth generation (5G) of the wireless communication system. In this paper, we propose a low-complexity joint antenna and user selection scheme with block diagonalization (BD) precoding for MU massive MIMO downlink channel in the time division duplex (TDD) system. The base station (BS) is equipped with a large-scale transmit antenna array while each user is using the single receive antenna in the system. To reduce the hardware cost, BS will be implemented by limited number of radio frequency (RF) chains and BS must activate some selected transmit antennas in the BS side for data transmitting and some users' receive antennas in user side for data receiving. To achieve the reduction in the computation complexity in the antenna and user selection while maintaining the same or higher sum-rate in the system, the proposed scheme relies on three complexity reduction key factors. The first key factor is that finding the average channel gains for the transmit antenna in the BS side and the receive antenna in the user side to select the best channel gain antennas and users. The second key factor called the complexity control factor ξ(Xi) for the antenna set and the user set limitation is used to control the complexity of the brute force search. The third one is that using the assumption of the point-to-point deterministic MIMO channel model to avoid the singular value decomposition (SVD) computation in the brute force search. We show that the proposed scheme offers enormous reduction in the computation complexity while ensuring the acceptable performance in terms of total system sum-rate compared with optimal and other conventional schemes.

Unitary operator discrimination is a fundamental problem in quantum information theory. The basic version of this problem can be described as follows: Given a black box implementing a unitary operator U∈S:={U1, U2} under some probability distribution over S, the goal is to decide whether U=U1 or U=U2. In this paper, we consider the query complexity of this problem. We show that there exists a quantum algorithm that solves this problem with bounded error probability using $lceil{sqrt{6} heta_{ m cover}^{-1}} ceil$ queries to the black box in the worst case, i.e., under any probability distribution over S, where the parameter θcover, which is determined by the eigenvalues of $U_1^dagger {U_2}$, represents the “closeness” between U1 and U2. We also show that this upper bound is essentially tight: we prove that for every θcover > 0 there exist operators U1 and U2 such that any quantum algorithm solving this problem with bounded error probability requires at least $lceil{rac{2}{3 heta_{ m cover}}} ceil$ queries under uniform distribution over S.

In this letter, a physical-layer network coding (PNC) scheme based on continuous phase modulation (CPM) signal using the titled-phase model, i.e., TIP-CPM-PNC, is presented, and the combined titled-phase state trellis for the superimposed CPM signal in TIP-CPM-PNC is discussed. Simulation results show that the proposed scheme with low decoding complexity can achieve the same error performance as CPM-PNC using the traditional-phase model.

In 2017, Shirase proposed a variant of Elliptic Curve Method combined with Complex Multiplication method for generating certain special kinds of elliptic curves. His algorithm can efficiently factorize a given composite integer when it has a prime factor p of the form 4p=1+Dv2 for some integer v, where -D is an auxiliary input integer called a discriminant. However, there is a disadvantage that the previous method works only for restricted cases where the class polynomial associated to -D has degree at most two. In this paper, we propose a generalization of the previous algorithm to the cases of class polynomials having arbitrary degrees, which enlarges the class of composite integers factorizable by our algorithm. We also extend the algorithm to more various cases where we have 4p=t2+Dv2 and p+1-t is a smooth integer.

The CC-Link proposed by the Mitsubishi Electric Company is an industrial network used exclusively in most industries. However, the probabilities of data loss and interference with equipment control increase if the transmission time is greater than the link scan time of 381µs. The link scan time can be reduced by designing the CC-Link module as an external microprocessor (MPU) interface of R-IN32M3; however, it then suffers from expandability issues. Thus, in this paper, we propose a new CC-Link module utilizing R-IN32M3 to improve the expandability. In our designed CC-Link module, we devise a dual-port RAM (DPRAM) function in an external I/O module, which enables parallel communication between the DPRAM and the external MPU. Our experiment with the implemented CC-Link prototype demonstrates that our CC-Link design improves the communication speed owing to the parallel communication between DPRAM and external MPU, and expandability of remote I/O. Our design achieves miniaturization of the CC-Link module, wiring reduction, and an approximately 30% reduction in the link scan time. Furthermore, because we utilize both the Renesas R-IN32M3 and Xilinx XC95144XL chips widely used in diverse application areas, the designed CC-Link module reduces the investment cost. The proposed design is expected to significantly contribute to the utilization of the programmable logic controller memory and I/O expansion for factory automation and improvement of the investment efficiency in the flat panel display industry.

Pseudorandom number generators are required to generate pseudorandom numbers which have good statistical properties as well as unpredictability in cryptography. An m-sequence is a linear feedback shift register sequence with maximal period over a finite field. M-sequences have good statistical properties, however we must nonlinearize m-sequences for cryptographic purposes. A geometric sequence is a sequence given by applying a nonlinear feedforward function to an m-sequence. Nogami, Tada and Uehara proposed a geometric sequence whose nonlinear feedforward function is given by the Legendre symbol, and showed the period, periodic autocorrelation and linear complexity of the sequence. Furthermore, Nogami et al. proposed a generalization of the sequence, and showed the period and periodic autocorrelation. In this paper, we first investigate linear complexity of the geometric sequences. In the case that the Chan-Games formula which describes linear complexity of geometric sequences does not hold, we show the new formula by considering the sequence of complement numbers, Hasse derivative and cyclotomic classes. Under some conditions, we can ensure that the geometric sequences have a large linear complexity from the results on linear complexity of Sidel'nikov sequences. The geometric sequences have a long period and large linear complexity under some conditions, however they do not have the balance property. In order to construct sequences that have the balance property, we propose interleaved sequences of the geometric sequence and its complement. Furthermore, we show the periodic autocorrelation and linear complexity of the proposed sequences. The proposed sequences have the balance property, and have a large linear complexity if the geometric sequences have a large one.

In the past two decades, many generalized cyclotomic sequences have been constructed and they have been used in cryptography and communication systems for their high linear complexity and low autocorrelation. But there are a few of papers focusing on the 2-adic complexities of such sequences. In this paper, we first give a property of a class of Gaussian periods based on Whiteman's generalized cyclotomic classes of order 4. Then, as an application of this property, we study the 2-adic complexity of a class of Whiteman's generalized cyclotomic sequences constructed from two distinct primes p and q. We prove that the 2-adic complexity of this class of sequences of period pq is lower bounded by pq-p-q-1. This lower bound is at least greater than one half of its period and thus it shows that this class of sequences can resist against the rational approximation algorithm (RAA) attack.

Detecting anomalies, such as network failure or intentional attack in Internet, is a vital but challenging task. Although numerous techniques have been developed based on Internet traffic, detecting anomalies from the perspective of Internet topology structure is going to be possible because the anomaly detection of structured datasets based on complex network theory has become a focus of attention recently. In this paper, an anomaly detection method for the large-scale Internet topology is proposed to detect local structure crashes caused by the cascading failure. In order to quantify the dynamic changes of Internet topology, the network path changes coefficient (NPCC) is put forward which highlights the Internet abnormal state after it is attacked continuously. Furthermore, inspired by Fibonacci Sequence, we proposed the decision function that can determine whether the Internet is abnormal or not. That is the current Internet is abnormal if its NPCC is out of the normal domain calculated using the previous k NPCCs of Internet topology. Finally the new Internet anomaly detection method is tested against the topology data of three Internet anomaly events. The results show that the detection accuracy of all events are over 97%, the detection precision for three events are 90.24%, 83.33% and 66.67%, when k=36. According to the experimental values of index F1, larger values of k offer better detection performance. Meanwhile, our method has better performance for the anomaly behaviors caused by network failure than those caused by intentional attack. Compared with traditional anomaly detection methods, our work is more simple and powerful for the government or organization in items of detecting large-scale abnormal events.