Often technologies are helping to make tasks easier. That is also nice :), but when technology is helping you to make impossible tasks possible, that is exciting thing. That happened with new audio support for Flash 10. Here I am talking about way to implement FFT (Fast Fourier Transform) with Flash.

Introduction

Last few years Flashers tried in different ways to squeeze out more from Flash Audio. Flash 9 introducet audio spectrum with SoundMixer.computeSpectrum(). This gave us a chance to make attractive audio visualizers with AS3. However, the biggest problem still left unsolved:

• real-time sound generation from Flash
• retrieving audio spectrum in real-time (computeSpectrum() provides only asynchronous pulling and reading current spectrum)
• real-time manipulation with audio signal in time and frequent domain
• recording audio signal from microphone

Flash 10

Flash 10 introduced the most important news related to sound in the last few Flash versions.

Audio Signal Dynamic Creation

Now, we are able to fill Sound object with audio samples that we created in our AS3. You know that that means you can creaty any kind of sound now :)

Reading audio samples from audio signal

This is another exciting feature that gives us a chance to read audio samples from some MP3 file in the real-time and than for example to mix it with another MP3 file and that is how we made a simple mixete ;)

Examples

Examples related to these new features are realy not difficult to find. Very interesting example is in very Flash 10 documentation. I do not have to much to say about that except that you should play with it ;)

FFT (Fast Fourier Transform)

Introduction

Time and spectral signal

Time signal is record of some sginal over time. In the case of digitallysampled singal, this is a sequence of sampled intensities over time in equidistant time intervals, T_delta.

Spectrum signal is mathematically similar :). Conceptually, it presents a set of all frequencies contained in the signal including intensities and phases. In spectrum signal we are also sampling in equidistant frequency intervals, F_delta. It is important to realize that in order to find out frequency in some signal, we will always make F_delta error. For some predictable signal we can make it smaller using interpolation.

FT (Fourier Transform)

FT (Fourier Transform) is mathematical tool that give us a way to calculate spectral signal from time signal and vice versa. That means, if you are able to access time signal (in Flash with extract() method= than you are able to calculate spectrum signal using FT. More precisely, you will use DFT (Discret Fourier Transform).

• signal pitching
• Sound filtering (Lowpass, Highpass, bandpass filters), noise reduction
• main frequency detection (i.e. guitar tunners :) )
• etc

For some of effect we need IFT (Inverse Fourier Transform) also. It provides us with transposing signal from spectral domain into time domain.

FFT & IFFT

FFT (Fast Fourier Transform) is optimised FT that is also adopted for computer processing. Optimisation is dramatic and without it many of real-time DSP algorithms wouldn't be possible.

To be shourt, I will just say that FFT use N samples of a signal from time domain, dissasebles it into N signals containing 1 sample (but beiing wide N samples; all other samples are equal to 0), calculates N frequency domains for N signals and thanassembles back all those frequency spectrums into one spectrum that coresponds to the original unassembled signal. This sound like a more work but it is not, since in onrmal DFT, calculation for each sample depends on all other samples, so in this way we broke up that complex dependency. This gives us complexity of O(n log n) for FFT, compared with O(n²) for DFT.

Here is the scenario of some FFT application:

• Signal (just a piece of signal like 1/20 of second) is retrieved indigitaly sampled time domain
• There is an initial processing in time domain (i.e. signal normalization)
• Signal is transposed to frequency domain with FFT
• We process signal in frequency domain (i.e. lowpass filtering)
• Signal is transposed back to time domain with IFFT
• We have final processing in time domain
• Signal is pushed to the output or next processing unit

One problem with signal processing in expressed way is in jittering. Where that jittering is coming from? It is a result of processing in frequency domain. If you used FFT just to obesrve signal in frequency domain, than you willnothave problems. However if you changed signal, then you destroyed signal phase at the borders of time-signal piece.This makes it unmatching with the previous and next time-signal pieces, which means that we will have jitters on "tailored" places.

There are solutions to avoid it but let's consider it later.

Example - Bandpassfilter

Introduction

This example is relatively simple. However, it consists of multiple components.

1. Sound Dispatcher - global infrastructure that makes audio distribution between different audio processing components
2. SourceMP3 - Component that extracts audio signal from mp3 file
3. SourceOscillation - Component that generates sinusoidal signal
4. Mixer - Component that mixes 2 audio signals
5. Output - Component that "plays" audio signal
6. FourierTransformation - Component tht executes Fourier Transform
7. Spectrum - Component that visuelize frequency spectru
8. KnobSlider - Vusual knob that gives us possibility to change oscillator frequency

COmponents that I will analyze are components 1, 6 and 7. The rest of components are here just to make example working, and they areneither finished nor topic of this post but probable some later one. Of course, you are free to explore and use them :)

Description

The following picture describes audio signal flow in our example:

Each componet is enough self-descriptive, except the one component that you couldn't even see; that component is the component that integrates all other components and forwards/dispatches requests and signal between them.

This component is contained in Мain.as file and for the present moment it is not implemented in the most elegant way and maybe too complicated. The reason for that is the fact that later will be developed AudioHeads system which will be set of Flash components for sound processing and there will be need for much more complex component for signal distribution.

Basic way of working

The basic way of working is presented with the following process: output audio component sends requests for audio samples to the sound distribution component:

	var num: int = parent.RequestData(this, this.inputBuffer, length, startPosition);

The later component tracks connections between all components and forwards request to the component that goes before in the sequence and return response to the audio output component:

	public function RequestData(requester:AudioComponent, target:ByteArray, 
	length:Number, startPosition:Number = -1, channel:int=0):Number{
		var sourceID:int = this.connectionsComponents[requester.id + channel*(LAST_COMPONENT+1)];
		var sourceComponent:AudioComponent = this.components[sourceID];
		return sourceComponent.RequestData(requester, target, length, startPosition);
	}

This method finds from connectionsComponents matrix the ID of the component that goes before, than references it from the array of components components, and forwards request that component and result of that request it returns to the component that initiated request (audio output component in this case).

The earlier component will request audio signal from the component that goes before it in the signal sequence :), and in that way all up to the sound source. From sound source sound will propagate back to audio output component.

FFT/IFFT component

Component name: FourierTransformation

Package: SoundProcessors

This is the most important and the most easier component at the same time.

The following functions are important:

RequestData()

This method is inerited from AudioProvider class. It is responsible for forwarding data to the component that follows in the audio chain; audio oputput in this case.

As already said, this method asks for audio samples from the audio component that goes before it in audio chain (audio mixer in this concrete case), and to do that it talks to parent component; sound dispatcher.

In the first loop, this method prepares data for FFT processing; fills real and imaginary samples. In the case of real sygnal, imaginary samples are 0. It also fills output samples for the following component in chain (in the case there is no processing in frequency domain).

After the loop, DirectFFT method is being called which calculates signal in frequency domain from signal in time domain. The whole chapter is needed to explain this method, so I will stay on introduction in the beginning of this post. For you is probable good enough to know that it is working :).

It is interesting that DirectFFT is returning frequency spectrum in the same arrays used for time spectrum; inputs_real and inputs_imag. For application of FFT method processOutput is more important. That method finds local maximums (i.e. main frequencies). In the case of complex signal it can produce a lot of pikes, so we need either to look for global maximum ir set level of minimal intesity. For some applications (like this example) call to this funcion is not needed. You also should consider storageoptimization, since we are firing Garbage Collector in this case.

If we need filtering in frequeny domain, than we do it and after that we call method responsible for IFFT.

	for( i= 0 ; i < num ; ++i )
	{
		// bandwidth filtering
		if(! ((i>=this.indexLow1 && i=this.indexLow2 && i<=this.indexHigh2)) ){
			this.inversed_real[i] = 0;
			this.inversed_imag[i] = 0;
		}else{
			this.inversed_real[i] = this.inputs_real[i];
			this.inversed_imag[i] = this.inputs_imag[i];
		}
	}

	this.InverseFFT(true, this.samplesNoLog2, this.samplesNo, this.inversed_real, this.inversed_imag);

Since frequency domain is symetric to Niquist frequency, that is the reason we have to clean Lower and Upper part of spectrum. Explanation for that is mathematicaly little bit too complex.

Finaly, with IFFT we transform frequency spectrum back to time domain and put it int vector that is response to the following audio component.

GetIndexForFrequency(frequency:Number, roundToHigher:Boolean)

This method calculates index in frequency spectrum that corresponds to provided frequency. I noted that samples in frequency domain are equidistant. In the case that frequency doesn't fit to the frequency of any sample, parameter roundToHigher insists on rounding up to the higher index.

SetFilter(frequencyLow:Number, frequencyHigh:Number)

This method sets filter. It calls function GetIndexForFrequency to find correct indexes, and indexes for symmetrical higher spectrum it calculates "manually".

GetSamples(spectrum:Vector., indexLow:int, indexHigh:int, samplesNo:int)

This method returns set of requested number of samples in specified frequency interval.It should be corrected to calculated cumulative average value of all samples that goes into one sample in result, and not just to take one that falls to that specific position. се узме онај који "пада" на датој позицији.

DirectFFT(dir:Boolean, m:int, n:int, re:Vector., im:Vector.)

InverseFFT(dir:Boolean, m:int, n:int, re:Vector., im:Vector.)

IFFT method relies on call to FFT method which is based on symmetry of FFT and IFFT calculation.

createTestInput(input_signals:Vector.)

This method used just for testing and it creates input test audio signal in time domain.ектру

DirectDFT()

This method implements classical FT which we can use to test our IFFT implementation or to notice enormous difference in processing time comparing to FFT method

Spectrum component

Spectrum component is used for visualization of frequency spectrum. Each frame it calls FFT component to retrieve samples in the interval it is interested in and than visualize them as small bars with height corresponding to intensity.

Possible improvements

Main problem of FFT way of filtering is in jittering. A way to avoid it is interpolation; to calculate additional frequency spectrums from the middle of intervals (N/2) and than to use that frequency spectrum for joints and normal frequency spectrums on the rest of interval.

Other improvement about better way of storing detected frequency pitches is already mentioned.

Next improvent is related to way of processing signal and needless of copying signal in each component (except in the case of mixer and delay component, etc). This helps us to optimize our system in memory and time resources.