Aleksandar Juriši´ c:

(1)

i i

i i List za mlade matematike, fizike, astronome in raˇcunalnikarje

ISSN 0351-6652 Letnik30(2002/2003) Številka 6

Strani 361–366, XXIII, XXIV

Aleksandar Juriši´ c:

NAPAKE NISO VEˇ CNE, Presek, zgošˇ cenke, pla- neti in kode

Kljuˇcne besede: raˇcunalništvo, matematika, informatika, kodiranje, odpravljanje napak, Hammingove kode, Red-Salomonove kode.

Elektronska verzija: http://www.presek.si/30/1531-Jurisic.pdf

c

2003 Društvo matematikov, fizikov in astronomov Slovenije c

2010 DMFA – založništvo

Vse pravice pridržane. Razmnoževanje ali reproduciranje celote ali posameznih delov brez poprejšnjega dovoljenja založnika ni dovo- ljeno.

(2)

NAPAKE NISO

VEČNE

Presek,

zgoščenke,

planeti

^In

kode

V časuinformacijsketehnologije (zgoščenke, mobilnitelefoni,bančne kar- tice, internet ) sevsi dobro zavedamo pom en a hitrega in natančnega prenosa , obdelova nja in hranj enj ainform acij. Šetakopopolnenap ravedelaj o nap ake,le-tepa lahkohitro spremenijo sicer izredno koristnoprogramsko in stroj no opremo v ničvredno ali celo nevarn ooro dje . Dolgo časaso se ljudje tru dili izdela ti računalnike in pomnilnike,ki bod o nar edili oziro ma vsebovali,kar seda malo nap ak . Seveda so bile zato cene takih izdelkov vednovišje. Pot em paso sedomi slili ,da bi raj eračunalnike same naučili

iska ti in odpra vlja t i napake. Za povečanj e zanes lj ivosti prenosa in ob de- lave informacij smo dolgo časa upor ablj ali kontrolne bite (ang l. pari ty- check bits ), kot npr. pri šte vilki_bančnega _čeka, ki pa so služ ili le za od- krivanj e nap ak. Ko je matem a tik Richard Hamming vnašal v računalnik

progr am espomočjoluknjanj akarticin ko mu je računalnikzavrn il paket kartic zara di napak ,sejezamislil : _"Čezna_računalniksamodkrit i napako, zakaj ne zna najti tudi njenega mest a in jeodpraviti?"

Resnično nas vedno bolj zanima, kaj lahko sto rimo, če pride do tovrstn ih nap ak , saj so računalniki začeli prevzem ati večino dela na po-

dročjuinformacijin pri telekomunikacijah . Nazačetkusobili računalniški

progr amidovolj enostavni, tako da sotehničnenap ake (po navadi je odp o- vedala elekt ronka) hitro post al e_oč_itne. Tod a zrazvoj em stro j ne opre me sopost aj aliprogr amivse obsež nejš i in bolj zapleteni,stem pa je upanj e, da bilahkohitro opazili majhnenap ake,kispre me nijo delovanj enaprave, plahnelo. Možnost, da se na m izmu zne kakšn a nap aka ,je vse večja tud i zato, ker so elektro ns ka vezja iz dneva v dan manjša ,računaln i ki pa vse hit rejši. Tudi če je možnost napake ena sama milijardinka (npr. indu- strijs ki standard za trde diske je ena napaka na 10 milija rd bitov), se bo računalnik, ki opravi dve milijardi osnov nih operacij na sekundo, in tak računalnik je prav dolgočasno počasen glede na superračunalnike,

zmotil pribl ižno dvakrat na sekundo. Glede na količino pod atkov , ki jih obde luje mo dandan es,je to pravšnji recept za vsakod nev ne nevšečnosti.

Kaj lah ko torej storimo? Raziskovalcisonašli odgovo rvkod ah za od- pravlj anj e nap ak. Kodaje skupinasimbo lov,ki pred st avlj a informacijo.

Kod e obstajajo žetisočletja. To so npr. hiero glifi, grška abeceda, rimske številkeali pa genet ska koda za sestavljanje ribonuklein skihkislin ,različne

kode za zapi s govora ali glasbe, Mor sejeva abecedaza prenosinformacij, kod e za shranjevanje podatkov. Matematičnateorija kod,ki seje razvil a vzadnjih petdesetihletih,jeračunalnikarj em in inženirj em omogočila, da sestavijo sisteme , ki so,kar se da zanes lj ivi (kolikor pač dopušča st ro j na

(3)

oprema). Tako teor ija kodir a nja lahko predstavlja varnostno mrežo,svo- jevrstno matematičnozavarovanje pred muhastim materialnimsvet om, v katerem živimo .

Tehnologija kod za popravljanje napak je danes tako rez širjen« kot

zgoščenke (CD) . Omogoča nam, da poslušamo priljubljeni Mozartov aliMadonninCD brezkakršnih kolimotenj,četudinam gamačkaprav pošteno spraska.

Enako tehno logijo upora bljajo za komunikacijo tud i vesoljske ladje in sonde, ki raziskujejo našeosončje. Kode za od pravljanje napakomogoča

jo,dakljub elekt ro magnetnim motnjam pridejona Zemljo kristalno jasni posnetkioddalje n ih planetov ,pritem pa za prenos porabimo manj ene r- gije kot hladilnikova žarnica (gre torej za šepetanje,ki mora prep ot ovati

več milijard kilom et rov).

V nad aljevanjuprispevka bomonajprej preds t avilienostavnejšekod e za odpravljanje nap ak, npr. kode s ponavljanje m in Ham mingove kode, nat o pabomo spoznali šepoenost avlj enovariantot.i. Reed-Salomo novih kod. Nazadnje si bomo ogledaliosnove kodiranj ana zgoščenkah.

Preproste kode za odpravljanje napak

Claude Shannon je kmalu po kon cu druge svetovne vojne postavil teo-

retičneosnove teorijiinfor macij in zanes lj ivemu prenosu digitalnih pod atkov. Let a 1948 pa je Richard Hamming izumil met odo za popravljanje ene napakein odkrivanjedveh nap ak. Bist vovseh metodza odpravljanje napak je dod aj anj e kontrolnih bitov. Naje nostavnejša kod a za odpravljanje nap ak je zasnovana na ponavljanj u. _Če npr. _pričakujemo , da pri prenosuneboprišlodovečkot enesamenap ake,potemjedovolj,davsak bit ponovimo trikrat in pri sprejemu upor abimo "večinsko pravilo" (zelo kratko "simfonijo" 1101 zakodiramo v III III 000 lll). Če prejmemo III all 000 lll, popravim o sporočilo v III III 000 III in ga nazadnje še dekod ira mo v 1l01. V sp lošnem lahko odprav imo n napak z(2n

+

^1)-

kratnim pon avlj an jem in uporabovečinskegapravila . Toda ta metod a je

preveč potratna. V času, ko si želimo hitrega prenosa čim večje količine

podatkov,je takšno napihovanjevečinoma nesprejemlji vo. Namestotega si želimo dodati manj še število kontrolnih bito v, ki pa naj bodo ravno tako,ali pa morda še bolj,učinkoviti.

Najpreprostejši primer Hammingove kode za odpravljanje napak preds tavimo kar s _p_omočjo Presekovega znamenj a (slika 1 na III. st ran i ovit ka ).

SHammingovokodonamjeusp elo zma njšat ištevilo kontrolnihbitov z osem na tri, dobili smo torej kod o z informacijsko stopnjo 4/7 name-

(4)

sto prejšnjih 4/12

=

1/3. Opisan o Hammingovo kod o lah ko seved a po- splošim o. Običajno to storimo z nekaj linearne algebre (glej [3]).

Hammingova koda odkrije, da je do napake pri prenos u prišlo tudi, kadar jeprišlododveh napak,saj vsi trijekroginemor ejo vsebovatiobeh polj, na katerihje prišlo do nap ake. _Če pa na dveh mestih zazna mo,da simbola manjkat a,da ju npr. ne mor emo prebrati (angl.erasure) ,potem znamo ti dve mesti celo popraviti.

V grobe m lahko rečemo, da je cilj teorij e kodiranja najti primerno ravnovesje med skrom no metodonadzora z nekaj kontrolnimi biti in raz- sipno metodo s ponavljanji . Ha m mingova koda pred st avlja prvi korak v to sme r.

Re ed- S alom o nov e kode

Po odkritj u Hammingove kode je sledilo ob do b je šte vilnih poskusov s kod ami za odpravljanje napak. Ko je bila teorija kod stara deset let , sta Irving Reed in Gustave Salomon (takrat zaposlena v Lincolnovem laboratoriju na MIT) namesto ničel in enic uporabila skupine bitov, ki jim tud i v računalništvu pravimo kar besede. Ta izbira je pripomogla k odpravljanju t.i. groz d nih napak, pri katerih se pok vari več zap ore d nih bit ov. Če delamo npr.sskupinam i,sestavljenim i iz osmih bitov, potem celo devet zapore dnih nap ak lahko pokva ri največ dve besedi. Reed- Salom onova kod a (na kratko RS-kod a) za odpravlja nje dveh napak torej pred st avlja žeprecej dobro zaščito.

Naj bo (aa,al,...,alO), a; E ~13 , sporočilo, ki ga želimo prenesti. Nadomestimo ga s13-terico (co, Cl,...,CIO, Cn,CI2),tako daje Ci

=

a, za i E{O,...,lO},besediCn,Cl2 E_~13 pa _izračunam_o iz _enačb

CO+CI +..'+ CI2 mod 13

=

O in Cl+2C2+" ·+12cI2 mod 13

=

O(1)

in pošljemo. Predpost avimo, da smo prejeli zaporedje (ro,rl , .. . ,rlO, rn,rI2),pričemerjeprišlokvečjemudo ene napake. Čeje do napake pri- šlopriprenosu besedeCi ,potem veljarj = Cj za vsejE {O,1,... ,12}\{i}

in ri

=

Ci+ezanekie E {1,...,12}. Ize

=

rO+r l+..·+r I2 mod 13=1= O ug o t o vimo, da je prišlo do napake. Nato pa iz rl

+

2r2

+ . . . +

12r l2

==

ie (mod 13)z deljenj em z eizračunamoše i,ki nam pove,na katerem mestumoramo odš tetie,daodpravimo napako. Prišlismo do [13,11]-kode z informacij sko stopnj o 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 (1) dobimo 6 + Cn + Cl2

=

^O^{mod 13} ^{in 2}^- ^2cn ^- ^C^{l 2}

=

Ô^môd ¹³ôziroma^Cⁿ

=

⁸

mod 13inCl2

=

12 mod 13,torejjeC

=

(1,3,8,2,7,0,1 ,9,11 ,4,12,8,12).

(5)

Recim o,da smo dobili r = (1,3,8 ,2,1,0,1,9 ,11 ,4,1 2,8,12). Iz ro+ +rl+..·+r12 = 7zaključimo,da jee = 7,nato paiz rl+2r2+" ·+12r12=

= 2še 2/7

==

4 (mo d 13). Slednje deljenj e smoseveda izvedli v končnem

obseg u (glej [2]). Pravzaprav mor amo številu 2 v števcu prišt evati 13, vse dokler se deljenj e ne izide. Torej, ker 2+ 13=15 še ni deljivo s 7, posku sim o z 2+13+13=28 in dobimo 4, kar pomeni, da je potrebno na mestu z indeksom 4odšteti nap ako7.

Reed-Salom onovekod elahko obravnavamo veliko bolj splošno in pridem o tud i do tist ih,ki odpravljaj odvein več nap ak. Vendar pa za to potrebu- jemo ševečmatematičnegazna nja,ki presega našokvir,pa tud iračunanj e

v praštevilskem obsegu ~pje potrebno nadomestiti zračunanjem vkonč

nem obseg u GF(2ⁿ). Poleg zgoščenk se RS-kode uporablj ajo tudi v telekomunikacijah . Ena izmed najpom embnejših upor ab je bila kodiranj e digit alnih slik, ki sta namjih na Zemljopošiljalavesoljs kisondi Voyager1 in 2 (glej sliki na IV.strani ovit ka ).

Zgoščenke - CD

Zapi sovanj e glasbe na CD-je je prevzelo ljubitelje glasbe tako rekoč čez noč . Visokokvaliteto predvaj anj a zvoka je poleg laserske tehnike v veliki meri pripisatikodam za odpravljanje napak. Oglejm o sinačinzapisaCD nekoliko pobližje (slika 3).

.... ~ ..

·h~••• . . . ..., • 10•••••••••I

. r.:

•••1••J" ^u._i^{0 . 0}~• • • • ••:_ : ;..:• • •~•

... ,•••6;::..,•••i/ .

~ v ~

"';" ~ ~ ,.: ^~

"o• • •• •, =:._ ..~''::. ^Oo.. -. : . , -.

Slika 3. CD ima pre mer 12cmin deb elino 1,2mm,izd ela n paje izprozorne plastike.

Na po pisanern CD-j u se nahaja sp irala,kise začenjaiz not ranjost i in je sestavljena iz hribčkov in dolinic. Branje poteka zlaserj em (žarek ima premer 1tLm),ki zazna sp re membovišinesp irale (preko jak ost i svetlo be,kise odbijeod diska,odbojsvetl obe je ali svetlejš ialitem ne jši ,saj jerazlika v višin i približno1/4 valov nedolžin esvet lo be vdisk u). Na ta_načindo bi m o dvoj iškozaporedje,vsak a spre membaustreza šte vilu 1, odsotnostspre me m be višinepa ustreza št evilu O.

1. Procesrazdelimo na faze: digit alno /analo gnikonvert er , kode in mo- dulacija (slika 4).

2. Pri kodiranju bomo nabajtegledali kot naelementeiz obseg a GF(2⁸) ,

glej [2]. V stereot ehniki posnam emo št iri bajt enavsak "tik",ki pomeni 1/44.100-ti del sekunde . Meritev šest ih zapo rednih tikov združimo v

(6)

sporočilodolžin e24 baj t ov,kiga v dveh kor akih zakodiramo v32baj t ov.

Naj prej uporabimo [28,24]-RS kod o,kizna popraviti dve napaki,in na t o še [32,28]-RS kodo,ki tud i zna popraviti dve napaki. Tem 32-im bajtom dodamo še 33.bajt ,kije števec pesmi. Le-tegaobičajnovidim o na zaslonu predvajalnika .

3. Doseda j so bili vsi omenj eni baj t i bodi sinosilci informacije bodisiso bilidodani kot kontrola za odkrivan jein popravljanjenapak. Zbesedami sm o računali za potrebe kodiranja,sed aj pa se zarad i fizikalnih last nosti mat erialovspustimo na nivobitov. Potrebnojepaziti,da zap ored ne enice niso ne preveč blizu (med njima morat a biti vsa j dve ničli) in ne preveč

nar azen (med njimaje lahko največ deset ničel). RS-kod eseveda nimaj o takih lastnosti, vendar pa ima to las tnost natanko 267 dvojiških besed dolžine 14 (p reve rje no z računalnikom). Zato preslikamo 256 elementov

končnegaobsega spomočjo dobro izbrane tabele v 256 besed ,preostalih 11 besed pa zavržemo. Ta postopek se imenuje EFM (a ngl. eight to fourteen modulation) . Da pa bi zgoraj omenj enalast nost veljalatudi med besedamidolžine14,mednj epostavimošetri dod at nebite (ničle alienice;

pri tem pazimo še, da sta šte vili doslej prebranih ničel in enic čim bolj skupa j) in dobimo kodne besede dolžin e 33 . 17 = 561 bitov. Končno,

da za be ležimo začetek novega niza, priključimo vsaki kodni besedi še 27 sinhro nizacijs kih bitov, ki imaj o zgorn jo las t nost in so izbrani tako, da nikakor ne morejo sest avljati kodirnega podzaporedja. Ena sekunda glas be se torej pretvori v (561+ 27)·44.100/6 =4.321.800 bitov glas be na

spirali. .

Slika 4.Med sne m anjem izmerimo glasbo 44.l00-krat na sekundo,po enkrat na levi in enkrat na desni. Amplitudo zvoka opi še naravn o število med O in 2¹⁶- 1, ki ga predstavlj a v dvojiškem sistemu 16bitov. Ker gre za st ereo glasbo,dobimo pr ivsaki meritvi 32 bit ov (t.i.audio-biti ) oziro maštiri baj t epodatkov.

Pri branjuzgoščenke se lahko pojavi tudi čez 100.000 napak. Le-te lahko

povzročajo neza želeni delci ,mikroskopski mehurčki v plastiki,prstni od- tisi,praske alicelo manjšeluknjevCD-j u . Za primerj avo vzem im o knjigo z 200st ra nm i, izpisano vpisavi,kidopušča3000 znakovna stra n. Recim o, da je tiskalnik le 99,9% zanes lj iv. V povprečju lahko torej pričakujemo

do tri napake na stran. Vrnimo se k CD-je m. _Če bi bila verjetnost, da predvajalnik preberenapačenbit, enaka 10-⁴, biševednoimelinast ot ine napak vsakosekundo. Kvaliteto zvoka seveda izboljšajo kode. Napake se

običaj no poj avij ov gručah (t. i. grozdne napake). Da zm anjša mo njihov vpliv,je kodiranj enarejenov dveh korakih. Pri tem druga koda kot vhod

(7)

(8)

(9)

Slika 2. Desno: Voyagerja sta let a 1979 poslika la Jupiter, let a 1980/81 Saturn,nat o pa je Voya- ger 2 poslikal let a 1981 Uran in let a 1989 Neptun;

htt p:/ /ns sdc. gsf c .nas a. gov / plan e t ar y / voya ger. html.

Spodaj: Ju p iter in njegovi Gali- lej ski satelit i, lo, Evropa, Gani- medinKalisto (montaža);

ht t p:/ /ns sdc . gsf c.nasa . g ov / phot o_gall e r y /phot ogal l e r y- jup i ter. html.