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.

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...