Signals occur in a wide range of physical phenomenon. They might be human speech, blood pressure variations with time, seismic waves, radar and sonar signals, pictures or images, stress and strain signals in a building structure, stock market prices, a city's population, or temperature across a plate. These signals are often modeled or represented by a real or complex valued mathematical function of one or more variables. For example, speech is modeled by a function representing air pressure varying with time. The function is acting as a mathematical analogy to the speech signal and, therefore, is called an analog signal. For these signals, the independent variable is time and it changes continuously so that the term continuous-time signal is also used. In our discussion, we talk of the mathematical function as the signal even though it is really a model or representation of the physical signal. The description of signals in terms of their sinusoidal frequency content has proven to be one of the most powerful tools of continuous and discrete-time signal description, analysis, and processing. For that reason, we will start the discussion of signals with a development of Fourier transform methods. We will first review the continuous-time methods of the Fourier series (FS), the Fourier transform or integral (FT), and the Laplace transform (LT). Next the discrete-time methods will be developed in more detail with the discrete Fourier transform (DFT) applied to finite length signals followed by the discrete-time Fourier transform (DTFT) for infinitely long signals and ending with the Z-transform which allows the powerful tools of complex variable theory to be applied. More recently, a new tool has been developed for the analysis of signals. Wavelets and wavelet transforms , , , , are another more flexible expansion system that also can describe continuous and discrete-time, finite or infinite duration signals. We will very briefly introduce the ideas behind wavelet-based signal analysis.

The Fourier Series The problem of expanding a finite length signal in a trigonometric series was posed and studied in the late 1700's by renowned mathematicians such as Bernoulli, d'Alembert, Euler, Lagrange, and Gauss. Indeed, what we now call the Fourier series and the formulas for the coefficients were used by Euler in 1780. However, it was the presentation in 1807 and the paper in 1822 by Fourier stating that an arbitrary function could be represented by a series of sines and cosines that brought the problem to everyone's attention and started serious theoretical investigations and practical applications that continue to this day , , , , , . The theoretical work has been at the center of analysis and the practical applications have been of major significance in virtually every field of quantitative science and technology. For these reasons and others, the Fourier series is worth our serious attention in a study of signal processing.

Definition of the Fourier Series We assume that the signal x(t) to be analyzed is well described by a real or complex valued function of a real variable t defined over a finite interval {0≤t≤T}. The trigonometric series expansion of x(t) is given by x ( t ) = a ( 0 ) 2 + ∑ k = 1 ∞ a ( k ) cos ( 2 π T k t ) + b ( k ) sin ( 2 π T k t ) . where xk(t)=cos(2πkt/T) and yk(t)=sin(2πkt/T) are the basis functions for the expansion. The energy or power in an electrical, mechanical, etc. system is a function of the square of voltage, current, velocity, pressure, etc. For this reason, the natural setting for a representation of signals is the Hilbert space of L2[0,T]. This modern formulation of the problem is developed in , . The sinusoidal basis functions in the trigonometric expansion form a complete orthogonal set in L2[0,T]. The orthogonality is easily seen from inner products ( cos ( 2 π T k t ) , cos ( 2 π T ℓ t ) ) = ∫ 0 T ( cos ( 2 π T k t ) cos ( 2 π T ℓ t ) ) d t = δ ( k - ℓ ) and ( cos ( 2 π T k t ) , sin ( 2 π T ℓ t ) ) = ∫ 0 T ( cos ( 2 π T k t ) sin ( 2 π T ℓ t ) ) d t = 0 where δ(t) is the Kronecker delta function with δ(0)=1 and δ(k≠0)=0. Because of this, the kth coefficients in the series can be found by taking the inner product of x(t) with the kth basis functions. This gives for the coefficients a ( k ) = 2 T ∫ 0 T x ( t ) cos ( 2 π T k t ) d t and b ( k ) = 2 T ∫ 0 T x ( t ) sin ( 2 π T k t ) d t where T is the time interval of interest or the period of a periodic signal. Because of the orthogonality of the basis functions, a finite Fourier series formed by truncating the infinite series is an optimal least squared error approximation to x(t). If the finite series is defined by x ^ ( t ) = a ( 0 ) 2 + ∑ k = 1 N a ( k ) cos ( 2 π T k t ) + b ( k ) sin ( 2 π T k t ) , the squared error is ε = 1 T ∫ 0 T | x ( t ) - x ^ ( t ) | 2 d t which is minimized over all a(k) and b(k) by () and (). This is an extraordinarily important property. It follows that if x(t)∈L2[0,T], then the series converges to x(t) in the sense that ε→0 as N→∞, . The question of point-wise convergence is more difficult. A sufficient condition that is adequate for most application states: If f(x) is bounded, is piece-wise continuous, and has no more than a finite number of maxima over an interval, the Fourier series converges point-wise to f(x) at all points of continuity and to the arithmetic mean at points of discontinuities. If f(x) is continuous, the series converges uniformly at all points , , . A useful condition , states that if x(t) and its derivatives through the qth derivative are defined and have bounded variation, the Fourier coefficients a(k) and b(k) asymptotically drop off at least as fast as 1kq+1 as k→∞. This ties global rates of convergence of the coefficients to local smoothness conditions of the function. The form of the Fourier series using both sines and cosines makes determination of the peak value or of the location of a particular frequency term difficult. A different form that explicitly gives the peak value of the sinusoid of that frequency and the location or phase shift of that sinusoid is given by x ( t ) = d ( 0 ) 2 + ∑ k = 1 ∞ d ( k ) cos ( 2 π T k t + θ ( k ) ) and, using Euler's relation and the usual electrical engineering notation of j=-1, e j x = cos ( x ) + j sin ( x ) , the complex exponential form is obtained as x ( t ) = ∑ k = - ∞ ∞ c ( k ) e j 2 π T k t where c ( k ) = a ( k ) + j b ( k ) . The coefficient equation is c ( k ) = 1 T ∫ 0 T x ( t ) e - j 2 π T k t d t The coefficients in these three forms are related by | d | 2 = | c | 2 = a 2 + b 2 and θ = a r g { c } = tan - 1 ( b a ) It is easier to evaluate a signal in terms of c(k) or d(k) and θ(k) than in terms of a(k) and b(k). The first two are polar representation of a complex value and the last is rectangular. The exponential form is easier to work with mathematically. Although the function to be expanded is defined only over a specific finite region, the series converges to a function that is defined over the real line and is periodic. It is equal to the original function over the region of definition and is a periodic extension outside of the region. Indeed, one could artificially extend the given function at the outset and then the expansion would converge everywhere.

A Geometric View It can be very helpful to develop a geometric view of the Fourier series where x(t) is considered to be a vector and the basis functions are the coordinate or basis vectors. The coefficients become the projections of x(t) on the coordinates. The ideas of a measure of distance, size, and orthogonality are important and the definition of error is easy to picture. This is done in , , using Hilbert space methods.

Properties of the Fourier Series The properties of the Fourier series are important in applying it to signal analysis and to interpreting it. The main properties are given here using the notation that the Fourier series of a real valued function x(t) over {0≤t≤T} is given by F{x(t)}=c(k) and x˜(t) denotes the periodic extensions of x(t). Linear: F{x+y}=F{x}+F{y} Idea of superposition. Also scalability: F{ax}=aF{x} Extensions of x(t): x˜(t)=x˜(t+T)x˜(t) is periodic. Even and Odd Parts: x(t)=u(t)+jv(t) and C(k)=A(k)+jB(k)=|C(k)|ejθ(k)uvAB|C|θeven0even0even0odd00oddeven00even0evenevenπ/20oddodd0evenπ/2

Convolution: If continuous cyclic convolution is defined by y(t)=h(t)∘x(t)=∫0Th˜(t-τ)x˜(τ)dτ then F{h(t)∘x(t)}=F{h(t)}F{x(t)} Multiplication: If discrete convolution is defined by e(n)=d(n)*c(n)=∑m=-∞∞d(m)c(n-m) then F{h(t)x(t)}=F{h(t)}*F{x(t)} This property is the inverse of property 4 and vice versa. Parseval: 1T∫0T|x(t)|2dt=∑k=-∞∞|C(k)|2 This property says the energy calculated in the time domain is the same as that calculated in the frequency (or Fourier) domain. Shift: F{x˜(t-t0)}=C(k)e-j2πt0k/T A shift in the time domain results in a linear phase shift in the frequency domain. Modulate: F{x(t)ej2πKt/T}=C(k-K) Modulation in the time domain results in a shift in the frequency domain. This property is the inverse of property 7. Orthogonality of basis functions: ∫0Te-j2πmt/Tej2πnt/Tdt=Tδ(n-m)=Tifn=m0ifn≠m. Orthogonality allows the calculation of coefficients using inner products in () and (). It also allows Parseval's Theorem in property 6. A relaxed version of orthogonality is called “tight frames" and is important in over-specified systems, especially in wavelets.

Examples An example of the Fourier series is the expansion of a square wave signal with period 2π. The expansion is x(t)=4π[sin(t)+13sin(3t)+15sin(5t)⋯]. Because x(t) is odd, there are no cosine terms (all a(k)=0) and, because of its symmetries, there are no even harmonics (even k terms are zero). The function is well defined and bounded; its derivative is not, therefore, the coefficients drop off as 1k. A second example is a triangle wave of period 2π. This is a continuous function where the square wave was not. The expansion of the triangle wave is x(t)=4π[sin(t)-132sin(3t)+152sin(5t)+⋯]. Here the coefficients drop off as 1k2 since the function and its first derivative exist and are bounded. Note the derivative of a triangle wave is a square wave. Examine the series coefficients to see this. There are many books and web sites on the Fourier series that give insight through examples and demos.

Theorems on the Fourier Series Four of the most important theorems in the theory of Fourier analysis are the inversion theorem, the convolution theorem, the differentiation theorem, and Parseval's theorem . The inversion theorem is the truth of the transform pair given in (), (), and().. The convolution theorem is property 4. The differentiation theorem says that the transform of the derivative of a function is jω times the transform of the function. Parseval's theorem is given in property 6. All of these are based on the orthogonality of the basis function of the Fourier series and integral and all require knowledge of the convergence of the sums and integrals. The practical and theoretical use of Fourier analysis is greatly expanded if use is made of distributions or generalized functions (e.g. Dirac delta functions, δ(t)) , . Because energy is an important measure of a function in signal processing applications, the Hilbert space of L2 functions is a proper setting for the basic theory and a geometric view can be especially useful , . The following theorems and results concern the existence and convergence of the Fourier series and the discrete-time Fourier transform . Details, discussions and proofs can be found in the cited references. If f(x) has bounded variation in the interval (-π,π), the Fourier series corresponding to f(x) converges to the value f(x) at any point within the interval, at which the function is continuous; it converges to the value 12[f(x+0)+f(x-0)] at any such point at which the function is discontinuous. At the points π,-π it converges to the value 12[f(-π+0)+f(π-0)]. If f(x) is of bounded variation in (-π,π), the Fourier series converges to f(x), uniformly in any interval (a,b) in which f(x) is continuous, the continuity at a and b being on both sides. If f(x) is of bounded variation in (-π,π), the Fourier series converges to 12[f(x+0)+f(x-0)], bounded throughout the interval (-π,π). If f(x) is bounded and if it is continuous in its domain at every point, with the exception of a finite number of points at which it may have ordinary discontinuities, and if the domain may be divided into a finite number of parts, such that in any one of them the function is monotone; or, in other words, the function has only a finite number of maxima and minima in its domain, the Fourier series of f(x) converges to f(x) at points of continuity and to 12[f(x+0)+f(x-0)] at points of discontinuity. , If f(x) is such that, when the arbitrarily small neighborhoods of a finite number of points in whose neighborhood |f(x)| has no upper bound have been excluded, f(x) becomes a function with bounded variation, then the Fourier series converges to the value 12[f(x+0)+f(x-0)], at every point in (-π,π), except the points of infinite discontinuity of the function, provided the improper integral ∫-ππf(x)dx exist, and is absolutely convergent. If f is of bounded variation, the Fourier series of f converges at every point x to the value [f(x+0)+f(x-0)]/2. If f is, in addition, continuous at every point of an interval I=(a,b), its Fourier series is uniformly convergent in I. If a(k) and b(k) are absolutely summable, the Fourier series converges uniformly to f(x) which is continuous. If a(k) and b(k) are square summable, the Fourier series converges to f(x) where it is continuous, but not necessarily uniformly. Suppose that f(x) is periodic, of period X, is defined and bounded on [0,X] and that at least one of the following four conditions is satisfied: (i) f is piecewise monotonic on [0,X], (ii) f has a finite number of maxima and minima on [0,X] and a finite number of discontinuities on [0,X], (iii) f is of bounded variation on [0,X], (iv) f is piecewise smooth on [0,X]: then it will follow that the Fourier series coefficients may be defined through the defining integral, using proper Riemann integrals, and that the Fourier series converges to f(x) at a.a.x, to f(x) at each point of continuity of f, and to the value 12[f(x-)+f(x+)] at all x. For any 1≤p<∞ and any f∈Cp(S1), the partial sums Sn=Sn(f)=∑|k|≤nf^(k)ek converge to f, uniformly as n→∞; in fact, ||Sn-f||∞ is bounded by a constant multiple of n-p+1/2. The Fourier series expansion results in transforming a periodic, continuous time function, x˜(t), to two discrete indexed frequency functions, a(k) and b(k) that are not periodic.

The Fourier Transform Many practical problems in signal analysis involve either infinitely long or very long signals where the Fourier series is not appropriate. For these cases, the Fourier transform (FT) and its inverse (IFT) have been developed. This transform has been used with great success in virtually all quantitative areas of science and technology where the concept of frequency is important. While the Fourier series was used before Fourier worked on it, the Fourier transform seems to be his original idea. It can be derived as an extension of the Fourier series by letting the length or period T increase to infinity or the Fourier transform can be independently defined and then the Fourier series shown to be a special case of it. The latter approach is the more general of the two, but the former is more intuitive , .

Definition of the Fourier Transform The Fourier transform (FT) of a real-valued (or complex) function of the real-variable t is defined by X ( ω ) = ∫ - ∞ ∞ x ( t ) e - j ω t d t giving a complex valued function of the real variable ω representing frequency. The inverse Fourier transform (IFT) is given by x ( t ) = 1 2 π ∫ - ∞ ∞ X ( ω ) e j ω t d ω . Because of the infinite limits on both integrals, the question of convergence is important. There are useful practical signals that do not have Fourier transforms if only classical functions are allowed because of problems with convergence. The use of delta functions (distributions) in both the time and frequency domains allows a much larger class of signals to be represented .

Properties of the Fourier Transform The properties of the Fourier transform are somewhat parallel to those of the Fourier series and are important in applying it to signal analysis and interpreting it. The main properties are given here using the notation that the FT of a real valued function x(t) over all time t is given by F{x}=X(ω). Linear: F{x+y}=F{x}+F{y} Even and Oddness: if x(t)=u(t)+jv(t) and X(ω)=A(ω)+jB(ω) then uvAB|X|θeven0even0even0odd00oddeven00even0evenevenπ/20oddodd0evenπ/2

Convolution: If continuous convolution is defined by: y(t)=h(t)*x(t)=∫-∞∞h(t-τ)x(τ)dτ=∫-∞∞h(λ)x(t-λ)dλ then F{h(t)*x(t)}=F{h(t)}F{x(t)} Multiplication: F{h(t)x(t)}=12πF{h(t)}*F{x(t)} Parseval: ∫-∞∞|x(t)|2dt=12π∫-∞∞|X(ω)|2dω Shift: F{x(t-T)}=X(ω)e-jωT Modulate: F{x(t)ej2πKt}=X(ω-2πK) Derivative: F{dxdt}=jωX(ω) Stretch: F{x(at)}=1|a|X(ω/a) Orthogonality: ∫-∞∞e-jω1tejω2t=2πδ(ω1-ω2)

Examples of the Fourier Transform Deriving a few basic transforms and using the properties allows a large class of signals to be easily studied. Examples of modulation, sampling, and others will be given. If x(t)=δ(t) then X(ω)=1 If x(t)=1 then X(ω)=2πδ(ω) If x(t) is an infinite sequence of delta functions spaced T apart, x(t)=∑n=-∞∞δ(t-nT), its transform is also an infinite sequence of delta functions of weight 2π/T spaced 2π/T apart, X(ω)=2π∑k=-∞∞δ(ω-2πk/T). Other interesting and illustrative examples can be found in , . Note the Fourier transform takes a function of continuous time into a function of continuous frequency, neither function being periodic. If “distribution" or “delta functions" are allowed, the Fourier transform of a periodic function will be a infinitely long string of delta functions with weights that are the Fourier series coefficients.

The Laplace Transform The Laplace transform can be thought of as a generalization of the Fourier transform in order to include a larger class of functions, to allow the use of complex variable theory, to solve initial value differential equations, and to give a tool for input-output description of linear systems. Its use in system and signal analysis became popular in the 1950's and remains as the central tool for much of continuous time system theory. The question of convergence becomes still more complicated and depends on complex values of s used in the inverse transform which must be in a “region of convergence" (ROC).

Definition of the Laplace Transform The definition of the Laplace transform (LT) of a real valued function defined over all positive time t is F ( s ) = ∫ - ∞ ∞ f ( t ) e - s t d t and the inverse transform (ILT) is given by the complex contour integral f ( t ) = 1 2 π j ∫ c - j ∞ c + j ∞ F ( s ) e s t d s where s=σ+jω is a complex variable and the path of integration for the ILT must be in the region of the s plane where the Laplace transform integral converges. This definition is often called the bilateral Laplace transform to distinguish it from the unilateral transform (ULT) which is defined with zero as the lower limit of the forward transform integral (). Unless stated otherwise, we will be using the bilateral transform. Notice that the Laplace transform becomes the Fourier transform on the imaginary axis, for s=jω. If the ROC includes the jω axis, the Fourier transform exists but if it does not, only the Laplace transform of the function exists. There is a considerable literature on the Laplace transform and its use in continuous-time system theory. We will develop most of these ideas for the discrete-time system in terms of the z-transform later in this chapter and will only briefly consider only the more important properties here. The unilateral Laplace transform cannot be used if useful parts of the signal exists for negative time. It does not reduce to the Fourier transform for signals that exist for negative time, but if the negative time part of a signal can be neglected, the unilateral transform will converge for a much larger class of function that the bilateral transform will. It also makes the solution of linear, constant coefficient differential equations with initial conditions much easier.

Properties of the Laplace Transform Many of the properties of the Laplace transform are similar to those for Fourier transform , , however, the basis functions for the Laplace transform are not orthogonal. Some of the more important ones are: Linear: L{x+y}=L{x}+L{y} Convolution: If y(t)=h(t)*x(t)=∫h(t-τ)x(τ)dτ then L{h(t)*x(t)}=L{h(t)}L{x(t)} Derivative: L{dxdt}=sL{x(t)} Derivative (ULT): L{dxdt}=sL{x(t)}-x(0) Integral: L{∫x(t)dt}=1sL{x(t)} Shift: L{x(t-T)}=C(k)e-Ts Modulate: L{x(t)ejω0t}=X(s-jω0) Examples can be found in , and are similar to those of the z-transform presented later in these notes. Indeed, note the parallals and differences in the Fourier series, Fourier transform, and Z-transform.