# DSP: Recurrence Relations in a Linear Algebra Equation

• I
• Destroxia
In summary, the conversation discusses a simple delay feedback loop in digital signal processing, where a signal from x[n] and z^-1 are added together until a full signal is formed for the output y[n]. The system can be modeled as y[n] = x[n] + D{y[n]}, with D representing z^-1. The conversation also explores the use of linear algebra equations to model the system, but the matrix appears to be non-invertible. However, the concept of the z-transform is introduced as a way to solve the problem in the frequency domain.
Destroxia
Hello, I've been working through some Digital Signal Processing stuff by myself online, and I saw a system that I wanted to write down as a Linear Algebra Equation. It's a simple delay feedback loop, looks like this:

The (+) is an adder that adds 2 signals together, so the signal from x[n] and z^-1 will be added each time until a full signal is formed for the output y[n].

However, on the first run of the loop, z^-1 is initialized to 0, so it's contribution on the first run is zero. (z^-1 will return always return whatever it was last fed, so on the second run it will have whatever came from x[n] the first time and spit that out)So we can model this system as: $$y[n]=x[n]+ D\lbrace y[n] \rbrace=x[n]+y[n-1], \space \space \space \space \space \space y[0]=x[0]=1$$
Where: $$\space x[n], \space y[n] \space \in \space \mathbb{C}^{N}$$
and D is a size NxN linear operator matrix which represents z^-1, which acts like so: ## D[{x[n]}]= x[n-1] ##

If you want, you can generalize the system for more delay: $$y[n]=x[n]+ D_{N}\lbrace y[n] \rbrace=x[n]+y[n-N], \space \space \space \space \space \space y[0]=x[0]=1$$

Now imagine we have an input x[n] of dimension 4 that is simply a pulse:
$$x = \left[ {\begin{array}{c} 1\\ 0\\ 0\\ 0\\ \end{array} } \right]$$

If we push this input into the system, with say a delay of Z^-2, we should get a pulse every 2 loops, so the output would look like so:
$$y = \left[ {\begin{array}{c} 1\\ 0\\ 1\\ 0\\ \end{array} } \right]$$

My issue is, when I try to model this with a linear algebra equation, there is recursion, and I can't seem to get a closed form due to an non-invertible matrix. I was looking at recurrence relations on wikipedia to try to solve my issue, but I guess I just don't understand them yet.

My process for modeling this in Linear Algebra has gone like so:

$$y = x + Dy$$
$$y - Dy = x$$
$$(I - D)y = x$$
$$I -D = \left[ {\begin{array}{cccc} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\\ \end{array} } \right] - \left[ {\begin{array}{cccc} 0 & 0 & 0 & 1\\ 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ \end{array} } \right] = \left[ {\begin{array}{cccc} 1 & 0 & 0 & -1\\ -1 & 1 & 0 & 0\\ 0 & -1 & 1 & 0\\ 0 & 0 & -1 & 1\\ \end{array} } \right] )$$

This matrix appears to be uninvertible, but I should be able to somehow create a closed form for this system... I just need to be pointed in the right direction.

(I apologize if this is the wrong board for this, but this is more of a linear algebra question than a signal processing question, as I understand the signal processing part.)

#### Attachments

• system.jpg
7.4 KB · Views: 860
I believe I may have solved my own issue:

Instead of treating this as a linear equation right away, something called the "z-transform" can be taken of the equation. And this allows us to easily solve the problem in the frequency domain.

(The Z-transform is the discrete time version of the laplace transform)

## 1. What is a recurrence relation in a linear algebra equation?

A recurrence relation in a linear algebra equation is a mathematical equation that recursively defines a sequence of values. It is used to model systems where the next value in the sequence depends on the previous values.

## 2. How is a recurrence relation used in DSP?

In DSP (Digital Signal Processing), recurrence relations are used to model and analyze signals in the time and frequency domains. They are particularly useful in analyzing and designing digital filters.

## 3. What is the difference between a linear and nonlinear recurrence relation?

A linear recurrence relation is one where the next value in the sequence is a linear combination of the previous values. In contrast, a nonlinear recurrence relation involves nonlinear operations, making it more complex to solve.

## 4. How do you solve a recurrence relation in a linear algebra equation?

To solve a recurrence relation in a linear algebra equation, you can use various methods such as substitution, iteration, and generating functions. The method used depends on the complexity of the relation and the desired outcome.

## 5. What are some real-world applications of recurrence relations in DSP?

Recurrence relations in DSP have various real-world applications, including audio and image processing, data compression, and communication systems. They are also used in time series analysis, speech recognition, and control systems.

• Linear and Abstract Algebra
Replies
19
Views
2K
• Linear and Abstract Algebra
Replies
3
Views
2K
• Linear and Abstract Algebra
Replies
4
Views
969
• Linear and Abstract Algebra
Replies
4
Views
2K
• Linear and Abstract Algebra
Replies
3
Views
1K
• Linear and Abstract Algebra
Replies
8
Views
961
• Linear and Abstract Algebra
Replies
2
Views
2K
• Linear and Abstract Algebra
Replies
1
Views
873
• Linear and Abstract Algebra
Replies
3
Views
1K
• Linear and Abstract Algebra
Replies
4
Views
2K