Afstand mellem kodeord. Beskrivelse af HEngine-algoritmen til en statisk opgave

Side 1

Hammerafstand mellem to sekvenser lige lang svarer til antallet af positioner besat af ikke-matchende elementer. I tilfælde af sekvenser af forskellig længde er Hamming-afstanden defineret som det mindste antal positioner, der er optaget af ikke-matchende elementer ved.

Hammerafstand d(u,v) mellem to ord u og v samme længde lig med antallet af uoverensstemmende cifre i disse ord. Det bruges i teorien om blokkoder (V.

Ved at bruge de metriske egenskaber for Hamming-afstanden bekræftes det direkte, at /l er en metrik på Xt, men ikke er en metrik på sættet af blandede periodiske sekvenser.

Denne nærhedsfunktion svarer til Hamming-afstanden.

Metrikken p i KLOP-algoritmen er specificeret af Hamming-afstanden.

Hvis søgeproceduren kan finde en position, hvor Hamming-afstanden er nul, vil problemet være løst.

En sammenligning af de uklare undergrupper B og B3, grader af uklarhed samt Hamming-afstanden viser, at de uklare undergrupper, der overvejes, er forskellige. Men hvis vi tager elementet m2 G Uz som den beregnede værdi, hvis grad hører til den resulterende fuzzy delmængde er maksimal, så kan brugen af fuzzy relationen R beregnet på denne måde retfærdiggøres. Sammen med det faktum, at det med denne tilgang er muligt at beskrive ikke-lineariteten af forholdet mellem den maksimale temperatur i reaktorens anden zone og polyethylensmeltestrømningshastigheden, tager denne metode ikke højde for den ikke-stationære natur af reaktoren. proces med at opnå LDPE, som er forbundet med ændringer i den teknologiske process karakteristika.

Overførselsfunktionen af denne kode indikerer, at der er den eneste måde med Hamming-afstand d - fra stien for alle nuller, som smelter sammen med stien for alle nuller ved en given knude. Fra tilstandsdiagrammet vist i fig. 8.2.6, eller espalierdiagrammet vist i fig. 8.2.5, er det tydeligt, at stien fra d6 er acbe. Igen fra tilstandsdiagrammet eller gitteret ser vi, at disse stier er acdbe og acbcbe. Det tredje led i (8.1.2) angiver, at der er fire stier med afstand d 0 og så videre. Dermed, Transmissionsfunktion giver os afstandsegenskaberne for en foldningskode.

Dette resultat stemmer overens med den observation, at en sti med alle nuller (/0) har en Hamming-afstand på d3 fra den modtagne sekvens, mens en sti på /1 har en Hamming-afstand på d5 fra den modtagne sti. Hamming-afstand er således en ækvivalent målestok for hård beslutningsdekodning.

På et sæt binære ord af længde m afstand d(a,b) mellem ordene a og b er antallet af ikke-matchende positioner af disse ord, for eksempel: afstanden mellem ordene a = 01101 og b = 00111 er 2.

Begrebet defineret på denne måde kaldes Hamming-afstanden.

Den opfylder følgende afstandsaksiomer:

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

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

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

Vægten w(a) af et ord a er antallet af ener blandt dets koordinater. Så er afstanden mellem ordene a og b vægten af deres sum a b: d(a,b)=w(a b) , hvor symbolet  angiver operationen af koordinatmæssig addition modulo 2. Intuitivt er koden bedre egnet til fejldetektion og korrektion, jo mere forskellige kodeordene er. Begrebet Hamming-afstand giver os mulighed for at afklare dette.

Sætning For at en kode kan detektere fejl i k (eller færre) positioner, er det nødvendigt og tilstrækkeligt, at den mindste afstand mellem kodeord er  k + 1.

Beviset for denne sætning svarer til beviset for følgende udsagn.

Sætning. For at koden kan rette alle fejl i k (eller færre) positioner, er det nødvendigt og tilstrækkeligt, at den mindste afstand mellem kodeord er  2k + 1.

32. Sætning om koders korrigerende evne.

Koder, der automatisk kan rette fejl, kaldes selvkorrigerende. For at bygge en selvkorrigerende kode designet til at rette enkelte fejl, er et kontrolciffer ikke nok. Som det fremgår af det følgende, skal antallet af kontrolbit k vælges således, at uligheden 2k≥k+m+1eller k≥log2(k+m+1) er opfyldt, hvor m er antallet af grundlæggende binære bits. af kodeordet. I øjeblikket er binære blokkorrektionskoder af størst interesse. Ved brug af sådanne koder transmitteres information i form af blokke af samme længde, og hver blok kodes og afkodes uafhængigt af hinanden. I næsten alle blokkoder kan tegn opdeles i information og verifikation.

De vigtigste egenskaber ved selvkorrigerende koder er:

1. Antal tilladte og forbudte kombinationer. Hvis n er antallet af symboler i blokken, r er antallet af kontrolsymboler i blokken, k er antallet af informationssymboler, så er 2n antallet af mulige kodekombinationer, 2k er antallet af tilladte kodekombinationer, 2n −2k er antallet af forbudte kombinationer.

2. Kode redundans. Værdien rn kaldes redundansen af korrektionskoden.

3. Minimum kodeafstand. Den mindste kodeafstand d er det mindste antal forvrængede symboler, der kræves for at skifte fra en tilladt kombination til en anden.

4. Antal fejl opdaget og rettet. Hvis g er antallet af fejl, som koden kan rette, så er det nødvendigt og tilstrækkeligt, at d≥2g+1

5. Korrigerende muligheder for koder.

33. Matrixkodning. Gruppekoder.

Når kodningsskemaet eksplicit specificeres i ( m, n)-kode skal angive 2 m kodeord, hvilket er meget ineffektivt.

En økonomisk måde at beskrive et kodningsskema på er matrixkodningsteknikken.

Tidligere blev hvert indkodningsskema beskrevet af tabeller, der specificerede et kodeord af længde n for hvert kildeord af længde m. For lange blokke kræver denne metode en stor mængde hukommelse og er derfor upraktisk. For eksempel for ( 16, 33 ) kode vil kræve 33 * 2 16 = 2.162.688 bit.

Kræver meget mindre hukommelse matrix kodning. Lade E dimensionsmatrix m×n, bestående af elementer e ij , hvor jeg er linjenummeret, og j - kolonnenummer. Hvert af matrixelementerne e ij kan være enten 0 eller 1. Kodning implementeres af operationen b = aE eller hvor kodeord betragtes som vektorer, dvs. som rækkematricer af størrelse 1×n.

Kodning bør ikke tildele det samme kodeord til forskellige kildemeddelelser. En enkel måde at opnå dette på er at m matrix søjler dannede en enhedsmatrix. Når en hvilken som helst vektor multipliceres med identitetsmatrixen, opnås den samme vektor; derfor vil forskellige meddelelsesvektorer svare til forskellige vektorer af den systematiske kode.

Matrixkoder kaldes også lineære koder. Til lineær (n − r, n)-koder med minimum Hamming-afstand d eksisterer Plotkin nedre bund (Plotkin) for mindste mængde kontrol bits r på n³ 2d − 1,

binær ( En m, n) kode kaldes en gruppekode, hvis dens kodeord danner en gruppe.

Bemærk, at mængden af alle binære ord med længden m danner en kommutativ gruppe med operationen af koordinatmæssig addition modulo 2, hvori relationen a a gælder. Følgelig er sættet af meddelelsesord a med længden m en kommutativ gruppe.

Blokkode kaldes gruppe, hvis dets kodeord danner en gruppe.

Hvis koden er en gruppekode, så er den mindste afstand mellem to kodeord mindste vægt ikke-nul ord.

Dette følger af forholdet d(b jeg , b j ) = w(b jeg + b j ).

Når du bruger en jokerkode, bliver de og kun de fejl, der svarer til fejlstrenge, der nøjagtigt svarer til kodeordene, uopdaget.

Sådanne fejllinjer oversætter et kodeord til et andet.

Derfor er sandsynligheden for, at en fejl forbliver uopdaget, lig med summen af sandsynligheden for alle fejlstrenge, der er lig med kodeord.

Sæt af alle binære ord a = a 1 ... a m længde m danner en abelsk (kommutativ) gruppe med hensyn til bitvis addition.

Lade E - kodning m×n-en matrix, der har m × m- en submatrix med en ikke-nul determinant, for eksempel identitet. Derefter kortlægningen a → a E oversætter en gruppe af alle binære ord af længde m til en gruppe kodeord af længde n.

Lad os antage, at Så for vi får

dvs. Derfor en en-til-en kortlægning af en gruppe af binære ord af længde m ved hjælp af en given matrix E bevarer egenskaberne for en gruppeoperation, hvilket betyder, at kodeordene danner en gruppe.

Gruppekodeegenskab: den mindste kodeafstand mellem kodevektorer er lig med minimumsvægten af vektorer, der ikke er nul. Vægten af kodevektoren er lig med antallet af ener i kodekombinationen.

Det er praktisk at specificere gruppekoder ved hjælp af matricer, hvis dimension er bestemt af parametrene k og n. Antallet af rækker er k og antallet af kolonner er n = k+m.

Koderne genereret af disse matricer kaldes (n, k)-koder, og de tilsvarende matricer kaldes generatorer (generatorer).

Hammerafstand

Den amerikanske matematiker Hamming undersøgte, hvad der bestemmer denne kode om den vil opdage fejl, og hvornår den kan rette dem. Intuitivt er det klart, at dette afhænger af, hvordan kodeordene er adskilt, og hvor mange fejl der kan forekomme i overførte ord. Vi vil nu formalisere følgende idé. Ved indkodning skal I aftale nummeret mulige fejl i det transmitterede kodeord, således at når det transmitterede kodeord ændres, forbliver det tættere på det originale kodeord end noget andet kodeord.

Definition 13.1. Overvej mængden af alle binære ord i alfabetet I= (0,1) længde T afstand d(x, på), hvilket er lig med antallet af ikke-matchende positioner for disse ord. For eksempel For ord x = 011101, på= 101010 afstand er d(x, y) = 5. Denne afstand kaldes Hammerafstand .

Det kan vises, at Hamming-afstanden opfylder aksiomer for metrisk rum:

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

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

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

Sætning 13.1(om detektionskode). Koden detekterer i det tilfælde, hvor det transmitterede ord ikke indeholder mere end k

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

Sætning 13.2(om rettelseskoden.). Koden retter alle fejl i det tilfælde, hvor det transmitterede ord ikke indeholder mere end k fejl, hvis og kun hvis den mindste afstand mellem kodeord

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

Bevis. Beviserne for disse teoremer er ens. Derfor vil vi kun bevise den sidste sætning.

Tilstrækkelighed. Lad os for alle kodeord, vi har d(b 1, b 2) ≥ 2k+ 1. Hvis, når du sender et kodeord b 1 skete der ikke mere k fejl, så for det accepterede ord med vi har d(b 1, c) ≤ k. Men fra trekanten ulighed for ethvert andet kodeord b 2 vi har d(b 1, Med) + d(c, b 2) ≥ d(b 1, b 2) ≥ 2 k+ 1. Derfor er afstanden fra det modtagne ord til ethvert andet kodeord d(c, b 2) ≥ k+ 1, dvs. mere end tidligere b 1. Derfor ifølge det accepterede ord Med du kan helt sikkert finde det nærmeste kodeord b 1 og derefter afkode den.

Nødvendighed. Fra det modsatte. Antag, at minimumsafstanden mellem kodeord er mindre end 2 k+ 1. Så er der to kodeord, afstanden mellem dem vil være d(b 1, b 2) ≤ 2 k. Lad, når du overfører ordet b 1 accepteret ord Med er placeret mellem ordene b 1, b 2i har præcis k fejl. Derefter d(c, b 1) = k, d (c, b 2) = d(b 1, b 2) – d(c, b 1) ≤ k. Ud fra ordet c er det således umuligt entydigt at rekonstruere kodeordet, der blev transmitteret, b 1 eller b 2. Vi kom til en modsigelse.

Eksempel 13.3 . Overvej følgende fem-bit koder for ord med længde 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.

Minimumsafstanden mellem forskellige kodeord er d(bi, bj) = 3. I kraft af den første sætning om detektionskoden er denne kode i stand til ikke at detektere mere end to fejl i et ord. I kraft af den anden sætning er koden i stand til at rette højst én fejl i et ord.

Gruppekoder

Lad os se nærmere på koderne for ord i alfabetet I= (0, 1). Hvis for ord af længde T kodeord af længde bruges n, så kalder vi sådanne koder ( T , P)-koder. Samlet ordlængde m er lig med 2 m. At indstille ( T , P)-kode, kan du liste kodeord for alle mulige ord længde m, som i det foregående eksempel. En mere økonomisk måde at specificere kodeord på er en matrixopgave.

I dette tilfælde er den genererende matrix specificeret G= ∣∣ gij∣∣ rækkefølge T × P fra 0 og 1. Kodeord bestemmes hver gang for ord EN = EN 1-en 2... på ved at gange dette ord til venstre, som en vektor, med den genererende matrix

Her defineres addition modulo 2. For at forskellige ord svarede forskellige kodeord, er det nok at have i matrixen G enhedsbasis mindre af ordre T, for eksempel den yderste venstre.

Eksempel 13.4 . Overvej den genererende matrix

Denne matrix definerer (3, 4) koden. I dette tilfælde er de første tre tegn i kodeordet informative, og det fjerde er et kontroltegn. Det er lig med 0 if lige tal enheder i det oprindelige ord, og 1 if ulige tal enheder. For eksempel for ordet EN= 101 kode vil være b= aG= 1010. Den mindste Hamming-afstand mellem kodeord er d(bi, bj) = 2. Derfor er dette kode, der registrerer en engangsfejl.

Definition 13.2. Koden hedder gruppe , hvis sættet af alle kodeord danner en gruppe. Antallet af enheder i ordet a kaldes vægte ord og betegnes If b- kodeord og ord modtaget i kommunikationskanalen Med = b + e, så ordet e hedder vektor af fejl .

Sætning 13.3. Lad der være en gruppe ( T , P)-kode. Derefter den kommutative gruppe TIL af alle kodeord er en undergruppe af den kommutative gruppe MED alle ord af længde P, som kan modtages i kommunikationskanalen. Den mindste afstand mellem kodeord er lig med den mindste vægt af et kodeord, der ikke er nul og

Overvej faktorgruppen S/K. Cosets her vil blive bestemt af skiftet e + b, b∈ K.

Som repræsentant for coset-klassen vælger vi det element med mindst vægt. Vi vil kalde sådanne elementer tilstødende klasseledere .

Hvis ledere fortolkes som fejlvektorer, så er hver tilstødende klasse et sæt forvrængede ord i en kommunikationskanal med en fast fejlvektor, især når e= 0 har vi en tilstødende klasse af ord uden forvrængninger, dvs. mængden af alle kodeord. Processen med ordkorrektion og afkodning Med består i at søge efter den tilstødende klasse, som ordet tilhører Med = e + b. Fejlvektor e bestemmer antallet og placeringen af fejl, kodeord b bestemmer rettelsen af det modtagne ord.

For at lette søgningen efter et coset og dermed fejlvektoren foreslog Hamming at bruge gruppekoder med specielle genereringsmatricer.

Hamming koder

Lad os overveje konstruktionen af Hamming ( T , P)-kode med den mindste kodeordsvægt lig med 3, dvs. en kode, der retter en fejl.

Lad os sætte P = 2 r– 1 og lad hvert kodeord indeholde r kontroltegn, og T tegn ( T = P – r= 2 r– 1– r) - informativ, r≥ 2, for eksempel (1, 3) kode, (4, 7) kode osv. Desuden i hvert kodeord b= b 1b 2... b p symboler med indekser, lige grader 2 vil være kontrol, og resten vil være informativ. 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 kontrol dem, og symbolerne b 3b 5b 6b 7- oplysende. For at specificere generatormatrixen G Hammings ( T , P)-kode, overveje hjælpematrix M bestille r× P, Hvor P = 2 r– 1, sådan at der i hver j matrix kolonne M der vil være binære symboler j, for eksempel for (4, 7)-koden matrixen M vil være 3 × 7:

Vi definerer mængden af alle kodeord som et sæt af løsninger homogent system lineær algebraiske ligninger venlig

b MT= 0.

For eksempel, for en (4, 7) kode ville et sådant system være:

Lad os vælge en naturlig basis mindre af systemet b MT= 0, stående i kolonner med tal svarende til potensen 2. Således opdeler vi variablerne i basis (kode) og fri (information). Nu, efter at have defineret gratis variabler, er det nemt at få grundlæggende. Lad os finde det grundlæggende system m= P – r løsninger af dette homogene system. Så er enhver løsning til systemet en lineær kombination af disse m beslutninger. Skriv derfor linje for linje m løsninger af grundsystemet i form af en matrix G størrelse m× P, får vi den genererende matrix for Hamming-gruppen ( T , P)-kode, for eksempel for (4, 7)-kode grundlæggende system løsninger vil der være 4 = 7 – 3 følgende løsninger af et homogent system:

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

Enhver lineær kombination af disse løsninger vil være en løsning, dvs. et kodeord. Lad os sammensætte en genererende matrix ud fra disse grundlæggende løsninger

Nu ifølge ethvert ord EN længde T= 4 let at beregne kodeord b længde P= 7 ved hjælp af generatormatricen b= aG. Samtidig er symbolerne b 3, b 5, b 6, b 7 vil være oplysende. De falder sammen med EN 1, EN 1, EN 3, EN 4.Symboler b 1, b 2, b 4 vil være kontrol.

Konklusion. Hamming-koder er praktiske, fordi cosets let bestemmes under afkodning. Lad ordet modtaget over kommunikationskanalen være Med = e + b, Hvor e- fejl, b- et kodeord. Derefter ganges det med hjælpematrixen cMT= (e + b)MT= eM T. Hvis eM T= 0, derefter ordet Med- kode og vi overvejer: der er ingen fejl. Hvis eM T≠ 0, derefter ordet e definerer en fejl.

Husk, at de konstruerede Hammings ( T , P)-kode identificerer én fejl. Derfor fejlvektoren e indeholder en enhed i jeg stillinger. Desuden antallet jeg position opnås i binær repræsentation som resultat eM T, sammenfaldende med jeg matrix kolonne M. Det er tilbage at ændre symbolet jeg i ordet c modtaget over kanalen, streg kontroltegnene ud og skriv det afkodede ord ned.

Lad for eksempel det accepterede ord være Med= 1100011 for (4, 7) Hamming-koden. Lad os gange dette ord med matrixen M T. Vi får

(1100011)M T=(010).

Derfor er der en fejl i det andet tegn. Derfor bliver kodeordet b= 1000011. Kryds kontroltegnene b 1, b 2, b 4.Det afkodede ord vil være EN = 0011.

Selvfølgelig, hvis fejlen blev lavet i mere end ét tegn, så vil denne kode ikke rette den.

) V vektor rum kodesekvenser, i dette tilfælde er Hamming-afstanden mellem to binære sekvenser (vektorer) og længden antallet af positioner, hvor de er forskellige - i denne formulering er Hamming-afstanden inkluderet i Dictionary of Algorithms and Data Structures Nationalinstituttet amerikanske standarder ( engelsk NIST Dictionary of Algoritms and Data Structures ).

Således er Hamming-afstanden mellem vektorerne 0 011 1 og 1 010 1 lig med 2 (forskelle er markeret med rødt stykker). Efterfølgende blev metrikken generaliseret til q-ary-sekvenser: for et par strenge "valg" og "hegn" er Hamming-afstanden lig med tre.

I generel opfattelse Hamming-afstanden for objekter og dimensioner er givet af funktionen:

Hamming-afstanden har egenskaberne som en metrik, der opfylder følgende betingelser:

Hammerafstand ind bioinformatik Og genomik

Litteratur

Richard W. Hamming. Fejldetektering og fejlretningskoder, Bell System Technical Journal 29(2):147-160, 1950.
Richard Bleichut. Teori og praksis for fejlkontrolkoder. M., "Mir", 1986

Links

Richard Hamming og begyndelsen på kodningsteori // Virtual Computer Museum

Wikimedia Foundation. 2010.

Se, hvad "Hamming distance" er i andre ordbøger:

Hammerafstand- Hammerafstand Afstand d (u,v) mellem to kodesekvenser u og v af samme længde, lig med tallet karakterer, hvor de er forskellige. En blokkode med en minimum Hamming-afstand d gør det muligt at detektere (d 1) og... ...

kode afstand- Minimum Hamming distance overtaget alle baner af forskellige kodeord i en ensartet kode. [Samling af anbefalede vilkår. Udgave 94. Teori om informationstransmission. USSR's Videnskabsakademi. Teknisk terminologiudvalg. 1979] Emneteori... ... Teknisk oversættervejledning

Inden for matematik og informationsteori er en lineær kode vigtig type blokkode, der bruges i fejlsøgnings- og korrektionsskemaer. Lineære koder, sammenlignet med andre koder, tillader implementering af mere effektive algoritmer... ... Wikipedia

Inden for matematik og informationsteori er en lineær kode en vigtig type blokkode, der bruges i fejldetektions- og korrektionsskemaer. Lineære koder, sammenlignet med andre koder, tillader implementering af mere effektive algoritmer... ... Wikipedia

Detektering af fejl i kommunikationsteknologi er en handling, der har til formål at overvåge integriteten af data, når der optages/gengives information, eller når den transmitteres over kommunikationslinjer. Fejlrettelse (fejlrettelse) gendannelsesprocedure... ... Wikipedia