تبدیل فوریه گسسته — از صفر تا صد

۵۸۵۱ بازدید
آخرین به‌روزرسانی: ۱۶ اردیبهشت ۱۴۰۲
زمان مطالعه: ۲۶ دقیقه
تبدیل فوریه گسسته — از صفر تا صد

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

997696

مواقع و شرایط زیادی وجود دارد که نیاز داریم محتوای فرکانسی یک سیگنال حوزه زمان را مشخص کنیم. برای مثال، ممکن است بخواهیم طیف خروجی یک نوسان‌ساز LC را برای مشاهده مقدار نویز موجود در سیگنال سینوسی تولیدی تحلیل کنیم. این کار با استفاده از تبدیل فوریه گسسته (Discrete Fourier Transform) یا DFT میسر است. تبدیل فوریه گسسته، در کنار فیلتر‌سازی دیجیتال، یکی از دو ابزار قوی پردازش سیگنال دیجیتال است.

تبدیل فوریه گسسته چیست؟

سیگنال پیوسته x(t) x (t) را در نظر بگیرید که در شکل ۱ نشان داده شده است.

می‌خواهیم این سیگنال را تحلیل کنیم.

شکل ۱: یک سیگنال پیوسته که می‌خواهیم محتوای فرکانسی آن را به دست آوریم. 
شکل ۱: یک سیگنال پیوسته که می‌خواهیم محتوای فرکانسی آن را به دست آوریم.

بدیهی است که یک کامپیوتر دیجیتال نمی‌تواند با یک سیگنال پیوسته کار کند و لازم است که تعدادی نمونه از x(t) x (t) بگیریم و به جای سیگنال اصلی، این نمونه‌ها را تحلیل کنیم. علاوه بر این، علی‌رغم اینکه شکل ۱ تنها ۵ میلی‌ثانیه از سیگنال را نشان می‌دهد، ممکن است x(t) x(t) ساعت‌ها، سال‌ها یا بیشتر از آن ادامه داشته باشد. از آنجایی که کامپیوتر دیجیتال توانایی فقط تعداد محدودی از نمونه‌ها را دارد، باید از تقریب استفاده کرده و از تعداد محدودی نمونه بهره ببریم. بنابراین، عموماً، دنباله‌ای به طول محدود برای نمایش این سیگنال پیوسته آنالوگ به کار می‌رود که می‌تواند روی محور زمان به مثبت بی‌نهایت میل کند. از سیگنال x(t) x(t) شکل ۱ با نرخ نمونه‌برداری ۸۰۰۰ نمونه بر ثانیه، تعداد L=8L=8 نمونه می‌گیریم. نتیجه این نمونه‌برداری در شکل ۲ نشان داده شده است.

شکل ۲: با استفاده از نمونه‌برداری می‌توان سیگنال‌های پیوسته را در یک کامپیوتر دیجیتال تحلیل کرد.
شکل ۲: با استفاده از نمونه‌برداری می‌توان سیگنال‌های پیوسته را در یک کامپیوتر دیجیتال تحلیل کرد.

اگر محور زمان را به دوره نمونه‌برداری Ts=1fsT_s=\frac{1}{f_s} بهنجار (نرمالیزه) کنیم، دنباله گسسته x(n)x(n) را به دست خواهیم آورد که در جدول زیر ارائه شده است:‌

7766554433221100nn
0.8321-0.83211.2165-1.21650.5821-0.58210.21650.21650.58210.58210.78350.78350.83210.83210.21650.2165x(n)x(n)

تحلیل فوریه چندین ابزار ریاضی را برای تعیین محتوای فرکانسی یک سیگنال حوزه زمان ارائه می‌کند، اما کدام‌یک از این ابزارها برای تحلیل x(n) x (n) مناسب‌تر است؟ تنها دو روش از خانواده تحلیل فوریه وجود دارد که مختص سیگنال‌های گسسته‌اند: تبدیل فوریه زمان‌گسسته (Discrete-time Fourier Transform) یا DTFT و تبدیل فوریه گسسته (Discrete Fourier Transform) یا DFT.

تبدیل فوریه زمان‌گسسته (DTFT) دنباله ورودی x(n) x(n) به صورت زیر بیان می‌شود:

X(ejω)=n=+x(n)ejnω          (1) \large X ( e ^ { j \omega } ) = \sum _ { n = - \infty } ^ { + \infty } x ( n ) e ^ { - j n \omega } \; \; \; \; \; ( 1 )

معکوس DTFT نیز به شکل زیر است:

x(n)=12πππX(ejω)ejnωdω          (2) \large x ( n ) = \frac { 1 } { 2 \pi } \int _ { - \pi } ^ { \pi } X ( e ^ { j \omega } ) e ^ { j n \omega } d \omega \; \; \; \; \; ( 2 )

می‌توانیم از معادله (۱) برای یافتن طیف سیگنال x(n)x(n) استفاده کنیم که دامنه زمانی آن متناهی است. در معادله بالا، X(ejω)X(e^{j \omega}) تابعی پیوسته از ω \omega است. بنابراین، یک کمپیوتر دیجیتال نمی‌تواند مستقیماً از معادله (۱) برای تحلیل x(n) x (n) استفاده کند. البته می‌توانیم از نمونه‌های X(ejω)X(e^{j \omega}) برای یافتن تقریبی از طیف x(n) x(n) استفاده کنیم. ایده نمونه‌برداری X(ejω)X(e^{j \omega}) در نقاط فرکانسی با فاصله برابر، در واقع، اساس روش دوم فوریه، یعنی DFT است که در بالا به آن اشاره کردیم. توجه کنید که این نمونه‌برداری در حوزه فرکانس انجام می‌شود (X(ejω)X(e^{j \omega}) تابعی از فرکانس است).

ریاضیات تبدیل فوریه گسسته (DFT)

این بخش را با بررسی مثالی که در بخش قبل بیان کردیم معرفی می‌کنیم. دنباله‌ای به طول LL از سیگنال x(n) x(n) داریم که مربوط سیگنال پیوسته آنالوگ x(t)x(t) است. هدفی که به دنبال آن هستیم، یافتن مجموعه‌ای از سینوسی‌ها است که می‌توان آن‌ها را با هم جمع و x(n) x(n) را تولید کرد.

همان‌طور که در بخش قبلی گفتیم، DFT مبتنی بر نمونه‌برداری در نقاط فرکانسی با فواصل برابر از DTFT است که در رابطه (۱) داده شد.  X(ejω) X(e^{j \omega}) یک تابع دوره‌ای یا متناوب از ω \omega با دوره تناوب 2π2 \pi است. اگر در هر دوره X(ejω)X(e^{j \omega})، تعداد NN نمونه بگیریم، فاصله بین نقاط نمونه‌بردای  2πN \frac{ 2\pi }{N} خواهد بود. بنابراین، فرکانس مجموعه سینوسی‌هایی که به دنبال یافتن آن‌ها هستیم، به فرم 2πN×k\frac{2 \pi}{N} \times k خواهد بود که در آن، k=0,1,...,N1k=0, 1, ..., N-1. با استفاده از نمایی‌های مختلط مشابه با معادلات (۱) و (۲)، توابع پایه به صورت ej2πNkne^{j \frac{2 \pi}{N}kn} خواهند بود. می‌خواهیم یک مجموع وزن‌دار از این توابع را پیدا کنیم که سیگنال اصلی x(n)x(n) را نتیجه دهند. در نتیجه، خواهیم داشت:

x(n)=k=0N1X(k)ej2πNkn,      n=0,1,,L1          (3) \large x ( n ) = \sum _ { k = 0 } ^ { N - 1 } X' ( k ) e ^ { j \frac { 2 \pi } { N } k n }, \; \; \; n=0, 1, \dots, L-1 \; \; \; \; \; ( 3 )

که در آن، X(k)X'(k) وزن نمایی مختلط  ej2πNkn e^{j \frac{2 \pi}{N}kn} است. معادله (۳)، معادل با مجموعه معادلات زیر است:‌

x(0)=X(0)+X(1)+X(2)++X(N1)x(1)=X(0)+X(1)ej2πN+X(2)ej2πN2++X(N1)ej2πN(N1)x(2)=X(0)+X(1)ej2πN2+X(2)ej2πN2×2++X(N1)ej2πN(N1)×2                (4)x(L1)=X(0)+X(1)ej2πN(L1)+X(2)ej2πN2×(L1)++X(N1)ej2πN(N1)×(L1) \large x ( 0 ) = X' ( 0 ) + X' ( 1 ) + X' ( 2 ) + \dots + X' ( N - 1 ) \\ \large x ( 1 ) = X' ( 0 ) + X' ( 1 ) e ^ { j \frac { 2 \pi }{ N } } + X' ( 2 ) e ^ { j \frac { 2 \pi } { N } 2 } + \dots + X' ( N - 1 ) e ^ { j \frac { 2 \pi } { N } ( N - 1 ) } \\ \large x ( 2 ) = X' ( 0 ) + X' ( 1 ) e ^ { j \frac { 2 \pi }{ N } 2 } + X' ( 2 ) e ^ { j \frac { 2 \pi } { N } 2 \times 2 } + \dots + X' ( N - 1 ) e ^ { j \frac { 2 \pi } { N } ( N - 1 ) \times 2 } \; \; \; \; \; \; \; \; (4) \\ \large \vdots \\ \large x ( L - 1 ) = X' ( 0 ) + X' ( 1 ) e ^ { j \frac { 2 \pi } { N } ( L - 1 ) } + X' ( 2 ) e^ { j \frac { 2 \pi } { N } 2 \times ( L - 1 ) } + \dots + X' ( N - 1 ) e ^ { j \frac { 2 \pi } { N } ( N - 1 ) \times ( L - 1 ) }

برای یک LL و NN مشخص، مقادیر نمایی‌های مختلط معلوم بوده و با داشتن مقدار سیگنال حوزه زمان می‌توانیم ضرایب X(k)X'(k) را محاسبه کنیم. تعداد نمونه‌های حوزه زمان (LL)، تعداد معادلات را در مجموعه معادلات و تعداد نمونه‌های حوزه فرکانس X(ejω)X(e^{j\omega})، تعداد مجهولات معادله (۴) را مشخص می‌کند. با قرار دادن L=NL = N ، تعداد NN معادله مستقل خطی برای یافتن NN مجهولِ X(k)X'(k) خواهیم داشت.

با فرض L=N=8L=N=8، می‌توانیم فرم ماتریسی معادله (۴) را نوشته و با استفاده از متلب، مجهولات را به دست آوریم:

7766554433221100kk
0.5j0.5j0.1083+0.0625j0.1083+0.0625j0000000.10830.0625j0.1083-0.0625j0.5j-0.5j00X(k)X'(k)

اما تفسیر این تحلیل چیست؟‌ ما دنباله x(n) x (n) را به صورت مجموع نمایی‌های مختلط معادله (۳) نوشتیم. اکنون نتایج را در معادله مذکور جایگذاری می‌کنیم. با L=N=8L=N=8 و حذف نمایی‌هایی که ضریبشان صفر است، طبق جدول بالا می‌توان نوشت:

x(n)=X(1)ej2π8n+X(2)ej2π82n+X(6)ej2π86n+X(7)ej2π87n \large x ( n ) = X' ( 1 ) e ^ { j \frac { 2 \pi }{ 8 } n } + X' ( 2 ) e ^ { j \frac { 2 \pi } { 8 } 2 n } + X' ( 6 ) e ^ { j \frac { 2 \pi } { 8 } 6 n } + X' ( 7 ) e ^ { j \frac { 2 \pi } { 8 } 7 n }

از آنجایی که این توابع نمایی دوره‌ای با N=8N=8 هستند، می‌توانیم این معادله را ساده‌تر کنیم. برای مثال، ej2π87ne^{j\frac{2\pi}{8}7n} برابر با ej2π8(81)n=ej2π88nej2π8n=ej2π8ne^{j\frac{2\pi}{8}(8-1)n}=e^{j\frac{2\pi}{8}8n}e^{-j\frac{2\pi}{8}n}=e^{-j\frac{2\pi}{8}n} است. بعد از ساده‌سازی و بازآرایی جملات معادله بالا، خواهیم داشت:‌

x(n)=X(1)ej2π8n+X(7)ej2π8n+X(2)ej2π82n+X(6)ej2π82n \large x ( n ) = X' ( 1 ) e ^ { j \frac { 2 \pi } { 8 }n } + X' ( 7 ) e ^ {- j \frac { 2 \pi } { 8 } n } + X' ( 2 ) e ^ { j \frac { 2 \pi }{ 8 } 2 n } + X' ( 6 ) e ^ { - j \frac { 2 \pi } { 8 } 2 n }

در نهایت، رابطه زیر را به دست خواهیم آورد:

x(n)amp;=sin(2π8n)+0.125sin(4π8n)+0.2166cos(4π8n)amp;=sin(2π8n)+0.25sin(4π8n+3π3)          (5) \large \begin {align*} x ( n ) & = \sin ( \frac { 2 \pi } { 8} n ) + 0 . 1 2 5 \sin ( \frac { 4 \pi } { 8 } n ) + 0 . 2 1 6 6 \cos ( \frac { 4 \pi }{ 8 } n ) \\ &= \sin ( \frac { 2 \pi } { 8 } n) + 0 . 2 5 \sin ( \frac { 4 \pi }{ 8 } n+ 3 \frac { \pi } { 3 } ) \end {align*} \; \; \; \; \; (5)

رابطه بالا نشان می‌دهد که می‌توانیم x(n)x(n) را با دو مؤلفه نشان دهیم: یکی در فرکانس نرمالیزه 2π8\frac{2\pi}{8} با دامنه 11 و دیگری در 4π8\frac{4\pi}{8} با دامنه 0.250.25. این فرکانس‌ها نرمالیزه هستند؛ اگر فرکانس نمونه‌برداری fs=8000f_s=8000 نمونه بر ثانیه باشد، فرکانس این دو مؤلفه، به ترتیب، f1=2π8fs2π=1kHzf_1=\frac{2\pi}{8}\frac{f_s}{2\pi}=1 kHz و f2=4π8fs2π=2kHzf_2=\frac{4\pi}{8}\frac{f_s}{2\pi}=2 kHz خواهد بود.

اکنون خلاصه‌ای را از آنچه که گفتیم بیان می‌کنیم. ما با یک سیگنال زمان‌پیوسته شروع کردیم و از تعداد محدودی نمونه برای تحلیل محتوای فرکانسی این سیگنال پیوسته استفاده کردیم. دیدیم که مسئله تجزیه این دنباله گسسته به حل مجموعه‌ای از معادلات خطی می‌انجامد. در مثال ساده‌ای که بررسی کردیم، معادله (۵) را نیز ساده کرده و یک معادله صریح برای x(n) x (n) به دست آوردیم.

این، نکته‌ای است که باید توجه ویژه‌ای به آن داشته باشیم. تحلیل با دنباله‌ای به طول ۸ شروع می‌شود که در شکل ۳ نشان داده شده است. واضح است که مقدار x(n)x(n) را برای  n=0,,7 n=0, \dots, 7 می‌دانیم، اما اطلاعی از مقدار آن در خارج از این محدوده نداریم.

شکل ۳: شروع تحلیل، فقط با ۸ نمونه
شکل ۳: شروع تحلیل، فقط با ۸ نمونه

تحلیل بالا، در واقع، جست‌وجو برای مجموعی از نمایی‌های مختلط است که می‌توانند مقادیر x(n) x(n) را برای n=0,,7n=0, \dots, 7 بازتولید کنند. معادله (۵) را در خارج از این بازه آزمایش می‌کنیم. برای جلوگیری از ابهام، به دنباله p(n)p(n) بر می‌گردیم که در معادله (۵) داده شد. نمودار p(n)p(n) که یک تابع دوره‌ای با N=8 N=8 است، در شکل ۴ نشان داده شده است. همان‌طور که در این شکل می‌بینیم، مقادیر x(n) x (n) اصلی هر ۸ نمونه یک‌بار تکرار می‌شوند. به عبارت دیگر، وقتی بتوانیم x(n)x(n) را با استفاده از تعدادی نمایی مختلط نشان دهیم، نمایشِ به دست آمده متناوب بوده و x(n)x(n) فقط در یک دوره تناوب برابر با p(n)p(n) است.

شکل ۴: تحلیل منجر به <span class=p(n)p(n) می‌شود که فرم متناوب x(n)x(n) است." width="524" height="392">
شکل ۴: تحلیل منجر به p(n)p(n) می‌شود که فرم متناوب x(n)x(n) است.

توجه کنید که وقتی درباره تشکیل، تحلیل و اعمال DFT بحث می‌کنیم، منظورمان نمایشی از دنباله‌ای با طول متناهی با استفاده از یک دنباله متناوب است که در آن، مقادیرِ یک دوره تناوب از این دنباله دوره‌ای برابر با مقادیر آن دنباله متناهی هستند.

همچنین دقت داشته باشید که رفتار دوره‌ای p(n)p(n) را می‌توان با یادآوری این نکته درک کرد که در حال نمونه‌برداری از X(ejω)X(e^{j\omega}) در حوزه فرکانس (تبدیل فوریه زمان‌گسسته x(n)x(n)) هستیم. در واقع، نمونه‌برداری از  X(ejω) X(e^{j\omega}) در حوزه فرکانس، به نسخه برابر x(n) x (n) در حوزه زمان می‌انجامد. فرم تناوبی x(n) x(n) در شکل ۳ و p(n)p(n) در شکل ۴ نشان داده شد.

استخراج معادلات DFT

روش بالا را که برای محاسبه طیف یک دنباله با طول متناهی بیان کردیم، ساده و قابل درک است و مبیّن رفتار تناوبی ذاتی نمایش DFT است. با وجود این، می‌توانیم از مباحث بالا استفاده کرده و فرم بسته معادلات DFT را بدون نیاز به محاسبه معکوس یک ماتریس بزرگ به دست آوریم. برای این کار، تنها لازم است یک سیگنال تناوبی با NN نمونه از دنباله‌ای با طول متناهی بسازیم. پس از آن، با اعمال بسط سری فوریه زمان‌گسسته، می‌توانیم نمایش حوزه فرکانس سیگنال تناوبی را به دست آوریم. ضرایب سری فوریه به دست آمده، جز برای یک عامل مقایس‌بندی، مشابه ضرایب DFT هستند.

فرض کنید دنباله متناهی که می‌خواهیم آن را تحلیل کنیم در شکل ۵ (الف) نشان داده شده است. برای محاسبه تبدیل فوریه گسسته Nنقطه‌ای، لازم است از روی سیگنال x(n)x(n) با دوره تناوب NN، سیگنال P(n)P(n) را بسازیم (شکل ۵ (ب)).

شکل ۵: (الف) دنباله متناهی <span class=x(n)x(n) که می‌خواهیم آن را تحلیل کنیم. (ب) سیگنال متناوب به دست آمده از x(n)x(n)" width="449" height="523">
شکل ۵: (الف) دنباله متناهی x(n)x(n) که می‌خواهیم آن را تحلیل کنیم. (ب) سیگنال متناوب به دست آمده از x(n)x(n)

با توجه به رابطه p(n)=x(n)p(n)=x(n) به ازای n=0,1,,N1n=0, 1, \dots, N-1 سری فوریه زمان‌گسسته این سیگنال متناوب به صورت زیر است:

ak=1Nn=0N1x(n)ej2πNkn          (6) \large a _ k = \frac { 1 } { N } \sum _ { n = 0 } ^ { N - 1 } x ( n ) e ^ { - j \frac { 2 \pi } { N } k n } \; \; \; \; \; ( 6 )

که در آن، NN دوره تناوب سیگنال است. سیگنال حوزه زمان را می‌توان به صورت زیر به دست آورد:

x(n)=k=0N1akej2πNkn          (7) \large x ( n ) = \sum _ { k = 0 } ^ { N - 1 } a _ { k } e ^ { j \frac { 2 \pi } { N } k n } \; \; \; \; \; ( 7 )

با ضرب ضرایب معادله (۶) در NN، ضرایب تبدیل فوریه گسسته (X(n)X(n)) به دست می‌آید:

X(k)=n=0N1x(n)ej2πNkn          (8) \large X ( k ) = \sum _ { n = 0 } ^ { N - 1 } x ( n ) e ^ { -j \frac { 2 \pi } { N } k n } \; \; \; \; \; ( 8 )

تبدیل فوریه گسسته معکوس به صورت زیر خواهد بود:

x(n)=1Nk=0N1X(k)ej2πNkn          (9) \large x ( n ) = \frac { 1 } { N } \sum _ { k = 0 } ^ { N - 1 } X ( k ) e ^ { j \frac { 2 \pi } { N } k n } \; \; \; \; \; ( 9 )

توجه کنید که وقتی سری فوریه زمان‌گسسته یک سیگنال متناوب باشد، ضرایب DFT یک دنباله متناهی در 0kN10 \leq k \leq N-1 هستند.

مثال‌ها

در این بخش، دو مثال ساده را بررسی می‌کنیم.

مثال ۱

فرض کنید x0=1x_0=1، x1=x2==xN1=0x_1=x_2= \cdots = x_{N-1} = 0 . تبدیل فوریه گسسته xn x_n به صورت زیر است:

Xk=n=0N1xne2πikn/N=1. \large X _ k = \sum _ { n = 0 } ^ { N - 1 } x _ n e ^ { - 2 \pi i k n / N } = 1 .

بنابراین، xnx_n به صورت زیر خواهد بود:

xn=1Nk=0N1e2πikn/N. \large x _ n = \frac 1 { N } \sum _ { k = 0 } ^ { N - 1 } e ^ { 2 \pi i k n / N } .

توجه کنید که وقتی n=0n=0، x0=1NN=1 x _0 = \frac {1} {N} \cdot N = 1 و وقتی n0 n \neq 0، داریم:

xnamp;=1Nk=0N1(e2πin/N)kamp;=1N(e2πin/N)N1e2πin/N1amp;=1Ne2πin1e2πin/N1amp;=0. \large \begin {aligned} x _ n &amp; = \frac 1 { N } \sum _ { k = 0 } ^ { N - 1 } \big ( e ^ { 2 \pi in / N } \big ) ^ k \\\\ &amp; = \frac 1 { N } \frac { \big ( e ^ { 2 \pi in / N } \big ) ^ N - 1 } { e ^ { 2 \pi in / N } - 1 } \\\\ &amp; = \frac 1 { N } \frac { e ^ { 2 \pi i n } - 1 } { e ^ { 2 \pi in / N } - 1 } \\\\ &amp; = 0 . \end {aligned}

مثال ۲

تبدیل فوریه f(x0,x1,x2,x3)=(0,1,0,0) f ( x _ 0 , x _ 1 , x _ 2 , x _ 3 ) = ( 0 , 1 , 0 , 0 ) را به دست آورید.

حل: در این مثال، داریم:

Xk=n=03xne2πikn/4=e2πik/4. \large X _ k = \sum _ { n = 0 } ^ 3 x _ n e ^ { - 2 \pi i k n / 4 } = e ^ { - 2 \pi i k / 4 } .

بنابراین، می‌توان گفت: X0=1X_0=1، X1=iX_1=-i، X2=1X_2 = -1 و X3=iX_3 = i. در نتیجه، پاسخ (1,i,1,i)(1, -i , -1 , i ) است.

در نتیجه، xnx_n به صورت زیر خواهد بود:

xn=1ie2πin/4e4πin/4+ie6πin/4. \large x _ n = 1 - i e ^ { 2 \pi i n / 4 } - e ^ { 4 \pi i n / 4 } + i e ^ { 6 \pi i n / 4 } .

با تبدیل ضرایب مختلط به نمایی‌های مختلط، داریم:

xnamp;=1+e6πi/4e2πin/4+e4πi/4e4πin/4+e2πi/4e6πin/4amp;=1+e2πi(n+3)/4+e2πi(2n+2)/4+e2πi(3n+1)/4. \large \begin {aligned} x _ n &amp; = 1 + e ^ { 6 \pi i / 4 } e ^ { 2 \pi i n / 4 } + e ^ { 4 \pi i / 4 } e ^ { 4 \pi i n / 4 } + e ^ { 2 \pi i / 4 } e ^ { 6 \pi i n / 4 } \\ &amp; = 1 + e ^ { 2 \pi i ( n + 3 ) / 4 } + e ^ { 2 \pi i ( 2 n + 2 ) / 4 } + e ^ { 2 \pi i ( 3 n + 1 ) / 4 } . \end {aligned}

این مثال، موردی از جابه‌جایی فاز است که اتفاق می‌افتد. با در نظر گرفتن بخش‌های حقیقی هر دو سمت، مجموعی از موج‌های کسینوسی خواهیم داشت:

xn=1+cos(2πn/4+3π/2)+cos(4πn/4+π)+cos(6πn/4+π/2) \large x _ n = 1 + \cos ( 2 \pi n / 4 + 3 \pi / 2 ) + \cos ( 4 \pi n / 4 + \pi ) + \cos ( 6 \pi n / 4 + \pi / 2 )

که در آن، افزوده شدن 3π/23\pi/2، π\pi و π/2\pi/2 موجب جابه‌جایی شکل موج‌ها به ترتیب، به اندازه 270270^\circ، 180180^ \circ و 90 90 ^ \circ خواهد شد.

تعامد و تبدیل معکوس

چرا فرمول تبدیل معکوس درست است؟ XkX_k را در فرمول xn x _ n جایگذاری می‌کنیم:

k=0N1Xke2πikn/Namp;=1Nk=0N1m=0N1xme2πikm/Ne2πikn/Namp;=1Nk=0N1m=0N1xme2πik(mn)/Namp;=1Nm=0N1xmk=0N1e2πik(mn)/N. \large \begin {aligned} \sum _ { k = 0 } ^ { N - 1 } X _ k e ^ { - 2 \pi i k n / N } &amp; = \frac 1 { N } \sum _ { k = 0 } ^ { N - 1 } \sum _ { m = 0 } ^ { N - 1 } x _ m e ^ { 2 \pi i k m / N } e ^ { - 2 \pi i k n / N } \\ &amp; = \frac 1 { N } \sum _ { k= 0 } ^ { N - 1 } \sum _ { m = 0 } ^ { N - 1 } x _ m e ^ { 2 \pi i k ( m - n ) / N } \\ &amp; = \frac 1 { N } \sum _ { m = 0 } ^ { N - 1 } x _ m \sum _ { k = 0 } ^ { N - 1 } e ^ { 2 \pi i k ( m - n ) / N } . \end {aligned}

اگر mn m \neq n، مجموع داخلی طبق فرمول سری هندسی برابر با صفر است. وقتی m=n m = n، مجموع داخلی برابر با N N خواهد بود. بنابراین، مجموع کلی برابر است با 1NxnN=xn \frac {1}{N} \cdot x _ n \cdot N = x _ n .

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

vk=(1,ωNk,ωN2k,,ωNk(N1)), \large v _ k = \left ( 1 , \omega _ N ^ k , \omega _ N ^{ 2 k } , \ldots , \omega _ N ^ { k ( N - 1 ) } \right ) ,

که در آن‌ها، ωN=e2πi/N \omega _ N = e ^ {2 \pi i /N} است. با استدلالی مشابه آنچه در بالا گفتیم، این بردارهای مختلط نسبت به ضرب نقطه‌ای مختلط متعامد هستند: vkvl=N v _k \cdot v _ l = N اگر k=l k = l و در غیر این صورت، برابر با صفر است.

فرمول DFT برای Xk X_k به سادگی به صورت Xk=xvk X _ k = x \cdot v _ k بیان می‌شود، که در آن، xx بردار (x0,x1,,xN1) ( x _ 0, x _ 1, \cdots , x _ {N-1}) است. فرمول معکوس، x x را با نوشتن xx با استفاده از فرمول استاندارد برای بیان هر بردار به عنوان ترکیب خطی بردارهای پایه متعامد بر حسب XX بر می‌گرداند:

x=k=0N1xvkvkvkvk=1Nk=0N1Xkvk. \large x = \sum _ { k = 0 } ^ { N - 1 } \frac { x \cdot v _ k }{ v _ k \cdot v _ k } v _ k = \frac 1 { N } \sum _ { k = 0 } ^ { N - 1 } X _ k v _ k .

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

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

در حالت کلی می‌توان گفت که DFT تابعی است که برداری با nn عدد مختلط را به برداری با nn عدد مختلط دیگر می‌نگارد. با در نظر گرفتن مبداء 00، فرض می‌کنیم x(t) x (t) نشان دهنده ttاُمین درایه بردار ورودی و X(k) X(k) نشان دهنده kkاُمین درایه بردار خروجی باشد. تبدیل فوریه گسسته پایه با فرمول زیر بیان می‌شود:

X(k)=t=0n1x(t)e2πitk/n \large X ( k ) = \displaystyle \sum _ { t = 0 } ^ { n - 1 } x ( t ) e ^ { - 2 \pi i t k / n }

فرمول بالا مبیّن این موضوع است که بردار xx سطح یا اندازه سیگنال را در نقاط زمانی مختلف نشان می‌دهد و بردار XX مجموع اندازه را در فرکانس‌های مختلف به نمایش می‌گذارد. آنچه این فرمول می‌گوید، این است که اندازه سیگنال در فرکانس kk برابر است با مجموع اندازه‌های سیگنال در هر زمان tt ضرب در یک نمایی مختلط.

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

ساختار برنامه

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

1void dft(double[] inreal , double[] inimag,
2         double[] outreal, double[] outimag) {
3    // Assume all 4 arrays have the same length
4    int n = inreal.length;
5    // Incomplete: Method body
6}

در ادامه حلقه بیرونی را برای اختصاص دادن یک مقدار به هر درایه خروجی می‌نویسیم:

1void dft(double[] inreal , double[] inimag,
2         double[] outreal, double[] outimag) {
3    int n = inreal.length;
4    for (int k = 0; k < n; k++) {  // For each output element
5        outreal[k] = ?;  // Incomplete
6        outimag[k] = ?;  // Incomplete
7    }
8}

مجموع

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

j=abf(j)=f(a)+f(a+1)++f(b1)+f(b) \large \displaystyle \sum _ { j = a } ^ { b } f ( j ) = f ( a ) + f ( a + 1 ) + \cdots + f ( b - 1 ) + f ( b )

در حقیقت، در سری بالا مقادیر jj را یک به یک جایگذاری می‌کنیم. به سادگی کد سری بالا را می‌توان به صورت زیر نوشت:

1double sum = 0;
2for (int j = a; j <= b; j++) {
3    sum += f(j);
4}
5// The value of 'sum' now has the desired answer

ریاضیات عدد مختلط

جمغ دو عدد مختلط به سادگی انجام می‌شود:

(a+bi)+(c+di)=(a+c)+(b+d)i \large ( a + b i ) + ( c + d i ) = ( a + c ) + ( b +d ) i

ضرب دو عدد مختلط کمی سخت‌تر است؛ با استفاده از قانون توزیع و اتحاد i2=1 i ^ 2 = - 1 ، داریم:‌

(a+bi)(c+di)=ac+adi+bcibd=(acbd)+(ad+bc)i \large ( a + b i ) ( c + d i ) = a c + a d \, i + b c \, i - b d = ( a c - b d ) + ( a d + b c ) i

طبق رابطه اویلر، برای هر عدد حقیقی x x، می‌توان تساوی  exi=cosx+isinx e^{xi} = \cos x + i \sin x را نوشت. علاوه بر این، کسینوس یک تابع زوج بوده و رابطه  cos(x)=cosx \cos(-x) = \cos x برقرار است. همچنین، از آنجایی که سینوس یک تابع فرد است، می‌توان تساوی sin(x)=(sinx)\sin(-x) = -(\sin x) را نوشت. بنابراین، خواهیم داشت:

e2πitk/n=e(2πtk/n)iamp;=cos(2πtkn)+isin(2πtkn)amp;=cos(2πtkn)isin(2πtkn) \large \begin {align*} e ^ { - 2 \pi i t k / n } = e ^ { ( - 2 \pi t k / n ) i } &amp; = \cos \left ( - 2 \pi \frac { t k } { n } \right ) + i \sin \left ( -2 \pi \frac { t k } { n } \right ) \\ &amp;= \cos \left ( 2 \pi \frac { t k } { n } \right ) - i \sin \left ( 2 \pi \frac { t k } { n } \right ) \end {align*}

نماد Re(x)\text{Re}(x) را به عنوان بخش حقیقی xx و  Im(x) \text{Im}(x) را به عنوان بخش موهومی آن در نظر می‌گیریم. طبق تعریف، x=Re(x)+iIm(x)x = \text{Re}(x) + i \, \text{Im}(x) . بنابراین:

x(t)e2πitk/n=[Re(x(t))+iIm(x(t))][cos(2πtkn)isin(2πtkn)] \large x ( t ) \, e ^ { - 2 \pi i t k / n } = \left [ \text {Re} ( x ( t ) ) + i \, \text {Im} ( x ( t ) ) \right ] \left [ \cos \left ( 2 \pi \frac { t k } { n } \right ) - i \sin \left ( 2 \pi \frac { t k } { n } \right ) \right ]

با گسترش ضرب مختلط، داریم:

x(t)e2πitk/namp;=[Re(x(t))cos(2πtkn)+Im(x(t))sin(2πtkn)]amp;        +i[Re(x(t))sin(2πtkn)+Im(x(t))cos(2πtkn)] \large \begin {align*} x ( t ) \, e ^ { - 2 \pi i t k / n } &amp; = \left [ \text {Re} ( x ( t ) ) \cos \left ( 2 \pi \frac { t k } { n } \right ) + \text {Im}( x ( t ) ) \sin \left ( 2 \pi \frac { t k } { n } \right ) \right ] \\ &amp; \;\;\;\; + i \left [ -\text {Re} ( x ( t ) ) \sin \left ( 2 \pi \frac { t k } { n } \right ) + \text {Im} ( x ( t ) ) \cos \left ( 2 \pi \frac { t k } { n } \right ) \right ] \end {align*}

بنابراین، هر عبارت در مجموع کد زیر را برای بخش‌های حقیقی و موهومی خواهد داشت:

1double angle = 2 * Math.PI * t * k / n;
2double real =  inreal[t] * Math.cos(angle) + inimag[t] * Math.sin(angle);
3double imag = -inreal[t] * Math.sin(angle) + inimag[t] * Math.cos(angle);

ترکیب همه بخش‌ها با یکدیگر

اگر همه بخش‌ها را که گفتیم، با هم ترکیب کنیم، برنامه زیر را برای محاسبه سری فوریه گسسته خواهیم داشت:

1static void dft(double[] inreal , double[] inimag,
2                double[] outreal, double[] outimag) {
3    int n = inreal.length;
4    for (int k = 0; k < n; k++) {  // For each output element
5        double sumreal = 0;
6        double sumimag = 0;
7        for (int t = 0; t < n; t++) {  // For each input element
8            double angle = 2 * Math.PI * t * k / n;
9            sumreal +=  inreal[t] * Math.cos(angle) + inimag[t] * Math.sin(angle);
10            sumimag += -inreal[t] * Math.sin(angle) + inimag[t] * Math.cos(angle);
11        }
12        outreal[k] = sumreal;
13        outimag[k] = sumimag;
14    }
15}

در ادامه، کد DFT را برای چند زبان برنامه‌نویسی مختلف ارائه می‌کنیم. قبل از بررسی این کدها، نکات زیر را در نظر داشته باشید:

  • زبان‌های برنامه‌نویسی پایتون، سی، سی‌پلاس‌‌پلاس، سی‌شارپ، و متلب، اعداد مختلط را به صورت توکار دارند. این ویژگی کارمان را برای نوشتن برنامه DFT بسیار آسان‌تر می‌کند.
  • هریک از برنامه‌ها، نام‌گذاری قراردادی، سبک قالب‌بندی و اصطلاحات کدنویسی مربوط به خود را دارند و لزوماً شبیه آن چیزی نیستند که برای جاوا بیان کردیم.
  • تبدیل فوریه گسسته‌ای که در این بخش بیان کردیم، برای سادگی، شامل نرمالیزه‌ کردن/مقیاس‌بندی نیست. گزینه‌های متعددی برای چگونگی مقیاس‌بندی DFT وجود دارد. مثلاً‌ مقیاس‌بندی فقط تبدیل مستقیم با 1/n1/n، مقیاس‌بندی تبدیل‌های مستقیم و معکوس با 1/n1/\sqrt{n}، مقیاس‌بندی جداول مثلثاتی از پیش محاسبه شده و... .

برنامه تبدیل فوریه گسسته در جاوا

1/* 
2 * Discrete Fourier transform (Java)
3 * by Project Nayuki, 2017. Public domain.
4 * https://www.nayuki.io/page/how-to-implement-the-discrete-fourier-transform
5 */
6
7
8public final class Dft {
9	
10	/* 
11	 * Computes the discrete Fourier transform (DFT) of the given complex vector.
12	 * All the array arguments must be non-null and have the same length.
13	 */
14	public static void computeDft(double[] inreal, double[] inimag, double[] outreal, double[] outimag) {
15		int n = inreal.length;
16		for (int k = 0; k < n; k++) {  // For each output element
17			double sumreal = 0;
18			double sumimag = 0;
19			for (int t = 0; t < n; t++) {  // For each input element
20				double angle = 2 * Math.PI * t * k / n;
21				sumreal +=  inreal[t] * Math.cos(angle) + inimag[t] * Math.sin(angle);
22				sumimag += -inreal[t] * Math.sin(angle) + inimag[t] * Math.cos(angle);
23			}
24			outreal[k] = sumreal;
25			outimag[k] = sumimag;
26		}
27	}
28	
29}

برنامه تبدیل فوریه گسسته در C

1/* 
2 * Discrete Fourier transform (C)
3 * by Project Nayuki, 2017. Public domain.
4 * https://www.nayuki.io/page/how-to-implement-the-discrete-fourier-transform
5 */
6
7
8/* 
9 * Computes the discrete Fourier transform (DFT) of the given complex vector.
10 * All the array arguments must be non-NULL and have a length equal to n.
11 */
12#include <complex.h>
13#include <math.h>
14void compute_dft_complex(const double complex input[], double complex output[], int n) {
15	for (int k = 0; k < n; k++) {  // For each output element
16		complex double sum = 0.0;
17		for (int t = 0; t < n; t++) {  // For each input element
18			double angle = 2 * M_PI * t * k / n;
19			sum += input[t] * cexp(-angle * I);
20		}
21		output[k] = sum;
22	}
23}
24
25
26/* 
27 * (Alternate implementation using only real numbers.)
28 * Computes the discrete Fourier transform (DFT) of the given complex vector.
29 * All the array arguments must be non-NULL and have a length equal to n.
30 */
31#include <math.h>
32void compute_dft_real_pair(const double inreal[], const double inimag[],
33		double outreal[], double outimag[], int n) {
34	
35	for (int k = 0; k < n; k++) {  // For each output element
36		double sumreal = 0;
37		double sumimag = 0;
38		for (int t = 0; t < n; t++) {  // For each input element
39			double angle = 2 * M_PI * t * k / n;
40			sumreal +=  inreal[t] * cos(angle) + inimag[t] * sin(angle);
41			sumimag += -inreal[t] * sin(angle) + inimag[t] * cos(angle);
42		}
43		outreal[k] = sumreal;
44		outimag[k] = sumimag;
45	}
46}

برنامه تبدیل فوریه گسسته در C++‎

1/* 
2 * Discrete Fourier transform (C++)
3 * by Project Nayuki, 2017. Public domain.
4 * https://www.nayuki.io/page/how-to-implement-the-discrete-fourier-transform
5 */
6
7// Shared definitions
8#include <cmath>
9#include <vector>
10using std::size_t;
11using std::vector;
12
13
14/* 
15 * Computes the discrete Fourier transform (DFT) of the given complex vector.
16 * All the array arguments must have the same length.
17 */
18#include <complex>
19using std::complex;
20using std::exp;
21vector<complex<double> > computeDft(const vector<complex<double> > &input) {
22	vector<complex<double> > output;
23	size_t n = input.size();
24	for (size_t k = 0; k < n; k++) {  // For each output element
25		complex<double> sum(0.0, 0.0);
26		for (size_t t = 0; t < n; t++) {  // For each input element
27			double angle = 2 * M_PI * t * k / n;
28			sum += input[t] * exp(-angle);
29		}
30		output.push_back(sum);
31	}
32	return output;
33}
34
35
36/* 
37 * (Alternate implementation using only real numbers.)
38 * Computes the discrete Fourier transform (DFT) of the given complex vector.
39 * All the array arguments must have the same length.
40 */
41using std::cos;
42using std::sin;
43void computeDft(const vector<double> &inreal, const vector<double> &inimag,
44		vector<double> &outreal, vector<double> &outimag) {
45	
46	size_t n = inreal.size();
47	for (size_t k = 0; k < n; k++) {  // For each output element
48		double sumreal = 0;
49		double sumimag = 0;
50		for (size_t t = 0; t < n; t++) {  // For each input element
51			double angle = 2 * M_PI * t * k / n;
52			sumreal +=  inreal[t] * cos(angle) + inimag[t] * sin(angle);
53			sumimag += -inreal[t] * sin(angle) + inimag[t] * cos(angle);
54		}
55		outreal[k] = sumreal;
56		outimag[k] = sumimag;
57	}
58}

برنامه تبدیل فوریه گسسته در C#‎

1/* 
2 * Discrete Fourier transform (C#)
3 * by Project Nayuki, 2017. Public domain.
4 * https://www.nayuki.io/page/how-to-implement-the-discrete-fourier-transform
5 */
6
7using System;
8using System.Numerics;  // For Complex
9
10
11public sealed class Dft {
12	
13	/* 
14	 * Computes the discrete Fourier transform (DFT) of the given complex vector.
15	 */
16	public static Complex[] computeDft(Complex[] input) {
17		int n = input.Length;
18		Complex[] output = new Complex[n];
19		for (int k = 0; k < n; k++) {  // For each output element
20			Complex sum = 0;
21			for (int t = 0; t < n; t++) {  // For each input element
22				double angle = 2 * Math.PI * t * k / n;
23				sum += input[t] * Complex.Exp(new Complex(0, -angle));
24			}
25			output[k] = sum;
26		}
27		return output;
28	}
29	
30	
31	/* 
32	 * Computes the discrete Fourier transform (DFT) of the given complex vector.
33	 * All the array arguments must be non-null and have the same length.
34	 */
35	public static void computeDft(double[] inreal, double[] inimag, double[] outreal, double[] outimag) {
36		int n = inreal.Length;
37		for (int k = 0; k < n; k++) {  // For each output element
38			double sumreal = 0;
39			double sumimag = 0;
40			for (int t = 0; t < n; t++) {  // For each input element
41				double angle = 2 * Math.PI * t * k / n;
42				sumreal +=  inreal[t] * Math.Cos(angle) + inimag[t] * Math.Sin(angle);
43				sumimag += -inreal[t] * Math.Sin(angle) + inimag[t] * Math.Cos(angle);
44			}
45			outreal[k] = sumreal;
46			outimag[k] = sumimag;
47		}
48	}
49	
50}

برنامه تبدیل فوریه گسسته در JavaScript

1/* 
2 * Discrete Fourier transform (JavaScript)
3 * by Project Nayuki, 2018. Public domain.
4 * https://www.nayuki.io/page/how-to-implement-the-discrete-fourier-transform
5 */
6
7"use strict";
8
9
10/* 
11 * Computes the discrete Fourier transform (DFT) of the given complex vector.
12 * 'inreal' and 'inimag' are each an array of n floating-point numbers.
13 * Returns an array of two arrays - outreal and outimag, each of length n.
14 */
15function computeDft(inreal, inimag) {
16	var n = inreal.length;
17	var outreal = new Array(n);
18	var outimag = new Array(n);
19	for (var k = 0; k < n; k++) {  // For each output element
20		var sumreal = 0;
21		var sumimag = 0;
22		for (var t = 0; t < n; t++) {  // For each input element
23			var angle = 2 * Math.PI * t * k / n;
24			sumreal +=  inreal[t] * Math.cos(angle) + inimag[t] * Math.sin(angle);
25			sumimag += -inreal[t] * Math.sin(angle) + inimag[t] * Math.cos(angle);
26		}
27		outreal[k] = sumreal;
28		outimag[k] = sumimag;
29	}
30	return [outreal, outimag];
31}

برنامه تبدیل فوریه گسسته در TypeScript

1/* 
2 * Discrete Fourier transform (TypeScript)
3 * by Project Nayuki, 2018. Public domain.
4 * https://www.nayuki.io/page/how-to-implement-the-discrete-fourier-transform
5 */
6
7"use strict";
8
9
10/* 
11 * Computes the discrete Fourier transform (DFT) of the given complex vector.
12 * 'inreal' and 'inimag' are each an array of n floating-point numbers.
13 * Returns an array of two arrays - outreal and outimag, each of length n.
14 */
15function computeDft(inreal: Array<number>, inimag: Array<number>): [Array<number>,Array<number>] {
16	const n: number = inreal.length;
17	let outreal: Array<number> = new Array(n);
18	let outimag: Array<number> = new Array(n);
19	for (let k = 0; k < n; k++) {  // For each output element
20		let sumreal: number = 0;
21		let sumimag: number = 0;
22		for (let t = 0; t < n; t++) {  // For each input element
23			const angle: number = 2 * Math.PI * t * k / n;
24			sumreal +=  inreal[t] * Math.cos(angle) + inimag[t] * Math.sin(angle);
25			sumimag += -inreal[t] * Math.sin(angle) + inimag[t] * Math.cos(angle);
26		}
27		outreal[k] = sumreal;
28		outimag[k] = sumimag;
29	}
30	return [outreal, outimag];
31}

برنامه تبدیل فوریه گسسته در Python

1# 
2# Discrete Fourier transform (Python)
3# by Project Nayuki, 2017. Public domain.
4# https://www.nayuki.io/page/how-to-implement-the-discrete-fourier-transform
5# 
6
7
8# 
9# Computes the discrete Fourier transform (DFT) of the given complex vector.
10# 'input' is a sequence of numbers (integer, float, or complex).
11# Returns a list of complex numbers as output, having the same length.
12# 
13import cmath
14def compute_dft_complex(input):
15	n = len(input)
16	output = []
17	for k in range(n):  # For each output element
18		s = complex(0)
19		for t in range(n):  # For each input element
20			angle = 2j * cmath.pi * t * k / n
21			s += input[t] * cmath.exp(-angle)
22		output.append(s)
23	return output
24
25
26# 
27# (Alternate implementation using only real numbers.)
28# Computes the discrete Fourier transform (DFT) of the given complex vector.
29# 'inreal' and 'inimag' are each a sequence of n floating-point numbers.
30# Returns a tuple of two lists of floats - outreal and outimag, each of length n.
31# 
32import math
33def compute_dft_real_pair(inreal, inimag):
34	assert len(inreal) == len(inimag)
35	n = len(inreal)
36	outreal = []
37	outimag = []
38	for k in range(n):  # For each output element
39		sumreal = 0.0
40		sumimag = 0.0
41		for t in range(n):  # For each input element
42			angle = 2 * math.pi * t * k / n
43			sumreal +=  inreal[t] * math.cos(angle) + inimag[t] * math.sin(angle)
44			sumimag += -inreal[t] * math.sin(angle) + inimag[t] * math.cos(angle)
45		outreal.append(sumreal)
46		outimag.append(sumimag)
47	return (outreal, outimag)

برنامه تبدیل فوریه گسسته در Rust

1/* 
2 * Discrete Fourier transform (Rust)
3 * by Project Nayuki, 2017. Public domain.
4 * https://www.nayuki.io/page/how-to-implement-the-discrete-fourier-transform
5 */
6
7
8fn compute_dft(inreal: &[f64], inimag: &[f64], outreal: &mut [f64], outimag: &mut [f64]) {
9	let n: usize = inreal.len();
10	for k in 0 .. n {  // For each output element
11		let mut sumreal: f64 = 0.0;
12		let mut sumimag: f64 = 0.0;
13		for t in 0 .. n {  // For each input element
14			let angle: f64 = 2.0 * std::f64::consts::PI
15				* (t as f64) * (k as f64) / (n as f64);
16			sumreal +=  inreal[t] * angle.cos() + inimag[t] * angle.sin();
17			sumimag += -inreal[t] * angle.sin() + inimag[t] * angle.cos();
18		}
19		outreal[k] = sumreal;
20		outimag[k] = sumimag;
21	}
22}

برنامه تبدیل فوریه گسسته در MATLAB

1% 
2% Discrete Fourier transform (MATLAB)
3% by Project Nayuki, 2017. Public domain.
4% https://www.nayuki.io/page/how-to-implement-the-discrete-fourier-transform
5% 
6
7
8% 
9% Computes the discrete Fourier transform (DFT) of the given complex vector.
10% 'input' can be a row vector or a column vector. The returned output has the same dimensions.
11% 
12function output = compute_dft_scalarized(input)
13	assert(isvector(input));
14	n = numel(input);
15	output = NaN(size(input));
16	for k = 0 : n - 1  % For each output element
17		s = 0;
18		for t = 0 : n - 1  % For each input element
19			s = s + input(t + 1) * exp(-2i * pi * t * k / n);
20		end
21		output(k + 1) = s;
22	end
23end
24
25
26% 
27% (Alternate implementation using matrix arithmetic.)
28% Computes the discrete Fourier transform (DFT) of the given complex vector.
29% 'input' can be a row vector or a column vector. The returned output has the same dimensions.
30% 
31function output = compute_dft_vectorized(input)
32	assert(isvector(input));
33	n = numel(input);
34	matrix = exp(-2i * pi / n * (0 : n-1)' * (0 : n-1));
35	if size(input, 1) == 1  % Row vector
36		output = input * matrix;
37	elseif size(input, 2) == 1  % Column vector
38		output = matrix * input;
39	end
40end

جمع‌بندی

  • تبدیل فوریه گسسته یکی از قوی‌ترین ابزارهای پردازش سیگنال دیجیتال است که به ما این امکان را می‌دهد طیف سیگنال متناهی x(n) x(n) را پیدا کنیم.
  • اساساً، محاسبه DFT معادل با حل مجموعه‌ای از معادلات خطی است.
  • تبدیل فوریه گسسته با استفاده از یک دنباله متناوب نمایشی از یک دنباله متناهی در اختیار ما قرار می‌دهد. یک دوره تناوب دنباله متناوب مشابه با دنباله متناهی است. در نتیجه، می‌توانیم از سری فوریه زمان‌گسسته برای استخراج معادلات DFT استفاده کنیم.

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

^^

بر اساس رای ۹ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
All About CircuitsProject NayukiBrilliant
۶ دیدگاه برای «تبدیل فوریه گسسته — از صفر تا صد»

با سلام
بسیار عالی
فقط یک باید بگم در ابتدای بحث، تعداد نمونه برداری شما 1600 نقطه بر ثانیه است یعنی 1600 هرتز است. که اشتباها تایپ شده 8000 هرتز.
زیرا کل شکل 1، 5 میلی ثانیه است و 8 نمونه گرفته شده
8 تقسیم بر 5 میلی ثانیه میشه.. 1600 هرتز

پریود تابع آنالوگ 1 میلی ثانیه هست که با نرخ نمونه برداری 8000 مورد بر ثانیه، زمان بین دو نمونه متوالی 1/8000 ثانیه خواهد بود که اگر 8 نمونه را لحاظ کنیم، به یک سیکل کامل میرسیم.

با سلام؛
متن بازبینی شد و صحیح است.
با تشکر از همراهی شما با مجله فرادرس

چقدر روان مثال زدید و توضیح دادید… یکی از مباحث مهم در پردازش سیگنال نحوه پیاده سازی تبدیل فوریه هست که به ساده ترین شکل اون رو انجام دادید. سپاسگزارم

سلام.
خوشحالیم که این آموزش برایتان مفید بوده است.
شاد و پیروز باشید.

سلام
روز بخیر
عااالی بود کاملا متوجه شدم.
ممنون

نظر شما چیست؟

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