### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Digital Signal Processing With Applications ECE 43800

Purdue

GPA 3.59

### View Full Document

## 84

## 0

## Popular in Course

## Popular in Electrical Engineering & Computer Science

This 42 page Class Notes was uploaded by Cassidy Casper on Saturday September 19, 2015. The Class Notes belongs to ECE 43800 at Purdue University taught by Staff in Fall. Since its upload, it has received 84 views. For similar materials see /class/207907/ece-43800-purdue-university in Electrical Engineering & Computer Science at Purdue University.

## Popular in Electrical Engineering & Computer Science

## Reviews for Digital Signal Processing With Applications

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/19/15

32 CHAPTER 1 ANALYSIS OF DISCRETEiTIME LINEAR TIMEilNVARIANT SYSTEMS lt3 Figure 118 A complex number z can be represented in Cartesian coordinates x y or polar coordi nates R 9 I 13 Frequency Analysis I 131 A Review of Complex Numbers A complex number is represented in the form 2 90 31 where x and y are real numbers satisfying the usual rules of addition and multiplication and the symbol j called the imaginary unit has the property 3 2 71 The numbers x and y are called the real and imaginary part of 2 respectively and are denoted by z 9W i 92 We say that z is real if y 0 while it is purely imaginary if x 0 Example 110 The complex number 2 3 Qj has real part 3 and imaginary part 2 while the real number 5 can be uiewed as the complex number 2 5 Oj whose real part is 5 and imaginary part is 0 I Geometrically complex numbers can be represented as vectors in the plane Fig 118 We will call the xy plane when Viewed in this manner the complex plane with the x axis designated as the real axis and the y axis as the imaginary axis We designate the complex number zero as the origin Thus xjy0meansxy0 In addition since two points in the plane are the same if and only if both their x and y coordinates agree we can de ne equality of two complex numbers as follows 1 jy1 2 jyg means 1 2 and y1 yz Thus we see that a single statement about the equality of two complex quantities actually contains two real equations Sec 1 3 Frequency Analysis 33 De nition 11 Complex Arithmetic Let 21 ml jy1 and 22 2 jyg Then we de ne a 21 i 22 901 i 902 2241 i 242 b 2122 961962 241242 31901242 902241 c for 22 32 0 w is the complex number for which 21 22w I Note that instead of the Cartesian coordinates x and y we could use polar coordi nates to represent points in the plane The polar coordinates are radial distance R and angle 29 as illustrated in Fig 118 The relationship between the two sets of coordinates is R cos 0 R sin 29 e wee2121 arctan Note that R is called the modulus or the absolute value of 2 and it alternatively denoted Thus the polar representation is estates l 2 lzlcosd jlzl sin29 lzlcos0 jsin0 De nition 12 Complex Exponential Function The complex exponential func tion denoted by 52 or expz is de ned by ez emHy e cosy jsin I In particular if z 0 we have Euler s equation ejy cosy j siny Comparing this with the terms in the polar representation of a complex variable we see that any complex variable can be written as 2 izieje Properties of Complex Exponentials 1 cos0 5e79 e779 i 1 s1n29 2 je797e 79 W 1 521512 51112 7 7 1 e Z ezlzwn emcosy 27m jsiny 27rn emcosy j sin y ez for any integer n 34 CHAPTER 1 ANALYSIS OF DISCRETEiTIME LINEAR TIMEilNVARIANT SYSTEMS 2 2122 g lzll21l39l22l t9 9192 y 21 92 91 z 9 Figure 119 Multiplication of two complex numbers 21 21 lejgl and 22 l22lej92 22 is not shown The result is z lzlejg with lzl lzll l22l and 6 91 62 DT complex exponential functions whose frequencies differ by 27139 are thus identical ejw27rn ejwn27rjn ejwn We have seen examples of this phenomenon before when we discussed DT sinusoids It follows from the multiplication rule that 2122 l21lej91l22lej92 21H22lej9192 Therefore in order to multiply two complex numbers 0 add the angles 0 multiply the absolute values Multiplication of two complex numbers is illustrated in Fig 119 De nition 13 Complex Conjugate If2 z jy then the complex conjugate of 2 2395 2 m 7 jy sometimes also denoted I This de nition is illustrated in Fig 120a Note that if 2 l2le79 then 2 l2le 79 Here are some other useful identities involving complex conjugates 9 ltz 2 so 2ijltz 7 z gt 2 22 23 Z7 2 2 ltgt 2 is real 21 22 2f Z 2122 Sec 1 3 Frequency Analysis 35 S 3 222 y zzjy 1 21jlzl 97r4 z 9 1 9 1z127j2 5 2Iijy 1 21ij a b Figure 120 a Complex number z and its complex conjugate z b Illustrations to Ebrample 111 Example 111 Let us compute the various quantities de ned above for z 1 j 1 2 an x 93 21ij 2 12 2 Alternatively M 22 1jgt17j 1j7j7j2 9 z3z1 Polar representation 2 cos l jsin e To compute 22 square the absolute value and double the angle 22 2cosg jsing 2j 2e The same answer is obtained from the Cartesian representation 1j1j12jj212j712j To compute 12 multiply both the numerator and the denominator by 2 1 i 2 1ij 272271j17j7 2 72 239 Alternatively use the polar representation 7173 71 j 36 CHAPTER 1 ANALYSIS OF DISCRETEiTIME LINEAR TIMEilNVARIANT SYSTEMS We can check to make sure that 1 7 1j 77 1 These computations are illustrated in Fig 1201 I I 132 A Review of Basic Linear Algebra Frequency analysis involves studying representations of the form 3 Zakgk 16 k where signal 3 which is being analyzed is written as a linear combination of a set of orthogonal sinusoidal signals gk For example Eq 16 is called DT Fourier series if signals gk are DT complex exponential signals representing different frequency compo nents of a periodic DT signal 3 Similarly if gk are CT complex exponential signals and s is a CT periodic signal representation 16 becomes CT Fourier series There are moreover other ways of decomposing a signal into its basic components which are not necessarily frequency components As a matter of fact we have already seen a decomposition like this when deriving the convolution formula Section 123 where gk 6k were shifted unit impulse signals There are many other reasons some of which will become clear later in the course for studying representations of the form 16 in general rather than focusing solely on Fourier series We pose the following questions regarding Eq 16 H Given an arbitrary signal 3 and a set of pairwise orthogonal signals gk does representation 16 exist In other words can we nd such coef cients ak that Eq 16 is satis ed to If so what are the coef cients ak OJ If not can we at least nd coef cients ak such that Eq 16 is approximately satis ed Precise answers to these three questions are impossible unless we de ne what we mean by orthogonal and approximately In order to do this we generalize the notions of orthogonality and length found in planar geometry to spaces of signals via the following procedure 0 de ne an appropriate space of signals 0 de ne what it means for two signals to be orthogonal by appropriately general izing the notion of orthogonality of two vectors in a plane 0 de ne the distance between any two signals by appropriately generalizing the notion of distance in a plane Sec 1 3 Frequency Analysis 37 We address the rst item on this agenda by initially restricting our attention to complex valued DT signals de ned on a xed interval say 0N 7 1 where N is some xed nonnegative integer In other words we consider DT signals whose domain is the set 0 1 N 7 1 and whose range is C Each such signal 3 can be represented as an N dimensional vector 5 by recording its N samples in a column 80 81 3N 7 1 The collection of all such signals is therefore the same as the set of all N dimensional complex valued vectors which we call CN Several remarks about notational conventions are in order here 0 In writing vectors are usually denoted by underlining them 3 ln printed texts however it is customary to use boldface letters 5 to denote vectors 0 A transpose of a column vector is a row vector7that is an equivalent expression for s is s 30 31 3N 71T c We will occasionally be using vectors to represent signals de ned for n 1 2 N rather than n 01 N 7 1 In this case 81 82 3N Although we will mostly work with complex valued signals sometimes it is useful to consider only real valued signals The corresponding set of all N dimensional real valued vectors is called RN Since any real valued vector can be viewed as a complex valued vector with a zero imaginary part RN is a subset of CN Even though the domain of de nition of our signals is a set consisting of N points it is sometimes helpful to pretend that the signals are actually de ned for all integer 71 Two most commonly used ways of doing this are pudding with zeros and periodic extension The former assumes that the signal values outside ofn01N71 areall zero 3n0 nlt00rnN The latter assumes that the signals under consideration are periodic with pe riod N 3n 3n mod N nlt00rnN in other words 3N 30 3N 1 31 etc 38 CHAPTER 1 ANALYSIS OF DISCRETEiTIME LINEAR TIMEilNVARIANT SYSTEMS y A 1 quotquotquot quot391 lt91gtl 0 2 a w 2 35 ED 1 0 2 m Figure 121 Two Vectors in the real plane are orthogonal if and only if they form a 90 angle 0 We will often be using symbol 6 which means is an element of For example 5 6 CN means 5 is an element of CN Inner Products and Orthogonality De nition 14 The inner product of two vectors 5 6 CN and g 6 UN is denoted by s g and is de ned by 2 lt57 ggt 8n9n n0 Two vectors 5 and g are de ned to be orthogonal denoted s 1 g if their inner product is zero 5 1 g means sggt 0 l Example 112 Let us see whether our de nition of orthogonality makes sense for vectors in the real plane R2 Two vectors in the plane are called orthogonal if the angle m1 ERZandgltm2 1 342 between them is 90 Lets E R2 be two vectors in the real plane shown in Fig 121 Their inner product is then sggt xlzg ylyg If the inner product is equal zero then 2 7 Q 241 9027 which says that the right triangles AOBA and ACDO are similar From the similarity of these triangles we get ZAOB ZOCD Therefore ACOA 180 7 AAOB 7 ADOC 180 7 100D 7 ADOC 90 Similar reasoning applies if the two vectors are oriented di erently with respect to the coordinate axes Therefore saying that the inner product of two vectors in the real Sec 1 3 Frequency Analysis 39 plane is zero is equivalent to saying that they form a 90 angle This shows that our de nition of orthogonality in UN is an appropriate generalization of orthogonality in the real plane I It is easily seen that the inner product of a vector with itself is always a real number N71 N71 ltS7Sgt Z SWWWW Z M n0 n0 This number is called the energy of the vector De nition 15 The inner product of a uector s with itself is called the energy of s The square root of the energy is called the norm4 of s and is denoted HsH vltssgt Example 113 For example the norm of the uector lt 1 gt in Fig 121 is Mm y 1 which is simply the length of the segment 0A Our de nition of a norm therefore generalizes the familiar concept of the length of a uector in the real plane I Here are some properties of inner products and norms 1 ltgsgt lt57ggt 2 alsl azsz ggt a1lt51ggt a2lt527ggt 3 sa1g1 a2g2gt afltsg1gt a lts g2 4 Hasll lal 39 M 5 Pythagoras s theorem the sum of energies of two orthogonal vectors is equal to the energy of their sum ie if lt5 ggt 0 then HSHZ llgllz H5 gllz Fig 121 and the two examples above illustrate the fact that our de nitions of orthogonality and the norm in UN generalize the corresponding concepts from planar geometry Therefore when considering vectors in UN it is often helpful to draw planar pictures to guide our intuition Note however that the proof of any facts concerning inner products and norms in UN for example the properties listed above cannot be based solely on pictures the pictures are there to guide our reasoning but rigorous proofs must rely only on de nitions and properties proved before For example in proving Property 1 above we can only rely on our de nition of the inner product Once Property 1 is proved we can use both Property 1 if we need to and the de nition of the inner product in proving Property 2 etc Wis actually more general The speci c norm that is the square root of the energy is called the Euclidean norm or the 2 norm or the 2n0rm 40 CHAPTER 1 ANALYSIS OF DISCRETEiTIME LINEAR TIMEilNVARIANT SYSTEMS Projection 5 onto G 575 g g2 pace G the span of g1 and g2 a b Figure 122 a The orthogonal projection 53 of a vector 5 onto another Vector g b The orthogonal projection SG of a vector 5 onto a space G can be obtained by projecting 5 onto g1 and g2 and adding the results where g1g2 is an orthogonal basis for G Orthogonal Projections In the real plane the coordinates of a vector are given by the projections of the vector onto the coordinate axes For example the projections of the vector 1 in Fig 121 1 1 onto the m axis and y axis are the vectors lt 3 gt and lt 0 gt respectively We will soon see that the coordinates of a signal in a Fourier basisithat is the Fourier series coe icientsican also be computed from the projections of the signal onto the individual Fourier basis functions We de ne the projection of a vector 5 6 CN onto another vector g 6 CN by gener alizing the notion of an orthogonal projection from planar geometry Speci cally when we project 5 onto g we get another vector sg which is collinear with g ie it is of the form ag such that the difference 5 7 5g is orthogonal to g An illustration of this for the real plane is given in Fig 122a De nition 16 The orthogonal projection of a vector 5 6 CN onto a nonzero vector g 6 UN is such a vector 5g 6 CN that 1 5g ag for some complex number a and 2 s 7 5g 1 g The orthogonalprojectz39on of a real valved vector 5 6 RN onto another real valved vector g 6 RN is de ned similarly I Note again that even though our de nition applies to the general case of CN we can use the planar picture of Fig 122a to guide our analysis From this picture we Sec 1 3 Frequency Analysis 41 Figure 123 Illustration to EbCample 114 immediately see that the coefficient a in the expression sg ag is not arbitrary If it is too small or too large7 the angle between s 7 5g and g will not be 90 To nd the correct coe icient a7 note that the two conditions in the de nition above imply that lt5 7 was 0 But this equation can be rewritten as follows 5 g 7 altg7 g 0 Therefore7 a 1 lt5 ggt ltg7ggt sg g g 17 Example 114 Does our result of Eq 17 make sense for 2 dlmenslonal real uectorsf2 1 2 2 gt onto the uectorg 7 lt 0 As Suppose that we want to project the vector 5 shown in Fig 123 the result should clearly be sg lt 1 Does our formula 17 glue the same answerf2 42 CHAPTER 1 ANALYSIS OF DISCRETEeTIME LINEAR TIMEelNVARIANT SYSTEMS Our de nition works as expected in the plane Just as we did with the concepts of orthogonality and length before we have generalized the planar concept of orthogonal projection to UN I We now generalize our orthogonal projection formula 17 to the case when we project a vector 5 onto a space G This is illustrated in Fig 122b We show that if an orthogonal basis for space G is known it is easy to compute the projection of any vector 5 onto G Of course we need to precisely de ne what we mean by an orthogonal basis before we proceed De nition 17 A subset G of UN is called a uector subspace of CN if 1 agEGforanygEG andanyaEC 2 and g1 g2 E G for any g1g2 E G A subset G of RN is called a uector subspace of RN if 1 agEGforanygEG andanyaElR 2 andg1g2 Gforanyg1g2 G I In other words a set C in UN or in RN is called a vector subspace if it is closed under multiplication by a scalar and under vector addition 04 Example 115 The set of all uectors of the form 0 where 04 E C is a uector subspace of C3 if you multiply a uector of this form by a complex number you get a uector of this form if you add two uectors of this form you again get a uector of this form On the other hand this set of uectors is not a uector subspace of R3 simply because it is not a subset ofR Oz The set of all uectors of the form 0 where 04 E C is not a uector subspace of 1 204 C3 if you multiply a uector like that by 2 you get 0 which is no longer in the 2 set De nition 18 Vectors g1 g2 gm are called linearly independent if none of them can be expressed as a linear combination of the others g iZakgk fori12m kg Equiualently g1 g2 gm are called linearly independent if a1g1a2g2amgm0 implies a1a2am0 I Sec 1 3 Frequency Analysis 43 De nition 19 The space spanned by uectors g1 g2 gm is the set of all their linear combinations ie the set of all vectors of the form a1g1 lng amgm where a1 a2 am are numbers complex numbers if we are in UN real numbers if we are in RN I De nition 110 If G spang1 gm and if g1 gm are linearly independent then g1gm is said to be a basis for space G If in addition g1gm are pairwise orthogonal the basis is said to be an orthogonal basis I 1 0 2 z 1 0 Example 116 spanlt0gtlt 1 7C sinceltygt 7zlt0gtylt1gt for any Z 6 C2 It is an easy exercise to show that 0 and 1 are linearly independent and moreouer orthogonal Therefore these two uectors form an orthogonal basis for C2 I We will need the following important result from linear algebra which we state here without proof Theorem 12 Any N linearly independent uectors in UN RN form a basis for UN RN Any N pairwise orthogonal nonzero vectors in UN RN form an orthogonal basis for UN I We now de ne the orthogonal projection sG of a vector 5 onto a subspace G of CN We use the 3 dimensional picture of Fig 122b as a guide First sG must lie in G Second the difference between s and so must be orthogonal to G De nition 111 The orthogonal projection of a uector s 6 CN onto a subspace G of UN is such a uector SC 6 CN that 1 SC 6 G and 2 s 7 SC 1 G that is s 7 SC is orthogonal to any uector in G The orthogonal projection of a real ualued uector s 6 RN onto a subspace G of RN is de ned similarly I Let sG be the orthogonal projection of 5 onto a subspace G of CN Suppose that g1 gm is an orthogonal basis for G One consequence of this is that any vector in G can be represented as a linear combination of vectors g1 gm In particular since SC 6 G we have that in SC Zakgk for some complex numbers a1 am 18 k1 44 CHAPTER 1 ANALYSIS OF DISCRETEiTIME LINEAR TIMEilNVARIANT SYSTEMS These coefficients 11 am cannot be any arbitrary set of numbers however they have to be such numbers that s 7 so is orthogonal to any vector in G In particular sisa Lg 5750 ng sisa Lgm sisagp O forp1m ltsvgpgt7lt507gpgt 0 lt57gpgtiltzakgk7gpgt 0 k1 lt57 gpgt 7 M3 akltgk7 gpgt 0 w H 1 But notice that the orthogonality of the basis g1 gm implies that gk gpgt 0 unless p k Therefore only one term in the summation can be nonzeroithe term for k p lt57 gpgt apltgpv gpgt 0 lt57 gpgt a for p1m p ltgp7 gpgt Note that since g1 gm is a basis gp 7 0 and therefore gp gpgt 7 O This means that dividing by gp gpgt is allowed Substituting the expression we obtained for the coefficients into Eq 18 we obtain 50 iltsl gkgtgtgk 19 k1 ltgk7 gk Comparing this result with our result 17 for projecting one vector onto another we see that projecting onto a space G which has an orthogonal basis g1 gm amounts to the following 0 project onto the individual basis vectors 0 sum the results This is illustrated in Fig 122b for projecting a 3 dimensional vector onto a plane spanned by two orthogonal vectors g1 and g2 Formula 19 is actually a lot more than a formula for projecting a vector onto a subspace Note that if the vector 5 belongs to G then its projection onto G is equal to the vector itself 50 s if s E G In this case Eq 19 tells us how to represent 5 as a linear combination of orthogonal basis vectors Sec 1 3 Frequency Analysis 45 50 the orthogonal projection 1 of 5 onto space G Space G with orthogonal basis g1 Figure 124 Illustration to the proof of Theorem 14 The Closest point in space G to a xed vector 5 is the orthogonal projection SG of 5 onto Theorem 13 Decomposition and Reconstruction in an Orthogonal Basis Suppose that g1 gm is an orthogonal basis for a subspace G of UN in particular G could be CN itself and suppose that s E G Then m s Zakgk synthesis or reconstruction formula 110 k1 where ak for k1m gkvgk analysis or decomposition formula 111 The coe cients 111 are unique ie there is no other set of coe cients that satisfy Eq 110 I As we will shortly see a particular case of these equations are the DT Fourier series formulas These equations however are very general they work for non Fourier bases of CN Slight modi cations of these equations also apply to other spaces of DT and CT signals For example the CT Fourier series formulas are essentially a particular case of Eqs 110111 Suppose now that s does not belong to the subspace G Can we nd coe icients a1 am such that Eq 110 is satis ed approximately Speci cally we would like to nd the coe icients that minimize the energy or equivalently the 2 norm of the 46 CHAPTER 1 ANALYSIS OF DISCRETETIME LINEAR TIMEINVARIANT SYSTEMS error7ie the 2 norm of the difference between the two sides of 110 m s 7 Z akgk k1 It turns out that the answer is still Eq 1117ie that the orthogonal projection sG of 5 onto G is the closest vector to 5 among all vectors in G To show this consider Fig 124 Using the de nition of orthogonal projection we see that the vector 5 7 SC must be orthogonal to G ie nd a1 am to minimize S7501V forany VEG For any arbitrary vector f E G we have SC 7 f E G Hence 57 SO 1 SC 7 f We can therefore apply Pythagoras s theorem to the triangle formed by vectors 5 7 f s 7 so and SC 7 f Hsifll2 HSSGSGfH2 Hsisallz lsaifllz 2 Hsisallz Therefore H5 7 50 H5 7 fH for any f E G or alternatively 7 i 7 f HS SCH Igglls H So so is the closest vector in G to s It is easily seen moreover that equality is achieved only if f sG which means that SC is the unique closest vector to 5 Theorem 14 Approximation by an Orthogonal Set of Vectors Suppose that g1 gm is an orthogonal basis for a subspace G of UN in particular G could be CN itself and suppose that s 6 UN is a uector which may or may not belong to G We seek to approximate s by a uector in G If we look for an approximation s E G which minimizes the 2 norm 7 5H of the error then m s Zakgk 112 k1 s where ak for k1m 113 ltgh7 gk The coe cients 113 are unique ie there is no other set of coe cients that results in the minimum 2 norm of the error I Sec 1 3 Frequency Analysis 47 I 133 Discrete Time Fourier Series and DFT Example 117 Let 91 and 92 be the following two discrete time complex exponential functions de ned for n 1 2 34 2 71 91n exp n 1234 and 92n exp n 1234 a Suppose that 2 n 71j n2 sn 0 n ilij n4 Can the signal 3 be represented as a linear combination of 91 and 92 If so nd coe cients a1 a2 in this representation 501 119101 1292007 71 1727374 b Suppose that 0 n S 22 0 n4 Can the signal 3 be represented as a linear combination of 91 and 92 If so nd coe cients a1a2 in this representation s ltngt a391n sz n 1234 Solution a Write all three signals as vectors ie 911 921 81 g1 912 g2 922 5 82 913 7 923 7 83 914 924 84 48 CHAPTER 1 ANALYSIS OF DISCRETEiTIME LINEAR TIMEilNVARIANT SYSTEMS S Figure 125 Illustration to Example 117 The four entries of Vector g1 as points in the complex plane 913 gamma 27r3 37139 914 exp J 4 gtexp lt37 Fig 125 shows a plot of these in the complex plane recall that expj0 has absolute value 1 and angle 0 Calculations for g2 are similar We obtain 1 1 j 7 1 gl 7 71 7 2 7 1 j 1 One method of solving this problem would be to simply notice that 2 s 710 J gl 1 g2 by inspection 1 7 j We have thus represented s as a linear combination of g1 and g2 with coefficients a1 a2 1 3n 91n 9271 n 1727374 Another method is to notice that g1 and g2 are orthogonal7 ltg1g2gt11jlt71gtlt71gt1lt7jgtlt71gt17j71jo Sec 1 3 Frequency Analysis 49 3939 Projectionlgf s onto G Space G7 the span of g1 and g2 Figure 126 Illustration to Example 117 Vector 5 lies in the space spanned by g1 and g2 and therefore can be represented as their linear combination Vector s is not in the space spanned by g1 and g2 and cannot be represented as a linear combination of g1 and g2 The closest linear combination of g1 and g2 to s is the orthogonal projection of 5 onto the span of g1 and g2 We can therefore use Theorem 13 if s is representable as a linear combination of g1 and g2 then the coefficients are found from ltsg1gt 2171Hj071717j7j ltg17g1gt 11jj711jij 7 2lj10lij171 1111 lts7g2gt 21 71H 71 01 7173 1 ltg27g2gt 11111111 2117j011j7 1111 Since g1 g2 57 the answer is that s can indeed be represented as a linear combination of g1 and g2 with coefficients a1 a2 1 Geometrically7 this means that 5 lies in the space spanned by g1 and g2 as illustrated in Fig 126 b We take the same approach as in Part a if s is representable as a linear 50 CHAPTER 1 ANALYSIS OF DISCRETEiTIME LINEAR TIMEilNVARIANT SYSTEMS combination of g1 and g2 then the coefficients are found from al lts 7g1gt010j110jV 71 ltg17g1gt 4 4 12 5 32 0107111071V 1 g27g2gt 4 4 However 0 1 73471 4 4g14g2 12 7amp5 E 4 Therefore 5 cannot be represented as a linear combination of g1 and g2 Geometrically this means that 5 lies outside of the space spanned by g1 and g2 as illustrated in Fig 126 The coefficients a 1 714 and a z 14 we computed are actually the coefficients of the orthogonal projection of 5 onto this space Theorem 14 states that in this case figl 1 g is the best approximation of s as a linear combination of g1 and g2 in the sense that it minimizes the 2 norm of the error I Example 118 In addition to the signals gln and ggn de ned in Example 117 de ne the signals gon and ggn as follows gem exp n 1234 and 93n exp n 1 23 4 In other words we now have four signals gkn k 0123 de ned for n 1 2 34 by 9M exp Similarly to Example 117 it is easy to check that these four signals are pairwise or thogonal Since they are all nonzero Theorem 12 implies that they form an orthogonal basis for C4 Theorem 13 is therefore applicable to any signal in C4 in particular both to s and 3 de ned in Example 117 a Using Theorem 13 nd coe icients a0 a1 a2a3 in the following Fourier series expansion 871 0109001 0119101 0129200 a393n7 71 17273747 for signal sn de ned in Example 117 Sec 1 3 Frequency Analysis 51 b Using Theorem 13 nd coe icients a67a17 a27ag in the following Fourier series expansion 8 01 a690n 19101 29201 13193007 71 17 27 3 4 for signal sn de ned in Example 117 Solution a We already know from Example 117 that s 91 kgrie7 the additional basis signals go and 93 are not needed to represent 3 The answer is a0 a3 0 and a1 a2 1 If we did not have the results of Example 117 available to us7 we would proceed similarly to Example 117 First7 we write all signals as vectors 1 1 1 1 2 7 1 7 j 7 1 7 ii 7 1j see 1 7g1 71 7927 1 7937 71 57 0 1 ij 71 j 7173 Then we calculate the inner products used in Eq 1117 and compute the coe icients These calculations were done in Example 117 for g1 and g2 The calculations for go and g3 are similar g07g0gt g37 g3gt 47 and ltsygogt 211J 1011j107 lt57gogt 0 a 07 0 ltgo7gogt 4 lt57g3gt 211jj011jf 2 1jj 717M733 2ijj2jj207 lt57g3gt 0 a3 ltgs7gsgt 4 b We can use ghgk 4 computed in Example 117 and Part a above Recall that 0 0 7 s 1 0 This makes its inner products with the basis vectors very simple 1 lt5 7gkgt ltgk7 gk 0 9k1 019142 19k3 0 9k4 4 7 lt9 lt3gtgt 4 7 14 k02 714 k13 52 CHAPTER 1 ANALYSIS OF DISCRETEiTIME LINEAR TIMEilNVARIANT SYSTEMS Therefore 1 1 1 1 3 n 19001 19101 t 19201 19371 This is consistent with what we saw in Example 117 5 cannot be represented as a linear combination of only g1 and g2 Note however that if in the expansion 571 71 1 71 4g0 4g1 4g2 4g37 we drop the terms which do not contain g1 and g2 we will get the following vector 1 1 4g1 4g27 which is the answer we obtained in Example 117 This is the closest approximation of s by a linear combination of g1 and g2 I Now let us generalize Examples 117 and 118 from four dimensions to N Example 119 Discrete Fourier Transform Consider the following DT complex exponential functions gknexpltgt n0N71 k0N71 114 In other words there are N functions gongl n gN1n and each of them is de nedforn 01N71 a Proue that these N signals are pairwise orthogonal and nd their energies 17 Find a formula for the Fourier series coe cients X0X1 XN 71 of an N point complex valued signal Mn N71 Xkgkn n0N71 k0 N71 1 yQ n kn NXkexpltTgt n0N71 115 Solution a To show orthogonality and compute the energies we need to calculate all inner products gkgigt for all k O N 7 1 and i O N 71 If we can show that these inner products for k 7 i are zero we will show that the signals are pairwise orthogonal Moreover the inner products for k i will give us the energies N71 ltgk7gigt ngn9in n0 Sec 1 3 Frequency Analysis 53 7 N711 yQ n kn 1 j27rin Nexp N N n0 N71 1 327139 kizn 72 lt gt n0 N71 When k 2 each term of the summation is equal to 1 and therefore the sum is N The energy of each gk is therefore NNZ 1N When k 31 2 the sum is zero why7 b Since g0 gNA are nonzero and pairwise orthogonal we can apply Theorem 12 to infer that go gN1 is an orthogonal basis for UN Any signal s 6 CN can therefore be uniquely represented as their linear combination according to Theorem 13 The coefficients in the representation are given by Eq 111 The denominator of that formula is the energy of gk which we found in Part a to be 1N Therefore 7 M XW gmgk ltX7gkgt 1N N71 N39 ain gwn n0 N71 1 yQ n kn N zn ex 7 H ltgtN p N N71 amex 7M k0N71 116 H H p N lt gt The representation 115 of an N point complex valued signal x as a linear combination of complex exponentials 114 of frequencies 0 27rN 27rN 7 1N is called the DT Fourier series for the signal m 1 N4 27rkn znNZXkexp n0N71 117 k0 The signal X comprised of the N Fourier series coefficients is called the discrete Fourier transform DFT of the signal m The DFT Xk is obtained from as follows N71 2 k Zmnexp k0N71 118 n0 Xk 54 CHAPTER 1 ANALYSIS OF DISCRETEiTIME LINEAR TIMEilNVARIANT SYSTEMS Since Eq 117 is the recipe for obtaining signal samples from the DFT it is sometimes called the inverse DFT formula I Eqs 117 and 118 are particular cases of Eqs 110 and 111 respectively and were easily obtained in Example 119 by applying Theorem 13 to a complex exponential basis also called Fourier basis for UN Eq 117 tells us how to represent any signal in UN as the linear combination of Fourier basis functions The k th term in the representation is the orthogonal projection of the signal onto the k th basis signal The projection coefficients are calculated using Eq 118 Note that Example 118 is a special case of Example 119 by setting N 4 in Eqs 117 and 118 and appropriately normalizing the basis functions we can get the answers to Example 118 I 134 Complex Exponentials as Eigenfunctions of LTI Systems Discrete Time Fourier Transform DTFT One of the major reasons for the importance of Fourier series representations and also Fourier transforms is that the Fourier basis functions are eigenfunctions of LTI systems In other words the response of an LTI system to any one of the Fourier basis functions of Eq 114 gk is that same function times a complex number akgk where the complex number 0 depends on the system and on the frequency of the Fourier basis function To see this let us consider an LTI system with the impulse response h and use the DT convolution formula to calculate its response to the following signal 57 for all integer n where the frequency w is an arbitrary xed real number We have that the response y is Mn 2 7107090017771 was 00 where Hejw Z hme 7 m m7oo The function H Viewed as a function of w is called the frequency response of the system and is the discretetime Fourier transform DTFT not to be confused with DFT of the impulse response h We will have much more to say about DTFTs below For now it is important to note that we obtained the following property Sec 1 3 Frequency Analysis 55 Theorem 15 Consider an LT system whose impulse response is h If the com plex exponential signal ewe de ned for all integer n is its input then the output is He7 0e7 0 for all integer n where He7 0 is the frequency response of the system evaluated at the frequency we of the input signal I Example 120 a Find a di erence equation that describes the system in Fig 127 ie relates the output of the ouerall system to its input Here A B and C are xed constants Figure 127 The system diagram for EbCample 120 Solution From the system diagram of Fig 127 we haue Axn Bxn 71 Cxn 7 2 17 Find the frequency response of this system by calculating the response to a complex exponential Solution To nd Hej we calculate the response of the system to the input signal e m e m Ae m Bewm l Cejwmizl A Be j Ceizjw e m Hej c Suppose that A B C 1 and 5 for 700 lt n lt oo Calculate using the frequency response Solution 5ej0 yltngt He seam 1 1 1 5 15 for all integer n l 56 CHAPTER 1 ANALYSIS OF DISCRETEiTIME LINEAR TIMEilNVARIANT SYSTEMS Example 121 Consider a DT LTI system with a known frequency response Hej The response of such a system to an euerlasting complex exponential input signalgn 57 700 lt n lt 00 is gnHe for 7 00 lt n lt oo 119 In other words elm is an eigenfunction of the system with an eigenualue Hej a Does Eq 119 hold for sinusoidal inputs In other words suppose that the input to a DT LTI system is cos wn 4p for 700 lt n lt 00 Is it always the case that the output is cos wn LpHe quot for 700 lt n lt 00 Does this hold for DT LTI systems with euen frequency responses ie for systems with Hej H0577 Solution We decompose coswn 4p into complex exponentials 1 7Wn JQ WJrW coswn 4p 2 e e ewewn e we wn eMHejwejWL e jWHe jwe jwn Unless Hej is euen ie Hej H0577 or else is not equal to coswn LpHe quot Note in general coswn 4p and e7 mun are not eigen functions of LTI systems 17 Use the aboue property 119 to deriue a simple expression for the response of the system to the following input signal 2cos 8n Solution Using the preuious part we get 1 7r 1 n 2 557TH578578n Ee JTHe 78e 78n Hej8ej8n He j8e j8 I I 135 Further Remarks on the Importance of DFT Suppose that S is an LTl system with a known impulse response h of duration N hn 7 O for n0N71 hn 0 otherwise Suppose further that x is an input signal which is periodic with period N How many arithmetic operations will it take to calculate the response y using the convolution formula First notice that the response is also periodic with period N ynN Z hmxnN7m Z hmxnim yn for any integer n m7oo m7oo Sec 1 3 Frequency Analysis 57 We therefore only need to calculate N samples of yn for example for n 0 N Since It has duration N and x has in nite duration the convolution sum will always have N terms 00 N71 Mn 2 710709001 m 2 710709001 7 m7oo m0 h0znh1mn71hN71zn7N1 for n0N71 Therefore the computation of one particular sample requires N multiplications and N 7 1 additions5 There are altogether N samples of y to be computed and therefore the overall number of multiplications is N2 and the overall number of additions is NN 7 1 N2 7 N The overall order of the number of operations required is N2 In other words the process of calculating the response has computational complexity 9N2 This is a very high computational cost for something as basic and as frequently needed as t a dis r im t Speci cally suppose that on our computer this operation takes 1 second for N N1 Then for N 100N1 it will be approximately 1002 10000 times slower ie it will take approximately 28 hours We need an algorithm for calculating convolutions more quickly Let us use the fact that since z is periodic with period N it can be represented as the following linear combination where gk are the Fourier basis functions given by Eq 114 Using the linearity of our system we obtain the following representation for the output N71 24 Slv l XkSl9kl k0 But since gk is a complex exponential of frequency 27rkN we can use Theorem 15 to write the response to gk as Sgk He 7 kNgk Substituting this into the formula for y we get N71 y SM XkHej27rkN9k k0 But this is a representation of the signal y as a linear combination of Fourier basis signals 9 with coefficients XkHe 7 kN In other words the Fourier series coefficients of y are Yk XkHej2quotkN for k 0 N 71 Assuming that the values of H5727 kN for k 0N 7 1 are known we have discovered the following procedure for calculating y 5These are complex multiplications and complex additions since we assume in general that our signals are complexValued 58 CHAPTER 1 ANALYSIS OF DISCRETEeTIME LINEAR TIMEeINVARIANT SYSTEMS Step 1 Calculate the N DFT coefficients Xk of m using the DFT formula Step 2 Calculate the N DFT coefficients mt XkH572 kN of y Step 3 Calculate y from its DFT coefficients using the inverse DFT formula It turns out that Steps 1 and 3 the DFT and the inverse DFT can be implemented using a fast Fourier transform FFT6 algorithms whose computational complexity is 9NlogN Moreover if the N values H5727 kN of the frequency response were not known but had to be calculated from the impulse response h that too could be done using FFT with computational complexity 0Nlog N Step 2 consists of N multiplications The overall computational complexity is therefore only 9Nlog N a marked improvement over 9N2 especially for large N To summarize we have just seen two aspects of why it is important to study rep resentations of signals as weighted sums of complex exponentials in the context of our study of LTl systems 0 Conceptual importance LTl systems process each frequency component sep arately and in a very simple way ie by multiplying it by a frequency dependent complex number Computational importance To obtain the response of an LTl system with an N point impulse response to an N periodic signal we need 9N2 computational effort ifwe use the convolution formula directly The computational complexity is however reduced to 9N log N if we use the frequency domain representations instead I 136 Continuous Time Fourier Series As indicated above the notions of orthogonal bases and projections can be extended to spaces of CT signals Determining whether a series representation converges and if so what it converges to is much more complicated than for niteduration DT signals We therefore will only consider one very important exampleRCT Fourier series Consider the set of signals L2T0 de ned as follows it is the set of all periodic complex valued CT signals 3t with period To for which TTo lstl2dt lt oo where 739 is an arbitrary real numberiie the integral is taken over any period It turns out that L2T0 is a vector space each vector in this case being a continuoustime signal If we de ne the inner product of two functions as follows 739 To ltsggt l slttgtltglttgtwt 6We will discuss the mechanics of FFT below What is important for now is that it is a fast algorithm for calculating the DFT of a signal Sec 1 3 Frequency Analysis 59 then the in nite collection of TO periodic complex exponentials 2 kt gm exp k 01111 To forms an orthogonal basis for L2T0 We can represent any To periodic CT signal 3 as a linear combination of these complex exponentials st i akg t i akexp 32 120 k7oo T k7oo 0 The rst 7 sign in Eq 120 needs careful interpretation unlike the nite duration DT case the equality here is not pointwise Instead the equality is understood in the following sense H0 as Naioo andMHoo M S Zakgk kN Nevertheless formula 110 is still valid 9 121 lt9k79kgt The inner product of gk and 9 is easily computed TTO y27rkt y2mt 7 dt yam T explt To gtexplt To gt To 2 k2 exp dt 739 T0 T0 ifk2 0 ifky i a The fact that 91mm 0 shows that our vectors are indeed pairwise orthogonal7 Substituting gkgk T0 back into Eq 121 we get lt579kgt 7 1 To j27rkt aki T0 7T0 T stexp To dt 122 7Note however that this is not enough to prove that they form an orthogonal basis for L2To since L2To is in nitedimensional and Theorem 12 no longer holds it is not true that any in nite set of nonzero orthogonal Vectors forms an orthogonal basis for L2To Proving the fact that signals gk do form an orthogonal basis for L2To is beyond the scope of this course 60 CHAPTER 1 ANALYSIS OF DISCRETEiTIME LINEAR TIMEilNVARIANT SYSTEMS I I 7 7 E 7 Lo I LO E To 2 2 2 2 T0 t Figure 128 Signal st of Ebrample 122 Example 122 Let T0 t0 and A be three positiue real numbers such that To gt to gt 0 Consider the following periodic signal slttgt 1321 0 if lt 70 periodically extended with period To as shown in Fig 128 Using Eq with r iToQ its Fourier series coe icients are 1 tOZ Ato 0 To 702 5 T07 1 W2 27rkt ak To itOZAexp 7 dt 7 A To exp Jam 02 T0 ijn39k T0 402 7 A i exp We 7 exp 73ka wk Qj T0 TO A Wkto sm 0 Note that this last formula is also ualid for k 0 if we de ne SI Another common way of decomposing CT periodic signals as linear combinations of sinusoidal signals is by using sines and cosines as basis functions7 instead of complex exponentials The following in nite collection of functions is also an orthogonal basis for L2T07 and is also called a Fourier basis 3005 1 2 kt ckt coslt 7r 7 k12 1 I 90 To 2 kt skt sinlt Ogt k12 Sec 1 3 Frequency Analysis 61 As we did previously7 let us rst prove that these functions are pairwise orthogonal7 and nd their energies over one period We need to consider all pairwise inner products7 which will now be integrals of products of trigonometric functions We will therefore need the following formulas sina sin3 COS04 7 3 7 cosa 3 123 sinacos3 sinoz 7 3 sina 3 124 cosacos3 COS04 7 3 cosa 3 125 Now we compute the inner products7 keeping in mind that skt is de ned for k 2 1 while ckt is de ned for k 2 O TTO t t 39 i 2 k i 2 4 dt 51mm T s1nlt 7139 To s1nlt 7TZT0gt El 123 1 T0 t t 01 cos lt27rk7ifogt 7cos lt27rkifogt dt g k i 0 k 7 TTO t t 39 i 2 k 2 4 dt 31mg T s1nlt 7139 To coslt 7TZT0gt El 124 T0 q sin lt27rk7iTi0gt sin lt27rkiTi0gt 1250 TTO t t 2 k 2 4 dt 01mg T cos lt 7139 To cos lt 7TZT0gt Eq 1 25 17 cos lt27rk 7 cos lt27rk dt 2 To k 0 k2 7 0 0 mm We are now ready to derive formulas for the coef cients 01012 and b07191 b2 of the expansion of a CT To periodic signal st 575 50 iaksz t ibkcz t 126 k1 k1 300 b 0 ltcocogt 62 CHAPTER 1 ANALYSIS OF DISCRETEiTIME LINEAR TIMEilNVARIANT SYSTEMS Figure 129 Signal xt of EbCample 123 1 rTo t To sts1n 271 alt7 k 712 Example 123 Suppose that the period is To 2 and let signal m be de ned by 1 71 tlt0 t 0 0 tlt1 as illustrated in Fig 129 Let us compute the Fourier series coe cients with respect to the Fourier basis of sines and cosines From the formulas aboue with r 71 1 0 1 b 1dt 0 211 2 2 0 t Forkil7 bk 5 cos 27rk dt 71 0 cos7rkt dt 71 1 t0 sinhkt t71 0 2 0 1 t ak 571S1nlt27rk gt dt 0 sin7rkt dt 1 1 71 Sec 13 Frequency Analysis 63 1 t0 7 cos7rkt wk t71 7 7 ifk is odd 7 0 ifk is even 7 A di erent method of nding the coe cients is to notice that a Signalx is related to signals of Example 122 If we set to 1 A 1 and To 2 in Example 123 and shifts by tOQ to the left we will obtain x xt st b C omplex exponential basis signals are related to the sine and cosine basis signals Using the Fourier series coe cients obtained in Example 122 we have the following representation of xt in the complex exponential Fourier basis at slt g lt We lt k 0 i A wkto j27rkt02 j27rkt kgioo Wk Sln To exp lt To exp To i A Wkto j n kto t Sln ex Wk To 13 To 9k 7 700 which means that the coe cients ofx in the complex exponential Fourier basis are 7 A Wkto j n kto 04k 7 Wk Sln To exp To 1 wk j n k s1n exp 127 But notice that the complex exponential basis functions are related to the sine and cosine basis functions as follows got 1c0t7 2 kt 2 kt ForkZl gm cos 7 jsin 7 cktjskt To To 2 kt 2 kt Hos 7 jsin 7 cmwsw To To 64 CHAPTER 1 ANALYSIS OF DISCRETEiTIME LINEAR TIMEilNVARIANT SYSTEMS Therefore 00 9075 Z 0ng k7oo co 71 04090t204k9kt Z 04k9kt k1 k7oo co 0409005 Z104k9kt 04710714731 k H m8 aooot 04kCkt MW aikckt 713140 8E 00 a0c0t 2ak akckt Z ak 7 akskt k1 k1 Matching these coe cients with the coe icients in Eq 126 we get the following rela tionship between the exponential Fourier series coe cients and the sine cosine Fourier series coe icients of any To periodic signal 190 0407 bk akaik for k127 ak j04k704k fork12 Using expression 127 we found for the coe cients 04k of the speci c signal x we are considering in this example we get b0 101 sin7rk2exp 1 2 wk2 2 k0 27 bk 04k 046 isin exp 1 sin exp wk 2 2 7r7k 2 2 7r 7 2 wk wk 7 Wk sm 2 cos 2 1 sin0 sinwk O 4 1 wk j n k 1 wk ak 3akia7ky sm 7 exp T iwltiks1n 77 exp 7 Sec 1 3 Frequency Analysis 65 O7 ifk is even 7 ifk is odd Notice that these are the same results we got before by eualuating the inner products with sines and cosines directly I I 137 Discrete Time Fourier Transform DTFT Revisited The de nition of the discrete time Fourier transform of a discretetime signal is 00 Xejw Z zne7 m n7oo Notice that are the continuous time Fourier series coef cients of Xe7 To see this better7 we can relate DTFT to the CTFS formulas above by making the following identi cations To 27r7 w 27rtT0 t7 n 7k aek The DTFT formula then becomes the inverse CTFS formula 1207 and therefore the inverse DTFT formula is obtained by relabeling variables in the CTFS formula 122 1 wo27r I I i Xe7we7wndw 27139 We Thus7 DTFSDFT7 CTFS7 and DTFT are all particular cases of our general framework of orthogonal representations Properties of the DTFT 1 Linearity the DTFT of a1z1n a2z2n is a1X1 Sim ang Sim 2 Delay the DTFT of z n 7 no is co 00 2 m n 7 no eiiwminwei mo mg im Z mme jwm e771 O 66 CHAPTER 1 ANALYSIS OF DISCRETEiTIME LINEAR TIMEilNVARIANT SYSTEMS 3 Convolution Y en 2mm n Z hn 7 5771 n k Z hn 7 Meijwn k n propgtyz 2 H egg 57739wa k H 57 Zei uk k k Xej He X 5 So7 if h gtk Mn7 then Y 57 H 57 X 57 4 Parseval s theorem 2 Mn HM de Z jXejw Y 5 dw 5 00 X5 0 Z 9071 6 7 Modulation the DTFT of zn57 0 is Zmne lwoiwn X ejw wov Example 124 1 Mn 5M 9071 1 Find the frequency response He7quotquot Is this system a low pass band pass or high pass lter Plot lH 5in and 4H 51w Sec 1 3 Frequency Analysis Solution 67 Method 1 Use the eigenfunction property e m H ejw e m 2401 H ejw Method 2 Y ejw H ejw ejwnejwnilgt 1eijwejwn 1 Hej e7j 4 e jgt whale I 392 w e 7200s 2 DTFT mn 7 ngFTmm DTFTzn 7 1 1 5X 1 EX e j 1 e77 y 55w X e7 1 5 1 e77 are x are we Method 3 Impulse response hn 6n 7 1 HM DTFThn DTFT6n i Mamil DTFT6n 71 677w HM 1e 7 To plot the magnitude response and the phase response we note w H eWH COSE 41115739 Ae jzcos NIE 0 68 CHAPTER 1 ANALYSIS OF DISCRETEiTIME LINEAR TIMEilNVARIANT SYSTEMS because gt0 077 lt lt i6 77ltwlt7 COS 2 27227 7 Note is periodic with period 27139 since it is a DTFT of a DT signal Since the values of H eWH at low frequencies near w 0 are close to one and its values at high frequencies nearw in are close to zero this a low pass lter WWW Figure 131 The plot of 4H elm7 for Ex 124 Example 125 Repeat Ex 124 for the following system 1 2471 5941 9071 2 Solution H ejw Sec 1 3 Frequency Analysis 69 iHej i isinwi 4H 51 fj e jw zsinw 7w 2 7 giw nggn 7 igiw ingwgo because i Z 07 0 w 7r s1nw S W S and therefore zsinwi 0 O w w 7 77139 ingwgo This is a band pass lter Note it is a convention to keep angles in the range inn Figure 133 The plot of 4H ejw7 for Ebn 125 I 138 Discrete Fourier Transform DFT Revisited Our motivation for studying frequency analysis of DT signals is summarized in Fig 134 70 CHAPTER 1 ANALYSIS OF DISCRETEiTIME LINEAR TIMEilNVARIANT SYSTEMS 2 N71 N71 an Emma yltngt 2XltkgtH av gm k0 k0 H6jw Figure 134 A system diagram motivating the use of frequency analysis In this gure7 the input is N periodic and the basis function 9km is given by 1 mm 91671 N HT for k 07 7N71 and for all n 128 0 Conceptual importance LTI systems process each harmonic separately in a sim ple way ie7 multiply each harmonic by a frequency dependent complex number MW 0 Computational importance 27rk 7 to obtain XkH HT from Xk for k 01 7N 717 we need only N operations 7 to obtain Xk from and from XkH 571 we need only 0Nlog N operations This can be done through FFT If we put and 9km in vector form7 we get 250 351 LeiZE k39l x gk fork01N71 129 zN 71 EjltN71gt We can then write N71 X Xkgk 130 k0 Since the gk s are pairwise orthogonal7 we can use the projection formula to calculate the coefficients and obtain the inversion formula 118 0 Remark 1 DFT 7 DTFT although related DFT discrete frequency k DTFT continuous frequency w Sec 1 3 Frequency Analysis 71 0 Remark 2 57 is periodic as a function of n with period N Therefore7 lDFT de nes a periodic signal for foo lt n lt 00 We will often think of as N periodic If we let X0 X f XN 7 1 then we can rewrite Eq 130 as N71 X Xkgk k0 X0g0 X1g1 XN1gN71 X0 g0 g1 gN71 E XN 7 1 g0 g1 gN71X BX 7 where B is an N x N matrix whose columns are gk s and whose entry BM in the n th row and k th column is given by 1 27rk71n71 Bnk N 57 N forn12 7N k12 7N To get the formula for DFT7 we premultiply X BX by the matrix A NBH7 where yH yT means the conjugate transpose of y Since the rows of BH are conjugate transposes of gk s7 we have H g g1 A N 7 f1 gN71 where ng lt 57390 57391 57239N1 The entry in the k th row and n th column of A is 7 ej ZW W 7 i 7 AkniNBnkie N fork7172 Nn712 7 7 7 N Premultiplying X BX by A7 we get AX ABX 72 CHAPTER 1 ANALYSIS OF DISCRETEATIME LINEAR TIMEAINVARIANT SYSTEMS Figure 135 An illustration of the DFT as matrix multiplication We now calculate AB g1 AB N 3 g0 g1 gNil H gNil g lgo g lgl g lgzvil gflgo gflgl glIgNil N g lgo g lgl g lgwil Note that since gilgp i ltgp7gkgt N71 7 ngn9kn7 n0 AB simpli es to i N i 0 AB N N 0 1 1 0 0 1 L where I is the identity matrix Sec 1 3 Frequency Analysis 73 Hence7 A and B are inverses of each other The DFT of x can then be calculated by X Ax From Fig 1357 we see that we need N2 complex multiplications for a brute force implementation of DFT However7 the fact that the matrix A is highly structured can be exploited to produce a much faster algorithm for multiplying a vector by this matrix

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I made $350 in just two days after posting my first study guide."

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.