Kraft-McMillanova nerovnost

Autor: MIROSLAV

Kraft-McMillanova nerovnost je koncept v teorii informace a kódování, který se používá k určení, zda je daný soubor kódů "prefixový" nebo "bezprefixový" (tj. žádný kód není prefixem jiného). Má zásadní význam pro efektivní a bezchybné kódování a dekódování zpráv. Nechme zatím technické detaily stranou, vysvětlíme si to na jednoduchém příkladu.

Představte si, že jste velitel armády a chcte posílat zprávy svým jednotkám na bojišti. Tyto zprávy mohou být různé - "Postupujte dopředu", "Ustupte", "Zaútočte zleva" atd. Chcete, aby byly tyto zprávy co nejkratší (kvůli rychlosti a efektivitě), ale také aby byly jasné a jednoznačné.

Rozhodnete se tedy použít kód pro každý typ zprávy. Například, "Postupujte dopředu" může být "01", "Ustupte" může být "001", "Zaútočte zleva" může být "0001" atd. Takovýto kódový systém by ale mohl způsobit problémy. Pokud by přišla zpráva "01", nebylo by jasné, jestli je to celá zpráva (tj. "Postupujte dopředu") nebo jestli je to jen začátek delší zprávy (tj. může to být začátek "Ustupte" nebo "Zaútočte zleva"). To by mohlo vést k zmatení jednotek a chybám. Proto potřebujeme systém, kde žádný kód není začátek (prefixem) jiného kódu. Takový systém se nazývá "bezprefixový" kódový systém.

A tady přichází na řadu Kraft-McMillanova nerovnost. Tato nerovnost nám říká, jaké jsou možné délky kódů v bezprefixovém kódovém systému. Představme si, že máme systém s kódy délky 1, 2, 3 atd. Pokud označíme počet kódů délky i jako Ni, pak Kraft-McMillanova nerovnost říká, že:

Σ (1 / 2^Ni) <= 1

Tj. součet hodnot 1 dělených počtem možných kódů každé délky musí být menší nebo rovno 1. Pokud toto platí, pak je náš kódový systém bezprefixový a můžeme ho bezpečně používat ke kódování a dekódování zpráv.

Kraft-McMillanova nerovnost nám tak umožňuje navrhnout efektivní a jednoznačné kódové systémy, které jsou základem moderní komunikace a datového zpracování.

Příklad 1.

odívejme se na konkrétní příklad. Představme si, že máme systém, který používá čtyři různé kódy. Kódy mají následující délky:

Kód A: délka 1
Kód B: délka 2
Kód C: délka 3
Kód D: délka 4

Podle Kraft-McMillanovy nerovnosti musí platit:

(1 / 2^1) + (1 / 2^2) + (1 / 2^3) + (1 / 2^4) <= 1

Když to spočítáme, dostaneme:

0,5 + 0,25 + 0,125 + 0,0625 = 0,9375 <= 1

Protože výsledek je menší než 1, Kraft-McMillanova nerovnost platí a náš kódový systém je bezprefixový. Můžeme ho tedy bezpečně použít k kódování a dekódování zpráv.

V praxi by to znamenalo, že pokud bychom chtěli zakódovat sérii zpráv, například "AABCD", mohli bychom to udělat takto:

A: 0
B: 10
C: 110
D: 1110

Celá zpráva by tedy byla zakódována jako "001011101110", a díky našemu bezprefixovému kódovému systému bychom mohli tuto zprávu jednoznačně dekódovat zpět na "AABCD".

Kraft-McMillanova nerovnost se tedy týká pouze délek kódů v kódovém systému, nikoli samotných kódů. To znamená, že nemusíme znát konkrétní kódy, abychom mohli použít Kraft-McMillanovu nerovnost a určit, zda je daný systém bezprefixový.

Důležité je si uvědomit, že Kraft-McMillanova nerovnost je nezbytnou, ale ne dostatečnou podmínkou pro existence bezprefixového kódování. To znamená, že pokud nerovnost platí, tak MŮŽE EXISTOVAT bezprefixový kód s danými délkami kódů. Pokud nerovnost neplatí, tak takový kód nemůže existovat.

Představme si ještě délky kódů následovně:

Kód A: délka 1
Kód B: délka 1
Kód C: délka 2
Kód D: délka 3
Kód E: délka 2
Kód F: délka 2
Kód G: délka 5

Tady je to docela neintuitivní. Museli bychom si to kombinatoricky určit. To se nám nechce. Takže použijeme naši nerovnost a musí platit:

(1 / 2^1) + (1 / 2^1) + (1 / 2^2) + (1 / 2^3) + (1 / 2^2) + (1 / 2^2) + (1 / 2^5) <= 1

Když to spočítáme, dostaneme:

0,5 + 0,5 + 0,25 + 0,125 + 0,25 + 0,25 + 0,03125 = 1,90625 > 1

Protože výsledek je větší než 1, Kraft-McMillanova nerovnost neplatí a náš kódový systém nemůže být bezprefixový. Pak nemá ani smysl žádné kódy vytvářet, protože vždycky se najde nějaký prefix.

Pojďme to udělat softwarově. Přece nebudeme v roce 2023 nic zdlouhavě počítat.

Pokračování brzy:)