Discrete systems and difference equations

In the past few decades, analog controllers have often been replaced by digital controllers whose inputs and outputs are defined at discrete time instances.

Discrete systems and difference equations

In a discrete system over time, the relationship that binds the input sequence u(k) to the output y(k) is expressed through a recursive difference equation:

y(k)=f\left\{y(k-1),y(k-2),\cdots ;u(k),u(k-1),\cdots ,k\right\}

The system is also causal in that the output at instant k depends only on the previous outputs and inputs.

In this article we will consider only discrete time-invariant systems in which, that is, f{•} does not explicitly depend on k and of the finite-dimensional type, for which the output at instant k depends on a finite number of previous inputs and outputs:

y(k)=f\left\{y(k-1),y(k-2),\cdots y(k-N);u(k),u(k-1),\cdots ,u(k-M) \right\}

If we define n=max{N,M} as the order of the system, the equation is called difference equation of order n.

In the case of multivariable systems, y(k) and u(k) will be vectors of appropriate size, and the relation input-output will be described by a system of difference equations.

Similarly to continuous systems over time, much of the analysis and synthesis of discrete systems is carried out in the context of Time-Invariant Linear Discrete Systems, indicated by DLIT. For DLIT systems the representation becomes:

y(k)=\sum_{i=1}^{N}a_{i}y(k-i)+\sum_{j=0}^{M}b_{j}u(k-j)

where the coefficients are real.

The output y(k) is a linear combination of the previous N outputs and the previous M inputs, in addition to the current u(k) input if b_{0}\neq 0 .

The representation of a DLIT system with the recursive difference equation is also called the Autoregressive Moving Average (ARMA) model. It corresponds to the linear differential equation with constant coefficients for linear and continuous systems over time.

The determination of the output y(k) given the input sequence u(k) can be done by iteratively solving the difference equation of order n, starting from the initial conditions, that is, the M+N previous values of the input and output.

The difference equation of order n can then be associated with the following calculation procedure:

Difference equation solving procedure

R and S are memory areas in which the previous M+N input and output values necessary for the calculation of y(k) are stored.

Discrete systems have become increasingly important as computer applications for real-time signal processing have increased. In a DDC control, the control algorithm developed by the µP can be described as a discrete system, very often of the DLIT type, since the synthesis of the regulator is conducted within linear systems (neglecting the quantizations).

However, there are many other applications in areas other than control, where you have to deal with discrete systems. An example is the field of digital signal processing, which is of great interest in the fields of telecommunications and data analysis (instrumentation). In general, an iterative calculation procedure that processes a sequence of input data can be represented as a discrete system and vice versa.

Example: Algorithm for the square root of a real number

Consider, as an example, the algorithm for determining the square root of a real number U. As is known, the calculation can take place iteratively by solving this equation with Newton’s method:

y^{2}-U=0

which leads to the following algorithm:

y(k)=0.5\left [ y(k-1)+\frac{U}{y(k-1)} \right ]

This equation represents a discrete system of order 1, non-linear and time-invariant, subjected to a constant input U, with initial condition given by y(-1), which corresponds to an initial estimate of \sqrt{U}.

As k increases, the output tends to \sqrt{U}.

The fact that a calculation algorithm can be thought of as a discrete system made it possible to apply system stability theorems to the problems of numerical convergence of iterative algorithms.

Given the enormous interest in discrete systems in the field of digital signal processing (digital filters) appeared, in the late 70s, special microprocessors, based on a different architecture, which allow the efficient calculation of the difference equation of order n that describes a DLIT.

These devices, called DSPs (Digital Signal Processors) execute the following instruction very quickly (tens of nanoseconds):

AR=AR+COEFF*VAR

where AR is the accumulator register, COEFF a coefficient (ai,bj) and VAR a variable (y(i), u(j)).

Impulse response

We now consider the h(k) impulse response of a DLIT system, i.e. the output sequence in response to an input signal equal to δ(k) from null initial conditions. Since the input sequence u(k) can be expressed by:

u(k)=\sum_{i=-\infty }^{\infty}u(i)\delta (k-i)

for the linearity of the system the output at instant k is given by the sum of the impulsive responses of the system in response to the various inputs u(i)δ(i), that is:

y(k)=\sum_{i=-\infty }^{\infty }u(i)h(k-i)

which represents the discrete convolution operation between the two signals u(k) and h(k).

For causal systems h(k)=0 for k<0, it turns out:

y(k)=\sum_{i=-\infty }^{k }u(i)h(k-i)=\sum_{j=0}^{\infty }h(j)u(k-j)

DLIT systems for which the impulse response is canceled for all k above a finite value, are called FIR (Finite Impulse Response); otherwise, they are called IIR (Infinite Impulse Response).

The forced response yf(k), that is, starting from null initial conditions, to a causal input u(k) applied at the initial instant (k=0), becomes:

y_{f}(k)=\sum_{i=0 }^{k }u(i)h(k-i)

Given the invariance over time of the system, this expression is generally valid considering as the initial instant that of application of the input.

How to solve difference equations

The calculation of the forced response of a DLIT system to a u(k) input can essentially take place in two ways:

  1. iteratively solving the equation to differences of order n;
  2. resorting to the discrete convolution of the input with the impulse response of the system.

We will see these methods in a future article.

Avatar photo
About Carlo Bazzo 17 Articles
Sysadmin & network eng. @Epysoft, editor @TheTechGoggler, CTO @HDEMO. Former developer @MSFT @GOOG. Former MOps consultant @XRX @HPQ. LinkedIn: it.linkedin.com/in/carlobazzo