Distributed computing is one of the powerful solutions for computational tasks that need the massive size of dataset. Lagrange coded computing (LCC), proposed by Yu et al. [15], realizes private and secure distributed computing under the existence of stragglers, malicious workers, and colluding workers by using an encoding polynomial. Since the encoding polynomial depends on a dataset, it must be updated every arrival of new dataset. Therefore, it is necessary to employ efficient algorithm to construct the encoding polynomial. In this paper, we propose Newton coded computing (NCC) which is based on Newton interpolation to construct the encoding polynomial. Let K, L, and T be the number of data, the length of each data, and the number of colluding workers, respectively. Then, the computational complexity for construction of an encoding polynomial is improved from O(L(K+T)log 2(K+T)log log (K+T)) for LCC to O(L(K+T)log (K+T)) for the proposed method. Furthermore, by applying the proposed method, the computational complexity for updating the encoding polynomial is improved from O(L(K+T)log 2(K+T)log log (K+T)) for LCC to O(L) for the proposed method.

This paper proposes a non-linear overloaded MIMO detector that outperforms the conventional soft-input maximum likelihood detector (MLD) with less computational complexity. We propose iterative log-likelihood ratio (LLR) estimation and multi stage LLR estimation for the proposed detector to achieve such superior performance. While the iterative LLR estimation achieves better BER performance, the multi stage LLR estimation makes the detector less complex than the conventional soft-input maximum likelihood detector (MLD). The computer simulation reveals that the proposed detector achieves about 0.6dB better BER performance than the soft-input MLD with about half of the soft-input MLD's complexity in a 6×3 overloaded MIMO OFDM system.

In software defined radio systems, a channelizer plays an important role in extracting the desired signals from a wideband signal. Compared to the conventional methods, the proposed scheme provides a solution to design a digital channelizer extracting the multiple subband signals at different center frequencies with low complexity. To do this, this paper formulates the problem as an optimization problem, which minimizes the required multiplications number subject to the constraints of the ripple in the passbands and the stopbands for single channel and combined multiple channels. In addition, a solution to solve the optimization problem is also presented and the corresponding structure is demonstrated. Simulation results show that the proposed scheme requires smaller number of the multiplications than other conventional methods. Moreover, unlike other methods, this structure can process signals with different bandwidths at different center frequencies simultaneously only by changing the status of the corresponding multiplexers without hardware reimplementation.

In this survey we summarize properties of pseudorandomness and non-randomness of some number-theoretic sequences and present results on their behaviour under the following measures of pseudorandomness: balance, linear complexity, correlation measure of order k, expansion complexity and 2-adic complexity. The number-theoretic sequences are the Legendre sequence and the two-prime generator, the Thue-Morse sequence and its sub-sequence along squares, and the prime omega sequences for integers and polynomials.

This paper proposes low complexity resource allocation in frequency domain non-orthogonal multiple access where many devices access with a base station. The number of the devices is assumed to be more than that of the resource for network capacity enhancement, which is demanded in massive machine type communications (mMTC). This paper proposes two types of resource allocation techniques, all of which are based on the MIN-MAX approach. One of them seeks for nicer resource allocation with only channel gains. The other technique applies the message passing algorithm (MPA) for better resource allocation. The proposed resource allocation techniques are evaluated by computer simulation in frequency domain non-orthogonal multiple access. The proposed technique with the MPA achieves the best bit error rate (BER) performance in the proposed techniques. However, the computational complexity of the proposed techniques with channel gains is much smaller than that of the proposed technique with the MPA, whereas the BER performance of the proposed techniques with channel gains is only about 0.1dB inferior to that with the MPA in the multiple access with the overloading ratio of 1.5 at the BER of 10-4. They attain the gain of about 10dB at the BER of 10-4 in the multiple access with the overloading ration of 2.0. Their complexity is 10-16 as small as the conventional technique.

Pseudorandom sequences with large linear complexity can resist the linear attack. The trace representation plays an important role in analysis and design of pseudorandom sequences. In this letter, we present the construction of a family of new binary sequences derived from Euler quotients modulo pq, where pq is a product of two primes and p divides q-1. Firstly, the linear complexity of the sequences are investigated. It is proved that the sequences have larger linear complexity and can resist the attack of Berlekamp-Massey algorithm. Then, we give the trace representation of the proposed sequences by determining the corresponding defining pair. Moreover, we generalize the result to the Euler quotients modulo pmqn with m≤n. Results indicate that the generalized sequences still have high linear complexity. We also give the trace representation of the generalized sequences by determining the corresponding defining pair. The result will be helpful for the implementation and the pseudorandom properties analysis of the sequences.

Automatic modulation recognition (AMR) plays a critical role in modern communication systems. Owing to the recent advancements of deep learning (DL) techniques, the application of DL has been widely studied in AMR, and a large number of DL-AMR algorithms with high recognition rates have been developed. Most DL-AMR algorithm models have high recognition accuracy but have numerous parameters and are huge, complex models, which make them hard to deploy on resource-constrained platforms, such as satellite platforms. Some lightweight and low-complexity DL-AMR algorithm models also struggle to meet the accuracy requirements. Based on this, this paper proposes a lightweight and high-recognition-rate DL-AMR algorithm model called Lightweight Densely Connected Convolutional Network (DenseNet) Long Short-Term Memory network (LDLSTM). The model cascade of DenseNet and LSTM can achieve the same recognition accuracy as other advanced DL-AMR algorithms, but the parameter volume is only 1/12 that of these algorithms. Thus, it is advantageous to deploy LDLSTM in resource-constrained systems.

This paper analyzes a blockchain network forming a directed acyclic graph (DAG), called a DAG-type blockchain, from the viewpoint of graph algorithm theory. To use a DAG-type blockchain, NP-hard graph optimization problems on the DAG are required to be solved. Although various problems for undirected and directed graphs can be efficiently solved by using the notions of graph parameters, these currently known parameters are meaningless for DAGs, which implies that it is hopeless to design efficient algorithms based on the parameters for such problems. In this work, we propose a novel graph parameter for directed graphs called a DAG-pathwidth, which represents the closeness to a directed path. This is an extension of the pathwidth, a well-known graph parameter for undirected graphs. We analyze the features of the DAG-pathwidth and prove that computing the DAG-pathwidth of a DAG (directed graph in general) is NP-complete. Finally, we propose an efficient algorithm for a variant of the maximum k-independent set problem for the DAG-type blockchain when the DAG-pathwidth of the input graph is small.

This paper proposes a novel approach to low complexity soft input decoding for lattice reduction-aided MIMO receivers. The proposed approach feeds a soft input decoder with soft signals made from hard decision signals generated by using a lattice reduction-aided linear detector. The soft signal is a weighted-sum of some candidate vectors that are near by the hard decision signal coming out from the lattice reduction-aided linear detector. This paper proposes a technique to adjust the weight adapt to the channel for the higher transmission performance. Furthermore, we propose to introduce a coefficient that is used for the weights in order to enhance the transmission performance. The transmission performance is evaluated in a 4×4 MIMO channel. When a linear MMSE filter or a serial interference canceller is used as the linear detector, the proposed technique achieves about 1.0dB better transmission performance at the BER of 10-5 than the decoder fed with the hard decision signals. In addition, the low computational complexity of the proposed technique is quantitatively evaluated.

A unified construction for yielding optimal and balanced quaternary sequences from ideal/optimal balanced binary sequences was proposed by Zeng et al. In this paper, the linear complexity over finite field 𝔽2, 𝔽4 and Galois ring ℤ4 of the quaternary sequences are discussed, respectively. The exact values of linear complexity of sequences obtained by Legendre sequence pair, twin-prime sequence pair and Hall's sextic sequence pair are derived.

A vertex subset I of a graph G is called a k-path vertex cover if every path on k vertices in G contains at least one vertex from I. The K-PATH VERTEX COVER RECONFIGURATION (K-PVCR) problem asks if one can transform one k-path vertex cover into another via a sequence of k-path vertex covers where each intermediate member is obtained from its predecessor by applying a given reconfiguration rule exactly once. We investigate the computational complexity of K-PVCR from the viewpoint of graph classes under the well-known reconfiguration rules: TS, TJ, and TAR. The problem for k=2, known as the VERTEX COVER RECONFIGURATION (VCR) problem, has been well-studied in the literature. We show that certain known hardness results for VCR on different graph classes can be extended for K-PVCR. In particular, we prove a complexity dichotomy for K-PVCR on general graphs: on those whose maximum degree is three (and even planar), the problem is PSPACE-complete, while on those whose maximum degree is two (i.e., paths and cycles), the problem can be solved in polynomial time. Additionally, we also design polynomial-time algorithms for K-PVCR on trees under each of TJ and TAR. Moreover, on paths, cycles, and trees, we describe how one can construct a reconfiguration sequence between two given k-path vertex covers in a yes-instance. In particular, on paths, our constructed reconfiguration sequence is shortest.

Binary sequences with high linear complexity and high 2-adic complexity have important applications in communication and cryptography. In this paper, the 2-adic complexity of a class of balanced Whiteman generalized cyclotomic sequences which have high linear complexity is considered. Through calculating the determinant of the circulant matrix constructed by one of these sequences, the result shows that the 2-adic complexity of this class of sequences is large enough to resist the attack of the rational approximation algorithm (RAA) for feedback with carry shift registers (FCSRs).

We study the computational complexity of the puzzle game Critter Crunch, where the player has to rearrange Critters on a board in order to eliminate them all. Smaller Critters can be fed to larger Critters, and Critters will explode if they eat too much. Critters come in several different types, sizes, and colors. We prove the NP-hardness of levels that contain Blocker Critters, as well as levels where the player must clear the board in a given number of moves (i.e., “puzzle mode”). We also characterize the complexity of the game, as a function of the number of columns on the board, in two settings: (i) the setting where Critters may have several different colors, but only two possible sizes, and (ii) the setting where Critters come in all three sizes, but with no color variations. In both settings, the game is NP-hard for levels with exactly two columns, and solvable in linear time for levels with only one column or more than two columns.

In this paper, we propose a novel user selection scheme based on jointly combining channel gain (CG) and signal to interference plus noise ratio (SINR) to improve the sum-rate as well as to reduce the computation complexity of multi-user massive multi-input multi-output (MU-massive MIMO) downlink transmission through a block diagonalization (BD) precoding technique. By jointly considering CG and SINR based user sets, sum-rate performance improvement can be achieved by selecting higher gain users with better SINR conditions as well as by eliminating the users who cause low sum-rate in the system. Through this approach, the number of possible outcomes for the user selection scheme can be reduced by counting the common users for every pair of user combinations in the selection process since the common users of CG-based and SINR-based sets possess both higher channel gains and better SINR conditions. The common users set offers not only sum-rate performance improvements but also computation complexity reduction in the proposed scheme. It is shown by means of computer simulation experiments that the proposed scheme can increase the sum-rate with lower computation complexity for various numbers of users as compared to conventional schemes requiring the same or less computational complexity.

Air traffic management (ATM) systems around the world are being modernized to accommodate shifts towards performance- and trajectory-based operations. These shifts will require new indices for safety, efficiency and complexity. The authors have been developing an index for evaluating air traffic control (ATC) difficulty that utilizes the relative positions and velocity vectors of aircraft pairs as input data. Prior to practical application of the index, it is necessary to understand the effects of input data error, i.e. errors in the positions and velocities of a pair of aircraft, on the estimated difficulty value. Two sensitivity analyses were therefore performed for a pair of aircraft cruising at constant speeds on intersecting linear tracks at the same altitude. Sensitivity analysis examines how uncertainty in inputs relates to uncertainty in outputs. Firstly, an analysis of propagation error was carried out. The formula of the propagation error at a certain point was derived based on the assumed input error, and the distribution of propagation error was investigated for all possible situations and compared with the distribution of difficulty values to clarify its characteristics. Secondly, a sensitivity analysis based on variance was carried out that evaluated the effect of each input parameter using a conditional variance value called the Sobol indices. Using a Monte Carlo method, we investigated the effect of each input parameter on the calculated difficulty value for all possible situations of aircraft pairs on intersecting trajectories. As a result, it was found that the parameter that most affects the difficulty value is the intersection angle of the trajectories.

In order to realize the higher bit rates compared for the fifth-generation (5G) mobile communication system, massive MIMO technologies in higher frequency bands with wider bandwidth are being investigated for 5G evolution and 6G. One of practical method to realize massive MIMO in the high frequency bands is hybrid beamforming (BF). With this approach, user selection is an important function because its performance is highly affected by inter-user interference. However, the computational complexity of user selection in multi-user massive MIMO is high because MIMO channel matrix size excessive. Furthermore, satisfying user fairness by proportional fairness (PF) criteria leads to further increase of the complexity because re-calculation of precoding and postcoding matrices is required for each combination of selected users. To realize a fair and low-complexity user selection algorithm for multi-user massive MIMO employing hybrid BF, this paper proposes a two-step user selection algorithm that combines PF based user selection and chordal distance user selection. Computer simulations show that the proposed two-step user selection algorithm with higher user fairness and lower computational complexity can achieve higher system performance than the conventional user selection algorithms.

A universal interconnection network implements arbitrary interconnections among n terminals. This paper considers a problem to realize such a network using contact switches. When n=2, it can be implemented with a single switch. The number of different connections among n terminals is given by the Bell number B(n). The Bell number shows the total number of methods to partition n distinct elements. For n=2, 3, 4, 5 and 6, the corresponding Bell numbers are 2, 5, 15, 52, and 203, respectively. This paper shows a method to realize an n terminal universal interconnection network with $rac {3}{8}(n^2-1)$ contact switches when n=2m+1≥5, and $rac {n}{8}(3n+2)$ contact switches, when n=2m≥6. Also, it shows that a lower bound on the number of contact switches to realize an n-terminal universal interconnection network is ⌈log 2B(n)⌉, where B(n) is the Bell number.

This letter presents an efficient technique to reduce the computational complexity involved in training binary convolutional neural networks (BCNN). The BCNN training shall be conducted focusing on the optimization of the sign of each weight element rather than the exact value itself in convention; in which, the sign of an element is not likely to be flipped anymore after it has been updated to have such a large magnitude to be clipped out. The proposed technique does not update such elements that have been clipped out and eliminates the computations involved in their optimization accordingly. The complexity reduction by the proposed technique is as high as 25.52% in training the BCNN model for the CIFAR-10 classification task, while the accuracy is maintained without severe degradation.

This paper proposes a parallel peak cancellation (PC) process for the computational complexity-efficient algorithm called PC with a channel-null constraint (PCCNC) in the adaptive peak-to-average power ratio (PAPR) reduction method using the null space in a multiple-input multiple-output (MIMO) channel for MIMO-orthogonal frequency division multiplexing (OFDM) signals. By simultaneously adding multiple PC signals to the time-domain transmission signal vector, the required number of iterations of the iterative algorithm is effectively reduced along with the PAPR. We implement a constraint in which the PC signal is transmitted only to the null space in the MIMO channel by beamforming (BF). By doing so the data streams do not experience interference from the PC signal on the receiver side. Since the fast Fourier transform (FFT) and inverse FFT (IFFT) operations at each iteration are not required unlike the previous algorithm and thanks to the newly introduced parallel processing approach, the enhanced PCCNC algorithm reduces the required total computational complexity and number of iterations compared to the previous algorithms while achieving the same throughput-vs.-PAPR performance.

Cross-component linear model (CCLM) chromaticity prediction is a new technique introduced in Versatile Video Coding (VVC), which utilizes the reconstructed luminance component to predict the chromaticity parts, and can improve the coding performance. However, it increases the coding complexity. In this paper, how to accelerate the chroma intra-prediction process is studied based on texture characteristics. Firstly, two observations have been found through experimental statistics for the process. One is that the choice of the chroma intra-prediction candidate modes is closely related to the texture complexity of the coding unit (CU), and the other is that whether the direct mode (DM) is selected is closely related to the texture similarity between current chromaticity CU and the corresponding luminance CU. Secondly, a fast chroma intra-prediction mode decision algorithm is proposed based on these observations. A modified metric named sum modulus difference (SMD) is introduced to measure the texture complexity of CU and guide the filtering of the irrelevant candidate modes. Meanwhile, the structural similarity index measurement (SSIM) is adopted to help judging the selection of the DM mode. The experimental results show that compared with the reference model VTM8.0, the proposed algorithm can reduce the coding time by 12.92% on average, and increases the BD-rate of Y, U, and V components by only 0.05%, 0.32%, and 0.29% respectively.