Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics

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ét
A 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ét
A 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ét
A 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ét
A 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ét
Biná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ét
Blokkbó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ét
A 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ét
A 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ét
A 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ét
A 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ét
A 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ét
A 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ét
A 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ét
A 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.

a. A szorgalmi időszakban: 1 ZH

b. A vizsgaidőszakban: Szóbeli vizsga választott tételekkel.

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/