2
$\begingroup$

I have this system:

$$ y[n] = -\frac{1}{2} x[n+2] - y[n+1] $$

I have no idea how to prove if the system is linear or not, because, it depends on future outputs...

Thanks for the help

$\endgroup$
4
$\begingroup$

Matt's original answer, regarding linearity, is correct.

Let $\mathbb{T}\{ . \}$ be the linear operator that maps input $x[n]$ to output $y[n]$.

$$ y[n] = \mathbb{T}\{ x[n] \} $$

the sole necessary definition for linearity is simply whether superposition applies for all possible inputs. for a discrete-time system, if, for two completely arbitrary inputs, $x_1[n]$ and $x_2[n]$, this

$$ y_1[n] + y_2[n] = \mathbb{T}\{ x_1[n] \} + \mathbb{T}\{ x_2[n] \} = \mathbb{T}\{ x_1[n] + x_2[n] \} \quad \forall n \in \mathbb{Z}$$

is true, then the system is Linear. that is the sole criterion.

the scaling property

$$ \begin{align} a \cdot y[n] &= a \cdot \mathbb{T}\{ x[n] \} \\ & = \mathbb{T}\{ a \cdot x[n] \} \quad \forall n \in \mathbb{Z}, a \in \mathbb{C} \\ \end{align} $$

can be derived directly from the superposition property, first for integer $a$, then for reciprocal integer $a$, then for real and rational $a$. a little more handwaving regarding continuity and limits is needed to extend this to any real $a$, and not much else is needed to extend to $a \in \mathbb{C} $.

Linearity is solely a property of the system. it is not a property of the input. so if it is true for one particular input, if the system is Linear, it's also true for any other input.

similarly, for Time-Invariance, if, for a discrete-time $y[n] = \mathbb{T}\{ x[n] \}$, then

$$ y[n-N] = \mathbb{T}\{ x[n-N] \} \quad \forall n,N \in \mathbb{Z} $$

if the discrete-time system satisfies that criterion, it's Time-Invariant. likewise, Time-Invariancy is a property solely of the system, not of the inputs to the system.

if a system satisfies both criteria for Linearity and Time-Invariancy, then it is "LTI" and we get to use all this cool Fourier and Z-transform technique on it.

the system as depicted by the OP is LTI, however, it is also anti-causal (which is also "acausal", but "acausal" is a less specific property than "anti-causal") .

$\endgroup$
  • $\begingroup$ I obviously agree with your statement that linearity is solely a property of the system. However, a non-zero initial condition is part of the system, and in this way it affects the system's properties. As I've mentioned above, the OP's system could be linear (and time-invariant) if it is initially at rest. If not, it will be neither. I've copied a relevant piece of text of Oppenheim and Schafer's DTSP into my answer to clear up this point. $\endgroup$ – Matt L. Oct 2 '14 at 17:27
  • $\begingroup$ since this is not the position you're taking @MattL., i won't edit your answer with it. this is the sole definition of the system from the OP: $$ y[n] = -\frac{1}{2} x[n+2] - y[n+1] $$ . now, tell us all, if $y_1[n]=\mathbb{T}\{x_1[n]\}$ is the output of that system as it is defined with any arbitrary input $x_1[n]$, and if $y_2[n]$ is the output of that system with any arbitrary input $x_2[n]$, does or does not this system satisfy this criterion (as depicted in your original answer): $$ a\ y_1[n] + b\ y_2[n] = \mathbb{T}\{ a\ x_1[n] + b \ x_2[n] \} $$?? that is the only issue. $\endgroup$ – robert bristow-johnson Oct 2 '14 at 17:45
  • $\begingroup$ I've removed the snippet from Oppenheim and Schafer from my answer (since you didn't like it) and added a proof that the system is linear only if it is initially at rest (zero initial condition) and non-linear otherwise. $\endgroup$ – Matt L. Oct 2 '14 at 20:05
  • $\begingroup$ listen, i really like O&S, and even though i've been accused (long ago on comp.dsp by Eric Jacobsen) of "quoting O&S scripture" as a substitute for proof (it was about whether or not the DFT inherently windows or inherently periodically extends its finite input data), i have, in the past, found where O&S definitions (or at least 1 definition) do not square with other lit and other disciplines. so, to begin with, if $h[n]$ are all constant with respect to everything else except $n$, would you say that this is LTI: $$ y[n] = \sum\limits_{i=-\infty}^{+\infty} h[i] x[n-i] $$ ?? $\endgroup$ – robert bristow-johnson Oct 2 '14 at 20:35
  • $\begingroup$ Of course a system described by convolution is LTI. Problem is that a system with non-zero initial conditions is not fully described by convolution. What do you think: is $y[n]=x[n]+c$ with an arbitrary constant $c$ LTI? And this is exactly what a non-zero initial condition does to a system. $\endgroup$ – Matt L. Oct 3 '14 at 6:53
4
$\begingroup$

For linearity it is irrelevant if the output depends on future values. This only affects the system's causality. For linearity you just need to check whether the response to the signal

$$ax_1[n] + bx_2[n]$$

equals

$$ay_1[n] + by_2[n]$$

where $y_1[n]$ and $y_2[n]$ are the individual responses to inputs $x_1[n]$ and $x_2[n]$, respectively.

And of course you can write the input/output relation as

$$y[n+1] = -\frac12 x[n+2] - y[n]\tag{1}$$

I will now characterize all sequences that satisfy the recursion (1) for the specific input signal $x[n]=\delta[n]$. Applying the $\mathcal{Z}$-transform to (1) we get (with $X(z)=1$)

$$Y(z)=-\frac12\frac{z^2}{1+z}\tag{2}$$

The function $Y(z)$ corresponds to one left-sided sequence and to one right-sided sequence. Note that left-sided and right-sided doesn't necessarily mean anti-causal and causal, but it only means that $y(n)=0$ for $n>N$ or for $n<N$, respectively, for some positive or negative integer $N$. These two sequences are given by

$$y_{p1}[n]=\frac12 (-1)^{n}u(n+1)\tag{3}$$ and $$y_{p2}[n]=-\frac12 (-1)^n u(-n-2)\tag{4}$$

Note that neither (3) nor (4) is causal. The sequences $y_{p1}[n]$ and $y_{p2}[n]$ are particular solutions of the difference equation (1) for $x[n]=\delta[n]$. They are in fact impulse responses of two different linear time-invariant (LTI) systems described by the difference equation (1). The impulse response $y_{p1}[n]$ was mentioned by Dilip Sarwate in a comment below, and something similar to $y_{p2}[n]$ was mentioned by Robert B.-J. I completely agree with them that the difference equation (1) describes an LTI system, if it is used to describe a system with either (3) or (4) as impulse response.

However, the sequences (3) and (4) are not the only sequences that satisfy (1). Looking at the homogeneous difference equation

$$y[n+1]=-y[n]\tag{5}$$

we see that

$$y_h[n]=c(-1)^n,\quad c\in\mathbf{R}\tag{6}$$

is a solution of (5). Consequently, the general solution of (1) (with $x[n]=\delta[n]$) can be written as

$$y[n]=y_{p1}[n]+y_h[n]=\frac12 (-1)^{n}u(n+1) + c(-1)^n\tag{7}$$

Of course we could as well have used $y_{p2}[n]$ to define the general solution. Note that $y_{p2}[n]$ is obtained from (7) by choosing $c=-1/2$.

Now assume that we scale the input signal and use $x[n]=2\delta[n]$ instead. Obviously, the solutions $y_{p1}[n]$ and $y_{p2}[n]$ will change accordingly, but the general solution (7) will not (unless $c=0$ or $c=-1/2$), because the homogeneous solution (6) does not depend on $x[n]$. This is why I claim that the difference equation (1) does not necessarily describe an LTI system. In our case, it describes exactly two LTI systems and an infinite number of systems which are neither linear nor time-invariant.

$\endgroup$
  • $\begingroup$ Thanks for your answer, So in this case, I have: ay1(n) = a*(-0.5*x1(n+2) - y(n+1)) by2(n) = b*(-0.5*x2(n+2) - y(n+1)) And the response to ax1(n)+bx2(n) is: -0.5(ax1(n+2)+bx2(n+2)) - y(n+1) But this is not equal to y1(n)+y2(n) so I guess my system is not linear right ? Thanks again ! $\endgroup$ – johnny Oct 1 '14 at 15:37
  • $\begingroup$ @johnny No, it is linear. Your equations are incorrect. $\endgroup$ – Jim Clay Oct 1 '14 at 17:02
  • $\begingroup$ @johnny: I've added more information to my answer. $\endgroup$ – Matt L. Oct 2 '14 at 8:01
  • $\begingroup$ @JimClay: I know what you mean by saying 'it is linear', but to be precise we have to say that we don't know, unless the initial condition is given. If $y(0)\neq 0$, the system is neither linear nor time-invariant. $\endgroup$ – Matt L. Oct 2 '14 at 8:03
  • $\begingroup$ @MattL. Good point. $\endgroup$ – Jim Clay Oct 2 '14 at 13:37
0
$\begingroup$

so, using Matt's original criterion for the property of "Linearity": if $y_1[n]$ is the output when $x_1[n]$ is the input and $y_2[n]$ is the output when $x_2[n]$ is input, is

$$a \ y_1[n] + b \ y_2[n]$$

the output of the same system when

$$a \ x_1[n] + b \ x_2[n]$$

is the input?

since the system is fully and solely described as

$$ y[n] = -\frac12 x[n+2] - y[n+1] $$

, this depends on whether equality is maintained with the above substitution. is

$$ a \ y_1[n] + b \ y_2[n] \ = \ -\frac12 \left(a \ x_1[n+2] + b \ x_2[n+2] \right) - \left(a \ y_1[n+1] + b \ y_2[n+1] \right) $$

true or not? if it's true, the system is linear according to the criterion Matt L first held out. if not, it's not linear.

$\endgroup$
  • $\begingroup$ I've updated my answer one more time because I'm not happy with our disagreement which I believe is at least partly based on misunderstandings. I've replaced some old parts by a new explanation, not because I think that what I had written was wrong, but because I've tried to write a clearer exposition of what I mean. Please have a look and let me know at what point our opinions diverge. $\endgroup$ – Matt L. Oct 8 '14 at 7:42
  • $\begingroup$ okay, @MattL., i am reviewing it. changing $$y[n] = -\frac12 x[n+2] - y[n+1]$$ to $$y[n+1] = -\frac12 x[n+2] - y[n]$$ does seem to change the operation of the system from one that is left-sided to one that is right-sided. this zero-input, non-zero output case $$y[n] = -y[n+1]$$ clearly, in-and-of-itself depicts something that cannot be linear. it was something i was considering at comp.dsp a couple days ago.. for me, i have trouble with this because it seems to make marginal stability the LTI issue. $\endgroup$ – robert bristow-johnson Oct 8 '14 at 12:03
  • $\begingroup$ so @MattL., is stability a property that is orthogonal to LTI or does the property of stability affect whether or not a system is LTI? $\endgroup$ – robert bristow-johnson Oct 8 '14 at 12:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.