1. A KOMMUNIKÁCIÓS RENDSZER FŐ JELLEMZŐI; A SHANNON-FÉLE

Informatikai alapismeretek (írta: Bernát Péter – BEPMABT.ELTE)

1. oldal

Letöltés helye: http://bernatp.web.elte.hu

1. A KOMMUNIKÁCIÓS RENDSZER FŐ JELLEMZŐI; A SHANNON-FÉLE KOMMUNIKÁCIÓS RENDSZER Az információ Folyamatosan érkeznek üzenetek a világból, melyek sokszor tudatosulnak, sokszor nem. Ha tudatosulnak, akkor tudásra teszünk szert. A tudás pedig akkor válik információvá, amikor szükségét érezzük, hogy átadjuk – tehát az információ az egyik személytől a másikig átadható – vagy átadásra is kerülő – üzenet. Az üzeneteket továbbíthatjuk térben (rádió, televízió, telefon), vagy időben is (írás, hangfelvételek, fényképezés). A kommunikáció A kommunikáció az állatvilágban is alapvető fontosságú. A méheknél például a táplálékforrás helyének közlésében játszik nagy szerepet. Az állatoknál is megfigyelhetők a kommunikáció általános jellemzői: a puszta fizikai kölcsönhatásoktól megkülönböztethetők; a rendszer szervezett működését biztosítja; és a rendszer egyik elemétől a másikhoz közvetítő közeg által jut el a jelzés, amely az azt érzékelő egyed állapotát megváltoztatja. Az emberek az ősidőktől cseréltek egymással információkat (tam-tam dob, futár, tűzés füstjelek). Nagy változást hozott az elektromos áram felfedezése (távíró, telefon), illetve a rádióhullám alkalmazása (rádió, tévé). Az alapokat Shannon és Weaver rakta le; mindketten a rádió átvitel-technikai problémáiból indultak ki, és főként a közvetítő közeg problémáival foglalkoztak.


2. oldal


A Shannon-féle kommunikációs rendszer

A rajzban szereplő figurák csupán a megjegyzést segítik, tehát a csatorna nem feltétlenül nagyanyó kunyhajának ereszéből készül stb. Hat, egymással kapcsolatban álló kibernetikai komponensből áll. FORRÁS: előállítja a véges üzenetet, ami diszkrét, véges számú jelből áll. ADÓ: az üzenetet a csatornán továbbítható jelek sorozatává alakítja: közlemény. CSATORNA: térben (esetleg időben is) továbbítja a közleményt. VEVŐ: a csatornán érkező közleményt visszaalakítja üzenetté. CÍMZETT: ezt az üzenetet értelmezni, hasznosítani tudja. Azt a komplex rendszert, mely csak ezt az öt alrendszert tartalmazza, zajmentes hírközlési rendszernek nevezzük. A valóságnak azonban jobban megfelel az a modell, amelyben a zajforrás is helyet kap. Példa: telefonos beszélgetés FORRÁS: beszélő hangképző szervei KÓDOLÓ: a mikrofon, ami elektromos jeleket állít elő CSATORNA: vezeték VEVŐ: a hallgató, ami a vezetékben érkező jeleket hangokká alakítja át

Informatikai alapismeretek (írta: Bernát Péter – BEPMABT.ELTE) Letöltés helye: http://bernatp.web.elte.hu

CÍMZETT: a telefon másik végén lévő személy ZAJFORRÁS: a vezeték rossz szigetelése

3. oldal


4. oldal


2. A HÍR ÉRTÉKE Állapot – esemény – hír Mi a Shannon-féle kommunikációs modellben a forrást olyan véges rendszernek tekintjük, melynek ismerjük az állapothalmazát: X = {x1, x2, x3,…,xv}. A forrás állapota változó, vagyis mindig a véges állapothalmaz valamelyik lehetséges értékét veszi fel. Az állapot egyúttal esemény is: Ei:=(X=Xi). A rendszer üzenete tehát az lehet, hogy melyik esemény következett be. Az eseménytér (E = {E1,E2,…,Ev}) véges sok elemű, és egyértelmű megfeleltetés van közte, és X között: Xi ↔ Ei. Teljes eseményrendszer: az előbbi E eseményhalmaz, mivel a felsorolt események közül mindig pontosan egyikük következik be. Például, ha két kockával dobunk, és a dobott pontok összegét tekintjük: E = {X=2, X=3,…, X=12}. Az S forrást a hírkészletével is jellemezhetjük: H = {h1,h2,…,hv}. Egyértelmű megfeleltetésben állnak az E elemeivel H elemei; összefoglalva tehát: megtehetjük, hogy a rendszer Xk ∈ S elemeit váltogatva állapotoknak, eseményeknek vagy híreknek nevezzük! A hírérték Az egyes hi híreknek eltérő lehet a közvetítési valószínűsége, másképpen tehát a vele megfeleltetett esemény bekövetkeztének valamilyen valószínűsége van. A hír értékességét a váratlanságához kell kapcsolni. Mi legyen a hírérték mérési módja? Természetes kívánalom, hogy az Xk ↔ Ek ↔ hk hírhez kapcsolandó η(x) [ejtsd: éta-iksz] az xk-hoz tartozó pk valószínűség monoton csökkenő függvénye legyen, vagyis: pi < pj

⇒

η(xi) > η(xj)


5. oldal


Azaz, ha gyakoribb az állapot, akkor kisebb a hírértéke. Lehetne például η(xk)=1/pk, mint monoton csökkenő függvény, ám figyelembe érdemes venni, hogy a hírek végső fázisukban fiziológiai csatornákon érkeznek hozzánk, az érzékszerveinkben keltett érzetekről pedig már régen megállapították, hogy az ingerekkel logaritmikus összefüggésben állnak. Vagyis az η(x) hírtartalmat a megfelelő p ∈ P valószínűség logaritmusával arányos mértékkel kell mérni:

η(x) = k

loga(p)

a-t és k-t pedig úgy kell megadni, hogy érvényben maradjon a korábbi kívánalom, vagyis elvben két lehetőség adódik: 1. a > 1 és k < 0 2. 0 < a < 1 és k > 0 Három mértékegységet dolgoztak ki: 1. bináris egység: η(x) = – log2(p) bit 2. decimális egység: η(x) = – log10(p) Hartley 3. természetes egység: η(x) = – ln(p) Nat A valószínűség meghatározása megfigyelésekkel A megfigyelések száma legyen N, a kedvező események száma pedig k. (Kedvező esemény: ps vizsgálatakor Es.) Ekkor 0≤k/N≤1 áll fenn, és a középső tört a relatív gyakoriság. Feltételezzük, hogy az események bekövetkezése egymástól függetlenek. Ekkor minél nagyobb N, annál jobban közelíti k/N a p-t, vagyis k/N ≈ p. Biztos eseményre p = 1, lehetetlen eseményre p = 0 értelemszerűen.


6. oldal


Példa A) Harminckét lapos magyar kártyából kihúztuk a piros ászt. Mennyi ennek a hírértéke? S = {x1,x2,…,x32}, ahol az állapotok az egyes kihúzott lapok. E = {E1,E2,…,E32}

η(x) = – log2p bit = –(–5) bit = 5 bit B) Ugyanilyen pakliból most hetes lapot húztunk. Mennyi ennek a hírértéke? p = 4/32

η(x) = – log2(1/8) = 3 bit.


7. oldal


3. AZ ENTRÓPIA; A SZEPARÁLHATÓ KÓDOK Az entrópia Egyes híreket tudunk jellemezni hírértékkel, de gyakran az információs forrás értékelése a fontosabb. Tekintsünk egy S forrást, amiből nagyon sok hír lép ki. A hírek össz száma legyen N. A H = {h1,h2,…,hv} hírek fejenkénti előfordulási darabszáma legyen rendre k1,k2,…,kv. Vagyis: k1+k2+…+kv = N. Az S forrás átlagos hírértékét (entrópiáját) úgy adjuk meg, hogy kiszámoljuk az egyes hírértékek gyakoriságokkal súlyozott közepét: H (S ) =

k1η ( x1 ) + k 2η ( x2 ) + ... + k vη ( xv ) [ejtsd: éta-es] k1 + k 2 + ... + k v

Mivel N nagyon nagy, így jó közelítéssel ki/N=pi, vagyis ki=Npi, továbbá az η(xi)=– log2pi (bit) felhasználásából adódik: v

H ( S ) = −∑ pi log 2 pi i =1

Ez az entrópia, ahol pi az egyes állapotokhoz tartozó valószínűségek, v pedig a teljes eseményrendszer halmazának elemszáma. Egyenletes eloszlású hírforrás esetén: v v 1 1 H ( S ) = −∑ pi log 2 pi = −∑ log 2 = log 2 v v i =1 i =1 v

SHANNON ELSŐ TÉTELE VÉGES VOLUMENŰ FORRÁSOK ENTRÓPIÁJA NEM LEHET AKÁRMILYEN NAGY, ÉS MIND KÖZÖTT AZ EGYENLETES ELOSZLÁSÚ HÍRFORRÁS ENTRÓPIÁJA A LEGNAGYOBB: v

H ( S ) = −∑ pi log 2 pi ≤ log 2 v = H 0 i =1


8. oldal


A szeparálható kódok Ha a forrás egyes állapotaihoz képest kevesebb állapottal rendelkezik a csatorna, akkor az az egyetlen megoldás marad, hogy a forrás egy hírének a csatorna több jeléből álló jelsorozatot kell megfeleltetnünk. A csatorna jelkészletét ábécének nevezzük, az egyes jeleket pedig betűknek. A lehetséges betűk száma az ábécé volumene: B. A kódolónak tehát az a feladata, hogy a forrás bármelyik állapotának bekövetkeztekor előállítsa és a csatornába juttassa azt a közleményt, amely az M ábécé elemeiből álló adott sorozat fizikai megfelelője. Az ábécé elemeiből tehát sorozatokat kell alkotnunk – ezek a sorozatok a kódszavak. A kódszavakból pedig összeállítható egy szótár. Sokszor találkozunk viszont a következő követelménnyel: biztosítani kell, hogy a kommunikációs rendszer folyamatosan, szünet nélkül működjék. Fontos tehát, hogy olyan kódolási rendszereket, olyan szótárakat használjunk, melyekkel szünetek, üresjárat nélkül továbbíthatók az üzenetek. Szeparálhatónak nevezünk egy kódot akkor, ha az egymástól szünetekkel el nem választott szavakból álló összetett közlemény minden szavát fel lehet ismerni, vagyis az összekapcsolt szóláncot egyértelműen az eredeti szavakra lehet bontani.


9. oldal


4. SHANNON TÉTELE SZEPARÁLHATÓ KÓDOKRA Bevezetés: az előző tétel A szeparálható kódok című egysége.

SHANNON MÁSODIK TÉTELE ADOTT H(S) [EJTSD: ÉTA-ES] ENTRÓPIÁJÚ FORRÁSNAK EGY B-BETŰS ÁBÉCÉVEL VALÓ KÓDOLÁSÁNÁL A SZEPARÁLHATÓ KÓD ÁTLAGOS

L0 =

L’ SZÓHOSSZÚSÁGA NEM LEHET EGY BIZONYOS L0-NÁL KISEBB, AMI:

H (S ) ≤ L' log 2 B

AZ L0 TEHÁT A MINIMÁLIS ÁTLAGOS SZÓHOSSZÚSÁG. Ennek bizonyítása Tekintsünk egy szünet nélküli közleménysort, mely egy W szótár N db szavából van összekapcsolva. E lánc minden szava átlagosan H(S) információt hordoz, a teljes lánc pedig η = N

H(S) információt.

A vizsgált összetett közlemény betűk, jelek egymásutánja, melyek mindegyike valamennyi információt szolgáltat. Mivel az M ábécé egyes betűi nem egyforma gyakorisággal fordulnak elő, a betűnkénti információnak csupán a (becsült) átlagával dolgozhatunk, melyet jelentrópiának nevezünk, és H(M)-mel jelölünk. H (M ) =

η N ⋅ H (S ) = n N ⋅ L'

Shannon első tétele szerint viszont minden forrásnak, így az M jelforrásnak is korlátos az H(M) entrópiája és ennek maximuma log2(B), és az így kapott egyenlőtlenséget rendezve a tétel állítását kapjuk. H (S ) ≤ L' log 2 B


10. oldal


5. PREFIX KÓDOK, EZEKRE VONATKOZÓ SHANNON-TÉTEL A prefix kód Prefixnek – vagy irreducibilisnek – nevezzük azokat a kódokat, szótárakat, melyeknek egyetlen szavából sem lehet egy másik szót betűk hozzácsatolásával származtatni (ebből következően a szavak végén lévő betűk elhagyásával sem kapható szótárban lévő szó). A humán nyelvek egyike sem prefix, tehát csak a mesterséges kódolás jöhet szóba. A prefix kód szeparálható is A prefix kód szeparálható, vagyis a prefix tulajdonság megkövetelése szigorúbb feltételt jelent. Tekintsünk egy több szóból álló közleményt, mely egyetlen szünet nélküli betűláncként áll rendelkezésünkre. Ha az egyes szavakat szeparálni akarjuk, akkor az első betűtől indulva addig kell a betűláncban előremenni, amíg szótári szót nem kapunk. Mivel a kód prefix, e megtalált szóból újabb betűk hozzácsatolásával már újabb értelmes szót nem kaphatunk. Ezzel az első szót egyértelműen leválasztottuk, és így haladunk tovább. Érdemes meggondolni tehát, hogy például az M = {A,B,C} ábécé és a V = {AB,ABC,BC} szavak alkotta kódolás prefix-e, illetve szeparálható-e? Mit kellene változtatni a szótár szavain? A prefix tulajdonság ellenőrzése A szótár elemeit lexikografikus sorrendbe (betűrendbe) rakjuk. Ekkor minden olyan szó, mely kezdete valamelyik hosszabb szónak, meg kell, hogy előzze emezt. Sőt, ha ilyen párok vannak, akkor a hosszabb szavak egyike közvetlen követi prefixumát. Vagyis a rendezett szótárban elegendő az egymást követő párokat összehasonlítani, hogy kiderüljön, a kód prefix-e.


11. oldal


SHANNON MÁSODIK TÉTELÉNEK IDEVÁGÓ ÁLLÍTÁSA A CÉL, HOGY ADOTT S FORRÁSHOZ ADOTT M CSATORNAÁBÉCÉ MELLETT MINÉL JOBBAN MEGKÖZELÍTSÜK A MINIMÁLIS

L0 ÁTLAGOS SZÓHOSSZÚSÁGOT ÚGY, HOGY A KÓD SZEPARÁLHATÓ IS LEGYEN EGYÚTTAL.

A TÉTEL KIMONDJA, HOGY HA A FORRÁS ELOSZLÁSA ÉS AZ ÁBÉCÉ ADOTT, AKKOR MINDIG KÉSZÍTHETŐ OLYAN PREFIX KÓD, MELYBEN AZ ÁTLAGOS SZÓHOSSZÚSÁG NEM HALADJA MEG

1 BETŰVEL SEM A

MINIMUMOT:

L0 ≤ L’ < L0 + 1 Sőt, Shannon megadta a kód elkészítésének receptjét is, a pontos kódolási algoritmust (lásd: következő tétel).


12. oldal


6. SHANNON-ALGORITMUS SZIMBOLIKUS KÓDSZAVAK KÉSZÍTÉSÉRE Bevezetés Az algoritmus természetesen nem a fizikai kódszótárt, hanem az úgynevezett szimbolikus kódot szolgáltatja. A szimbolikus kód ábécéje nem fizikai jeleket, hanem egy szimbólumkészletet tartalmaz, melyek mindegyikét a fizikai csatorna egyegy jelének feleltetjük meg. A Shannon-algoritmus 1. lépés A hírkészletet átrendezzük a p eloszlás elemeinek csökkenő sorrendje szerint. Az egyszerűség kedvéért feltehetjük, hogy az eloszlás már rendezett: p1 ≥ p2 ≥ p3 ≥ … ≥ pv 2. lépés Meghatározzuk a szóhosszakat: Li :=  − log B ( pi )  3. lépés Elkészítjük azt a monoton növő (qi) számsort, melynek elemei a (pi) sorozat részletösszegei az előző elemig bezárólag: q1 = 0, q2 = p1, q3 = p1 + p2, … qv = p1 + p2 + … + pv-1


13. oldal


4. lépés Felírjuk a (qi) számsor tagjait a B alapú számrendszerben, s a törtrész Li számú jegyét megtartjuk. Ezek lesznek a szimbolikus kódszavak. Mivel p1 + p2 + … + pv = 1, és minden qi kisebb ennél az összegnél, ezért a qi mindegyike valódi tört. Házi feladatként hozzuk létre az algoritmussal azt a bináris prefix kódot, amellyel azt kódoljuk, hogy egy dobókockával kapott érték kisebb-e háromnál, három és öt közé esik-e, vagy pedig 6. Annak bizonyítása, hogy a kapott szótár átlagos szóhosszúsága megfelelő Ez abból következik, hogy minden xi ∈ S hír kódolására olyan ai ∈ M* szót alkottunk, melynek hossza Li :=  − log B ( pi )  . A felfelé kerekítés miatt: − log B ( pi ) ≤ Li < − log B ( pi ) + 1 Ezt az egyenlőséget a pozitív pi – vel szorozva és i=1..v-re összegezve kapjuk: v

v

v

v

i =1

i =1

i =1

i =1

− ∑ pi log B ( pi ) ≤ ∑ pi Li < −∑ pi log B ( pi ) + ∑ pi Áttérve a B alapú logaritmusról kettes alapúra: v

− ∑ pi log 2 ( pi ) i =1

log 2 ( B )

v

v

− ∑ pi log 2 ( pi )

i =1

log 2 ( B )

≤ ∑ pi Li <

i =1

v

+ ∑ pi i =1

A törtek számlálójában felismerhetjük az entrópia formuláját, középen pedig az átlagos szóhosszúságét. Az egyenlőtlenségek a behelyettesítések után így alakulnak: H (S ) H (S ) ≤ L' < +1 log 2 ( B ) log 2 ( B ) Mivel az itt szereplő törtek éppen az L0 szóhosszúsággal azonosak, az átlagos szóhosszúság valóban eleget tesz a tételnek.


14. oldal


7. A KÓD GEOMETRIÁJA Kódszóból egy téri pont A blokk kódnak nevezett szótárak szavai azonos hosszúságúak. A bináris blokk kódok továbbításánál fellépő hibák matematikai elemzéséhez alkalmas a Hamming által kidolgozott geometriai modell. Egy úgynevezett karakterisztikus függvény segítségével a „0” illetve „1” szimbólumokhoz hozzárendeljük a 0 illetve 1 számokat. Vagyis a bináris blokk kód egyes szavaihoz hozzárendelünk egy rendezett szám n-est (pl. számhármast). Az ilyen rendezett szám n-est felfoghatjuk úgy, mint az n-dimenziós tér egy pontját vagy vektorát. A bináris kódtér A bináris kódszavak betűivel csak olyan pontokat adunk meg, melyeknek bármelyik koordinátája 0 vagy 1. E pontoknak a halmazát nevezzük Hamming-féle bináris kódtérnek. Például a három bites kódszavak tere az egységkocka nyolc csúcsa.

Természetesen a háromnál több bitből álló kódok geometriai modellje már nem ilyen szemléletes, de előnyös. A háromdimenziós modellen látható: minden egyes pontból 3 él indul ki, és a szomszédok koordinátái mindig csak egy bittel térnek el a szóban forgó pontétól. Az n-dimenziós térben ezzel analóg módon a kockának 2n számú pontja van; minden pontnak n számú szomszédja van.


15. oldal


Hamming-féle norma Az x = (x1, x2, x3, …, xn) vektor normája a koordináták négyzetösszege. A Hammingvektorok koordinátáit persze felesleges négyzetre emelni, s így a definíció egyszerűsödik: az a = (α1,α2,…,αn) bináris kódszó Hamming-féle normája: a

H

= α1 + α 2 + ... + α n

(Egyes forrásokban – például Márkus Tibor előadásán – a norma ezen összeg moduló 2 vett értéke. Ez esetben az előbb felírt összeget a továbbiakban nevezzük norma helyett súlynak!) Ez a norma a kódszóban szereplő 1-esek száma. A mozgás, mely a kocka élein történik, annyi lépésben visz a csúcsból az origóba, amennyi a kérdéses kódszó normája. Ezt általánosíthatjuk két tetszőleges pont esetére is: két pont közötti távolságon a kockaéleken vezető legrövidebb összekötőutat alkotó élek számát értjük. Így pontosan annyi lépést kell tennünk, ahány helyen a két kódszóban különböznek a bitek. Pontosabb definícióhoz jutunk, ha értelmezzük a két pontot összekötő vektor különbségét. A különbség pedig az összeadás inverz művelete, amit moduló 2 értelmezünk, s így adódik, hogy a moduló 2 kivonás értéktáblázata egyezik az összeadáséval. Tehát két Hamming-vektor összeadását illetve kivonását úgy értelmezzük, hogy a műveletet a megfelelő koordinátákkal végezzük el. A távolság, mint két pont relatív helyzetét jellemző számérték azt mutatja meg, hogy a két szó hány helyen különbözik. HAMMING-FÉLE GÖMB Definiálhatjuk egy A pont r-sugarú környezetét: azok a pontok tartoznak ebbe a ponthalmazba, melyeknek a középponttól való távolsága az adott ponttól r-nél nem nagyobb. Az A ponttól pontosan r távolságra levő pontok halmazát pedig r-sugarú gömbnek nevezzük. A Hamming-féle gömb persze egyáltalán nem hasonlít a megszokott felületre; diszkrét pontokból áll, a sugara pedig nem egyenes. A maximális r = n sugarú gömbfelület pedig egyetlen pontból áll, a kocka átellenes pontjából.


16. oldal


8. SZÁMRENDSZEREK A történelem folyamán rengeteg számolási módszer látott napvilágot, de mi most csak a tízes számrendszerrel, és a hozzá hasonló, de más alapú helyiértékes számrendszerekkel foglalkozunk. A számítógépek számára a bináris számábrázolás a célravezető, de az emberek a tízes számrendszert használják. Ez vezet minket ahhoz, hogy a számrendszerek közti átváltással foglalkozzunk. Használnak a számítástechnikában 8-as, 16-os számrendszert; utóbbi jelkészletét az angol ábécé első hat betűjével egészítik ki. A többjegyű kóddal felírt szám jegyeinek helyiértéke a számrendszertől függ; ezek – a kialakult szokások szerint – jobbról balra növekednek, és a számrendszer alapszámának egész kitevőjű hatványai. Ha a számrendszer alapja a q>1 egész, akkor az anan-1an-2…a2a1a0 jegyekkel felírt szám értéke: anqn+an-1qn-1+…+a1q1+a0q0. Ez átalakítható az úgynevezett Horner-sémába: (…((anq+an-1)q+an-2)q+…+a1)q+a0 Ennek segítségével könnyű egyik számrendszerből a másikba váltani, tízesből egy másik alapúba, vagy másik alapúból a tízesbe. Például az 10112 algoritmusszerűen megfejthető: szorozni kell az alapszámmal, majd hozzáadni a következő számjegyet (balról jobbra): ((1 2+0) 2+1) 2+1=1110 Ha tízes számrendszerből alakítunk át egy számot más alapúba, akkor a Hornersémát úgy kell használnunk, hogy az ismeretlenek értékét jobbról balra határozzuk meg maradékos osztás alapján. Házi feladatként váltsuk át a 200510-öt hetes számrendszerbe!


17. oldal


A helyiértékes törtek vizsgálatakor szorítkozhatunk az úgynevezett valódi törtekre, vagyis melyeknek nulla az egész része: 0,a-1a-2…a-m Ekkor az értelmezés: −m

∑a q

i = −1

i

i

Így például 0,0315 = 0 5-1+3 5-2+1 5-3=0,12810. A valódi törtekhez is felírható egy Horner-séma, amiből a következő számítási módszer adódik: például a 0,687510 átváltása kettes számrendszerbe: jegy

tört

0

6875 X 2

1

375

0

75

1

5

1

0

Ebből következik, hogy 0,687510=0,10112. Tapasztalhatunk azonban olyat, hogy ami tízes számrendszerben véges tizedes tört, az egy másik számrendszerben végtelen sok jegyből áll (vagy fordítva). Házi feladat találni ilyen példát! Vizsgáljuk meg, hogy amennyiben az α=0,α1α2α3… törtnek csak az első n darab (nulla utáni) jegyét tároljuk (vagy írjuk le), akkor mekkora hibát vétünk ezzel! 0,α1α2α3…αn | αn+1αn+2… A fenti felírásban a „|” utáni jegyek elvesznek. A hiba nagysága tehát:

α n +1q − ( n +1) + α n + 2 q − ( n + 2) + ... Mivel minden αi legfeljebb q-1, ezért a maximális hiba: (q − 1)q − ( n +1) + (q − 1)q − ( n + 2 ) + ... = (q − 1)q − ( n +1) (1 + q −1 + q −2 + ...) = q − n Utóbbiak a végtelen sorok összegére vonatkozó ismeretek alapján adódnak.


18. oldal


9. FIXPONTOS, LEBEGŐPONTOS KÓDOK Fixpontos kódok Az egész számok kódolásánál egy fix kódhosszt használnak (pl. 4, 8, … bit). Többféle kódolás létezik, de az első bitből általában megállapítható a kódolt szám előjele: ez az előjelbit. A kódszó többi bitje, melyek a szám abszolút értékét kódolják, a helyiértékbitek. A legjobban használható kódolás a komplemens-kód (=kettes komplemens kód) Kettes komplemens kód A zérus legyen: 0000 0000; és előre, illetve hátra való számlálással képezzük a pozitív, illetve negatív számok kódszavait. Megállapodás szerint a pozitív számok szavai addig tartanak, amíg az első bit nulla (vagyis 127 a maximum); a negatív számoké pedig addig, amíg az első bit egy (vagyis –128 a minimum). Pozitív szám kódolása (0-127): Felírjuk kettes számrendszerbeli alakját, és szükséges számú vezető nullával egészítjük ki. Például +11: 0000 1011. Negatív szám kódolása ((-128)-(-1)): felírjuk abszolút értékének kettes számrendszerbeli alakját; kiegészítjük vezető nullákkal, majd: 1. minden bitet ellentétesre váltunk, 2. az így kapott bináris számhoz egyet adunk. Például: –11: 1111 0101, mert: 0. lépés: 0000 1011 1. lépés: 1111 0100 2. lépés: 1111 0101. Megjegyzés: ez a módszer a „visszafelé forgatás” elvéből következik.


19. oldal


Többletes kód A komplemens kód egyetlen esetben okoz kényelmetlenséget, amikor két kódolt számról meg kell állapítani, hogy melyik a nagyobb. Ebben a kódolásban a komplemens kód előjelbitjét negálják, vagyis 2m többletet adnak a teljes bináris kódszóhoz. Például +11: 1000 1011; –11: 0111 0101. Lebegőpontos kódok Valós számok ábrázolása. Bármilyen B-alapú számrendszert is használunk, minden x valós szám (vagy annak közelítése) megadható x = µ

Bk, ahol µ a szám

mantisszája, és a B bázis k kitevője a szám karakterisztikája. Ezt még normalizálni kell: normalizált a felírás, ha 1/B≤|µ |<1. További követelmény: rögzíteni kell a kódszavak hosszát, és azt is meg kell adni, hogy ebből a mantissza, illetve a karakterisztika számára hány bitet használunk. Sőt: rögzíteni kell, hogy a két komponenst milyen előjeles kóddal ábrázoljuk. A mantisszát komplemens kódban, a karakterisztikát többletes kódban célszerű ábrázolni.


20. oldal


10. FIXPONTOS ÉS LEBEGŐPONTOS ARITMETIKAI MŰVELETEK Fixpontos aritmetikai műveletek A komplemens kódolás lehetővé teszi, hogy a számok szavait – mint bináris számokat – összeadjuk, ekkor helyes eredményt fogunk kapni, még az előjelbit is helyes lesz (még szorzásnál is), és a legfelső biten keletkező átvitel közömbös. A műveletek eredménye időnként átlép, túlcsordul az ábrázolás határain: ilyenkor a túlcsordulás bit 1-esre vált. Lebegőpontos aritmetikai műveletek Additív műveletek Az összeadás és a kivonás elvégzésénél az első lépés a közös karakterisztikára hozás: a = 0,3416 1004 → 0,0034(16) 1006 b = 0,5712 1006 → 0,5712 1006 a+b = 0,5776 1006 Közös karakterisztikának mindig a nagyobbikat választjuk: a kisebb számot kell denormalizálni, és a léptetési művelet során a két karakterisztika különbségét kell léptetni. Ezzel pár jegy elvész (pl. fent a 16 jegyek elvesznek), de azon a helyiértéken a másik szám jegyeit már eleve nem ismerjük. Ha a karakterisztikák különbsége nagyobb, mint a mantissza hossza, akkor kisebb számból a denormalizálás nullát csinál: virtuális nulla.


21. oldal


Kivonásnál egy kellemetlen jelenséggel találkozunk: bináris normál mantisszák kivonásakor a különbség kisebb lesz 2-1-nél, tehát az a helyiérték mindig 0 lesz, sőt a 2-2, 2-3… helyre is kerülhet 0. A legkisebb különbség 2-m. a = 0.1101101 b = 0.1101001 a-b = 0.0000100 → 0.1000000. A vastagított nullák helypótló nullák, nem értékesek. Ha a helypótló nullák száma h, akkor a relatív hibakorlátja az eredményt ábrázoló lebegőpontos adatnak nem 2-m, hanem 2-m+h. Multiplikatív műveletek Sem szorzásnál, sem osztásnál nem kell a mantisszákat átalakítani. Más jelenséggel találkozunk: 1/q

22. oldal


11. MINTAVÉTELEZÉSES KÓDOLÁS (HANGRÖGZÍTÉS PÉLDÁJÁN) Egyre nagyobb lett az igény a hangok, zenék digitalizálására; elvégre a digitalizált zenei vagy hanganyag jobban továbbítható és jobban is tárolható. A hang digitális kódolására mintavételezéses kódolást alkalmaznak. Az eljárás lényege, hogy előre megadott szabályos időközönként megmérik az analóg akusztikus jel nagyságát, és azokból diszkrét digitális jeleket hoznak létre. Jó esetben ennek a diszkrét jelsorozatnak az információtartalma megegyezik a folytonos akusztikus jel információtartalmával: ehhez az kell, hogy a mintavételi frekvencia legalább kétszer akkora legyen, mint az eredeti analóg akusztikus jelben előforduló legmagasabb frekvencia. Szabványos mintavételi frekvenciák a következők: 11,025 kHz; 22,05 kHz; 44,1 kHz csatornánként. Egy csatorna esetén monóról, két csatorna esetén sztereóról beszélünk. Minthogy az emberi hallás kb. 20 Hz és 20 kHz között érzékel, így a 44,1 kHz-es mintavételi frekvencia Hi-fi minőséget biztosít. A mintavételezéssel kapott amplitúdóminták végtelen sok értéket felvehetnek, de ebből csak véges sok értéket tárolhatunk pl. 8 vagy 16 bit nagyságú minták segítségével: a legközelebbi értéket kell kiválasztani. A digitális hangállomány minőségét 3 tényező befolyásolja: – mintavételi frekvencia (v) – kvantálás szóhosszúsága (k) – csatornák száma (N) Példa: v = 44 100 Hz (1/s); k = 16 bit; N = 2. T (tárigény) = 1411200 bit/sec, ami kb. 605 MB/óra.


23. oldal


12. AUTOMATA Moor-automata A Moor-automatát az automata lehetséges – véges sok – állapotával és – szintén véges sok – betűkkel jellemezhetjük. Az automata egy a1a2…ak szót olvas (ai ∈ A) és közben mindig egy-egy qi ∈ Q állapotba kerül. Ezt írja le az átmenetfüggvény: δ

:

Q X A → Q, vagyis a

következő állapotot a jelenlegi állapot és az olvasás alatt lévő betű együttese határozza meg. Véges determinisztikus automata Jellemzése: M = (A,Q,δ0,δF,δ) – ennek jelentése M = (ábécé, állapothalmaz, kezdő állapot, végső állapot, átmenetfüggvény) 1. példa

Itt A = {0,1}; Q = {p,q,r}; q0 ≡ p;

δ(p,0)=q; δ(p,1)=q; δ(q,0)=q; δ(q,1)=r; δ(r,0)=q; δ(r,1)=r.


24. oldal


2. példa

Itt A = {0,1}; Q = {p,q,r,s}; q0 ≡ p; qF ≡ s;

δ(p,0)=q; δ(p,1)=q; δ(q,0)=q; δ(q,1)=r; δ(r,0)=s; δ(r,1)=r. Ez az automata ilyen szavakat olvas végig: w = (0 vagy 1)00…0111…10. Ugyanis ezek az elfogadott szavak, vagyis azok a szavak, melyeket az automata végigolvas, és az automata végállapotba kerül. Az automatát minden pillanatban jellemzi az aktuális konfigurációja, ami egy (q,a) rendezett pár: milyen állapotban van, és milyen betűt olvas. A 2. példa esetén a w = 100110 szó alkalmával a konfigurációk sorozata: (p,1)

(q,0)

jelkészletnek.

(q,0)

(q,1)

(r,1)

(r,0)

(s,⊥); ahol ⊥végjelkarakter, ami nem része a


25. oldal


13. KÓDOLÁS: PARITÁSELLENŐRZÉS, BLOKK-KÓDOLÁS, LINEÁRIS KÓDOLÁS Bevezetés – a kódszavak Ha a forrás egyes állapotaihoz képest kevesebb állapottal rendelkezik a csatorna, akkor az az egyetlen megoldás marad, hogy a forrás egy hírének a csatorna több jeléből álló jelsorozatot kell megfeleltetnünk. A csatorna jelkészletét ábécének nevezzük, az egyes jeleket pedig betűknek. A lehetséges betűk száma az ábécé volumene: B. A kódolónak tehát az a feladata, hogy a forrás bármelyik állapotának bekövetkeztekor előállítsa és a csatornába juttassa azt a közleményt, amely az M ábécé elemeiből álló adott sorozat fizikai megfelelője. Az ábécé elemeiből tehát sorozatokat kell alkotnunk – ezek a sorozatok a kódszavak. A kódszavakból pedig összeállítható egy szótár. A digitális bináris kódszavak az M = {0;1} ábécé két betűjét használják. Így ha a kódszavak n bitesek, akkor 2n szó létezhet. Általánosan: ha az ábécé B-féle jelet tartalmaz, és n betűs kódszavakat képezünk, akkor Bn szót kapunk. A legföljebb n hosszú kódolás esetén lehetnek 0, 1, 2, …, n hosszú szavak; ezek száma: B 0 + B 1 + B 2 + ... + B n =

B n +1 − 1 B −1

Ekkor a forrásból kilépő különböző hírek száma, vagyis a hírkészlet volumene legfeljebb annyi lehet, mint az előbbi tört.


26. oldal


Paritásellenőrzés Egyik legegyszerűbb hibajelzési mód, amely egyetlen hibáról jelzést ad, de a hiba helyéről nem képes tájékoztatni. Pl. 8 bites kódszavak esetén minden kódszó elejére vagy végére (ez megállapodás kérdése) elhelyezünk egy paritásbitet: 1011 0011|1 A paritás bitet úgy választjuk meg, hogy a kilenc jegy moduló 2 vett összege nulla legyen. Ha tehát nincs hiba adattovábbításnál, akkor a moduló 2 vett összeg nulla, ha egyetlen hiba van, akkor 1 lesz. Több hiba lehetősége mellett már semmit nem mondhatunk, hiszen a hibák akár kompenzálhatják is egymást. Blokk-kódolás Egy α kódszót felbontunk (amennyiben ez lehetséges) azonos hosszúságú részekre:

α1, α2, …, αk; mindegyiknek a hossza legyen m betű: α1

0

1

0

…

1

0

α2

1

1

0

…

1

1

α3

0

0

1

…

0

1

…

αk

… 1

1

1

…

1

0

0

1

0

…

1

0

Az egyes oszlopokat illetve sorokat kiegészítjük egy-egy paritív bittel, és az így kapott sor illetve oszlop találkozásánál szintén kiszámítunk egy azon sorra illetve oszlopra vonatkozó paritív bitet. Belátható: egy hiba felismerhető a teljes továbbított csomagban, és javítható is! Ha tehát m oszlop van, és k sor, akkor m+k+1 bit kell az ellenőrzéshez.


27. oldal


Lineáris kódolás Legyen az α kódszó: α = c1c2c3…cn, ahol ci ∈ {0,1} Ehhez még ugyanennyi betűt hozzáillesztünk a következő számolási eljárással: minden i = 1..n esetén : cn+i :=c1⊕c2⊕…⊕ci-1⊕ci+1⊕…⊕cn, vagyis az eredeti kódszó minden betűjét összeadjuk az i-edik jegy kivételével! Így megkapjuk a c1c2c3… cncn+1…c2n kétszeres hosszúságú kódszót. Állítás: egy hiba felismerhető, és javítható is! A bizonyítás legyen házi feladat, de annyit azért segítenék, hogy két esetet kell vizsgálni: az egyik szerint a hiba az első n darab bitben van, a második eset szerint pedig a második n darab bitben.


28. oldal


14. HIBAKEZELÉS; ADATOK TÖMÖRÍTÉSE Hibakezelés A hiba hatásainak kivédéséhez elsősorban arról kell gondoskodni, hogy a hibát észrevegyük. Pusztán a hiba észlelése csak akkor elég, ha lehetőség van a közlemény – akár többszöri – megismétlésére (pl. ha csak egyetlen hiba lehetséges, és egy adott üzenetet háromszor is továbbítanak, akkor a hiba javítható is). A továbbiakban blokk-kódokkal foglalkozunk.

I. Belátható, hogy a hibát sem észlelni, sem kezelni nem lehet, ha a kódszótár minden n-bites kódszót tartalmazza, hiszen a címzett így nem veheti észre a hamis közleményt. A CÍMZETT CSAK AKKOR ÉSZLELHETI, HOGY HAMIS A CSATORNA KIMENETÉN MEGJELENŐ ÜZENET, HA AZ NEM RÉSZE A KÖZÖS MEGEGYEZÉSSEL KIALAKÍTOTT ÉS HASZNÁLT SZÓTÁRNAK.

II. Tegyük fel, hogy a maximális hiba súlya egy, és bármelyik bit lehet az, amelyik sérül. Ekkor nem szabad, hogy bármely kódszó közvetlen szomszédja is szótárbeli kódszó legyen. Általánosítva: a legfeljebb k súlyú hiba észlelésére alkalmas kód szótárában a szavak minimális távolságának legalább k+1-nek kell lenni; ekkor a címzett felismeri a hamis közleményt, de az eredeti szót nem feltétlenül ismerheti fel!

III. Ha két különböző kódszó a és b, akkor ha a-ra rárakódik egy legfeljebb k súlyú hiba, akkor az ’a’ körüli k sugarú Hamming-gömbben marad. Hasonlóképpen van ez ’b’ esetében is, tehát ha meg akarjuk tudni, hogy egy hibás kódszó melyik kódszó volt eredetileg, akkor a két gömbnek egyetlen közös pontja sem lehet. Ebből következően a legfeljebb k súlyú hiba javítására alkalmas kód szótárában a szavak minimális távolságának legalább 2k+1-nek kell lenni.


29. oldal


Adatok tömörítése Előadáson (Márkus Tibor előadásán) a szakaszhossz-kódolással ismerkedtünk meg, amely egy adatvesztés nélküli tömörítéses kódolás. A módszer akkor előnyös, ha sok 0, és viszonylag kevéskre 1-es van egy kódsorozatban: 0000001000000000000010001011

1. első lépésben felbontjuk a számsort olyan részekre, melyek utolsó jegye 1-es, és az összes előtte álló jegy 0: 0000001 | 00000000000001 | 0001 | 01 | 1

2. minden szakaszban meghatározzuk a nullák számát bináris alakban (i), és az i jegyeinek számát (j).

3/a. ha i>1, akkor a szakasz kódja: j-1 db 1-es | 0 | „i”, 3/b. ha i=1, akkor a szakasz kódja 01, 3/c. ha i=0, akkor a szakasz kódja 00.

Ezek alapján az előző oldalon szereplő számsor tömörített alakja: 1101101110110110100100 Házi feladatként gondoljuk meg, hogyan lehet az előző sorból visszafejteni a kódolt számsort!


30. oldal


15. AZ ADATFELDOLGOZÁS ELEMEI Az első számítógépeket matematikai feladatok megoldására készítették, de már az 1960-as évektől a számítógépes alkalmazások jelentős részét az adatfeldolgozás tette ki. Elemi adat: típus + érték (utóbbihoz tartozik egy domain, vagyis egy értelmezési tartomány) Elemi adattípusok: CHAR(n):

n hosszú karaktersorozat

VARCHAR(n):

legfeljebb n hosszú karaktersorozat

INTEGER:

egész szám (röviden: INT)

REAL:

valós (lebegőpontos) szám

stb… Rekord: az adatbázis alapvető egysége; szekvenciálisan szerkesztett adat, vagyis mezők szekvenciája: a mezők adatai elemi adatok, melyek különböző típusúak lehetnek. Egyed: egy, a valós világban létező dolog, amit attribútumokkal akarunk leírni, pl. a Mikulás. Attribútum: az egyed egy jellemzője, pl. a Mikulás életkora, szeme színe, rénszarvasainak száma stb. Relációséma: attribútumhalmaz, melyhez azonosítónevet rendelünk. R(A1, A2, …, An) módon szokás jelölni, ahol minden Ai attribútum, R pedig a séma neve. Például Harry Potter mindenízű cukorkáinak nyilvántartására szolgáló relációséma: Cukor(kódszám, ízhatás, szín) Több adattábla (=reláció) együttesen alkotja a relációs adatbázist, amely egy teljes jelenségkör leírására alkalmas. A relációs adatmodell lényege, hogy a különböző relációsémák azonos attribútumokat tartalmazhatnak, ezáltal kerülnek kapcsolatba egymással, és így a különálló adattáblák együttese egy szervesen összefüggő adatbázist alkot. Megjegyzés: minden adattábla gerince egy relációséma (lásd: mindenízű cukorkák).


31. oldal


I. halmazműveletek Kompatíbilis táblák esetében alkalmazhatók. Két tábla kompatíbilis, ha a hozzájuk tartozó relációsémák attribútumhalmazai darabszámban, és az elemek domainjében azonos, vagyis az attribútumok csak elnevezésben különböznek.

1. unió T1 és T2 kompatíbilis tábla. Ekkor T := T1 U T2 esetén T azon sorokat fogja tartalmazni, amelyek akár T1-ben, akár T2-ben előfordulnak. Az unióművelet tehát két lépésben történhet: először a két tábla egymás után írásával, majd az ismétlődő sorok törlésével.

2. metszet T:=T1 ∩ T2: azon sorokat fogja tartalmazni, melyek T1-ben és T2-ben is előfordulnak.

3. különbség T:=T1 – T2: T1 azon sorait fogja tartalmazni, amelyek T2-ben nem szerepelnek.

II. Projekció Adott oszlopok kiválasztása a táblából attribútumok kiválasztásával. Jelölése: π attribútumlista(tábla)


32. oldal


III. Szelekció (kiválasztás) Adott sorok kiválasztása egy feltételnek való megfelelés alapján Jelölése: σfeltétel(tábla) [szigma] Például σízhatás= torma(cukorkák). IV. kombinációs műveletek Itt két tábla összekapcsolásával új táblát hozunk létre.

A) Descartes-szorzat T1 és T2 táblák Descartes-szorzatát úgy kapjuk, hogy T1 minden sorát párosítjuk T2 minden sorával: T = T1 X T2. Ilyenkor természetesen az eredmény tábla attribútumhalmaza a korábbi két tábla attribútumhalmazainak uniója.

B) Természetes összekapcsolás (Natural Join) Feltétel, hogy legyen közös attribútuma R1-nek és R2-nek. A két tábla Descartesszorzatából kiválasztjuk azokat a sorokat, amelyek egy adott attribútum (vagy attribútumhalmaz) tekintetében megegyeznek, majd projekcióval a duplán szereplő attribútumot (vagy attribútumokat) csak egy példányban tartjuk meg. Házi feladat legyen ezt az eljárást két megfelelően megválasztott táblázattal kipróbálni!

C) Theta-join: a táblák Descartes-szorzatából tetszőleges feltétel szerint választunk ki sorokat. Pl. (szín = ’piros’) és (méret > XL)

Bernát Péter (BEPMABT.ELTE) [email protected]

1. A KOMMUNIKÁCIÓS RENDSZER FŐ JELLEMZŐI; A SHANNON-FÉLE

Recommend Documents