Shannonovo kódování - Shannon coding

V oblasti komprese dat, Shannonovo kódování, pojmenoval podle jeho tvůrce, Claude Shannon, je bezztrátová komprese dat technika pro konstrukci a kód předpony na základě sady symbolů a jejich pravděpodobností (odhadovaných nebo měřených). Je neoptimální v tom smyslu, že nedosahuje nejnižší možné očekávané délky kódového slova Huffmanovo kódování ano, a nikdy lepší, ale někdy se rovná Shannon – Fano kódování.

Metoda byla první svého druhu, tato technika byla použita k prokázání Shannonova bezhlučná věta o kódování ve svém článku z roku 1948 „Matematická teorie komunikace“,^[1] a je proto středobodem informačního věku.

Tato metoda kódování dala vzniknout oblasti informační teorie a bez jejího přínosu by svět neměl žádného z mnoha nástupců; například kódování Shannon-Fano, kódování Huffman, nebo aritmetické kódování. Velká část našeho každodenního života je významně ovlivněna digitální data a to by nebylo možné bez Shannonova kódování a jeho pokračujícího vývoje metod předcházejícího kódování.

V Shannonově kódování jsou symboly uspořádány v pořadí od nejpravděpodobnějšího po nejméně pravděpodobné a přiřazená kódová slova jsou převzata první ${ displaystyle l_ {i} = vlevo lceil - log _ {2} p_ {i} vpravo rceil}$ bity z binárních expanzí kumulativních pravděpodobností ${ displaystyle sum limity _ {k = 1} ^ {i-1} p_ {k}.}$ Tady ${ displaystyle lceil x rceil}$ označuje stropní funkce (který zaokrouhlí ${ displaystyle x}$ až na další celočíselnou hodnotu).

Příklad

V následující tabulce je příklad vytvoření kódového schématu pro symboly A₁ na A₆. Hodnota l_i udává počet bitů použitých k reprezentaci symbolu A_i. Poslední sloupec je bitový kód každého symbolu.

i	stri	li	${ displaystyle sum _ {n = 0} ^ {i-1} p_ {n}}$	Předchozí hodnota v binárním formátu	Kódové slovo pro Ai
1	0.36	2	0.0	0.0000	00
2	0.18	3	0.36	0.0101...	010
3	0.18	3	0.54	0.1000...	100
4	0.12	4	0.72	0.1011...	1011
5	0.09	4	0.84	0.1101...	1101
6	0.07	4	0.93	0.1110...	1110

Reference