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

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

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

پیاده سازیِ بهینۀ تبدیلِ فوریۀ گسسته (از نظر تعداد عملیات ریاضی لازم برای محاسبه تبدیل)، تبدیلِ فوریۀ سریع (Fast Fourier Transform - FFT) نام دارد. مهم‌ترین کاربرد FFT، در پردازش سیگنال است.

البته تبدیل فوریه گسسته در بررسی الگوریتم‌ها برای ضرب سریع چندجمله‌ایها نیز استفاده می‌شود.

تعاریف و ویژگی‌های کلی

تعریف

${\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {2\pi i}{N}}kn}\quad \quad k=0,\dots ,N-1}$

ویژگی‌ها

کامل بودن

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

تعامد

بردارهای ${\displaystyle e^{{\frac {2\pi i}{N}}kn}}$ دو به دو برهم عمود هستند، یعنی:

${\displaystyle \sum _{n=0}^{N-1}\left(e^{{\frac {2\pi i}{N}}kn}\right)\left(e^{-{\frac {2\pi i}{N}}k'n}\right)=N~\delta _{kk'}}$

که ${\displaystyle ~\delta _{kk'}}$ تابع دلتای کرونکر می‌باشد.

کاربرد در ضرب چندجمله‌ای‌ها

علاوه بر این کاربردها، در بررسی الگوریتم‌ها، برای ضرب چند جمله‌ای‌ها نیز از تبدیل فوریه سریع استفاده می‌شود. در این روش ابتدا چندجمله‌ای را به فرم دیگری تبدیل می‌کنیم که انجام عملیات ضرب و تقسیم بر روی این فرم نمایش می‌تواند سریع انجام شود. پس از انجام عملیات، با تبدیل عکس فوریه (${\displaystyle DFT^{-1}}$) می‌توان پاسخ را در قالب چندجمله‌ای بدست آورد. در ادامه به بررسی دقیق این الگوریتم می‌پردازیم.

فرم‌های نمایش توابع

برای نمایش توابع راه‌های گوناگونی وجود دارد، به طور مثال می‌توان یک تابع را با مجموعه اعضا (برای توابع با دامنهٔ محدود)، ضابطهٔ کلی تابع، یک سری مانند بسط تیلور یا بسط فوریه و… نمایش داد. یک فرم که در انجام محاسبات بسیار کاراست، را در این جا توضیح می‌دهیم. می‌دانیم که در صفحه می‌توان هرچند جمله‌ای از درجه n را با دقیقاً n+1 نقطه از آن به طور یکتا مشخص کرد. مثلاً هر خط راست را می‌توان با دو نقطه از آن به طور یکتا مشخص کرد و برعکس؛ یا این که هر سه نقطه یک سهمی را به طور یکتا تعیین می‌کنند. پس یک روش نمایش چندجمله‌ای‌های درجه n، نگهداری n+1 نقطهٔ آن است. دقت کنید که این نقاط به دلخواه از دامنهٔ تابع انتخاب می‌شوند. به طور دقیق تر:

${\displaystyle FFT\left(P_{n}\right)=\left\{\left(x_{i},P_{n}\left(x_{i}\right)\right)|x_{i}\in \mathbb {C} ,\forall i\neq j:x_{i}\neq x_{j}\right\}}$

برای مثال نمایش‌های زیر هم ارزند:

${\displaystyle x^{2}-3x+4\equiv \left\{\left(0,4\right),\left(1,2\right),\left({\sqrt {2}},6-3{\sqrt {2}}\right)\right\}\equiv \left\{\left(0,4\right),\left(2,2\right),\left(-1,8\right)\right\}}$

نکته‌ای مهم در این نمایش این است که لازم نیست که مختصات نقاط حقیقی باشند و می‌توان مقدار تابع را در نقاطی مختلط محاسبه کرد و به عنوان نمایش آن تابع دانست. از این موضوع در الگوریتم تبدیل سریع فوریه به خوبی استفاده می‌کنیم.
لازم است ذکر شود که اگر یک چندجمله‌ای درجه n را در بیش از تعداد لازم نقطه مقدار یابی کنیم، به آن فرم فوریهٔ گسترش یافته می‌گویند. مثلاً این که سه نقطهٔ هم خط هم یک چندجمله‌ای درجه یک را مشخص می‌کنند، هر چند که یک نقطهٔ آن اضافی است. در نتیجه می‌توان هر چندجمله‌ای در فرم فوریه را با یافتن آن در تعدادی نقاط اضافی، به فرم گسترش یافته تبدیل کرد. این کار نیز در ضرب چند جمله‌ای‌ها لازم است، زیرا اگر دو چندجمله‌ای درجه n را در فرم فوریه داشته باشیم برای بدست آوردن حاصل ضرب آن دو نیاز به تعداد بیش تری نقطه از هر یک داریم.

تبدیل فرم‌ها

تا این جا دو فرم مهم برای نمایش چندجمله‌ای‌ها ارائه دادیم: فرم فوریه و فرم ضابطه‌ای. حال می‌خواهیم به تبدیل بین این دو فرم بپردازیم. این تبدیل اساس کار الگوریتم‌های محاسباتی پیش رو خواهد بود. به تبدیل از فرم ضابطه‌ای به فرم فوریه، مقدار یابی می‌گویند و به عکس این عمل یعنی تبدیل از فرم فوریه به فرم چندجمله‌ای درون یابی گفته می‌شود.
یک الگوریتم برای تبدیل فرم ضابطه‌ای به فرم فوریه، این است که ابتدا n+1 مقدار دلخواه ${\displaystyle \left\{x_{1},..,x_{n}\right\}}$ را انتخاب کنیم و سپس مقدار چند جمله‌ای را در این نقاط محاسبه کنیم (مثلاً با الگوریتم هورنر) که زوج مرتب‌های بدست آمده یک فرم فوریه برای چندجمله‌ای خواهند بود. این الگوریتم از ${\displaystyle \Theta \left(n^{2}\right)}$ است. در ادامه نشان می‌دهیم که می‌توان برای هر چندجمله‌ای، فرم فوریه آن را در زمان ${\displaystyle \Theta \left(n\cdot lg\left(n\right)\right)}$ بدست آورد که به این الگوریتم تبدیل سریع (گسسته ی) فوریه می‌گویند.
برای انجام عکس این عمل، یعنی درون یابی یا (${\displaystyle DFT^{-1}}$) نیز الگوریتم سریعی وجود دارد.

محاسبات روی فرم فوریه

نکتهٔ جالب در مورد فرم فوریه برای نمایش چند جمله‌ای‌ها، سادگی انجام برخی محاسبات روی آن است. به طور مثال اگر بخواهیم دو چندجمله‌ای را جمع/ضرب کنیم، کافی است آن دو را با یک سری مقادیر x یکسان به فرم فوریه تبدیل کنیم و سپس مقادیر متناظر هر نقطه از آن دو تابع را با هم جمع/ضرب کنیم. دیده می‌شود که در این فرم اعمالی مانند ضرب یا تقسیم بسیار آسان تر از صورت ضابطه‌ای قابل انجام اند. در حقیقت جمع و تفریق و ضرب و تقسیم چندجمله‌های به این فرم با ${\displaystyle \Theta \left(n\right)}$ امکان‌پذیر است. در ادامه به بررسی جزئیات پیاده‌سازی ضرب چندجمله‌ای‌ها می‌پردازیم.

مسئلهٔ ضرب چندجمله‌ای

در این مسئله می‌خواهیم دو چندجمله‌ای از درجه‌های ${\displaystyle m}$ و ${\displaystyle n}$ که به فرم ضابطه‌ای با ضرایب هر توانی از ${\displaystyle x}$ آن‌ها مشخص شده‌اند را در هم ضرب کنیم و ضابطهٔ چندجمله‌ای حاصل را بدست آوریم.
حال با توجه به بحث پیش، می‌توان دید که اگر دو چندجمله‌ای داشته باشیم می‌توان ابتدا آن‌ها را در تعدادی نقطهٔ مشترک مقدار یابی کرد و پس از آن فرم فوریهٔ ضرب آن‌ها را از ضرب مولفه‌های دوم زوج مرتب‌های بدست آمده پیدا کرد. باید توجه کرد که حاصل ضرب، یعنی ${\displaystyle P\cdot Q}$ دارای درجه‌ای برابر ${\displaystyle m+n}$ است پس باید برای نمایش آن به تعداد ${\displaystyle m+n+1}$ زوج مرتب از آن را داشته باشیم، به همین منظور می‌توان از ابتدا هر دو چندجمله‌ای را به فرم فوریهٔ گسترش یافته با ${\displaystyle m+n+1}$ نقطه تبدیل کرد، و سپس این نقاط را نظیر به نظیر ضرب کرد و حاصل ضرب را در فرم فوریه بدست آورد. برای یافتن جواب کافی است آن را از فرم فوریه به فرم ضابطه‌ای تبدیل کنیم. پس دوباره با دو مسئله‌ای که به آن‌ها اشاره کردیم روبرو شدیم: تبدیل فرم‌های ضابطه‌ای و فوریه. کافی است به بررسی پیاده‌سازی سریع این دو مسئله بپردازیم.

تبدیل سریع فرم‌ها

برای این که بتوانیم از روی فرم ضابطه‌ای چندجمله‌ای، n نقطه از نمودار را بدست آوریم، به گونه‌ای هوشمندانه طوری آن ${\displaystyle n}$ نقطه را انتخاب می‌کنیم که نوعی وابستگی به هم داشته باشند و در نتیجه بتوانیم در کل محاسبات مربوط به پیدا کردن مقدار تابع در آن ${\displaystyle n}$ نقطه را به خاطر همان وابستگی سریع تر انجام دهیم، زیرا عملاً برخی از محاسبات تکراری می‌شوند. در ادامه به بیان دقیق تر الگوریتم را بیان می‌کنیم.

بخش یک: تبدیل مستقیم یا DFT

فرض می‌کنیم که چندجمله‌ای داده شده ${\displaystyle A\left(x\right)}$ باشد. تبدیل فوریهٔ ${\displaystyle n}$ ام ${\displaystyle A}$ را ماتریس مقدارهای این چندجمله‌ای در ریشه‌های ${\displaystyle n}$ ام واحد تعریف کرده و با ${\displaystyle Y}$ نشان می‌دهیم:

${\displaystyle DFT_{n}^{-1}\left(Y\right):a_{j}={\frac {1}{n}}\sum _{k=0}^{n-1}{y_{k}\cdot w^{-kj}}}$

به طور بدیهی می‌توان این ماتریس را در زمان ${\displaystyle n^{2}}$ محاسبه کرد زیرا محاسبهٔ آن شامل ${\displaystyle n}$ بار محاسبهٔ مقدار چندجمله‌ای است که هر بار آن با روشی مانند الگوریتم هورنر به میزان ${\displaystyle \Theta \left(n\right)}$ زمان نیاز دارد. برای بهبود این روش می‌توان الگوریتم بازگشتی با زمان ${\displaystyle n\cdot lg\left(n\right)}$ ارائه کرد. فرض کنید می‌خواهیم مقدار ماتریس تبدیل فوریه را بیابیم. اگر تعریف کنیم:

${\displaystyle A^{\left[0\right]}=a_{0}+a_{2}\cdot x+a_{4}\cdot x^{2}+...+a_{n-2}\cdot x^{{\frac {n}{2}}-1}}$
${\displaystyle A^{\left[1\right]}=a_{1}+a_{3}\cdot x+a_{5}\cdot x^{2}+...+a_{n-1}\cdot x^{{\frac {n}{2}}-1}}$

خواهیم داشت:

${\displaystyle A=A^{\left[0\right]}\left(x^{2}\right)+x\cdot A^{\left[1\right]}\left(x^{2}\right)}$

ولی اگر n زوج باشد، مربعات ریشهٔ ${\displaystyle n}$ ام واحد، ریشه‌های ${\displaystyle {\frac {n}{2}}}$ ام واحد هستند. زیرا که:

${\displaystyle \left(w_{n}^{k+{\frac {n}{2}}}\right)^{2}=w_{n}^{2k+n}=w_{n}^{2k}\cdot w_{n}^{n}=w_{n}^{2k}=\left(w_{n}^{k}\right)^{2}}$

پس توانستیم مسئله را به دو زیر مسئله تقسیم کنیم، زیرا اکنون کافی است که ماتریس تبدیل فوریهٔ ${\displaystyle A^{i}}$ها را که از اندازهٔ ${\displaystyle {\frac {n}{2}}}$ هستند، در نقاط با مختص اول ریشه‌های ${\displaystyle {\frac {n}{2}}}$ ام واحد پیدا کنیم که همان مسئلهٔ ابتدایی است. پس از دو بازگشت، کافی است با رابطهٔ داده شده جواب‌ها را با هم ادغام کنیم تا جواب اصلی مسئله حاصل شود. الگوریتم کلی به روش بازگشتی در زیر آمده است:

DFT(a)

n = length[A] //must be a power of 2 if (n==1) return A wn = exp(2ᴨi/n) w = 1 a0 = (a0, a2,... , an-2) a1 = (a1, a3,... , an-1) y0 = FFT(a0) y1 = FFT(a1) for (k=0 to n/2-1) do

yk = yk0 + w.yk1 yk+n/2 = yk0 - w.yk1 w = w.wn

 return y

برای تحلیل زمانی این الگوریتم می‌توان به راحتی رابطهٔ بازگشتی زیر را پیشنهاد داد:

${\displaystyle T\left(n\right)=2T\left({\frac {n}{2}}\right)+\Theta \left(n\right)}$

که با یکی از روش‌های حل معادله بازگشتی مانند قضیهٔ اساسی می‌توان دید که:

${\displaystyle T\left(n\right)=\Theta \left(n\cdot lg\left(n\right)\right)}$

بخس دو: تبدیل معکوس یا iDFT

اکنون به بررسی فرایند معکوس یعنی نوعی از درون یابی می‌پردازیم. در این مسئله ماتریس Y را داریم و می‌خواهیم که ${\displaystyle A}$ را بیابیم. توجه می‌کنیم که می‌توان تبدیل فوریه را به شکل ماتریسی زیر هم نوشت:

${\displaystyle Y=V_{n}\cdot A}$

که در آن V ماتریس وندرموند است که با رابطهٔ زیر تعریف می‌شود:

${\displaystyle V_{i,j}={w_{n}}^{ij}}$

پس یک معادلهٔ ماتریسی برای تبدیل فوریه یافتیم. حال اگر حدس طرفین معادله را در وارون ماتریس وندرموند ضرب کنیم می‌توانیم A را بر حسب Y بیان کرد؛ ولی به راحتی می‌توان دید که برای وارون ماتریس وندرموند داریم:

${\displaystyle V_{n}^{-1}\left(i,j\right)={\frac {w_{n}^{-i\cdot j}}{n}}}$

زیرا که ضرب آن در خود ماتریس وندرموند ماتریس همانی می‌شود:

${\displaystyle \left(V_{n}^{-1}\cdot V_{n}\right)_{j{j}'}=\sum _{k=0}^{n-1}{\left(w_{n}^{-{\frac {kj}{n}}}\right)\cdot \left(w_{n}^{k{j}'}\right)}=\sum _{k=0}^{n-1}{w_{n}^{\frac {k\cdot \left(j-{j}'\right)}{n}}}}$

نکتهٔ جالب تشابه بسیار زیاد ماتریس وندرموند و وارون آن است، تا جایی که می‌توان از همان الگوریتم تبدیل فوریهٔ مستقیم برای وارون تبدیل فوریه نیز استفاده کنیم با این تغییرات که در آن الگوریتم، نقش A و Y را جابجا کنیم، ${\displaystyle w_{n}}$ را به ${\displaystyle {w_{n}}^{-1}}$ تبدیل کنیم و تک تک درایه‌ های نتیجهٔ حاصل را در آخر کار بر ${\displaystyle n}$ تقسیم کنیم.

نکات پیاده‌سازی

با وجود آسان بودن بیان الگوریتم بازگشتی بالا، پیاده‌سازی آن سختی‌های خاص خود را دارد. ۱) اولین مشکل این است که باید در هر مرحله از بازگشت، n عددی زوج باشد، که یعنی n آغازین باید توانی از دو باشد که شاید مسئلهٔ اصلی این شرط را برآورده نکند. برای حل این مشکل، متداول‌ترین راه چندجمله‌ای اولیه است، به این معنی که آن را یک چندجمله‌ای با درجه‌ای بیش از n فرض کرد، مثلاً m که m کوچک‌ترین توان دوی بزرگ‌تر از n باشد، و سپس ضرایب بزرگ‌تر از n آن را صفر گذاشت. این کار به ظاهر مشکل را حل می‌کند و در اکثر کاربردها نیز همین گونه است ولی در برخی موارد مانند پردازش سیگنال، این روش به خاطر ماهیت الگوریتم فوریه که شامل محاسبات مختلط است، دچار خطا شده و حتی در جواب پایانی سیگنال‌هایی با فرکانس بالای اضافه پدید می‌آیند. روش حل این مشکل فراتر از سطح این بحث است و نادیده گرفته می‌شود. ۲) علاوه بر این مشکل، سختی خود پیاده‌سازی الگوریتم گفته شده به صورتی کاراست. زیرا در هر مرحله باید آرایه را به دو بخش جدید تقسیم کنیم که نیاز به حافظهٔ اضافی دارد. یک روش این است که پیش از فراخوانی بازگشتی مسئله برای اندازهٔ نصف، به جای ایجاد دو آرایهٔ جدید، عناصر آرایهٔ اولیه را جابجا کنیم و عناصر با اندیس زوج را به نیمهٔ اول آرایه و عناصر با اندیس فرد را به نیمهٔ دوم آرایه انتقال دهیم و پس از اتمام بازگشت نیز دوباره ترتیب قبلی را بازیابی کنیم. همچنین خود بازگشتی بودن الگوریتم کمی سربار اضافی دارد که می‌توان سعی کرد که آن را به فرم غیر بازگشتی پیاده‌سازی کرد. با اعمال این دو تغییر به پیاده‌سازی کاراتری خواهیم رسید که در بخش بعد به توضیح آن می‌پردازیم. ۳) مشکل بنیادی تری که الگوریتم تبدیل سریع فوریه دارد این است که حتی زمانی که چند جمله‌ای اولیه دارای ضرایب صحیح باشد، نیاز به محاسبات مختلط پیش می‌آید. با این که این گونه محاسبات در رایانه‌های پیشرفتهٔ امروزی به راحتی و با سرعت قابل قبولی انجام پذیر است، ولی مشکلی که وجود دارد این است که شاید در طی این محاسبات مختلط، بخشی از دقت محاسبه کم شود. به بیان دقیق تر این الگوریتم از لحاظ محاسباتی پایداری کمی دارد و خطای اولیه به شدت تشدید می‌شود. این مشکل برای حالتی که ضرایب صحیح باشند با استفاده از حساب پیمانه‌ای به جای حساب مختلط قابل حل است ولی بیش از این به جزئیات آن نمی‌پردازیم.

روش‌های پیاده‌سازی سریع

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

حال اگر بتوانیم از همان ابتدا آرایه را به صورت بالا بچینیم می‌توانیم به راحتی بدون انجام بازگشت به تدریج بخش‌های مجاور را با هم ادغام کنیم و به سمت بالا برویم. یعنی عملاً به جای رویکرد بالا به بایین از روش بایین به بالا بهره بردیم که باعث سادگی بیاده سازی و کارایی بیش تر آن می‌شود. الگوریتم انجام این کار را نیز آورده‌ایم. لازم به توضیح است که آن بخشی از الگوریتم که جدا نوشته شده و با نام Bit-Reverse-Copy نام گذاری شده در ابتدا آرایه را به ترتیبی که گفتیم بازچینی می‌کند. این الگوریتم منحصر به این مبحث نیست و در بسیاری از تابع‌های بازگشتی مورد استفاده قرار می‌گیرد.

//Rearranges a and stores the result in A
Bit-Reverese-Copy(a, A)


n = length[a]
for (k=0 to n-1) do

A[reverse-bits(k)] = a_k

//Computues the DFT of a without recursion
Iterative-DFT(a)

Bit-Reverse-Copy(a, A)
n = length[a]
for (s=1 to lg n) do

m = 2^s
w_m = exp(2πi/m)
for (k=0 to n-1) by m do

w=1
for (j=0 to m/2 - 1) do

t = wA[k + j + m/2]
u = A[k + j]
A[k + j] = u + t
A[k + j + m/2] = u - t
w = w.w_n

موازی سازی الگوریتم

مشاهده می‌شود که در پیاده‌سازی فوق بخش‌های مختلف از آرایه تا حد زیادی از هم مستقل هستند. به این معنی که مراحل اولیهٔ ادغام بخش‌های مختلف آرایه می‌توانند مستقل از هم انجام شوند. به این ترتیب اگر ما بیش از یک پردازنده داشته باشیم به راحتی می‌توان بهترین استفاده از این موضوع را برد و مراحل اولیه را بین پردازنده‌ها تقسیم کنیم. در پایان نیز می‌توان عمل ادغام نهایی کار پردازنده‌ها را مشابها با یک پردازنده انجام داد و به جواب رسید.
در الگوریتم DFT که در بالا آمده بخش اصلی پردازش مربوط به سه خط درونی حلقهٔ برنامه است. در حقیقت کل محاسبات توسط این خطوط انجام می‌شود. حال اگر به این فرایند یک عملیات پروانه‌ای بگوییم می‌توان گفت که کل تبدیل فوریه بر اساس عملیات‌های پروانه‌ای انجام می‌شود. می‌توان الگوریتم فوریه را بر اساس شبکه‌های موازی الگوریتم پیاده‌سازی کرد. به طور خلاصه در این نظریه فرض می‌شود که تعداد زیادی پردازنده داریم (متناسب با n) که هر کدام تنها می‌توانند عمل خاصی را انجام دهند مانند مقایسه یا… حال شبکه‌ای طراحی می‌شود که داده‌ها با عبور از آن و پردازش شدن در حین عبور در انتهای شبکه فرم دلخواه را بگیرند (و به جواب برسیم). در این شبکه‌ها معیار زمان اجرا عمق شبکه است. با استفاده از این نظریه در حالتی که n پردازنده داشته باشیم (که هر یک بتوانند عملیات پروانه‌ای روی دو یا چند ورودی خود انجام دهند) می‌توان با شبکه‌ای با عمق lg n تبدیل فوریه را محاسبه کرد. ایدهٔ کلی بسیار ساده است به این صورت که در درخت بازگشت که یک مثال آن در بالا رسم شده است راس‌های برگ را ورودی فرض کنیم و به جای هر راس غیر برگ یک پردازنده قرار دهیم.

جستارهای وابسته

• تبدیل سریع فوریه
• چندجمله‌ای
• ضرب چندجمله‌ای
• الگوریتم
• الگوریتم موازی

منابع

• Cormen, Thomas H. (2001). "Chapter 30: Polynomials and the FFT". مقدمه‌ای بر الگوریتم‌ها (Second ed.). MIT Press and McGraw-Hill. pp. 822–848. ISBN 0-262-03293-7. esp. section 30.2: The DFT and FFT, pp. 830–838.
• Multiplication using the FFT
• How the FFT works

• جبر خطّی عددی (انگلیسی)
• مقدمه‌ای بر ریاضیات کاربردی (انگلیسی)

• Strang, Gilbert (۱۹ ژوئیه ۲۰۰۵), Linear Algebra and Its Applications (4th ed.), Brooks Cole, ISBN 978-0-03-010567-8