36 INFORMATICA 3/1979 KODIRANJE IN DE KODI RAN JE KOREKTURNEGA KODA Z MIKRO RAČUNALNIKOM M. ŠUBELJ J. KORENINI F. NOVAK R. TROBEC UDK: 681.327.63 : 621.3 INSTITUT JOŽEF ŠTEFAN. LJUBLJANA V članku je obravnavano kodiranje in dekodiranje korekturnega koda realizirano z mikro računal­ nikom. Najprej je definirana Hammingova razdalja in princip dekodiranja "idealni opazovalec". Tipi korekturnih kodov so razdeljeni na kode, ki e napak popravijo in kode, ki (e-1) napak po­ pravijo in e-to napako detektirajo. Primer prikazuje princip oddaje kodiranih znakov in sprejem in dekodiranje znakov. V zbirnem jeziku za procesor P-8 sta dodana tudi programska modula za kodiranje in dekodiranje. CODING AND DECODING OF A COHRECTION CODE BY A MICROCOMPUTER - Coding and decoding of a correction code implemented in microcomputer is discussed in the paper. The definition of "Hamming diatance" is given and the "ideal observer" decoding technique is deacribed. Different correction codea are classified as e-error-correcting codea and (e-l)-error-dorrecting, e-error-detecting -codes. An example of tranamisslon and reception of correction codea in practice ia shovn. Program modules fdr coding and decoding written In F8 a8sembly language are alr.o given. / 1. UVOD 2. KOREKTURNI KOD IN RAZDALJE Pri prenosu informacije preko telefonskega kabla se pojavi problem zanesljivega prenosa. Motnje, ki jih lahko povzročijo preklopi na liniji,dlstorzija signala, atmosferske motnje, presluh med linijama, lahko povzročijo, da bit informacije spremeni avojo električno vred­ nost. Za zanesljiv prenos poznamo več metod kontrole napake pri prenosu. Ml se bomo omejili na kon­ trolo napake, ki omogoča popravljanje napake, v nekaterih primerih pa samo odkrivanje. Izved­ ba je programska in nam omogoča veliko prila-t godljlvost in relativno enostavno modifikaci­ jo na drugačen kod. Znaki se lahko prenašajo paralelno (vsi biti znaka istočasno) ali se­ rijsko. Sinhronizacija in paralelno serijska in serijsko paralelna pretvorba je lahko Iz­ vedena aparaturno (ACIA) ali programsko. Predpostavlja se, da se informacija prenaša preko simetričnega binarnega kanala. Vhod v kanal tvori zaporedje binarnih kodnih ••beee(^ W = j w,, Vo,..., wsj dolžine n. Vse besede imajo isto verjetnost, da pridejo pri oddaji na vrsto. Ha izhodu iz kanala Imamo sprejem­ nik, ki se odloči po pravilu "idealnega opa­ zovalca". Dekoder "idealni opazovalec" se odloča za tis­ to varianto, kjer je verjetnost napake najmanj­ ša ali drugače povedano, za tisto besedo koda W= {w, ,...,• w j , do katere Je Hammingova razdalja najmanjše'. Heimmingova razdalja d{wj^, v«) med dvema binarnima besedama w, in itf« dolžine n je število binarnih znakov, v katerih ae..razllkujeta..basedl.w,. in. K,.-- • Predpostavimo, da Je zaradi motenj možna na­ paka na vsakem binarnem znaku. Ker je vhodna beseda dolžine n, lahko na Izhodu sprejmemo 2 različnih besed dolžine n. Predpostavimo, naj vir pošilja zaporedje besed 37 W = fw-, , Wp,..., w I in sprejemnik sprejema zaporedje besed V = |v^, Vg,..-, ^ j^i Zanima nas, kakšna je povezava med odposlani­ mi in sprejetimi besedami. Oglejmo si Hammin- govo razdaljo med besedami koda W = | w,,W2, •••' V) = a) d (wi, wj) = 2e + 1 , i = l,2,...,s i?^ j j = 1,2 s Predočimo si še grafično razdaljo med be­ sedama wi in wj. V prvem primeru se lahko odločimo. Sprejeto besedo vj, dekodiramo kot wi. Beseda je pra­ vilno dekodirana, če je bila napaka e-1 ali manj kratija. V drugem primeru besede ni možno dekodirati, saj je razdalja besede vj enaka do dveh besed wi in wk. Napako se lahko samo detektira. 3. PRINCIP ODDAJE IN SPREJEMA KOREKTURNEGA KODA d(wi, Mj) = 5 => e = 2 ' Vidimo,da vsaka sprejeta beseda vj c V j=l,2, ..., 2 pade v okolje samo ene izmed besed W= ( w-, , vfj,... , w j s Hammingovo razdaljo d(wi, vj)£ e 1 =1,2,... s in j = 1,2,...,2". Naloga dekoderja "idealni opazovalec" je, da najde , to besedo 'wi e W , i = 1,2,... ,,s. Beseda dekodirana po, tem principu je bila pravilno dekodirana v odposlano besedo, če.je bila na­ paka e ali manj kratna. b) d(wi, wj) = 2e i = 1,2,...,s ± d d J = 1,£1,...,S Predočimo si grafično razdaljo med besedama. d(rfi, wj) = 4 => e C 2 Oglejmo si Hammingovo razdaljo med sprejeto besedo vj e V j = 1,2,. '"- "s} in besedami koda W = j wy,v.p. Razdalja je: - d(wi,vj) = e ali - d(wl,vj) = d(wk,vj) z= e 1,2,. 1,2,. 1,2,. 1,2,- k = 1,2,. • ,3 pn • ,s •,2 • ,3 n Zgled obravnava primer prenosa informacije a kodom 4 . korekturnih in 4- . informacijskih bitov. Hammingova razdalja med besedami koda je 4, zato tak kod popravlja enojne in detek­ tira dvojne napake na 8 bitih. Za 8 bitno be­ sedo smo se odločili zaradi najpogostejše aparaturne organizacije mikroračunalniških , ko- jonent (CPU, ACIA). Seveda je možno izbrati tadi kod, ki bo imel drugačno razmerje med informacijskimi in korekturnimi biti pri enaki dolžini besede. V primeru koda 4 informacijskih in 4 korektur­ nih bitov^oddajnik odda zlog (8 bitov) infor­ macije kot dve 8 bitni kodi. Najprej kodira zgornje 4 bite informacije s Hammingovim kodom (8 bitov) in ga odda. Za tem kodira še spodnje 4 bite informacije' in kod odda. Sprejemnik dela v jobratnem vrstnem redu. Sprej­ me kod (8 bitov),ga dekodira (4 biti) in shrani na zgornja 4 mesta vmesnika informacije. Za tem sprejme še drugi kod, ga dekodira in prida na spodnja štiri mesta vmesnika infor­ macije. Modula za kodiranje in dekodiranje se sklicujeta na isto tabelo Hammingovih kodpv. Osnovni moduli za sprejem in oddajo so napi­ sani kot subrutine. Ogljemo si jih podrobneje opisane v psevdo kodu: a) ODDAJA: , . THBY: subrutina odda zlog (8 bitov) infor­ macije kodirane s kodom Hammingove raicdalje 4. Vhodni parameter : adresa lokacije, iz katere bo zlog oddan. 38 SUBROUTINE TRBY VLOŽITEV ZLOGA; POMIK ZA 4 MESTA V. DESNO; CALL KOHE CALL TRG VLOŽITEV ZLOGA; OHRANITEV SP. ^ BITOV; CALL KOHE CALL TRC ENDSUBHOUTINE KOHE : subrutina 4 bitom priredi kod Hammingove razdalje 4 (8 bitov). Vhodnj. parameter: 4 informacijski biti v reg. DIO. Izhodni parameter: kod Hammingove razdalje (8 bitov) v reg. DIO. SUBROUTINE KOHE ADRESIRANJE ZAČETNE ADRESE TABELE HAMMINGOVIH KODOV; iiELATIVNI PREMIK ADRESE ZA 4 INF. BITE (IZRAČUN ADRESE KODA); VLOŽITEV IN SHRANITEV KODA; ENDSUBROUTINE TRC : subrutina odda znak na izhod za ; oddajo. Vhodni register: znak (Hemmingov kod) v reg. DIO. SUBROUTINE TRC DOUHTIL (MOŽNOST ODDAJE ZNAKA) ENDDO ODDAJA ZNAKA NA IZHOD; ENDSUBROUTINE b) SPREJEM REBY : sprejme zlog (8 bitov) informacije kodirane s kodom Hammingove raz^ dalje 4. Vhodni parameter Je adresa loka­ cije, kamor bo sprejeti zlog shranjen. SUBROUTINE REBY CALL REC CALL DEHE SHRANITEV ZG. CALL REC .•CALL DEHE SHRANITEV SP, ENDSUBHOUTINE 4 BITOV ZLOGA; 4 BITOV ZLOGA; DEHE : subrutina kod Hammingove razdalje 4 (8 bitov) dekodira v 4 bite. V primeru, ko se ne more odločiti (d)wi,vj) = d(wk,vj)) postavi zas­ tavico "programska detekcija na­ pake". Vhodni parameter: kod Hammingove razdalje v reg. DIO. Izhodni parameter: kod dekodiran v 4 informacijske bite v reg. DIO ali DIO nespremenjen in zastavica "programska detekcija napake" v reg. DRS. SUBROUTINE DEHE ŠTEVEC KODOV*O; ADRESIRANJE ZAČETKA TABELE HAMMINGOVIH KODOV;- DOUITTIL (TEST VSEH KODOV ALI DEKODIRANJE) ŠTEVEC BIT0V=8 EKCLUSIVNi' OR MED SPREJETIM ZNAKOM IN ADRESNIM ZNAKOM TABELE KODOV (ADRESIRANJE LOKACIJE NASLEDNJEGA KODA) IF (STA ENAKA, REZULTAT=0) THEN DEKODIHANI SPREJETI ZNAK=ŠTEVEC KODOV, IZTOP; ELSE DOUNTIL (POJAVITEV 1. ENICE V REZULTATU) PRIPRAVA NASLEDNJEGA MESTA; ŠTEVEC EITOV=ŠTEVEC BITOV-i; EMDDO DOUNTIL (TEST OSTALIH MEST REZULTATA) ENDDO- ; IF (NI VEČ ENIC) TliEN SPREJETI ZKAK=ŠTEVEC KODOV, IZTOP; ELSE ŠTEVEC KODOV=ŠTEVEC KODOV+1; ENDIF ENDIF ENDDO POSTAVITEV ZASTAVICE PROG.DET.NAPAKE; ENDSUBROUTINE REC : subrutina sprejme znak preko vhoda za sprejem Izhodni parameter: sprejeti znak (Hammingov kod) v reg. DIO. 39 SUBBOUTIHEBEC . DOUMTIL (MOŽNOST SPEEJEMA ZNAKA] ENBDO. SPREJEM ZNAKA PREKO VHODA; ENDSUBEOUTIHE 4. SKLEP 5. LITERATURA /1/ L. Gyergyek: Statistične metod? v teoriji sistero.ov, teorija o informacijah, .Fakul­ teta za elektrotehniko 1971• /2/ Electronics Book Series: Basics of data Communications, Me Graw-Hill igVS. /5/ Moatek: Programming Guide Cilj članka je predstaviti možnost prenosa podatkov kodiranih s konkretnim kodom pri ko­ munikaciji med mikro računalniki. Ta dogradi­ tev,sicer zmanjša množino koristne informacije prenesene v časovnem intervalu, vendar poveča zauesloivost prenosa in izboljša kvaliteto ka­ nala. 1.2.1979 M.SUBELJ TITLE SUBRUTINA KODIRANJE HAMlilN&A » »SUB.KOHE DOLOČI 4 INFORMACIJSKIH blTOM KOD tHAMlilNGOVE RAZDALJE 4.KOD SESTAVLJAJO 4 »INFORMACIJSKI BITI + 4 KOREKTURNI BITI. 0000 0001 0004 0005 0006 0007 0008 08 2A 00 47 SE 16 57 OC » « • •VHOD: * •IZHOD * •UPOR. • DIO • « • KOHE • 34 • • DIO " 1 DIO 4 INFORMA = KOD HAMM REG.iACC Eeu EQU .EQU EQU LR LIS LR OCI LIS LR LR xn BZ NI BH SL DS BR NI . BH SL DS BNZ LR LR BR LR INC LR ti BNZ LI LR PK DC OC DC OC OC OC OC DC DC DC DC DC DC DC DC DC 0 H'00' H'01' H'03' H'07' Ki P H'00' )!U>A TAHEM H'08' XLtA A1OIO DEHE3 H'FF' DEHE6 1 XL DEHEl H'FF' DEHE4 1 XL DEHE2 AiXU DIOiA DEHE3 AiXU XU.A H'10' DEHEO H'10' DRSiA H'00' H'D2' H'33' H'87' H'99' H'4B' H'CC' H'1E' H'E1' H'33' H'B4' H'66' H'78' H* AA' H'2D' H'FF' DELOVNI REGISTER DELOVNI RE6ISTER PODATKI V SUB. LRS IN PODATKI V I/O SUB . 8R8 VLOŽITEV ŠTEVCA KOOOV XU=0 ADRESIRANJE ZAČETKA TABELA KOOOV OOUNTIL (TESTIRANJE VSEH KODOV) VLOŽITEV ŠTEVCA BITOV SL=8 VLOŽITEV SPREJETEGA ZNAKA IN PRIMERJANJE Z ZNAKOH TABELA IF ( STA ENAKA) THEN3 DEHE3tELSE... OOUNTIL (POJAVITEV t.ENICE) IF (ENICA) THEN DEHE6iELSE... PRIPRAVA NASLEDNJEGA BITA ŠTEVEC BITOV XLnXL-l ENDDO TESTIRANJE ALI JE 2.ENICA IF (ENICA) THEN DEHE4«EL8E... (DEHE6 PRIPRAVA NOVEGA NESTA) IF (TEST VSI BITI) THEN....ELSE DEHE2 VLOŽITEV DEKODIRANE BESEDE IZHOD IZ SUB. POVEČANJE ŠTEVCA KODOV IN TEST ALI SO TESTIRANI VSI KODI ENDDO POSTAVITEV FLA6-A PROGRAMSKE DETEKCIJE NAPAKE PRI SPREJEMU TABELA KODOV (8 BITNA KODA) UO Ml U2 U3 H4 U3 tib W7 m M9 UlO Hll U12 U13 t)14 U13