डैम एल्गोरिथ्म: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
त्रुटि का पता लगाने में, डैम [[कलन विधि]] [[ संख्या जांचें |संख्या जांचें]] एल्गोरिदम है जो सभी [[प्रतिलेखन त्रुटि]] | एकल-अंक त्रुटियों और सभी ट्रांसक्रिप्शन त्रुटि # ट्रांसपोज़िशन त्रुटि का पता लगाता है। इसे 2004 में एच. माइकल डैम द्वारा प्रस्तुत किया गया था।<ref name="fenwick2014" />
त्रुटि का पता लगाने में, डैम [[कलन विधि|एल्गोरिथ्म]] [[ संख्या जांचें |चेक डिजिट]] एल्गोरिदम है जो सभी [[प्रतिलेखन त्रुटि]] या एकल-अंक त्रुटियों और सभी ट्रांसक्रिप्शन त्रुटि या  ट्रांसपोज़िशन त्रुटि का पता लगाता है। इसे 2004 में एच. माइकल डैम द्वारा प्रस्तुत किया गया था।<ref name="fenwick2014" />


== सशक्तता और अशक्त ==


== ताकत और कमजोरियाँ ==
=== सशक्त ===
डैम एल्गोरिथम [[वेरहॉफ एल्गोरिथम]] के समान है। यह दो सबसे अधिक बार दिखाई देने वाली प्रकार की ट्रांसक्रिप्शन त्रुटियों की सभी घटनाओं का भी पता लगाएगा, अर्थात् अंक को बदलना या दो आसन्न अंकों को ट्रांसपोज़ करता है (अनुगामी चेक अंक और पूर्ववर्ती अंक के ट्रांसपोज़ेशन सहित)।<ref name="fenwick2014" /><ref name="Salomon2005" /> इस प्रकार डैम एल्गोरिथ्म का लाभ यह है कि इसमें समर्पित रूप से निर्मित क्रम[[परिवर्तन]] और इसकी स्थिति-विशिष्ट घातांक या वेरहॉफ एल्गोरिथ्म के एब्स्ट्रेक्ट बीजगणित में नहीं है। जब ऑपरेशन तालिका की सभी मुख्य विकर्ण प्रविष्टियाँ शून्य हों तो व्युत्क्रम तत्व की तालिका को भी समाप्त किया जा सकता है।


=== ताकत ===
डैम एल्गोरिथ्म केवल 10 संभावित मान उत्पन्न करता है, गैर-अंकीय वर्ण की आवश्यकता को बहिष्कृत करता है (जैसे कि आईएसबीएन या आईएसबीएन-10 चेक अंक गणना में [[एक्स]] या 10-अंकीय आईएसबीएन चेक अंक या आईएसबीएन 10 योजना)।
डैम एल्गोरिथम [[वेरहॉफ एल्गोरिथम]] के समान है। यह दो सबसे अधिक बार दिखाई देने वाली प्रकार की ट्रांसक्रिप्शन त्रुटियों की सभी घटनाओं का भी पता लगाएगा, अर्थात् अंक को बदलना या दो आसन्न अंकों को ट्रांसपोज़ करना (अनुगामी चेक अंक और पूर्ववर्ती अंक के ट्रांसपोज़ेशन सहित)।<ref name="fenwick2014" /><ref name="Salomon2005" />डैम एल्गोरिथ्म का लाभ यह है कि इसमें समर्पित रूप से निर्मित क्रम[[परिवर्तन]] और इसकी स्थिति-विशिष्ट घातांक # वेरहॉफ एल्गोरिथ्म के अमूर्त बीजगणित में नहीं है। जब ऑपरेशन तालिका की सभी मुख्य विकर्ण प्रविष्टियाँ शून्य हों तो व्युत्क्रम तत्व की तालिका को भी समाप्त किया जा सकता है।


डैम एल्गोरिथ्म केवल 10 संभावित मान उत्पन्न करता है, गैर-अंकीय वर्ण की आवश्यकता को टालता है (जैसे कि आईएसबीएन#आईएसबीएन-10 चेक अंक गणना में [[एक्स]]|10-अंकीय आईएसबीएन चेक अंक#आईएसबीएन_10 योजना)
अग्रणी शून्य को जोड़ने से चेक अंक (चर-लंबाई कोड के लिए अशक्ती) प्रभावित नहीं होता है।<ref name="fenwick2014" />


अग्रणी शून्य को जोड़ने से चेक अंक (चर-लंबाई कोड के लिए कमजोरी) प्रभावित नहीं होता है।<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 का अर्धसमूह है (अर्थात् होना)। {{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" />
इसका आवश्यक भाग ऑर्डर (समूह सिद्धांत) 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=''x'' ∗ ''x'' = 0}}
ज़रूरी है। ऐसे अर्धसमूह का निर्माण स्तंभों को इस तरह से पुनर्व्यवस्थित करके किसी भी पूरी तरह से विरोधी-सममित अर्धसमूह से किया जा सकता है कि सभी शून्य विकर्ण पर हों। और, दूसरी ओर, किसी भी कमजोर पूरी तरह से विरोधी-सममित क्वासिग्रुप से स्तंभों को इस तरह से पुनर्व्यवस्थित करके पूरी तरह से विरोधी-सममित क्वासिग्रुप का निर्माण किया जा सकता है कि पहली पंक्ति प्राकृतिक क्रम में हो।<ref name="dhmd" />




और यदि केवल पहला निहितार्थ सही बैठता है तो इसे अशक्त पूर्णतया विरोधी-सममितीय कहा जाता है। डैम ने सिद्ध किया कि ऑर्डर n के एक पूरी तरह से एंटी-सिमेट्रिक अर्धसमूह का अस्तित्व, ऑर्डर n के एक अशक्त पूरी तरह से एंटी-सिमेट्रिक अर्धसमूह के अस्तित्व के सामान है। इस प्रकार चेक समीकरण के साथ डैम एल्गोरिदम के लिए {{math|1=(...((0 ∗ ''x<sub>m</sub>'') ∗ ''x''<sub>''m''−1</sub>) ∗ ...) ∗ ''x''<sub>0</sub> = 0}}, अर्धसमूह {{math|1=''x'' ∗ ''x'' = 0}} के साथ एक अशक्त पूरी तरह से एंटी-सिमेट्रिक अर्धसमूह की आवश्यकता है ऐसे अर्धसमूह का निर्माण स्तंभों को इस तरह से पुनर्व्यवस्थित करके किसी भी पूरी तरह से विरोधी-सममित अर्धसमूह से किया जा सकता है कि सभी शून्य विकर्ण पर होंते है। और दूसरी ओर किसी भी अशक्त पूर्णत: सममित-विरोधी अर्धसमूह से स्तंभों को इस प्रकार पुनर्व्यवस्थित करके एक पूर्णतः-सममित-विरोधी अर्धसमूह का निर्माण किया जा सकता है कि पहली पंक्ति प्राकृतिक क्रम में होते है।<ref name="dhmd" />
== एल्गोरिथम ==
== एल्गोरिथम ==
चेक अंक वाले अंक अनुक्रम की वैधता क्वासिग्रुप पर परिभाषित की जाती है। उपयोग के लिए तैयार क्वासिग्रुप तालिका डैम के शोध प्रबंध (पृष्ठ 98, 106, 111) से ली जा सकती है।<ref name="dhmd" />यदि प्रत्येक मुख्य विकर्ण प्रविष्टि है तो यह उपयोगी है {{math|0}},<ref name=fenwick2014 />क्योंकि यह चेक अंक गणना को सरल बनाता है।
चेक अंक वाले अंक अनुक्रम की वैधता अर्धसमूह पर परिभाषित की जाती है। इस प्रकार उपयोग के लिए तैयार अर्धसमूह तालिका डैम के शोध प्रबंध (पृष्ठ 98, 106, 111) से ली जा सकती है।<ref name="dhmd" /> इस प्रकार यदि प्रत्येक मुख्य विकर्ण प्रविष्टि {{math|0}} है तो यह उपयोगी है ,<ref name=fenwick2014 /> क्योंकि यह चेक अंक गणना को सरल बनाता है।
 
=== शामिल चेक अंक के विरुद्ध किसी संख्या को मान्य करना ===
# एक अंतरिम अंक सेट करें और इसे प्रारंभ करें {{math|0}}.
# संख्या अंक को अंक दर अंक संसाधित करें: संख्या के अंक को स्तंभ सूचकांक के रूप में और अंतरिम अंक को पंक्ति सूचकांक के रूप में उपयोग करें, तालिका प्रविष्टि लें और अंतरिम अंक को इसके साथ बदलें।
# संख्या तभी मान्य है जब परिणामी अंतरिम अंक का मान हो {{math|0}}.<ref name=fenwick2014 />


=== सम्मिलित चेक अंक के विरुद्ध किसी संख्या का सत्यापन करना ===
# एक अंतरिम अंक सेट करें और इसे {{math|0}} से प्रारंभ करें .
# संख्या के अंक को अंक के अनुसार संसाधित करें, संख्या के अंक को स्तंभ सूचकांक के रूप में और अंतरिम अंक को पंक्ति सूचकांक के रूप में उपयोग करें, तालिका प्रविष्टि लें और अंतरिम अंक को इसके साथ बदलें।
# संख्या तभी मान्य है जब परिणामी अंतरिम अंक का मान {{math|0}} हो।<ref name=fenwick2014 /><br />


=== चेक अंक की गणना ===
=== चेक अंक की गणना ===
पूर्वावश्यकता: तालिका की मुख्य विकर्ण प्रविष्टियाँ हैं {{math|0}}.
पूर्वावश्यकता: तालिका की मुख्य विकर्ण प्रविष्टियाँ {{math|0}} हैं .
# एक अंतरिम अंक सेट करें और इसे प्रारंभ करें {{math|0}}.
# एक अंतरिम अंक सेट करें और इसे {{math|0}} से प्रारंभ करें .
#संख्या अंक को अंक दर अंक संसाधित करें: संख्या के अंक को स्तंभ सूचकांक के रूप में और अंतरिम अंक को पंक्ति सूचकांक के रूप में उपयोग करें, तालिका प्रविष्टि लें और अंतरिम अंक को इसके साथ बदलें।
#संख्या अंक को अंक दर अंक संसाधित करें: संख्या के अंक को स्तंभ सूचकांक के रूप में और अंतरिम अंक को पंक्ति सूचकांक के रूप में उपयोग करें, तालिका प्रविष्टि लें और अंतरिम अंक को इसके साथ बदलें।
#परिणामस्वरूप अंतरिम अंक चेक अंक देता है और इसे संख्या के पीछे वाले अंक के रूप में जोड़ा जाएगा।<ref name=fenwick2014 />
#परिणामस्वरूप अंतरिम अंक चेक अंक देता है और इसे संख्या के पीछे वाले अंक के रूप में जोड़ा जाएगा।<ref name=fenwick2014 />
Line 45: Line 39:


== उदाहरण ==
== उदाहरण ==
निम्नलिखित ऑपरेशन तालिका का उपयोग किया जाएगा.<ref name="fenwick2014" />इसे पूरी तरह से एंटी-सिमेट्रिक क्वासिग्रुप से प्राप्त किया जा सकता है {{math|''x'' ∗ ''y''}}डैम के डॉक्टरेट शोध प्रबंध पृष्ठ 111 में<ref name="dhmd" />पंक्तियों को पुनर्व्यवस्थित करके और क्रमपरिवर्तन के साथ प्रविष्टियों को बदलकर {{math|1=''φ'' = (1&nbsp;2&nbsp;9&nbsp;5&nbsp;4&nbsp;8&nbsp;6&nbsp;7&nbsp;3)}} और परिभाषित करना {{math|1=''x'' ⋅ ''y'' = ''φ''<sup>&minus;1</sup>(''φ''(''x'') ∗ ''y'')}}.
निम्नलिखित ऑपरेशन तालिका का उपयोग किया जाएगा।<ref name="fenwick2014" /> इसे डैम के डॉक्टरेट शोध प्रबंध पृष्ठ 111 <ref name="dhmd" /> में पूरी तरह से एंटी-सिमेट्रिक अर्धसमूह {{math|''x'' ∗ ''y''}} से पंक्तियों को पुनर्व्यवस्थित करके और क्रमपरिवर्तन {{math|1=''φ'' = (1&nbsp;2&nbsp;9&nbsp;5&nbsp;4&nbsp;8&nbsp;6&nbsp;7&nbsp;3)}} के साथ प्रविष्टियों को बदलकर और {{math|1=''x'' ⋅ ''y'' = ''φ''<sup>&minus;1</sup>(''φ''(''x'') ∗ ''y'')}} को परिभाषित करके प्राप्त किया जा सकता है।
{| class="wikitable" style="text-align:center;background:none;color:#E000E0"
{| class="wikitable" style="text-align:center;background:none;color:#E000E0"
|- style="color:#00A000"
|- style="color:#00A000"
Line 95: Line 89:
{| class="wikitable" style="text-align:center;background:none;color:#E000E0"
{| class="wikitable" style="text-align:center;background:none;color:#E000E0"
|- style="color:#00A000"
|- style="color:#00A000"
!style="color:black"| <span style="color:#00A000">digit to be processed</span> column index
!style="color:black"| संसाधित होने वाला अंक स्तंभ सूचकांक
|style="width:1.5em"| 5
|style="width:1.5em"| 5
|style="width:1.5em"| 7
|style="width:1.5em"| 7
|style="width:1.5em"| 2
|style="width:1.5em"| 2
|-
|-
!style="color:black"| old <span style="color:#E000E0">interim digit</span> row index
!style="color:black"| पुराना अंतरिम अंक पंक्ति सूचकांक
| '''0'''
| '''0'''
| 9
| 9
| 7
| 7
|-
|-
!style="color:black"| table entry new <span style="color:#E000E0">interim digit</span>
!style="color:black"| तालिका प्रविष्टि नया अंतरिम अंक
| 9
| 9
| 7
| 7
Line 115: Line 109:
{| class="wikitable" style="text-align:center;background:none;color:#E000E0"
{| class="wikitable" style="text-align:center;background:none;color:#E000E0"
|- style="color:#00A000"
|- style="color:#00A000"
!style="color:black"| <span style="color:#00A000">digit to be processed</span> column index
!style="color:black"| संसाधित होने वाला अंक स्तंभ सूचकांक
|style="width:1.5em"| 5
|style="width:1.5em"| 5
|style="width:1.5em"| 7
|style="width:1.5em"| 7
Line 122: Line 116:
|style="width:1.5em"| 4
|style="width:1.5em"| 4
|-
|-
!style="color:black"| old <span style="color:#E000E0">interim digit</span> row index
!style="color:black"| पुराना अंतरिम अंक पंक्ति सूचकांक
| '''0'''
| '''0'''
| 9
| 9
Line 129: Line 123:
| 4
| 4
|-
|-
!style="color:black"| table entry new <span style="color:#E000E0">interim digit</span>
!style="color:black"| तालिका प्रविष्टि नया अंतरिम अंक
| 9
| 9
| 7
| 7
Line 138: Line 132:
परिणामी अंतरिम अंक 0 है, इसलिए संख्या वैध है।
परिणामी अंतरिम अंक 0 है, इसलिए संख्या वैध है।


=== चित्रमय चित्रण ===
=== ग्राफिकल चित्रण ===


यह उपरोक्त उदाहरण है जो चेक अंक (धराशायी नीला तीर) उत्पन्न करने वाले एल्गोरिदम का विवरण दिखाता है और चेक अंक के साथ संख्या 572 को सत्यापित करता है।
यह उपरोक्त उदाहरण है जो चेक अंक (डैश नीला तीर) उत्पन्न करने वाले एल्गोरिदम का विवरण दिखाता है और चेक अंक के साथ संख्या 572 को सत्यापित करता है।


[[File:Check digit TA quasigroup dhmd111rr illustration eg5724.svg]]
[[File:Check digit TA quasigroup dhmd111rr illustration eg5724.svg]]

Revision as of 09:47, 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, yQ के लिए, निम्नलिखित निहितार्थ हैं: [4] (cx) ∗ y = (cy) ∗ xx = y

  1. xy = yxx = y,


और यदि केवल पहला निहितार्थ सही बैठता है तो इसे अशक्त पूर्णतया विरोधी-सममितीय कहा जाता है। डैम ने सिद्ध किया कि ऑर्डर n के एक पूरी तरह से एंटी-सिमेट्रिक अर्धसमूह का अस्तित्व, ऑर्डर n के एक अशक्त पूरी तरह से एंटी-सिमेट्रिक अर्धसमूह के अस्तित्व के सामान है। इस प्रकार चेक समीकरण के साथ डैम एल्गोरिदम के लिए (...((0 ∗ xm) ∗ xm−1) ∗ ...) ∗ x0 = 0, अर्धसमूह xx = 0 के साथ एक अशक्त पूरी तरह से एंटी-सिमेट्रिक अर्धसमूह की आवश्यकता है ऐसे अर्धसमूह का निर्माण स्तंभों को इस तरह से पुनर्व्यवस्थित करके किसी भी पूरी तरह से विरोधी-सममित अर्धसमूह से किया जा सकता है कि सभी शून्य विकर्ण पर होंते है। और दूसरी ओर किसी भी अशक्त पूर्णत: सममित-विरोधी अर्धसमूह से स्तंभों को इस प्रकार पुनर्व्यवस्थित करके एक पूर्णतः-सममित-विरोधी अर्धसमूह का निर्माण किया जा सकता है कि पहली पंक्ति प्राकृतिक क्रम में होते है।[3]

एल्गोरिथम

चेक अंक वाले अंक अनुक्रम की वैधता अर्धसमूह पर परिभाषित की जाती है। इस प्रकार उपयोग के लिए तैयार अर्धसमूह तालिका डैम के शोध प्रबंध (पृष्ठ 98, 106, 111) से ली जा सकती है।[3] इस प्रकार यदि प्रत्येक मुख्य विकर्ण प्रविष्टि 0 है तो यह उपयोगी है ,[1] क्योंकि यह चेक अंक गणना को सरल बनाता है।

सम्मिलित चेक अंक के विरुद्ध किसी संख्या का सत्यापन करना

  1. एक अंतरिम अंक सेट करें और इसे 0 से प्रारंभ करें .
  2. संख्या के अंक को अंक के अनुसार संसाधित करें, संख्या के अंक को स्तंभ सूचकांक के रूप में और अंतरिम अंक को पंक्ति सूचकांक के रूप में उपयोग करें, तालिका प्रविष्टि लें और अंतरिम अंक को इसके साथ बदलें।
  3. संख्या तभी मान्य है जब परिणामी अंतरिम अंक का मान 0 हो।[1]

चेक अंक की गणना

पूर्वावश्यकता: तालिका की मुख्य विकर्ण प्रविष्टियाँ 0 हैं .

  1. एक अंतरिम अंक सेट करें और इसे 0 से प्रारंभ करें .
  2. संख्या अंक को अंक दर अंक संसाधित करें: संख्या के अंक को स्तंभ सूचकांक के रूप में और अंतरिम अंक को पंक्ति सूचकांक के रूप में उपयोग करें, तालिका प्रविष्टि लें और अंतरिम अंक को इसके साथ बदलें।
  3. परिणामस्वरूप अंतरिम अंक चेक अंक देता है और इसे संख्या के पीछे वाले अंक के रूप में जोड़ा जाएगा।[1]


उदाहरण

निम्नलिखित ऑपरेशन तालिका का उपयोग किया जाएगा।[1] इसे डैम के डॉक्टरेट शोध प्रबंध पृष्ठ 111 [3] में पूरी तरह से एंटी-सिमेट्रिक अर्धसमूह xy से पंक्तियों को पुनर्व्यवस्थित करके और क्रमपरिवर्तन φ = (1 2 9 5 4 8 6 7 3) के साथ प्रविष्टियों को बदलकर और xy = φ−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 को सत्यापित करता है।

Check digit TA quasigroup dhmd111rr illustration eg5724.svg

संदर्भ

  1. 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.
  2. 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. 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. 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.
  5. 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. 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.
  2. 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.
  3. 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.


बाहरी संबंध