📄 261-266.html
字号:
<HTML>
<HEAD>
<META name=vsisbn content="1558515682"><META name=vstitle content="Java Digital Signal Processing"><META name=vsauthor content="Douglas A. Lyon"><META name=vsimprint content="M&T Books"><META name=vspublisher content="IDG Books Worldwide, Inc."><META name=vspubdate content="11/01/97"><META name=vscategory content="Web and Software Development: Programming, Scripting, and Markup Languages: Java"><TITLE>Java Digital Signal Processing:Digital Audio Transform Recipes</TITLE>
<!-- HEADER --><STYLE type="text/css"> <!-- A:hover { color : Red; } --></STYLE><META NAME="ROBOTS" CONTENT="NOINDEX, NOFOLLOW">
<!--ISBN=1558515682//-->
<!--TITLE=Java Digital Signal Processing//-->
<!--AUTHOR=Douglas A. Lyon//-->
<!--PUBLISHER=IDG Books Worldwide, Inc.//-->
<!--IMPRINT=M & T Books//-->
<!--CHAPTER=6//-->
<!--PAGES=261-266//-->
<!--UNASSIGNED1//-->
<!--UNASSIGNED2//-->
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="255-261.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="266-273.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
<P><BR></P>
<P>Thus, line 2 replaces <I>N</I>, the number of items in the list plus 1, with the log of <I>N</I> to the base 2, rounded <I>down</I> (also known as the <I>floor function</I>) to the nearest integer.</P>
<!-- CODE SNIP //-->
<PRE>
N=log2(N);
</PRE>
<!-- END CODE SNIP //-->
<P>Finally, line 5 creates a number that is an integral power of two:
</P>
<!-- CODE SNIP //-->
<PRE>
N = 1<<N;
</PRE>
<!-- END CODE SNIP //-->
<BLOCKQUOTE>
<P><FONT SIZE="-1"><HR><B>NOTE: </B>DFT does not need to truncate the length of the data to be a power of two. We will see, however, that there are implementations of the FFT that require this truncation. To compare the performance of the DFT implementation fairly against the FFT implementation, we must perform the same truncation for both algorithms.<HR></FONT>
</BLOCKQUOTE>
<H3><A NAME="Heading4"></A><FONT COLOR="#000077">The futils.Timer Class: Benchmarking the DFT</FONT></H3>
<P>Benchmarking is a craft that measures hardware and software performance. One of the remarkable things about Java is that the compile-once-run-anywhere attribute enables the same byte codes to be executed on different implementations of the Java machine. In addition, we have similar Java virtual machines that are implemented on different hardware platforms. This arrangement enables a baseline comparison of different hardware platforms when executing the byte codes. Benchmarking can measure the effect of the implementation of an algorithm on execution time. Also of interest is the execution time of two different algorithms for the same data.
</P>
<BLOCKQUOTE>
<P><FONT SIZE="-1"><HR><B>NOTE: </B>There is a difference between the performance measurement of various algorithmic <I>implementations</I> and the performance measurement of various <I>algorithms</I>. Better algorithms are generally combined with better implementations to yield performance improvement<HR></FONT>
</BLOCKQUOTE>
<H4 ALIGN="LEFT"><A NAME="Heading5"></A><FONT COLOR="#000077">Class Summary</FONT></H4>
<!-- CODE //-->
<PRE>
package futils.bench;
import java.io.*;
public class Timer {
public Timer()
public void mark()
public void record()
public float elapsed()
public void report(PrintStream pstream)
public void report()
}
</PRE>
<!-- END CODE //-->
<H4 ALIGN="LEFT"><A NAME="Heading6"></A><FONT COLOR="#000077">Class Usage</FONT></H4>
<P>Suppose the following variables are predefined:
</P>
<!-- CODE SNIP //-->
<PRE>
Timer t1;
PrintStream pstream;
</PRE>
<!-- END CODE SNIP //-->
<P>To make an instance of a <I>Timer</I> class (with the elapsed time set to zero), use the following:</P>
<!-- CODE SNIP //-->
<PRE>
t1 = new Timer();
</PRE>
<!-- END CODE SNIP //-->
<P>To mark the time (similar to resetting a stopwatch):
</P>
<!-- CODE SNIP //-->
<PRE>
t1.mark();
</PRE>
<!-- END CODE SNIP //-->
<P>To add the elapsed time to the total elapsed time since the <I>record</I> method was last invoked:</P>
<!-- CODE SNIP //-->
<PRE>
t1.record();
</PRE>
<!-- END CODE SNIP //-->
<P>To return the elapsed time in seconds:
</P>
<!-- CODE SNIP //-->
<PRE>
t1.elapsed();
</PRE>
<!-- END CODE SNIP //-->
<P>To print the elapsed time, in seconds, to the <I>PrintStream</I> instance <I>pstream</I>:</P>
<!-- CODE SNIP //-->
<PRE>
t1.report(pstream);
</PRE>
<!-- END CODE SNIP //-->
<P>To print the elapsed time, in seconds, to <I>System.out</I>:</P>
<!-- CODE SNIP //-->
<PRE>
t1.report();
</PRE>
<!-- END CODE SNIP //-->
<H4 ALIGN="LEFT"><A NAME="Heading7"></A><FONT COLOR="#000077">Benchmarking the DFT Method</FONT></H4>
<P>In this section we show how to use the <I>Timer</I> class to measure the execution time of the DFT. This example shows how to use the DFT and how to benchmark a method. Benchmarking showed that executing the DFT on 2,048 points took 55 seconds on a 100-MHz PPC 601 without a JIT compilier. The following example of how to use the DFT in the <I>lyon.audio</I> package is contained in the <I>AudioFrame</I> class:</P>
<!-- CODE //-->
<PRE>
public void dft() {
FFT f = new FFT();
double [] doubleData = ulc.getDoubleArray();
double [] psd;
// Time the fft
Timer t1 = new Timer();
t1.mark();
psd=f.dft(doubleData);
// Stop the timer and report.
t1.record();
System.out.println(“Time to perform DFT:”);
t1.report();
f.graphs();
new DoubleGraph(psd,”psd”);
}
</PRE>
<!-- END CODE //-->
<H3><A NAME="Heading8"></A><FONT COLOR="#000077">The Inverse DFT</FONT></H3>
<P>Recall that the inverse Fourier transform of <I>V(f)</I> was given by</P>
<P ALIGN="CENTER"><IMG SRC="images/06-17d.jpg"></P>
<P>To solve this for the sampled waveform (given by Equation 6.1), we must perform an IDFT (Inverse Discrete Fourier Transform which is given by:
</P>
<P ALIGN="CENTER"><IMG SRC="images/06-18d.jpg"></P>
<P>(6.10)
</P>
<BLOCKQUOTE>
<P><FONT SIZE="-1"><HR><B>NOTE: </B>Recall Equation 6.4:</FONT>
</BLOCKQUOTE>
<P ALIGN="CENTER"><IMG SRC="images/06-19d.jpg"></P>
<BLOCKQUOTE>
<P><FONT SIZE="-1">The summation result is multiplied by 1/<I>N</I>. This is not the case in Equation 6.10. In some expositions, both Equations 6.10 and 6.4 are multiplied by</FONT>
</BLOCKQUOTE>
<P ALIGN="CENTER"><IMG SRC="images/06-20d.jpg"></P>
<BLOCKQUOTE>
<P><FONT SIZE="-1">to keep the DFT and IDFT symmetric. We abandoned such an approach during development, because it complicates the presentation of the PSD and requires slightly more computation.<HR></FONT>
</BLOCKQUOTE>
<P>Recall, from Chapter 5, Euler’s relation:
</P>
<P ALIGN="CENTER"><IMG SRC="images/06-21d.jpg"></P>
<P>Substituting Equation 6.4a into Equation 6.10 results in
</P>
<P ALIGN="CENTER"><IMG SRC="images/06-22d.jpg"></P>
<P>(6.11)
</P>
<P>Recall that when two complex numbers are multiplied together, <I>z</I><SUB>1</SUB><I>z</I><SUB>2</SUB>, the result can be expressed as</P>
<P ALIGN="CENTER"><IMG SRC="images/06-23d.jpg"></P>
<P>(6.11a)
</P>
<P>Based on Equation 6.11a, we conclude that the real part of <I>z</I><SUB>1</SUB><I>z</I><SUB>2</SUB> is given by</P>
<P ALIGN="CENTER"><IMG SRC="images/06-24d.jpg"></P>
<P>(6.11b)
</P>
<P>and the imaginary part of <I>z</I><SUB>1</SUB><I>z</I><SUB>2</SUB> is given by</P>
<P ALIGN="CENTER"><IMG SRC="images/06-25d.jpg"></P>
<P>(6.11c)
</P>
<P>We are interested in a reconstruction of a real signal, so we do not need to compute the result in Equation 6.11c. Substituting Equation 6.11b into Equation 6.11 yields</P>
<P ALIGN="CENTER"><IMG SRC="images/06-26d.jpg"></P>
<P>(6.12)
</P>
<P>Computing only the real part of the IDFT saves 2<I>N</I> multiplications and <I>N</I> additions for each frequency index, <I>k</I>. A comparison of Equation 6.12 with Equation 6.5,</P>
<P ALIGN="CENTER"><IMG SRC="images/06-27d.jpg"></P>
<P>The following code implements the IDFT shown in Equation 6.12:
</P>
<!-- CODE //-->
<PRE>
// assume that r_data and i_data are
// set. Also assume that the real
// value is to be returned
public double[] idft() {
int N = r_data.length;
double twoPiOnN = 2 * Math.PI / N;
double twoPikOnN;
double twoPijkOnN;
double v[] = new double[N];
System.out.println("Executing IDFT on "+N+" points...");
for(int k=0; k<N; k++) {
twoPikOnN = twoPiOnN *k;
for(int j = 0; j < N; j++) {
twoPijkOnN = twoPikOnN * j;
v[k] += r_data[j] * Math.cos(twoPijkOnN )
- i_data[j] * Math.sin(twoPijkOnN );
}
}
return(v);
}
</PRE>
<!-- END CODE //-->
<P><BR></P>
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="255-261.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="266-273.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
<hr width="90%" size="1" noshade><div align="center"><font face="Verdana,sans-serif" size="1">Copyright © <a href="/reference/idgbooks00001.html">IDG Books Worldwide, Inc.</a></font></div>
<!-- all of the reference materials (books) have the footer and subfoot reveresed --><!-- reference_subfoot = footer --><!-- reference_footer = subfoot --></BODY></HTML><!-- END FOOTER -->
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -