الگوریتم ورهوف

الگوریتم Verhoeff [1] یک جمع کنترلی برای تشخیص خطا است که اولین بار توسط ریاضیدان هلندی Jacobus Verhoeff در سال 1969 منتشر شد . ارقام مجاور، [4] که در آن زمان با چنین کدی غیرممکن به نظر می رسید.

این روش به طور مستقل توسط H. Peter Gumm در سال 1985 کشف شد، این بار شامل یک اثبات رسمی و گسترش برای هر پایه است. [5]

اهداف

هدف ورهوف یافتن یک کد اعشاری بود - کدی که در آن رقم چک یک رقم اعشاری منفرد است - که تمام خطاهای تک رقمی و همه جابجایی ارقام مجاور را شناسایی می کرد. در آن زمان، شواهد فرضی مبنی بر عدم وجود [6] این کدها، کدهای پایه 11 را محبوب کردند، به عنوان مثال در رقم چک ISBN .

اهداف او نیز عملی بود، و او ارزیابی کدهای مختلف را بر اساس داده های زنده از سیستم پستی هلند، با استفاده از یک سیستم امتیاز وزن برای انواع مختلف خطا، استوار کرد. تجزیه و تحلیل خطاها را به چند دسته تقسیم کرد: اول، تعداد ارقام در خطا. برای کسانی که دو رقم اشتباه دارند، جابجایی ( abbaدوقلوها ( aa → 'bb')، جابجایی های پرش ( abccbaآوایی ( 1aa0 )، و دوقلوهای پرش ( abacbc ) وجود دارد. علاوه بر این، ارقام حذف شده و اضافه شده وجود دارد. اگرچه فرکانس برخی از این نوع خطاها ممکن است کوچک باشد، برخی از کدها ممکن است علاوه بر اهداف اولیه شناسایی همه تک‌ها و جابه‌جایی‌ها، از آنها مصون باشند.

خطاهای آوایی به طور خاص اثرات زبانی را نشان دادند، زیرا در هلندی، اعداد معمولاً به صورت جفت خوانده می شوند. و همچنین در حالی که 50 صدایی شبیه به 15 در هلندی دارد، 80 به نظر 18 نمی رسد.

با در نظر گرفتن اعداد شش رقمی به عنوان مثال، ورهوف طبقه بندی زیر را از خطاها گزارش کرد:.

ارقام به اشتباه طبقه بندی شمردن فرکانس
1 رونویسی 9,574 79.05٪
2 جابجایی ها 1,237 10.21٪
دوقلوها 67 0.55٪
آوایی 59 0.49٪
دیگر مجاور 232 1.92٪
جابجایی های پرش 99 0.82٪
پرش دوقلوها 35 0.29٪
سایر خطاهای پرش 43 0.36٪
دیگر 98 0.81٪
3 169 1.40٪
4 118 0.97٪
5 219 1.81٪
6 162 1.34٪
جمع 12,112

شرح

ایده کلی الگوریتم این است که هر یک از ارقام (0 تا 9) را به عنوان عناصر گروه دو وجهی نشان دهد . یعنی ارقام را به نگاشت کنید ، آنها را دستکاری کنید، سپس به ارقام برگردانید. بگذارید این نقشه برداری باشد

رقم n و تعداد ارقام آن باشد .

به عنوان مثال با توجه به کد 248 پس از آن 3 و .

حالا جایگشت را تعریف کنید

مثلا . مثال دیگر از آن زمان است

با استفاده از نماد ضربی برای عملیات گروهی ، رقم چک به سادگی یک مقدار است به طوری که

به صراحت با جایگشت معکوس داده می شود

برای مثال، رقم چک برای 248 5 است. برای تأیید این موضوع، از نگاشت به LHS معادله قبلی استفاده کنید و در آن وارد کنید.

برای ارزیابی سریع این جایگشت از آن استفاده کنید

برای بدست آوردن آن

این همان بازتابی است که به طور مکرر ضرب می شود. استفاده کنید که بازتاب ها معکوس خودشان هستند. [7]

در عمل، الگوریتم با استفاده از جداول جستجوی ساده بدون نیاز به درک نحوه تولید آن جداول از گروه زیربنایی و تئوری جایگشت پیاده‌سازی می‌شود. این به درستی یک خانواده از الگوریتم ها در نظر گرفته می شود، زیرا جایگشت های دیگر نیز کار می کنند. ورهوف خاطرنشان می کند که جایگشت خاص، که در بالا داده شد، خاص است زیرا دارای خاصیت تشخیص 95.3٪ از خطاهای آوایی است. [8]

نقاط قوت الگوریتم این است که تمام خطاهای نویسه‌گردانی و جابه‌جایی، و به‌علاوه بیشتر خطاهای دوقلو، پرش دوقلوی، جابجایی پرش و خطاهای آوایی را تشخیص می‌دهد.

نقطه ضعف اصلی الگوریتم ورهوف پیچیدگی آن است. محاسبات مورد نیاز را نمی توان به راحتی به عنوان یک فرمول بیان کرد . جداول جستجو برای محاسبه آسان مورد نیاز است. کد مشابه الگوریتم Damm است که کیفیت های مشابهی دارد.

الگوریتم مبتنی بر جدول

الگوریتم Verhoeff را می توان با استفاده از سه جدول پیاده سازی کرد: جدول ضرب d ، جدول معکوس inv و جدول جایگشت p .

جدول اول، d ، بر اساس ضرب در گروه دو وجهی D 5 است . [7] و به سادگی جدول Cayley گروه است. توجه داشته باشید که این گروه جابجایی نیست ، یعنی برای برخی از مقادیر j و k ، d ( j ، k ) ≠ d ( k ، j ).

جدول معکوس inv معکوس ضربی یک رقم را نشان می دهد، یعنی مقداری که d ( j , inv ( j )) = 0 را برآورده می کند.

جدول جایگشت p یک جایگشت برای هر رقم بر اساس موقعیت آن در عدد اعمال می کند. این در واقع یک جایگشت واحد است (1 5 8 9 4 2 7 0) (3 6) به صورت تکراری اعمال می شود. یعنی p ( i + j ، n ) = p ( i ، p ( j ، n )).

محاسبه جمع کنترلی Verhoeff به صورت زیر انجام می شود:

  1. یک آرایه n از ارقام مجزای عدد، از راست به چپ گرفته شده ایجاد کنید (راست ترین رقم n 0 و غیره است).
  2. جمع چک c را به صفر مقداردهی کنید.
  3. برای هر شاخص i از آرایه n که از صفر شروع می شود، c را با .

شماره اصلی معتبر است اگر و فقط اگر .

برای ایجاد یک رقم چک، a را اضافه کنید0 ، محاسبه را انجام دهید: رقم بررسی صحیح است .

مثال ها

همچنین ببینید

منابع

  1. ^ Verhoeff, J. (1969). خطا در تشخیص کدهای اعشاری (تراکت 29) . مرکز ریاضی، آمستردام Bibcode :1971ZaMM...51..240N. doi :10.1002/zamm.19710510323.
  2. کرتلند، جوزف (2001). "5. نظریه گروه و طرح ارقام بررسی Verhoeff". شماره های شناسایی و بررسی طرح های رقمی . انجمن ریاضی آمریکا پ. 153. شابک 0-88385-720-0.
  3. سالومون، دیوید (2005). "§2.11 روش رقم بررسی Verhoeff". کد نویسی برای داده ها و ارتباطات کامپیوتری . اسپرینگر. صص 56-58. شابک 0-387-21245-0.
  4. هاونسپرگر، دینا؛ کندی، استفان، ویرایش. (2006). لبه کیهان: جشن ده سال افق ریاضی. انجمن ریاضی آمریکا پ. 38. شابک 978-0-88385-555-3. LCCN  2005937266.
  5. ^ Gumm, H. (ژانويه 1985). "یک کلاس جدید از روش های چک رقمی برای سیستم های اعداد دلخواه (Corresp.)". معاملات IEEE در تئوری اطلاعات . 31 (1): 102-105. doi :10.1109/TIT.1985.1056991.
  6. سیسون، راجر ال. (مه 1958). "بررسی افزونگی اعشاری بهبود یافته". ارتباطات ACM . 1 (5): 10-12. doi : 10.1145/368819.368854 .
  7. ^ ab Gallian، Joseph A. (2010). جبر انتزاعی معاصر (ویرایش هفتم). بروکس/کول. پ. 111. شابک 978-0-547-16509-7. LCCN  2008940386 . بازبینی شده در 26 اوت 2011 . رقم چک ورهوف
  8. ^ Verhoeff 1969, p. 95
  9. ^ Verhoeff 1969, p. 83

لینک های خارجی

  • شرح مفصلی از الگوریتم ورهوف
برگرفته از "https://en.wikipedia.org/w/index.php?title=Verhoeff_algorithm&oldid=1220353290"