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

اصطلاح	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.

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

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

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

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

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

اصطلاح	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 تثمات فی رودبار استعمال ا‏‏ے۔

ہور ویکھو

درمائلت

↑ F. Rieke, D. Warland, R Ruyter van Steveninck, W Bialek, Spikes: Exploring the Neural Code. The MIT press (1997).
↑ 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
↑ Rando Allikmets, Wyeth W. Wasserman, Amy Hutchinson, Philip Smallwood, Jeremy Nathans, Peter K. Rogan, Thomas D. Schneider Archived 2012-02-04 at the وے بیک مشین, Michael Dean (1998) Organization of the ABCR gene: analysis of promoter and splice junction sequences, Gene 215:1, 111-122
↑ 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.
↑ Jaynes, E. T. (1957) Information Theory and Statistical Mechanics, Phys. Rev. 106:620
↑ Charles H. Bennett, Ming Li, and Bin Ma (2003) Chain Letters and Evolutionary Histories Archived 2007-10-07 at the وے بیک مشین, Scientific American 288:6, 76-81
↑ David R. Anderson (نومبر ۱, ۲۰۰۳). «Some background on why people in the empirical sciences may want to better understand the information-theoretic methods». بایگانی‌شده از اصلی (pdf) در ۲۰۰۸-۱۲-۲۴. دریافت‌شده در ۲۰۰۷-۱۲-۳۰.
↑ Fazlollah M. Reza (1961, 1994). An Introduction to Information Theory. Dover Publications, Inc., New York. ISBN 0-486-68210-2.
↑ Robert B. Ash (1965, 1990). Information Theory. Dover Publications, Inc.. ISBN 0-486-66521-6.
↑ واضح رہے کہ ایہ اطلاعات $\ I(x,y)=-\log p(x,y)$ تو‏ں مختلف شے ا‏‏ے۔
↑ Jerry D. Gibson (1998). Digital Compression for Multimedia: Principles and Standards. Morgan Kaufmann. ISBN 1-55860-369-7.

کتاباں

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

E=mc² پنجابی ویکیپیڈیا اُتے ریاضی مساوات نو‏‏ں کھبے تو‏ں سجے LTR پڑھو ریاضی علامات

سانچہ:Mathematics-footer

[1] F. Rieke, D. Warland, R Ruyter van Steveninck, W Bialek, Spikes: Exploring the Neural Code. The MIT press (1997).

[2] . 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 Archived 2012-02-04 at the وے بیک مشین, 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 Archived 2007-10-07 at the وے بیک مشین, Scientific American 288:6, 76-81

[7] David R. Anderson (نومبر ۱, ۲۰۰۳). «Some background on why people in the empirical sciences may want to better understand the information-theoretic methods». بایگانی‌شده از اصلی (pdf) در ۲۰۰۸-۱۲-۲۴. دریافت‌شده در ۲۰۰۷-۱۲-۳۰.

[Reza-8] Fazlollah M. Reza (1961, 1994). An Introduction to Information Theory. Dover Publications, Inc., New York. ISBN 0-486-68210-2.

[Ash-9] Robert B. Ash (1965, 1990). Information Theory. Dover Publications, Inc.. ISBN 0-486-66521-6.

[10] واضح رہے کہ ایہ اطلاعات $\ I(x,y)=-\log p(x,y)$ تو‏ں مختلف شے ا‏‏ے۔

[11] Jerry D. Gibson (1998). Digital Compression for Multimedia: Principles and Standards. Morgan Kaufmann. ISBN 1-55860-369-7.

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

[۷]

[۸]

[۹]

[۱۰]

[۱۱]