4.8. 4.8. McMillan-dekódolási tétel

4.33. Tétel. (McMillan-dekódolási tétel) Ha egyértelműen dekódolható, akkor

Bizonyítás. Jelölje azon hosszúságú közleményeknek a számát, melyek kódközleményének a hossza éppen

A bizonyítás lépései (vázlat):

1. A kód egyértelműen dekódolható.

Tehát

2. Teljes indukcióval bizonyítjuk, hogy

3. Ha és adott pozitív számok, akkor az

egyenlőtlenség nem teljesülhet minden természetes számra, így

4.34. Tétel. Egyértelműen dekódolható kód esetén

Bizonyítás. Legyen

Ekkor

4.35. Tétel. Bármely egyértelműen dekódolható kód helyettesíthető egy másik ugyanolyan kódhosszúságú kóddal, amely viszont már prefix kód.

Bizonyítás. A McMillan dekódolási tétel szerint egyértelműen dekódolható kódra teljesül a Kraft-Fano egyenlőtlenség. A Kraft-Fano megfordítása szerint viszont létezik olyan prefix kód amelyiknek pontosan ezek a kódhosszai.

4.36. Megjegyzés. Az előző tétel szerint az optimális egyértelműen dekódolható kódhoz létezik ugyanilyen prefix, így az optimális prefix optimális az egyértelműen dekódolható kódok között is.