الگوریتم دام

از ویکیپدیا، دانشنامه آزاد
پرش به ناوبری پرش به جستجو

در تشخیص خطا ، الگوریتم Damm یک الگوریتم رقم چک است که تمام خطاهای تک رقمی و تمام خطاهای جابجایی مجاور را شناسایی می کند. این توسط اچ. مایکل دام در سال 2004 ارائه شد. [1]

نقاط قوت و ضعف

نقاط قوت

الگوریتم Damm شبیه الگوریتم Verhoeff است . همچنین تمام رخدادهای دو نوع خطای رونویسی که اغلب ظاهر می شوند ، یعنی تغییر یک رقم تک رقمی، و جابجایی دو رقم مجاور (از جمله جابجایی رقم چک عقب و رقم قبل) را شناسایی می کند. [1] [2] اما الگوریتم Damm این مزیت را دارد که بدون اینکه جایگشت‌های اختصاصی ساخته شده و قدرت‌های خاص موقعیت آن در طرح Verhoeff ذاتی باشد عمل می‌کند. علاوه بر این، می توان از جدول معکوس ها صرف نظر کرد، مشروط بر اینکه تمام ورودی های مورب اصلی جدول عملیات صفر باشند.

الگوریتم Damm از تجاوز از تعداد 10 مقدار ممکن رنج نمی برد و در نتیجه نیاز به استفاده از یک کاراکتر غیر رقمی (به عنوان X در طرح رقم 10 رقمی ISBN ).

پیش‌فرض کردن صفرهای ابتدایی روی رقم چک تأثیری نمی‌گذارد (یک ضعف برای کدهای با طول متغیر). [1]

شبه گروه های کاملاً ضد متقارن وجود دارند که تمام خطاهای آوایی مرتبط با زبان انگلیسی را شناسایی می کنند (13 ↔ 30، 14 ↔ 40، ...، 19 ↔ 90). جدول مورد استفاده در مثال مصور مبتنی بر نمونه ای از این نوع است.

نقاط ضعف

برای همه الگوریتم‌های جمع کنترلی از جمله الگوریتم Damm، صفرهای پیش‌فرض روی رقم چک تأثیری نمی‌گذارد، [1] بنابراین 1، 01، 001 و غیره همان رقم چک را تولید می‌کنند. در نتیجه کدهای با طول متغیر نباید با هم تأیید شوند.

طراحی

بخش اساسی آن یک شبه گروه از مرتبه 10 است (یعنی دارای مربع لاتین 10 × 10 به عنوان بدنه جدول عملیاتی آن ) با ویژگی خاص ضعیف بودن کاملاً ضد متقارن بودن . [3] [4] [i] [ii] [iii] دام روش‌های مختلفی را برای ایجاد شبه‌گروه‌های کاملاً ضد متقارن از مرتبه 10 نشان داد و نمونه‌هایی را در پایان‌نامه دکترای خود بیان کرد. [3] [i] با این کار، دام همچنین یک حدس قدیمی را رد کرد که شبه گروه های کاملاً ضد متقارن مرتبه 10 وجود ندارند. [5]

یک شبه گروه ( Q , ∗) کاملاً ضد متقارن نامیده می شود اگر برای همه c , x , yQ , مفاهیم زیر برقرار باشد: [4]

  1. ( cx ) ∗ y = ( cy ) ∗ xx = y
  2. xy = yxx = y ،

و اگر فقط دلالت اول برقرار باشد به آن ضعیف کاملاً ضد متقارن می گویند. دام ثابت کرد که وجود یک شبه گروه کاملاً ضد متقارن از مرتبه n معادل وجود یک شبه گروه کاملاً ضد متقارن ضعیف از مرتبه n است. برای الگوریتم دام با معادله بررسی (...((0 ∗ x m ) ∗ x m −1 ) ∗ ...) ∗ x 0 = 0 یک شبه گروه ضعیف کاملاً ضد متقارن با ویژگی xx = 0 لازم است. چنین شبه گروهی را می توان از هر شبه گروه کاملاً ضد متقارن ساخت، با چیدمان مجدد ستون ها به گونه ای که همه صفرها روی مورب قرار گیرند. و از سوی دیگر، از هر شبه گروه ضعیف کاملاً ضد متقارن، می توان با چیدمان مجدد ستون ها به گونه ای که ردیف اول به ترتیب طبیعی باشد، یک شبه گروه کاملاً ضد متقارن ساخت. [3]

الگوریتم

اعتبار یک دنباله رقمی حاوی یک رقم چک بر روی یک شبه گروه تعریف می شود. یک جدول شبه گروهی آماده برای استفاده را می توان از پایان نامه دام (صفحات 98، 106، 111) گرفت. [3] اگر هر ورودی مورب اصلی 0 باشد مفید است، [1] زیرا محاسبه رقم چک را ساده می کند.

اعتبارسنجی یک عدد در برابر رقم چک موجود

  1. یک رقم موقت تنظیم کنید و آن را به 0 مقداردهی کنید.
  2. پردازش رقم به رقم: از رقم عدد به عنوان نمایه ستون و رقم میانی به عنوان نمایه ردیف استفاده کنید، ورودی جدول را بردارید و رقم میانی را با آن جایگزین کنید.
  3. این عدد در صورتی معتبر است که رقم میانی حاصل مقدار 0 باشد . [1]

محاسبه رقم چک

پیش نیاز: ورودی های مورب اصلی جدول 0 است.

  1. یک رقم موقت تنظیم کنید و آن را به 0 مقداردهی کنید.
  2. پردازش رقم به رقم: از رقم عدد به عنوان نمایه ستون و رقم میانی به عنوان نمایه ردیف استفاده کنید، ورودی جدول را بردارید و رقم میانی را با آن جایگزین کنید.
  3. رقم میانی حاصل، رقم چک را می دهد و به عنوان رقم انتهایی به عدد اضافه می شود. [1]

مثال

جدول عملیات زیر استفاده خواهد شد. [1] ممکن است از شبه گروه کاملاً ضد متقارن xy در پایان نامه دکتری دام صفحه 111 [3] با ترتیب مجدد ردیف ها و تغییر مدخل ها با جایگشت φ = (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 را با رقم چک تأیید می کند.

بررسی رقمی TA quasigroup dhmd111rr illustration eg5724.svg

منابع

  1. ^ a b c d e f g h فنویک، پیتر (2014). "مجموعه های بازرسی و کنترل خطا". در فنویک، پیتر (ویرایش). مقدمه ای بر نمایش داده های کامپیوتری . انتشارات علوم بنتام صص  191-218 . doi : 10.2174/9781608058822114010013 . شابک 978-1-60805-883-9.
  2. ^ برای انواع خطاهای رایج و فراوانی آنها، Salomon, David (2005) را ببینید. کد نویسی برای داده ها و ارتباطات کامپیوتری . Springer Science+Business Media, Inc. p. 36. شابک 978-0387-21245-6.
  3. ^ a b c d e Damm, H. Michael (2004). Total antisymmetrische Quasigruppen (PDF) (Dr. rr. nat.) (به آلمانی). فیلیپس-دانشگاه ماربورگ urn:nbn:de:hebis:04-z2004-05162 .
  4. ^ a b Damm, H. Michael (2007). "شبه گروه های کاملاً ضد متقارن برای همه سفارشات n ≠2،6" . ریاضیات گسسته . 307 (6): 715-729. doi : 10.1016/j.disc.2006.05.033 . ISSN 0012-365X . 
  5. دام، اچ. مایکل (2003). "درباره وجود شبه گروه های کاملاً ضد متقارن از مرتبه 4 k  + 2". محاسبات . 70 (4): 349-357. doi : 10.1007/s00607-003-0017-3 . ISSN 0010-485X . S2CID 31659430 .  
  1. ^ a b Beliavscaia، Galina; ایزباش، ولادیمیر؛ شسرباکوف، ویکتور (2003). "سیستم های کاراکتر را بر روی شبه گروه ها و حلقه ها بررسی کنید" (PDF) . شبه گروه ها و سیستم های مرتبط . 10 (1): 1-28. ISSN 1561-2848 .  صفحه 23 را ببینید.
  2. چن جیانان (2009). "NP-کاملیت تکمیل مربع های لاتین ضد متقارن جزئی" (PDF) . مجموعه مقالات کارگاه بین المللی امنیت اطلاعات و کاربرد 2009 (IWISA 2009) . ناشر آکادمی. صص  322-324 . شابک  978-952-5726-06-0.صفحه 324 را ببینید.
  3. ^ میلوا، ا. دیمیتروا، وی (2009). "شبه گروه های ساخته شده از نگاشت کامل یک گروه (Z 2 n ,⊕)" (PDF) . مشارکت ها، بخش. ریاضی. فنی Sci., MANU/MASA . XXX (1–2): 75–93. ISSN 0351-3246 .  صفحه 78 را ببینید.

پیوندهای خارجی