Mbi grupin e fjalëve binare të gjatësisë m largësia d(a,b) ndërmjet fjalëve a dhe b është numri i pozicioneve që nuk përputhen me këto fjalë, për shembull: distanca midis fjalëve a = 01101 dhe b = 00111 është 2.

Koncepti i përcaktuar në këtë mënyrë quhet distanca Hamming.

Ai plotëson aksiomat e mëposhtme të distancës:

1) d(a,b)  0 dhe d(a,b)=0 nëse dhe vetëm nëse a = b;

2) d(a, b) = d(b, a);

3) d(a,b) + d(b,c)  d(a,c) (pabarazi trekëndëshi).

Pesha w(a) e fjalës a është numri i njësive midis koordinatave të saj. Atëherë distanca ndërmjet fjalëve a dhe b është pesha e shumës së tyre a b: d(a,b)=w(a b) , ku simboli  tregon veprimin e modulit 2 të mbledhjes së koordinatave. për zbulimin dhe korrigjimin e gabimeve, aq më shumë ndryshojnë fjalët e koduara. Koncepti i distancës Hamming na lejon ta sqarojmë këtë.

Teorema Në mënyrë që kodi të zbulojë gabime në k (ose më pak) pozicione, është e nevojshme dhe e mjaftueshme që distanca më e vogël ndërmjet fjalëve të kodit të jetë  k + 1.

Vërtetimi i kësaj teoreme është i ngjashëm me vërtetimin e pohimit të mëposhtëm.

Teorema. Në mënyrë që kodi të korrigjojë të gjitha gabimet në k (ose më pak) pozicione, është e nevojshme dhe e mjaftueshme që distanca më e vogël ndërmjet fjalëve të kodit të jetë  2k + 1.

32. Teorema mbi aftësinë korrigjuese të kodeve.

Kodet në të cilat është i mundur korrigjimi automatik i gabimit quhen vetë-korrigjues. Për të ndërtuar një kod vetë-korrigjues të krijuar për të korrigjuar gabimet e vetme, një shifër kontrolli nuk mjafton. Siç shihet nga sa vijon, numri i biteve të kontrollit k duhet të zgjidhet në mënyrë që të plotësohet pabarazia 2k≥k+m+1 ose k≥log2(k+m+1), ku m është numri i biteve bazë. të fjalës kodike. Aktualisht, kodet e korrigjimit të bllokut binar janë me interesin më të madh. Kur përdorni kode të tilla, informacioni transmetohet në formën e blloqeve me të njëjtën gjatësi, dhe secili bllok kodohet dhe deshifrohet në mënyrë të pavarur nga njëri-tjetri. Pothuajse në të gjitha kodet e bllokut, simbolet mund të ndahen në informative dhe kontrolluese.

Karakteristikat kryesore të kodeve vetë-korrigjuese janë:

1. Numri i kombinimeve të lejuara dhe të ndaluara. Nëse n është numri i simboleve në bllok, r është numri i simboleve të kontrollit në bllok, k është numri i simboleve të informacionit, atëherë 2n është numri i kombinimeve të mundshme të kodeve, 2k është numri i kombinimeve të kodeve të lejuara, 2n −2k është numri i kombinimeve të ndaluara.

2. Teprica e kodit. Vlera e rn quhet tepricë e kodit të korrigjimit.

3. Distanca minimale e kodit. Distanca minimale e kodit d është numri minimal i simboleve të shtrembëruara që kërkohen për kalimin nga një kombinim i lejuar në tjetrin.

4. Numri i gabimeve të zbuluara dhe të korrigjuara. Nëse g është numri i gabimeve që kodi mund të rregullojë, atëherë është e nevojshme dhe e mjaftueshme që d≥2g+1

5. Mundësitë korrigjuese të kodeve.

33. Kodimi matricor. kodet e grupit.

Kur specifikoni në mënyrë eksplicite një skemë kodimi në ( m, n)-kodi duhet të specifikojë 2 m fjalë kodi, gjë që është shumë joefikase.

Një mënyrë ekonomike për të përshkruar një skemë kodimi është teknika e kodimit të matricës.

Më parë, çdo skemë kodimi përshkruhej nga tabela që specifikonin një fjalë kodi me gjatësi n për çdo fjalë origjinale të gjatësisë m. Për blloqe me gjatësi të madhe, kjo metodë kërkon një sasi të madhe memorie dhe për këtë arsye është jopraktike. Për shembull, për ( 16, 33 )-kodi do të kërkojë 33 * 2 16 = 2 162 688 bit.

Kërkohet shumë më pak memorie kodimi i matricës. Le E matrica e dimensioneve m × n, i përbërë nga elementet e ij , ku i është numri i linjës, dhe j - numri i kolonës. Çdo element i matricës e ij mund të jetë ose 0 ose 1. Kodimi zbatohet nga operacioni b = aE ose ku fjalët e koduara trajtohen si vektorë, pra si matrica rreshtash të madhësisë 1 × n.

Kodimi nuk duhet të caktojë të njëjtën fjalë kode për mesazhe të ndryshme origjinale. Një mënyrë e lehtë për ta arritur këtë është që m kolonat e matricës formojnë një matricë identiteti. Kur shumëzoni çdo vektor me matricën e identitetit, fitohet i njëjti vektor, prandaj, vektorë të ndryshëm të kodit sistematik do t'i korrespondojnë vektorëve të ndryshëm të mesazheve.

Quhen gjithashtu kodet e matricës kodet e linjave. Për lineare (n − r, n)-kodet me distancë minimale Hamming d ekziston Kufiri i poshtëm i Plotkinit (Plotkin) për numrin minimal të shifrave kontrolluese r në n³ 2d − 1,

Binar ( Një kod m, n) quhet kod grupi nëse fjalët e kodit të tij formojnë një grup.

Vini re se bashkësia e të gjitha fjalëve binare me gjatësi m formon një grup komutativ me veprimin e modulit të mbledhjes koordinative 2, në të cilin vlen relacioni a a. Prandaj, bashkësia e fjalë-mesazheve a me gjatësi m është një grup komutativ.

Kodi i bllokut quhet grup, nëse fjalët e kodit të tij formojnë një grup.

Nëse kodi është një kod grupi, atëherë distanca më e vogël midis dy fjalëve kodike është e barabartë me peshën më të vogël të një fjale jozero.

Kjo rrjedh nga raporti d(b i , b j ) = w(b i + b j ).

Kur përdorni një kod grupi, ato dhe vetëm ato gabime që korrespondojnë me vargjet e gabimeve që janë saktësisht të barabarta me fjalët e kodit mbeten pa u vënë re.

Vargje të tilla gabimi përkthejnë një fjalë kodi në një tjetër.

Prandaj, probabiliteti që një gabim të mbetet i pazbuluar është i barabartë me shumën e probabiliteteve të të gjitha rreshtave të gabimit të barabartë me fjalët e koduara.

Bashkësia e të gjitha fjalëve binare a = a 1 ...a m gjatësia m formon një grup abelian (komutativ) në lidhje me mbledhjen bit.

Le E - kodimi m × nështë një matricë që ka m × m- një nënmatricë me një përcaktues jo zero, për shembull, identiteti. Pastaj hartëzimi a → aE përkthen grupin e të gjitha fjalëve binare me gjatësi m në një grup fjalësh kodike me gjatësi n.

Supozoni se Pastaj për ne marrim

dmth. Prandaj, një hartë një-për-një e një grupi fjalësh binare me gjatësi m duke përdorur një matricë të caktuar E ruan vetitë e operacionit të grupit, që do të thotë se fjalët e koduara formojnë një grup.

Vetia e kodit të grupit: distanca minimale e kodit ndërmjet vektorëve të kodit është e barabartë me peshën minimale të vektorëve jozero. Pesha e vektorit të kodit është e barabartë me numrin e 1 në fjalën e koduar.

Kodet e grupit specifikohen me lehtësi duke përdorur matrica, dimensioni i të cilave përcaktohet nga parametrat k dhe n. Numri i rreshtave është k dhe numri i kolonave është n = k+m.

Kodet e krijuara nga këto matrica quhen (n, k)-kode, dhe matricat përkatëse quhen gjeneruese (gjeneruese, gjeneruese).

Distanca e Hamingut

Matematikani amerikan Hamming hetoi se nga varet kodi i dhënë, nëse ai do të zbulojë gabime dhe kur mund t'i korrigjojë ato. Është intuitivisht e qartë se kjo varet nga mënyra se si fjalët e kodit janë të ndara dhe sa gabime mund të shfaqen në fjalën e transmetuar. Tani po zyrtarizojmë idenë e mëposhtme. Gjatë kodimit, është e nevojshme të koordinoni numrin e gabimeve të mundshme në fjalën e transmetuar, në mënyrë që kur fjala kodike e transmetuar të ndryshojë, të mbetet më afër fjalës së kodit origjinal sesa me çdo fjalë kodi tjetër.

Përkufizimi 13.1. Merrni parasysh grupin e të gjitha fjalëve binare në alfabet AT= (0,1) gjatësi t distancë d(x, në), që është e barabartë me numrin e pozicioneve që nuk përputhen me këto fjalë. Për shembull, për fjalët X = 011101, në= 101010 distanca është d(x, y) = 5. Kjo distancë quhet Distanca e Hamingut .

Mund të tregohet se distanca Hamming plotëson aksiomat e një hapësire metrike:

1) d(x, në) ≥ 0, d(x, në) = 0 nëse dhe vetëm nëse X = y;

2) d(x, y) = d(y, x);

3) d(x, në) ≤ d(x, z) +d(z, në) është pabarazia e trekëndëshit.

Teorema 13.1(në lidhje me kodin e zbulimit). Kodi është detektiv në rastin kur fjala e transmetuar nuk përmban më shumë se k

d(b 1, b 2) ≥ k+ 1.

Teorema 13.2(në lidhje me kodin e rregullimit.). Kodi korrigjon të gjitha gabimet në rastin kur fjala e transmetuar nuk përmban më shumë se k gabimet nëse dhe vetëm nëse distanca më e vogël ndërmjet fjalëve të kodit

d(b 1, b 2) ≥ 2k+ 1.

Dëshmi. Vërtetimet e këtyre teoremave janë të ngjashme. Prandaj, vërtetojmë vetëm teoremën e fundit.

Përshtatshmëria. Le për çdo fjalë kodi që kemi d(b 1, b 2) ≥ 2k+ 1. Nëse gjatë transmetimit të një fjale kodi b 1 nuk ndodhi më k gabime, atëherë për fjalën e marrë me kemi d(b 1, c) ≤ k. Por nga pabarazia e trekëndëshit për çdo fjalë kodi tjetër b 2 kemi d(b 1, Me) + d(c, b 2) ≥ d(b 1, b 2) ≥ 2 k+ 1. Prandaj, nga fjala e marrë në çdo fjalë kodi tjetër, distanca d(c, b 2) ≥ k + 1, pra më shumë se më parë b 1. Prandaj, sipas fjalës së pranuar Me ju mund të gjeni pa mëdyshje fjalën e kodit më të afërt b 1 dhe më pas deshifroni atë.

Nevoja. Nga e kundërta. Supozoni se distanca minimale midis fjalëve të kodit është më e vogël se 2 k+ 1. Pastaj ka dy fjalë kodike, distanca ndërmjet të cilave do të jetë d(b 1, b 2) ≤ 2 k. Lëreni kur transmetoni një fjalë b 1 fjalë e pranuar Me ndodhet mes fjalëve b 1, b 2 dhe ka saktësisht k gabimet. Pastaj d(c, b 1) = k, d (c, b 2) = d(b 1, b 2) – d(c, b 1) ≤ k. Kështu, nga fjala c, është e pamundur të rivendosni në mënyrë unike fjalën e kodit që u transmetua, b 1 ose b 2. Erdhi në një kontradiktë.

Shembulli 13.3 . Merrni parasysh kodet e mëposhtme pesë-bitësh të fjalëve me gjatësi 2 në alfabet AT = {0,1}:

b 1= K(00) = 00000, b 2= K(01) = 01011,

b 3= K(10) = 10101, b 4= k(11) =11110.

Distanca minimale ndërmjet fjalëve të ndryshme kodike është d(bi, bj) = 3. Në bazë të teoremës së parë mbi kodin zbulues, ky kod është i aftë të zbulojë jo më shumë se dy gabime në një fjalë. Në bazë të teoremës së dytë, kodi është në gjendje të korrigjojë jo më shumë se një gabim për fjalë.

Kodet e grupit

Le të hedhim një vështrim më të afërt në kodet e fjalëve në alfabet AT= (0, 1). Nëse për fjalë të gjata t përdoren fjalë kodike me gjatësi n, atëherë kodet e tilla do të thirren ( t , P)-kodet. Gjatësia totale e fjalëve mështë e barabartë me 2 m. për të vendosur ( t , P)-code, mund të numërohen fjalë kodike për të gjitha fjalët e mundshme me gjatësi m, si në shembullin e mëparshëm. Një mënyrë më ekonomike për të specifikuar fjalët e kodit është caktimi i matricës.

Në këtë rast, jepet matrica gjeneruese G= ∣∣ gij∣∣ porosit t × P prej 0 dhe 1. Fjalët kodike përcaktohen çdo herë nga një fjalë a = a 1a 2... në duke e shumëzuar këtë fjalë në të majtë, si vektor, me matricën gjeneruese

Këtu, shtimi është përcaktuar moduli 2. Në mënyrë që fjalë të ndryshme të korrespondojnë me fjalë të ndryshme kodi, mjafton të kemi në matricë G njësi bazë e vogël e porosisë t, për shembull ekstremi i majtë.

Shembulli 13.4 . Merrni parasysh matricën gjeneruese

Kjo matricë përcakton një kod (3, 4). Në këtë rast, tre karakteret e para në fjalën e kodit janë informuese, dhe i katërti është një karakter kontrolli. Është 0 nëse ka një numër çift të 1-ve në fjalën origjinale, dhe 1 nëse ka një numër tek 1-sh. Për shembull, për fjalën a= 101 kodi do të jetë b= aG= 1010. Distanca minimale Hamming ndërmjet fjalëve të kodit është d(bi, bj) = 2. Prandaj, ky është një kod që zbulon një gabim të vetëm.

Përkufizimi 13.2. Kodi quhet grup nëse bashkësia e të gjitha fjalëve kodike formon një grup. Numri i njësive në fjalën a quhet peshore fjalë dhe shënohen me If b- fjala kod dhe fjala e marrë në kanalin e komunikimit Me = b + e, pastaj fjala e thirrur vektori i gabimit .

Teorema 13.3. Le të ketë një grup ( t , P)-Kodi. Pastaj grupi komutativ te i të gjitha fjalëve të kodit është një nëngrup i grupit komutativ NGA të gjitha fjalët e gjata P që mund të merren në kanalin e komunikimit. Distanca më e vogël ndërmjet fjalëve të koduara është e barabartë me peshën më të vogël të një fjale kodike jo zero dhe

Merrni parasysh grupin e faktorëve C/K. Klasat e vazhdueshme këtu do të përcaktohen me ndërrim e + b, b∈ K.

Si përfaqësues i kosetit, ne zgjedhim elementin me peshën më të vogël. Ne do t'i quajmë elementë të tillë drejtuesit e klasave fqinje .

Nëse liderët interpretohen si vektorë gabimi, atëherë çdo koset është një grup fjalësh të shtrembëruara në kanalin e komunikimit me një vektor gabimi fiks, në veçanti, kur e= 0 kemi një grup fjalësh pa shtrembërim, d.m.th., grupin e të gjitha fjalëve të kodit. Procesi i korrigjimit dhe dekodimit të fjalëve Meështë gjetja e kosetit të cilit i përket fjala Me = e + b. Vektor i defekteve e përcakton numrin dhe lokalizimin e gabimeve, fjalën e kodit b përcakton korrigjimin e fjalës së marrë.

Për të lehtësuar kërkimin për një koset dhe për rrjedhojë një vektor gabimi, Hamming propozoi përdorimin e kodeve grupore me matrica të veçanta gjeneratorësh.

Kodet Hamming

Merrni parasysh ndërtimin e hamming ( t , P)-kodi me peshën më të vogël të kodit të barabartë me 3, d.m.th., një kod që korrigjon një gabim.

Le të vendosim P = 2 r– 1 dhe le të ketë çdo fjalë kodi r personazhet e kontrollit dhe t personazhet ( t = P – r= 2 r– 1– r) - informative, r≥ 2, për shembull (1, 3)-code, (4, 7)-code, etj. Për më tepër, në çdo fjalë kodi b= b 1b 2... b fq simbolet me indekse të barabartë me fuqinë 2 do të jenë kontrolli, dhe pjesa tjetër do të jetë informative. Për shembull, për kodin (4, 7) në fjalën e kodit b= b 1b 2b 3b 4b 5b 6b 7 simbole b 1b 2b 4 do të jetë kontrolli, dhe personazhet b 3b 5b 6b 7- informative. Për të përcaktuar një matricë gjeneratori G proshutë ( t , P)-code, konsideroni matricën ndihmëse M urdhëroj r× P, ku P = 2 r– 1, e tillë që në secilën j kolona e matricës M do të ketë simbole të zgjerimit binar të numrit j, për shembull, për një kod (4, 7), matrica M do të jetë 3×7:

Ne përcaktojmë grupin e të gjitha fjalëve të kodit si bashkësinë e zgjidhjeve të një sistemi homogjen të ekuacioneve algjebrike lineare të formës

b MT= 0.

Për shembull, për kodin (4, 7), një sistem i tillë do të ishte:

Le të zgjedhim minorin bazë natyror të sistemit b MT= 0, duke qëndruar në kolona me numra të barabartë me fuqinë e 2. Kështu, ne i ndajmë variablat në bazë (kodi) dhe të lirë (informacion). Tani, pasi të keni vendosur variabla të lirë, është e lehtë të merren ato bazë. Le të gjejmë sistemin themelor m= P – r zgjidhjet e këtij sistemi homogjen. Atëherë çdo zgjidhje e sistemit është një kombinim linear i këtyre m Zgjidhjet. Prandaj, duke shkruar rresht pas rreshti m zgjidhjet e sistemit themelor në formën e një matrice G madhësia m× P, marrim matricën gjeneruese të grupit Hamming ( t , P)-kodi, për shembull, për kodin (4, 7), sistemi themelor i zgjidhjeve do të jetë 4 = 7 - 3 zgjidhjet e mëposhtme të sistemit homogjen:

g 1= 1110000, g 2= 1001100, g 3= 0101010, g 4= 1101001.

Çdo kombinim linear i këtyre zgjidhjeve do të jetë një zgjidhje, pra një fjalë kodi. Nga këto zgjidhje themelore, ne krijojmë një matricë gjeneruese

Tani për çdo fjalë a gjatësia t= 4 e lehtë për të llogaritur fjalën e kodit b gjatësia P= 7 duke përdorur matricën gjeneruese b= aG. Në të njëjtën kohë, simbolet b 3, b 5, b 6, b 7 do të jetë informative. Ato përputhen me a 1, a 1, a 3, a 4.Simbolet b 1, b 2, b 4 do të jenë kontrollet.

konkluzioni. Kodet Hamming janë të përshtatshëm sepse klasat e afërsisë përcaktohen lehtësisht gjatë dekodimit. Fjala e marrë në kanalin e komunikimit le të jetë Me = e + b, ku e- gabim, b- fjalen e koduar. Pastaj e shumëzojmë me matricën ndihmëse SMT= (e + b)MT= em T. Nese nje em T= 0, pastaj fjala Me- kodoni dhe merrni parasysh: nuk ka asnjë gabim. Nese nje em T≠ 0, pastaj fjala e përcakton një gabim.

Kujtojmë se Hammings të ndërtuar ( t , P)-code përcakton një gabim. Prandaj, vektori i gabimit e përmban një njësi i pozicionet. Dhe numri i Si rezultat, pozicioni fitohet në paraqitjen binar em T, që përkon me i kolona e matricës M. Mbetet për të ndryshuar simbolin i në fjalën c të marrë në kanal, fshini karakteret e kontrollit dhe shkruani fjalën e deshifruar.

Për shembull, le të jetë fjala e pranuar Me= 1100011 për kodin Hamming (4, 7). Shumëzojeni këtë fjalë me matricën M T. Marr

(1100011)M T=(010).

Prandaj, ka një gabim në karakterin e dytë. Pra, fjala kod do të jetë b= 1000011. Kryqëzoni karakteret e kontrollit b 1, b 2, b 4. Fjala e deshifruar do të jetë a = 0011.

Sigurisht, nëse gabimi është bërë në më shumë se një karakter, atëherë ky kod nuk do ta rregullojë atë.

) në hapësirën vektoriale të sekuencave të kodit, në këtë rast, distanca Hamming midis dy sekuencave binare (vektorëve) dhe gjatësisë është numri i pozicioneve në të cilat ato janë të ndryshme - në këtë formulim, distanca Hamming u përfshi në Fjalorin e Algoritmeve. dhe Strukturat e të Dhënave të Institutit Kombëtar të Standardeve të Shteteve të Bashkuara (Eng. NIST Fjalori i Algoritmeve dhe Strukturave të të Dhënave ).

Kështu, distanca Hamming midis vektorëve 0 011 1 dhe 1 010 1 është e barabartë me 2 (bitë të ndryshëm janë shënuar me të kuqe). Më vonë, metrika u përgjithësua në sekuenca q-ary: për një palë vargjesh "zgjedhje" dhe "gardhe", distanca Hamming është e barabartë me tre.

Në përgjithësi, distanca Hamming për objektet dhe dimensionet jepet nga funksioni:

Distanca Hamming ka vetitë e një metrike, që plotëson kushtet e mëposhtme:

Distanca Hamming në bioinformatikë dhe gjenomikë

Letërsia

• Richard W. Hamming. Kodet e zbulimit dhe korrigjimit të gabimeve, Revista Teknike e Sistemit Bell 29(2): 147-160, 1950.
• Richard Blahuth. Teoria dhe praktika e kodeve të kontrollit të gabimeve. M., Mir, 1986

Lidhjet

• Richard Hamming dhe Fillimet e Teorisë së Kodimit // Muzeu Virtual i Kompjuterit

Fondacioni Wikimedia. 2010 .

Shihni se çfarë është "Hamming distance" në fjalorë të tjerë:

Distanca e Hamingut- Distanca Hamming Distanca d (u,v) ndërmjet dy sekuencave kodike u dhe v me të njëjtën gjatësi, e barabartë me numrin e karaktereve në të cilat ato ndryshojnë. Një kod blloku me një distancë minimale Hamming d ju lejon të zbuloni (d 1) dhe ... ...

distanca e kodit- Distanca minimale Hamming, e marrë përsipër të gjitha lares e fjalëve të ndryshme kodike në një kod uniform. [Mbledhja e termave të rekomanduara. Çështja 94. Teoria e transmetimit të informacionit. Akademia e Shkencave e BRSS. Komiteti i Terminologjisë Teknike. 1979] Temat e teorisë ... ... Manuali i Përkthyesit Teknik

Në fushën e matematikës dhe teorisë së informacionit, një kod i linjës është një lloj i rëndësishëm kodi bllok i përdorur në qarqet e zbulimit dhe korrigjimit të gabimeve. Kodet lineare, në krahasim me kodet e tjera, lejojnë zbatimin e algoritmeve më efikase ... ... Wikipedia

Në fushën e matematikës dhe teorisë së informacionit, një kod i linjës është një lloj i rëndësishëm kodi bllok i përdorur në qarqet e zbulimit dhe korrigjimit të gabimeve. Kodet lineare, në krahasim me kodet e tjera, lejojnë zbatimin e algoritmeve më efikase ... ... Wikipedia

Zbulimi i gabimeve në teknologjinë e komunikimit është një veprim që synon monitorimin e integritetit të të dhënave gjatë regjistrimit / riprodhimit të informacionit ose gjatë transmetimit të tij përmes linjave të komunikimit. Procedura e rikuperimit të korrigjimit të gabimit (korrigjimi i gabimit) ... ... Wikipedia

Zbulimi i gabimeve në teknologjinë e komunikimit është një veprim që synon monitorimin e integritetit të të dhënave gjatë regjistrimit / riprodhimit të informacionit ose gjatë transmetimit të tij përmes linjave të komunikimit. Procedura e korrigjimit të gabimit (korrigjimi i gabimit) për rikuperimin e informacionit pas ... ... Wikipedia

Zbulimi i gabimeve në teknologjinë e komunikimit është një veprim që synon monitorimin e integritetit të të dhënave gjatë regjistrimit / riprodhimit të informacionit ose gjatë transmetimit të tij përmes linjave të komunikimit. Procedura e korrigjimit të gabimit (korrigjimi i gabimit) për rikuperimin e informacionit pas ... ... Wikipedia

Zbulimi i gabimeve në teknologjinë e komunikimit është një veprim që synon monitorimin e integritetit të të dhënave gjatë regjistrimit / riprodhimit të informacionit ose gjatë transmetimit të tij përmes linjave të komunikimit. Procedura e korrigjimit të gabimit (korrigjimi i gabimit) për rikuperimin e informacionit pas ... ... Wikipedia

Përpunimi i imazhit

• tutorial

Ky artikull do të fokusohet në algoritmin HEngine dhe zbatimin e zgjidhjes së problemit të llogaritjes së distancës Hamming në sasi të mëdha të dhënash.

Prezantimi

Distanca Hamming është numri i pozicioneve të ndryshme për vargjet me të njëjtën gjatësi. Për shembull HD ( 1 00 , 0 01 ) = 2.

Problemi i llogaritjes së distancës Hamming u parashtrua për herë të parë nga Minsky dhe Papert në vitin 1969, ku detyra ishte të gjente të gjitha rreshtat nga baza e të dhënave që janë brenda një distance të caktuar Hamming me atë të kërkuar.

Një detyrë e tillë është jashtëzakonisht e thjeshtë, por kërkimi për zgjidhjen e saj efektive është ende në axhendë.

Distanca Hamming tashmë përdoret mjaft gjerësisht për detyra të ndryshme si gjetja e dublikatave të afërta, njohja e modelit, klasifikimi i dokumenteve, korrigjimi i gabimeve, zbulimi i viruseve, etj.

Për shembull, Manku dhe të tjerët propozuan një zgjidhje për problemin e grupimit të dyfishtë kur indeksohen dokumentet në ueb bazuar në llogaritjen e distancës Hamming.
Gjithashtu, Miller dhe miqtë propozuan konceptin e kërkimit të këngëve nga një fragment i caktuar audio.
Zgjidhje të ngjashme janë përdorur për problemin e kërkimit të imazheve dhe njohjes së retinës, etj.

Përshkrimi i problemit

Ekziston një bazë të dhënash e vargjeve binare T, madhësia n, ku gjatësia e çdo rreshti m. Vargu i kërkuar a dhe distancën e kërkuar Hamming k.

Detyra zbret në gjetjen e të gjitha vargjeve që janë brenda distancës k.

Në konceptin origjinal të algoritmit, konsiderohen dy variante të problemit: statike dhe dinamike.

Në një problem statik, distanca k është e paracaktuar.
- Në dinamikë, përkundrazi, distanca e kërkuar nuk dihet paraprakisht.

Artikulli përshkruan zgjidhjen e vetëm një problemi statik.

Përshkrimi i algoritmit HEngine për një detyrë statike

Ky zbatim fokusohet në kërkimin e vargjeve brenda k <= 10.

Ekzistojnë tre zgjidhje për problemin statik: kërkimi linear (skanimi linear), zgjerimi i pyetjes (zgjerimi i pyetjes) dhe zgjerimi i bazës së të dhënave (zgjerimi i tabelës).

Në këtë rast, nën zgjerimi i pyetjes do të thotë gjenerimi i të gjitha varianteve të mundshme të vargjeve që përshtaten në distancën e dhënë për vargun origjinal.
Zgjerimi i bazës të dhëna nënkupton krijimin e kopjeve të shumta të kësaj baze të dhënash, ku ose gjenerohen të gjitha opsionet e mundshme që plotësojnë kërkesat e distancës së kërkuar, ose të dhënat përpunohen në ndonjë mënyrë tjetër (më shumë për këtë pak më vonë.).

HEngine përdor një kombinim të këtyre tre metodave për të balancuar në mënyrë efektive kujtesën dhe kohën e ekzekutimit.

Pak teori

Algoritmi bazohet në një teoremë të vogël që thotë si më poshtë:

Nëse për dy rreshta a dhe b distanca HD( a, b) <= k, atëherë nëse i ndajmë rreshtat a dhe b te nënvargjet sipas metodës rcut duke përdorur faktori i segmentimit
r >= ⌊k/2⌋ + 1
duhet të ketë të paktën q= r − ⌊k/2⌋ nënvargjet kur distanca e tyre nuk e kalon një, HD( a unë, b i)<= 1.

Nxjerrja e nënvargjeve nga një varg bazë duke përdorur metodën rcut kryhet sipas parimeve të mëposhtme:
Vlera e emërtuar faktori i segmentimit, e cila plotëson kushtin
r >= ⌊k/2⌋ + 1

Gjatësia e të parës r − (m mod r) nënvargjet do të kenë gjatësi ⌊ m / r⌋ dhe e fundit m mod r nënvargjet ⌈ m/r⌉. Ku mështë gjatësia e vargut.

Tani e njëjta gjë, vetëm me një shembull:

Jepen dy vargje binare me gjatësi m= 8 bit: A = 11110000 dhe B = 11010001, distanca midis tyre k = 2.
Zgjedhja e një faktori segmentimi r= 2 / 2 + 1 = 2, d.m.th. në total do të ketë 2 nënvargje me gjatësi m/r= 4 bit.

A1=1111, a2=0000
b1=1101, b2=0001

Nëse tani llogarisim distancën midis nënvargjeve përkatëse, atëherë të paktën ( q= 2 - 2/2 = 1) një nënvarg do të përputhet ose distanca e tyre nuk do të kalojë një.

Ajo që shohim:
HD(a1, b1) = HD(1111, 1101) = 1
dhe
HD(a2, b2) = HD(0000, 0001) = 1

Nënvargjet e vargut bazë janë emërtuar nënshkrimet.
Nënshkrimet ose nënvargjet a1 dhe b1 (a2 dhe b2, a3 dhe b3 ..., a r dhe b r) quhen të pajtueshme me njëri-tjetrin, dhe nëse numri i tyre i biteve të ndryshëm nuk është më shumë se një, atëherë thirren këto nënshkrime që përkon.

Dhe ideja kryesore e algoritmit HEngine është përgatitja e bazës së të dhënave në mënyrë të tillë që të gjejë nënshkrimet që përputhen dhe më pas të zgjidhni ato rreshta që janë brenda distancës së kërkuar Hamming.

Parapërpunimi i bazës së të dhënave

Ne e dimë tashmë se nëse vargu është i ndarë saktë në nënvargje, atëherë të paktën një nënvarg do të përputhet me nënvargun përkatës, ose numri i biteve të ndryshëm nuk do të kalojë një (nënshkrimet do të përputhen).

Kjo do të thotë që nuk kemi nevojë të bëjmë një kërkim të plotë nëpër të gjitha rreshtat nga baza e të dhënave, por fillimisht duhet të gjejmë ato nënshkrime që përputhen, d.m.th. nënvargjet do të ndryshojnë me maksimumi një.

Por si të kërkojmë sipas nënvargjeve?

Metoda binar e kërkimit duhet të bëjë një punë mjaft të mirë për këtë. Por kërkon që lista e vargjeve të renditet. Por ne marrim disa nënvargje nga një varg. Për të kryer një kërkim binar në një listë me nënvargje, secila listë e tillë duhet të renditet paraprakisht.
Prandaj, kjo sugjeron një metodë për zgjerimin e bazës së të dhënave, domethënë krijimin e disa tabelave, secila për nënvargun ose nënshkrimin e vet. (Një tabelë e tillë quhet tabela e nënshkrimit. Dhe grupi i tavolinave të tilla - grup nënshkrimesh).

Versioni origjinal i algoritmit përshkruan gjithashtu ndërrimin e nënvargjeve në atë mënyrë që nënvargjet e zgjedhura të jenë në radhë të parë. Kjo bëhet më shumë për lehtësinë e zbatimit dhe për optimizime të mëtejshme të algoritmit:

Ekziston një varg A, i cili është i ndarë në 3 nënvargje, a1, a2, a3, lista e plotë e permutacioneve do të jetë përkatësisht:
a1, a2, a3
a2, a1, a3
a3, a1, a2

Këto tabela nënshkrimi janë renditur më pas.

Zbatimi i kërkimit

Në këtë fazë, pas përpunimit paraprak të bazës së të dhënave, kemi disa kopje të tabelave të renditura, secila për nënvargun e vet.

Natyrisht, nëse duam të gjejmë së pari nënvargjet, duhet të marrim nënshkrime nga vargu i kërkuar në të njëjtën mënyrë që është përdorur gjatë krijimit të tabelave të nënshkrimit.

Ne gjithashtu e dimë se nënvargjet e kërkuara ndryshojnë nga më së shumti një element. Dhe për t'i gjetur ato, duhet të përdorni metodën e zgjerimit të pyetjes.

Me fjalë të tjera, kërkohet që nënvargu i përzgjedhur të gjenerojë të gjitha kombinimet, duke përfshirë vetë këtë nënvarg, në të cilin diferenca do të jetë më së shumti një element. Numri i kombinimeve të tilla do të jetë i barabartë me gjatësinë e nënvargut + 1.

Veprime të tilla duhet të kryhen për të gjitha nënvargjet dhe për të gjitha tabelat.

Dhe në fund, ju duhet të filtroni ato rreshta që nuk përshtaten në kufirin e caktuar të distancës Hamming. Ato. kryeni një kërkim linear në linjat e gjetura dhe lini vetëm ato rreshta që plotësojnë kushtin HD( a, b) <= k.

Filtri i lulëzimit

Autorët sugjerojnë përdorimin e një filtri Bloom për të zvogëluar numrin e kërkimeve binare.
Filtri Bloom mund të përcaktojë shpejt nëse një nënvarg është në një tabelë me një përqindje të vogël të pozitivëve të rremë. E cila është më e shpejtë se hash-i i tabelës.

Nëse, përpara një kërkimi binar për një nënvarg në një tabelë, filtri kthen që nënvargu nuk është në atë tabelë, atëherë nuk ka kuptim të bëhet kërkimi.

Prandaj, duhet të krijohet një filtër për çdo tabelë nënshkrimi.

Tani e njëjta gjë, vetëm me një shembull

Ekziston një bazë të dhënash e vargjeve binare me gjatësi 8 bit:
11111111
10000001
00111110

Detyra është të gjesh të gjitha vargjet ku numri i biteve të ndryshëm nuk i kalon 2 në vargun e synuar 10111111.
Pra distanca e kërkuar k = 2.

1. Zgjidhni një faktor segmentimi.
Bazuar në formulën, zgjidhni faktorin e segmentimit r= 2, që do të thotë se do të ketë dy nënvargje nga një varg.

2. Krijo një grup nënshkrimesh.
Meqenëse numri i nënvargjeve është 2, duhet të krijohen vetëm 2 tabela:
T1 dhe T2

3. Ne ruajmë nënvargjet në tabelat përkatëse duke ruajtur një lidhje me burimin.

T1 T2
1111 1111 => 11111111
1000 0001 => 10000001
0011 1110 => 00111110

4. Renditni tabelat. Secila veç e veç.
T1
0011 => 00111110
1000 => 10000001
1111 => 11111111

T2
0001 => 10000001
1110 => 00111110
1111=> 11111111

Kjo përfundon parapërpunimin. Dhe le të fillojmë të kërkojmë.

1. Marrim nënshkrimet e vargut të kërkuar.
Vargu i kërkimit 10111110 është i ndarë në nënshkrime. Rezulton përkatësisht 1011 dhe 1100, e para për tabelën e parë, dhe e dyta për të dytën.

2. Ne gjenerojmë të gjitha kombinimet që ndryshojnë nga një.
Numri i opsioneve do të jetë 5.

2.1 Për nënvargun e parë 1011:
1011
0 011
11 11
100 1
1010

2.2 Për nënvargun e dytë 1100:
1100
0 100
10 00
111 0
1101

3. Kërkimi binar.

3.1 Për të gjitha variantet e krijuara të nënvargut të parë 1011, ne kryejmë një kërkim binar në tabelën e parë për një përputhje të plotë.

1011
0011 == 0011 => 00111110
1111 == 1111 => 11111111
1001
1010

U gjetën dy nënvargje.

3.2 Tani, për të gjitha variantet e nënvargut të dytë 1100, ne kryejmë një kërkim binar në tabelën e dytë.

1100
0100
1000
1110 == 1110 => 00111110
1101

U gjet një nënvarg.

4. Kombinimi i rezultateve në një listë:
00111110
11111111

5. Kontrolloni në mënyrë lineare për pajtueshmërinë dhe filtroni kushtet e papërshtatshme<= 2:

HD(10111110, 00111110) = 1
HD(10111110, 11111111) = 2

Të dy vargjet plotësojnë kushtin e ndryshimit të jo më shumë se dy elementeve.

Edhe pse në këtë fazë kryhet një kërkim linear, lista e vargjeve kandidate pritet të jetë mjaft e vogël.
Në kushtet kur numri i kandidatëve do të jetë i madh, propozohet përdorimi i versionit rekurziv të HEngine.

qartë

Figura 1 tregon një shembull të algoritmit të kërkimit.
Për një gjatësi të vargut prej 64 dhe një kufi distancë prej 4, faktori i segmentimit është 3, që korrespondon me vetëm 3 nënvargje për varg.
Ku T1, T2 dhe T3 janë tabela nënshkrimi që përmbajnë vetëm nënvargje B1, B2, B3, 21, 21 dhe 22 bit të gjatë.

Vargu i kërkuar ndahet në nënvargje. Më pas, gjenerohet një sërë nënshkrimesh për nënvargjet përkatëse. Për nënshkrimin e parë dhe të dytë, numri i kombinimeve do të jetë 22. Dhe nënshkrimi i fundit jep 23 opsione. Në fund, kryhet një kërkim binar.

Figura 1. Versioni i thjeshtuar i përpunimit të pyetjeve të tabelës së nënshkrimit.

rezultatet

Kompleksiteti mesatar i një algoritmi të tillë është O(P* (log n+ 1)) ku nështë numri i përgjithshëm i rreshtave në bazën e të dhënave, log n+ 1 kërkim binar dhe P- numri i kërkimeve binare: llogaritet, në rastin tonë, si numri i kombinimeve për tabelë shumëzuar me numrin e tabelave: P = (64 / r + 1) * r

Në raste ekstreme, kompleksiteti mund të kalojë linear.

Vihet re se kjo qasje përdor më pak memorie në 4.65 dhe është 16% më e shpejtë se puna e mëparshme e përshkruar në. Dhe është mënyra më e shpejtë e njohur aktualisht për të gjetur të gjitha vargjet brenda një kufiri të caktuar.

Zbatimi

E gjithë kjo është sigurisht joshëse, por derisa ta prekni në praktikë, është e vështirë të vlerësoni shkallën.
Një prototip HEngine u krijua dhe u testua në të dhënat reale të disponueshme.

Testet$ ./përputhet 7 data/db/table.txt data/query/face2.txt Leximi i të dhënave ........ u krye. 752420 db hash dhe 343 hash pyetjesh. Ndertese me 7 hamming distance te lidhur ....... e kryer. Koha e ndërtimit: 12.964 sekonda Kërkimi i ndeshjeve HEngine ....... gjeti 100 ndeshje gjithsej. Koha e pyetjes së HEngine: 0,1 sekonda Kërkimi i përputhjeve lineare ....... gjetën 100 ndeshje gjithsej. Koha lineare e pyetjes: 6.828 sekonda

Rezultatet janë inkurajuese, pasi kërkimi për 343 hash nga një bazë prej 752420 merr ~0.1 sekonda, që është 60 herë më shpejt se një kërkim linear.

Duket se ne mund të ndalemi këtu. Por me të vërtetë doja të përpiqesha ta përdorja disi në një projekt real.

Nga PHP mjafton të telefononi:
$lista = file_get_contents ("http://fcgi.local/?" . $hashes);
E cila e kthen rezultatin në ~0,5 sekonda. Kur një kërkim linear zgjat 9 sekonda, dhe përmes pyetjeve në MySQL të paktën 20 sekonda.

Faleminderit të gjithëve që e bënë atë.

Lidhjet

M. Minsky dhe S. Papert. Perceptronet. MIT Press, Kembrixh, MA, 1969.
G. S. Manku, A. Jain dhe A. D. Sarma. Zbulimi i afër-duplikatave për zvarritje në ueb. Në Proc. 16 WWW, maj 2007.
M. L. Miller, M. A. Rodriguez dhe I. J. Cox. Gjurmët audio: Kërkimi i fqinjit më të afërt në hapësirën binare me dimensione të larta. Në MMSP, 2002.
M. L. Miller, M. A. Rodriguez dhe I. J. Cox. Gjurmimi i gishtërinjve audio: kërkimi i fqinjit më të afërt në hapësira binare me dimensione të larta. Journal of VLSI Signal Processing, Springer, 41 (3): 285–291, 2005.
J. Landrée dhe F. Truchetet. Marrja e imazhit me distancë binare të hamingut. Në Proc. VISAPP 2, 2007.
H. Yang dhe Y. Wang. Një metodë e njohjes së fytyrës me bazë LBP me kufizim të distancës së përplasjes. Në Proc. ICIG e katërt, 2007.
B. Lulëzimi. Kompensimet hapësinore/kohore në kodimin hash me gabime të lejueshme. Communications of ACM, 13(7):422–426, 1970.
Alex X. Liu, Ke Shen, Eric Torng. Përpunimi i pyetjeve në distancë të Hamming në shkallë të madhe. Konferenca e ICDE, faqe 553 - 564, 2011.
github.com/valbok/HEngine Implementimi im i HEngine në C++ Shto etiketa

Libri i Stefan Cvajgut, Orët me Yje të Njerëzimit, përmban një histori të jashtëzakonshme, Gjeniu i një nate, për një oficer të ushtrisë franceze, Rouge de Lisle, i cili shkroi Marsejën e famshme gjatë një nate në vapën e frymëzimit të tij. Ishte në vitin 1792 në Marsejën revolucionare. Kënga u përhap në të gjithë Francën brenda pak ditësh, shpejt fitoi popullaritet të jashtëzakonshëm në të gjithë botën dhe më pas u bë himni kombëtar i Republikës Franceze. Historia e ka ruajtur emrin Rouge në kujtesën e pasardhësve falë kësaj kënge të vetme.

Për analogji, Richard Hamming mund të quhet një "gjeni i një ideje". Ai e formuloi atë në vitin 1950 në punimin e tij të vetëm shkencor mbi kodet e korrigjimit të gabimeve. Artikulli përmbante ndërtimin e një kodi blloku që korrigjon gabimet e vetme që ndodhin gjatë transmetimit të mesazhit.

Richard Hamming ishte vazhdimisht aktiv në kërkimin shkencor, por vepra e tij e vetme në fushën e teorisë së informacionit u bë e famshme, duke përbërë një përqindje të parëndësishme të punës së tij shkencore për nga vëllimi. Ky artikull fitoi shpejt famë botërore dhe i solli famë të merituar.

Ashtu si zbulimet e Faraday dhe Maxwell u pasuan nga shpikje të shumta në fushën e telekomunikacionit që ndryshuan jetën tonë, kështu pas krijimit të teorisë së informacionit nga Claude Shannon dhe Vladimir Kotelnikov, teoria e imunitetit të mundshëm ndaj zhurmës hapi mundësi të reja për zhvillim. të telekomunikacionit. Një nga seksionet më të rëndësishme të teorisë së informacionit është teoria e kodimit, themelet e së cilës u hodhën nga Hamming.

Shannon zbuloi se informacioni mund të transmetohet pa gabime në një kanal komunikimi nëse shpejtësia e transmetimit nuk e kalon kapacitetin e tij. Megjithatë, prova e Shannon nuk ishte konstruktive. Studimet e tij të mëvonshme dhe një tjetër shkencëtar amerikan S. O. Rice treguan se pothuajse çdo kod i zgjedhur rastësisht ju lejon të arrini kufirin teorik të imunitetit ndaj zhurmës për marrjen e mesazheve. Sidoqoftë, një kod i tillë kishte një kompleksitet të lartë dekodimi: numri i operacioneve të nevojshme për të deshifruar kombinimin e kodit të marrë u rrit në mënyrë eksponenciale me gjatësinë e tij.

Hamming ishte i pari që propozoi një metodë konstruktive për ndërtimin e kodeve me tepricë dhe dekodim të thjeshtë. Puna e tij paracaktoi drejtimin e shumicës së punës në këtë fushë që pasoi më vonë.

Për nder të tij, Instituti i Inxhinierëve Elektrikë dhe Elektronikë krijoi një medalje, e cila u jepet shkencëtarëve që kanë dhënë kontribut të rëndësishëm në teorinë e informacionit.

Kodet e aftë për të korrigjuar gabimet (në kanalet e komunikimit në kompjuterët dixhitalë etj.) gjatë përpunimit të sinjalit u propozuan nga Hamming edhe para vitit 1948, kur u botua artikulli i famshëm i Shannon "Teoria Matematike e Komunikimit", i cili hodhi një themel të fortë për teorinë në këtë. zonave.

Në këtë artikull, Shannon, duke iu referuar një studimi të bërë në 1947 nga kolegu i tij në Bell Lab, Richard Hamming, përshkroi si shembull një kod të thjeshtë me gjatësi 7 që korrigjon të gjitha gabimet e vetme. Publikimi i materialit origjinal të Hamming u vonua deri në prill 1950 për arsye patente. Duhet të theksohet se shembulli i kodit të korrigjimit të gabimeve, i dhënë në artikullin e përmendur të Shannon, nisi studimin e një shkencëtari tjetër amerikan, M. E. Golay. Golay, pavarësisht nga Hamming, zbuloi kode që korrigjojnë gabimet e vetme. Në vitin 1949 (d.m.th., përpara Hamming-ut) ai botoi një shënim të shkurtër (vetëm gjysmë faqe) në lidhje me rezultatet e tij në Procedurat e IEEE. Në këtë shënim, ai mori në konsideratë jo vetëm kodet binare, por edhe kodet e përgjithshme, kombinimet e të cilave i përkasin një fushe të fundme (një grup matematikor elementësh me veprime të caktuara të mbledhjes, zbritjes, pjesëtimit dhe shumëzimit) me elemente pn (p është një i thjeshtë , dhe n është një numër i plotë).

Duhet të theksohet se një sërë idesh themelore të teorisë së komunikimit njiheshin si rezultate të veçanta matematikore edhe përpara se të përdoreshin nga shkencëtarët që zgjidhin problemet e transmetimit të mesazheve përmes kanaleve të komunikimit. Në librin e tij Teoria e kodimit algjebrik, E. Berlekamp, ​​një specialist i shquar amerikan në fushën e teorisë së kodimit, bëri një vërejtje shumë interesante. Ai vuri në dukje se ndërtimi i kodeve Hamming u përshkrua në një kontekst tjetër në vitin 1942 nga matematikani i famshëm amerikan R. A. Fisher, në një vepër kushtuar teorisë së analizës së faktorëve (një nga seksionet e statistikave matematikore) dhe lidhjes së saj me matematikën. teoria e grupeve. Nga rruga, teorema e V. A. Kotelnikov, që tregon mundësinë e paraqitjes së sinjaleve analoge në formë dixhitale, u zbulua gjithashtu si një nga rezultatet e veçanta matematikore të teorisë së interpolimit të një funksioni në fillim të shekullit të 20-të nga matematikanët anglezë. E. T. dhe J. M. Whitkers. Duhet theksuar se as Fisher dhe as shkencëtarët britanikë të përmendur nuk i lidhën rezultatet e tyre me problemet më të rëndësishme për botën moderne në transmetimin e informacionit përmes kanaleve të komunikimit.

Wolfgang Goethe tha: “Nuk mjafton vetëm të fitosh njohuri; Më duhet të gjej një aplikacion për të. Nuk mjafton vetëm të urosh; duhet bërë”. Për teorinë dhe teknologjinë e komunikimeve, teorema Kotelnikov dhe kodet Hamming kanë një rëndësi të jashtëzakonshme, pasi falë tyre u hap një perspektivë e qartë e krijimit të sistemeve dixhitale para inxhinierëve, të cilët në fund të shekullit të 20-të revolucionarizuan. telekomunikacioni dhe prandaj me të drejtë quhen me emrat e këtyre shkencëtarëve.

Duke u bërë një katalizator që përshpejtoi zhvillimin e teorisë së kodimit, artikulli i Hamming tërhoqi vëmendjen e komunitetit shkencor. Në të gjitha tekstet shkollore, kjo klasë kodesh quhet kodet Hamming, dhe prezantimi i teorisë së kodimit fillon me një përshkrim të ndërtimit të tyre. Me sa duket, do të ishte akoma më e drejtë që këto kode të quheshin kode Hamming-Golay, duke qenë se Golay doli me të njëjtat ide si Hamming në mënyrë të pavarur dhe i publikoi ato më herët. Fakti që artikulli i tij nuk tërhoqi vëmendjen e duhur është me shumë mundësi një rastësi.

Krahasuar me teorinë e Shannon, kodet e Hamming ishin jashtëzakonisht të dobëta. Megjithatë, metodat e rregullta të Hamming për ndërtimin e kodeve të korrigjimit të gabimeve ishin të një rëndësie themelore. Ata u treguan inxhinierëve mundësinë praktike për të arritur kufijtë e treguar nga ligjet e teorisë së informacionit. Këto kode kanë gjetur zbatim praktik në krijimin e sistemeve kompjuterike. Letra e Hamming gjithashtu çoi në një zgjidhje për problemin e paketimit më të dendur për fushat e fundme. Ai futi në përdorim shkencor konceptet më të rëndësishme të teorisë së kodimit - distancën Hamming midis kombinimeve të kodeve në një hapësirë ​​vektoriale, e përcaktuar për kodet binare si numri i pozicioneve të këtyre kombinimeve me karaktere të ndryshme, dhe kufijtë Hamming për aftësinë korrigjuese të bllokut. kodet e korrigjimit. Lidhja Hamming për kodet binare llogaritet duke përdorur formulën e mëposhtme:

Në këtë shprehje, numri i gabimeve e mund të korrigjohet nga një kod blloku korrigjues me gjatësi N që ka fjalë kodike M (CjN është koeficienti binomial).

Puna e Hamming luajti një rol kyç në zhvillimin e mëvonshëm të teorisë së kodimit dhe stimuloi kërkime të gjera të kryera në vitet e mëvonshme. Në vitin 1956, David Slepyan ishte i pari që prezantoi teorinë e kodeve të kontrollit të barazisë mbi një bazë serioze matematikore. Një ndryshim i madh në teorinë e kodimit ndodhi kur shkencëtari francez A. Hockwingham (1959) dhe amerikanët R. C. Bowes dhe D. C. Roy-Chowdhury (1960) gjetën një klasë të madhe kodesh (kodet BCH) që korrigjojnë gabimet e shumëfishta. Studiuesit amerikanë I. S. Reed dhe G. Solomon (1960) gjetën një klasë kodesh për kanalet jobinare të lidhura me kodet BCH.

Në vitin 1980, Hamming shkroi një libër shkollor të shkëlqyer, Teoria e Kodimit dhe Teoria e Informacionit, i cili u përkthye në Rusisht në 1983. Ky libër, si veprat e tjera të tij, dallohet për origjinalitetin e formulimit të pyetjeve, popullaritetin e prezantimit, kuptimin e thellë të problemeve praktike, korrektësinë dhe shkallën e arsyeshme të ashpërsisë së interpretimit matematikor të çështjeve të ngritura. Paraqitja e materialit është e strukturuar në atë mënyrë që lexuesit ta ketë të qartë se pse kjo apo ajo teoremë është e vërtetë.

Artikulli i mëparshëm: Nëse produkti ndahet me një nga faktorët, atëherë do të merret një faktor tjetër Artikulli vijues: Format bazë të përshëndetjes (përkthyer nga Nihao)