logo elektroda
logo elektroda
X
logo elektroda
Adblock/uBlockOrigin/AdGuard mogą powodować znikanie niektórych postów z powodu nowej reguły.

SWAP próbek w FFT. Algorytm do przetestowania próbek.

kopernik8 20 Mar 2006 22:16 2006 1
  • #1 2438479
    kopernik8
    Poziom 21  
    Witam!
    Szukam kogoś kto w prosty sposób mi przedstawi jakiś algorytm do przetasowania próbek na potrzebę FFT.
    Teorię znam ale ni jak nie moge tego odpowiednio poukładać:/
    pozdrawiam
  • #2 2494251
    shg
    Poziom 35  
    Chodzi Ci może o odwracanie bitowe?
    Jeżeli tak, to zasada działania jest względnie prosta.
    mamy próbki w tablicy o indeksach powiedzmy i = 0..n-1.
    teraz bierzemy drugą taką tablicę (to tak dla uproszczenia, w rzeczywistości nie jest ona konieczna, bo można zrobić to na tej samej tablicy)
    dla każdej próbki o indeksie i odwracamy kolejność bitów w zmiennej i, tzn. dla i=01100101 robimy i=10100110 i zapisujemy w tablicy jako element o takim indeksie.

    i największym problemem jest włąśnie to odwrócenie kolejności bitów. metod jest conajmniej kilka.
    Najprostsza, ale strasznie niewydajna to przetwarzanie po jednym bicie, w asemblerze jeszcze jako tako to wygląda, bo tam można operować bitem przeniesienia, ale w C... hmmm, już nie ma tak lekko, zwłąszcza, że raczej żaden kompilator tego odpowiednio nie zoptymalizuje.

    Przykład strasznie paskudny:
    int bitrev(int i, int n) { /* i - wartość do 'obrócenia', n - ilość bitów */
      int z, o;
      o = 0;
      for(z = 0; z<n; z++)
        if(i && 1<<z)
          o |= 1<<(n-z-1);
    
      return(o);
    }


    Druga opcja, to wygenerowanie odpowiedniej tabeli zawierającej 'odwrócone' wartości, wtedy zamiana miejscami pójdzie naprawdę szybko

    Poza tym widziałem ten algorytm wykonany na wszelakiej moaści pętlach; nowe indeksy były przeliczane 'w locie', coś jak dodawanie binarne, tyle że z odwrotnie ustawionymi bitami.

    Na przykład zwiększenie 'odwróconej' liczby o 1 (przykłąd z książki "Hackers Delight"):
    unsigned x, m; 
     
    m = 0x80000000; 
    x = x ^ m; 
    if ((int)x >= 0) {
       do {
          m = m >> 1; 
          x = x ^ m; 
       } while (x < m); 
    } 


    Można też sukcesywnie dzielić liczbę (jej zapis bitowy) na połowy (żródło j.w.):
    x = (x & 0x55555555) <<  1 | (x & 0xAAAAAAAA) >>  1; 
    x = (x & 0x33333333) <<  2 | (x & 0xCCCCCCCC) >>  2; 
    x = (x & 0x0F0F0F0F) <<  4 | (x & 0xF0F0F0F0) >>  4; 
    x = (x & 0x00FF00FF) <<  8 | (x & 0xFF00FF00) >>  8; 
    x = (x & 0x0000FFFF) << 16 | (x & 0xFFFF0000) >> 16; 


    Jeżeli zamierzasz to implementować na komputerze i będziesz liczył wiele transformat tej samej wielkości pod rząd, to chyba najwydajniejsza będzie metoda z uprzednim wygenerowaniem tabelki.

    No i chyba tyle. Mam nadzieję, że o to chodziło :P
REKLAMA