På et sett med binære ord med lengde m avstand d(a,b) mellom ordene a og b er antall ikke-matchende posisjoner til disse ordene, for eksempel: avstanden mellom ordene a = 01101 og b = 00111 er 2.

Konseptet definert på denne måten kalles Hamming-avstanden.

Den tilfredsstiller følgende avstandsaksiomer:

1) d(a,b)  0 og d(a,b)=0 hvis og bare hvis a = b;

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

3) d(a,b) + d(b,c)  d(a,c) (trekantulikhet).

Vekten w(a) til et ord a er antallet enere blant dets koordinater. Da er avstanden mellom ordene a og b vekten av summen deres a b: d(a,b)=w(a b) , hvor symbolet  angir operasjonen av koordinatvis addisjonsmodulo 2. Intuitivt er koden bedre egnet for feildeteksjon og korrigering, jo mer forskjellige kodeordene er. Konseptet Hamming-avstand lar oss klargjøre dette.

Teorem For at en kode skal oppdage feil i k (eller færre) posisjoner, er det nødvendig og tilstrekkelig at den minste avstanden mellom kodeord er  k + 1.

Beviset for denne teoremet ligner beviset for følgende utsagn.

Teorem. For at koden skal rette opp alle feil i k (eller færre) posisjoner, er det nødvendig og tilstrekkelig at den minste avstanden mellom kodeord er  2k + 1.

32. Teorem om koders korrigeringsevne.

Koder som automatisk kan rette feil kalles selvkorrigerende. For å bygge en selvkorrigerende kode designet for å korrigere enkeltfeil, er ikke ett kontrollsiffer nok. Som det fremgår av det følgende, må antall kontrollbiter k velges slik at ulikheten 2k≥k+m+1eller k≥log2(k+m+1) er tilfredsstilt, der m er antall grunnleggende binære biter. av kodeordet. For tiden er binære blokkkorreksjonskoder av størst interesse. Ved bruk av slike koder overføres informasjon i form av blokker av samme lengde og hver blokk kodes og dekodes uavhengig av hverandre. I nesten alle blokkkoder kan tegn deles inn i informasjon og verifisering.

Hovedkarakteristikkene til selvkorrigerende koder er:

1. Antall tillatte og forbudte kombinasjoner. Hvis n er antall symboler i blokken, r er antall kontrollsymboler i blokken, k er antall informasjonssymboler, så er 2n antall mulige kodekombinasjoner, 2k er antall tillatte kodekombinasjoner, 2n −2k er antall forbudte kombinasjoner.

2. Koderedundans. Verdien rn kalles redundansen til korreksjonskoden.

3. Minimum kodeavstand. Minste kodeavstand d er det minste antallet forvrengte symboler som kreves for å gå fra en tillatt kombinasjon til en annen.

4. Antall feil oppdaget og rettet. Hvis g er antall feil som koden kan rette, er det nødvendig og tilstrekkelig at d≥2g+1

5. Korrigerende muligheter for koder.

33. Matrisekoding. Gruppekoder.

Når du eksplisitt spesifiserer kodingsskjemaet i ( m, n)-kode bør spesifisere 2 m kodeord, noe som er svært ineffektivt.

En økonomisk måte å beskrive et kodeskjema på er matrisekodingsteknikken.

Tidligere ble hvert kodeskjema beskrevet av tabeller som spesifiserte et kodeord med lengde n for hvert kildeord av lengde m. For blokker lang lengde denne metoden krever mye minne og er derfor upraktisk. For eksempel for ( 16, 33 ) kode vil kreve 33 * 2 16 = 2 162 688 biter.

Krever mye mindre minne matrisekoding. La E dimensjonsmatrise m×n, bestående av elementer e ij , hvor Jeg er linjenummeret, og j - kolonnenummer. Hvert av matriseelementene e ij kan være enten 0 eller 1. Koding implementeres av operasjonen b = aE eller hvor kodeord betraktes som vektorer, dvs. som radmatriser av størrelse 1×n.

Koding bør ikke tilordne det samme kodeordet til forskjellige kildemeldinger. En enkel måte å oppnå dette på er å m matrisekolonner dannet en enhetsmatrise. Når en hvilken som helst vektor multipliseres med identitetsmatrisen, oppnås den samme vektoren; derfor vil forskjellige meldingsvektorer tilsvare forskjellige vektorer av den systematiske koden.

Matrisekoder kalles også lineære koder. For lineær (n − r, n)-koder med minimum Hamming-avstand d finnes Plotkin nedre grense (Plotkin) for minimum antall sjekkbiter r på n³ 2d − 1,

binær ( En m, n) kode kalles en gruppekode hvis kodeordene danner en gruppe.

Legg merke til at settet med alle binære ord med lengde m danner en kommutativ gruppe med operasjonen av koordinatvis addisjon modulo 2, der relasjonen a a gjelder. Følgelig er settet med meldingsord a med lengde m en kommutativ gruppe.

Blokkkode kalles gruppe, hvis kodeordene danner en gruppe.

Hvis koden er en gruppekode, er den minste avstanden mellom to kodeord lik den minste vekten av ordet som ikke er null.

Dette følger av forholdet d(b Jeg ,b j ) = w(b Jeg + b j ).

Når du bruker en jokertegnkode, blir de og bare de feilene som tilsvarer feilstrenger nøyaktig lik kodeordene uoppdaget.

Slike feillinjer oversetter ett kodeord til et annet.

Derfor er sannsynligheten for at en feil forblir uoppdaget lik summen av sannsynlighetene for alle feilstrenger lik kodeord.

Sett med alle binære ord a = a 1 ... a m lengde m danner en abelsk (kommutativ) gruppe med hensyn til bitvis addisjon.

La E - koding m×n-en matrise som har m × m- en submatrise med en determinant som ikke er null, for eksempel identitet. Så kartleggingen a → a E oversetter en gruppe av alle binære ord med lengde m til en gruppe kodeord av lengde n.

La oss anta at Da får vi

dvs. Derfor en en-til-en-kartlegging av en gruppe binære ord med lengde m ved hjelp av en gitt matrise E bevarer egenskapene til en gruppeoperasjon, som betyr at kodeordene danner en gruppe.

Gruppekodeegenskap: minste kodeavstand mellom kodevektorer er lik minimumsvekten til vektorer som ikke er null. Vekten til kodevektoren er lik antallet enere i kodekombinasjonen.

Det er praktisk å spesifisere gruppekoder ved hjelp av matriser, hvis dimensjon bestemmes av parametrene k og n. Antall rader er k og antall kolonner er n = k+m.

Kodene som genereres av disse matrisene kalles (n, k)-koder, og de tilsvarende matrisene kalles generatorer (generatorer).

I denne artikkelen vi vil snakke om HEngine-algoritmen og implementering av en løsning på problemet med å beregne Hamming-avstanden på store datamengder.

Introduksjon

Hamming-avstanden er antall forskjellige posisjoner for strenger av samme lengde. For eksempel, HD(100; 001) = 2.

Problemet med å beregne Hamming-avstanden ble først stilt av Minsky og Papert i 1969, hvor problemet var å finne alle rader fra en database som er innenfor en gitt Hamming-avstand til spørringen.

En oppgave som dette er utrolig enkel, men å finne den effektiv løsning er fortsatt på agendaen.

Hamming-avstanden er allerede ganske mye brukt til ulike oppgaver, for eksempel søk etter nære duplikater, mønstergjenkjenning, dokumentklassifisering, feilretting, virusdeteksjon osv.

For eksempel foreslo Manku og kolleger en løsning på problemet med duplikatgruppering i webdokumentindeksering basert på beregning av Hamming-avstanden.
Miller og venner foreslo også konseptet med å søke etter sanger basert på et gitt lydfragment.
Lignende løsninger har blitt brukt for problemet med bildehenting og netthinnegjenkjenning, etc.

Beskrivelse av problemet

Det er en database binære strenger T, størrelse n, hvor lengden på hver linje m. Forespurt streng en og den nødvendige Hamming-avstanden k.

Oppgaven går ut på å finne alle strenger som er innenfor avstanden k.

Det opprinnelige konseptet til algoritmen vurderer to varianter av problemet: statisk og dynamisk.

I et statisk problem er avstanden k forhåndsbestemt.
– I dynamisk er tvert imot nødvendig distanse ukjent på forhånd.

Artikkelen beskriver løsningen på kun et statisk problem.

Beskrivelse av HEngine-algoritmen for en statisk oppgave

Denne implementeringen fokuserer på å finne strenger innenfor k <= 10.

Det er tre løsninger på et statisk problem: lineær skanning, spørringsutvidelse og tabellutvidelse.

I dette tilfellet under spørringsutvidelse Dette refererer til generering av alle mulige strengvarianter som passer innenfor en gitt avstand for den originale strengen.
Baseutvidelse data innebærer opprettelse av mange kopier av denne databasen, der enten alle mulige alternativer som oppfyller kravene til den nødvendige avstanden også genereres, eller dataene behandles på annen måte (mer om dette litt senere.).

HEngine bruker en kombinasjon av disse tre teknikkene for å effektivt balansere mellom minne og utførelsestid.

Litt teori

Algoritmen er basert på et lite teorem som sier følgende:

Hvis for to linjer en Og b avstand HD( en, b) <= k, så hvis vi deler linjene en Og b inn i understrenger ved hjelp av metoden rcut ved hjelp av segmenteringsfaktor
r >= ⌊k/2⌋ + 1
det vil definitivt være i det minste q= r − ⌊k/2⌋ understrenger, når deres avstand ikke overstiger én, HD( en Jeg, b Jeg)<= 1.

Trekker ut delstrenger fra basisstrengen ved å bruke metoden rcut utføres i henhold til følgende prinsipper:
Verdien som er navngitt segmenteringsfaktor, som tilfredsstiller betingelsen
r >= ⌊k/2⌋ + 1

Første lengde r − (m mod r) understreng vil ha lengde ⌊ m / r⌋, og de siste m mod r delstrenger ⌈ m/r⌉. Hvor m er lengden på strengen, ⌊ er avrundet til nærmeste bunn, og ⌉ er avrundet til nærmeste over.

Nå det samme, bare med et eksempel:

Gitt to binære strenger med lengde m= 8 biter: A = 11110000 og B = 11010001, avstand mellom dem k = 2.
Velge en segmenteringsfaktor r= 2 / 2 + 1 = 2, dvs. det vil være totalt 2 delstrenger i lengde m/r= 4 biter.

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

Hvis vi nå beregner avstanden mellom de tilsvarende delstrengene, så i det minste q= 2 - 2/2 = 1, én delstreng vil matche eller avstanden deres vil ikke overstige én.

Hva vi ser:
HD(a1; b1) = HD(1111; 1101) = 1
Og
HD(a2; b2) = HD(0000; 0001) = 1

Basestrengens understrenger ble navngitt signaturer.
Signaturer eller understrenger a1 og b1 (a2 og b2, a3 og b3 ..., a r og b r) er kalt kompatibel med hverandre, og hvis antallet forskjellige biter ikke er mer enn én, kalles disse signaturene matchende.

Og hovedideen til HEngine-algoritmen er å forberede databasen på en slik måte å finne matchende signaturer og deretter velge de radene som er innenfor den nødvendige Hamming-avstanden.

Databaseforbehandling

Vi vet allerede at hvis vi deler en streng inn i delstrenger riktig, vil minst én delstreng matche den tilsvarende delstrengen eller antallet forskjellige biter vil ikke overstige én (signaturene vil samsvare).

Dette betyr at vi ikke trenger å foreta et fullstendig søk over alle rader fra databasen, men først må finne de signaturene som matcher, dvs. understrenger vil avvike med maksimalt én.

Men hvordan søke etter understrenger?

Den binære søkemetoden bør gjøre en god jobb med dette. Men det krever at listen over strenger er sortert. Men vi får flere delstrenger fra én linje. For å utføre et binært søk på en liste over understrenger, må hver slik liste sorteres på forhånd.
Derfor foreslår dette en metode for å utvide databasen, dvs. lage flere tabeller, hver for sin egen understreng eller signatur. (Denne tabellen kalles tabell over signaturer. Og samlingen av slike tabeller er sett med signaturer).

Den opprinnelige versjonen av algoritmen beskriver også omorganisering av delstrenger slik at de valgte delstrengene er på første plass. Dette gjøres mer for enkel implementering og for ytterligere optimalisering av algoritmen:

Det er en streng A, som er delt inn i 3 understrenger, a1, a2, a3, den komplette listen over permutasjoner vil være tilsvarende:
a1, a2, a3
a2, a1, a3
a3, a1, a2

Disse signaturtabellene blir deretter sortert.

Gjennomføring av søk

På dette stadiet, etter foreløpig behandling av databasen, har vi flere kopier av de sorterte tabellene, hver for sin egen underrad.

Selvfølgelig, hvis vi først vil finne understrenger, må vi hente signaturer fra den forespurte strengen på samme måte som ble brukt til å lage signaturtabellene.

Vi vet også at de nødvendige understrengene avviker med høyst ett element. Og for å finne dem må du bruke søkeutvidelsesmetoden.

Med andre ord, for den valgte delstrengen er det nødvendig å generere alle kombinasjoner, inkludert denne delstrengen selv, der forskjellen vil være høyst ett element. Antall slike kombinasjoner vil være lik lengden på delstrengen + 1.

Slike handlinger må utføres for alle underrader og for alle tabeller.

Og helt til slutt må du filtrere ut linjene som ikke passer innenfor den angitte Hamming-avstandsgrensen. De. utfør et lineært søk gjennom de funnet strengene og la bare de strengene som oppfyller betingelsen HD( en, b) <= k.

Bloom filter

Hvis filteret, før et binært søk etter en understreng i en tabell, returnerer at understrengen ikke er i den tabellen, er det ingen vits i å utføre søket.

Følgelig må du opprette ett filter for hver signaturtabell.

Forfatterne bemerker også at bruk av Bloom-filteret på denne måten reduserer spørringsbehandlingstiden med gjennomsnittlig 57,8 %. På mine testprøver har et slikt filter praktisk talt ingen effekt på den resulterende driftstiden. Merkbar bare på en tilfeldig generert database.

Nå det samme, bare med et eksempel

Det er en database med binære strenger på 8 bit:
11111111
10000001
00111110

Oppgaven er å finne alle linjer der antall forskjellige biter ikke overstiger 2 til mållinjen 10111111.

Altså nødvendig avstand k = 2.

1. Velg en segmenteringsfaktor.

Basert på formelen velger vi segmenteringsfaktoren r= 2 og det betyr at det bare vil være to delstrenger fra en linje.

2. Lag et sett med signaturer.

Siden antallet understrenger er 2, trenger bare 2 tabeller å opprettes:

3. Vi lagrer understrengene i de aktuelle tabellene mens vi opprettholder en kobling til den opprinnelige kilden.

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

4. Sorter tabellene. Hver for seg.

T1
0011 => 00111110
1000 => 10000001
1111 => 11111111

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

Dette fullfører forbehandlingen. Og la oss starte søket.

5. Vi mottar signaturene til den forespurte strengen.

Den søkte strengen 10111110 er delt inn i signaturer. Det viser seg henholdsvis 1011 og 1100, det første for det første bordet, og det andre for det andre.

6. Generer alle kombinasjoner som avviker med én.
Antall alternativer vil være 5.

6.1 For den første delstrengen 1011:
1011
0 011
11 11
100 1
1010

6.2 For den andre delstrengen 1100:
1100
0 100
10 00
111 0
1101

7. Binært søk.

7.1 For alle genererte varianter av den første delstrengen 1011, utfører vi et binært søk i den første tabellen for en fullstendig match.

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

To understrenger funnet.

7.2 Nå, for alle varianter av den andre delstrengen 1100, utfører vi et binært søk i den andre tabellen.

1100
0100
1000
1110 == 1110 => 00111110
1101

En understreng funnet.

8. Kombiner resultatene til én liste:
00111110
11111111

9. Sjekk lineært for samsvar og filtrer ut de som ikke samsvarer med betingelsen<= 2:

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

Begge strengene tilfredsstiller betingelsen om at ikke mer enn to elementer er forskjellige.

Selv om det utføres et lineært søk på dette stadiet, forventes det at listen over kandidatstrenger ikke vil være stor i det hele tatt.
Under forhold hvor antallet kandidater er stort, foreslås det å bruke den rekursive versjonen av HEngine.

Helt klart

Figur 1 viser et eksempel på hvordan søkealgoritmen fungerer.
For en linjelengde på 64 og en avstandsgrense på 4 er segmenteringsfaktoren 3, tilsvarende kun 3 delstrenger per linje.
Hvor T1, T2 og T3 er signaturtabeller som kun inneholder understrenger B1, B2, B3.

Den forespurte strengen er delt inn i understrenger. Deretter genereres en rekke signaturer for de tilsvarende understrengene. Til slutt utføres et binært søk.

Fig 1. En forenklet versjon av behandling av spørringer til signaturtabeller.

resultater

Gjennomsnittlig kompleksitet for en slik algoritme O(m(Logg n+ 1)), hvor n er det totale antallet rader i databasen, m er antall binære søk, og logg n+ 1 binært søk.
I ekstreme tilfeller kan det overskride lineært. For eksempel gitt q= 1 og når alle rader fra alle signaturtabeller, bortsett fra den siste, samsvarer med den forespurte, så viser det seg O((r - 1)mn(Logg n + 1)).

Det bemerkes at denne tilnærmingen bruker 4,65 mindre minne og er 16 % raskere enn det forrige arbeidet beskrevet i .

Gjennomføring

Alt dette er absolutt fristende, men før du faktisk berører det, er det vanskelig å vurdere skalaen.
En Hengine-prototype ble laget og testet på tilgjengelige reelle data.

Tester$ ./matches 7 data/db/table.txt data/query/face2.txt Lesing av datasettet ........ ferdig. 752420 db-hasjer og 343 søke-hasher. Bygg med 7 hammingsavstand bundet ....... ferdig. Byggetid: 12.964 sekunder. Søkte HEngine-treff ....... fant totalt 100 treff. Hengine-søketid: 0.228 sekunder. Søkte lineære treff ....... fant 100 treff totalt. Lineær spørretid: 6,828 sekunder

Resultatene var oppmuntrende, fordi søk etter 343 hashes fra en database på 752420 tar ~0,2 sekunder, som er 30 ganger raskere enn et lineært søk.

Det ser ut til at vi kunne stoppe her. Men jeg ville virkelig prøve å bruke det på en eller annen måte i et ekte prosjekt.

Ett klikk før ekte applikasjon

Det er en database med bildehasher og en backend i PHP.
Oppgaven var å på en eller annen måte koble sammen funksjonaliteten til HEngine og PHP.
Det ble bestemt å bruke FastCGI, innleggene habrahabr.ru/post/154187/ og habrahabr.ru/post/61532/ hjalp meg mye med dette.

Fra PHP bare ring:

$list = file_get_contents("http://fcgi.local/?" . $hashes);

Som på ca 0,5 sekunder gir resultatet. Når et lineært søk krever 9 sekunder, og gjennom spørringer til MySQL minst 20 sekunder.

Takk til alle som fullførte det.

) i et vektorrom av kodesekvenser, i dette tilfellet er Hamming-avstanden mellom to binære sekvenser (vektorer) og lengde antallet posisjoner der de er forskjellige - i denne formuleringen er Hamming-avstanden inkludert i Dictionary of Algorithms og Datastrukturer fra National Institute of Standards i USA (eng. NIST Dictionary of Algoritms and Data Structures ).

Dermed er Hamming-avstanden mellom vektorene 0 011 1 og 1 010 1 2 (forskjellige biter er markert med rødt). Deretter ble metrikken generalisert til q-ary-sekvenser: for et par strenger "valg" og "gjerde" er Hamming-avstanden lik tre.

Generelt er Hamming-avstanden for objekter og dimensjoner gitt av funksjonen:

Hamming-avstanden har egenskapene til en metrikk, som tilfredsstiller følgende betingelser:

Hammeravstand innen bioinformatikk og genomikk

Litteratur

• Richard W. Hamming. Feildeteksjons- og feilrettingskoder, Bell System Technical Journal 29(2):147-160, 1950.
• Richard Bleichut. Teori og praksis for feilkontrollkoder. M., "Mir", 1986

Linker

• Richard Hamming og begynnelsen på kodingsteori // Virtual Computer Museum

Wikimedia Foundation. 2010.

Se hva «Hamming distance» er i andre ordbøker:

Hamming avstand- Hamming-avstand Avstanden d (u,v) mellom to kodesekvenser u og v av samme lengde, lik antall symboler der de er forskjellige. En blokkkode med minimum Hamming-avstand d lar en oppdage (d 1) og... ...

kodeavstand- Minimum Hamming-distanse tatt over alle lares av forskjellige kodeord i en enhetlig kode. [Samling av anbefalte vilkår. Utgave 94. Teori om informasjonsoverføring. USSRs vitenskapsakademi. Teknisk terminologikomité. 1979] Temateori ... ... Teknisk oversetterveiledning

I feltene matematikk og informasjonsteori er en lineær kode en viktig type blokkkode som brukes i feildeteksjons- og korrigeringsskjemaer. Lineære koder, sammenlignet med andre koder, tillater implementering av mer effektive algoritmer... ... Wikipedia

I feltene matematikk og informasjonsteori er en lineær kode en viktig type blokkkode som brukes i feildeteksjons- og korrigeringsskjemaer. Lineære koder, sammenlignet med andre koder, tillater implementering av mer effektive algoritmer... ... Wikipedia

Deteksjon av feil i kommunikasjonsteknologi er en handling som tar sikte på å overvåke integriteten til data ved registrering/gjengivelse av informasjon eller ved overføring over kommunikasjonslinjer. Feilretting (feilretting) gjenopprettingsprosedyre... ... Wikipedia

Deteksjon av feil i kommunikasjonsteknologi er en handling som tar sikte på å overvåke integriteten til data ved registrering/gjengivelse av informasjon eller ved overføring over kommunikasjonslinjer. Feilretting (feilretting) prosedyre for å gjenopprette informasjon etter... ... Wikipedia

Deteksjon av feil i kommunikasjonsteknologi er en handling som tar sikte på å overvåke integriteten til data ved registrering/gjengivelse av informasjon eller ved overføring over kommunikasjonslinjer. Feilretting (feilretting) prosedyre for å gjenopprette informasjon etter... ... Wikipedia

Deteksjon av feil i kommunikasjonsteknologi er en handling som tar sikte på å overvåke integriteten til data ved registrering/gjengivelse av informasjon eller ved overføring over kommunikasjonslinjer. Feilretting (feilretting) prosedyre for å gjenopprette informasjon etter... ... Wikipedia

Hamming avstand

Den amerikanske matematikeren Hamming studerte hva denne koden avhenger av, om den vil oppdage feil og når den kan rette dem. Intuitivt er det klart at dette avhenger av hvordan kodeordene er separert fra hverandre og hvor mange feil som kan forekomme i det overførte ordet. Vi vil nå formalisere følgende idé. Ved koding er det nødvendig å koordinere antall mulige feil i det overførte kodeordet slik at når det overførte kodeordet endres, forblir det nærmere det opprinnelige kodeordet enn noe annet kodeord.

Definisjon 13.1. Tenk på settet med alle binære ord i alfabetet I= (0,1) lengde T avstand d(x, på), som er lik antall ikke-matchende posisjoner for disse ordene. For eksempel For ord X = 011101, på= 101010 avstand er d(x, y) = 5. Denne avstanden kalles Hamming avstand .

Det kan vises at Hamming-avstanden tilfredsstiller aksiomene til metrisk rom:

1) d(x, på) ≥ 0, d(x, på) = 0 hvis og bare hvis X = y;

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

3) d(x, på) ≤ d(x, z) +d(z, på) - trekantulikhet.

Teorem 13.1(om deteksjonskode). Koden oppdager i tilfellet når det overførte ordet ikke inneholder mer enn k

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

Teorem 13.2(om korrigeringskoden.). Koden korrigerer alle feil i tilfellet når det overførte ordet ikke inneholder mer enn k feil, hvis og bare hvis den minste avstanden mellom kodeord

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

Bevis. Bevisene for disse teoremene er like. Derfor vil vi bare bevise det siste teoremet.

Tilstrekkelighet. La for alle kodeord vi har d(b 1, b 2) ≥ 2k+ 1. Hvis, når du sender et kodeord b 1 ikke mer skjedde k feil, så for det aksepterte ordet med vi har d(b 1, c) ≤ k. Men fra trekanten ulikhet for alle andre kodeord b 2 vi har d(b 1, Med) + d(c, b 2) ≥ d(b 1, b 2) ≥ 2 k+ 1. Derfor, fra det mottatte ordet til et hvilket som helst annet kodeord, er avstanden d(c, b 2) ≥ k + 1, dvs. mer enn før b 1. Derfor, ifølge det aksepterte ordet Med du kan definitivt finne det nærmeste kodeordet b 1 og deretter dekode den.

Nødvendighet. Fra det motsatte. Anta at minimumsavstanden mellom kodeord er mindre enn 2 k+ 1. Så er det to kodeord, avstanden mellom dem vil være d(b 1, b 2) ≤ 2 k. La når du overfører ordet b 1 akseptert ord Med er plassert mellom ordene b 1, b 2i har akkurat k feil. Deretter d(c, b 1) = k, d (c, b 2) = d(b 1, b 2) – d(c, b 1) ≤ k. Fra ordet c er det altså umulig å entydig rekonstruere kodeordet som ble overført, b 1eller b 2. Vi kom til en motsetning.

Eksempel 13.3 . Tenk på følgende fem-bits koder for ord med lengde 2 i alfabetet I = {0,1}:

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

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

Minimumsavstanden mellom forskjellige kodeord er d(bi, bj) = 3. I kraft av det første teoremet om deteksjonskoden, er denne koden i stand til å oppdage ikke mer enn to feil i et ord. I kraft av det andre teoremet er koden i stand til å korrigere maksimalt én feil i et ord.

Gruppekoder

La oss se nærmere på kodene til ord i alfabetet I= (0, 1). Hvis for ord av lengde T kodeord med lengde brukes n, så kaller vi slike koder ( T , P)-koder. Total lengde på ord m tilsvarer 2 m. Å sette ( T , P)-kode, kan du liste kodeord for alle mulige ord med lengde m, som i forrige eksempel. En mer økonomisk måte å spesifisere kodeord på er en matriseoppgave.

I dette tilfellet er genereringsmatrisen spesifisert G= ∣∣ gij∣∣ rekkefølge T × P fra 0 og 1. Kodeord bestemmes hver gang for ord EN = EN 1en 2... på ved å multiplisere dette ordet til venstre, som en vektor, med den genererende matrisen

Her er addisjon definert modulo 2. For at ulike ord skal korrespondere med ulike kodeord er det nok å ha i matrisen G enhetsbasis mindre av ordre T, for eksempel den helt til venstre.

Eksempel 13.4 . Tenk på genereringsmatrisen

Denne matrisen definerer (3, 4) koden. I dette tilfellet er de tre første tegnene i kodeordet informative, og det fjerde er en kontroll. Det er lik 0 hvis det er et partall av enere i kildeordet, og 1 hvis det er et oddetall av enere. For eksempel for ordet EN= 101 kode vil være b= aG= 1010. Minimum Hamming-avstand mellom kodeord er d(bi, bj) = 2. Derfor er dette kode som oppdager en engangsfeil.

Definisjon 13.2. Koden kalles gruppe , hvis settet med alle kodeord danner en gruppe. Antall enheter i ordet a kalles vekter ord og er betegnet If b- kodeord og ord mottatt i kommunikasjonskanalen Med = b + e, deretter ordet e kalt vektor av feil .

Teorem 13.3. La det være en gruppe ( T , P)-kode. Deretter den kommutative gruppen TIL av alle kodeord er en undergruppe av den kommutative gruppen MED alle ord av lengde P, som kan mottas i kommunikasjonskanalen. Den minste avstanden mellom kodeord er lik den minste vekten til et kodeord som ikke er null og

Tenk på faktorgruppen S/K. Cosets her vil bli bestemt av skiftet e + b, b∈ K.

Som representant for coset-klassen velger vi elementet med minst vekt. Vi vil kalle slike elementer tilstøtende klasseledere .

Hvis ledere tolkes som feilvektorer, er hver tilstøtende klasse et sett med forvrengte ord i en kommunikasjonskanal med en fast feilvektor, spesielt når e= 0 har vi en tilstøtende klasse med ord uten forvrengninger, dvs. settet av alle kodeord. Prosessen med ordkorreksjon og dekoding Med består i å søke etter den tilstøtende klassen som ordet tilhører Med = e + b. Feilvektor e bestemmer antall og plassering av feil, kodeord b bestemmer korrigeringen av det mottatte ordet.

For å lette søket etter et coset og dermed feilvektoren, foreslo Hamming å bruke gruppekoder med spesielle genererende matriser.

Hamming-koder

La oss vurdere konstruksjonen av Hamming ( T , P)-kode med minste kodeordvekt lik 3, dvs. en kode som retter en feil.

La oss sette P = 2 r– 1 og la hvert kodeord inneholde r kontrolltegn, og T tegn ( T = P – r= 2 r– 1– r) - informativ, r≥ 2, for eksempel (1, 3) kode, (4, 7) kode osv. Dessuten, i hvert kodeord b= b 1b 2... b s symboler med indekser lik en potens på 2 vil være kontrollsymboler, og resten vil være informasjonssymboler. For eksempel for en (4, 7) kode i kodeordet b= b 1b 2b 3b 4b 5b 6b 7 tegn b 1b 2b 4 vil være kontroll seg, og symbolene b 3b 5b 6b 7- informativ. For å spesifisere generatormatrisen G Hammings ( T , P)-kode, vurdere hjelpematrisen M rekkefølge r× P, Hvor P = 2 r– 1, slik at i hver j matrisekolonne M det vil være binære symboler j, for eksempel for (4, 7)-koden matrisen M vil være 3 × 7:

Vi definerer settet av alle kodeord som sett med løsninger til et homogent system av lineære algebraiske ligninger av formen

b MT= 0.

For eksempel, for en (4, 7) kode vil et slikt system være:

La oss velge en naturlig basis mindre av systemet b MT= 0, står i kolonner med tall lik potensen 2. Dermed deler vi variablene inn i grunnleggende (kode) og fri (informasjon). Nå, etter å ha definert gratis variabler, er det enkelt å skaffe grunnleggende. La oss finne det grunnleggende systemet m= P – r løsninger av dette homogene systemet. Da er enhver løsning på systemet en lineær kombinasjon av disse m beslutninger. Skriv derfor ut linje for linje m løsninger av det grunnleggende systemet i form av en matrise G størrelse m× P, får vi genereringsmatrisen til Hamming-gruppen ( T , P) kode, for eksempel, for en (4, 7) kode, vil det grunnleggende løsningssystemet være 4 = 7 – 3 av følgende løsninger av et homogent system:

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

Enhver lineær kombinasjon av disse løsningene vil være en løsning, dvs. et kodeord. La oss komponere en genererende matrise fra disse grunnleggende løsningene

Nå ifølge ethvert ord EN lengde T= 4 enkle å beregne kodeord b lengde P= 7 ved å bruke generatormatrisen b= aG. Samtidig symbolene b 3, b 5, b 6, b 7 vil være informativ. De sammenfaller med EN 1, EN 1, EN 3, EN 4. Symboler b 1, b 2, b 4 vil være kontroll.

Konklusjon. Hamming-koder er praktiske fordi cosets lett kan bestemmes under dekoding. La ordet mottatt over kommunikasjonskanalen være Med = e + b, Hvor e- feil, b- et kodeord. Multipliser det deretter med hjelpematrisen cMT= (e + b)MT= eM T. Hvis eM T= 0, deretter ordet Med- kode og vi vurderer: det er ingen feil. Hvis eM T≠ 0, deretter ordet e definerer en feil.

Husk at de konstruerte Hammings ( T , P)-kode identifiserer én feil. Derfor feilvektoren e inneholder en enhet i Jeg stillinger. Dessuten nummeret Jeg posisjon oppnås i binær representasjon som resultat eM T, sammenfallende med Jeg matrisekolonne M. Det gjenstår å endre symbolet Jeg i ordet c mottatt over kanalen, kryss ut kontrolltegnene og skriv ned det dekodede ordet.

La for eksempel det aksepterte ordet være Med= 1100011 for (4, 7) Hamming-koden. La oss multiplisere dette ordet med matrisen M T. Vi får

(1100011)M T=(010).

Derfor er det en feil i det andre tegnet. Derfor blir kodeordet b= 1000011. Kryss av kontrolltegnene b 1, b 2, b 4.Det dekodede ordet vil være EN = 0011.

Selvfølgelig, hvis feilen ble gjort i mer enn ett tegn, vil ikke denne koden rette den.