Browse Prior Art Database

Verringerung der numerischen Komplexität von FFT-Algorithmen durch Ausnutzung von a priori Informationen bei zero-padded Input-Datensätzen

IP.com Disclosure Number: IPCOM000017895D
Original Publication Date: 2001-Oct-01
Included in the Prior Art Database: 2003-Jul-23
Document File: 1 page(s) / 150K

Publishing Venue

Siemens

Related People

Matthias Drobnitzky: AUTHOR

Abstract

Die Fouriertransformation als mathematische Metho- de zur Spektralzerlegung von Messdaten hat vielfälti- ge Einsatzgebiete, insbesondere in der Magnetreso- nanz (MR)-Tomographie wird sie sowohl in Auslese- richtung als auch in Phasenkodierrichtung bei der Bildrekonstruktion eingesetzt. Während die diskrete Fouriertransformation (DFT) von der numerischen Komplexität O(n 2 ) ist, wird ab Vektorgrößen von n=32 – 64 die sogenannte Fast Fouriertransformati- on (FFT) eingesetzt, deren Komplexität nur noch O (n log 2 n) ist. Die FFT ist besonders performant, solange die Vektorlänge eine 2-er Potenz ist. Ist die Vektorlänge n ein Produkt ganzer Zahlen, so finden -1 -1 i.d.R. mixed-radix FFTs Anwendung. In der Praxis wird jedoch häufig aus Praktikabilitätsgründen der Input-Datenvektor mit Nullen auf die nächste 2-er Potenz aufgefüllt (zero-padding, SINC-Interpolation) und dann eine normale FFT durchgeführt. Das ist besonders günstig in Situationen wie der Bildberech- nung in der MR-Tomographie, wo feste Darstel- lungsmatrizen zur Darstellung von Bildern aus ge- messenen MR-Signalen Anwendung finden, die 2-er Potenzen als Ausdehnung haben (64, 128, 256, 512 - Matrix). Zero-padding der Input-Daten taucht z.B. in den MR-Applikationen auf, wo eine anisotrope Ort- sauflösung (zum Zwecke von Messzeitreduktion oder SNR-Erhöhung) erwünscht ist. Dies ist üblich in Auslese- wie auch in Phasenkodier- und 3D- Partitionrichtung. Eine weitere übliche Anwendung ist die eines rechteckigen, nicht-quadratischen Field- of-Views (FOV) oder allgemein einer rechteckigen Volumenabdeckung. Es wird vorgeschlagen, das a priori Wissen um die Anzahl und die genaue Lage von durch zero-padding in den Datenvektor eingefügter Nullen dahingehend auszunutzen, dass durch entsprechende Umgestaltung des FFT-Algorithmus weniger komplexe Multiplika- tionen durchgeführt werden müssen. Da deren Anzahl wesentlich in die numerische Komplexität und damit die Rekonstruktionsgeschwindigkeit eingeht, ist so eine erhöhte Bildrekonstruktionsrate möglich. Es profitieren alle Anwendungen, bei denen aufgrund o.g. Gründe von einer 2-er Potenz als Länge der Datenvektoren abgewichen wird. Das Verfahren lässt sich auf die normale FFT wie auch alle mixed-radix FFT und Varianten derselben anwenden. Am Beispiel einer decimation-in-time FFT zeigt sich (siehe Abb.1), dass die numerische Komplexität von n/2

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 54% of the total text.

Information / Kommunikation

Verringerung der numerischenKomplexität von FFT-Algorithmendurch Ausnutzung von a priori In-formationen bei zero-padded In-put-Datensätzen

Idee: Matthias Drobnitzky, Erlangen

Die Fouriertransformation als mathematische Metho-de zur Spektralzerlegung von Messdaten hat vielfälti-ge Einsatzgebiete, insbesondere in der� Magnetreso-nanz� (MR)-Tomographie wird sie sowohl in Auslese-richtung� als� auch� in� Phasenkodierrichtung� bei� derBildrekonstruktion eingesetzt. Während die� diskreteFouriertransformation� (DFT) von� der� numerischenKomplexität� O(n 2 )� ist,� wird� ab� Vektorgrößen� vonn=32 – 64 die� sogenannte Fast Fouriertransformati-on� (FFT) eingesetzt, deren Komplexität nur noch O(n� log 2� � n)� ist.� Die� FFT� ist� besonders performant,solange die Vektorlänge eine 2-er Potenz ist. Ist dieVektorlänge� n ein Produkt ganzer Zahlen, so findeni.d.R. mixed-radix FFTs Anwendung. In der Praxiswird� jedoch� häufig� aus� Praktikabilitätsgründen� derInput-Datenvektor� mit� Nullen� auf � die nächste 2-erPotenz aufgefüllt (zero-padding, SINC-Interpolation)und� dann� eine� normale� FFT� durchgeführt.� Das istbesonders günstig in Situationen wie der Bildberech-nung� in� der� MR-Tomographie,� wo� feste� Darstel-lungsmatrizen� zur� Darstellung� von� Bildern� aus ge-messenen MR-Signalen Anwendung finden, die 2-erPotenzen als Ausdehnung haben (64, 128, 256, 512� -Matrix). Zero-padding der Input-Daten taucht z.B. inden MR-Applikationen auf, wo eine anisotrope Ort-sauflösung (zum Zwecke von Messzeitreduktion oderSNR-Erhöhung)� erwünscht� ist.� Dies ist üblich inAuslese- wie auch in Phasenkod...