Хемингово растојање — разлика између измена

| [[Датотека:Hamming distance 3 bit binary.svg|мини|140п|3-битна бинарна [[коцка]] за налажење ХаминговогХеминговог растојања]]

|colspan=2 | [[Датотека:Hamming distance 4 bit binary.svg|мини|280п|4-бинарна [[хиперкоцка]] за налажење ХаминговогХеминговог растојања]]

У [[теорија информације|теорији информација]], '''ХаминговоХемингово растојање''' између две [[ниска|ниске]] (речи) једнаких дужина је једнако броју места на којима се одговарајући симболи тих ниски не поклапају. Другим речима, ХаминговоХемингово растојање представља минималан број ''замена'' које је неопходно спровести да би се једна ниска претворила удругу, или број ''грешака'' које су трансформисале једну ниску у другу.

ХаминговоХемингово растојање између:

За фиксну дужину ''-{n}-'', ХаминговоХемингово растојање је [[метрика (математика)|метрика]] на векторском простору речи те дужине, јер очигледно испуњава својства ненегативности, важи да је -{H(x, y) = 0}- [[ако и само ако|акко]] -{x = y}-, испуњава својство симетрије, и лако се може показати [[потпуна индукција|потпуном индукцијом]] да задовољава и својство [[неједнакост троугла|неједнакости троугла]]. ХаминговоХемингово растојање између речи ''-{a}-'' и ''-{b}-'' може такође да се посматра и као [[ХаминговаХемингова тежина]] за ''-{a''−''b}-'' уз одговарајући избор оператора −.

Кад су у питању '''бинарне ниске''' ''-{a}-'' и ''-{b}-'' ХаминговоХемингово растојање је једнако броју јединица у ''-{a}-'' -{[[Искључива дисјункција|XOR]]}- ''-{b}-''. Метрички простор бинарних ниски дужине ''-{n}-'', са ХаминговимХеминговим растојањем је познат као ''ХаминговаХемингова коцка''; она је као метрички простор еквивалентна скупу чворова у графу у облику хиперкоцке. Бинарне ниске дужине ''-{n}-'' могу да се посматрају и као вектор у <math>R^n</math> где се сваки симбол посматра као реална координата; на овај начин, ниске дају чворове ''-{n}-''-димензионе [[хиперкоцка|хиперкоцке]], а ХаминговоХемингово растојање између две ниске је еквивалентно [[Менхетн растојању]] између чворова.

ХаминговоХемингово растојање је названо по [[Ричард ХамингХеминг|Ричарду ХамингуХемингу]], који га је увео у свом раду о [[ХаминговомХеминговом коду]], ''Кодирања за откривање и корекцију грешака'' из 1950. године.<ref>Hamming, Richard W. (1950), "Error detecting and error correcting codes", Bell System Technical Journal 26 (2): 147–160, MR0035935, http://www.caip.rutgers.edu/~bushnell/dsdwebsite/hamming.pdf .</ref> Користи се у [[телекомуникације|телекомуникацијама]] где број замењених битова у бинарној речи фиксне дужине представља процену грешке, и стога се понекад назива '''сигнално растојање'''. Анализа ХаминговеХемингове тежине се користи у више дисциплина укључујући [[теорија информације|теорију информација]], [[теорија кодирања|теорију кодирања]], и [[криптографија|криптографију]]. Међутим, за упоређивање ниски различитих дужина, или ниски где се не очекују само замене симбола већ и њихово уметање или брисање, од веће користи су софистицираније метрике, попут [[Левенштајново растојање|Левенштајновог растојања]].

За ''-{q}-''-арне ниске над азбуком величине ''-{q}-''&nbsp;≥&nbsp;2 ХаминговоХемингово растојање се примењује у случају ортогоналне [[модулација|модулације]], док се [[Лијево растојање]] користи за фазну модулацију. Ако је -{''q''&nbsp;=&nbsp;2}- или -{''q''&nbsp;=&nbsp;3}- ова два растојања се поклапају.

ХаминговоХемингово растојање се такође користи у систематици, као мера генетског растојања.<ref name="pmid18351799">Pilcher, C. D.; Wong, J. K.; Pillai, S. K. (March 2008), "Inferring HIV transmission dynamics from phylogenetic sequence relationships", PLoS Med. 5 (3): e69, doi:10.1371/journal.pmed.0050069, PMID 18351799.</ref>

[[Пајтон (програмски језик)|Пајтон]] функција <code>hamming_distance()</code> рачуна ХаминговоХемингово растојање између две ниске (или других итерабилних објеката) једнаке дужине, тако што направи низ нула и јединица које означавају поклапања или непоклапања између одговарајућих позиција у две ниске, и затим сабере елементе тог низа.

Следећа [[C (програмски језик)|C]] функција рачуна ХаминговоХемингово растојање два цела броја (посматрана у бинарном облику, то јест као низ битова). Време извршавања ове процедуре је пропорционално ХаминговомХеминговом растојању два броја а не броју битова у улазу. Рачуна се [[битовска операција|битовска]] [[искључива дисјункција|ексклузивна дисјункција]] два задата броја, а затим се налази [[ХаминговаХемингова тежина]] резултата (број битова различитих од нуле) коришћењем алгоритма <ref>Wegner, Peter (1960), "A technique for counting ones in a binary computer", Communications of the ACM 3 (5): 322, doi:10.1145/367236.367286.</ref> који узастопно проналази и брише бит различит од нуле најнижег реда.

* [http://people.revoledu.com/kardi/tutorial/Similarity/HammingDistance.html Пример ХаминговогХеминговог растојања] {{en}}

* [http://www.ee.unb.ca/cgi-bin/tervo/hamming.pl?X=+Generate+&L=12&D=4&T=000000000000 Алат за прављење ХаминговогХеминговог кода] {{en}}