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.