Fast Fourier Transforms

دسته بندی: موجک و پردازش سیگنال
ویرایش:  
نویسندگان: Burrus C.S. (Ed.)  
سری:  
 
ناشر:  
سال نشر:  
تعداد صفحات: 254 
زبان: English 
فرمت فایل : PDF (درصورت درخواست کاربر به PDF، EPUB یا AZW3 تبدیل می شود) 
حجم فایل: 1 مگابایت 

قیمت کتاب (تومان) : 40,000

دانشگاه رایس، 2008، -254 ص. این کتاب بر تبدیل فوریه گسسته (DFT)، کانولوشن گسسته، و به ویژه، الگوریتم های سریع برای محاسبه آنها تمرکز دارد. . این موضوعات از ابتدا در مرکز پردازش سیگنال دیجیتال قرار داشته اند و نتایج جدید در سخت افزار، تئوری و برنامه های کاربردی همچنان آنها را مهم و هیجان انگیز نگه می دارد. تکنیک‌هایی که اکنون تبدیل فوریه سریع (FFT) برای محاسبه ضرایب در یک انبساط مثلثاتی مدار یک سیارک در سال 1805 می‌نامیم [174]. با این حال، این مقاله اصلی کولی و توکی [88] در سال 1965 بود که توجه جامعه علم و مهندسی را به خود جلب کرد و به نوعی، رشته پردازش سیگنال دیجیتال (DSP) را پایه گذاری کرد.
تاثیر Cooley-Tukey FFT بسیار زیاد بود. مشکلاتی را می‌توان به سرعت حل کرد که حتی چند سال قبل به آن توجه نمی‌شد. انبوهی از تحقیقات تئوری را گسترش داد و برنامه های عملی عالی را توسعه داد و همچنین برنامه های کاربردی جدیدی را باز کرد [94]. در سال 1976، وینوگراد مقاله کوتاهی را منتشر کرد [403] که دومین شتاب تحقیقاتی را به حرکت درآورد [86]. این نوع دیگری از الگوریتم بود که طول داده‌ها را که می‌توانستند به طور مؤثر تبدیل شوند گسترش می‌داد و تعداد ضرب‌های مورد نیاز را کاهش می‌داد. کار زمینی برای این الگوریتم قبلاً توسط Good [148] و توسط Rader [308] تنظیم شده بود. در سال 1997 فریگو و جانسون برنامه‌ای را توسعه دادند که آنها را FFTW (سریعترین تبدیل فوریه در غرب) نامیدند [130]، [135] که ترکیبی از بسیاری از ایده‌های موجود در الگوریتم‌های دیگر و همچنین نتایج جدید برای ارائه یک نتیجه قوی و بسیار سریع است. سیستمی برای طول داده های کلی در انواع معماری های کامپیوتر و DSP. این اثر در سال 1999 برنده جایزه Wilkinson برای نرم افزار عددی شد.
تاکید بیش از حد بر اهمیت الگوریتم های DFT، کانولوشن و سریع دشوار است. با سابقه ای که به گاوس [174] برمی گردد و مجموعه ای از مراجع در مورد این موضوعات که در سال 1995 منجر به بیش از 2400 مدخل شد [362]، FFT ممکن است مهم ترین الگوریتم عددی در علوم، مهندسی و ریاضیات کاربردی باشد. نتایج نظری جدید هنوز ظاهر می‌شوند، پیشرفت‌ها در رایانه‌ها و سخت‌افزار دائماً سؤالات اساسی را بازگو می‌کنند، و برنامه‌های کاربردی جدید حوزه‌های جدیدی را برای تحقیق باز می‌کنند. امید است که این کتاب زمینه، منابع، برنامه‌ها و انگیزه‌ای برای تشویق به تحقیقات و نتایج بیشتر در این زمینه و همچنین ابزارهایی برای کاربردهای عملی فراهم کند.
مطالعه FFT نه تنها برای درک یک ابزار قدرتمند ارزشمند است. ، همچنین نمونه اولیه یا نمونه ای است از اینکه چگونه الگوریتم ها را می توان کارآمد ساخت و چگونه می توان یک نظریه برای تعریف بهینه ایجاد کرد. تاریخچه این توسعه همچنین بینشی به فرآیند تحقیقاتی می دهد که در آن زمان و خوشبختی نقش های جالبی دارند. پیشگفتار: تبدیل فوریه سریع
مقدمه: فوریه سریع تبدیل
نقشه شاخص چند بعدی
توضیح چند جمله ای سیگنال ها
DFT به عنوان پیچیدگی یا فیلتر کردن
عملکرد عملگرهای پردازش سیگنال
الگوریتم های کوتاه DFT وینوگراد
DFT و FFT : یک نمای جبری
الگوریتم تبدیل فوریه سریع کولی-توکی
الگوریتم های تبدیل فوریه فاکتور اولیه و وینوگراد در عمل
الگوریتم هایی برای داده ها با محدودیت
الگوریتم های کانولوشن
نظرات : تبدیل فوریه سریع
نتیجه‌گیری: تبدیل فوریه سریع
فلوگراف‌های FFT
تعداد عملیات برای FFT با طول عمومی
برنامه‌های کامپیوتری FFT
برنامه‌ها برای FFT‌های کوتاه

Rice University, 2008, -254 pp. This book focuses on the discrete Fourier transform (DFT), discrete convolution, and, particularly, the fast algorithms to calculate them. These topics have been at the center of digital signal processing since its beginning, and new results in hardware, theory and applications continue to keep them important and exciting.
As far as we can tell, Gauss was the first to propose the techniques that we now call the fast Fourier transform (FFT) for calculating the coefficients in a trigonometric expansion of an asteroid's orbit in 1805 [174]. However, it was the seminal paper by Cooley and Tukey [88] in 1965 that caught the attention of the science and engineering community and, in a way, founded the discipline of digital signal processing (DSP).
The impact of the Cooley-Tukey FFT was enormous. Problems could be solved quickly that were not even considered a few years earlier. A flurry of research expanded the theory and developed excellent practical programs as well as opening new applications [94]. In 1976, Winograd published a short paper [403] that set a second _urry of research in motion [86]. This was another type of algorithm that expanded the data lengths that could be transformed efficiently and reduced the number of multiplications required. The ground work for this algorithm had be set earlier by Good [148] and by Rader [308]. In 1997 Frigo and Johnson developed a program they called the FFTW (fastest Fourier transform in the west) [130], [135] which is a composite of many of ideas in other algorithms as well as new results to give a robust, very fast system for general data lengths on a variety of computer and DSP architectures. This work won the 1999 Wilkinson Prize for Numerical Software.
It is hard to overemphasis the importance of the DFT, convolution, and fast algorithms. With a history that goes back to Gauss [174] and a compilation of references on these topics that in 1995 resulted in over 2400 entries [362], the FFT may be the most important numerical algorithm in science, engineering, and applied mathematics. New theoretical results still are appearing, advances in computers and hardware continually restate the basic questions, and new applications open new areas for research. It is hoped that this book will provide the background, references, programs and incentive to encourage further research and results in this area as well as provide tools for practical applications.
Studying the FFT is not only valuable in understanding a powerful tool, it is also a prototype or example of how algorithms can be made efficient and how a theory can be developed to define optimality. The history of this development also gives insight to the process of research where timing and serendipity play interesting roles. Preface: Fast Fourier Transforms
Introduction: Fast Fourier Transforms
Multidimensional Index Mapping
Polynomial Description of Signals
The DFT as Convolution or Filtering
Factoring the Signal Processing Operators
Winograd's Short DFT Algorithms
DFT and FFT: An Algebraic View
The Cooley-Tukey Fast Fourier Transform Algorithm
The Prime Factor and Winograd Fourier Transform Algorithms in Practice
Algorithms for Data with Restrictions
Convolution Algorithms
Comments: Fast Fourier Transforms
Conclusions: Fast Fourier Transforms
FFT Flowgraphs
Operation Counts for General Length FFT
FFT Computer Programs
Programs for Short FFTs