دانلود پروژه کامل رباتیک 120 ص+40 اسلاید+ کدهای نوشته شده در نرم‌افزار MATLAB + عکس + برنامه و مقالات انگلیسی

اختصاصی از یارا فایل دانلود پروژه کامل رباتیک 120 ص+40 اسلاید+ کدهای نوشته شده در نرم‌افزار MATLAB + عکس + برنامه و مقالات انگلیسی دانلود با لینک مستقیم و پرسرعت .

فرمت فایل ها :  word,pdf,ppt,code Matlab
 

چکیده:

این مقاله الگوریتمی جدید برای مسئله برنامه ریزی مسیرکلی به یک هدف ، برای ربات متحرک را با استفاده از الگوریتم ژنتیک ارائه می دهد .الگوریتم ژنتیک برای یافتن مسیر بهینه برای ربات متحرک جهت حرکت در محیط استاتیک که توسط نقشه ای با گره ها و لینک ها بیان شده است ،بکار گرفته شده است.موقعیت هدف و موانع برای یافتن یک مسیر بهینه در محیط دو بعدی داده شده است .هر نقطه اتصال در شبکه ژنی است که با استفاده از کد باینری ارائه شده است.تعداد ژن ها در یک کروموزوم تابعی از تعداد موانع در نقشه (نمودار)می باشد.
بنابراین از یک کروموزوم با طول ثابت استفاده کردیم.مسیر ربات ایجاد شده ، در مفهوم کوتاهترین مسیر ،بهینه است .ربات دارای محل آغاز و محل هدف تحت فرضیه ای است که ربات از هر محل فقط یکبار می گذرد یا اصلا نمی گذرد.نتایج بدست آمده در شبیه سازی ؛قدرت الگوریتم پیشنهادی را تایید می نماید.

 مقدمه:
 
مسئله طراحی مسیر ربات متحرک را می توان بصورت ذیل بیان کرد:
داده های مسئله (محل شروع،محل هدف، نقشه ای دو بعدی مسیرهاکه شامل موانع ساکن می باشد).هدف بدست آوردن یک مسیر بدون تصادم بین دو نقطه خاص در ایفای معیار بهینه سازی با در نظر گرفتن محدودیت ها (به احتمال زیاد:کوتاهترین مسیر)می باشد. مسئله طراحی مسیر از نظر محاسباتی بسیار پر هزینه است.
با اینکه حجم زیادی از تحقیقات برای حل بیشتر این مسائل انجام شده است،با این وجود،روش های معمول ،غیر قابل انعطاف می باشند.
1.اهداف مختلف بهینه سازی و تغییرات اهداف
2. عدم قطعیت ها در محیط ها
3. محدودیت های متفاوت برای منابع محاسباتی
مرور و بازنگری روش های موجود برای حل مسئله طراحی مسیر ،در [1] ارائه شده است . روش های زیادی برای ایجاد یک مسیر بهینه از قبیل برنامه ریزی دینامیک و روش های تبدیل مسافت گزارش شده است .
در روش برنامه ریزی دینامیک اگر نقطه ی شروعSP و نقطه ی هدف GP باشد ، نقطه ی زیر هدف IP است.و روش تولید مسیر ،نحوه تعیین توالی زیر اهداف است که زیر اهداف خود از مجموعه IP (I=1,2,3,…) انتخاب می شوند.ما باید تمام مسیرهای ممکن را بررسی کرده و مسیر با کمترین  مقدار هزینه را به عنوان مسیر بهینه انتخاب نمائیم.توان محاسباتی بسیار فراوانی بویژه در محیط های دارای زیر اهداف فراوان مورد نیاز است . در روش تبدیل مسافت ،کارطراحی مسیر ،محیطی را با شبکه یکنواخت می پوشاند و فواصل را از طریق فضای خالی ،از سلول هدف،منتشر می کند.قسمت پیشین موج مسافت ،حول موانع و در نهایت از طریق تمامی فضاهای آزاد در محیط جریان می یابد.برای هر نقطه شروع در محیط نمایانگر محل اولیه ربات متحرک ،کوتاهترین مسیر به مقصد،از طریق رفتن به قسمت پائین و از طریق شیب دارترین مسیر نزولی رسم شده است.با این وجود به هنگام وجود دو سلول یا بیشتر جهت گزینش با همان حداقل تبدیل فاصله ابهام مسیرهای بهینه وجود دارد. دو روش مذکور ملزم توان محاسباتی بسیار بالا در محیطی است که دارای تعداد زیاد اهداف فرعی (زیر اهداف)و موانع است.
محققان روش های فراوان را برای حل مسائل طراحی مسیر ربات های متحرک با وجود موانع ایستا و متحرک بر مبنای soft computing ،بیان کرده اند. soft computing متشکل از منطق فازی،شبکه های عصبی و محاسبات تکاملی است (الگوریتم های ژنتیک و تکاملی GA & EA).تاکنون تلاش های زیادی در استفاده از منطق فازی برای طراحی و برنامه ریزی حرکت ربات متحرک وجود داشته است .اخیرا استفاده از محاسبات تکاملی رواج فراوانی پیدا کرده و در واقع روشی است که به منظور بکارگیری در موقعیت هایی که دانش اولیه راجع حل مسئله وجود نداشته و یا اطلاعات محدود می باشد،قابلیت استفاده به گونه ای موثرتر،عمومی تر و راحت تر را داراست.
الگوریتم های ژنتیکی و تکامکلی نیازمند اطلاعات اشتقاقی یا برآوردهای فرمال اولیه از راه حل نیستند و از آنجائیکه طبیعتا تصادفی می باشند دارای قابلیت جستجوی کل فضای جواب با احتمال بیشتر پیدا کردن بهینه عمومی می باشند.
می توان تحقیق قبلی راجع طراحی مسیر را به صورت یکی از دو روش مقابل طبقه بندی کرد: مبتنی بر مدل و مبتنی بر سنسور .
در حالت مبتنی بر مدل ،مدل های منطقی از موانع شناخته شده ،برای تولید تصادم بدون مسیر بکار گرفته می شوند.در حالیکه در روش مبتنی بر سنسور ، کشف و اجتناب از موانع ناشناخته است.در این مقاله الگوریتمی جدید جهت بدست آوردن مسیر بهینه بر مبنای مدل پیشنهاد شده است.

ادامه مطالب مقاله بصورت ذیل مرتب شده اند :
در بخش 2 ،مقدمه ای مختصر راجع الگوریتم ژنتیک ارائه شده است .در بخش 3 ،فرمول سازی مسئله مورد بررسی واقع شده،در بخش 4 الگوریتم پیشنهادی ، معرفی و در بخش 5 نتایج شبیه سازی نشان داده شده است.


1.مسیریابی

مسئله مسیریابی ربات در چند حالت قابل بررسی است :
در یک مفهوم می توان مسیریابی روبات را در قالب تعقیب خط (عموما مسیری از پیش تعیین شده با رنگ متفاوت از زمینه ) معرفی نمود.روبات هایی با این کاربرد تحت عنوان مسیریاب شناخته می شوند . یکی از کاربرد های عمده این ربات ، حمل و نقل وسایل و کالاهای مختلف در کارخانجات ، بیمارستان ها ، فروشگاه ها ، کتابخانه ها و ... میباشد .
ربات تعقیب خط تا حدی قادر به انجام وظیفه کتاب داری کتابخانه ها می باشد . به این صورت که بعد از دادن کد کتاب ، ربات با دنبال کردن مسیری که کد آن را تعیین میکند ، به محلی که کتاب در آن قرار گرفته می رود و کتاب را برداشته و به نزد ما می آورد .مثال دیگر این نوع ربات در بیمارستان های پیشرفته است ، کف بیمارستان های پیشرفته خط کشی هایی به رنگ های مختلف به منظور هدایت ربات های مسیریاب به محل های مختلف وجود دارد . (مثلا رنگ قرمز به اتاق جراحی یا آبی به اتاق زایمان.) بیمارانی که توانایی حرکت کردن و جا به جا شدن را ندارند و باید از ویلچر استفاده کنند ، این ویلچر نقش ربات تعقیب خط را دارد ، و بیمار را از روی مسیر مشخص به محل مطلوب می برد .
با توجه به وجود موانع (استاتیک و دینامیک) در محیط ،مسیریابی روبات در مفهومی کاربردی تر ،پیمودن مسیر مبدا تا مقصد بدون برخورد با موانع می باشد.مسلما با وجود تعداد زیاد موانع ،تعداد مسیرهای قابل عبور روبات بسیار زیاد خواهد بود و یقینا انتخاب کوتاه ترین مسیر توسط روبات برای حرکت از مبدا به مقصد ،دارای ارزش اجرایی بالایی خواهد بود.در این مقاله چنین مسئله ای مورد بررسی واقع شده است.نقاط مبدا و مقصد و نیز محل موانع به عنوان ورودی داده شده است ،نیز می دانیم موانع ایستا می باشند (در حالت وجود موانع پویا در عین نزدیکی بیشتر به شرایط واقعی ،روش های مورد استفاده بسیار پیچیده خواهند بود)و مسئله در حالت دو بعدی بررسی می شود (روبات بر روی صفحه حرکت می نماید). برای این منظور الگوریتم های مسیریابی با هدف انتخاب کوتاهترین مسیر قابل استفاده می باشند ،الگوریتم هایی که به منظور مسیریابی در شبکه ها قابلیت استفاده دارند.با این وجود در این بررسی از الگوریتم ژنتیک استفاده شده است . همچنین الگوریتم های ژنتیک و نیز دیگر روش های مشابه به منظور بهینه سازی مصرف انرژی روبات ،مسیر تغییر زاویه ازوی روبات ،زمان حرکت روبات و... قابل استفاده می باشند .  

2.الگوریتم ژنتیک

 GA در سال 1975 توسط Holland بر پایه تقلیدی از تکامل طبیعی یک جمعیت پایه ریزی شد به نحوی که کروموزوم ها به منظور خلق نسل جدید اجازه تولید مجدد داشته و جهت بقاء در نسل آینده به رقابت می پردازند.با گذشت زمان ،بر روی نسل ها ، fitness  بهبود می یابد و در نهایت بهترین راه حل قابل حصول است .اولین جمعیت p(0) به طور تصادفی با 0و1 کد می شود در هر نسل ،t، مناسبترین عناصر برای حضور در mating pool انتخاب می شوند و با سه عملگر پایه ای ژنتیک ؛ تولید مثل،ادغام و جهش ؛ جهت تولید نسل جدید تکامل می یابند .بر پایه بقاء بهترین هامی توان نتیجه گرفت کروموزوم های بدست آمده با استفاده از روشی منتخب بهترین کروموزوم ها قابل حصول می باشند.

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



Procedure
GA
Begin
t=0
initialize  p(t)
evaluate  p(t)
while not satisfy stopping rule do
begin
t=t+1
select  p(t)  from   p(t-1)
alter(t)
evaluate   p(t)
end
end

چنانچه بیان شد عموما تکامل از یک نسل به نسل بعد ،شامل سه مرحله است :ارزیابی تناسب،گزینش و بازآفرینی.
ابتدا ،جمعیت کنونی با استفاده از تابع تکامل تناسب ارزیابی شده و سپس بر اساس مناسب بودنشان طبقه بندی می شوند و در واقع نسل جدید با هدف بهبود و ارتقاء تناسب بوجود می آید.
روش بکار بردن عملگرهای ،تولیدمثل؛جهش و ادغام توسط الگوریتم ژنتیک به شکل زیر است :
در آغاز ، باز آفرینی منتخب ،بر روی جمعیت کنونی بنحوی بکار گرفته می شود که رشته ،تعدادی کپی ،بر اساس مناسب بودن آنها تهیه می کند.این عمل منجر به تولید جمعیت میانی خواهد شد. سپس دوما ،الگوریتم ژنتیک والدین را از جمعیت کنونی با احتمال بیشتر در انتخاب کروموزوم های بهتر گزینش می نماید.این عمل همراه با کمیت تناسب و دسته بندی کروموزوم خواهد بود و نهایتا (سوما)،این الگوریتم فرزندان (رشته های جدید)را از والدین منتخب با استفاده از اپراتورهای ادغام یا جهش بازآفرینی می نماید.اساسا ادغام،شامل تبادل تصادفی بیت هابین دو رشته جمعیت میانی می باشد.در نهایت عملگر جهش ،به طور تصادفی تعدادی از بیت های بین رشته های جدید را تعویض می نماید.این الگوریتم زمانی پایان می یابد که راه حل قابل قبول پیدا شودویا معیار همگرایی ایفا شود و یا وقتی که به تعداد محدود و از پیش تعیین شده تکرار دست یابیم.مشخصه های اصلی الگوریتم های ژنتیک این است که آنها می توانند فضای جستجو را به طور برابر جستجو کنند و نیازی به بهینه سازی تابع برای تمایز گذاشتن یا هرگونه ویژگی یکنواخت ندارند.دقت راه حل اکتسابی به تعداد کد مورد استفاده برای کدگذاری متغیر خاص(طول کروموزوم)بستگی دارد.


3.فرمول سازی مسئله

مسئله به صورت زیر بیان شده است :ربات متحرک در مسیری بسته حرکت می نماید.این ناحیه به صورت نموداری دو بعدی توصیف می شود.چنین نموداری شامل تعداد محدودی موانع ایستا و یک سری نقاط به منظور جلوگیری از برخورد رباتها به موانع است.هدف،طراحی مسیر بهینه بدون هیچ گونه تصادم بین نقطه شروع و نقطه هدف می باشد.به این معنا که باید معیار هدف را با محدودیت عاری از تصادم بهینه سازی کرد .اگر نمودار دو بعدی شامل نقاط اتصال باشد ،فضای کل راه حل های احتمالی ،بسیار بزرگ است .در واقع فضای C هر ربات ، فضای کل پیکربندی  های مسیر ربات است .
مسئله طراحی مسیر ، معادل با طراحی حرکت یک نقطه از ربات (نقطه مرجع )در فضای C می باشد.فضای C بدون رخورد ، اشاره به مکان هندسی تمام نقاط فضای C  دارد که نمایانگر پیکربندی های عملی و عاری از تصادم است.به این معنا که باید مسیر بهینه عملی و میسر باشد.به طور کل برای پیدا کردن مسیر بهینه بدون تصادم ، سه هدف بهینه سازی متفاوت وجود دارد:
1.به حداقل رساندن مسافت طی شده (کوتاهترین مسیر)
2.حفظ مسیر یکنواخت
3.ایفای ملزومات مشخص (ربات نباید خیلی به موانع نزدیک شود)

شکل 1 موقعیت های مختلف را نشان می دهد

 

مسیر1.مسیری محتمل در نظر گرفته نمی شود(تصادم مانع)
مسیر2.کوتاهترین مسافت و مسیر محتمل است
مسیر3.میسر بوده و مطمئن تر است (دورترین مسیر از مانع)
مسیر4.میسر است ولی معیار بهینگی را ایفا نمی کند

می توان این اهداف را با عوامل متفاوت،نسبت به اهمیت شان در مسئله بهینه سازی ایستامورد آزمایش قرار داد.در این مقاله بر ارائه کوتاهترین مسیر بدون تصادم،بین نقطه شروع(PS)ونقطه هدف(PG)با استفاده از الگوریتم ژنتیک متمرکز می شویم.


4.الگوریتم طراحی مسیر پیشنهادی

در این بخش ،برای پیدا کردن مسیرهای بهینه برای یک ربات ،جهت حرکت در محیط ایستای بیان شده از طریق یک نمودار با گره ها و لینک ها،الگوریتم ژنتیک بکار رفته است.از موارد کاربرد این مسئله می توان به استفاده از چنین ربات هایی در نمایشگاه ها ،بیمارستان ها ،موزه ها و لابراتوارها برای انتقال مواد اشاره داشت. در الگوریتم پیشنهادی ،هر مسیر از نقطه شروع تا هدف ،جواب است.در آغاز جمعیت های تصادفی از رشته ،تولید شده که نشان دهنده جواب های مجاز (میسر)یا غیر مجاز(غیر میسر)می باشد.جواب های غیر مجاز ، رشته هایی هستند که نمی توانند به هدف برسند.به این معنا که جواب رشته ،ربات را به حرکت در تصادم با موانع ،هدایت می کند.جواب های مجاز ،رشته هایی هستند که می توانند به هدف برسند.برای حرکات ربات متحرک به سمتی که از برخورد با موانع اجتناب نماید باید بهترین رشته ای را بیابیم که هدف را در کوتاهترین مسیر می رساند.
راه حل غیرمجاز دارای کمترین تناسب است (تناسب صفر).نمودار x-y که در مقاله مورد بررسی واقع شده است چنانچه در شکل  2نشان داده شده است ناحیه ای با مساحت 15m2  می باشد.
ربات دارای یک نقطه شروع و نقطه هدف روی نمودار ، تحت این فرضیه است که در طراحی مسیر ،ربات از هر نقطه فقط یکبار می گذرد یا اصلا نمی گذرد.هر گره دارای یک عدد در شکل 2 است و گره ها برای رمزگذاری مسیر ،به صورت رشته بیان شده طبق ترتیب اعداد ،بکار می روند.برای مثال0-4-5-10-9-15
              یک مسیر با PS=0 و PG=15 می باشد.


با استفاده از الگوریتم ژنتیک، نقاط اتصال ،در آغاز بطور تصادفی انتخاب شده اند،حال آنکه می بایستی اعداد مجاور ، با یک لینک روی نمودار ،بهم متصل باشند.در این زمینه ،اکثر محققان ،رشته مبنی بر ترتیب و دارای طول متغیر (کروموزوم ها)را بکار برده اند.این کروموزوم،از طریق رشته بیت ها ، بازآفرینی شده است (یعنی،نمایش طبیعی و نه دودوئی).بنابراین باید عملگرادغام و جهش خاصی را اتخاذ نمود.هنگام ادغام ،رشته ای که مناسب تشخیص داده شده است ،به طور تصادفی به عنوان یک والد انتخاب می شود.اگر والد دوم شامل عدد مشترکی در رشته اول باشد.یکی از دو رشته ها،بخشی از رشته هایشان را بعد از عدد مشترک مبادله می کنند در غیر اینصورت ،رشته ای دیگر بصورت والدین دوم انتخاب می شود و همین فرآیند دنبال می شود برای مثال با استفاده از نمودار شکل 2  :

والد1:  
والد2:       
 

هر والد دارای نقطه مشترک 10 است،بخش زیر خط دار هر رشته مبادله شده و دو مولود بصورت زیر ایجاد می شود

مولود1 : 0-1-5-10-9-15
مولود2 : 0-3-6-4-510-11-12-15
   
بعد از ادغام ،برای مشخص کردن تکرار یا عدم تکرار عدد در هر رشته ،مولود ها(فرزندان) بررسی می شوند.در اینصورت بخشی از رشته بین ارقام تکراری حذف می شود.سپس اصلاحاتی مورد نیاز است زیرا ممکن است حالتی پیش آید که مولود ها راه حل مجاز نیستند.این روش ،الگوریتم را پیچیده تر می سازد.مسئله مهم،نحوه تولید کدهای دودوئی به گونه ای که استفاده از کروموزوم هایی با طول ثابت عملی و آسان است .یکی از چالش آورترین جنبه های روش پیشنهادی ،کد گذاری هر رشته در کد دودوئی با طول ثابت است .مسیر ربات متحرک با استفاده از اعداد دودوئی کدگذاری شده که در آن هر ژن در یک کروموزوم ،از طریق 4 بیت باینری به گونه ای که در جدول 1 نشان داده شده است ،کدگذاری شده است.
 

A.کروموزوم ها و جمعیت اولیه

یک کروموزوم ،مطابق با راه حل عملی مسئله بهینه سازی است.بنابراین هر کروموزوم نشان دهنده مسیر است که متشکل از  قطعات خط راست می باشد ،به صورت توالی گره ها با اولین گره که نشان دهنده نقطه شروع اولین قطعه ،به دنبال گره های یانی بین قطعات و قطعه آخری نشان دهنده نقطه پایانی قطعه آخری،هدف،می باشد.حداکثر طول کروموزوم پیش فرض ،برابر با تعداد  نقاط نمودار در طول ژن است. در این حالت ،16 نقطه داری که هر نقطه در 4 بیت دودوئی کدگذاری شده است.به این معناکه طول کروموزوم برابر با 64=4*16 بیت می باشد.این نتیجه ساده است زیرا می توانیم طول موثر کروموزوم را برای کاستن توان محاسباتی لازم،کاهش دهیم.از توپولوژی نمودار مشاهده کردیم که مسیر بهینه برای رسیدن به نقطه هدف مرتبط با تعداد موانع است .
اگر تعداد موانع ایستا برابر با m باشد،کوتاهترین مسیر متشکل از حداکثر نقاط (m+2)یا تعداد(m+1)تکه خط است.این رابطه می پذیرد که شکل مانع پیچیده نیست و می تواند به صورت نقطه حجم در نظر گرفته شود.  
برای مثال اگر هیچگونه مانعی وجود نداشته باشد(m=0)کوتاهترین مسیر متشکل از یک قطعه خطی از نقطه شروع تا هدف است (تعداد نقاط 2)در شکل1،تعداد موانع استا m=3 ؛کوتاهترین مسیر تشکل از 3 نقطه ؛کمتر از 5 (m+2)می باشد.در شکل 2 ،m=7،کوتاهترین مسیر از نقاط 0 تا نقطه 15 {0-4-6-7-9-15} (6 نقطه)می باشد که کمتر از 9 است(m+2).بنابراین معادله زیر برای تعریف طول کروموزوم بکار خواهد رفت. Cn=m+2 که m تعداد موانع ایستا و cn   تعداد ژن ها در کروموزوم است.برای نمودار داده شده در شکل2،طول کروموزوم =4*(2+7)بیت دودوئی،می توان جمعیت اولیه کرووزوم ها را به طور تصادفی چنان تولید کرد کههر کروموزوم دارای m ژن تصادفی باشد حال آنکه نقاط آغازین و هدف در جمعیت ثابت شده اند.

.ارزیابیB

معمولا انتخاب تابع ارزیاب بر مسئله تحت شرایط بسیار خاص است.تابع ارزیاب یک کروموزوم،برای محاسبه تعیین مناسب بودن آن بکار می رود .زیرا تناسب باید به صورت کاهش فاصله ،افزایش یابد.بنابراین تابع تناسب F از یک مسیر محتمل بصورت زیرارزیابی شده است.

 
 


که در آن d(pi,pi+1)  طول قطعه بین دو نقطه pi,pi+1 در کروموزوم با تعداد نقاط m+2 است.


می توان طول قطعه را با استفاده از مقادیر مختصات x-y در جدول 1 به صورت زیر محاسبه نمود
 
اگر مسیر محتمل نباشد ،مقدار تناسب آن صفر می باشد.الگوریتم پیشنهادی قادر است نقاط مسیر را برای آشکار سازی عملی بودن آن یا عدم عملی بودنش در جدول 2 ,ترسیم نماید.نقاط اتصالی, نقاط مجاز مجاوربه نقاط کنونی در راه حل برای اجتناب از موانع اند.
 
C.عملگرها

در الگوریتم ,ازدو عملگر ژنتیکی رایج استفاده شده است.ادغام وجهش.ادغام ,دو مسیر "والد" را برای تولید دومسیر جدید "مولود"در نسل بعدی دوباره ترکیب می کند.از ادغام دو نقطه ای استفاده شده است. هردومسیر والد به طور تصادفی به سه بخش تقسیم شده و دوباره ترکیب شده اند.بخش  وسطی اولین مسیر بین موقعیت های بیت  هی ادغام و بخش میانی دومین مسیر(والد دوم) برای ایجادفرزندان جدید  تبادل می شوند,موقعیت های بیت ادغام به طور تصادفی در طول کوروموزوم  بین  موقعیت های 5.32 انتخاب  شده اند.این محدودیت ها,برای عدم اعمال تغییر نقاط اولی و هدف,طی فرآیند ادغام ,انتخاب شده اند.برای مثال ,با مشخص ودن والدین (36 بیت)  به صورت زیر ,باید به طور تصادفی  در موقعیتهای 15و23  ادغام  داده شوند.همچین فرآیند جهش ,برای  تغییر تصادفی موقعیت یک بیت  در کروموزوم کار برده شده است(بین موقعیت 5و32).شبه کد الگوریتم پیشنهادی بصورت ذیل داده شده است:


5.نتایج شبیه سازی

الگوریتم بالا به منظور شبیه سازی با استفاده از Matlabآزمایش شده است.محیط شبیه سازی دارای دستورات دستکاری رشته ای بسیار موثر است که تبدیل متغیرهای عدی به رشته ای و عکس این حالت را به گونه ای موثر میسر می سازد.در نتیجه عملگرهای ادغام و جهش به راحتی قابل پیاده سازی می باشند.



مثال شبیه سازی شده :
نقطه ی شروع 0 و نقطه ی پایان 15 است شکل 2 به صورت تولید کننده مسیر شبیه سازی شده است .بیت آغازین متشکل از 6 کروموزوم 63 بیتی است.احتمال ادغام 100 درصد در نظر گرفته شده و احتمال جهش 0.005 درصد می باشد.بهترین نتایج با استفاده از دو نقطه ادغام بدست امده است.نتایج شبیه سازی بعد از 50 نسل بصورت زیر داده شده است :

 

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


کروموزوم دومی به علت فرآیند جهش ،تاحدودی متفاوت است.بخشی از اعداد تکراری ،جداشده و نتیجه نهایی کوتاهترین مسیر منفرد{0-4-6-7-9-15}یا مسیر بهینه منفرد با طول 17.975 همگرا شده است.
این مسئله ،با سایر نقاط آغازین تست شده و نقاط نهایی و همگرایی آن،برای بدست آوردن مسیر بهینه در هر مورد ضمانت شده است.

الگوریتم ژنتیک ساده با طول ثابت کروموزوم،برای یک ربات متحرک به منظور دریافت کوتاهترین مسیر در محیط ایستای دو بعدی با M مانع ،شکل گرفته است.الگوریتم توسعه یافته از طرح کدگذاری موثر با رشته دودوئی دارای طول ثابت استفاده می نماید.طول کروموزوم بستگی به تعداد موانع ساکن دارد.هر کروموزوم دارای طول ثابت (m+2)ژن است.این الگووریتم نیازمند توان محاسباتی کمتر از سایر الگوریتمهای اخیرا توسعه یافته است.در محیط های دینامیک لازم است طول کروموزوم متغیر در نظر گرفته شود.

بررسی بیشتر

چنانچه در بخش 1 اشاره گردید نسخه های زیادی از مسأله طراحی مسیر وجود دارد .در این بخش با عنوان بررسی بیشتر ،هدف بررسی اجمالی یک نمونه مطالعه موردی در بهینه سازی حرکت بازوی روبات و نیز مروری بر روشهای قبلی اعمال شده می باشد. دسته بندی دقیقی از این مسائل و روشهایی برای حل آنها را می توان در بررسی انجام شده توسط Hwang وAhuja  در سال 1992 پیدا کرد. برای روشن شدن بحث، مورد ویژه ای را بررسی می نمائیم . یک بازوی ربات در طول مجموعه از موانع قرار گرفت . موقعیت های ابتدایی و انتهایی بازوی ربات داده شدند و مسأله پیداکردن مجموعه حرکاتی است که روبات را راهنمایی می کند تا بین دو موقعیت بدون برخورد با موانع حرکت کند.
برای حرکت دادن روبات از بین موانع ، روشهای قبلی (Brooks 1983) مستقیماً بکار رفتند تا مدلهای 3D CAD برای روبات و موانع برای یافتن راه حلی بکار آیند،
یعنی «فضای سه بعدی اختیاری» مدنظر آنها بود . در این فضا مسأله طراحی مسیر شامل یافتن حرکاتی از ساختار مجتمع سه بعدی روبات در فضایی درهم ریخته 3 بعدی می باشند.
پیشرفت اساسی ، بیان مسأله در فضای شناخته شده دیگر به صورت فضای پیکربندی شده بود که  توسط Lozano perez بیان گردید. در این فضا موقعیت(پیکربندی) روبات کاملاً توسط نقطه ای منفرد که دارای n پارامتر مستقل به صورت هماهنگ است مشخص شده بود . موقعیت هایی که از لحاظ فیزیکی غیرقانونی اند (به دلیل تصادفها) توسط نواحی خاصی بیان و نامیده می شوند. درفضای پیکربندی شده ، مسأله طراحی مسیر ، شامل یافتن یک منحنی پیوسته است (بیان ونمایش مسیر برای یک نقطه منفرد هندسی) است که:
نقاط بیان کننده پیکربندی اولیه ونهایی روبات را به هم وصل می کند
(ii)یکدیگر را قطع نمی کنند
این روش سبب تسهیل مسأله طراحی مسیر می گردد (یک مسیر را برای یک نقطه تنها جستجو می کند ) در مقابل جستجوی یک فضای چند بعدی (ابعاد به تعداد DOF روبات است) و در برابر شکلهای پیچیده تر موانع(موانع فیزیکی خیلی ساده ممکن است در نتیجه خیلی پیچیده و مجتمع باشند ). به عنوان مثال ، اجازه دهید بازوی طراحی شکل 1 را در نظر بگیریم . موقعیتش در طول موانع ، یکبار که مقادیر زاویه های بین اتصالاتش شناخته شوند، کاملاً مشخص می شود. بنابراین ، برای هر زوج ، امکان دارد که تصمیم گرفت که کجا روبات با موانع محیطی برخورد کند . این چیزی است که ما در شکل 2 ، برای نمایش نقشه بین موانع فیزیکی در فضای کاری انجام دادیم .

اکنون با حرکت یک نقطه در طول پیوستگی منحنی برای بازوی طراحی بین نقاط مربوطه و در فضای اختیاری یک حرکت آزاد از برخورد تعریف خواهد شد . این منحنی یک راه حل برای مسأله ی طراحی این مسیر خاص می باشد.
روش جدیدی در این زمینه ،  به «فضای مسیر گلوله» توجه دارد که در آن تمام مسیر به عنوان یک نقطه ی تنها نمایش داده می شود . عامل هماهنگ کردن این نقطه ، مقادیر پارامترهایی است که حرکات موفق روبات را تعریف می کند.
برای نمونه ، فهرست فرمانهای موفق ارسال شده به کنترل کننده ی روبات ، عمیقاً مسیر ورودی روبات را کشف می کند. در این فضا، مسأله طراحی مسیر ، به جستجو برای یک نقطه تنها ، کاسته می شود . یکبار دیگر ما ، ساده سازی مسأله طراحی مسیر را (جستجو برای یک نقطه ) در برابر جستجوی فضای چند بعدی (ابعاد فضای مسیر گلوله ، به تعداد پارامترهای مورد نیاز برای ساده سازی کامل تمام مسیر است)عوض کردیم.
برای مثال ، در شکل 2 ، مسیر مابین ، میتواند توسط نقطه ای در یک فضای هفت بعدی ساده شده که از توجه به طول هفت قطعه بدست آمده نمایش داده می شود.


 

شکل1: یک بازوی DOF که در طول موانع در یک فضای کاری قرار دارد.


 

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

روش های کلی :
روش های کلی تر به دو کلاس اصلی تقسیم می شوند:

روشهای قبض و جمع شدن
روشهای بسط و تجزیه
در روشهای قبض ، سعی می شود ابعاد مسأله آغازین را با ایجاد پیوستگی مجدد روی زیر مجموعه های متعدد فضای شکل گرفته ، کاهش داد. در روشهای تجزیه سعی می شود نواحی فضای ساخته شده را که رها از موانع اند تشخیص دهند و بشناسند. در نهایت هر دو روش با یک گراف کلاسیک که بیش تر از جستجوی یک فضای نظری است تمام می شوند. در اصل این روشها کاملند، چرا که اگر یک مسیر موجود باشد ، مسیر را خواهند یافت و اگر مسیری موجود نباشد در یک زمان محدود تمام می شوند .متأسفانه قبض مجدد یا گراف تجزیه یک مسأله کاملاً NP می باشد: همچنانکه تعداد DOF افزایش می یابد ، پیچیدگی این وظیفه هم بصورت نهایی (Exponentially) رشد می کند.
درنتیجه ، این طراحها فقط برای رباتهایی به کار می روند که تعداد محدودی DOF (3 یا 4) داشته باشند. علاوه بر آن، آنها آهسته اند و فقط می توانند بصورت Offline بکار روند. طراح مدلی از محیط اطراف را به کمک می طلبد . طرحی را ایجاد می کند که به کنترل کنندۀ ربات می رود و در واقع آن را اجرا می کند. معمولاً زمان مورد نیاز برای رسیدن به این هدف به اندازه کافی کوتاه نیست تا اجازه دهد که ربات در یک محیط دینامیک حرکت کند.

طراحی مسیر با طراحهای محلی:

یک راه برای مبارزه با مسئله ، جابجایی کامل شدن در برابر اجرا شدن می باشد . برای انجام این عمل، طراحهای محلی توسط شیب یک تابع هزینه (معمولاً فاصلۀ Euclidean به هدف) راهنمایی می شود و شروع به شمارش فشارهایی می کنند که موانع را معرفی می نماید تا از آنها پرهیز کند.
از آنجا که مسئله طراحی مسیر NP کامل می باشد با اطلاع از تابع هزینه، معمولاً طراحی یک محیط فریبنده امکان پذیر می گردد که در آن روش در یک حداقل محلی گیر خواهد افتاد. به هر حال این روشها ، کاربردهای صنعتی زیادی دارند ، چرا که می توانند توسط رباتهای مجتمع و مدلهای محیطی که دارای هزاران صورت هستند به کار گرفته شود، که اغلب زمان زیادی برای روشهای کلی صرف می کند.
طراحی مسیر با تکنیک های تصادفی و نشانه های رمزی:
تماس و دسترسی رندوم یا تصادفی ، اولین بار توسط Latombe & Barraquand معرفی شد و بعداً توسط Overmars و اخیراً توسط Kavyaki به کار رفته است . ایدۀ اصلی در پشت این الگوریتم ها ساخت گرافیکی در فضای شکل گرفته می باشد. گراف به صورت افزایشی به صورت زیر، بدست می آید:

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

روشهای دیگری هم طراحی شده اند که نشانه های مرزی استفاده می کنند برای مثال ، Sandros که توسط Hwang و Chen معرفی شده است که از نشانه های مرزی استفاده می کنند تا فضای آزاد را تقریبی نماید. این روش مشابه «طراحی سلسله مراتبی » است که  در AI به کار رفته است :
روش باید در رسیدن به یک هدف دچار خطا شود و هدفهای جزئی تر تولید شوند تا زمانیکه مسئله برای حل شدن کاملاً آسان شود . در سایر روش های آنها ، ابتدا یک طراح محلی به کار می رود تا به موقعیت نهایی برسد . طراح محلی باید خطلا کند تا فضای شکل گرفته به دو زیر فضا تقسیم شود ، که یکی از آنها حاوی هدف و دیگری شامل هدف جزئی تر است . لذا مسئله به دو مسئله کوچکتر تقسیم می شود :


از موقعیت آغازین به هدف جزئی تر می رود.
از هدف جزئی تر به موقعیت نهایی می رود .
Sandros نشان داده است که برای یافتن مسیر به طرز استادانه به خوبی سازگار شده است این روش برای مسیرهای طراحی شده برای ربات های Puma و Adept تکمیل و تست شده است

طراحی مسیر در فضای مسیر گلوله:

روشهای قبلی اساساً بر اساس فضای شکل گرفته استوار بودند ، قبض یا جمع شدن ،  تجزیه یا بسط ، یا بهینه سازی در این فضا ساخته می شود . روش دیگر توجه به «فضای مسیر گلوله » می باشد. به عنوان مثال ، Ferbach در روش خود VDP ، با توجه به موضوع خط راستی که در شکل آغازین و نهایی را پیوند می دهد شروع کرد. این مسیر بصورت تصاعدی تغییر می کند بطوریکه ، نواحی ممنوع برای عبور کاهش می یابد.
در هر تکرار، یک زیر مجموعه چند برابری که شامل مسیر صحیح است ، به صورت رندوم تولید میشود. سپس با استفاده از یک روش برنامه ریزی دینامیک، تجدید نظر و جستجو می گذرد که از طول ناحیه ممنوعه به عنوان تابع هزینه برای دستیابی به حداقل استفاده میکند. نتایج جستجو در مسیر گلوله ای جدیدی که با نواحی ممنوعه برخورد میکند از مسیر گلوله ای اصلی کوچکتر است، فرایند تکرار می شود تا یک مسیر گلوله ای مناسب پیدا شود.
همانطوریکه در بخش قبل دیدیم ، همچنین ممکن است محیط های ساده ای را طراحی کرد که این نوع از الگوریتم ها آهسته تر از یک روش رندم خالص می سازد . طرز کار Michalewicz and و Xiao و Lin مشابه این روش است . همانطور که در نسخه قبلی الگوریتم اشاره شد، الگوریتم های ژنتیک برای بهینه سازی از فضای مسیر گلوله به کار می رود.
 مسیرهای گلوله ای با استفاده از هماهنگ های نقطه های واسطه پارامتربندی می شود . یک الگوریتم تکاملی برای بهینه سازی تابع هزینه بکار می رود که بر اساس طول مسیر گلوله و عرض نواحی ممنوعه قرار دارد . اپراتورهای استاندارد  الگوریتم های ژنتیک تغییر یافته اند و بعداً برای ایجاد متغیر های بزرگ مسیرها توسعه یافته اند. تعداد نقاط واسطه ثابت شده است و با استفاده از یک روش ذهنی و غیر مستدل انتخاب می شوند . این تعداد داده شده ، ممانعتی برای طراحی یک مسئله ایجاد نمی کنند که برای حل شدن نیاز به نقاط واسطه بیشتری خواهد داشت و الگوریتم را به خطامی کشاند و قتی که یک راه حل وجود دارد....

پروژه جامع و کامل  به صورت اختصاصی از پایان نامه فوریو به مدت محدودی با قیمت فقط 4،500 تومان

مقاله و تحقیق جامع کدهای بلوکی و کدهای کانولوشن (همراه با تصاویر)

اختصاصی از یارا فایل مقاله و تحقیق جامع کدهای بلوکی و کدهای کانولوشن (همراه با تصاویر) دانلود با لینک مستقیم و پرسرعت .

فرمت فایل : word(قابل ویرایش)

تعداد صفحات:76

فهرست مطالب:

فصل اول : کدهای بلوکی و کدهای کانولوشن

1-1- مقدمه :

1-2- ماکزیمم احتمال دیکدینگ  Maximum Likelihood Decoding

1-3­- انواع خطا Type of error

1-4- راه کارهای کنترل خطا  Error control Strategies

1-5- بررسی کدهای تصحیح کننده خطای برست (از هم پاشیدگی)  Burst –Error – Correcting Codes

1-6-دیکدینگ کدهای چرخشی تصحیح کننده خطای برست تکی

1-7- کدهای تصحیح کننده خطای برست تکی  Single – Burst – Correcting Codes

1-7-1-کدهای آتشین (Fire codes) :

1-8-سایر کدها :

1-9-کدهای یک در میان سازی  Interleaved Codes :

1-10-کدهای تصحیح خطای برست فاز بندی شده :  Phased – Burst-Error-Correcting

1-10-1- کدهای Burton

فصل دوم : کدهای تصحیح خطای رندم و برست  

2-1- کدهای محصول (Product)

2-2-کدهای    Reed-Solomon

2-3-کدهای بهم پیوسته ( متصل شده )   Concatenated Codes

2-4-تصحیح کدهای آتشی برای تصحیح همزمان خطاهای رندم و برست :

2-5- تصحیح خطای برست با کد های کانولوشن

2-6- کدهای کانولوشن تصحیح خطای برست

2-6-1- کدهای Berlekamp – Preparata

2-6-3-کدهای کانولوشن یک درمیان شده :

2-6-2-کدهای Iwadare-Messey

2-7-کدهای کانولوشن تصحیح کننده هردو خطاهای برست و رندم :      Burst – And-

2-7-1- کدهای پراکنده شده ( منتشر شونده Diffuse  )

2-7-2- سیستم جستجوی برست  ‏ The Burst Finding System

2-7-3-سیستم تله گذاری برست   The Burst-Trapping System

فصل سوم : کدهای تصحیح کننده پاک شدگی برست با تأخیر پائین

3-1-مقدمه :

3-2- ساختمان کد :

3-3-کدهای حداکثر کوتاه شده :

3-4-بررسی مجموع اغتشاش ها و گین های کدینگ :

فصل چهارم : یک الگوریتم طراحی شده جدید برای دیکدینگ کدهای

خلاصه :

4-1- مقدمه

4-2- انکدینگ کدهای RS :

4-3-دیکدینگ کدهای RS :

4-4- الگوریتم 1  کدهای RS :

تشریح عملیاتی بودن این الگوریتم :

4-5-الگوریتم   1a : دیکدینگ کدهای RS (تغییر یافته ):

4-6-تبدیل فوریه سریع   Fast Fourier Transforms (FFT)  :

– FFT‌ وفقی :

فصل پنجم : روش بسته بندی  پی در پی جهت دست یافتن به تکنیک یک درمیان سازی چند بعدی (M-D):

5-1- مقدمه :

5-2- آرایه های یک درمیان شده پایه :

رویه 4-1 :

5-3- آرایه پایه  دوبعدی مربع شده :

– آنالیز اجرای رویه فوق :

فصل ششم :  کد های محصول با افزونگی کاسته شده ، جهت تصحیح خطاهای

6-1-مقدمه :

6-2- ساختاری ساده ای با استفاده از کدهای کاسته شده افزونگی :

6-3- کاهش افزونگی بیشتر :

6-4-اضافه کردن تصحیح خطای ردیفی ( ساختار 3 )

مقدمه :

امروزه دو نوع عمومی از کدها استفاده می شود : کدهای بلوکی و کدهای کانولوشن . انکدینگ یک کد بلوکی را به تر تیبی از اطلاعات در قالب بلوکهای پیغام از k بیت اطلاعات برای هر کدام تقسیم می کند . یک بلوک پیغام با k مقدار باینری که بصورت u=(u1,u2,…,uk) نشان داده می شود ، یک پیغام نامیده می شود . در کدینگ بلوکی از سمبل u جهت نشان دادن k بیت پیغام از کل ترتیب اطلاعات استفاده می گردد .

تعداد کل بیت های پیغام متفادت موجود پیغام است . انکدر هر پیغام u را بطور غیر وابسته ، بصورت یک n تایی v=(v1,v2,…,vn) که کلمه کد (codeword) نامیده می شود ، ارسال می دارد . در کدینگ بلوکی سمبل v برای مشخص کردن سمبل بلوک از کل ترتیب انکد شده استفاده می گردد .

از پیغام قابل ساخت ، کلمه کد مختلف در خروجی انکدر قابل ایجاد است . این مجموعه کلمات کد با طول n یک کد بلوکی (n,k) نامیده می شود. نسبت R=k/n نرخ کد نامیده می شود . نرخ کد می تواند تعداد بیتهای اطلاعات که انکد می شود را در هر سمبل انتقال یافته ،محدود کند . در حالتیکه n سمبل خروجی کلمه کد که فقط به k بیت ورودی پیغام وابسته باشد ، انکدر را بدون حافظه (memory-less) گویند . انکدر بدون حافظه با ترکیبی از مدارات لاجیک قابل ساخت یا اجرا است . در کد باینری هر کلمه کد v باینری است . برای اینکه کد باینری قابل استفاده باشد ، بعبارت دیگر برای داشتن کلمات کد متمایز باید یا باشد . هنگامیکه k<n باشد ، n-k بیتهای افزونگی (redundant) می تواند به بیتهای یک پیغام اضافه گردد و کلمه کد را شکل دهد . این بیتهای اضافه شده توانایی کد را در مبارزه با نویز کانال فراهم می آورد . با نرخ ثابتی از کد ، بیت های افزونگی بیشتری را می توان با افزایش دادن طول بلوک n از کد ، با پیغام جمع کرد و این تا هنگامی است که نسبت k/n ثابت نگه داشته شود .

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

انکدر یک کد کانولوشن نیز به همان ترتیب ، k بیت بلوکی از ترتیب اطلاعات u را می پذیرد و ترتیب انکد شده ( کلمه کد ) v با n  سمبل بلوکی را می سازد . باید توجه کرد که در کدینگ کانولوشن سمبل های u و v جهت مشخص کردن بلوکهای بیشتر از یک بلوک استفاده می گردند . بعبارت دیگر هر بلوک انکد شده ای نه تنها وابسته به بلوک پیغام k بیتی متناظرش است ( در واحد زمان )‌ بلکه همچنین وابسته به m بلوک پیغام قبلی نیز می باشد . در این حالت انکدر دارای حافظه (memory ) با مرتبه m است .

محصول انکد شده ترتیبی است از یک انکدر k ورودی ، n خروجی با حافظه مرتبه m که کد کانولوشن (n,k,m) نامیده می شود . در اینجا نیز R=k/n نرخ کد خواهد بود و انکدر مذکور با مدارات لاجیک ترتیبی قابل ساخت خواهد بود . در کد باینری کانولوشن ، بیت های افزونگی برای تقابل با کانال نویزی می تواند در حالت k<n یا R<1  به ترتیب اطلاعات اضافه می گردد .

معمولاً k و n اعداد صحیح کوچکی هستند و افزونگی بیشتر با افزایش مرتبه حافظه از این کدها بدست می آید . و از این رو k و n و در نتیجه R ثابت نگه داشته می شود.

اینکه چگونه استفاده کنیم از حافظه تا انتقالی قابل اطمینان در یک کانال نویزی داشته باشیم ، از مسائل مهم طراحی انکدر ها محسوب می شود .

1-2– ماکزیمم احتمال دیکدینگ Maximum Likelihood Decoding

یک بلوک دیاگرام از سیستم کد شده در یک کانال AWGN با کوانتیزاسیون محدود خروجی در شکل 1 نشان داده شده است.

در این سیستم خروجی منبع u نشاندهنده پیغام k بیتی ، خروجی انکدر ، v نشاندهنده کلمه کد n- سمبلی خروجی دیمدولاتور ، r نشاندهنده آرایه Q دریافت شده n تایی متناظر و خروجی دیکدر نشاندهنده تخمینی از پیغام انکد شده k بیتی است . در سیستم کد شده کانولوشن ، u ترتیبی از kl بیت اطلاعات و v یک کلمه کد است که دارای N=nl+nm=n(l+m) سمبل می باشد . kl طول ترتیب اطلاعات و N طول کلمه کد است . سرانجام nm سمبل انکد شده بعد از آخرین بلوک از بیتهای اطلاعات در خروجی ایجاد می گردد . این عمل در طول m واحد زمانی حافظه انکدر انجام می پذیرد . خروجی دی مدولاتور ، r یک N تایی دریافت شده Q- آرایه ای است و خروجی یک تخمین از ترتیب اطلاعات می باشد. در واقع دیکدر می بایستی یک تخمین از ترتیب اطلاعات u براساس ترتیب دریافت شده r تولید نماید . پس یک تناظر یک به یک بین ترتیب اطلاعات u و کلمه کد v وجود دارد که دیکدر بر این اساس می تواند یک تخمین از کلمه کد v بدست آورد . روشن است که در صورتی است ، اگر و فقط اگر .

قانون دیکدینگ (یا برنامه دیکدینگ ) در واقع استراتژی انتخاب یک روش تخمین ، جهت تخمین کلمه کد از هر ترتیب دریافت شده ممکنr است . اگر کلمه کد v فرستاده شده باشد ، یک خطای دیکدینگ رخ داده است اگر و فقط اگر .

با دریافت r ، احتمال خطای شرطی دیکدر بصورت زیر تعریف می گردد : (1)

پس احتمال خطا دیکدر : (2) بدست می آید .

P(r) وابسته به قانون دیکدینگ نمی باشد . از این رو یک دستورالعمل دیکدینگ بهینه یعنی با حداقل P(E) باید را برای تمام مقادیر R به حداقل برساند .

به حداقل رسانیدن به مفهوم به حداکثر رسانیدن است . توجه گردد که اگر برای یک r دریافت شده با احتمال ماکزیمم انتخاب کردن ( تخمین ) از کلمه کد v به حداقل می رسد : (3) که شبیه ترین کلمه از r دریافت شده است . در صورتیکه تمام ترتیبات اطلاعات و درپی آن تمام کلمات کد مشابه باشند ، ( یعنی P( r ) برای تمام v ها یکسان باشد ) حداکثر کردن رابطه 3 معدل حداکثر کردن P(r|v) است . و برای یک DMC(Discrete memoryless channel) داریم :   (4)‌ .

باید توجه داشت که برای یک کانال بدون حافظه هر سمبل دریافت شده فقط به سمبل فرستاده شده متناظرش وابسته است . یک دیکدر که روش تخمینی جهت ماکزیمم کردن رابطه 4 انتخاب کند ، دیکدر با حداکثر احتمال نامیده می شود . MLD(Maximum Likelihood Decoder) – ماکزمم کردن رابطه 4 معادل ماکزمم کردن تابع احتمال لگاریتمی زیر است : (5)  بنابراین یک MLD برای یک DMC یک را بعنوان تخمینی از کلمه کد v برگزیند که رابطه 5 ماکزیمم گردد . درصورتیکه کلمات که معادل نباشد ، MLD لزوماً بهینه نمی گردد.

دراین حالت احتمالات شرطی P(r|v) باید بوسیله احتمالات کلمات کد P ( r) وزن داده شود تا مشخص گردد که کدام کلمه کد P(v|r) را ماکزیمم می کند .

اکنون مشخصه های MLD در یک BSC (Binary systematic Channel) مورد بررسی قرار می گیرد . در این حالت r  یک ترتیب باینری است که بغلت نویزی بودن کانال ممکن است از کلمه کد انتقال یافته v در بعضی موقعیت ها متفاوت باشد .

وقتی و بالعکس وقتی در نظر می گیریم . d(r,v) را فاصله بین rوv ( یعنی تعداد موقعیت های متفاوت بین rو v ) در نظر می گیریم . برای یک طول n یک کد بلوکی رابطه 5 بشکل زیر در می آید : (6)

. توجه گردد که برای کد کانولوشن n در رابطه 6 با N  بزرگ جایگزین می گردد .

در صورتیکه را برای P<1/2 و  ثابت برای تمام v ها ، در نظر بگیریم ، قاعده دیکدینگ MLD برای BSC ، را بعنوان کلمه کد v  انتخاب می کند که فاصله d(r,v) را بین rوv به حداقل برساند . بعبارت دیگر کلمه کدی را انتخاب می کند که در تعداد کمتری از موقعیتها از ترتیب دریافت شده ، متفاوت باشد . برای همین یک MLD برای BSC یک دیکدر با حداقل فاصله نامیده می شود .

تحقیقات Shannon در رابطه به بررسی توانایی کانال نویزی در ارسال اطلاعت تئوری کدینگ کانال نویزی را حاصل کرد و بیان می دارد که هر کانال دارای یک ظرفیت کانال C است و برای هر نرخ R<C ، کدهای ایجاد شده با نرخ R  با دیکدینگ ماکزیمم احتمال ، دارای کمترین احتمال خطای دیکدینگ P(E) است . در عمل برای هر R<C برای کدهای بلوکی با طول n داریم : (7) و برای کدهای کانولوشن با حافظه m : (8)  می باشد .

که طول اجباری کد نامیده می شود . و توابع مثبتی از R برای R<C هستند . که با پارامترهای کانال مشخص می گردند . مزر رابطه 7 بطور قرار دادی براین مطلب دلالت دارد که احتمالات خطای کوچک با کدینگ بلوکی R<C ثابت با افزایش طول n بلوک درحالتیکه نرخ k/n ثابت بماند ، بدست می آید . مرز رابطه 8 بیان می دارد که احتمالات خطای کوچک برای هر R<C  ثابت ، با افزایش طول یعنی با افزایش مرتبه حافظه m مادامیکه k و n ثابت باشند قابل دست یابی است . تئوری کدینگ کانال نویزی بر پایه یک استدلال ، کدینگ رندم نامیده می شود .

مرزهای بنا نهاده شده در واقع بر اساس احتمال خطای متوسط از مجموعه تمام کدها بدست می آید . مادامیکه کدها بهتر از حد متوسط شکل گیرند ، تئوری کدینگ کانال نویزی ، وجود کدها را در مرزبندی روابط 7 و 8 تضمین می نماید اما بیان نمی دارد که این کدها چگونه ساخته شوند .

برای دست یافتن به احتمالات خطای خیلی کمتر برای کدهای بلوکی با نرخ ثابت R<C طول های خیلی بزرگ از آن احتیاج است و در پی آن باید کلمات کد خیلی بزرگ باشد . و بعبارت دیگر هنگامیکه برای یک MLD  باید برای هر کد آن LogP(r|v) محاسبه گردد . سپس کلمه کدی که ماکزیمم باشد ، انتخاب گردد ، تعداد محاسبات برای شکل دادن یک MLD بسیار زیاد خواهد شد . برای کدهای کانولوشن ، احتمالات خطای کوچک به یک مرتبه m حافظه بزرگ محتاج است .

یک MLD برای کدهای کانولوشن به تقریباص محاسبه برای دیکد کردن هر بلوک از k بیت اطلاعات احتیاج دادرد و این محاسبات با افزایش m زیاد می شود . از این رو با استفاده از دیکدینگ با ماکزیمم احتمال جهت دستیابی به احتمالات خطای پائین غیر عملی به نظر می رسد . لذا دو مشکل اساسی جهت دستیابی به احتمالات خطای پائین مورد نیاز است :

• ساخت کدهای طولانی خوب با استفاده از دیکدینگ ماکزیمم احتمال که مرزهای روابط 7 و 8 را ارضا کند .
• یافتن روشهای اجرایی ساده جهت انکدینگ و دیکدینگ این کدها .

پایان نامه تحلیل و شبیه سازی کدهای CDMA به منظور کاهش تداخل بین کاربران

اختصاصی از یارا فایل پایان نامه تحلیل و شبیه سازی کدهای CDMA به منظور کاهش تداخل بین کاربران دانلود با لینک مستقیم و پرسرعت .

فرمت فایل: WORD (قابل ویرایش)

تعداد صفحات:101

پایان نامه کارشناسی

رشته مهندسی برق گرایش مخابرات

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

———————————————
1Autocorrelation Function
2 Crosscorrelation Function
3 Code Division Multiple Access
4 Frequncy Hopping
1- 2   تعا ریف
1-2-1  تابع همبستگی متقابل برای سیگنالهای پریودیک [3]
اگر  سیگنالهای پیوسته در زمان و پریودیک با پریود زمانی   باشند تابع همبستگی متقابل پریودیک آنها را به صورت زیر تعریف می کنیم                                   :                                                               (1-1)                                     
  برای سیگنال های گسسته در زمان و پریودیک   با پریود   نیز تعریف معادل زیر را به کار می بریم :  
(1-2)                                            
اگر بر طبق  که موج گسترش دهنده است تعریف شود تابع همبستگی متقابل به صورت زیر است :
(1-3)                                     
که فرض شده هر دو شکل موج   دوره تناوب   دارند و تابع همبستگی متقابل آن نیز متناوب با دوره تناوب  است .
با جایگذاری  در رابطه بالا بدست می آید :
 

 (1-4)
اگر   باشد دو پالس هم پوشانی دارند و اگر   باشد دو پالس تلاقی ندارند و حاصل انتگرال صفر خواهد بود و اگر   باشد دو پالس مجدداً هم پوشانی دارند و اگر   باشد دو پالس تلاقی ندارند و در نتیجه حاصل انتگرال صفر خواهد بود .
1-2-2  تابع خود همبستگی برای سیگنالهای پریودیک [3]
متناظر با تعریفهای فوق برای تابع خود همستگی پریودیک نیز تعریفهای زیر را خواهیم داشت .
حالت پیوسته :                                                       
(1-5)                                
و برای حالت گسسته با پریود  :
(1-6)                                       
فهرست مراجع


فهرست مطالب

فصل اول : پیش نیازهای ریاضی و تعاریف  1
1-1 مقدمه  2
1-2 تعا ریف  3
1-2-1 تابع همبستگی متقابل برای سیگنالهای پریودیک  3
1-2-2 تابع خود همبستگی برای سیگنالهای پریودیک  4
1-2-3 خواص توابع همبستگی پریودیک گسسته  5
1-3 نامساوی ولچ  6
1-4 نامساوی سید لینکوف  6
1-5 تابع همبستگی غیر پریودیک گسسته  7
فصل دوم : معرفی کدهای ماکزیمال و گلد و کازامی  8
2-1 مقدمه  9
2-2 تعریف  10
2-3 دنباله¬های کلاسیک  10
2-3-1 دنباله¬هایی با طول ماکزیمال  10
2-3-2 خواص دنباله¬های ماکزیمال  11
2-4 انواع تکنیکهای باند وسیع  13
2-4-1 روش دنباله مستقیم (DS)  13
2-5 کدPN   14

2-5-1 دنباله PN و پس خور ثبات انتقالی  15
2-5-2 مجموعه دنباله¬های ماکزیمال دارای همبستگی ناچیز  16
2-5-3 بزرگترین مجموعه به هم پیوسته از دنباله¬های ماکزیمال  17
2-6 دنباله گلد  19
2-7 مجموعه کوچک رشته¬های کازامی  20
2-8 مجموعه بزرگ رشته¬های کازامی  21
فصل سوم : نحوه¬ی تولید کدهای ماکزیمال و گلد و کازامی  22
3-1 تولید کد ماکزیمال  23
3-2 تولید کد گلد  28
3-3 تولید کد کازامی  32
فصل چهارم : مروری بر سیستمهای دستیابی چندگانه تقسیم کد  36
4-1 مقدمه  37
4-2 سیستمهای دستیابی چندگانه تقسیم کد  38
4-3 مزایای سیستمهای دستیابی چندگانه تقسیم کد  40
4-4 نگاهی به مخابرات سیار  41
4-5 طریقه¬ی مدولاسیون  46
4-6 پدیده دور- نزدیک  46
4-7 استفاده از شکل موجهای مناسب CDMA  49
4-8 بررسی مساله¬ی تداخل بین کاربران  49

فصل پنجم : مراحل و نتایج شبیه سازی  50
5-1 مقدمه  51
5-2 بررسی کد ماکزیمال در شبیه سازی  52
5-3 بررسی کد گلد در شبیه سازی  57
5-4 بررسی کد کازامی در شبیه سازی  62
5-5 عملکرد خطای بیت  66

شکلها
شکل (1-1) شکل موج گسترش یافته  5
شکل (1-2) مدار شیفت رجیستر  11
شکل (2-2) بلوک دیاگرام یک سیستم DSSS  14
شکل (2-3) بلوک دیاگرام یک فیدبک شیفت رجیستر  16
شکل (3-1) چگونگی ترکیب کد ماکزیمال با داده ها  23
شکل (3-2) تولید کد ماکزیمال با استفاده از شیفت رجیستر  24
شکل (3-3) تابع همبستگی کد ماکزیمال  25
شکل (3-4) تابع همبستگی متقابل با طول دنباله31 و تعداد 100 کاربر  26
شکل (3-5) تابع همبستگی متقابل با طول دنباله63 و تعداد 100 کاربر  27
شکل (3-6) نحوه¬ی تولید کد گلد  28
شکل (3-7) تابع خود همبستگی و همبستگی متقابل با طول دنباله 31 و تعداد 50 کاربر  29
شکل (3-8) تابع خود همبستگی و همبستگی متقابل با طول دنباله 31 و تعداد 100 کاربر  30
شکل (3-9) تابع خود همبستگی و همبستگی متقابل با طول دنباله 63 و تعداد 50 کاربر  31
شکل (3-10) نحوه¬ی تولید کد کازامی  32
شکل (3-11) تابع خود همبستگی و همبستگی متقابل با طول دنباله 31 و k=2 , m=-1  33
شکل (3-12) تابع خود همبستگی و همبستگی متقابل با طول دنباله 31 و k=-1 , m=10  34
شکل (3-13) تابع خود همبستگی و همبستگی متقابل با طول دنباله 31 و k=-4 , m=4  35


شکل (4-1) مدل سیستم دستیابی چندگانه تقسیم کد  38
شکل (4-2) تقسیم بندی سیستم دستیابی چندگانه تقسیم کد  39
شکل (4-3) هدف سیستم دستیابی چندگانه تقسیم کد  41
شکل (4-4) نمونه¬ای از مخابرات سلولی  42
شکل ( 4-5) مدلهای مختلف سیستمهای چندگانه  45
شکل (4-6) اثر پدیده دور- نزدیک  47
شکل (5-1) فرستنده CDMA  51
شکل (5-2) گیرنده CDMA  52
شکل (5-3) سیگنال مدولاسیون BPSK همراه fft سیگنال برای 40 کاربر  53
شکل (5-4) سیگنال CDMA همراه fft سیگنال برای 40 کاربر  53
شکل (5-5) سیگنال غیر گسترش یافته در گیرنده همراه fft سیگنال برای 40 کاربر  53
شکل (5-6) سیگنال دمدولاسیون BPSK در گیرنده همراه fft سیگنال برای 40 کاربر  53
شکل (5-7) نمودار BER برای 40 کاربر کد ماکزیمال  54
شکل (5-8) سیگنال مدولاسیون BPSK همراه fft سیگنال برای 80 کاربر  55
شکل (5-9) سیگنال CDMA همراه fft سیگنال برای 80 کاربر  55
شکل (5-10) سیگنال غیر گسترش یافته در گیرنده همراه fft سیگنال برای 80 کاربر  55
شکل (5-11) سیگنال دمدولاسیون BPSK در گیرنده همراه fft سیگنال برای 80 کاربر  55
شکل (5-12) نمودار BER برای 80 کاربر کد ماکزیمال  56
شکل (5-13) روش بدست آوردن کد گلد  57
شکل (5-14) سیگنال مدولاسیون BPSK همراه fft سیگنال برای 40 کاربر  58
شکل (5-15) سیگنال CDMA همراه fft سیگنال برای 40 کاربر  58
شکل (5-16) سیگنال غیر گسترش یافته در گیرنده همراه fft سیگنال برای 40 کاربر  58
شکل (5-17) سیگنال دمدولاسیون BPSK در گیرنده همراه fft سیگنال برای 40 کاربر  58
شکل (5-18) نمودار BER برای 40 کاربر کد گلد  59
شکل (5-19) سیگنال مدولاسیون BPSK همراه fft سیگنال برای 80 کاربر  60
شکل (5-20) سیگنال CDMA همراه fft سیگنال برای 80 کاربر  60
شکل (5-21) سیگنال غیر گسترش یافته در گیرنده همراه fft سیگنال برای 80 کاربر  60
شکل (5-22) سیگنال دمدولاسیون BPSK در گیرنده همراه fft سیگنال برای 80 کاربر  60
شکل (5-23) نمودار BER برای 80 کاربر کد گلد  61
شکل (5-24) سیگنال مدولاسیون BPSK همراه fft سیگنال برای 40 کاربر  62
شکل (5-25) سیگنال CDMA همراه fft سیگنال برای 40 کاربر  62
شکل (5-26) سیگنال غیر گسترش یافته در گیرنده همراه fft سیگنال برای 40 کاربر  62
شکل (5-27) سیگنال دمدولاسیون BPSK در گیرنده همراه fft سیگنال برای 40 کاربر  62
شکل (5-28) نمودار BER برای 40 کاربر کد کازامی  63
شکل (5-29) سیگنال مدولاسیون BPSK همراه fft سیگنال برای 80 کاربر  64
شکل (5-30) سیگنال CDMA همراه fft سیگنال برای 80 کاربر  64
شکل (5-31) سیگنال غیر گسترش یافته در گیرنده همراه fft سیگنال برای 80 کاربر  64
شکل (5-32) سیگنال دمدولاسیون BPSK در گیرنده همراه fft سیگنال برای 80 کاربر  64
شکل (5-33) نمودار BER برای 80 کاربر کد کازامی  65
شکل (5-34) مقایسه سه کاربر برای کد ماکزیمال  68
شکل (5-35) مقایسه سه کاربر برای کد گلد  69
شکل (5-36) مقایسه سه کاربر برای کد کازامی  70
شکل (5-37) مقایسه سه کد برای 40 کاربر  71
شکل (5-38) مقایسه سه کد برای 80 کاربر  72
جدول (2-1) مقدیری از دنباله¬های ماکزیمال  18



[1] R.L Peterson , R.E Zimer and D.E Borth , introduction to spread spectrum communications , prentice hall 1995.
[2] S.Glisic and B.Vucetio , spread spectrum CDMA systems for wirless communication , Altech , Nor Wood , MA , 1997.
[3] الکس ، وبلیوم و ساواسه تانتارانتا . مترجم : دکتر محمد ابطحی . تئوری و کاربرد سیستم¬های طیف گسترده . موسسه فرمبنایی نص .
[4] E.J,Groth , "Generation of binary sequence with controllable complexity" , IEEE Trans , inf . Teory , Vol . IT-17 . no.3 , p.p.288-269, May 1971.
[5] S.W.Golomb , shift register sequence , revised ED , Langune Hills , CA : Aegean park press , 1982.
[6] C.P.Pfleeger , Security in coputing , Englewood cliffs , Nj : prentice Hall , 1989.
[7] Mohamad A.Landolsi  and Wayne E.stark , "DS-CDMA chip waveform design for minimal interference under bandwidth , phase and envelop constraint "IEEE Transations on communications , Vol.47 , no.11 , November 1999.
[8] Shu-Ming Tseng and Mark R.Bell , "Asyncchronous Multicarrier DS-CDMA Using Mutually Orthognonal Complementary Sets of Sequnces" IEEE Transaction on Communication , Vlol.48 , No.1 , janury 2000 .
[9] G.Giunta , "Basic.note on Spread Spectrum CDMA Signals" , Rome , May 2000 .
[10] Fatih Alagoz , "Optimum Multiuser Detection in CDMA system" power point.
[11] S.Das , S.Ganu , N.Rivera , R.Roy , "Performance Analysis of Downlink Power Control Algorithm for CDMA system" power point .
[12] Robert AKL , D.Sc . "Departmenet of Computer Scince and Engineering" power point .
[13] Saraswathi Pulakurty , "Exploration of multi-user Detection Techniques for MC-CDMA" , 12th April 2004 .
[14] Soshant Bal , "on the of Cancellation order is Successive Interference Cancellation for CDMA systems" power point .
[15] www.umtsword.com/CDMA overview.
[16] www.tsp.ece.mcgill-ca/telecom/Dos/CDMA  technology.
[17] www.peaple.seas.harvard.eda/~  jones/Code Division Multiple Access-CDMA .
[18] Nazmul Islam , "Simulation of Asynchronous CDMA" , SID#230-85-1670 , E.CE Dept , Vivginia Tech .