Olet kehittämässä järjestelmää, joka hakee esineitä sarjanumeron perusteella. Tiedät käyttäjien tekevän aika ajoin virheitä, joten olisi hyvä olla tapa varmistaa, että numero on kirjoitettu oikein. Koska käyttäjä syöttää muutenkin numeroita, päätät lisätä sarjanumeron loppuun yhden tarkistusnumeron. Kuinka tämä numero kannattaisi laskea?
Ensimmäisenä yrityksenä päätät tarkistaa, että numeroiden summa päättyy nollaan. Esimerkiksi tuotteen 978048628152 tarkistussumma on silloin
ja lisäämällä tarkistusnumero 0 päättyy numeroiden summa nollaan. Minkä tahansa numeron muuttaminen muuttaa summaa niin, että se ei enää päätykään nollaan. Ongelma ratkaistu?
Varsin usein kaksi vierekkäistä numeroa vaihtaa vahingossa paikkaa. Äskeinen summa ei kuitenkaan välitä numeron paikasta, sillä $2+1 = 1+2$. Tämä puute on helppo korjata: kerrotaan joka toinen termi vaikkapa kolmella, jolloin esimerkiksi tuotteen 978951884517 tarkistussumma on
Jos tarkistusnumeroksi lisätään 4, numeroiden summa päättyy mukavasti nollaan. Tämä on oikeasti se menetelmä, jota kaupan tuotekoodit käyttävät. Vieläkin on mahdollista tehdä virheitä, mutta niiden todennäköisyys on jo sopivan pieni suhteessa laskutavan yksinkertaisuuteen.
Arjen tärkeät numerot sisältävät tarkistustietoa pienten ja suurten virheiden välttämiseksi. Henkilötunnuksen (tarkistusmerkki lopussa) tai tilinumeron (kaksi tarkistusnumeroa lopussa) näppäileminen väärin on tehty hankalaksi. Virheitä tapahtuu kaikkialla... ja osan niistä voi huomaamatta korjata.
(Call of Dutyn varhainen betatestaaja. 1946, Public Domain.)
Automaattinen tietojenkorruptointi
Verkkokaapelit ovat vaarallisia paikkoja tiedolle. Riski kadota tai muuttua on vielä nykyaikanakin olemassa, saatikka sitten yli puoli vuosisataa takaperin tietojenkäsittelyn alkuaikoina. Tietokoneet ja niiden väliset yhteydet söivät bittejä aamupalaksi, lounaaksi ja illalliseksi. Bell Labsissa työskenteli 40-luvulla kaksi matemaatikkoa, jotka esittivät ensimmäisiä ratkaisuja virheenkorjaukseen. He olivat Claude Shannon, johon tutustumme ensi kerralla, ja Richard Hamming. Hamming alkoi kehittää korjauskoodeja reaktiona alkeellisten tietokoneiden jatkuvaan kaatuiluun, joka haittasi hänen työntekoaan.
Tietokoneet käsittelevät tietoa binäärilukuina eli ykkösten ja nollien yhdistelmänä. Kaikki seuraavat esimerkit käyttävät 60-luvun ASCII-koodilla tallennettua sanaa AI, joka koneelle on $1000001~1001001$. Viidennen bitin kääntäminen ykköseksi muuttaa sen sanaksi EI (vakavin seurauksin, totta kai). Tehtävänä on siirtää viesti muuttumattomana tietokoneelta toiselle häiriöherkkää kaapelia pitkin.
Ensimmäinen tapa olisi toistaa jokainen bitti kolmesti. Jos vastaanottaja odottaa lukua $000$ tai $111$ ja saa luvun $001$, ei ole vaikeaa päätellä oikeaa tarkoitusta. Toisaalta viestin koko kolminkertaistuu, mikä ei ole läheskään optimaalista. Tällä tavalla koodattu viesti olisi siis
\[ 111000000000000000111~111000000111000000111. \]Toinen tapa on lisätä tarkistusnumeron vastine. Lisätään kirjaimen perään 0, jos kirjaimessa on parillinen määrä ykkösiä, ja muuten 1. Nyt lähettämämme viesti on
\[ 1000001\underline{0}~1001001\underline{1}, \]jossa alleviivatut numerot ovat "pariteettibittejä". Tämä menetelmä huomaa yhden bitin kääntymisen, mutta ei pysty korjaamaan virhettä, taikka huomaamaan kahden bitin kääntymistä samassa kirjaimessa. Toisaalta se vie vähän tilaa ja virheen huomaaminenkin on jo iso juttu.
Kuten usein on, hyvä ratkaisu löytyy jostain puolestavälistä. Kirjoitetaan viestin kirjaimet taulukkoon ja lasketaan pariteettibitit sekä pysty- että vaakasuunnassa:
| $1000001$ | $\underline{0}$ |
| $1001001$ | $\underline{1}$ |
| $\underline{0001000}$ |
Nyt yhden bitin muuttuessa pariteettibitti huomaa virheen sekä pysty- että vaakarivillä, jolloin virheellinen bitti voidaan korjata rivien leikkauspisteessä. Tässä tapauksessa virheenkorjaus lähes kaksinkertaistaa viestin koon, mutta esimerkin vuoksi viesti oli lyhyt. Suuremmalla ruudukolla kokoero on pienempi, mutta tietenkin todennäköisyys useampaan virheeseen kasvaa. Koodattu viesti on nyt
\[ 1000001\underline{0}~1001001\underline{1}~\underline{0001000}. \]Hammingin menetelmä toimii lähes samalla tyylillä: siinä pariteettibittejä on ripoteltu viestin sekaan kakkosen potenssien kohdalle. Jokaista lopullisen viestin bittiä vastaa yksilöllinen pariteettibittien yhdistelmä, jolloin yhden bitin virheet ovat korjattavissa huomaamalla, mitkä pariteettibitit eivät täsmää.
Menetelmän tehokkuus perustuu siihen, että jokainen pariteettibitti tarkistaa itseään ja suurta joukkoa databittejä. Pienellä muutoksella se voi havaita kaksikin virhettä ja joka tapauksessa korjata yhden. Lopullinen viesti tällä tavalla on vieläpä miellyttävän lyhyt
\[ \underline{0}\underline{0}1\underline{0}000\underline{1}001~1001\underline{1}001. \]Loistavan virheenkorjauskoodinsa lisäksi Hamming kehitti alan matemaattista teoriaa pitkälle. Myöhemmin tältä pohjalta kehitettiin entistä tehokkaampia menetelmiä erilaisiin sovelluksiin. Yksi esimerkki on CD- ja DVD-levyillä sekä digitelevisiossa käytettävä Reedin-Solomonin koodi, joka kykenee korjaamaan pitkiäkin virheitä, joita vaikkapa naarmuuntuneilla levyillä esiintyy. Se puolestaan perustuu viestin käsittelyyn polynomifunktion kertoimina ja kasaan jännittävän näköistä algebraa.
Ensi kerralla: Tutustumme Shannoniin ja hänen teoriaansa tiedosta.
Ei kommentteja:
Lähetä kommentti
Kommentit ovat moderoituja — yritän hyväksyä kommenttisi mahdollisimman pian. Voit kirjoittaa kommenttiin LaTeX-koodia tai yksinkertaista HTML-merkintää: lue lisää Kommentointi-sivulta.