कोड का सिद्धांत। कोडिंग सिद्धांत

विकिपीडिया, निःशुल्क विश्वकोष से

कोडिंग सिद्धांत- कोड के गुणों का विज्ञान और लक्ष्य प्राप्त करने के लिए उनकी उपयुक्तता।

सामान्य जानकारी

एन्कोडिंग सीधे उपयोग के लिए सुविधाजनक रूप से डेटा को ट्रांसमिशन, स्टोरेज, स्वचालित प्रसंस्करण और अनधिकृत पहुंच से संरक्षण के लिए सुविधाजनक रूप में परिवर्तित करने की प्रक्रिया है। कोडिंग सिद्धांत की मुख्य समस्याओं में एक-से-एक कोडिंग के मुद्दे और दी गई शर्तों के तहत एक संचार चैनल को लागू करने की जटिलता शामिल है:86। इस संबंध में, कोडिंग सिद्धांत मुख्य रूप से निम्नलिखित क्षेत्रों पर विचार करता है: 18:

आधार - सामग्री संकोचन

आगे त्रुटि सुधार

क्रिप्टोग्राफी

क्रिप्टोग्राफी (अन्य ग्रीक से। κρυπτός - छिपा हुआ और γράφω - मैं लिखता हूं), यह गोपनीयता सुनिश्चित करने के तरीकों के बारे में ज्ञान का क्षेत्र है (बाहरी लोगों को जानकारी पढ़ने की असंभवता), डेटा अखंडता (अपरिहार्य रूप से बदलती जानकारी की असंभवता), प्रमाणीकरण (लेखकत्व या किसी वस्तु के अन्य गुणों का प्रमाणीकरण), साथ ही लेखकत्व को अस्वीकार करने की असंभवता

04/04/2006 लियोनिद चेर्न्याक श्रेणी:प्रौद्योगिकी

"ओपन सिस्टम" कंप्यूटर का निर्माण असंभव होगा, यदि एक साथ उनकी उपस्थिति के साथ, सिग्नल कोडिंग का सिद्धांत नहीं बनाया गया होता। कोडिंग सिद्धांत गणित के उन क्षेत्रों में से एक है जिसने कंप्यूटिंग के विकास को महत्वपूर्ण रूप से प्रभावित किया है।

"ओपन सिस्टम्स"

कंप्यूटर का निर्माण असंभव होता, यदि एक साथ उनकी उपस्थिति के साथ, सिग्नल कोडिंग का सिद्धांत नहीं बनाया गया होता।

कोडिंग सिद्धांत गणित के उन क्षेत्रों में से एक है जिसने कंप्यूटिंग के विकास को स्पष्ट रूप से प्रभावित किया है। इसका दायरा वास्तविक (या शोर) चैनलों पर डेटा ट्रांसमिशन तक फैला हुआ है, और विषय प्रेषित जानकारी की शुद्धता सुनिश्चित करना है। दूसरे शब्दों में, यह अध्ययन करता है कि डेटा को सर्वोत्तम तरीके से कैसे पैक किया जाए ताकि सिग्नलिंग के बाद डेटा से विश्वसनीय और आसानी से उपयोगी जानकारी निकाली जा सके। कभी-कभी कोडिंग सिद्धांत को एन्क्रिप्शन के साथ भ्रमित किया जाता है, लेकिन यह सच नहीं है: क्रिप्टोग्राफी उलटा समस्या हल करती है, इसका लक्ष्य डेटा से जानकारी निकालना मुश्किल बनाना है।

टेलीग्राफ के आविष्कार के तुरंत बाद डेटा को एनकोड करने की आवश्यकता डेढ़ सौ साल से भी पहले सामने आई थी। चैनल महंगे और अविश्वसनीय थे, जिससे लागत को कम करने और टेलीग्राम प्रसारण की विश्वसनीयता बढ़ाने का काम अत्यावश्यक हो गया। ट्रान्साटलांटिक केबल बिछाने से समस्या और बढ़ गई है। 1845 से, विशेष कोड पुस्तकें उपयोग में आई हैं; उनकी मदद से, टेलीग्राफिस्ट मैन्युअल रूप से "संपीड़ित" संदेश, सामान्य शब्द अनुक्रमों को छोटे कोड के साथ बदलते हैं। उसी समय, स्थानांतरण की शुद्धता की जांच करने के लिए, समता का उपयोग किया जाने लगा, एक विधि जिसका उपयोग पहली और दूसरी पीढ़ी के कंप्यूटरों में छिद्रित कार्डों के इनपुट की शुद्धता की जांच के लिए भी किया जाता था। ऐसा करने के लिए, चेकसम के साथ एक विशेष रूप से तैयार कार्ड को अंतिम इनपुट डेक में डाला गया था। यदि इनपुट डिवाइस बहुत विश्वसनीय नहीं था (या डेक बहुत बड़ा था), तो एक त्रुटि हो सकती है। इसे ठीक करने के लिए, इनपुट प्रक्रिया को तब तक दोहराया गया जब तक कि परिकलित चेकसम कार्ड पर संग्रहीत राशि से मेल नहीं खाता। यह योजना न केवल असुविधाजनक है, बल्कि इसमें दोहरे दोष भी हैं। संचार चैनलों के विकास के साथ, एक अधिक प्रभावी नियंत्रण तंत्र की आवश्यकता थी।

शोर चैनलों पर डेटा ट्रांसमिशन की समस्या का पहला सैद्धांतिक समाधान सांख्यिकीय सूचना सिद्धांत के संस्थापक क्लाउड शैनन द्वारा प्रस्तावित किया गया था। शैनन अपने समय के एक स्टार थे, वे अमेरिकी शैक्षणिक अभिजात वर्ग में से एक थे। वन्नेवर बुश में एक स्नातक छात्र के रूप में, 1940 में उन्हें नोबेल पुरस्कार मिला (नोबेल पुरस्कार के साथ भ्रमित नहीं होना चाहिए!), 30 वर्ष से कम आयु के वैज्ञानिकों को प्रदान किया गया। बेल लैब्स में रहते हुए, शैनन ने "ए मैथमेटिकल थ्योरी ऑफ़ मैसेज ट्रांसमिशन" (1948) लिखा, जहाँ उन्होंने दिखाया कि यदि चैनल की बैंडविड्थ संदेश स्रोत की एन्ट्रापी से अधिक है, तो संदेश को एन्कोड किया जा सकता है ताकि यह बिना किसी देरी के प्रसारित किया गया। यह निष्कर्ष शैनन द्वारा सिद्ध किए गए प्रमेयों में से एक में निहित है, इसका अर्थ इस तथ्य से उबलता है कि यदि पर्याप्त बैंडविड्थ वाला कोई चैनल है, तो संदेश कुछ समय की देरी से प्रेषित किया जा सकता है। इसके अलावा, उन्होंने चैनल में शोर की उपस्थिति में विश्वसनीय संचरण की सैद्धांतिक संभावना दिखाई। सूत्र C = W लॉग ((P+N)/N), मिशिगन में अपने गृहनगर में स्थापित शैनन के एक मामूली स्मारक पर उकेरा गया है, इसकी तुलना अल्बर्ट आइंस्टीन के सूत्र E = mc 2 के मूल्य से की गई है।

शैनन के काम ने सूचना सिद्धांत के क्षेत्र में बहुत अधिक शोध को जन्म दिया, लेकिन उनके पास कोई व्यावहारिक इंजीनियरिंग अनुप्रयोग नहीं था। बेल लैब्स में शैनन के सहयोगी रिचर्ड हैमिंग के प्रयासों से सिद्धांत से व्यवहार में परिवर्तन संभव हुआ, जिन्होंने "हैमिंग कोड" कहे जाने वाले कोड के एक वर्ग की खोज के लिए प्रसिद्धि प्राप्त की। एक किंवदंती है कि 40 के दशक के मध्य में बेल मॉडल V रिले गणना मशीन पर पंच कार्ड के साथ काम करने की असुविधा ने उनके हैमिंग कोड के आविष्कार को प्रेरित किया। उन्हें सप्ताहांत में मशीन पर काम करने का समय दिया जाता था जब कोई ऑपरेटर नहीं होता था, और उन्हें खुद इनपुट के साथ खिलवाड़ करना पड़ता था। जैसा भी हो सकता है, लेकिन हैमिंग ने मुख्य रूप से प्रोसेसर और मेमोरी के बीच कंप्यूटर में डेटा ट्रांसमिशन लाइनों सहित संचार चैनलों में त्रुटियों को ठीक करने में सक्षम कोड प्रस्तावित किए। हैमिंग कोड इस बात का प्रमाण बन गए कि कैसे शैनन के प्रमेयों द्वारा बताई गई संभावनाओं को व्यवहार में लाया जा सकता है।

हैमिंग ने 1950 में अपना पेपर प्रकाशित किया, हालांकि आंतरिक रिपोर्ट्स में उनके कोडिंग सिद्धांत की तारीख 1947 है। इसलिए, कुछ का मानना है कि हैमिंग, न कि शैनन, को कोडिंग सिद्धांत का जनक माना जाना चाहिए। हालाँकि, प्रौद्योगिकी के इतिहास में पहले की तलाश करना बेकार है।

यह केवल निश्चित है कि यह हैमिंग ही थे जिन्होंने सबसे पहले "एरर-करेक्टिंग कोड" (एरर-करेक्टिंग कोड, ECC) प्रस्तावित किया था। इन कोडों के आधुनिक संशोधनों का उपयोग सभी डेटा स्टोरेज सिस्टम में और प्रोसेसर और रैम के बीच आदान-प्रदान के लिए किया जाता है। उनके वेरिएंट में से एक, रीड-सोलोमन कोड, सीडी में उपयोग किए जाते हैं, जिससे रिकॉर्डिंग को स्क्वीक्स और शोर के बिना चलाया जा सकता है जो खरोंच और धूल के कणों का कारण बन सकता है। हैमिंग पर आधारित कोड के कई संस्करण हैं, वे कोडिंग एल्गोरिदम और चेक बिट्स की संख्या में भिन्न हैं। इस तरह के कोडों ने इंटरप्लेनेटरी स्टेशनों के साथ गहरे अंतरिक्ष संचार के विकास के संबंध में विशेष महत्व प्राप्त किया है, उदाहरण के लिए रीड-मुलर कोड हैं, जहां सात सूचना बिट्स के लिए 32 नियंत्रण बिट्स या छह के लिए 26 हैं।

नवीनतम ECC कोडों में, LDPC (लो-डेंसिटी पैरिटी-चेक कोड) कोड का उल्लेख किया जाना चाहिए। वास्तव में, वे लगभग तीस वर्षों से जाने जाते हैं, लेकिन हाल के वर्षों में उनमें विशेष रुचि का पता चला, जब हाई-डेफिनिशन टेलीविजन का विकास शुरू हुआ। एलडीपीसी कोड 100% विश्वसनीय नहीं हैं, लेकिन चैनल बैंडविड्थ का पूर्ण उपयोग करते हुए त्रुटि दर को वांछित स्तर पर समायोजित किया जा सकता है। "टर्बो कोड" उनके करीब हैं, वे गहरे अंतरिक्ष में स्थित वस्तुओं और सीमित चैनल बैंडविड्थ के साथ काम करते समय प्रभावी होते हैं।

व्लादिमीर अलेक्जेंड्रोविच मोटेलनिकोव का नाम कोडिंग सिद्धांत के इतिहास में मजबूती से अंकित है। 1933 में, "संचार के तकनीकी पुनर्निर्माण पर पहली ऑल-यूनियन कांग्रेस के लिए रेडियो संचार पर सामग्री," उन्होंने काम प्रकाशित किया "बैंडविड्थ पर? ईथर? और तार? Kotelnikov का नाम, एक समान के रूप में, कोडिंग सिद्धांत में सबसे महत्वपूर्ण प्रमेयों में से एक के नाम में शामिल है। यह प्रमेय उन शर्तों को परिभाषित करता है जिनके तहत सूचना के नुकसान के बिना संचरित सिग्नल को बहाल किया जा सकता है।

इस प्रमेय को "डब्ल्यूकेएस प्रमेय" (संक्षिप्त नाम डब्ल्यूकेएस को व्हिटेकर, मोटेलनिकोव, शैनन से लिया गया है) सहित विभिन्न रूप से बुलाया गया है। कुछ स्रोतों में, Nyquist-Shannon नमूनाकरण प्रमेय और Whittaker-Shannon नमूनाकरण प्रमेय दोनों का उपयोग किया जाता है, और घरेलू विश्वविद्यालय की पाठ्यपुस्तकों में, बस "Kotelnikov's theorem" सबसे अधिक पाया जाता है। वास्तव में, प्रमेय का एक लंबा इतिहास है। इसका पहला भाग 1897 में फ्रांसीसी गणितज्ञ एमिल बोरेल द्वारा सिद्ध किया गया था। 1915 में एडमंड व्हिटेकर ने योगदान दिया। 1920 में, जापानी किन्नोसुकी ओगुरा ने व्हिटेकर के शोध में सुधार प्रकाशित किए, और 1928 में, अमेरिकी हैरी न्यक्विस्ट ने डिजिटलीकरण और एनालॉग सिग्नल पुनर्निर्माण के सिद्धांतों को परिष्कृत किया।

क्लाउड शैनन(1916 - 2001) ने अपने स्कूल के वर्षों से गणित और इलेक्ट्रिकल इंजीनियरिंग में समान रुचि दिखाई। 1932 में, उन्होंने मिशिगन विश्वविद्यालय में प्रवेश किया, 1936 में - मैसाचुसेट्स इंस्टीट्यूट ऑफ टेक्नोलॉजी में, जहाँ से उन्होंने 1940 में स्नातक किया, दो डिग्री प्राप्त की - इलेक्ट्रिकल इंजीनियरिंग में मास्टर डिग्री और गणित में डॉक्टरेट। 1941 में शैनन बेल लेबोरेटरीज में शामिल हो गए। यहां उन्होंने विचारों को विकसित करना शुरू किया जो बाद में सूचना सिद्धांत में परिणत हुआ। 1948 में, शैनन ने "संचार का गणितीय सिद्धांत" लेख प्रकाशित किया, जहां वैज्ञानिक के मूल विचारों को तैयार किया गया था, विशेष रूप से, एन्ट्रापी के माध्यम से सूचना की मात्रा का निर्धारण, और सूचना की एक इकाई भी प्रस्तावित की जो दो की पसंद को निर्धारित करती है। समान रूप से संभावित विकल्प, यानी जिसे बाद में बिट कहा गया। 1957-1961 में, शैनन ने शोर संचार चैनलों के लिए थ्रूपुट प्रमेय साबित करने वाले कार्यों को प्रकाशित किया, जो अब उनके नाम पर है। 1957 में, शैनन मैसाचुसेट्स इंस्टीट्यूट ऑफ टेक्नोलॉजी में प्रोफेसर बने, जहां से वे 21 साल बाद सेवानिवृत्त हुए। "अच्छी तरह से लायक आराम" पर शैनन ने करतब दिखाने के अपने पुराने जुनून के लिए खुद को पूरी तरह से समर्पित कर दिया। उन्होंने कई करतब दिखाने वाली मशीनें बनाईं और यहां तक कि करतब दिखाने का एक सामान्य सिद्धांत भी बनाया।

रिचर्ड हैमिंग(1915 - 1998) ने शिकागो विश्वविद्यालय में अपनी शिक्षा शुरू की, जहाँ उन्होंने 1937 में स्नातक की उपाधि प्राप्त की। 1939 में उन्होंने नेब्रास्का विश्वविद्यालय से मास्टर डिग्री और इलिनोइस विश्वविद्यालय से गणित में डॉक्टरेट की उपाधि प्राप्त की। 1945 में, हैमिंग ने मैनहट्टन प्रोजेक्ट पर काम करना शुरू किया, जो कि परमाणु बम बनाने के लिए बड़े पैमाने पर सरकारी शोध प्रयास था। 1946 में, हैमिंग बेल टेलीफोन प्रयोगशालाओं में शामिल हो गए, जहाँ उन्होंने क्लाउड शैनन के साथ काम किया। 1976 में, हैमिंग ने मॉन्टेरी, कैलिफोर्निया में नेवल पोस्टग्रेजुएट स्कूल में एक कुर्सी प्राप्त की।

काम जिसने उन्हें प्रसिद्ध किया, त्रुटि का पता लगाने और सुधार कोड का एक मौलिक अध्ययन, 1950 में हैमिंग द्वारा प्रकाशित किया गया था। 1956 में, वे शुरुआती आईबीएम 650 मेनफ्रेम में से एक के विकास में शामिल थे। उनके काम ने एक प्रोग्रामिंग भाषा की नींव रखी जो बाद में उच्च-स्तरीय प्रोग्रामिंग भाषाओं में विकसित हुई। कंप्यूटर विज्ञान के क्षेत्र में हैमिंग के योगदान की मान्यता में, IEEE ने उनके नाम पर कंप्यूटर विज्ञान और सिस्टम थ्योरी के लिए एक विशिष्ट सेवा पदक की स्थापना की।

व्लादिमीर मोटेलनिकोव(1908 - 2005) 1926 में उन्होंने N. E. बॉमन (MVTU) के नाम पर मॉस्को हायर टेक्निकल स्कूल के इलेक्ट्रिकल इंजीनियरिंग फैकल्टी में प्रवेश किया, लेकिन मॉस्को पावर इंजीनियरिंग इंस्टीट्यूट (MPEI) के स्नातक बन गए, जो मॉस्को हायर टेक्निकल स्कूल से अलग हो गया। एक स्वतंत्र संस्थान। ग्रेजुएट स्कूल (1931-1933) में पढ़ते समय, Kotelnikov ने गणितीय रूप से "संदर्भ प्रमेय" को सटीक रूप से तैयार किया और साबित किया, जिसे बाद में उनके नाम पर रखा गया। 1933 में स्नातक विद्यालय से स्नातक होने के बाद, मॉस्को पावर इंजीनियरिंग इंस्टीट्यूट में पढ़ाने वाले Kotelnikov, सेंट्रल रिसर्च इंस्टीट्यूट ऑफ कम्युनिकेशंस (TsNIIS) में काम करने चले गए। 1941 में, V. A. Kotelnikov ने आवश्यकताओं पर एक स्पष्ट स्थिति तैयार की कि एक गणितीय रूप से अविवेकी प्रणाली को संतुष्ट करना चाहिए और इसे समझने की असंभवता का प्रमाण दिया गया था। 1944 में, Kotelnikov ने MPEI के रेडियो इंजीनियरिंग संकाय के प्रोफेसर, डीन का पद संभाला, जहाँ उन्होंने 1980 तक काम किया। 1953 में, 45 वर्ष की आयु में, Kotelnikov को तुरंत USSR विज्ञान अकादमी का पूर्ण सदस्य चुना गया। 1968 से 1990 तक, V. A. Kotelnikov मास्को इंस्टीट्यूट ऑफ फिजिक्स एंड टेक्नोलॉजी में एक विभाग के प्रमुख प्रोफेसर भी थे।

कोडिंग सिद्धांत का जन्म

04/04/2006 लियोनिद चेर्न्याक श्रेणी:प्रौद्योगिकी

"ओपन सिस्टम्स"

कंप्यूटर का निर्माण असंभव होता, यदि एक साथ उनकी उपस्थिति के साथ, सिग्नल कोडिंग का सिद्धांत नहीं बनाया गया होता।

कोडिंग सिद्धांत का जन्म

"इस पाठ्यक्रम का लक्ष्य आपको आपके तकनीकी भविष्य के लिए तैयार करना है।"

हे हबर। भयानक लेख "आप और आपकी नौकरी" याद है (+219, 2442 बुकमार्क, 394k पढ़ता है)?

तो हैमिंग (हाँ, हाँ, स्व-जाँच और स्वयं-सुधार करने वाले हैमिंग कोड) में उनके व्याख्यानों के आधार पर एक पूरी पुस्तक लिखी गई है। हम इसका अनुवाद करते हैं, क्योंकि आदमी अपने मन की बात कहता है।

यह किताब सिर्फ आईटी के बारे में नहीं है, यह अविश्वसनीय रूप से शांत लोगों के सोचने के तरीके के बारे में एक किताब है। “यह केवल सकारात्मक सोच का आरोप नहीं है; यह उन परिस्थितियों का वर्णन करता है जो महान कार्य करने की संभावना को बढ़ाते हैं।"

हम पहले ही 28 (30 में से) अध्यायों का अनुवाद कर चुके हैं। और हम "पेपर में" प्रकाशन पर काम कर रहे हैं।

कोडिंग थ्योरी - I

कंप्यूटर और वे कैसे काम करते हैं, इस पर विचार करने के बाद, अब हम सूचना प्रतिनिधित्व के प्रश्न पर विचार करेंगे: कंप्यूटर कैसे उस जानकारी का प्रतिनिधित्व करते हैं जिसे हम संसाधित करना चाहते हैं। किसी भी वर्ण का अर्थ इस बात पर निर्भर हो सकता है कि इसे कैसे संसाधित किया जाता है, मशीन का उपयोग किए गए बिट के लिए कोई विशिष्ट अर्थ नहीं है। अध्याय 4 में सॉफ्टवेयर के इतिहास पर चर्चा करते समय, हमने कुछ सिंथेटिक प्रोग्रामिंग भाषा पर विचार किया, जिसमें स्टॉप इंस्ट्रक्शन का कोड अन्य निर्देशों के कोड के समान था। यह स्थिति अधिकांश भाषाओं के लिए विशिष्ट है, निर्देश का अर्थ संबंधित कार्यक्रम द्वारा निर्धारित किया जाता है।

सूचना प्रतिनिधित्व की समस्या को सरल बनाने के लिए, सूचना को बिंदु से बिंदु तक स्थानांतरित करने की समस्या पर विचार करें। यह प्रश्न सूचना को सहेजने के प्रश्न से संबंधित है। समय और स्थान में सूचना प्रसारण की समस्याएं समान हैं। चित्र 10.1 एक विशिष्ट सूचना हस्तांतरण मॉडल दिखाता है।

चित्र 10.1

चित्र 10.1 के बाईं ओर सूचना का स्रोत है। मॉडल पर विचार करते समय, स्रोत की प्रकृति हमारे लिए महत्वहीन होती है। यह वर्णमाला वर्णों, संख्याओं, गणितीय सूत्रों, संगीत नोटों, प्रतीकों का एक सेट हो सकता है जिसके साथ हम नृत्य आंदोलनों का प्रतिनिधित्व कर सकते हैं - स्रोत की प्रकृति और उसमें संग्रहीत वर्णों का अर्थ ट्रांसमिशन मॉडल का हिस्सा नहीं है। हम केवल सूचना के स्रोत पर विचार करते हैं, ऐसी सीमा के साथ, एक शक्तिशाली, सामान्य सिद्धांत प्राप्त होता है, जिसे कई क्षेत्रों तक बढ़ाया जा सकता है। यह कई अनुप्रयोगों से एक सार है।

1940 के अंत में जब शैनन ने सूचना सिद्धांत बनाया, तो यह सोचा गया कि इसे संचार सिद्धांत कहा जाना चाहिए था, लेकिन उन्होंने शब्द सूचना पर जोर दिया। यह शब्द सिद्धांत में बढ़ती रुचि और निरंतर निराशा दोनों का एक निरंतर कारण बन गया है। जांचकर्ता पूरे "सूचना के सिद्धांतों" का निर्माण करना चाहते थे, वे पात्रों के सेट के बारे में सिद्धांतों में पतित हो गए। स्थानांतरण मॉडल पर लौटते हुए, हमारे पास डेटा का एक स्रोत होता है जिसे स्थानांतरण के लिए एन्कोड करने की आवश्यकता होती है।

एनकोडर में दो भाग होते हैं, पहले भाग को स्रोत एनकोडर कहा जाता है, सटीक नाम स्रोत प्रकार पर निर्भर करता है। विभिन्न प्रकार के डेटा के स्रोत विभिन्न प्रकार के एनकोडर के अनुरूप होते हैं।

एन्कोडिंग प्रक्रिया के दूसरे भाग को चैनल कोडिंग कहा जाता है और डेटा ट्रांसमिशन के लिए चैनल के प्रकार पर निर्भर करता है। इस प्रकार, एन्कोडिंग प्रक्रिया का दूसरा भाग ट्रांसमिशन चैनल प्रकार से मेल खाता है। इस प्रकार, मानक इंटरफेस का उपयोग करते समय, स्रोत से डेटा पहले इंटरफ़ेस की आवश्यकताओं के अनुसार एन्कोड किया जाता है, और फिर उपयोग किए गए डेटा ट्रांसमिशन चैनल की आवश्यकताओं के अनुसार।

मॉडल के अनुसार, चित्र 10.1 में, डेटा लिंक "अतिरिक्त यादृच्छिक शोर" के अधीन है। सिस्टम में सभी शोर इस बिंदु पर विलीन हो जाते हैं। यह माना जाता है कि एनकोडर बिना विरूपण के सभी प्रतीकों को प्राप्त करता है, और डिकोडर त्रुटियों के बिना अपना कार्य करता है। यह कुछ आदर्शीकरण है, लेकिन कई व्यावहारिक उद्देश्यों के लिए यह वास्तविकता के करीब है।

डिकोडिंग चरण में भी दो चरण होते हैं: चैनल - मानक, मानक - डेटा रिसीवर। हस्तांतरण के अंत में, डेटा उपभोक्ता को स्थानांतरित कर दिया जाता है। फिर से, हम इस बात पर विचार नहीं करते हैं कि उपभोक्ता इस डेटा की व्याख्या कैसे करता है।

जैसा कि पहले उल्लेख किया गया है, एक डेटा ट्रांसमिशन सिस्टम, जैसे टेलीफोन संदेश, रेडियो, टीवी कार्यक्रम, कंप्यूटर के रजिस्टरों में संख्याओं के एक समूह के रूप में डेटा का प्रतिनिधित्व करता है। फिर से, अंतरिक्ष में प्रसारण समय में संचरण या सूचना के भंडारण से अलग नहीं है। क्या आपके पास ऐसी जानकारी है जिसकी कुछ समय बाद आवश्यकता होगी, तो इसे डेटा संग्रहण स्रोत पर एन्कोड और संग्रहीत किया जाना चाहिए। यदि आवश्यक हो, तो जानकारी को डिकोड किया जाता है। यदि एन्कोडिंग और डिकोडिंग सिस्टम समान है, तो हम ट्रांसमिशन चैनल के माध्यम से अपरिवर्तित डेटा संचारित करते हैं।

भौतिकी में प्रस्तुत सिद्धांत और सामान्य सिद्धांत के बीच मूलभूत अंतर यह धारणा है कि स्रोत और रिसीवर पर कोई शोर नहीं होता है। वास्तव में, किसी भी उपकरण में त्रुटियां होती हैं। क्वांटम यांत्रिकी में, शोर अनिश्चितता के सिद्धांत के अनुसार किसी भी स्तर पर होता है, न कि प्रारंभिक स्थिति के रूप में; किसी भी मामले में, सूचना सिद्धांत में शोर की अवधारणा क्वांटम यांत्रिकी में समान अवधारणा के बराबर नहीं है।
निश्चितता के लिए, हम आगे सिस्टम में डेटा प्रतिनिधित्व के बाइनरी फॉर्म पर विचार करेंगे। अन्य रूपों को समान तरीके से संसाधित किया जाता है, सरलता के लिए हम उन पर विचार नहीं करेंगे।

चलो चर लंबाई के कोडित वर्णों के साथ सिस्टम के साथ शुरू करते हैं, जैसा कि डॉट्स और डैश के क्लासिक मोर्स कोड में होता है, जिसमें अक्सर होने वाले वर्ण छोटे होते हैं और दुर्लभ वर्ण लंबे होते हैं। यह दृष्टिकोण उच्च कोड दक्षता प्राप्त करने की अनुमति देता है, लेकिन यह ध्यान देने योग्य है कि मोर्स कोड टर्नरी है, बाइनरी नहीं, क्योंकि इसमें डॉट्स और डैश के बीच एक स्पेस कैरेक्टर होता है। यदि कोड में सभी वर्ण समान लंबाई के हैं, तो ऐसे कोड को ब्लॉक कहा जाता है।

कोड की पहली स्पष्ट आवश्यक संपत्ति शोर की अनुपस्थिति में स्पष्ट रूप से एक संदेश को डिकोड करने की क्षमता है, कम से कम यह एक वांछनीय संपत्ति लगती है, हालांकि कुछ स्थितियों में इस आवश्यकता को उपेक्षित किया जा सकता है। ट्रांसमिशन चैनल से डेटा रिसीवर को 0s और 1s की स्ट्रीम के रूप में दिखाई देता है।

हम दो आसन्न वर्णों को एक डबल एक्सटेंशन, तीन आसन्न वर्णों को एक ट्रिपल एक्सटेंशन कहेंगे, और सामान्य तौर पर यदि हम N वर्ण भेजते हैं तो रिसीवर N वर्णों के आधार कोड में जोड़ देखता है। रिसीवर, एन के मूल्य को नहीं जानता, धारा को प्रसारण ब्लॉकों में विभाजित करना चाहिए। या, दूसरे शब्दों में, मूल संदेश को फिर से बनाने के लिए रिसीवर को एक अनोखे तरीके से धारा को विघटित करने में सक्षम होना चाहिए।

अक्षरों की एक छोटी संख्या के वर्णमाला पर विचार करें; आमतौर पर अक्षर बहुत बड़े होते हैं। भाषा के अक्षर 16 से 36 वर्णों से शुरू होते हैं, जिनमें अपरकेस और लोअरकेस वर्ण, संख्याएँ, चिह्न, विराम चिह्न शामिल हैं। उदाहरण के लिए, ASCII तालिका में, 128 = 2^7 वर्ण।
एक विशेष कोड पर विचार करें जिसमें 4 वर्ण s1, s2, s3, s4 शामिल हैं

एस 1 = 0; एस2 = 00; एस3 = 01; एस 4 = 11।

रिसीवर को निम्नलिखित प्राप्त अभिव्यक्ति की व्याख्या कैसे करनी चाहिए

कैसे s1s1s4या कैसे s2s4?

आप स्पष्ट रूप से इस प्रश्न का उत्तर नहीं दे सकते, यह कोड निश्चित रूप से डिकोड नहीं किया गया है, इसलिए यह असंतोषजनक है। दूसरी ओर, कोड

एस 1 = 0; एस2 = 10; एस3 = 110; एस 4 = 111

संदेश को अनोखे तरीके से डिकोड करता है। आइए एक मनमानी स्ट्रिंग लें और विचार करें कि रिसीवर इसे कैसे डीकोड करेगा। आपको चित्र 10.II में दिए गए आकार के अनुसार एक डिकोडिंग ट्री बनाने की आवश्यकता है। पंक्ति

1101000010011011100010100110 …

चरित्र ब्लॉकों में विभाजित किया जा सकता है

110, 10, 0, 10, 0, 110, 111, 0, 0, 0, 10, 10, 0, 110, …

डिकोडिंग ट्री के निर्माण के लिए निम्नलिखित नियम के अनुसार:

यदि आप पेड़ के शीर्ष पर हैं, तो अगला वर्ण पढ़ें। जब आप पेड़ के पत्ते तक पहुंचते हैं, तो आप अनुक्रम को एक वर्ण में परिवर्तित कर देते हैं और शुरुआत में वापस आ जाते हैं।

ऐसा पेड़ मौजूद होने का कारण यह है कि कोई भी वर्ण दूसरे का उपसर्ग नहीं है, इसलिए आप हमेशा जानते हैं कि डिकोडिंग ट्री के शीर्ष पर कब लौटना है।

निम्न बातों पर ध्यान देना आवश्यक है। सबसे पहले, डिकोडिंग एक सख्त स्ट्रीमिंग प्रक्रिया है जिसमें प्रत्येक बिट की केवल एक बार जांच की जाती है। दूसरे, प्रोटोकॉल में आमतौर पर वर्ण शामिल होते हैं जो डिकोडिंग प्रक्रिया के अंत को चिह्नित करते हैं और संदेश के अंत को इंगित करने के लिए आवश्यक होते हैं।

अनुगामी वर्ण का उपयोग नहीं करना कोड डिज़ाइन में एक सामान्य गलती है। बेशक, एक स्थायी डिकोडिंग मोड प्रदान किया जा सकता है, जिस स्थिति में समाप्ति प्रतीक की आवश्यकता नहीं होती है।

चित्र 10.II

अगला प्रश्न स्ट्रीमिंग (तात्कालिक) डिकोडिंग के लिए कोड है। पिछले वर्ण मानचित्रण से प्राप्त कोड पर विचार करें

एस 1 = 0; एस2 = 01; एस3 = 011; एस 4 = 111।

मान लीजिए हमारे पास अनुक्रम है 011111...111 . जिस तरह से आप संदेश के पाठ को डिकोड कर सकते हैं, वह समूह में अंत से 3 तक समूह बिट्स है और समूहों को एक से पहले अग्रणी शून्य के साथ चुनें, फिर आप डीकोड कर सकते हैं। ऐसा कोड एक अनोखे तरीके से डिकोड करने योग्य है, लेकिन तुरंत नहीं! डिकोड करने के लिए, आपको स्थानांतरण के अंत तक प्रतीक्षा करनी होगी! व्यवहार में, यह दृष्टिकोण डिकोडिंग गति (मैकमिलन के प्रमेय) को समतल करता है, इसलिए तत्काल डिकोडिंग के तरीकों की तलाश करना आवश्यक है।

एक ही वर्ण को सांकेतिक शब्दों में बदलने के दो तरीकों पर विचार करें, Si:

एस 1 = 0; एस2 = 10; एस3 = 110; s4=1110, s5=1111,

इस पद्धति के लिए डिकोडिंग ट्री चित्र 10.III में दिखाया गया है।

चित्र 10.III

दूसरा तरीका

एस 1 = 00; एस2 = 01; एस3 = 100; s4=110, s5=111,

इस देखभाल का डिकोडिंग ट्री चित्र 10.IV में प्रस्तुत किया गया है।

कोड गुणवत्ता को मापने का सबसे स्पष्ट तरीका संदेशों के कुछ सेट की औसत लंबाई है। ऐसा करने के लिए, प्रत्येक प्रतीक की कोड लंबाई की गणना करना आवश्यक है, घटना पीआई की इसी संभावना से गुणा किया जाता है। यह आपको पूरे कोड की लंबाई देगा। क्यू अक्षरों के वर्णमाला के लिए औसत लंबाई एल कोड का सूत्र इस प्रकार है

जहां पाई वर्ण सी की घटना की संभावना है, ली एन्कोडेड वर्ण की संगत लंबाई है। एक कुशल कोड के लिए, एल का मान जितना संभव हो उतना छोटा होना चाहिए। यदि P1 = 1/2, p2 = 1/4, p3 = 1/8, p4 = 1/16 और p5 = 1/16, तो कोड #1 के लिए हमें कोड लंबाई का मान मिलता है

और कोड #2 के लिए

प्राप्त मूल्य पहले कोड के लिए वरीयता का संकेत देते हैं।
यदि वर्णमाला के सभी शब्दों के होने की संभावना समान है, तो दूसरा कोड अधिक बेहतर है। उदाहरण के लिए, पाई = 1/5 के साथ, कोड की लंबाई #1

और कोड की लंबाई #2

यह परिणाम कोड 2 के लिए वरीयता दर्शाता है। इस प्रकार, "अच्छा" कोड डिजाइन करते समय, वर्णों के होने की संभावना को ध्यान में रखा जाना चाहिए।

चित्र 10.IV

चित्र 10.वी

क्राफ्ट की असमानता पर विचार करें, जो वर्ण कोड लंबाई ली के सीमा मूल्य को निर्धारित करती है। आधार 2 के अनुसार, असमानता को इस रूप में दर्शाया गया है

यह असमानता कहती है कि वर्णमाला में बहुत अधिक छोटे वर्ण नहीं हो सकते, अन्यथा योग काफी बड़ा होगा।

किसी भी तेज़ अद्वितीय डिकोडेबल कोड के लिए क्राफ्ट की असमानता को साबित करने के लिए, हम एक डिकोडिंग ट्री का निर्माण करते हैं और गणितीय प्रेरण की विधि लागू करते हैं। यदि पेड़ में एक या दो पत्तियाँ हैं, जैसा कि चित्र 10.V में दिखाया गया है, तो इसमें कोई संदेह नहीं है कि असमानता सत्य है। इसके अलावा, यदि पेड़ में दो से अधिक पत्तियाँ हैं, तो हम m लंबाई के पेड़ को दो उपवृक्षों में विभाजित करते हैं। प्रेरण के सिद्धांत के अनुसार, हम मानते हैं कि ऊंचाई m -1 या उससे कम की प्रत्येक शाखा के लिए असमानता सही है। प्रेरण के सिद्धांत के अनुसार, प्रत्येक शाखा में असमानता को लागू करना। आइए हम शाखा कोड K" और K" की लंबाई को निरूपित करें। जब पेड़ की दो शाखाओं को मिलाया जाता है, तो प्रत्येक की लंबाई 1 से बढ़ जाती है, इसलिए, कोड की लंबाई में K'/2 और K' का योग होता है। '/2,

प्रमेय सिद्ध हो चुका है।

मैकमिलन के प्रमेय के प्रमाण पर विचार करें। आइए क्राफ्ट की असमानता को गैर-धाराबद्ध डिकोडेबल कोड पर लागू करें। प्रमाण इस तथ्य पर आधारित है कि किसी भी संख्या K > 1 के लिए, संख्या की nवीं शक्ति निश्चित रूप से n के रैखिक फलन से अधिक होती है, जहां n काफी बड़ी संख्या है। क्राफ्ट की असमिका को nवें घात तक बढ़ाएँ और व्यंजक को योग के रूप में निरूपित करें

जहाँ Nk लंबाई k के वर्णों की संख्या है, योग nth वर्ण प्रतिनिधित्व की न्यूनतम लंबाई से शुरू होता है और nl की अधिकतम लंबाई के साथ समाप्त होता है, जहाँ l एन्कोडेड वर्ण की अधिकतम लंबाई है। यह अद्वितीय डिकोडिंग आवश्यकता से अनुसरण करता है। राशि के रूप में प्रस्तुत किया गया है

यदि K > 1 है, तो असमानता के असत्य होने के लिए n को काफी बड़ा सेट करना आवश्यक है। इसलिए के<= 1; теорема Макмиллана доказана.

आइए क्राफ्ट की असमानता के आवेदन के कुछ उदाहरणों पर विचार करें। क्या लंबाई 1, 3, 3, 3 के साथ एक विशिष्ट डिकोडेबल कोड हो सकता है? हां, क्योंकि

लंबाई 1, 2, 2, 3 के बारे में क्या? सूत्र के अनुसार गणना करें

असमानता का उल्लंघन! इस कोड में बहुत अधिक छोटे वर्ण हैं।

डॉट कोड (अल्पविराम कोड) ऐसे कोड होते हैं जिनमें वर्ण 1 होते हैं, वर्ण 0 में समाप्त होते हैं, अंतिम वर्ण को छोड़कर, जिसमें सभी शामिल होते हैं। विशेष मामलों में से एक कोड है

एस 1 = 0; एस2 = 10; एस3 = 110; एस4 = 1110; एस5 = 11111।

इस कोड के लिए, हमें क्राफ्ट की असमानता के लिए एक व्यंजक प्राप्त होता है

इस मामले में, हम समानता प्राप्त करते हैं। यह देखना आसान है कि पॉइंट कोड के लिए क्राफ्ट की असमानता एक समानता में बदल जाती है।

कोड बनाते समय, आपको क्राफ्ट योग पर ध्यान देना होगा। यदि क्राफ्ट राशि 1 से अधिक होने लगती है, तो यह औसत कोड लंबाई को कम करने के लिए एक अलग लंबाई के प्रतीक को शामिल करने का संकेत है।

यह ध्यान दिया जाना चाहिए कि क्राफ्ट की असमानता यह नहीं कहती है कि यह कोड विशिष्ट रूप से डिकोडेबल है, लेकिन यह कि ऐसी लंबाई के प्रतीकों वाला एक कोड है जो विशिष्ट रूप से डिकोडेबल है। एक अद्वितीय डिकोडेबल कोड बनाने के लिए, आप बिट्स ली में इसी लंबाई को बाइनरी नंबर के रूप में निर्दिष्ट कर सकते हैं। उदाहरण के लिए, लंबाई 2, 2, 3, 3, 4, 4, 4, 4 के लिए हमें क्राफ्ट की असमानता मिलती है

इसलिए, इस तरह के एक अद्वितीय डिकोडेबल स्ट्रीम कोड मौजूद हो सकते हैं।

एस 1 = 00; एस2 = 01; एस3 = 100; एस4 = 101;

एस5 = 1100; एस6 = 1101; एस 7 = 1110; एस 8 = 1111;

मैं इस बात पर ध्यान देना चाहता हूं कि वास्तव में क्या होता है जब हम विचारों का आदान-प्रदान करते हैं। उदाहरण के लिए, इस समय, मैं अपने दिमाग से आपके दिमाग में एक विचार स्थानांतरित करना चाहता हूं। मैं कुछ ऐसे शब्द कह रहा हूँ जिनके माध्यम से मुझे विश्वास है कि आप इस विचार को समझ (प्राप्त) कर सकेंगे।

लेकिन जब बाद में आप इस विचार को अपने मित्र को बताना चाहते हैं, तो आप निश्चित रूप से पूरी तरह से अलग शब्द कहेंगे। वास्तव में, अर्थ या अर्थ किसी विशेष शब्द के भीतर समाहित नहीं है। मैंने कुछ शब्दों का इस्तेमाल किया है, लेकिन आप एक ही विचार व्यक्त करने के लिए पूरी तरह से अलग शब्दों का इस्तेमाल कर सकते हैं। इस प्रकार, अलग-अलग शब्द एक ही जानकारी को संप्रेषित कर सकते हैं। लेकिन, जैसे ही आप अपने वार्ताकार को बताते हैं कि आप संदेश को नहीं समझते हैं, तो एक नियम के रूप में, वार्ताकार अर्थ बताने के लिए शब्दों का एक अलग सेट उठाएगा, दूसरा या तीसरा भी। इस प्रकार, जानकारी विशिष्ट शब्दों के समूह में निहित नहीं है। एक बार जब आप कुछ शब्द प्राप्त कर लेते हैं, तो शब्दों को उस विचार में अनुवाद करने का अच्छा काम करें जो वार्ताकार आपको बताना चाहता है।

वार्ताकार के अनुकूल होने के लिए हम शब्दों का चयन करना सीखते हैं। एक मायने में, हम अपने विचारों और चैनल में शोर के स्तर के अनुसार शब्दों का चयन करते हैं, हालांकि इस तरह की तुलना उस मॉडल को सटीक रूप से प्रतिबिंबित नहीं करती है जिसका उपयोग मैं डिकोडिंग प्रक्रिया में शोर का प्रतिनिधित्व करने के लिए करता हूं। बड़े संगठनों में, एक गंभीर समस्या वार्ताकार की यह सुनने में अक्षमता है कि दूसरा व्यक्ति क्या कह रहा है। उच्च पदों पर, कर्मचारी वही सुनते हैं जो वे सुनना चाहते हैं। कुछ मामलों में, कॉर्पोरेट सीढ़ी पर ऊपर जाते समय आपको इसे ध्यान में रखना होगा। औपचारिक रूप में सूचना का निरूपण हमारे जीवन की प्रक्रियाओं का एक आंशिक प्रतिबिंब है और इसे कंप्यूटर अनुप्रयोगों में औपचारिक नियमों की सीमाओं से बहुत दूर व्यापक अनुप्रयोग मिला है।

करने के लिए जारी...

पुस्तक के अनुवाद, लेआउट और प्रकाशन में कौन मदद करना चाहता है - व्यक्तिगत या ईमेल में लिखें [ईमेल संरक्षित]

वैसे हमने एक और मस्त किताब का अनुवाद भी लॉन्च किया है -

सूचना के विभिन्न स्रोतों, साथ ही उनके प्रसारण के चैनलों का विश्लेषण करने के लिए, एक मात्रात्मक माप होना आवश्यक है जो संदेश में निहित जानकारी की मात्रा का अनुमान लगाने और सिग्नल द्वारा ले जाने की अनुमति देगा। ऐसा उपाय 1946 में अमेरिकी वैज्ञानिक सी। शैनन द्वारा पेश किया गया था।

इसके अलावा, हम मानते हैं कि सूचना का स्रोत असतत है, प्राथमिक संदेशों (i,) का एक अनुक्रम देता है, जिनमें से प्रत्येक को असतत पहनावा (वर्णमाला) a, a 2 ,...,d A; कोसूचना स्रोत के वर्णमाला का आयतन है।

प्रत्येक प्राथमिक संदेश में सूचना के एक सेट के रूप में कुछ जानकारी होती है (विचाराधीन उदाहरण में) विचाराधीन सूचना स्रोत की स्थिति के बारे में। इस जानकारी के माप की मात्रा निर्धारित करने के लिए, इसकी शब्दार्थ सामग्री, साथ ही इसके प्राप्तकर्ता के लिए इस जानकारी के महत्व की डिग्री महत्वपूर्ण नहीं है। ध्यान दें कि संदेश प्राप्त करने से पहले, प्राप्तकर्ता को हमेशा अनिश्चितता होती है कि मैं कौन सा संदेश हूं। हर संभव में से उसे दिया जाएगा। इस अनिश्चितता का अनुमान i, संदेश के प्रसारण की पूर्व संभाव्यता P(i) का उपयोग करके लगाया जाता है। हम यह निष्कर्ष निकालते हैं कि एक असतत स्रोत के प्राथमिक संदेश में निहित जानकारी का एक उद्देश्य मात्रात्मक माप किसी दिए गए संदेश को चुनने की संभावना से निर्धारित होता है और इस संभावना के कार्य के रूप में सीसी निर्धारित करता है। वही कार्य अनिश्चितता की डिग्री को दर्शाता है कि जानकारी प्राप्त करने वाले के पास असतत स्रोत की स्थिति के बारे में है। यह निष्कर्ष निकाला जा सकता है कि अपेक्षित सूचना के बारे में अनिश्चितता की डिग्री सूचना प्रसारण चैनलों के लिए आवश्यकताओं को निर्धारित करती है।

सामान्य तौर पर, संभावना पी (ए,)कुछ प्रारंभिक संदेश के स्रोत का चुनाव i, (बाद में हम इसे प्रतीक कहेंगे) पहले चुने गए प्रतीकों पर निर्भर करता है, अर्थात। एक सशर्त संभावना है और इस तरह की पसंद की प्राथमिकता संभावना के साथ मेल नहीं खाएगा।

टिम वह ^ पी (ए:) = 1, चूंकि सभी मैं घटनाओं का एक पूरा समूह बनाता हूं

gyi), और इन प्रतीकों का चुनाव कुछ कार्यात्मक निर्भरता का उपयोग करके किया जाता है जे (ए,)= पी (ए,) = 1, यदि स्रोत द्वारा प्रतीक की पसंद प्राथमिकता निर्धारित है, जे (ए,)= ए "ए पी (ए टी, ए)इस तरह की पसंद की संभावना है, तो प्रतीकों की एक जोड़ी में निहित जानकारी की मात्रा प्रत्येक प्रतीक i और i में निहित जानकारी की मात्रा के योग के बराबर है। सूचना के मात्रात्मक माप के इस गुण को योगात्मकता कहा जाता है .

ऐसा हमारा विश्वास है पी (ए,)- चरित्र i को चुनने की सशर्त संभावना, इससे पहले के सभी वर्णों के बाद, और पी (ए,,i,) चिह्न i चुनने की सप्रतिबंध प्रायिकता है; मैं के बाद, और सभी पूर्ववर्ती, लेकिन, वह दिया पी (ए 1, ए 1) \u003d पी (ए) P(i,|i y), योगात्मकता की स्थिति लिखी जा सकती है

हम नोटेशन पेश करते हैं पी (ए) = पी पी पी (एआर) \u003d क्यूऔर फिर से लिखने की स्थिति (5.1):

ऐसा हमारा विश्वास है आर, ओ* 0. व्यंजक (5.2) का उपयोग करते हुए, हम फलन का रूप निर्धारित करते हैं (р (आर)।अवकलन करके, गुणा करके आर* 0 और निरूपण आरओ = आर,लिखो

ध्यान दें कि संबंध (5.3) किसी के लिए भी संतुष्ट है आर एफ ओ यू^^ ओ। हालाँकि, यह आवश्यकता (5.3) के दाएं और बाएं पक्षों की स्थिरता की ओर ले जाती है: पीक्यू>"(पी)=अर"(/?) - को -स्थिरांक। फिर हम समीकरण पर आते हैं पीसी> "(पी) = कोऔर एकीकरण के बाद हमें मिलता है

आइए ध्यान दें कि हम फिर से लिखेंगे

नतीजतन, जे (ए,) के गुणों पर दो शर्तों की पूर्ति के तहत, यह पता चला कि कार्यात्मक निर्भरता का रूप जे (ए,)प्रतीक चुनने की संभावना पर परस्थिर गुणांक तक कोविशिष्ट रूप से परिभाषित

गुणक कोकेवल पैमाने को प्रभावित करता है और सूचना की मात्रा को मापने के लिए इकाइयों की प्रणाली निर्धारित करता है। चूंकि एलएन [पी] एफ 0, तो यह चुनने के लिए समझ में आता है ओएस के लिए ताकि जानकारी की मात्रा का एक उपाय हो जे (ए)सकारात्मक था।

स्वीकार कर लिया के =-1, लिखो

यह निम्नानुसार है कि सूचना की मात्रा की इकाई उस सूचना के बराबर है जो एक घटना घटित हुई है, जिसकी संभावना बराबर है मुझे।सूचना की मात्रा की ऐसी इकाई को प्राकृतिक इकाई कहा जाता है। अधिक बार यह माना जाता है को= - तब

इस प्रकार, हम जानकारी की मात्रा की एक द्विआधारी इकाई में आए, जिसमें दो समान रूप से संभावित घटनाओं में से एक के घटित होने के बारे में एक संदेश होता है और इसे "बिट" कहा जाता है। संचार प्रौद्योगिकी में बाइनरी कोड के उपयोग के कारण यह इकाई व्यापक है। सामान्य मामले में लघुगणक का आधार चुनना, हम प्राप्त करते हैं

जहाँ लघुगणक एक स्वेच्छ आधार के साथ हो सकता है।

सूचनाओं के मात्रात्मक माप की योगात्मकता गुण अभिव्यक्ति (5.9) के आधार पर, प्रतीकों के अनुक्रम से युक्त संदेश में सूचना की मात्रा निर्धारित करने के लिए संभव बनाता है। इस तरह के अनुक्रम को चुनने वाले स्रोत की संभावना को पहले से उपलब्ध सभी संदेशों को ध्यान में रखकर लिया जाता है।

प्रारंभिक संदेश में निहित सूचना का मात्रात्मक माप a (, सूचना की औसत मात्रा का अंदाजा नहीं देता है जे (ए) स्रोत द्वारा जारी किया जाता है जब एक प्राथमिक संदेश का चयन किया जाता है एक घ

सूचना की औसत मात्रा सूचना के स्रोत को समग्र रूप से दर्शाती है और संचार प्रणालियों की सबसे महत्वपूर्ण विशेषताओं में से एक है।

आइए इस विशेषता को वर्णमाला के साथ स्वतंत्र संदेशों के असतत स्रोत के लिए परिभाषित करें को।द्वारा निरूपित करें पर)प्रति वर्ण सूचना की औसत मात्रा और एक यादृच्छिक चर L की गणितीय अपेक्षा है - एक यादृच्छिक रूप से चयनित वर्ण में निहित जानकारी की मात्रा ए

प्रति प्रतीक सूचना की औसत मात्रा को स्वतंत्र संदेशों के स्रोत की एन्ट्रॉपी कहा जाता है। अगले प्रतीक को चुनते समय एंट्रॉपी औसत प्राथमिक अनिश्चितता का सूचक है।

यह अभिव्यक्ति (5.10) से इस प्रकार है कि यदि संभावनाओं में से एक पी (ए)एक के बराबर है (इसलिए, अन्य सभी शून्य के बराबर हैं), तो सूचना स्रोत की एन्ट्रापी शून्य के बराबर होगी - संदेश पूरी तरह से परिभाषित है।

एन्ट्रापी अधिकतम होगी यदि सभी संभावित प्रतीकों की पूर्व संभावनाएँ समान हों को, अर्थात। आर (ए () = 1 /को,तब

यदि स्रोत स्वतंत्र रूप से प्रायिकता पी, = के साथ बाइनरी प्रतीकों का चयन करता है पी (एक एक्स)और पी 2 \u003d 1 - पी, फिर प्रति चरित्र एन्ट्रापी होगी

अंजीर पर। 16.1 दो बाइनरी प्रतीकों में से चुनने की एक प्राथमिक संभावना पर एक बाइनरी स्रोत की एन्ट्रापी की निर्भरता को दर्शाता है, यह आंकड़ा यह भी दर्शाता है कि एन्ट्रॉपी आर पर अधिकतम है, = आर 2 = 0,5

1 ओ 1 डीवीडी - और बाइनरी इकाइयों में लॉग 2 2 = 1-

चावल। 5.1। एंट्रॉपी निर्भरता पर कश्मीर = 2 उनमें से किसी एक को चुनने की संभावना पर

प्रतीकों के परिवर्तनीय विकल्प के साथ स्रोतों की एंट्रॉपी, लेकिन विभिन्न आकार के अक्षरों के साथ को,वृद्धि के साथ लघुगणकीय रूप से बढ़ता है को।

यदि प्रतीकों को चुनने की संभावना अलग है, तो स्रोत की एंट्रॉपी कम हो जाती है मैं एक)संभावित अधिकतम के सापेक्ष एच (ए) पीएसएच =लकड़ी का लट्ठा को।

प्रतीकों के बीच जितना अधिक सहसंबंध होता है, बाद के प्रतीकों को चुनने की स्वतंत्रता उतनी ही कम होती है और नए चयनित प्रतीक के पास कम जानकारी होती है। यह इस तथ्य के कारण है कि सशर्त वितरण की अनिश्चितता उनके बिना शर्त वितरण की एन्ट्रॉपी से अधिक नहीं हो सकती है। स्मृति और वर्णमाला के साथ स्रोत की एन्ट्रापी को निरूपित करें कोद्वारा एच(एए"),और स्मृति के बिना स्रोत की एन्ट्रापी, लेकिन एक ही वर्णमाला में - के माध्यम से पर)और असमानता साबित करें

नोटेशन पेश करके पी(एए")प्रतीक a चुनने की सशर्त प्रायिकता के लिए,(/ = 1, 2, को)यह मानते हुए कि प्रतीक पहले चुना गया है अजीज =1,2,को)और परिवर्तनों को छोड़ कर, हम बिना प्रमाण के लिखते हैं

जो असमानता (5.13) को सिद्ध करता है।

(5.13) या (5.14) में समानता कब प्राप्त की जाती है

इसका मतलब यह है कि किसी प्रतीक को चुनने की सशर्त संभावना इसे चुनने की बिना शर्त संभावना के बराबर होती है, जो केवल स्मृति रहित स्रोतों के लिए ही संभव है।

दिलचस्प बात यह है कि रूसी में पाठ की एन्ट्रॉपी प्रति वर्ण 1.5 बाइनरी यूनिट है। उसी समय, उसी वर्णमाला के साथ के = 32 स्वतंत्र और परिवर्तनीय प्रतीकों की स्थिति के साथ एच (ए) टीपी =प्रति वर्ण 5 बाइनरी वाले। इस प्रकार, आंतरिक कड़ियों की उपस्थिति ने एन्ट्रापी को लगभग 3.3 गुना कम कर दिया।

असतत स्रोत की एक महत्वपूर्ण विशेषता इसकी अतिरेक p और है:

सूचना स्रोत का अतिरेक भीतर एक आयामहीन मात्रा है। स्वाभाविक रूप से, अतिरेक के अभाव में p u = 0।

एक स्रोत से एक निश्चित मात्रा में सूचना प्रसारित करने के लिए जिसमें प्रतीकों के बीच सहसंबंध नहीं है, सभी प्रतीकों की समान संभावना के साथ, प्रेषित प्रतीकों की न्यूनतम संभव संख्या /7 मिनट: /आर 0 (/7 0 आर (एल अधिकतम)) आवश्यक है। एन्ट्रापी के साथ एक स्रोत से समान मात्रा में सूचना प्रसारित करने के लिए (प्रतीक आपस में जुड़े हुए हैं और असमान रूप से संभावित हैं), औसत संख्या में प्रतीकों की आवश्यकता होती है एन = एन "एच (ए) एम जेएच (ए)।

असतत स्रोत भी प्रदर्शन की विशेषता है, जो कि समय की प्रति इकाई वी एच के प्रतीकों की संख्या से निर्धारित होता है:

यदि प्रदर्शन मैं एक)बाइनरी इकाइयों में परिभाषित करें, और सेकंड में समय, फिर पर) -प्रति सेकंड बाइनरी इकाइयों की संख्या है। असतत स्रोतों के लिए जो पर्याप्त रूप से बड़ी लंबाई /? के स्थिर चरित्र अनुक्रम उत्पन्न करते हैं, निम्नलिखित अवधारणाएं पेश की जाती हैं: स्रोत वर्णों के विशिष्ट और असामान्य अनुक्रम, जिसमें लंबाई के सभी अनुक्रम पी।सभी विशिष्ट क्रम एनआईएल (ए)स्रोत पर पी-»oo के घटित होने की लगभग समान संभावना होती है

सभी असामान्य अनुक्रमों की घटना की कुल संभावना शून्य हो जाती है। समानता (5.11) के अनुसार, यह मानते हुए कि विशिष्ट अनुक्रमों की संभावना / एन आरएम (ए),स्रोत की एंट्रोपी logN TIin (,4) और फिर है

शोर के साथ असतत चैनल पर सूचना प्रसारण की मात्रा और गति पर विचार करें। पहले, हमने वर्णों के अनुक्रम (i) के रूप में असतत स्रोत द्वारा निर्मित जानकारी पर विचार किया।

अब मान लीजिए कि स्रोत जानकारी एन्कोडेड है और कोड प्रतीकों के अनुक्रम का प्रतिनिधित्व करती है (बी, (/ = 1,2,..टी -कोड बेस), एक असतत सूचना प्रसारण चैनल के अनुरूप है, जिसके आउटपुट पर प्रतीकों का एक क्रम दिखाई देता है

हम मानते हैं कि एन्कोडिंग ऑपरेशन एक-से-एक है - वर्णों के अनुक्रम द्वारा (बी,)कोई विशिष्ट रूप से अनुक्रम (i,) को पुनर्स्थापित कर सकता है, अर्थात कोड प्रतीकों द्वारा स्रोत जानकारी को पूरी तरह से पुनर्स्थापित करना संभव है।

हालांकि, अगर हम बचने वाले पात्रों पर विचार करें |?। j और इनपुट प्रतीक (/>,), फिर, सूचना प्रसारण चैनल में हस्तक्षेप की उपस्थिति के कारण, पुनर्प्राप्ति असंभव है। आउटपुट अनुक्रम की एन्ट्रापी //(/?)

इनपुट अनुक्रम की एन्ट्रापी से अधिक हो सकता है एच (बी), लेकिन प्राप्तकर्ता के लिए जानकारी की मात्रा में वृद्धि नहीं हुई।

सबसे अच्छे मामले में, इनपुट और आउटपुट के बीच एक-से-एक संबंध संभव है और उपयोगी जानकारी खो नहीं जाती है; सबसे खराब स्थिति में, सूचना प्रसारण चैनल के आउटपुट प्रतीकों से इनपुट प्रतीकों के बारे में कुछ नहीं कहा जा सकता है, चैनल में उपयोगी जानकारी पूरी तरह से खो गई है।

आइए एक शोर वाले चैनल में सूचना के नुकसान और एक शोर वाले चैनल पर प्रसारित सूचना की मात्रा का अनुमान लगाएं। हम मानते हैं कि संचरित वर्ण 6 के साथ, यह प्राप्त होता है, तो चरित्र सही ढंग से प्रेषित किया गया था

प्रतीक बी.जे.एक ही नंबर के साथ (/= जे)।फिर बिना शोर के एक आदर्श चैनल के लिए, हम लिखते हैं:

प्रतीक द्वारा बी.जे.असमानताओं के कारण चैनल आउटपुट पर (5.21)

अनिश्चितता अपरिहार्य है। हम मान सकते हैं कि प्रतीक में जानकारी बी मैंपूरी तरह से प्रसारित नहीं होता है और इसका कुछ हिस्सा हस्तक्षेप के कारण चैनल में खो जाता है। सूचना के एक मात्रात्मक माप की अवधारणा के आधार पर, हम मान लेंगे कि प्रतीक फीट प्राप्त करने के बाद चैनल के आउटपुट पर होने वाली अनिश्चितता की संख्यात्मक अभिव्यक्ति; :

और यह ट्रांसमिशन के दौरान चैनल में खोई हुई जानकारी की मात्रा निर्धारित करता है।

फिक्सिंग फीट। और औसत (5.22) सभी संभावित प्रतीकों पर, हम योग प्राप्त करते हैं

जो एक प्रतीक प्राप्त करते समय स्मृति के बिना एक चैनल पर एक प्राथमिक प्रतीक संचारित करते समय चैनल में खोई हुई जानकारी की मात्रा निर्धारित करता है बीजे (टी)।

सभी फीट के योग (5.23) का औसत निकालने पर, हमें Z?) का मान प्राप्त होता है, जिसे हम निरूपित करते हैं n(इन/इन-यह स्मृति रहित चैनल पर एक वर्ण को प्रसारित करते समय खोई हुई जानकारी की मात्रा निर्धारित करता है:

कहाँ प ^ bjbjj-किसी घटना की संयुक्त संभावना, जब संचरित होती है

प्रतीक बी।यह प्रतीक लेगा बीटी ।

एच [डब्ल्यू/सूचना के स्रोत की विशेषताओं पर निर्भर करता है

चैनल इनपुट मेंऔर संचार चैनल की संभाव्य विशेषताओं पर। सांख्यिकीय संचार सिद्धांत में शैनन के अनुसार एन (इन / इनचैनल अविश्वसनीयता कहा जाता है।

सशर्त एन्ट्रापी एचबी/बी, असतत स्रोत की एन्ट्रापी

चैनल इनपुट पर एच (डब्ल्यू)और एन्ट्रापी और ^ बी) इसके आउटपुट पर नहीं हो सकता

नकारात्मक। एक हस्तक्षेप मुक्त चैनल में, चैनल अविश्वसनीयता

एन (वी / वी = 0. (5.20) के अनुसार, हम ध्यान दें कि एच ^ वी / वी ^

और समानता तभी होती है जब चैनल के इनपुट और आउटपुट सांख्यिकीय रूप से स्वतंत्र होते हैं:

आउटपुट प्रतीक इनपुट प्रतीकों पर निर्भर नहीं होते हैं - टूटे हुए चैनल या बहुत मजबूत हस्तक्षेप का मामला।

पहले की तरह, विशिष्ट अनुक्रमों के लिए, हम लिख सकते हैं

यह कहना कि हस्तक्षेप के अभाव में, इसकी अविश्वसनीयता

चैनल पर औसतन प्रसारित जानकारी के तहत J[ b/ प्रति प्रतीक हम चैनल इनपुट पर सूचना की मात्रा के बीच के अंतर को समझते हैं जे (बी)और /? चैनल में खोई हुई जानकारी)।

यदि सूचना का स्रोत और चैनल बिना मेमोरी के हैं, तो

अभिव्यक्ति (5.27) चैनल के आउटपुट प्रतीकों की एंट्रॉपी निर्धारित करता है। चैनल के आउटपुट पर जानकारी का एक हिस्सा उपयोगी है, और बाकी गलत है, क्योंकि यह चैनल में हस्तक्षेप से उत्पन्न होता है। आइए ध्यान दें एन [वी/ 2?) चैनल में हस्तक्षेप के बारे में जानकारी व्यक्त करता है, और अंतर i(d)-I(d/d) - चैनल के माध्यम से पारित उपयोगी जानकारी।

ध्यान दें कि चैनल के आउटपुट पर बनने वाले अधिकांश अनुक्रम असामान्य हैं और उनकी कुल संभावना बहुत कम है।

एक नियम के रूप में, सबसे सामान्य प्रकार के हस्तक्षेप को ध्यान में रखा जाता है - योज्य शोर। एन (टी);चैनल के आउटपुट पर सिग्नल का रूप है:

असतत संकेतों के लिए, समतुल्य शोर, (5.28) के बाद, एक असतत संरचना है। शोर एक असतत यादृच्छिक अनुक्रम है, जो इनपुट और आउटपुट सिग्नल के अनुक्रम के समान है। आइए असतत चैनल में योगात्मक शोर के वर्णमाला के प्रतीकों को C1 = 0, 1,2, के रूप में निरूपित करें। टी- 1). ऐसे चैनल में सशर्त संक्रमण की संभावनाएं

क्योंकि और (^बी/?) और (बी) तो, परिणामस्वरूप, इनपुट के सापेक्ष असतत चैनल #(/) के आउटपुट अनुक्रम की जानकारी बी (टी)या विपरीत और (बी) - एच ^ इन / इन) (5)।

दूसरे शब्दों में, चैनल पर प्रेषित सूचना इसके इनपुट पर सूचना से अधिक नहीं हो सकती।

यदि चैनल इनपुट औसत प्राप्त करता है एक्स केएक सेकंड में प्रतीक, तो शोर वाले चैनल पर औसत सूचना अंतरण दर निर्धारित करना संभव है:

कहाँ एन (बी) = वी के जे (बी, बी ^ -चैनल इनपुट पर स्रोत प्रदर्शन; एन (इन / इन) \u003d यू टू एन (इन, इन) ~समय की प्रति इकाई चैनल की अविश्वसनीयता; एच (बी) = वी के एच ^ बी ^- चैनल के आउटपुट द्वारा गठित स्रोत का प्रदर्शन (उपयोगी का हिस्सा और झूठी जानकारी का हिस्सा देना); एच ^ इन / बी ^ \u003d यू टू 1 / (इन / इन)- झूठी सूचना की मात्रा,

प्रति यूनिट समय में चैनल में व्यवधान पैदा किया।

एक चैनल पर सूचना संचरण की मात्रा और गति की अवधारणाओं को संचार चैनल के विभिन्न वर्गों पर लागू किया जा सकता है। यह "एनकोडर इनपुट - डिकोडर आउटपुट" खंड हो सकता है।

ध्यान दें कि, विचाराधीन चैनल के खंड का विस्तार करके, इसके किसी भी घटक भागों पर गति को पार करना असंभव है। किसी भी अपरिवर्तनीय परिवर्तन से सूचना का नुकसान होता है। अपरिवर्तनीय परिवर्तनों में न केवल हस्तक्षेप का प्रभाव शामिल है, बल्कि अतिरेक के साथ कोड का पता लगाना, डिकोड करना भी शामिल है। प्राप्त हानि को कम करने के तरीके हैं। यह "सामान्य रूप से स्वागत" है।

असतत चैनल की बैंडविड्थ और इष्टतम कोडिंग प्रमेय पर विचार करें। शैनन ने एक विशेषता पेश की जो इनपुट संकेतों के संयोजन पर कई प्रतिबंधों के तहत ज्ञात गुणों (शोर) वाले चैनल पर अधिकतम संभव सूचना अंतरण दर निर्धारित करती है। यह चैनल सी की बैंडविड्थ है। असतत चैनल के लिए

जहां संभावित इनपुट स्रोतों द्वारा अधिकतम की रक्षा की जाती है मेंदिया गया वीकेऔर इनपुट वर्ण वर्णमाला का आयतन टी।

असतत चैनल के थ्रूपुट की परिभाषा के आधार पर हम लिखते हैं

ध्यान दें कि C = 0 स्वतंत्र इनपुट और आउटपुट (चैनल में उच्च शोर स्तर) के साथ और, तदनुसार,

संकेत पर हस्तक्षेप हस्तक्षेप के अभाव में।

मेमोरी के बिना बाइनरी सममित चैनल के लिए

चावल। 5.2।

पैरामीटर पर बाइनरी चैनल की क्षमता की निर्भरता का ग्राफ आरचित्र में दिखाया गया है। 5.2। पर आर= 1/2 चैनल बैंडविड्थ सी = 0, सशर्त एन्ट्रॉपी

//(/?//?) = 1. व्यावहारिक रुचि

ग्राफ 0 पर दर्शाता है

इष्टतम कोडिंग पर शैनन का मौलिक प्रमेय क्षमता की अवधारणा से संबंधित है। असतत चैनल के लिए इसका सूत्रीकरण इस प्रकार है: यदि संदेश स्रोत का प्रदर्शन पर)चैनल सी की बैंडविड्थ से कम:

वें इष्टतम कोडिंग और डिकोडिंग की एक विधि है, जिसके तहत चैनल की त्रुटि या अविश्वसनीयता की संभावना है n[a!A j मनमाने ढंग से छोटा हो सकता है। अगर

ऐसे कोई तरीके नहीं हैं।

शैनन के प्रमेय के अनुसार, परिमित मूल्य साथचैनल पर त्रुटि मुक्त सूचना अंतरण दर का सीमा मूल्य है। लेकिन एक शोर चैनल के लिए, इष्टतम कोड खोजने के तरीके इंगित नहीं किए गए हैं। हालाँकि, प्रमेय ने सूचना प्रसारण प्रौद्योगिकी की मूलभूत संभावनाओं पर विचारों को मौलिक रूप से बदल दिया। शैनन से पहले, यह माना जाता था कि एक शोर चैनल में सूचना अंतरण दर को शून्य तक कम करके मनमाने ढंग से छोटी त्रुटि संभावना प्राप्त करना संभव था। यह, उदाहरण के लिए, स्मृति रहित चैनल में चरित्र पुनरावृत्ति के परिणामस्वरूप संचार निष्ठा में वृद्धि है।

शैनन के प्रमेय के कई कठोर प्रमाण ज्ञात हैं। यादृच्छिक कोडिंग द्वारा असतत स्मृतिहीन चैनल के लिए प्रमेय सिद्ध किया गया था। इस मामले में, किसी दिए गए स्रोत और किसी दिए गए चैनल के लिए सभी बेतरतीब ढंग से चुने गए कोडों के सेट पर विचार किया जाता है और सभी कोडों पर गलत डिकोडिंग की औसत संभावना के शून्य के लिए स्पर्शोन्मुख दृष्टिकोण के तथ्य की अवधि में असीमित वृद्धि के साथ जोर दिया जाता है। संदेश अनुक्रम। इस प्रकार, केवल त्रुटि-मुक्त डिकोडिंग की संभावना प्रदान करने वाले कोड के अस्तित्व का तथ्य सिद्ध होता है, हालांकि, एक अस्पष्ट कोडिंग विधि प्रस्तावित नहीं है। साथ ही, सबूत के दौरान, यह स्पष्ट हो जाता है कि संदेश अनुक्रम के समेकन के एन्ट्रॉपी की समानता को बनाए रखते हुए और संचरण के लिए उपयोग किए जाने वाले कोड शब्दों के एक-से-एक संबंधित सेट, पहनावा मेंकोड प्रतीकों के अनुक्रम की पारस्परिक निर्भरता बढ़ाने के लिए अतिरिक्त अतिरेक पेश किया जाना चाहिए। यह केवल कोड अनुक्रमों के सेट का विस्तार करके किया जा सकता है जिसमें से कोड शब्द चुने गए हैं।

इस तथ्य के बावजूद कि शोर चैनलों के लिए मुख्य कोडिंग प्रमेय किसी विशेष कोड को चुनने के स्पष्ट तरीकों को इंगित नहीं करता है और वे प्रमेय के प्रमाण में भी अनुपस्थित हैं, यह दिखाया जा सकता है कि पर्याप्त रूप से लंबे संदेश को एन्कोडिंग करते समय यादृच्छिक रूप से चुने गए अधिकांश कोड अनुक्रम, गलत डिकोडिंग की औसत संभावना से थोड़ा अधिक है। हालांकि, मेमोरी सिस्टम को लागू करने में कठिनाइयों और बड़ी संख्या में कोड तत्वों के अनुक्रमों के तार्किक प्रसंस्करण के साथ-साथ सूचना के प्रसारण और प्रसंस्करण में देरी के कारण लंबे ब्लॉकों में कोडिंग की व्यावहारिक संभावनाएं सीमित हैं। वास्तव में, विशेष रुचि के परिणाम हैं जो परिमित अवधि के लिए गलत डिकोडिंग की संभावना निर्धारित करना संभव बनाते हैं पीप्रयुक्त कोड ब्लॉक। व्यवहार में, वे मध्यम विलंब मूल्यों तक सीमित हैं और चैनल बैंडविड्थ के अधूरे उपयोग के साथ संचरण संभावना में वृद्धि प्राप्त करते हैं।