उपसर्ग कोड

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

उदाहरण के लिए, कोड शब्द {9, 55} वाले कोड में उपसर्ग गुण होता है; {9,5,59,55} वाला कोड ऐसा नहीं करता, क्योंकि 5, 59 का उपसर्ग है और 55 का भी। उपसर्ग कोड विशिष्ट रूप से डिकोड करने योग्य कोड है: पूर्ण और सटीक अनुक्रम दिए जाने पर, रिसीवर शब्दों के बीच विशेष मार्कर की आवश्यकता के बिना प्रत्येक शब्द की पहचान कर सकता है। हालाँकि, विशिष्ट रूप से डिकोड करने योग्य कोड हैं जो उपसर्ग कोड नहीं हैं; उदाहरण के लिए, उपसर्ग कोड का उल्टा अभी भी विशिष्ट रूप से डिकोड करने योग्य है (यह प्रत्यय कोड है), लेकिन यह जरूरी नहीं कि यह उपसर्ग कोड हो।

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

उपसर्ग कोड का उपयोग करके, संदेश को बिना किसी आउट-ऑफ़-बैंड डेटा | आउट-ऑफ-बैंड मार्कर या (वैकल्पिक रूप से) शब्दों के बीच विशेष मार्करों के बिना संदेश में शब्दों को फ्रेम करने (दूरसंचार) के रूप में प्रसारित किया जा सकता है। . प्राप्तकर्ता वैध कोड शब्द बनाने वाले अनुक्रमों को बार-बार ढूंढकर और हटाकर, संदेश को स्पष्ट रूप से डिकोड कर सकता है। यह आम तौर पर उन कोडों के साथ संभव नहीं है जिनमें उपसर्ग गुण का अभाव होता है, उदाहरण के लिए {0,1,10,11}: कोड शब्द की शुरुआत में 1 पढ़ने वाला रिसीवर यह नहीं जान पाएगा कि क्या वह पूरा कोड शब्द 1 था, या केवल कोड शब्द 10 या 11 का उपसर्ग; इसलिए स्ट्रिंग 10 की व्याख्या या तो एकल कोडवर्ड के रूप में या 1 और फिर 0 शब्दों के संयोजन के रूप में की जा सकती है।

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

उपसर्ग कोड त्रुटि-सुधार करने वाले कोड नहीं हैं। व्यवहार में, संदेश को पहले उपसर्ग कोड के साथ संपीड़ित किया जा सकता है, और फिर ट्रांसमिशन से पहले चैनल कोडिंग (त्रुटि सुधार सहित) के साथ फिर से एन्कोड किया जा सकता है।

किसी भी वेरिएबल-लेंथ_कोड#Uniquely_decodable_codes कोड के लिए उपसर्ग कोड होता है जिसकी कोड शब्द लंबाई समान होती है। क्राफ्ट की असमानता कोड शब्द लंबाई के सेट की विशेषता बताती है जो वेरिएबल-लेंथ_कोड#यूनीकली_डिकोडेबल_कोड कोड में संभव है।

तकनीक

यदि कोड में प्रत्येक शब्द की लंबाई समान है, तो कोड को निश्चित-लंबाई कोड, या ब्लॉक कोड कहा जाता है (हालांकि ब्लॉक कोड शब्द का उपयोग चैनल कोडिंग में निश्चित आकार के त्रुटि-सुधार कोड के लिए भी किया जाता है)। उदाहरण के लिए, ISO 8859-15 अक्षर हमेशा 8 बिट लंबे होते हैं। UTF-32/UCS-4 अक्षर हमेशा 32 बिट लंबे होते हैं।अतुल्यकालिक अंतरण विधा हमेशा 424 बिट्स (53 बाइट्स) लंबा होता है। निश्चित लंबाई k बिट्स का निश्चित-लंबाई कोड तक एनकोड कर सकता है $2^{k}$ स्रोत प्रतीक.

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

संक्षिप्त बाइनरी एन्कोडिंग उन मामलों से निपटने के लिए निश्चित-लंबाई कोड का सीधा सामान्यीकरण है जहां प्रतीकों की संख्या n दो की शक्ति नहीं है। स्रोत प्रतीकों को लंबाई k और k+1 के कोडवर्ड दिए गए हैं, जहां k को चुना गया है ताकि 2^क < n ≤ 2^k+1.

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

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

स्व-सिंक्रोनाइज़िंग कोड उपसर्ग कोड होते हैं जो फ्रेम तुल्यकालन की अनुमति देते हैं।

संबंधित अवधारणाएँ

प्रत्यय कोड शब्दों का समूह है जिनमें से कोई भी किसी अन्य का प्रत्यय नहीं है; समकक्ष रूप से, शब्दों का समूह जो उपसर्ग कोड के विपरीत होता है। उपसर्ग कोड की तरह, ऐसे शब्दों के संयोजन के रूप में स्ट्रिंग का प्रतिनिधित्व अद्वितीय है। बिफ़िक्स कोड शब्दों का समूह है जो उपसर्ग और प्रत्यय कोड दोनों है। इष्टतम उपसर्ग कोड न्यूनतम औसत लंबाई वाला उपसर्ग कोड होता है। यानि की वर्णमाला मान लीजिये nसंभावनाओं वाले प्रतीक $p(A_{i})$ उपसर्ग कोड के लिए C. अगर C' अन्य उपसर्ग कोड है और $\lambda '_{i}$ के कोडवर्ड की लंबाई हैं C', तब $\sum _{i=1}^{n}{\lambda _{i}p(A_{i})}\leq \sum _{i=1}^{n}{\lambda '_{i}p(A_{i})}\!$.

उपसर्ग कोड आज उपयोग में हैं

उपसर्ग कोड के उदाहरणों में शामिल हैं:

• चर-लंबाई हफ़मैन कोडिंग
• देश कॉलिंग कोड
• चेन-हो एन्कोडिंग
• आईएसबीएन का देश और प्रकाशक भाग
• UMTS W-CDMA 3G वायरलेस स्टैंडर्ड में प्रयुक्त सेकेंडरी सिंक्रोनाइज़ेशन कोड
• वीसीआर प्लस|वीसीआर प्लस+ कोड
• यूनिकोड परिवर्तन प्रारूप, विशेष रूप से यूनिकोड वर्णों को एन्कोड करने के लिए यूटीएफ-8 -8 प्रणाली, जो उपसर्ग-मुक्त कोड और स्व-सिंक्रनाइज़िंग कोड दोनों है
• परिवर्तनीय-लंबाई मात्रा

तकनीक

उपसर्ग कोड के निर्माण के लिए आम तौर पर उपयोग की जाने वाली तकनीकों में हफ़मैन कोडिंग और पहले के शैनन-फ़ानो कोडिंग|शैनन-फ़ानो कोड, और यूनिवर्सल कोड (डेटा संपीड़न) शामिल हैं जैसे:

• इलियास डेल्टा कोडिंग
• इलियास गामा कोडिंग
• इलियास ओमेगा कोडिंग
• फाइबोनैचि कोडिंग
• लेवेनशेटिन कोडिंग
• यूनरी कोडिंग
• गोलोम्ब राइस कोड
• फैला हुआ बिसात (सरल क्रिप्टोग्राफी तकनीक जो उपसर्ग कोड उत्पन्न करती है)
• बाइनरी कोडिंग

संदर्भ

• Berstel, Jean; Perrin, Dominique; Reutenauer, Christophe (2010). Codes and automata. Encyclopedia of Mathematics and its Applications. Vol. 129. Cambridge: Cambridge University Press. ISBN 978-0-521-88831-8. Zbl 1187.94001.
• Elias, Peter (1975). "Universal codeword sets and representations of the integers". IEEE Trans. Inf. Theory. 21 (2): 194–203. doi:10.1109/tit.1975.1055349. ISSN 0018-9448. Zbl 0298.94011.
• D.A. Huffman, "A method for the construction of minimum-redundancy codes", Proceedings of the I.R.E., Sept. 1952, pp. 1098–1102 (Huffman's original article)
• Profile: David A. Huffman, Scientific American, Sept. 1991, pp. 54–58 (Background story)
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 16.3, pp. 385–392.
•  This article incorporates public domain material from Federal Standard 1037C. General Services Administration. Archived from the original on 2022-01-22.

बाहरी संबंध

• Codes, trees and the prefix property by Kona Macphee