Bit Umkehr

Hallo,

ich muss für die Uni in C eine Bit-Umkehr programmieren, komme aber irgendwie nicht weiter.
Hat vielleicht jemand eine Idee wie das funktionieren soll?

Danke
Mary

Was ghenau versteht ihr unter einer Bit-Umkehr? Eine Variable mit mehreren Bits, in der nun jedes einzelne Bit invertiert werden soll? Für PC oder µC?

Hi ,

dank dir für deine Antwort..

Ja genau..es soll jedes einzelne Bit invertiert werden..

LG
Mary

Das bitweise Komplement eine Variable bildet man mit ~. Hast du kein C-Handbuch oder ne Befehlsübersicht, wo sowas drinsteht?

dank dir doch hab ich..aber bekomms trotzdem nicht hin.. ](*,)

VIelleicht so:
char bBit; // da sin irgendwelche bits gesetzt
bBit ^= (1<<Bitnummer)
das Bit mit der bitnummer 0-7 wird umgedreht

Hm..also habs so..aber irgendwie ist es falsch

Code:

---

#include <stdio.h>
#include <math.h>
#include <complex.h>       

#define Pi 3.14159265358979323846264        /* Pi */

/* *** Die eigentliche FFT
 * f[]: Eingabe: zu transformierende Daten
 *        Ausgabe: Ergebnis der Transformation
 * N:        Anzahl der Datenpunkte (2er-Potenz !!!!)
 * sign=-1: Hintransformation; sign=1: Ruecktransformation */

void fft(complex f[], int N, int sign) {
  double isqrtN;
  complex temp, W, Wk;
  int r, t, mask, n, no2, m, k, l;
  /* *** Teste, ob N 2er-Potenz ist */
  for(mask=1; mask<N; mask <<= 1)        ;
  if(mask != N) {
    fprintf(stderr, "N = %d ist keine 2er-Potenz !\n", N);
    exit(13);
  }
  /* *** Teile Daten durch sqrt(N) */
  isqrtN = 1/sqrt(N);
  for(r=0; r<N; r++)
    f[r] *= isqrtN;
  /* *** Bit-Umkehr */
  for(t=0, r=0; r<N; r++) {
    if(t > r) {        /* Vertausche f[r] und f[t] */
        temp = f[r];
        f[r] = f[t];
        f[t] = temp;
      }
    mask = N;                /* Bit-umgekehrtes Inkrement von t */
    do {
        mask >>= 1;
        t ^= mask;
      } while((! (t & mask)) && mask);
  }

no2 = 1;
  for(m=1; (n=(no2 << 1)) <= N; m++) {
    W = cexp(I*sign*2*Pi/n);        /* W_n (C99 kennt I) */
    Wk = 1;
    for(k=0; k<no2; k++) {
        for(l=k; l<N; l+=n) {
          complex temp = Wk*f[l+no2];
          f[l+no2] = f[l] - temp;
          f[l] += temp;
        }
        Wk *= W;        /* Wk = W^k */
      }
    no2 = n;
  }
 }

---

Nochmal: was meinst du mit Bit-Umkehr?

Da es um FFT geht, vermute ich mal, du meinst damit bit-reverse addressing.

Um die Bits zu vertauschen (also bit_n <-> bit_{N-n} bei N Bits), kann man folgendes machen:

Code:

---

/* Reverse bits of the N-bit value bits */
static inline unsigned int
reverse_bits (unsigned int N, unsigned int bits)
{
        unsigned int rev = 0;
       
        while (N--)
        {
                rev <<= 1;
                if (bits & 1)
                        rev |= 1;
                bits >>= 1;       
        }
       
        return rev;
}

---

Das Bit-reverse Inkrement von t ist dann

reverse_bits (N, 1+reverse_bits (N, t))

oder so?

Da es wahrscheinlich auch auf Effizienz (speed) ankommt, kann man das noch mit Assembler tunen. Das wiederum ist plattformabhänhig. Manche µC verfügen eigens dafür über einen bit-reverse addressing mode (etwa TriCore).

Hoppla, hab gerade gesehen, daß du N schon verwendest... in dem falls ist
N_SprinterSB = exact_log2 (N_Mary)

BTW pi gibt's schon als Makro M_PI

Hab nun das raus... Hat vlt einer eine Idee wo der Fehler sein kann??

Code:

---

#include<stdio.h>
#include<math.h>
# define pi 3.14

struct komplex
{
      double re;
      double im;
};
komplex Cadd(komplex x, komplex y)
{
        komplex res;
        res.re=x.re+y.re;
        res.im=x.im+y.im;
        return res;
}
komplex Csub(komplex x, komplex y)
{
        komplex res;
        res.re=x.re-y.re;
        res.im=x.im-y.im;
        return res;   
}
komplex Cmult(komplex x, komplex y)
{
        komplex res;
        res.re=x.re*y.re-x.im*y.im;
        res.im=x.im*y.re+x.re*y.im;
        return res;
}

int potenz(int i)
{
    int j,k=1;
    for(j=0;j<i;j++)
    {
                    k=k*2;
    }               
    return k;
}


int main()
{ 
  int j,n,k,p,r,m,t,M,q=3;
  n=potenz(q);
  komplex x[n];


//Stützstellen     
      for(j=0;j<n;j++)
      {
      x[j].im=0.;
      x[j].re=((2*pi*j)/n)-pi;   
      }
komplex f[n];
/*
//Sägezahn
for (j=0;j<n;j++)
{
    if(-pi<=x[j].re<pi)
    {
    f[j].im=0.;
    f[j].re=x[j].re;
    }
} 

//Rechteck
for (j=0;j<n;j++)
{
    f[j].im=0.;
    if(x[j].re<0.)
    {
    f[j].re=pi;
    }
    else
    {
        f[j].re=-pi;
    }   
}
 */   
//Dreieck
for (j=0;j<n;j++)
{
    f[j].im=0.;
    if(x[j].re<-pi/2.)
    {
                    f[j].re=2.*x[j].re+2.*pi;
    }                     
    else if(x[j].re>=-pi/2. && x[j].re<pi/2.)
    {             
                    f[j].re=-2.*x[j].re;
    }
    else if(pi/2.<=x[j].re)
    {
                    f[j].re=2.*x[j].re-2.*pi;
    }               
}   

//Umsortierung......DIE IST FALSCH UND ICH WILL WISSEN WIE ES RICHTIG FUNKTIONIERT
for(k=0;k<=n/2-1;k++)
{
                    t=2*k;
                    m=n/2;
                    while(t>=m)
                    {
                                t=t-m;
                                m=m/2;
                    }
                    t=t+m;         
                    f[k].re=f[t].re;

printf("%i\n",t);
}
for(k=n/2;k<=n-1;k++)
{
                    t=2*k+1;
                    m=n/2;
                    while(t>=m)
                    {
                                t=t-m;
                                m=m/2;
                    }
                    t=t+m;         
                    f[k].re=f[t].re;                 
printf("%i\n",t);
}
//FFT

        for(r=0;r<=q-1;r++)
        {
                  M=potenz(r);
                  komplex w,x;
                  w.re=cos(pi/M);
                  w.im=-sin(pi/M);
            for(k=0;k<=M-1;k++)
            {
                  for(j=0;j<=potenz(q-r-1)-1;j++)
                  {
                                                 
                      x=Cmult(w,f[2*j*M+M+k]);
                      f[2*j*M+M+k]=Csub(f[2*j*M+k],x);
                      f[2*j*M+k]=Cadd(f[2*j*M+k],x);                                                           
                  }   
              }
        }

//Inverse FFT:Wir machen aus f[j] die inversen: f[j]/n!!!



komplex umkehr;
umkehr.re=1/n;
umkehr.im=0.;
for(j=0;j<=potenz(q)-1;j++)
{
f[j]=Cmult(umkehr,f[j]);                       
}                         



//Berechnung der koeffizienten
double A[n/2], B[n/2-1];


for (j=0;j<=n/2;j++)
{
    if(j==0)        {A[0]=2.*f[0].re;}
   
    else            {A[j]=f[j].re+f[n-j].re;
                    printf("A(%i)=(%3.3f)\n",j,A[j]);
                    }
}
printf("\n\n");

for (j=1;j<(n/2)-1;j++)
{       
                    B[j]=f[n-1].im-f[j].im;
                    printf("B(%i)=(%3.3f)\n",j,B[j]);
}
//Auswertung an der Stelle z
double wert,summe,z=pi/2.;                                     

for(j=1;j<=n/2-1;j++)
{
    summe=0;
    summe=summe+A[j]*cos(j*z)+B[j]*sin(j*z);               
}
wert=A[0]/2.+summe+cos(z*n/2.)*A[n/2]/2.;

printf("p(%5.5f)=%5.5f\n",z,wert);


getchar();

}

---

Euch nochmals einen riesen Dank für die Mühe!!

Scherzkeks. Wie wär's damit, den Code mal gescheit einzurücken und zu erzählen, WAS nicht geht oder was du überhaupt haben willst?

Sorry ist nun richtig eingerückt ;)

Also es werden bei mir andere Zahlen angezeigt..Aber rauskommen sollten 0,4,2,6,1,5,3,7

Ich denke das es soweit richtig ist, bis auf die Umsortierung..

mfg