הצגת המקור של הדף "מרחק המינג"

[[קובץ:Hamming distance 4 bit binary example.svg|350px|שמאל|ממוזער|לכל שני קודקודים מחוברים בתמונה, מרחק המינג 1. מרחק המינג בין המחרוזת 0100 למחרוזת 1001 הוא 3 (מספר הצלעות במסלול האדום).]]
ב[[תורת האינפורמציה]], '''מרחק הַמינג''' (Hamming) בין שתי [[מחרוזת (תכנות)|מחרוזות]] בעלות אורך זהה, הוא מספר המקומות שבהם סימנים מקבילים בשתי המחרוזות שונים זה מזה. בניסוח אחר, מרחק המינג הוא מספר השינויים המזערי שיש לעשות במחרוזת אחת כדי לקבל את המחרוזת השנייה. כן ניתן לראות את מרחק המינג כאילו נוצר בעת שידור המחרוזת הראשונה, שנקלט כמחרוזת השנייה, כך שמרחק המינג מייצג את מספר השגיאות שנוצרו בתשדורת זו. מחרוזת, לעניין זה, יכולה להיות בכל שיטת קידוד, כגון מחרוזת [[סיבית|סיביות]], מחרוזת [[תו (מחשב)|תווים]] וכדומה.
דוגמאות:
* מרחק המינג בין המחרוזת '''10<span style="color:blue;">1</span>1<span style="color:blue;">1</span>01''' למחרוזת '''10<span style="color:red;">0</span>1<span style="color:red;">0</span>01''' הוא 2.
* מרחק המינג בין המחרוזת '''2<span style="color:blue;">14</span>3<span style="color:blue;">8</span>96''' למחרוזת '''2<span style="color:red;">23</span>3<span style="color:red;">7</span>96''' הוא 3.
* מרחק המינג בין המחרוזת "'''<span style="color:blue;">t</span>o<span style="color:blue;">n</span>e<span style="color:blue;">d</span>'''" למחרוזת "'''<span style="color:red;">r</span>o<span style="color:red;">s</span>e<span style="color:red;">s</span>'''" הוא 3.

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

מרחק המינג קרוי על שמו של [[ריצ'רד המינג]], שהציג רעיון זה במאמרו הבסיסי [http://guest.engelschall.com/~sb/hamming/ error-detecting and error-correcting codes] משנת [[1950]], מאמר שבו הציע את [[קוד המינג]].

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

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

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

== לקריאה נוספת ==
<div class="mw-content-ltr">
*{{cite journal
 |author-last=Hamming |author-first=Richard W. |author-link=ריצ'רד המינג|mr=0035935
 |issue=2
 |journal=[[Bell System Technical Journal]]
 |pages=147–160
 |title=Error detecting and error correcting codes
 |url=http://wayback.archive.org/web/20060525060427/http://www.caip.rutgers.edu/~bushnell/dsdwebsite/hamming.pdf
 |volume=29
 |date=1950
 |doi=10.1002/j.1538-7305.1950.tb00463.x}}
*{{cite journal
 |author-last1=Pilcher |author-first1=C. D.
 |author-last2=Wong |author-first2=J. K.
 |author-last3=Pillai |author-first3=S. K.
 |date=March 2008
 |doi=10.1371/journal.pmed.0050069
 |issue=3
 |journal=PLoS Med.
 |page=e69
 |pmid=18351799
 |title=Inferring HIV transmission dynamics from phylogenetic sequence relationships
 |volume=5
 |pmc=2267810}}
*{{cite journal
 |author-last=Wegner |author-first=Peter |author-link=Peter Wegner
 |doi=10.1145/367236.367286
 |issue=5
 |journal=[[Communications of the ACM]]
 |page=322
 |title=A technique for counting ones in a binary computer
 |volume=3
 |date=1960}}
*{{cite book
 |author-last=Ayala |author-first=Jose
 |journal=Integrated Circuit and System Design
 |page=62
 |title=Fast Propagation of Hamming and Signal Distances for Register-Transfer Level Datapaths
 |volume=1
 |date=2012}}
* {{cite book |author-link=David J. C. MacKay |author-last=MacKay |author-first=David J. C. |url=http://www.inference.phy.cam.ac.uk/mackay/itila/book.html |title=Information Theory, Inference, and Learning Algorithms |location=Cambridge |publisher=[[Cambridge University Press]] |date=2003 |isbn=0-521-64298-1}}
</div>

==קישורים חיצוניים==
* {{MathWorld}}

{{בקרת זהויות}}

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