کدینگ

واحد شهر مجلسی :موضوع سمینار کدینگ ‏Coding :تهیه و ارائه مبین فرهانی پور کارشناسی ارشد مخابرات -سیستم 911114536 ‏Eng.farhani.irib@hotmail.com 2 کدینگ ( :کد کردن منابع اطالعات ) فرآیند یا پروسه ای است که خروجی یک منبع اطالعات رابه یک دنباله ی باینری تبدیل می کند کلمه کد با طول متغیر پیام ورودی کد کننده ی منبع دنباله های سیمبل های تولید شده توسط منبع اطالعات می باشد و کد کننده به قالب های سمبل ها .کلمات کد باینری با طول متغیر را نسبت داده و در خروجی خود یک دنباله ی باینری تولید میکند. کد بهینه :کدی است که به طور یکتا و بدون ابهام قابل کشف است و متوسط طول کلمات کد حداقل باشد که از الگوریتم های متفاوت استفاده می کنیم .از جمله کد فانو- شانون که یک کد شبه بهینه و کد هافمن که یک کد بهینه است . نامساوی کرافت :در روبه رو یک منبع نشان داده شده است: . پیام های تولید شده توسط منبع احتمال تولید پیام طول کلمات کد ‏ m1, , mq  ‏ ‏ ‏x  p1, ,pq  ‏ n , , n  ‏q  ‏ 1 شرط الزم و کافی برای وجود یک کد قابل کشف (لحظه ای) آنست که : طول کلمه ی کد پیام از روابط روبه رو به دست می آید : ‏1 ‏ni ‏q ‏2 ‏i 1 ‏ni ‏mi 1 ‏pi 2 ‏ni log ولی چون طول کلمات کد باید صحیح باشد پس : 1 ‏pi 2 ‏ni 1 log 1 ‏pi 2 این نامساوی نشان میدهد که هر چه احتمال وقوع پیام کمتر باشد طول کلمه ی کد متناظر با آن بیش تر می باشد و بر عکس . کدهای بهینه و شبه بهینه :منبع رو به رو را در نظر بگیرید : ‏ m1, , mq  ‏x  ‏ ‏ p1, , pq  ‏log فرض میکنیم احتمال وقوع پیام ها به صورت p1  p2   pq باشد .هم چنین پیام miمرکب از Nسمبل باشد .آنگاه می توان تعداد ‏HˆN متوسط بیت بر سیمبل به کار برده شده که با. نمایش میدهیم را از رابطه ی روبه رومحاسبه کرد: ‏q ‏ni pi ‏ ‏i ‏1 1 ‏HˆN  ‏N ‏q 1 ‏pi log ‏ ‏pi ‏i 1 1 ‏ ‏N ‏GN بهره ی کدینگ :از رابطه ی زیر محاسبه می گردد : آنتروپی منبع وابسته تعداد متوسط بیت برسیمبل به یک نزدیک تر است . هر چه Nبزرگتر باشد اگر Nبه سمت بی نهایت میل Nکند Hبه Hنزدیک تر می شود . وبهره ی کدینگ 1می گردد .اما این امر یک مشکل عملی دارد .زیرا زمان زیادی برای ارسال پیام های منبع می طلبد. ‏H ‏ ‏HˆN هدف :فرض کنید ورودی کد کننده یکی از qپیام منبع باشند .می خواهیم به جای پیام iام یعنی miیک کد باینری یکتا Ciبا طول متغیر niجای گزین کنیم . که ‏Ci ni برای i=1,….,qمی باشد. و هدف محاسبه ی مراحل روش کد فانو – شانون : - 1سیمبل ها را به ترتیب احتمال می نویسیم : ‏p1  p2 ......  pq -2طول کلمه ی کد iام است باni به طوری که 1i q 1 1 ‏log ni 1 log ‏pi ‏pi بنا بر این در مر حله ی دوم طول کلمات کد را برای تمام پیام ها محاسبه می کنیم. -3محاسبه ی ‏FK برای تمام پیام ها با استفاده از رابطه ی زیر : ‏F1 0 ‏F2 F1  P1 ‏ ‏FK FK  1  PK  1 ‏FK 1 FK  PK  -4کلمه ی کد iام یعنی Cبسط باینری FKاست تاni ‏i رقم . ‏Ci  FK  binary , خواص الگوریتم فانو-شانون : -1طول کلمه ی کد با احتمال وقوع پیام نسبت عکس دارد . -2کلمه ی کد iام یعنی Cحد اقل در یک بیت با سایر کلمات کد که بعد از آن می آیند ‏i اختالف خواهند داشت .بنابر این پیام ها به طور یکتا قابل کشف خواهند بود.  - 3تعداد متوسط بیت بر سیمبل که توسط کد کننده به کار می رود در رابطه ی زیر صدق می کند : 1 ˆ ‏GN HN GN  ‏N 1 ) p (mi 2 که باشد . ‏1 ‏p(mi )log ‏ ‏N i ‏GN  Gاز فرمول گفته شده محاسبه می شود و بیانگر اطالعات موجود در هر سیمبل می ‏N برای اثبات این رابطه کافیSست طرفیSن نامساوی فوق را iدرP ضرب کرده و برای تمام iها جمع کنیم : 1 ‏Pi 2 ‏q ‏q 1 ‏Pi 2 ‏q 1 ‏Pi 2 1 ‏Pi 2 1 ˆ ‏log ni 1 log   Pi log  Pi ni 1  Pi log  GN HN  GN ‏N ‏i 1 ‏i 1 ‏i 1 : یادآوری :بسط باینری عدد اعشاری . 534نشان داده شده است .منظور از بسط باینری همان انتقال از مبنای 10به مبنای 2می باشد . مثال : ‏ .534 10  ? 2 .534* 2 1.068 .068 1 .068* 2 .136 .136  0 .136* 2 .272 .272 0 .272* 2 .544 .544 0 .544* 2 1.0888 .088 1 ‏ ‏ .534 10  10001 همان طور که در مثال باال نشان داده شده است عدد در مبنای 10را در 2ضرب کرده .و به صورت حاصل جمع قسمت اعشار و صحیح می نویسیم .سپس قسمت اعشار را دوباره در 2 ضرب کرده و عینا مرحله باال را تکرار می کنیم .قسمت صحیح از باال به پایین بسط باینری را تشکیل می دهد . تمام مراحل گفته شده در الگوریتم فانو -شانون در مثال زیر توضیح داده می شود . مثال :یک کد کننده با N=1,2طراحی کنیدHˆ. N را محاسبه و بهره را در هر 2حالت به دست آورید( .منبع ایستان است) 3/4 ‏B 3/4 ‏C 2 ‏C 1/4 1/4 1 ‏A حل :برای به دست آوردن احتمال حالت های اولیه کافیست : ‏ a ‏ b ‏  1 4 ‏ 3 4 ‏3 ‏4 ‏ ‏1 ‏ 4 ‏ a ‏P ‏  P ‏    ‏ b ‏T ‏P (1) a ‏P (2) b ادامه ی حل مثال تذکر :1منظور از P (1) a ‏P (2) b همان احتمال های اولیه می باشند . ‏T ‏  تذکر :2چSون ماتریس انتقال متقارن است پس داریم : ‏ a ‏ b ‏  1 4 ‏ 3 4 ‏3 ‏4 ‏ ‏1 ‏ 4 ‏ a ‏P ‏  P ‏    ‏ b ‏T ادامه حل مثال چون این دو معادله مستقل خطی نیستند ,می توان یکی را از روی معادله ی دیگر به دست آورد. بنابر این 1معادله و دو مجهول داریم .پس از معادله کمکی =1a+bاستفاده می کنیم . 3 1 ‏a  a b 4 4 1 3 ‏a  b b 4 4 1 ‏ a b  2 ابتدا برای N=1محاسبه می کنیم .منظور پیام های تک سیمبلی است. 1 3 3 ‏P (A)    2 4 8 1 3 3 ‏P (B)    2 4 8 1 1 1 1 1 1 2 ‏P (C)        2 4 2 4 8 8 8 1 ‏A 3/4 1 1/2 1/4 2 1 ‏C ‏C 1/4 3/4 ‏B 1 2 1/2 ادامه حل مثال طبق نمودار درختی احتماالت روبه رو محاسبه میشود : 1 3 3 ‏P (A)    2 4 8 1 3 3 ‏P (B)    2 4 8 1 1 1 1 1 1 2 ‏P (C)        2 4 2 4 8 8 8 محاسبه ی طول کلمات کد : 1 ‏Pi 2 1 ‏Pi 2 ‏log ni 1 log ‏ n1 2 1 )P (A 2 ‏n1 1 log 1 )P (A 2 ‏ log به طریق مشابه ‏n2 2 ‏n3 2 مرحله ی بعد محاسبه ی ‏Fi منظور طول کد پیام تک سیمبلی دوم و سوم می باشد : 3 ‏F1 0  F2 F1  P1  F2   0 8 3 3 6 ‏F3 F2  P2    8 8 8 ادامه حل مثال حال ‏Ci بسط باینری Fiاست : در بسط باینری فقط جواب آخر نوشته شد که برای نمونه C2 ‏C2 010 ‏Ci (Fi )2 ‏C1 00 ‏C 2 01 ‏C3 11 را محاسبه می کنیم : .375* 2 .75 0 .75* 2 .5 1 .5* 2 1 0 چونn1 2 است پس تا دو رقم اعشار محاسبه می کنیم حال ˆ Hرا محاسبه می کنیم . ‏N ‏q 1 ˆ  n p ‏H ‏N ‏i i ‏N i 1 1 3 3 3 ˆ ‏H1  (2  2  2 ) 2 1 8 8 8 برای محاسبه ی H ‏ ‏HˆN باید آنتروپی منابع وابسته را نیز محاسبه کنیم : ‏q ‏H (X)  Pi Hi 1 برای حالت اول منبع : A   3  4 C  1 4 4 3 1 3 H1  log2  log24 .8113 4 4 برای حالت دوم منبع B   3  4 H  X  PH 1 1  P2H 2 C  1  H2 .8113 H .8113 ‏ ‏ ‏40.5% 2 ‏HˆN حال برای N=2محاسبه میکنیم که منظور پیام های مرکب از 2سیمبل می باشد . ابتدا Piرا برای حالت های مختلف پیام دو سیمبل محاسبه میکنیم. A 3/4 1 3/4 1/2 1/ 4 C A AC 2 1 1/ 4 C 1/ 4 C 2 3/ 4 B 3/ 4 A 1 1/2 AA 1 1/ 4 1/ 4 C C CC 1 CB 1 CA 2 2 2 1/ 4 3/ 4 B C 2 1 3/ 4 B 2 CC AC BA : طبق نمودار درختی باال mi P  mi  AA 1/2*3/4*3/4=9/32 AC ½*3/4*1/4=3/32 CC 2/32 CB 3/32 CA 3/32 BC 3/32 BB 9/32 AA BB AC CB BC CA CC 9/32 9/32 3/32 3/32 3/32 3/32 3/32 ni 2 2 4 4 4 4 4 Fi 0 0 18/32 18/32 21/32 24/32 30/32 00 01 1001 1010 1100 1101 1111 mi Pi Ci پس می توان Ĥ2را از جدول محاسبه کنیم : 1 9 9 2 2 ˆ ‏H2  (2  2  4(4 )  4 ) 1.44bit ‏symbol 2 32 32 32 32  .مثال :یک منبع مستقل دنباله ای مستقل از سمبل هارا از الفبایی مرکب از 5سمبل با احتماالت به ترتیب 4.,2.,2.,1.,1 .تولید می کند .آنتروپی را محاسبه و یک 8کد کننده منبع با اندازه ی قالب N=2طراحی کنید . محاسبه آنتروپی: ‏x5  ‏ .1  ‏x4 .1 ‏2.12bit / sym ‏x3 .2 1 ‏Pi ‏x2 .2 ‏ x1 ‏X  ‏ .4 5 ‏H (X )  Pi log2 ‏i 1 55 25 ‏N=2 پیام دو حرفی ایجاد می شود :از آنجا که 5سیمبل مستقل توسط منبع تولیSد میSشد تعداد ) P (x i y j ) P (x i ).P (y j که احتمال پیام های دو تایی عبارت است از : مثال ‏P (x1x 2 ) .4.2 .8 که در جدول بعد چند پیام از 25پیام محاسبه شده است .بقیه نیز به همین روند محاسبه می شوند پیام Pi x1x1 x1x 2 x1x 3 x 2x 4 .16 3 0 000 .08 4 .16 0010 .08 4 .24 0011 .08 4 .32 0101 .04 5 .6 1001 1 .04 5 .64 1010 0 .04 5 .68 1010 1 x 5x1 x 2x 3 x 3x 2 ni Fi Ci پیام x 2x 4 x 2x 5 x 4x 2 x 5x 2 x 3x 4 x 3x 5 x 4x 3 Pi ni 6 Fi Ci .02 6 .8 1100 11 .02 6 .82 1101 00 .02 6 .84 1101 01 .02 6 .86 1101 11 .02 6 .88 1110 00 .02 6 .9 1110 01 .02 6 .92 1110 10 مشکل انتشار خطا :عیب کد های با طول متغیر بحث انتشار خطاست .زیرا ممکن است بر اثر خطا در یک بیت نه تنها در همان کاراکتر دچار خطا شود بلکه سیمبل های بعدی نیز متاثر از این خطا شده و آنها نیز دچار خطا گردند .بنابر این اگر سرعت مهم نیست از کد هایی با طول ثابت مانند کد اسکی استفاده میشود که برای 128کاراکتر موجود روی کیبورد کامپیوتر ها از 7 بیت استفاده کند . مثال در مثال زیر برای N=2تک تک بیت ها را بررسی می کند که آیا طبق جدول متناظر با ان کدی هست یا خیر یعنی ابتدا 10را بررسی (چون کوتاهترین طول کد 2است ) سپس 100تا به 1001که کد Acاست میرسد و به این ترتیب ت آخر جلو می رود . ‏BB ‏CA ‏AA ‏CB ‏BB 0 1 1101 00 1010 01 1001011101001010 01 .حل اگر خطایی در یکی از بیت ها رخ دهد کل دنباله را تحت تاثیر قرار می دهد ‏AC 1001 دمدوله کننده دیکدر کانال های مخابراتی کانال انتقاال خروجی آنالوگ f خروجی : الفبای گسسته ی Mمرکب از سیمبل ‏c کانال آنالوگ پیوسته کانال گسسته مدوله کننده ‏d کد کننده ورودی آنالوگ ورودی :الفب ای گسسته gی مرکب M سمبلی 34 همان طو ر که در بلوک دیاگرام اسالید قبلی مشاهده شد یک سیستم مخابراتی را می توان به سه قسمت فرستنده و کانال انتقال و گیرنده تقسیم نمود که فرستنده شامل یک کد کننده و یک مدوله کننده گیرنده شامل دیکدر ودمدوله کننده می باشد .بین نقاط , gو cیک کانال گسسته که کانال کد کننده نامیده میشود و وررودی و خروجی آن دنباله ای از سیمبل ها می باشد .کانال بین dو fارتباط الکتریکی بین فرستنده و گیرنده را تامین می کند . کانال گسسته ی بدون حافظه : ‏YمGتغیر تGGGصادGفGیبGGا اGGلفبای MسGGیمبلی تابع انتقال ‏XمGتغیر تGGGصادGفGیبGGا اGGلفبایM سGGیمبلی تابع احتمال (انتقال )کانال : ‏P ‏ij :احتمال دریافت jامین سیمبل در خروجی کانال هنگامی که Iامین سیمبل به عنوان ورودی کانال از M سیمبل انتخاب شده است . ) Pij P (Y  jX i ‏i , j 1,.....,M احتمال اینکه ورودی کانال سیمبل iام باشد : ‏P  X i  Pit احتمال اینکه خروجی کانال سیمبل jام باشد : ‏M ‏ ‏ ‏M ‏Pjr P Y  j   P Y  jX i .P X i   Pij .Pit ‏i 1 ‏i 1 به دلیل وجود عوامل ناخواسته مانند نویز ممکن است خطا رخ دهد که با Peنمایش می دهند : ‏M ‏Pe P Y X   P (Y X X i ).P  X i  ‏i 1 میتوان خطا را طبق فرمول زیر محاسبه کرد ‏ m ‏ ‏P Y X X i P Y iX i   Pij  Pe    Pij .Pi t ‏ ‏ ‏i , j 1 ‏i 1  i , j 1 ‏j i ‏ j i ‏ ‏M ‏m ‏ ‏  ‏ : ) کانال باینری (دوتایی: مثال 0 0 P01  Pe    i 1  M P10  Pij  .Pi t   i ,j  1  j i  m 1 1 Pe P01.P0t  P10.P1t : P0r مثال برای محاسبه ی r j M P  Pij .Pi t P00  P0t  P01  P1t i 1 نکته :در مثال کانال باینری اگرP00 P11 کانال باینری را BSCیا متقارن می نامیم . چند تعریف :برای یک کانال گسسته ی بدون حا فظه Mتایی با دو فر آیند ورودی کانال و اغتشاش سر وکار داریم .بناببر این تعدادی آنتروپی یا محتوایاطالعاتی برای تعریف وجود دارد : ‏Pit .log2 ‏t ‏M ‏Pi ‏ ‏i ‏H  x   آ8ن8ت8رو8پیورود8یX ‏ 1 ‏Pi r ‏r ‏Pj .log2 ‏Pi t ‏M ‏ ‏j ‏H  y   آنتروپی خروجی Y ‏ 1 ‏Pi r بیانگر دریافت Iامین سیمبل در برابر است با احتمال اینکه سمبل iام به عنوان ورودی باشد و خروجی می باشد .هم چنین ) H(yبیانگر تعداد متوسط بیت بر سمبل خروجی کانال می باشد . آنتروپی شرطی که به طور متوسط ابهام موجود در مورد xرا هنگامی که مقدارyمعلوم باشد بیان می کند : ‏P (X  ) i Y j 2 ‏M M ‏H (X Y )   P (X i ,Y  j ).log ‏i 1 j 1 بنابر این می توان آنتروپی مشترک را به صورت زیر تعر8یف کرد ) H (X ,Y ) H (XY)  H(Y) H (Y X )  H(X می دانیم به دلیل وجود نویز اطالعات در کانل ممکن است گم شود که )H (XY در مورد آنچه فرستنده می فرستد خواهد بود که شرایط مرزی ابهام یا به حد اقل خود میرسد یعنی 0و یا هیچ از ابهام کم نمی شود. بیانگر مقدار ابهام گیرنده مثال :یک کانال غیر متقارن نشان داده شده است . الف )اگر P(X=0)=1/4و P(X=1)=3/4و  .9 a=..75و 0 1  1  1 )H (X مطلوبست ) H(Y ) H (XY )H (Y X 0 1 : فرمول های به کار برده شده در حل مسئله M  M  :حل Pjr P Y  j   P Y  jX i .P X i   Pij .Pit i 1 H  x   M Pi  i t i 1 Pit .log2  1 H  y   M  j  1 Pjr Pi r .log2 H (X ) H (1/ 4,3/ 4) 1/ 4log4 3/ 4log4/ 3 .8113bit / sym H (Y ) ? P (Y 0) P (Y 0 X 0).P(X 0)  P (Y 0 X 1).P(X 1) 1/ 4  3/ 4 1   .2625 P (Y 1) 1 P (Y 0) .7375 H (Y ) H (.2625,.7375) .8305 M M P (X xi Y y j ) H (X Y )    P (X i i ,Y Y j ).log2 i 1 j 1 P (x 0,Y 0) P (Y 0 X 0).P(X 0)  1/ 4 .1875 P (X 1,Y 1) P (Y 1X 1).P(X 1)  3/ 4 .675 P(X 0,Y 1) P(Y  1X 0).P (X 0) (1  ) 1/ 4 .06258 P (X 1,Y 0) P(Y 0 X 1).P (X 1) (1  ) 3/ 4 .075 P (x 0,Y 0) .1875 P (x 0,Y 0)   .7143 P (Y 0) .2625 P (X 1,Y 1) .675 P (X 1,Y 1)   .9153 P (Y 1) .7375 P(X 0,Y 1) .625 P(X 0,Y 1)   .0847 P (Y 1) .7375 P (X 1,Y 0) .075 P (X 1,Y 0)   .2857 P (Y 0) .2625 H (X Y ) .5353bit / sym .تمام مراحل مانند قبلی است که به اختصار جواب آخر نوشته شد M L H (Y  X )   P (x x i , y  y j ).logP (y  y j x x i ) i 1 j 1 H (Y  X ) .5564bit / sym