Az Informatika Elméleti Alapjai dr. Kutor László
Minimális redundanciájú kódok Statisztika alapú tömörítő algoritmusok http://mobil.nik.bmf.hu/tantargyak/iea.html Felhasználónév: iea 2008. ősz
BMF NIK
Jelszó: IEA07 dr. Kutor László
IEA 8/1
A kódolás folyamata és fogalmai U Forrás
A Kódoló
A* Csatorna
U* Dekódoló
Vevő
A kódolás céljai: U-nak A-ba történő leképezése minimális redundancia létrehozásával
„Forrás kódolás”
U-nak A-ba történő leképezése növelt redundancia létrehozásával
„Csatorna kódolás”
U-nak A-ba történő leképezése a kódrendszer titkos megváltoztatásával
„Titkosító kódolás”
2008. ősz
BMF NIK
dr. Kutor László
IEA 8/2
A kódolással szemben támasztott
követelmények 1. Egyértelmű dekódolhatóság: nem redukálható = „irreducibilis” kód ! Feltétele: hogy egyik kódszó sem lehet a másik kódszó része 2. Forráskódolásnál a minimális szóhossz 3.
Csatornakódolásnál a hibák észlelése és javítása
4. Titkosító kódolásnál a „megfelelően” nehéz dekódolhatóság 2008. ősz
BMF NIK
dr. Kutor László
Morse kód (redukálható) J .--- S ... A .B -... K -.- T C -.-. L .-.. U ..D -.. M -- V ...N -. W .-E . X -..F ..-. O --Y -.-G --. P .--. Z --.. H .... Q --.- 0 ----R .-. 1 .---I .. 2008. ősz
BMF NIK
IEA 8/3
2 ..--3 ...-4 ....5 ..... 6 -.... 7 --... 8 ---.. 9 ----. Fullstop .-.-.Comma --..-Query ..--..
dr. Kutor László
IEA 8/4
Statisztikára épülő adattömörítés Forrás
Kódoló
Csatorna
Statisztika
Dekódoló
Vevő
Statisztika
Előnye: biztosítja a minimális átlagos szóhosszat (minimum redundanciát) Hátránya: a statisztikát is továbbítani kell 2008. ősz
BMF NIK
dr. Kutor László
Minimum redundanciájú kódok 1. Shannon-Fano kód Claude Shannon Bell Lab.
IEA 8/5
~1950
R.M. Fano M.I.T.
Az üzenetek (szimbólumok) előfordulási gyakoriságának (valószínűségének) ismeretében létrehozható olyan kód amely ♦ egyértelműen dekódolható ♦ változó (szó) hosszúságú ♦ a kódszavak hossza a kódolt szimbólumok előfordulási valószínűségétől függ
2008. ősz
Gyakori szimbólum
rövid kód
Ritka szimbólum
hosszú kód BMF NIK
dr. Kutor László
IEA 8/6
A Shannon-Fano algoritmus 1. Az üzenetekben előforduló szimbólumok előfordulási 2. 3. 4. 5.
gyakoriságának meghatározása A szimbólumok gyakoriság szerinti csökkenő sorrendbe rendezése A lista két részre osztása úgy, hogy a két részben lévő szimbólumok összesített gyakorisága (közel) egyenlő legyen A lista felső részéhez „0”-át, az alsó részéhez „1”-et rendelünk (vagy fordítva) A 3.-ik és 4.-ik eljárást addig ismételjük, amíg a kettéosztott lista mindkét részében csak 1-1 szimbólum található
2008. ősz
BMF NIK
dr. Kutor László
IEA 8/7
Példa a Shannon – Fano algoritmusra Szimbólumok
A B C D E A (15) (22) 0 B (7) C (6) D (6) (17) 1 E (5) 2008. ősz
Előfordulások száma
15 7 6 6 5
A (15) B (7) C (6) D (6) E (5)
Információ tartalom
1.38 2.48 2.7 2.7 2.96
0 1 0 D (6) 0 1 E (5) 1
BMF NIK
dr. Kutor László
Bitek száma
20.68 17.35 16.2 16.2 14.82
A = 00 B = 01 C = 10 D = 110 E = 111 ASCII 39* 8 = 312 Shannon-Fano 89? IEA 8/8
Minimum redundanciájú kódok 2. Huffmann kód D.A. Huffmann (1952) 1. Az üzenetekben előforduló szimbólumok előfordulási
gyakoriságának meghatározása 2. A szimbólumok gyakoriság szerinti csökkenő sorrendbe rendezése 3. A két legkevésbé gyakori szimbólumot összevonjuk és beírjuk a szimbólumok közé a gyakorisági sorba 4. A 3.-ik pontot addig ismételjük, amíg 2 elemű lesz a lista. Ekkor az egyik elemhez „0”-át a másikhoz „1”-et rendelünk. 5. Visszalépünk az előző összevont szimbólumhoz, és az előbbivel azonos sorrendben a két szimbólumhoz „0”-át és „1”-etrendelünk, mindaddig, míg vissza nem jutunk az egyes szimbólumokhoz 2008. ősz
BMF NIK
dr. Kutor László
IEA 8/9
Példa a Huffmann algoritmusra Szimbólumok
A B C D E
Előfordulások száma
15 7 6 6 5
Információ tartalom
1.38 2.48 2.7 2.7 2.96
Bitek száma
20.68 17.35 16.2 16.2 14.82
A (15) A (15) BCDE(24) A (15) 1 A= 0 DE (11) BC(13) 1 A (15) B (7) = 111 0 B C = 110 C (6) B (7) 1 DE (11) 0 D = 101 D (6) 1 C (6) 0 E = 100 E (5) 0 ASCII 39* 8 = 312 Huffmann
2008. ősz
BMF NIK
dr. Kutor László
87?
IEA 8/10
1/2 példa a „Huffmann”algoritmusra: Dekódolás Dekódolandó üzenet: 1101001010111101000110…
Kódtábla:
C
A= 0 B = 111 C = 110 D = 101 E = 100 Visszafejtett kód:
E D A B D AAAC
CEDABDAAAC
2008. ősz
BMF NIK
dr. Kutor László
IEA 8/11
A kódolási példa fa szerkezete BCDE 1 0
DE
D
1
1
D 2008. ősz
0
0
„gyökér”
A= 0 B = 111 C = 110 D = 101 E = 100
BC
E B 1
E
A
B
0
C
C BMF NIK
A „levelek” dr. Kutor László
IEA 8/12
2. példa a „Huffmann” algoritmusra: Kódolandó szöveg: ” Semmi nem olyan egyszerű,
e(6) (6) m(5) mint amilyennek látszik” n(5) 1. A karakterek gyakoriságának meghatározása i(4) l(3) „= 2, S=1, e=6, m=5, i=4, _=6, n=5, y(3) o=1, l=3, y=3, a=2, g=1, s=2, z=2, ”(2) r=1, ű=1, ,=1, t=2, k=2 ∑=50 a(2) 2. Gyakoriság szerinti rendezés s(2) z(2) 3. A kevésbé gyakori karaktereket kettesével t(2) összevonjuk és beírjuk a gyakorisági sorba, k(2) o(1) ami két elemű lesz a lista r(1) 4. A lista elemekhez rendre 0-át és 1-et rendelve ű(1) g(1) létrehozzuk, majd kiolvassuk a kódot ,(1) 2008. ősz
BMF NIK
dr. Kutor László
IEA 8/13
FAX gépek adattömörítése CCITT szerint G1, G2, G3 (G4?) G1 G2 G3
A4-es oldal továbbításához szükséges idő: 6 perc 3 perc 40-60 s
felbontás (vonal/mm) 3.85 3.85 3.85(7.7)
átvitel vivő
analóg (1300.1700 Hz) analóg (2100) CCITT (2400 bit/s)
A 215 mm hosszú sor 1728 pontból áll Egydimenziós kódolás
Kétdimenziós kódolás (15 – 20 mp) 2008. ősz
BMF NIK
dr. Kutor László
IEA 8/14
Minimum redundanciájú kódok 3. (1952) Aritmetikai kód US Pat. #: 4,905,297 Az egész üzenetet egy számmal helyettesítjük
Például: BILL GATES
2008. ősz
BMF NIK
0.2572167752
dr. Kutor László
IEA 8/15
Az aritmetikai kódolás algoritmusa 1. Az üzenetekben előforduló szimbólumok előfordulási
gyakoriságának meghatározása 2. Minden szimbólumhoz hozzárendelünk egy 0 – 1 közé eső számtartományt. A számtartomány nagysága arányos a szimbólum relatív gyakoriságával 3. A teljes karaktersorozatot egy számmá alakítjuk. Az átalakítást úgy végezzük, hogy az üzenetben egymás után következő karakterek által kijelölt számtartományt lépésről lépésre beszűkítjük, míg végül egy számhoz jutunk
2008. ősz
BMF NIK
dr. Kutor László
IEA 8/16
1. példa az aritmetikai kódolásra Kódolandó szöveg: ALMA Szimbólumok Előfordulások Relatív száma gyakoriság
A L M
2 1 1
2/4 1/4 1/4
A
Számtartomány
0 <=tA< 0.5 0.5 <=tL< 0.75 0.75<=tM< 1
L
M
0 <= tA < 0. 5 0.25 <= tAL < 0.375 0…. <= tALM < 0….. 0…. <= tALMA< 0….. 2008. ősz
BMF NIK
dr. Kutor László
IEA 8/17
2. példa az aritmetikai kódolásra Kódolandó szöveg: Szimbólumok
-_ A B E G I L S T
2008. ősz
„Data Compresson book Mark Nelson 1991 Számtartomány
BILL_GATES
Előfordulások Relatív száma gyakoriság
1 1 1 1 1 1 2 1 1
1/10 1/10 1/10 1/10 1/10 1/10 2/10 1/10 1/10
BMF NIK
0.00 0.10 0.20 0.30 0.40 0.50 0.60 0.80 0.90
dr. Kutor László
<= t_< <= tA< <= tB< <= tE< <= tG< <= tI< <= tL< <= tS< <= tT<
0.10 0.20 0.30 0.40 0.50 0.60 0.80 0.90 1.00
IEA 8/18
2/2. példa az aritmetikai kódolásra Kódolt szöveg:
BILL_GATES
Számtartomány
„Kódtáblázat” 0.00 0.10 0.20 0.30 0.40 0.50 0.60 0.80 0.90
<= __ < <= A < <= B < <= E < <= G < <= I < <= L < <= S < <= T <
0.10 0.20 0.30 0.40 0.50 0.60 0.80 0.90 1.00
2008. ősz
0.2572167752
B I L L G A T E S
BMF NIK
alsó érték
felső érték
0.2 0.25 0.256 0.2572 0.25720 0.257216 0.2572164 0.257216772 0.257216772 0.2572167752 dr. Kutor László
0.3 0.26 0.258 0.2576 0.25724 0.2572220 0.2572168 0.257216776 0.257216776 0.2572167756 IEA 8/19
2/3. példa az aritmetikai kódolásra: Dekódolás 1. 0.2572167752
Kiinduló kód:
0.2572167752
„Kódtáblázat” 0.00 0.10 0.20 0.30 0.40 0.50 0.60 0.80 0.90 2008. ősz
<= __ < <= A < <= B < <= E < <= G < <= I < <= L < <= S < <= T <
0.10 0.20 0.30 0.40 0.50 0.60 0.80 0.90 1.00 BMF NIK
B 0.2572167752 a 0.2 (a tartomány alsó értéke) b 0.0572167752 /0.1=0.57216… 2. 0.572167752 I tartomány a 0.5 b 0.072167752 /0.1=0.7216…. 3. 0.72167752 L a 0.6 b 0.12167752/0.2= 0.6083876 4. 0.6083876 L a 0.6 b 0.0083876/0.2=0.041938 5. 0.041938 _ a 0.0 b 0.041938/0.1=0.41938 6. 0.41938 G …...... dr. Kutor László
IEA 8/20
