उपसर्ग कोड

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

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

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

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

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

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

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

तकनीक

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

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

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