applied mathematics

DSP Filter to generate Fibonacci numbers

Nalin PithwaLeave a comment

The title is slight misnomer; but I am presenting below is a closed form expression for the nth term of the Fibonacci sequence.

Reference: Digital Signal Processing by Proakis and Manolakis, Sixth Edition.

The one-sided z-transform is a very efficient tool for the solution of difference equations with nonzero intial conditions. It achieves that by reducing the difference equation relating the two time-domain signals to an equivalent algebraic equation relating their one-sided z-transforms. This equation can be easily solved to obtain the transform of the desired signal. The signal in the time domain is obtained by inverting the resulting z-transform. For instance:

Example: The well-known Fibonacci sequence of integers is obtained by computing each term as the sum of the two-previous ones. The first few terms of the sequence are: 1,1,2,3,5, 8, \ldots

Determine a closed form expression for the nth term of the Fibonacci sequence.

Solution: Let y(n) be the nth term of the Fibonacci sequence. Clearly, y(n) satisfies the difference equation:

y(n) = y(n-1) + y(n-2)…..Equation A

with initial conditions

y(0)=y(-1)+y(-2)=1…..B

y(1)=y(0)+y(-1)=1….C

From the above, y(-1)=0 and y(-2)=1. Thus, we have to determine y(n) for n \geq 0, which satisfies equation A with initial conditions y(-1)=0 and y(-2)=1.

By taking the one-sided z-transform of the equation A and using the shifting property, we obtain:

Y^{+}(z) = (z^{-1}Y^{+}(z)+y(-1))+(z^{-1}Y^{+}(z)+y(-2)+y(-1)z^{-1})

or Y^{+}(z) = \frac{1}{1-z^{-1}-z^{2}} = \frac{z^{2}}{z^{2}-z-1}….equation D

where we have used the fact that y(-1)=0 and y(-2)=1.

We can invert Y^{+}(z) by the partial fraction expansion method. The poles of Y^{+}(z) are:

p_{1} = \frac{1+\sqrt{5}}{2}, and p_{2} = \frac{1-\sqrt{5}}{2}

and the corresponding coefficients are A_{1} = \frac{p_{1}}{\sqrt{5}} and A_{2}=\frac{-p_{1}}{\sqrt{5}}. Therefore,

y(n) = (\frac{1+\sqrt{5}}{2\sqrt{5}})(\frac{1+\sqrt{5}}{2})^{n}u(n) - \frac{1-\sqrt{5}}{2\sqrt{5}}(\frac{1-\sqrt{5}}{2})^{n}u(n)

or, equivalently,

y(n) = \frac{1}{\sqrt{5}}(\frac{1}{2})^{n+1}((1+\sqrt{5})^{n+1}-(1-\sqrt{5})^{n+1})u(n).

One smallish comment: We can implement a difference equation of a filter as either FIR or IIR. Of course, based on the physical nature of the signal/processing, one or the other might be preferable.

Regards,

Nalin Pithwa.