מרחק המינג

בתורת האינפורמציה, מרחק הַמינג () בין שתי מחרוזות בעלות אורך זהה, הוא מספר המקומות שבהם סימנים מקבילים בשתי המחרוזות שונים זה מזה. בניסוח אחר, מרחק המינג הוא מספר השינויים המזערי שיש לעשות במחרוזת אחת כדי לקבל את המחרוזת השנייה. כן ניתן לראות את מרחק המינג כאילו נוצר בעת שידור המחרוזת הראשונה, שנקלט כמחרוזת השנייה, כך שמרחק המינג מייצג את מספר השגיאות שנוצרו בתשדורת זו. מחרוזת, לעניין זה, יכולה להיות בכל שיטת קידוד, כגון מחרוזת סיביות, מחרוזת תווים וכדומה.
דוגמאות:
 מרחק המינג בין המחרוזת 1011101 למחרוזת 1001001 הוא 2.
 מרחק המינג בין המחרוזת 2143896 למחרוזת 2233796 הוא 3.
 מרחק המינג בין המחרוזת "toned" למחרוזת "roses" הוא 3.

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

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

את מרחק המינג בין שתי מחרוזות ניתן לראות גם כהפרש ביניהן, על-פי הגדרה נאותה של פעולת החיסור. לשתי מחרוזות בינאריות ההפרש הוא מספר הביטים הדלוקים בתוצאה של פעולת XOR ביניהן, או מספר הביטים הדלוקים לאחר חיסור רגיל במרחב הווקטורי  כאשר מזהים את התו 0 עם המספר 0 (מודולו 2) ואת התו 1 עם הספרה 1 (מודולו 2).

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

מרחק המינג בין שתי מילים בינאריות A ו־B ניתן על ידי משקל המינג של תוצאת הפעלת XOR על שתי המילים:

כאשר  היא מרחק המינג ו־ היא משקל המינג.

לדוגמה, מרחק המינג בין  ו־ הוא 3:

ראו גם
 סאונדקס
 מרחק לוינשטיין

 לקריאה נוספת 


קישורים חיצוניים


הערות שוליים

קטגוריה:תורת הקודים