4.9. 4.9. Blokkos kódolás, tömörítés, stacionér forrás entrópiája

Blokkos kódolás, azaz

esetén jelölje az együttes eloszlást és az átlagos kódhosszot.

Az egy betűre jutó átlagos kódhossz pedig legyen

Az optimális kódra:

Emlékezetnélküli, stacionárius forrás esetén a függetlenségből

s így

A következőkben egy stacionér forrás entrópiájával foglalkozunk, mert ennek segítségével tudjuk megadni a korlátokat általános esetben.

4.37. Tétel.

Bizonyítás. jelölje egy lehetséges értékét, és legyen

Ekkor és is egy eloszlást ad, ha felveszi azokat az értékeket, amelyre azaz Az I-divergencia tulajdonságai alapján:

azaz

Szorozzuk be a közös nevezővel és bontsuk fel a logaritmust a következőképpen:

Ez minden és esetén teljesül. Végezzül el a összegzést ezekre az egyenlőtlenségekre. Mivel

így igazoltuk az állítást.

4.38. Tétel. Stacionér forrás esetén a

határérték létezik.

Jele:

Bizonyítás. Tudjuk, hogy a forrás stacionér és

ezért

A véletlen vektor függvénye a véletlen vektornak, ezért

Tehát

Ekkor

Tehát a sorozat monoton csökkenő és alulról korlátos, s így létezik a határérték.

4.39. Definíció. A mennyiséget a forrás átlagos entrópiájának nevezzük.

4.40. Megjegyzés. Emlékezetnélküli esetben egyébként

Tekintsünk egy csatornát, amelybe bemennek a kódjeleink (jelölje általánosan ) és kijönnek a jelek (jelölje általánosan ). Kérdés mennyi információmennyiség érkezett meg az elküldöttből, azaz az mennyit mond el a -ről. Ez nyilván a kölcsönös információmennyiség. Ezután a csatornakapacitás (emlékezetnélküli eset):

4.41. Megjegyzés. Mivel az eloszlások korlátos, zárt halmazt alkotnak, így a maximum létezik. Legyen a kapacitás, az átlagos kódhossz. Ha akkor továbbíthatjuk a forrás által szolgáltatott közleményeket.

4.42. Megjegyzés. Zajmentes és emlékezetnélküli csatorná esetén ezért

4.43. Megjegyzés. Bináris szimmetrikus csatorna:

Milyenek a bemeneti illetve kimeneti eloszlások?

4.20. ábra - Bináris szimmetrikus csatorna

Bináris szimmetrikus csatorna

4.21. ábra - Bináris szimmetrikus csatorna kapacitása a valószínűség függvényében

Bináris szimmetrikus csatorna kapacitása a valószínűség függvényében

4.44. Tétel. (A zajmentes hírközlés alaptétele) Ha a entrópiájú stacionárius forrás közleményeit kapacitású zajmentes csatornán továbbítjuk, akkor nincsen olyan egyértelműen dekódolható blokkonkénti kódolási eljárás, melynél

ha viszont akkor létezik olyan blokkhossz, hogy

4.45. Megjegyzés. A McMillan-particionálási tétel szerepe: 1. Felhasználható állandó kódhosszú kód tervezéséhez. 2. Gyakorlati szempont: megfelelő az olyan kódolás is, amelynél annak valószínűsége, hogy egy kódszó dekódolásánál hibát követünk el kisebb, mint egy előre megadott szám. Az ilyen kódolási eljárást megbízhatósággal dekódolhatónak nevezzük.

4.46. Megjegyzés. A jegyzetnek nem feladata kompresszióval, tömörítéssel foglalkozni, de közvetlenül kapcsolódik a blokkos kódoláshoz. Kompresszióról beszélünk, ha a forrásüzenetet úgy kódoljuk, hogy a kódüzenet rövidebb, mint az eredeti. Erre biztosíték ha pl.

mert ekkor az entrópia tulajdonságai alapján

A következő példák mutatják, hogy milyen lehetőségeink vannak független (emlékezetnélküli) és függő esetben.

4.22. ábra - Példa blokkos kódoláshoz 1.

Példa blokkos kódoláshoz 1.

4.23. ábra - Példa blokkos kódoláshoz 2.

Példa blokkos kódoláshoz 2.

4.24. ábra - Példa blokkos kódoláshoz 3.

Példa blokkos kódoláshoz 3.