New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

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

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here


by: Miss Flossie Collier

DigitalSignalProcess ECE8231

Miss Flossie Collier
GPA 3.96


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




Popular in Course


This 40 page Class Notes was uploaded by Miss Flossie Collier on Wednesday October 28, 2015. The Class Notes belongs to ECE8231 at Villanova University taught by Staff in Fall. Since its upload, it has received 32 views. For similar materials see /class/230590/ece8231-villanova-university in ELECTRICAL AND COMPUTER ENGINEERING at Villanova University.



Reviews for DigitalSignalProcess


Report this Material


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: 10/28/15
Department of Electrical and mnputcr Engineering ECE823 1 Digital Signal Processing httpwww ece villanova eduwhangECE823 1 Yimin Zhang Depamnent of Electrical amp Computer Engineering Villanova University Chapter 8 The Discrete Fourier Transform Introduction El In Chapters 2 and 3 we discussed the representation of sequences and LTI systems in terms of Fourier and ztransforms El For nite duration sequences it is possible to develop an alternative Fourier representation called the discrete Fourier transform DFT CI The DF I is a sequence rather than a function of a continuous variable It corresponds to samples equally spaced in 39equency of the Fourier transfonn of a signal Cl DFT plays a central role in the implementation of a variety of DSP algorithms because ef cient algorithms exist for the computation of DPT chapter 9 II We will begin by considering the Fourier series representation of periodic sequences Then we will consider the relationship between periodic sequences and nitelength sequences The Diserele Fourier Series I We rst review the Fourier series for periodic continuoustime signals For a continuoustime Tperiodic signal xt the Fourier series approximation can be written as 1 t a ejaxlrm m T k where 21d T is the fundamental frequency That is a periodic signal can be represented by a Fourier series corresponding to a sum of harmonically related complex exponential sequences In nitely many harmonically related complex exponentials are required The frequency of the complex exponentials are integer multiples of the fundamental 39equency ZnT The Diserele Fourier Series 2 El Consider a sequence 3112 that is periodic with period N so that fin 35Lquot 1N for any integer value of n and r El As with continuoustime periodic signals such sequences can be represented by a Fourier series corresponding to a sum of harmonieally related complex exponential sequences El The equency of the complex exponentials are integer multiples of the ftmdamental 39equency ZnN ie the Fourier series representation has the form mk z neWW I The Discrete Fourier 9911ch Time Fry Ilene Continuous aperiodic Aperiodic continuous Discrae aperiodic Periodic continuous Continuous Periodic Aperiodic discrete Discrete Periodic Periodic Discrete CI The period is 22 and the fundamental frequency is 2nN Cl Therefore the discretetime periodic signal case only requires N hannonically related complex exponentials The Diserele Fourier Series 1 I El Denote en e 2 Wquot Then for any mteger I we have chimp ejZxINklNn ejlxlnejmxlhf w ekpz Consequently the set of N periodic complex exponentials e091 e1n eNln de nes all the distinct periodic complex exponentials El Thus the Fourier series representation of a periodic sequence Tc39n need contain only N of these complex exponentials Therefore it has the form Nl N 3111 X k equot 2quot 393 N i0 El What is 521k The Diserele Fourier Series 5 a To obtain 521k we multiply both sides by quotMW and summing om n 0 to n N l we obtain 12 IN 1 g It mar ne m Xke quotquot HQ 30 520 Exploiting the orthogonality of the complex exponentials 8quot21ka rln 2 1 k r Mam an N quot0 0 otherwise Nl N l N 1 N l I w 2 Enej2xi m ej21Nk rnlXr n0 k0 Nix0 Therefore the Fourier series coef cients become N 1 3 k Z u e lcz m 0 The Discrete Fourier Series 6 u m is periodic with period N For integer I we have i k IN Z ne quot2quotW W quot 110 N l N Z 302181217 ejCZIINb1 k0 El For convenience of notation we can de ne Wv e jcz m Then the analysis and synthesis pair of discrete Fourier series DFS is expressed as M analysis equation 3 k Z 31 n W13quot k0 N l synthesis equation 3cquotn X leJM 150 DPS We can also use the notation 3quotn gt X k Examples of VS I Exanwle 1 DFS of a Perioaic Impulse Train El Consider the periodic impulse train nl2 nrN1 nrN ranymt6ger 0 otherwise Since 3c n 639 n for 0 s n s N l the DPS coef cients are found as N4 2211 2 5mm W 1 k0 If we synthesize the signal from the DPS coe cients we have n f kWg In ism rm i0 1 N k0 74 Examp es 01139 DIFS 2 gym 7 Bi 1 39qj m I g m mm awu a u Examples of VS 3 Exanwle 2 Dualigr in the DFS El We see that the two equations of DFS pair are very similar differing only in a constant multiplier and the sign of the exponents El Consider the periodic impulse train 171k 2 N6k rN Then quotw 1 3quot 1 2m n Z NYkWN kquot 2 kW b39 W 1 N M i0 El Compared with the previous example we see that 17kN k n1n Examples of DES 4 L 1 439 u a n CMUHSIW gt 39 mi gma L 39 quot 3 15 1 0 n 0 5 10 15 20 g g 3917 Xmazm e M WT m a u b 1quot 11 EMUk mm Examp es 0f DFS 5 Eimtg EE wfquotf n39 1 7 wmr A mag of Xk o N H 4 4 4 H H 4 4 4 H 4 r39o phase of Xk o N 439 I rupcrlics of DIN l El It is not surprising that many of the basic properties are analogous to properties of the Fourier and ztransforms Linearity El Consider two periodic sequences 3r n and 3n both with period N such that N we N DFS 61 n 6 X1 k x291 9 X zlk then DFS a331nbi 2n 45 aX1k bX2k Shi of 1 Sequence DFS El If 3 nlt gt X k then on N was n m 7 WyXIk W n H Xk l I rnpcrlics uf DFS 2 Sivnunetric Properties El If n X Uc thcn 3512 2 k DFS SET n lt gt x m Remnn fet k k quotkl J Imfflnl 3 3 okk k itn1in1i nn3f Re1k an3n JET uni 11mm I rnpcrlics uf I FS 5 Sjvnmetric Properties cont El When Z n is real than XkX k Rek Re39 k Imik1 humkn Iflklllfkn 4211 42H En1En1i n if Rem DFS N foln 3551quot n H Jquot 1mXk Properties of DFS 4 Periodic Convolution El Consider two periodic sequences 36M and 352 n both with period N and their DFS coef cients are 2 k and 22m respectively If we form the product f3k k2k then the periodic sequence 322 with DFS coefficients ZR is N l N I falnlZElmF2nml Zleml39fllnm El A convolution in the above form is referred to as a periodic convolution CI The duality theorem suggests that if Eda Eln139f2n then N l 1 N4 falkl flame 117 Emilie I TT N 13y ngwww M L11er w 1 m if f Vf fp v39YiW V QgLgxigg WLO NH 1w WI o O 2 0 o o O o o o N I ll i2 1 m 552m 7 1 WW Fourier 39l mnsl39orm nl39 l orimlic Signals I El As discussed in Chapter 2 uniform convergence of the Fourier transform of a sequence requires that the sequence be absolutely summable and meansquare convergence requires that the sequence be square summable Periodic sequence satisfy neither condition Cl However in Chapter 2 we know that sequences that can be expressed as a sum of complex exponentials can be considered to have a Fourier transform representation in the form of a train of impulse Cl Similarly it is often use rl to incorporate the DPS representation of periodic signals within the framework of the Fourier transform This can be done by interpreting the Fourier transform of a periodic signal to be an impulse train in the frequency domain with the impulse values proportional to the DPS eoe icients for the sequence Fourier l39rzmsl nrm nl39n quotnnslanl Consider the sequence xn1for all n This sequence is neither absolutely smmnble not square summable and the Fourier transform does not converge in either the uniform or mean square sense for this case However it is possible and useful to de ne the Fourier transform of the sequence xn to be the periodic impulse train m Xejquot 22750H27rr The impulses in this case are functions of a continuous variable and therefore are of in nite height zero width and unit area consistent with the fact that Fourier transform does not converge The above equation is justi es principally because result leads to correct inverse Fourier transform Fourier 39l ranxl39orm of 39mnplex Exponential Sequences Consider a sequence xn whose Fourier transform is the periodic impulse train Xequot 227602 600 27rr fw To obtain the inverse Fourier transform we can assume that 7tltCDOlt1 in this problem Then we need include only the r0 term and xiii i I 275 a mo efwndw em For coo0 this reduces to the sequence of a constant considered in the previous example Fourier 39l mnsl39nrm nl39 l crimlic Siunzllx 2 h El If 3311 is periodic with period N and its DFS coefficients are 521k then the Fourier transfomi of u is de ned to be the impulse train m w E Xe ANXk6m N El To show that 281 is a Fourier transform representation of EM we obtain the inverse Fourier u ansform as Oltslt2nN l xa i 1 ts w 2g X J Md X 6 quotquot61 2x e 9 w 2 32 N k 2 N 2 w 1 2quot w 27rk l 2quot ejam X j21lNlm N g XIk L8 5 at dc N 0 ke xn Fourier Transform of Periodic Siulmlx 3 9395 Exanqm The Fourier Transform ofa Periodic Impulse Train Cl Consider a periodic impulse train Iain i atn er rao we know that the DFS coefficients for this sequence are i5k1 for allk Therefore the Fourier transform of EDI is 2n Zak PM 5m ng N F f Tramsfmm f Pcerf qbdl q Sigma s 4 Q 2 mg pm wa g Na omw u m 01 SKEW Widbl mm d 5 1 W1 gt2quot i Eigg mam n J I T T T Y I I T T I I T T VN 0 N n Fourier 39l mnsl39nrm of l crimlic Sinllzllx 5 9quot El Denote the Fourier transform of xn as Xe then the Fourier transform of n becomes 52eiquot Xej 33e Xequot f 5 a 3 Ira66 N El Compare with the de nition of If 31quot we conclude that 21quot Xej2xmk Xe I gram That is DFS coemcients 171k are the equally spaced samples of Mei the Fourier transform of xln3c39n osnsN I i Xej2xN1k6w23k k gt 0 otherwise Fourier Tram brm of Periodic SigniniS 6 rah Mm C er arm n 0 o 01 x 0 5 1 0 1 5 20 I1 1 133 W aqmmm fL s 7 ML iwia i w gi k am m Fmm r5TFaMSf rma TPr md S gm S7 m 79w 7 m t 65 mm 5 Tlth D m Jr IXerI N k 4 X gt N quotI V a g gt zg gm AKQ Lgt4 waiQ paw r quotM 1m 1 A E 4 u a I n v v a Q 1 7T 27T 3 1T 477 gill 0 1o 20 k k8 Samp mg 0f the anr cer Tramsfwm 1 cmgir infal 1f ml u mgln Tip cam and Cmg fs w am mm mam F mim KW g and by Xiw aft Z kzW i339 Em MW sqzmmt 39 i 1 fufltjllt39 f i 301 52 mm a1le 1 b a mml 01mg M2 an N 379 amdl 111 i hlcea maid m 9m 2 m Vrr j wa riNMt u 4 A Lag gmmm 3939 a Unit 27P13ne circle If am w gg dia Q S E N 11 Sampling uf he Fnuricr Transform 2 El The sequence of samples 51k of Xz being periodic with period N could be the sequence of DFS coe icients of a sequence itquotn CI The sequence can be obtained as N l Nl I 1 1511 x xn1FZ Xej2 kINWNh i0 k0 A i mkqawmmwgm k0 armlt29 an 1 N4 ZxImJ Z WM mzwo Nk0 ixtmustn m 3140 UAquotquot quot 0 39 39m quot 39 wo n39vo quot A 39139 D Mump mg QM We me nagn Tmauug mm Q9 Cl 257 fs W 2mm ff o JA 71 f A a 73 KIWI1 AC If fWlfv Lquot1Q xn IIT 0 xn r zw n r12 Samp mg f 6 Wmm w Tmm mm 4 E Eu jg ag 90 Smilax TKO 1619 pmbl m of m m1 ms m wimpquot 1le RWEdlLUt 3 N Laurga Eggam i b Ikangm J f zr 219 ne map 10 m1 1 mi mmd 211a Chm th39eir handg Wham N t39hkaum of a iu F 2 439 39 39 f m wager 20 OV J IJO am 1166 p md Sampling of the Fourier l rzmsl orm 5 D To summarize if xn has nite length cf continuoustime signal sampling X00 is bandlimited and we take suf cient number a number greater than or equal to the length of xn of equally spaced samples of its Fourier transform cf continuous time signal sampling sampling rate should be larger than the Nyquist rate then the Fourier transform is recoverable from these samples and equivalently xn is recoverable from the corresponding periodic sequence 3212 through the relation Hn OSnSN l xw o otherwise El To recover xn it is not necessary to know Xelquot at all frequencies if xn has nite length Discrete Fourier 39rl39runsl39nrm I From the above discussion we understand that given a nite length sequence xn we can form a periodic sequence n which can be represented by a DFS ER 0n the other hand given the sequence of DES coefficients k we can nd 3c n and then obtain xn When the DFS is used in this way to represent nitelenng sequences it is called the discrete Fourier transform DFT It is always important to remember that the representation through samples of the Fourier transform is in effect a representation of the niteduration sequences by a periodic sequence one period which is niteduration sequence that we wish to represent Discrete Fourier 39l39ransl39orm 2 El We assume thatxn 0 outside the range 0 Sn SN 1 In many instances we will assume that a sequence has length N even if its length is M s N In such cases we simply recognize that the last N M samples are zero El When there is no aliasing the nitelength sequence xn and the periodic sequence 3111 are associated by 3111 z xnrN An alternative expression is 3111 xn modulo N For convenience we will denote it as 37TH x nv Iiltcrelc Fourier Transform 3 El The sequence of DFS coefficients XTk are periodic with period N To a duality between the time and frequency domains we will choose the Fourier coef cients that are associated with a niteduration sequence to Be a niteduration sequence corresponding to the one period of X k That is Xlk Xk OSkSiV l 0 otherwnse and Elk We modulo N1 Xk 1 Discrete Fourier Trelllsl39llrlll 4 El Recall that le and 35m are related as N N I Xk1 23 391le n0 e 1 N1 xn F xmwm The DFT pairs become N I N h Xm XkxnWN 03ng 1 0 otherwise 1quot b Enz XkW OsnsN l M 1 IN 0 otherwise Discrete Fourier 39l39ranxl39nrm 5 El Generally the DFT analysis and synthesis equations are written as follows m X k Erinle n0 1 Nl 4m xn X kWN k0 CI The relationship between xn and Xk will sometimes be denoted as DFT xln H Xlk Cl It is noted that if we evaluate xn outside 0 s n s N 1 the result will not be zero but rather a periodic extension of x39n Same can be said for Xk In de ning the DFT representation we are simply recognizing that we are only interested in values ofxn forOSnSN 1 andXIk forOSnSN l I x J I Wsatmm Fumm m Tr am mm i r AT T r 2 39 1 iAiGZQM39 1 xquot 0 4 I W k m 4 2 039 3 4 2o 1 ltXk 04 7T 02 7T 10


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

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

Jim McGreen Ohio University

"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."

Kyle Maynard Purdue

"When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the I made $280 on my first study guide!"

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!

Refund 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


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:

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

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.