ISSN 0351-6652 Letnik 30 (2002/2003) Številka 6
Strani 361-366, XXIII, XXIV
Aleksandar Jurišic:
NAPAKE NISO VECNE, Presek, zgoščenke, planeti in kode
Ključne besede: računalništvo, matematika, informatika, kodiranje, odpravljanje napak, Hammingove kode, Red-Salomonove kode.
Elektronska verzija: http://www.presek.si/30/1531-Jurisic.pdf
© 2003 Društvo matematikov, fizikov in astronomov Slovenije © 2010 DMFA - založništvo
NAPAKE NISO VEČNE Presek, zgoščenke, planeti in kode
V času informacijske tehnologije (zgoščenke, mobilni telefoni, bančne kartice, internet) se vsi dobro zavedamo pomena hitrega in natančnega prenosa, obdelovanja in hranjenja informacij. Še tako popolne naprave delajo napake, le-te pa lahko hitro spremenijo sicer izredno koristno programsko in strojno opremo v ničvredno ali celo nevarno orodje. Dolgo časa so se ljudje trudili izdelati računalnike in pomnilnike, ki bodo naredili oziroma vsebovali, kar se da malo napak. Seveda so bile zato cene takiii izdelkov vedno višje. Potem pa so se domislili, da bi raje računalnike same naučili iskati in odpravljati napake. Za povečanje zanesljivosti prenosa in obdelave informacij smo dolgo Časa uporabljali kontrolne bite (angl. parity-check bits), kot npr. pri številki bančnega čeka, ki pa so služili le za odkrivanje napak. Ko je matematik Richard Hamming vnašal v računalnik programe s pomočjo luknjanja kartic in ko mu je računalnik zavrnil paket kartic zaradi napak, se je zamislil: "Ce zna računalnik sam odkriti napako, zakaj ne zna najti tudi njenega inesta in je odpraviti?"
Resnično nas vedno bolj zanima, kaj lahko storimo, Če pride do tovrstnih napak, saj so računalniki začeli prevzemati večino dela na področju informacij in pri telekomunikacijah. Na začetku so bili računalniški programi dovolj enostavni, tako da so tehnične napake (ponavadi je odpovedala elektronka) hitro postale očitne. Toda z razvojem strojne opreme so postajali programi vse obsežnejši in bolj zapleteni, s tem pa je upanje, da bi lahko hitro opazili majhne napake, ki spremenijo delovanje naprave, plahnelo. Možnost, da se nam izmuzne kakšna napaka, je vse večja tudi zato, ker so elektronska vezja iz dneva v dan manjša, računalniki pa vse hitrejši. Tudi če je možnost napake ena sama milijardinka (npr. industrijski standard za trde diske je ena napaka na 10 milijard bitov), se bo računalnik, ki opravi dve milijardi osnovnih operacij na sekuudo, in tak računalnik je prav dolgočasno počasen glede na superračunalnike, zmotil približno dvakrat na sekundo. Glede na količino podatkov, ki jih obdelujemo dandanes, je to pravšnji recept za vsakodnevne nevšečnosti.
Kaj lahko torej storimo? Raziskovalci so našli odgovor v kodah za odpravljanje napak. Koda je skupina simbolov, ki predstavlja informacijo. Kode obstajajo že tisočletja. To so npr. hieroglifi, grška abeceda, rimske številke ali pa genetska koda za sestavljanje ribonukleinskih kislin, različne kode za zapis govora ali glasbe, Morsejeva abeceda za prenos informacij, kode za shranjevanje podatkov. Matematična teorija kod, ki se je razvila v zadnjih petdesetih letih, je računalnikarjem in inženirjem omogočila, da sestavijo sisteme, ki so, kar se da zanesljivi (kolikor pač dopušča strojna
oprema). Tako teorija kodiranja lahko predstavlja varnostno mrežo, svojevrstno matematično zavarovanje pred muhastim materialnim svetom, v katerem živimo.
Tehnologija kod za popravljanje napak je danes tako razširjena kot zgoščenke (CD). Omogoča nam, da poslušamo priljubljeni Mozartov ali Madonnin CD brez kakršnih koli motenj, četudi nam ga mačka prav pošteno spraska.
Enako tehnologijo uporabljajo za komunikacijo tudi vesoljske ladje in sonde, ki raziskujejo naše osončje. Kode za odpravljanje napak omogočajo, da kljub elektromagnetnim motnjam pridejo na Zemljo kristalno jasni posnetki oddaljenih planetov, pri tem pa za prenos porabimo manj energije kot. hladilnikova žarnica (gre torej za šepetanje, ki mora prepotovati več milijard kilometrov).
V nadaljevanju prispevka bomo najprej predstavili enostavnejše kode za odpravljanje napak, npr. kode s ponavljanjem in Hammingove kode, nato pa bomo spoznali še poenostavljeno varianto t. i. Reed-Salomonov i h kod. Nazadnje si bomo ogledali osnove kodiranja na zgoščenkah.
Preproste kode za odpravljanje napak
Claude Shannon je kmalu po koncu druge svetovne vojne postavil teoretične osnove teoriji informacij in zanesljivemu prenosu digitalnih podatkov. Leta 1948 pa je Riehard Hamming izumil metodo za popravljanje ene napake in odkrivanje dveh napak. Bistvo vseh metod za odpravljanje napak je dodajanje kontrolnih bitov. Najenostavnejša koda za odpravljanje napak je zasnovana na ponavljanju. Ce npr. pričakujemo, da pri prenosu ne bo prišlo do več kot ene same napake, potem je dovolj, da vsak bit ponovimo trikrat in pri sprejemu uporabimo "večinsko pravilo" (zelo kratko "simfonijo" 1101 zakodiramo v 111 111 000 111). Ce prejmemo 111 011 000 111, popravimo sporočilo v 111 111 000 111 in ga nazadnje še dekodiramo v 1101. V splošnem lahko odpravimo n napak z (2ji + 1)-kratnim ponavljanjem in uporabo večinskega pravila. Toda ta metoda je preveč potratna. V času, ko si želimo hitrega prenosa čim večje količine podatkov, je takšno napihovanje večinoma nesprejemljivo. Namesto tega si želimo dodati manjše število kontrolnih bitov, ki pa naj bodo ravno tako, ali pa morda še bolj, učinkoviti.
Najpreprostejši primer Hammingove kode za odpravljanje napak predstavimo kar s pomočjo Presekovega znamenja (slika 1 na III. stTani ovitka).
S Ilammingovo kodo nam je uspelo zmanjšati število kontrolnih bitov z osem na tri, dobili smo torej kodo z informacijsko stopnjo 4/7 name-
sto prejšnjih 4/12 = 1/3. Opisano Hammingovo kodo lahko seveda posplošimo, Običajno to storimo z nekaj linearne algebre (glej [3]).
Hammingova koda odkrije, da je do napake pri prenosu prišlo tudi, kadar je prišlo do dveh napak, saj vsi trije krogi ne morejo vsebovati obeh polj, na katerih je prišlo do napake. Če pa na dveh mestih zaznamo, da simbola manjkata, da ju npr. ne moremo prebrati (angl. erasure), potem znamo ti dve mesti celo popraviti.
V grobem lahko rečemo, da je cilj teorije kodiranja najti primerno ravnovesje med skromno metodo nadzora z nekaj kontrolnimi biti in razsipno metoda s ponavljanji. Hammingova koda predstavlja prvi korak v to smer.
Reed-Salomoriove kode
Po odkritju Hammingove kode je sledilo obdobje številnih poskusov s kodami za odpravljanje napak. Ko je bila teorija kod stara deset let, sta Irving Reed in Gustave Salomon (takrat zaposlena v Lincoln oveni laboratoriju na MIT) namesto ničel in enic uporabila skupine bitov, ki jim tudi v računalništvu pravimo kar besede. Ta izbira je pripomogla k odpravljanju t.i. grozdnih napak, pri katerih se pokvari več zaporednih bitov. Ce delamo npr. s skupinami, sestavljenimi iz osmih bitov, potein celo devet, zaporednih napak lahko pokvari največ dve besedi. R.eed-Salomonova koda (na kratko RS-koda) za odpravljanje dveh napak torej predstavlja že precej dobro zaščito.
Naj bo (oo,ai,..., Ojo), a* £ sporočilo, ki ga želimo prenesti. Nadomestimo ga s 13-terico (co, Ci,..., CiotCmCia)) ^a 3e c< = ai za i g {0,----10}. besedi cu,cj2 E pa izračunamo iz enačb
c0+c1 + ---+c12 mod 13 = 0 in c1 + 2c2 + -• ■ + 12cl2 mod 13 = 0 (1)
in pošljemo. Predpostavimo, da smo prejeli zaporedje (rQ,r\,... ,no, fiii ri2)j pri čemer je prišlo kvečjemu do ene napake. Ce je do napake prišlo pri prenosu besede Cj, potem velja ry = c} za vse j £ {0,1,..., 12}\{i}
in r; — c, + e za neki e e {1,..., 12}. Iz e = tq + ri -I-----j-rl2 mod 13 ^ 0
ugotovimo, da je prišlo do napake. Nato pa iz T\ -t- + ••■+- 12i'i2 = = ie (mod 13) z deljenjem z e izračunamo Še i. ki nam pove, na katerem mestu moramo odšteti e, da odpravimo napako. Prišli smo do [13,1 l]-kode z informacijsko stopnjo 11/13, ki zna popraviti eno napačno besedo.
Primer. Naj bo a = (1,3,8,2,7,0,1,9,11,4,12). Potem iz (I) dobimo 6 + en 4- c12 — 0 mod 13 in 2 - 2cu - C12 = 0 mod 13 oziroma en = 8 mod 13 inc,3 = 12 mod 13, torej je e = (1,3,8,2.7,0,1,9.11.4,12,8,12).
Recimo, da smo dobili r=- (1,3,8,2,1,0, 1,9,11,4,12,8,12). Iz r0 +
+riH-----FTxa — 7 zaključimo, da je e = 7, nato pa iz ri + 2r"aH-----l-12ri2 =
= 2 še 2/7 = 4 (mod 13). Slednje deljenje smo seveda izvedli v končnem obsegu (glej [2]). Pravzaprav moramo številu 2 v števcu prištevati 13, vse dokler se deljenje ne izide. Torej, ker 2+13=15 še ni deljivo s 7. poskusimo z 2+13+13=28 in dobimo 4, kar pomeni, da je potrebno na mestu z indeksom 4 odšteti napako 7.
Reed-Salomonove kode lahko obravnavamo veliko bolj splošno in pridemo tudi do tistih, ki odpravljajo dve in več napak. Vendar pa za to potrebujemo še več matematičnega znanja, ki presega naš okvir, pa tudi računanje v praštevilskem obsegu 7LV je potrebno nadomestiti z računanjem v končnem obsegu GF(2"). Poleg zgoščenk se RS-kode uporabljajo tudi v telekomunikacijah. Ena izmed najpomembnejših uporab je bila kodiranje digitalnih slik. ki sta nam jih na Zemljo pošiljala vesoljski sondi Voyager 1 in 2 (glej sliki na IV. strani ovitka).
Zgoščenke - CD
Zapisovanje glasbe na CD-je je prevzelo ljubitelje glasbe tako rekoč čez noč. Visoko kvaliteto predvajanja zvoka je poleg laserske tehnike v veliki meri pripisati kodam za odpravljanje napak. Oglejmo si način zapisa CD nekoliko pobližje (slika 3).
oiooiooiooooGioDooioooioooioooooa o o o o i o
Slika 3. CD ima premer 12 cm in debelino 1.2 mm, izdelan pa je k prozorne plastike. Na popisanem CD-ju se nahaja spirala, ki se začenja iz notranjosti in je sestavljena iz hribčkov in dolinic. Branje poteka z laserjem (žarek ima premer 1 /in), ki zazna spremembo višine spirale (preko jakosti svetlobe, ki se odbije od diska, odboj svetlobe je ali svetlejši ali temnejši, saj je razlika v višini približno 1/4 valovne dolžine svetlobe v disku). Na ta način dobimo dvojiško zaporedje, vsaka sprememba ustreza številu 1, odsotnost spremembe višine pa ustreza številu 0.
1.	Proces razdelimo na faze: digitalno/analogni konverter, kode in mo-dulacija (slika 4).
2.	Pri kodiranju bomo na bajte gledali kot na elemente iz obsega GF(2S), glej [2]. V stereotehniki posnamemo Štiri bajte na vsak "tik", ki pomeni 1/44.100-ti del sekunde. Meritev šestih zaporednih tikov združimo v
sporočilo dolžine 24 bajtov, ki ga v dveh korakih zakodiramo v 32 bajtov. Najprej uporabimo [2S,24j-ii S kodo, ki zna popraviti dve napaki, in nato še [32,28]-RS kodo, ki tudi zna popraviti dve napaki. Tem 32-hn bajtom dodamo Še 33, bajt. ki je števec pesmi. Le-tega običajno vidimo na zaslonu predvajalnika.
3. Do sedaj so bih vsi omenjeni bajti bodisi nosilci informacije bodisi so bili dodani kot kontrola za odkrivanje in popravljanje napak. Z besedami smo računali za potrebe kodiranja, sedaj pa se zaradi fizikalnih lastnosti materialov spustimo na nivo bitov. Potrebno je paziti, da zaporedne enice niso ne preveč blizu (med njima morata biti vsaj dve ničli) in ne preveč narazen (med njima je lahko največ deset ničel). RS-kode seveda nimajo takih lastnosti, vendar pa ima to lastnost natanko 267 dvojiških besed dolžine 14 (preverjeno z računalnikom). Zato preslikamo 256 elementov končnega obsega s pomočjo dobro izbrane tabele v 256 besed, preostalih 11 besed pa zavržemo. Ta postopek se imenuje EFM (angl. eight to fourteen modulation). Da pa bi zgoraj omenjena lastnost veljala tudi med besedami dolžine 14, mednje postavimo še tri dodatne bite (ničle ali enice; pri tem pazimo še, da sta števili doslej prebranih ničel in enic čim bolj skupaj) in dobimo kodne besede dolžine 33 ■ 17 = 561 bitov. Končno, da zabeležimo začetek novega niza, priključimo vsaki kodni besedi še 27 sinhronizacijskih bitov, ki imajo zgornjo lastnost in so izbrani tako, da nikakor ne morejo sestavljati kodirnega podzaporedja. Ena sekunda glasbe se torej pretvori v (561+27) ■ 44.100/6 =4,321.800 bitov glasbe na spirali.
pr
digitalni konv.
Ukodezi odpravo napak
likndc k odpravo napak
ur "
- i l>.: I I kri"-.
Slika 4. Med snemanjem izmerimo glasbo 44,100-krat, na sekundo, po enkrat na levi in enkrat na desni. Amplitudo zvoka opiše naravno število med 0 in 216 — 1, ki ga predstavlja v dvojiškem sistemu 16 hitov. Ker gre za stereo glasbo, dobimo pri vsaki meritvi 32 bitov (t. i. audio-biti) oziroma štiri bajte podatkov.
Pri branju zgoščenke se lahko pojavi tudi čez 100.000 napak. Le-te lahko povzročajo nezaželeni delci, mikroskopski mehurčki v plastiki, prstni odtisi, praske ali celo manjše luknje v CD-ju. Za primerjavo vzemimo knjigo z 200 stranmi, izpisano v pisavi, ki dopušča 3000 znakov na stran. Recimo, daje tiskalnik le 09,9% zanesljiv. V povprečju lahko torej pričakujemo do tri napake na stran. Vrnimo se k CD-jem. Ce bi bila verjetnost, da predvajalnik prebere napačen bit, enaka 10~4, bi še vedno imeli na stotine napak vsako sekundo. Kvaliteto zvoka seveda izboljšajo kode. Napake se običajno pojavijo v gručah (t. i. grozdne napake). Da zmanjšamo njihov vpliv, je kodiranje narejeno v dveh korakih. Pri tem druga koda kot vhod
uporabi nekoliko prepleten izhod prve kode. tako da bajti, ki so sosednji v kodnih besedah (glasbi), niso sosednji tudi na disku. Kodirna shema za CD-je se imenuje CIRC (Cross-Interleaved Reed-Salomon Scheme Čude) iu pravilno odpravi vse grozdne napake do dolžine 8.871 bitov, kar ustreza približno 2.5 nun spirale na CD-ju.
V članku smo si ogledali le nekaj najbolj osnovnih vidikov ko dir nega procesa, praksa pa je seveda še nekoliko bolj zapletena reč.
Aleksandar Jurišič
Viri m dodatno branje
[1]	B. Cipra, The Ubiquitous Reed-Solomon Codes, SI AM News 26/1 (1993) (http: //huu. siam.org/siamiiews/nitc/iDtcl93 .htm).
[2]	A. Jurišič. Računala nove dobe, 2. dej. Presek 30 (21W12 -03), str. 291-296. |3| S. Klavžar. O teoriji kodiranju, linearnih kodah in slikah z Mar.sa, Obzornik
mat. fos. 45 (1998) 4. str. 97 106. [4| Več avtorjev. For aJJ practical purposes.- introduction to contemporary mat hematics. 5. izdaja. New York, W. H. Freeman, 200(1,
Slika I (a) Našo kratko "aimibtiijrj" J10I spravimo tokrat zaporedoma na rjavo (1). zeleno (2). oranžno (3) in vijoličasto polje (J), preostala polja pa dopolnimo tako, da bo v vsakem krogu vsota števil soiJu. Dobimo kodo 111)1001, kjer zadnja tri mesta predstavljajo zaporedoma rumeno (5). rdeče (6) in modro polje (7).
Naštejmo vseli Iti kodnih besed, ki jih lahko dobimo na ta način: OOOOOOU. 0001011, 001D110, 0011101, 01110101, 0111111 D. 0110011, 01:1000, 1000111, 1001100, 10100(11, 1011010, 1100010, 1101001, 11101DO, 1111111
(h) Recimo. da je prišlo do ene same napake in da smo prejeli zaporedje 1111001. Potem bo prejemnik lahko ugotovil, da ju napaka v rumenem (levem) in rdečem (desnem) krogu, ne pa v modrem (zgornjem), kar pomeri, daje potrebno popraviti oranžno polje (3). Ni se težko prepričati, da je mogoče na lak način odpraviti napako na poljubnem mestu (tudi kontrolnem), seveda ob pogoju, da je to edina napaka.
Računalništvo
Slika 2. Desno: Voyagerja sta leta 197!) poslikala Jupiter, leta 1980/81 Saturn, nato pa je Voyager 2 poslikal leta 1981 Uran in leta 1989 Neptun; http://nssdc.gsfc.nasa.gov/ planetary/voyager,html.
Spodaj: Jupiter in njegovi Galilejski sateliti, lo, Evropa, Gaiii-med in Kalisto (montaža); http://nssdc.gsf c.nasa.gov/ photo.gallery/photogallery-jupiter.html.
\