Hamming-kod

Binära Hamming-koder
Binära Hamming-koder
	Hamming(7,4)-koden (med r = 3 )
Döpt efter	Richard W. Hamming
Klassificering
Typ	Linjär blockkod
Blocklängd	2 r − 1 där r ≥ 2
Meddelandets längd	2 r − r − 1
Betygsätta	1 − r / (2 r − 1)
Distans	3
Alfabetets storlek	2
Notation	[2 r − 1, 2 r − r − 1, 3] 2 -kod
Egenskaper
	perfekt kod

Inom datavetenskap och telekommunikation är Hamming-koder en familj av linjära felkorrigerande koder . Hamming-koder kan upptäcka enbits- och tvåbitarsfel, eller korrigera enbitsfel utan upptäckt av okorrigerade fel. Däremot kan den enkla paritetskoden inte korrigera fel och kan endast detektera ett udda antal felbitar. Hamming-koder är perfekta koder , det vill säga de uppnår högsta möjliga hastighet för koder med deras blocklängd och minsta avstånd på tre. Richard W. Hamming uppfann Hamming-koder 1950 som ett sätt att automatiskt korrigera fel som introducerades av hålkortsläsare . I sin ursprungliga artikel utvecklade Hamming sin allmänna idé, men fokuserade specifikt på Hamming(7,4) -koden som lägger till tre paritetsbitar till fyra databitar.

I matematiska termer är Hamming-koder en klass av binär linjär kod. För varje heltal $r \geq 2$ finns ett kodord med blocklängd $n = 2 r - 1$ och meddelandelängd $k = 2 r - r - 1$ . Därför är hastigheten för Hamming-koder $R = k / n = 1 - r / (2 r - 1)$ , vilket är den högsta möjliga för koder med minsta avstånd på tre (dvs. det minimala antalet bitändringar som krävs för att gå från någon kodord till något annat kodord är tre) och blocklängd $2 r - 1$ . Paritetskontrollmatrisen för en Hamming-kod konstrueras genom att lista alla kolumner med längden $r$ som inte är noll, vilket betyder att den dubbla koden för Hamming-koden är den förkortade Hadamard-koden . Paritetskontrollmatrisen har egenskapen att två valfria kolumner är parvis linjärt oberoende .

På grund av den begränsade redundans som Hamming-koder lägger till data, kan de bara upptäcka och korrigera fel när felfrekvensen är låg. Detta är fallet i datorminne (vanligtvis RAM), där bitfel är extremt sällsynta och Hamming-koder används i stor utsträckning, och ett RAM med detta korrigeringssystem är ett ECC RAM (ECC-minne ) . I detta sammanhang används ofta en utökad Hamming-kod med en extra paritetsbit. Utökade Hamming-koder uppnår ett Hamming-avstånd på fyra, vilket gör att avkodaren kan skilja mellan när högst ett enbitsfel inträffar och när några tvåbitarsfel uppstår. I denna mening är utökade Hamming-koder enkelfelskorrigering och dubbelfelsdetektering, förkortat SECDED .

Historia

Richard Hamming , uppfinnaren av Hamming-koder, arbetade på Bell Labs i slutet av 1940-talet på Bell Model V -datorn, en elektromekanisk reläbaserad maskin med cykeltider i sekunder. Inmatningen matades in på stansad papperstejp , sju åttondelar av en tum bred, som hade upp till sex hål per rad. Under vardagar, när fel i reläerna upptäcktes, stannade maskinen och blinkade med lampor så att operatörerna kunde åtgärda problemet. Under arbetstid och på helger, när det inte fanns några operatörer, gick maskinen helt enkelt vidare till nästa jobb.

Hamming arbetade på helgerna och blev allt mer frustrerad över att behöva starta om sina program från början på grund av upptäckta fel. I en inspelad intervju sa Hamming: "Och så jag sa, 'fan fan, om maskinen kan upptäcka ett fel, varför kan den inte lokalisera felets position och rätta till det?'". Under de närmaste åren arbetade han med problemet med felkorrigering och utvecklade en allt kraftfullare uppsättning algoritmer. 1950 publicerade han vad som nu är känt som Hamming-kod, som fortfarande används i applikationer som ECC-minne .

Koder före Hamming

Ett antal enkla feldetekterande koder användes före Hamming-koder, men ingen var lika effektiv som Hamming-koder i samma overhead.

Paritet

Paritet lägger till en enda bit som indikerar om antalet ettor (bitpositioner med värden ett) i föregående data var jämnt eller udda . Om ett udda antal bitar ändras i överföringen kommer meddelandet att ändra paritet och felet kan detekteras vid denna punkt; dock kan biten som ändrades ha varit paritetsbiten själv. Den vanligaste konventionen är att ett paritetsvärde på ett indikerar att det finns ett udda antal ettor i data, och ett paritetsvärde på noll indikerar att det finns ett jämnt antal ettor. Om antalet ändrade bitar är jämnt kommer kontrollbiten att vara giltig och felet kommer inte att upptäckas.

Dessutom indikerar inte paritet vilken bit som innehöll felet, även när den kan upptäcka det. Uppgifterna måste kasseras helt och sändas på nytt från grunden. På ett bullrigt överföringsmedium kan en framgångsrik överföring ta lång tid eller kanske aldrig inträffa. Men även om kvaliteten på paritetskontrollen är dålig, eftersom den bara använder en enda bit, resulterar denna metod i minsta overhead.

Två-av-fem-kod

En två-av-fem-kod är ett kodningsschema som använder fem bitar som består av exakt tre nollor och två ettor. Detta ger tio möjliga kombinationer, tillräckligt för att representera siffrorna 0–9. Detta schema kan upptäcka alla enstaka bitfel, alla udda numrerade bitfel och några jämna bitar (till exempel vändning av båda 1-bitarna). Den kan dock fortfarande inte korrigera något av dessa fel.

Upprepning

En annan kod som användes vid den tiden upprepade varje databit flera gånger för att säkerställa att den skickades korrekt. Till exempel, om databiten som ska skickas är en 1, kommer en n = 3 upprepningskod att skicka 111. Om de tre mottagna bitarna inte är identiska, inträffade ett fel under överföringen. Om kanalen är tillräckligt ren kommer för det mesta bara en bit att ändras i varje trippel. Därför motsvarar 001, 010 och 100 vardera en 0-bit, medan 110, 101 och 011 motsvarar en 1-bit, med den större mängden siffror som är samma ('0' eller en '1') som indikerar vad databiten ska vara. En kod med denna förmåga att rekonstruera det ursprungliga meddelandet i närvaro av fel är känd som en felkorrigerande kod. Denna trippelrepetitionskod är en Hamming-kod med m = 2, eftersom det finns två paritetsbitar, och 2 ² − 2 − 1 = 1 databit.

Sådana koder kan dock inte reparera alla fel korrekt. I vårt exempel, om kanalen vänder två bitar och mottagaren får 001, kommer systemet att upptäcka felet, men dra slutsatsen att den ursprungliga biten är 0, vilket är felaktigt. Om vi ökar bitsträngens storlek till fyra kan vi upptäcka alla tvåbitsfel men kan inte korrigera dem (mängden paritetsbitar är jämnt); vid fem bitar kan vi både upptäcka och korrigera alla tvåbitarsfel, men inte alla trebitarsfel.

Att öka storleken på paritetsbitsträngen är dessutom ineffektivt, vilket minskar genomströmningen med tre gånger i vårt ursprungliga fall, och effektiviteten sjunker drastiskt när vi ökar antalet gånger varje bit dupliceras för att upptäcka och korrigera fler fel.

Beskrivning

Om fler felkorrigerande bitar ingår i ett meddelande, och om dessa bitar kan arrangeras så att olika felaktiga bitar ger olika felresultat, kan dåliga bitar identifieras. I ett sjubitarsmeddelande finns det sju möjliga enbitsfel, så tre felkontrollbitar skulle potentiellt kunna specificera inte bara att ett fel inträffade utan också vilken bit som orsakade felet.

Hamming studerade de befintliga kodningsscheman, inklusive två av fem, och generaliserade deras koncept. Till att börja med utvecklade han en nomenklatur för att beskriva systemet, inklusive antalet databitar och felkorrigeringsbitar i ett block. Till exempel inkluderar paritet en enda bit för vilket dataord som helst, så om man antar ASCII- ord med sju bitar, beskrev Hamming detta som en ( 8,7) kod, med totalt åtta bitar, varav sju är data. Upprepningsexemplet skulle vara (3,1) , enligt samma logik. Kodhastigheten är det andra talet dividerat med det första, för vårt upprepningsexempel, 1/3 .

Hamming märkte också problemen med att vända två eller flera bitar och beskrev detta som "avståndet" (det kallas nu Hamming-avståndet efter honom). Pariteten har ett avstånd på 2, så en bit flip kan upptäckas men inte korrigeras, och alla två bit flips kommer att vara osynliga. (3,1)-repetitionen har ett avstånd på 3, eftersom tre bitar måste vändas i samma trippel för att få ett annat kodord utan synliga fel. Den kan korrigera enbitsfel eller den kan upptäcka - men inte korrigera - tvåbitsfel. En (4,1) upprepning (varje bit upprepas fyra gånger) har ett avstånd på 4, så vändning av tre bitar kan upptäckas, men inte korrigeras. När tre bitar vänder i samma grupp kan det finnas situationer där ett försök att korrigera kommer att producera fel kodord. I allmänhet kan en kod med avstånd k upptäcka men inte korrigera k − 1 fel.

Hamming var intresserad av två problem samtidigt: öka avståndet så mycket som möjligt, samtidigt som kodhastigheten ökade så mycket som möjligt. Under 1940-talet utvecklade han flera kodningsscheman som var dramatiska förbättringar av befintliga koder. Nyckeln till alla hans system var att ha paritetsbitarna överlappande, så att de lyckades kontrollera varandra såväl som data.

Allmän algoritm

Följande allmänna algoritm genererar en enkelfelskorrigeringskod (SEC) för valfritt antal bitar. Huvudidén är att välja de felkorrigerande bitarna så att index-XOR ( XOR för alla bitpositioner som innehåller en 1) är 0. Vi använder positionerna 1, 10, 100, etc. (i binärt) som felet -korrigerande bitar, vilket garanterar att det är möjligt att ställa in de felkorrigerande bitarna så att index-XOR för hela meddelandet är 0. Om mottagaren tar emot en sträng med index-XOR 0, kan de dra slutsatsen att det inte fanns några korruptioner, och annars indikerar index-XOR indexet för den skadade biten.

En algoritm kan härledas från följande beskrivning:

Numrera bitarna med början från 1: bit 1, 2, 3, 4, 5, 6, 7, etc.
Skriv bittalen i binärt: 1, 10, 11, 100, 101, 110, 111, etc.
Alla bitpositioner som är potenser av två (har en enda 1-bit i binär form av sin position) är paritetsbitar: 1, 2, 4, 8, etc. (1, 10, 100, 1000)
Alla andra bitpositioner, med två eller fler 1-bitar i binär form av sin position, är databitar.
Varje databit ingår i en unik uppsättning av 2 eller fler paritetsbitar, som bestäms av den binära formen av dess bitposition.
1. Paritetsbit 1 täcker alla bitpositioner som har den minst signifikanta bituppsättningen: bit 1 (paritetsbiten själv), 3, 5, 7, 9, etc.
2. Paritetsbit 2 täcker alla bitpositioner som har den näst minst signifikanta bituppsättningen: bitarna 2-3, 6-7, 10-11, etc.
3. Paritetsbit 4 täcker alla bitpositioner som har den tredje minst signifikanta bituppsättningen: bitarna 4–7, 12–15, 20–23, etc.
4. Paritetsbit 8 täcker alla bitpositioner som har den fjärde minst signifikanta bituppsättningen: bitarna 8–15, 24–31, 40–47, etc.
5. I allmänhet täcker varje paritetsbit alla bitar där den bitvisa OCH för paritetspositionen och bitpositionen är icke-noll.

Om en byte av data som ska kodas är 10011010, då skulle dataordet (med _ för att representera paritetsbitarna) vara __1_001_1010, och kodordet är 011100101010.

Valet av paritet, jämn eller udda, är irrelevant men samma val måste användas för både kodning och avkodning.

Denna allmänna regel kan visas visuellt:

Kodade databitar		p1	p2	d1	p4	d2	d3	d4	p8	d5	d6	d7	d8	d9	d10	d11	sid 16	d12	d13	d14	d15
Bitposition		1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	…
Paritetsbittäckning _ _	p1
	p2
	p4
	p8
	p16

Endast 20 kodade bitar (5 paritet, 15 data) visas men mönstret fortsätter i det oändliga. Det viktigaste med Hamming-koder som kan ses från visuell inspektion är att varje given bit ingår i en unik uppsättning paritetsbitar. För att leta efter fel, kontrollera alla paritetsbitar. Mönstret av fel, som kallas felsyndromet , identifierar biten som är fel. Om alla paritetsbitar är korrekta finns det inget fel. Annars identifierar summan av positionerna för de felaktiga paritetsbitarna den felaktiga biten. Till exempel, om paritetsbitarna i positionerna 1, 2 och 8 indikerar ett fel, då är bit 1+2+8=11 felaktigt. Om endast en paritetsbit indikerar ett fel, är själva paritetsbiten fel.

Med $m$ paritetsbitar kan bitar från 1 upp till $2^{m}-1$ täckas. Efter diskontering av paritetsbitarna $2^{m}-m-1$ bitar för användning som data. Eftersom $m$ varierar får vi alla möjliga Hamming-koder:

Paritetsbitar	Totalt bitar	Databitar	namn	Betygsätta
2	3	1	Hamming(3,1) (Trippel repetitionskod )	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
9	511	502	Hamming(511 502)	502/511 ≈ 0,982
…
$m$	$n=2^{m}-1$	$k=2^{m}-m-1$	Hamming $(2^{m}-1,2^{m}-m-1)$	$(2^{m}-m-1)/(2^{m}-1)$

Hamming-koder med extra paritet (SECDED)

Hamming-koder har ett minimiavstånd på 3, vilket innebär att avkodaren kan upptäcka och korrigera ett enstaka fel, men den kan inte skilja ett dubbelbitfel för något kodord från ett enstaka bitfel för ett annat kodord. Sålunda kommer vissa dubbelbitsfel att felaktigt avkodas som om de vore enkelbitsfel och därför förbli oupptäckta, såvida ingen korrigering görs.

För att avhjälpa denna brist kan Hamming-koder utökas med en extra paritetsbit. På så sätt är det möjligt att öka det minsta avståndet för Hamming-koden till 4, vilket gör att avkodaren kan skilja mellan enkelbitsfel och tvåbitarsfel. Således kan avkodaren detektera och korrigera ett enda fel och samtidigt detektera (men inte korrigera) ett dubbelfel.

Om avkodaren inte försöker korrigera fel kan den på ett tillförlitligt sätt upptäcka trippelbitfel. Om avkodaren korrigerar fel, kommer vissa trippelfel att förväxlas med enstaka fel och "korrigeras" till fel värde. Felkorrigering är därför en kompromiss mellan säkerhet (förmågan att på ett tillförlitligt sätt upptäcka trippelbitfel) och resiliens (förmågan att fortsätta fungera inför enkelbitsfel).

Denna utökade Hamming-kod var populär i datorminnessystem, från och med IBM 7030 Stretch 1961, där den är känd som SECDED (eller SEC-DED, förkortat från single error correction, double error detection) . Serverdatorer under 2000-talet, samtidigt som de vanligtvis håller SECDED-skyddsnivån, använder inte längre Hammings metod, utan förlitar sig istället på designen med längre kodord (128 till 256 bitar av data) och modifierade balanserade paritetskontrollträd. (72,64) Hamming-koden är fortfarande populär i vissa hårdvarudesigner, inklusive Xilinx FPGA- familjer.

[7,4] Hamming-kod

Grafisk skildring av de fyra databitarna och tre paritetsbitarna och vilka paritetsbitar som gäller för vilka databitar

1950 introducerade Hamming Hamming-koden [7,4]. Den kodar fyra databitar till sju bitar genom att lägga till tre paritetsbitar. Den kan upptäcka och korrigera enbitsfel. Med tillägg av en övergripande paritetsbit kan den också upptäcka (men inte korrigera) dubbelbitsfel.

Konstruktion av G och H

Matrisen $\mathbf {G} :={\begin{pmatrix}{\begin{array}{c|c}I_{k}&-A^{\text {T}}\\\end{array}}\end{pmatrix}}$ kallas en (kanonisk) generatormatris av en linjär ( n , k ) kod,

och $\mathbf {H} :={\begin{pmatrix}{\begin{array}{c|c}A&I_{nk}\\\end{array}} \end{pmatrix}}$ kallas en paritetskontrollmatris .

Detta är konstruktionen av G och H i standard (eller systematisk) form. Oavsett form G och H för linjära blockkoder uppfylla

${\displaystyle \mathbf {H} \,\mathbf {G} ^{\text{T}}=\mathbf {0} } ,$ en matris med helt nollor.

Eftersom [7, 4, 3] = [ n , k , d ] = [2 ^m − 1, 2 ^m − 1 − m , 3]. Paritetskontrollmatrisen H för en Hamming - kod konstrueras genom att lista alla kolumner med längden m som är parvis oberoende.

Sålunda är H en matris vars vänstra sida är alla n -tuplar som inte är noll, där ordningen på n -tuplarna i matrisens kolumner inte spelar någon roll. Den högra sidan är bara ( n − k ) -identitetsmatrisen .

Så G kan erhållas från H genom att transponera den vänstra sidan av H med identiteten k - identitetsmatris på vänster sida av G .

Kodgeneratormatrisen $\mathbf {G}$ och paritetskontrollmatrisen $\displaystyle \mathbf {H} }$ { är:

$&1&0\\0&1&0&0&1&0&1&1\\0&0&1&1&1&1&0&0&1&1&1&1&1&0&0&0 slut{ pmatrix}}_{4,7}}$

och

$\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\end{pmatrix}}_{3,7}.$

Slutligen kan dessa matriser muteras till ekvivalenta icke-systematiska koder genom följande operationer:

Kolumnpermutationer (byta kolumner)
Elementära radoperationer (ersätter en rad med en linjär kombination av rader)

Kodning

Exempel

Från matrisen ovan har vi 2 ^k = 2 ⁴ = 16 kodord. Låt ${\vec {a}}$ vara en radvektor av binära databitar, ${\vec {a}}=[a_{1},a_{2},a_{3},a_{4}],\quad a_{i}\in \{0,1\}$ . Kodordet ${\vec {x}}$ för någon av de 16 möjliga datavektorerna ${\vec {a}}$ ges av standardmatrisprodukten ${\vec {x}}={\vec {a}}G$ där summeringsoperationen görs modulo-2.

Låt till exempel ${\vec {a}}=[1,0,1,1]$ . Med hjälp av generatormatrisen $G$ från ovan har vi (efter att ha tillämpat modulo 2, på summan),

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

[7,4] Hammingkod med en extra paritetsbit

Samma [7,4] exempel från ovan med en extra paritetsbit. Detta diagram är inte avsett att motsvara matrisen H för detta exempel.

[7,4] Hamming-koden kan enkelt utökas till en [8,4]-kod genom att lägga till en extra paritetsbit ovanpå det (7,4) kodade ordet (se Hamming(7,4) ). Detta kan sammanfattas med de reviderade matriserna:

&0&0&0&0&1\\1&0&0&0&1&1&1&1&0&0&1&1&1&1&0 1&0&1&0&0&1&0 \end{pmatrix}}_{4,8}}

och

{\displaystyle \mathbf {H} :={\begin{pmatrix}1&0&1&0&1&0&1&0\\0&1&1&0&0&0&1&1&0\\0&0&0&1&1&1&1&0\\1&1&1&1&1&1&1&1\}}_{pmatrix}.

Observera att H inte är i standardform. För att erhålla G kan elementära radoperationer användas för att erhålla en ekvivalent matris till H i systematisk form:

\mathbf {H} =\left({\begin{array}{cccc|cccc}0&1&1&1&1&0&0&0\\1&0&1&1&0&1&0&0\\1&1&0&1&0&0&1&0\\1&1&1&1&0&0&0}_}&1,\end{1

Till exempel är den första raden i denna matris summan av den andra och tredje raden av H i icke-systematisk form. Genom att använda den systematiska konstruktionen för Hamming-koder från ovan, är matrisen A uppenbar och den systematiska formen av G skrivs som

{\displaystyle \mathbf {G} =\left({\begin{array}{cccc|cccc}1&0&0&0&0&1&1&1\\0&1&0&0&1&0&1&1\\0&0&1&0&1&1&0&1\\0&0&0&1&1&1_}&0},\end)

Den icke-systematiska formen av G kan radreduceras (med hjälp av elementära radoperationer) för att matcha denna matris.

Tillägget av den fjärde raden beräknar effektivt summan av alla kodordsbitar (data och paritet) som den fjärde paritetsbiten.

00 Till exempel kodas 1011 (med den icke-systematiska formen av G i början av detta avsnitt) till 01 1 011 där blå siffror är data; röda siffror är paritetsbitar från [7,4] Hamming-koden; och den gröna siffran är paritetsbiten som adderas av [8,4]-koden. Den gröna siffran gör pariteten för kodorden [7,4] jämn.

Slutligen kan det visas att minimiavståndet har ökat från 3, i [7,4]-koden, till 4 i [8,4]-koden. Därför kan koden definieras som [8,4] Hamming-kod.

För att avkoda [8,4] Hamming-koden, kontrollera först paritetsbiten. Om paritetsbiten indikerar ett fel, kommer en felkorrigering ([7,4] Hamming-koden) att indikera felplatsen, med "inget fel" som indikerar paritetsbiten. Om paritetsbiten är korrekt, kommer enstaka felkorrigering att indikera (bitvis) exklusiva-eller av två felplatser. Om platserna är lika ("inget fel") så har ett dubbelbitfel antingen inte inträffat eller så har det upphört. Annars har ett dubbelbitfel inträffat.

Se även

Anteckningar

Hamming, Richard Wesley (1950). "Feldetektering och felkorrigeringskoder" (PDF) . Bell System teknisk journal . 29 (2): 147–160. doi : 10.1002/j.1538-7305.1950.tb00463.x . S2CID 61141773 . Arkiverad (PDF) från originalet 2022-10-09.
Moon, Todd K. (2005). Felkorrigeringskodning . New Jersey : John Wiley & Sons . ISBN 978-0-471-64800-0 .
MacKay, David JC (september 2003). Informationsteori, slutlednings- och inlärningsalgoritmer . Cambridge : Cambridge University Press . ISBN 0-521-64298-1 .
DK Bhattacharryya, S. Nandi. "En effektiv klass av SEC-DED-AUED-koder". 1997 Internationellt symposium om parallella arkitekturer, algoritmer och nätverk (ISPAN '97) . s. 410–415. doi : 10.1109/ISPAN.1997.645128 .
"Matematisk utmaning april 2013 Felkorrigerande koder" (PDF) . swissQuant Group Leadership Team. April 2013. Arkiverad (PDF) från originalet 2017-09-12.
Kythe, Dave K.; Kythe, Prem K. (28 juli 2017). "Utökade Hamming-koder" . Algebraisk och stokastisk kodningsteori . CRC Tryck. s. 95–116. ISBN 978-1-351-83245-8 .

externa länkar

Binära Hamming-koder
Hamming(7,4)-koden (med $r = 3$ )
Döpt efter	Richard W. Hamming
Klassificering
Typ	Linjär blockkod
Blocklängd	$2 r - 1$ där $r \geq 2$
Meddelandets längd	$2 r - r - 1$
Betygsätta	$.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px} 1 − r / (2 r − 1)$
Distans	$3$
Alfabetets storlek	$2$
Notation	$[2 r - 1, 2 r - r - 1, 3] 2$ -kod
Egenskaper
perfekt kod