Search

Let n be a positive integer. An NFSR of n stages is called irreducible if the family of output sequences of any NFSR of stages less than n is not included in that of the NFSR. In this paper, we prove that the density of the irreducible NFSRs of n stages is larger than 0.39. This implies that it is expected to find an irreducible NFSR of n stages among three randomly chosen NFSRs of n stages. [ABSTRACT FROM PUBLISHER]

In this paper, the sequence families of which maximum correlation is determined by the Weil bound of exponential sums are revisited. Using the same approach, two new constructions with large family sizes and low maximum correlation are given. The first construction is an analog of one recent result derived from the interleaved structure of Sidel'nikov sequences. For a prime p and an integer M\vert (p-1), the new M-ary sequence families of period p are obtained from irreducible quadratic polynomials and known power residue-based sequence families. The new sequence families increase family sizes of the known power residue-based sequence families, but keep the maximum correlation unchanged. In the second construction, the sequences derived from the Weil representation are generalized, where each new sequence is the elementwise product of a modulated Sidel'nikov sequence and a modulated trace sequence. For positive integers d

This paper studies the distinctness of primitive sequences over \bf Z/(M) modulo 2, where M is an odd integer that is composite and square-free, and \bf Z/(M) is the integer residue ring modulo M. A new sufficient condition is given for ensuring that primitive sequences generated by a primitive polynomial f\left(x\right) over \bf Z/(M) are pairwise distinct modulo 2. Such result improves a recent result obtained in our previous paper, and consequently, the set of primitive sequences over \bf Z/(M) that can be proven to be distinct modulo 2 is greatly enlarged. [ABSTRACT FROM PUBLISHER]

This paper is concerned with an important matrix condition in compressed sensing known as the restricted isometry property (RIP). We demonstrate that testing whether a matrix satisfies RIP is \ssr NP-hard. As a consequence of our result, it is impossible to efficiently test for RIP provided \ssr P\ne\ssr NP. [ABSTRACT FROM PUBLISHER]

Chemical mechanical polishing/planarization (CMP) combines physical grinding and chemical reactions to planarize the wafer surface. The complex mechanism of CMP brings great challenges to the mechanism-based modeling process. The data-driven CMP modeling process is limited by insufficient datasets. At the same time, these two types of models generally have high computational complexity. In this paper, we introduce the group method of data handling (GMDH)-type polynomial network to build the CMP model to address the above challenges. We designed and manufactured the test chip using a 28nm process. The measurement data from the test chip shows that compared with the mechanism-based CMP model, the trained CMP model based on GMDH-type polynomial network has higher accuracy and lower computational complexity, with the average simulation speed being 115x faster. Experiments based on silicon data show that this modeling method has a small demand for data, and 20 randomly selected sets of data can meet the needs for modeling the current CMP process. [ABSTRACT FROM AUTHOR]

List decoding of insertions and deletions in the Levenshtein metric is considered. The Levenshtein distance between two sequences is the minimum number of insertions and deletions needed to turn one of the sequences into the other. In this paper, a Johnson-like upper bound on the maximum list size when list decoding in the Levenshtein metric is derived. This bound depends only on the length and minimum Levenshtein distance of the code, the length of the received word, and the alphabet size. It shows that polynomial-time list decoding beyond half the Levenshtein distance is possible for many parameters. Further, we also prove a lower bound on list decoding of deletions with the well-known binary Varshamov–Tenengolts codes, which shows that the maximum list size grows exponentially with the number of deletions. Finally, an efficient list decoding algorithm for two insertions/deletions with VT codes is given. This decoder can be modified to a polynomial-time list decoder of any constant number of insertions/deletions. [ABSTRACT FROM AUTHOR]

In this article we present our results from the SC19 Student Cluster Competition Reproducibility Challenge. The challenge entails reproducing the article entitled “Computing Planetary Interior Normal Modes with A Highly Parallel Polynomial Filtering Eigensolver” presented at SC’18, which proposes a parallel polynomial filtered Lanczos algorithm to directly calculate the planetary normal modes of heterogeneous planets. The proposed algorithm showed excellent performance with relatively low memory consumption and high parallel efficiency. In this work, we reproduce the scaling tests in that article on a cluster using Intel Cascade Lake architecture and use the proposed algorithm to illustrate specific normal modes of Mars. We compare the results obtained on our cluster with those in the original article. We also design a new metric to better analyze the results. In addition, we use the profiling tool Intel VTune Amplifier to explain our discoveries. Our results demonstrate that the given models show great scalability, which is similar to the original article. The required normal modes of Mars are also successfully calculated and visualized. [ABSTRACT FROM AUTHOR]

Constacyclic codes are well-known generalizations of cyclic and negacyclic codes. Due to their rich algebraic structure, constacyclic codes are used to construct quantum codes and symbol-pair codes. Let ${\mathbb {F}}_{q}$ be a finite field with order $q$ , where $q$ is a positive power of a prime $p$. Suppose that $n$ is a positive integer and the product of distinct prime factors of $n$ divides $q-1$ , i.e., $rad(n)\mid (q-1)$. In this paper, we explicitly factorize the polynomial $x^{n}-\lambda $ for each $\lambda \in {\mathbb {F}}_{q}^{*}$. As applications, first, we obtain all repeated-root $\lambda $ -constacyclic codes and their dual codes of length $np^{s}$ over ${\mathbb {F}}_{q}$ ; second, we determine all simple-root LCD cyclic codes and LCD negacyclic codes of length $n$ over ${\mathbb {F}}_{q}$ ; third, we list all self-dual repeated-root negacyclic codes of length $np^{s}$ over ${\mathbb {F}}_{q}$. In contrast to known results, the lengths of constacyclic codes in this paper have more flexible parameters. [ABSTRACT FROM AUTHOR]

Due to the practical and theoretical importance, failure prediction of discrete-event systems (DESs) has received increasing attention recently. In this paper, the predictability of failure events in decentralized DESs is investigated. The main contributions are as follows. First, the notion of copredictability of DESs is formalized under the decentralized framework to capture the feature that the occurrences of failure events can be predicted based on at least one local observation. It is deducted that the copredictability is weaker than the predictability but stronger than the codiagnosability. Second, in order to achieve the performance of prediction, a nondeterministic automaton called coverifier is constructed from the given system. Third, the necessary and sufficient condition for verifying the copredictability of DESs based on the coverifier is presented, which generalizes the main results by Genc and Lafortune from the centralized systems to the decentralized setting. It is worth noting that both constructing the coverifier and verifying the copredictability can be realized with polynomial complexity in the number of states and events of the system. Note to Practitioners—The research in this paper is motivated by the following practical problem. Before failure events occur in a manufacturing system, can engineers predict the occurrences based on the observation record of the system? This paper aims to investigate the predictability issue of discrete-event systems under a decentralized framework by introducing the notion of copredictability. In order to verify the copredictability of systems, an approach is proposed by constructing the coverifier. In particular, the verification is polynomial-time. [ABSTRACT FROM AUTHOR]

For a function $f$ from $\mathbb {F}_{2}^{n}$ to $\mathbb {F}_{2}^{n}$ , the planarity of $f$ is usually measured by its differential uniformity and differential spectrum. In this paper, we propose the concept of vanishing flats, which supplies a combinatorial viewpoint on the planarity. First, the number of vanishing flats of $f$ can be regarded as a measure of the distance between $f$ and the set of almost perfect nonlinear functions. In some cases, the number of vanishing flats serves as an “intermediate” concept between differential uniformity and differential spectrum, which contains more information than differential uniformity, however less than the differential spectrum. Secondly, the set of vanishing flats forms a combinatorial configuration called partial quadruple system, since it conveys a detailed structural information about $f$. We initiate this study by considering the number of vanishing flats and the partial quadruple systems associated with monomials and Dembowski-Ostrom polynomials. In addition, we present an application of vanishing flats to the partition of a vector space into disjoint equidimensional affine spaces. We conclude the paper with several further questions and challenges. [ABSTRACT FROM AUTHOR]

This paper addresses the issue of placing a simple polygon (upon translation and rotation) on an isometric triangular grid such that the polygon contains the maximum number of triangles in its closure. This solves the problem left open in two recent papers titled “On the problem of the automated design of large-scale robot skin” and “An improved algorithm for the automated design of large scale robot skin” published in the IEEE Transactions on Automation Science and Engineering . Based on the properties of the grid, an improved algorithm is also presented. We also present some experimental results describing the use of this algorithm. [ABSTRACT FROM AUTHOR]

The hardness of fitness functions is an important research topic in the field of evolutionary computation. In theory, this paper can help with understanding the ability of evolutionary algorithms (EAs). In practice, this paper may provide a guideline to the design of benchmarks. The aim of this paper is to answer the following research questions. Given a fitness function class, which functions are the easiest with respect to an EA? Which are the hardest? How are these functions constructed? This paper provides theoretical answers to these questions. The easiest and hardest fitness functions are constructed for an elitist (1 + 1) EA to maximize a class of fitness functions with the same optima. It is demonstrated that the unimodal functions are the easiest and deceptive functions are the hardest in terms of the time-based fitness landscape. This paper also reveals that in a fitness function class, the easiest function to one algorithm may become the hardest to another algorithm, and vice versa. [ABSTRACT FROM AUTHOR]

The main contribution of this paper is to present a recursive estimation/detection technique for reduced-order state-space systems. The recursive state and parameter estimator is built on the framework of polynomial chaos theory and maximum likelihood estimation. The estimator quantifies the reliability of its estimate in real-time by recursively calculating a signal-to-noise ratio. The signal-to-noise ratio (SNR) indicates how well the output of the reduced-order estimation model matches the actual system output. A detection algorithm makes decisions to trust or distrust the current estimate by comparing the current value of the SNR ratio against a threshold value. This paper applies the proposed techniques to estimate the sprung mass of an actual vehicle. It uses a reduced-order model to approximate the complex ride dynamics of the vehicle. Despite the modeling approximations and simplifications, the proposed technique is able to reliably estimate the sprung mass of the vehicle to within 10% of the true value. [ABSTRACT FROM AUTHOR]

This paper focuses on the complexity of the (weak) soundness problem of acyclic workflow (WF) nets, and two main results are established: 1) soundness of 1-bounded acyclic WF nets is co-NP-complete and 2) weak soundness of 3-bounded acyclic asymmetric-choice WF nets is co-NP-complete. [ABSTRACT FROM AUTHOR]

Matrix multiplication is a fundamental building block in various distributed computing algorithms. In order to multiply large matrices, it is common practice to distribute the computation into multiple tasks running on different nodes. In order to tolerate stragglers among such nodes, various coding schemes have been proposed by adding additional coded tasks. However, most existing coding schemes for matrix multiplication are constructed for only one matrix multiplication, while batch matrix multiplication is common in large-scale distributed computing workloads. In this paper, we propose Rook Coding (RC), a novel polynomial-based coding framework for computing the multiplication of $n$ pairs of matrices in batch. Designed to achieve lower encoding time in practice, we construct RC as polynomials of much simpler forms than existing coding schemes for batch matrix multiplication, achieving a recovery threshold of $O(n^{\log _{2} ~3})$. Compared to existing coding schemes, RC achieves a lower encoding complexity in practice, because of its simpler forms in the encoding polynomials. Through extensive experiments, we show that RC can save the time of the whole job thanks to its low overhead of encoding. [ABSTRACT FROM AUTHOR]

This article addresses polynomial computation with unipolar stochastic logic by exploiting correlation between the bit-streams. The AND-OR, double-NAND, OR-AND and double-NOR circuits are presented for polynomials with all positive coefficients whose sum is less than or equal to one by mathematically analyzing the joint probability distribution of coefficient bit-streams. The NAND-AND expansion is also developed for polynomials with alternatively positive and negative coefficients whose absolute values are decreasing by applying the same idea. Unlike the original methods with multiple uncorrelated random number sources (RNSs) for coefficient bit-stream generation, the presented methods only require a single RNS. Since the RNSs take up huge hardware resource in stochastic circuits, the proposed RNS-sharing techniques for polynomial computation result in a significant reduction of hardware complexity. For the factorization technique in the general polynomials, this paper enhances the original stochastic designs for the second-order polynomial and further presents the simple correlation-dependent circuits. Results show that the proposed architectures are superior to the previous ones by reducing the total number of RNSs. [ABSTRACT FROM AUTHOR]

This paper introduces a node-asynchronous communication protocol in which an agent in a network wakes up randomly and independently, collects states of its neighbors, updates its own state, and then broadcasts back to its neighbors. This protocol differs from consensus algorithms and it allows distributed computation of an arbitrary eigenvector of the network, in which communication between agents is allowed to be directed. (The graph operator is still required to be a normal matrix). To analyze the scheme, this paper studies a random asynchronous variant of the power iteration. Under this random asynchronous model, an initial signal is proven to converge to an eigenvector of eigenvalue 1 (a fixed point) even in the case of operator having spectral radius larger than unity. The rate of convergence is shown to depend not only on the eigenvalue gap but also on the eigenspace geometry of the operator as well as the amount of asynchronicity of the updates. In particular, the convergence region for the eigenvalues gets larger as the updates get less synchronous. Random asynchronous updates are also interpreted from the graph signal perspective, and it is shown that a non-smooth signal converges to the smoothest signal under the random model. When the eigenvalues are real, second order polynomials are used to achieve convergence to an arbitrary eigenvector of the operator. Using second order polynomials the paper formalizes the node-asynchronous communication model. As an application, the protocol is used to compute the Fiedler vector of a network to achieve autonomous clustering. [ABSTRACT FROM AUTHOR]

Partial MDS (PMDS) codes are a class of erasure-correcting array codes that combine local correction of the rows with global correction of the array. An $\boldsymbol {m}\times \boldsymbol {n}$ array code is called an $(\boldsymbol {r};\boldsymbol {s})$ PMDS code if each row belongs to an ${[}\boldsymbol {n},\boldsymbol {n}-\boldsymbol {r}, \boldsymbol {r}+\textbf {1}{]}$ MDS code and the code can correct erasure patterns consisting of $\boldsymbol {r}$ erasures in each row together with $\boldsymbol {s}$ more erasures anywhere in the array. While a recent construction by Calis and Koyluoglu generates $(\boldsymbol {r};\boldsymbol {s})$ PMDS codes for all $\boldsymbol {r}$ and $\boldsymbol {s}$ , its field size is exponentially large. In this paper, a family of PMDS codes with field size ${\mathcal{ O}}\left ({\max \{\boldsymbol {m},\boldsymbol {n}^{\boldsymbol {r}+\boldsymbol {s}}\}^{\boldsymbol {s}} }\right)$ is presented for the case where $\boldsymbol {r}= {\mathcal{ O}}(1), \boldsymbol {s}= {\mathcal{ O}}(1)$. [ABSTRACT FROM AUTHOR]

The hull of a linear code is defined to be the intersection of the code and its dual, and was originally introduced to classify finite projective planes. The hull plays an important role in determining the complexity of algorithms for checking permutation equivalence of two linear codes and computing the automorphism group of a linear code. It has been shown that these algorithms are very effective in general if the size of the hull is small. The objective of this paper is to present some sufficient and necessary conditions that linear codes and cyclic codes have one-dimensional hull. It is shown that there are no such binary or ternary cyclic codes. Based on these characterizations, some constructions of linear codes with one-dimensional hull were given by employing quadratic number fields, partial difference sets, and difference sets. We also construct cyclic codes with one-dimensional hull. Some optimal codes with one-dimensional hull are obtained. [ABSTRACT FROM AUTHOR]

Linear codes with certain special properties have received renewed attention in recent years due to their practical applications. Among them, binary linear complementary dual (LCD) codes play an important role in implementations against side-channel attacks and fault injection attacks. Self-orthogonal codes can be used to construct quantum codes. In this paper, four classes of binary linear codes are constructed via a generic construction which has been intensively investigated in the past decade. Simple characterizations of these linear codes to be LCD or self-orthogonal are presented. Resultantly, infinite families of binary LCD codes and self-orthogonal codes are obtained. Infinite families of binary LCD codes from the duals of these four classes of linear codes are produced. Many LCD codes and self-orthogonal codes obtained in this paper are optimal or almost optimal in the sense that they meet certain bounds on general linear codes. In addition, the weight distributions of two sub-families of the proposed linear codes are established in terms of Krawtchouk polynomials. [ABSTRACT FROM AUTHOR]

The linear model, in which a set of observations is assumed to be given by a linear combination of columns of a matrix (often termed a dictionary), has long been the mainstay of the statistics and signal processing literature. One particular challenge for inference under linear models is understanding the conditions on the dictionary under which reliable inference is possible. This challenge has attracted renewed attention in recent years, since many modern inference problems (e.g., high-dimensional statistics and compressed sensing) deal with the underdetermined setting, in which the number of observations is much smaller than the number of columns in the dictionary. This paper makes several contributions for this setting when the set of observations is given by a linear combination of a small number of groups of columns of the dictionary, termed the block-sparse case. First, it specifies conditions on the dictionary under which most block submatrices of the dictionary (often termed block subdictionaries) are well conditioned. This result is fundamentally different from prior work on block-sparse inference because: 1) it provides conditions that can be explicitly computed in polynomial time; 2) the given conditions translate into near-optimal scaling of the number of columns of the block subdictionaries as a function of the number of observations for a large class of dictionaries; and 3) it suggests that the spectral norm, rather than the column/block coherences of the dictionary, fundamentally limits the scaling of dimensions of the well-conditioned block subdictionaries. Second, in order to help understand the significance of this result in the context of block-sparse inference, this paper investigates the problems of block-sparse recovery and block-sparse regression in underdetermined settings. In both of these problems, this paper utilizes its result concerning conditioning of block subdictionaries and establishes that near-optimal block-sparse recovery and block-sparse regression is possible for a large class of dictionaries as long as the dictionary satisfies easily computable conditions and the coefficients describing the linear combination of groups of columns can be modeled through a mild statistical prior. Third, the paper reports extensive numerical experiments that highlight the effects of different measures of the dictionary in block-sparse inference problems. [ABSTRACT FROM PUBLISHER]

The parameters estimation of cubic-phase signal based on local polynomial Wigner distribution (LPWD) was proposed in the author’s previous paper, and it outperforms the traditional algorithms in inverse synthetic aperture radar (ISAR) imaging of maneuvering target. The contribution of this paper is that the asymptotic statistical performance of LPWD for the parameters estimation of cubic-phase signal is analyzed theoretically, and the asymptotic statistical results are derived for all the estimated parameters via the first-order perturbation principle. Then, the LPWD is used in ISAR imaging of ship target with complex motion, and the high-quality instantaneous ISAR images can be obtained. [ABSTRACT FROM PUBLISHER]

Nonlinear estimation problems, such as range-only and bearing-only target tracking, are often addressed using linearized estimators, e.g., the extended Kalman filter (EKF). These estimators generally suffer from linearization errors as well as the inability to track multimodal probability density functions. In this paper, we propose a bank of batch maximum a posteriori (MAP) estimators as a general estimation framework that provides relinearization of the entire state trajectory, multihypothesis tracking, and an efficient hypothesis generation scheme. Each estimator in the bank is initialized using a locally optimal state estimate for the current time step. Every time a new measurement becomes available, we relax the original batch-MAP problem and solve it incrementally. More specifically, we convert the relaxed one-step-ahead cost function into polynomial or rational form and compute all the local minima analytically. These local minima generate highly probable hypotheses for the target's trajectory and hence greatly improve the quality of the overall MAP estimate. Additionally, pruning of least probable hypotheses and marginalization of old states are employed to control the computational cost. Monte Carlo simulation and real-world experimental results show that the proposed approach significantly outperforms the standard EKF, the batch-MAP estimator, and the particle filter. [ABSTRACT FROM PUBLISHER]

In this paper, the response surface method (RSM) is exploited in the cooling system design optimization of oil-immersed transformers. To generate the training data for RSM, a 3-D computational fluid dynamic model for the transformer under study is constructed and solved, followed by verification on the solutions. Based on the simulation data, two types of RSMs, i.e., the second-order polynomial method and the Kriging method, are employed to evaluate their performance for this specific problem. The response surface with the best performance is used in the optimization process. The solution is compared with that found by the direct optimization method to showcase the effectiveness of applying RSM to oil-immersed transformer cooling system design. Details of implementation of the studied transformer are also presented. [ABSTRACT FROM AUTHOR]

This paper presents an effective approach to variability analysis of integrated capacitors due to manufacturing process uncertainty. The proposed approach combines the generalized polynomial chaos method for uncertainty quantification with the efficient floating random walk algorithm for capacitance extraction. For applications where detailed statistical descriptions are required, the method allows achieving a $1000 {\times }$ acceleration compared to standard Monte Carlo analysis. Application to variability analysis in digital to analog converters is illustrated. [ABSTRACT FROM AUTHOR]

In this paper, we present a method to implement digital predistortion (DPD) memory models using lookup tables (LUTs) with linear interpolation and extrapolation. We introduce the required set of basis functions to describe this model. The DPD output is expressed as a linear combination of these basis functions and we show how to directly estimate the LUT entries using least squares. We show how this model achieves lower complexity at similar or better performance compared to polynomial models translated to LUTs with interpolation or models based on LUTs without interpolation whose coefficients are adapted directly. We refer to this model as the direct adaptation of LUTs with interpolation/extrapolation (DLUTI). In this paper we also introduce the composite memory polynomial model: a new polynomial model which is a hybrid between the generalized memory polynomial and the dynamic deviation reduction models. This model is used as a starting point to generate the final LUT-based model. [ABSTRACT FROM PUBLISHER]

Compact representation of signals and images is a key for many applications. Compactness is often achieved through linear transforms with good energy concentration property. We present an adaptive wavelet filter bank with fixed number of vanishing moments, plus additional local adaptation. Proposed adaptation method is conducted at each sample according to the least absolute deviation (LAD) criterion. Fixed vanishing moments provide for polynomial annihilation. Adaptation is aimed to achieve maximum sparseness for a wider class of signals, such as sine waves. LAD criterion results in more accurate adaptation on sudden changes of signal statistics. In this paper, an efficient LAD realization is proposed, in spite of nonexistence of the closed form solution. Combining least squares and LAD criterion, we have achieved unbiased adaptation, robust to noise. Due to its simplicity and acceptable computational speed, the proposed scheme is a good candidate for the real-world applications. In this paper, advantages of the proposed scheme are shown in signal denoising and reconstruction. [ABSTRACT FROM AUTHOR]

This paper proposes a generator polynomial model-based eye diagram estimation method for the error-correction codes (ECCs), which are the Bose–Chaudhuri–Hocquenghem (BCH) code and the Reed–Solomon (RS) code. The ECCs compensate for the channel loss at the bit level, so most of the systems include the ECC block. The BCH and RS codes are the generator polynomial-based ECCs; this paper proposes the generator polynomial model-based method. The model provides the accurate probability density function of the code words for the BCH and RS code. Thus, the proposed method is capable of achieving the signal integrity analysis for the system level. For verification, we design the BCH and RS encoders. The estimated eye diagrams are nearly the same as that of the transient simulation for the BCH and RS codes. Furthermore, the voltage bathtub curves are the same up to 10−8. For a smaller bit-error rate value, the proposed method only provides the bathtub curve. This paper successfully verifies the eye diagram estimation method for the BCH and RS codes. [ABSTRACT FROM AUTHOR]

This paper deals with the modeling and simulation of the effect of rotor eccentricity in permanent magnet synchronous machines. Static eccentricity is analyzed in a 2-D setting. The 3-D effect of an inclined rotor shaft is accounted by considering 2-D slices and interpolating on a grid constructed from finite-element simulations [response surface model (RSM)]. Common tools of uncertainty quantification, i.e., generalized polynomial chaos and Monte Carlo, are used to study the effect on the electromotive force. The novelty of this paper is the twofold use of the RSM: 1) to speed up the calculations in the 2-D setting and 2) to mimic a multislice model for inclined eccentricity. [ABSTRACT FROM AUTHOR]

Multivariate nonparametric frequency response estimation is important in engineering. It allows one to get a quick insight into the dynamics of the system from input–output measurements. Sometimes, measurements can be missing due to faulty sensors or communication links. In this paper, we develop a method that estimates the frequency response matrix together with the missing samples from partially known data. In addition, the method can estimate the level of nonlinear (NL) contribution and the additive noise level of weakly NL systems when excited by a periodic excitation. Several special cases can be handled if the reference input is known, like samples missing at the inputs, noisy inputs, and identification in feedback. [ABSTRACT FROM PUBLISHER]

Frequency response matrix (FRM) estimation is an important preprocessing step in system identification. This nonparametric step can give a quick insight into the behavior of a dynamic system without making too many assumptions. Sensor failures or faulty communication links make the measurement data go missing. In this paper, a nonparametric method is developed that identifies a multiple-input-multiple-output system from data with missing samples at the noisy outputs. Here, the systems are considered to be excited by arbitrary (random) inputs. The proposed method gives an accurate FRM estimate with its uncertainty and an estimate of the output noise covariance. In addition, the method gives an estimate of the missing time-domain samples and their uncertainties. If the reference signal is known, the proposed method can also handle partially missing data in one or a combination of the following cases: 1) in both inputs and the outputs; 2) in an errors-in-variables framework; and 3) in the presence of a feedback loop. [ABSTRACT FROM PUBLISHER]

This paper investigates the problem of H\infty filtering for polynomial-fuzzy-model-based discrete-time networked systems under an event-triggered scheme. A polynomial fuzzy filter is designed to estimate the control output. In order to reduce the data size transmitted in a network, signal quantization is managed via a logarithmic quantizer. A novel method is designed to guarantee a filtering error system to be asymptotically stable and to satisfy the desired performance. Furthermore, sufficient conditions developed via the method are represented as a sum of squares, which can be solved by SOSTOOLS. A simulation example is provided to demonstrate the effectiveness of the proposed results. [ABSTRACT FROM PUBLISHER]

In this paper, we study the number of different interference alignment (IA) solutions in a $K$ -user multiple-input multiple-output (MIMO) interference channel, when the alignment is performed via beamforming and no symbol extensions are allowed. We focus on the case where the number of IA equations matches the number of variables. In this situation, the number of IA solutions is finite and constant for any channel realization out of a zero-measure set and, as we prove in this paper, it is given by an integral formula that can be numerically approximated using Monte Carlo integration methods. More precisely, the number of alignment solutions is the scaled average of the determinant of a certain Hermitian matrix related to the geometry of the problem. Interestingly, while the value of this determinant at an arbitrary point can be used to check the feasibility of the IA problem, its average (properly scaled) gives the number of solutions. For single-beam systems, the asymptotic growth rate of the number of solutions is analyzed and some connections with classical combinatorial problems are presented. Nonetheless, our results can be applied to arbitrary interference MIMO networks, with any number of users, antennas, and streams per user. [ABSTRACT FROM PUBLISHER]

This paper proposes a novel scheme for the design of topology-transparent scheduling (TTS) in mobile ad hoc networks (MANETs), based on the Chinese remainder theorem (CRT). TTS can provide each node with guaranteed success in each schedule without any detailed topology information and yields a guaranteed upper bound on the transmission delay of each packet at every node in a MANET. In general, TTS requires two global constraints on the number of nodes in the MANET and the maximum nodal degree of the graph representing connectivity of the MANET. Due to the inherent mobility of MANETs, the maximum nodal degree, however, cannot be available or easily estimated. To eliminate the requirement for the maximum nodal degree, this paper proposes TTS via the CRT. By the redundancy property of the Chinese remainder representation, the proposed CRT-based scheme not only preserves the advantages of providing guaranteed success in each schedule with only the global constraint on the number of nodes in the MANET, but also offers flexibility in constructing TTS. To have a better transmission delay bound for a node with lower interference, this paper also introduces two threaded counterparts of the proposed CRT-based scheme. This paper provides performance analyses for the proposed CRT-based scheme and its threaded counterparts. Numerical results demonstrate that TTS via the CRT can outperform existing schemes, especially in scenarios with harsh interference, and is a versatile approach for the design of TTS. [ABSTRACT FROM AUTHOR]

Because of their efficient encoding and decoding algorithms, cyclic codes—an interesting class of linear codes—are widely used in communication systems, storage devices, and consumer electronics. BCH codes form a special class of cyclic codes, and are usually among the best cyclic codes. A subclass of good BCH codes is the narrow-sense primitive BCH codes. However, the dimension and minimum distance of these codes are not known in general. The main objective of this paper is to study the dimension and minimum distances of a subclass of the narrow-sense primitive BCH codes with design distance \delta =(q-\ell 0)q^{m-\ell 1-1}-1 for certain pairs (\ell 0, \ell 1) , where 0 \leq \ell 0 \leq q-2 and 0 \leq \ell 1 \leq m-1 . The parameters of other related classes of BCH codes are also investigated, and some open problems are proposed in this paper. [ABSTRACT FROM PUBLISHER]

In this paper, time-invariant spatially coupled low-density parity-check convolutional codes (SC-LDPC-CCs) are considered, and the connections existing between their low-weight codewords and cycles in their Tanner graphs are studied. Using the polynomial representation of these codes, we show that parity-check matrices having columns with weight ≥2 can be analyzed considering a certain number of parity-check sub-matrices having regular columns with weight 2. These sub-matrices are associated to cycles in the code Tanner graph and define as many codes we denote as component codes. Based on this observation, we find that codewords of the main code can be expressed as combinations of codewords of the component codes. The design of codes free of codewords up to a certain weight is also addressed. We show that low-weight codewords in the main code can be avoided by removing some types of cycles in its Tanner graph. Our design approach is applied to some well-known ensembles of SC-LDPC-CCs to prove its effectiveness. [ABSTRACT FROM AUTHOR]

Electrical parameter estimation of the soil is an essential step for the design of grounding systems, and is based on optimization techniques that minimize the error between a theoretical function and the field measurements. The determining factor for reaching the most adequate solution depends on a method for solving the indefinite integral of the theoretical function, as well as the accuracy and performance of the parameter estimation. This paper presents a precise and tested technique for achieving these goals known as Chebyshev polynomials. This paper also introduces an error calculation procedure for the truncation of the Chebyshev series. Besides this, this paper points toward an optimization algorithm for estimating soil parameters by use of measurements associated with differential evolution. The effectiveness of this approach has been proven by applying cases extracted from the literature. [ABSTRACT FROM AUTHOR]

This paper proposes a new approach based on the unknown input method to synthesize the observer for polynomial Takagi–Sugeno fuzzy system with uncertainties. In this paper, the upper bounds of uncertainties are not given and the effect of uncertainties is eliminated without designing an extra controller. With the aids of the noncommon Lyapunov theory and Matlab's tools of the sum-of-square, a new observer is synthesized in which the observer form is completely different from the traditional observer forms reported in previous papers. The conditions for the observer synthesis are much relaxed and the complexity of the design process is reduced. Finally, two illustrative examples are presented to demonstrate the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

In this paper, we show that the maximum number of bent component functions of a vectorial function F:GF(2)^n\to GF(2)^n is 2^n-2^n/2 . We also show that it is very easy to construct such functions. However, it is a much more challenging task to find such functions in polynomial form F\in GF(2^n)[x] , where F has only a few terms. The only known power functions having such a large number of bent components are x^{d} , where d=2^{n/2}+1 . In this paper, we show that the binomials F^i(x)=x^2^i(x+x^2^n/2) also have such a large number of bent components, and these binomials are inequivalent to the monomials x^2^n/2+1 if 0

In range analysis (RA), suitable integer bit-widths are assigned to the variables so that no overflow occurs. Although the accuracy in RA rather than error analysis has more impact on hardware cost and efficiency, there are few works that offer new approaches to improve RA. Arithmetic functions, mostly represented by polynomials, are normally suitable for both optimization and verification purposes. In this paper, a safe and more accurate RA of feed-forward fixed-point polynomial data-flow graphs is proposed. The method employs particular features of RA and maps it to a specific class of polynomial optimization problems. The proposed method provides tighter ranges while taking less runtime in comparison with satisfiability-modulo theory-based method. Furthermore, the improved ranges lead to enhance the area and delay efficiency more than 50% and 24%, respectively, when the circuits are implementing the functions in comparison with the state-of-the-art techniques. [ABSTRACT FROM PUBLISHER]

Existing sparse array (SA) geometries, such as coprime and nested arrays, can be regarded as a concatenation of two uniform linear arrays (ULAs). Such arrays lead to a significant increase in the number of degrees of freedom (DOF) when the second-order information is utilized, i.e., they provide long virtual difference coarrays (DCAs). Thus, the idea of this paper is based on the observation that SAs can be fitted through the concatenations of sub-ULAs. A corresponding SA design principle, called ULA fitting, is then proposed. It aims to design SAs from multiple sub-ULAs. Towards this goal, a polynomial model for arrays is used, and based on it, a DCA structure is analyzed for the general case when an SA is composed of an arbitrary number of sub-ULAs. ULA fitting enables to transfer SA design requirements, such as hole–free, low mutual coupling, and other requirements, into pseudo-polynomial equation, and hence, find particular solutions. We mainly focus on designing SAs with low mutual coupling and large uniform DOF. Two examples of SAs with closed-form expressions are then developed based on ULA fitting. Numerical experiments verify the superiority of the proposed SAs in the presence of heavy mutual coupling. [ABSTRACT FROM AUTHOR]

A low-cost very large scale integration (VLSI) implementation of real-time correction of barrel distortion for video-endoscopic images is presented in this paper. The correcting mathematical model is based on least-squares estimation. To decrease the computing complexity, we use an odd-order polynomial to approximate the back-mapping expansion polynomial. By algebraic transformation, the approximated polynomial becomes a monomial form which can be solved by Hornor's algorithm. With the iterative characteristic of Hornor's algorithm, the hardware cost and memory requirement can be conserved by time multiplexed design. In addition, a simplified architecture of the linear interpolation is used to reduce more computing resource and silicon area. The VLSI architecture of this paper contains 13.9-K gates by using a 0.18 \mum CMOS process. Compared with some existing distortion correction techniques, this paper reduces at least 69% hardware cost and 75% memory requirement. [ABSTRACT FROM AUTHOR]

This paper analyzes complexities of decision diagrams for elementary functions such as polynomial, trigonometric, logarithmic, square root, and reciprocal functions. These real functions are converted into integer-valued functions by using fixed-point representation. This paper presents the numbers of nodes in decision diagrams representing the integer-valued functions. First, complexities of decision diagrams for polynomial functions are analyzed, since elementary functions can be approximated by polynomial functions. A theoretical analysis shows that binary moment diagrams (BMDs) have low complexity for polynomial functions. Second, this paper analyzes complexity of edge-valued binary decision diagrams (EVBDDs) for monotone functions, since many common elementary functions are monotone. It introduces a new class of integer functions, Mp-monotone increasing function, and derives an upper bound on the number of nodes in an EVBDD for the Mp-monotone increasing function. A theoretical analysis shows that EVBDDs have low complexity for Mp-monotone increasing functions. This paper also presents the exact number of nodes in the smallest EVBDD for the n-bit multiplier function, and a variable order for the smallest EVBDD. [ABSTRACT FROM AUTHOR]

This paper considers multirobot task allocation problems where the estimated costs for performing tasks are interrelated, and the overall team objective need not be a standard sum-of-costs (or utilities) model, enabling straightforward treatment of the additional costs incurred by resource contention. In the model we introduce, a team may choose one of a set of shared resources to perform a task (e.g., several routes to reach a destination), and interference is modeled when multiple robots use the same resource. We show that the general problem is NP-hard, and investigate specialized subinstances with particular cost structures. For the general problem, we describe an exact algorithm which finds an optimal assignment in a reasonable time on small instances. Aiming at larger problems, we turn two particular subinstances, introducing an two algorithms that find assignments quickly even for problems of considerable size, the first being optimal, the second being an approximation algorithm but also producing high-quality solutions with bounded suboptimality. [ABSTRACT FROM PUBLISHER]