An Introduction To The Mathematics Of Digital Signal Processing: Part I .

literature.In Part I of this tutorial we shall stick with i;Part II will use j, since signal processing is a branch ofengineering.)An imaginarynumberis any realnumbertimes i,and since the realsinclude the other numbersets, we can haveimaginary integers, imaginary rationals, even imaginarynaturals!The final set of numbersis just a combination of therealswith the imaginaries,which are called complex numbers.The set of all complex numbersis denoted C, and eachmemberof the set has the formx iyf(x)54 .Sx 1-(x)32 -f(x 3) 2.5x,yE Rwherex is called the "realpart",and iy is called the "imaginary part."Complexnumbersmay be added, subtracted,multiplied and dividedaccordingto the usual rules of algebra.If cl and c2 (read "c-sub-one and c-sub-2") are twocomplex numbers,with cl xl iyl and c2 x2 iy2, thenthe rules of complex arithmeticare as follows:Rule Cl (complex addition): To add two complex numbers,add the real and imaginaryparts independently,i.e.,-4-31-1--223456789-1--x-3 -Figure 1. A graphof f(x) .5x 1cl c2 (x1 iyl) (x2 iy2) (xl x2) i(y1 Y2)Rule C2 (complex subtraction)(similarto addition):c1 - c2 (xI iyl) - (x2 iy2) (x -x2) i(y 1 -Y2)Rule C3 (complex multiplication):The productis formedbythe ordinaryrules of algebra:C1c2 (xI iyl) (x2 iy2) X1X2 iY1x2 i1 y2 i2y1y2 (X x2 -Y1Y2) i (xy2 Y1X2)(Rememberthat by definition, i2 - 1)Rule C4 (complex division):Again,ordinaryalgebrais used todefine the quotient:Sc2 iy xx iyx2 iy2m, b constantsis the graphof a straightline. m is called the slope of thefunction since it is the amount by which the function changesfor a unit changein x. Setting m to .5, as in Figure 1, meansthat every time x increasesby one, f(x) will increaseby .5,hence a positive slope is associatedwith lines slopingupwardto the right.f(x) will always cross the vertical axis whenx 0, and since f(x 0) b, b is called the verticalaxisintercept of f The horizontalaxis will be crossed,of course,whenf(x) equalszero, which occursin this example at:f(x) .5x 1 0x -2x 2 Y12 i(y1x2 - XY2)x22 y2Actually, Figure 1 is not a graphof f(x) .5x 1, but morepreciselya graphof this function for the values of x between- 4 and 9, or in most propernotation:obtained by multiplyingbyiy which is equivalentto 1.x2 2-- iY2While a function is most generallystated in algebraicform, it is often enlighteningto drawgraphsin orderto get aclearidea of how a function variesas its argumentchanges.The conventionalgraphuses a horizontalline to representtheindependentvariable,and a verticalscale to representvaluesofthe function. Thus,in orderto find the value of a function forsome value of the independentvariable,say, x 3, we slideone fingeralong the horizontalaxis until we point at 3, thenmove straightup (or down) to find the valuef(x 3) (read:"the functionfat x 3").A glance at Figure 1 tells us severalthings about thefunction f(x) .5x 1. First, the graphis a straightline,sloping upwardsto the right; second, it crosses the verticalaxis at the value 1; third,it crossesthe horizontalaxis at thevalue -2. In fact, any function which has the formPage 40f (x) mx bf(x) .5x 1- 4 x 9The original function could extend for all x, that is x 0, but graphingthe entirety of such a functionwould requirea very big piece of paperindeed. Graphsare useful to get the generalpictureof a function, but they can serveother purposesas well. For example, it is often useful to addgraphs directly, especially when it is difficult to do theaddition algebraically,or when the algebraicsum of twofunctions is difficult to interpret.Graphicaladdition of twofunctions consists of carefully drawingboth functions on thesame graph,and then carefullyaddingup the verticaldistancesfor all (or many) valuesof the independentvariable,to obtaina graphof the sum function (see Figure 2). Such graphicaltechniques are, of course, only approximate,but oftensufficient to gain considerableinsight into the shape ofcomposite functions.Computer Music Journal, Box E, Menlo Park, CA 94025This content downloaded from 165.123.228.54 on Wed, 03 Feb 2016 11:57:34 UTCAll use subject to JSTOR Terms and ConditionsVolume II Number 1

if the equationhas the formax2 bx c 0h (x) f(x) g(x)4then-b/X 3.5g(x) x2If(x)\2\/The method 2 solution yields:x2 x -6 0 0(x 3)(x-2)x -3 or 2h( ) f(1) g(1)--1.5- - - -\.5x 1Themethod 3 solution, with a 1, b 1, and c - 6 alsoyieldsf(()X-3 -2.52 -1.5 -1-.5-5-.-.511.52J -4b2- 4ac2a2.53-b /b"- 4ac2a2a-1-1-1.5-?J12-4.1.(-6)2-1-1 5- -3or22What about such formulasas x2 1 0? The quadraticformulaworksjust as well on those:-1- 2-2-2TFigure2. Graphicaladdition of f(x) .5x 1 andg(x) x2to get graphof h (x) f(x) g (x) x2 .5x 1a 1, b 0, c 1,sox Polynomialsand RootsA polynomial is an algebraicexpressionwhich has theform:f(x) ao al x a2x2 a3x3 ? 2i2 ior-iwhich says that againthere are 2 roots, and that they are bothimaginary.In factorialform, we could have written anxnThe a's are constants (numbers)called coefficients, and thehighest power of x which occurs in any given polynomial(n) is called the degree of the polynomial. Thusf(x) inFigure 2 is a first-degree polynomial, since the greatestpower of x in .5x 1 is one. Both g (x) and h (x) from thesame figure are second degree, or quadratic,polynomials.Third degree polynomials are called cubic, fourth degreequartic, and so on, though after that one rarelyhears of,say, "quinticpolynomials"instead of "fifth-degreepolynomials." A polynomial is "solved"by setting it to zero, andfinding which values of the independentvariablemake theequation true. For example, to find the roots of the quadraticequationx2 x - 6 0, we can do any of at least three things:1. try every value of x and see when the formulais true,2. try to factor the polynomial,or3. use the quadraticformula, which will give the roots forany quadraticpolynomial.Method 1 may sound a bit absurd,but sometimesit is the bestwe can do. Method2 meanstryingto write the polynomialinthe form (x- zl) (x - z2) 0. zl and z2, are called the"zeroes" of the function, since if x is equal to zl, the firstfactor, and hence the product, will be zero; and similarlyforx z2. Method 3 requiresrememberingthe generalsolutionfor any second-degreepolynomial (or looking it up), calledthe quadraticformula:0?J x2 1 (x -i)(x i) 0The Fundamental Theorem of Algebra states that anynth-degreepolynomialalwayshas exactly n roots, that theymay in generalbe complex (havingboth real and imaginaryparts),and that all the roots may not be different from eachother (distinct). Also, we might have guessedthat if i is asolution to x2 1 0, then - i is also, since complex rootsalways appearin conjugatepairs if the coefficients of thepolynomial are real numbers.(If c x iy is a complexnumber,then its conjugate,written c* , is x - iy.)If the generalformulamethod works so well, why wouldwe ever use factoring,or trial and error?The answeris bothsimple and unfortunate: General formulas exist only forpolynomialswith degreeless than 5, and in fact the FrenchmathematicianGaloisprovedthat no such formulascan existfor degree5 or more. Even the generalquarticformulais verycomplicated;it is often easierto factor than to use it! Andfinally, trial and errorsolutions are often implementedwithcomputers,using specialguessingalgorithmssuch as Newton'sMethod,which work remarkablywell.Exponents, Logarithms,and the NumbereIf we say that addition and subtractionare easy, thatmultiplication and division are harder, and that taking anumberto a power is most difficult, then the rules of expo-F. R. Moore: An Introduction to the Mathematics of Digital Signal Processing, Part IThis content downloaded from 165.123.228.54 on Wed, 03 Feb 2016 11:57:34 UTCAll use subject to JSTOR Terms and ConditionsPage 41

nents show us how many problemsin mathematicsmay bemade one level easier! It is important to rememberwhichkinds of numbersthese rulesapply to, so in the followinglist,we will use p and q to stand for any realnumbers(that is,p, q E R), a and b are positive reals(a, b E R?), and m andn are positive integers(m, n E N).Rule El:Rule E2:aP - aaq aP q a - qRule E3:(aP)q apqRule E4:nflF- am/nlogax K logbxwhereKlogba1Rule E5:a-pRule E6:ao 1 (if a*0)RuleE7:na 1Rule E8:(ab)P aPK is givenin the following table for base changesamong 10,2, and e:b10Rule Ll:logaxy logaX logayRule L2: logax - logayylogaylogaxY y 9.1.44270.1Thusloglox .30103 log2x .43429 Inxand so on, where In stands for "naturallogarithm"(i.e.,In x Logarithmsare defined only for positivelogex).numbers.Wheredoes the numbere come from? Unfortunately,its true originsareburieddeep within calculus,which is not apart of our subjectmatter,but some of its properties,as weshallsee, turn out to be remarkable.e is an irrationalnumberlike 7r,which meansthat its decimalexpansionis both infiniteand that it neverrepeatsitself:e 2.71828 18284 59045 23536 0287.wherex, y E R.Also, if logax p, then x is called the antilogarithmof p to the base a, writtenx antilogap, since by definitionaP x.Any numberexcept 0 or 1 may be used for the base, but infact only three numbersare used very often: 10, 2, ande 2.71828. . Logarithmsto the base 10 are used becausewe commonly use a decimal (base 10) number system foreverythingelse! Logarithmsto the base 2 are very oftenencounteredin the relativelynew fields of computerscienceand information theory, since computers typically operateusing binaryarithmetic(internally),and both computersandinformation theory define the unit of informationas a bit(short for binary digit). Logarithmsto the base e are called"natural"logarithms,and are the most used in mathematics.It is hard for us today to appreciatewhat a boonlogarithmswere to mathematiciansbefore the adventof computersand pocket calculators.Logarithmswere so useful thattwo 16th century mathematiciansliterally devoted most ofPage 422 apbpUsing these rules, we can deduce such things as 4s 2(Rule E4, since .5 ?), x'/x5 x-' 1/x (Rules E2 andES), and /-6 -2 4J3(Rule E7). In fact, the first 3 rulesareso useful in doing calculations,that the entire system oflogarithmshas been devisedto make them universallyapplicable to the more "difficult" problems of multiplication,division,and exponentiation.If ap x, wherea is not 0 or 1, then p is called thelogarithm to the base a of x, written logaX p. Thus,log28 3, since 23 8, and loglo10000 4, since10000 104. The rules for logarithmsare derivedfrom El,E2 and E 3, above:Rule L3:their lives to calculating"log tables"in orderto relievetheircolleagues of the drudgeryof multiplicationand division:Briggscalculatedthe so-called common, Briggsian,or base 10logarithms,and Napier the "natural",Naperian,base e logarithms. Base 2 logarithmsare not found in mathematicalhandbooks, and they probably never will be, since theircomputation today is largely a matter of button-pushing.Also, if the log of a numberis availablein any one base, it iseasy to changeit to anotherbase using the following relationships:If you would like to calculateit to more accuracythan this,the following formulamay be used:e 1 -I 11!2!1 I 14!3!1 "wheren! meansn factorial, which is the product of all theintegersfrom one to n (3! 6, 4! 24, 5! 120, etc.).A more useful form of this infinite expressionyields thevalue of e raisedto any powerx:2e 1 324T.Another way to write the same thing is with sum notation:eX 1 XwhichthesameThe capital"says"exactlysig lthing.which "says"exactly the same thing. The capitalsigma(Computer Music Journal, Box E, Menlo Park, CA 94025This content downloaded from 165.123.228.54 on Wed, 03 Feb 2016 11:57:34 UTCAll use subject to JSTOR Terms and Conditions) isVolume II Number 1

used to denote that we should add up all valuesof xn/n!startingwith n 1, then n 2, etc. (It is read: "the sum over nfrom one to infinity of x to the n dividedby n factorial".)Sums and SeriesSuch formulasas the one above for ex are called infiniteseries, or infinite sequences, since there are infinitely manytermsin the sum, even though we know what any one of themwould be. Such sums need not be infinite, of course. Forexample,the following formulaillustratesa finite sum:their beautiful princesswas known only to initiates, for itconveyed all of their secrets at once. The name of theirprincesswas Sohcahtoa.]If we label a right triangle (one which contains aright angle) with respect to an anglee- (see Figure3), sideO is opposite the angle, side A is adjacent to anglea, andside H is, of course,the hypotenuse of the triangle.n 1 2 3 - nkk 1Owhich is just the sum of the first n integers.It is both interesting and useful that many such sumshave a general,or "closedform" formula,makingit unnecessaryto carryout the lengthyaddition sequence.For example:nk1)n (n 2n1 2 3 . The closed form is clearlymore useful if n is greaterthan 3 or4 or so. Other sum formulasoften crop up in digital signalprocessing.For exampleo00Earkk O248 E k 0 sina HA cos e Hsineof acosine of o2-k -OAtangentof a tanaoo1 A The 3 basic trigonometricfunctions are defined asfollows:rThis sum exists only if r 1, since otherwisethe sum will beinfinite, a is the first term in the sequence,and r is called theratio, since it is multipliedby any term to get the next term inthe sequence. Thus, we see thatICa a ar ar2 1Figure3. A right trianglewith inscribedanglee and sidesO, A, and Hnk 1a2Clearly,the size of the righttriangledoesn't matter,since, fora givenanglea, if we double the length of one of the sides, theotherswill double as well. Only the ratios of their lengths areneeded to define the trigonometricfunctions.The 3 remainingtrigonometricfunctions are definedin termsof the first 3:l-MIf there is not an infinite number of terms, we can removethe restrictionthat r be less than 1:cosecant of e cscesecant of a seccotangentofan-1ark rnalr(1-r)1-rk OIf r # 1, and the last term 1 ar n -1 , then this sum is alsoequal toa - rl1 -rTrigonometry[It has been said that a tribe called the TrigonometricIndians once roamed the earth, that they spoke in sinelanguage,and never used wrong angles. The secret name of1- sinH- OH1Acos e- - A1A cot atanl- O Radians,Degrees,and GradsAs almosteveryoneknows, if you slice a pie into 360equal wedges,you have not only very smallslices to eat, butthe angleat the tip of each slice will be one degree(1 0). Ifyou are very hungry,however,and slice the pie into 4 equalpieces, the angleat the tip of each slice will be 900, which isexactly right.Anothermeasureis to dividethe circularpie into 400equal pieces, or 400 grads.But by far the most commonmeasureof anglesused in mathematicsis the radian. Sincethe ratio of the circumferenceof a circle to its diameteris7r 3. 14159 26535 ., and since the radiusof a circleF. R. Moore: An Introduction to the Mathematics of Digital Signal Processing, Part IThis content downloaded from 165.123.228.54 on Wed, 03 Feb 2016 11:57:34 UTCAll use subject to JSTOR Terms and ConditionsPage 43

is exactly one half its diameter, the circumferenceof acircle is exactly 2nrtimes the length of its radius,and we saythere are 21rradiansin a circle. A right angleis then any of900, 100 grads,or n/2 radians,dependingon which measurewe areusing.If we choose a circle with radiusequal to one unit,and we inscribe our right trianglesinside the circle (seeFigure4),is also equal to one, as is sin - 3n/2. In fact sin-11 e hasinfinitely many solutions, all of the form e i/2 k2n,where k is any integer. The principle values of the inversetrigonometricfunctions are chosen to be close to e 0,and these are used to resolvethe problemof which answertochoose. Thus:sin-' x ? 22 02 cos-'x nr , and tan-1x? 2Inspection of Figure 5 also shows that the sine andcosine functions are also identical to each other, except fortheir startingplace at e 0, i.e., they differ only in phase:2H2 Osin(-- %., e) , andcosocos(&- ) sinesin e/IIIICOS&IIII/IIFigure4. A unit circle with inscribedrighttriangleswe can "solve" the triangles conveniently with thePytha orean theorem: 02 A2 H', or 02 A2 1,. Anglesare conventionallyO 1 - A , and A 7J1--Ufrom the right hand horizontalmeasuredcounter-clockwiseaxis (see a1, and a2 in the figure). Angles measuredin aclockwise directionare considerednegative.We can treat the anglee as an independentvariableandgraphthe basic functions as shown in Figure5.The inversetrigonometricfunctions are defined in asimilarway to the antilogarithm:if sin a x, then the arcsineof x sin-1x 0, and so on, for each of the six trigonometricfunctions.We can see from the graphof sin e that the function isperiodic, that is, it repeatsitself over and over againas e getslargeror smallerby 27r,which is called the period of sin e.Furthermore,sin & always has a value between 1 and - 1inclusive,so we say that the domainof the sine function is theset of all realnumbersbetween I and - 1, or in more mathematical form:sinE R , - 1 sin e 1Because of this restricteddomain, it is meaninglessto writesin-12 o, since no anglee has a sine equal to 2. But whatabout sin-' 1 e? From the graph,it is clear that sin 7r/2 1,so, o 7r/2 is one solution to this equation. But sin 5nT/2Page 44IIIIIIIItan eiIIi/i1.IiIIII007r27rr223r237r27r 57r5 2227r31r37T71r 44rr2271rFigure5. Graphsof sin e-, cos e, and tan e as functions ofe,& in radians.TrigonometricIdentitiesMany formulasmay be derivedfrom the basic definitions of the trigonometricfunctionswhich are often useful inthe manipulation of equations involving trigonometricfunctions. They are called identities since, like all equations,the expressionson either side of the equal sign "say"exactlythe same thing, but in a useful way. In the followingidentities,A and B are any angles:Computer Music Journal, Box E, Menlo Park, CA 94025This content downloaded from 165.123.228.54 on Wed, 03 Feb 2016 11:57:34 UTCAll use subject to JSTOR Terms and ConditionsVolume II Number 1

(T1): sin2A 2 sin AcosA(T2): cos 2A cos2 A - sin2 A(T3): sin2 A ? - /2cos 2A(T4): cos2 A 1/2cos 2A(TS): sin A sin B 2 sin 1 (A B) cos ? (A - B)(T6): sin A - sin B 2 cos x (A B) sin ? (A - B)(T7): cos A cos B 2 cos ? (A B) cos 1 (A - B)(T8): cos A - cos B 2 sin (A B) sin a (B - A)(T9): sin A sin B 1/2[cos(A - B) - cos (A B)](T10): cos A cos B ? [cos (A - B) cos (A B)](T11): sin A cos B 1/2[sin (A - B) sin (A B)](T12): sin (A ? B) sin A cos B cos A sin B(T13): cos (A B) cos A cos B T sin A sin BThese identities are fairly easy to derivefrom each other, and,of course,many more exist.Like ex, the sine and cosine functions may be represented as summationseries:sinx x-x3!2cosx 1-2!2! ----5!X44!4 !" --7!X66!"-'" wherex is an anglemeasuredin radians.other words, pitched soundshave periodsrangingfrom about1/20 to 1/20, 000 of a second. The amplitude,or strength,ofthe vibrationis a measureof how far the pressuredeviatesfrom the atmosphericmean. One could measurethe peakdeviation from the mean, or possibly the averagedeviation,but the word amplitudegenerallyrefersto the peak deviation,unless stated otherwise,and is relatedto our perceptionof theloudness of a sound. Finally, the general shape of thewaveformdeterminesits tone quality,or timbre.All of thesefactors interact perceptually.For instance, the pitch can beaffected by the amplitudeand the shape as well as the periodof a waveform.Hence it is importantto distinguishbetweenfrequency, which is a measureof the repetition rate of aperiodic waveform,and pitch, which is our perception ofsomethinglike the "tonalheight" of a sound.An importantmathematicaltool which will be describedin Part II of this tutorial is Fourier's theorem, which statesthat any periodic waveformcan be describedas the sum ofa number,possibly an infinite number,of sinusoidalvariations,each with a particularfrequency, amplitude, and phase.Futhermore,there is a method for determiningexactly whatthese frequencies,amplitudes,and phasesmust be in ordertore-construct the waveformby addingtogether sine waves,which are seen to be the basic "buildingblocks" of periodicwaveforms.Actually there are a few other requirementsaswell as periodicity;suffice it to be said that any waveformwhich could exist in the physicalworld will obey these otherconditions (called the Dirichletconditions).Stated mathematically,the waveformmust obey theconditionf(t) f(t T), wheref is the periodicwaveform,t is time, and T is the period of the waveform.ThenUsing Tr

requires understanding of calculus. But digital signal processing inherently requires less calculus than analog signal processing, since the integral signs are replaced by the easier-to- understand discrete summations. It is an experimental goal of this tutorial to see how far into digital signal processing it is possible to explore without .