Binary maximal-length sequences (or m-sequences) are sequences of period 2m-1 generated by a linear recursion of degree m. Decimating an m-sequence {st} by an integer d relatively prime to 2m-1 leads to another m-sequence {sdt} of the same period. The crosscorrelation of m-sequences has many applications in communication systems and has been an important and well studied problem during more than 40 years. This paper presents an updated survey on the crosscorrelation between binary m-sequences with at most five-valued crosscorrelation and shows some of the many recent connections of this problem to several areas of mathematics such as exponential sums and Dickson polynomials.

Orthogonal frequency division multiplexing (OFDM) signals have high peak-to-average power ratio (PAPR) and cause large nonlinear distortions in power amplifiers (PAs). Memory effects in PAs also become no longer ignorable for the wide bandwidth of OFDM signals. Digital baseband predistorter is a highly efficient technique to compensate the nonlinear distortions. But it usually has many parameters and takes long time to converge. This paper presents a novel predistorter design using a set of orthogonal polynomials to increase the convergence speed and the compensation quality. Because OFDM signals are approximately complex Gaussian distributed, the complex Hermite polynomials which have a closed-form expression can be used as a set of orthogonal polynomials for OFDM signals. A differential envelope model is adopted in the predistorter design to compensate nonlinear PAs with memory effects. This model is superior to other predistorter models in parameter number to calculate. We inspect the proposed predistorter performance by using an OFDM signal referred to the IEEE 802.11a WLAN standard. Simulation results show that the proposed predistorter is efficient in compensating memory PAs. It is also demonstrated that the proposal acquires a faster convergence speed and a better compensation effect than conventional predistorters.

A (k,δ,ε)-locally decodable code C:Fqn FqN is an error-correcting code that encodes =(x1,x2,...,xn) ∈ Fqn to C() ∈ FqN and has the following property: For any ∈ FqN such that d(,C()) ≤ δ N and each 1 ≤ i ≤ n, the symbol xi of can be recovered with probability at least 1-ε by a randomized decoding algorithm looking at only k coordinates of . The efficiency of a (k,δ,ε)-locally decodable code C:Fqn FqN is measured by the code length N and the number k of queries. For a k-query locally decodable code C:Fqn FqN, the code length N was conjectured to be exponential of n, i.e., N=exp(nΩ(1)), however, this was disproved. Yekhanin [In Proc. of STOC, 2007] showed that there exists a 3-query locally decodable code C:F2n F2N such that N=exp(n1/log log n) assuming that infinitely many Mersenne primes exist. For a 3-query locally decodable code C:Fqn FqN, Efremenko [ECCC Report No.69, 2008] further reduced the code length to N=exp(nO((log log n/ log n)1/2)), and in general showed that for any integer r>1, there exists a 2r-query locally decodable code C:Fqn FqN such that N=exp(nO((log log n/ log n)1-1/r)). In this paper, we will present improved constructions for query-efficient locally decodable codes by introducing a technique of "composition of locally decodable codes," and show that for any integer r>5, there exists a 9 2r-4-query locally decodable code C:Fqn FqN such that N=exp(nO((log log n/ log n)1-1/r)).

Time-variant channels degrade the performance of Orthogonal Frequency Division Multiplexing (OFDM) systems because they collapse the orthogonality between the sub-carriers, which necessitates estimating the resulting off-diagonals of the channel matrix in order to properly equalize the received signal. This letter presents a new method of estimating the channel matrix for OFDM systems in rapidly time-variant channels. The method approximates the time variation of the channel over a few successive OFDM symbols making use of Newton polynomial interpolation.

An alternative polynomial expansion for electromagnetic field estimation inside three-dimensional dielectric scatterers is presented in this article. In a continuation with the previous work of authors, the Tensor-Volume Integral Equation (TVIE) is solved by using the Galerkin-based moment method (MoM) consisting of a combination of entire-domain and sub-domain basis functions including three-dimensional polynomials. Instead of using trivial power polynomials, Legendre polynomials are adopted for electromagnetic fields expansion in this study. They have the advantage of being a set of orthogonal functions, which allows the use of high-order basis functions without introducing an ill-condition MoM matrix. The accuracy of such approach in MoM is verified by comparing its numerical results with that of exact analytical method such as Mie theory and conventional procedures in MoM. Besides, it is also confirmed that the condition number of the MoM matrix obtained with the proposed approach is lower than that of the previous approaches.

As a fundamental building block of multirate systems, the downsampler, also known as the decimator, is a periodically time-varying linear system. An eigensignal of the downsampler is defined to be an input signal which appears at the output unaltered or scaled by a non-zero coefficient. In this paper, the eigensignals are studied and characterized in the time and z domains. The time-domain characterization is carried out using number theoretic principles, while the one-sided z-transform and Lambert-form series are used for the transform-domain characterization. Examples of non-trivial eigensignals are provided. These include the special classes of multiplicative and completely multiplicative eigensignals. Moreover, the locus of poles of eigensignals with rational z transforms are identified.

An explicit expression for the impulse response coefficients of the predictive FIR digital filters is derived. The formula specifies a four-parameter family of smoothing FIR digital filters containing the Savitsky-Goaly filters, the Heinonen-Neuvo polynomial predictors, and the smoothing differentiators of arbitrary integer orders. The Hahn polynomials, which are orthogonal with respect to a discrete variable, are the main tool employed in the derivation of the formula. A recursive formula for the computation of the transfer function of the filters, which is the z-transform of a terminated sequence of polynomial ordinates, is also introduced. The formula can be used to design structures with low computational complexity for filters of any order.

We show that a problem of deciding whether a formula for a multivariate polynomial of n variables over a finite field of characteristic 2 has degree n when reduced modulo a certain Boolean ideal belongs to P. When the formula is allowed to have succinct representations as sums of monomials, the problem becomes P-complete.

Extensive studies have been made of the public key cryptosystems based on multivariate polynomials over F2. However most of the proposed public key cryptosystems based on multivariate polynomials, are proved not secure. In this paper, we propose several types of new constructions of public key cryptosystems based on randomly generated singular simultaneous equations. One of the features of the proposed cryptosystems is that the sets of random singular simultaneous equations significantly enlarges the size of the transformation.

In this paper, we propose a transmitter structure in digital QAM systems where pre-compensator compensates for nonlinearity with "memory effects" at the output amplifier. The nonlinearity is modeled as a linear time-invariant filter cascaded by memoryless nonlinearity (Wiener model), whereas the pre-compensator comprises an FIR-type adaptive filter that follows a memoryless predistorter based on a series expansion with orthogonal polynomials for digital QAM data. The predistorter and the adaptive filter of the pre-compensator are stochastically and directly adapted using the error signal. The theoretically optimum parameters of the predistorter are approximately solved whence the steady-state mean square compensation error is calculated. Simulations show that the proposed pre-compensator can be adapted to achieve a sufficiently small compensation error, restoring the original QAM constellation through linearization and equalization of the nonlinearity with memory effects.

Two operations, polynomial multiplication and modular reduction, are newly induced by the properties of the modified Booth's algorithm and irreducible all one polynomials, respectively. A new and effective methodology is hereby proposed for computing multiplication over a class of fields GF(2m) using the two operations. Then a low complexity multiplexer-based multiplier is presented based on the aforementioned methodology. Our multiplier consists of m 2-input AND gates, an (m2 + 3m - 4)/2 2-input XOR gates, and m(m - 1)/2 4 1 multiplexers. For the detailed estimation of the complexity of our multiplier, we will expand this argument into the transistor count, using a standard CMOS VLSI realization. The compared results show that our work is advantageous in terms of circuit complexity and requires less delay time compared to previously reported multipliers. Moreover, our architecture is very regular, modular and therefore, well-suited for VLSI implementation.

This paper derives a set of orthogonal polynomials for a complex random variable that is uniformly distributed in two dimensions (2D). The polynomials are used in a series expansion to approximate memoryless nonlinearities in digital QAM systems. We also study stochastic identification of nonlinearities using the orthogonal polynomials through analysis and simulations.

The uniform switching system is the family of non-linear n m binary arrays constrained such that all columns are from the constant weight k vectors and all rows have weights divisible by p > 0. For this system, we present a cardinality formula and an enumerative algorithm.

This paper analyses the performance of a joint receiving structure for DS-CDMA communications systems. To reduce undesirable performance degradation due to the multiple access interferences and the near-far problem in multipath fading channel environment, this paper exploits the receiving structure for the multiuser communication composed of a beamformer-RAKE receiver and a decorrelating multiuser detector. The proposed DS-CDMA receiving structure mitigates the performance impairment invoked from the noise enhancement and reveals less computational complexity by utilizing the multipath temporal combiner prior to accessing the decorrelating detection. Also an efficient block Toeplitz inversion technique using the matrix Levinson polynomials is introduced to further diminish the computational burden encountered from applying the decorrelating multiuser detection process as in usual. Simulation results are conducted to demonstrate the superior performance of the proposed multiuser detection structure in multipath fading CDMA channel.

For a real Schur polynomial, estimates are derived for a Schur stability margin in terms of matrix entries or tableau entries in some stability test methods. An average size of the zeros of the polynomial is also estimated. These estimates enable us to obtain more information than stability once a polynomial is tested to be stable via the established Schur stability criterion for real polynomials.

This paper deals with an orthogonal functional expansion of a non-linear stochastic functional of a stationary binary sequence taking 1 with unequal probability. Several mathematical formulas, such as multivariate orthogonal polynomials, recurrence formula and generating function, are given in explicit form. A formula of an orthogonal functional expansion for a stochastic functional is presented; the completeness of expansion is discussed in Appendix.

Minato has proposed canonical representation for polynomial functions using zero-suppressed binary decision diagrams (ZBDDs). In this paper, we extend binary moment diagrams (BMDs) proposed by Bryant and Chen to handle variables with degrees higher than l. The experimental results show that this approach is much more efficient than the previous ZBDDs' approach. The proposed approach is expected to be useful for various problems, in particular, for computer algebra.

The necessary and sufficient conditions for f (x2+x+1) and f (x2+x) to be irreducible, when f (x) is irreducible, are proved. A method that produces polynomials whose roots are linearly independent (therefore form a normal basis for a finite field) is presented.

In this paper we propose a class of byte-error-correcting codes derived from algebraic curves which is a generalization on the Reed-Solomon codes, and present their fast parallel decoding algorithm. Our algorithm can correct up to (m + b -θ)/2b byte-errors for the byte length b, where m + b -θ + 1dG for the Goppa designed distance dG. This decoding algorithm can be parallelized. In this algorithm, for our code over the finite field GF (q), the total complexity for finding byte-error locations is O (bt(t + q - 1)) with time complexity O (t(t + q - 1)) and space complexity O(b), and the total complexity for finding error values is O (bt(b + q - 1)) with time complexity O (b(b + q - 1)) and space complexity O (t), where t(m + b -θ)/2b. Our byte-error-correcting algorithm is superior to the conventional fast decoding algorithm for randomerrors in regard to the number of correcting byte-errors in several cases.

In order to realize a continuous-time system model in digital computers, we must construct a discrete-time system model simulating the continuous-time processes in some characteristic aspect. Though many discretization methods have been proposed, they do not necessarily provide a discrete-time system in which input, state and output are identical with the sampled values of the original continuous-time system. The isomorphism discretization that all of the input, state and output of a continuous-time system can be recovered from the corresponding discrete-time system is crucial for our analysis. This paper aims at guaranteeing the isomorphism between a continuous- and a discrete-time system models (fluency system model) which were proposed by the authors. The isomorphism of input space had been already shown in the previous works by one of the authors. In this paper, by showing the isomorphism of the state function and output spaces, the aim will be achieved.