Fast Fourier Transform and Convolution Algorithms

در اولین ویرایش این کتاب، ما در فصل 6 و 7 کاربردهای کانولوشن های چند بعدی و DFT تبدیل هایی را که در سال 1977 معرفی کردیم و تبدیل های چند جمله ای نامیدیم، پوشش دادیم. از زمان انتشار اولین ویرایش این کتاب، چندین تحول مهم جدید در مورد تبدیل های چند جمله ای رخ داده است، و ما در این نسخه، بحثی در مورد رابطه بین الگوریتم های تبدیل چند جمله ای DFT و کانولوشن قرار داده ایم. این ماده در پیوست A همراه با ارائه الگوریتم‌های تبدیل چند جمله‌ای کانولوشن جدید و با استفاده از تبدیل‌های چند جمله‌ای برای محاسبه تبدیل‌های کسینوس چند بعدی پوشش داده شده است. ما دریافتیم که الگوریتم‌های کانولوشن کوتاه و محصول چند جمله‌ای فصل. 3 به طور گسترده مورد استفاده قرار گرفته است. این ما را بر آن داشت تا در این نسخه چندین الگوریتم محصول چند جمله‌ای یک بعدی و دو بعدی را که در پیوست B فهرست شده‌اند، در این نسخه قرار دهیم. از آنجایی که کتاب ما به عنوان بخشی از چندین دوره تحصیلات تکمیلی که در دانشگاه‌های مختلف تدریس می‌شود، استفاده می‌شود. مجموعه ای از مشکلات را به این نسخه اضافه کرد که بخش ها را پوشش می دهد. 2 تا 8. برخی از این مشکلات همچنین برای نشان دادن برخی از کارهای تحقیقاتی در مورد DFT و الگوریتم‌های کانولوشن کاربرد دارند. من مدیون خانم A. Schlageter هستم که نسخه خطی این ویرایش دوم را آماده کرد. لوزان HENRI J. NUSSBAUMER آوریل 1982 مقدمه بر چاپ اول این کتاب به روشی یکپارچه الگوریتم های سریع مختلفی را که برای اجرای فیلترهای دیجیتال و ارزیابی تبدیل های فوریه گسسته استفاده می شوند، ارائه می دهد.

In the first edition of this book, we covered in Chapter 6 and 7 the applications to multidimensional convolutions and DFT's of the transforms which we have introduced, back in 1977, and called polynomial transforms. Since the publication of the first edition of this book, several important new developments concerning the polynomial transforms have taken place, and we have included, in this edition, a discussion of the relationship between DFT and convolution polynomial transform algorithms. This material is covered in Appendix A, along with a presentation of new convolution polynomial transform algorithms and with the application of polynomial transforms to the computation of multidimensional cosine transforms. We have found that the short convolution and polynomial product algorithms of Chap. 3 have been used extensively. This prompted us to include, in this edition, several new one-dimensional and two-dimensional polynomial product algorithms which are listed in Appendix B. Since our book is being used as part of several graduate-level courses taught at various universities, we have added, to this edition, a set of problems which cover Chaps. 2 to 8. Some of these problems serve also to illustrate some research work on DFT and convolution algorithms. I am indebted to Mrs A. Schlageter who prepared the manuscript of this second edition. Lausanne HENRI J. NUSSBAUMER April 1982 Preface to the First Edition This book presents in a unified way the various fast algorithms that are used for the implementation of digital filters and the evaluation of discrete Fourier transforms.