מרחק המינג

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

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

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

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

מאפיינים

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

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

משקל המינג

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

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

$d_{H}(A,B)=w_{H}(A\oplus B)$

כאשר $d_{H}$ היא מרחק המינג ו־$w_{H}$ היא משקל המינג.

לדוגמה, מרחק המינג בין $A=100101$ ו־$B=110110$ הוא 3:

$d_{H}(100101,110110)=w_{H}(100101\oplus 110110)=w_{H}(010011)=3$

ראו גם

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

לקריאה נוספת

• Hamming, Richard W. (1950). "Error detecting and error correcting codes" (PDF). Bell System Technical Journal. 29 (2): 147–160. doi:10.1002/j.1538-7305.1950.tb00463.x. MR 0035935.
• Pilcher, C. D.; Wong, J. K.; Pillai, S. K. (במרץ 2008). "Inferring HIV transmission dynamics from phylogenetic sequence relationships". PLoS Med. 5 (3): e69. doi:10.1371/journal.pmed.0050069. PMC 2267810. PMID 18351799. {{cite journal}}: (עזרה)
• Wegner, Peter (1960). "A technique for counting ones in a binary computer". Communications of the ACM. 3 (5): 322. doi:10.1145/367236.367286.
• Ayala, Jose (2012). Fast Propagation of Hamming and Signal Distances for Register-Transfer Level Datapaths. Integrated Circuit and System Design. Vol. 1. p. 62.
• MacKay, David J. C. (2003). Information Theory, Inference, and Learning Algorithms. Cambridge: Cambridge University Press. ISBN 0-521-64298-1.

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

• מרחק המינג, באתר MathWorld (באנגלית)