Android Question Problem with FFT.Transform2

[Rodrigo Muñoz]

Hi,

I'm having trouble with the Transform2 and Inverse2 methods of the FFT library.

Transform and Inverse work as expected, so that transforming and then inverting produces no change:

'AUDIO_REAL is an array of size 2^N, with audio data.
'AUDIO_IMAG is an array of size 2^N, with zeros.
FFT.Transform(AUDIO_REAL, AUDIO_IMAG)
FFT.Inverse(AUDIO_REAL, AUDIO_IMAG)
'Returned AUDIO_REAL is identical to the one that went in.

However, this does not happen with Transform2 and Inverse2:

'AUDIO is an array of size 2^N, with audio data.
'FFT_REAL and FFT_IMAG are arrays of size 2^(N-1)
FFT.Transform2(AUDIO, FFT_REAL, FFT_IMAG)
FFT.Inverse2(FFT_REAL, FFT_IMAG, AUDIO)
'AUDIO is different than the one that went in.

As expected, the arrays returned by Transform are redundant (the upper half contains mirrored conjugates of the lower half, except for the first element of each half, which are always real). The arrays returned by Transform2 are not redundant (they contain the elements of the lower half only). However, Transform2 does not include the first element of the upper half, which is a not a conjugate of any element in the lower half. This number is always real, and I'm guessing that it contains important information to reconstitute the original data.

I would really like to use Transform2 and Inverse2, because they do the array copy for me. Are these methods native? Do you think that the results I'm getting are expected, and I may be missunderstanding something?

Thanks!

PS: Did my tests with an input array of 8 elements.

 

[klaus]

What is different ?
Can you post your test data.
I have never used only 8 elements.
If you test the demo program you get the original time data after calculating the inverse FFT.

 

[Rodrigo Muñoz]

Hi Klaus,

Thanks very much replying. Here is the full test code:

Dim I As Int

'With Transform and Inverse
Dim AUDIO_REAL(8) As Double
Dim AUDIO_IMAG(8) As Double
AUDIO_REAL(0) = 76
AUDIO_REAL(1) = 23
AUDIO_REAL(2) = 2
AUDIO_REAL(3) = 56
AUDIO_REAL(4) = 8
AUDIO_REAL(5) = 75
AUDIO_REAL(6) = 2
AUDIO_REAL(7) = 44
FFT.Transform(AUDIO_REAL, AUDIO_IMAG)
FFT.Inverse(AUDIO_REAL, AUDIO_IMAG)
Log("With Transform and Inverse")
For I = 0 To 7
  Log(AUDIO_REAL(I))  'Data is the same as it went in
Next


'With Transform2 and Inverse2
Dim AUDIO(8) As Double
Dim FFT_REAL(4) As Double
Dim FFT_IMAG(4) As Double
AUDIO(0) = 76
AUDIO(1) = 23
AUDIO(2) = 2
AUDIO(3) = 56
AUDIO(4) = 8
AUDIO(5) = 75
AUDIO(6) = 2
AUDIO(7) = 44
FFT.Transform2(AUDIO, FFT_REAL, FFT_IMAG)
FFT.Inverse2(FFT_REAL, FFT_IMAG, AUDIO)
Log("With Transform2 and Inverse2")
For I = 0 To 7
  Log(AUDIO(I))  'Data is different than it went in
Next

 

[Rodrigo Muñoz]

Another test with 1024 elements (also doesn't work):

'With Transform and Inverse
Dim AUDIO_REAL(1024) As Double
Dim AUDIO_IMAG(1024) As Double
For I = 0 To 1023 Step 8
    AUDIO_REAL(I + 0) = 76
    AUDIO_REAL(I + 1) = 23
    AUDIO_REAL(I + 2) = 2
    AUDIO_REAL(I + 3) = 56
    AUDIO_REAL(I + 4) = 8
    AUDIO_REAL(I + 5) = 75
    AUDIO_REAL(I + 6) = 2
    AUDIO_REAL(I + 7) = 44
Next
FFT.Transform(AUDIO_REAL, AUDIO_IMAG)
FFT.Inverse(AUDIO_REAL, AUDIO_IMAG)
Log("With Transform and Inverse")
For I = 0 To 1023
  Log(AUDIO_REAL(I))  'Data is the same as it went in
Next

'With Transform2 and Inverse2
Dim AUDIO(1024) As Double
Dim FFT_REAL(512) As Double
Dim FFT_IMAG(512) As Double
For I = 0 To 1023 Step 8
    AUDIO(I + 0) = 76
    AUDIO(I + 1) = 23
    AUDIO(I + 2) = 2
    AUDIO(I + 3) = 56
    AUDIO(I + 4) = 8
    AUDIO(I + 5) = 75
    AUDIO(I + 6) = 2
    AUDIO(I + 7) = 44
Next
FFT.Transform2(AUDIO, FFT_REAL, FFT_IMAG)
FFT.Inverse2(FFT_REAL, FFT_IMAG, AUDIO)
Log("With Transform2 and Inverse2")
For I = 0 To 1023
  Log(AUDIO(I))  'Data is different than it went in
Next

 

[klaus]

What exactly doesn't work ?
Could you post a small project as a zip file so I could have a look at it.

 

[Rodrigo Muñoz]

Hi Klaus, here is the zip file with the test project. Look at the log to see the output data. Input data is:

76
23
2
56
8
75
2
44

The problems is that the output data with Transform2 and Inverse2 is:

89.75
9.25
15.75
42.25
21.75
61.25
15.75
30.25

 

[klaus]

You are right, Transform2 and Inverse2 give wrong results.
The error becomes smaller the higher the sample number.
I had never noticed this because I never used sample numbers less than 256 and always with periodic signals.
For periodic signals and beginning and ending with 0 the result is right.
To get correct results you need to use Transform and Inverse.

 

[Rodrigo Muñoz]

Hi Klaus,

Thanks for checking this.

I think that the idea of Transform2 and Inverse2 is good. Perhaps in the future add one more element to the frequency-domain arrays, to incorporate the Nyquist frequency?

Thanks again,

Rod

 

[klaus]

The library was written by agraham.
I don't know if he is still looking at the forum.
I don't have the source code nor the java knowledge.

 

[Rodrigo Muñoz]

Thanks Klaus.

To sum up and close this thread, programmers should be aware that FFT.Transform2 will not return the N/2+1 'th element of the Fast Fourier Transform.

 

[klaus]

Hi Rodrigo,
I contacted agraham about the FFT library, he sent me his source code and I modified it to amend the errors.
Attached you find two new FFT library files (version 1.1) with Transform2 and Invert2 working correctly.
I am currently updating the demo program before updating the library in the 'official' thread.

UPDATE 2014.08.03:
The library files have been removed, they are updated in the first post of the original FFT library thread.

 

[Erel]

Well done Klaus!!!

 

[Rodrigo Muñoz]

Thanks so much!