Shannon féle kommunikációs modell és egyértelmű dekódolhatóság

Question 1

Shannon-féle kommunikáció modell

Answer 1

A -> kódolás -> csatorna -> dekódolás -> B
Forrás abc: Q véges abc, ahol 2 <= q = |Q|
Csatorna abc: A véges abc, ahol 2 <= m = |A|
Kódolás: fi: Q->A*{lambda}
Kód: C = {fi(e) | e eleme Q-nak}
|C|<= |Q|

Question 2

Kódolás kiterjesztése

Answer 2

fi’: Q* -> C* részhalmaza A* úgy, hogy minden w eleme Q*
fi’(w) = fi(w[1)]fi(w[2)]fi(w[3)]…fi(w[n)]
fi’ - betűnként kódolás, folyamkódolás

Question 3

Példa egyértelmű és nem egyértelmű forráskódolásra

Answer 3

Egyértelmű:
Q = {a, b, c}
A = {0, 1}
fi: {a = 00, b= 110, c = 010}
fi(baccab) = 110 00 010 010 00 110 (szóköz nélkül)

Nem egyértelmű:
Q = {a, b, c}
A = {0, 1}
fi: {a = 01, b= 101, c = 010}
fi(cb) = 010101 (szóköz nélkül)
fi(aaa) = 010101 (szóköz nélkül)
- több bementre ugyanaz a kimenet

Question 4

Mi az egyértelmű dekódolhatóság

Answer 4

Egy C kódot egyértelműen dekódolhatónak nevezünk, ha minden w1, …, wk, u1, .. ul eleme C kódszó-sorozatra abból, hogy w1 * .. * wk = u1 * … * ul következik, hogy k = l és w1 = u1, …, wl = ul

Pl.
𝐴 = {0,1}
𝐶 = {01,101,011}
01101 = 01 ⋅ 101 = 011 ⋅ 01
Nem egyértelmű!

Pl.
𝐴 = {0,1}
𝐶 = {01,001,011}
Egyértelmű!
Szakaszokra bontható: 0-val kezdődik, 1-re végződik

Pl.
𝐴 = {0,1}
𝐶 = {1,01,001}
Egyértelmű!
Szakaszokra bontható: minden szakasz pontosan 1 darab 1-est
tartalmaz.

Question 5

Hogyan dönthető el az egyértelmű dekódolhatóság? Sardinas-Patterson tétel

Answer 5

Sardinas-Patterson tétel:
Ha van egy kód ami részhalmaza A*-nak és
az új kód úgy épül fel hogy van egy kódszó w ami eleme A+-nak és lépésenként haladva létezik egy u ami eleme az új C-nek és v ami eleme Cn-1nek, v = uw vagy u = vw.
Akkor lesz egyértelműen dekódolható ha az új kód végtelenig haladva ha metszük a C kóddal akkor üreshalmazt kapunk.

Question 6

Hogyan dönthető el az egyértelmű dekódolhatóság? McMillan tétel

Answer 6

Van egy C = {w1, .., wq} kód ami részhalmza A*-nak és egyértelműen dekódolható és |A| = m ekkor summa i = 1-q-ig m^(-l(wi) <=1

Question 7

Mi a prefix kód?

Answer 7

Egy C eleme A* akkor prefix kód ha w, u eleme C és v eleme A * ha w=uv akkor w = u
C prefix ha semmilyen kódszó nem kezdőszelete egy másiknak

A prefix egyértelműen dekódolható
ha veszünk két szósorozatot 3 eset van:
- hosszban megegyeznek, ekkor w1=u1 (kezdőszeletek)
- w1 hosszabb mint u1 akkor az u1 a valódi kezdőszelete w1-nek ami nem lehet
- fordítva is ugyanaz a baj

Question 8

Kraft tétel

Answer 8

A véges abc és |A| = m, 1<=li<=lq amire summa i=1-qig m^(-li) <=1 ekkor létezik C{w1, w2, .., wq} eleme A* prefix kód amire l(wi) = li

Question 9

Mi a teljes kód?

Answer 9

C részhalmaza A* teljes kód ha, minden u eleme A* szóhoz léteznek w1, .., wk eleme C kószó és v eleme A* amire u*v = w1 * … * wk

C akkor teljes ha minden u-ra az u hossza nagyobb vagy egyenlő mint a C szavai, az u kódszó vagy van olyan kezdőszelete ami kódszó