کدینگ

کدینگ

اسلاید 1: واحد شهر مجلسیموضوع سمینار :کدینگCodingتهیه و ارائه :مبین فرهانی پورکارشناسی ارشد مخابرات - سیستم911114536Eng.farhani.irib@hotmail.com2

اسلاید 2: کدینگ : ( کد کردن منابع اطلاعات )فرآیند یا پروسه ای است که خروجی یک منبع اطلاعات رابه یک دنباله ی باینری تبدیل می کندورودی کد کننده ی منبع دنباله های سیمبل های تولید شده توسط منبع اطلاعات می باشد و کد کننده به قالب های سمبل ها .کلمات کد باینری با طول متغیر را نسبت داده و در خروجی خود یک دنباله ی باینری تولید میکند.پیامکلمه کد با طول متغیر

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

اسلاید 4: شرط لازم و کافی برای وجود یک کد قابل کشف (لحظه ای) آنست که : طول کلمه ی کد پیام از روابط روبه رو به دست می آید :

اسلاید 5: ولی چون طول کلمات کد باید صحیح باشد پس : این نامساوی نشان میدهد که هر چه احتمال وقوع پیام کمتر باشد طول کلمه ی کد متناظر با آن بیش تر می باشد و بر عکس . کدهای بهینه و شبه بهینه : منبع رو به رو را در نظر بگیرید :

اسلاید 6: فرض میکنیم احتمال وقوع پیام ها به صورت باشد . هم چنین پیام مرکب از N سمبل باشد . آنگاه می توان تعداد متوسط بیت بر سیمبل به کار برده شده که با. نمایش میدهیم را از رابطه ی روبه رومحاسبه کرد:

اسلاید 7: بهره ی کدینگ: از رابطه ی زیر محاسبه می گردد : هر چه N بزرگتر باشد به یک نزدیک تر است . اگر N به سمت بی نهایت میل کند به H نزدیک تر می شود . وبهره ی کدینگ 1 می گردد. اما این امر یک مشکل عملی دارد. زیرا زمان زیادی برای ارسال پیام های منبع می طلبد. آنتروپی منبع وابستهتعداد متوسط بیت برسیمبل

اسلاید 8: هدف : فرض کنید ورودی کد کننده یکی از q پیام منبع باشند. می خواهیم به جای پیام iام یعنی یک کد باینری یکتا با طول متغیر جای گزین کنیم . که هدف محاسبه ی و برای i=1,….,q می باشد. مراحل روش کد فانو – شانون : 1-سیمبل ها را به ترتیب احتمال می نویسیم :

اسلاید 9: 2-طول کلمه ی کد i ام است با به طوری که بنا بر این در مر حله ی دوم طول کلمات کد را برای تمام پیام ها محاسبه می کنیم.3- محاسبه ی برای تمام پیام ها با استفاده از رابطه ی زیر :

اسلاید 10: 4- کلمه ی کد i ام یعنی بسط باینری است تا رقم .خواص الگوریتم فانو-شانون :1- طول کلمه ی کد با احتمال وقوع پیام نسبت عکس دارد . 2-کلمه ی کد i ام یعنی حد اقل در یک بیت با سایر کلمات کد که بعد از آن می آیند اختلاف خواهند داشت. بنابر این پیام ها به طور یکتا قابل کشف خواهند بود.

اسلاید 11: 3- تعداد متوسط بیت بر سیمبل که توسط کد کننده به کار می رود در رابطه ی زیر صدق می کند :که از فرمول گفته شده محاسبه می شود و بیانگر اطلاعات موجود در هر سیمبل می باشد .

اسلاید 12: برای اثبات این رابطه کافیست طرفین نامساوی فوق را در ضرب کرده و برای تمام i ها جمع کنیم ::

اسلاید 13: یادآوری : بسط باینری عدد اعشاری 534. نشان داده شده است . منظور از بسط باینری همان انتقال از مبنای 10 به مبنای 2 می باشد . مثال :

اسلاید 14: همان طور که در مثال بالا نشان داده شده است عدد در مبنای 10 را در 2 ضرب کرده . و به صورت حاصل جمع قسمت اعشار و صحیح می نویسیم . سپس قسمت اعشار را دوباره در 2 ضرب کرده و عینا مرحله بالا را تکرار می کنیم . قسمت صحیح از بالا به پایین بسط باینری را تشکیل می دهد . تمام مراحل گفته شده در الگوریتم فانو- شانون در مثال زیر توضیح داده می شود .

اسلاید 15: مثال : یک کد کننده با N=1,2 طراحی کنید . را محاسبه و بهره را در هر 2 حالت به دست آورید. (منبع ایستان است) حل : برای به دست آوردن احتمال حالت های اولیه کافیست : 12CC1/41/43/4B3/4A

اسلاید 16: ادامه ی حل مثال تذکر 1: منظور از همان احتمال های اولیه می باشند . تذکر 2: چون ماتریس انتقال متقارن است پس داریم :

اسلاید 17: ادامه حل مثالچون این دو معادله مستقل خطی نیستند, می توان یکی را از روی معادله ی دیگر به دست آورد. بنابر این 1 معادله و دو مجهول داریم . پس از معادله کمکی 1a+b= استفاده می کنیم .

اسلاید 18: ابتدا برای N=1 محاسبه می کنیم . منظور پیام های تک سیمبلی است. 1121123/4A1/4C1/4C3/4B1/21/2

اسلاید 19: ادامه حل مثالطبق نمودار درختی احتمالات روبه رو محاسبه میشود :محاسبه ی طول کلمات کد :

اسلاید 20: به طریق مشابه مرحله ی بعد محاسبه ی می باشد : منظور طول کد پیام تک سیمبلی دوم و سوم

اسلاید 21: ادامه حل مثالحال بسط باینری است :در بسط باینری فقط جواب آخر نوشته شد که برای نمونه را محاسبه می کنیم :

اسلاید 22: چون است پس تا دو رقم اعشار محاسبه می کنیم حال را محاسبه می کنیم . برای محاسبه ی باید آنتروپی منابع وابسته را نیز محاسبه کنیم :

اسلاید 23: : برای حالت اول منبعبرای حالت دوم منبع

اسلاید 24: حال برای N=2 محاسبه میکنیم که منظور پیام های مرکب از 2 سیمبل می باشد . ابتدا را برای حالت های مختلف پیام دو سیمبل محاسبه میکنیم.

اسلاید 25: 11122122212211/21/23/4A3/41

اسلاید 26: طبق نمودار درختی بالا : AA1/2*3/4*3/4=9/32AC½*3/4*1/4=3/32CC2/32CB3/32CA3/32BC3/32BB9/32

اسلاید 27:

اسلاید 28: پس می توان را از جدول محاسبه کنیم :

اسلاید 29: مثال : یک منبع مستقل دنباله ای مستقل از سمبل هارا از الفبایی مرکب از 5 سمبل با احتمالات. به ترتیب . 1,.1,.2,.2,.4 تولید می کند . آنتروپی را محاسبه و یک کد کننده منبع با اندازه ی قالب N=2 طراحی کنید .محاسبه آنتروپی:N=2 : از آنجا که 5 سیمبل مستقل توسط منبع تولید میشد تعداد پیام دو حرفی ایجاد می شود که احتمال پیام های دو تایی عبارت است از :مثلا که در جدول بعد چند پیام از 25 پیام محاسبه شده است . بقیه نیز به همین روند محاسبه می شوند

اسلاید 30: پیامپیام6.1630000.026.8110011.084.160010.026.82110100.084.240011.026.84110101.084.320101.026.86110111.045.610011.026.88111000.045.6410100.026.9111001.045.6810101.026.92111010

اسلاید 31: مشکل انتشار خطا : عیب کد های با طول متغیر بحث انتشار خطاست . زیرا ممکن است بر اثر خطا در یک بیت نه تنها در همان کاراکتر دچار خطا شود بلکه سیمبل های بعدی نیز متاثر از این خطا شده و آنها نیز دچار خطا گردند . بنابر این اگر سرعت مهم نیست از کد هایی با طول ثابت مانند کد اسکی استفاده میشود که برای 128 کاراکتر موجود روی کیبورد کامپیوتر ها از 7 بیت استفاده کند . مثلا در مثال زیر برای N=2 تک تک بیت ها را بررسی می کند که آیا طبق جدول متناظر با ان کدی هست یا خیر یعنی ابتدا 10 را بررسی (چون کوتاهترین طول کد 2 است ) سپس 100تا به 1001که کد Acاست میرسد و به این ترتیب ت آخر جلو می رود . AC BB CA AA CB BB 0 1 1101 00 1010 01حل اگر خطایی در یکی از بیت ها رخ دهد کل دنباله را تحت تاثیر قرار می دهد . 100101110100101001

اسلاید 32: کانال های مخابراتی کد کنندهمدوله کنندهکانال انتقاالدمدوله کنندهدیکدر کانال گسسته ورودی :الفبای گسسته ی مرکب M سمبلی خروجی : الفبای گسسته ی مرکب از M سیمبل ورودی آنالوگخروجی آنالوگکانال آنالوگ پیوستهg

اسلاید 33: همان طو ر که در بلوک دیاگرام اسلاید قبلی مشاهده شد یک سیستم مخابراتی را می توان به سه قسمت فرستندهو کانال انتقال و گیرنده تقسیم نمود که فرستنده شامل یک کد کننده و یک مدوله کننده گیرنده شامل دیکدرودمدوله کننده می باشد . بین نقاط g ,و c یک کانال گسسته که کانال کد کننده نامیده میشود و وررودی و خروجیآن دنباله ای از سیمبل ها می باشد . کانال بین d و f ارتباط الکتریکی بین فرستنده و گیرنده را تامین می کند . کانال گسسته ی بدون حافظه : تابع احتمال (انتقال )کانال : :احتمال دریافت j امین سیمبل در خروجی کانال هنگامی که I امین سیمبل به عنوان ورودی کانال از M سیمبل انتخاب شده است . 34تابع انتقال Yمتغیر تصادفی با الفبای M سیمبلیXمتغیر تصادفی با الفبای M سیمبلی

اسلاید 34: احتمال اینکه ورودی کانال سیمبل i ام باشد :احتمال اینکه خروجی کانال سیمبل j ام باشد :به دلیل وجود عوامل ناخواسته مانند نویز ممکن است خطا رخ دهد که با نمایش می دهند : میتوان خطا را طبق فرمول زیر محاسبه کرد

اسلاید 35: مثال : کانال باینری (دوتایی) :مثلا برای محاسبه ی : 001

اسلاید 36: نکته : در مثال کانال باینری اگر کانال باینری را BSC یا متقارن می نامیم .چند تعریف : برای یک کانال گسسته ی بدون حا فظه M تایی با دو فر آیند ورودی کانال و اغتشاش سر وکار داریم . بناببر این تعدادی آنتروپی یا محتوایاطلاعاتی برای تعریف وجود دارد : Xآنتروپی ورودی آنتروپی خروجی Yبرابر است با احتمال اینکه سمبل i ام به عنوان ورودی باشد و بیانگر دریافت I امین سیمبل در خروجی می باشد . هم چنین H(y ) بیانگر تعداد متوسط بیت بر سمبل خروجی کانال می باشد .

اسلاید 37: آنتروپی شرطی که به طور متوسط ابهام موجود در مورد x را هنگامی که مقدارyمعلوم باشد بیان می کند :بنابر این می توان آنتروپی مشترک را به صورت زیر تعریف کرد

اسلاید 38: می دانیم به دلیل وجود نویز اطلاعات در کانل ممکن است گم شود که بیانگر مقدار ابهام گیرنده در مورد آنچه فرستنده می فرستد خواهد بود که شرایط مرزی ابهام یا به حد اقل خود میرسد یعنی 0 و یا هیچ از ابهام کم نمی شود.

اسلاید 39: مثال : یک کانال غیر متقارن نشان داده شده است . الف )اگر P(X=0)=1/4و P(X=1)=3/4 و a=..75 و مطلوبست 0

اسلاید 40: حل: فرمول های به کار برده شده در حل مسئله :

اسلاید 41:

اسلاید 42: تمام مراحل مانند قبلی است که به اختصار جواب آخر نوشته شد.