Yes, the output is �almost� correct. I was hoping that it was due to
�HalfResult� being wrong, but, as you note, it�s False (which is what
it should be). I can only conclude that the code is wrong. Somehow,
some way, it is skipping the addition of the 6 and 7 output points
that would be needed to make the results correct. That would indicate
an indexing problem (e.g.: some variable going from 0 to 5, but
missing the 6 and 7 points.
Those kind of problems can be difficult to spot and correct. You can
try printing out all index values to see the sequence of butterflies
performed by the code, and then try to fix the one(s) being skipped.
I don�t have a compiler that will run your code, so I�m afraid you�re
on your own when trying to debug it. An alternative would be to
download the same code from wherever you got it, and see if you
clipped or inadvertently modified any of it from what you have now.
Another possibility is to find some different code. I think it�s
essential that you always have some code that you can trust. That
way, when you compare its results to the output of a different
program, you know what you should be getting.
Kevin
Reply by Il Totem●April 16, 20092009-04-16
>>HalfResult determines wheter to take n/2 samples
>>from the result (if true)or the whole output (if false).
>
>>Since the intermediate results seems not to
>>be correct (quite disturbing)
>
>Your intermediate result is definitely not correct if you want all N
>outputs. But it would seem to be correct for the =91half results=92 case
>for outputs 0 to N/2. Perhaps the value of HalfResult isn't what you
>think it is within the function? Find out by printing it out while
>within the function.
>
>Your routine is definitely based on a negative exponent, so your
>result should be:
>Im: 0,-40i,0,0,0,0,0,40i
>Re: all zeros
>
>It looks like you're getting only half the results with some leftover
>intermediate data in the upper part. And note that if you added
>(-14.14+34.13i) to (14.14+5.87i), you'd get 40i. It's almost as if
>you=92re missing the upper part of the last column of butterflies.
>
>Given that your forward results are not correct for all N outputs,
>it's not surprising that an inverse won't work. You need to get the
>outputs shown above before doing the inverse.
>
>Kevin
>
You are right, but:
1. HalfResult is always false and I am sure of that because when the
function is called I do not pass it a variabile but a constant (false);
2. I am not the author of that fft code, and thus I cannot correct it.
That was the best implementation I could find, since it was the only one to
give exact results, until... now. Well, the output is almost all correct,
but in programming "almost" is a strange thing, because I am used to see
something completely wrong or something completely right. I would be glad
to see that someone has found a bug in that code...
Reply by ●April 15, 20092009-04-15
>HalfResult determines wheter to take n/2 samples
>from the result (if true)or the whole output (if false).
>Since the intermediate results seems not to
>be correct (quite disturbing)
Your intermediate result is definitely not correct if you want all N
outputs. But it would seem to be correct for the �half results� case
for outputs 0 to N/2. Perhaps the value of HalfResult isn't what you
think it is within the function? Find out by printing it out while
within the function.
Your routine is definitely based on a negative exponent, so your
result should be:
Im: 0,-40i,0,0,0,0,0,40i
Re: all zeros
It looks like you're getting only half the results with some leftover
intermediate data in the upper part. And note that if you added
(-14.14+34.13i) to (14.14+5.87i), you'd get 40i. It's almost as if
you�re missing the upper part of the last column of butterflies.
Given that your forward results are not correct for all N outputs,
it's not surprising that an inverse won't work. You need to get the
outputs shown above before doing the inverse.
Kevin
Reply by Il Totem●April 15, 20092009-04-15
>
>something must be wrong with your FFT, what do you get for your very
>first FFT? Should be 0,-40i,0,0,0,0,0,40i
>
The results of the first FFT are:
0, -40i, 0, 0, 0, 0, -14.14+34.13i, 14.14+5.87i
The FFT code is:
Public Shared Function ComplexFFTComplexOutput(ByRef TimeDomain() As
ComplexSample, Optional ByVal HalfResult As Boolean = True) As
ComplexSample()
n = TimeDomain.Length
nu = CInt((Math.Log(n) / Math.Log(2)))
Dim n2 As Integer = n / 2
Dim nu1 As Integer = nu - 1
Dim xre(n - 1) As Double
Dim xim(n - 1) As Double
Dim tr, ti, p, arg, c, s As Double
For i As Integer = 0 To n - 1
xre(i) = TimeDomain(i).RealPart
xim(i) = TimeDomain(i).ImaginaryPart
Next
Dim k As Integer = 0
For l As Integer = 1 To nu
While (k < n)
For i As Integer = 1 To n2
p = BitReverse(k >> nu1)
arg = 2 * CDbl(Math.PI) * p / n
c = CDbl(Math.Cos(arg))
s = CDbl(Math.Sin(arg))
tr = xre(k + n2) * c + xim(k + n2) * s
ti = xim(k + n2) * c - xre(k + n2) * s
xre(k + n2) = xre(k) - tr
xim(k + n2) = xim(k) - ti
xre(k) += tr
xim(k) += ti
k += 1
Next
k += n2
End While
k = 0
nu1 -= 1
n2 = n2 / 2
Next
k = 0
Dim r As Integer
While (k < n)
r = BitReverse(k)
If r > k Then
tr = xre(k)
ti = xim(k)
xre(k) = xre(r)
xim(k) = xim(r)
xre(r) = tr
xim(r) = ti
End If
k += 1
End While
Dim Result() As ComplexSample
If HalfResult Then
ReDim Result(n / 2 - 1)
For i As Int64 = 0 To n / 2 - 1
Result(i).RealPart = xre(i)
Result(i).ImaginaryPart = xim(i)
Next
Else
ReDim Result(n - 1)
For i As Int64 = 0 To n - 1
Result(i).RealPart = xre(i)
Result(i).ImaginaryPart = xim(i)
Next
End If
xre = Nothing
xim = Nothing
Return Result
End Function
HalfResult determines wheter to take n/2 samples from the result (if true)
or the whole output (if false). Since the intermediate results seems not to
be correct (quite disturbing), could anyone look at that code and tell me
if there's something wrong, put that HalfResult is always false?
Reply by ●April 15, 20092009-04-15
I just did the following:
Set real inputs r[0 to 7] to: 0., 7.07, 10., 7.07, 0., -7.07, -10.,
-7.07, and imaginary inputs i[0 to 7] to zero. Then I did an 8 point
forward FFT. Then I divided all outputs by N (= 8 in this case).
Then I inversed by exchanging the r[ ] and i[ ] in the forward call:
fft( N , r, i ) // forward fft
Divide results by N ( = 8 in this case)
fft( N, i, r ) //inverse fft via a forward fft
The output result in the array r[ ] is the same as what I started
with:
0., 7.07, 10., 7.07, 0., -7.07, -10., -7.07
Note that there's no real swapping of anything going on. It's all
done due the way you give the array names to the function that
matters. After the inverse, the r[ ] array is your real output and
the i[ ] array is your imaginary output.
This technique has been around for at least 20+ years (perhaps much
longer), and it works. If it doesn�t work for you, then check your
code. And, as noted in steve�s previous post, perhaps your fft is not
working correctly. Note that to do the above, you have to have an fft
routine that accepts and works with both real and imaginary inputs/
outputs. Some routines for real inputs won�t do that.
Kevin
Reply by bung...@yahoo.com●April 14, 20092009-04-14
On Apr 14, 1:16�pm, "Il Totem" <nicolo1...@yahoo.it> wrote:
> >Works find in matlab...
>
> >for an input of 1 2 3 4 5 6 7 8
>
> >the conj method
>
> >>> fft(conj (fft ([1 2 3 4 5 6 7 8])))/8
>
> >ans =3D
>
> > � � 1 � � 2 � � 3 � � 4 � � 5 � � 6 � � 7 � � 8
>
> >and the swap real and imag method
>
> > >> fft ([1 2 3 4 5 6 7 8])
>
> >ans =3D
>
> > �Columns 1 through 5
>
> > �36.0000 � � � � � �-4.0000 + 9.6569i �-4.0000 + 4.0000i �-4.0000 +
> >1.6569i �-4.0000
>
> > �Columns 6 through 8
>
> > �-4.0000 - 1.6569i �-4.0000 - 4.0000i �-4.0000 - 9.6569i
>
> >>> imag(fft(imag(ans) + j*real(ans))/8)
>
> >ans =3D
>
> > � � 1 � � 2 � � 3 � � 4 � � 5 � � 6 � � 7 � � 8
>
> I am sure that with matlabs it works well, but this does not help me. I
> will show you and exmplae of what I receive as output. Suppose that the
> time domain is composed by real-only sample, with these values:
> �0, 7.07, 10, 7.07, 0, -7.07, -10, -7.07
> I take the fft of those, I swap the real and imaginary part of freq
> domain's samples, then I compute a direct fft of the latter and therefore
> take the imaginary part of the output. It gives me the following values:
> �0, 9.57, 7.5, -3.96, -3.54, -1.04, -7.5, -1.04- Hide quoted text -
>
> - Show quoted text -
something must be wrong with your FFT, what do you get for your very
first FFT? Should be 0,-40i,0,0,0,0,0,40i
I am sure that with matlabs it works well, but this does not help me. I
will show you and exmplae of what I receive as output. Suppose that the
time domain is composed by real-only sample, with these values:
0, 7.07, 10, 7.07, 0, -7.07, -10, -7.07
I take the fft of those, I swap the real and imaginary part of freq
domain's samples, then I compute a direct fft of the latter and therefore
take the imaginary part of the output. It gives me the following values:
0, 9.57, 7.5, -3.96, -3.54, -1.04, -7.5, -1.04
I am sure that with matlabs it works well, but this does not help me. I
will show you and exmplae of what I receive as output. Suppose that the
time domain is composed by real-only sample, with these values:
0, 7.07, 10, 7.07, 0, -7.07, -10, -7.07
I take the fft of those, I swap the real and imaginary part of freq
domain's samples, then I compute a direct fft of the latter and therefore
take the imaginary part of the output. It gives me the following values:
0, 9.57, 7.5, -3.96, -3.54, -1.04, -7.5, -1.04
Reply by bung...@yahoo.com●April 14, 20092009-04-14
On Apr 14, 5:03�am, "Il Totem" <nicolo1...@yahoo.it> wrote:
> >you can do it either way use, use a conjugate or swap the real and
> >imaginary, or �to save computations for a real input you can do
> >neither and get the correct result but backwards!
>
> Indeed, nothing seems to work. I have tried every method explained on the
> Internet, including reverting input to receive the original output, but the
> results are constantly wrong. In the resulting array there are some correct
> values, but they are less than an half and are located in apparently random
> places in the array.
Works find in matlab...
for an input of 1 2 3 4 5 6 7 8
the conj method
>> fft(conj (fft ([1 2 3 4 5 6 7 8])))/8
ans =
1 2 3 4 5 6 7 8
>>
and the swap real and imag method
>> fft ([1 2 3 4 5 6 7 8])
ans =
Columns 1 through 5
36.0000 -4.0000 + 9.6569i -4.0000 + 4.0000i -4.0000 +
1.6569i -4.0000
Columns 6 through 8
-4.0000 - 1.6569i -4.0000 - 4.0000i -4.0000 - 9.6569i
>> imag(fft(imag(ans) + j*real(ans))/8)
ans =
1 2 3 4 5 6 7 8
>>
Reply by Il Totem●April 14, 20092009-04-14
>
>you can do it either way use, use a conjugate or swap the real and
>imaginary, or to save computations for a real input you can do
>neither and get the correct result but backwards!
>
Indeed, nothing seems to work. I have tried every method explained on the
Internet, including reverting input to receive the original output, but the
results are constantly wrong. In the resulting array there are some correct
values, but they are less than an half and are located in apparently random
places in the array.