Forum Rule: Always post complete source code & details to reproduce any issue!
Results 1 to 12 of 12

Thread: Getting real and imaginary FFT data from AudioAnalyzeFFT1024

  1. #1
    Junior Member
    Join Date
    Oct 2019
    Posts
    11

    Getting real and imaginary FFT data from AudioAnalyzeFFT1024

    Like the title says, can you get both real and imaginary FFT data from AudioAnalyzeFFT1024? I am trying to use this:
    https://github.com/adamstark/BTrack
    beat detection algorithm in my audio project but it requires real and imaginary FFT data. In the function void AudioAnalyzeFFT1024::update(void) I found this code:

    Code:
    // TODO: support averaging multiple copies
        for (int i=0; i < 512; i++) {
    	uint32_t tmp = *((uint32_t *)buffer + i); // real & imag
    	uint32_t magsq = multiply_16tx16t_add_16bx16b(tmp, tmp);
    	output[i] = sqrt_uint32_approx(magsq);
        }
    but I can't really find much other mention of the imaginary FFT data, and its a little confusing how I would get the real and imaginary data out of that. I am trying to match this format from the beat detection code:

    Code:
    // store real and imaginary parts of FFT
        for (int i = 0; i < frameSize; i++)
        {
            complexOut[i][0] = fftOut[i].r;
            complexOut[i][1] = fftOut[i].i;
        }

  2. #2
    Senior Member
    Join Date
    Jul 2020
    Posts
    969
    It doesn't currently return complex values. It wouldn't be hard to create a version that produced complex though.

    The code uses dual 16 bit operations on the two halves of the complex value for efficiency, which is why its a bit
    opaque.

    The code also forgets to return the Nyquist bin, for some reason.

  3. #3
    The arm_cfft_radix4_q15(&fft_inst, buffer) function output is located in the buffer[] in the form real, complex, real, complex......
    The for loop you show in your code snippet converts that to magnitude. So, if you are willing to comment out that for loop in the library function, the buffer[] array has the fftOut[i].r and fftOut[i].r you need.

  4. #4
    Senior Member
    Join Date
    Jul 2020
    Posts
    969
    The problem is that buffer is actively overwritten everytime there's enough new samples, so you can't
    guarantee to read a consistent set of frequency data without taking a snapshot like the code current does.

    The buffer has private scope too.

  5. #5
    Your right. So the modification to the library would have to be more extensive than I said. It make more sense to bypass the Audio library FFT and do the FFT separately.

  6. #6
    Junior Member
    Join Date
    Feb 2021
    Posts
    13
    hey guys,

    be patient with me...but i aswell don't get jack shit out of this FFT1024 algorithm. It's just written in such a blunt style and without any urge at any point to explain what it doest like somebody wanted you to not get the concept behind it on purpose lol.

    The fact that the transformation works with multiple files from the audio library and the ARM library aswell makes it even more confusing.

    I'm not a godlike programmer like you guys seem to be and i think that it would help a lot of users on this board if some of you would explain the modus operandi of the actual audio library codes a bit more specifically, instead of throwing in some terrible 3 line pseudo-theory answer that doesn't get anyone anywhere.

    Please only try to help if you really want to try to help.


    Back to the problem: I'm an electrical engineer, that's why i can't unite these FFT codes to the actual discrete fourier analysis i would assume to be occurring here ANYWHERE. Something like:

    Output = Input * e^-i2πkn/N

    So please for the love of god someone explain to me how those cheesy signed saturated r shifts do all the magic here again??? I'm just not getting jack shit like always... Why isn't there a single god damn euler / sine / cosine function in all those thousands of FFT1024.cpp / FFT1024.h / math.h files??? I even checked the ARM library and it's just thousands of lines of god damn definitions aswell. If the FFT works with shifts only then can someone maybe point out how that is possible? And what is the benefit? Are you saving up that much multiplications with avoiding the standard euler transform / multiplication?

    I'm stuck here, my brain is melting... all I'm doing for the last couple of weeks really is to analyze the audio library codes, especially the 1024FFT code... following the outcome that i just don't get jack shit at some point in between because i can't combine the actual lines code with "stuff that i would expect to happen in there" ... then i write the codes down on a piece of paper... still not getting most of it... it really hurts sometimes

    Little reminder again: please be patient with me and if you don't want to answer something productive then I'm fine if you just don't answer anything at all. Thank you.

    With kind regards, mala

  7. #7
    Senior Member
    Join Date
    Jul 2014
    Posts
    3,150
    @mala96,
    As far as I can see you did not ask any question in this thread
    but your post is full of insults, so I urge superusers to take note.

  8. #8
    Junior Member
    Join Date
    Feb 2021
    Posts
    13
    Quote Originally Posted by WMXZ View Post
    @mala96,
    As far as I can see you did not ask any question in this thread
    but your post is full of insults, so I urge superusers to take note.
    I did indeed ask a few questions in this thread. But i can summarize one main question for you if you want:

    For a DFT/FFT i was assuming a formula like

    " Σ 0,...,N-1 (output) = Σ 0,...,N-1 (input * e^-i2πkn/N ) "

    That is the formula i remember from theory.
    So my question is: Where inside in the FFT1024 code is the actual fourier transformation happening?

    I can't comprehend the part where the fourier transformation is being made and the only operation i can see there right now is a 15bit shift on val being forwarded to *buf. I'm sorry if i was being scabrous but i am very frustrated and have no idea on how to get it into my knowledge. I apologize dearly for being insensitive WMXZ.

    with kind regards, mala

  9. #9
    Senior Member
    Join Date
    Jul 2020
    Posts
    969
    In the arm_cfft_radix4_q16 call, part of the CMSIS library provided by ARM:
    Code:
    		arm_cfft_radix4_q15(&fft_inst, buffer);
    You can look up the docs for these arm routines by googling the function names. There's also a setup
    call to arm_cfft_radix4_init_q15 in analyze_fft1024.h.
    All the twiddle factors are precomputed.

    You clearly haven't encountered much programming-in-the-large - most code ends up being boiler-plate
    rather than business logic, especially in low level languages like C and C++

  10. #10
    Senior Member
    Join Date
    Jul 2014
    Posts
    3,150
    Quote Originally Posted by mala96 View Post
    I did indeed ask a few questions in this thread. But i can summarize one main question for you if you want:

    For a DFT/FFT i was assuming a formula like

    " Σ 0,...,N-1 (output) = Σ 0,...,N-1 (input * e^-i2πkn/N ) "

    That is the formula i remember from theory.
    So my question is: Where inside in the FFT1024 code is the actual fourier transformation happening?

    I can't comprehend the part where the fourier transformation is being made and the only operation i can see there right now is a 15bit shift on val being forwarded to *buf. I'm sorry if i was being scabrous but i am very frustrated and have no idea on how to get it into my knowledge. I apologize dearly for being insensitive WMXZ.

    with kind regards, mala
    Let's ignore that DFT formula is
    y_k = Σ 0,...,N-1 (x_n * e^-i2πkn/N )
    i.e. no left-hand side sum

    FFT is called Fast because it does not implement this formula, which has O(N^2) complex multiplies and add operations for all frequencies k, but implements an algorithm that needs O(N*logxN)) operations for a radix x FFT (logx is logarithm to base x, where x is typically is 2,4,8)

    a 1024 radix2 FFT needs about 10*1024 multiply-add operations and a radix8 FFT needs about 3*1024 operations

    To get a feeling how it is done, check out the classic https://en.wikipedia.org/wiki/Cooley..._FFT_algorithm
    Obviously, a radix-8 FFT is a little bit more complicated, but it follows the same line to exploit more symmetries in the phasor e^-i2πkn/N.

  11. #11
    Junior Member
    Join Date
    Feb 2021
    Posts
    13
    Thank you for your replies to my bemused post yesterday... sometimes my overeagerness is embarrassing, i was feeling very ashamed reading my own words again this morning, so thank you for not letting me down besides my inappropriate behaviour.

    Like MarkT points out i have very little large scale programming experience and since Corona I'm kind of isolated from university. I don't have anyone to ask anything and don't know on how to overcome the lack of experience to get more programming experience without having any programming experience in the first place.

    I noticed one thing from your answers that i found out through calculating a fourier transformation on a piece of paper of the exemplary sum (1,2,3,4).

    The transform of (1,2,3,4) is (10, -2+2i, -2, -2-2i)

    So actually for a radix4 algorithm the last 4 calculations from exp(-i2πkn/N) are always resulting in a product inside the exponential function with either π, -π , π/2 or -π/2 which gets you either -1, 1, i or -i for the multiplication.

    I'm so stupid, the reason why there are no terms with exp(), sine() or cosine() is because you just need -1, 1, i or -i...

    Please excuse my confusing chut yesterday - i really was being an idiot. Thanks again for not letting me down.


    With kind regards, mala

  12. #12
    Senior Member
    Join Date
    Jul 2020
    Posts
    969
    The FFT utilizes a factorization of the DFT matrix and divide-and-conquer to calculate the DFT more efficiently,
    its just algebraic simplification at heart.
    Its common, but not necessary, to factorize by powers of two. There's even a way to do an FFT for a prime number
    of samples, but mostly we use powers of two in practice.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •