On compensator design for linear time-invariant dual-inputsingle-output systems

This paper presents a new method for the design of compensators for linear time-invariant dual-input/single-output (DISO) systems in continuous time or discrete time. The new method reduces the problem to two single-input/single-output (SISO) design problems, which are well suited to frequency-response design techniques. The first part of the method is the design of a stabilizing compensator for an auxiliary feedback system. The auxiliary compensator parameterizes the two output blocks of the single-input/dual-output compensator such that the zeros of the parallel system formed by cascade of the compensator with the plant are stable. The auxiliary compensator also determines the relative contribution to the output of the two parallel subsystems of the DISO system. The second SISO compensator design is used to ensure that the feedback system is stable and that performance and robustness specifications are achieved. This paper includes a discrete-time-design example for a dual-stage actuator system for a disk drive including implementation results. Straightforward extensions for multi-input/single-output systems are discussed     

Reliability and component importance of a consecutive-k-out-of-n system

This paper explores the duality between the consecutive-k-out-of-n F and G systems, studies the Birnbaum reliability importance of the components in an i.i.d. system, and reviews the research in uniform treatment of the linear and circular consecutive-k-out-of-n:F systems. Upper and lower bounds for the reliability of a linear consecutive-k-out-of-n system are developed by constructing k-fold series and parallel redundant systems from the linear system.     

l-Delay Input and Initial-State Reconstruction for Discrete-Time Linear Systems

Prior results on input reconstruction for multi-input, multi-output discrete-time linear systems are extended by defining l-delay input and initial-state observability. This property provides the foundation for reconstructing both unknown inputs and unknown initial conditions, and thus is a stronger notion than l-delay left invertibility, which allows input reconstruction only when the initial state is known. These properties are linked by the main result (Theorem 4), which states that a MIMO discrete-time linear system with at least as many outputs as inputs is l-delay input and initial-state observable if and only if it is l-delay left invertible and has no invariant zeros. In addition, we prove that the minimal delay for input and state reconstruction is identical to the minimal delay for left invertibility. When transmission zeros are present, we numerically demonstrate l-delay input and state reconstruction to show how the input-reconstruction error depends on the locations of the zeros. Specifically, minimum-phase zeros give rise to decaying input reconstruction error, nonminimum-phase zeros give rise to growing reconstruction error, and zeros on the unit circle give rise to persistent reconstruction error.     

Representations of Linear Dual-Rate System Via Single SISO LTI Filter, Conventional Sampler and Block Sampler

In this brief, it is proved that a linear dual-rate system can be represented via a series cascade of: 1) a conventional expander, a single-input single-output (SISO) linear time-invariant (LTI) filter and a block decimator, or 2) a block expander, an SISO LTI filter and a conventional decimator. Hence, incompatible nonuniform filter banks could achieve perfect reconstruction via LTI filters, conventional samplers and block samplers without expanding the input-output dimension of a subsystem of linear dual-rate systems or converting the nonuniform filter banks to uniform filter banks. The main advantage of the proposed representations is to avoid complicated design of the circuit layout caused by connecting subsystems with large input-output dimension or a lot of subsystems together.     

On Time Optimal Implementation of Uniform Recurrences onto Array Processors via Quadratic Programming

Many important algorithms can be described by n-dimensional uniform recurrences. The computations are then indexed by integral vectors of length n and the data dependencies between computations can be described by the difference vector of the corresponding indexes which are independent of the indexes. This paper addresses the following optimization problem: Given an n-dimensional uniform recurrence whose computation indexes are mapped by a linear function onto the processors of an array processor embedded in k-space (1 k n). Find an optimal linear function for the computation indexes. We study a continuous approximation of this problem by passing from linear to quasi-linear timing functions. The resultant problem formulation is then a quadratic programming problem which can be solved by standard algorithms for quadratic or general nonlinear optimization problems. We demonstrate the effectiveness of our approach by several nontrivial test examples.     

On the Wold decomposition of discrete-time cyclostationaryprocesses

The Wold decomposition of discrete-time CS (cyclostationary) processes into a regular and predictable component is considered. Using the properties of the zeros of linear periodic systems, it is shown that the predictable component consists of a linear combination of sine waves     

Turbo Product Code Decoder Without Interleaving Resource: From Parallelism Exploration to High Efficiency Architecture

This article proposes to explore parallelism in Turbo-Product Code (TPC) decoding through a parallelism level classification and characterization. From this design space exploration, an innovative TPC decoder architecture without any interleaving resource is presented. This architecture includes a fully-parallel SISO decoder capable of processing n symbols in one clock period. Syntheses results show the better efficiency of such an architecture compared with existing solutions. Considering a six-iteration turbo decoder of a BCH(32,26)² product code, synthesized in 90 nm CMOS technology, 10 Gb/s can be achieved with an area of 600 Kgates. Moreover, a second architecture enhancing parallelism rate is described. The throughput is 50 Gb/s while an area estimation gives 2.2 Mgates. Finally, comparisons with existing TPC decoders and existing LDPC decoders are performed. They validate the potential of proposed TPC decoder for Gb/s optical fiber transmission systems.     

Bounds for reliability of k-within connected-(r, s)-out-of-(m, n) failure systems

A k-within linear connected-(r, s)-out-of-(m, n) failure system is a two-dimensional grid whose components are ordered like the elements of an (m, n)-matrix. A k-within circular connected-(r, s)-out-of (m, n) failure system consists of the intersection points of m circles centered at the same point with n rays starting from that point and crossing the circles. The components of both systems either operate or fail. By definition, a k-within (linear or circular) connected-(r, s)-out-of-(m, n) failure system fails if at least one (r, s)-submatrix contains k or more failed components. These systems are used as mathematical models for design and operation of many engineering systems. For systems with statistically independent and identically distributed components, a lower and upper bound of system reliability are derived using improved Bonferroni inequalities. These bounds are easy to compute and provide good estimates for system reliability. New bounds for the reliability of other connected-(r, s)-out-of-(m, n) failure systems existing in the current literature are also obtained. Several failure systems with various values of the parameters k, r, s, m, n and p are used as numerical examples for comparison and illustrative purposes.     

Zeros and poles of linear periodic multivariable discrete-time systems

In this paper the notions of transmission zero, invariant zero, and structural zero (that is the geometric notion of zero) are extended to linear periodic discrete-time systems, as well as the notion of pole. Their meaning is clarified and their relationships stressed, thus extending the time-invariant theory. In particular, the invariant zeros and the structural zeros are shown to coincide, together with their multiplicities, and the former are shown to be independent of a linear state feedback. Moreover, the nonzero transmission zeros, the nonzero invariant zeros, and the nonzero poles are shown to be independent of time, together with their multiplicities. Some of these results are obtained with the help of the notions of reachability subspace and inner controllable subspace, which constitute a further development of the geometric theory for this class of systems.This work was supported by the Ministero Pubblica Istruzione.     

Characterization of Forced Vibration for Difference Inclusions: A Lyapunov Approach

A Lyapunov approach to the characterization of forced vibration for continuous-time systems was recently proposed in. The objective of this paper is to derive counterpart results for discrete-time systems. The class of oscillatory input signals to be considered include sinusoidal signals, multitone signals, and periodic signals which can be described as the output of an autonomous system. The Lyapunov approach is developed for linear systems, homogeneous systems (difference inclusions), and nonlinear systems (difference inclusions), respectively. It is established that the steady-state gain can be arbitrarily closely characterized with Lyapunov functions if the output response converges exponentially to the steady state. We also evaluate other output measures such as the peak of the transient response and the convergence rate. Applying the results to linear difference inclusions, optimization problems with linear matrix inequality constraints can be formulated for the purpose of estimating the output measures. This paper's results can be readily applied to the evaluation of frequency responses of general nonlinear and uncertain systems by restricting the inputs to sinusoidal signals. Similar to continuous-time systems, it is observed that the peak of the frequency response can be strictly larger than the gain for a linear difference inclusion.     

A necessary condition for optimal consecutive-k-out-of-n:G system design

A consecutive-k-out-of-n:G system is a sequence of n components such that the system works if and only if at least k consecutive components work. When the components have different reliabilities, a problem of interest is how to arrange these components to maximize system reliability. This paper proves a set of necessary conditions for optimal arrangement of linear consecutive-k-out-of-2k:G systems.     

The vulnerability of geometric sequences based on fields of odd characteristic

A new method of cryptologic attack on binary sequences is given, using their linear complexities relative to odd prime numbers. We show that, relative to a particular prime number p, the linear complexity of a binary geometric sequence is low. It is also shown that the prime p can be determined with high probability by a randomized algorithm if a number of bits much smaller than the linear complexity is known. This determination is made by exploiting the imbalance in the number of zeros and ones in the sequences in question, and uses a new statistical measure, the partial imbalance.This project was sponsored by the National Security Agency under Grant No. MDA904-91-H-0012. The United States Government is authorized to reproduce and distribute reprints notwithstanding any copyright notation hereon.     

Robust and Retunable State Realizations of Transfer Functions with known Poles and Zeros

The standard controllable and observable canonical realizations have A-matrices whose eigenvalue locations are highly sensitive to small perturbations to the nonzero entries of the A-matrix that correspond to the coefficients of the characteristic polynomial. On the other hand, the eigenvalue locations of tridiagonal A-matrices are relatively insensitive to similar perturbations. Given a set of known poles and zeros from which the transfer function of a SISO is computed, this paper details an approach to state space realizations with tridiagonal A-matrices using a genetic algorithm and the equivalence of the realization with the controllable canonical form. In addition to the insensitivity of the tridiagonal realization to perturbations, an additional genetic algorithm is used to reconfigure input and output matrices when nonzero gains in the B- and C-matrices are perturbed to zero, i.e., disconnections (shorts/opens) which account for over 70% of field failures. The reconfigured matrices achieve an equivalent realization, thereby maintaining the same input–output behavior. Reconfigurable systems are critical to maintaining exact input–output behavior (automatically) without being able to repair the disconnection.     

Stability Testing of Two-Dimensional Discrete-Time Systems by a Scattering-Type Stability Table and Its Telepolation

Stability testing of two-dimensional (2-D) discrete-time systems requires decision on whether a 2-D (bivariate) polynomial does not vanish in the closed exterior of the unit bi-circle. The paper reformulates a tabular test advanced by Jury to solve this problem. The 2-D tabular test builds for a real 2-D polynomial of degree (n ₁, n ₂) a sequence of n ₂ matrices or 2-D polynomials (the 2-D table). It then examines its last polynomial - a 1-D polynomial of degree 2n ₁ n ₂ - for no zeros on the unit circle. A count of arithmetic operations for the tabular test is performed. It shows that the test has O(n ⁶) complexity (assuming n ₁ = n ₂ = n)- a significant improvement compared to previous tabular tests that used to be of exponential complexity. The analysis also reveals that, even though the testing of the condition on the last polynomial requires O(n ⁴) operations, the count of operations required for the table's construction makes the overall complexity O(n ⁶). Next it is shown that it is possible to telescope the last polynomial of the table by interpolation and circumvent the construction of the 2-D table. The telepolation of the tabular test replaces the table by n ₁ n ₂ + 1 stability tests of 1-D polynomials of degree n ₁ or n ₂ of certain form. The resulting new 2-D stability testing procedure requires a very low O(n ⁴) count of operations. The paper also brings extension for the tabular test and its simplification by telepolation to testing 2-D polynomials with complex valued coefficients.     

A Constructive Approach to Stabilizability and Stabilization of a Class of nD Systems

This paper presents a constructive approach to the problem of output feedback stabilizability and stabilization of a class of linear multidimensional (nD, n>2) systems, whose varieties of the ideals generated by the reduced minors are infinite with respect to not more than two variables. The main idea of the proposed approach is to decompose the variety of an nD system in this class into a union of several varieties, each of which is defined by polynomials in just two variables. The new method can be considered as a combination of Gröbner bases and existing results on two-dimensional (2D) digital filter stability tests and on stabilizability and stabilization of 2D systems. An example is illustrated.     

Algebraic nonlinearity and its applications to cryptography

The algebraic nonlinearity of an n-bit boolean function is defined as the degree of the polynomial f(X) Z ₂[x ₁, x ₂,..., x _n] that represents f. We prove that the average degree of an ANF polynomial for an n-bit function is n+o(1). Further, for a balanced n-bit function, any subfunction obtained by holding less than n-[log n]- 1 bits constant is also expected to be nonaffine. A function is partially linear if f(X) has some indeterminates that only occur in terms bounded by degree 1. Boolean functions which can be mapped to partially linear functions via a linear transformation are said to have a linear structure, and are a potentially weak class of functions for cryptography. We prove that the number of n-bit functions that have a linear structure is asymptotic .The author is presently employed by the Distributed System Technology Center, Brisbane, Australia.Project sponsored in part by NSERC operating Grant OGP0121648, and the National Security Agency under Grant Number MDA904-91-H-0012. The United States Government is authorized to reproduce and distribute reprints notwithstanding any copyright notation hereon.     

Performance enhancement of a class of nonlinear systems bydisturbance observers

A large class of single-input single-output (SISO) nonlinear systems is considered. The nonlinearity in a system of this class has the property that its output can be decomposed as the summation of the outputs of a stable SISO linear time-invariant system and a bounded function of time. For the class of systems under consideration, disturbance observers are designed to estimate the effects of nonlinearities and to cancel them subsequently. The designed disturbance observers are thus able to make the nonlinear systems behave linearly and to enhance their performance. Examples are given to show disturbance observers can suppress the effect of dead-zone nonlinearity and limit cycles caused by backlash     

Topological considerations for autoregressive systems with fixed Kronecker indices

In this paper we will study topological properties of the class of proper and improperp×m transfer functions of a fixed McMillan degreen. A natural generalization of this class is all autoregressive systems of degreen under external system equivalence. The subset of irreducible systems has in a natural way the structure of a manifold and we show how to extend this topology to the set of all autoregressive systems of degree at mostn. We will describe the subset of systems with fixed Kronecker indicesv=(v₁,...,v _p ) as an orbit space, which will enable us to calculate the topological dimension for each collection of indicesv. Finally, we will describe the topological closure of those sets in the space of all autoregressive systems.Supported in part by NSF grant DMS-9201263Supported in part by Frank M. Freimann chair in Electrical Engineering.Supported in part by the Research Enhancement Fund from College of Art and Sciences, Texas Tech University.     

Further Results on n-D Polynomial Matrix Factorizations

In this paper, some new results on zero prime factorization for a normal full rank n-D (n>2) polynomial matrix are presented. Assume that d is the greatest common divisor (g.c.d.) of the maximal order minors of a given n-D polynomial matrix F ₁. It is shown that if there exists a submatrix F of F ₁, such that the reduced minors of F have no common zeros, and the g.c.d. of the maximal order minors of F equals d, then F ₁ admits a zero right prime (ZRP) factorization if and only if F admits a ZRP factorization. A simple ZRP factorizability of a class of n-D polynomial matrices based on reduced minors is given. An advantage is that the ZRP factorizability can be tested before carrying out the actual matrix factorization. An example is illustrated.