रिचर्ड ह्यामिङ: अध्याय 13। सूचना सिद्धान्त

हामीले गर्यो!

"यस कोर्सको उद्देश्य तपाईको प्राविधिक भविष्यको लागि तपाईलाई तयार गर्नु हो।"

नमस्ते, Habr। गजबको लेख सम्झनुहोस् "तिमी र तिम्रो काम" (+219, 2588 बुकमार्क, 429k पढियो)?

त्यसैले ह्यामिङ (हो, हो, स्व-निगरानी र आत्म-सुधार ह्यामिङ कोडहरू) त्यहाँ एक पूर्ण छ पुस्तकउनको व्याख्यानको आधारमा लेखिएको हो। हामी यसलाई अनुवाद गर्छौं, किनभने मानिसले आफ्नो मनको कुरा गर्छ।

यो IT को बारेमा मात्र होइन, यो अविश्वसनीय रूपमा कूल मानिसहरूको सोच शैलीको बारेमा पुस्तक हो। "यो सकारात्मक सोचको बढावा मात्र होइन; यसले ती अवस्थाहरू वर्णन गर्दछ जसले ठूलो काम गर्ने सम्भावना बढाउँछ।"

अनुवादको लागि Andrey Pakhomov लाई धन्यवाद।

सूचना सिद्धान्त 1940 को दशक को अन्त मा C.E. Shannon द्वारा विकसित गरिएको थियो। बेल ल्याब्स प्रबन्धनले जोड दिए कि उसले यसलाई "सञ्चार सिद्धान्त" भन्यो किनभने ... यो धेरै सटीक नाम हो। स्पष्ट कारणहरूका लागि, "सूचना सिद्धान्त" नामले जनतामा धेरै ठूलो प्रभाव पारेको छ, जसका कारण शाननले यसलाई रोजेका छन्, र यो नाम हामीले आजसम्म जान्दछौं। नाम आफैंले सुझाव दिन्छ कि सिद्धान्तले जानकारीसँग सम्बन्धित छ, जसले यसलाई महत्त्वपूर्ण बनाउँछ जब हामी सूचना युगमा गहिरिएर जान्छौं। यस अध्यायमा, म यस सिद्धान्तबाट धेरै मुख्य निष्कर्षहरूमा छुनेछु, म यस सिद्धान्तका केही व्यक्तिगत प्रावधानहरूको कडा होइन, बरु सहज प्रमाण प्रदान गर्नेछु, ताकि तपाईंले "सूचना सिद्धान्त" वास्तवमा के हो भनेर बुझ्न सक्नुहुन्छ, जहाँ तपाइँ यसलाई लागू गर्न सक्नुहुन्छ। र कहाँ छैन।

सबैभन्दा पहिले, "जानकारी" भनेको के हो? शाननले जानकारीलाई अनिश्चिततासँग बराबरी गर्छ। उसले घटनाको सम्भाव्यताको नकारात्मक लोगारिदम छनोट गर्यो तपाईंले प्राप्त गर्नुभएको जानकारीको मात्रात्मक मापनको रूपमा जब सम्भाव्यता p भएको घटना हुन्छ। उदाहरणका लागि, यदि म तपाईंलाई लस एन्जलसको मौसम कुहिरो छ भनी भन्छु, तब p 1 को नजिक छ, जसले वास्तवमा हामीलाई धेरै जानकारी दिँदैन। तर यदि म भन्छु कि यो जुनमा मोन्टेरेमा वर्षा हुन्छ भने, सन्देशमा अनिश्चितता हुनेछ र यसले थप जानकारी समावेश गर्नेछ। लग १ = ० भएकोले भरपर्दो घटनामा कुनै जानकारी हुँदैन।

यसलाई थप विवरणमा हेरौं। शैनन विश्वास गर्थे कि जानकारीको मात्रात्मक मापन घटना पी को सम्भाव्यता को एक निरन्तर कार्य हुनुपर्छ, र स्वतन्त्र घटनाहरु को लागी यो additive हुनुपर्छ - दुई स्वतन्त्र घटनाहरु को घटना को परिणाम को रूप मा प्राप्त जानकारी को मात्रा बराबर हुनुपर्छ। संयुक्त घटना को घटना को परिणाम को रूप मा प्राप्त जानकारी को मात्रा। उदाहरण को लागी, पासा रोल र सिक्का रोल को नतिजा सामान्यतया स्वतन्त्र घटनाहरु को रूप मा व्यवहार गरिन्छ। माथिको गणितको भाषामा अनुवाद गरौं। यदि I (p) सम्भाव्यता p भएको घटनामा समावेश भएको जानकारीको मात्रा हो भने, सम्भाव्यता p1 र y सम्भावना p2 सँग दुई स्वतन्त्र घटनाहरू मिलेर बनेको संयुक्त घटनाको लागि हामीले प्राप्त गर्छौं।

(x र y स्वतन्त्र घटनाहरू हुन्)

यो कार्यात्मक Cauchy समीकरण हो, सबै p1 र p2 को लागि सही। यो कार्यात्मक समीकरण समाधान गर्न, मान्नुहोस्

p1 = p2 = p,

यो दिन्छ

यदि p1 = p2 र p2 = p भने

आदि घातांकका लागि मानक विधि प्रयोग गरेर यस प्रक्रियालाई विस्तार गर्दै, सबै परिमेय संख्याहरू m/n को लागि निम्न सत्य हो।

जानकारी मापनको अनुमानित निरन्तरताबाट, यसले निम्नानुसार गर्दछ कि लॉगरिदमिक प्रकार्य कार्यात्मक काउची समीकरणको एक मात्र निरन्तर समाधान हो।

सूचना सिद्धान्तमा, लगरिथम आधारलाई २ मा लिनु सामान्य कुरा हो, त्यसैले बाइनरी छनोटमा ठ्याक्कै १ बिट जानकारी हुन्छ। तसर्थ, जानकारी सूत्र द्वारा मापन गरिन्छ

रोक्नुहोस् र माथि के भयो बुझौं। सबैभन्दा पहिले, हामीले "सूचना" को अवधारणा परिभाषित गरेनौं; हामीले केवल यसको मात्रात्मक मापनको लागि सूत्र परिभाषित गर्यौं।

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

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

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

तपाईंले कुनै पनि शब्दावली प्रस्ताव गर्दा सोच्नको लागि यहाँ केहि छ। कसरी प्रस्तावित परिभाषा, जस्तै शैननको जानकारीको परिभाषा, तपाईंको मौलिक विचारसँग सहमत छ र यो कत्तिको फरक छ? त्यहाँ लगभग कुनै पनि शब्द छैन जुन तपाइँको अवधारणाको अघिल्लो दृष्टिकोणलाई ठ्याक्कै प्रतिबिम्बित गर्दछ, तर अन्ततः, यो प्रयोग गरिएको शब्दावली हो जसले अवधारणाको अर्थलाई प्रतिबिम्बित गर्दछ, त्यसैले स्पष्ट परिभाषा मार्फत केहि औपचारिकताले सधैं केहि आवाजको परिचय दिन्छ।

एउटा प्रणालीलाई विचार गर्नुहोस् जसको वर्णमालामा सम्भावनाहरू pi संग q प्रतीकहरू हुन्छन्। यस मामला मा जानकारी को औसत मात्रा प्रणालीमा (यसको अपेक्षित मान) बराबर छ:

यसलाई सम्भाव्यता वितरण {pi} भएको प्रणालीको एन्ट्रोपी भनिन्छ। हामी "इन्ट्रोपी" शब्द प्रयोग गर्छौं किनभने उही गणितीय रूप थर्मोडायनामिक्स र सांख्यिकीय मेकानिक्समा देखिन्छ। यही कारणले गर्दा "एन्ट्रोपी" शब्दले आफ्नो वरिपरि एक निश्चित महत्वको आभा सिर्जना गर्दछ, जुन अन्ततः उचित हुँदैन। नोटेशनको एउटै गणितीय रूपले प्रतीकहरूको एउटै व्याख्यालाई संकेत गर्दैन!

सम्भाव्यता वितरणको एन्ट्रोपी कोडिङ सिद्धान्तमा प्रमुख भूमिका खेल्छ। दुई फरक सम्भाव्यता वितरण pi र qi को लागि गिब्स असमानता यस सिद्धान्तको महत्त्वपूर्ण परिणामहरू मध्ये एक हो। त्यसैले हामीले त्यो प्रमाणित गर्नुपर्छ

प्रमाण स्पष्ट ग्राफमा आधारित छ, चित्र। 13.I, जसले त्यो देखाउँछ

र समानता तब मात्र प्राप्त हुन्छ जब x = 1। बायाँ तर्फबाट योगको प्रत्येक पदमा असमानता लागू गरौं:

यदि सञ्चार प्रणालीको वर्णमालामा q प्रतीकहरू छन् भने, प्रत्येक प्रतीकको प्रसारणको सम्भाव्यता qi = 1/q र प्रतिस्थापन गर्दै, हामीले गिब्स असमानताबाट प्राप्त गर्छौं।

चित्र 13.I

यसको मतलब यो हो कि यदि सबै q प्रतीकहरू प्रसारण गर्ने सम्भावना समान र बराबर - 1 / q छ भने, अधिकतम एन्ट्रोपी ln q बराबर हुन्छ, अन्यथा असमानता राख्छ।

विशिष्ट रूपमा डिकोडेबल कोडको मामलामा, हामीसँग क्राफ्टको असमानता छ

अब यदि हामी छद्म सम्भाव्यताहरू परिभाषित गर्छौं

जहाँ पक्कै पनि = 1, जुन गिब्सको असमानताबाट पछ्याउँछ,

र थोरै बीजगणित लागू गर्नुहोस् (याद गर्नुहोस् कि K ≤ 1, ताकि हामी लोगारिदमिक शब्द छोड्न सक्छौं, र सम्भवतः पछि असमानतालाई बलियो बनाउन सक्छौं), हामीले पाउँछौं।

जहाँ L औसत कोड लम्बाइ हो।

यसरी, एन्ट्रोपी कुनै पनि क्यारेक्टर-द्वारा-सिम्बोल कोडको लागि औसत कोडवर्ड लम्बाइ Lको लागि न्यूनतम बाउन्ड हो। यो हस्तक्षेप-रहित च्यानलको लागि शान्ननको प्रमेय हो।

अब सञ्चार प्रणालीहरूको सीमितताहरूको बारेमा मुख्य प्रमेयलाई विचार गर्नुहोस् जसमा जानकारी स्वतन्त्र बिट र आवाजको स्ट्रिमको रूपमा प्रसारित हुन्छ। यो बुझिन्छ कि एक बिट को सही प्रसारण को सम्भाव्यता P > 1/2 हो, र प्रसारण को समयमा बिट मान उल्टो हुनेछ (एउटा त्रुटि हुनेछ) को सम्भाव्यता Q = 1 - P को बराबर छ। सुविधा को लागी, हामी मान्नुहोस् कि त्रुटिहरू स्वतन्त्र छन् र प्रत्येक पठाइएको बिटको लागि त्रुटिको सम्भावना समान छ - त्यो हो, संचार च्यानलमा "सेतो आवाज" छ।

हामीसँग एउटा सन्देशमा एन्कोड गरिएको n बिटहरूको लामो स्ट्रिम एक-बिट कोडको n - आयामी विस्तार हो। हामी पछि n को मान निर्धारण गर्नेछौं। n-आयामिक स्पेसको बिन्दुको रूपमा n-bits समावेश भएको सन्देशलाई विचार गर्नुहोस्। हामीसँग एन-आयामी ठाउँ भएको हुनाले - र सरलताको लागि हामी प्रत्येक सन्देशको घटनाको समान सम्भावना छ भनी मान्नेछौं - त्यहाँ M सम्भावित सन्देशहरू छन् (M पनि पछि परिभाषित गरिनेछ), त्यसैले पठाइएको कुनै सन्देशको सम्भावना

(प्रेषक)
अनुसूची 13.II

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

जहाँ, पहिले जस्तै, P कुनै पनि पठाइएको बिटमा कुनै त्रुटि नहुने सम्भावना हो। n स्वतन्त्र बिटहरू पठाउँदा, च्यानल क्षमता द्वारा दिइएको छ

यदि हामी च्यानल क्षमताको नजिक छौं भने, हामीले प्रत्येक प्रतीक ai, i = 1, ..., M को लागि लगभग यति मात्रामा जानकारी पठाउनु पर्छ। प्रत्येक प्रतीक ai को घटनाको सम्भाव्यता 1 / M हो भनेर विचार गर्दै, हामीले पायौ

जब हामी कुनै पनि M समान सम्भावित सन्देश पठाउँछौं, हामीसँग हुन्छ

जब n बिटहरू पठाइन्छ, हामी nQ त्रुटिहरू हुने आशा गर्छौं। अभ्यासमा, n-bits भएको सन्देशको लागि, हामीले प्राप्त सन्देशमा लगभग nQ त्रुटिहरू हुनेछन्। ठूलो n को लागि, सापेक्ष भिन्नता (variation = वितरण चौडाई, )
n बढ्दै जाँदा त्रुटिहरूको संख्याको वितरण झन्झन् साँघुरो हुँदै जान्छ।

त्यसोभए, ट्रान्समिटर पक्षबाट, म सन्देश पठाउनको लागि ai लिन्छु र यसको वरिपरि त्रिज्याको साथ गोला कोर्छु।

जुन त्रुटि Q, (चित्र 2.II) को अपेक्षित संख्या भन्दा e13 को बराबर रकमले थोरै ठूलो छ। यदि n पर्याप्त ठूलो छ भने, त्यहाँ सन्देश बिन्दु bj को स्वेच्छाचारी रूपमा सानो सम्भाव्यता रिसीभर साइडमा देखा पर्दछ जुन यस क्षेत्र भन्दा बाहिर फैलिएको छ। ट्रान्समिटरको दृष्टिकोणबाट मैले यसलाई हेर्दा स्थितिलाई स्केच गरौं: हामीसँग ट्रान्समिट गरिएको सन्देश ai देखि प्राप्त सन्देश bj सम्मको कुनै पनि त्रिज्या छ जसमा त्रुटिको सम्भावना बराबर (वा लगभग बराबर) सामान्य वितरणमा, अधिकतममा पुग्छ। nQ मा। कुनै पनि दिइएको e2 को लागि, त्यहाँ n यति ठूलो छ कि नतिजा बिन्दु bj मेरो क्षेत्र बाहिर भएको सम्भावना तपाईलाई मनपर्ने सानो छ।

अब तपाईको पक्षबाट उही अवस्था हेरौं (चित्र 13.III)। रिसिभर साइडमा n-आयामिक स्पेसमा प्राप्त बिन्दु bj वरिपरि उही त्रिज्या r को एक गोला S(r) छ, जस्तै कि यदि प्राप्त सन्देश bj मेरो क्षेत्र भित्र छ भने, मैले पठाएको सन्देश ai तपाईंको भित्र छ। क्षेत्र।

त्रुटि कसरी हुन सक्छ? तलको तालिकामा वर्णन गरिएका मामिलाहरूमा त्रुटि हुन सक्छ:

चित्र 13.III

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

यदि सन्देश ai पठाइएको थियो भने त्रुटि Pe को सम्भाव्यताको लागि हामीसँग गणितीय समीकरण छ

हामीले दोस्रो कार्यकालमा पहिलो कारकलाई १ को रूपमा लिएर बाहिर निकाल्न सक्छौं। यसरी हामीले असमानता पाउँछौं।

यो स्पष्ट छ कि

यसैले

दायाँ तिर अन्तिम अवधिमा पुन: आवेदन दिनुहोस्

n पर्याप्त मात्रामा लिएर, पहिलो पदलाई चाहेको रूपमा सानो लिन सकिन्छ, केही संख्या d भन्दा कम भन्नुहोस्। त्यसैले हामीसँग छ

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

समान सम्भावना भएको कोड शब्दकोशहरू ½nM। निस्सन्देह, कोडबुक सिर्जना गर्ने अनियमित प्रक्रियाको अर्थ डुप्लिकेटको सम्भावना छ, साथै कोड बिन्दुहरू जुन एकअर्काको नजिक हुनेछन् र त्यसैले सम्भावित त्रुटिहरूको स्रोत हुनेछ। यदि यो कुनै पनि सानो चयन गरिएको त्रुटि स्तर भन्दा ठूलो सम्भाव्यता संग भएको छैन भने, दिइएको n पर्याप्त ठूलो छ भनेर प्रमाणित गर्नुपर्छ।
महत्त्वपूर्ण बिन्दु यो हो कि शाननले औसत त्रुटि फेला पार्न सबै सम्भावित कोडबुकहरू औसत गरे! हामी सबै सम्भावित अनियमित कोडबुकहरूको सेटमा औसत मान बुझाउन प्रतीक Av[।] प्रयोग गर्नेछौं। स्थिर d भन्दा माथिको औसत, निस्सन्देह, एक स्थिरता दिन्छ, किनकि प्रत्येक पदको औसतको लागि योगमा प्रत्येक अन्य पदहरू जस्तै हुन्छ,

जुन बढाउन सकिन्छ (M-1 M मा जान्छ)

कुनै पनि सन्देशको लागि, सबै कोडबुकहरूमा औसत गर्दा, एन्कोडिङ सबै सम्भावित मानहरू मार्फत चल्छ, त्यसैले बिन्दु गोलामा रहेको औसत सम्भावना भनेको स्पेसको कुल भोल्युममा गोलाको भोल्युमको अनुपात हो। गोलाको आयतन छ

जहाँ s=Q+e2 <1/2 र ns अनिवार्य रूपमा पूर्णांक हुनुपर्छ।

दायाँको अन्तिम पद यो योगफलमा सबैभन्दा ठूलो हो। पहिले, तथ्यांकका लागि स्टर्लिङ सूत्र प्रयोग गरेर यसको मूल्य अनुमान गरौं। त्यसपछि हामी यसको अगाडि पदको घट्दो गुणांकलाई हेर्नेछौं, ध्यान दिनुहोस् कि यो गुणांक बढ्दै जाँदा हामी बायाँ तिर जान्छौं, र त्यसैले हामी निम्न गर्न सक्छौं: (1) योगको मानलाई ज्यामितीय प्रगतिको योगमा सीमित गर्नुहोस्। यो प्रारम्भिक गुणांक, (२) ज्यामितीय प्रगतिलाई एनएस सर्तहरूबाट अनन्त संख्यामा सर्तहरूमा विस्तार गर्नुहोस्, (३) अनन्त ज्यामितीय प्रगतिको योगफल गणना गर्नुहोस् (मानक बीजगणित, केही महत्त्वपूर्ण छैन) र अन्तमा सीमित मान प्राप्त गर्नुहोस् (पर्याप्त रूपमा ठूलोको लागि। n):

बिनोमियल पहिचानमा एन्ट्रोपी H(हरू) कसरी देखा पर्‍यो याद गर्नुहोस्। नोट गर्नुहोस् कि टेलर शृङ्खला विस्तार H(s)=H(Q+e2) ले पहिलो व्युत्पन्नलाई मात्र ध्यानमा राखेर र अरू सबैलाई बेवास्ता गरेर प्राप्त गरिएको अनुमान दिन्छ। अब अन्तिम अभिव्यक्ति सँगै राखौं:

जहाँ

हामीले गर्नुपर्ने भनेको e2 छनोट गर्नु हो कि e3 < e1, र त्यसपछि अन्तिम पद स्वेच्छाचारी रूपमा सानो हुनेछ, जबसम्म n पर्याप्त ठूलो छ। फलस्वरूप, च्यानल क्षमता स्वेच्छाचारी रूपमा C को नजिकको साथ औसत PE त्रुटि चाहिने जति सानो प्राप्त गर्न सकिन्छ।
यदि सबै कोडहरूको औसतमा पर्याप्त सानो त्रुटि छ भने, कम्तिमा एउटा कोड उपयुक्त हुनुपर्छ, त्यसैले त्यहाँ कम्तिमा एउटा उपयुक्त कोडिङ प्रणाली छ। यो श्यानन द्वारा प्राप्त एक महत्वपूर्ण परिणाम हो - "शोर च्यानल को लागी शान्ननको प्रमेय", यद्यपि यो ध्यान दिनु पर्छ कि उनले यो मैले प्रयोग गरेको साधारण बाइनरी सिमेट्रिक च्यानल भन्दा धेरै सामान्य मामलाको लागि प्रमाणित गरे। सामान्य अवस्थामा, गणितीय गणनाहरू धेरै जटिल छन्, तर विचारहरू धेरै फरक छैनन्, त्यसैले धेरै पटक, एक विशेष केसको उदाहरण प्रयोग गरेर, तपाइँ प्रमेयको सही अर्थ प्रकट गर्न सक्नुहुन्छ।

नतिजाको आलोचना गरौं । हामीले बारम्बार दोहोर्यायौं: "पर्याप्त ठूलो एनको लागि।" तर एन कति ठूलो छ? धेरै, धेरै ठूलो यदि तपाईं साँच्चै च्यानल क्षमताको नजिक हुन चाहनुहुन्छ र सही डाटा स्थानान्तरणमा निश्चित हुनुहोस्! यति ठुलो, वास्तवमा, तपाईंले यसलाई पछि ईन्कोड गर्नको लागि पर्याप्त बिटहरूको सन्देश सङ्कलन गर्न धेरै लामो समय कुर्नुपर्नेछ। यस अवस्थामा, यादृच्छिक कोड शब्दकोशको आकार मात्र ठूलो हुनेछ (जस्तै, यस्तो शब्दकोश सबै Mn बिटहरूको पूर्ण सूची भन्दा छोटो रूपमा प्रतिनिधित्व गर्न सकिँदैन, तथ्यको बावजुद n र M धेरै ठूलो छन्)!

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

एकै समयमा, माथि प्रमाणित प्रमेय अझै पनि अर्थहीन छैन! यसले देखाउँछ कि कुशल प्रसारण प्रणालीहरूले धेरै लामो बिट स्ट्रिङहरूको लागि चतुर एन्कोडिङ योजनाहरू प्रयोग गर्नुपर्छ। एउटा उदाहरण बाहिरी ग्रहहरूभन्दा बाहिर उडेका उपग्रहहरू हुन्; जब तिनीहरू पृथ्वी र सूर्यबाट टाढा जान्छन्, तिनीहरू डेटा ब्लकमा अधिक र अधिक त्रुटिहरू सच्याउन बाध्य हुन्छन्: केही उपग्रहहरूले सौर्य प्यानलहरू प्रयोग गर्छन्, जसले लगभग 5 W प्रदान गर्दछ, अरूले परमाणु ऊर्जा स्रोतहरू प्रयोग गर्छन्, जसले लगभग समान शक्ति प्रदान गर्दछ। पावर सप्लाईको कम पावर, ट्रान्समिटर डिशहरूको सानो आकार र पृथ्वीमा रिसीभर डिशहरूको सीमित आकार, सिग्नलले यात्रा गर्नुपर्ने ठूलो दूरी - यी सबैलाई निर्माण गर्न उच्च स्तरको त्रुटि सुधारको साथ कोडहरू प्रयोग गर्न आवश्यक छ। प्रभावकारी संचार प्रणाली।

हामीले माथिको प्रमाणमा प्रयोग गरेको n-आयामी ठाउँमा फर्कौं। यसको बारेमा छलफल गर्दा, हामीले गोलाको लगभग सम्पूर्ण भोल्युम बाहिरी सतह नजिकै केन्द्रित भएको देख्यौं - यसैले, यो लगभग निश्चित छ कि पठाइएको संकेत प्राप्त संकेत वरिपरि बनाइएको क्षेत्रको सतह नजिकै अवस्थित हुनेछ, एक अपेक्षाकृत संग पनि। यस्तो क्षेत्र को सानो त्रिज्या। त्यसकारण, यो अचम्मको कुरा होइन कि प्राप्त गरिएको संकेत, स्वेच्छाचारी रूपमा ठूलो संख्यामा त्रुटिहरू सच्याएपछि, nQ, त्रुटिहरू बिना संकेतको नजिक मनमानी रूपमा बाहिर निस्कन्छ। हामीले पहिले छलफल गरेको लिङ्क क्षमता यो घटना बुझ्नको लागि कुञ्जी हो। याद गर्नुहोस् कि त्रुटि सुधार गर्ने ह्यामिङ कोडहरूको लागि निर्माण गरिएका समान क्षेत्रहरू एकअर्कालाई ओभरल्याप गर्दैनन्। n-आयामिक स्पेसमा लगभग ओर्थोगोनल आयामहरूको ठूलो संख्याले हामी किन थोरै ओभरल्यापको साथ अन्तरिक्षमा M क्षेत्रहरू फिट गर्न सक्छौं भनेर देखाउँछ। यदि हामीले एउटा सानो, स्वेच्छाचारी रूपमा सानो ओभरल्यापलाई अनुमति दियौं, जसले डिकोडिङको क्रममा थोरै मात्र त्रुटिहरू निम्त्याउन सक्छ, हामी अन्तरिक्षमा गोलाहरूको घना स्थान प्राप्त गर्न सक्छौं। ह्यामिङले त्रुटि सुधारको निश्चित स्तरको ग्यारेन्टी गर्‍यो, श्यानन - त्रुटिको कम सम्भावना, तर एकै समयमा वास्तविक थ्रुपुटलाई मनपरी रूपमा सञ्चार च्यानलको क्षमताको नजिक राख्दै, जुन ह्यामिङ कोडहरूले गर्न सक्दैन।

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

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

अब हामी IQ परीक्षणको एउटा उदाहरण हेर्नेछौं जहाँ परिभाषा तपाईलाई मन परेको गोलाकार र परिणाम स्वरूप, भ्रामक छ। एक परीक्षण सिर्जना गरिएको छ जुन बुद्धि मापन गर्न मानिन्छ। यसलाई सकेसम्म एकरूप बनाउन यसलाई परिमार्जन गरिन्छ, र त्यसपछि यसलाई प्रकाशित गरिन्छ र, सरल विधिमा, क्यालिब्रेट गरिन्छ ताकि "बुद्धिमत्ता" मापन गरिएको सामान्य रूपमा वितरित हुन्छ (अंकांकन वक्रमा, अवश्य पनि)। सबै परिभाषाहरू पुन: जाँच गरिनु पर्छ, तिनीहरू पहिलो प्रस्तावित हुँदा मात्र होइन, तर धेरै पछि पनि, जब तिनीहरू निकालिएका निष्कर्षहरूमा प्रयोग गरिन्छ। समस्या समाधानको लागि परिभाषित सीमानाहरू कति हदसम्म उपयुक्त छन्? कति पटक एउटै सेटिङमा दिइएका परिभाषाहरू एकदम फरक सेटिङहरूमा लागू गर्न आउँछन्? यो धेरै पटक हुन्छ! मानविकीहरूमा, जुन तपाईंले आफ्नो जीवनमा अनिवार्य रूपमा सामना गर्नुहुनेछ, यो प्रायः हुन्छ।

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

एडिङ्टनको प्रसिद्ध कथाले समुद्रमा जाल लगाएर माछा मार्ने मानिसहरूको बारेमा बताउँछ। तिनीहरूले समातेको माछाको आकार अध्ययन गरेपछि, तिनीहरूले समुद्रमा पाइने माछाको न्यूनतम आकार निर्धारण गरे! तिनीहरूको निष्कर्ष वास्तविकता द्वारा होइन, प्रयोग गरिएको उपकरण द्वारा संचालित थियो।

फेरि जारी राखौंला…

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

खैर, हामीले अर्को सुन्दर पुस्तकको अनुवाद पनि सुरु गरेका छौं - "द ड्रीम मेसिन: द स्टोरी अफ द कम्प्युटर रिभोलुसन")

हामी विशेष गरी खोजिरहेका छौं जसले अनुवाद गर्न मद्दत गर्नेछ बोनस अध्याय, जुन भिडियोमा मात्र छ। (10 मिनेटको लागि स्थानान्तरण, पहिलो 20 पहिले नै लिइएको छ)

पुस्तकको सामग्री र अनुवादित अध्यायहरूForeword

1. विज्ञान र इन्जिनियरिङको कलाको परिचय: लर्निङ टु लर्न (मार्च २८, १९९५) अनुवाद: अध्याय 1
2. "डिजिटल (असक्रित) क्रान्तिको आधारहरू" (मार्च ३०, १९९५) अध्याय 2. डिजिटल (असक्रित) क्रान्तिको आधारभूत कुराहरू
3. "कम्प्युटरको इतिहास - हार्डवेयर" (मार्च ३१, १९९५) अध्याय 3. कम्प्युटरको इतिहास - हार्डवेयर
4. "कम्प्युटरको इतिहास - सफ्टवेयर" (अप्रिल ४, १९९५) अध्याय 4. कम्प्युटरको इतिहास - सफ्टवेयर
5. "कम्प्युटरको इतिहास - अनुप्रयोगहरू" (अप्रिल ६, १९९५) अध्याय 5: कम्प्युटरको इतिहास - व्यावहारिक अनुप्रयोगहरू
6. "कृत्रिम बुद्धिमत्ता - भाग I" (अप्रिल ७, १९९५) अध्याय 6. कृत्रिम बुद्धिमत्ता - 1
7. "कृत्रिम बुद्धिमत्ता - भाग II" (अप्रिल 11, 1995) अध्याय 7. कृत्रिम बुद्धिमत्ता - II
8. "कृत्रिम बुद्धिमत्ता III" (अप्रिल 13, 1995) अध्याय 8. कृत्रिम बुद्धिमत्ता-III
9. "n-Dimensional Space" (अप्रिल 14, 1995) अध्याय 9. N-आयामी ठाउँ
10. "कोडिङ सिद्धान्त - सूचना को प्रतिनिधित्व, भाग I" (अप्रिल 18, 1995) अध्याय 10. कोडिङ सिद्धान्त - I
11. "कोडिङ सिद्धान्त - सूचना को प्रतिनिधित्व, भाग II" (अप्रिल 20, 1995) अध्याय 11. कोडिङ थ्योरी - II
12. "त्रुटि-सुधार कोडहरू" (अप्रिल २१, १९९५) अध्याय 12. त्रुटि सुधार कोडहरू
13. "सूचना सिद्धान्त" (अप्रिल २५, १९९५) अध्याय 13. सूचना सिद्धान्त
14. "डिजिटल फिल्टर, भाग I" (अप्रिल २७, १९९५) अध्याय 14. डिजिटल फिल्टर - 1
15. "डिजिटल फिल्टर, भाग II" (अप्रिल २८, १९९५) अध्याय 15. डिजिटल फिल्टर - 2
16. "डिजिटल फिल्टर, भाग III" (मे २, १९९५) अध्याय 16. डिजिटल फिल्टर - 3
17. "डिजिटल फिल्टर, भाग IV" (मे ४, १९९५) अध्याय 17. डिजिटल फिल्टर - IV
18. "सिमुलेशन, भाग I" (मे ५, १९९५) अध्याय 18. मोडलिङ - I
19. "सिमुलेशन, भाग II" (मे ९, १९९५) अध्याय 19. मोडलिङ - II
20. "सिमुलेशन, भाग III" (मे ११, १९९५) अध्याय 20. मोडलिङ - III
21. "फाइबर अप्टिक्स" (मे १२, १९९५) अध्याय २१। फाइबर अप्टिक्स
22. "कम्प्युटर एडेड निर्देशन" (मे १६, १९९५) अध्याय 22: कम्प्युटर असिस्टेड इन्स्ट्रक्शन (CAI)
23. "गणित" (मे १८, १९९५) अध्याय 23. गणित
24. "क्वान्टम मेकानिक्स" (मे १९, १९९५) अध्याय 24. क्वान्टम मेकानिक्स
25. "सिर्जनशीलता" (मे २३, १९९५)। अनुवाद: अध्याय 25. रचनात्मकता
26. "विज्ञहरू" (मे २५, १९९५) अध्याय 26। विशेषज्ञहरू
27. "अविश्वसनीय डाटा" (मे २६, १९९५) अध्याय 27. अविश्वसनीय डाटा
28. "सिस्टम इन्जिनियरिङ्" (मे ३०, १९९५) अध्याय २८। प्रणाली इन्जिनियरिङ्
29. "तपाईंले के मापन गर्नुहुन्छ" (जून 1, 1995) अध्याय 29: तपाईले के मापन गर्नुहुन्छ तपाईले पाउनु हुन्छ
30. "हामीलाई के थाहा छ भनेर हामी कसरी जान्दछौं" (जुन 2, 1995) १० मिनेटको टुक्रामा अनुवाद गर्नुहोस्
31. ह्यामिङ, "तपाईं र तपाईंको अनुसन्धान" (जुन 6, 1995)। अनुवाद: तपाईं र तपाईंको काम

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

स्रोत: www.habr.com