بخشی از مقاله
چکیده –
تبدیل فوریه از پرکاربردترین تبدیلات در پردازش سیگنالهاي رقومی همچون پردازش تصویر و صوت است. پیاده سازي این تبدیل در سخت افزارهاي پردازشی مبتنی بر میکروکن ترلرها و پردازنده هاي پیشرفته، دو مشکل زمان پردازش زیاد و نیاز به حجم حافظه برنامه زیاد را در سر راه قرار میدهد. جهت کاهش زمان پردازش، الگوریتم FFT مورد استفاده قرار میگیرد. اما پیاده سازي این الگوریتم نیز نیاز به حجم حافظه
برنامه زیاد دارد. در این مقاله، مسئله کوتاه سازي کد برنامه براي پیاده سازي این الگوریتم مورد بررسی قرار گرفته و دو کد کوتاه مناسب معرفی شده است. کدهاي برنامه مورد شبیه سازي قرار گرفته و نتایج شبیه سازي، درستی عملکرد آن را به اثبات رسانده است.
کلید واژه- تبدیل فوریه، الگوریتم FFT، الگوریتم Radix.2، سخت افزارهاي پردازشی، پردازش سیگنالهاي رقومی، پردازش تصویر، پردازش صوت.
-1 مقدمه
یکی از مباحـث پایـهاي در پـردازش سـیگنالهـاي رقـومی، محاسبه ضرایب فوریه از یک سیگنال گسسته استتـابع. DFT1 کاربردهــاي فراوانــی در پــردازش ســیگنال دیجیتــال، ارتباطــات مخابراتی، پردازش صوت و پردازش تصویر دارد. یکی از مشکلاتی که در استفاده از این تابع با آن روبرو هستیم، زمان زیادي اسـت که براي محاسبه ضرایب این تابع صرف مـیشـود .[1] بـه همـین منظور Cooley و Tukey در سال 1965 مقالهاي با موضوع حذف محاسبات زاید در محاسبه تابع DFT، براي کاهش زمان آن ارائـه دادند.[2] بعد از این مقاله، الگوریتمهاي مختلفی به ایـن منظـور ارایه گردید، که از جمله پرکاربردترین آنها میتوان بـه Radix-2،
Radix-4 و Split-radix اشاره کرد.[6-3]
تبدیل FFT2 ماهیت جدیدي در حوزه تبـدیل ایجـاد نمـی - کند؛ بلکه راه حلی براي کاهش محاسبات تبدیل فوریـه گسسـته ارائه میکنـد .[7] پیچیـدگی محاسـباتی تبـدیل فوریـه گسسـته O(N2) میباشد؛ در صورتیکه تبدیل FFT ایـن پیچیـدگی را بـه
O(Nlog(N)) کاهش میدهد.[8]
همانطور که ذکر شد، انگیزه اصلی استفاده از FFT افـزایش
1
سرعت محاسبات میباشد. مسئلهاي که در پیـادهسـازي سـخت - افزاري این الگوریتم با آن روبرو هستیم، محدودیت حافظـه مـی - باشد. همانطور کـه مـیدانـیم هـر میکروکنترلـر و DSP داراي اندازه محدودي حافظه داخلی میباشد. همچنـین مـیدانـیم کـه ارتباط بین این پردازندهها با حافظه خـارجی، یـک ارتبـاط کنـد نسبت به ارتباط پردازنده با حافظه داخلی میباشد.
در پیادهسازي عملی ایـن الگـوریتم بـا دو مسـئله سـرعت و قیمت در انتخاب پردازنده روبرو هسـتیم. هرچـه میـزان حافظـه داخلی یک پردازنده بالاتر باشد، قیمت آن نیز بالاتر میرود. حـال اگر پیادهسازي الگوریتم به صورتی انجام شود که فضاي حافظـه داخلی پردازنـده ارزان قیمـت بـراي آن کـافی نباشـد دو راهکـار روبروي ما قرار میگیرد. اولین راهکار اضافه کردن حافظه خارجی و استفاده از آن به منظور پیادهسازي الگوریتم اسـت. همـانطـور که در بالا به آن اشاره کردیم، این کار عـلاوه بـر اﻓـﺰاﯾﺶ هزینـه سختافزار، سرعت پردازش را پـایین مـیآورد؛ بـه طـوري کـه از هدف اصلی خود که افزایش سرعت اسـت بـه کلـی دور خـواهیم شد. دومین راهکار استفاده از پردازنـده بـا حافظـه داخلـی بـالاتر است که قیمت خیلی بالاتري خواهد داشت.
هدف از این مقاله، کاهش حافظه مصـرفی، در پیـاده سـازي الگوریتم FFT در پردازنده مورد نظر میباشد. بـا کـاهش حافظـه
شانزدهمین کنفرانس دانشجویی مهندسی برق ایران دانشگاه آزاد اسلامی واحد کازرون، 12 -14 شهریور 1392
مصرفی در عین داشتن سرعت بـالاي پـردازش، قیمـت تمام شده سختافزار نیز کاهش مییابد.
براي این منظور در این مقاله دو کد براي پیـادهسـازي ایـن الگوریتم در محـیط MATLAB پیشـنهاد شـده اسـت. کـدهاي نوشته شده طوري هستند که کمترین میـزان حافظـه را اشـغال میکنند. دلیل این امر، پیادهسازي قسمت اصلی الگـوریتم FFT در یک خط از صفحه دستوري MATLAB است. کد ارائـه شـده دوم، بهینه شده کد اول میباشد که سرعت بـالاتري در پـردازش دارد.
در بخش 2، الگوریتم Radix-2 براي محاسبه FFT ارائه شده است. در این بخش نحوه کاهش پیچیدگی محاسبات در الگوریتم FFT نسبت به DFT شرح داده مـی شـود. در بخـش 3، کـدهاي پیشنهادي بیان شده و نتایج آن با دسـتور FFT موجـود درنـرم افزار MATLAB مقایسه شده است. در پایان نیز یک جمعبنـدي و نتیجهگیري از بخشهاي مذکور ارائه شده است.
