dolás, felbontható kód Prefix kód Blokk kódk Kódfa

Kódelmélet

2007. má május 31.

Gazdasá Gazdaságos kó kódolá dolás

1

Témavázlat Gazdaságos kódolás o Kódolás o Betőnkénti kódolás, felbontható kód Prefix kód Blokk kód Kódfa

o A kódok hosszának alsó korlátja McMillan-egyenlıtlenség Kraft-tétele

o Optimális kód Átlagos szóhossz, a kód költsége Optimális kódok Entrópia Shannon-tétele Bináris Huffman-kód Adaptív kódok: LZ-, LZW-kód 2007. má május 31.


2

Gazdaságos kódolás

2007. má május 31.


3

A hírközlésben szükségünk van arra, hogy valamilyen üzenetet egy csatornán átjuttassunk. A csatorna azonban csak meghatározott jeleket tud befogadni, ezért az üzenetet idınként megfelelıképpen át kell alakítanunk, kódolnunk kell.

Ez az átalakítás olyan kell legyen, hogy a csatorna túlsó oldalán többé-kevésbé helyesen visszaállítható legyen az eredeti üzenet.

Az alábbiakban olyan kódolásokkal foglalkozunk, amelyek – lehetıvé teszik a kódból az üzenet helyes visszaállítását, és – a kódok lehetıség szerint rövidek.

Ennek az elvi korlátait vizsgáljuk.

2007. má május 31.


4

Kódolás Definíció. Az A={a1,…, an} véges, nemüres halmazt ábécé-nek nevezzük, elemei a betők, a belılük képezhetı véges hosszú sorozatok a szavak. Az összes véges hosszú sorozat halmazát A* jelöli. Definíció. Legyen B és C ábécé. A f: B → C* leképezést kódolásnak nevezzük, ha injektív. f(B)⊆ C* a kódszavak halmaza, a kód. A b∈B bető kódja f(b). Az injektivitás garantálja a dekódolhatóságot, vagyis azt, hogy a képelemekbıl helyesen vissza tudjuk állítani a B halmaz elemeit. 1. példa. Legyen B={a, b, c}, C={0, 1} és f(a)= 0, f(b)=01, f(c)=001. Ez a leképezés kódolás. 2007. má május 31.


5

Betőnkénti kódolás, felbontható kód Definíció. Terjesszük ki f-et B*-ra a következıképpen: Legyen b=b1b2…bs∈B*. Ekkor f(b)=f(b1)f(b2 ) …f(bs). A B*-beli szavak kódját a szavakat alkotó betők kódjainak egymás mellé írásával kapjuk. Ekkor az f: B* → C* kódolást betőnkénti kódolásnak nevezzük. Definíció. Az f: B* → C* betőnkénti kódolás felbontható kódot állít elı, ha két különbözı B*-beli szóhoz tartozó kód különbözı. A kód felbonthatósága garantálja az üzenet kódjából az üzenet egyértelmő visszaállíthatóságát. 2. példa. Az 1. példa kódja például nem felbontható, mert f(ab)=f(c). 2007. má május 31.


6

Prefix kód Definíció. Betőnkénti kódolás esetén a kódot prefixnek nevezzük, ha egyik kódszó sem valódi szókezdı része a másiknak. 3. példa. Az elızı példában szereplı kód nem prefix. f(a)= 0, f(b)=01, f(c)=001, Például f(a) szerepel f(b) elején, más szóval f(b) az f(a)-nak folytatása. 4. példa. Legyen B={a, b, c}, C={0, 1} és f(a)= 0, f(b)=10, f(c)=100. Ez a kód prefix. Tétel. Prefix kód felbontható. Bizonyítás. Könnyen adható dekódolási algoritmus. Ez prefix kód esetén egyértelmően elıállítja a kódolt üzenetbıl az eredetit. 2007. má május 31.


7

Blokk-kód Definíció. Betőnkénti kódolás esetén a kódot blokk-kódnak nevezzük, ha a B halmaz mindegyik eleméhez ugyanolyan hosszú kódszó tartozik. Tétel. Blokk-kód felbontható. Bizonyítás. A blokk-kód egyúttal prefix kód is, így az elızı tétel alkalmazható.

2007. má május 31.


8

Kódfa Definíció. Az f: B → C* által létrehozott prefix kódhoz irányított fát, un. kódfát rendelhetünk a következı módon. A fa csúcsaiból legfeljebb |C| elemszámú él vezethet ki, ezeket az éleket C elemeivel címkézzük meg. A fa leveleit (olyan csúcsok, amelyekbıl nem vezet ki él) a B elemeivel címkézzük meg. Ekkor a kódolás a következıképpen olvasható le a fáról. Legyen az egyik levél a b∈B és a gyökérbıl a hozzá vezetı élek címkéi sorban c1, c2, …, ck. Ekkor f(b)= c1c2…ck . A következı példában bináris prefix kód kódfáját látjuk.

2007. má május 31.


9

5. példa. 0

0 b1

0

1

1 b6

b3

1

0

b2

B={b1, b2, b3, b4, b5, b6} C={0,1} f(b1)=000 f(b2)=001 f(b3)=01 f(b4)=1000 f(b5)=1001 f(b6)=11 2007. má május 31.

1

0

0 b4


1 b5

10

A kódok hosszának alsó korlátja

2007. má május 31.


11

McMillan-egyenlıtlenség Tétel. (McMillan-egyenlıtlenség) Tegyük fel, hogy f: B → C* felbontható kódot határoz meg. B ={b1, b2, … , bk}, és az f(b1), f(b2 ), …, f(bk) kódszavak hossza {h1, h2, … , hk}, |C|=c. k 1 Ekkor ≤1

∑

hi c i =1

6. példa. A 4. példa prefix kódjára |C|=2, a kódhosszak 1, 2, 3, a McMillan-egyenlıtlenség teljesül. k

1 1 1 7 ∑ hi = 2 + 22 + 23 = 8 ≤ 1 i =1 c 2007. má május 31.

1


12

Vigyázzunk, a McMillan-egyenlıtlenség nem megfordítható. Ha teljesül az egyenlıtlenség, nem biztos, hogy a kód felbontható. 7. példa. Az 1. példa esetében ugyanazt az értéket kapjuk mint az 5. példában, pedig az elıbbi kód nem felbontható. Tétel. (Kraft-tétel) Legyen B és C véges ábécé, B ={b1, b2, … , bk}, |C|=c, és legyenek {h1, h2, … , hk} pozitív egész számok, melyekre teljesül a McMillan-egyenlıtlenség. k

∑

1

i =1 c

hi

≤1

Ekkor létezik olyan prefix kódot meghatározó f: B → C* kódolás, amelyre az f(b1), f(b2 ), …, f(bk) kódszavak hossza éppen {h1, h2, … , hk}. 2007. má május 31.


13

Következmény. A McMillan- és a Kraft-tételbıl következik, hogy ha f: B → C* felbontható kódot határoz meg, akkor létezik olyan prefix kód, hogy a két kódban a B elemeihez tartozó kódszavak hossza megegyezik. Ez a tény megnöveli a prefix kód jelentıségét.

2007. má május 31.


14

Optimális kód

2007. má május 31.


15

Átlagos szóhossz, a kód költsége A kódolandó üzenetben a különbözı jelek más és más gyakorisággal fordulhatnak elı. Ha törekszünk arra, hogy az üzenethez tartozó kód minél rövidebb legyen, akkor a gyakrabban elıforduló jelekhez rövidebb kódot, míg a ritkábban elıfordulókhoz a hosszabb kódokat érdemes rendelnünk.

2007. má május 31.


16

Tegyük fel a továbbiakban, hogy az F jelforrás a B ={b1, b2, … , bk} ábécé jeleit egymástól függetlenül véletlenszerően bocsátja ki. Jelölje pi annak a valószínőségét, hogy az F által kibocsátott jel bi . Feltesszük, hogy k pi >0 (i=1..k), és p =1

∑

i

i =1

Elég hosszú, pl. M számú jelbıl álló jelsorozatban a benne elıforduló bi-k száma közelítıleg piM. k Az M számú jelbıl álló sorozat kódjának átlagos hossza: M ∑ pi ⋅ hi i =1

k

Ha csökken a ∑ pi ⋅ hi értéke, akkor csökken a közlések átlagos 1 hossza is. Ezi =indokolja a következı definíciót.

2007. má május 31.


17

Definíció. Tegyük fel, hogy az f: B → C* felbontható kódolást alkalmazzuk, és az f(b1), f(b2 ), …, f(bk) kódszavak hossza {h1, h2, … , hk}, |C|=c, K=f(B)⊆C*. Jelölje pi annak a valószínőségét, hogy az F forrás által kibocsátott jel bi . A K kód F forrás melletti átlagos szóhossza, vagy költsége: k

H ( K ) = ∑ pi hi i =1

2007. má május 31.


18

Optimális kódok Definíció. Legyen B és C véges ábécé. Rögzítsük a F jelforrást, vagyis a B ábécé betőihez tartozó pi valószínőségeket. Tekintsük az f: B → C* függvények által meghatározott felbontható kódokat. Ezek közül a legkisebb átlagos szóhosszúságú (költségő) kódot optimális kódnak nevezzük. Korábbi megjegyzésünk alapján elég adott esetben az optimális prefix kódot keresnünk.

2007. má május 31.


19

Entrópia Definíció. Az alábbi E(F) értéket az F forrás entrópiájának nevezzük. (A log 2-es alapú logaritmust jelöl) k

k 1 E ( F ) = ∑ pi log = −∑ pi log pi pi i =1 i =1

2007. má május 31.


20

k 1 H ( K ) = ∑ pi hi E ( F ) = ∑ pi log = −∑ pi log pi pi i =1 i =1 i =1 Tétel. (Shannon tétele zajmentes csatornákra) Egy F jelforráshoz tartozó tetszıleges K felbontható kódra teljesül a következı k

k

E(F ) H (K ) ≥ log c

Prefix kóddal ez a korlát jól megközelíthetı. Tétel. E(F ) Létezik olyan f: B→C* prefix kód, amelyre H ( K ) ≤ +1 log c Bizonyítás. A bizonyítást például az un. Shannon-Fano kód segítségével lehet elvégezni. 2007. má május 31.


21

Bináris Huffman-kód Legyen B ={b1, b2, … , bk}, a valószínőségek pedig sorban (nagyság szerint csökkenıen rendezve): {0,20; 0,20; 0,19; 0,12; 0,11; 0,09; 0,09} b1 b2 b3 b4 b5 b6 b7 b1 b2 b3 b4 b5 b6 b7

0,20 0,20 0,19 0,12 0,11 0,09 0,09 10 11 000 010 011 0010 0011

2007. má május 31.

0,20 0,20 0,19 0,18 0,12 0,11 10 11 000 001 010 011

0,23 0,20 0,20 0,19 0,18

01 10 11 000 001

0,37 0,23 0,20 0,20

00 01 10 11


0,40 0,37 0,23

1 00 01

0,60 0,40

0 1

22

A Huffmann-kód elınye: Optimális kódot állít elı. A Huffmann-kód hátrányai: Ismernünk kell kódolásnál a teljes szöveget. Kétszer kell végigmennünk az adatokon. Elıször meghatározzuk a forrásbetők relatív gyakoriságát, ami megegyezik a valószínőségekkel, majd ennek felhasználásával elvégezzük a tényleges kódolást. Adaptív Huffmann-kódolás. Csak egyszer megy végig az adatokon. Az optimalitás rovására idıt takarítunk meg. Egy forrásbetőt az elızı forrásbetők elıfordulásai alapján kódolunk, s ezzel együtt lépésenként változik maga a kód is. Az aktuális forrásbető kódolását egy, az elızıleg feldolgozott forrásbetőkre optimális kóddal hajtjuk végre. 2007. má május 31.


23

Adaptív kódok. Menet közben győjtünk információt a forrásszimbólumokról, az aktuális szimbólumot az ezt megelızı szimbólumok alapján kódoljuk. Lempel-Ziv kódok: LZ77 algoritmus. 1977-ben publikálták. LZ78 algoritmus. LZW kód: Terry Welch az LZ78-at módosította. Az Unix COMPRESS parancsa és a GIF (Graphics Interchange Format) képtömörítı is az LZW algoritmust használja.

2007. má május 31.


24

Irodalomjegyzék

Demetrovics, Denev, Pavlov: A számítástudomány matematikai alapjai Tankönyvkiadó, Budapest, 1985 Gyırfi László-Gyıri Sándor-Vajda István: Információ és kódelmélet Typotex Kiadó, 2000 Jablonszkij, Lupanov: Diszkrét matematika a számítástudományban Mőszaki Könyvkiadó, 1980

2007. má május 31.


25

dolás, felbontható kód Prefix kód Blokk kódk Kódfa

Recommend Documents