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

آزاد دائرۃ المعارف، ویکیپیڈیا سے
:چھلانگ بطرف رہنمائی، تلاش
اصطلاح term

معطیات
ابلاغیات
تخزین
متعبر
دابی

data
communication
store
reliable
compress

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

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

نظریہ اطلاعات کی اطلاقیات کے بنیادی موضوعات میں شامل ہیں بغیر خسارہ معطیاتی دابیت (مثال، 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 کی درمائلت یوں تعریف ہوتی ہے:[8]

 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 کے لحاظ سے اوسط نکالی جاتی ہے: [9]

 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) نکتہ بہ نکتہ باہمی اطلاع ہے۔[10]


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

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);

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

گنجائشِ رودبار[ترمیم]

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

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

Comm Channel.svg

یہاں 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} ثنائی درمائلت دالہ ہے۔
Binary symmetric channel.svg
  • یک ثنائی مٹانا رودبار جس کے مٹانے کا احتمال p ہو، ایک ثنائی ادخال، سہی (تین) اخراج رودبار ہے۔ رودبار کے ممکنہ اخراج 0، 1، اور تیسری علامت e ہے جسے مٹیا کہتے ہیں۔ مٹیے اطلاعات کے مکمل خسارے کی نمائندگی کرتا ہے۔ اس رودبار کی گنجائش 1 - p تثمات فی رودبار استعمال ہے۔


Binary erasure channel.svg

اور دیکھو[ترمیم]

  1. ^ F. Rieke, D. Warland, R Ruyter van Steveninck, W Bialek, Spikes: Exploring the Neural Code. The MIT press (1997).
  2. ^ cf. Huelsenbeck, J. P., F. Ronquist, R. Nielsen and J. P. Bollback (2001) Bayesian inference of phylogeny and its impact on evolutionary biology, Science 294:2310-2314
  3. ^ Rando Allikmets, Wyeth W. Wasserman, Amy Hutchinson, Philip Smallwood, Jeremy Nathans, Peter K. Rogan, Thomas D. Schneider, Michael Dean (1998) Organization of the ABCR gene: analysis of promoter and splice junction sequences, Gene 215:1, 111-122
  4. ^ Burnham, K. P. and Anderson D. R. (2002) Model Selection and Multimodel Inference: A Practical Information-Theoretic Approach, Second Edition (Springer Science, New York) ISBN 978-0-387-95364-9.
  5. ^ Jaynes, E. T. (1957) Information Theory and Statistical Mechanics, Phys. Rev. 106:620
  6. ^ Charles H. Bennett, Ming Li, and Bin Ma (2003) Chain Letters and Evolutionary Histories, Scientific American 288:6, 76-81
  7. ^ David R. Anderson (November 1, 2003). "Some background on why people in the empirical sciences may want to better understand the information-theoretic methods" (pdf). http://www.jyu.fi/science/laitokset/bioenv/en/coeevolution/events/itms/why. Retrieved 2007-12-30. 
  8. ^ Fazlollah M. Reza (1961, 1994). An Introduction to Information Theory. Dover Publications, Inc., New York. ISBN 0-486-68210-2. http://books.google.com/books?id=RtzpRAiX6OgC&pg=PA8&dq=intitle:%22An+Introduction+to+Information+Theory%22++%22entropy+of+a+simple+source%22&as_brr=0&ei=zP79Ro7UBovqoQK4g_nCCw&sig=j3lPgyYrC3-bvn1Td42TZgTzj0Q. 
  9. ^ Robert B. Ash (1965, 1990). Information Theory. Dover Publications, Inc.. ISBN 0-486-66521-6. http://books.google.com/books?id=ngZhvUfF0UIC&pg=PA16&dq=intitle:information+intitle:theory+inauthor:ash+conditional+uncertainty&as_brr=0&ei=kKwNR4rbH5mepgKB4d2zBg&sig=YAsiCEVISjJ484R3uGoXpi-a5rI. 
  10. ^ واضح رہے کہ یہ اطلاعات \ I(x,y)=-\log p(x,y) سے مختلف شئے ہے۔
  11. ^ Jerry D. Gibson (1998). Digital Compression for Multimedia: Principles and Standards. Morgan Kaufmann. ISBN 1558603697. http://books.google.com/books?id=aqQ2Ry6spu0C&pg=PA56&dq=entropy-rate+conditional&as_brr=3&ei=YGDsRtzGGKjupQKa2L2xDw&sig=o0UCtf0xZOf11lPIexPrjOKPgNc#PPA57,M1. 


کتابیں[ترمیم]

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