রিচার্ড হ্যামিং: অধ্যায় 13. তথ্য তত্ত্ব

আমরা এটা করেছি!

"এই কোর্সের উদ্দেশ্য হল আপনাকে আপনার প্রযুক্তিগত ভবিষ্যতের জন্য প্রস্তুত করা।"

হ্যালো, হাবর। দুর্দান্ত নিবন্ধটি মনে রাখবেন "আপনি এবং আপনার কাজ" (+219, 2588 বুকমার্ক, 429k পঠিত)?

তাই হ্যামিং (হ্যাঁ, হ্যাঁ, স্ব-পর্যবেক্ষণ এবং স্ব-সংশোধনকারী হ্যামিং কোড) একটি সম্পূর্ণ আছে একটি বই, তার লেকচারের উপর ভিত্তি করে লেখা। আমরা এটি অনুবাদ করি, কারণ মানুষটি তার মনের কথা বলে।

এটি একটি বই শুধুমাত্র আইটি সম্পর্কে নয়, এটি অবিশ্বাস্যভাবে শান্ত মানুষের চিন্তার শৈলী সম্পর্কে একটি বই। "এটি কেবল ইতিবাচক চিন্তাভাবনার উত্সাহ নয়; এটি এমন অবস্থার বর্ণনা করে যা মহান কাজ করার সম্ভাবনা বাড়ায়।"

অনুবাদের জন্য আন্দ্রে পাখোমভকে ধন্যবাদ।

তথ্য তত্ত্বটি 1940 এর দশকের শেষের দিকে সি.ই. শ্যানন দ্বারা তৈরি করা হয়েছিল। বেল ল্যাবস ম্যানেজমেন্ট জোর দিয়েছিল যে তিনি এটিকে "যোগাযোগ তত্ত্ব" বলে ডাকেন কারণ... এটি অনেক বেশি সঠিক নাম। সুস্পষ্ট কারণগুলির জন্য, "তথ্য তত্ত্ব" নামটি জনসাধারণের উপর অনেক বেশি প্রভাব ফেলে, এই কারণেই শ্যানন এটিকে বেছে নিয়েছিলেন এবং এটি আমরা আজ অবধি পরিচিত নাম। নামটি নিজেই পরামর্শ দেয় যে তত্ত্বটি তথ্যের সাথে কাজ করে, যা তথ্য যুগের গভীরে যাওয়ার সাথে সাথে এটিকে গুরুত্বপূর্ণ করে তোলে। এই অধ্যায়ে, আমি এই তত্ত্ব থেকে কয়েকটি প্রধান উপসংহারে স্পর্শ করব, আমি এই তত্ত্বের কিছু স্বতন্ত্র বিধানের কঠোর নয়, বরং স্বজ্ঞাত প্রমাণ প্রদান করব, যাতে আপনি বুঝতে পারেন যে "তথ্য তত্ত্ব" আসলে কী, যেখানে আপনি এটি প্রয়োগ করতে পারেন এবং কোথায় না.

প্রথমত, "তথ্য" কি? শ্যানন তথ্যকে অনিশ্চয়তার সাথে সমান করে। তিনি একটি ইভেন্টের সম্ভাব্যতার নেতিবাচক লগারিদমকে বেছে নিয়েছিলেন যখন আপনি প্রাপ্ত তথ্যের পরিমাণগত পরিমাপ হিসাবে যখন একটি সম্ভাব্যতা p সহ একটি ঘটনা ঘটে। উদাহরণস্বরূপ, যদি আমি আপনাকে বলি যে লস অ্যাঞ্জেলেসের আবহাওয়া কুয়াশাচ্ছন্ন, তাহলে p 1 এর কাছাকাছি, যা সত্যিই আমাদের খুব বেশি তথ্য দেয় না। কিন্তু আমি যদি বলি যে জুনে মন্টেরিতে বৃষ্টি হচ্ছে, তাহলে বার্তায় অনিশ্চয়তা থাকবে এবং এতে আরও তথ্য থাকবে। একটি নির্ভরযোগ্য ইভেন্টে কোনো তথ্য থাকে না, যেহেতু লগ 1 = 0।

এর আরো বিস্তারিতভাবে এই তাকান. শ্যানন বিশ্বাস করতেন যে তথ্যের পরিমাণগত পরিমাপ একটি ইভেন্ট p এর সম্ভাব্যতার একটি অবিচ্ছিন্ন ফাংশন হওয়া উচিত এবং স্বাধীন ইভেন্টগুলির জন্য এটি সংযোজন হওয়া উচিত - দুটি স্বাধীন ঘটনা ঘটার ফলে প্রাপ্ত তথ্যের পরিমাণ সমান হওয়া উচিত। একটি যৌথ ঘটনা ঘটার ফলে প্রাপ্ত তথ্যের পরিমাণ। উদাহরণস্বরূপ, একটি ডাইস রোল এবং একটি কয়েন রোলের ফলাফলকে সাধারণত স্বাধীন ঘটনা হিসাবে বিবেচনা করা হয়। আসুন আমরা উপরেরটি গণিতের ভাষায় অনুবাদ করি। যদি I (p) সম্ভাব্যতা p সহ একটি ইভেন্টে থাকা তথ্যের পরিমাণ হয়, তাহলে সম্ভাব্যতা p1 সহ y এবং সম্ভাব্য p2 সহ দুটি স্বাধীন ইভেন্ট নিয়ে গঠিত যৌথ ইভেন্টের জন্য আমরা পাই

(x এবং y স্বাধীন ঘটনা)

এটি কার্যকরী কচি সমীকরণ, সমস্ত p1 এবং p2 এর জন্য সত্য। এই কার্যকরী সমীকরণটি সমাধান করতে, ধরে নিন

p1 = p2 = p,

এই দেয়

p1 = p2 এবং p2 = p হলে

ইত্যাদি সূচকগুলির জন্য আদর্শ পদ্ধতি ব্যবহার করে এই প্রক্রিয়াটি প্রসারিত করা, সমস্ত মূলদ সংখ্যার জন্য নিম্নলিখিতটি সত্য

তথ্য পরিমাপের অনুমান ধারাবাহিকতা থেকে, এটি অনুসরণ করে যে লগারিদমিক ফাংশন হল কচি কার্যকরী সমীকরণের একমাত্র অবিচ্ছিন্ন সমাধান।

তথ্য তত্ত্বে, লগারিদমের ভিত্তি 2 হওয়া সাধারণ, তাই একটি বাইনারি পছন্দে ঠিক 1 বিট তথ্য থাকে। অতএব, তথ্য সূত্র দ্বারা পরিমাপ করা হয়

চলুন বিরতি এবং বুঝতে উপরে কি ঘটেছে. প্রথমত, আমরা "তথ্য" ধারণাটি সংজ্ঞায়িত করিনি; আমরা কেবলমাত্র এর পরিমাণগত পরিমাপের সূত্রটি সংজ্ঞায়িত করেছি।

দ্বিতীয়ত, এই পরিমাপটি অনিশ্চয়তার সাপেক্ষে, এবং যদিও এটি যৌক্তিকভাবে মেশিনের জন্য উপযুক্ত-উদাহরণস্বরূপ, টেলিফোন সিস্টেম, রেডিও, টেলিভিশন, কম্পিউটার ইত্যাদি-এটি তথ্যের প্রতি সাধারণ মানুষের মনোভাব প্রতিফলিত করে না।

তৃতীয়ত, এটি একটি আপেক্ষিক পরিমাপ, এটি আপনার জ্ঞানের বর্তমান অবস্থার উপর নির্ভর করে। আপনি যদি একটি র্যান্ডম সংখ্যা জেনারেটর থেকে "এলোমেলো সংখ্যা" এর একটি স্ট্রীম দেখেন, আপনি অনুমান করবেন যে প্রতিটি পরবর্তী সংখ্যা অনিশ্চিত, কিন্তু আপনি যদি "র্যান্ডম সংখ্যা" গণনার সূত্রটি জানেন তবে পরবর্তী সংখ্যাটি জানা যাবে, এবং তাই হবে না তথ্য ধারণ

তাই শ্যাননের তথ্যের সংজ্ঞা অনেক ক্ষেত্রে মেশিনের জন্য উপযুক্ত, কিন্তু শব্দটি মানুষের বোঝার সাথে মানানসই বলে মনে হয় না। এই কারণেই "তথ্য তত্ত্ব" কে "যোগাযোগ তত্ত্ব" বলা উচিত ছিল। যাইহোক, সংজ্ঞাগুলি পরিবর্তন করতে অনেক দেরি হয়ে গেছে (যা তত্ত্বটিকে তার প্রাথমিক জনপ্রিয়তা দিয়েছে এবং যা এখনও লোকেদের মনে করে যে এই তত্ত্বটি "তথ্য" নিয়ে কাজ করে), তাই আমাদের তাদের সাথে থাকতে হবে, কিন্তু একই সাথে আপনাকে অবশ্যই শ্যাননের তথ্যের সংজ্ঞা তার সাধারণভাবে ব্যবহৃত অর্থ থেকে কতটা দূরে তা স্পষ্টভাবে বুঝতে পারেন। শ্যাননের তথ্য সম্পূর্ণ ভিন্ন কিছু নিয়ে কাজ করে, যথা অনিশ্চয়তা।

আপনি যখন কোন পরিভাষা প্রস্তাব করেন তখন এখানে চিন্তা করার কিছু আছে। কিভাবে একটি প্রস্তাবিত সংজ্ঞা, যেমন তথ্যের শ্যাননের সংজ্ঞা, আপনার মূল ধারণার সাথে একমত এবং এটি কতটা ভিন্ন? এমন কোন শব্দ নেই যা আপনার ধারণার পূর্ববর্তী দৃষ্টিভঙ্গিকে সঠিকভাবে প্রতিফলিত করে, কিন্তু শেষ পর্যন্ত, এটি ব্যবহৃত পরিভাষা যা ধারণাটির অর্থ প্রতিফলিত করে, তাই স্পষ্ট সংজ্ঞার মাধ্যমে কিছুকে আনুষ্ঠানিক করা সবসময় কিছু শব্দের পরিচয় দেয়।

এমন একটি সিস্টেমের কথা বিবেচনা করুন যার বর্ণমালায় q চিহ্ন রয়েছে এবং সম্ভাব্যতা pi। এক্ষেত্রে তথ্যের গড় পরিমাণ সিস্টেমে (এর প্রত্যাশিত মান) এর সমান:

এটিকে বলা হয় সম্ভাব্যতা বন্টন {pi} সহ সিস্টেমের এনট্রপি। আমরা "এনট্রপি" শব্দটি ব্যবহার করি কারণ একই গাণিতিক ফর্ম তাপগতিবিদ্যা এবং পরিসংখ্যানগত বলবিদ্যায় উপস্থিত হয়। এই কারণেই "এনট্রপি" শব্দটি নিজের চারপাশে গুরুত্বের একটি নির্দিষ্ট আভা তৈরি করে, যা শেষ পর্যন্ত ন্যায়সঙ্গত নয়। স্বরলিপির একই গাণিতিক ফর্ম প্রতীকগুলির একই ব্যাখ্যাকে বোঝায় না!

সম্ভাব্যতা বন্টনের এনট্রপি কোডিং তত্ত্বে একটি প্রধান ভূমিকা পালন করে। দুটি ভিন্ন সম্ভাব্যতা বন্টনের জন্য গিবস অসমতা pi এবং qi এই তত্ত্বের একটি গুরুত্বপূর্ণ পরিণতি। তাই আমাদের এটা প্রমাণ করতে হবে

প্রমাণ একটি সুস্পষ্ট গ্রাফ উপর ভিত্তি করে, চিত্র. 13.I, যা দেখায় যে

এবং সমতা তখনই অর্জিত হয় যখন x = 1। আসুন বাম দিক থেকে যোগফলের প্রতিটি পদে অসমতা প্রয়োগ করি:

যদি একটি যোগাযোগ ব্যবস্থার বর্ণমালায় q চিহ্ন থাকে, তাহলে প্রতিটি চিহ্ন qi = 1/q এবং q প্রতিস্থাপনের সম্ভাব্যতা গ্রহণ করলে, আমরা গিবস অসমতা থেকে পাই

চিত্র 13.I

এর মানে হল যে যদি সমস্ত q চিহ্ন প্রেরণের সম্ভাবনা একই এবং সমান হয় - 1 / q, তবে সর্বাধিক এনট্রপি ln q এর সমান, অন্যথায় অসমতা ধরে থাকে।

একটি অনন্যভাবে ডিকোডেবল কোডের ক্ষেত্রে, আমাদের ক্র্যাফ্টের অসমতা রয়েছে

এখন যদি আমরা ছদ্ম-সম্ভাবনা সংজ্ঞায়িত করি

যেখানে অবশ্যই = 1, যা গিবসের অসমতা থেকে অনুসরণ করে,

এবং একটু বীজগণিত প্রয়োগ করুন (মনে রাখবেন যে K ≤ 1, যাতে আমরা লগারিদমিক শব্দটি বাদ দিতে পারি এবং সম্ভবত পরবর্তীতে অসমতাকে শক্তিশালী করতে পারি), আমরা পাই

যেখানে L হল গড় কোড দৈর্ঘ্য।

এইভাবে, এনট্রপি হল একটি গড় কোডওয়ার্ড দৈর্ঘ্য L সহ যেকোনো অক্ষর-দ্বারা-প্রতীক কোডের জন্য সর্বনিম্ন আবদ্ধ। এটি হস্তক্ষেপ-মুক্ত চ্যানেলের জন্য শ্যাননের উপপাদ্য।

এখন যোগাযোগ ব্যবস্থার সীমাবদ্ধতা সম্পর্কে মূল উপপাদ্যটি বিবেচনা করুন যেখানে তথ্য স্বতন্ত্র বিট এবং শব্দের একটি প্রবাহ হিসাবে প্রেরণ করা হয়। এটা বোঝা যায় যে এক বিটের সঠিক ট্রান্সমিশনের সম্ভাবনা হল P > 1/2, এবং ট্রান্সমিশনের সময় বিটের মান উল্টে যাওয়ার সম্ভাবনা (একটি ত্রুটি ঘটবে) Q = 1 - P এর সমান। সুবিধার জন্য, আমরা অনুমান করুন যে ত্রুটিগুলি স্বাধীন এবং প্রতিটি প্রেরিত বিটের জন্য একটি ত্রুটির সম্ভাবনা একই - অর্থাৎ, যোগাযোগ চ্যানেলে "সাদা গোলমাল" রয়েছে।

যেভাবে আমাদের একটি বার্তায় এন বিটের দীর্ঘ স্ট্রীম এনকোড করা আছে তা হল ওয়ান-বিট কোডের n-মাত্রিক এক্সটেনশন। আমরা পরে n এর মান নির্ধারণ করব। n-মাত্রিক স্থানের একটি বিন্দু হিসাবে n-বিট সমন্বিত একটি বার্তা বিবেচনা করুন। যেহেতু আমাদের একটি n-মাত্রিক স্থান রয়েছে - এবং সরলতার জন্য আমরা ধরে নেব যে প্রতিটি বার্তার একই সম্ভাবনা রয়েছে - সেখানে M সম্ভাব্য বার্তা রয়েছে (এমও পরে সংজ্ঞায়িত করা হবে), তাই প্রেরিত কোনও বার্তার সম্ভাবনা

(প্রেরক)
তফসিল 13.II

এরপরে, চ্যানেলের ক্ষমতার ধারণাটি বিবেচনা করুন। বিশদ বিবরণে না গিয়ে, চ্যানেলের ক্ষমতা সর্বাধিক কার্যকরী কোডিং ব্যবহারকে বিবেচনায় রেখে একটি যোগাযোগ চ্যানেলে নির্ভরযোগ্যভাবে প্রেরণ করা যেতে পারে এমন তথ্যের সর্বাধিক পরিমাণ হিসাবে সংজ্ঞায়িত করা হয়। একটি যোগাযোগ চ্যানেলের মাধ্যমে তার ক্ষমতার চেয়ে বেশি তথ্য প্রেরণ করা যেতে পারে এমন কোন যুক্তি নেই। এটি একটি বাইনারি সিমেট্রিক চ্যানেলের জন্য প্রমাণিত হতে পারে (যা আমরা আমাদের ক্ষেত্রে ব্যবহার করি)। চ্যানেল ক্ষমতা, বিট পাঠানোর সময়, হিসাবে নির্দিষ্ট করা হয়

যেখানে, পূর্বের মত, P হল কোন প্রেরিত বিটে কোন ত্রুটি না থাকার সম্ভাবনা। n স্বাধীন বিট পাঠানোর সময়, চ্যানেলের ক্ষমতা দেওয়া হয়

যদি আমরা চ্যানেলের ক্ষমতার কাছাকাছি থাকি, তাহলে আমাদের অবশ্যই ai, i = 1, ..., M চিহ্নগুলির জন্য প্রায় এই পরিমাণ তথ্য পাঠাতে হবে। প্রতিটি প্রতীক ai-এর উপস্থিতির সম্ভাবনা 1 / M, বিবেচনা করে। আমরা পেতে

যখন আমরা M-এর যেকোনো একটি সমান সম্ভাব্য বার্তা পাঠাই, তখন আমাদের কাছে থাকে

যখন n বিট পাঠানো হয়, আমরা আশা করি nQ ত্রুটি ঘটবে। অনুশীলনে, এন-বিট সমন্বিত একটি বার্তার জন্য, প্রাপ্ত বার্তায় আমাদের প্রায় nQ ত্রুটি থাকবে। বড় n এর জন্য, আপেক্ষিক প্রকরণ (প্রকরণ = বন্টন প্রস্থ, )
n বাড়ার সাথে সাথে ত্রুটির সংখ্যার বন্টন ক্রমশ সংকীর্ণ হয়ে যাবে।

সুতরাং, ট্রান্সমিটারের দিক থেকে, আমি বার্তাটি পাঠাতে এবং ব্যাসার্ধ সহ এর চারপাশে একটি গোলক আঁকতে নিয়েছি

যা প্রত্যাশিত সংখ্যক ত্রুটি Q, (চিত্র 2.II) থেকে e13 এর সমান পরিমাণে কিছুটা বড়। যদি n যথেষ্ট বড় হয়, তাহলে এই গোলকের বাইরে প্রসারিত রিসিভারের দিকে একটি বার্তা পয়েন্ট bj প্রদর্শিত হওয়ার ইচ্ছামত ছোট সম্ভাবনা রয়েছে। ট্রান্সমিটারের দৃষ্টিকোণ থেকে আমি পরিস্থিতিটি স্কেচ করে দেখি: আমাদের কাছে প্রেরিত বার্তা ai থেকে প্রাপ্ত বার্তা bj পর্যন্ত যেকোন রেডিআই আছে যার সম্ভাব্যতা স্বাভাবিক বিতরণের সমান (বা প্রায় সমান) ত্রুটির সম্ভাবনা রয়েছে, সর্বাধিক পৌঁছেছে nQ-তে। যেকোন প্রদত্ত e2-এর জন্য, একটি n এত বড় যে ফলাফল বিন্দু bj আমার গোলকের বাইরে থাকার সম্ভাবনা আপনার পছন্দ মতো ছোট।

এখন আপনার দিক থেকে একই পরিস্থিতি দেখুন (চিত্র 13.III)। রিসিভার সাইডে এন-ডাইমেনশনাল স্পেসে প্রাপ্ত বিন্দু bj এর চারপাশে একই ব্যাসার্ধের একটি গোলক S(r) রয়েছে, যেমন প্রাপ্ত বার্তা bj যদি আমার গোলকের ভিতরে থাকে, তাহলে আমার পাঠানো বার্তা ai আপনার ভিতরে রয়েছে গোলক

কিভাবে একটি ত্রুটি ঘটতে পারে? নীচের টেবিলে বর্ণিত ক্ষেত্রে ত্রুটি ঘটতে পারে:

চিত্র 13.III

এখানে আমরা দেখতে পাচ্ছি যে যদি প্রাপ্ত বিন্দুর চারপাশে নির্মিত গোলকটিতে একটি সম্ভাব্য প্রেরিত আনকোড করা বার্তার সাথে সম্পর্কিত কমপক্ষে আরও একটি বিন্দু থাকে, তবে সংক্রমণের সময় একটি ত্রুটি ঘটেছে, যেহেতু আপনি এই বার্তাগুলির মধ্যে কোনটি প্রেরণ করা হয়েছিল তা নির্ধারণ করতে পারবেন না। প্রেরিত বার্তাটি ত্রুটি-মুক্ত হয় শুধুমাত্র যদি এটির সাথে সংশ্লিষ্ট বিন্দুটি গোলকের মধ্যে থাকে এবং প্রদত্ত কোডে একই গোলকের মধ্যে অন্য কোন বিন্দু সম্ভব না থাকে।

বার্তা ai পাঠানো হলে ত্রুটি Pe এর সম্ভাব্যতার জন্য আমাদের একটি গাণিতিক সমীকরণ আছে

আমরা দ্বিতীয় মেয়াদে প্রথম গুণনীয়কটিকে 1 হিসাবে গ্রহণ করতে পারি। এইভাবে আমরা অসমতা পাই

এটা যে সুস্পষ্ট

তাই

ডানদিকে শেষ মেয়াদে পুনরায় আবেদন করুন

n যথেষ্ট বড় নিলে, প্রথম পদটি যতটা ইচ্ছা ছোট নেওয়া যেতে পারে, বলুন কিছু সংখ্যার চেয়ে কম। তাই আমরা আছে

এখন দেখা যাক কিভাবে আমরা n বিট সমন্বিত M বার্তাগুলিকে এনকোড করার জন্য একটি সাধারণ প্রতিস্থাপন কোড তৈরি করতে পারি। ঠিক কীভাবে একটি কোড তৈরি করতে হয় (ত্রুটি-সংশোধনকারী কোডগুলি এখনও উদ্ভাবিত হয়নি) সম্পর্কে ধারণা না থাকায়, শ্যানন এলোমেলো কোডিং বেছে নিয়েছিলেন। বার্তার প্রতিটি n বিটের জন্য একটি মুদ্রা উল্টান এবং M বার্তাগুলির জন্য প্রক্রিয়াটি পুনরাবৃত্তি করুন। মোট, nM মুদ্রা উল্টানো প্রয়োজন, তাই এটি সম্ভব

কোড অভিধানে একই সম্ভাবনা ½nM। অবশ্যই, একটি কোডবুক তৈরির এলোমেলো প্রক্রিয়াটির অর্থ হল যে ডুপ্লিকেট হওয়ার সম্ভাবনা রয়েছে, সেইসাথে কোড পয়েন্টগুলি যা একে অপরের কাছাকাছি হবে এবং সেইজন্য সম্ভাব্য ত্রুটির উৎস হবে। একজনকে অবশ্যই প্রমাণ করতে হবে যে যদি এটি কোনও ছোট নির্বাচিত ত্রুটি স্তরের চেয়ে বেশি সম্ভাবনার সাথে না ঘটে তবে প্রদত্ত n যথেষ্ট বড়।
গুরুত্বপূর্ণ পয়েন্ট হল যে শ্যানন গড় ত্রুটি খুঁজে বের করার জন্য সম্ভাব্য সমস্ত কোডবুক গড়লেন! সমস্ত সম্ভাব্য এলোমেলো কোডবুকের সেটের গড় মান বোঝাতে আমরা Av[.] চিহ্নটি ব্যবহার করব। একটি ধ্রুবক d এর উপর গড়, অবশ্যই, একটি ধ্রুবক দেয়, যেহেতু প্রতিটি পদের গড় যোগফলের অন্যান্য পদের মতোই,

যা বাড়ানো যেতে পারে (M-1 M-তে যায়)

যেকোন প্রদত্ত বার্তার জন্য, যখন সমস্ত কোডবুক জুড়ে গড় করে, এনকোডিং সমস্ত সম্ভাব্য মানের মাধ্যমে চলে, তাই একটি গোলকের মধ্যে একটি বিন্দু থাকার গড় সম্ভাব্যতা হল স্থানের মোট আয়তনের সাথে গোলকের আয়তনের অনুপাত। গোলকের আয়তন হল

যেখানে s=Q+e2 <1/2 এবং ns অবশ্যই একটি পূর্ণসংখ্যা হতে হবে।

ডানদিকের শেষ পদটি এই যোগফলের মধ্যে সবচেয়ে বড়। প্রথমে, ফ্যাক্টরিয়ালের জন্য স্টার্লিং সূত্র ব্যবহার করে এর মান অনুমান করা যাক। তারপরে আমরা এটির সামনে পদটির ক্রমহ্রাসমান ফ্যাক্টরটি দেখব, মনে রাখবেন যে আমরা বাম দিকে যাওয়ার সাথে সাথে এই ফ্যাক্টরটি বৃদ্ধি পায়, এবং তাই আমরা করতে পারি: (1) যোগফলের মানকে জ্যামিতিক অগ্রগতির যোগফলের সাথে সীমাবদ্ধ করতে পারি এই প্রাথমিক সহগ, (2) জ্যামিতিক অগ্রগতি ns পদ থেকে অসীম সংখ্যক পদে প্রসারিত করুন, (3) একটি অসীম জ্যামিতিক অগ্রগতির যোগফল গণনা করুন (মান বীজগণিত, উল্লেখযোগ্য কিছু নয়) এবং অবশেষে সীমিত মান পান (পর্যাপ্ত পরিমাণে বড় জন্য n):

দ্বিপদী পরিচয়ে এনট্রপি H(গুলি) কীভাবে উপস্থিত হয়েছে তা লক্ষ্য করুন। মনে রাখবেন যে টেলর সিরিজের সম্প্রসারণ H(s)=H(Q+e2) শুধুমাত্র প্রথম ডেরিভেটিভকে বিবেচনায় নিয়ে এবং অন্য সকলকে উপেক্ষা করে প্রাপ্ত একটি অনুমান দেয়। এখন চূড়ান্ত অভিব্যক্তি একসাথে করা যাক:

যেখানে

আমাদের যা করতে হবে তা হল e2 বেছে নিন যেমন e3 < e1, এবং তারপর শেষ পদটি ইচ্ছামত ছোট হবে, যতক্ষণ না n যথেষ্ট বড় হয়। ফলস্বরূপ, গড় PE ত্রুটি ইচ্ছামত ছোট হিসাবে পাওয়া যেতে পারে চ্যানেলের ক্ষমতা নির্বিচারে C এর কাছাকাছি।
যদি সমস্ত কোডের গড় একটি ছোট যথেষ্ট ত্রুটি থাকে, তাহলে অন্তত একটি কোড উপযুক্ত হতে হবে, তাই অন্তত একটি উপযুক্ত কোডিং সিস্টেম আছে। এটি শ্যানন দ্বারা প্রাপ্ত একটি গুরুত্বপূর্ণ ফলাফল - "শ্যাননের উপপাদ্য একটি গোলমাল চ্যানেল", যদিও এটি উল্লেখ করা উচিত যে আমি যে সাধারণ বাইনারি সিমেট্রিক চ্যানেল ব্যবহার করেছি তার চেয়ে অনেক বেশি সাধারণ ক্ষেত্রে তিনি এটি প্রমাণ করেছেন। সাধারণ ক্ষেত্রে, গাণিতিক গণনাগুলি আরও জটিল, তবে ধারণাগুলি এত আলাদা নয়, তাই প্রায়শই, একটি নির্দিষ্ট ক্ষেত্রে উদাহরণ ব্যবহার করে, আপনি উপপাদ্যটির প্রকৃত অর্থ প্রকাশ করতে পারেন।

আসুন ফলাফলের সমালোচনা করি। আমরা বারবার বলেছি: "যথেষ্ট বড় n এর জন্য।" কিন্তু এন কত বড়? খুব, খুব বড় যদি আপনি সত্যিই চ্যানেলের ক্ষমতার কাছাকাছি হতে চান এবং সঠিক ডেটা স্থানান্তর সম্পর্কে নিশ্চিত হন! এত বড়, আসলে, আপনাকে পর্যাপ্ত বিটগুলির একটি বার্তা সংগ্রহ করার জন্য এটিকে পরে এনকোড করার জন্য খুব দীর্ঘ সময় অপেক্ষা করতে হবে। এই ক্ষেত্রে, র্যান্ডম কোড অভিধানের আকার কেবল বিশাল হবে (সর্বশেষে, এই জাতীয় অভিধানটি সমস্ত Mn বিটের সম্পূর্ণ তালিকার চেয়ে সংক্ষিপ্ত আকারে উপস্থাপন করা যায় না, যদিও n এবং M খুব বড় হওয়া সত্ত্বেও)!

ত্রুটি-সংশোধনকারী কোডগুলি একটি দীর্ঘ বার্তার জন্য অপেক্ষা করা এড়ায় এবং তারপরে এটিকে এনকোডিং এবং ডিকোডিং খুব বড় কোডবুকের মাধ্যমে এড়িয়ে যায় কারণ তারা নিজেরাই কোডবুকগুলি এড়িয়ে চলে এবং পরিবর্তে সাধারণ গণনা ব্যবহার করে। সাধারণ তত্ত্বে, এই জাতীয় কোডগুলি চ্যানেলের ক্ষমতার কাছে যাওয়ার ক্ষমতা হারাতে থাকে এবং এখনও একটি কম ত্রুটির হার বজায় রাখে, কিন্তু যখন কোডটি প্রচুর পরিমাণে ত্রুটি সংশোধন করে, তখন তারা ভাল কার্য সম্পাদন করে। অন্য কথায়, আপনি যদি ত্রুটি সংশোধনের জন্য কিছু চ্যানেলের ক্ষমতা বরাদ্দ করেন, তাহলে আপনাকে অবশ্যই বেশিরভাগ সময় ত্রুটি সংশোধন ক্ষমতা ব্যবহার করতে হবে, অর্থাৎ, প্রেরিত প্রতিটি বার্তায় প্রচুর পরিমাণে ত্রুটি সংশোধন করতে হবে, অন্যথায় আপনি এই ক্ষমতাটি নষ্ট করবেন।

একই সাথে, উপরে প্রমাণিত উপপাদ্যটি এখনও অর্থহীন নয়! এটি দেখায় যে দক্ষ ট্রান্সমিশন সিস্টেমগুলিকে খুব দীর্ঘ বিট স্ট্রিংগুলির জন্য চতুর এনকোডিং স্কিম ব্যবহার করতে হবে। একটি উদাহরণ হল উপগ্রহ যা বাইরের গ্রহের বাইরে উড়ে গেছে; পৃথিবী এবং সূর্য থেকে দূরে সরে যাওয়ার সাথে সাথে, তারা ডেটা ব্লকে আরও বেশি ত্রুটি সংশোধন করতে বাধ্য হয়: কিছু উপগ্রহ সৌর প্যানেল ব্যবহার করে, যা প্রায় 5 ওয়াট সরবরাহ করে, অন্যরা পারমাণবিক শক্তির উত্স ব্যবহার করে, যা প্রায় একই শক্তি সরবরাহ করে। পাওয়ার সাপ্লাইয়ের কম শক্তি, ট্রান্সমিটার ডিশের ছোট আকার এবং পৃথিবীতে রিসিভার ডিশের সীমিত আকার, সিগন্যালকে ভ্রমণ করতে হবে এমন বিশাল দূরত্ব - এই সমস্ত কিছুর জন্য একটি উচ্চ স্তরের ত্রুটি সংশোধন সহ কোড ব্যবহার করা প্রয়োজন। কার্যকর যোগাযোগ ব্যবস্থা।

আসুন আমরা উপরের প্রমাণে ব্যবহৃত n-মাত্রিক স্থানটিতে ফিরে আসি। এটি নিয়ে আলোচনা করতে গিয়ে, আমরা দেখিয়েছি যে গোলকের প্রায় পুরো আয়তনটি বাইরের পৃষ্ঠের কাছাকাছি কেন্দ্রীভূত - এইভাবে, এটি প্রায় নিশ্চিত যে প্রেরিত সংকেতটি প্রাপ্ত সংকেতের চারপাশে নির্মিত গোলকের পৃষ্ঠের কাছে অবস্থিত হবে, এমনকি তুলনামূলকভাবে এই ধরনের একটি গোলকের ছোট ব্যাসার্ধ। অতএব, এটি আশ্চর্যের কিছু নয় যে প্রাপ্ত সংকেত, একটি নির্বিচারে বড় সংখ্যক ত্রুটি সংশোধন করার পরে, nQ, ত্রুটি ছাড়াই নির্বিচারে একটি সংকেতের কাছাকাছি হতে দেখা যায়। আমরা আগে আলোচনা করা লিঙ্ক ক্ষমতা এই ঘটনা বোঝার চাবিকাঠি. লক্ষ্য করুন যে হ্যামিং কোড ত্রুটি-সংশোধনের জন্য নির্মিত অনুরূপ গোলকগুলি একে অপরকে ওভারল্যাপ করে না। এন-ডাইমেনশনাল স্পেসে প্রায় অরথোগোনাল ডাইমেনশনের বিশাল সংখ্যা দেখায় কেন আমরা সামান্য ওভারল্যাপ সহ মহাকাশে M গোলকগুলিকে ফিট করতে পারি। যদি আমরা একটি ছোট, নির্বিচারে ছোট ওভারল্যাপের অনুমতি দিই, যা ডিকোডিংয়ের সময় শুধুমাত্র অল্প সংখ্যক ত্রুটির কারণ হতে পারে, তাহলে আমরা মহাকাশে গোলকের একটি ঘন বসানো পেতে পারি। হ্যামিং একটি নির্দিষ্ট স্তরের ত্রুটি সংশোধনের নিশ্চয়তা দিয়েছে, শ্যানন - ত্রুটির একটি কম সম্ভাবনা, কিন্তু একই সময়ে প্রকৃত থ্রুপুটটি নির্বিচারে যোগাযোগ চ্যানেলের ক্ষমতার কাছাকাছি বজায় রাখা, যা হ্যামিং কোডগুলি করতে পারে না।

তথ্য তত্ত্ব আমাদের বলে না কিভাবে একটি দক্ষ সিস্টেম ডিজাইন করতে হয়, তবে এটি দক্ষ যোগাযোগ ব্যবস্থার দিকে নির্দেশ করে। এটি মেশিন-টু-মেশিন যোগাযোগ ব্যবস্থা তৈরির জন্য একটি মূল্যবান হাতিয়ার, কিন্তু, যেমনটি আগে উল্লেখ করা হয়েছে, মানুষ কীভাবে একে অপরের সাথে যোগাযোগ করে তার সাথে এর সামান্য প্রাসঙ্গিকতা রয়েছে। প্রযুক্তিগত যোগাযোগ ব্যবস্থার মতো জৈবিক উত্তরাধিকার কতটা অজানা, তাই তথ্য তত্ত্ব কীভাবে জিনের ক্ষেত্রে প্রযোজ্য তা বর্তমানে পরিষ্কার নয়। আমাদের চেষ্টা করা ছাড়া কোন বিকল্প নেই, এবং যদি সাফল্য আমাদের এই ঘটনার যন্ত্রের মতো প্রকৃতি দেখায়, তবে ব্যর্থতা তথ্যের প্রকৃতির অন্যান্য উল্লেখযোগ্য দিক নির্দেশ করবে।

আসুন খুব বেশি বিভ্রান্তি না করি। আমরা দেখেছি যে সমস্ত মূল সংজ্ঞা, বৃহত্তর বা কম পরিমাণে, আমাদের মূল বিশ্বাসের সারমর্ম প্রকাশ করতে হবে, কিন্তু সেগুলি কিছু মাত্রার বিকৃতি দ্বারা চিহ্নিত এবং তাই প্রযোজ্য নয়। এটা ঐতিহ্যগতভাবে গৃহীত হয় যে, পরিশেষে, আমরা যে সংজ্ঞা ব্যবহার করি তা আসলে সারাংশকে সংজ্ঞায়িত করে; কিন্তু, এটি কেবল আমাদের বলে যে কীভাবে জিনিসগুলি প্রক্রিয়া করতে হয় এবং কোনওভাবেই আমাদের কাছে কোনও অর্থ প্রকাশ করে না। পোস্টুলেশনাল পদ্ধতি, গাণিতিক চেনাশোনাগুলিতে এত দৃঢ়ভাবে সমর্থন করা হয়, অনুশীলনে কাঙ্ক্ষিত হতে অনেক কিছু ছেড়ে যায়।

এখন আমরা আইকিউ পরীক্ষার একটি উদাহরণ দেখব যেখানে সংজ্ঞাটি আপনার পছন্দ মতো বৃত্তাকার এবং ফলস্বরূপ, বিভ্রান্তিকর। একটি পরীক্ষা তৈরি করা হয় যা বুদ্ধিমত্তা পরিমাপ করার কথা। তারপরে এটিকে যতটা সম্ভব সামঞ্জস্যপূর্ণ করার জন্য এটিকে সংশোধিত করা হয়, এবং তারপরে এটি প্রকাশ করা হয় এবং, একটি সহজ পদ্ধতিতে, ক্রমাঙ্কিত করা হয় যাতে পরিমাপ করা "বুদ্ধিমত্তা" সাধারণত বিতরণ করা হয় (অবশ্যই একটি ক্রমাঙ্কন বক্ররেখায়)। সমস্ত সংজ্ঞা পুনঃচেক করা আবশ্যক, শুধুমাত্র যখন সেগুলি প্রথম প্রস্তাবিত হয় তখনই নয়, অনেক পরেও, যখন সেগুলি টানা সিদ্ধান্তে ব্যবহার করা হয়৷ সমস্যা সমাধানের জন্য সংজ্ঞাগত সীমানা কতটা উপযুক্ত? একটি সেটিংয়ে প্রদত্ত সংজ্ঞাগুলি কত ঘন ঘন ভিন্ন ভিন্ন সেটিংসে প্রয়োগ করা হয়? এটা প্রায়ই ঘটে! মানবিক বিভাগে, যা আপনি অনিবার্যভাবে আপনার জীবনে সম্মুখীন হবেন, এটি প্রায়শই ঘটে।

সুতরাং, তথ্য তত্ত্বের এই উপস্থাপনার উদ্দেশ্যগুলির মধ্যে একটি, এর উপযোগিতা প্রদর্শনের পাশাপাশি, আপনাকে এই বিপদ সম্পর্কে সতর্ক করা বা কাঙ্ক্ষিত ফলাফল পাওয়ার জন্য এটিকে কীভাবে ব্যবহার করতে হয় তা দেখানো ছিল। এটি দীর্ঘদিন ধরে লক্ষ করা হয়েছে যে প্রাথমিক সংজ্ঞাগুলি নির্ধারণ করে যে আপনি শেষ পর্যন্ত কী খুঁজে পান, এটি মনে হয় তার চেয়ে অনেক বেশি পরিমাণে। প্রারম্ভিক সংজ্ঞাগুলির জন্য আপনার কাছ থেকে অনেক মনোযোগের প্রয়োজন, শুধুমাত্র যেকোন নতুন পরিস্থিতিতেই নয়, সেই সাথে যে সমস্ত ক্ষেত্রে আপনি দীর্ঘদিন ধরে কাজ করছেন। এটি আপনাকে বুঝতে সাহায্য করবে যে প্রাপ্ত ফলাফলগুলি একটি টাউটোলজি এবং দরকারী কিছু নয়।

এডিংটনের বিখ্যাত গল্পটি এমন লোকদের বলে যারা জাল দিয়ে সমুদ্রে মাছ ধরত। তারা মাছের আকার অধ্যয়ন করার পরে, তারা সমুদ্রে পাওয়া মাছের সর্বনিম্ন আকার নির্ধারণ করে! তাদের উপসংহার বাস্তবে নয়, ব্যবহৃত যন্ত্র দ্বারা চালিত হয়েছিল।

চলবে…

যারা বইটির অনুবাদ, বিন্যাস এবং প্রকাশনার জন্য সাহায্য করতে চান - একটি ব্যক্তিগত বার্তা বা ইমেলে লিখুন [ইমেল সুরক্ষিত]

যাইহোক, আমরা আরেকটি দুর্দান্ত বইয়ের অনুবাদও চালু করেছি - "দ্য ড্রিম মেশিন: কম্পিউটার বিপ্লবের গল্প")

আমরা বিশেষ করে খুঁজছি যারা অনুবাদ করতে সাহায্য করবে বোনাস অধ্যায়, যা শুধুমাত্র ভিডিওতে. (10 মিনিটের জন্য স্থানান্তর, প্রথম 20 ইতিমধ্যে নেওয়া হয়েছে)

বইয়ের বিষয়বস্তু এবং অনূদিত অধ্যায়ভূমিকা

1. দ্য আর্ট অফ ডুয়িং সায়েন্স অ্যান্ড ইঞ্জিনিয়ারিংয়ের ভূমিকা: শিখতে শেখা (মার্চ ২৮, ১৯৯৫) অনুবাদঃ ১ম অধ্যায়
2. "ডিজিটাল (বিচ্ছিন্ন) বিপ্লবের ভিত্তি" (মার্চ 30, 1995) অধ্যায় 2। ডিজিটাল (বিচ্ছিন্ন) বিপ্লবের মৌলিক বিষয়
3. "কম্পিউটারের ইতিহাস - হার্ডওয়্যার" (মার্চ 31, 1995) অধ্যায় 3. কম্পিউটারের ইতিহাস - হার্ডওয়্যার
4. "কম্পিউটারের ইতিহাস - সফ্টওয়্যার" (এপ্রিল 4, 1995) অধ্যায় 4. কম্পিউটারের ইতিহাস - সফ্টওয়্যার
5. "কম্পিউটারের ইতিহাস - অ্যাপ্লিকেশন" (এপ্রিল 6, 1995) অধ্যায় 5: কম্পিউটারের ইতিহাস - ব্যবহারিক প্রয়োগ
6. "কৃত্রিম বুদ্ধিমত্তা - প্রথম অংশ" (এপ্রিল 7, 1995) অধ্যায় 6. কৃত্রিম বুদ্ধিমত্তা - 1
7. "কৃত্রিম বুদ্ধিমত্তা - পার্ট II" (এপ্রিল 11, 1995) অধ্যায় 7. কৃত্রিম বুদ্ধিমত্তা - II
8. "কৃত্রিম বুদ্ধিমত্তা III" (এপ্রিল 13, 1995) অধ্যায় 8. কৃত্রিম বুদ্ধিমত্তা-III
9. "এন-ডাইমেনশনাল স্পেস" (এপ্রিল 14, 1995) অধ্যায় 9. N-মাত্রিক স্থান
10. "কোডিং তত্ত্ব - তথ্যের প্রতিনিধিত্ব, প্রথম অংশ" (এপ্রিল 18, 1995) অধ্যায় 10. কোডিং তত্ত্ব - I
11. "কোডিং থিওরি - তথ্যের প্রতিনিধিত্ব, পার্ট II" (এপ্রিল 20, 1995) অধ্যায় 11. কোডিং তত্ত্ব - II
12. "ত্রুটি-সংশোধন কোড" (এপ্রিল 21, 1995) অধ্যায় 12. ত্রুটি সংশোধন কোড
13. "তথ্য তত্ত্ব" (25 এপ্রিল, 1995) অধ্যায় 13. তথ্য তত্ত্ব
14. "ডিজিটাল ফিল্টার, পার্ট I" (এপ্রিল 27, 1995) অধ্যায় 14. ডিজিটাল ফিল্টার - 1
15. "ডিজিটাল ফিল্টার, পার্ট II" (28 এপ্রিল, 1995) অধ্যায় 15. ডিজিটাল ফিল্টার - 2
16. "ডিজিটাল ফিল্টার, পার্ট III" (মে 2, 1995) অধ্যায় 16. ডিজিটাল ফিল্টার - 3
17. "ডিজিটাল ফিল্টার, পার্ট IV" (মে 4, 1995) অধ্যায় 17. ডিজিটাল ফিল্টার - IV
18. "সিমুলেশন, পার্ট I" (মে 5, 1995) অধ্যায় 18. মডেলিং - I
19. "সিমুলেশন, পার্ট II" (মে 9, 1995) অধ্যায় 19. মডেলিং - II
20. "সিমুলেশন, পার্ট III" (মে 11, 1995) অধ্যায় 20. মডেলিং - III
21. "ফাইবার অপটিক্স" (মে 12, 1995) অধ্যায় 21. ফাইবার অপটিক্স
22. "কম্পিউটার সহায়ক নির্দেশনা" (মে 16, 1995) অধ্যায় 22: কম্পিউটার সহায়ক নির্দেশনা (CAI)
23. "গণিত" (মে 18, 1995) অধ্যায় 23। গণিত
24. "কোয়ান্টাম মেকানিক্স" (মে 19, 1995) অধ্যায় 24। কোয়ান্টাম মেকানিক্স
25. "সৃজনশীলতা" (মে 23, 1995)। অনুবাদ: অধ্যায় 25. সৃজনশীলতা
26. "বিশেষজ্ঞ" (মে 25, 1995) অধ্যায় 26। বিশেষজ্ঞ
27. "অনির্ভরযোগ্য ডেটা" (মে 26, 1995) অধ্যায় 27. অবিশ্বস্ত তথ্য
28. "সিস্টেম ইঞ্জিনিয়ারিং" (মে 30, 1995) অধ্যায় 28. সিস্টেম ইঞ্জিনিয়ারিং
29. "আপনি যা পরিমাপ করেন তা পান" (জুন 1, 1995) অধ্যায় 29: আপনি যা পরিমাপ করেন তা পাবেন
30. "আমরা যা জানি তা আমরা কীভাবে জানি" (জুন 2, 1995) 10 মিনিটের অংশে অনুবাদ করুন
31. হ্যামিং, "আপনি এবং আপনার গবেষণা" (জুন 6, 1995)। অনুবাদ: তুমি এবং তোমার কাজ

যারা বইটির অনুবাদ, বিন্যাস এবং প্রকাশনার জন্য সাহায্য করতে চান - একটি ব্যক্তিগত বার্তা বা ইমেলে লিখুন [ইমেল সুরক্ষিত]

উত্স: www.habr.com