Vertailtavat jonot
Syötä kaksi yhtä pitkää jonoa. Ne voivat olla bittijonoja (esim. 1011101) tai tavallista tekstiä. Hamming-etäisyys lasketaan vain, jos jonot ovat yhtä pitkiä.
Esimerkit:
Hamming-etäisyyslaskuri
Laske kahden yhtä pitkän merkki- tai bittijonon Hamming-etäisyys eli niiden eroavien kohtien määrä.
Hamming-etäisyyslaskuri
Tämä laskuri laskee kahden yhtä pitkän merkki- tai bittijonon Hamming-etäisyyden eli niiden kohtien lukumäärän, joissa jonot eroavat. Syötä molemmat jonot, niin laskuri näyttää etäisyyden, vertaillun pituuden ja eroavien kohtien sijainnit.
Mikä on Hamming-etäisyys?
Hamming-etäisyys kertoo, kuinka monessa kohdassa kaksi yhtä pitkää jonoa poikkeavat toisistaan. Se vastaa kysymykseen, montako symbolia on vaihdettava, jotta ensimmäisestä jonosta saadaan toinen:
d(1011101, 1001001) = 2
Käsite on nimetty matemaatikko Richard Hammingin mukaan, ja se on yksi koodausteorian peruskäsitteistä.
Miten etäisyys lasketaan?
Jonot asetetaan kohdakkain ja verrataan kohta kohdalta. Jokainen eroava kohta kasvattaa etäisyyttä yhdellä:
Hamming-etäisyys = eroavien kohtien lukumäärä
Bittijonoilla saman tuloksen saa myös laskemalla jonojen XOR-operaation ja laskemalla tuloksen ykkösbittien määrän.
Vaiheittainen esimerkki
Lasketaan bittijonojen 1011101 ja 1001001 Hamming-etäisyys.
Verrataan kohta kohdalta vasemmalta oikealle:
1=1, 0=0, 1≠0, 1=1, 1≠0, 0=0, 1=1
Erot ovat kohdissa 3 ja 5, joten Hamming-etäisyys on 2.
Miksi jonojen on oltava yhtä pitkiä?
Hamming-etäisyys vertaa symboleja samoissa kohdissa, joten se on määritelty vain, kun jonot ovat yhtä pitkiä. Eri pituisia jonoja ei voi verrata kohta kohdalta. Jos pituudet poikkeavat, tarvitaan muita mittoja, kuten muokkausetäisyyttä (Levenshtein), joka sallii lisäykset ja poistot.
Hamming-etäisyys virheenkorjauksessa
Tiedonsiirrossa ja tallennuksessa Hamming-etäisyydellä mitataan, kuinka erilaisia eri koodisanat ovat. Koodin pienin Hamming-etäisyys eri koodisanojen välillä määrää sen virheensietokyvyn:
- Etäisyydellä d voidaan havaita enintään d − 1 bittivirhettä.
- Etäisyydellä d voidaan korjata enintään (d − 1) / 2 bittivirhettä.
Esimerkiksi koodi, jonka minimietäisyys on 3, havaitsee kaksi virhettä ja korjaa yhden.
Muita käyttökohteita
- Bioinformatiikka: DNA-sekvenssien vertailu ja mutaatioiden laskenta.
- Tietoturva: salausavainten ja tiivisteiden erojen arviointi.
- Tietoliikenne: virheenkorjauskoodien, kuten Hamming-koodin, suunnittelu.
Hamming-etäisyys ja informaatioteoria
Hamming-etäisyys kuuluu informaatioteorian peruskäsitteistöön. Sen avulla määritellään koodiavaruuden rakenne ja arvioidaan, kuinka luotettavasti tieto voidaan siirtää häiriöisen kanavan yli. Mitä suurempi koodisanojen välinen etäisyys on, sitä paremmin koodi kestää virheitä.
Kokeile myös näitä palveluita
Mainos
Usein kysytyt kysymykset
Mikä on Hamming-etäisyys?
Hamming-etäisyys on kahden yhtä pitkän merkkijonon eroavien kohtien lukumäärä. Se kertoo, kuinka monta symbolia pitäisi vaihtaa, jotta ensimmäisestä jonosta saataisiin toinen. Käsitteen esitti Richard Hamming, ja se on keskeinen informaatioteoriassa ja koodausteoriassa.
Miten Hamming-etäisyys lasketaan?
Verrataan jonoja kohta kohdalta ja lasketaan, kuinka monessa kohdassa symbolit eroavat. Esimerkiksi jonoissa 1011101 ja 1001001 erot ovat kolmannessa ja viidennessä kohdassa, joten Hamming-etäisyys on 2. Bittijonoilla tämä vastaa bittien XOR-operaation ykkösten määrää.
Miksi jonojen on oltava yhtä pitkiä?
Hamming-etäisyys vertaa symboleja samoissa kohdissa, joten se on määritelty vain yhtä pitkille jonoille. Jos jonot ovat eri pituisia, niitä ei voi verrata kohta kohdalta, ja silloin tarvitaan muita mittoja, kuten Levenshtein-etäisyyttä.
Mihin Hamming-etäisyyttä käytetään?
Hamming-etäisyyttä käytetään virheiden havaitsemiseen ja korjaamiseen tiedonsiirrossa ja tallennuksessa. Se kertoo, kuinka monta bittivirhettä koodi sietää: koodin minimietäisyys määrää, montako virhettä voidaan havaita tai korjata. Sitä hyödynnetään myös bioinformatiikassa ja tietoturvassa.
Mitä eroa on Hamming-etäisyydellä ja Levenshtein-etäisyydellä?
Hamming-etäisyys laskee vain korvaukset yhtä pitkien jonojen välillä. Levenshtein-etäisyys eli muokkausetäisyys sallii myös lisäykset ja poistot, joten se toimii myös eri pituisilla jonoilla. Hamming-etäisyys on näistä yksinkertaisempi ja nopeampi laskea.
Oliko tästä laskurista apua?
