Parallele 2D-FFT Algorithmen

Parallele 2D-FFT Algorithmen sind in der digitalen Bildverarbeitung von Bedeutung, wenn Bilder aus z.B. $512 \times 512$ Pixeln, also $2^{18}$ einzelnen Werten, möglichst in Echtzeit transformiert werden sollen. In diesem Abschnitt sollen zwei vom Ansatz und der Verteilung der Daten auf die Prozessoren her verschiedene parallele 2D-FFT Algorithmen für den Einsatz auf MIMD-Systemen (Multiple Instruction Multiple Data) vorgestellt werden. Als Kommunikationsnetzwerk des Zielsystems wird jeweils ein Basis 2 de Bruijn-Graph angenommen.

Es gibt zwei Möglichkeiten Algorithmen zur Berechnung der 2D-DFT zu realisieren

• durch geschachtelte Anwendung der 1D-FFT
• durch Übertragung des Vorgehens beim Entwickeln der 1D-FFT auf 2 Dimensionen

Für die folgenden Algorithmen habe die Eingangsmatrix die Größe $N \times N$ mit $N := 2^p > 1, p \in {\rule[0pt]{0.21mm}{8pt}\hspace*{0.08mm}{\sf N}}$ und es sei $n := N/2$.