ज़रूरी Coding Theory [pdf]

• यह पुस्तक coding theory की मुख्य अवधारणाओं और आधुनिक विकास को व्यापक रूप से व्यवस्थित करती है
• error-correcting codes के बुनियादी सिद्धांत, विभिन्न codes की संरचना और सीमाएँ, तथा उनके वास्तविक अनुप्रयोगों को कवर करती है
• Shannon theory और Hamming code सहित Reed-Solomon जैसे वास्तविक दुनिया में व्यापक रूप से इस्तेमाल होने वाले codes का विस्तार से वर्णन करती है
• hashing, group testing, biometric data protection जैसे आधुनिक IT systems में अनुप्रयोगों के उदाहरण भी व्यवस्थित रूप से प्रस्तुत करती है
• परिशिष्ट, अभ्यास प्रश्न और संदर्भ सामग्री सहित यह सीखने वालों और प्रैक्टिशनर्स दोनों के लिए एक प्रभावी संदर्भ पुस्तक के रूप में तैयार की गई है

---

प्रस्तावना

• यह पुस्तक Venkatesan Guruswami, Atri Rudra, Madhu Sudan के coding theory lecture notes पर आधारित है
• University of Washington, CMU, University at Buffalo SUNY, Harvard, MIT आदि में दिए गए lectures की सामग्री पर आधारित है
• NSF CAREER grant CCF-0844796 का समर्थन प्राप्त है
• लेखकों के विचार और निष्कर्ष NSF की आधिकारिक स्थिति का प्रतिनिधित्व नहीं करते
• यह Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License के अंतर्गत उपलब्ध है

विषय सूची सारांश

अध्याय 1: मूलभूत प्रश्न

• coding theory का उद्देश्य, बुनियादी परिभाषाएँ और codes
• error correction और code distance की अवधारणा, Hamming code और bounds
• code families का वर्गीकरण, अभ्यास प्रश्न और संदर्भ सहित

भाग I: बुनियाद

• linear codes, finite fields, vector spaces जैसी गणितीय संरचनाओं का परिचय
• Hamming code की efficient decoding और dual codes का विवरण
• अभ्यास प्रश्न और संदर्भ सामग्री शामिल

अध्याय 3: probability और q-ary entropy function

• probability theory की बुनियाद, probabilistic method, q-ary entropy function की समझ
• संबंधित अभ्यास प्रश्न और संदर्भ सामग्री उपलब्ध

भाग II: combinatorics

• Hamming, Gilbert-Varshamov, Singleton, Plotkin आदि code bounds और सीमाओं का वर्णन
• Reed-Solomon code, polynomials और finite fields के अनुप्रयोग
• Shannon का noise model और information transmission की सीमाएँ, Hamming के साथ तुलना
• list decoding, Johnson Bound, list decoding capacity आदि का विस्तार
• Elias-Bassalygo, linear programming bounds जैसी नई limit theories

भाग III: विभिन्न code structures

• polynomial-based codes और binary fields का उपयोग, सामान्य code संरचनाएँ
• code concatenation, Zyablov Bound, उन्नत concatenation techniques और सारांश
• Expander graphs और Expander codes, distance amplification और अनुप्रयोग उदाहरण

भाग IV: algorithms

• Reed-Solomon, Reed-Muller, concatenated codes की efficient decoding methods
• BSCp channel capacity प्राप्त करने के तरीके और inner/outer code संरचना
• Polar codes, polarization सिद्धांत तथा encoder/decoder implementation, list decoding क्षमता
• linear-time encoding और local recovery वाले codes का विवरण

भाग V: applications

• hashing का सिद्धांत और collision prevention, almost universal hash functions, proof of data possession
• biometric authentication (fingerprint) protection के लिए Fuzzy Vault की अवधारणा
• group testing का formulation, bounds और data stream algorithms में अनुप्रयोग
• coding problems की complexity: nearest codeword problem, preprocessing-based decoding, approximation, minimum distance problem आदि
• computational complexity से जुड़े विषय जैसे communication complexity, randomness, pseudorandomness, hardcore predicates, average-case hardness problems आदि भी शामिल

परिशिष्ट

• प्रतीक तालिका, उपयोगी inequalities और equalities, asymptotic notation, algorithms और complexity की बुनियादी पृष्ठभूमि
• algebraic algorithms, finite fields, polynomial operations का परिचय
• information theory की प्रमुख अवधारणाएँ: entropy, conditional entropy, mutual information आदि का सारांश

विशेषताएँ और उपयोगिता

• आधुनिक information and communication, data storage, cryptographic systems आदि में आवश्यक error-correcting algorithms की सैद्धांतिक पृष्ठभूमि और व्यावहारिक उपयोग को व्यापक रूप से प्रस्तुत करती है
• बुनियादी अवधारणाओं से लेकर नवीनतम रुझानों और वास्तविक अनुप्रयोगों तक, यह नए developers, researchers और IT practitioners को व्यापक ज्ञान देती है
• प्रत्येक अध्याय में अभ्यास प्रश्न और संदर्भ शामिल हैं, जिससे अध्ययन और self-learning में सुविधा होती है
• Creative Commons license के तहत इसे शैक्षणिक/गैर-व्यावसायिक उद्देश्यों के लिए स्वतंत्र रूप से उपयोग किया जा सकता है

[GN⁺]

Hacker News राय

• मैं यह ज़ोर देकर कहना चाहूँगा कि Claude Shannon की "The Mathematical Theory of Communication" सूचना सिद्धांत का एक बुनियादी दस्तावेज़ है, और इसे इतनी आसानी से समझाया गया है कि गहरी गणितीय पृष्ठभूमि न होने पर भी कोई भी इसे पढ़ सकता है लिंक

  • मैं यह भी कहना चाहूँगा कि Shannon गणितीय सोच शुरू करने के लिए सचमुच एक बेहतरीन व्यक्ति हैं। उन्होंने information entropy की अवधारणा शुरू में किसी विशेष अर्थ के बिना, सिर्फ़ आवश्यक गुणों के आधार पर निकाली थी। हैरानी की बात यह है कि इस तरह संयोग से बनी यह परिभाषा physics की thermodynamic entropy से लगभग मेल खाती है, और इसका नाम Von Neumann ने सुझाया था। गणित अक्सर "अगर इसे ये नियम पूरे करने हैं" जैसी तार्किक प्रगति से आगे बढ़ता है, और यही कारणों में से एक है कि बहुत से लोगों को यह कठिन लगता है। Shannon का paper केवल coding theory की रूपरेखा बनाता है; वास्तविक implementation उसमें नहीं है। मैंने अपने पुराने startup में इस paper के book version को साथ पढ़ने के लिए एक book club चलाया था, और मैं इसे information theory तथा गणित को व्यापक रूप से समझने के लिए सचमुच एक बहुत अच्छा अनुभव मानकर recommend करना चाहूँगा

• lossless compression का क्षेत्र generative AI से काफ़ी निकटता से जुड़ा है, इसलिए अगर इसमें और सामग्री जोड़ी जाए तो यह दिलचस्प होगा। lossless compression और machine learning के संबंध का अच्छा परिचय देने वाली एक PhD thesis recommend करना चाहूँगा लिंक

  • इसे सिर्फ़ lossless compression तक सीमित रखने की भी ज़रूरत नहीं है। दरअसल लगभग सारा machine learning एक तरह की compression के रूप में समझा जा सकता है, ज़्यादातर lossy compression के रूप में। उदाहरण के लिए, अगर केवल semantic embedding को channel के माध्यम से भेजा जाए, तो मूल पूरा पाठ न होने पर भी embedding values में इतना information होता है कि काम किया जा सके। data classification भी आख़िरकार data को सामान्य categories के latent representation तक सीमित करके बाकी को फेंक देने की प्रक्रिया है। generative AI के मामले में, यह इसलिए अच्छा काम करता है क्योंकि हम 'lossy compression' कर रहे होते हैं। हम जानबूझकर कुछ information फेंकते हैं, और उन्हीं खाली जगहों पर inference करना पड़ता है, जिससे generalization का रास्ता खुलता है। lossless LLM वास्तव में व्यावहारिक उपयोग में कोई ख़ास रोचक चीज़ नहीं है। लेकिन recommend किया गया paper इस मायने में बहुत विशेष है कि machine learning में दुर्लभ रूप से lossless compression को संबोधित करता है

• हाल में बना एक अच्छा संसाधन <i>Information Theory: From Coding to Learning</i> नाम की एक पाठ्यपुस्तक है। इसका online PDF version भी उपलब्ध है, इसलिए उसे देखना उपयोगी हो सकता है लिंक

  • मैं David MacKay की <i>Information Theory, Inference, and Learning Algorithms</i> भी recommend करना चाहूँगा लिंक

• "coding" से क्या मतलब है, इस सवाल का जवाब यह है कि यहाँ coding का अर्थ information को एक representation से दूसरे representation में बदलने वाली encoding/decoding प्रक्रिया से है। ऐसे systems को code कहा जाता है, और इन्हें information transfer के दौरान interference, tampering, या eavesdropping का सामना करने लायक बनाया जाता है। यानी code(coding) का उपयोग data compression, encryption, error detection and correction, data transmission, और storage जैसी अनेक जगहों पर होता है लिंक

  • ख़ास तौर पर, जिस किताब का ज़िक्र किया गया है वह error correcting code पर केंद्रित है। message भेजते समय खोए हुए हिस्सों को recover किया जा सके, इसके लिए अतिरिक्त data जोड़ा जाता है। हल करने वाली कठिन समस्या यह है कि न्यूनतम overhead और उचित computation time के भीतर इतना अतिरिक्त data कैसे डिज़ाइन किया जाए कि पर्याप्त errors को recover किया जा सके। यह तकनीक वास्तव में WiFi, hard drives, QR codes, RAM जैसी बेहद विविध जगहों पर इस्तेमाल होती है। उदाहरण के लिए, ECC RAM में ECC का मतलब ही error correcting code है। हाल में DDR5 में यह तकनीक आंशिक रूप से अनिवार्य की गई है

• चूँकि यहाँ मुफ़्त CS ebooks साझा करने का माहौल है, मैं Jeff E. की Algorithms किताब भी ज़ोरदार तरीके से recommend करना चाहूँगा। algorithms सीखने या अपनी क्षमता ताज़ा करने वालों के लिए यह अनिवार्य पाठ है लिंक

• मैंने इस किताब के कुछ अध्याय पढ़े हैं और मैं इससे बहुत संतुष्ट हूँ। आने वाले कुछ हफ़्तों या शायद कुछ महीनों में इसे धीरे-धीरे पढ़ने की योजना है

• अगर आप information theory और coding theory को और गहराई से पढ़ना चाहते हैं, तो मैं ये संसाधन भी recommend करूँगा। error correcting codes के लिए "W. Wesley Peterson और E. J. Weldon, Jr. की Error-Correcting Codes", और abstract algebra, ख़ासकर field theory, के लिए "Oscar Zariski और Pierre Samuel की Commutative Algebra" उपयोगी संदर्भ हैं

  • LaTeX commands यहाँ काम नहीं करते

• शुरुआती लोगों के लिए recommend की जाने वाली कुछ किताबें,

  1. John R. Pierce की <i>An Introduction to Information Theory, Symbols, Signals and Noise</i> - अवधारणाएँ समझने और intuition बनाने के लिए एक बेहतरीन classic। इसी लेखक की दूसरी किताबें भी शानदार हैं
  2. James V. Stone की <i>Information Theory: A Tutorial Introduction</i> - आसान और अच्छी शुरुआती किताब। लेखक के दूसरे tutorials भी उपयोगी हैं
  3. Stefan Moser और Po-ning chen की <i>A Student's Guide to Coding and Information Theory</i> - संक्षिप्त और स्पष्ट मार्गदर्शिका, और इसी series की दूसरी किताबें भी recommend करने लायक हैं

• जब भी कोई कहता है कि "यह अनिवार्य है", तब मेरे लिए, जिसने अपने department में उस विषय को बस थोड़ा-सा ही छुआ है, वह हमेशा थोड़ा डराने वाला पल होता है

  • इस course में 'अनिवार्य' का मतलब यह नहीं है कि हर computer science छात्र को यह ज़रूर आना चाहिए, बल्कि यह कि इसमें coding theory का सार समाहित है। इस किताब के सह-लेखक हमारे स्कूल में स्वयं यह पढ़ाते हैं, और यह course गणितीय सामग्री से भरा हुआ एक upper-level elective है। चार-वर्षीय computer science program में इसे आम तौर पर अंतिम वर्ष के बहुत कम छात्र लेते हैं, और मेरे आसपास जिन्होंने इसे लिया, वे सभी गणितीय proofs पसंद करने वाले लोग थे। उन्हें यह course पसंद आया

  • अगर किसी चीज़ पर "अनिवार्य" या "परिचय" लिखा हो, तो वह अक्सर इस बात का संकेत होता है कि अंदर एक बहुत सघन textbook आपका इंतज़ार कर रही है