-         

Seite 1 von 2 12 LetzteLetzte
Ergebnis 1 bis 10 von 12

Thema: Bit Umkehr

  1. #1
    Neuer Benutzer Öfters hier
    Registriert seit
    25.05.2006
    Ort
    nrw
    Beiträge
    7

    Bit Umkehr

    Anzeige

    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

  2. #2
    Erfahrener Benutzer Robotik Einstein
    Registriert seit
    06.02.2005
    Ort
    Hamburg
    Alter
    31
    Beiträge
    4.255
    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?

  3. #3
    Neuer Benutzer Öfters hier
    Registriert seit
    25.05.2006
    Ort
    nrw
    Beiträge
    7
    Hi ,

    dank dir für deine Antwort..

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

    LG
    Mary

  4. #4
    Erfahrener Benutzer Robotik Einstein
    Registriert seit
    06.02.2005
    Ort
    Hamburg
    Alter
    31
    Beiträge
    4.255
    Das bitweise Komplement eine Variable bildet man mit ~. Hast du kein C-Handbuch oder ne Befehlsübersicht, wo sowas drinsteht?

  5. #5
    Neuer Benutzer Öfters hier
    Registriert seit
    25.05.2006
    Ort
    nrw
    Beiträge
    7
    dank dir doch hab ich..aber bekomms trotzdem nicht hin..

  6. #6
    Super-Moderator Robotik Visionär Avatar von PicNick
    Registriert seit
    23.11.2004
    Ort
    Wien
    Beiträge
    6.836
    VIelleicht so:
    char bBit; // da sin irgendwelche bits gesetzt
    bBit ^= (1<<Bitnummer)
    das Bit mit der bitnummer 0-7 wird umgedreht
    mfg robert
    Wer glaubt zu wissen, muß wissen, er glaubt.

  7. #7
    Neuer Benutzer Öfters hier
    Registriert seit
    25.05.2006
    Ort
    nrw
    Beiträge
    7
    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;
       }
     }

  8. #8
    Erfahrener Benutzer Robotik Einstein Avatar von SprinterSB
    Registriert seit
    09.06.2005
    Ort
    An der Saar
    Beiträge
    2.801
    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
    Disclaimer: none. Sue me.

  9. #9
    Neuer Benutzer Öfters hier
    Registriert seit
    25.05.2006
    Ort
    nrw
    Beiträge
    7
    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();
    
    }

  10. #10
    Neuer Benutzer Öfters hier
    Registriert seit
    25.05.2006
    Ort
    nrw
    Beiträge
    7
    Euch nochmals einen riesen Dank für die Mühe!!

Seite 1 von 2 12 LetzteLetzte

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •