Bit Umkehr

[Mary]

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

[uwegw]

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?

[Mary]

Hi ,

dank dir für deine Antwort..

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

LG
Mary

[uwegw]

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

[Mary]

dank dir doch hab ich..aber bekomms trotzdem nicht hin..

[PicNick]

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

[Mary]

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

#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;
   }
 }

[SprinterSB]

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:

/* 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

[Mary]

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

#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();

}

[Mary]

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