تور لحظه آخری
امروز : جمعه ، 24 اسفند 1403    احادیث و روایات:  پیامبر اکرم (ص):خداوند! زبان را عذابى دهد كه هيچ يك از اعضاى ديگر را چنان عذابى ندهد. زبان گويد...
سرگرمی سبک زندگی سینما و تلویزیون فرهنگ و هنر پزشکی و سلامت اجتماع و خانواده تصویری دین و اندیشه ورزش اقتصادی سیاسی حوادث علم و فناوری سایتهای دانلود گوناگون شرکت ها

تبلیغات

تبلیغات متنی

خرید پرینتر سه بعدی

سایبان ماشین

اجاره سند در شیراز

armanekasbokar

armanetejarat

Future Innovate Tech

آموزشگاه آرایشگری مردانه شفیع رسالت

پی جو مشاغل برتر شیراز

خرید یخچال خارجی

بانک کتاب

طراحی سایت تهران سایت

irspeedy

درج اگهی ویژه

تعمیرات مک بوک

قیمت فرش

خرید بلیط هواپیما

بلیط اتوبوس پایانه

خرید از چین

خرید از چین

خرید سرور اچ پی ماهان شبکه

خودارزیابی چیست

رزرو هتل خارجی

تولید کننده تخت زیبایی

سی پی کالاف

دوره باریستا فنی حرفه ای

چاکرا

استند تسلیت

کلینیک دندانپزشکی سعادت آباد

پی ال سی زیمنس

دکتر علی پرند فوق تخصص جراحی پلاستیک

تعمیر سرووموتور

تحصیل پزشکی در چین

مجله سلامت و پزشکی

تریلی چادری

خرید یوسی

مهاجرت به استرالیا

ایونا

تعمیرگاه هیوندای

کاشت ابرو با خواب طبیعی

هدایای تبلیغاتی

خرید عسل

صندوق سهامی

تزریق ژل

خرید زعفران مرغوب

تحصیل آنلاین آمریکا

سوالات آیین نامه

سمپاشی سوسک فاضلاب

مبل کلاسیک

بهترین دکتر پروتز سینه در تهران

صندلی گیمینگ

کفش ایمنی و کار

دفترچه تبلیغاتی

خرید سی پی

قالیشویی کرج

سررسید 1404

تقویم رومیزی 1404

ویزای توریستی ژاپن

قالیشویی اسلامشهر

قفسه فروشگاهی

چراغ خطی

ابزارهای هوش مصنوعی

آموزش مکالمه عربی

اینتیتر

استابلایزر

خرید لباس

7 little words daily answers

7 little words daily answers

7 little words daily answers

گوشی موبایل اقساطی

ماساژور تفنگی

قیمت ساندویچ پانل

مجوز آژانس مسافرتی

پنجره دوجداره

خرید رنگ نمای ساختمان

ناب مووی

خرید عطر

قرص اسلیم پلاس

nyt mini crossword answers

مشاوره تبلیغاتی رایگان

دانلود فیلم

 






آمار وبسایت

 تعداد کل بازدیدها : 1865099062




هواشناسی

نرخ طلا سکه و  ارز

قیمت خودرو

فال حافظ

تعبیر خواب

فال انبیاء

متن قرآن



اضافه به علاقمنديها ارسال اين مطلب به دوستان آرشيو تمام مطالب
archive  refresh

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


واضح آرشیو وب فارسی:فان پاتوق: مهم.ترین کاربرد FFT، یا تبدیل سریع فوریه، در پردازش سیگنال است. که در آن، سیگنال به صورت تابعی از زمان به شدت سیگنال است. همان طور که می توان (برخی از) توابع را به صورت بسط تیلور از توابع چندجمله ای نوشت، می توان توابع متناوب را به خوبی بر حسب تابع.های سینوسی با فاز اولیه و ضریب دلخواه نوشت. حال تبدیل شکل سیگنال به سری فوریه با روش.های تبدیل سریع فوریه انجام می شود. به وسیله تبدیل گسسته فوریه (Discrete Fourier transform - DFT) می.توان توابع و سیگنال.های گسسته را از حوزهٔ زمان به حوزهٔ فرکانس (و یا از حوزهٔ مکان به حوزهٔ عدد موج) تبدیل کرد.
البته نوعی دیگر از این تبدیل، که با نام تبدیل گسستهٔ فوریه شناخته می.شود در بررسی الگوریتم.ها برای ضرب سریع چندجمله ای ها و بردازش رایانه ای سیکنال.ها استفاده می شود. در این بحث به این سری از کاربردهای تبدیل سریع فوریه می بردازیم.

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

تعریف




ویژگی.ها

کامل بودن

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

بردارهای

دو به دو بر هم عمود هستند، یعنی:



که

تابع دلتای کرونکر می.باشد.


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

علاوه بر این کاربرد، در بررسی الگوریتم ها، برای ضرب چند جمله ای.ها از نوعی از تبدیل فوریه با نام خاص تر تبدیل سریع فوریهٔ گسسته (Discrete Fourior Transform یا DFT) استفاده می شود. در این روش ابتدا چندجمله ای را به فرم دیگری تبدیل می کنیم که انجام عملیات ضرب و تقسیم بر روی این فرم نمایش می تواند سریع انجام شود. پس از انجام عملیات، با تبدیل عکس فوریه (DFT − 1) می توان پاسخ را در قالب چندجمله ای بدست آورد. در ادامه به برسی دقیق این الگوریتم می پردازیم.
فرم.های نمایش توابع

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





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






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

تا این جا دو فرم مهم برای نمایش چندجمله ای.ها ارائه دادیم: فرم فوریه و فرم ضابطه ای. حال می خواهیم به تبدیل بین این دو فرم بپردازیم. این تبدیل اساس کار الگوریتم.های محاسباتی پیش رو خواهد بود. به تبدیل از فرم ضابطه ای به فرم فوریه، مقداریابی می گویند و به عکس این عمل یعنی تبدیل از فرم فوریه به فرم چندجمله ای درون یابی گفته می شود.
یک الگوریتم برای تبدیل فرم ضابطه ای به فرم فوریه، این است که ابتدا n+1 مقدار دلخواه

را انتخاب کنیم و سپس مقدار چند جمله ای را در این نقاط محاسبه کنیم (مثلا با الگوریتم هورنر) که زوج مرتب.های بدست آمده یک فرم فوریه برای چندجمله ای خواهند بود. این الگوریتم از

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

بدست آورد که به این الگوریتم تبدیل سریع (گسسته ی) فوریه می گویند.
برای انجام عکس این عمل، یعنی درون یابی یا (DFT − 1) نیز الگوریتم سریعی وجود دارد.
محاسبات روی فرم فوریه

نکتهٔ جالب در مورد فرم فوریه برای نمایش چند جمله ای ها، سادگی انجام برخی محاسبات روی آن است. به طور مثال اگر بخواهیم دو چندجمله ای را جمع/ضرب کنیم، کافی است آن دو را با یک سری مقادیر x یکسان به فرم فوریه تبدیل کنیم و سپس مقادیر متناظر هر نقطه از آن دو تابع را با هم جمع/ضرب کنیم. دیده می.شود که در این فرم اعمالی مانند ضرب و یا تقسیم بسیار آسان تر از صورت ضابطه ای قابل انجام اند. در حقیقت جمع و تفریق و ضرب و تقسیم چندجمله.های به این فرم با

امکان پذیر است. در ادامه به بررسی جزییات پیاده سازی ضرب چندجمله ای.ها می پردازیم.
مسئلهٔ ضرب چندجمله ای

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

دارای درجه ای برابر m + n است پس باید برای نمایش آن به تعداد m + n + 1 زوج مرتب از آن را داشته باشیم، به همین منظور می توان از ابتدا هر دو چندجمله ای را به فرم فوریهٔ گسترش یافته با m + n + 1 نقطه تبدیل کرد، و سپس این نقاط را نظیر به نظیر ضرب کرد و حاصل ضرب را در فرم فوریه بدست آورد. برای یافتن جواب کافی است آن را از فرم فوریه به فرم ضابطه ای تبدیل کنیم. پس دوباره با دو مسئله ای که به آن.ها اشاره کردیم روبرو شدیم: تبدیل فرم.های ضابطه ای و فوریه. کافی است به بررسی پیاده سازی سریع این دو مسئله بپردازیم.
تبدیل سریع فرم.ها

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

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

فرض می کنیم که چندجمله ای داده شده

باشد. تبدیل فوریهٔ n ام A را ماتریس مقدارهای این چندجمله ای در ریشه.های n ام واحد تعریف کرده و با Y نشان می دهیم:





به طور بدیهی می توان این ماتریس را در زمان n2 محاسبه کرد زیرا محاسبهٔ آن شامل n بار محاسبهٔ مقدار چندجمله ای است که هر بار آن با روشی مانند الگوریتم هورنر به میزان

زمان نیاز دارد. برای بهبود این روش می توان الگوریتم بازگشتی با زمان

ارائه کرد. فرض کنید می خواهیم مقدار ماتریس تبدیل فوریه را بیابیم. اگر تعریف کنیم:







خواهیم داشت:





ولی اگر n زوج باشد، مربعات ریشهٔ n ام واحد، ریشه.های

ام واحد هستند. زیرا که:





پس توانستیم مسئله را به دو زیر مسئله تقسیم کنیم، زیرا اکنون کافی است که ماتریس تبدیل فوریهٔ Aiها را که از اندازهٔ

هستند، در نقاط با مختص اول ریشه.های

ام واحد پیدا کنیم که همان مسئلهٔ ابتدایی است. پس از دو بازگشت، کافی است با رابطهٔ داده شده جواب.ها را با هم ادغام کنیم تا جواب اصلی مسئله حاصل شود. الگوریتم کلی به روش بازگشتی در زیر آمده است:
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





این صفحه را در گوگل محبوب کنید

[ارسال شده از: فان پاتوق]
[مشاهده در: www.funpatogh.com]
[تعداد بازديد از اين مطلب: 10163]

bt

اضافه شدن مطلب/حذف مطلب




-


گوناگون

پربازدیدترینها
طراحی وب>


صفحه اول | تمام مطالب | RSS | ارتباط با ما
1390© تمامی حقوق این سایت متعلق به سایت واضح می باشد.
این سایت در ستاد ساماندهی وزارت فرهنگ و ارشاد اسلامی ثبت شده است و پیرو قوانین جمهوری اسلامی ایران می باشد. لطفا در صورت برخورد با مطالب و صفحات خلاف قوانین در سایت آن را به ما اطلاع دهید
پایگاه خبری واضح کاری از شرکت طراحی سایت اینتن