Search

Binary sequences generated from finite state automata are studied in this correspondence by utilizing system theoretic concepts. We develop a new unified approach for analyzing the linear complexity of such sequences, via controllability and observability conditions. A vectorial trace representation of sequences with arbitrary period is provided, which leads to a new generalized discrete Fourier transform allowing the generation of sequences with prescribed linear complexity. Furthermore, we introduce new classes of nonlinear filters, using the proposed approach, which generalize currently known classes and guarantee the same lower bound on the linear complexity. Index Terms--Complexity, discrete Fourier transform, feedback shift registers, nonlinear filters, sequences, state space generators.

The nonlinear complexity of binary sequences and its connections with Lempel-Ziv complexity is studied in this paper. A new recursive algorithm is presented, which produces the minimal nonlinear feedback shift register of a given binary sequence. Moreover, it is shown that the eigenvalue profile of a sequence uniquely determines its nonlinear complexity profile, thus establishing a connection between Lempel-Ziv complexity and nonlinear complexity. Furthermore, a lower bound for the Lempel-Ziv compression ratio of a given sequence is proved that depends on its nonlinear complexity. Index Terms--Compression, cryptography, eigenvalue, Lempel-Ziv complexity, nonlinear complexity, nonlinear feedback shift registers, sequences.

A novel algorithm based on subspace projections is developed for blindly estimating the discrete orders of a linear finite-impulse-response (FIR) multiple-input multiple-output (MIMO) system, the number of subsystems that attain each other and the total number of inputs. Simulations in the context of blind channel order estimation show good performance in comparison to existing schemes developed for single-input multiple-output (SIMO) systems.

The problem of finding the shortest feedback shift register, with quadratic feedback function that generates a given finite-length sequence is considered. An algorithm for the determination of the quadratic span and the feedback function, which takes advantage of the special block structure of the associated system of linear equations, is proposed. Index Terms--Binary sequences, feedback functions, linear span, quadratic span, shift registers.

The problem of finding the length of a shortest feedback shift register that generates a given finite-length sequence is considered. An efficient algorithm for the determination of the span is proposed, that takes advantage of the special block structure of the associated system of linear equations. The span distribution of finite-length binary sequences is also studied. Index Terms--Binary sequences, nonlinear feedback functions, shift registers, span.

Binary sequences of period [2.sup.n]--1 generated by a linear feedback shift register (LFSR) whose stages are filtered by a nonlinear function f are studied. New iterative formulas are derived for the calculation of the linear complexity of the output sequences. It is shown that these tools provide an efficient mechanism for controlling the linear complexity of the nonlinearly filtered maximal-length sequences. Index Terms--Binary sequences, filter functions, linear complexity, linear feedback shift registers (LFSRs), m-sequences.

Blind identification of a class of bilinear systems, excited by non-Gaussian higher order white noise, is examined and discussed.

The determination of the minimum linear span sequence that differs from a given binary sequence, of period N = [2.sup.n] - 1, by at most one digit Is discussed and three methods are presented: the sequential divisions method, the congruential equations method, and the phase synchronization method. High-level algorithm organizations are provided. Finally, guidelines on sequence characterization and design via the notion of robustness are given. Index Terms--Binary sequences, linear span, sequence approximation, single-error linear span profile, weight complexity.

Identification of a discrete input-output bilinear system driven by an independent identically distributed (iid) stochastic input and corrupted by measurement noise is discussed. An algorithmic procedure for direct computation of unknown model parameters is proposed, based on crosscumulant information up to third order.

The problem of designing an N-band perfect reconstruction of finite impulse response filter banks is considered. The problem, which involves computing N-K filters given that one

General nonlinear input-output systems having Volterra expansions and inspired by stationary, zero mean Gaussian inputs with arbitrary spectra are identified. Time and frequency domain formulae are found for the kernels, using crosscumulant information. The time and frequency domain formulae's optimality in mean squared error is established.

The covariance approach in signal modeling is solved by a numerically stable, fast-order recursive algorithm, whose application involves the study of the data acquisition errors and propagation of finite arithmetic errors in detail. Initially, the main algorithmic recursions are linearized. After that, a required transformation changes the resulting equations of accumulated errors into residual forms, whose bounds are calculated.

Several adaptive algorithms are presented for multichannel least squares filtering and multivariable system identification. The transversal and lattice-structured methods apply to cases requiring multichannel finite impulse response filtering, rational infinite impulse response filtering, ARX multichannel system identification and identification of general linear systems. They exhibit lower computational complexity over the coventional least squares and Gauss-Newton approaches.

Proposed efficient algorithms are designed to identify multivariable systems and multichannel Fourier infrared filtering under conditions of varying register lengths for each input channel. These programs offer decreased computational complexity, scalar-only operations, parallelism and a framework open to least squares (LS) multichannel identification and filtering algorithms. The proposed programs can be applied in identifying the high speed operations such as equalizing channels of mobile communications and two-dimensional Wiener and LS image and restoration filtering.

Two efficient adaptive algorithms are outlined for least squares multichannel Fourier infrared filtering and system identification with the first algorithm focusing on the covariance or unwindowed data case and the second using the prewindowing data assumption for added simplification. A new channel decomposition method is used and data parameter nesting elements are resolved with proper variations for both algorithms which can carry multichannel filters with varying filter orders and are free from matrix operations.

In this correspondence, closed-form expressions for the blind identification of linear-quadratic Volterra systems are established. The system is excited by a complex valued random sequence and the output cumulants (of order up to 4) are employed. It is assumed that the memory of the linear part is greater than or equal to the memory of the quadratic part. Cumulant-based formulas are developed demonstrating that the system is uniquely identifiable. An SVD based variant with improved performance is also derived. Simulations and comparisons with existing techniques are presented. [ABSTRACT FROM AUTHOR]

We consider a model of the form y = Ax + n, where x ϵ CM is sparse with at most L nonzero coefficients in unknown locations, y ϵ CN is the observation vector, A ϵ CNxM is the measurement matrix and n ϵ CN is the Gaussian noise. We develop a Cramér-Rao bound on the mean squared estimation error of the nonzero elements of x, corresponding to the genie-aided estimator (GAE) which is provided with the locations of the nonzero elements of x. Intuitively, the mean squared estimation error of any estimator without the knowledge of the locations of the nonzero elements of x is no less than that of the GAE. Assuming that L /N is fixed, we establish the existence of an estimator that asymptotically achieves the Cramér-Rao bound without any knowledge of the locations of the nonzero elements of x as N → ∞, for A a random Gaussian matrix whose elements are drawn i.i.d. according to A((O, 1). [ABSTRACT FROM AUTHOR]