Hírközléselmélet II.
A tantárgy angol neve: Infocommunication Theory II.
Adatlap utolsó módosítása: 2023. február 27.
Doktori képzés
Doktori Választható tárgy
Név:
Beosztás:
Tanszék, Int.:
Dr. Pap László
egyetemi tanár
Hálózati Rendszerek és Szolgáltatások Tanszék
Valószinűségszámítás és híradástechnikai rendszerekkel kapcsolatos alapismeretek.
-
A tárgy második félévének a célja, hogy a híradástechnikai érdeklődésű poszgraduális hallgatók megismerkedjenek a modern hírközlő információelméleti alapjaival és a gyakorlati rendszerekre jellemző elméleti korlátokkal.
1. hétA diszkrét valószínűségelmélet rövid áttekintése (eseménytér, esemény, valószínűségi mérték, elemi esemény, valószínűségi változó, eloszlásfüggvény, vektor valószínűségi változó, együttes eloszlásfüggvény, peremeloszlás, függetlenség, várható érték, feltételes eloszlás, feltételes várható érték, konvergencia valószínűségben). A Hartley féle információmérték. A Shannon féle információmérték (valószínűségi változó "bizonytalanságának" a mértéke, entrópiája)
2. hétA Shannon féle információmértékkel kapcsolatos néhány összefüggés és egyenlőtlenség (információelméleti egyenlőtlenség, a diszkrét valószínűségi változó bizonytalansági (entrópia) függvényének a felső korlátja). Feltételes entrópia (a feltételes entrópiára korlátai). Egy vektor valószínűségi változó entrópiája (lánc szabály). Példa a fent ismertetett fogalmakra. A kölcsönös információ (a kölcsönös információ korlátai).
3. hétA digitális információk forráskódolása. A prefix-free kódok fogalma és jelentősége a forráskódolásban. A Kraft-egyenlőtlenség, a prefix-free kódok létezésének a feltétele. Gyökeres fa valószínűségekkel (az úthossz segédtétel, a terminális csomópontok E[W] átlagos távolsága a gyökértől). Entrópia (bizonytalansági) függvények a gyökeres fán (terminális entrópia, elágazási entrópia és azok kapcsolata).
4. hétA prefix-free kódok átlagos hosszának alsó korlátja (egy K értékkészletű U valószínűségi változó D-szintű prefix-free kódjának átlagos szóhossza).A Shannon-Fano prefix-free kód, a kódszó hosszak megválasztása, kapcsolat a Kraft-egyenlőtlenséggel. Egy K értékkészletű valószínűségi változó kódolási tétele. Huffman-kódok, változó hosszúságú optimális prefix-free kódok.
5. hétBináris Huffman-kód, a bináris Huffman-kód algoritmusa. Nem bináris Huffman-kód, a nem bináris Huffman-kód algoritmusa. Diszkrét memóriamentes források változó hosszúságú kódolása, kódolás üzenetblokkból változó hosszúságú kódba, a diszkrét memóriamentes források kódolási tétele. Diszkrét memóriamentes források blokk kódolása, Tunstall-kódok (Tunstall-segédtétel), optimális blokk kódok (a Tunstall-algoritmus). A Tunstall kódok aszimptotikus tulajdonságai.
6. hétBlokkból blokkba kódolás, a tipikus sorozatok fogalma. A Csebisev-egyenlőtlenség és a nagy számok gyenge törvénye (a szórásnégyzet három tulajdonsága, a nagy számok gyenge törvénye, a nagy számok gyenge törvényének egy speciális alkalmazása). A tipikus sorozatok tulajdonságai (első, második és harmadik jellemző tulajdonság).
7. hétA diszkrét memóriamentes források blokkból blokkba kódolása, a blokkból blokkba kódolás tétele. Csatornakódolás zajos csatornában. A kauzális, memóriamentes, időinvariáns, visszacsatolás mentes csatorna fogalma. Példák a diszkrét memóriamentes csatornára (bináris szimmetrikus csatorna, bináris törléses csatorna). A diszkrét memóriamentes és visszacsatolás mentes csatorna tétele.
8. hétA csatorna kapacitása, a diszkrét memóriamentes csatorna C kapacitásának a definíciója. A csatorna kapacitásának a kiszámítása néhány speciális csatorna esetén (egyenletes diszperzív csatorna, egyenletesen fókuszáló csatorna, erősen szimmetrikus csatorna). A "szimmetria" általános definíciója. Az adatfeldolgozási segédtétel és a Fano-segédtétel.
9. hétA zajos diszkrét memóriamentes csatorna kódolási tételének a megfordítása. A zajos diszkrét memóriamentes csatorna kódolási tétele. A blokk kódolás elve és korlátai. Kódolási és dekódolási kritériumok (lehetséges optimális dekódolási szabályok, maximum a posteriori, maximum likelihood és minimax szabály). A blokk hibavalószínűség minimalizálása, az optimális dekódolási szabály megfogalmazása.
10. hétA Bhattacharyya-korlát két kódszó esetén (a döntési tartomány fogalma). A bináris Bhattacharyya-korlát. Példa a bináris esetre. A Bhattacharyya-korlát kettőnél több kódszó esetén, uniós korlát. A Bhattacharyya-korlát általánosítása, a Gallager-korlát. A Gallager- és a Bhattacharyya-korlát összehasonlítása.
11. hétA véletlen kódolás fogalma, véletlen kódolás két kódszó esetén, a csatornák határsebessége (cut-off rate). A blokk hibavalószínűség felső korlátja két kódszó esetén. Példák a bináris esetre. Véletlen kódolás több kódszó esetén, a határsebesség értelmezése. Véletlen blokk kódok uniós korlátja. A véletlen kódolási tétel Gallager-féle verziója. Véletlen blokk kódok Gallager-korlátja.
12. hétA véletlen kódolási korlátok értelmezése (az egyenletesen jó kód létezése). Fa és trellis kódolás (egy elvi példa vizsgálata, fa típusú kódok, trellis kódok, a kódoló kényszertávolsága). A Viterbi féle maximum likelihood dekódolási algoritmus (egy elvi példa analízise). A Viterbi dekódolás metrikájának a megválasztása általános esetben. A Viterbi féle dekódolási algoritmus lépései.
13. hétA Viterbi-dekóder hibavizsgálata, a kitérők számának meghatározása. A Viterbi-dekóder hibavizsgálata, a bithibaarány felső korlátjának meghatározása. Véletlen kódolás trellis kód esetén, a Viterbi-exponens számítása. A bithibavalószínűség felső korlátjának a számítása (trellis kódoló és Viterbi-dekódolás esetén, a Gallager-korlát alkalmazása).
14. hétA trellis kódok Viterbi féle véletlen kódolási korlátja. Véletlen kódolás esetén az átlagos bithibaarány Viterbi féle felső korlátját (diszkrét memóriamentes csatorna, trellis vagy konvolúciós kódoló, maximum likelihood dekódoló). A trellis kódok Viterbi féle kódolási tétele. A Gallager-függvény és a Gallager-exponens tulajdonságainak részletes elemzése. Az átlagokra vonatkozó egyenlőtlenség igazolása. Az E[Wj] felső korlátjának származtatása trellis kódoló és véletlen kódolás esetén.
Előadás, az előadáson megoldott szemléltető feladatokkal
a. A szorgalmi időszakban: 1 ZH
b. A vizsgaidőszakban: Szóbeli vizsga választott tételekkel.
c. Elővizsga: megbeszélés szerint
ZH pótlása a vizsgaidőszak első hetében.
Vizsga pótlása a vizsgaidőszakban.
Lindsey-Simon: Communication System Engineering
A.J.Viterbi - J.K. Omura: Priciples of Digital
Communication and Coding
Pap László: Hírközléselmélet I. https://www.mcl.hu/education/vihid038/