Hamingo atstumas. Puiki naftos ir dujų enciklopedija

Apie dvejetainių ilgio žodžių rinkinį m atstumas d(a,b) tarp žodžių a ir b yra šių žodžių nesutampančių pozicijų skaičius, pavyzdžiui: atstumas tarp žodžių a = 01101 ir b = 00111 yra 2.

Taip apibrėžta sąvoka vadinama Hamingo distancija.

Jis atitinka šias atstumo aksiomas:

1) d(a,b)  0 ir d(a,b)=0 tada ir tik tada, jei a = b;

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

3) d(a,b) + d(b,c)  d(a,c) (trikampio nelygybė).

Žodžio a svoris w(a) yra vienetų skaičius tarp jo koordinačių. Tada atstumas tarp žodžių a ir b yra jų sumos a b svoris: d(a,b)=w(a b) , kur simbolis  žymi koordinačių sudėjimo modulio 2 veiksmą. Intuityviai aišku, kad kodas geriau tinka klaidų aptikimui ir taisymui, tuo labiau skiriasi kodo žodžiai. Hamingo atstumo sąvoka leidžia mums tai išsiaiškinti.

Teorema Kad kodas aptiktų klaidas k (ar mažiau) padėtyse, būtina ir pakanka, kad mažiausias atstumas tarp kodo žodžių būtų  k + 1.

Šios teoremos įrodymas panašus į šio teiginio įrodymą.

Teorema. Kad kodas ištaisytų visas k (ar mažiau) pozicijų klaidas, būtina ir pakanka, kad mažiausias atstumas tarp kodo žodžių būtų  2k + 1.

32. Kodų taisymo gebėjimo teorema.

Kodai, galintys automatiškai ištaisyti klaidas, vadinami savaiminiais taisymais. Norint sukurti savaime taisantį kodą, skirtą atskiroms klaidoms ištaisyti, neužtenka vieno kontrolinio skaitmens. Kaip matyti iš to, valdymo bitų skaičius k turi būti parinktas taip, kad būtų įvykdyta nelygybė 2k≥k+m+1arba k≥log2(k+m+1), kur m yra pagrindinių dvejetainių bitų skaičius. kodinio žodžio. Šiuo metu didžiausią susidomėjimą kelia dvejetainių blokų taisymo kodai. Naudojant tokius kodus, informacija perduodama vienodo ilgio blokų pavidalu ir kiekvienas blokas užkoduojamas ir dekoduojamas nepriklausomai vienas nuo kito. Beveik visuose blokiniuose koduose simbolius galima suskirstyti į informacinius ir tikrinamuosius.

Pagrindinės savaime taisančių kodų charakteristikos yra šios:

1. Leidžiamų ir draudžiamų derinių skaičius. Jei n yra simbolių skaičius bloke, r yra kontrolinių simbolių skaičius bloke, k yra informacijos simbolių skaičius, tai 2n yra galimų kodų kombinacijų skaičius, 2k yra leistinų kodų kombinacijų skaičius, 2n −2k yra draudžiamų derinių skaičius.

2. Kodo perteklius. Reikšmė rn vadinama pataisos kodo pertekliumi.

3. Minimalus kodo atstumas. Minimalus kodo atstumas d yra minimalus iškraipytų simbolių skaičius, reikalingas norint pereiti iš vienos leidžiamos kombinacijos į kitą.

4. Aptiktų ir ištaisytų klaidų skaičius. Jei g yra klaidų, kurias kodas gali ištaisyti, skaičius, tai būtina ir pakanka, kad d≥2g+1

5. Kodų koregavimo galimybės.

33. Matricinis kodavimas. Grupės kodai.

Kai aiškiai nurodote kodavimo schemą ( m, n) kodas turėtų nurodyti 2 m kodo žodžių, o tai labai neefektyvu.

Vienas ekonomiškas būdas apibūdinti kodavimo schemą yra matricinio kodavimo technika.

Anksčiau kiekviena kodavimo schema buvo aprašyta lentelėmis, nurodančiomis ilgio kodo žodį n kiekvienam šaltinio ilgio žodžiui m. Ilgiems blokams šis metodas reikalauja daug atminties, todėl yra nepraktiškas. Pavyzdžiui, už ( 16, 33 ) kodui reikės 33 * 2 16 = 2 162 688 bitų.

Reikalauja daug mažiau atminties matricos kodavimas. Leisti E matmenų matrica m×n, susidedantis iš elementų e ij , kur i yra eilutės numeris ir j - stulpelio numeris. Kiekvienas iš matricos elementų e ij gali būti 0 arba 1. Kodavimą įgyvendina operacija b = aE arba kur kodiniai žodžiai laikomi vektoriais, t. y. dydžio eilučių matricomis 1 × n.

Kodavimas neturėtų priskirti to paties kodinio žodžio skirtingiems šaltinio pranešimams. Paprastas būdas tai pasiekti yra m matricos stulpeliai sudarė vienetinę matricą. Padauginus bet kurį vektorių iš tapatybės matricos, gaunamas tas pats vektorius, todėl skirtingi pranešimų vektoriai atitiks skirtingus sisteminio kodo vektorius.

Matriciniai kodai taip pat vadinami linijiniai kodai. Linijiniam (n - r, n)-kodus su minimaliu Hamingo atstumu d egzistuoja Plotkin apatinė riba (Plotkin) už minimalų kontrolinių bitų skaičių r adresu n³ 2d – 1,

dvejetainis ( M, n) kodas vadinamas grupės kodu, jei jo kodiniai žodžiai sudaro grupę.

Atkreipkite dėmesį, kad visų m ilgio dvejetainių žodžių aibė sudaro komutuojančią grupę su koordinačių sudėjimo modulio 2 operacija, kurioje galioja santykis a a. Vadinasi, m ilgio žinučių žodžių a rinkinys yra komutacinė grupė.

Iškviečiamas blokavimo kodas grupė, jei jo kodiniai žodžiai sudaro grupę.

Jei kodas yra grupės kodas, mažiausias atstumas tarp dviejų kodo žodžių yra lygus mažiausiam nulinio žodžio svoriui.

Tai išplaukia iš santykio d(b i , b j ) = w(b i + b j ).

Naudojant pakaitos kodą, neaptinkamos tos ir tik tos klaidos, kurios atitinka klaidų eilutes, lygias kodiniams žodžiams.

Tokios klaidų eilutės vieną kodinį žodį paverčia kitu.

Todėl tikimybė, kad klaida liks neaptikta, yra lygi visų klaidų eilučių, lygių kodiniams žodžiams, tikimybių sumai.

Visų dvejetainių žodžių rinkinys a = a 1 ... a m ilgio m sudaro Abelio (komutacinę) grupę bitinio sudėjimo atžvilgiu.

Leisti E - kodavimas m×n-matrica, kuri turi m × m- submatrica su ne nuliu determinantu, pavyzdžiui, tapatybė. Tada kartografavimas a → a E verčia visų ilgio dvejetainių žodžių grupę m ilgio kodinių žodžių grupei n.

Tarkime, kad Tada mes gauname

t.y. Todėl dvejetainių žodžių grupės atvaizdavimas vienas su vienu m naudojant nurodytą matricą E išsaugo grupės operacijos savybes, o tai reiškia, kad kodiniai žodžiai sudaro grupę.

Grupės kodo savybė: mažiausias kodo atstumas tarp kodo vektorių yra lygus mažiausiam nulinių vektorių svoriui. Kodo vektoriaus svoris lygus vienetų skaičiui kodų kombinacijoje.

Grupių kodus patogu nurodyti naudojant matricas, kurių matmenį lemia parametrai k ir n. Eilučių skaičius yra k, o stulpelių skaičius n = k+m.

Šių matricų sugeneruoti kodai vadinami (n, k)-kodais, o atitinkamos matricos – generatoriais (generatoriais).

Puslapis 1

Hamingo atstumas tarp dviejų vienodo ilgio sekų atitinka pozicijų, kurias užima nesutampantys elementai, skaičių. Skirtingo ilgio sekų atveju Hamingo atstumas apibrėžiamas kaip minimalus pozicijų, kurias užima nesutampantys elementai, skaičius.

Hamingo atstumas d (u, v) tarp dviejų vienodo ilgio žodžių u ir v yra lygus šių žodžių besiskiriančių skaitmenų skaičiui. Jis naudojamas blokinių kodų teorijoje (V.

Naudojant Hamingo atstumo metrines savybes, tiesiogiai patikrinama, ar /l yra Xt metrika, bet nėra mišrių periodinių sekų rinkinio metrika.

Ši artumo funkcija atitinka Hamingo atstumą.

Metrikas p KLOP algoritme nurodomas Hamingo atstumu.

Jei paieškos procedūra gali rasti vietą, kurioje Hamingo atstumas yra lygus nuliui, problema bus išspręsta.

Palyginus neaiškius poaibius B ir B3, neryškumo laipsnius, taip pat Hamingo atstumą, matyti, kad nagrinėjami neryškūs poaibiai yra skirtingi. Tačiau jei skaičiuojama reikšme imsime elementą m2 G Uz, kurio laipsnis priklauso gautam neaiškiam poaibiui yra maksimalus, tai tokiu būdu apskaičiuoto neaiškiojo ryšio R panaudojimas gali būti pateisinamas. Be to, taikant šį metodą galima apibūdinti netiesiškumą tarp maksimalios temperatūros antroje reaktoriaus zonoje ir polietileno lydalo srauto greičio, šis metodas neatsižvelgia į nestacionarų reaktoriaus pobūdį. LDPE gavimo procesas, susijęs su technologinio proceso charakteristikų pokyčiais.

Šio kodo perdavimo funkcija rodo, kad yra vienas kelias, kurio Hamingo atstumas d – nuo nulinio kelio, kuris tam tikrame mazge susilieja su nuliniu keliu. Iš būsenos diagramos, parodytos fig. 8.2.6 arba grotelių diagrama, parodyta pav. 8.2.5, aišku, kad kelias nuo d6 yra acbe. Vėlgi iš būsenos diagramos arba gardelės matome, kad šie keliai yra acdbe ir acbcbe. Trečiasis (8.1.2) narys rodo, kad yra keturi keliai, kurių atstumas d 0 ir pan. Taigi perdavimo funkcija suteikia mums konvoliucinio kodo atstumo savybes.

Šis rezultatas atitinka pastebėjimą, kad visų nulių (/0) kelio Hamingo atstumas nuo gautos sekos yra d3, o kelio /1 Hamingo atstumas nuo gautos sekos yra d5. Taigi Hamingo atstumas yra lygiavertė sunkių sprendimų dekodavimo metrika.

Stefano Zweigo knygoje „Geriausios žmonijos valandos“ – nuostabus pasakojimas „Vienos nakties genijus“ apie prancūzų armijos karininką Rouget de Lisle'ą, kuris per vieną naktį jį apėmusio įkvėpimo įkarštyje parašė garsųjį „Marselietiją“. Tai įvyko 1792 m. revoliuciniame Marselyje. Daina per kelias dienas išplito visoje Prancūzijoje, greitai sulaukė didžiulio populiarumo visame pasaulyje ir vėliau tapo Prancūzijos Respublikos himnu. Šios vienintelės dainos dėka istorija išsaugojo vardą Rouge palikuonių atmintyje.

Pagal analogiją Richardas Hamingas gali būti vadinamas „vienos idėjos genijumi“. Jis jį suformulavo 1950 m. vieninteliame moksliniame straipsnyje, skirtame klaidų taisymo kodams. Straipsnyje buvo sukurtas blokinis kodas, kuris ištaiso pavienes klaidas, atsirandančias perduodant pranešimą.

Richardas Hammingas nuolat užsiėmė aktyviais moksliniais tyrimais, tačiau išgarsėjo vienintelis jo darbas informacijos teorijos srityje, kuris savo apimtimi sudaro nedidelę jo mokslinio darbo dalį. Šis straipsnis greitai pelnė pasaulinę šlovę ir atnešė jam pelnytą šlovę.

Kaip po Faradėjaus ir Maksvelo atradimų atsirado daugybė išradimų telekomunikacijų srityje, pakeitusių mūsų gyvenimus, taip Claude'o Shannono ir Vladimiro Kotelnikovo sukūrus informacijos teoriją, potencialaus atsparumo triukšmui teoriją, atsivėrė naujos galimybės. telekomunikacijų plėtra. Viena iš svarbiausių informacijos teorijos dalių yra kodavimo teorija, kurios pagrindus padėjo Hamingas.

Shannon nustatė, kad informacija gali būti perduodama be klaidų per ryšio kanalą, jei perdavimo greitis neviršija jo pajėgumų. Tačiau Šenono įrodymas nebuvo konstruktyvus. Vėlesni jo ir kito amerikiečių mokslininko S. O. Rice'o tyrimai parodė, kad beveik bet koks atsitiktinai parinktas kodas leidžia pasiekti teorinę pranešimų priėmimo triukšmo atsparumo ribą. Tačiau toks kodas turėjo didelį dekodavimo sudėtingumą: operacijų, reikalingų gautam kodo deriniui iššifruoti, skaičius eksponentiškai padidėjo jo ilgiui.

Hammingas pirmasis pasiūlė konstruktyvų kodų kūrimo metodą su pertekliumi ir paprastu dekodavimu. Jo darbas iš anksto nulėmė daugumos darbų šioje srityje kryptį, kuri buvo vėliau.

Jo garbei Elektros ir elektronikos inžinierių institutas įsteigė medalį, skirtą pripažinti mokslininkus, daug prisidėjusius prie informacijos teorijos.

Kodus, galinčius ištaisyti klaidas (ryšio kanaluose skaitmeniniuose kompiuteriuose ir kt.) apdorojant signalą, Hammingas pasiūlė dar prieš 1948 m., kai buvo paskelbtas garsusis Shannon straipsnis „Matematical Theory of Communication“, padėjęs tvirtus pagrindus teorijai šioje srityje. srityje.

Šiame darbe Šenonas, remdamasis 1947 metais savo kolegos „Bell Labs“ Richardo Hamingo atliktu tyrimu, kaip pavyzdį apibūdino paprastą 7 ilgio kodą, kuris ištaisė visas pavienes klaidas. Hamingo originalios medžiagos paskelbimas buvo atidėtas iki 1950 m. balandžio mėn. Pažymėtina, kad minėtame Šenono straipsnyje pateiktas klaidų taisymo kodo pavyzdys inicijavo kito amerikiečių mokslininko M. E. Golay tyrimus. Golay, nepriklausomai nuo Hamingo, atrado kodus, kurie ištaiso atskiras klaidas. 1949 m. (t. y. prieš Hamingą) jis paskelbė trumpą pastabą (tik pusę puslapio) apie savo rezultatus Proceedings of IEEE. Šioje pastaboje jis nagrinėjo ne tik dvejetainius kodus, bet ir bendruosius kodus, kurių deriniai priklauso baigtiniam laukui (matematinė elementų rinkinys su tam tikromis sudėties, atimties, dalybos ir daugybos operacijomis) su pn elementais (p yra pirminis dydis , o n yra sveikas skaičius).

Pažymėtina, kad nemažai esminių komunikacijos teorijos idėjų buvo žinomos kaip privatūs matematiniai rezultatai dar prieš pradedant jas taikyti mokslininkams, sprendžiant pranešimų perdavimo komunikacijos kanalais problemas. Žymus amerikiečių kodavimo teorijos ekspertas E. Berlekampas savo knygoje „Algebrinė kodavimo teorija“ padarė labai įdomią pastabą. Jis pažymėjo, kad Hamingo kodų dizainą kitame kontekste dar 1942 m. aprašė garsus amerikiečių matematikas R. A. Fisheris veikale, skirtame faktorinės analizės teorijai (vienai iš matematinės statistikos šakų) ir jos sąsajai su matematine. grupių teorija. Beje, V. A. Kotelnikovo teoremą, nurodančią galimybę pavaizduoti analoginius signalus skaitmenine forma, kaip vieną iš ypatingų matematinių funkcijų interpoliacijos teorijos rezultatų dar XX amžiaus pradžioje atrado anglų matematikai E. T. ir J. M. Whitkeris. Reikia pabrėžti, kad nei Fisheris, nei minėti anglų mokslininkai savo rezultatų nesusiejo su svarbiausiomis šiuolaikiniam informacijos perdavimo komunikacijos kanalais pasauliui problemomis.

Wolfgangas Goethe sakė: „Neužtenka vien įgyti žinių; Turiu rasti jam skirtą programėlę. Nepakanka tik palinkėti; reikia padaryti". Teorijai ir technologijoms... komunikacijoms Kotelnikovo teorema ir Hamingo kodai turi išskirtinę reikšmę, nes būtent jų dėka inžinieriams atsivėrė aiški perspektyva kurti skaitmenines sistemas, kurios XX amžiaus pabaigoje padarė perversmą telekomunikacijų srityje ir todėl jie teisėtai vadinami šių mokslininkų vardais.

Tapęs katalizatoriumi, paspartinusiu kodavimo teorijos raidą, Hamingo straipsnis patraukė mokslo bendruomenės dėmesį. Visuose vadovėliuose ši kodų klasė vadinama Hamingo kodais, o kodavimo teorijos pristatymas pradedamas nuo jų konstrukcijos aprašymo. Matyt, vis tiek būtų teisingiau šiuos kodus vadinti Hamming-Golay kodais, nes Golay savarankiškai atėjo į tas pačias idėjas kaip ir Hammingas ir paskelbė jas anksčiau. Tai, kad jo straipsnis nesulaukė tokio dėmesio, kurio nusipelnė, greičiausiai yra dėl atsitiktinumo.

Palyginti su Šenono teorija, Hamingo įvesti kodai buvo apmaudunai silpni. Tačiau įprastiniai Hamingo klaidų taisymo kodų konstravimo metodai buvo labai svarbūs. Jie inžinieriams pademonstravo praktinę galimybę pasiekti informacijos teorijos dėsnių nurodytas ribas. Šie kodai buvo praktiškai pritaikyti kuriant kompiuterines sistemas. Hamingo popierius taip pat leido išspręsti tankesnio užpildymo baigtiniuose laukuose problemą. Jis įvedė į mokslą svarbiausias kodavimo teorijos sąvokas – Hamingo atstumą tarp kodų kombinacijų vektorinėje erdvėje, dvejetainiams kodams apibrėžtą kaip šių kombinacijų su skirtingais simboliais padėčių skaičių, ir Hamingo ribas, skirtas koreguoti bloko gebėjimą. kodų taisymas. Dvejetainių kodų Hamingo riba apskaičiuojama pagal šią formulę:

Šioje išraiškoje klaidų skaičius e gali būti ištaisytas N ilgio koreguojančiu blokiniu kodu, turinčiu M kodų derinių (CjN yra dvinario koeficientas).

Hamingo darbas suvaidino pagrindinį vaidmenį vėliau plėtojant kodavimo teoriją ir paskatino tolesnius metus atlikti išsamius tyrimus. 1956 m. Davidas Slepyanas pirmasis rimtai matematiškai pateikė pariteto tikrinimo kodų teoriją. Didelis poslinkis kodavimo teorijos srityje įvyko, kai prancūzų mokslininkas A. Hoquenghem (1959) ir amerikiečiai R. K. Bose ir D. K. Roy-Chowdhury (1960) surado didelę kodų klasę (BCH kodai), kurie ištaiso kartotinių klaidų. Amerikiečių tyrinėtojai I. S. Reedas ir G. Solomonas (1960) rado kodų klasę, skirtą ne dvejetainiams kanalams, susijusiems su BCH kodais.

1980 m. Hammingas parašė puikų vadovėlį „Kodavimo teorija ir informacijos teorija“, kuris 1983 m. buvo išverstas į rusų kalbą. Ši knyga, kaip ir kiti jo darbai, išsiskiria klausimų formulavimo originalumu, pristatymo populiarumu, giliu praktinių problemų supratimu, iškeltų problemų matematinio aiškinimo teisingumu ir pagrįstu griežtumu. Medžiagos pateikimas sudarytas taip, kad skaitytojas intuityviai suprastų, kodėl ta ar kita teorema yra teisinga

) kodų sekų vektorinėje erdvėje, šiuo atveju Hamingo atstumas tarp dviejų dvejetainių sekų (vektorių) ir ilgis yra pozicijų, kuriose jos skiriasi, skaičius – šioje formuluotėje Hamingo atstumas įtrauktas į Algoritmų žodyną ir Jungtinių Valstijų nacionalinio standartų instituto duomenų struktūros (angl. NIST algoritmų ir duomenų struktūrų žodynas ).

Taigi Hamingo atstumas tarp vektorių 0 011 1 ir 1 010 1 yra 2 (skirtingi bitai pažymėti raudonai). Vėliau metrika buvo apibendrinta iki q eilučių: eilučių „rinkimai“ ir „tvora“ porai Hamingo atstumas yra lygus trims.

Apskritai objektų ir matmenų Hamingo atstumas nustatomas pagal funkciją:

Hamingo atstumas turi metrikos savybes, atitinkančias šias sąlygas:

Hamingo atstumas bioinformatikoje ir genomikoje

Literatūra

Richardas W. Hamingas. Klaidų aptikimo ir klaidų taisymo kodai, Bell System Technical Journal 29(2):147-160, 1950.
Ričardas Bleichutas. Klaidų kontrolės kodų teorija ir praktika. M., „Mir“, 1986 m

Nuorodos

Richardas Hammingas ir kodavimo teorijos pradžia // Virtualus kompiuterių muziejus

Wikimedia fondas.

2010 m.

Pažiūrėkite, kas yra „Hammingo atstumas“ kituose žodynuose: Hamingo atstumas

- Hamingo atstumas Atstumas d (u,v) tarp dviejų vienodo ilgio kodų sekų u ir v, lygus simbolių, kuriais jos skiriasi, skaičiui. Bloko kodas su minimaliu Hamingo atstumu d leidžia aptikti (d 1) ir... ... kodo atstumas - Minimalus Hamingo atstumas, perimtas visų skirtingų kodinių žodžių lares vienodame kode. [Rekomenduojamų terminų rinkinys. 94 laida. Informacijos perdavimo teorija. SSRS mokslų akademija. Techninės terminologijos komitetas. 1979] Temų teorija... ...

Techninis vertėjo vadovas

Matematikos ir informacijos teorijos srityse linijinis kodas yra svarbi blokinio kodo rūšis, naudojama klaidų aptikimo ir taisymo schemose. Linijiniai kodai, lyginant su kitais kodais, leidžia įgyvendinti efektyvesnius algoritmus... ... Vikipedija

Ryšių technologijų klaidų aptikimas – tai veiksmas, kuriuo siekiama stebėti duomenų vientisumą įrašant/atkuriant informaciją arba perduodant ją ryšio linijomis. Klaidų taisymo (klaidų taisymo) atkūrimo procedūra... ... Vikipedija