الگوریتم FFT

پروژه: پیاده‌سازی الگوریتم FFT

شاید بتوان الگوریتم FFT را مهمترین الگوریتم ۱۰۰ سال اخیر در حوزه پردازش سیگنال دیجیتال دانست. الگوریتم FFT در بسیاری از سیستم‌های پردازش سیگنال کاربرد دارد و بنابراین، پیاده‌سازی بهینه آن، مساله مهمی در ساخت این نوع سیستم‌ها است. در این مقاله، در مورد این الگوریتم و نحوه پیاده‌سازی آن در FPGA صحبت خواهم کردم و ایده‌هایی را برای پیاده‌سازی ارائه خواهم کرد.

 

FFT چیست؟

الگوریتم FFT که مخفف عبارت Fast Fourier Transform است، یک روتین بسیار مناسب و بهینه برای پیاده‌سازی تبدیل DFT یا Discrete Fourier Transform است. اما در این لحظه ممکن است سوال کنید که DFT چیست؟

بر مبنای سری فوریه، می‌توان نشان داد که هر سیگنال پریودیک را می‌توان به صورت مجموع سیگنال‌های سینوسی و کسینوسی بیان کرد. به هر کدام از این سیگنال‌های سینوسی، یک مؤلفه گفته می‌شود. هر مؤلفه، یک فرکانس و دامنه دارد. بنابراین، اگر برای یک سیگنال یا موج در حوزه زمان، سری فوریه آن را محاسبه کنیم، می‌توان مؤلفه‌های آن را در نمودار دیگری که محور افقی آن فرکانس مؤلفه‌ها و محور عمودی آن، دامنه مؤلفه‌ها هستند نمایش داد. این نمایش را، نمایش حوزه فرکانس سیگنال می‌گویند.

مثلا فرض کنید سیگنال (x(t در حوزه زمان، دارای سری فوریه‌ زیر باشد:

(f(t) = a1 sin(w1t) + a2 cos(w2t) + a3 sin(w3t

یعنی این سیگنال دارای سه مؤلفه با فرکانس‌های w،w2 و w3 و دامنه‌های a1 ،a2 و a3 است. نمایش حوزه فرکانس سیگنال (x(t در شکل زیر نشان داده شده است.

 

سری فوریه

 

حال فرض کنید با یک سیگنال نمونه‌برداری شده (مثلا توسط یک مبدل آنالوگ به دیجیتال یا ADC) سروکار داریم. مثلا سیگنال (x(t در مثال فوق را با فرکانس Fs نمونه‌برداری کرده‌ایم. همچنین فرض کنید تعداد محدود و مشخصی از این نمونه‌ها را در اختیار داریم؛ مثلا تعداد N نمونه از سیگنال (x(t را با فرکانس Fs نمونه‌برداری کرده‌ایم.

الگوریتم DFT، الگوریتمی است که تعداد مشخصی از نمونه‌های گسسته یک سیگنال در حوزه زمان را که با فرکانس Fs نمونه‌برداری شده‌اند به عنوان ورودی دریافت می‌کند و در خروجی، ضرایب سری فوریه آن را محاسبه می‌کند. به عبارت دیگر، الگوریتم DFT، یک تابع گسسته را از حوزه زمان به حوزه فرکانس منتقل می‌کند. تعداد نمونه‌های در حوزه زمان ورودی (N) در این الگوریتم، با تعداد نمونه‌های حوزه فرکانس خروجی برابر است. مثلا در مورد مثال فوق، خروجی این الگوریتم برابر با دامنه‌های مؤلفه‌های سری فوریه، یعنی a،aو a3 خواهد بود. اگر تعداد ورودی‌های یک تبدیل DFT برابر با N باشد، به آن DFTی Nنقطه‌ای گفته می‌شود.

فاصله فرکانسی مؤلفه‌های محاسبه شده در خروجی DFT، برابر با Fs/N است. یعنی مثلا اگر از یک سیگنال در حوزه زمان با فرکانس نمونه‌برداری ۱۰۰MHz، تعداد ۱۰۰۰ نمونه توسط ADC تهیه شود و به الگوریتم DFT به عنوان ورودی اعمال شود، در خروجی این الگوریتم، ۱۰۰۰ نمونه در حوزه فرکانس خواهیم داشت که هر کدام از نمونه‌ها به اندازه ۱۰۰MHz/1000 = 100KHz با یکدیگر فاصله خواهند داشت. بنابراین، اولین خروجی DFT، مؤلفه فرکانس صفر است. دومین خروجی، مؤلفه فرکانس ۱۰۰KHz است. سومین مؤلفه خروجی DFT مربوط به فرکانس ۲۰۰KHz است و آخرین مؤلفه مربوط به فرکانس ۹۹۹۰۰KHz است.

شکل زیر، یک سیگنال فرضی در حوزه زمان را که با فرکانس ۱۰۰kHz نمونه‌برداری شده است به همراه تبدیل DFTی ۴نقطه‌ای آن که در حقیقت نمایش سیگنال در حوزه فرکانس است نشان می‌دهد. چون تعداد نقطه‌های DFT چهار عدد است و فرکانس نمونه‌برداری ۱۰۰kHz است، پس فاصله فرکانسی بین هر دو مؤلفه برابر با ۲۵kHz است.

 

تبدیل DFT

 

به این نکته هم توجه کنید که ورودی‌ها و خروجی‌های الگوریتم DFT، مختلط هستند. یعنی هر ورودی که یک نمونه در حوزه زمان است، به صورت x(n) = a + jb است و خروجی معادل آن هم به صورت F(n) = w + jz است. حال اگر شما سیگنالی نمونه‌برداری شده دارید که فقط شامل بخش‌های حقیقی است، می‌توانید مقدار بخش‌های موهومی را در ورودی DFT برابر با صفر قرار دهید. در هر حال، خروجی این تبدیل، هم شامل بخش حقیقی و هم شامل بخش موهومی خواهد بود. بنابراین، برای دستیابی به مؤلفه مورد نظر، باید مقدار دامنه خروجی مختلط، یعنی (sqrt(w^2 + z^2 را محاسبه کنید.

الگوریتم FFT، یک الگوریتم بهینه برای محاسبه سریع‌تر تبدیل DFT است. خروجی الگوریتم FFT همان مؤلفه‌های خروجی الگوریتم DFT است. اما الگوریتم FFT این کار را بسیار سریع‌تر انجام می‌دهد و شاید مهمتر از آن، دارای پیاده‌سازی بسیار ساده‌تری است.

 

الگوریتم FFT

رایج‌ترین الگوریتم پیاده‌سازی FFT در حال حاضر، الگوریتم Cooley–Tukey است. در این مقاله، قصد ندارم در مورد جزئیات این الگوریتم و محاسبات آن صحبت کنم و همچون مقالات قبلی، بیشتر در زمینه مباحث مربوط به پیاده‌سازی توضیح خواهد دادم.

برای اینکه با ساختار الگوریتم FFT برای پیاده‌سازی آشنا شوید، اجازه دهید یک FFTی چهار نقطه‌ای را با هم بررسی کنیم. در بخش بعدی، در مورد پیاده‌سازی این FFTی چهار نقطه‌ای ایده‌هایی به شما خواهم داد تا بتوانید به سرعت، پیاده‌سازی آن را شروع کنید. در بخش بعدی، توضیح خواهم داد که برای FFTهای بزرگ، بهتر است از IP Core یا ماجول‌های از پیش آماده شده استفاده کرد.

ساختار الگوریتم Cooley–Tukey ایجاب می‌کند که تعداد نمونه‌های FFT توانی از دو باشند. بنابراین، به کمک این الگوریتم می‌توان FFTهای ۴نقطه‌ای، ۸نقطه‌ای، …، ۱۰۲۴نقطه‌ای و … را پیاده‌سازی کرد. هسته اصلی در محاسبات الگوریتم FFT، بلوکی است به نام Butterfly که در شکل زیر نشان داده شده است. بلوک Butterfly در حقیقت یک FFTی دونقطه‌ای است که با اتصال مناسب تعدادی از آنها به یکدیگر می‌توان یک FFTی بزرگتر ایجاد کرد.

 

بلوک Butterfly

 

در بلوک Butterfly نشان داده شده در شکل بالا، (x(0 و (x(1 ورودی‌های مختلط و (F(0 و (F(1 خروجی‌های مختلط هستند. یک راه برای نمایش این ورودی‌ها و خروجی‌های مختلط، روش زیر است:

x(0) = x0_r + jx0_i

x(1) = x1_r + jx1_i

F(0) = F0_r + jF0_i

F(1) = F1_r + jF1_i

 

در شکل Butterfly روی بعضی از خط‌ها یک مقدار نوشته شده است که به این معنی است که ورودی باید در آن مقدار ضرب شود. در جاهایی که دو خط به یکدیگر رسیده‌اند، باید مقدار آن دو خط با یکدیگر جمع شوند. بنابراین، مقدار خروجی‌های Butterfly را می‌توان به صورت زیر نوشت:

(F(0) = x(0) + W20 x(1

(F(1) = x(0) – W20 x(1

 

ضریب W در این بلوک، خود دارای فرمول کلی e^(-j2πn/N) = WNn است که در آن e^jx = cos x + j sin x است. در نتیجه ۱ = W20 است.

یک FFTی ۴نقطه‌ای از چهار بلوک Butterfly تشکیل شده است. شکل زیر، این FFT را نشان می‌دهد. همانطور که در شکل دیده می‌شود، در طبقه اول، دو بلوک Butterfly وجود دارد که خروجی آنها به نحو خاصی به دو Butterfly دیگر در طبقه دوم متصل شده است. همچنین دقت کنید که ورودی‌ها به ترتیب نرمال به بلوک‌های Butterfly متصل نشده‌اند. روش اتصال آنها را اصطلاحا بیت-معکوس یا bit-reverse می‌گویند.

 

ساختار FFT چهارنقطه‌ای

 

در این مثال، سه ضریب W وجود دارد که با استفاده از فرمول فوق، مقدار آنها برابر خواهد بود با: ۱ = W20 = W40 و j = W41_.

 

ایده‌هایی برای پیاده‌سازی فیلتر دیجیتال

پیاده‌سازی الگوریتم FFT خصوصا برای تعداد نقاط زیاد، کاری پیچیده و طولانی محسوب می‌شود و حتی در یک روند پیاده‌سازی حرفه‌ای نیز بهتر است از آن اجتناب شود. به همین دلیل، معمولا برای پیاده‌سازی FFT از IP Coreها که همان ماجول‌های از پیش‌آماده شده هستند استفاده می‌شود.

خوشبختانه در نرم‌افزار ISE، یک IP Core بسیار عالی برای پیاده‌سازی انواع FFT با تعداد نقاط مختلف و ساختارهای پیاده‌سازی متنوع وجود دارد که پیشنهاد می‌کنم در صورت نیاز به استفاده از این الگوریتم در پروژه‌تان، از این IP Core استفاده کنید.

برای آشنایی با IP Coreها در نرم‌افزار ISE و نحوه بکارگیری آنها، این برنامه ویدئویی را ببینید…

اما در ادامه این مقاله و با هدف تمرین پیاده‌سازی و آشنایی با چند نکته مهم در پیاده‌سازی الگوریتم‌های با مقادیر مختلط، ایده‌هایی را برای پیاده‌سازی FFTی ۴نقطه‌ای ارائه خواهم داد. این پیاده‌سازی، یکی از تمرین‌های هفتگی دوره طراحی دیجیتال با FPGA در آموزشگاه فراد اندیش است و پیشنهاد می‌کنم شما هم حتما آن را پیاده‌سازی و تست کنید تا به کمک آن بتوانید مهارتتان را در پیاده‌سازی الگوریتم‌های پردازشی افزایش دهید.

مثل همیشه اجازه دهید ابتدا به سراغ تعیین ورودی‌ها و خروجی‌ها برویم. با توجه به اینکه می‌خواهیم یک FFTی ۴نقطه‌ای را پیاده‌سازی کنیم، نیاز به چهار ورودی و چهار خروجی خواهیم داشت. اما نکته‌ای که در این پروژه وجود دارد این است که ورودی‌ها و خروجی‌های FFT به صورت اعداد مختلط هستند و چیزی به نام پورت مختلط در زبان VHDL وجود ندارد.

برای آشنایی با زبان VHDL، این برنامه ویدئویی را ببینید…

برای تعریف پورت‌هایی که مربوط به اعداد مختلط می‌شوند باید به ازای هر ورودی یا خروجی، دو پورت تعریف کرد. یک پورت برای دریافت مقدار حقیقی و یک پورت برای دریافت مقدار موهومی. بنابراین، در این پروژه باید هشت پورت به عنوان ورودی و هشت پورت به عنوان خروجی تعریف کنیم. عرض بیت این پورت‌ها بستگی به مشخصات پروژه شما دارد. در این تمرین، من عرض بیت‌ها را هشت در نظر گرفته‌ام.

شکل زیر، ماجول FFTی ۴نقطه‌ای مختلط را برای پیاده‌سازی در FPGA نشان می‌دهد. برای پیاده‌سازی این FFT می‌توانید از یکی از دو ایده زیر پیروی کنید:

  • نوشتن کد توصیف سخت‌افزاری این FFT به صورت یک ماجول؛
  • نوشتن ماجول Butterfly و سپس اتصال چهار نمونه از ماجول Butterfly در یک ماجول دیگر.

همچنین در پیاده‌سازی به هر کدام از دو روش فوق، می‌توانید از تکنیک پایپ‌لاین برای افزایش سرعت کلاک قابل اعمال به ماجول استفاده کنید.

 

ماجول FFT چهار نقطه‌ای

 

در پیاده‌سازی بسیاری از الگوریتم‌ها از جمله الگوریتم این پروژه، بهتر است ابتدا و قبل از شروع پیاده‌سازی، بخشی از محاسبات را روی کاغذ انجام دهید و سپس عبارات محاسباتی ساده شده را پیاده‌سازی کنید. اجازه دهید ابتدا یک بلوک Butterfly را پیاده‌سازی کنیم.

ارتباط بین ورودی‌ها و خروجی‌های بلوک Butterfly به صورت تعریف می‌شود:

(F(0) = x(0) + W20 x(1

(F(1) = x(0) – W20 x(1

اگر به جای (F(nها، (x(nها و WNnها مقدار مختلط آنها را از روابطی که بالاتر به آنها اشاره کردم قرار دهیم، عبارات زیر به دست خواهند آمد:

(F(0) = (x0_r + x1_r) + j(x0_i + x1_i

(F(1) = (x0_r – x1_r) + j(x0_i – x1_i

و چون خود (F(nها مختلط هستند داریم:

F(0) = F0_r + jF0_i

F(1) = F1_r + jF1_i

در نتیجه داریم:

F0_r = x0_r + x1_r

F0_i = x0_i + x1_i

F1_r = x0_r – x1_r

F1_i = x0_i – x1_i

 

بنابراین، چهار خروجی بلوک Butterfly را می‌توان از طریق روابط فوق محاسبه کرد.

همانطور که پیش‌تر هم اشاره کردم، در این مرحله می‌توانید دو ایده را در نظر بگیرید. ایده اول این است که به کمک چهار بلوک Butterfly که در بالا طراحی کردیم و اتصال مناسب آنها به یکدیگر در ماجول اصلی (ماجول FFTی ۴نقطه‌ای) طراحی را کامل کنیم.

ایده دوم هم این است که کل محاسبات مربوط به FFTی ۴نقطه‌ای را مشابه کاری که برای بلوک Butterfly انجام دادیم، کامل کنیم و FFT را در یک ماجول پیاده‌سازی کنیم. پیشنهاد می‌کنم شما هر دو روش را انجام دهید و نتیجه را با یکدیگر مقایسه کنید.

در انجام این پروژه در نظر داشته باشید که نیاز به هیچ عمل ضربی ندارید. چون مقادیر WNnها در این تمرین خاص، برابر با ۱، ۱- یا j- است و برای هیچکدام از این موارد نیاز نیست که از عملگر ضرب استفاده شود. همانطور که می‌دانید، اگر عدد مختلطی در j- ضرب شود، فقط جای مقدار حقیقی با موهومی عوض می‌شود و مقدار حقیقی حاصل هم تغییر علامت می‌دهد.

 

قدم بعدی برای پیاده‌سازی الگوریتم FFT

با توجه به اینکه در عمل، FFTی ۴نقطه‌ای کاربردی ندارد و پیاده‌سازی FFTهای بزرگ‌تر هم معمولا به کمک IP Coreها انجام می‌شود، پیشنهاد می‌کنم یک ماجول FFTی ۱۲۸نقطه‌ای را به کمک IP Core موجود در نرم‌افزار ISE پیاده‌سازی کنید.

برای آشنایی با نرم‌افزار ISE این برنامه ویدئویی را ببینید…

بعد از انتخاب IP Core، باید تنظیمات مختلفی را برای IP انجام دهید. مثلا تعداد نقاط FFT و عرض بیت‌ها را مشخص کنید. تنظمیات دیگری هم وجود دارند که می‌توانید با مطالعه Datasheet این IP که در نرم‌افزار موجود است، آنها را به نحو مناسب انجام دهید.

به زودی کارگاهی را در زمینه پیاده‌سازی الگوریتم‌های پردازش سیگنال با FPGA برگزار خواهم کردم که در آن به اصول و روش‌های پیاده‌سازی انواع الگوریتم‌های پردازش سیگنال به کمک FPGA خواهم پرداخت. به کمک اطلاعاتی که از این کارگاه به دست خواهید آورد، می‌توانید دانش و مهارت خودتان را در بکارگیری FPGAها برای طراحی مدارات دیجیتال، یک گام به جلو ببرید و قابلیت خودتان را در انجام پروژه‌های حرفه‌ای و بزرگ به نحو چشمگیری افزایش دهید.

 

چطور از صحت پیاده‌سازی خودمان مطمئن شویم؟

بعد از پیاده‌سازی FFTی ۴نقطه‌ای، می‌توانید به کمک تست‌بنچ آن را شبیه‌سازی کنید. برای اینکه بتوانید خروجی‌های ماجول خودتان را با یک مقدار درست مقایسه کنید، بهتر است از نرم‌افزار MATLAB استقاده کنید. چهار مقدار مختلط دلخواه را به عنوان ورودی انتخاب کنید و توسط تابع fft در نرم‌افزار MATLAB مقدار آن را محاسبه کنید. برای این کار می‌توانید در نرم‌افزار MATLAB بنویسید:

[x = [7+i 5-4i 3+23i 9-2i

(fft(x

جوابی که در نرم‌افزار مشاهده خواهید کرد به صورت زیر خواهد بود:

۲۴+۱۸i 2-18i -4+30i 6-26i

 

حال می‌توانید در تست‌بنچ، مقادیر ورودی را به پورت‌های ورودی مدار اعمال کنید و شبیه‌سازی را انجام دهید. در نرم‌افزار شبیه‌ساز ISim باید همان خروجی‌های محاسبه شده در نرم‌افزار MATLAB را مشاهده کنید.

برای آشنایی با نرم‌افزار ISim و شبیه‌سازی رفتاری به کمک آن، این برنامه ویدئویی را ببینید…

 

اگر سوالی در زمینه پیاده‌سازی الگوریتم FFT دارید، یا روش‌های دیگری برای پیاده‌سازی و شبیه‌سازی آن دارید، لطفا همین جا و در پایین همین مقاله، آنها را با من و دیگر علاقمندان به اشتراک بگذارید.

 

8 پاسخ
  1. محمد
    محمد says:

    با تشکر مقاله جالبی بود
    با عرض معزت این مقاله طبق تفکرات و دانسته های خودتان بوده و زیاد روان نبوده, بهتر می بود که به صورت ویدو منتشر می کردین و کسی اگه می خواهد خوب درک کنه کتاب سیگنال گسسته در زمان اوپنهایم را مطالعه کند و منظورم از روان نبودن بار علمی اش نیست بلکه افرادی که در زمینه dft مطالعه نداشته اند را گیج می کند
    اگه میشه توضیحاتی هم درباره IP CORE بدهید من خودم تحقیقاتی در این زمینه کردم و شرکت های جالبی مثل synopsys و… را بررسی کردم و market جهانی این حوزه جالب بود آیا آماری از بازار ایران وجود دارد که کسی هم به فکر ایجاد شرکتی در زمینه ip core تو ایران باشه

    پاسخ دادن
    • احمد ثقفی
      احمد ثقفی says:

      سلام، ممنون از شما.

      بله همانطور که شما هم اشاره کردید، اگر کسی فقط این مقاله را بخواند نمی‌تواند درک کاملی از FFT داشته باشد، اما هدف این مقاله هم آموزش مفهوم FFT یا DFT نیست.

      هدف اصلی مقالات مجموعه “پروژه هفته” معرفی موضوعات مهم در زمینه پیاده‌سازی با FPGA است. موضوعاتی که در بازار کار این رشته در حال حاضر مهم هستند. این معرفی برای افرادی انجام می‌شود که تمایل به انجام تمرین بیشتر در زمینه پیاده‌سازی دارند. در واقع به درخواست بسیاری از اعضای سایت و افرادی که در دوره طراحی دیجیتال با FPGA شرکت کرده‌اند، این بخش را راه‌اندازی کردیم.

      سعی من بیشتر این بوده است که ضمن آشنا نمودن خوانندگان با این موضوعات، راهنمایی‌هایی هم در زمینه پیاده‌سازی ارائه دهم. با این حال، همانطور که شما هم اشاره کردید، افرادی که قصد دارند به طور جدی هر کدام از موارد مطرح شده در مقالات را دنبال کنند، باید خودشان به منابع مفصل‌تر مراجعه کنند و به صورت عمیق‌تری موضوع را مطالعه کنند.

      امیدوارم مطالب دیگر سایت برای شما مفید باشند.

      پاسخ دادن
  2. محمدقاسمی
    محمدقاسمی says:

    با سلام و تشکر از اموزشهای عالیتون
    خواستم در مورد تبدیل موجک یا wave let transformer هم در صورت امکان بحث بشه و پیاده سازی اون در fpga.

    پاسخ دادن
  3. امین
    امین says:

    سلام استاد
    با تشکر از شما خواستم بگم مطالبتون مفید هست و امیدوارم که ادامه دهنده این راه باشین.

    اگر امکانش هست در مورد DDS IP core صحبت کنید و پروژه هفته رو اگر میشه بذارین ساخت سیگنال chirp یا LFM با fpga

    اگر هم گروه یا کانال تلگرامی دارید ممنون میشم منو Add کنید. شماره ۰۹۱۷۱۳۳۸۱۴۱
    باز هم مرسی

    پاسخ دادن

دیدگاه خود را ثبت کنید

خوشحال خواهم شد نظرتان را در مورد این پست بدانم.
ایمیل شما برای دیگران قابل مشاهده نخواهد بود.

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *