डैम एल्गोरिथ्म: Difference between revisions
(Created page with "त्रुटि का पता लगाने में, डैम कलन विधि एक संख्या जांचें एल्गोरिद...") |
No edit summary |
||
| Line 1: | Line 1: | ||
त्रुटि का पता लगाने में, डैम [[कलन विधि]] | त्रुटि का पता लगाने में, डैम [[कलन विधि]] [[ संख्या जांचें |संख्या जांचें]] एल्गोरिदम है जो सभी [[प्रतिलेखन त्रुटि]] | एकल-अंक त्रुटियों और सभी ट्रांसक्रिप्शन त्रुटि # ट्रांसपोज़िशन त्रुटि का पता लगाता है। इसे 2004 में एच. माइकल डैम द्वारा प्रस्तुत किया गया था।<ref name="fenwick2014" /> | ||
| Line 5: | Line 5: | ||
=== ताकत === | === ताकत === | ||
डैम एल्गोरिथम [[वेरहॉफ एल्गोरिथम]] के समान है। यह दो सबसे अधिक बार दिखाई देने वाली प्रकार की ट्रांसक्रिप्शन त्रुटियों की सभी घटनाओं का भी पता लगाएगा, अर्थात् | डैम एल्गोरिथम [[वेरहॉफ एल्गोरिथम]] के समान है। यह दो सबसे अधिक बार दिखाई देने वाली प्रकार की ट्रांसक्रिप्शन त्रुटियों की सभी घटनाओं का भी पता लगाएगा, अर्थात् अंक को बदलना या दो आसन्न अंकों को ट्रांसपोज़ करना (अनुगामी चेक अंक और पूर्ववर्ती अंक के ट्रांसपोज़ेशन सहित)।<ref name="fenwick2014" /><ref name="Salomon2005" />डैम एल्गोरिथ्म का लाभ यह है कि इसमें समर्पित रूप से निर्मित क्रम[[परिवर्तन]] और इसकी स्थिति-विशिष्ट घातांक # वेरहॉफ एल्गोरिथ्म के अमूर्त बीजगणित में नहीं है। जब ऑपरेशन तालिका की सभी मुख्य विकर्ण प्रविष्टियाँ शून्य हों तो व्युत्क्रम तत्व की तालिका को भी समाप्त किया जा सकता है। | ||
डैम एल्गोरिथ्म केवल 10 संभावित मान उत्पन्न करता है, गैर-अंकीय वर्ण की आवश्यकता को टालता है (जैसे कि आईएसबीएन#आईएसबीएन-10 चेक अंक गणना में [[एक्स]]|10-अंकीय आईएसबीएन चेक अंक#आईएसबीएन_10 योजना)। | डैम एल्गोरिथ्म केवल 10 संभावित मान उत्पन्न करता है, गैर-अंकीय वर्ण की आवश्यकता को टालता है (जैसे कि आईएसबीएन#आईएसबीएन-10 चेक अंक गणना में [[एक्स]]|10-अंकीय आईएसबीएन चेक अंक#आईएसबीएन_10 योजना)। | ||
अग्रणी शून्य को जोड़ने से चेक अंक (चर-लंबाई कोड के लिए | अग्रणी शून्य को जोड़ने से चेक अंक (चर-लंबाई कोड के लिए कमजोरी) प्रभावित नहीं होता है।<ref name="fenwick2014" /> | ||
पूरी तरह से एंटी-सिमेट्रिक क्वासिग्रुप हैं जो अंग्रेजी भाषा से जुड़ी सभी ध्वन्यात्मक त्रुटियों का पता लगाते हैं ({{nowrap|13 ↔ 30}}, {{nowrap|14 ↔ 40}}, ..., {{nowrap|19 ↔ 90}}). उदाहरणात्मक उदाहरण में प्रयुक्त तालिका इस प्रकार के | पूरी तरह से एंटी-सिमेट्रिक क्वासिग्रुप हैं जो अंग्रेजी भाषा से जुड़ी सभी ध्वन्यात्मक त्रुटियों का पता लगाते हैं ({{nowrap|13 ↔ 30}}, {{nowrap|14 ↔ 40}}, ..., {{nowrap|19 ↔ 90}}). उदाहरणात्मक उदाहरण में प्रयुक्त तालिका इस प्रकार के उदाहरण पर आधारित है। | ||
=== कमजोरियाँ === | === कमजोरियाँ === | ||
डैम एल्गोरिथ्म सहित सभी चेकसम एल्गोरिदम के लिए, अग्रणी शून्य को जोड़ने से चेक अंक प्रभावित नहीं होता है,<ref name="fenwick2014" />इसलिए 1, 01, 001, आदि समान चेक अंक उत्पन्न करते हैं। परिणामस्वरूप चर-लंबाई कोड को | डैम एल्गोरिथ्म सहित सभी चेकसम एल्गोरिदम के लिए, अग्रणी शून्य को जोड़ने से चेक अंक प्रभावित नहीं होता है,<ref name="fenwick2014" />इसलिए 1, 01, 001, आदि समान चेक अंक उत्पन्न करते हैं। परिणामस्वरूप चर-लंबाई कोड को साथ सत्यापित नहीं किया जाना चाहिए। | ||
== डिज़ाइन == | == डिज़ाइन == | ||
इसका आवश्यक भाग ऑर्डर (समूह सिद्धांत) 10 का | इसका आवश्यक भाग ऑर्डर (समूह सिद्धांत) 10 का अर्धसमूह है (अर्थात् होना)। {{nowrap|10 × 10}} इसके [[केली टेबल]] के मुख्य भाग के रूप में [[लैटिन वर्ग]]) क्वासिग्रुप#टोटल एंटीसिमेट्री|कमजोर रूप से पूरी तरह से एंटी-सिमेट्रिक होने की विशेष विशेषता के साथ।<ref name="dhmd" /><ref name="damm2007" /><ref group="lower-roman" name="BIS2003" /><ref group="lower-roman" name="Chen2009" /><ref group="lower-roman" name="Mileva2009" />डैम ने क्रम 10 के पूरी तरह से विरोधी-सममित क्वासिग्रुप बनाने के लिए कई तरीकों का खुलासा किया और अपने डॉक्टरेट शोध प्रबंध में कुछ उदाहरण दिए।<ref name="dhmd" /><ref group="lower-roman" name="BIS2003" />इसके साथ, डैम ने पुराने अनुमान को भी खारिज कर दिया कि ऑर्डर 10 के पूरी तरह से विरोधी सममित क्वासिग्रुप मौजूद नहीं हैं।<ref name="damm2003" /> | ||
एक अर्धसमूह {{math|(''Q'', ∗)}} को यदि सभी के लिए पूर्णतः सममित विरोधी कहा जाता है {{math|''c'', ''x'', ''y'' ∈ ''Q''}}, निम्नलिखित निहितार्थ हैं:<ref name="damm2007" /># {{math|1=(''c'' ∗ ''x'') ∗ ''y'' = (''c'' ∗ ''y'') ∗ ''x'' ⇒ ''x'' = ''y''}} | एक अर्धसमूह {{math|(''Q'', ∗)}} को यदि सभी के लिए पूर्णतः सममित विरोधी कहा जाता है {{math|''c'', ''x'', ''y'' ∈ ''Q''}}, निम्नलिखित निहितार्थ हैं:<ref name="damm2007" /># {{math|1=(''c'' ∗ ''x'') ∗ ''y'' = (''c'' ∗ ''y'') ∗ ''x'' ⇒ ''x'' = ''y''}} | ||
# {{math|1=''x'' ∗ ''y'' = ''y'' ∗ ''x'' ⇒ ''x'' = ''y''}}, | # {{math|1=''x'' ∗ ''y'' = ''y'' ∗ ''x'' ⇒ ''x'' = ''y''}}, | ||
और यदि केवल पहला निहितार्थ सही बैठता है तो इसे कमजोर पूर्णतया विरोधी-सममितीय कहा जाता है। लानत ने साबित कर दिया कि क्रम के | और यदि केवल पहला निहितार्थ सही बैठता है तो इसे कमजोर पूर्णतया विरोधी-सममितीय कहा जाता है। लानत ने साबित कर दिया कि क्रम के पूरी तरह से एंटीसिमेट्रिक अर्ध समूह का अस्तित्व {{math|''n''}} आदेश के कमजोर पूर्णतः विरोधी सममित अर्धसमूह के अस्तित्व के बराबर है {{math|''n''}}. चेक समीकरण के साथ डैम एल्गोरिदम के लिए | ||
{{math|1=(...((0 ∗ ''x<sub>m</sub>'') ∗ ''x''<sub>''m''−1</sub>) ∗ ...) ∗ ''x''<sub>0</sub> = 0}}, | {{math|1=(...((0 ∗ ''x<sub>m</sub>'') ∗ ''x''<sub>''m''−1</sub>) ∗ ...) ∗ ''x''<sub>0</sub> = 0}}, | ||
संपत्ति के साथ | संपत्ति के साथ कमजोर पूरी तरह से विरोधी सममित अर्धसमूह | ||
{{math|1=''x'' ∗ ''x'' = 0}} | {{math|1=''x'' ∗ ''x'' = 0}} | ||
ज़रूरी है। ऐसे अर्धसमूह का निर्माण स्तंभों को इस तरह से पुनर्व्यवस्थित करके किसी भी पूरी तरह से विरोधी-सममित अर्धसमूह से किया जा सकता है कि सभी शून्य विकर्ण पर हों। और, दूसरी ओर, किसी भी कमजोर पूरी तरह से विरोधी-सममित क्वासिग्रुप से स्तंभों को इस तरह से पुनर्व्यवस्थित करके | ज़रूरी है। ऐसे अर्धसमूह का निर्माण स्तंभों को इस तरह से पुनर्व्यवस्थित करके किसी भी पूरी तरह से विरोधी-सममित अर्धसमूह से किया जा सकता है कि सभी शून्य विकर्ण पर हों। और, दूसरी ओर, किसी भी कमजोर पूरी तरह से विरोधी-सममित क्वासिग्रुप से स्तंभों को इस तरह से पुनर्व्यवस्थित करके पूरी तरह से विरोधी-सममित क्वासिग्रुप का निर्माण किया जा सकता है कि पहली पंक्ति प्राकृतिक क्रम में हो।<ref name="dhmd" /> | ||
== एल्गोरिथम == | == एल्गोरिथम == | ||
चेक अंक वाले अंक अनुक्रम की वैधता | चेक अंक वाले अंक अनुक्रम की वैधता क्वासिग्रुप पर परिभाषित की जाती है। उपयोग के लिए तैयार क्वासिग्रुप तालिका डैम के शोध प्रबंध (पृष्ठ 98, 106, 111) से ली जा सकती है।<ref name="dhmd" />यदि प्रत्येक मुख्य विकर्ण प्रविष्टि है तो यह उपयोगी है {{math|0}},<ref name=fenwick2014 />क्योंकि यह चेक अंक गणना को सरल बनाता है। | ||
=== शामिल चेक अंक के विरुद्ध किसी संख्या को मान्य करना === | === शामिल चेक अंक के विरुद्ध किसी संख्या को मान्य करना === | ||
Revision as of 09:12, 31 July 2023
त्रुटि का पता लगाने में, डैम कलन विधि संख्या जांचें एल्गोरिदम है जो सभी प्रतिलेखन त्रुटि | एकल-अंक त्रुटियों और सभी ट्रांसक्रिप्शन त्रुटि # ट्रांसपोज़िशन त्रुटि का पता लगाता है। इसे 2004 में एच. माइकल डैम द्वारा प्रस्तुत किया गया था।[1]
ताकत और कमजोरियाँ
ताकत
डैम एल्गोरिथम वेरहॉफ एल्गोरिथम के समान है। यह दो सबसे अधिक बार दिखाई देने वाली प्रकार की ट्रांसक्रिप्शन त्रुटियों की सभी घटनाओं का भी पता लगाएगा, अर्थात् अंक को बदलना या दो आसन्न अंकों को ट्रांसपोज़ करना (अनुगामी चेक अंक और पूर्ववर्ती अंक के ट्रांसपोज़ेशन सहित)।[1][2]डैम एल्गोरिथ्म का लाभ यह है कि इसमें समर्पित रूप से निर्मित क्रमपरिवर्तन और इसकी स्थिति-विशिष्ट घातांक # वेरहॉफ एल्गोरिथ्म के अमूर्त बीजगणित में नहीं है। जब ऑपरेशन तालिका की सभी मुख्य विकर्ण प्रविष्टियाँ शून्य हों तो व्युत्क्रम तत्व की तालिका को भी समाप्त किया जा सकता है।
डैम एल्गोरिथ्म केवल 10 संभावित मान उत्पन्न करता है, गैर-अंकीय वर्ण की आवश्यकता को टालता है (जैसे कि आईएसबीएन#आईएसबीएन-10 चेक अंक गणना में एक्स|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]इसे पूरी तरह से एंटी-सिमेट्रिक क्वासिग्रुप से प्राप्त किया जा सकता है x ∗ yडैम के डॉक्टरेट शोध प्रबंध पृष्ठ 111 में[3]पंक्तियों को पुनर्व्यवस्थित करके और क्रमपरिवर्तन के साथ प्रविष्टियों को बदलकर φ = (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 चुनते हैं।
चेक अंक की गणना
| digit to be processed → column index | 5 | 7 | 2 |
|---|---|---|---|
| old interim digit → row index | 0 | 9 | 7 |
| table entry → new interim digit | 9 | 7 | 4 |
परिणामी अंतरिम अंक 4 है। यह परिकलित चेक अंक है। हम इसे संख्या के साथ जोड़ते हैं और 5724 प्राप्त करते हैं।
शामिल चेक अंक के विरुद्ध किसी संख्या को मान्य करना
| digit to be processed → column index | 5 | 7 | 2 | 4 | |
|---|---|---|---|---|---|
| old interim digit → row index | 0 | 9 | 7 | 4 | |
| table entry → new interim digit | 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.
बाहरी संबंध
