4.4. 4.4. Shannon-Fano kód

Bár Shannon nevét általában az információmennyiség meghatározásával kapcsolatban szokták legtöbbször emlegetni, információelméleti munkáiban a kódolás elvi kérdéseit is tisztázta, sőt eljárást is kidolgozott az optimális kódolásra. A shannoni tétel kimondja, hogy valamely meghatározott kódábécé esetén egy és csakis egy olyan ábrázolási mód van, amely adott mennyiségű információt a lehető legkevesebb jellel fejez ki. Ez az optimális kód. Ha az üzenetet több jellel fejezzük ki, redundánssá válik. Ez történik például, amikor egy olyan ábécét kell bináris kódra átírnunk, amelyben a betűk száma nem kettőnek egész számú hatványa. Egy betűs ábécét csak bináris számjeggyel írhatunk át. A látszólagos információmennyiség tehát bit, holott egy betűhöz csak bit tényleges információmennyiség tartozik. A parazita információk arányát csökkenthetjük, ha a betűket nem egyenként, hanem blokkonként, kettesével, hármasával stb. kódoljuk. Ekkor azonban a kód egyre bonyolultabbá válik és nő a kódolás költsége.

4.27. Tétel. Létezik prefix kód, hogy

Bizonyítás. A bizonyítás konstruktív és az elkészített kódot Shannon-Fano kódnak nevezzük.

Most pedig nézzük, hogy az algoritmus milyen lépésekből áll.

Legyen

tetszőleges forráseloszlás.

Ekkor a lépések a következők:

  1. Rendezzük a valószínűségeket csökkenő sorrendbe:

    1. Képezzük az értékeket a következőképpen:

    2. Ábrázoljuk ezen értékeket a intervallumon és osszuk fel a intervallumot egyenlő részre ( a kódábécé elemeinek száma).

    3. Azokat az intervallumokat, melyek egynél több értéket tartalmaznak osszuk fel újra egészen addig míg mindegyik más intervallumba nem kerül.

    4. A kódszó az hosszúságú intervallumok megfelelő sorszámából áll, amelyekben benne van, ahol a kódszó hossza, illetve az osztáslépések száma.

A konstrukcióból látszik, hogy prefix kódot kapunk.

Megmutatjuk, hogy

ahol

Az értéket tartalmazó utolsó előtti, hosszúságú intervallumban legalább még egy pont van, azaz az és az közül legalább az egyik. Mivel a így mindenképpen igaz, hogy

Képezzük mindkét oldal logaritmusát, majd negatívját és összegezzük minden -re, akkor kapjuk, hogy

Ezzel az állítást bizonyítottuk.

4.2. ábra - Példa a Shannon-Fano kódolásra (intervallumfelosztás)

Példa a Shannon-Fano kódolásra (intervallumfelosztás)

4.3. ábra - Példa a Shannon-Fano kódolásra (kódfa)

Példa a Shannon-Fano kódolásra (kódfa)

4.4. ábra - Példa a Shannon-Fano kódolásra (kód)

Példa a Shannon-Fano kódolásra (kód)

4.5. ábra - Példa a Shannon-Fano kódolásra (intervallumfelosztás)

Példa a Shannon-Fano kódolásra (intervallumfelosztás)

4.6. ábra - Példa a Shannon-Fano kódolásra (kód)

Példa a Shannon-Fano kódolásra (kód)