| 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ódolás hatásfoka 100% lett. Ha a forrásjeleket nem lehet egyenlő valószínűségű részhalmazokra 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 üzemelteté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 maximá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 biztonsá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ódolá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 redundancia 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 telefonbeszélgeté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).
|
