Hamming kode

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 2. marts 2021; checks kræver 12 redigeringer .

Binær Hamming-kode
Hamming kode med $(7,4)$ $r=3$
Opkaldt efter	Richard Hamming
Type	lineær blokkode
Blok længde	$2^{r}-1$
Beskedens længde	$2^{r}-r-1$
Del	$1-{\frac {2}{2^{r}-1))$
Afstand	3
Alfabet størrelse	2
Betegnelse	${\displaystyle [2^{r}-1,2^{r}-r-1,3]_{2))$
Mediefiler på Wikimedia Commons

Hamming-koden er en selvkontrollerende og selvkorrigerende kode . Bygget med reference til det binære talsystem .

Giver dig mulighed for at rette en enkelt fejl (en fejl i en bit af et ord) og finde en dobbelt [1] .

Opkaldt efter den amerikanske matematiker Richard Hamming , der foreslog koden.

Historie

I midten af 1940'erne blev Bell Model V - regnemaskinen skabt på Bell Laboratories . Det var en elektromekanisk maskine, der brugte relæblokke, hvis hastighed var meget lav: en operation på få sekunder. Data blev indtastet i maskinen ved hjælp af hulkort med upålidelige læseenheder, så der opstod ofte fejl under læseprocessen. På arbejdsdage blev der brugt specielle koder til at opdage og rette fundne fejl, mens operatøren lærte om fejlen ved lysets skær, rettede og genstartede maskinen. I weekender, hvor der ikke var nogen operatører, ville maskinen, hvis der opstod en fejl, automatisk afslutte programmet og starte et nyt.

Hamming arbejdede ofte i weekenden og blev mere og mere irriteret, da han måtte genindlæse sit program på grund af hulkortlæserens upålidelighed. I flere år ledte han efter en effektiv fejlkorrektionsalgoritme. I 1950 udgav han en kodningsmetode kendt som Hamming-koden.

Systematiske koder

Systematiske koder danner en stor gruppe af blokke, adskillelige koder (hvor alle symboler i et ord kan opdeles i verifikation og information). Et træk ved systematiske koder er, at kontrolsymboler dannes som et resultat af lineære logiske operationer på informationssymboler. Derudover kan ethvert tilladt kodeord opnås som et resultat af lineære operationer på et sæt lineært uafhængige kodeord.

Selvkontrollerende koder

Hamming-koder er selvovervågningskoder, det vil sige koder, der automatisk opdager fejl i datatransmission. For at bygge dem er det nok at tildele et ekstra (kontrol) binært ciffer til hvert ord og vælge cifferet for dette ciffer, så det samlede antal enheder i billedet af ethvert tal er for eksempel ulige. En enkelt fejl i et hvilket som helst ciffer i det transmitterede ord (herunder måske i kontrolcifferet) vil ændre pariteten af det samlede antal enheder. Modulo 2-tællere, der tæller antallet af dem, der er indeholdt blandt de binære cifre i et tal, giver et signal om tilstedeværelsen af fejl. I dette tilfælde er det umuligt at vide, i hvilken position af ordet fejlen opstod, og derfor er der ingen måde at rette den på. Fejl, der opstår samtidigt i to, fire osv. - i et lige antal cifre forbliver også ubemærket. Det antages, at dobbelte og endnu mere flere fejl er usandsynlige.

Selvkorrigerende koder

Koder, hvor automatisk fejlretning er mulig, 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 kontrolbits vælges således, at uligheden eller er opfyldt , hvor er antallet af informationsbinære bits af kodeordet. Minimumsværdierne af k for givne værdier af m, fundet i overensstemmelse med denne ulighed, er angivet i tabellen. $k$ $2^k \geq k+m+1$ $k \geq \log_2(k+m+1)$ $m$

Rækkevidde m	kmin _
en	2
2-4	3
5-11	fire
12-26	5
27-57	6

Af størst interesse er binære blokkorrektionskoder . 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 den anden. I næsten alle blokkoder kan symboler opdeles i information og kontrol eller kontrol. Således er alle ord opdelt i tilladte (hvor forholdet mellem information og kontroltegn er muligt) og forbudte.

Hovedkarakteristika ved selvkorrigerende koder:

Antallet af tilladte og forbudte kombinationer. Hvis - antallet af tegn i blokken - antallet af kontroltegn i blokken - antallet af informationstegn, så - antallet af mulige kodekombinationer - antallet af tilladte kodekombinationer - antallet af forbudte kombinationer . $n$ $r$ $k$ $2^{n}$ $2^k$ ${\displaystyle 2^{n}-2^{k))$
Kode redundans. Værdien kaldes redundansen af korrektionskoden. ${\tfrac {r}{n))$
Minimum kodeafstand. Den mindste kodeafstand er det mindste antal forvrængede symboler, der kræves for at skifte fra en tilladt kombination til en anden. $d$
Antallet af fejl opdaget og rettet. Hvis er antallet af fejl, som koden er i stand til at rette, så er det nødvendigt og tilstrækkeligt $g$ $d\geq 2g+1$
Korrigerende koder.

Plotkin -grænsen giver en øvre grænse for kodeafstanden:

d\leqslant {\tfrac {n\cdot 2^{k-1}}{2^{k}-1)),

eller:

r\geq 2\cdot (d-1)-\log _{2}d

på

n\geq 2\cdot d-1.

Hamming-grænsen indstiller det maksimalt mulige antal tilladte kodekombinationer:

2^{k}\leq {2^{n}}/\sum _{i=0}^{\tfrac {d-1}{2}}C_{n}^{i},

hvor er antallet af kombinationer af elementer for elementer. Herfra kan du få et udtryk for at estimere antallet af tjeksymboler:

C_n^i

n

jeg

r\geq \log _{2}\left(\sum _{i=0}^{(d-1)/2}C_{n}^{i}\right).

For værdier er forskellen mellem Hamming-bundet og Plotkin-bundet lille. $(d/n)\leq 0{,}3$

Varshamov-Gilbert-grænsen for stort n definerer en nedre grænse for antallet af check-symboler:

r\geq \log _{2}\left(\sum _{i=0}^{d-2}C_{n-1}^{i}\right).

Alle ovenstående estimater giver en idé om den øvre grænse ved faste og eller et lavere estimat af antallet af check-symboler. $d$ $n$ $k$

Hamming kode

Konstruktionen af Hamming-koder er baseret på princippet om at kontrollere antallet af enkelttegn for paritet: et sådant element føjes til sekvensen, så antallet af enkelttegn i den resulterende sekvens er lige:

r_{1}=i_{1}\oplus i_{2}\oplus ...\oplus i_{k}.

Tegnet her betyder modulo 2 addition : $\plus$

S=i_{1}\oplus i_{2}\oplus ...\oplus i_{n}\oplus r_{1}.

Hvis - så er der ingen fejl, hvis - så en enkelt fejl. $S=0$ $S=1$

En sådan kode kaldes eller . Det første tal er antallet af sekvenselementer, det andet er antallet af informationstegn. $(k+1,\ k)$ $(n,\ n-1)$

For hvert antal afkrydsningssymboler er der en klassisk Hamming-kode med markeringer: $r=3,\ 4,\ 5\ ...$

(n,k)=(2^{r}-1,2^{r}-1-r),

altså - .

(7,4),(15,11),(31,26)

Med andre værdier fås den såkaldte trunkerede kode, for eksempel den internationale telegrafkode MTK-2, som har . Det kræver en Hamming-kode, som er en trunkeret version af klassikeren $k$ $k = 5$ $(9,\ 5),$ $(15,\ 11).$

Overvej for eksempel den klassiske Hamming-kode . Lad os gruppere afkrydsningssymbolerne som følger: $(7,\ 4)$

r_{1}=i_{1}\oplus i_{2}\oplus i_{3},

r_{2}=i_{2}\oplus i_{3}\oplus i_{4},

r_{3}=i_{1}\oplus i_{2}\oplus i_{4}.

At få kodeordet ser sådan ud:

\begin{pmatrix} i_1 & i_2 & i_3 & i_4 & \\ \end{pmatrix}

\begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 \\ \end{pmatrix}

= .

\begin{pmatrix} i_1 & i_2 & i_3 & i_4 & r_1 & r_2 & r_3 \\ \end{pmatrix}

Dekoderens input modtager et kodeord , hvor symboler er markeret med et streg, som kan blive forvrænget som følge af interferens. I dekoderen i fejlkorrektionstilstanden bygges en sekvens af syndromer: $V=(i_{1}',\ i_{2}',\ i_{3}',\ i_{4}',\ r_{1}',\ r_{2}',\ r_{ 3}')$

S_{1}=r_{1}\oplus i_{1}\oplus i_{2}\oplus i_{3},

S_{2}=r_{2}\oplus i_{2}\oplus i_{3}\oplus i_{4},

S_{3}=r_{3}\oplus i_{1}\oplus i_{2}\oplus i_{4}.

$S=(S_{1},\ S_{2},\ S_{3})$ kaldet sekvenssyndromet.

At få syndromet ser sådan ud:

\begin{pmatrix} i_1 & i_2 & i_3 & i_4 & r_1 & r_2 & r_3 \\ \end{pmatrix}

\begin{pmatrix} 1 & 0 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{pmatrix}

= .

{\begin{pmatrix}S_{1}&S_{2}&S_{3}\\\end{pmatrix}}

$i_1$	$i_2$	$i_3$	$i_4$	$r_{1}$	$r_{2}$	$r_3$	$i_1$	$i_2$	$i_3$	$i_4$	$r_{1}$	$r_{2}$	$r_3$
0	0	0	0	0	0	0	en	0	0	0	en	0	en
0	0	0	en	0	en	en	en	0	0	en	en	en	0
0	0	en	0	en	en	0	en	0	en	0	0	en	en
0	0	en	en	en	0	en	en	0	en	en	0	0	0
0	en	0	0	en	en	en	en	en	0	0	0	en	0
0	en	0	en	en	0	0	en	en	0	en	0	0	en
0	en	en	0	0	0	en	en	en	en	0	en	0	0
0	en	en	en	0	en	0	en	en	en	en	en	en	en

Kodeordene for Hamming-koden er angivet i tabellen. $(7,\ 4)$

Syndromet indikerer, at der ikke er nogen forvrængning i sekvensen. Hvert ikke-nul syndrom svarer til et bestemt fejlmønster, som korrigeres på afkodningsstadiet. $(0,0,0)$

Syndrom	001	010	011	100	101	110	111
Fejlkonfiguration _	0000001	0000010	0001000	0000100	1000000	0010000	0100000
Symbol fejl	$r_3$	$r_{2}$	$i_4$	$r_{1}$	$i_1$	$i_3$	$i_2$

For koden i tabellen til højre er ikke-nul syndromer og deres tilsvarende fejlkonfigurationer angivet (for formen: ). $(7,4)$ $i_1$ $i_2$ $i_3$ $i_4$ $r_{1}$ $r_{2}$ $r_3$

Kodningsalgoritme

Antag, at vi skal generere en Hamming-kode for et eller andet informationskodeord. Lad os tage et 15-bit kodeord som eksempel, selvom algoritmen er velegnet til kodeord af enhver længde. I tabellen nedenfor giver den første linje positionsnumrene i kodeordet, den anden linje giver bitbetegnelsen, og den tredje linje giver bitværdierne. $x_{1}\dots \ x_{15},$

en	2	3	fire	5	6	7	otte	9	ti	elleve	12	13	fjorten	femten
x 1	x2 _	x 3	x4 _	x5 _	x6 _	x 7	x 8	x9 _	x 10	x 11	x 12	x 13	x 14	x 15
en	0	0	en	0	0	en	0	en	en	en	0	0	0	en

Lad os indsætte kontrolbits i informationsordet på en sådan måde, at deres positionsnumre er heltalspotenser af to: 1, 2, 4, 8, 16 ... Vi får et 20-bit ord med 15 informationer og 5 kontrolbits. Indledningsvis sættes kontrolbittene til nul. På figuren er kontrolbits fremhævet med pink. ${\displaystyle r_{0}\dots \ r_{4))$

en	2	3	fire	5	6	7	otte	9	ti	elleve	12	13	fjorten	femten	16	17	atten	19	tyve
r0 _	r1 _	x 1	r2 _	x2 _	x 3	x4 _	r3 _	x5 _	x6 _	x 7	x 8	x9 _	x 10	x 11	r4 _	x 12	x 13	x 14	x 15
0	0	en	0	0	0	en	0	0	0	en	0	en	en	en	0	0	0	0	en

Generelt er antallet af kontrolbits i et kodeord lig med den binære logaritme af et tal, der er en større end antallet af bits i kodeordet (inklusive kontrolbits); logaritmen rundes op. For eksempel kræver et 1-bit informationsord to kontrolbit, et 2-, 3- eller 4-bit informationsord kræver tre, et 5...11-bit informationsord kræver fire, et 12...26- bit information ord kræver fem, og så videre.

Lad os tilføje 5 rækker til tabellen (i henhold til antallet af kontrolbits), hvori vi vil placere transformationsmatrixen. Hver række vil svare til en kontrolbit (nul kontrolbit er den øverste linje, den fjerde er den nederste), hver kolonne vil svare til en bit af det kodede ord. I hver kolonne i transformationsmatricen placerer vi det binære tal for denne kolonne, og rækkefølgen af bits vil blive omvendt - den mindst signifikante bit vil blive placeret i den øverste linje, den mest signifikante - i bunden. For eksempel vil den tredje kolonne i matrixen indeholde tallene 11000, som svarer til den binære repræsentation af tallet tre: 00011.

en	2	3	fire	5	6	7	otte	9	ti	elleve	12	13	fjorten	femten	16	17	atten	19	tyve
r0 _	r1 _	x 1	r2 _	x2 _	x 3	x4 _	r3 _	x5 _	x6 _	x 7	x 8	x9 _	x 10	x 11	r4 _	x 12	x 13	x 14	x 15
0	0	en	0	0	0	en	0	0	0	en	0	en	en	en	0	0	0	0	en
en	0	en	0	en	0	en	0	en	0	en	0	en	0	en	0	en	0	en	0	r0 _
0	en	en	0	0	en	en	0	0	en	en	0	0	en	en	0	0	en	en	0	r1 _
0	0	0	en	en	en	en	0	0	0	0	en	en	en	en	0	0	0	0	en	r2 _
0	0	0	0	0	0	0	en	en	en	en	en	en	en	en	0	0	0	0	0	r3 _
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	en	en	en	en	en	r4 _

I højre del af tabellen blev en kolonne efterladt tom, hvori vi placerer resultaterne af beregningen af kontrolbittene. Vi beregner kontrolbittene som følger: vi tager en af rækkerne i transformationsmatricen (for eksempel ) og finder dens skalarprodukt med kodeordet, det vil sige, vi multiplicerer de tilsvarende bits i begge rækker og finder summen af Produkter. Hvis summen viste sig at være større end én, finder vi resten af dens division med 2. Med andre ord tæller vi, hvor mange gange der er enheder på de samme positioner i kodeordet og den tilsvarende række i matricen, og tag dette tal modulo 2. $r_{0}$

Hvis vi beskriver denne proces i form af matrixalgebra, så er operationen en multiplikation af transformationsmatrixen med matrixkolonnen i kodeordet, hvilket resulterer i en matrixkolonne af kontrolbits, som skal tages modulo 2.

For eksempel for linjen : $r_{0}$

r_{0}

= (1 0+0 0+1 1+0 0+1 0+0 0+1 1+0 0+1 0+0 0+1 1+0 0+ 1 1+0 1+1 1+0 0+ 1 0+0 0+1 0+0 1) mod 2 = 5 mod 2 = 1.

De resulterende kontrolbits indsættes i kodeordet i stedet for de nuller, der var der tidligere. Analogt finder vi kontrolbittene i de resterende linjer. Hamming-kodning er færdig. Det modtagne kodeord er 11110010001011110001.

en	2	3	fire	5	6	7	otte	9	ti	elleve	12	13	fjorten	femten	16	17	atten	19	tyve
r0 _	r1 _	x 1	r2 _	x2 _	x 3	x4 _	r3 _	x5 _	x6 _	x 7	x 8	x9 _	x 10	x 11	r4 _	x 12	x 13	x 14	x 15
en	en	en	en	0	0	en	0	0	0	en	0	en	en	en	en	0	0	0	en
en	0	en	0	en	0	en	0	en	0	en	0	en	0	en	0	en	0	en	0	r0 _	en
0	en	en	0	0	en	en	0	0	en	en	0	0	en	en	0	0	en	en	0	r1 _	en
0	0	0	en	en	en	en	0	0	0	0	en	en	en	en	0	0	0	0	en	r2 _	en
0	0	0	0	0	0	0	en	en	en	en	en	en	en	en	0	0	0	0	0	r3 _	0
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	en	en	en	en	en	r4 _	en

Afkodningsalgoritme

Hamming-afkodningsalgoritmen er fuldstændig identisk med indkodningsalgoritmen. Transformationsmatrixen for den tilsvarende dimension multipliceres med kodeordskolonnematrixen, og hvert element i den resulterende kolonnematrix tages modulo 2. Den resulterende kolonnematrix kaldes "syndrommatrixen". Det er let at verificere, at et kodeord, der er genereret i overensstemmelse med algoritmen beskrevet i det foregående afsnit, altid giver en nul-syndrom-matrix.

Syndrommatricen bliver ikke-nul, hvis en af bits i det oprindelige ord har ændret sin værdi som følge af en fejl (f.eks. ved overførsel af et ord over en støjende kommunikationslinje). Antag for eksempel, at i kodeordet opnået i det foregående afsnit, har den sjette bit ændret sin værdi fra nul til én (angivet med rødt i figuren). Så får vi følgende matrix af syndromer.

en	2	3	fire	5	6	7	otte	9	ti	elleve	12	13	fjorten	femten	16	17	atten	19	tyve
r0 _	r1 _	x 1	r2 _	x2 _	x 3	x4 _	r3 _	x5 _	x6 _	x 7	x 8	x9 _	x 10	x 11	r4 _	x 12	x 13	x 14	x 15
en	en	en	en	0	en	en	0	0	0	en	0	en	en	en	en	0	0	0	en
en	0	en	0	en	0	en	0	en	0	en	0	en	0	en	0	en	0	en	0	s0 _	0
0	en	en	0	0	en	en	0	0	en	en	0	0	en	en	0	0	en	en	0	s 1	en
0	0	0	en	en	en	en	0	0	0	0	en	en	en	en	0	0	0	0	en	s2 _	en
0	0	0	0	0	0	0	en	en	en	en	en	en	en	en	0	0	0	0	0	s3 _	0
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	en	en	en	en	en	s4 _	0

Bemærk, at med en enkelt fejl er syndrommatrixen altid en binær post (det mindst signifikante ciffer i den øverste række) af det positionsnummer, hvor fejlen opstod. I eksemplet ovenfor svarer syndrommatrixen (01100) til det binære tal 00110 eller decimal 6, hvilket betyder, at fejlen opstod i den sjette bit.

Ansøgning

Hamming-kode bruges i nogle lagringsapplikationer, især RAID 2 . Derudover har Hamming-metoden længe været brugt i ECC -hukommelsen og giver dig mulighed for at rette enkeltfejl og opdage dobbeltfejl i farten.

Se også

Noter

↑ Hamming-koder - "Alt om højteknologi" . all-ht.ru. Dato for adgang: 20. januar 2016. Arkiveret fra originalen 15. januar 2016. (ubestemt)

Litteratur

Peterson W., Weldon E. Fejlretningskoder: Pr. fra engelsk. Moskva: Mir, 1976, 594 s.
Penin P. E., Filippov L. N. Radiotekniske informationstransmissionssystemer. Moskva: Radio og kommunikation, 1984, 256 s.
Blahut R. Teori og praksis for fejlkontrolkoder. Om. fra engelsk. M.: Mir, 1986, 576 s.