Hamming-kod

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 2 mars 2021; kontroller kräver 12 redigeringar .

Binär Hamming-kod
Hamming kod med $(7,4)$ $r=3$
Döpt efter	Richard Hamming
Sorts	linjär blockkod
Blocklängd	$2^{r}-1$
Meddelandets längd	$2^{r}-r-1$
Dela med sig	$1-{\frac {2}{2^{r}-1))$
Distans	3
Alfabetets storlek	2
Beteckning	${\displaystyle [2^{r}-1,2^{r}-r-1,3]_{2))$
Mediafiler på Wikimedia Commons

Hamming-koden är en självkontrollerande och självkorrigerande kod . Byggd med hänvisning till det binära talsystemet .

Låter dig korrigera ett enstaka fel (ett fel i en bit av ett ord) och hitta en dubbel [1] .

Uppkallad efter den amerikanske matematikern Richard Hamming som föreslog koden.

Historik

I mitten av 1940-talet skapades beräkningsmaskinen Bell Model V på Bell Laboratories . Det var en elektromekanisk maskin som använde reläblock, vars hastighet var mycket låg: en operation på några sekunder. Data matades in i maskinen med hjälp av hålkort med opålitliga läsenheter, så fel uppstod ofta under läsningsprocessen. På arbetsdagar användes speciella koder för att upptäcka och korrigera upptäckta fel, medan operatören fick reda på felet genom att lamporna sken, korrigerade och startade om maskinen. På helger när det inte fanns några operatörer, om ett fel inträffade, skulle maskinen automatiskt avsluta programmet och starta ett nytt.

Hamming jobbade ofta helger och blev alltmer irriterad då han var tvungen att ladda om sitt program på grund av hålkortsläsarens opålitlighet. I flera år letade han efter en effektiv felkorrigeringsalgoritm. 1950 publicerade han en kodningsmetod som kallas Hamming-koden.

Systematiska koder

Systematiska koder bildar en stor grupp av block, separerbara koder (där alla symboler i ett ord kan delas in i verifiering och information). En egenskap hos systematiska koder är att kontrollsymboler bildas som ett resultat av linjära logiska operationer på informationssymboler. Dessutom kan vilket tillåtet kodord som helst erhållas som ett resultat av linjära operationer på en uppsättning linjärt oberoende kodord.

Självkontrollerande koder

Hammingkoder är självövervakningskoder, det vill säga koder som automatiskt upptäcker fel vid dataöverföring. För att bygga dem räcker det att tilldela ytterligare en (kontroll) binär siffra till varje ord och välja siffran för denna siffra så att det totala antalet enheter i bilden av valfritt tal är till exempel udda. Ett enstaka fel i valfri siffra i det överförda ordet (inklusive, kanske, i kontrollsiffran) kommer att ändra pariteten för det totala antalet enheter. Modulo 2-räknare, som räknar antalet ettor som finns bland de binära siffrorna i ett nummer, ger en signal om förekomsten av fel. I det här fallet är det omöjligt att veta i vilken position av ordet felet inträffade, och därför finns det inget sätt att korrigera det. Fel som uppstår samtidigt i två, fyra, etc. - i ett jämnt antal siffror förblir också obemärkta. Det antas att dubbla och ännu mer flera fel är osannolikt.

Självkorrigerande koder

Koder där automatisk felkorrigering är möjlig kallas självkorrigerande. För att bygga en självkorrigerande kod utformad för att korrigera enstaka fel räcker det inte med en kontrollsiffra. Som framgår av det följande måste antalet styrbitar väljas så att olikheten eller är uppfylld , där är antalet binära informationsbitar i kodordet. Minimivärdena på k för givna värden på m, hittade i enlighet med denna olikhet, anges i tabellen. $k$ $2^k \geq k+m+1$ $k \geq \log_2(k+m+1)$ $m$

Räckvidd m	kmin _
ett	2
2-4	3
5-11	fyra
12-26	5
27-57	6

Av störst intresse är binära blockkorrigeringskoder . Vid användning av sådana koder överförs information i form av block av samma längd, och varje block kodas och avkodas oberoende av det andra. I nästan alla blockkoder kan symboler delas upp i information och kontroll eller kontroll. Således är alla ord indelade i tillåtna (för vilka förhållandet mellan information och kontrolltecken är möjligt) och förbjudna.

Huvudegenskaper hos självkorrigerande koder:

Antalet tillåtna och förbjudna kombinationer. Om - antalet tecken i blocket, - antalet kontrolltecken i blocket, - antalet informationstecken, då - antalet möjliga kodkombinationer, - antalet tillåtna kodkombinationer, - antalet förbjudna kombinationer . $n$ $r$ $k$ $2^{n}$ $2^k$ ${\displaystyle 2^{n}-2^{k))$
Kodredundans. Värdet kallas redundansen för korrigeringskoden. ${\tfrac {r}{n))$
Minsta kodavstånd. Minsta kodavstånd är det minsta antalet förvrängda symboler som krävs för att övergå från en tillåten kombination till en annan. $d$
Antalet fel som upptäckts och korrigerats. Om är antalet fel som koden kan fixa, så är det nödvändigt och tillräckligt att $g$ $d\geq 2g+1$
Korrigerande koder.

Plotkin- gränsen ger en övre gräns för kodavståndet:

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 anger det maximala antalet tillåtna kodkombinationer:

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

där är antalet kombinationer av element efter element. Härifrån kan du få ett uttryck för att uppskatta antalet checksymboler:

C_n^i

n

i

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

För värden är skillnaden mellan Hamming-gränsen och Plotkin-gränsen liten. $(d/n)\leq 0{,}3$

Varshamov-Gilberts gräns för stort n definierar en nedre gräns för antalet checksymboler:

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

Alla ovanstående uppskattningar ger en uppfattning om den övre gränsen vid fasta och eller en lägre uppskattning av antalet checksymboler. $d$ $n$ $k$

Hamming-kod

Konstruktionen av Hamming-koder är baserad på principen att kontrollera antalet enstaka tecken för paritet: ett sådant element läggs till sekvensen så att antalet enstaka tecken i den resulterande sekvensen är jämnt:

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

Tecknet här betyder modulo 2-tillägg : $\ plus$

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

Om - då finns det inget fel, om - då ett enda fel. $S=0$ $S=1$

En sådan kod kallas eller . Den första siffran är antalet sekvenselement, den andra är antalet informationstecken. $(k+1,\ k)$ $(n,\ n-1)$

För varje antal checksymboler finns det en klassisk Hamming-kod med markeringar: $r=3,\ 4,\ 5\ ...$

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

det vill säga - .

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

Med andra värden erhålls den så kallade trunkerade koden, till exempel den internationella telegrafkoden MTK-2, som har . Det kräver en Hamming-kod, som är en trunkerad version av klassikern $k$ $k = 5$ $(9,\ 5),$ $(15,\ 11).$

Tänk till exempel på den klassiska Hamming-koden . Låt oss gruppera bocksymbolerna enligt följande: $(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}.

Att få kodordet ser ut så här:

\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}

Dekoderns ingång får ett kodord , där symboler är markerade med ett streck, vilket kan förvrängas till följd av störningar. I avkodaren i felkorrigeringsläget byggs en sekvens av syndrom: $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})$ kallas sekvenssyndromet.

Att få syndromet ser ut så här:

\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	ett	0	0	0	ett	0	ett
0	0	0	ett	0	ett	ett	ett	0	0	ett	ett	ett	0
0	0	ett	0	ett	ett	0	ett	0	ett	0	0	ett	ett
0	0	ett	ett	ett	0	ett	ett	0	ett	ett	0	0	0
0	ett	0	0	ett	ett	ett	ett	ett	0	0	0	ett	0
0	ett	0	ett	ett	0	0	ett	ett	0	ett	0	0	ett
0	ett	ett	0	0	0	ett	ett	ett	ett	0	ett	0	0
0	ett	ett	ett	0	ett	0	ett	ett	ett	ett	ett	ett	ett

Kodorden för Hamming-koden anges i tabellen. $(7,\ 4)$

Syndromet indikerar att det inte finns någon förvrängning i sekvensen. Varje icke-noll-syndrom motsvarar ett visst felmönster, som korrigeras vid avkodningsstadiet. $(0,0,0)$

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

För koden i tabellen till höger anges syndrom som inte är noll och deras motsvarande felkonfigurationer (för formuläret: ). $(7,4)$ $i_1$ $i_2$ $i_3$ $i_4$ $r_{1}$ $r_{2}$ $r_3$

Kodningsalgoritm

Anta att vi behöver generera en Hamming-kod för något informationskodord. Låt oss ta ett 15-bitars kodord som exempel, även om algoritmen är lämplig för kodord av vilken längd som helst. I tabellen nedan ger den första raden positionsnumren i kodordet, den andra raden ger bitbeteckningen och den tredje raden ger bitvärdena. $x_{1}\dots \ x_{15},$

ett	2	3	fyra	5	6	7	åtta	9	tio	elva	12	13	fjorton	femton
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
ett	0	0	ett	0	0	ett	0	ett	ett	ett	0	0	0	ett

Låt oss infoga kontrollbitar i informationsordet på ett sådant sätt att deras positionsnummer är heltalpotenser av två: 1, 2, 4, 8, 16 ... Vi får ett 20-bitars ord med 15 information och 5 kontrollbitar. Initialt sätts styrbitarna till noll. I figuren är kontrollbitarna markerade i rosa. ${\displaystyle r_{0}\dots \ r_{4))$

ett	2	3	fyra	5	6	7	åtta	9	tio	elva	12	13	fjorton	femton	16	17	arton	19	tjugo
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	ett	0	0	0	ett	0	0	0	ett	0	ett	ett	ett	0	0	0	0	ett

I allmänhet är antalet kontrollbitar i ett kodord lika med den binära logaritmen för ett nummer ett större än antalet bitar i kodordet (inklusive kontrollbitar); logaritmen avrundas uppåt. Till exempel kräver ett 1-bitars informationsord två kontrollbitar, ett 2-, 3- eller 4-bitars informationsord kräver tre, ett 5...11-bitars informationsord kräver fyra, ett 12...26- bitinformationsord kräver fem, och så vidare.

Låt oss lägga till 5 rader i tabellen (enligt antalet kontrollbitar), där vi kommer att placera transformationsmatrisen. Varje rad kommer att motsvara en kontrollbit (nollkontrollbiten är den översta raden, den fjärde är den nedersta), varje kolumn kommer att motsvara en bit av det kodade ordet. I varje kolumn i transformationsmatrisen placerar vi det binära numret för denna kolumn, och ordningen på bitarna kommer att omvändas - den minst signifikanta biten kommer att placeras på den översta raden, den mest signifikanta - i botten. Till exempel kommer den tredje kolumnen i matrisen att innehålla siffrorna 11000, vilket motsvarar den binära representationen av talet tre: 00011.

ett	2	3	fyra	5	6	7	åtta	9	tio	elva	12	13	fjorton	femton	16	17	arton	19	tjugo
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	ett	0	0	0	ett	0	0	0	ett	0	ett	ett	ett	0	0	0	0	ett
ett	0	ett	0	ett	0	ett	0	ett	0	ett	0	ett	0	ett	0	ett	0	ett	0	r0 _
0	ett	ett	0	0	ett	ett	0	0	ett	ett	0	0	ett	ett	0	0	ett	ett	0	r1 _
0	0	0	ett	ett	ett	ett	0	0	0	0	ett	ett	ett	ett	0	0	0	0	ett	r2 _
0	0	0	0	0	0	0	ett	ett	ett	ett	ett	ett	ett	ett	0	0	0	0	0	r3 _
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	ett	ett	ett	ett	ett	r4 _

I den högra delen av tabellen lämnades en kolumn tom, där vi placerar resultaten av beräkningen av kontrollbitarna. Vi beräknar kontrollbitarna enligt följande: vi tar en av raderna i transformationsmatrisen (till exempel ) och hittar dess skalära produkt med kodordet, det vill säga vi multiplicerar motsvarande bitar i båda raderna och hittar summan av Produkter. Om summan visade sig vara större än ett, hittar vi resten av dess division med 2. Med andra ord, vi räknar hur många gånger det finns enheter på samma positioner i kodordet och motsvarande rad i matrisen, och ta detta nummer modulo 2. $r_{0}$

Om vi beskriver denna process i termer av matrisalgebra, är operationen en multiplikation av transformationsmatrisen med kodordets matriskolumn, vilket resulterar i en matriskolumn av kontrollbitar, som måste tas modulo 2.

Till exempel för raden : $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 resulterande kontrollbitarna infogas i kodordet istället för de nollor som fanns där tidigare. I analogi finner vi kontrollbitarna i de återstående raderna. Hamming-kodningen är klar. Det mottagna kodordet är 11110010001011110001.

ett	2	3	fyra	5	6	7	åtta	9	tio	elva	12	13	fjorton	femton	16	17	arton	19	tjugo
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
ett	ett	ett	ett	0	0	ett	0	0	0	ett	0	ett	ett	ett	ett	0	0	0	ett
ett	0	ett	0	ett	0	ett	0	ett	0	ett	0	ett	0	ett	0	ett	0	ett	0	r0 _	ett
0	ett	ett	0	0	ett	ett	0	0	ett	ett	0	0	ett	ett	0	0	ett	ett	0	r1 _	ett
0	0	0	ett	ett	ett	ett	0	0	0	0	ett	ett	ett	ett	0	0	0	0	ett	r2 _	ett
0	0	0	0	0	0	0	ett	ett	ett	ett	ett	ett	ett	ett	0	0	0	0	0	r3 _	0
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	ett	ett	ett	ett	ett	r4 _	ett

Avkodningsalgoritm

Hamming-avkodningsalgoritmen är helt identisk med kodningsalgoritmen. Transformationsmatrisen för motsvarande dimension multipliceras med kodordets kolumnmatris, och varje element i den resulterande kolumnmatrisen tas modulo 2. Den resulterande kolumnmatrisen kallas "syndrommatrisen". Det är lätt att verifiera att ett kodord genererat i enlighet med algoritmen som beskrivs i föregående avsnitt alltid ger en nollsyndrommatris.

Syndrommatrisen blir icke-noll om, som ett resultat av ett fel (till exempel vid sändning av ett ord över en brusig kommunikationslinje), en av bitarna i det ursprungliga ordet har ändrat sitt värde. Anta till exempel att i kodordet som erhölls i föregående avsnitt har den sjätte biten ändrat sitt värde från noll till ett (indikeras med rött i figuren). Då får vi följande matris av syndrom.

ett	2	3	fyra	5	6	7	åtta	9	tio	elva	12	13	fjorton	femton	16	17	arton	19	tjugo
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
ett	ett	ett	ett	0	ett	ett	0	0	0	ett	0	ett	ett	ett	ett	0	0	0	ett
ett	0	ett	0	ett	0	ett	0	ett	0	ett	0	ett	0	ett	0	ett	0	ett	0	s0 _	0
0	ett	ett	0	0	ett	ett	0	0	ett	ett	0	0	ett	ett	0	0	ett	ett	0	s 1	ett
0	0	0	ett	ett	ett	ett	0	0	0	0	ett	ett	ett	ett	0	0	0	0	ett	s2 _	ett
0	0	0	0	0	0	0	ett	ett	ett	ett	ett	ett	ett	ett	0	0	0	0	0	s3 _	0
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	ett	ett	ett	ett	ett	s4 _	0

Observera att med ett enda fel är syndrommatrisen alltid en binär post (den minst signifikanta siffran i den översta raden) av positionsnumret där felet inträffade. I exemplet ovan motsvarar syndrommatrisen (01100) det binära talet 00110 eller decimal 6, vilket innebär att felet inträffade i den sjätte biten.

Applikation

Hamming-kod används i vissa lagringsapplikationer, särskilt RAID 2 . Dessutom har Hamming-metoden länge använts i ECC- minnet och låter dig korrigera enstaka fel och upptäcka dubbla fel i farten.

Se även

Anteckningar

↑ Hamming Codes - "Allt om Hi-Tech" . all-ht.ru. Tillträdesdatum: 20 januari 2016. Arkiverad från originalet 15 januari 2016. (obestämd)

Litteratur

Peterson W., Weldon E. Felkorrigerande koder: Per. från engelska. Moskva: Mir, 1976, 594 s.
Penin P. E., Filippov L. N. Radiotekniska informationsöverföringssystem. Moskva: Radio och kommunikation, 1984, 256 s.
Blahut R. Teori och praktik av felkontrollkoder. Per. från engelska. M.: Mir, 1986, 576 sid.