Hammingavstånd

Hammingavstånd (äldre beteckning: Hammingdistans), uppkallat efter Richard Hamming, är en storhet i informationsteorin, som i ett visst avseende anger skillnaden mellan två lika långa teckensträngar eller ord. Begreppet används i samband med olika slags felkorrigerande koder, vilka används för att upptäcka och korrigera fel vid informationsöverföring.

Exempel

Två exempelavstånd: 100→011 har avståndet 3 (röd väg); 010→111 har avståndet 2 (blå väg)

Två exempelavstånd: 0100→1001 har avståndet 3 (röd väg); 0110→1110 har avståndet 1 (blåväg)

Hammingavståndet mellan dessa är antalet färgade tecken:

• "toned" och "roses" är 3.
• 1011101 och 1001001 är 2.
• 2173896 och 2233796 är 3.

Teori

Om man har ett alfabet, som består av q ≥ 2 tecken, till exempel någon av mängderna {0,1} eller {1,x,2}, kan man bilda "ord" med n ≥ 1 tecken. Det finns $q^{n}$ sådana ord av längden n, vilka representerar tal i det binära talsystemet eller stryktipsrader. En kod är här en mängd av ord av lika längd. En sådan kod kan korrigera e stycken fel, om Hammingavståndet mellan varje par av olika kodord är minst 2e + 1. I följande kod, som korrigerar ett fel, är orden skrivna lodrätt:

x x x 1 1 1 2 2 2

x 1 2 x 1 2 x 1 2

x 1 2 1 2 x 2 x 1

x 2 1 1 x 2 2 1 x

En kod, som korrigerar e stycken fel benämns tättpackad, om varje ord av längden n har Hammingavståndet högst 2e + 1 från något annat ord i koden. Koden ovan är tättpackad, vilket gör den användbar för konstruktion av tipssystem. Den garanterar tre rätt vid fyra tippade matcher.

Då q är en primtalspotens har man visat att det finns oändligt många tättpackade koder, som korrigerar ett fel, och att det existerar exakt två särskilda, "singulära", tättpackade koder, vilka korrigerar mer än ett fel. En av de båda singulära koderna kan översättas till ett tipssystem på $3^{6}=729$ rader, som garanterar minst nio rätt vid elva tippade matcher.

Hammingvikt. Ett ords Hammingvikt är lika med antalet ettor i ordet. Om ordet u = 1101010, är således dess Hammingvikt, wt(u) = 4. Om två ord, a och b, "adderas", på så sätt att man adderar talen i motsvarande positioner modulo 2, så kallad ordaddition, kan deras Hammingavstånd, d(a,b), avläsas som Hammingvikten av den bildade ordsumman, det vill säga d(a,b) = wt(a + b).

Exempelvis: Om a = 0011101010 och b = 1010110001 blir a + b = 1001011011. Hammingavståndet, d(a,b) = wt(a + b) = 6.

Källor

• V. Pless, Introduction to the Theory of Error-correcting Codes, Wiley, 1982.
• E.R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, 1968.
• Bernt Lindström, Elementa nummer 4 1972, Tidskrift för Matematik, Fysik och Kemi.