Forums

FFT Return Values

Started by Raeldor August 7, 2010
Hi Guys,

I am using FFT for an audio programming project I'm working on, and
was wondering what are the bounds of the array values returned from
the FFT function (FFTW)?  The input is an array of 16-bit integers
representing amplitude between -16,384 and 16,383, with a sample rate
of 22k.  I am passing a sample length of 2048.  At the moment the
return values do seem to represent some kind of amplitude, but it's
hard to tell exactly what the upper and lower bounds are.  How would
it be possible to constrain the return values within the range 0.0 to
1.0 where 0.0 represents no sounds and 1.0 represents the maximum
possible amplitude.

Thanks
Ray
On 8/7/2010 9:07 PM, Raeldor wrote:
> Hi Guys, > > I am using FFT for an audio programming project I'm working on, and > was wondering what are the bounds of the array values returned from > the FFT function (FFTW)? The input is an array of 16-bit integers > representing amplitude between -16,384 and 16,383, with a sample rate > of 22k. I am passing a sample length of 2048. At the moment the > return values do seem to represent some kind of amplitude, but it's > hard to tell exactly what the upper and lower bounds are. How would > it be possible to constrain the return values within the range 0.0 to > 1.0 where 0.0 represents no sounds and 1.0 represents the maximum > possible amplitude.
The returned values are paired real and imaginary. The amplitude represented by a pair is sqrt(real^2 + imaginary^2), which could concievably be as large as 23,170. Dividing by a suitable number between that and 16384 will normalize to the range you want. You would be wise to try to understand the tools you use. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
On Aug 7, 8:15&#2013266080;pm, Jerry Avins <j...@ieee.org> wrote:
> On 8/7/2010 9:07 PM, Raeldor wrote: > > > Hi Guys, > > > I am using FFT for an audio programming project I'm working on, and > > was wondering what are the bounds of the array values returned from > > the FFT function (FFTW)? &#2013266080;The input is an array of 16-bit integers > > representing amplitude between -16,384 and 16,383, with a sample rate > > of 22k. &#2013266080;I am passing a sample length of 2048. &#2013266080;At the moment the > > return values do seem to represent some kind of amplitude, but it's > > hard to tell exactly what the upper and lower bounds are. &#2013266080;How would > > it be possible to constrain the return values within the range 0.0 to > > 1.0 where 0.0 represents no sounds and 1.0 represents the maximum > > possible amplitude. > > The returned values are paired real and imaginary. The amplitude > represented by a pair is sqrt(real^2 + imaginary^2), which could > concievably be as large as 23,170. Dividing by a suitable number between > that and 16384 will normalize to the range you want. > > You would be wise to try to understand the tools you use. > > Jerry > -- > Engineering is the art of making what you want from things you can get. > &#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;
Thanks Jerry. I would love to be able to understand it, but the math involved looks far more advanced than my current knowledge level. I will definitely try and find some more lamen's articles in the meantime, but just understanding the concept and the input/output means I can usefully use it in my project. I am curious though... why 23,170? Thanks Ray
Raeldor <raeldor@gmail.com> wrote:
 
> I am using FFT for an audio programming project I'm working on, and > was wondering what are the bounds of the array values returned from > the FFT function (FFTW)? The input is an array of 16-bit integers > representing amplitude between -16,384 and 16,383, with a sample rate > of 22k. I am passing a sample length of 2048.
Scaling of fixed point Discrete Fourier Transforms is a complicated question. There is a (1/N) factor that must be either in the forward transform, inverse transform, or some part of each. As written on the wikipedia Discrete_Fourier_transform page, the 1/N factor is in the inverse transform. In that case, the forward transform can easily overflow. The zero frequency (first) term of the transform is the sum of the input array, and so can be up to N times the input. (If, for example, the input is 2048 elements of all 16383.) Moving the (1/N) to the forward transform, by doing a divide by two in each stage of an FFT, removes that problem. Such overflow is less likely to occur in the inverse transform, especially if the transform is the result of a forward transform.
> At the moment the > return values do seem to represent some kind of amplitude, but it's > hard to tell exactly what the upper and lower bounds are. How would > it be possible to constrain the return values within the range 0.0 to > 1.0 where 0.0 represents no sounds and 1.0 represents the maximum > possible amplitude.
-- glen
% Newsgroups: comp.dsp
% From: Raeldor <rael...@gmail.com>
% Date: Sat, 7 Aug 2010 18:07:00 -0700 (PDT)
% Subject: FFT Return Values
% >
% > I am using FFT for an audio programming project I'm working on,
and
% > was wondering what are the bounds of the array values returned
from
% > the FFT function (FFTW)?  The input is an array of 16-bit integers
% > representing amplitude between -16,384 and 16,383, with a sample
rate
% > of 22k.  I am passing a sample length of 2048.  At the moment the
% > return values do seem to represent some kind of amplitude, but
it's
% > hard to tell exactly what the upper and lower bounds are.  How
would
% > it be possible to constrain the return values within the range 0.0
to
% > 1.0 where 0.0 represents no sounds and 1.0 represents the maximum
% > possible amplitude.

For each of 2 states of the random number generator, I ran
6 trials of length [128,256, ... 4096] using uniform
random distributions of N = 2048 integers in [-16384 16383]
to look for trends in the extreme values of the real part,
imaginary part, and magnitude of the FFT.
As the number of samples per trial increased, the only obvious
trend was the monotonicity of the extremes of the imaginary
part where, curiously, min(imagpart) = -max(imagpart).
Results are independent of the sampling rate Fs.

Obviously, if there is a magic equation for the extreme
values I didn't find it.

With X ~ fft(x), the results of the second run are

% minmaxrealX =
%
%   -1.373e+006  1.3194e+006
%  -1.3595e+006  1.4608e+006
%  -1.4064e+006  1.8275e+006
%  -1.5774e+006  1.5758e+006
%  -1.8404e+006  1.5892e+006
%  -1.7827e+006  1.6605e+006
%
% minmaximagX =                 % NOTE min = -max
%
%  -1.3289e+006  1.3289e+006
%  -1.4058e+006  1.4058e+006
%   -1.457e+006   1.457e+006
%  -1.4758e+006  1.4758e+006
%  -1.5632e+006  1.5632e+006
%  -1.7699e+006  1.7699e+006
%
% minmaxabsX =
%
%        972.61  1.4015e+006
%           883  1.4977e+006
%           128  1.8275e+006
%            12  1.6373e+006
%            52  1.8404e+006
%           143  1.8008e+006

MATLAB code:

comments are denoted by %
matrix transpose by '
matrix column stacking by :
fft operates along matrix columns
minmax operates along matrix rows

close all, clear all, clc
N = 2^11                       % 2048
M = 2^14                       % 16384
p = 0                          % plot index
%rand('state',0)               % first run
rand('state',4151941)          % second run

i = 0
for m = 7:12                   % minmax(2^m) = [ 128 4096 ]
    i=i+1

    %    2^m rows of N = 2048 random integers
    %    in the interval[-16834 16383]

    x = [-M*ones(2^m,1),-M+round((2*M-1)*rand(2^m,N-2)),...
         (M-1)*ones(2^m,1)];
    x1              = x(:,2:end-1); % check extremes of nonendpoints
    minmaxx1(i,1:2) = minmax(x1(:)'); % [-16384 16383 ]

    % 2^m columns of FFTs of length N = 2048

    X                  = fft(x');        % Note the transpose
    X1                 = X(:)';          % Note the transpose
    realX1             = real(X1);
    minmaxrealX(i,1:2) = minmax(realX1);
    imagX1             = imag(X1);
    minmaximagX(i,1:2) = minmax(imagX1);
    absX1              = abs(X1);
    minmaxabsX(i,1:2)  = minmax(absX1);
end

% Printing ...

minmaxrealX = minmaxrealX
minmaximagX = minmaximagX
minmaxabsX  = minmaxabsX

% Plotting ...

p=p+1,figure(p)
subplot(211),hold on
plot(minmaxrealX(:,1),'.-')
plot(minmaximagX(:,1),'.-r')
plot(minmaxabsX(:,1),'.-k')
legend('real','imag','abs')
title('FFT Minima')
subplot(212),hold on
plot(minmaxrealX(:,2),'.-')
plot(minmaximagX(:,2),'.-r')
plot(minmaxabsX(:,2),'.-k')
legend('real','imag','abs',2)
title('FFT Maxima')


Hope this helps.

Greg
On 8/9/2010 1:39 AM, Raeldor wrote:


> ... I am curious though... why 23,170?
To cover the unlikely possibility that both I and Q are each 16,383. 16383*sqrt(2) = 23196.06 Jerry -- Engineering is the art of making what you want from things you can get. &#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;