Android Question Problem with FFT.Transform2

Rodrigo Muñoz

Member
Licensed User
Longtime User
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:

B4X:
'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:

B4X:
'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.
 
Last edited:

Rodrigo Muñoz

Member
Licensed User
Longtime User
Hi Klaus,

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

B4X:
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
 
Upvote 0

Rodrigo Muñoz

Member
Licensed User
Longtime User
Another test with 1024 elements (also doesn't work):

B4X:
'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
 
Upvote 0

Rodrigo Muñoz

Member
Licensed User
Longtime User
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
 

Attachments

  • TestFFT.zip
    384.1 KB · Views: 342
Upvote 0

klaus

Expert
Licensed User
Longtime User
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.
 
Last edited:
Upvote 0

Rodrigo Muñoz

Member
Licensed User
Longtime User
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
 
Upvote 0

Rodrigo Muñoz

Member
Licensed User
Longtime User
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.
 
Upvote 0

klaus

Expert
Licensed User
Longtime User
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.
 
Last edited:
Upvote 0
Top