Permutation codes
क्रमपरिवर्तन कोड त्रुटि सुधार कोड का एक परिवार है जिसे पहली बार 1965 में स्लेपियन द्वारा पेश किया गया था. और फ्लैश मेमोरी और पावर-लाइन संचार से संबंधित उनके अनुप्रयोगों के कारण संयोजन और सूचना सिद्धांत दोनों में व्यापक रूप से अध्ययन किया गया है। परिभाषा और गुण एक क्रमपरिवर्तन कोड को सममित समूह के एक उपसमुच्चय के रूप में परिभाषित किया गया है जो लंबाई के तारों के बीच सामान्य हैमिंग दूरी के साथ संपन्न है। अधिक सटीक रूप से, यदि क्रमपरिवर्तन हैं, तो एक क्रमपरिवर्तन कोड की न्यूनतम दूरी को न्यूनतम सकारात्मक पूर्णांक के रूप में परिभाषित किया जाता है जैसे कि मौजूद, विशिष्ट, जैसे कि। कुछ चैनलों के लिए क्रमपरिवर्तन कोड उपयुक्त होने का एक कारण यह है कि वर्णमाला के प्रतीक प्रत्येक कोडवर्ड में केवल एक बार दिखाई देते हैं, जो उदाहरण के लिए पावरलाइन संचार के संदर्भ में होने वाली त्रुटियों को कोडवर्ड गिल्बर्ट-वार्शमोव बाउंड पर कम प्रभावशाली बनाता है। छोटी लंबाई को छोड़कर बहुत कम प्रगति हुई है। हम उन सभी क्रमपरिवर्तनों के समूह को निरूपित करने के लिए परिभाषित कर सकते हैं जिनमें पहचान से बिल्कुल दूरी होती है। मान लीजिए, क्रम की विसंगतियों की संख्या कहाँ है। गिल्बर्ट-वार्शमोव सीमा एक बहुत प्रसिद्ध ऊपरी सीमा है, और अब तक के छोटे मूल्यों के लिए अन्य सीमाओं से बेहतर प्रदर्शन करती है। प्रमेय 1: इस मामले में सुधार हुआ है जहाँ जैसा कि अगली प्रमेय से पता चलता है। प्रमेय 2: यदि किसी पूर्णांक के लिए, तो। और के छोटे मूल्यों के लिए, शोधकर्ताओं ने कुछ निर्धारित ऑटोमोर्फिज्म के साथ सीधे क्रमपरिवर्तन कोड की तलाश करने के लिए विभिन्न कंप्यूटर खोज रणनीतियाँ विकसित की हैं अन्य सीमाएँ क्रमपरिवर्तन कोड पर कई सीमाएँ हैं, हम यहां दो को सूचीबद्ध करते हैं गिल्बर्ट-वार्शमोव बाउंड इम्प्रूवमेंट एक सुधार गिल्बर्ट-वार्शमोव बाउंड के लिए किया जाता है जो पहले से ही ऊपर चर्चा की गई है। कुछ ग्राफों में क्रमपरिवर्तन कोड और स्वतंत्र सेटों के बीच संबंध का उपयोग करके कोई भी गिल्बर्ट-वार्शमोव को एक कारक द्वारा स्पर्शोन्मुख रूप से बांध सकता है, जब कोड की लंबाई अनंत तक जाती है। काइली ग्राफ और में पहचान के पड़ोस द्वारा प्रेरित उपग्राफ को निरूपित करें। मान लीजिए कि प्रमेय 3 में अधिकतम डिग्री दर्शाई गई हैः मान लीजिए और फिर, कहाँ। गिल्बर्ट-वार्शमोव सीमा है, प्रमेय 4: जब निश्चित किया जाता है और अनंत तक जाता है, तो हमारे पास रैखिक कोड का उपयोग करके निचली सीमाएँ होती हैं एक रैखिक ब्लॉक कोड का उपयोग करके, कोई यह साबित कर सकता है कि डिग्री के सममित समूह में एक क्रमपरिवर्तन कोड मौजूद है, जिसमें कम से कम न्यूनतम दूरी और बड़ी कार्डिनलिटी है। क्रमपरिवर्तन कोड के लिए एक निचली सीमा जो क्रमपरिवर्तन कोड की लंबाई और दूरी के कुछ नियमों में स्पर्शोन्मुख सुधार प्रदान करती है, नीचे चर्चा की गई है। सममित समूह के दिए गए सबसेट के लिए, हम कम से कम पूरी तरह से निहित न्यूनतम दूरी के क्रमपरिवर्तन कोड की अधिकतम कार्डिनलिटी से दर्शाते हैं, अर्थात। .. प्रमेय 5: मान लीजिए कि पूर्णांक ऐसे हों कि और। इसके अलावा एक अभाज्य शक्ति होने दें और सकारात्मक पूर्णांक होने दें जैसे कि और। यदि कोई ऐसा कोड मौजूद है जिसमें हैमिंग भार का एक कूटशब्द है, तो जहां कोरोलरी 1: प्रत्येक अभाज्य शक्ति के लिए, प्रत्येक के लिए,। उपसंहार 2: प्रत्येक अभाज्य शक्ति के लिए, प्रत्येक के लिए। संदर्भ त्रुटि का पता लगाने और सुधार