$$x[n] = \big(A_1 r_1^n\cos(\omega_1 n) + A_2 r_2^n \cos(\omega_2 n) + A_3 \sin(\omega_3*n) \big)u[n],$$

where $\qquad \omega_1 \ne \omega_2 \ne \omega_3, \qquad |r_1|,|r_2|<1$

I need an linear prediction model that perfectly predicts the signal with zero error $\forall n \ge n_0 > 0$ and how to find the $n_0$

I am not sure how to proceed with this as my initial thought was to minimize the energy of the first two terms that include $\cos(\omega_1 n)$ and $\cos(\omega_2 n)$ but something seems off.

• so, i think if Ced's analysis and answer is right, your $n_0 \ge 6$. – robert bristow-johnson Apr 27 '18 at 9:45

Is this a homework problem?

I figured out a way to solve this, but it isn't that simple.

First, you can split your function into three parts:

\begin{align} x_1[n] &= A_1 r_1^n \cos(\omega_1 n) \\ \\ x_2[n] &= A_2 r_2^n \cos(\omega_2 n) \\ \\ x_3[n] &= A_3 \sin(\omega_3 n) \\ \end{align}

The $u[n]$ doesn't matter because we are only concerned with $n \ge 0$ and $x_3[0]=0$.

The cosines can be solved like this:

\begin{align} x[n] &= r^n \cos(\omega n) \\ \\ x[n-1] &= r^{n-1} \cos(\omega n-\omega) \\ &= r^{n-1} \big(\cos(\omega n)\cos(\omega) + \sin(\omega n)\sin(\omega) \big) \\ \\ x[n+1] &= r^{n+1} \cos(\omega n+\omega ) \\ &= r^{n+1} \big( \cos(\omega n)\cos(\omega) - \sin(\omega n)\sin(\omega) \big)\\ \\ r x[n-1] + \tfrac{1}{r} x[n+1] &= 2 r^n \cos(\omega n)\cos(\omega) \\ &= 2 \cos(\omega ) x[n]\\ \\ x[n+1] &= 2r \cos(\omega ) x[n] - r^2 x[n-1]\\ \\ x[i] &= 2r \cos(\omega ) x[i-1] - r^2 x[i-2] \\ \end{align}

The sine can be solved like this:

\begin{align} x[n] &= r^n \sin(\omega n) \\ \\ x[n-1] &= r^{n-1} \sin(\omega n-\omega) \\ &= r^{n-1} \big( \sin(\omega n)\cos(\omega) - \cos(\omega n)\sin(\omega ) \big) \\ \\ x[n+1] &= r^{n+1} \sin(\omega n+\omega) \\ &= r^{n+1} \big( \sin(\omega n)\cos(\omega) + \cos(\omega n)\sin(\omega) \big) \\ \\ r x[n-1] + \tfrac{1}{r} x[n+1] &= 2 r^n \sin(\omega n)\cos(\omega) = 2 \cos(\omega ) x[n] \\ \\ x[n+1] &= 2r \cos(\omega) x[n] - r^2 x[n-1] \\ \\ x[i] &= 2r \cos(\omega) x[i-1] - r^2 x[i-2] \\ \end{align}

Notice, whether sine or cosine, the LPC equations are the same, what matters are the initial conditions. Your parts are multiples of these, but that is also taken care of by proper selection of initial conditions.

Here is some Python code that demonstrates that these equations work:

(Edit: The code is now in the followup below.)

What remains now is to combine these three parts into one equation. This is where it gets messy.

What you have is your solution in the form of:

\begin{align} x_1[n] &= a_{11} x_1[n-1] + a_{21} x_1[n-2] \\ x_2[n] &= a_{12} x_2[n-1] + a_{22} x_2[n-2] \\ x_3[n] &= a_{13} x_3[n-1] + a_{23} x_3[n-2] \\ \end{align}

You need to convert them to a common set of coefficients ($v_k$'s) in this form:

\begin{align} x_1[n] &= v_1 x_1[n-1] + v_2 x_1[n-2] + v_3 x_1[n-3] \\ &+ v_4 x_1[n-4] + v_5 x1[n-5] + v_6 x_1[n-6] \\ \\ x_2[n] &= v_1 x_2[n-1] + v_2 x_2[n-2] + v_3 x_2[n-3] \\ &+ v_4 x_2[n-4] + v_5 x2[n-5] + v_6 x_2[n-6] \\ \\ x_3[n] &= v_1 x_3[n-1] + v_2 x_3[n-2] + v_3 x_3[n-3] \\ &+ v_4 x_3[n-4] + v_5 x3[n-5] + v_6 x_3[n-6] \end{align}

That way they can be added together:

\begin{align} x[n] &= x_1[n] + x_2[n] + x_3[n] \\ \\ x[n] &= v_1 x[n-1] + v_2 x[n-2] + v_3 x[n-3] \\ &+ v_4 x[n-4] + v_5 x[n-5] + v_6 x[n-6] \\ \end{align}

The way I can think of right now is a lot of work, but there may be another slick way to simplify this. With a bunch of algebra, the following linear algebra problem can be set up:

$$\left[ \begin{array}{c} a_{11} \\ a_{21} \\ a_{12} \\ a_{22} \\ a_{13} \\ a_{23} \\ \end{array} \right] = W \cdot \left[ \begin{array}{c} v_1 \\ v_2 \\ v_3 \\ v_4 \\ v_5 \\ v_6 \end{array} \right]$$

Where $W$ is a 6×6 array and its elements are functions of the $a$'s. The $v$'s can then be found my multiplying the left array by $W^{-1}$.

I haven't done the algebra, but there is a pattern there.

Hope this helps, phew.

Ced

Followup:

So there is a much easier way to figure out the $v$ values. I didn't figure it out myself, I asked on the Math Exchange. (see https://math.stackexchange.com/questions/2755034).

You simply have to multiply out:

$$(S^2 - a_{11} S - a_{21})(S^2 - a_{12} S - a_{22})(S^2 - a_{13} S - a_{23}) \\ \qquad \qquad \qquad \qquad = S^6 - v_1 S^5 - v_2 S^4 - v_3 S^3 - v_4 S^2 - v_5 S^1 - v_6$$

Messy, but it works. Here it is in Python:

import numpy as np

#==========================================================
def MultiplyTuple( p, q ):

Np = len( p )
Nq = len( q )

r = np.zeros( Np + Nq - 1 )

for ip in range( Np ):
for iq in range( Nq ):
r[ip+iq] += p[ip] * q[iq]

return r

#==========================================================

x1 = np.zeros( 100 )
x2 = np.zeros( 100 )
x3 = np.zeros( 100 )
x  = np.zeros( 100 )
y  = np.zeros( 100 )

w1 = .1
w2 = .18
w3 = .05

r1 = .9
r2 = .5

A1 = 1.0
A2 = 0.5
A3 = 0.4

a11 = 2.0 * r1 * np.cos( w1 )
a21 = - r1 * r1
a12 = 2.0 * r2 * np.cos( w2 )
a22 = - r2 * r2
a13 = 2.0 * np.cos( w3 )
a23 = - 1

x1[0] = A1
x1[1] = A1 * a11 / 2.0
x2[0] = A2
x2[1] = A2 * a12 / 2.0
x3[0] = 0
x3[1] = A3 * np.sin( w3 )

print 0, x1[0], x2[0], x3[0]
print 1, x1[1], x2[1], x3[1]

for i in range( 2, 20 ):
x1[i] = a11 * x1[i-1] + a21 * x1[i-2]
x2[i] = a12 * x2[i-1] + a22 * x2[i-2]
x3[i] = a13 * x3[i-1] + a23 * x3[i-2]
print i, x1[i], x2[i], x3[i]

print

for i in range( 0, 20 ):
y1 = A1 * r1**i * np.cos( w1 * i )
y2 = A2 * r2**i * np.cos( w2 * i )
y3 = A3 * np.sin( w3 * i )
y[i] = y1 + y2 + y3
print i, y1, y2, y3

p1 = np.array( [ 1, -a11, -a21 ] )
p2 = np.array( [ 1, -a12, -a22 ] )
p3 = np.array( [ 1, -a13, -a23 ] )

p12  = MultiplyTuple(  p1, p2 )
p123 = MultiplyTuple( p12, p3 )

print p123

v1 = -p123[1]
v2 = -p123[2]
v3 = -p123[3]
v4 = -p123[4]
v5 = -p123[5]
v6 = -p123[6]

print

for i in range( 0, 6 ):
x[i] = x1[i] + x2[i] + x3[i]
print i, x[i], y[i]

for i in range( 6, 20 ):
x[i] = v1*x[i-1] + v2*x[i-2] + v3*x[i-3] \
+ v4*x[i-4] + v5*x[i-5] + v6*x[i-6]
print i, x[i], y[i]

• thanks so so much for your time and effort @Cedron ! Yes this is for homework.. I already mentioned it but since |r1|,|r2|<1 would it make sense to try and minimize the energy for the first two terms in order to see where it stops affecting the signal and then call that the no I am looking for? – siegfried Apr 25 '18 at 17:34
• @siegfried, You're welcome. I am not that knowledgeable in this area. i looked at this as a general math problem. Your proposed approach is marred by the fact that your r values can be arbitrarily close to 1. Your use of the term "perfectly" implies exactness to me. You will never achieve that mathematically with your approach, although you may reach it numerically. The method I outlined does not lend itself to a formulaic expression. I'll take another whack at it later. When solved, it will give you an exact equation starting at n = 6. – Cedron Dawg Apr 25 '18 at 18:12
• I see your point. I thought the "perfectly" and "zero error" instructions were some kind of directions for minimizing the energy of the signal since this is what I am supposed to do from what I understood in theory. – siegfried Apr 25 '18 at 20:07
• @siegfried,The solution is complete now thanks to some help from the Math Exchange. It's probably not how your class did it. – Cedron Dawg Apr 26 '18 at 23:56
• %##*&!!@^!!!!  can't you guys use text for code and $\LaTeX$ for math??! i'm coming back here to finish it if Ced doesn't fix it. – robert bristow-johnson Apr 27 '18 at 5:12