نظریۂ اطلاعات

اصطلاح	term
معطیات ابلاغیات تخزین متعبر دابی	data communication store reliable compress

نظریۂ اطلاعات (information theory) شاخ ہے اطلاقی ریاضیات اور برقی ہندسیہ کی، جو اطلاعات کے مقداری تعین سے متعلق ہے۔ تاریخی طور پر، نظریہ اطلاعات کو کلاڈ شانن نے ترقیا، معطیات کو ابلاغنے اور متعبر تخزین کے لیے دابنے کی بنیادی حدود جاننے کے لیے۔ اپنے آغاز سے، اس کا دائرہ دوسرے علاقوں میں وسیع ہو گیا ہے، جس میں شامل ہیں احصائی اِستنتاج، قدرتی زبان عملیات، اخفی‌اشفی اور جامعاً، ابلاغی نیٹ ورکوں کے علاوہ دوسرے نیٹ ورک — جیسا کہ عصبیات، سالماتی رموز کا ارتقا، اور فنکشن بيئيات میں مثیل کا انتخاب، حرارتی طبیعیات، مقداریہ شمارندگی، علمی سرقہ کا انکشاف، اور معطیاتی تحلیل کی دوسری اقسام۔

نظریہ اطلاعات میں ایک کلیدی ناپ درمائلت کہلاتا ہے، جو عام طور پر ابلاغیت یا تخزین کے لیے درکار تثمات کی اوسط تعداد اظہار کیا جاتا ہے۔ وجدانی طور پر، درمائلت کسی تصادفی متغیر سے مٹھ بھیڑ پر لاتیقن کی مقدار بتاتا ہے۔ مثلاً، ایک کھرے سکہ کے اُچھالنے (دو برابر امکانی نتائج) پر درمائلت طاس کے لڑکھانے (چھ برابر امکانی نتائج) سے کم ہو گی۔

نظریہ اطلاعات کی اطلاقیات کے بنیادی موضوعات میں شامل ہیں بغیر خسارہ معطیاتی دابیت (مثال، ZIP ملف)، خساری معطیاتی دابیت (مثال MP3) اور رودبار رمزیہ (مثال: DSL لکیریں)۔ یہ شعبہ ریاضیات، احصاء، طبیعیات، شمارندی سائنس، عصبیات اور برقی ہندسیہ کے قاطع پر ہے۔ اس کا اثر گہری فضاء کے وائجر سفارت کی کامیابی، قرص کی ایجاد، محمول کا ممکن ہونے، جالکار کی ترقی، لسانیات اور انسانی آگاہی، ثقب اسود کی سمجھ بوجھ اور بہت سے دوسرے میدانوں میں، پر ہوا۔ نظریہ اطلاعات کے اہم ذیلی میدان ہیں، منبع ترمیز، رودبار ترمیز، نظریہ الخوارزمی پچیدگی اور اطلاعات کے ناپ۔

اصطلاح	term
ترمیز منبع رودبار اکھڑپن دابیت شوریلا	coding source channel robustness compression noisy

جائزہ

نظریہ اطلاعات کے بنیادی تصورات کو گرفت میں لانے کے لیے توجہ کرو انسانی ابلاغیات کا کثیر ترین وسیلہ: زبان۔ زبان کے دو اہم پہلو ذیل ہیں: پہلا، سب سے عام الفاظ (مثلاً ہے، کا) چھوٹے ہونے چاہیے ہیں ایسے الفاظ سے جو نسبتاً کم عام ہوں (مثلاً جمہوریت، کمینہ)، تا کہ جملے بہت لمبے نہ ہوں۔ اس طرح لفظ کی لمبائی میں تجارت ایسی ہی ہے جیسے معطیات دابیت اور منبع ترمیز کا لازمی پہلو ہے۔ دوسرا، اگر جملہ کا کچھ حصہ سنا نہ جا سکا ہو یا غلط سمجھ میں آیا ہو شور کی وجہ سے — جیسے گزرتی گاڑی کی وجہ سے — تو سامع پھر بھی جملہ کا معنی اخذ کر سکے۔ اس طرح کا اکھڑپن برقی ابلاغیات کے لیے لازم ہے جس طرح یہ زبان کے لیے ہے؛ صحیح طریقہ سے یہ اکھڑپن ابلاغیات میں ڈالنا رودبار ترمیز سے کیا جاتا ہے۔ منبع ترمیز اور رودبار ترمیز بنیادی معاملات ہیں نظریہ اطلاعات کے ۔

خیال رہے کہ ان معاملات کا پیغامات کی اہمیت سے کوئی تعلق نہیں۔ مثال کے طور پر، رسمی فقرہ " شکریہ؛ دوبارہ آئیے گا" کو لکھنے میں تقریباً اتنا ہی وقت درکار ہوتا ہے جتنا کہو کہ ایک فوری درخواست کی صدا، "ہسپتال لے چلو!"، جبکہ صاف طور پر آخرالذکر کی اہمیت زیادہ ہے اور زیادہ با معنی ہے۔ نظریہ اطلاعات میں پیغام کا مطلب یا اہمیت پر توجہ نہیں دی جاتی، چونکہ یہ معاملات ڈیٹا کی کیفیت سے متعلق ہیں نہ کہ مقدار یا ڈیٹا کے قابل پڑھ سے ؛ آخر الذکر صرف احتمالات سے جبر ہوتی ہے۔

نظریہ اطلاعات کی بنیاد کلاڈ شانن نے 1948ء میں اپنے تخمی کام ابلاغیات کا ریاضیاتی نظریہ سے رکھی۔ اس نظریہ کا نمونہ ہندسیہ میں شوریلی رودبار پر اطلاعات کی ترسیل ہے۔ اس نظریہ کا سب سے بنیادی نتیجہ شانن کا منبع ترمیز قضیہ ہے، جو قائم کرتا ہے کہ کسی لاتیقن واقعہ کو نمائندہ کرنے کے لیے تثمات کی اوسط تعداد اس واقعہ کی درمائلت کے برابر ہے؛ اور شانن کا شوریلی-رودبار ترمیز قضیہ، جو بیان کرتا ہے کہ شوریلی رودبار پر متعبر ابلاغ ممکن ہے بشرط کہ ابلاغیات کی شرح ایک خاص عتبہ سے کم رکھی جائے، جسے گنجائشِ رودبار کہتے ہیں۔ گنجائشِ رودبار تک پہنچایا جا سکتا ہے مناسب رمزی اور کشف رمزی نظامات کے استعمال سے ۔

نظریہ اطلاعات کا خالص اور اطلاقی شعبوں کے مجموعہ سے قریبی تعلق ہے جن کی پچھلی نصف صدی میں تفتیش کر کے انھیں ہندسیہ ممارست میں لایا گیا ہے مختلف سُرخیوں سے : نظامِ تلاوم، نظام پیش بندی، مصنوع ذہانت، پیچیدہ نظام، علم پچیدگی، سیادیات، معلومیات، آلاتی تعلم اور نظاماتی سائنس کے بیشتر تفاصیل۔ نظریہ اطلاعات وسیع اور گہرا ریاضیاتی نظریہ ہے، جس جے اتنے ہی وسیع اور گہرے اطلاقیات ہیں، جن میں شامل نظریہ ترمیز کا حیوی میدان ہے۔

نظریہ ترمیز ایسے قطعی طرائق ڈھوندنے سے متعلق ہے، جنہیں رموز کہتے ہیں، جن سے شوریلی رودبار پر ڈیٹا کے ابلاغ کی کارکردگی بڑھانے اور ابلاغ میں غلطی کی شرح کو اُس حد تک کم کرنے کی کوشش کی جاتی ہے جس کا شانن نے ثبوت دیا تھا کہ یہ اس رودبار کے لیے یہ کم ترین ممکن شرح ہے۔ اس رموز کو تقسیم کیا جا سکتا ہے معطیات دابیت (رودبار ترمیز) اور غلطی درستی (رودبار ترمیز) تکانیک میں۔ آخرالذکر کے معاملہ میں شانن کے ممکن بتانے کے بہت برسوں بعد ایسے طریقے دریافت کیے جا سکے۔ نظریہ اطلاعات کے رموز کی تیسری قسم اخفااشفا الخوازم ہیں (رموز اور صفریہ)۔ نظریہ اطلاعات کے تصورات اور طرائق اخفااشفا اور اخفا تحلیل میں بہت استعمال ہوتے ہیں۔

نظریہ اطلاعات کا استعمال اطلاعات مستعاد، معلومات اکٹھگی، جؤا بازی، احصاء اور موسیقی ترکیب تک، میں بھی ہوتا ہے۔

اطلاعاتی نظریے کا عملی اطلاق WinRar اور WinZip جیسے سافٹ وئیر میں ہمیں بہتر طور پر نظر آتا ہے جو ایک بہت بڑی فائل کو بہت کم جگہہ میں سٹور کرنے کے قابل بناتے ہیں۔ اسی طرح اس تھیوری کی بدولت ہم انٹرنیٹ پر بہت کم سپیڈ کے باوجود گفتگو سن سکتے ہیں۔ طرح طرح کے ویڈیو اور آڈیو فارمیٹ اسی ٹیکنالوجی کی بنیاد پر کام کرتے ہیں جیسے .mp3 ogg gif jpeg bmp وغیرہ۔ ہر فائل فارمیٹ ہمیں معلومات کی کوالٹی اور اس کے ہارڈڈسک پر حجم کے درمیان ایک ٹریڈآف مہیا کرتا ہے۔ جیسے BMP تصویر کی کوالٹی بہتر ہو گی تو JPEG یا GIF میں وہی تصویر کم جگہہ لے گی۔

کسی پیغام کو ہم زیادہ سے زیادہ کتنا Compress یا مختصر کر سکتے ہیں اس کا انحصار اس بات پر ہے کہ اس میں معلومات کی مقدار کتنی ہے۔ اطلاعاتی نظرئے میں معلومات کی مقدار کو (انٹروپی Entropy)کہتے ہیں۔ اور اس کی اکائی بٹ (Bit) ہے۔ بڑی اکائیاں کلو بٹ(1000 بٹس) اور میگا بٹ(1000 کلو بٹ) ہیں۔

اس تھیوری کا بنیادی نقطہ یہ ہے کہ جو الفاظ زیادہ استعمال ہوتے ہیں ان کو کم حروف سے ظاہر کیا جانا چاہیے جبکہ کم استعمال ہونے والے حروف کچھ زیادہ بڑے ہوں تو بھی مذائقہ نہیں۔ ہم دیکھتے ہیں کا ہماری اپنی زبان اردو میں تمام الفاظ برابر حروف پر مشتمل نہیں۔ بکثرت استعمال ہونے والے الفاظ عموما چھوٹے ہوتے ہیں جیسے کا' کے ' کی' ہے' ہیں وغیرہ۔ ان کے مقابلے میں "دائرۃ المعارف" اور اس جیسے دوسرے کئی الفاظ جو کم استعمال ہوتے ہیں' نسبتا لمبے ہیں۔ کیا یہ بہتر نہ ہو کہ تمام الفاظ ایک سٹینڈیرڈ لمبائی کے ہوں؟ اس کا جواب ہے ' جی نہیں

جس طرح پانچوں اگلیاں برابر نہیں ہوتیں اور ہر ایک اپنی جگہہ بہترین آلہ کے طور پے موجود ہے بالکل اسی طرح کسی زبان کے الفاظ بھی بڑے جھوٹے ہونا بھی ایک نعمت ہے اور اس کے کئی فائدے ہیں اطلاعاتی نظریہ ہمیں بتاتا ہے کہ اس طرج ہم اپنی بات جلدی کہہ سکتے ہیں۔ شاید آپ کے علم ہو کہ کمپیوٹر میں الفاظ اور حروف کو زخیرہ کرنے کے لیے ہر ایک حرف ایک مقررہ لمبائی کا ہی ہوتا ہے۔ جیسے یونی کوڈ میں جو اس صفحے کے لیے استعمال ہو رہا ہے' ہر حرف کے لیے 16 ثنائی ہندسے (Bits) استعمال کرتا ہے۔ یا پھر انگریزی کا بہت مشہور کوڈ ASCII ہر حرف کے لیے 8 ثنائی ہندسے استعمال کرتا ہے۔ 1948 میں ایک امریکی الیکٹرانکس انجنئیر نے یہ نظریہ پیش کیا کہ اگر ہم ان حروف کو سٹور کرنے کے لیے ہر حرف کے لیے مختلف لمبائی کے ثنائی ہندسوں کی مدد لیں' اس طرح کہ زیادہ استعمال میں آنے والے حروف جیسے "A", "E", "I", "O" وغیر ہ کو کم سے کم ہندسوں سے اور کم استعمال ہونے والے حروف جیسے "Z", "Q" وغیرہ کو زیادہ حروف سے ظاہر کریں تو نتیجے کے طور پر ہم کسی بڑی فائل کو بہت کم جگہہ میں محفوظ کر سکتے ہیں۔

اطلاعات کی مقداریں

نظریہ اطلاعات کی اساس نظریہ احتمال اور احصاء ہیں۔ اطلاعات کی سب سے اہم مقداروں میں ہے درمائلت، یعنی تصادفی متغیر میں اطلاع کی مقدار اور باہمی اطلاع، یعنی دو تصادفی متغیروں میں مشترک اطلاع کی مقدار۔ اول الذکر یہ بتاتی ہے کہ پیغام ڈیٹا کو کتنی آسانی سے دابیت سکتا ہے اور آخرالذکر رودبار کے پار ابلاغ کی شرح ڈھونڈنے میں کام آ سکتی ہے۔

ذیل کے کلیات میں لاگرتھم کی اساس اطلاعات درمائلت کے ناپ کی اکائی جبر کرتی ہے۔ سب سے عام اکائی تثم ہے، جو اساس 2 (تثنیہ) کے لاگرتھم کے انتخاب سے ملحق ہے۔ دوسری اکائیوں میں شامل ہے قادری جو قدرتی لاگرتھم سے ملحق ہے۔

ذیل میں اظہاریہ $p\log p\,$ کو صفر سمجھا جائے گا جب بھی $p=0$ ہو۔

درمائلت

برناولی آزمائش کی درمائلت بطور کامیابی احتمال کی تفاعل، عموماً جسے ثنائی درمائلت دالہ $\ H_{\mbox{b}}(p)$ کہتے ہیں۔ اس درمائلت کی تکبیر تب ہوتی ہے جب ہر آزمائش کی درمائلت 1 تثم ہو جو اس وقت ہوتا ہے جب دونوں ممکنہ نتائج برابر امکانی ہوں، جیسا کہ ایک کھرے سکہ کے اُچھال میں۔

ایک متفرد تصادفی متغیر $X$ کی درمائلت $H$ اس متغیر $X$ کی قدر کے ساتھ مشارکہ لاتیقن کو ناپتی ہے۔ فرض کرو کہ ہزار تثمات (0 اور 1) ترسیل کیے جاتے ہیں۔ اگر آپ کی طرف ترسیل سے پہلے ہی یہ آپ کو معلوم ہیں (کسی قدر پر مطلق احتمال سے )، تو منطق کا تقاضا ہے کہ کوئی اطلاع ترسیل نہیں ہوئی۔ البتہ اگر، ہر تثم برابر امکان کے ساتھ 0 یا 1 ہے، تو 1000 تثمات ترسیل کیے گئے ہیں۔ ان دو شدتوں کے درمیان، اطلاع کی مقدار کا یوں تعین کیا جا سکتا ہے: اگر تمام ممکنہ پیغامات $\{x_{1},...,x_{n}\}$ کا طاقم $\mathbb {X}$ ہے جو $X$ ممکنہ طور پر ہو سکتا ہے اور $\ p(x)$ احتمال ہے $X$ کا کہ $x\in \mathbb {X}$ ہو، تو تصادفی متغیر $X$ کی درمائلت یوں تعریف ہوتی ہے:

$H(X)=\mathbb {E} _{X}[I(x)]=-\sum _{x\in \mathbb {X} }p(x)\log p(x)$

(یہاں $\ I(x)=-\log p(x)$ خود-اطلاع ہے، جو ایک پیغام کی انفرادی درمائلت کا حصہ ہے اور $\mathbb {E} _{X}$ تصادفی متغیر کی متوقع قدر ہے۔) درمائلت کا اہم خاصہ یہ ہے کہ درمائلت کبیر ہوتی ہے جب تمام ممکنہ پیغامات برابر امکانی ہوں $p(x)=1/n$، — یعنی سب سے زیادہ ناقابلِ پیشن گوئی— جس صورت میں $H(X)=\log n$ ہوتی ہے۔

ایسے تصادفی متغیر جس کی ممکنہ اقدار صرف دو ہوں، کی درمائلت (ثنائی درمائلت دالہ) یہ خاص صورت اختیار کر جائے گی:

$H_{\mbox{b}}(p)=-p\log _{2}p-(1-p)\log _{2}(1-p)\,$

مشترک درمائلت

دو متفرد تصادفی متغیروں $X$ اور $Y$ کی مشترک درمائلت محض ان دونوں کے جوڑے $\ (X,Y)$ کی درمائلت ہے۔ اس سے منتقض ہے کہ اگر $X$ اور $Y$ احصائی آزاد ہوں، تو ان کی مشترک درمائلت حاصل جمع ہو گی ان کی انفرادی درمائلتوں کا۔

مثال کے طور پر اگر $\ (X,Y)$ نمائندہ ہے شطرنج کے مہرہ کے مقام کا — $X$ قطار اور $Y$ ستون، تو مہرہ کی قطار اور مہرہ کے ستون کی مشترک درمائلت، مہرہ کے مقام کی درمائلت ہو گی۔

$H(X,Y)=\mathbb {E} _{X,Y}[-\log p(x,y)]=-\sum _{x,y}p(x,y)\log p(x,y)\,$

مشابہ علامت کے باوجود مشترک درمائلت کو کَج درمائلت سے گڈمڈ نہیں کرنا چاہیے۔

مشروط درمائلت (مُلتَبَس)

کسی تصادفی متغیر $X$ کی مشروط درمائلت یا مشروط لاتیقن جبکہ ایک دوسرے تصادفی متغیر $Y$ کی قدر معلوم ہو (یعنی $Y=y$)، یوں لکھی جا سکتی ہے:

$H(X|y)=-\sum _{x\in X}p(x|y)\log p(x|y)$

یہ مشروط درمائلت کی پہلی تعریف ہے۔

مشروط درمائلت کی دوسری تعریف، جو زیادہ عام ہے، میں تصادفی متغیر $Y$ کے لحاظ سے اوسط نکالی جاتی ہے:

$H(X|Y)=\mathbb {E} _{Y}[H(X|y)]=-\sum _{y\in Y}p(y)\sum _{x\in X}p(x|y)\log p(x|y)=-\sum _{x,y}p(x,y)\log {\frac {p(x,y)}{p(y)}}.$

اسے Y کے بارے میں X کا ملتبس بھی کہا جاتا ہے۔

یہ دونوں تعریفیں مختلف ہیں۔ پہلی میں تصادفی متغیر $Y$ کے کسی خاص قدر $y$ ہونے پر مشروط ہے، جبکہ دوسری میں تصادفی متغیر $Y$ پر مشروط کر کے $Y$ کے لحاظ سے متوقع قدر حاصل کی گئی ہے۔ ہم دوسری تعریف استعمال کریں گے۔

مشروط درمائلت کا اساسی خاصہ ہے کہ:

$H(X|Y)=H(X,Y)-H(Y)\,$

اصطلاح	term
تباعد ربح نسبتاً باہمی مشروط توزیع متناظر مُلتَبَس انتقال کلباک-لابلر	divergence gain relative mutual conditional distribution symmetric equivocation trans Kullback–Leibler

باہمی اطلاعات (انتقالِ اطلاعات)

ایک تصادفی متغیر کا مشاہدہ کرنے سے دوسرے تصادفی متغیر بارے ملنے والی اطلاعات کو باہمی اطلاعات کہتے ہیں۔ ابلاغیات میں یہ اہم ہے کہ اس سے ترسیل کیے گئے اور وصول ہوئے اشارات کے درمیان اطلاعات کی مقدار کی تکبیر کی جا سکتی ہے۔ تصادفی متغیر $X$ کی باہمی اطلاعات نسبت تصادفی متغیر $Y$ کے، یوں دی جاتی ہے:

$I(X;Y)=\mathbb {E} _{X,Y}[SI(x,y)]=\sum _{x,y}p(x,y)\log {\frac {p(x,y)}{p(x)\,p(y)}}$

جہاں (SI=specific mutual information) نکتہ بہ نکتہ باہمی اطلاع ہے۔

باہمی اطلاعات کا اساسی خاصہ ہے کہ:

$I(X;Y)=H(X)-H(X|Y)\,$

یعنی Y کو جان کر ہم X کی ترمیز میں اوسطاً $I(X;Y)$ تثمات بچا سکتے ہیں۔

باہمی اطلاعات متناظر ہے:

$I(X;Y)=I(Y;X)=H(X)+H(Y)-H(X,Y).\,$

کالبک-لائبلر تباعد (اطلاعات ربح)

کالبک-لابلر تباعد (یا اطلاعات تباعد یا اطلاعات ربح یا نسبتاً درمائلت) طریقہ ہے دو توزیعات کا موازنہ کرنے کا: ایک سچ توزیع احتمال p(x) اور ایک تعسُفی توزیع احتمال q(x) ۔ اگر ہم یہ تصور کر کے ڈیٹا کی دابیت کریں کہ اس زیریں توزیع q(x) ہے، جبکہ حقیقت میں صحیح توزیع p(x) ہو، کلباک-لابلر تباعد ہر معطع کی دابیت کے لیے اوسط اضافی تثمات کی تعداد کے برابر ہے۔ اس کو یوں تعریف کیا جاتا ہے:

$D_{\mathrm {KL} }(p(X)\|q(X))=\sum _{x\in X}-p(x)\log {q(x)}\,-\,\left(-p(x)\log {p(x)}\right)=\sum _{x\in X}p(x)\log {\frac {p(x)}{q(x)}}$

اگرچہ اس کو کبھی 'فاصلہ بَحر' کے استعمال کیا جاتا ہے، مگر یہ سچی بَحر نہیں ہے کیونکہ یہ متناظر نہیں اور مثلث نامساوات کی تسکین نہیں کرتی (اس لیے نیم-بَحر ہے)۔

نظریہ ترمیز

A picture showing scratches on the readable surface of a CD-R. Music and data CDs are coded using error correcting codes and thus can still be read even if they have minor scratches using error detection and correction.

نظریۂ اطلاعات کا ایک اہم ترین اطلاقیات نظریہ ترمیز ہے۔ اس کی مزید تقسیم کی جا سکتی ہے نظریۂ منبع ترمیز اور نظریۂ رودبار ترمیز میں۔ ڈیٹا کے احصائی بیان سے، نظریہ اطلاعات ڈیٹا کو بیان کرنے کے لیے درکار تثمات کی تعداد کا تعین کرتا ہے، جو منبع کی درمائلتِ اطلاع ہے۔

• ڈیٹا دابیت (منبع ترمیز): دابیت کے مسئلہ کے دو کلیات ہیں:

1. غیر الخسارہ دابیت: ڈیٹا سے قطعی تعیرِ نو ممکن ہونا چاہیے۔
2. خساری معطیات دابیت: تعمیرِ نو کے لیے تثمات کی تفویض اس طرح کی جاتی ہے کہ وفادری سطح جو اعوجاج دالہ سے ناپی جاتی ہے ایک خاص سطح سے نیچے نہ گرے۔

• غلطی درستی رمز (رودبار ترمیز): جبکہ ڈیٹا دابیت جہاں تک ممکن ہو وفر کو ہٹاتا ہے، غلطی درستی رمز صحیح طرز کی وفر ڈالتا ہے (غلطی درستی) جو ڈیٹا کی شوریلی رودبار کے پار بااہل اور وفادار ترسیل کے لیے ضروری ہو۔

نظریہ ترمیز کی دابیت اور ترسیل میں تقسیم اطلاعاتی ترسیل قضیات سے برحق ہے یا منبع–رودبار علیحدگی قضیہ جو یہ ثابت کرے ہیں کہ تثبات مختلف سیاق و سباق میں اطلاعات کا کائناتی سکہ ہے۔ البتہ یہ قضیہ صرف اس وقت لاگو ہوتے ہیں جب ایک ترسیلی صارف اور ایک وصولی صارف ہو۔ ان مناظر میں جب جب ایک سے زیادہ ترسیلہ ہوں (متعدد-رسائی رودبار) یا ایک سے زیادہ وصولہ ہوں (نشری رودبار) یا وسطی مددگار (بدیل رودبار) یا زیادہ جامع کمپیوٹر نیٹ ورک، ان صورتوں میں دابیت کے بعد ترسیل (غلطی درستی رمز کے ساتھ) کو کامل ہونا نہیں کہا جا سکتا۔

اصطلاح	term
منبع شرح اِعُوِجاج علامت پیغام غیر حافظہ مقیم قالب مٹیا	source rate distortion symbol message memoryless stationary block erasure

نظریہ منبع

کوئی بھی عمل جو پے درپے پیغامات تولید کرتا ہے، کو اطلاعات کا منبع سمجھا جا سکتا ہے۔ ذیل میں ان پیغامات کو علامات کہا جائے گا اور $\{X_{k}\}$ لکھا جائے گا۔ غیر سٹوریج منبع ایسا ہوتا ہے جس میں ہر پیغام آزاد یکساں توزیعی تصادفی متغیر ہو، جبکہ عرگودیائی اور مقیمیت زیادہ عام پابندیاں لاگو کرتے ہیں۔ یہ تمام عملیات عشوائی ہیں۔ ان کو نظریہ اطلاعات کے باہر اپنی وجہ سے مطالعہ کیا جاتا ہے۔

شرح

اطلاعات شرح r اوسط درمائلت فی علامت (پیغام) ہے۔ لاسٹوریج منبع کے لیے یہ محض درمائلت فی علامت ہے، جبکہ مقیم عشوائی عملیات کے لیے، یہ شرح ہے

$r=\lim _{n\to \infty }H(X_{n}|X_{n-1},X_{n-2},X_{n-3},\ldots );$

یعنی علامت کی مشروط درمائلت جبکہ تمام پچھلے تولید شدہ علامات دیے (معلوم) ہوں۔ زیادہ جامع عملیات جو بے شک مقیم نہ ہو کے لیے اوسط شرح ہے

$r=\lim _{n\to \infty }{\frac {1}{n}}H(X_{1},X_{2},\dots X_{n});$

یعنی مشترک درمائلت فی علامت کی حد۔ مقیم منبع کے لیے یہ دو اظہاریہ ایک ہی نتیجہ دے ہیں۔ نظریہ اطلاعات میں زبان کی "شرح" یا زبان کی "درمائلت" بولنا عام ہے۔ یہ مناسب ہے مثال کہ طور پر جب منبع اردو نثر ہو۔ اطلاعات منبع کی شرح کا رشتہ اس میں وافریت سے ہے اور اس سے کہ اسے کتنا دابیت کیا جا سکتا ہے، جو منبع ترمیز کے موضوعات ہیں۔

گنجائشِ رودبار

رودبار پر ابلاغ جیسا کہ —mobile phone پر گپ شپ— نظریہ اطلاعات کی اولٰی تحریک ہے۔ محمول صارفین کو البتہ تجربہ ہے کہ یہ رودباریں اکثر اشارات کی قطعی تعمیرِ نو میں ناکام ہو جاتی ہیں، خاموش وقفے اور اشاراتی فاسدگی کی دوسری ہئیتیں کفیت کو گھٹا دیتے ہیں۔ ایک شوریلی رودبار پر ہم کتنی اطلاعات ابلاغ کرنے کی امید رکھ سکتے ہیں؟

ایک متفرد رودبار پر ابلاغی عملیات کو دیکھو۔ اس عملیات کا سادہ تمثیل نیچے دکھایا ہے:

یہاں X نمائندہ ہے ترسیل شدہ پیغمات کی فضاء کا اور Y فضاء ہے وصولہ پیغامات کا جو ایکائی وقت میں ہماری رودبار پر وصول ہوتے ہیں۔ چلو $\ p(y|x)$ مشروط توزیع احتمال ہو Y کی جبکہ X دیا (معلوم) ہو۔ ہم p(y|x) کو ابلاغی رودبار کا جبلی مستقل خاصہ سمجھیں گے (جو ہماری رودبار کی شور قدرت کی نمائندہ ہے)۔ تب X اور Y کی مشترک توزیع مکمل طور پر جبر ہو جاتی ہے ہماری رودبار اور ہمارے f(x) کے انتخاب سے، ہمارے پیغام جو ہم رودبار پر بھیجنا چاہتے ہیں کی مختتم توزیع۔ ان پابندیوں کے تحت ہم اطلاعات کی شرح یا اشارات، کی تکبیر کرنا چاہیں گے، جو ہم رودبار پر ابلاغ کر سکتے ہیں۔ اس کے لیے مناسب ناپ باہمی اطلاعات ہے اور اس تکبیر باہمی اطلاعات کو گنجائشِ رودبار کہے ہیں اور اس طرح دے ہیں:

$C=\max _{f}I(X;Y).\!$

گنجائش کا ذیل خاصہ ہے جو شرح R پر ابلاغ سے نسبت ہے (جہاں R عموماً تثمات فی علامت ہوتا ہے)۔ کسی بھی اطلاعات شرح R <C اور رمز غلطی ε> 0 اور کافی بڑے N کے لیے، لمبائی N اور شرح ≥ R کا رمز وجود رکھتا ہے اور کشف رمزی الخوارزم بھی کہ تکبیری قالب غلطی کا احتمال ≤ ε ہو گا؛ یعنی تعسُفی چھوٹی قالب غلطی سے ترسیل کرنا ہمیشہ ممکن ہو گا۔ اس کے علاوہ، اگر R> C ہو تو تعسُفی چھوٹی غلطی سے ترسیل کرنا ناممکن ہو گا۔

رودبار ترمیز کا معاملہ ایسے قریباً کامل رمز ڈھونڈنے سے ہے جو شوریلی رودبار پر چھوٹی ترمیز غلطی کے ساٹھ گنجائشِ رودبار کے قریب شرح پر ڈیٹا کی ترسیل کے لیے استعمال ہو سکیں۔

گنجائشِ رودبار اور متخصص رودبار تمثیلیں

• ایک استمری-وقت ابلاغ رودبار جو گاسی شور کے زیر ہو — دیکھو شانن ہارٹلے قضیہ۔
• ایک ثنائی متناظر رودبار جس کا آرپار احتمال p ہو، ایک ثنائی ادخال، ثنائی اخراج رودبار ہے، جو ادخال تثم کو احتمال p سے اُلٹا دیتی ہے۔ اس رودبار کی گنجائش فی رودبار استعمال $\ 1-H_{\mbox{b}}(p)$ ہے، جہاں $\ H_{\mbox{b}}$ ثنائی درمائلت دالہ ہے۔

• یک ثنائی مٹانا رودبار جس کے مٹانے کا احتمال p ہو، ایک ثنائی ادخال، سہی (تین) اخراج رودبار ہے۔ رودبار کے ممکنہ اخراج 0، 1 اور تیسری علامت e ہے جسے مٹیا کہتے ہیں۔ مٹیے اطلاعات کے مکمل خسارے کی نمائندگی کرتا ہے۔ اس رودبار کی گنجائش 1 - p تثمات فی رودبار استعمال ہے۔

مزید دیکھیے

• درمائلت

کتابیں

• نظریہ اطلاعات، اِستنتاج اور تعلّم الخوارزم "Information Theory, Inference and Learning Algorithms"

E=mc2     اردو ویکیپیڈیا پر ریاضی مساوات کو بائیں سے دائیں LTR پڑھیٔے     ریاضی علامات