> i don't presume the OP means integral values but fixed-point representation.
A distinction without a difference; fixed-point vs. integers is just a
choice of scale factors.
> if there are enough bits in those integers (32+) and if there is some care
> taken to scaling [...] you can have some decent results.
The errors in a fixed-point FFT, which go as sqrt(N), are intrinsically
worse than the errors in a floating-point FFT, which go as sqrt(log N)
on average. Because of that, the OP is almost certainly better off
using a floating-point FFT and converting to integers at the end with
an appropriate scaling. Besides which floating-point FFTs are simpler
to implement than fixed-point, and are probably faster as well on a
modern general-purpose CPU. (We're not talking about DSP chips here,
or embedded systems without an FPU.)
Steven
Reply by robert bristow-johnson●February 1, 20062006-02-01
in article 1138815145.765657.122150@o13g2000cwo.googlegroups.com,
stevenj@alum.mit.edu at stevenj@alum.mit.edu wrote on 02/01/2006 12:32:
> Robert Hay wrote:
>> My problem actually is as follows: My program (in Java) gets two array of
>> integers from another program, uses FFT or Inverse FFT depending on what
>> the calling program requests, and returns two array of integers to the
>> caller. The next time the caller may want to get its original signal by
>> requesting from my program an Inverse FFT operation.
>
> This is an intrinsic problem -- integers cannot very accurately
> represent the results of a DFT
i don't presume the OP means integral values but fixed-point representation.
> and using an integer FFT will do nothing to solve it.
if there are enough bits in those integers (32+) and if there is some care
taken to scaling - either "block floating-point" or, if that is
computationally too messy, the "unitary" DFT scaling with 1/sqrt(N) so that
there is a divide-by-two (or ASR) ever *other* FFT pass - if you do that,
you can have some decent results.
those LakeDSP guys (the same who either stole Bill Gardner's idea for
zero-delay or low-delay fast convolution or came up with the idea
independently and nearly simultaneously, also a believable POV) had an old
convoluter built out of several Mot DSP56002, fixed-point DSPs, and i think
it sounded pretty good.
--
r b-j rbj@audioimagination.com
"Imagination is more important than knowledge."
Reply by Ron N.●February 1, 20062006-02-01
Robert Hay wrote:
> Should I conclude that Integer FFT/IFFT impossible is?
Certainly not. Both floating-point and integer FFT/IFFT
implementations produce rounding errors in the general
case. Depends on how much rounding error you can
tolerate.
IMHO. YMMV.
--
rhn A.T nicholson d.0.t C-o-M
Reply by ●February 1, 20062006-02-01
Robert Hay wrote:
> My problem actually is as follows: My program (in Java) gets two array of
> integers from another program, uses FFT or Inverse FFT depending on what
> the calling program requests, and returns two array of integers to the
> caller. The next time the caller may want to get its original signal by
> requesting from my program an Inverse FFT operation.
This is an intrinsic problem -- integers cannot very accurately
represent the results of a DFT -- and using an integer FFT will do
nothing to solve it.
The best you can do is to compute a floating-point FFT and then pick a
scaling for the results so that you lose as little precision as
possible when you truncate to integers. If you use an "integer FFT",
it will be computing exactly the same thing but losing even more bits
in the intermediate calculations.
You have to live with the fact that the inverse FFT is not going to
give your original signal back exactly. This is true even for a
floating-point FFT, but the errors if you truncate to
integer/fixed-point outputs are going to be bigger.
Regards,
Steven G. Johnson
Reply by Robert Hay●February 1, 20062006-02-01
>Robert Hay wrote:
>> >Since you're using Java, you can't possibly be concerned about speed,
so
>> >why not simply convert the integers to floats on input and then
>> >back to integers on output?
>> >--
>> >% Randy Yates % "How's life on earth?
>> >%% Fuquay-Varina, NC % ... What is it worth?"
>> >%%% 919-577-9882 % 'Mission (A World Record)',
>> >%%%% <yates@ieee.org> % *A New World Record*, ELO
>> >http://home.earthlink.net/~yatescr
>> >
>>
>>
>> I had already tried that. It doesn't work if I want to use the output
of
>> FFT as the input for the Inverse FFT. I don't get my original signal
>> back.
>
>1) Do not convert to integer on your float FFT routine.
>2) Convert between integer and float for your integer FFT routine.
>3) Integer FFT/IFFT's (generally) do not return the original signal
>without differences (due to rounding/quantization errors).
>
>--
>rhn
>
>
Should I conclude that Integer FFT/IFFT impossible is?
Reply by Ron N.●January 30, 20062006-01-30
Robert Hay wrote:
> >Since you're using Java, you can't possibly be concerned about speed, so
> >why not simply convert the integers to floats on input and then
> >back to integers on output?
> >--
> >% Randy Yates % "How's life on earth?
> >%% Fuquay-Varina, NC % ... What is it worth?"
> >%%% 919-577-9882 % 'Mission (A World Record)',
> >%%%% <yates@ieee.org> % *A New World Record*, ELO
> >http://home.earthlink.net/~yatescr
> >
>
>
> I had already tried that. It doesn't work if I want to use the output of
> FFT as the input for the Inverse FFT. I don't get my original signal
> back.
1) Do not convert to integer on your float FFT routine.
2) Convert between integer and float for your integer FFT routine.
3) Integer FFT/IFFT's (generally) do not return the original signal
without differences (due to rounding/quantization errors).
--
rhn
Reply by Jerry Avins●January 30, 20062006-01-30
Robert Hay wrote:
>>Since you're using Java, you can't possibly be concerned about speed, so
>>why not simply convert the integers to floats on input and then
>>back to integers on output?
>>--
>>% Randy Yates % "How's life on earth?
>>%% Fuquay-Varina, NC % ... What is it worth?"
>>%%% 919-577-9882 % 'Mission (A World Record)',
>>%%%% <yates@ieee.org> % *A New World Record*, ELO
>>http://home.earthlink.net/~yatescr
>>
>
>
>
> I had already tried that. It doesn't work if I want to use the output of
> FFT as the input for the Inverse FFT. I don't get my original signal
> back.
Do you know why not? Excessive truncation?
Jerry
--
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������
Reply by Robert Hay●January 30, 20062006-01-30
>
>I had already tried that. It doesn't work if I want to use the output of
>FFT as the input for the Inverse FFT. I don't get my original signal
>back.
>
>Thanks
>
My problem actually is as follows: My program (in Java) gets two array of
integers from another program, uses FFT or Inverse FFT depending on what
the calling program requests, and returns two array of integers to the
caller. The next time the caller may want to get its original signal by
requesting from my program an Inverse FFT operation.
My program uses a Java FFT to realize that. But the FFT routine accepts
floats (instead of integers) and it returns floats (instead of integers).
If my program converts the floats to integers and the next time the caller
requests an Inverse FFT then the original signal could not be recovered.
I know that Kiss supports Fixed-point FFT but the C code is very complex
for me. Therefore my question was: Has please somebody a Java FFT which
can handles integers? or Can please somebody tell me (in a few Java
statements) how a real FFT can be converted to integer FFT?
Thanks in advance
Reply by Robert Hay●January 30, 20062006-01-30
>Since you're using Java, you can't possibly be concerned about speed, so
>why not simply convert the integers to floats on input and then
>back to integers on output?
>--
>% Randy Yates % "How's life on earth?
>%% Fuquay-Varina, NC % ... What is it worth?"
>%%% 919-577-9882 % 'Mission (A World Record)',
>%%%% <yates@ieee.org> % *A New World Record*, ELO
>http://home.earthlink.net/~yatescr
>
I had already tried that. It doesn't work if I want to use the output of
FFT as the input for the Inverse FFT. I don't get my original signal
back.
Thanks
Reply by Randy Yates●January 26, 20062006-01-26
"Robert Hay" <rezahay@yahoo.com> writes:
> Hi,
>
> I have now a Java code implementing real FFT. I need actually Java code
> for implementing integer (fixed-point) FFT. I mean with this that the FFT
> accepts Java int type as input and produces Java int type as output. If
> there is no Java fixed-point FFT, how can I convert the existing Java real
> FFT to a fixed-point FFT? Would please somebody give a code example in
> Java.
>
> PS: I can now perform Inverse FFT using the current Java FFT and it does
> work very well (I get the original signal back). I assume that the
> fixed-point FFT will do the same.
Since you're using Java, you can't possibly be concerned about speed, so
why not simply convert the integers to floats on input and then
back to integers on output?
--
% Randy Yates % "How's life on earth?
%% Fuquay-Varina, NC % ... What is it worth?"
%%% 919-577-9882 % 'Mission (A World Record)',
%%%% <yates@ieee.org> % *A New World Record*, ELO
http://home.earthlink.net/~yatescr