همان طور که مشخص است تابع هزینه به صورت یک تابع درجه دوم از ضرایب فیلتر میباشد. حل معادله کمینهسازی تابع هزینه فوق منجر به معادله وینر-هوف میگردد که به صورت زیر میباشد:
در معادله فوق اگر R یک ماتریس غیرتکین باشد (ماتریسی با مقادیر ویژه غیر صفر) ضرایب بهینه wo از رابطه زیر بدست می آید:
اگر سیگنالهای xi[n] و xd[n] در بازه زمانی پردازشی ایستان باشند این امکان وجود دارد که با فیلترینگ بهینه به صورت فوق به میزان کمینه تابع هزینه که برابر با است، دست یافت. به علت آن که شرط حل معادله وینر-هوف همواره در دست داشتن R وP و عدم وابستگی آنها به زمان است و از آنجایی که در عمل وابستگی به زمان در این ماتریسها وجود دارد دستیابی به میزان کمینه تابع هزینه میسر نخواهد بود، در عمل تابع هزینه به صورت زیر خواهد بود:
در رابطه فوق نشانگر ضرایب قابل دسترس در عمل میباشد [۳۶-۳۷].
۳-۳-۲- الگوریتم LMS
الگوریتم LMS در سال ۱۹۶۰ توسط ویدرو و هوف پیشنهاد شده است و تا قبل از مطرح شدن الگوریتم RLS پرکاربردترین الگوریتم به حساب میآمد. همان طور که بیان شد الگوریتم LMS حالت عملی پیادهسازی فیلتر وینر میباشد با این تفاوت که این الگوریتم بدون نیاز به دانستن ماتریسهای R و P (ماتریس همبستگی سیگنال ورودی فیلتر و ماتریس همبستگی متقابل ورودی فیلتر و سیگنال مطلوب) و بدون نیاز به محاسبه معکوس ماتریس R برای حل معادله وینر-هوف، معادله وینر-هوف را به صورتی تکرارپذیر حل کرده و وزنهای بهینه برای کمینه کردن تابع هزینه را نتیجه میدهد. برای پیادهسازی الگوریتم LMS ابتدا یک مقدار اولیه به وزنها اختصاص میدهیم (معمولاً مقدار اولیه وزنها صفر در نظر گرفته می شود) سپس مراحل زیر را برای بهروزرسانی وزنها به ترتیب انجام میدهیم:
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت nefo.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))
۱- گرادیان تابع هزینه را محاسبه میکنیم. در واقع مربع خطا را به صورت لحظهای بنابر رابطه زیر محاسبه میکنیم:
در رابطه فوق و بیانگر تخمین لحظهای ماتریسهای P وR بوده و از روابط زیر بدست میآیند:
۲- پس از محاسبه گرادیان لحظهای با بهره گرفتن از آن عمل بهروزرسانی وزنها مطابق رابطه زیر انجام می شود:
در رابطه فوق μ به عنوان اندازه گام الگوریتم LMS شناخته می شود که عاملی مهم در عملکرد الگوریتم به حساب می آید.
عملیات محاسبه گرادیان و بهروزرسانی وزنها تا جایی ادامه مییابد که تغییر قابل ملاحظهای در وزنها مشاهده نشود و یا وزنها به مقدار مطلوب جهت کیمنه کردن تابع هزینه و خطا همگرا شوند.
یکی از علل پرکاربرد بودن الگوریتم LMS راحتی پیادهسازی آن میباشد به نحوی که در شرایطی که سیگنالها غیرمختلط باشند و تعداد ضرایب فیلتر را برابر با L در نظر بگیریم، پیادهسازی الگوریتم LMS منجر به انجام ۲L+1 ضرب (L ضرب برای محاسبه خروجی فیلتر و L ضرب برای بهروزرسانی وزنها و یک ضرب برای محاسبه ۲μxe) و ۲L جمع می شود و همان طور که مشخص است مرتبه محاسباتی این الگوریتم از مرتبه L میباشد. البته با وجود پیچیدگی محاسباتی کم، در الگوریتم LMS سرعت همگرایی وزنها و نحوه عملکرد الگوریتم برای حذف تداخل و آشکارسازی هدف در رادارهای پسیو مبتنی بر سیگنال DVB-T چندان مطلوب نبوده و توصیه می شود با الگوریتم VSLMS جایگزین شود. همان طور که بیان شد اندازه گام الگوریتم LMS عاملی مهم در عملکرد این الگوریتم میباشد. در واقع اثر μ در سرعت همگرایی الگوریتم میباشد. اگر μ مقداری بسیار کوچک انتخاب شود دقت الگوریتم بیشتر بوده و در نهایت خطای کمتری در همگرایی وزنها وجود خواهد داشت اما کوچک انتخاب کردن μ باعث کند شدن الگوریتم و پایین آمدن سرعت همگرایی می شود از طرفی بزرگ انتخاب کردن μ نیز منجر به داشتن سرعت همگرایی بالا و خطای نهایی بیشتر خواهد شد، حتی در حالاتی انتخاب μ بزرگتر از حدی باعث غیر همگرا شدن الگوریتم می شود. همین تناقض در نحوه انتخاب μ عاملی برای استفاده از الگوریتم VSLMS است. نتایج بررسیهای مختلفی که انجام شده است نشان میدهد که هرگاه μ مطابق رابطه زیر انتخاب شود بدون توجه به اینکه مقداردهی اولیه وزنها چگونه باشد (هر مقدار دلخواهی به عنوان مقدار اولیه وزنها انتخاب شود) ضرایب فیلتر به مقدار بهینه وینر خود همگرا میشوند.
که λmax بیانگر بزرگترین مقدار ویژه ماتریس R میباشد. در حالتی که λmax مشخص نباشد (یعنی اگر ماتریس R مشخص نباشد) با فرض اینکه بزرگترین مقدار ویژه ماتریس R از بقیه مقادیر ویژه بسیار بزرگتر است میتوان شرط همگرایی الگوریتم LMS را به صورت رابطه زیر در نظر گرفت:
همان طور که بیان شد در الگوریتم LMS به دلیل آن که در محاسبه P و R نمونههای زمانی جایگزین E{.} شده اند ضرایب فیلتر حول مقدار بهینه وینر خود در نوسان هستند. این بدان معناست که در محاسبه ضرایب، میزانی خطا برابر با رابطه زیر وجود خواهد داشت:
در نتیجه مقدار تقریبی کواریانس خطا در ضرایب مطابق رابطه زیر میباشد:
IM ماتریس همانی مرتبه M است.
وجود خطای فوق در محاسبه ضرایب منجر به تولید خطای اضافی در خروجی فیلتر می شود، این خطای اضافی از رابطه زیر محاسبه می شود:
بنابراین در حالتی که داده ورودی رنگی و با پراکندگی زیاد مقادیر ویژه همراه باشد سرعت همگرایی الگوریتم با λmin و خطای حالت ماندگار با λmax تعیین می شود. بنابر رابطه فوق واضح است که افزایش طول فیلتر وفقی که با الگوریتم LMS کار می کند منجر به افزایش خطای اضافی در الگوریتم می شود چرا که مقادیر ویژه ماتریس R همواره نامنفی هستند. در حالت کلی خطای الگوریتم LMS از زابطه زیر بدست می آید:
واضح است که در این الگوریتم خطای محاسبهی وزنها هیچ وقت به خطای کمینه حالت وینر خود نمیرسد [۳۵-۳۶-۳۷].
۳-۳-۳- الگوریتم NLMS
الگوریتم NLMS در واقع همان الگوریتم LMS است که به صورت نرمالیزه پیادهسازی می شود. منظور از پیادهسازی نرمالیزه الگوریتم، نحوه محاسبه وزنها به صورت زیر میباشد:
که در این رابطه باید برقرار باشد. در این الگوریتم نحوه انتخاب پارامتر در سرعت همگرایی و نحوه عملکرد الگوریتم بسیار موثر است. استفاده از این الگوریتم زمانی سودبخش می شود که سیگنال ورودی فیلتر وفقی نسبتاً بزرگ باشد، در این حالت با مسئله نویز گرادیان[۵۳] روبرو شده و در محاسبه وزنها مطابق خود الگوریتم LMS با مقادیر بزرگی مواجه میشویم. الگوریتم NLMS با نرمالیزه کردن اندازه گام در فرمول محاسبه وزنها از رویارویی با مقادیر بزرگ و مسئله نویز گرادیان جلوگیری کرده و با گامهایی مناسبتر به وزنهای تقریباً ایدهآل همگرا می شود و در نهایت یک الگوریتم با پایداری و سرعت بیشتر را پیادهسازی می کند. بقیه مباحث ذکر شده در الگوریتم LMS برای این الگوریتم نیز صادق است، برای مثال پیچیدگی محاسباتی در این الگوریتم نیز مانند الگوریتم LMS از مرتبه طول فیلتر وفقی میباشد. در اصل الگوریتم LMS و NLMS به صورت یک الگوریتم در نظر گرفته میشوند با این وجود تفاوتهایی بین الگوریتم LMS و NLMS نیز وجود دارد. برای مثال الگوریتم NLMS بر خلاف الگوریتم LMS یک الگوریتم با اندازه گام متفاوت با زمان میباشد و یا الگوریتم NLMS نرخ همگرایی را نشان میدهد که از نرخ همگرایی الگوریتم LMS بیشتر است یعنی الگوریتم NLMS سریعتر به مقادیر بهینه همگرا می شود [۳۵-۳۶-۳۷].
۳-۳-۴- الگوریتم VSLMS و VSNLMS
الگوریتم VSLMS در واقع بر پایه الگوریتم LMS پیادهسازی می شود، با این تفاوت که به هر یک از وزنهای فیلتر وفقی یک اندازه گام متغیر با زمان اختصاص داده می شود. علت این امر آن است که انتخاب μهای کوچک میزان خطای نهایی را کاهش میدهد، در حالی که برای کاهش زمان و افزایش سرعت همگرایی الگوریتم نیاز به انتخاب اندازه گامهای بزرگ میباشد. برای حل این تناقض در نحوه انتخاب μ از الگوریتم LMS با اندازه گامهای متغیر با زمان استفاده می شود به نحوی که میزان خطای نهایی نسبت به الگوریتم LMS کاهش یافته و سرعت همگرایی الگوریتم افزایش یابد. بهروزرسانی وزنها در این الگوریتم به صورت زیر انجام می شود [۳۶-۴۰-۴۲-۴۳-۴۴]:
gi در رابطه فوق با نام بردار گرادیان شناخته می شود. در رابطه فوق واضح است که μmin مقداری کمتر از μmax داشته و هر کدام مقداری در محدوده صفر و دو اختیار می کنند. در این الگوریتم هر یک از اندازه گامهای انتخابی باید در بازه مجاز μ برای الگوریتم LMS نیز قرار گیرند. ρ و μmin از پارامترهای قابل تنظیم برای بهبود عملکرد الگوریتم میباشند. انتخاب کوچک ρ سبب کاهش خطای ماندگار شده اما سرعت همگرایی را نیز کاهش میدهد. در هر صورت با انتخاب مناسب ρ میتوان سرعت همگرایی را نسبت به الگوریتم LMS افزایش داد. μmin را میتوان نزدیک به صفر انتخاب کرد به نحوی که الگوریتم همگرا شود. نحوه انتخاب پارامتر μmin در سرعت همگرایی الگوریتم تاثیر به سزایی داشته و بهبود الگوریتم با تنظیم مناسب این پارامتر امکان پذیر است.
الگوریتم VSNLMS نیز همان الگوریتم VSLMS است که به صورت نرمالیزه پیادهسازی می شود، علت استفاده از این الگوریتم نیز مانند علت استفاده از الگوریتم NLMS است. منظور از نرمالیزه کردن در این حالت این است که مقدار μmax در الگوریتم VSLMS بر حسب توان سیگنال ورودی فیلتر وفقی تعیین می شود. یعنی در این الگوریتم نیز مانند الگوریتم NLMS اندازه گام با توان سیگنال ورودی نسبت عکس دارد. این الگوریتم در واقع همان الگوریتم VSLMS است با این تفاوت که در این الگوریتم علاوه بر اندازه گام و گرادیان، ماکزیمم اندازه گام نیز در هر مرحله بهروزرسانی می شود. نکته قابل توجه آن است که از آنجا که الگوریتمهای VSLMS و VSNLMS نیز بر پایه الگوریتم LMS عمل می کنند پیچیدگی محاسباتی این الگوریتمها نیز از مرتبه طول فیلتر وفقی یعنی همان L میباشد. بهروزرسانی وزنها در الگوریتم VSNLMS به صورت زیر انجام میپذیرد [۳۶-۴۰-۴۲-۴۳-۴۴]:
در این الگوریتم نیز مانند VSLMS نحوه عملکرد و سرعت همگرایی الگوریتم با انتخاب مناسب پارامترهای ρ و μmin امکان پذیر است [۳۶-۴۰-۴۲-۴۳-۴۴].
۳-۳-۵- الگوریتم RLS
تا بدینجا فیلتر وینر و الگوریتمهای قابل پیادهسازی آن، یعنی الگوریتم خانواده LMS شامل الگوریتمهای LMS، NLMS، VSLMS و VSNLMS را معرفی کردیم. همانطور که در مقدمه بیان شد الگوریتمهای خانواده LMS بر اساس کمینه کردن میانگین آماری مربع خطا عمل می کنند اما الگوریتم RLS بر مبنای نظریه سیگنالهای قطعی استوار است. در الگوریتم RLS هدف کمینه کردن جمع وزندار مربع خطا عمل می کند. الگوریتم RLS در واقع پیادهسازی روش فیلترینگ LS[54] (حداقل مربعات) به صورت بازگشتی است. پیادهسازی یک فیلترینگ بر مبنای روش LS نیازمند داشتن اطلاعات ورودی فیلتر و سیگنال مطلوب در فیلترینگ از زمان آغازین بوده و از لحاظ عملی به علت حجم پیچیدگی محاسباتی بالا تیاز به حجم عظیمی از حافظه دارد از این رو از الگوریتم بازگشتی آن که همان الگوریتم RLS است استفاده می شود. در روش حداقل کردن مربعات از تمام داده های موجود از لحظه شروع تا لحظه nام استفاده می شود به همین دلیل طول داده های در دسترس با افزایش زمان و طول داده زیاد می شود. برای حل این مشکل از ضریب وزندهی با نام ضریب فراموشی استفاده می شود تا داده های قدیمیتر به دست فراموشی سپرده شده و عملیات فیلترینگ بر روی داده های جدیدتر انجام شود. ضریب فراموشی در الگوریتم RLS معمولاً در بازه [۹۹۹۹۹۹۹/۰ , ۹/۰] قرار دارد. پیچیدگی محاسباتی الگوریتم RLS در مقایسه با الگوریتمهای خانواده LMS چندان کم نبوده چرا که پیچیدگی محاسباتی در این الگوریتم از مرتبه L2 میباشد[۳۶-۳۷]. در این الگوریتم به تخمین ماتریس کواریانس، P، احتیاج است. این تخمین در هر مرحله با بهره گرفتن از بهره g[n] به صورت زیر به روز شده و با کمک آن وزنهای فیلتر وفقی مطابق روابط زیر بهروزرسانی میشوند[۳۵]:
در این الگوریتم، λ که ضریب فراموشی نامیده می شود عاملی مهم در سرعت همگرایی و کیفیت عملکرد الگوریتم میباشد. پیچیدگی محاسباتی الگوریتم RLS از مرتبه L2 (L طول فیلتر وفقی است) میباشد که این امر امکان پیادهسازی این الگوریتم برای فیلترهای با طول زیاد را مشکل می کند. با این وجود الگوریتم RLS از کیفیت و سرعت همگرایی بسیار بالاتری نسبت به الگوریتم LMS برخوردار است [۱۷-۳۶-۳۷-۴۵].
۳-۳-۶- الگوریتم Fast-RLS
الگوریتم Fast-RLS که با نامهای FTF[55] و FT-RLS[56] نیز شناخته می شود راهی دیگر برای کمینه کردن جمع وزندار مربع خطا میباشد. مزیت این روش پیچیدگی محاسباتی کم آن در مقایسه با الگوریتم RLS میباشد. پیچیدگی محاسباتی در این روش از مرتبه L یا همان طول فیلتر وفقی است. الگوریتم FT-RLS یک نسخه سریع از الگوریتم RLS میباشد. همان طور که بیان شد این الگوریتم نیز به صورتی متناوب و بازگشتی به حل مسأله کمینه کردن مربع خطا می پردازد و از نظر خواص آماری به الگوریتم RLS بسیار نزدیک است. در این الگوریتم با تعریف متغیری با نام ضریب همگرایی و بهروزرسانی این ضریب به کمک پیش بینی میزان خطا، بهروزرسانی وزنهای فیلتر وفقی انجام می شود. در الگوریتم FT-RLS نیز مانند الگوریتم RLS، λ یا همان ضریب فراموشی عاملی مهمی در تعیین سرعت همگرایی و عمکرد الگوریتم میباشد الگوریتم FT-RLS بر مبنای فیلترهای لاتیس[۵۷] در حل کمینهسازی مربع خطا عمل می کند با این تفاوت که در ساختار این الگوریتم برای کاهش میزان محاسبات مورد نیاز از چهار فیلتر Trannsversal به صورت همزمان استفاده می شود. در شکل ۳-۵ بلوک دیاگرام فیلترهای مذکور نشان داده شده است [۳۶-۴۶].
شکل ۳-۵: بلوک دیاگرام فیلتر Fast-RLS
در ادامه به توضیح عملکرد فیلترهای بلوک دیاگرام مذکور میپردازیم.