מרחק המינג

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
לכל שני קודקודים סמוכים בתמונה, מרחק המינג 1. מרחק המינג בין המחרוזת 0100 למחרוזת 1001 הוא 3 (מספר הצלעות במסלול האדום).

בתורת האינפורמציה, מרחק המינג בין שתי מחרוזות בעלות אורך זהה, הוא מספר המקומות שבהן סימנים מקבילים בשתי המחרוזות שונים זה מזה. בניסוח אחר, מרחק המינג הוא מספר השינויים המזערי שיש לעשות במחרוזת אחת כדי לקבל את המחרוזת השנייה. כן ניתן לראות את מרחק המינג כאילו נוצר בעת שידור המחרוזת הראשונה, שנקלט כמחרוזת השנייה, כך שמרחק המינג מייצג את מספר השגיאות שנוצרו בתשדורת זו. מחרוזת, לעניין זה, יכולה להיות בכל שיטת קידוד, כגון מחרוזת סיביות, מחרוזת תווים וכדומה. דוגמאות:

  • מרחק המינג בין המחרוזת 1011101 למחרוזת 1001001 הוא 2.
  • מרחק המינג בין המחרוזת 2143896 למחרוזת 2233796 הוא 3.
  • מרחק המינג בין המחרוזת "toned" למחרוזת "roses" הוא 3.

משקל המינג של מחרוזת הוא מרחק המינג שלה ממחרוזת בעלת אותו אורך שכולה אפסים. למעשה זהו מספר הסימנים שאינם אפס. במחרוזת סיביות זהו מספר הסיביות שערכן 1. דוגמה: משקל המינג של המחרוזת 11101 הוא 4.

מרחק המינג קרוי על שמו של ריצ'רד המינג, שהציג רעיון זה במאמרו הבסיסי error-detecting and error-correcting codes משנת 1950, מאמר שבו הציע את קוד המינג.

מאפיינים[עריכת קוד מקור | עריכה]

לאורך קבוע n, מרחק המינג הוא מטריקה מעל קבוצת המילים בנות אורך זה: קל לראות שמתקיימות הדרישות לאי-שליליות, למרחק 0 בין שווים ולסימטריה, ובאמצעות אינדוקציה שלמה ניתן להוכיח שמתקיים אי שוויון המשולש.

את מרחק המינג בין שתי מחרוזות ניתן לראות גם כהפרש ביניהן, על-פי הגדרה נאותה של פעולת החיסור. לשתי מחרוזות בינאריות ההפרש הוא פעולת XOR ביניהן, או חיסור רגיל במרחב הווקטורי \mathbb{Z}_2^n כאשר מזהים את התו 0 עם המספר 0 (מודולו 2) ואת התו 1 עם הספרה 1 (מודולו 2).

ראו גם[עריכת קוד מקור | עריכה]