Cascading systems in Haskell

Last weekend we learned how to build systems (LTI or otherwise) using Haskell. We now want to construct interconnections of systems. In this post we will study the series interconnection of systems, usually known as cascade interconnection. Parallel and feedback interconnections will be discussed in future posts.

__________

Cascading two LTI systems

Let us consider the series interconnection of two causal discrete-time LTI systems, $\mathcal{H}_1$ and $\mathcal{H}_2$ , as depicted below

where $y = \mathcal{H}_1 (x)$ and $w =\mathcal{H}_2 (y)$ are the outputs of each LTI system in the cascade. Since the output of system $\mathcal{H}_1$ is the input of system $\mathcal{H}_2$ , we have $w = (\mathcal{H}_2 \circ \mathcal{H}_1) (x)$ .

What LTI systems should we consider? Let us choose the simplest ones: the accumulator and the differentiator. Thus, let $\mathcal{H}_1$ be an accumulator (also known as “discrete-time integrator”), whose input-output relationship is as follows

$y (n) = y (n-1) + x (n)$ ,

and let $\mathcal{H}_2$ be a first difference operator (also known as “discrete-time differentiator”), whose input-output relationship is

$w (n) = y (n) - y (n-1)$ .

Note that the output of the cascade of these two LTI systems is thus

$w (n) = y (n) - y (n-1) = (y (n-1) + x (n)) - y (n-1) = x (n)$

and, hence, the cascade is input-output equivalent to the identity operator. Since $(\mathcal{H}_2 \circ \mathcal{H}_1) (x) = x$ for all signals $x$ , we say that $\mathcal{H}_2$ is the left-inverse of system $\mathcal{H}_1$ . Since both systems are LTI, the operators commute, i.e., $\mathcal{H}_2 \circ \mathcal{H}_1 = \mathcal{H}_1 \circ \mathcal{H}_2$ and, therefore, $\mathcal{H}_2$ is also the right-inverse of system $\mathcal{H}_1$ . Since $\mathcal{H}_2$ is the left- and right-inverse of $\mathcal{H}_1$ , we say that $\mathcal{H}_2$ is the inverse of system $\mathcal{H}_1$ (and vice-versa). Do keep in mind, however, that not all systems are invertible. For details, take a look at Oppenheim & Willsky [1].

__________

Implementation in Haskell

We can easily find a state-space realization for the accumulator, but that will not be necessary. As in previous posts, let us view discrete-signals as lists. Thus, the accumulator takes a list $[x_0, x_1, x_2, \dots]$ , and returns the following list

$[y_0, y_1, y_2, \dots] = [x_0, x_0 + x_1, x_0 + x_1 + x_2, \dots]$

where we assume that the initial condition of the accumulator is zero (i.e., $y_{-1} = 0$ ). Instead of using scanl yet once again (which would require us to drop the head of the list), let us now use scanl1 to implement the accumulator:

acc :: Num a => System a a
acc = scanl1 (+)

Please note that if the initial condition of the accumulator is not zero, we should use the following code instead:

acc' :: Num a => System a a
acc' us = tail $ scanl (+) acc_ini us

where acc_ini is the initial condition of the accumulator (analogous to the constant of integration in integral calculus).

The differentiator is not a proper system [2] and, therefore, it has no state-space realization. The differentiator takes a list $[y_0, y_1, y_2, \dots]$ , and returns the following list

$[w_0, w_1, w_2, \dots] = [y_0, y_1 - y_0, y_2 - y_1, \dots]$

where we again assume that $y_{-1} = 0$ . Note the following

$[w_0, w_1, w_2, \dots] = [y_0, y_1, y_2, \dots] - [0, y_0, y_1, \dots]$

i.e., list $w$ is obtained by elementwise subtraction of a right-shifted version of list $y$ from list $y$ itself. Subtracting two lists elementwise can be implemented using zipWith:

diff :: Num a => System a a
diff ys = zipWith (-) ys (0 : ys)

If the initial condition of the differentiator is not zero, we should instead use the following code:

diff' :: Num a => System a a
diff' ys = zipWith (-) ys (diff_ini : ys)

where diff_ini is the initial condition of the differentiator. Piecing it all together, we finally obtain the following Haskell script:

type Signal a = [a]
type System a b = Signal a -> Signal b

-- accumulator
acc :: Num a => System a a
acc = scanl1 (+)

-- differentiator
diff :: Num a => System a a
diff ys = zipWith (-) ys (0 : ys)

-- cascade of the acc. and diff.
sys :: Num a => System a a
sys = diff . acc

Take a look at the last line. It says that cascading systems is the same as composing systems! Hence, the Haskell implementation is conceptually very close to the mathematical formulation using operators. Functional analysis meets functional programming…

We run the script above on GHCi and then play with it:

*Main> -- build unit impulse
*Main> let delta = 1.0 : repeat 0.0 :: Signal Float
*Main> -- output of the accumulator
*Main> let ys = acc delta
*Main> take 20 ys
[1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,
1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0]
*Main> -- output of the differentiator
*Main> let ws = diff ys
*Main> take 20 ws
[1.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,
0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0]
*Main> -- impulse response of the cascade
*Main> let hs = sys delta
*Main> take 20 hs
[1.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,
0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0]

The impulse response of the accumulator is the unit step. The impulse response of the cascade is the unit impulse, as we expected. The differentiator is the inverse of the accumulator, and vice-versa.

__________

References

[1] Alan V. Oppenheim, Alan S. Willsky, S. Hamid Nawab, Signals & Systems, 2nd edition, Prentice-Hall, 1997.

[2] Panos Antsaklis, Anthony Michel, A Linear Systems Primer, Birkhäuser Boston, 2007.

Like this:

Be the first to like this post.

Tags: Haskell, List Processing, LTI Systems, Signals & Systems, Systems Theory

This entry was posted on January 25, 2012 at 08:22 and is filed under Haskell, LTI Systems, Systems Theory. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Rod Carvalho

Leave a Reply Cancel reply

Follow “Rod Carvalho”