Fast Fourier Transform (FFT)

<body onLoad="MM_checkPlugin('Shockwave Flash','','http://www.riskglossary.com/default_nofl.htm',false);return document.MM_returnValue" stylesrc="../_private/template.htm" bgcolor="#FFFFFF" link="#669933" vlink="#000000" alink="#000000"> <div align="center"> <center> <table border="0" cellpadding="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="100%" id="table1"> <tr> <td width="740"> <table border="0" cellpadding="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="100%" height="37" id="table2"> <tr> <td height="35" width="100%"> <table border="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="100%" cellpadding="0" id="table3"> <tr> <td width="100%" align="left" valign="top"> <p class="header_gold">Fast Fourier Transform (FFT)</td> <td width="45" align="right" valign="bottom"> <map name="FPMap6"> <area href="http://www.contingencyanalysis.com" shape="rect" coords="1, 0, 44, 11" target="_top"> </map> <img border="0" src="../images/home.gif" usemap="#FPMap6" width="45" height="12"></td> </tr> </table> </td> </tr> <tr> <td width="100%" bgcolor="#CC9966" height="2"> <img border="0" src="../images/blank_2x2.gif" width="2" height="2"></td> </tr> <tr> <td width="0%" valign="top" bgcolor="#FFFFCC"> <table border="0" style="border-collapse: collapse" bordercolor="#111111" width="100%" cellpadding="0" cellspacing="1" id="table4"> <tr> <td width="0%" align="left" valign="top"> <p class="header2_black">Explained:<br> <img border="0" src="../images/blank_1x100.gif" width="100" height="1"></td> <td width="100%" align="left" valign="top"><p class="word_list"> <a target="_self" href="#fast Fourier transform">fast Fourier transform</a><p class="word_list"> <a target="_self" href="#Fourier transform">Fourier transform</a><p class="word_list"> <a target="_self" href="#inverse Fourier transform">inverse Fourier transform</a></td> </tr> </table> </td> </tr> </table> <p class="body">Given a function <i>h</i>(<i>t</i>), its <b> <a name="Fourier transform">Fourier transform</a></b> <i>H</i>(<i>f</i>) <a name="[1]">is</a>:</p> <table border="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="100%" cellpadding="0" height="36" id="table5"> <tr> <td width="100%" align="center"> <p class="body"> <img border="0" src="../formulas/fft_1.gif" width="158" height="58"></td> <td width="5%" align="right"> <p class="body">[1]</td> </tr> </table> <p class="body">where <i>i</i> is the <a href="../articles/imaginary_numbers.htm">imaginary</a> square root of –1. The Fourier transform <i>H</i> is a function of some other variable <i> f</i>. The process can be reversed at any point <i>t</i> where <i>h</i> is continuous by taking <a name="inverse Fourier transform">the <b> inverse</b></a><b> Fourier <a name="[2]">transform</a></b><a name="[2]">:</a></p> <table border="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="100%" cellpadding="0" height="36" id="table6"> <tr> <td width="100%" align="center"> <p class="body"> <img border="0" src="../formulas/fft_2.gif" width="152" height="58"></td> <td width="5%" align="right"> <p class="body">[2]</td> </tr> </table> <p class="body">This may seem abstract, but Fourier transforms are widely used in practical applications. The classic example is signal processing. A signal can be represented as a function of time <i>t</i> or as a function of frequency <i>f</i>. You switch between the two representations by applying the Fourier transform or inverse Fourier transform.</p> <table border="0" cellpadding="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="345" align="left" id="table7"> <tr> <td width="336"> <script type="text/javascript"></script> <script type="text/javascript" src="http://pagead2.googlesyndication.com/pagead/show_ads.js"> </script>  </td> <td width="9"> </td> </tr> </table> <p class="body">Fourier transforms are also used to solve partial differential equations. Accordingly, they are used in applications where partial differential equations arise, such as physics and financial engineering.</p> <p class="body">Many software packages numerically evaluate Fourier transforms and their inverses. Results will be poor (often downright wrong) if the software employs standard techniques of numerical integration to evaluate integrals [<a href="#[1]">1</a>] and [<a href="#[2]">2</a>]. Such techniques are ill suited to the oscillatory integrands encountered with Fourier transforms. Effective software employs a technique known as the <b> <a name="fast Fourier transform">fast Fourier transform</a></b> (FFT). This algorithm was discovered by Cooley and Tukey (<a target="_self" href="#Cooley">1965</a>). It runs rapidly and provides excellent results. It was one of the most significant discoveries in applied mathematics in the latter part of the 20<sup>th</sup> century. It revolutionized telecommunications. See Brigham (<a target="_blank" href="http://www.riskbook.com/link/brigham_e_(1988).htm">1988</a>) for a discussion of Fourier transforms and the fast Fourier transform. </p> <p class="body">If you use off-the-shelf software to value Fourier transforms, be aware that the definitions of the Fourier transform and inverse Fourier transform are not standardized. Check your software literature for the precise definition it uses, and modify output if necessary. </p> <p class="body">To illustrate the use of fast Fourier transform software, consider the <a name="[3]">function</a>:</p> <table border="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="100%" cellpadding="0" height="36" id="table8"> <tr> <td width="100%" align="center"> <p class="body"> <img border="0" src="../formulas/fft_3.gif" width="111" height="49"></td> <td width="5%" align="right"> <p class="body">[3]</td> </tr> </table> <p class="body">which is graphed in Exhibit 1:</p> <div align="center"> <center> <table border="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="350" cellpadding="0" id="table9"> <tr> <td> <p class="exhibit_header"><span class="exhibit_header">Example: Graph of <i>h</i>(<i>t</i>)</span><br> <span class="exhibit_subheader">Exhibit 1</span></td> </tr> <tr> <td bgcolor="#CC9966" height="2"> <img border="0" src="../images/blank_2x2.gif" width="2" height="2"></td> </tr> <tr> <td> <img border="0" src="../images/ex1_fast_fourier_transform.gif" width="350" height="131"></td> </tr> <tr> <td> <p class="exhibit_legend">The graph of function [<a href="#[3]">3</a>] is indicated. The example of this section explains how to use fast Fourier transform software to take its Fourier transform.</td> </tr> </table> </center> </div> <p class="body">Although the function is defined for all <a href="../articles/set.htm">real numbers</a>, it can only be input to fast Fourier transform software on a finite interval. For this example, the interval considered is [–3,3]. Whatever interval you choose, it should be large enough to capture what is “important” about the function. To avoid an effect called aliasing, choose an interval such that the function equals 0—or almost 0—at the end points. The fast Fourier transform software treats the function as periodic, as illustrated in Figure 3.</p> <div align="center"> <center> <table border="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="350" cellpadding="0" id="table10"> <tr> <td> <p class="exhibit_header">The fast Fourier transform treats functions as periodic<br> <span class="exhibit_subheader">Exhibit 2</span></td> </tr> <tr> <td bgcolor="#CC9966" height="2"> <img border="0" src="../images/blank_2x2.gif" width="2" height="2"></td> </tr> <tr> <td> <img border="0" src="../images/ex2_fast_fourier_transform.gif" width="350" height="131"></td> </tr> <tr> <td> <p class="exhibit_legend">fast Fourier transform software treats your input function as one period of a periodic function that repeats continually on the real number line. This is illustrated with three periods for the function [<a href="#[3]">3</a>], which is depicted in Exhibit 1.</td> </tr> </table> </center> </div> <p class="body">Because of this imputed periodicity, you can shift the interval over which you input the function to the fast Fourier transform software. For technical reasons, you want to shift it so the left end-point is 0. For this example, the interval [0,6] is used instead of [–3,3] to input function [<a href="#[3]">3</a>] to the fast Fourier transform software. Described in this manner, the function appears as in Exhibit 3. Note that the function in Exhibit 3 is different from function [<a href="#[3]">3</a>], but it communicates the same information.</p> <div align="center"> <center> <table border="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="350" cellpadding="0" id="table11"> <tr> <td> <p class="exhibit_header">Example: Shifted Function <i>h</i>(<i>t</i>)<br> <span class="exhibit_subheader">Exhibit 3</span></td> </tr> <tr> <td bgcolor="#CC9966" height="2"> <img border="0" src="../images/blank_2x2.gif" width="2" height="2"></td> </tr> <tr> <td> <img border="0" src="../images/ex3_fast_fourier_transform.gif" width="350" height="131"></td> </tr> <tr> <td> <p class="exhibit_legend">Since fast Fourier transform software treats functions as periodic, you may shift the interval over which you input the function. For technical reasons, you want to shift the interval so that its left end point is 0. In the example, the interval [0,6] is used.</td> </tr> </table> </center> </div> <p class="body">Now sample (evaluate) the function at a <a href="../articles/set.htm">set</a> of <i>n</i> evenly spaced values for <i>t</i> on the interval [0,6]. The number <i>n</i> of sampled values must be a power of 2. Let’s sample 2<sup>5</sup> = 32 values. Let <font face="Times New Roman">Δ</font> = 6/32 = .1875 be the sample interval. Note that you sample at the left end-point but not the right end-point. In the example, the function is sampled at <i>t</i> = 0 but not at <i>t</i> = 6. </p> <p class="body">Output from the fast Fourier transform software comprises <i> n</i> values that are proportional to values of the Fourier transform <i> H</i>(<i>f</i>). To make them equal to <i>H</i>(<i>f</i>), multiply by <font face="Times New Roman">Δ</font>. Example results are indicated in Exhibit 4:</p> <div align="center"> <center> <table border="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="400" cellpadding="0" id="table12"> <tr> <td> <p class="exhibit_header"><span class="exhibit_header">Example: fast Fourier transform inputs and outputs</span><br> <span class="exhibit_subheader">Exhibit 4</span></td> </tr> <tr> <td bgcolor="#CC9966" height="2"> <img border="0" src="../images/blank_2x2.gif" width="2" height="2"></td> </tr> <tr> <td> <div align="center"> <table border="0" cellspacing="0" cellpadding="0" style="border-collapse: collapse" id="table13"> <tr style="height:10.0pt"> <td width="43" style="width:31.95pt;" class="body" height="18"> <p align="center" style="text-align:center;text-indent:0in"> <i> <span lang="FR"> t</span></i></td> <td width="38" style="width:.4in;" class="body" height="18"> <p align="center" style="text-align:center;text-indent:0in"> <span lang="FR"> <i>h</i>(<i>t</i>)</span></td> <td width="46" style="width:34.6pt;" class="body" height="18"> <p align="center" style="text-align:center;text-indent:0in"> <i>f</i></td> <td width="46" style="width:34.6pt;" class="body" height="18"> <p align="center" style="text-align:center;text-indent:0in"> <i>H</i>(<i>f</i>)</td> <td width="46" valign="top" style="width: 1; padding-left: 0pt; padding-right: 0pt; padding-top: 0in; padding-bottom: 0in" class="exhibit_legend" rowspan="17" bgcolor="#CC9966"> <p style="margin-top: 0; margin-bottom: 0"> <img border="0" src="../images/blank_1x1.gif" width="1" height="1"></td> <td width="43" style="width:31.95pt;" class="body" height="18"> <p align="center" style="text-align:center;text-indent:0in"> <i> <span lang="FR"> t</span></i></td> <td width="38" style="width:.4in;" class="body" height="18"> <p align="center" style="text-align:center;text-indent:0in"> <span lang="FR"> <i>h</i>(<i>t</i>)</span></td> <td width="46" style="width:34.6pt;" class="body" height="18"> <p align="center" style="text-align:center;text-indent:0in"> <i>f</i></td> <td width="46" style="width:34.6pt;" class="body" height="18"> <p align="center" style="text-align:center;text-indent:0in"> <i>H</i>(<i>f</i>)</td> </tr> <tr style="height:10.0pt"> <td width="43" valign="top" style="width:31.95pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 0.0000</span></td> <td width="38" valign="top" style="width:.4in;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 1.0</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 0.0000</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 3.9375</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 3.0000</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 0.0</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> -2.6667</span></td> <td width="49" valign="top" style="width:36.4pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 0.1875</span></td> </tr> <tr style="height:10.0pt"> <td width="43" valign="top" style="width:31.95pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 0.1875</span></td> <td width="38" valign="top" style="width:.4in;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 1.0</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 0.1667</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 1.6871</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 3.1875</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 0.0</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> -2.5000</span></td> <td width="49" valign="top" style="width:36.4pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> -0.0888</span></td> </tr> <tr style="height:10.0pt"> <td width="43" valign="top" style="width:31.95pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 0.3750</span></td> <td width="38" valign="top" style="width:.4in;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 1.0</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 0.3333</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> -0.7991</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 3.3750</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 0.0</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> -2.3333</span></td> <td width="49" valign="top" style="width:36.4pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> -0.1062</span></td> </tr> <tr style="height:10.0pt"> <td width="43" valign="top" style="width:31.95pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 0.5625</span></td> <td width="38" valign="top" style="width:.4in;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 1.0</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 0.5000</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> -0.0633</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 3.5625</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 0.0</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> -2.1667</span></td> <td width="49" valign="top" style="width:36.4pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 0.1950</span></td> </tr> <tr style="height:10.0pt"> <td width="43" valign="top" style="width:31.95pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 0.7500</span></td> <td width="38" valign="top" style="width:.4in;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 1.0</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 0.6667</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 0.4527</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 3.7500</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 0.0</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> -2.0000</span></td> <td width="49" valign="top" style="width:36.4pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> -0.0777</span></td> </tr> <tr style="height:10.0pt"> <td width="43" valign="top" style="width:31.95pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 0.9375</span></td> <td width="38" valign="top" style="width:.4in;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 1.0</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 0.8333</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> -0.3075</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 3.9375</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 0.0</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> -1.8333</span></td> <td width="49" valign="top" style="width:36.4pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> -0.1349</span></td> </tr> <tr style="height:10.0pt"> <td width="43" valign="top" style="width:31.95pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 1.1250</span></td> <td width="38" valign="top" style="width:.4in;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 1.0</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 1.0000</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> -0.0658</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 4.1250</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 1.0</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> -1.6667</span></td> <td width="49" valign="top" style="width:36.4pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 0.2212</span></td> </tr> <tr style="height:10.0pt"> <td width="43" valign="top" style="width:31.95pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 1.3125</span></td> <td width="38" valign="top" style="width:.4in;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 1.0</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 1.1667</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 0.2828</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 4.3125</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 1.0</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> -1.5000</span></td> <td width="49" valign="top" style="width:36.4pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> -0.0704</span></td> </tr> <tr style="height:10.0pt"> <td width="43" valign="top" style="width:31.95pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 1.5000</span></td> <td width="38" valign="top" style="width:.4in;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 1.0</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 1.3333</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> -0.1875</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 4.5000</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 1.0</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> -1.3333</span></td> <td width="49" valign="top" style="width:36.4pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> -0.1875</span></td> </tr> <tr style="height:10.0pt"> <td width="43" valign="top" style="width:31.95pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 1.6875</span></td> <td width="38" valign="top" style="width:.4in;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 1.0</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 1.5000</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> -0.0704</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 4.6875</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 1.0</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> -1.1667</span></td> <td width="49" valign="top" style="width:36.4pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 0.2828</span></td> </tr> <tr style="height:10.0pt"> <td width="43" valign="top" style="width:31.95pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 1.8750</span></td> <td width="38" valign="top" style="width:.4in;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 1.0</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 1.6667</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 0.2212</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 4.8750</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 1.0</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> -1.0000</span></td> <td width="49" valign="top" style="width:36.4pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> -0.0658</span></td> </tr> <tr style="height:10.0pt"> <td width="43" valign="top" style="width:31.95pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 2.0625</span></td> <td width="38" valign="top" style="width:.4in;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 0.0</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 1.8333</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> -0.1349</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 5.0625</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 1.0</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> -0.8333</span></td> <td width="49" valign="top" style="width:36.4pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> -0.3075</span></td> </tr> <tr style="height:10.0pt"> <td width="43" valign="top" style="width:31.95pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 2.2500</span></td> <td width="38" valign="top" style="width:.4in;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 0.0</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 2.0000</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> -0.0777</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 5.2500</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 1.0</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> -0.6667</span></td> <td width="49" valign="top" style="width:36.4pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 0.4527</span></td> </tr> <tr style="height:10.0pt"> <td width="43" valign="top" style="width:31.95pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 2.4375</span></td> <td width="38" valign="top" style="width:.4in;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 0.0</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 2.1667</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 0.1950</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 5.4375</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 1.0</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> -0.5000</span></td> <td width="49" valign="top" style="width:36.4pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> -0.0633</span></td> </tr> <tr style="height:10.0pt"> <td width="43" valign="top" style="width:31.95pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 2.6250</span></td> <td width="38" valign="top" style="width:.4in;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 0.0</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 2.3333</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> -0.1062</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 5.6250</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 1.0</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> -0.3333</span></td> <td width="49" valign="top" style="width:36.4pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> -0.7991</span></td> </tr> <tr style="height:10.0pt"> <td width="43" valign="top" style="width:31.95pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 2.8125</span></td> <td width="38" valign="top" style="width:.4in;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 0.0</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 2.5000</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> -0.0888</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 5.8125</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 1.0</span></td> <td width="46" valign="top" style="width:34.6pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> -0.1667</span></td> <td width="49" valign="top" style="width:36.4pt;padding:0in 1.5pt 0in 1.5pt; height:10.0pt" class="exhibit_legend"> <p class="MsoNormal" align="center" style="text-align:center;text-indent:0in"> <span style="font-size: 8.0pt; font-family: Arial; layout-grid-mode: line"> 1.6871</span></td> </tr> </table> </div> </td> </tr> <tr> <td bgcolor="#CC9966" height="2"> <img border="0" src="../images/blank_2x2.gif" width="2" height="2"></td> </tr> <tr> <td> <p class="exhibit_legend">Example inputs to the fast Fourier transform software comprise 32 values for <i>h</i>(<i>t</i>), adjusted as described in the text. Outputs comprise 32 values for <i> H</i>(<i>f</i>). Corresponding values for <i>t</i> and <i>f</i> are also indicated, although these are generally not included in inputs or outputs for fast Fourier transform software.</td> </tr> </table> </center> </div> <table border="0" cellpadding="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="135" align="left" id="table14"> <tr> <td width="125" height="10"> <font size="2"> </font></td> <td width="10" height="10"></td> </tr> <tr> <td width="125"> <script type="text/javascript"></script> <script type="text/javascript" src="http://pagead2.googlesyndication.com/pagead/show_ads.js"> </script>  </td> <td width="10"> </td> </tr> </table> <p class="body">Your fast Fourier transform software is likely to accept as inputs only the values for <i>h</i>(<i>t</i>) and provide as outputs only the values proportional to <i>H</i>(<i>f</i>). This means you will need to infer the corresponding values for <i>f</i> from the values for <i>t</i>. The first value for <i> f</i> is 0. Subsequent values are spaced <img border="0" src="../formulas/fft_4.gif" align="absbottom" width="37" height="16"> apart. At the half-way point, the <i>f</i> values cycle back to the negative <i>f</i>-axis. In the above example, the 17<sup>th</sup> value for <i>f</i> equals –2.6667 instead of 2.6667. This cycling is related to periodicity.</p> <p class="body">The fast Fourier transform is a numerical technique, so results are not exact. Exhibit 5 compares results of Exhibit 4 with the actual Fourier transform <i>H</i>(<i>f</i>) of <i>h</i>(<i>t</i>). In this example, results are excellent. You can improve results by sampling at a greater number <i>n</i> of values for <i>t</i>.</p> <div align="center"> <center> <table border="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="350" cellpadding="0" id="table15"> <tr> <td> <p class="exhibit_header">Example: fast Fourier transform Results<br> <span class="exhibit_subheader">Exhibit 5</span></td> </tr> <tr> <td bgcolor="#CC9966" height="2"> <img border="0" src="../images/blank_2x2.gif" width="2" height="2"></td> </tr> <tr> <td> <img border="0" src="../images/ex5_fast_fourier_transform.gif" width="350" height="225"></td> </tr> <tr> <td> <p class="exhibit_legend">Example results obtained with fast Fourier transform software are compared with the actual Fourier transform of function [<a href="#[3]">3</a>]. In this case, the match is excellent.</td> </tr> </table> </center> </div> <p class="body">When sampling a function <i>h</i>(<i>t</i>), the number <i> n</i> of values you sample as well as their spacing <font face="Times New Roman">Δ</font> should be chosen based upon the complexity of the graph of <i>h</i>. In the example, <i>h</i> had a simple graph, so sampling <i>n</i> = 32 points was sufficient. In probabilistic applications, you may deal with functions that oscillate wildly. Such functions need to be sampled at sufficiently many values to capture that oscillation. Otherwise, the fast Fourier transform will produce erroneous results. It is not uncommon to sample at 512 or more values.</p> <table border="0" cellpadding="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="100%" id="table16"> <tr> <td height="30" valign="bottom" colspan="2"> <p class="header2_black">Related Internal Links</td> </tr> <tr> <td colspan="2" bgcolor="#CC9966" height="2"> <img border="0" src="../images/blank_2x2.gif" width="2" height="2"></td> </tr> <tr> <td bgcolor="#FFFFCC" colspan="2"> <table border="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="100%" cellpadding="6" id="table17"> <tr> <td width="100%"> <p align="left" class="explanatory_text"> <img border="0" src="../images/bullet_link_glossary.gif" width="26" height="15"><strong style="font-weight: 400"><a href="../articles/imaginary_numbers.htm">complex number</a> </strong>A number of the form <i>a</i> + <i>bi</i>, where <i>a</i> and <i>b</i> are real, and <i>i</i> is the imaginary square root of –1.</p> <p align="left" class="explanatory_text"> <img border="0" src="../images/bullet_link_glossary.gif" width="26" height="15"><strong style="font-weight: 400"><a href="../articles/quadratic_transformation.htm">quadratic transformation</a> For a VaR measure, a transformation procedure that is applicable to quadratic portfolios.</strong></p> </td> </tr> </table> </td> </tr> <tr> <td height="30" valign="bottom" colspan="2"> <p class="header2_black">Sponsored Links</td> </tr> <tr> <td colspan="2" bgcolor="#CC9966" height="2"> <img border="0" src="../images/blank_2x2.gif" width="2" height="2"></td> </tr> <tr> <td bgcolor="#FFFFCC" width="75"> <img border="0" src="../images/ad_side_banner_1.jpg" width="103" height="285"></td> <td bgcolor="#FFFFCC" width="99%">  <p class="ad_legend" style="margin-left: 0; margin-bottom:2"> <a target="_top" href="http://www.riskexpertise.com/link/advertising.htm"> <font color="#000000">Ads by Contingency Analysis</font></a></p> <p style="margin-top: 0; margin-bottom: 0"> <iframe src="http://servedbyadbutler.com/adserve/;ID=147917;size=336x265;setID=82436;type=iframe" style="margin: 0px; padding: 0px; border-width: 0px" width="336" height="265" frameborder="0" marginwidth="0" marginheight="0" scrolling="no" name="I1"> <![if lt IE 4]> <script src="http://servedbyadbutler.com/adserve/;ID=147917;size=336x265;setID=82436;type=js" type="text/javascript"> </script> <noscript> <a href="http://servedbyadbutler.com/go2/;ID=147917;size=336x265;setID=82436"> <img src="http://servedbyadbutler.com/adserve.ibs/;ID=147917;size=336x265;setID=82436;type=img" border="0" height="265" width="336" alt=""></a> </noscript><![endif]></iframe>   </td> </tr> <tr> <td height="30" valign="bottom" colspan="2"> <p class="header2_black">Related Books</td> </tr> <tr> <td colspan="2" bgcolor="#CC9966" height="2"> <img border="0" src="../images/blank_2x2.gif" width="2" height="2"></td> </tr> <tr> <td bgcolor="#FFFFCC" colspan="2"> <table border="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="100%" cellpadding="6" id="table18"> <tr> <td width="100%"> <p class="explanatory_text">Apostol (<a target="_blank" href="http://www.riskbook.com/link/apostol_t_(1974).htm">1974</a>) is a masterful mathematics text that covers the theory of Fourier transforms. Brigham (<a target="_blank" href="http://www.riskbook.com/link/brigham_e_(1988).htm">1988</a>) is the essential practical introduction to the FFT.</p> <table border="0" cellpadding="4" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="100%" id="table19"> <tr> <td width="100" align="left" valign="top"> <map name="FPMap673"> <area target="_blank" href="http://www.riskbook.com/link/apostol_t_(1974).htm" shape="rect" coords="0, 0, 83, 124"> </map> <img border="0" src="../images/book_apostol_tom_(1974)_125.gif" usemap="#FPMap673" width="84" height="125"></td> <td align="left" valign="top"> <table border="0" cellpadding="1" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="100%" id="table20"> <tr> <td width="90%" colspan="3"> <p class="title"> <a target="_blank" href="http://www.riskbook.com/link/apostol_t_(1974).htm"> Mathematical Analysis</a></td> </tr> <tr> <td colspan="3"> <p class="author"><b>Tom Apostol</b></td> </tr> <tr> <td width="10%"><map name="FPMap674"> <area target="_blank" href="http://www.riskbook.com/main/ratings.htm" shape="rect" coords="0, 0, 89, 15"> </map> <img border="0" src="../images/star_6.gif" usemap="#FPMap674" width="90" height="16"></td> <td width="10%" class="author">quality</td> <td width="70%"> <p class="author"> </td> </tr> <tr> <td width="10%"><map name="FPMap675"> <area target="_blank" href="http://www.riskbook.com/main/ratings.htm" shape="rect" coords="0, 0, 89, 15"> </map> <img border="0" src="../images/tech_4.gif" usemap="#FPMap675" width="90" height="16"></td> <td width="10%" class="author">technical</td> <td width="70%">  </td> </tr> <tr> <td width="10%"> <p class="author">1974</td> <td width="10%"> </td> <td width="70%"> <p align="center"><map name="FPMap671"> <area target="_blank" coords="0, 0, 145, 19" shape="rect" href="http://www.riskbook.com/link/apostol_t_(1974).htm"> </map> <img border="0" src="../images/pointer_review.gif" usemap="#FPMap671" width="146" height="20"></td> </tr> </table> </td> </tr> </table> <table border="0" cellpadding="4" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="100%" id="table21"> <tr> <td width="100" align="left" valign="top"> <map name="FPMap672"> <area target="_blank" href="http://www.riskbook.com/link/brigham_e_(1988).htm" shape="rect" coords="0, 0, 83, 124"> </map> <img border="0" src="../images/book_brigham_e_(1988)_125.gif" usemap="#FPMap672" width="84" height="125"></td> <td align="left" valign="top"> <table border="0" cellpadding="1" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="100%" id="table22"> <tr> <td width="90%" colspan="3"> <p class="title"> <a target="_blank" href="http://www.riskbook.com/link/brigham_e_(1988).htm"> The Fast Fourier Transform and Its Applications</a></td> </tr> <tr> <td colspan="3"> <p class="author"><b>E. Oran Brigham</b></td> </tr> <tr> <td width="10%"><map name="FPMap669"> <area target="_blank" href="http://www.riskbook.com/main/ratings.htm" shape="rect" coords="0, 0, 89, 15"> </map> <img border="0" src="../images/star_6.gif" usemap="#FPMap674" width="90" height="16"></td> <td width="10%" class="author">quality</td> <td width="70%"> <p class="author"> </td> </tr> <tr> <td width="10%"><map name="FPMap670"> <area target="_top" href="http://www.riskbook.com/main/ratings.htm" shape="rect" coords="0, 0, 89, 15"> </map> <img border="0" src="../images/tech_4.gif" usemap="#FPMap675" width="90" height="16"></td> <td width="10%" class="author">technical</td> <td width="70%">  </td> </tr> <tr> <td width="10%"> <p class="author">1988</td> <td width="10%"> </td> <td width="70%"> <p align="center"><map name="FPMap366"> <area target="_blank" coords="0, 0, 145, 19" shape="rect" href="http://www.riskbook.com/link/brigham_e_(1988).htm"> </map> <img border="0" src="../images/pointer_review.gif" usemap="#FPMap366" width="146" height="20"></td> </tr> </table> </td> </tr> </table> </td> </tr> </table> </td> </tr> <tr> <td height="30" valign="bottom" colspan="2"> <p class="header2_black">Related Papers</td> </tr> <tr> <td colspan="2" bgcolor="#CC9966" height="2"> <img border="0" src="../images/blank_2x2.gif" width="2" height="2"></td> </tr> <tr> <td bgcolor="#FFFFCC" colspan="2"> <table border="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="100%" cellpadding="6" id="table23"> <tr> <td width="100%"> <p class="explanatory_text"> <img border="0" src="../images/bullet_paper_glossary.gif" width="21" height="15"><a name="Cooley">Cooley</a>, J. W. and J. W. Tukey (1965). An algorithm for the machine calculation of complex Fourier series, <i>Mathematics of Computation</i>, 19 (90), 297-301</td> </tr> </table> </td> </tr> <tr> <td height="30" valign="bottom" colspan="2"> <p class="header2_black">Sponsored Links</td> </tr> <tr> <td colspan="2" bgcolor="#CC9966" height="2"> <img border="0" src="../images/blank_2x2.gif" width="2" height="2"></td> </tr> <tr> <td bgcolor="#FFFFCC" width="75"> <img border="0" src="../images/ad_side_banner_3.jpg" width="103" height="285"></td> <td bgcolor="#FFFFCC" width="99%"> <script type="text/javascript"></script> <script type="text/javascript" src="http://pagead2.googlesyndication.com/pagead/show_ads.js"> </script>  </td> </tr> <tr> <td bgcolor="#FFFFCC" colspan="2"> <table border="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="100%" cellpadding="6" id="table24"> <tr> <td width="100%" bgcolor="#FFFFFF">  <p align="center"><map name="FPMap0_I1"> <area target="_top" href="http://www.riskglossary.com" shape="rect" coords="0, 0, 164, 102"> </map><img border="0" src="../images/logo.jpg" usemap="#FPMap0_I1" width="165" height="103"></p> <p align="center"><span class="verdana10"> <a href="http://www.riskglossary.com/main/disclaimer.htm">Disclaimer</a></span></p> <p align="center">website: <span class="verdana10"> <a target="_top" href="http://www.contingencyanalysis.com">http://www.contingencyanalysis.com</a></span><br> glossary direct link: <span class="verdana10"> <a target="_top" href="http://www.riskglossary.com">http://www.riskglossary.com</a></span><br> copyright © Contingency Analysis, 1996 - current</p> <p align="center"><map name="FPMap1_I1"> <area target="_top" href="http://www.contingencyanalysis.com" shape="rect" coords="0, 0, 240, 88"> </map><img border="0" src="../images/logo_glossary_white.gif" usemap="#FPMap1_I1" width="241" height="89"></p> </td> </tr> </table> </td> </tr> </table> </td> <td>  </td> </tr> </table> </center> </div> </body>