Although the discrete-time signal x(n) could be any ordered sequence of numbers, they are usually samples of a continuous-time signal. In this case, the real or imaginary valued mathematical function x(n) of the integer n is not used as an analogy of a physical signal, but as some representation of it (such as samples). In some cases, the term digital signal is used interchangeably with discrete-time signal, or the label digital signal may be use if the function is not real valued but takes values consistent with some hardware system. Indeed, our very use of the term “discrete-time" indicates the probable origin of the signals when, in fact, the independent variable could be length or any other variable or simply an ordering index. The term “digital" indicates the signal is probably going to be created, processed, or stored using digital hardware. As in the continuous-time case, the Fourier transform will again be our primary tool , , . Notation has been an important element in mathematics. In some cases, discrete-time signals are best denoted as a sequence of values, in other cases, a vector is created with elements which are the sequence values. In still other cases, a polynomial is formed with the sequence values as coefficients for a complex variable. The vector formulation allows the use of linear algebra and the polynomial formulation allows the use of complex variable theory.

The Discrete Fourier Transform The description of signals in terms of their sinusoidal frequency content has proven to be as powerful and informative for discrete-time signals as it has for continuous-time signals. It is also probably the most powerful computational tool we will use. We now develop the basic discrete-time methods starting 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 uses the powerful tools of complex variable theory.

Definition of the DFT It is assumed that the signal x(n) to be analyzed is a sequence of N real or complex values which are a function of the integer variable n. The DFT of x(n), also called the spectrum of x(n), is a length N sequence of complex numbers denoted C(k) and defined by C ( k ) = ∑ n = 0 N - 1 x ( n ) e - j 2 π N n k using the usual engineering notation: j=-1. The inverse transform (IDFT) which retrieves x(n) from C(k) is given by x ( n ) = 1 N ∑ k = 0 N - 1 C ( k ) e j 2 π N n k which is easily verified by substitution into (1). Indeed, this verification will require using the orthogonality of the basis function of the DFT which is ∑ k = 0 N - 1 e - j 2 π N m k e j 2 π N n k = N if n = m 0 if n ≠ m . The exponential basis functions, e-j2πNk, for k∈{0,N-1}, are the N values of the Nth roots of unity (the N zeros of the polynomial (s-1)N). This property is what connects the DFT to convolution and allows efficient algorithms for calculation to be developed . They are used so often that the following notation is defined by W N = e - j 2 π N with the subscript being omitted if the sequence length is obvious from context. Using this notation, the DFT becomes C ( k ) = ∑ n = 0 N - 1 x ( n ) W N n k One should notice that with the finite summation of the DFT, there is no question of convergence or of the ability to interchange the order of summation. No “delta functions” are needed and the N transform values can be calculated exactly (within the accuracy of the computer or calculator used) from the N signal values with a finite number of arithmetic operations.

Matrix Formulation of the DFT There are several advantages to using a matrix formulation of the DFT. This is given by writing () or () in matrix operator form as C 0 C 1 C 2 ⋮ C N - 1 = W 0 W 0 W 0 ⋯ W 0 W 0 W 1 W 2 W 0 W 2 W 4 ⋮ ⋮ W 0 ⋯ W ( N - 1 ) ( N - 1 ) x 0 x 1 x 2 ⋮ x N - 1 or C = Fx . The orthogonality of the basis function in () shows up in this matrix formulation by the columns of F being orthogonal to each other as are the rows. This means that FTF=kI, where k is a scalar constant, and, therefore, FT=kF-1. This is called a unitary operator. The definition of the DFT in () emphasizes the fact that each of the N DFT values are the sum of N products. The matrix formulation in () has two interpretations. Each k-th DFT term is the inner product of two vectors, k-th row of F and x; or, the DFT vector, C is a weighted sum of the N columns of F with weights being the elements of the signal vector x. A third view of the DFT is the operator view which is simply the single matrix equation (). It is instructive at this point to write a computer program to calculate the DFT of a signal. In Matlab , there is a pre-programmed function to calculate the DFT, but that hides the scalar operations. One should program the transform in the scalar interpretive language of Matlab or some other lower level language such as FORTRAN, C, BASIC, Pascal, etc. This will illustrate how many multiplications and additions and trigonometric evaluations are required and how much memory is needed. Do not use a complex data type which also hides arithmetic, but use Euler's relations e j x = cos ( x ) + j sin ( x ) to explicitly calculate the real and imaginary part of C(k). If Matlab is available, first program the DFT using only scalar operations. It will require two nested loops and will run rather slowly because the execution of loops is interpreted. Next, program it using vector inner products to calculate each C(k) which will require only one loop and will run faster. Finally, program it using a single matrix multiplication requiring no loops and running much faster. Check the memory requirements of the three approaches. The DFT and IDFT are a completely well-defined, legitimate transform pair with a sound theoretical basis that do not need to be derived from or interpreted as an approximation to the continuous-time Fourier series or integral. The discrete-time and continuous-time transforms and other tools are related and have parallel properties, but neither depends on the other. The notation used here is consistent with most of the literature and with the standards given in . The independent index variable n of the signal x(n) is an integer, but it is usually interpreted as time or, occasionally, as distance. The independent index variable k of the DFT C(k) is also an integer, but it is generally considered as frequency. The DFT is called the spectrum of the signal and the magnitude of the complex valued DFT is called the magnitude of that spectrum and the angle or argument is called the phase.

Extensions of Although the finite length signal x(n) is defined only over the interval {0≤n≤(N-1)}, the IDFT of C(k) can be evaluated outside this interval to give well defined values. Indeed, this process gives the periodic property 4. There are two ways of formulating this phenomenon. One is to periodically extend x(n) to -∞ and +∞ and work with this new signal. A second more general way is evaluate all indices n and k modulo N. Rather than considering the periodic extension of x(n) on the line of integers, the finite length line is formed into a circle or a line around a cylinder so that after counting to N-1, the next number is zero, not a periodic replication of it. The periodic extension is easier to visualize initially and is more commonly used for the definition of the DFT, but the evaluation of the indices by residue reduction modulo N is a more general definition and can be better utilized to develop efficient algorithms for calculating the DFT . Since the indices are evaluated only over the basic interval, any values could be assigned x(n) outside that interval. The periodic extension is the choice most consistent with the other properties of the transform, however, it could be assigned to zero . An interesting possibility is to artificially create a length 2N sequence by appending x(-n) to the end of x(n). This would remove the discontinuities of periodic extensions of this new length 2N signal and perhaps give a more accurate measure of the frequency content of the signal with no artifacts caused by “end effects". Indeed, this modification of the DFT gives what is called the discrete cosine transform (DCT) . We will assume the implicit periodic extensions to x(n) with no special notation unless this characteristic is important, then we will use the notation x˜(n).

Convolution Convolution is an important operation in signal processing that is in some ways more complicated in discrete-time signal processing than in continuous-time signal processing and in other ways easier. The basic input-output relation for a discrete-time system is given by so-called linear or non-cyclic convolution defined and denoted by y ( n ) = ∑ m = - ∞ ∞ h ( m ) x ( n - m ) = h ( n ) * x ( n ) where x(n) is the perhaps infinitely long input discrete-time signal, h(n) is the perhaps infinitely long impulse response of the system, and y(n) is the output. The DFT is, however, intimately related to cyclic convolution, not non-cyclic convolution. Cyclic convolution is defined and denoted by y ˜ ( n ) = ∑ m = 0 N - 1 h ˜ ( m ) x ˜ ( n - m ) = h ( n ) ∘ x ( n ) where either all of the indices or independent integer variables are evaluated modulo N or all of the signals are periodically extended outside their length N domains. This cyclic (sometimes called circular) convolution can be expressed as a matrix operation by converting the signal h(n) into a matrix operator as H = h 0 h L - 1 h L - 2 ⋯ h 1 h 1 h 0 h L - 1 h 2 h 1 h 0 ⋮ ⋮ h L - 1 ⋯ h 0 , The cyclic convolution can then be written in matrix notation as Y = H X where X and Y are column matrices or vectors of the input and output values respectively. Because non-cyclic convolution is often what you want to do and cyclic convolution is what is related to the powerful DFT, we want to develop a way of doing non-cyclic convolution by doing cyclic convolution. The convolution of a length N sequence with a length M sequence yields a length N+M-1 output sequence. The calculation of non-cyclic convolution by using cyclic convolution requires modifying the signals by appending zeros to them. This will be developed later.

Properties of the DFT The properties of the DFT are extremely important in applying it to signal analysis and to interpreting it. The main properties are given here using the notation that the DFT of a length-N complex sequence x(n) is F{x(n)}=C(k). Linear Operator: F{x(n)+y(n)}=F{x(n)}+F{y(n)} Unitary Operator: F-1=1NFT Periodic Spectrum: C(k)=C(k+N) Periodic Extensions of x(n): x(n)=x(n+N) Properties of Even and Odd Parts: x(n)=u(n)+jv(n) and C(k)=A(k)+jB(k) uvAB|C|θeven0even0even0odd00oddevenπ/20even0evenevenπ/20oddodd0even0

Cyclic Convolution: F{h(n)∘x(n)}=F{h(n)}F{x(n)} Multiplication: F{h(n)x(n)}=F{h(n)}∘F{x(n)} Parseval: ∑n=0N-1|x(n)|2=1N∑k=0N-1|C(k)|2 Shift: F{x(n-M)}=C(k)e-j2πMk/N Modulate: F{x(n)ej2πKn/N}=C(k-K) Down Sample or Decimate: F{x(Kn)}=1K∑m=0K-1C(k+Lm) where N=LK Up Sample or Stretch: If xs(2n)=x(n) for integer n and zero otherwise, then F{xs(n)}=C(k), for k=0,1,2,...,2N-1 N Roots of Unity: (WNk)N=1 for k=0,1,2,...,N-1 Orthogonality: ∑k=0N-1e-j2πmk/Nej2πnk/N=Nifn=m0ifn≠m. Diagonalization of Convolution: If cyclic convolution is expressed as a matrix operation by y=Hx with H given by (), the DFT operator diagonalizes the convolution operator H, or FTHF=Hd where Hd is a diagonal matrix with the N values of the DFT of h(n) on the diagonal. This is a matrix statement of Property 6. Note the columns of F are the N eigenvectors of H, independent of the values of h(n). One can show that any “kernel" of a transform that would support cyclic, length-N convolution must be the N roots of unity. This says the DFT is the only transform over the complex number field that will support convolution. However, if one considers various finite fields or rings, an interesting transform, called the Number Theoretic Transform, can be defined and used because the roots of unity are simply two raised to a powers which is a simple word shift for certain binary number representations , .

Examples of the DFT It is very important to develop insight and intuition into the DFT or spectral characteristics of various standard signals. A few DFT's of standard signals together with the above properties will give a fairly large set of results. They will also aid in quickly obtaining the DFT of new signals. The discrete-time impulse δ(n) is defined by δ ( n ) = 1 when n = 0 0 otherwise The discrete-time pulse ⊓M(n) is defined by ⊓ M ( n ) = 1 when n = 0 , 1 , ⋯ , M - 1 0 otherwise Several examples are: DFT{δ(n)}=1, The DFT of an impulse is a constant. DFT{1}=Nδ(k), The DFT of a constant is an impulse. D F T { e j 2 π K n / N } = N δ ( k - K ) D F T { cos ( 2 π M n / N ) = N 2 [ δ ( k - M ) + δ ( k + M ) ] D F T { ⊓ M ( n ) } = sin ( π N M k ) sin ( π N k ) These examples together with the properties can generate a still larger set of interesting and enlightening examples. Matlab can be used to experiment with these results and to gain insight and intuition.

The Discrete-Time Fourier Transform In addition to finite length signals, there are many practical problems where we must be able to analyze and process essentially infinitely long sequences. For continuous-time signals, the Fourier series is used for finite length signals and the Fourier transform or integral is used for infinitely long signals. For discrete-time signals, we have the DFT for finite length signals and we now present the discrete-time Fourier transform (DTFT) for infinitely long signals or signals that are longer than we want to specify . The DTFT can be developed as an extension of the DFT as N goes to infinity or the DTFT can be independently defined and then the DFT shown to be a special case of it. We will do the latter.

Definition of the DTFT The DTFT of a possibly infinitely long real (or complex) valued sequence f(n) is defined to be F ( ω ) = ∑ - ∞ ∞ f ( n ) e - j ω n and its inverse denoted IDTFT is given by f ( n ) = 1 2 π ∫ - π π F ( ω ) e j ω n d ω . Verification by substitution is more difficult than for the DFT. Here convergence and the interchange of order of the sum and integral are serious questions and have been the topics of research over many years. Discussions of the Fourier transform and series for engineering applications can be found in , . It is necessary to allow distributions or delta functions to be used to gain the full benefit of the Fourier transform. Note that the definition of the DTFT and IDTFT are the same as the definition of the IFS and FS respectively. Since the DTFT is a continuous periodic function of ω, its Fourier series is a discrete set of values which turn out to be the original signal. This duality can be helpful in developing properties and gaining insight into various problems. The conditions on a function to determine if it can be expanded in a FS are exactly the conditions on a desired frequency response or spectrum that will determine if a signal exists to realize or approximate it.

Properties The properties of the DTFT are similar to those for the DFT and are important in the analysis and interpretation of long signals. The main properties are given here using the notation that the DTFT of a complex sequence x(n) is F{x(n)}=X(ω). Linear Operator: F{x+y}=F{x}+F{y} Periodic Spectrum: X(ω)=X(ω+2π) Properties of Even and Odd Parts: x(n)=u(n)+jv(n) and X(ω)=A(ω)+jB(ω)uvAB|X|θeven0even0even0odd00oddeven00even0evenevenπ/20oddodd0evenπ/2

Convolution: If non-cyclic or linear convolution is defined by: y(n)=h(n)*x(n)=∑m=-∞∞h(n-m)x(m)=∑k=-∞∞h(k)x(n-k) then F{h(n)*x(n)}=F{h(n)}F{x(n)} Multiplication: If cyclic convolution is defined by: Y(ω)=H(ω)∘X(ω)=∫0TH˜(ω-Ω)X˜(Ω)dΩF{h(n)x(n)}=12πF{h(n)}∘F{x(n)} Parseval: ∑n=-∞∞|x(n)|2=12π∫-ππ|X(ω)|2dω Shift: F{x(n-M)}=X(ω)e-jωM Modulate: F{x(n)ejω0n}=X(ω-ω0) Sample: F{x(Kn)}=1K∑m=0K-1X(ω+Lm) where N=LK Stretch: F{xs(n)}=X(ω), for -Kπ≤ω≤Kπ where xs(Kn)=x(n) for integer n and zero otherwise. Orthogonality: ∑n=-∞∞e-jω1ne-jω2n=2πδ(ω1-ω2)

Evaluation of the DTFT by the DFT If the DTFT of a finite sequence is taken, the result is a continuous function of ω. If the DFT of the same sequence is taken, the results are N evenly spaced samples of the DTFT. In other words, the DTFT of a finite signal can be evaluated at N points with the DFT. X ( ω ) = D T F T { x ( n ) } = ∑ n = - ∞ ∞ x ( n ) e - j ω n and because of the finite length X ( ω ) = ∑ n = 0 N - 1 x ( n ) e - j ω n . If we evaluate ω at N equally space points, this becomes X ( 2 π N k ) = ∑ n = 0 N - 1 x ( n ) e - j 2 π N k n which is the DFT of x(n). By adding zeros to the end of x(n) and taking a longer DFT, any density of points can be evaluated. This is useful in interpolation and in plotting the spectrum of a finite length signal. This is discussed further in Chapter4 . There is an interesting variation of the Parseval's theorem for the DTFT of a finite length-N signal. If x(n)≠0 for 0≥n≥N-1, and if L≥N, then ∑ n = 0 N - 1 | x ( n ) | 2 = 1 L ∑ k = 0 L - 1 | X ( 2 π k / L ) | 2 = 1 π ∫ 0 π | X ( ω ) | 2 d ω . The second term in () says the Riemann sum is equal to its limit in this case.

Examples of DTFT As was true for the DFT, insight and intuition is developed by understanding the properties and a few examples of the DTFT. Several examples are given below and more can be found in the literature , , . Remember that while in the case of the DFT signals were defined on the region {0≤n≤(N-1)} and values outside that region were periodic extensions, here the signals are defined over all integers and are not periodic unless explicitly stated. The spectrum is periodic with period 2π. DTFT{δ(n)}=1 for all frequencies. D T F T { 1 } = 2 π δ ( ω ) D T F T { e j ω 0 n } = 2 π δ ( ω - ω 0 ) D T F T { cos ( ω 0 n ) } = π [ δ ( ω - ω 0 ) + δ ( ω + ω 0 ) ] D T F T { ⊓ M ( n ) } = sin ( ω M k / 2 ) sin ( ω k / 2 )

The Z-Transform The z-transform is an extension of the DTFT in a way that is analogous to the Laplace transform for continuous-time signals being an extension of the Fourier transform. It allows the use of complex variable theory and is particularly useful in analyzing and describing systems. The question of convergence becomes still more complicated and depends on values of z used in the inverse transform which must be in the “region of convergence" (ROC).

Definition of the Z-Transform The z-transform (ZT) is defined as a polynomial in the complex variable z with the discrete-time signal values as its coefficients , , . It is given by F ( z ) = ∑ n = - ∞ ∞ f ( n ) z - n and the inverse transform (IZT) is f ( n ) = 1 2 π j ∮ R O C F ( z ) z n - 1 d z . The inverse transform can be derived by using the residue theorem , from complex variable theory to find f(0) from z-1F(z), f(1) from F(z), f(2) from zF(z), and in general, f(n) from zn-1F(z). Verification by substitution is more difficult than for the DFT or DTFT. Here convergence and the interchange of order of the sum and integral is a serious question that involves values of the complex variable z. The complex contour integral in () must be taken in the ROC of the z plane. A unilateral z-transform is sometimes needed where the definition () uses a lower limit on the transform summation of zero. This allow the transformation to converge for some functions where the regular bilateral transform does not, it provides a straightforward way to solve initial condition difference equation problems, and it simplifies the question of finding the ROC. The bilateral z-transform is used more for signal analysis and the unilateral transform is used more for system description and analysis. Unless stated otherwise, we will be using the bilateral z-transform.

Properties The properties of the ZT are similar to those for the DTFT and DFT and are important in the analysis and interpretation of long signals and in the analysis and description of discrete-time systems. The main properties are given here using the notation that the ZT of a complex sequence x(n) is Z{x(n)}=X(z). Linear Operator: Z{x+y}=Z{x}+Z{y} Relationship of ZT to DTFT: Z{x}|z=ejω=DTFT{x} Periodic Spectrum: X(ejω)=X(ejω+2π) Properties of Even and Odd Parts: x(n)=u(n)+jv(n) and X(ejω)=A(ejω)+jB(ejω)uvABeven0even0odd00odd0even0even0oddodd0 Convolution: If discrete non-cyclic convolution is defined by y(n)=h(n)*x(n)=∑m=-∞∞h(n-m)x(m)=∑k=-∞∞h(k)x(n-k) then Z{h(n)*x(n)}=Z{h(n)}Z{x(n)} Shift: Z{x(n+M)}=zMX(z) Shift (unilateral): Z{x(n+m)}=zmX(z)-zmx(0)-zm-1x(1)-⋯-zx(m-1) Shift (unilateral): Z{x(n-m)}=z-mX(z)-z-m+1x(-1)-⋯-x(-m) Modulate: Z{x(n)an}=X(z/a) Time mult.: Z{nmx(n)}=(-z)mdmX(z)dzm Evaluation: The ZT can be evaluated on the unit circle in the z-plane by taking the DTFT of x(n) and if the signal is finite in length, this can be evaluated at sample points by the DFT.

Examples of the Z-Transform A few examples together with the above properties will enable one to solve and understand a wide variety of problems. These use the unit step function to remove the negative time part of the signal. This function is defined as u ( n ) = 1 if n ≥ 0 0 if n < 0 and several bilateral z-transforms are given by Z{δ(n)}=1 for all z. Z{u(n)}=zz-1 for |z|>1. Z{u(n)an}=zz-a for |z|>|a|. Notice that these are similar to but not the same as a term of a partial fraction expansion.

Inversion of the Z-Transform The z-transform can be inverted in three ways. The first two have similar procedures with Laplace transformations and the third has no counter part. The z-transform can be inverted by the defined contour integral in the ROC of the complex z plane. This integral can be evaluated using the residue theorem , . The z-transform can be inverted by expanding 1zF(z) in a partial fraction expansion followed by use of tables for the first or second order terms. The third method is not analytical but numerical. If F(z)=P(z)Q(z), f(n) can be obtained as the coefficients of long division. For example z z - a = 1 + a z - 1 + a 2 z - 2 + ⋯ which is u(n)an as used in the examples above. We must understand the role of the ROC in the convergence and inversion of the z-transform. We must also see the difference between the one-sided and two-sided transform.

Solution of Difference Equations using the Z-Transform The z-transform can be used to convert a difference equation into an algebraic equation in the same manner that the Laplace converts a differential equation in to an algebraic equation. The one-sided transform is particularly well suited for solving initial condition problems. The two unilateral shift properties explicitly use the initial values of the unknown variable. A difference equation DE contains the unknown function x(n) and shifted versions of it such as x(n-1) or x(n+3). The solution of the equation is the determination of x(t). A linear DE has only simple linear combinations of x(n) and its shifts. An example of a linear second order DE is a x ( n ) + b x ( n - 1 ) + c x ( n - 2 ) = f ( n ) A time invariant or index invariant DE requires the coefficients not be a function of n and the linearity requires that they not be a function of x(n). Therefore, the coefficients are constants. This equation can be analyzed using classical methods completely analogous to those used with differential equations. A solution of the form x(n)=Kλn is substituted into the homogeneous difference equation resulting in a second order characteristic equation whose two roots give a solution of the form xh(n)=K1λ1n+K2λ2n. A particular solution of a form determined by f(n) is found by the method of undetermined coefficients, convolution or some other means. The total solution is the particular solution plus the solution of the homogeneous equation and the three unknown constants Ki are determined from three initial conditions on x(n). It is possible to solve this difference equation using z-transforms in a similar way to the solving of a differential equation by use of the Laplace transform. The z-transform converts the difference equation into an algebraic equation. Taking the ZT of both sides of the DE gives a