Hamming kode - Hamming code

Binære Hamming -koder
Hamming -koden (7,4) (med r = 3 )
Opkaldt efter	Richard W. Hamming
Klassifikation
Type	Lineær blokkode
Bloklængde	2 r - 1 hvor r ≥ 2
Beskedlængde	2 r - r - 1
Sats	1 - r/(2 r - 1)
Afstand	3
Alfabetstørrelse	2
Notation	[2 r - 1, 2 r - r - 1, 3] 2 -kode
Ejendomme
perfekt kode
v t e

Inden for datalogi og telekommunikation er Hamming-koder en familie af lineære fejlkorrigerende koder . Hamming-koder kan registrere en-bit og to-bit fejl, eller rette en-bit fejl uden at detektere ukorrigerede fejl. I modsætning hertil kan den simple paritetskode ikke rette fejl og kan kun registrere et ulige antal bits ved fejl. Hamming -koder er perfekte koder , det vil sige, at de opnår den højest mulige rate for koder med deres bloklængde og minimumsafstand på tre. Richard W. Hamming opfandt Hamming -koder i 1950 som en måde til automatisk at rette fejl, der blev indført af stansede kortlæsere. I sit originale papir uddybede Hamming sin generelle idé, men fokuserede specifikt på Hamming -koden (7,4) , der tilføjer tre paritetsbit til fire bits data.

I matematiske termer er Hamming -koder en klasse af binær lineær kode. For hvert helt tal r ≥ 2 er der en kode med bloklængde n = 2 ^r - 1 og meddelelseslængde k = 2 ^r - r - 1 . Derfor er frekvensen af ​​Hamming -koder R = k / n = 1 - r / (2 ^r - 1) , hvilket er den højest mulige for koder med en minimumsafstand på tre (dvs. det minimale antal bitændringer, der er nødvendige for at gå fra enhver kodeord til ethvert andet kodeord er tre) og bloklængde 2 ^r - 1 . Den paritet-kontrol matrix af en Hamming-kode konstrueres, idet alle kolonner af længde r , som er ikke-nul, hvilket betyder, at den dobbelte kode af Hamming koden er den forkortede Hadamard kode . Paritetskontrolmatrixen har den egenskab, at to kolonner er parvis lineært uafhængige .

På grund af den begrænsede redundans, som Hamming -koder tilføjer til dataene, kan de kun opdage og rette fejl, når fejlprocenten er lav. Dette er tilfældet i computerhukommelse (normalt RAM), hvor bitfejl er ekstremt sjældne, og Hamming -koder er meget udbredt, og et RAM med dette korrektionssystem er et ECC RAM ( ECC -hukommelse ). I denne sammenhæng bruges ofte en udvidet Hamming -kode med en ekstra paritetsbit. Udvidede Hamming-koder opnår en Hamming-afstand på fire, hvilket gør det muligt for dekoderen at skelne mellem, når der højst opstår en en-bit fejl, og når der opstår to-bit fejl. I denne forstand er udvidede Hamming-koder enkeltfejlkorrigering og dobbeltfejlsdetektering, forkortet SECDED .

Historie

Richard Hamming , opfinderen af ​​Hamming-koder, arbejdede på Bell Labs i slutningen af ​​1940'erne på Bell Model V- computeren, en elektromekanisk relæbaseret maskine med cyklustider i sekunder. Input blev indført på stanset papirbånd , syv ottendedele af en tomme bredt, som havde op til seks huller pr. Række. I løbet af hverdage, hvor der blev registreret fejl i relæerne, stoppede maskinen og blinkede lys, så operatørerne kunne rette op på problemet. I perioder med efterarbejde og i weekender, hvor der ikke var nogen operatører, gik maskinen simpelthen videre til det næste job.

Hamming arbejdede i weekenden og blev stadig mere frustreret over at skulle genstarte sine programmer fra bunden på grund af opdagede fejl. I et optaget interview sagde Hamming: "Og så sagde jeg: 'Damn it, hvis maskinen kan opdage en fejl, hvorfor kan den så ikke finde fejlens position og rette den?'". I løbet af de næste par år arbejdede han på problemet med fejlkorrektion og udviklede en stadig mere kraftfuld række algoritmer. I 1950 offentliggjorde han det, der nu er kendt som Hamming -kode, som stadig er i brug i dag i applikationer såsom ECC -hukommelse .

Koder forud for Hamming

En række simple fejldetekterende koder blev brugt før Hamming-koder, men ingen var lige så effektive som Hamming-koder i samme overhead af rummet.

Paritet

Paritet tilføjer en enkelt bit, der angiver, om antallet af dem (bit-positioner med værdier på en) i de foregående data var lige eller ulige . Hvis et ulige antal bits ændres i transmissionen, ændrer meddelelsen paritet, og fejlen kan registreres på dette tidspunkt; den bit, der ændrede sig, kan dog have været selve paritetsbitten. Den mest almindelige konvention er, at en paritetsværdi på en angiver, at der er et ulige antal en i dataene, og en paritetsværdi på nul angiver, at der er et lige antal af dem. Hvis antallet af bits, der er ændret, er lige, vil checkbiten være gyldig, og fejlen vil ikke blive opdaget.

Desuden angiver paritet ikke, hvilken bit der indeholdt fejlen, selv når den kan registrere den. Dataene skal kasseres helt og videresendes fra bunden. På et støjende transmissionsmedium kan en vellykket transmission tage lang tid eller måske aldrig forekomme. Selvom kvaliteten af ​​paritetskontrol er dårlig, da den kun bruger en enkelt bit, resulterer denne metode i mindst overhead.

To ud af fem kode

En to-ud-af-fem kode er et kodningsskema, der bruger fem bits bestående af præcis tre 0'er og to 1'er. Dette giver ti mulige kombinationer, nok til at repræsentere cifrene 0–9. Dette skema kan registrere alle enkelt bit-fejl, alle ulige nummererede bit-fejl og nogle lige nummererede bit-fejl (f.eks. Vending af begge 1-bit). Det kan dog stadig ikke rette nogen af ​​disse fejl.

Gentagelse

En anden kode i brug på det tidspunkt gentog hver databit flere gange for at sikre, at den blev sendt korrekt. For eksempel, hvis den databit, der skal sendes, er en 1, sender en n = 3 gentagelseskode 111. Hvis de tre modtagne bits ikke er identiske, opstod der en fejl under transmissionen. Hvis kanalen er ren nok, ændres der oftest kun en bit i hver triple. Derfor svarer 001, 010 og 100 hver til en 0 bit, mens 110, 101 og 011 svarer til en 1 bit, med den større mængde cifre, der er ens ('0' eller '1'), der angiver, hvad databitten skal være. En kode med denne mulighed for at rekonstruere den originale meddelelse i nærvær af fejl er kendt som en fejlkorrigerende kode. Denne tredobbelte gentagelseskode er en Hamming -kode med m = 2, da der er to paritetsbit og 2 ² - 2 - 1 = 1 databit.

Sådanne koder kan imidlertid ikke korrekt reparere alle fejl. I vores eksempel, hvis kanalen vender to bits, og modtageren får 001, registrerer systemet fejlen, men konkluderer, at den originale bit er 0, hvilket er forkert. Hvis vi øger bitstrengens størrelse til fire, kan vi registrere alle to-bit fejl, men kan ikke rette dem (mængden af ​​paritetsbit er lige); ved fem bits kan vi både opdage og rette alle to-bit fejl, men ikke alle tre-bit fejl.

Desuden er det ineffektivt at øge størrelsen på paritetsbitstrengen, reducere gennemstrømningen tre gange i vores originale tilfælde, og effektiviteten falder drastisk, efterhånden som vi øger antallet af gange, hver bit bliver duplikeret for at opdage og rette flere fejl.

Beskrivelse

Hvis flere fejlkorrigerende bits er inkluderet i en meddelelse, og hvis disse bits kan arrangeres således, at forskellige forkerte bits producerer forskellige fejlresultater, kunne dårlige bits identificeres. I en syv-bit besked er der syv mulige enkeltbitfejl, så tre fejlkontrolbit kan potentielt angive ikke kun, at der opstod en fejl, men også hvilken bit, der forårsagede fejlen.

Hamming studerede de eksisterende kodningsordninger, herunder to-af-fem, og generaliserede deres begreber. Til at begynde med udviklede han en nomenklatur til at beskrive systemet, herunder antallet af databit og fejlkorrektionsbit i en blok. For eksempel inkluderer paritet en enkelt bit for ethvert dataord, så under antagelse af ASCII -ord med syv bits beskrev Hamming dette som en (8,7) kode, med otte bits i alt, hvoraf syv er data. Gentagelseseksemplet ville være (3,1) efter samme logik. Den kode sats er det andet tal divideret med den første, for vores gentagelse eksempel 1/3.

Hamming lagde også mærke til problemerne med at vende to eller flere bits, og beskrev dette som "afstanden" (det kaldes nu Hamming -afstanden , efter ham). Paritet har en afstand på 2, så en bit flip kan detekteres, men ikke korrigeres, og to bit -flip vil være usynlige. Gentagelsen (3,1) har en afstand på 3, da tre bits skal vendes i den samme triple for at opnå et andet kodeord uden synlige fejl. Det kan rette en -bit fejl, eller det kan opdage - men ikke rette - to -bit fejl. En (4,1) gentagelse (hver bit gentages fire gange) har en afstand på 4, så det kan detekteres at vende tre bits, men ikke korrigeres. Når tre bits vender i den samme gruppe, kan der være situationer, hvor et forsøg på at rette vil producere det forkerte kodeord. Generelt kan en kode med afstand k opdage, men ikke rette k - 1 fejl.

Hamming var interesseret i to problemer på én gang: at øge afstanden så meget som muligt, samtidig med at kodehastigheden blev øget så meget som muligt. I løbet af 1940'erne udviklede han flere kodningsordninger, der var dramatiske forbedringer af eksisterende koder. Nøglen til alle hans systemer var at have paritetsbitene overlappende, således at det lykkedes dem at kontrollere hinanden såvel som dataene.

Generel algoritme

Den følgende generelle algoritme genererer en enkeltfejlkorrigerende (SEC) kode for et vilkårligt antal bits. Hovedideen er at vælge de fejlkorrigerende bits således, at indeks-XOR ( XOR for alle bitpositioner, der indeholder en 1) er 0. Vi bruger position 1, 10, 100 osv. (I binær) som fejlen -korrektion af bits, hvilket garanterer, at det er muligt at indstille de fejlkorrigerende bits, så indeks-XOR for hele meddelelsen er 0. Hvis modtageren modtager en streng med index-XOR 0, kan de konkludere, at der ikke var nogen korruption, og ellers angiver indeks-XOR indekset for den beskadigede bit.

En algoritme kan udledes af følgende beskrivelse:

1. Nummer bitene fra 1: bit 1, 2, 3, 4, 5, 6, 7 osv.
2. Skriv bitnumrene i binært: 1, 10, 11, 100, 101, 110, 111 osv.
3. Alle bitpositioner, der er poweres af to (har en enkelt 1 bit i den binære form for deres position) er paritetsbit: 1, 2, 4, 8 osv. (1, 10, 100, 1000)
4. Alle andre bitpositioner, med to eller flere 1 bits i den binære form for deres position, er databit.
5. Hver databit er inkluderet i et unikt sæt med 2 eller flere paritetsbit, bestemt af den binære form for dens bitposition.
   1. Paritetsbit 1 dækker alle bitpositioner, der har det mindst signifikante bitsæt: bit 1 (selve paritetsbitten), 3, 5, 7, 9 osv.
   2. Paritetsbit 2 dækker alle bitpositioner, der har det næstmindst signifikante bitsæt: bit 2-3, 6-7, 10-11 osv.
   3. Paritetsbit 4 dækker alle bitpositioner, der har det tredje mindst betydelige bitsæt: bits 4–7, 12–15, 20–23 osv.
   4. Paritetsbit 8 dækker alle bitpositioner, der har det fjerde mindst signifikante bitsæt: bits 8–15, 24–31, 40–47 osv.
   5. Generelt dækker hver paritetsbit alle bits, hvor bitvis OG for paritetspositionen og bitpositionen er ikke-nul.

Hvis en byte af data, der skal kodes, er 10011010, ville dataordet (ved hjælp af _ til at repræsentere paritetsbitene) være __1_001_1010, og kodeordet er 011100101010.

Valget af paritet, lige eller ulige, er irrelevant, men det samme valg skal bruges til både kodning og afkodning.

Denne generelle regel kan vises visuelt:

Bit position		1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	…
Kodede databit		p1	p2	d1	p4	d2	d3	d4	s8	d5	d6	d7	d8	d9	d10	d11	s16	d12	d13	d14	d15
Paritets bit dækning	p1
	p2
	p4
	s8
	s16

Der vises kun 20 kodede bits (5 paritet, 15 data), men mønsteret fortsætter på ubestemt tid. Det centrale ved Hamming -koder, der kan ses fra visuel inspektion, er, at enhver given bit er inkluderet i et unikt sæt paritetsbits. For at kontrollere for fejl skal du kontrollere alle paritetsbitene. Fejlmønsteret, kaldet fejlsyndromet , identificerer bit ved fejl. Hvis alle paritetsbits er korrekte, er der ingen fejl. Ellers identificerer summen af ​​positionerne for de fejlagtige paritetsbit den fejlagtige bit. For eksempel, hvis paritetsbitene i positionerne 1, 2 og 8 angiver en fejl, er bit 1+2+8 = 11 fejl. Hvis kun én paritetsbit angiver en fejl, er selve paritetsbitten en fejl.

Med m paritets bits kan bits fra 1 op til dækkes. Efter diskontering af paritetsbitene forbliver bits til brug som data. Da m varierer, får vi alle de mulige Hamming -koder: ${\ displaystyle 2^{m} -1}$${\ displaystyle 2^{m} -m-1}$

Paritetsstykker	I alt bits	Databit	Navn	Sats
2	3	1	Hamming (3,1) (Triple gentagelseskode )	1/3 ≈ 0,333
3	7	4	Hamming (7,4)	4/7 ≈ 0,571
4	15	11	Hamming (15,11)	11/15 ≈ 0,733
5	31	26	Hamming (31,26)	26/31 ≈ 0,839
6	63	57	Hamming (63,57)	57/63 ≈ 0,905
7	127	120	Hamming (127.120)	120/127 ≈ 0,945
8	255	247	Hamming (255.247)	247/255 ≈ 0,969
…
m	${\ displaystyle n = 2^{m} -1}$	${\ displaystyle k = 2^{m} -m-1}$	Hamming${\ displaystyle (2^{m} -1,2^{m} -m-1)}$	${\ displaystyle (2^{m} -m-1)/(2^{m} -1)}$

Hammingkoder med ekstra paritet (SECDED)

Hammingkoder har en minimumsafstand på 3, hvilket betyder, at dekoderen kan registrere og rette en enkelt fejl, men den kan ikke skelne en dobbelt bitfejl i et eller andet kodeord fra en enkelt bitfejl i et andet kodeord. Nogle dobbeltbitfejl vil således blive forkert afkodet, som om de var enkeltbitfejl og derfor ikke blive opdaget, medmindre der ikke forsøges korrigeret.

For at afhjælpe denne mangel kan Hamming -koder udvides med en ekstra paritetsbit. På denne måde er det muligt at øge minimumsafstanden for Hamming-koden til 4, hvilket gør det muligt for dekoderen at skelne mellem enkeltbitfejl og to-bit-fejl. Således kan dekoderen detektere og rette en enkelt fejl og samtidig opdage (men ikke rette) en dobbeltfejl.

Hvis dekoderen ikke forsøger at rette fejl, kan den pålideligt registrere triple bit -fejl. Hvis dekoderen korrigerer fejl, vil nogle tredobbelte fejl blive betragtet som enkeltfejl og "korrigeret" til den forkerte værdi. Fejlkorrektion er derfor en afvejning mellem sikkerhed (evnen til pålideligt at opdage triple bit-fejl) og robusthed (evnen til at fortsætte med at fungere over for single bit-fejl).

Denne udvidede Hamming -kode er populær i computerhukommelsessystemer, hvor den er kendt som SECDED (forkortet fra enkeltfejlkorrektion , dobbeltfejldetektering ). Særligt populær er (72,64) koden, en afkortet (127,120) Hamming -kode plus en ekstra paritetsbit, som har samme pladsoverhead som en (9,8) paritetskode.

[7,4] Hamming -kode

Grafisk afbildning af de fire databit og tre paritetsbit, og hvilke paritetsbit der gælder for hvilke databit

I 1950 introducerede Hamming [7,4] Hamming -koden. Det koder fire databit til syv bit ved at tilføje tre paritetsbits. Det kan registrere og rette enkelt-bit fejl. Med tilføjelse af en samlet paritetsbit kan den også opdage (men ikke rette) dobbeltbitfejl.

Konstruktion af G og H

Matricen kaldes en (kanonisk) generatormatrix med en lineær ( n , k ) kode, ${\ displaystyle \ mathbf {G}: = {\ begin {pmatrix} {\ begin {array} {c | c} I_ {k} &-A^{\ text {T}} \\\ end {array}} \ end {pmatrix}}}$

og kaldes en paritetskontrolmatrix . ${\ displaystyle \ mathbf {H}: = {\ begin {pmatrix} {\ begin {array} {c | c} A & I_ {nk} \\\ end {array}} \ end {pmatrix}}}$

Dette er konstruktionen af G og H i standard (eller systematisk) form. Uanset form skal G og H for lineære blokkoder tilfredsstille

${\ displaystyle \ mathbf {H} \, \ mathbf {G} ^{\ text {T}} = \ mathbf {0}}$, en nul-matrix.

Da [7, 4, 3] = [ n , k , d ] = [2 ^m - 1, 2 ^m −1− m , 3]. Den paritet-kontrol matrix H af en Hamming-kode konstrueres, idet alle kolonner af længde m , der er parvis uafhængige.

Således er H en matrix, hvis venstre side er alle de nul-n-tupler, hvor rækkefølgen af ​​n-tuplerne i matrixkolonnerne ikke betyder noget. Den højre side er blot den ( n - k ) - identitet matrix .

Så G kan opnås fra H ved at tage transponerede venstre side af H med identiteten k- identitet matrix på venstre side af G .

Koden generator matrix og paritet-kontrol matrix er: ${\ displaystyle \ mathbf {G}}$ ${\ displaystyle \ mathbf {H}}$

${\ displaystyle \ mathbf {G}: = {\ begin {pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \\\ slut {pmatrix}} _ {4,7}}$

og

${\ displaystyle \ mathbf {H}: = {\ begin {pmatrix} 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 \\\ slut {pmatrix}} _ {3,7}.}$

Endelig kan disse matricer muteres til ækvivalente ikke-systematiske koder ved følgende operationer:

• Kolonnepermutationer (bytte kolonner)
• Elementære rækkeoperationer (udskiftning af en række med en lineær kombination af rækker)

Indkodning

Eksempel

Fra ovenstående matrix har vi 2 ^k = 2 ⁴ = 16 kodeord. Lad være en række vektor af binære databit, . Kodeordet for en hvilken som helst af de 16 mulige datavektorer er givet af standardmatrixproduktet, hvor summeringsoperationen udføres modulo-2. ${\ displaystyle {\ vec {a}}}$${\ displaystyle {\ vec {a}} = [a_ {1}, a_ {2}, a_ {3}, a_ {4}], \ quad a_ {i} \ in \ {0,1 \}}$${\ displaystyle {\ vec {x}}}$${\ displaystyle {\ vec {a}}}$${\ displaystyle {\ vec {x}} = {\ vec {a}} G}$

Lad f.eks . Ved hjælp af generatormatrix ovenfra har vi (efter at have anvendt modulo 2, til summen), ${\ displaystyle {\ vec {a}} = [1,0,1,1]}$${\ displaystyle G}$

${\ displaystyle {\ vec {x}} = {\ vec {a}} G = {\ begin {pmatrix} 1 & 0 & 1 & 1 \ end {pmatrix}} {\ begin {pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 & # 0 \\ end {pmatrix}} = {\ begin {pmatrix} 1 & 0 & 1 & 1 & 2 & 3 & 2 \ end {pmatrix}} = {\ begin {pmatrix} 1 & 0 & 1 & 1 & 0 & 1 & 0 \ end {pmatrix}}}$

[7,4] Hamming -kode med en ekstra paritetsbit

Det samme [7,4] eksempel ovenfra med en ekstra paritetsbit. Dette diagram er ikke beregnet til at svare til matrixen H for dette eksempel.

Den [7,4] Hamming -kode kan let udvides til en [8,4] -kode ved at tilføje en ekstra paritetsbit oven på det (7,4) kodede ord (se Hamming (7,4) ). Dette kan opsummeres med de reviderede matricer:

$$$

og

$$$

Bemærk, at H ikke er i standardform. For at opnå G kan elementære rækkeoperationer bruges til at opnå en ækvivalent matrix til H i ​​systematisk form:

$$$

For eksempel er den første række i denne matrix summen af ​​den anden og tredje række af H i ikke-systematisk form. Ved hjælp af den systematiske konstruktion til Hamming -koder ovenfra er matricen A tydelig, og den systematiske form for G skrives som

$$$

Den ikke-systematiske form for G kan reduceres i rækker (ved hjælp af elementære rækkeoperationer) for at matche denne matrix.

Tilføjelsen af ​​den fjerde række beregner effektivt summen af ​​alle kodeordbitene (data og paritet) som den fjerde paritetsbit.

For eksempel er 1011 kodet (ved hjælp af den ikke-systematiske form for G i starten af ​​dette afsnit) til 01 1 0 011 0, hvor blå cifre er data; røde cifre er paritetsbit fra [7,4] Hamming -koden; og det grønne ciffer er paritetsbit tilføjet af [8,4] koden. Det grønne ciffer gør pariteten af ​​[7,4] kodeordene lige.

Endelig kan det vises, at minimumsafstanden er steget fra 3 i [7,4] -koden til 4 i [8,4] -koden. Derfor kan koden defineres som [8,4] Hamming -kode.

For at afkode [8,4] Hamming -koden skal du først kontrollere paritetsbitten. Hvis paritetsbitten angiver en fejl, angiver enkeltfejlkorrektion ([7,4] Hamming -koden) fejlplaceringen, med "ingen fejl" angiver paritetsbiten. Hvis paritetsbiten er korrekt, angiver en enkelt fejlkorrektion den (bitvis) eksklusive eller to fejlplaceringer. Hvis placeringerne er ens ("ingen fejl"), er der enten ikke opstået en dobbeltbitfejl, eller den har annulleret sig selv. Ellers er der opstået en dobbeltbitfejl.

Se også

Noter

Referencer

eksterne links

• Visuel forklaring på Hamming -koder
• CGI -script til beregning af Hamming -afstande (fra R. Tervo, UNB, Canada)
• Værktøj til beregning af Hamming -kode