الگوریتم دم

در تشخیص خطا، الگوریتم دم (به انگلیسی: Damm algorithm) یک الگوریتم چک کردن رقمی (الگوریتم چکسام) است که تمام خطاهای تک رقمی و تمامی خطاهایی که در انتقال از مجاورت ایجاد می‌شوند را شناسایی و پیدا می‌نماید.

این الگوریتم توسط مایکل دم در سال ۲۰۰۴ ارایه گردید.

نقاط قوت و نقاط ضعف الگوریتم دم

نقاط قوت

الگوریتم دم شبیه الگوریتم ورهوف است، همچنین تمامی خطاهای رونویسی شامل تغییر یک رقم و جابه جایی دو رقم مجاور را (انتقال عدد چک و اعداد قبل) را شناسایی می‌کند.

برتری الگوریتم دم نسبت به الگوریتم ورهوف این است که الگوریتم دم بدون جایگشت‌های اختصاص داده شده عمل می‌کند.

علاوه بر این، معکوس جدول را می‌توان با صفر کردن تمام ورودی اصلی مورب جدول ایجاد کرد.

الگوریتم دم در اعداد بزرگتر از ۱۰ هم به درستی کار می‌کند و مشکلی ایجاد نمی‌کند ولی در عوض نیازمند یه کارکتر غیر عددی مانند X است (مثل طرح چک کردن رقم در الگوریتم ISBN 10-digit)

پیش‌بینی صفرهای پیشین روی رقم چک (چکسام) تأثیر نمی‌گذارد.

به‌طور کلی در شبه گروه‌های غیر متقارن تمام خطاهای آوایی مرتبط با زبان انگلیسی (۱۳ , ۳۰) , (۱۴ , ۴۰) , (۱۹ , ۹۰) تشخیص داده می‌شوند، جدول استفاده شده در مثال تصویری نمونه ای از این نوع است.

نقاط ضعف

با وجود خواص مطلوب الگوریتم دم در زمینه‌های متداول، در بیشتر موارد از الگوریتم‌های مشابه استفاده می‌کنند زیرا الگوریتم دم عمدتاً ناشناخته است و به ندرت در عمل کاربرد دارد.

از آنجایی که صفرهای پیشین بر روی رقم چک تأثیر نمی‌گذارند، طول کدها نباید با یکدیگر ادغام گردند. به‌طور مثال ۰٬۰۱ و ۰۰۱ رقم‌های چک یکسانی تولید می‌کنند. اگرچه تمام الگوریتم‌های چک کردن رقم چک با این روش آسیب‌پذیر هستند.

طرح الگوریتم دم

بخش ضروری این الگوریتم داشتن یک جدول مربعی ۱۰ در ۱۰ با ویژگی خاص غیر متقارن بودن ( کاملاً غیر متقارن ضعیف) به عنوان بدنهٔ اصلی عملیات است، آقای دم چندین روش را برای ایجاد جدول‌های کاملاً غیر متقارن در پایان‌نامه دکترای خود ارایه کرد همچنین با این کار خود تمام فرضیات قبلی مبنی بر اینکه جدول‌های کاملاً غیر متقارن از مرتبهٔ ۱۰ وجود ندارند را رد نمود.

یک شبه گروه (Q, ∗) به‌طور کامل غیر متقارن نامیده می‌شود اگر برای هر x , y که متعلق به Q باشند داشته باشیم:

c ∗ x) ∗ y = (c ∗ y) ∗ x ⇒ x = y) x ∗ y = y ∗ x ⇒ x = y

اگر فقط جدول از عمل اولی که در بالا ذکر شد پیروی کند غیر متقارن ضعیف نامیده می‌شود.

آقای دم ثابت کرد که وجود یک شبه گروه کامل غیر متقارن از مرتبهٔ n با وجود یک شبه گروه کامل غیر متقارن ضعیف از مرتبهٔ n برابر است. برای الگوریتم دم با معادله چک $(...((0*xm)*xm-1)*...)*x0=0$ یک شبه گروه کاملاً غیر متقارن ضعیف با ویژگی x ∗ x = ۰ نیاز است.

بدین ترتیب یک شبه گروه را می‌توان از هر شبه گروه کاملاً غیر متقارن بوسیله مرتب‌سازی ستون‌ها به طوری که همه صفرها بر قطر قرار گیرند ساخت و همچنین از سوی دیگر از هر کاملاً غیر متقارن ضعیف می‌توان یک کاملاً غیر متقارن ساخت بدین صورت که ستون‌ها را باید طوری مرتب‌سازی کنیم که سطر اول در نظم طبیعی قرار گیرد.

الگوریتم

اعتبار یک توالی ارقام حاوی یک رقم چک بر یک شبه گروه (جدول ۱۰ * ۱۰) تعریف شده‌است. اگر قطر آن همگی صفر باشند در این صورت این جدول محاسبهٔ چک سام را ساده می‌کند.

معتبر کردن یک عدد با شامل شدن رقم چک

یک رقم موقت در نظر می‌گیریم و آن را با صفر مقداردهی می‌کنیم.

عدد را رقم به رقم پردازش می‌کنیم: رقم عدد را با ستون و رقم موقت را با سطر مطابقت می‌دهیم و عدد مورد نظر را از جدول استخراج می‌کنیم.

رقم موقت را به رقم استخراج شده تغییر می‌دهیم.

عدد اولیه در صورتی معتبر است که آخرین رقم استخراج شده برابر با ۰ باشد.

مراحل بالا را تکرار می‌کنیم.

مثال

از جدول زیر برای مثال استفاده می‌کنیم که یک شبه گروه کاملاً غیر متقارن است.

جدول

۹	۸	۷	۶	۵	۴	۳	۲	۱	۰
۲	۴	۶	۸	۹	۵	۷	۱	۳	۰	۰
۳	۶	۸	۴	۵	۱	۲	۹	۰	۷	۱
۹	۵	۳	۱	۷	۸	۶	۰	۲	۴	۲
۶	۲	۴	۳	۸	۹	۰	۵	۷	۱	۳
۸	۷	۹	۵	۴	۰	۳	۲	۱	۶	۴
۱	۸	۵	۹	۰	۲	۴	۷	۶	۳	۵
۴	۳	۱	۰	۲	۷	۹	۶	۸	۵	۶
۷	۱	۰	۲	۶	۳	۵	۴	۹	۸	۷
۵	۰	۲	۷	۱	۶	۸	۳	۴	۹	۸
۰	۹	۷	۶	۳	۴	۱	۸	۵	۲	۹

از ویژگی‌های جدول این است که تمامی عناصر روی قطر اصلی صفر هستند.

حال فرض کنید عددی که می‌خواهیم آن را معتبر کنیم ۵۷۲ باشد.

محاسبه رقم چک

۲	۷	۵	رقم مورد پردازش قرار گرفته - اندیس ستون
۷	۹	۰	رقم موقت قبلی - اندیس سطر
۴	۷	۹	عنصر بدست آمده از جدول - رقم موقت جدید

آخرین رقم بدست آمده ۴ است پس باید به عدد مورد نظر رقم ۴ را اضافه کنیم تا عدد معتبری بدست آید.

معتبر سازی عدد با حساب رقم چک

۴	۲	۷	۵	رقم مورد پردازش قرار گرفته - اندیس ستون
۴	۷	۹	۰	رقم موقت قبلی - اندیس سطر
۰	۴	۷	۹	عنصر بدست آمده از جدول - رقم موقت جدید

در این حالت نتیجه بدست آمده برابر با صفر می‌باشد پس نتیجه می‌گیریم که عدد ما معتبر شده‌است.

توضیح شکل با استفاده از تصویر

در هر مرحله با استفاده از سطر و ستون رقم موقت بعدی را بدست می‌آوریم.

کد

matrix = (
    (0, 3, 1, 7, 5, 9, 8, 6, 4, 2),
    (7, 0, 9, 2, 1, 5, 4, 8, 6, 3),
    (4, 2, 0, 6, 8, 7, 1, 3, 5, 9),
    (1, 7, 5, 0, 9, 8, 3, 4, 2, 6),
    (6, 1, 2, 3, 0, 4, 5, 9, 7, 8),
    (3, 6, 7, 4, 2, 0, 9, 5, 8, 1),
    (5, 8, 6, 9, 7, 2, 0, 1, 3, 4),
    (8, 9, 4, 5, 3, 6, 2, 0, 1, 7),
    (9, 4, 3, 8, 6, 1, 7, 2, 0, 5),
    (2, 5, 8, 1, 4, 3, 6, 7, 9, 0)
)

def encode(number):
    number = str(number)
    interim = 0

    for digit in number:
        interim = matrix[interim][int(digit)]

    return interim

def check(number):
    return encode(number) == 0

if __name__ == '__main__':
    # quick sanity checking
    assert encode(572) == 4
    assert check(5724)
    assert encode('43881234567') == 9

تایع encode رقم چک را محاسبه می‌کند و تایع check عملیات چک کردن عدد مورد نظر را انجام می‌دهد که آیا عدد معتبر است یا خیر.

این کد به زبان python3 نوشته شده‌است.

جستارهای وابسته

• الگوریتم
• تشخیص و تصحیح خطا
• سرجمع
• بیت توازن
• کد همینگ
• الگوریتم لان