Eötvös Loránd Tudományegyetem Könyvtártudományi Informatikai Tanszék Fülöp Géza Az információ




Download 2.78 Mb.
bet9/47
Sana09.06.2021
Hajmi2.78 Mb.
1   ...   5   6   7   8   9   10   11   12   ...   47
3. ábra Bináris kód fadiagrammja

Legyen a forrásjelek halmaza S = {x1,x2,x3,x4}.

A kódfát a 3. ábrán láthatjuk. (Ha a szögpontokból nem két, hanem három, vagy több ágat indítunk ki, három stb. elemű kódot állíthatunk elő).

A forrásábécét sokféleképpen oszthatjuk részhalmazokra. Például úgy is, ahogy fent tettük, hogy rendre egy-egy jelet választunk le. Minden elméleti megfontolás nélkül észrevesszük, hogy így a kódfa rendkívül aszimetrikus. S ez az aszimetria összefüggésben van a kód hatásfokával. Ha például a fenti esetekben a négy forrásjel előfordulási valószínűsége egyenlő a forrás entrópiája H = log n = 2 bit.

A kódolt üzenet átlagos jelhossza pedig:

                                    

Mivel lineáris kódról van szó, a jelek száma egyenlő a bitek számával.

A cél az, hogy a közleményt minél kevesebb jellel továbbítsuk, azaz minden jel a lehető legtöbb információt hordozza. Tudjuk, hogy az egy jelre jutó átlagos információ akkor a legnagyobb, ha a jelek valószínűsége egyenlő. Ezen a megfontoláson alapulnak a különböző kódolási eljárások. Az alábbiakban a Shannon-Fano féle kódolási eljárást ismertetjük.



Legyen X a forrásábécé jeleinek halmaza és P a jelekhez tartozó valószínűségeké:

X=

x1

x2

x3

x4

x5

x6

x7

x8

P=

















Írjuk fel a forrásjeleket valószínűségük csökkenő sorrendjében, és osszuk fel két, lehetőleg egyenlő részhalmazra. Az egyik részhalmazhoz rendeljük hozzá a 0-t, a másikhoz az 1-et, majd a felosztást folytassuk mindaddig, amíg mindegyik részhalmaz csak egy-egy elemet tartalmaz. A részhalmazokhoz természetesen minden felosztásnál hozzárendeljük a 0-t és az 1-et. Az eljárást az alábbi táblázat és kódfa szemlélteti.

           Jel   Valószínűség

           

                                    0

           

           

                                       10

           

           

                                                     110

           

                                       11

           

                                                      111



           



4. ábra A Shannon - Fano-féle eljárással készített kód kódfája.

Lássuk milyen lesz ebben az esetben a kódolás hatásfoka?



A forrás entrópiája:

                                    

A kódolt forrásjelek átlagos hossza (az egy jelre jutó jegyek átlagos száma)::



                                    

Minthogy a fenti példában a forrásjeleket sikerült úgy csoportosítani, hogy a részhalmazok való­szí­nű­ségei rendre egyenlők legyenek a kódolt közlemény jelenkénti entrópiája 1 bit, s a kódo­lás hatásfoka 100% lett. Ha a forrásjeleket nem lehet egyenlő valószínűségű részhal­mazokra osztani, a Shannon - Fano-eljárással nem érhető el a 100%-os hatásfok, de jól megközelíthető.

A kódolásnál nagyon fontos szempont a gazdaságosság. A távközlő berendezések üzemel­tetése pénzbe kerül, s teljesítőképességük is korlátozott. A cél tehát az optimális kódolás. Az üzenet annyi és csak annyi jelet tartalmazzon, amennyi szükséges. Minden felesleges jel többletköltséget jelent. A kódszavak hosszát a lehető legkisebbre kell csökkenteni. Ennek azonban határt szab az egyértelmű dekódolhatóság igénye, hiszen amint a példaként adott kódfáról leolvasható, ha egy betűt 0-val kódolunk, a többinek a kódja már csak egy 1-gyel kezdődhet stb. S a másik baj, hogy az optimálisan kódolt üzenet, amelyben minden jel maxi­mális információt hordoz, teljesen védtelenül ki van szolgáltatva a zajnak. Zajos csatornában - márpedig tudjuk, hogy a valóságban minden csatorna zajos - az átviteli bizton­ságot csak a redundancia növelésével lehet biztosítani.

A redundancianövelés azt jelenti, hogy olyan jeleket adunk az üzenetben, amelyek nem tartalmaznak új információt, vagy amelyek nem az üzenet tartalmára vonatkozó információkat hordoznak, de lehetővé teszik a hibák felismerését és kijavítását. Másképp fogalmazva: mivel a zaj csökkenti a csatorna kapacitását, a redundáns jelek hozzáadásával az időegységenként átvitt jelek hasznos információtartalmát annyira csökkentjük, amennyit a csatornán a zaj mellett át lehet vinni.

A legegyszerűbb, de legkevésbé gazdaságos megoldás, ha az egész üzenetet, vagyis minden jelet megismételnek. Ebben az esetben a redundancia 50%-os.

A redundancia növelésének másik módszere, hogy a jelentéshordozó jelekhez ellenőrző jeleket adnak. Ha például az üzenet jeleit négyjegyű kódszavakkal kódolják, a négy jegyhez még három ellenőrző jegyet kapcsolnak, mégpedig úgy, hogy a hét bináris jel összege, ha az átvitel hibátlan volt, mindig páros legyen. Ha az eredmény páratlan, nemcsak az derül ki, hogy a kódszó hibás, hanem az is, hogy melyik jel volt a ludas. Példaként ismertetjük H. W. Hamming amerikai matematikus hibajavító kódját. A tíz decimális számjegy bináris kódo­lásához négy jelre van szükség (23=8 ; 24=16). A négy információt hordozó jelhez három ellenőrző - úgynevezett paritás-ellenőrző - jegyet adnak, mégpedig a következőképpen:

- ha az első három helyértéken az egyesek száma páratlan, az E helyértékre 1-es kerül;



- ha az első, második és negyedik helyen páratlan az egyesek száma, az F helyértékre kerül 1-es;

- ha az első, harmadik és negyedik helyen páratlan az egyesek száma, akkor a G helyértékre kerül 1-es.



decimális jegy




A

B

C

D

E

F

G

  0




0

0

0

0

0

0

0

  1




0

0

0

1

0

1

1

  2




0

0

1

0

1

0

1

  3




0

0

1

1

1

1

0

  4




0

1

0

0

1

1

0

  5




0

1

0

1

1

0

1

  6




0

1

1

0

0

1

1

  7




0

1

1

1

0

0

0

  8




1

0

0

0

1

1

1

  9




1

0

0

1

1

1

0

A hiba felderítése a következőképpen történik: egy ellenőrző áramkör minden kódszó vétele után három összeget határoz meg:

                                    A + B + C + E = S1

                                    A + B + D + F = S2

                                    A + C + D + G = S3

Ha az átvitelben nincs hiba, mindhárom összeg páros. Ha csak az egyik összeg hibás (páratlan), a hiba az ellenőrző helyértékben van. Ha két összeg hibás, a hiba abban a helyértékben van, amelyik a két összegben szerepel, de a harmadikban nem.

A fenti példák természetesen csak ízelítőt adhattak a kódolás elméletéből és gyakorlatából, hiszen az elmúlt évtizedekben a kódoláselmélet igen gyorsan fejlődő önálló diszciplínává vált. Az információátvitel biztonságát a berendezés szerkezetének és működésének bonyolításával is lehet növelni (visszacsatolással stb.) Végeredményben így is, úgy is a redundanciát növeljük. S ez természetesen növeli az átvitel költségét. Hogy meddig kifizetődő a redun­dancia növelése, az mindig attól függ, mekkora pontosságra van szükség. Az űrhajózásban például nyilván sokkal nagyobb redundanciát kell alkalmazni, mint a városi telefon­beszél­getésben. Hogy milyen nagy mértékben sikerült növelni az információátvitel biztonságát, azt az űrkutatási eredmények bizonyítják (Laeser et al., 1987).





Download 2.78 Mb.
1   ...   5   6   7   8   9   10   11   12   ...   47




Download 2.78 Mb.

Bosh sahifa
Aloqalar

    Bosh sahifa



Eötvös Loránd Tudományegyetem Könyvtártudományi Informatikai Tanszék Fülöp Géza Az információ

Download 2.78 Mb.