Fast Fourier Transform

The SoundWaveForm.java file provides the GUI, which includes saving and

loading a .wav file, and displaying the waveform (in time domain) and the

spectrum (in frequency domain, which will be obtained by DFT/FFT).

The ComplexNumber.java file is a class for complex numbers, which will

be needed for FFT and IFFT. It contains several basic operations, such

as constructor, setter and getter. You will have to fill in the operations

between complex numbers (e.g. addition, subtraction, etc) that are

necessary for DFT/IDFT/FFT/IFFT.

The WaveformLoader.java file contains the doSave() method for saving a

waveform (list of numbers) to a .wav file, and the doLoad() method for

loading a .wav file to a list of numbers.

Discrete/Fast Fourier Transform (DFT/FFT) can be used to analyse a

waveform (e.g. a series of numbers). Specifically, DFT/FFT transforms a

waveform from the time domain to the frequency domain, while Inverse

DFT/FFT (IDFT/IFFT) is from the frequency domain to the time domain.

Visualising the spectrum in the frequency domain can show different

aspects that are hidden in the time domain.

The template code already provides the methods for loading(store it as

a waveform (list of numbers) in the program) and save a waveform (list

of numbers) as a .wav file, and displaying a waveform in the time domain,

as well as displaying a spectrum in the frequency domain. You will need

to write the DFT, IDFT, FFT and IFFT methods (ideally creating a new

FourierTransform.java class file for them), as well as the supporting

methods, that is, the operations between complex numbers, in the

ComplexNumber.java file.

Apply DFT to the waveform in the time domain and transform it to the

frequency domain (NOTE: this can be very slow).

Apply FFT to the waveform in the time domain and transform it to the

frequency domain.

Apply IDFT to the series in the frequency domain and transform it back

to the time domain (NOTE: this can be very slow).

Apply IFFT to the series in the frequency domain and transform it back

to the time domain.

Formula:

For each file, you can load it using the "Load" button in the GUI, which

will also display the waveform (in the time domain) in the window. After

loading the file, you can test your FFT and IFFT methods. If everything

is correct, you should be able to display exactly the same waveform after

applying FFT and then IFFT. You can save the file with a different file

name. The file will be a truncated sound file of the original file, due

to the truncation to be the power of 2 in the FFT. You can play the saved

file to see if the sound is the same as the original file (easier to figure

out for the Forest.wav and Sea.wav files). Solving the problem in stages

Stage 1 – Complete the SoundWaveform.dft() and SoundWaveform.idft()

methods to implement the DFT and IDFT based on the formulas . You need

to implement the necessary operations between complex numbers in the

ComplexNumber.java file as supporting methods.Hint: You can test the DFT

and IDFT on the small .wav files. On large sound files they will be VERY

SLOW. ? Convert the Double list to complex number list to prepare for DFT/FFT. ? Successfully implement the (slow) Discrete Fourier transform, and can

display the obtained spectrum by clicking the GUI button. Work on the

small files. ? Successfully implement the (slow) Inverse Discrete Fourier transform.

Work on the small files. ? Convert the obtained complex number list to double list to restore

the waveform. Can display the restored waveform by clicking the GUI

button.

Stage 2 – Complete the SoundWaveform.fft() method to implement the FFT

based on the algorithm . Hint: You have to cut the tail of the waveform

to make its size equal to some power of two, so you can run FFT properly.

? Cut the tail of the waveform so its size equals to some power of 2.

Only tail is cut, that is, the original size of the waveform should

be smaller than the size after the cut times 2. ? Successfully implement the (recursive) FFT algorithm, and can display

the obtained spectrum by clicking the GUI button. ? For the small files, record the time taken by the slow DFT and FFT,

compare between them and discuss about the comparison.

Stage 3 – Complete the SoundWaveform.ifft() method to implement the IFFT.

It uses the divide-and-conquer algorithm which is very similar to the FFT.

You will need to figure out the difference between the two methods and

get the IFFT correct. Hint: You can compare the results of FFT (IFFT) and

DFT (IDFT) to see if they can obtain the same results. You can also compare

the computational time of FFT (IFFT) and DFT (IDFT) on the small .wav files

to understand the efficiency advantage of FFT (IFFT). Hint: The loading,

FFT and IFFT process can take time. To avoid breaking the program, you

should wait until the text screen shows “Loading/FFT/IFFT completed!”

? Successfully implement the IFFT algorithm, and can display the

restored waveform by clicking the GUI button. ? Record the time taken by the slow IDFT and IFFT, compare between them

and discuss about the comparison.

Hints:

The waveform loaded from a .wav file is an array list of Double. However,

the FFT method takes a list of ComplexNumber. Therefore, you need to

transform a Double to a ComplexNumber, which is easy to do.

Also, after IFFT, you will need to obtain the waveform as a list of Double.

This requires converting a list of ComplexNumber to a list of Double. A

simple way is to get its real part, since the imaginary part is supposed

to be (almost) zero.

The FFT algorithm works only when the size of the series equals some power

of 2. Therefore, cut the tail of the input list before doing FFT.

版权所有：编程辅导网 2020 All Rights Reserved 联系方式：QQ:99515681 电子信箱：99515681@qq.com

免责声明：本站部分内容从网络整理而来，只供参考！如有版权问题可联系本站删除。