Kraftova nerovnost

Kraftova nerovnost je věta užívaná v teorii kódování. Při kódování n znaky můžeme sestavit prefixový kód s délkami kódovaných slov d₁, d₂, d_r, právě když platí Kraftova nerovnost: n^-d1 + n^-d2 + ... + n^-dr =< 1

Příklad

Uvažujme binární prefixový kód pro kódování cifer 0,1,2,...,9 vhodný pro zprávy, kde se často vyskytují znaky 0,1 a řídce znaky 8,9. Nápad: pro 0 a 1 zvolíme kód délky 2 pro 2-7 zvolíme kód délky 3 pro 8 a 9 zvolíme kód délky 4. Potom by převodní tabulka vypadala takto:

0   00
1   01
2   1xx
3   1xx
4   1xx
5   1xx
6   1xx
7   1xx
8   xxxx
9   xxxx

Kombinace 1xx musí začínat jedničkou, aby byl kód prefixový,ale neposkytuje dost kombinací pro šest čísel.

Kraftova nerovnost to předem říká ve výpočtu:

2 * 2^-2 + 6 * 2^-3 + 2 * 2^-4 = 22/16 > 1

0   00
1   01
2   100
3   1010
4   1011
5   1100
6   1101
7   1110
8   11110
9   11111

a tedy 2 * 2^-2 + 1 * 2^-3 + 5 * 2^-4 + 2 * 2^-5 = (16 + 4 + 10 + 2) / 32 = 1

McMillanova věta: Pro každé jednoznačně dekódovatelné kódování platí Kraftova nerovnost.