Author: Nalin Pithwa

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.

The significance of Signals and Systems or Mathematical Systems Theory

Nalin PithwaLeave a comment

Based almost completely on preface of the classic text: Signals and Systems by Oppenheim and Willsky (later editions coauthor Nawab also).

In the beginning there was light….Light is a signal…Electricity also creates electro magnetic waves in the copper medium though the drift velocity of the electrons in a conducting material like copper is v v low …

Guglielmo Marconi discovered radio waves/signals…

Let us review the synopsis of Signals and Systems as explained long back by Prof Oppenheim, MIT. You might be surprised how much integral the concepts of signals and systems and mathematical systems theory are to AI, embedded vision/computer vision, robotics etc.

Without further ado, here we go:

The concepts of signals and systems arise in a wide a variety of fields, and the ideas and techniques associated with these concepts play an important role in such diverse areas of science and technology such as communications, aeronautics and astronautics, circuit design, acoustics, seismology, biomedical engineering, energy generation and distribution in systems, chemical process control, and speech processing. Although the physical nature of the signals and systems that arise in these various disciplines may be drastically different, they all have two very basic features in common. The signals, which are functions of one or more independent variables, contain information about the nature or behaviour of some phenomenon, whereas the systems respond to particular signals by producing other signals or some desired behaviour. Voltages and currents as a function of time in an electrical circuit are examples of signals, and the circuit itself is an example of a system, which in this case responds to applied voltages and currents. As another example, when an automobile driver depresses the accelerator pedal, the automobile responds by increasing the speed of the vehicle. In this case, the system is the automobile, the pressure on the accelerator pedal the input the system, and the automobile speed the response. A computer program for the automated diagnosis of electrodiagrams can be viewed as a system which has its input digitized electrodiagram and produces of estimates of parameters such as heartbeats as outputs. A camera is a system that receives light from different sources and reflected from objects and produces a photograph. A robot arm is a system whose movements are the responses to control inputs.

In the many contexts in which signals and systems arise, there are a variety of questions and problems that are of importance.In some cases, we are presented with a specific system and are interested in charactering it in detail to understand how it will respond to various inputs. Examples include the analysis of a circuit in order to quantify its response to different voltage and current sources and the determination of an aircraft’s response characteristics both to pilot commands and to wind gusts.

In other problems of signal and system analysis, rather than analyzing existing systems, our interest may be focused on designing systems to process signals in particular ways. One very common context in which such problems arise is in teh design of systems to enhance or restore signals that have been degraded in some way. For example, when a pilot is communicating with an airtraffic control tower, the communication can be degraded by the high level of background noise in the cockpit. In this and many similar cases, it is possible to design systems that will retain the desired signal, in this case, the pilot’s voice and reject (at least approximately) the unwanted noise signals. A similar set of objectives can also be found in the general area of image restoration and image enhancement. For example, images from deep space probes or earth observing satellites typically represent degraded versions of the scenes being imaged because of limitations of the imaging equipment, atmospheric effects, and errors in signal transmission in returning the images to earth. Consequently, images returned from space are routinely processed by systems to compensate for some of these degradations. In addition, such images are usually processed to enhance certain features, such as lines (corresponding, for example, to river beds or faults) or regional boundaries in which there are sharp contrasts in colour or darkness.

In addition to enhancement and restoration, in many applications there is a need to design systems to extract specific pieces of information from signals. The estimation of heart rate from an electrocardiogram is an example. Another arises in economic forecasting. We may, for example, wish to analyze the history of an economic time series, such as a set of stock market averages, in order to estimate trends and other characteristics such as seasonal variations that may be of use in making predictions about future behaviour. in other applications, the focus may be on the design of signals with particular properties. Specifically, in communications applications, consideratble attention is paid to design signals to meet the constraints and requirements of successful transmission. For example, long distance communication through the atmosphere requires the use of signals with frequencies in a particular part of the electromagnetic spectrum. The design of communication signals must also take into account the need for reliable reception in the presence of both distortion due to transmission by atmosphere and interference from other signals being transmitted simultaneously by other users.

Another very important class of applications in which the concepts and techniques of signals and systems arise are those in which we wish to modify or control the characteristics of a given system, perhaps through the choice of specific input signals or by combining the system with other systems. Illustrative of this kind of application is the design of control systems to regulate chemical processing plants. Plants of this type are equipped with a variety of sensors that measure physical signals such as temperature, pressure, humidity, and chemical composition. The control system in such a plant responds to these sensor signals by adjusting parameters such as flow rates and temperatures in order to regulate the ongoing chemical processes. The design of aircraft autopilots and computer control systems represents another example. In this case, signals measuring aircraft speed, altitude and heading are used by the aircraft’s control system in order to adjust the variables such as throttle setting and the positions of the rudder and ailerons. These adjustments are made to ensure that the aircraft follows a specified course, to smooth out the aircraft’s ride, and to enhance its responsiveness to pilot’s commands. In both this case and the previous example of chemical process control, an important concept, referred to as feedback, plays a major role,as measured signals are fed back and used to adjust the response characteristics of a system.

The examples in the preceding paragraphs represent only a few of an extraordinarily wide variety of applications for the concepts of signals and systems. The importance of these concepts stems not only from the diversity of phenomena and processes in which they arise, but also from the collection of ideas, analytical techniques, and methodologies that have been and are being developed and used to solve problems involving signals and systems. The history of this development extends back over many centuries, and although most of this work was motivated by specific applications, many of these ideas have proven to be of central importance to problems in a far larger variety of contexts than those for which they were originally intended. For example, the tools of Fourier analysis, which form the basis for the frequency domain analysis of signals and systems can be traced from problems of astronomy studied by ancient Babylonians to the development of mathematical physics in the eighteenth and nineteenth centuries.

In some of the examples that we have mentioned, the signals vary continuously in time, whereas in others, their evolution is described only in discrete points in time. For example, in the analysis of electrical circuits and mechanical systems we are concerned with signals that vary continuously. On the other hand the daily closing stock market average is by its very nature a signal that evolves over discrete points in time (that is, at the close of each day.) Rather than a curve as a function of a continuous variable, then, the closing stock market average is a sequence of numbers associated with the discrete time instants at which it is specified. This distinction is the basic description of the evolution of signals and of the systems that respond to or process these signals naturally lead to two parallel frameworks for signals and systems analysis, one for phenomena and processes that are described in continuous time and one for those that are described in discrete-time.

The concepts and techniques associated both with continuous-time signals and systems and with discrete-time signals and systems have a rich history and are conceptually closely related. Historically, however, because their applications have in the past been sufficiently different, they have for the most part been studied and developed somewhat separately. Continuous-time signals and systems have very strong roots in problems associated with physics and, then later, with electrical circuits and communications systems. The techniques of discrete-time signals have strong roots in numerical analysis, statistics, time-series analysis associated with such applications as the analysis of economic and demographic data. Over the past several decades, however, the disciplines of continuous-time and discrete-time signals and systems have become increasingly intertwined and the applications have become highly interrelated. The major impetus for this came from the dramatic advances in technology for the implementation of systems and the generation of signals. Specifically, the rapid development of high speed digital computers, integrated circuits, DSPs, microprocessors and sophisticated high speed device fabrication techniques made it increasingly advantageous to consider processing of continuous time signals by sampling them (that is, considering their discrete time samples). As one example, the computer control system for a modern aircraft digitizes sensor outputs such as vehicle speed in order to produce a sequence of sampled measurements which are then processed by the control system.

Hence, it has been possible to develop the theory of discrete-time signals and systems in paralled with the theory of continuous-time signals and systems and also to compare the techniques and results.

Cheers,

Nalin Pithwa