More fun with the Fast Fourier Transform
The sounds that we hear can be recorded via a microphone and can be graphed as a signal of amplitude versus time. Low notes show as a lower frequency wave, and high notes show as higher frequency waves.
![clip_image002[15]](https://www.bing.com/url?source=images&rch=60xnihcQ5Qfa4eIaprB6HAOyjfUESbS&url=http%3A%2F%2Fcnx.org%2Fcontent%2Fm33242%2Flatest%2Fpitch_signal.jpg&urltarget=_blank&q=audio+signal&view=detail&&id=54FF3B16FBB8554835CC918D6C917E319623B131&first=0&FORM=IDFRIR&ssIG=5552371de5fa47af82cb85d7e68ac8f6 "clip_image002[15]")
Over the past few decades, some music players, like a car radio or stereo amplifier, have an “equalizer” display. This is essentially a histogram of the frequency spectrum. If there’s a low note, the left side of the display is higher. Treble notes show on the right side. Thus it’s easy to recognize disco music by the display even without hearing it: the left side beats very strongly in 4/4 time.
![clip_image004[15]](https://www.bing.com/url?source=images&rch=N5uSvi6E0F_npMTq8Ziviq-gXmkJ0x_&url=http%3A%2F%2Fwww.ecardmedia.eu%2Fdata%2Fmedia%2F24%2Fk5%2520equalizer.jpg&urltarget=_blank&q=Music+Equalizer&view=detail&&id=EDBACFCF22F248855B7EC6009458C8C4525EF1DA&first=0&qpvt=Music+Equalizer&FORM=IDFRIR&ssIG=526972dc02964961b52263416169e176 "clip_image004[15]")
Another way to think about a frequency display spectrum is like a piano keyboard. As a low piano key is played, the left of the display increases.
The Fast Fourier Transform is merely a few dozen lines of calculations to convert an array of values to another array of values.
These calculations include quite a bit of mathematics, such as multiplication, addition, logarithm, sine, cosine, pi, imaginary numbers.
An FFT converts a time domain wave audio signal into a frequency spectrum: The FFT input array is in the time domain and the output is in the Frequency Domain.
The Inverse FFT (which is almost the same as the FFT) converts the values in the opposite direction.
I downloaded an Audio Analyzer application for my Windows Phone that’s pretty cool: I can just run it while playing the piano to see the spectrum of all the wrong notes I hit 
The sample code below can load a Wav file of a sound, manipulate it, and play it back. The sample Wav file is a 2 second recording of me saying “Foxpro Rocks” with a 2Khz Sine wav in the background, making it very difficult to hear.
If you download the sample WAV file and run the program, hit the Play button, you’ll hear the Wav file as it was recorded. You can click on the other buttons to try their functions.
Reverse, just reverses the samples, and doesn’t require any kind of transformation.
Similarly, FreqUp and FreqDn shift the frequency an octave (a power of two) to make it higher or lower in frequency.
The Add Sine button will add a sine wave of the desired frequency.
The Notch Filter will do an FFT to convert to the frequency domain, zero out the data in the range of the Sine wave frequency, convert back to the time domain and play back the sound, effectively filtering out all sounds of the specified frequency.
A WAV file is an old file format for recording and playing back sound. It’s very simple to use and I used it for my first FFT articles
If you have an old Windows XP machine lying around, you can copy the old sound recorder program, which records and plays back WAV files. This is not necessary for the demo code to run.
Copy c:\windows\system32\SndRec32.exe to your Windows 7 or Windows 2008R2 machine.
Or you can use Windows XP Mode on Windows 7 which will make a Virtual Windows XP machine that runs hosted by your Windows 7 machine and copy the file from there.
Below is a sample program that lets you manipulate
Start Visual Studio.
File->New->Project->C#->Windows WPF Application
Paste in the XAML and the Code segments below into the Xaml Designer and the code behind (MainWindow.Xaml.cs) file.
Ensure the “WpfApplication1” strings below match the name you chose for your application.
Add a reference to System.Windows.Forms, hit F5 to run the program.
See also
How to filter out unwanted sounds via Fourier Transform
Here is a link to the sample FoxRocks.Wav file (It will open in whatever app is associated with the WAV file extension on your machine: Windows Media Player, for example. Just choose “File->Save As” to save it locally. Or you can right click on the link and choose File->Save Target as)
<Xaml>
<Window x:Class="WpfApplication1.MainWindow"
xmlns="https://schemas.microsoft.com/winfx/2006/xaml/presentation"
xmlns:x="https://schemas.microsoft.com/winfx/2006/xaml"
Title="MainWindow" Height="496" Width="929" Loaded="Window_Loaded">
<Grid>
<TextBox Height="23" HorizontalAlignment="Left" Margin="24,21,0,0" Name="txtInputFile" VerticalAlignment="Top" Width="352" />
<Button Content="_..." Height="23" HorizontalAlignment="Left" Margin="396,21,0,0" Name="btnBrowse" VerticalAlignment="Top" Width="21" Click="btnBrowse_Click" />
<Button Content="_Reload" Height="23" HorizontalAlignment="Left" Margin="434,20,0,0" Name="btnReload" VerticalAlignment="Top" Width="75" Click="btnReload_Click" />
<Button Content="_Play" Height="23" HorizontalAlignment="Left" Margin="301,360,0,0" Name="btnPlay" VerticalAlignment="Top" Width="75" Click="btnPlay_Click" />
<MediaElement Height="49" HorizontalAlignment="Left" Margin="584,-6,0,0" Name="mediaElement1" VerticalAlignment="Top" Width="73" />
<Button Content="_SaveAs" Height="23" HorizontalAlignment="Left" Margin="65,360,0,0" Name="btnSaveAs" VerticalAlignment="Top" Width="75" Click="btnSaveAs_Click" />
<Slider Height="35" HorizontalAlignment="Left" Margin="112,124,0,0" Name="sldFiltFreq" VerticalAlignment="Top" Width="174"
TickPlacement="BottomRight" Value="2048" Minimum="0" Maximum="22000" />
<TextBox Height="23" HorizontalAlignment="Left" Margin="173,155,0,0" Name="textBox1" VerticalAlignment="Top" Width="40" DataContext="{Binding ElementName=sldFiltFreq}"
Text="{Binding Path=Value, StringFormat=n0}" />
<Slider Height="31" HorizontalAlignment="Left" Margin="301,124,0,0" Name="sldFiltWidth" VerticalAlignment="Top" Width="174" Value="150" Maximum="10000" />
<Slider Height="35" HorizontalAlignment="Left" Margin="109,304,0,0" Name="sldAddSine" TickPlacement="BottomRight" VerticalAlignment="Top" Width="174" LargeChange="128" Maximum="22000" Value="440" Minimum="40" />
<TextBox DataContext="{Binding ElementName=sldAddSine}" Height="23" HorizontalAlignment="Left" Margin="327,309,0,0" Name="textBox3" Text="{Binding Path=Value, StringFormat=n0}" VerticalAlignment="Top" Width="120" />
<Button Content="_NotchFilter" Height="23" HorizontalAlignment="Left" Margin="12,124,0,0" Name="btnNotchFilter" VerticalAlignment="Top" Width="75" Click="btnNotchFilter_Click" />
<Button Content="Re_verse" Height="23" HorizontalAlignment="Left" Margin="16,224,0,0" Name="btnReverse" VerticalAlignment="Top" Width="75" Click="btnReverse_Click" />
<Button Content="FreqUp" Height="23" HorizontalAlignment="Left" Margin="16,266,0,0" Name="btnFreqUp" VerticalAlignment="Top" Width="77" Click="btnFreq_Click" />
<Button Content="FreqDn" Height="23" HorizontalAlignment="Left" Margin="109,266,0,0" Name="btnFreqDn" VerticalAlignment="Top" Width="75" Click="btnFreq_Click" />
<Button Content="_AddSine" Height="23" HorizontalAlignment="Left" Margin="16,308,0,0" Name="btnAddSine" VerticalAlignment="Top" Width="75" Click="btnAddSine_Click" />
<TextBox DataContext="{Binding ElementName=sldFiltWidth}" Height="23" HorizontalAlignment="Left" Margin="365,155,0,0" Name="textBox4" Text="{Binding Path=Value, StringFormat=n0}" VerticalAlignment="Top" Width="40" />
<TextBox Height="302" HorizontalAlignment="Left" Margin="464,49,0,0" Name="txtStatus" VerticalAlignment="Top" Width="443" AcceptsReturn="True" AcceptsTab="True" MaxLines="15" IsReadOnly="True" VerticalScrollBarVisibility="Auto" />
</Grid>
</Window>
</Xaml>
<Code>
using System;
using System.IO;
using System.Text;
using System.Windows;
using System.Windows.Controls;
namespace WpfApplication1
{
public partial class MainWindow : Window
{
public WavFile _oWav;
public MainWindow()
{
InitializeComponent();
}
private void Window_Loaded(object sender, RoutedEventArgs e)
{
try
{
txtInputFile.Text = System.IO.Path.Combine(
System.Environment.GetFolderPath(
Environment.SpecialFolder.MyDocuments),
"FoxRocks.wav");
_oWav = new WavFile();
btnReload_Click(this, null);
}
catch (Exception ex)
{
AddStatus(ex.ToString());
}
}
private void btnBrowse_Click(object sender, RoutedEventArgs e)
{
var dlg = new System.Windows.Forms.OpenFileDialog();
dlg.InitialDirectory = System.IO.Path.GetDirectoryName(txtInputFile.Text);
if (dlg.ShowDialog() == System.Windows.Forms.DialogResult.OK)
{
txtInputFile.Text = dlg.FileName;
btnReload_Click(sender, e);
btnPlay_Click(this, null);
}
}
public void AddStatus(string txtMsg)
{
txtStatus.Text += txtMsg + "\r\n";
txtStatus.ScrollToEnd();
}
private void btnReload_Click(object sender, RoutedEventArgs e)
{
try
{
_oWav.ReadWav(txtInputFile.Text);
AddStatus("Reading " + txtInputFile.Text);
AddStatus("Sample OrigLength = " + _oWav._nOriginalLen.ToString());
AddStatus("Sample length = " + _oWav._aSamples.Length.ToString());
AddStatus("Sample Freq = " + _oWav._nHz.ToString());
AddStatus("Sample Bits/Samp= " + _oWav._nBitsPerSample.ToString());
AddStatus("Sample Bytes/Sec= " + _oWav._nBytesPerSec.ToString());
}
catch (Exception ex)
{
AddStatus(ex.ToString());
}
}
private void btnPlay_Click(object sender, RoutedEventArgs e)
{
try
{
var tmpFile = System.IO.Path.ChangeExtension(System.IO.Path.GetTempFileName(), ".wav");
_oWav.WriteWav(tmpFile);
mediaElement1.Source = new Uri(tmpFile);
}
catch (Exception ex)
{
AddStatus(ex.ToString());
}
}
private void btnSaveAs_Click(object sender, RoutedEventArgs e)
{
var dlg = new System.Windows.Forms.SaveFileDialog()
{
Filter = "Wav | *.wav",
AddExtension = true,
DefaultExt = "wav"
};
if (dlg.ShowDialog() == System.Windows.Forms.DialogResult.OK)
{
_oWav.WriteWav(dlg.FileName);
}
}
private void btnNotchFilter_Click(object sender, RoutedEventArgs e)
{
AddStatus(((new System.Diagnostics.StackTrace()).GetFrames()[0].GetMethod().Name));
_oWav.NotchFilter(sldFiltFreq.Value, (int)sldFiltWidth.Value);
btnPlay_Click(sender, e);
}
private void btnReverse_Click(object sender, RoutedEventArgs e)
{
AddStatus(((new System.Diagnostics.StackTrace()).GetFrames()[0].GetMethod().Name));
_oWav.Reverse();
btnPlay_Click(sender, e);
}
private void btnAddSine_Click(object sender, RoutedEventArgs e)
{
AddStatus(((new System.Diagnostics.StackTrace()).GetFrames()[0].GetMethod().Name));
_oWav.AddSine(sldAddSine.Value, nVolume: 1000);
btnPlay_Click(sender, e);
}
private void btnFreq_Click(object sender, RoutedEventArgs e)
{
var btn = sender as Button;
double val = 0;
if ((string)(btn.Content) == "FreqDn")
{
val = .5;
}
else
{
val = 2;
}
_oWav.FreqShift(val);
btnPlay_Click(sender, e);
}
}
public class WavFile
{
public int _nOriginalLen;
public int _nHz;
public int _nBitsPerSample;
public int _nBytesPerSec;
public int _nChannels; // mono = 1, stereo = 2
public enum Domain
{
TimeDomain = 1,
FreqDomain = 2
};
Domain currentDomain = Domain.TimeDomain;
int _np2; // nearest power of 2
public double[] _aSamples;
public double[] _aImaginary;
public void FFT(bool fInverse)
{
var n = _aImaginary.Length;
var nlg2 = (int)(Math.Log(n) / Math.Log(2));
{
var j = n / 2;
if (fInverse)
{
for (int i = 0; i < n; i++)
{
_aImaginary[i] = -_aImaginary[i];
}
}
for (int i = 1; i < n - 2; i++) // Bit Reversal order
{
if (i < j)
{
swap(ref _aSamples[j], ref _aSamples[i]);
swap(ref _aImaginary[j], ref _aImaginary[i]);
}
var k = n / 2;
while (k <= j)
{
j -= k;
k /= 2;
}
j += k;
}
}
var le2 = 1;
for (int lp = 0; lp < nlg2; lp++)
{
var le = 2 * le2;
var ur = 1.0;
var ui = 0.0;
var sr = Math.Cos(Math.PI / le2);
var si = -Math.Sin(Math.PI / le2);
double tr;
double ti;
for (int j = 0; j < le2; j++) // each sub DFT
{
for (int i = j; i < n; i += le) // butterfly loop: cross multiply and accumulate
{
var ip = i + le2;
tr = _aSamples[ip] * ur - _aImaginary[ip] * ui;
ti = _aSamples[ip] * ui + _aImaginary[ip] * ur;
_aSamples[ip] = _aSamples[i] - tr;
_aImaginary[ip] = _aImaginary[i] - ti;
_aSamples[i] = _aSamples[i] + tr;
_aImaginary[i] = _aImaginary[i] + ti;
}
tr = ur;
ur = tr * sr - ui * si;
ui = tr * si + ui * sr;
}
le2 *= 2;
}
if (fInverse)
{
for (int i = 0; i < n; i++)
{
_aSamples[i] = _aSamples[i] / n;
_aImaginary[i] = -_aImaginary[i] / n;
}
currentDomain = Domain.TimeDomain;
}
else
{
currentDomain = Domain.FreqDomain;
}
}
public void EnsureDomain(Domain toDomin)
{
if (currentDomain != toDomin)
{
if (currentDomain == Domain.TimeDomain)
{
FFT(fInverse: false);
}
else
{
FFT(fInverse: true);
}
}
}
public void NotchFilter(double nFreqNotch, int nNotchWidth)
{
EnsureDomain(Domain.FreqDomain);
// the Sine wave freq is 2048 hz, so we want the filter to be centered on that
int nMid = (int)(nFreqNotch / _nHz * _np2);
var nRange = nNotchWidth;
for (int i = nMid - nRange; i < nMid + nRange; i++)
{ // we want to set all values in the range to 0
if (i >= 0 && i < _aSamples.Length)
{
_aSamples[i] = 0;
_aImaginary[i] = 0;
_aSamples[_np2 - i] = 0;
_aImaginary[_np2 - i] = 0;
}
}
//for (int i = 0; i < _aImaginary.Length; i++)
//{
// var powerdensity = _aSamples[i] * _aSamples[i] + _aImaginary[i] * _aImaginary[i];
// if (powerdensity < 100000000)
// {
// _aSamples[i] = 0;
// _aImaginary[i] = 0;
// }
//}
}
public void Reverse()
{
EnsureDomain(Domain.TimeDomain);
for (int i = 0; i < _aSamples.Length / 2; i++)
{
swap(ref _aSamples[i], ref _aSamples[_aSamples.Length - i - 1]);
}
}
public void AddSine(double nFreq, double nVolume)
{
for (int i = 0; i < _aSamples.Length; i++)
{ //superposition
var sum = nVolume * Math.Sin(i * 2 * Math.PI * nFreq / _nHz); // generate a SIN wave
var y = _aSamples[i];
_aSamples[i] += sum;
}
}
public void FreqShift(double nFreqShift)
{
//EnsureDomain(Domain.FreqDomain);
//var n = _aImaginary.Length;
//var nover4 = _aImaginary.Length / 4;
//for (int i = 0; i < nover4; i++)
//{
// _aSamples[i] = _aSamples[i + nover4];
// _aImaginary[i] = _aImaginary[i + nover4];
//}
//for (int i = nover4; i < n / 2; i++)
//{
// _aSamples[i] = 0;
// _aImaginary[i] = 0;
//}
//for (int i = 0, j = n - 1; i < n / 2; i++, j--)
//{
// _aSamples[j] = _aSamples[i];
// _aImaginary[j] = _aImaginary[i];
//}
//EnsureDomain(Domain.TimeDomain);
//for (int i = 0; i < _aImaginary.Length/2; i++)
//{
// _aSamples[i] = _aSamples[2 * i];
//}
if (nFreqShift >= 1)
{
_nHz *= 2;
}
else
{
_nHz /= 2;
}
}
public void ReadWav(string fileName)
{
currentDomain = Domain.TimeDomain;
using (var file = System.IO.File.Open(fileName, FileMode.Open, FileAccess.Read))
{
if (file.ReadStr(4) != "RIFF")
{
throw new InvalidDataException("not wav format");
}
var nFileLen = file.ReadInt() + 8;
if (file.ReadStr(8) != "WAVEfmt ")
{
throw new InvalidDataException("not wav format");
}
var nSubchunk = file.ReadInt();
var AudioFormat = file.ReadInt16(); // Audio format 1=Pulse Code Modulated(PCM)
if (AudioFormat != 1)
{
throw new InvalidDataException("Only PCM supported");
}
_nChannels = file.ReadInt16();// # of channels 1=mono
_nHz = file.ReadInt(); // Samples per second
_nBytesPerSec = file.ReadInt(); // Bytes/sec (Samples/sec * NumChan * BitsPerSample/8)
var nBlkAlign = file.ReadInt16(); // Block Align = NumChan * BitsPerSample/8
_nBitsPerSample = file.ReadInt16();// Bits/sample
var ExtraPadding = file.ReadStr(nSubchunk - 16);
while (file.Position < file.Length)
{
var cSection = file.ReadStr(4);
switch (cSection)
{
case "fact":
var nFactchunk = file.ReadInt();
var nRealSize = file.ReadInt(); //uncompressed # of samples
break;
case "data":
var nBytesData = file.ReadInt();
var nSamples = (int)(nBytesData / (_nBitsPerSample / 8));
_aSamples = new double[nSamples];
for (int i = 0; i < nSamples; i++)
{
switch (_nBitsPerSample)
{
case 8:
_aSamples[i] = file.ReadByte() - 128;
break;
case 16:
_aSamples[i] = file.ReadInt16();
break;
}
}
break;
default:
throw new InvalidDataException("unknown section");
}
}
}
_nOriginalLen = _aSamples.Length;
_np2 = (int)Math.Pow(2, Math.Round((Math.Log(_nOriginalLen) / Math.Log(2)), 0)); // round array len to nearest power of 2
if (_np2 < _nOriginalLen)
{
_np2 *= 2;
Array.Resize<double>(ref _aSamples, _np2);
for (int i = _nOriginalLen + 1; i < _np2; i++)
{
_aSamples[i] = 0;
}
}
_aImaginary = new double[_np2];
}
private void swap<T>(ref T a, ref T b)
{
T tmp;
tmp = a;
a = b;
b = tmp;
}
public void WriteWav(string fileName)
{
EnsureDomain(Domain.TimeDomain);
using (var file = System.IO.File.Create(fileName))
{
// CD quality is 44Khz 16 bits/sample
var nFileLen = 0; // total files size in bytes
var nTrail = 10;
var nSamples = _aSamples.Length;
file.Write("RIFF");
file.Write(0); // placeholder for file size to be written later
file.Write("WAVE");
file.Write("fmt ");
file.Write(16); // Subchunk1 size
file.Write((Int16)1); // Audio format 1 = Pulse Code Modulated (PCM)
file.Write((Int16)_nChannels);
file.Write(_nHz); // # samples per second
file.Write(_nHz * _nChannels * _nBitsPerSample / 8); // Bytes/sec (Samples/sec * NumChan * BitsPerSample/8)
file.Write((Int16)(_nChannels * _nBitsPerSample / 8)); // && Block Align = NumChan * BitsPerSample/8
file.Write((Int16)_nBitsPerSample);// && Bits/sample
file.Write("data"); //"data" subchunk
file.Write(_nChannels * (nSamples + nTrail) * nSamples / 8); //&& # of bytes in data
for (int x = 0; x < nSamples; x++)
{
var y = _aSamples[x];
switch (_nBitsPerSample)
{
case 8: //unsigned, 0 to 255
y = Math.Max(Math.Min(y, 127), -128);
file.Write((byte)(y + 128));
break;
case 16: //2's comp, -32768 to 32767
y = Math.Max(Math.Min(y, 32767), -32768);
file.Write((Int16)(y));
break;
}
}
for (int i = 0; i < nTrail; i++)
{
switch (_nBitsPerSample)
{
case 8: //unsigned, 0 to 255
file.Write((byte)128); //write 0s to bring signal down to 0
break;
case 16: //2's comp, -32768 to 32767
file.Write((Int16)0); //write 0s to bring signal down to 0
break;
}
}
nFileLen = (nSamples + nTrail) * _nBitsPerSample / 8 + 44;
file.Seek(4, SeekOrigin.Begin);
file.Write(nFileLen);
file.Seek(0, SeekOrigin.End);
}
}
}
public static class Extensions
{
public static int ReadInt(this FileStream file)
{
var arr = new byte[4];
file.Read(arr, 0, 4);
return BitConverter.ToInt32(arr, 0);
}
public static Int16 ReadInt16(this FileStream file)
{
return (Int16)(file.ReadByte() + (file.ReadByte() << 8));
}
public static string ReadStr(this FileStream file, int nlen)
{
var arr = new byte[nlen];
file.Read(arr, 0, nlen);
var str = Encoding.ASCII.GetString(arr);
return str;
}
public static void Write(this FileStream file, byte[] arr)
{
file.Write(arr, 0, arr.Length);
}
public static void Write(this FileStream file, string str)
{
file.Write(Encoding.ASCII.GetBytes(str));
}
public static void Write(this FileStream file, int num)
{
file.Write(BitConverter.GetBytes(num));
}
public static void Write(this FileStream file, Int16 num)
{
file.Write(BitConverter.GetBytes(num));
}
}
}
</Code>