डैम एल्गोरिथ्म
त्रुटि का पता लगाने में, डैम एल्गोरिथ्म जांच अंक एल्गोरिदम है जो सभी प्रतिलेखन त्रुटि या एकल-अंक त्रुटियों और सभी ट्रांसक्रिप्शन त्रुटि या ट्रांसपोज़िशन त्रुटि का पता लगाता है। इसे 2004 में एच. माइकल डैम द्वारा प्रस्तुत किया गया था।[1]
सशक्तता और अशक्तता
सशक्त
डैम एल्गोरिथम वेरहॉफ एल्गोरिथम के समान है। यह दो सबसे अधिक बार दिखाई देने वाली प्रकार की ट्रांसक्रिप्शन त्रुटियों की सभी घटनाओं का भी पता लगाएगा, अर्थात् अंक को बदलना या दो आसन्न अंकों को ट्रांसपोज़ करता है (अनुगामी जांच अंक और पूर्ववर्ती अंक के ट्रांसपोज़ेशन सहित)।[1][2] इस प्रकार डैम एल्गोरिथ्म का लाभ यह है कि इसमें समर्पित रूप से निर्मित क्रमपरिवर्तन और इसकी स्थिति-विशिष्ट घातांक या वेरहॉफ एल्गोरिथ्म के एब्स्ट्रेक्ट बीजगणित में नहीं है। जब ऑपरेशन तालिका की सभी मुख्य विकर्ण प्रविष्टियाँ शून्य हों तो व्युत्क्रम तत्व की तालिका को भी समाप्त किया जा सकता है।
डैम एल्गोरिथ्म केवल 10 संभावित मान उत्पन्न करता है, गैर-अंकीय वर्ण की आवश्यकता को बहिष्कृत करता है (जैसे कि आईएसबीएन या आईएसबीएन-10 जांच अंक गणना में X या 10-अंकीय आईएसबीएन जांच अंक या आईएसबीएन 10 योजना)।
अग्रणी शून्य को जोड़ने से जांच अंक (वैरीएबल-लंबाई कोड के लिए अशक्त) प्रभावित नहीं होता है।[1]
पूरी तरह से एंटी-सिमेट्रिक अर्धसमूह हैं जो अंग्रेजी भाषा से जुड़ी सभी ध्वन्यात्मक त्रुटियों का पता लगाते हैं (13 ↔ 30, 14 ↔ 40, ..., 19 ↔ 90) उदाहरण में प्रयुक्त तालिका इस प्रकार के उदाहरण पर आधारित है।
अशक्त
डैम एल्गोरिथ्म सहित सभी चेकसम एल्गोरिदम के लिए, अग्रणी शून्य को जोड़ने से जांच अंक प्रभावित नहीं होता है,[1] इसलिए 1, 01, 001, आदि समान जांच अंक उत्पन्न करते हैं। परिणामस्वरूप वैरीएबल-लंबाई कोड को साथ सत्यापित नहीं किया जाना चाहिए।
डिज़ाइन
इसका आवश्यक भाग ऑर्डर (समूह सिद्धांत) 10 का अर्धसमूह है। 10 × 10 इसके केली टेबल के मुख्य भाग के रूप में लैटिन वर्ग) अर्धसमूह या टोटल एंटीसिमेट्री या अशक्त रूप से पूरी तरह से एंटी-सिमेट्रिक होने की विशेष विशेषता के साथ [3][4][lower-roman 1][lower-roman 2][lower-roman 3] डैम ने क्रम 10 के पूरी तरह से विरोधी-सममित अर्धसमूह बनाने के लिए कई विधियों का अनावरण किया और अपने डॉक्टरेट शोध प्रबंध में कुछ उदाहरण दिए थे।[3][lower-roman 1] इस प्रकार इसके साथ, डैम ने पुराने अनुमान को भी निरस्त कर दिया कि ऑर्डर 10 के पूरी तरह से विरोधी सममित अर्धसमूह उपस्थित नहीं हैं।[5]
एक अर्धसमूह (Q, ∗) को पूरी तरह से एंटी-सिमेट्रिक कहा जाता है यदि सभी c, x, y ∈ Q के लिए, निम्नलिखित निहितार्थ हैं: [4] (c ∗ x) ∗ y = (c ∗ y) ∗ x ⇒ x = y
- x ∗ y = y ∗ x ⇒ x = y,
और यदि केवल पहला निहितार्थ सही बैठता है तो इसे अशक्त पूर्णतया विरोधी-सममितीय कहा जाता है। डैम ने सिद्ध किया कि ऑर्डर n के एक पूरी तरह से एंटी-सिमेट्रिक अर्धसमूह का अस्तित्व, ऑर्डर n के एक अशक्त पूरी तरह से एंटी-सिमेट्रिक अर्धसमूह के अस्तित्व के सामान है। इस प्रकार जांच समीकरण के साथ डैम एल्गोरिदम के लिए (...((0 ∗ xm) ∗ xm−1) ∗ ...) ∗ x0 = 0, अर्धसमूह x ∗ x = 0 के साथ एक अशक्त पूरी तरह से एंटी-सिमेट्रिक अर्धसमूह की आवश्यकता है ऐसे अर्धसमूह का निर्माण स्तंभों को इस तरह से पुनर्व्यवस्थित करके किसी भी पूरी तरह से विरोधी-सममित अर्धसमूह से किया जा सकता है कि सभी शून्य विकर्ण पर होंते है। और दूसरी ओर किसी भी अशक्त पूर्णत: सममित-विरोधी अर्धसमूह से स्तंभों को इस प्रकार पुनर्व्यवस्थित करके एक पूर्णतः-सममित-विरोधी अर्धसमूह का निर्माण किया जा सकता है कि पहली पंक्ति प्राकृतिक क्रम में होते है।[3]
एल्गोरिथम
जांच अंक वाले अंक अनुक्रम की वैधता अर्धसमूह पर परिभाषित की जाती है। इस प्रकार उपयोग के लिए तैयार अर्धसमूह तालिका डैम के शोध प्रबंध (पृष्ठ 98, 106, 111) से ली जा सकती है।[3] इस प्रकार यदि प्रत्येक मुख्य विकर्ण प्रविष्टि 0 है तो यह उपयोगी है ,[1] क्योंकि यह जांच अंक गणना को सरल बनाता है।
सम्मिलित जांच अंक के विरुद्ध किसी संख्या का सत्यापन करना
- एक अंतरिम अंक सेट करें और इसे 0 से प्रारंभ करें .
- संख्या के अंक को अंक के अनुसार संसाधित करें, संख्या के अंक को स्तंभ सूचकांक के रूप में और अंतरिम अंक को पंक्ति सूचकांक के रूप में उपयोग करें, तालिका प्रविष्टि लें और अंतरिम अंक को इसके साथ बदलें।
- संख्या तभी मान्य है जब परिणामी अंतरिम अंक का मान 0 हो।[1]
जांच अंक की गणना
पूर्वावश्यकता: तालिका की मुख्य विकर्ण प्रविष्टियाँ 0 हैं .
- एक अंतरिम अंक सेट करें और इसे 0 से प्रारंभ करें .
- संख्या अंक को अंक दर अंक संसाधित करें: संख्या के अंक को स्तंभ सूचकांक के रूप में और अंतरिम अंक को पंक्ति सूचकांक के रूप में उपयोग करें, तालिका प्रविष्टि लें और अंतरिम अंक को इसके साथ बदलें।
- परिणामस्वरूप अंतरिम अंक जांच अंक देता है और इसे संख्या के पीछे वाले अंक के रूप में जोड़ा जाएगा।[1]
उदाहरण
निम्नलिखित ऑपरेशन तालिका का उपयोग किया जाता है।[1] इसे डैम के डॉक्टरेट शोध प्रबंध पृष्ठ 111 [3] में पूरी तरह से एंटी-सिमेट्रिक अर्धसमूह x ∗ y से पंक्तियों को पुनर्व्यवस्थित करके और क्रमपरिवर्तन φ = (1 2 9 5 4 8 6 7 3) के साथ प्रविष्टियों को परिवर्तित करके और x ⋅ y = φ−1(φ(x) ∗ y) को परिभाषित करके प्राप्त किया जा सकता है।
| ⋅ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 0 | 0 | 3 | 1 | 7 | 5 | 9 | 8 | 6 | 4 | 2 |
| 1 | 7 | 0 | 9 | 2 | 1 | 5 | 4 | 8 | 6 | 3 |
| 2 | 4 | 2 | 0 | 6 | 8 | 7 | 1 | 3 | 5 | 9 |
| 3 | 1 | 7 | 5 | 0 | 9 | 8 | 3 | 4 | 2 | 6 |
| 4 | 6 | 1 | 2 | 3 | 0 | 4 | 5 | 9 | 7 | 8 |
| 5 | 3 | 6 | 7 | 4 | 2 | 0 | 9 | 5 | 8 | 1 |
| 6 | 5 | 8 | 6 | 9 | 7 | 2 | 0 | 1 | 3 | 4 |
| 7 | 8 | 9 | 4 | 5 | 3 | 6 | 2 | 0 | 1 | 7 |
| 8 | 9 | 4 | 3 | 8 | 6 | 1 | 7 | 2 | 0 | 5 |
| 9 | 2 | 5 | 8 | 1 | 4 | 3 | 6 | 7 | 9 | 0 |
मान लीजिए हम संख्या (अंक अनुक्रम) 572 चुनते हैं।
जांच अंक की गणना
| संसाधित होने वाला अंक → स्तंभ सूचकांक | 5 | 7 | 2 |
|---|---|---|---|
| पुराना अंतरिम अंक → पंक्ति सूचकांक | 0 | 9 | 7 |
| तालिका प्रविष्टि → नया अंतरिम अंक | 9 | 7 | 4 |
परिणामी अंतरिम अंक 4 है। यह परिकलित जांच अंक है। हम इसे संख्या के साथ जोड़ते हैं और 5724 प्राप्त करते हैं।
सम्मिलित जांच अंक के विरुद्ध किसी संख्या को मान्य करना
| संसाधित होने वाला अंक → स्तंभ सूचकांक | 5 | 7 | 2 | 4 | |
|---|---|---|---|---|---|
| पुराना अंतरिम अंक → पंक्ति सूचकांक | 0 | 9 | 7 | 4 | |
| तालिका प्रविष्टि → नया अंतरिम अंक | 9 | 7 | 4 | 0 |
परिणामी अंतरिम अंक 0 है, इसलिए संख्या वैध है।
ग्राफिकल चित्रण
यह उपरोक्त उदाहरण है जो जांच अंक (डैश नीला तीर) उत्पन्न करने वाले एल्गोरिदम का विवरण दिखाता है और जांच अंक के साथ संख्या 572 को सत्यापित करता है।
संदर्भ
- ↑ 1.0 1.1 1.2 1.3 1.4 1.5 1.6 1.7 Fenwick, Peter (2014). "Checksums and Error Control". In Fenwick, Peter (ed.). Introduction to Computer Data Representation. Bentham Science Publishers. pp. 191–218. doi:10.2174/9781608058822114010013. ISBN 978-1-60805-883-9.
- ↑ For the types of common errors and their frequencies, see Salomon, David (2005). Coding for Data and Computer Communications. Springer Science+Business Media, Inc. p. 36. ISBN 978-0387-21245-6.
- ↑ 3.0 3.1 3.2 3.3 3.4 Damm, H. Michael (2004). Total anti-symmetrische Quasigruppen (PDF) (Dr. rer. nat.) (in Deutsch). Philipps-Universität Marburg. urn:nbn:de:hebis:04-z2004-05162.
- ↑ 4.0 4.1 Damm, H. Michael (2007). "Totally anti-symmetric quasigroups for all orders n ≠ 2, 6". Discrete Mathematics. 307 (6): 715–729. doi:10.1016/j.disc.2006.05.033. ISSN 0012-365X.
- ↑ Damm, H. Michael (2003). "On the Existence of Totally Anti-Symmetric Quasigroups of Order 4k + 2". Computing. 70 (4): 349–357. doi:10.1007/s00607-003-0017-3. ISSN 0010-485X. S2CID 31659430.
- ↑ 1.0 1.1 Beliavscaia, Galina; Izbaş, Vladimir; Şcerbacov, Victor (2003). "Check character systems over quasigroups and loops" (PDF). Quasigroups and Related Systems. 10 (1): 1–28. ISSN 1561-2848. See page 23.
- ↑ Chen Jiannan (2009). "The NP-completeness of Completing Partial anti-symmetric Latin squares" (PDF). Proceedings of 2009 International Workshop on Information Security and Application (IWISA 2009). Academy Publisher. pp. 322–324. ISBN 978-952-5726-06-0. See page 324.
- ↑ Mileva, A.; Dimitrova, V. (2009). "Quasigroups constructed from complete mappings of a group (Z2n,⊕)" (PDF). Contributions, Sec. Math. Tech. Sci., MANU/MASA. XXX (1–2): 75–93. ISSN 0351-3246. See page 78.
बाहरी संबंध
