Nsound::FFTransform Class Reference

A Class that performes the Fast Fouier Transfrom on a Buffer. More...

#include <Nsound/FFTransform.h>

Public Member Functions
	FFTransform (const float64 &sample_rate)
	~FFTransform ()
	Destructor. More...
Buffer	fft (const Buffer &time_domain) const
	Transforms the time_domain signal and calculates the FFT. More...
FFTChunkVector	fft (const Buffer &input, int32 n_order, int32 n_overlap=0) const
	Performs the FFT of size N on the input Buffer of overlaping frames. More...
Buffer	ifft (const FFTChunkVector &input) const
	Peforms an inverse FFT on each FFTChunk and concatenates the output. More...
Buffer	ifft (const Buffer &frequency_domain) const
	Peforms an inverse FFT on the input Buffer. More...
void	setWindow (WindowType type)
	A window is multiplied by the input prior to performing the transform, this help reduce artifacts near the edges. More...

Static Public Member Functions
static int32	roundUp2 (int32 raw)
	Returns nearest power of 2 >= raw. More...

Protected Attributes
uint32	sample_rate_
	Samples per second. More...

Private Member Functions
void	fft (Buffer &real, Buffer &img, int32 n_order) const
	Peforms an inplace, nth order Fast Fouier Transform on the Buffers. More...

Private Attributes
WindowType	type_

Detailed Description

A Class that performes the Fast Fouier Transfrom on a Buffer.

Implementing the fft algorithm on page 235 of the book: "Digital Signal Processing: A Practical Guide for Engineers and Scientists"

ISBN-13: 978-0-7506-7444-7

ISBN-10: 0-7506-7444-X

Definition at line 57 of file FFTransform.h.

Constructor & Destructor Documentation

FFTransform::FFTransform

(

const float64 &

sample_rate

)

Creates an FFTTransform instance. The sample rate here is only used to tell the FFTChunk objects how to plot the spectrum, otherwise it does play a role.

Example:

// C++
FFTransform t(44100.0);

// Python
t = FFTransform(44100.0)

Definition at line 41 of file FFTransform.cc.

    :
    sample_rate_(static_cast<uint32>(sample_rate)),
    type_(RECTANGULAR)
{
}

Nsound::FFTransform::~FFTransform ( )

inline

Destructor.

Definition at line 77 of file FFTransform.h.

{};

Member Function Documentation

Buffer FFTransform::fft

(

const Buffer &

time_domain

)

const

Transforms the time_domain signal and calculates the FFT.

The size of the FFT is determined to be a power of 2 greater than or equal to the length of time_domain. If time_domain is less than a power of 2, the Buffer is padded with zeros until it is exactly a power of 2.

Example:

// C++
FFTransform t(44100.0);
Buffer b("california.wav");
Buffer fdomain;
fdomain = t.fft(b);

// Python
t = FFTransform(44100.0)
b = Buffer("california.wav")
fdomain = t.fft(b)

Definition at line 50 of file FFTransform.cc.

References Nsound::Buffer::getLength(), Nsound::Buffer::getSpeedUp(), roundUp2(), and sample_rate_.

Referenced by Nsound::Spectrogram::computeMagnitude(), fft(), FFTransform_UnitTest(), Nsound::Filter::getFrequencyResponse(), Nsound::Filter::getPhaseResponse(), ifft(), main(), my_main(), Nsound::Stretcher::searchForBestMatch(), and Nsound::Spectrogram::Spectrogram().

{
    int32 N = roundUp2(time_domain.getLength());

    FFTChunkVector v = fft(time_domain, N);

    if(v.size() >= 1)
    {
        // Calculate the magnitude of the frequency domain.
        Buffer f_domain = v[0].getMagnitude();

        // Resample so to return exacly sample_rate / 2 samples.
        float64 sr_2 = sample_rate_ / 2.0;

        float64 factor = static_cast<float64>(f_domain.getLength()) / sr_2;

        // Simple down sample.
        return f_domain.getSpeedUp(factor);
    }

    return time_domain;
}

FFTChunkVector FFTransform::fft	(	const Buffer &	input,
		int32	n_order,
		int32	n_overlap = 0
	)		const

Performs the FFT of size N on the input Buffer of overlaping frames.

The size of the FFT is specifed by n_order. The input Buffer is broken up into frames of size n_order, the returned FFTChunkVector is the result for each frame. If n_overlap is > 0, the frames will overlap by that number of samples.

Example 1:

Let n_order = 16 and n_overlap = 0, this how the input is split into frames.

input = [xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx] // 42 samples

        |xxxxxxxxxxxxxxx|xxxxxxxxxxxxxxx|xxxxxxxxxx00000| // frames
            16 samples     16 samples     16 samples + pad

The returned FFTChunkVector will have 3 FFTChunk objects that represent the FFT for each of the frames above, note that the last frame will be padded out to compile a 16-point FFT.

Example 2:

Let n_order = 16 and n_overlap = 4, this how the input is split into frames.

input = [xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx] // 42 samples

        |xxxxxxxxxxxxxxx|
        16 samples   |xxxxxxxxxxxxxxx|
                     16 samples   |xxxxxxxxxxxxxxx|
                                  16 samples   |xxx000000000000|
                                               16 samples

The returned FFTChunkVector will have 4 FFTChunk objects that represent the FFT for each of the frames above, note that the these frames contain overlapping samples as specified. Also note that the last frame in this case has a large number of padded zeros.

Code Example:

// C++
FFTransform t(44100.0);
Buffer b("california.wav");
FFTChunkVector vec;
vec = t.fft(b, 16, 4);

// Python
t = FFTransform(44100.0)
b = Buffer("california.wav")
vec = t.fft(b, 16, 4)

Definition at line 75 of file FFTransform.cc.

References Nsound::Generator::drawWindow(), fft(), Nsound::Buffer::getLength(), roundUp2(), sample_rate_, Nsound::Generator::silence(), Nsound::Buffer::subbuffer(), and type_.

{
    const int32 N = roundUp2(n_order);

    const int32 input_length = input.getLength();

    FFTChunkVector vec;

    Generator gen(1);

    Buffer fft_window = gen.drawWindow(N, type_);

    for(int32 n = 0; n < input_length; n += (N - n_overlap))
    {
        // Create an FFTChunk to operate on.
        FFTChunk chunk(N, sample_rate_, input.getLength());

        // Grab N samples from the input buffer

        Buffer sub_signal = input.subbuffer(n,N);

        // Apply window
        int32 sub_length = sub_signal.getLength();
        if(sub_length == N)
        {
            sub_signal *= fft_window;
        }
        else
        {
            sub_signal *= gen.drawWindow(sub_length, type_);
        }

        (*chunk.real_) = sub_signal;

        int32 chunk_size = chunk.real_->getLength();

        // If there is less than N samples, pad with zeros
        for(int32 i = 0; i < N - chunk_size; ++i)
        {
            (*chunk.real_) << 0.0;
        }

        // Zero out the imaginary side.
        (*chunk.imag_) = gen.silence(N);

        fft(*chunk.real_, *chunk.imag_, N);

        vec.push_back(chunk);
    }

    return vec;
}

Buffer FFTransform::ifft

(

const FFTChunkVector &

input

)

const

Peforms an inverse FFT on each FFTChunk and concatenates the output.

This transforms the frequency domain signals held in the FFTChunkVector back to the time domain. If the FFTChunkVector was created with non-overlapping frames, the resulting output Buffer will be nearly identical to the original input (there will be some small round-off error).

Exmample:

// C++
FFTransform t(44100.0);
Buffer b("california.wav");
FFTChunkVector vec;
vec = t.fft(b, 16);
Buffer b2;
b2 = t.ifft(vec);

// Python
t = FFTransform(44100.0)
b = Buffer("california.wav")
vec = t.fft(b, 16)
b2 = t.ifft(vec)

Definition at line 207 of file FFTransform.cc.

References Nsound::Buffer::begin(), fft(), Nsound::FFTChunk::imag_, Nsound::FFTChunk::isPolar(), Nsound::FFTChunk::real_, roundUp2(), Nsound::Buffer::subbuffer(), and Nsound::FFTChunk::toCartesian().

Referenced by FFTransform_UnitTest(), ifft(), and main().

{
    Buffer output;

    FFTChunkVector::const_iterator itor = vec.begin();
    FFTChunkVector::const_iterator end = vec.end();

    const uint32 N = roundUp2(itor->real_->getLength() - 2);
    const float64 f_N = static_cast<float64>(N);

    while(itor != end)
    {
        FFTChunk chunk(*itor);

        if(chunk.isPolar()) chunk.toCartesian();

        // Change the sign of img.
        *chunk.imag_ *= -1.0;

        // Perform the forwared fft
        fft(*chunk.real_, *chunk.imag_, N);

        *chunk.real_ = chunk.real_->subbuffer(0, itor->getOriginalSize());

        // Divide the real by N.
        *chunk.real_ /= f_N;

        // Change the sign of img.  But the img is never used again so don't
        // bother.
//~        img *= -1.0;

        output << *chunk.real_;

        ++itor;
    }

    return output;
}

Buffer FFTransform::ifft

(

const Buffer &

frequency_domain

)

const

Peforms an inverse FFT on the input Buffer.

This transforms the frequency domain signal held in the input Buffer back to the time domain. The input signal will get padded so its length is exactly a power of 2.

Exmample:

// C++
FFTransform t(44100.0);
Buffer b("california.wav");
fdomain = t.fft(b);
Buffer tdomain;
tdomain = t.ifft(fdomain);

// Python
t = FFTransform(44100.0)
b = Buffer("california.wav")
fdomain = t.fft(b, 16)
tdomain = t.ifft(fdomain)

Definition at line 248 of file FFTransform.cc.

References Nsound::Buffer::getLength(), Nsound::Buffer::getReverse(), ifft(), roundUp2(), sample_rate_, and Nsound::Buffer::subbuffer().

{
    int32 N = roundUp2(frequency_domain.getLength());

    FFTChunk chunk(N, sample_rate_);

    *chunk.real_ << frequency_domain;

    for(uint32 i = 0; i < 2 * (N - frequency_domain.getLength()); ++i)
    {
        *chunk.real_ << 0.0;
    }

    *chunk.real_ << frequency_domain.getReverse();

    *chunk.imag_ = 0.0 * *chunk.real_;

    FFTChunkVector vec;

    vec.push_back(chunk);

    return ifft(vec).subbuffer(0, frequency_domain.getLength());
}

int32 FFTransform::roundUp2 ( int32  raw )

static

Returns nearest power of 2 >= raw.

Definition at line 274 of file FFTransform.cc.

Referenced by fft(), Nsound::Filter::getFrequencyAxis(), ifft(), and Nsound::Spectrogram::Spectrogram().

{
    raw = static_cast<int32>(::fabs(static_cast<float64>(raw - 1)));

    int32 n;

    n = 1;
    while(raw)
    {
        n   <<= 1;  // Multiply n by 2
        raw >>= 1;  // Divide raw by 2
    }

    return n;
}

void FFTransform::setWindow

(

WindowType

type

)

A window is multiplied by the input prior to performing the transform, this help reduce artifacts near the edges.

Definition at line 292 of file FFTransform.cc.

References type_.

{
    type_ = type;
}

void FFTransform::fft ( Buffer &  real, Buffer &  img, int32  n_order  ) const

private

Peforms an inplace, nth order Fast Fouier Transform on the Buffers.

Definition at line 130 of file FFTransform.cc.

References M_PI, and sr.

{
    const float64 pi = M_PI;
    const int32 n_minus_1 = N - 1;
    const int32 n_devide_2 = N / 2;
    const int32 m = static_cast<uint32>(
        std::log10(static_cast<float64>(N)) / std::log10(2.0) + 0.5);

    int32 j = n_devide_2;

    // Bit reversal sorting.
    for(int32 i = 1; i <= N - 2 ; ++i)
    {
        if(i < j)
        {
            float64 temp_real = real[j];
            float64 temp_img  = img[j];

            real[j] = real[i];
            img[j]  = img[i];

            real[i] = temp_real;
            img[i]  = temp_img;
        }

        int32 k = n_devide_2;

        while(k <= j)
        {
            j -= k;
            k /= 2;
        }
        j += k;
    }

    // Loop for each fft stage.
    for(int32 l = 1; l <= m; ++l)
    {
        int32 le = static_cast<int32>(std::pow(2.0, l) + 0.5);
        int32 le2 = le / 2;

        float64 ur = 1.0;
        float64 ui = 0.0;

        // Calculate sine and cosine values.
        float64 sr = std::cos(pi / static_cast<float64>(le2));
        float64 si = -1.0 * std::sin(pi / static_cast<float64>(le2));

        // Loop for each sub DFT.
        for(j = 1; j <= le2; ++j)
        {
            int32 j_minus_1 = j - 1;

            // Loop for each butterfly.
            for(int32 i = j_minus_1; i <= n_minus_1; i += le)
            {
                int32 ip = i + le2;

                // Butterfly calculation.
                float64 temp_real = ur * real[ip] - ui * img[ip];
                float64 temp_img  = ui * real[ip] + ur * img[ip];

                real[ip] = real[i] - temp_real;
                img[ip]  = img[i]  - temp_img;

                real[i] += temp_real;
                img[i]  += temp_img;
            }
            float64 temp = ur;
            ur = temp * sr - ui * si;
            ui = temp * si + ui * sr;
        }
    }
}

Member Data Documentation

uint32 Nsound::FFTransform::sample_rate_

protected

Samples per second.

Definition at line 220 of file FFTransform.h.

Referenced by fft(), and ifft().

WindowType Nsound::FFTransform::type_

private

Definition at line 228 of file FFTransform.h.

Referenced by fft(), and setWindow().

---

The documentation for this class was generated from the following files:

• Nsound/FFTransform.h
• Nsound/FFTransform.cc