نمایش مبدأ برای فاصله همینگ

{| align="left"
|-
| [[پرونده:Hamming distance 3 bit binary.svg|بندانگشتی|140px|3-bit binary [[مکعب]] for finding Hamming distance]]
| [[پرونده:Hamming distance 3 bit binary example.svg|بندانگشتی|140px|Two example distances: 100->011 has distance 3 (red path); 010->111 has distance 2 (blue path)]]
|-
|colspan=2 | [[پرونده:Hamming distance 4 bit binary.svg|بندانگشتی|280px|4-bit binary [[تسرکت]] for finding Hamming distance]]
|-
|colspan=2 | [[پرونده:Hamming distance 4 bit binary example.svg|بندانگشتی|280px|Two example distances: 0100->1001 has distance 3 (red path); 0110->1110 has distance 1 (blue path)]]
|}

در [[تئوری اطلاعات]] '''فاصلهٔ همینگ''' برای دو [[رشته]] با طول مساوی، برابر تعداد مکان‌هایی است که سمبل‌های متناظر متفاوت هستند. به عبارت دیگر، کمترین تعداد ''جایگزینی هایی'' است که یک رشته به یک رشته دیگر تغییرپیدا کند، یا تعداد ''خطاهایی'' که یک رشته به رشته دیگر تبدیل گردد.

== مثالها ==
فاصله همینگ بین:
* «'''<span style="color:blue;">t</font>o<span style="color:blue;">n</font>e<span style="color:blue;">d</font>'''»و«'''<span style="color:red;">r</font>o<span style="color:red;">s</font>e<span style="color:red;">s</font>'''»سه هست.
* '''۱۰<span style="color:blue;">۱</font>۱<span style="color:blue;">۱</font>۰۱''' و '''۱۰<span style="color:red;">۰</font>۱<span style="color:red;">۰</font>۰۱''' دو هست.
* '''۲<span style="color:blue;">۱۷</font>۳<span style="color:blue;">۸</font>۹۶''' و '''۲<span style="color:red;">۲۳</font>۳<span style="color:red;">۷</font>۹۶''' سه هست.

== مشخصات ==
برای یک طول ثابت ''n''، فاصله همینگ یک معیاراندازه روی [[فضای برداری]] از کلماتی با آن طول می‌باشد، بطوری‌که دارای شرایط غیر منفی، هویت متقارن و غیرقابل تشخیص تحقق می‌یابد، و آن می‌تواند به خوبی مسئله ارضاء [[نابرابری مثلث]] رابوسیله [[استقراءکامل]] نشان دهد. فاصله همینگ بین دوکلمه a و b می‌تواند همچنین به وسیلهٔ [[وزن هامینگ]] a-b برای یک انتخاب مناسب از عملگر - مشاهده گردد.
برای رشته دودویی a و b فاصله همینگ برابر با تعداد یک‌های a [[یای مانعةالجمع]] b می‌باشد. فضای برداری رشته‌های دودویی با طول n، با فاصله همینگ، به عنوان Hamming cube شناخته می‌شود;که آن معادل با فضای برداری مجموعه فواصل بین برداری در یک [[گراف ابر مکعب]] می‌باشد. می‌توان یک رشته دودویی با طول n را در <math>R^n</math> نشان داد بطوری‌که هر سمبل در رشته به عنوان یک مؤلفه حقیقی رفتار نماید. با این تعبیه، رشته هاراس‌های یک [[ابرمکعب]] n بعدی را شکل می‌دهند، و فاصله همینگ رشته‌ها برابر با فاصله مانهاتان ([[فاصله منهتن]])بین رأس‌ها می‌باشد.

== تاریخچه و کاربردها ==
فاصله هامینگ از نام [[ریچارد همینگ]] گرفته شده‌است. که در مقاله بنیادی اش در مورد [[کد همینگ]] معرفی شد. که در ارتباطات برای شمارش تعدادبیت‌های معکوس دریک کلمه دودویی با طول ثابت جهت تخمین خطارا می‌شمارد وبنابراین اکثر مواقع به آن '''signal distance'''گفته می‌شود. آنالیز [[وزن همینگ]] در چندین جا شامل [[نظریه اطلاعات]]، [[نظریه کدگذاری]] و [[رمزنگاری]] مورد استفاده قرارگرفته‌است. بهر حال برای مقایسه رشته‌های باطول متفاوت یا رشته‌های که شامل حذف یا درج می‌باشند اما شامل جابجایی نمی‌باشند اندازه‌گیری‌های پیچیده تری مانند [[فاصله لون‌اشتاین]] مورد نیاز می‌باشد. برای رشته‌های q تایی روی الفبای ''q''&nbsp;≥&nbsp;۲ فاصله همینگ در حالت ماژولایون متعامد انجام می‌گیرد. درحالی که [[Lee distance]] برای ماژولاسیون فازی صورت می‌گیرد. در حالت q=2,q=۳ دو حالت فاصله فراهم گردیده‌است. فاصله همینگ همچنین در کلاس بندی فاصله ژنتیکی مورد استفاده قرار گرفته‌است. در [[Lee distance]] نقاط یک [[von Neumann neighborhood]] آن نقطه را تشکیل می‌دهند.

== مثال الگوریتم ==
تابع [[پایتون (زبان برنامه‌نویسی)|پایتون]] فاصله همینگ بین دورشته با طول مساوی رامحاسبه می‌کند. با ایجاد یک دنباله از صفر و یک‌ها برابری یا عدم برابری دو رشته را نشان می‌دهیم و سپس دنباله را جمع می‌کنیم.
{{-}}
<syntaxhighlight lang="python">
def hamming_distance(s1, s2):
    assert len(s1) == len(s2)
    return sum(ch1!= ch2 for ch1, ch2 in zip(s1, s2))
</syntaxhighlight>
تابع C زیر فاصله همینگ دو [[عدد صحیح]] را محاسبه می‌کند(شامل مقادیر دودویی به صورت دنباله‌ای از بیت‌ها). زمان اجرای زیر برنامه بر اساس تعدادبیت‌های اعداد ورودی مشخص می‌گردد. آن [[bitwise operation|bitwise]] را برای دو وروی محاسبه می‌کند. و سپس وزن همینگ نتیجه را (تعداد بیت‌های غیر صفر)با استفاده از الگوریتم [[harvtxt۱۹۶۰]] پیدا می‌کند.
<syntaxhighlight lang="c">
unsigned hamdist(unsigned x, unsigned y)
{
  unsigned dist = 0, val = x ^ y;

  // Count the number of set bits
  while(val)
  {
    ++dist;
    val &= val - 1;
 }

  return dist;
}
</syntaxhighlight>

== جستارهای وابسته ==
{{درگاه|ریاضی}}
* [[کد همینگ]]
* [[ریچارد همینگ]]

== منابع ==
{{پانویس}}
* {{FS1037C}}
* {{citation
 | last = Hamming
 | first = Richard W.
 | author-link = Richard W. Hamming
 | id = {{MR|0035935}}
 | issue = 2
 | journal = [[Bell System Technical Journal]]
 | pages = 147–۱۶۰
 | title = Error detecting and [[error correcting code]]s
 | url = http://www.caip.rutgers.edu/~bushnell/dsdwebsite/hamming.pdf
 | volume = 29
 | year = 1950
 | accessdate = ۲۳ ژوئن ۲۰۱۱
 | archiveurl = https://web.archive.org/web/20060525060427/http://www.caip.rutgers.edu/~bushnell/dsdwebsite/hamming.pdf
 | archivedate = ۲۵ مه ۲۰۰۶
 | dead-url = yes
 }}.
* {{citation
 | last1 = Pilcher | first1 = C. D.
 | last2 = Wong | first2 = J. K.
 | last3 = Pillai | 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}}.
* {{citation
 | last = Wegner | 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
 | year = 1960}}.

== پیوند به بیرون ==
* [http://people.revoledu.com/kardi/tutorial/Similarity/HammingDistance.html Example of Hamming distance]
* [http://www.ee.unb.ca/cgi-bin/tervo/hamming.pl?X=+Generate+&L=12&D=4&T=000000000000 Hamming Code Tool] Tool to generate hamming code
* [https://web.archive.org/web/20110807205434/https://bitbucket.org/dignor_sign/set_matcher/overview set_matcher] Tool to match two families of sets from the same base population using Hamming distance.

[[رده:مکعب]]
[[رده:نظریه کدگذاری]]
[[رده:هندسه متریک]]