Digitale Fourier-Transformation



Ressonanz, duale Räume, Sprache, Lyrike Was soll das?

Was haben die Fourier-Transformationen und Digitalen Kompressionen hier gemein mit Sprache, Lyrike und dem Weg vom Vom Kennen zum Können? MmHhh ...

Jürgen_Mittelstraß (über den Verlust des Wissens, Konstanz 1992):
Information darf nicht an die Stelle des Nachdenkens und der Urteilskraft treten. Urteilskraft lässt sich nicht lernen oder lehren, sie muss erfahren werden. Wissen entsteht erst aus der im eigenen Kontext verstandenen Information.

Hochschulrektorenkonverenz:
In der Informationsgesellschaft werden sich Methoden und Techniken der Erzeugung, Verbreitung und Vermittlung von Wissen grundlegend ändern.

Rainer Maria Rilke :
Wo sich langsam aus dem Schon-Vergessen, einst Erfahrenes sich uns entgegenhebt, rein gemeistert, milde, unermessen und im Unantastbaren erlebt:

Dort beginnt das Wort, wie wir es meinen, seine Geltung übertrifft uns still - denn der Geist, der uns vereinsamt, will völlig sicher sein, uns zu vereinen.


Fourier-Transformation (anschauliche Einführung)

In der Signalverarbeitung und Informatik wird die Diskrete Fourier-Transformation (und "Unterarten") für viele Aufgaben verwendet. Siehe z.B. de.wikipedia Diskrete Fourier-Transformation .

Es gibt zahlreiche MPEG Standards. Alle Layer basieren auf dem Prinzip der Irrelevanzreduktion, indem die Anteile des Audiosignals, die vom Gehör nicht wahrnehmbar sind, weder übertragen noch gespeichert werden ( fraunhofer.de ). Beispiele: MPEG-1 allgemein, MP1 (MPEG-1 Layer 1), MP2 (MPEG-1 Layer 2), MP3 (MPEG-1 Layer 3), MPEG-2 allgemein, MPEG-4 allgemein. Advanced_Audio_Coding ( AAC (MPEG-2/4 LC-AAC), HE-AAC / aacPlus )

In gewisser Weise gibt es Verbindungen mit der Fensterfunktion, Faltung, Wavelet-Transformation, Gabor-Transformation, Laplace-Transformation, Diskrete Kosinustransformation, Fourierreihe, Short-Time-Fourier-Transformation.

Ein Signalverlauf kann auf unterschiedliche Weise betrachtet werden. Die Kurve x(t) stellt den Signalverlauf über der Zeit dar. Solche Diagramme zeigen, wie sich das Signal mit der Zeit ändert. Eine andere Darstellung ist, das Signal durch die darin entahltenen Frequenzen darzustellen. Dies entspricht einer Zerlegung des Signales x(t) in harmonische Anteile, wie z.B.

Was ist ein Spektum?

fourier4.jpg

 a meint Amplitude, f meint Frequenz
 ω   meint Kreis-Frequenz ω[k] = 2.π.f[k]
     mit k = 0, 1, 2, ... 
 Harmonischen Frequenz-Komponentent:
 harm( a, f[k], φ) = a · cos( ω[k] · t + φ )

Ein Spektrum ist ein Diagramm, bei dem die Amplituden a über den Frequenzen f aufgetragen sind. Periodische Signale führen zu Komponenten mit ganzzahligen Frequenzen f[k] = k.f[0].


DFT (anschauliche Ableitung)

Die digitale Fourier-Transformation soll anschaulich erklärt werden. Zur Vereinfachung sollen lediglich anz=5 Samples pSrcX[k] mit k=0,1,2,3,4 vorliegen. Ein Kreis wird in 5 Sektoren eingeteilt. Die Winkel sind w[i] = i*2*π/5 mit i=0,1,2,3,4. Die x-Komponenten der Punkte P[i]( cos[i], sin[i]) auf dem Einheitskreis sind cos(w[i]).

     i = 0 1 2 3 4 Summe
cos[i] =  1.000000  0.309016 -0.809016 -0.809016  0.309016  0.000000
sin[i] =  0.000000  0.951056  0.587785 -0.587785 -0.951056  0.000000

Die folgende Skizze zeigt die Kreispunkte und die x-Komponenten.

fourier-transformation.gif

 Betrachtung der x-Komponenten

 Samples      : pSrcX[k] mit k=0,1,2,3,4
 Einheitskreis: w[i] = i*2*π/5,  cos(w[i])

 Rechnung :
 Start    : x = 0.0; 
 Summation: x = x + cos(w[i]) * pSrcX[k] 
                    für ein j jeweils über alle k ergibt x[j]

DFT (Beispiel mit Sample-Anz=5)

Die anz=5 Samples ( pSrcX[k] k = 0, 1, 2 ,3, 4 ) werden jeweils 5 mal mit unterschiedlichen cos(w[i]) multipliziert.

j = 0   1   2   3   4  
k = 0 1 2 3 4   0 1 2 3 4   0 1 2 3 4   0 1 2 3 4   0 1 2 3 4  
  i   = k * j % anz = 0 0 0 0 0   0 1 2 3 4   0 2 4 1 3   0 3 1 4 2   0 4 3 2 1  
 Start mit x := 0.0; y := 0.0;
 Dann summiere für ein j 
 ( jeweils über alle k )
   x := x  +  cos[i] * pSrcX[k] ; 
   y := y  +  sin[i] * pSrcY[k] ;
 ergibt x[j]

Für jedes j = 0, 1, 2, 3, 4 ergeben sich wegen jeweils k = 0, 1, 2, 3, 4 für x jeweils 25 Multiplikationen cos[i] * pSrcX[k].

 j = 0 wird benutzt i = 0, 0, 0, 0, 0 
  j = 1  benutzt i = 0, 1, 2, 3, 4 
  j = 2  benutzt i = 0, 2, 4,  6,  8; wegen  > 2·Pi: ( 0, 2, 4, 1, 3 ) 
  j = 3  benutzt i = 0, 3, 6,  9, 12; wegen  > 2·Pi: ( 0, 3, 1, 4, 2 ) 
  j = 4  benutzt i = 0, 4, 8, 12, 16; wegen  > 2·Pi: ( 0, 4, 3, 2, 1 ) 

Die Produkte werden summiert und ergeben die x-Komponente der Spektralkomponente ( Fouriertransformierte ). Zum Verständnis ist es günstig, die 5 Partialsummen für jeden j-Werte zu bilden.


DFT (C-Programm)

Es liegen z.B. anz = 256 Sound-Samples vor. Das komplex Fourier-Spektrum soll berechnet werden. Das folgende Verfahren ist wegen den vielen sin(), cos()-Berechnungen für eine größere Sample-Anzahl zu langsam. Das Verfahren soll lediglich den Kern der komplexen Fourier-Transformation beschreiben. Es werden eindimensionale double-Array verwendet, die global seien und z.B. gemäß

 double * p = ( double * ) calloc( anz, sizeof( double ) );

allokiert wurden. Die Freigabe des Speichers sollte an geeigneter Stelle mit free( p ) erfolgen. In den double-Array pSrcX sind anz = 256 double-Samples enthalten und alle 256 Elemente des double-Arrays pSrcY seien 0.0. Es werden 2 globale Tabellen mit den berechneten cos( ), sin( )-Werten benötigt, die z.B. gemäß

 // Berechnung der Hilfarrays    pCos[ ], pSinY[ ]
 int k ; double w = 0.0 ; double dw = 2.0 * π / anz ; 
 for ( k = 0 ; k < anz ; k ++, w += dw , pCos ++ , pSin ++ ) {
    * pCos = cos( w ) ;
    * pSin = sin( w ) ;
 }

berechnet werden können.

// Fourier-Algorithmus ( in: anz, pSrcX[ ], pSrcY[ ]; out: pDstX[ ], pDstY[ ] )
  double x, y, Cos, Sin ;
  int  i, j, k ; 

  if ( typ == FT_SPECTRUM2TIME ) {
    for ( j = 0 ; j < anz ; j ++ ) { pSrcX[j] /= anz ; pSrcY[j] /= anz ; }
  }

  for ( j = 0 ; j < anz ; j ++ ) {    x = y = 0.0 ; 
    for ( k = 0 ; k < anz ; k ++ ) {  i = k * j % anz ;
      Cos = +pCos[ i ] ; 
      Sin = -pSin[ i ] ; if ( typ == FT_SPECTRUM2TIME ) Sin = -Sin ; 

      x += Cos * pSrcX[k] - Sin * pSrcY[k] ;
      y += Sin * pSrcX[k] + Cos * pSrcY[k] ;
    }
    pDstX[ j ] = x ; 
    pDstY[ j ] = y ; 
  }
}

Dieser Algorithmus berechnet aus den anz=256 Sample-Werten pSrcX[k] = Sample[k], pSrcY[k] = 0.0 das komplexe Spektrum pDstX[k], pDstY[k]. Die k-te Amplitude amplitude[k] ist dann

 Amplitude[k] = sqrt( pDstX[k]*pDstX[k] + pDstY[k]*pDstY[k] )

Die Umkehrtransformation ermittelt aus dem Spektrum die Samples. Zur Berechnung der Umkehrtransformation sind alle Werte des Spektrums in die Source-Arrays zu kopieren ( pSrcX[j] = pDstX[j], pSrcY[j] = pDstY[j] ) und mit ( typ == FT_SPECTRUM2TIME ) sollten sich dann in pDstX[j], pDstY[j] die ursprünglichen Samples ( bis auf Rundungsfehler ) ergeben.


DFT (ECMAScript)

Expeimenteller Code für DFT (ECMAScript):

<script type="text/javascript">/*<![CDATA[*/

function cos_tab ( anz ) {
 var k, C=[], w = 0.0, dw = 2.0 * Math.PI / anz ; 
 for (var k = 0 ; k < anz ; k ++, w += dw ) {
   C[k] = Math.cos( w ) ;
 } return C;
}

function sin_tab ( anz ) {
 var k, S=[], w = 0.0, dw = 2.0 * Math.PI / anz ; 
 for (var k = 0 ; k < anz ; k ++, w += dw ) {
   S[k] = Math.sin( w ) ;
 } return S;
}

// Geg. Samples (Daten)
var SrcX = [20, 40, 50, 30, 20, 10, 40, 50];
var SrcY = [ 0,  0,  0,  0,  0,  0,  0,  0];
//var typ  = 'TIME2SPECTRUM'; //vorwärts
//var typ  = 'SPECTRUM2TIME'; //rückwärts

function fourier_algorithmus ( SrcX, SrcY, typ ) {
  var i, j, k, x,y, c,s, DstX=[], DstY=[]; 
  var anz = Math.min(SrcX.length, SrcY.length);
  var Cos = cos_tab(anz), Sin = sin_tab(anz); 

  if ( typ == 'SPECTRUM2TIME' ) {
    for ( j = 0 ; j < anz ; j ++ ) { SrcX[j] /= anz ; SrcY[j] /= anz ; }
  }

  for ( j = 0 ; j < anz ; j ++ ) {    x = y = 0.0 ; 
    for ( k = 0 ; k < anz ; k ++ ) {  i = k * j % anz ;
      c = +Cos[i] ; 
      s = -Sin[i] ; if ( typ == 'SPECTRUM2TIME' ){ s = -s;} 
      x += c * SrcX[k] - s * SrcY[k]; 
      y += s * SrcX[k] + c * SrcY[k];
    } // DstX[j] = x; DstY[j] = y; 
    DstX[j] = x.toFixed(1); 
    DstY[j] = y.toFixed(1); 
  } return [DstX,DstY];
}

Aufrufe:

var dst = fourier_algorithmus ( SrcX, SrcY, 'TIME2SPECTRUM' );
var src = fourier_algorithmus ( dst[0], dst[1], 'SPECTRUM2TIME' );

var br = "<br />";
var ss = "DstX="+dst[0] +br+"DstY="+dst[1] +br+br 
       + "SrcX="+src[0] +br+ "SrcY="+src[1]

window.onload = function() { document.write(ss); }
/*]]>*/</script>

Ausgabe:

 DstX= 32.5,  4.425 , -6.25, -4.425,  0.0, -4.425, -6.25, 4.425
 DstY=  0.0, -2.1375,  3.75,  0.3625, 0.0, -0.3625,-3.75, 2.1375

 SrcX= 20.0, 40.0,   50.0,   30.0,   20.0, 10.0,   40.0, 50.0
 SrcY=  0.0,  0.0,   -0.0,   -0.0,    0.0,  0.0,   -0.0, -0.0

Plagiate sind out!
Viel Freude bei der Ausarbeitung!
Abgabetermin in der Veranstaltung.