ली दूरी

कोडिंग सिद्धांत में, ली दूरी q ≥ 2 के q-ary वर्ण-क्रम {0, 1, …, q − 1} पर समान लंबाई n की दो स्ट्रिंग (कंप्यूटर विज्ञान) $x_{1}x_{2}\dots x_{n}$ और $y_{1}y_{2}\dots y_{n}$ के बीच की दूरी है। यह एक मीट्रिक है जिसे इस प्रकार परिभाषित किया गया है

$$\sum _{i=1}^{n}\min(|x_{i}-y_{i}|,\,q-|x_{i}-y_{i}|).$$

यदि q = 2 या q = 3 ली दूरी हैमिंग दूरी के साथ मेल खाती है, क्योंकि दोनों दूरियाँ दो एकल समान प्रतीकों के लिए 0 हैं और दो एकल गैर-समान प्रतीकों के लिए 1 हैं। q > 3 के लिए अब यह स्थिति नहीं है; एकल अक्षरों के बीच ली की दूरी 1 से बड़ी हो सकती है। चूँकि, ली वजन के साथ $\mathbb {Z} _{4}$ और हैमिंग वजन के साथ $\mathbb {Z} _{2}^{2}$ के बीच एक ग्रे आइसोमेट्री (वजन-संरक्षण आक्षेप) उपस्थित है।

वर्ण-क्रम को योगात्मक समूह Z_q के रूप में मानते हुए, दो एकल अक्षरों $x$ और $y$ के बीच की दूरी केली ग्राफ में सबसे छोटे पथ की लंबाई है (जो कि समूह चक्रीय होने के कारण वृत्ताकार है)। अधिक सामान्यतः n लंबाई के दो तारों के बीच की ली दूरी, केली ग्राफ़ में उनके बीच के सबसे छोटे पथ की लंबाई है। इसे मैनहट्टन दूरी मॉड्यूलो जालक $\mathbf {Z} _{q}^{n}$ के साथ Zⁿ को कम करने के परिणामस्वरूप प्राप्त भागफल मीट्रिक के रूप में भी सोचा जा सकता है। Zⁿ मॉड्यूलो के भागफल पर अनुरूप भागफल मीट्रिक एक इच्छानुसार जालक को मैनहेम मीट्रिक या मैनहेम दूरी के रूप में जाना जाता है।

ली दूरी से प्रेरित मीट्रिक समिष्ट एलिप्टिक ज्यामिति का अलग एनालॉग है।

उदाहरण

यदि q = 6 है, तो 3140 और 2543 के बीच ली दूरी 1 + 2 + 0 + 3 = 6 है।

इतिहास और अनुप्रयोग

ली दूरी का नाम चेस्टर ची युआन ली (李始元) के नाम पर रखा गया है। इसे चरण मॉडुलन के लिए प्रयुक्त किया जाता है जबकि हैमिंग दूरी का उपयोग ऑर्थोगोनल मॉड्यूलेशन के स्थिति में किया जाता है।

बर्लेकैंप कोड ली मेट्रिक में कोड का एक उदाहरण है। अन्य महत्वपूर्ण उदाहरण प्रीपेराटा कोड और केरडॉक कोड हैं; जब किसी क्षेत्र पर विचार किया जाता है तो ये कोड गैर-रैखिक होते हैं, किन्तु वलय के ऊपर रैखिक होते हैं।

संदर्भ

• Lee, C. Y. (1958), "Some properties of nonbinary error-correcting codes", IRE Transactions on Information Theory, 4 (2): 77–82, doi:10.1109/TIT.1958.1057446
• Berlekamp, Elwyn R. (1968), Algebraic Coding Theory, McGraw-Hill
• Voloch, Jose Felipe; Walker, Judy L. (1998). "Lee Weights of Codes from Elliptic Curves". In Vardy, Alexander (ed.). Codes, Curves, and Signals: Common Threads in Communications. Springer Science & Business Media. ISBN 978-1-4615-5121-8.