Shannon – Fano – Elias kódování - Shannon–Fano–Elias coding

tento článek potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: „Shannon – Fano – Elias kódování“  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Dubna 2016) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v teorie informace, Shannon – Fano – Elias kódování je předchůdcem aritmetické kódování, ve kterých se k určení kódových slov používají pravděpodobnosti.^[1]

Popis algoritmu

Vzhledem k diskrétní náhodná proměnná X z objednal hodnoty, které mají být kódovány, ať ${ displaystyle p (x)}$ být pravděpodobnost pro všechny X v X. Definujte funkci

${ displaystyle { bar {F}} (x) = součet _ {x_ {i}$

Algoritmus:

Pro každého X v X,

Nechat Z být binární expanzí ${ displaystyle { bar {F}} (x)}$.

Vyberte délku kódování X, ${ displaystyle L (x)}$, být celé číslo ${ displaystyle left lceil log _ {2} { frac {1} {p (x)}} right rceil +1}$

Zvolte kódování X, ${ displaystyle kód (x)}$, buďte první ${ displaystyle L (x)}$ nejvýznamnější bity za desetinnou čárkou Z.

Příklad

Nechť X = {A, B, C, D}, s pravděpodobnostmi p = {1/3, 1/4, 1/6, 1/4}.

Pro

${ displaystyle { bar {F}} (A) = { frac {1} {2}} p (A) = { frac {1} {2}} cdot { frac {1} {3} } = 0,1666 ...}$

V binárním formátu Z (A) = 0.0010101010...

L (A) = ${ displaystyle left lceil log _ {2} { frac {1} { frac {1} {3}}} right rceil +1}$ = 3

kód (A) je 001

Pro B

${ displaystyle { bar {F}} (B) = p (A) + { frac {1} {2}} p (B) = { frac {1} {3}} + { frac {1 } {2}} cdot { frac {1} {4}} = 0,4583333 ...}$

V binárním formátu Z (B) = 0.01110101010101...

L (B) = ${ displaystyle left lceil log _ {2} { frac {1} { frac {1} {4}}} right rceil +1}$ = 3

kód (B) je 011

Pro C.

${ displaystyle { bar {F}} (C) = p (A) + p (B) + { frac {1} {2}} p (C) = { frac {1} {3}} + { frac {1} {4}} + { frac {1} {2}} cdot { frac {1} {6}} = 0,66666 ...}$

V binární podobě Z (C) = 0.101010101010...

L (C) = ${ displaystyle left lceil log _ {2} { frac {1} { frac {1} {6}}} right rceil +1}$ = 4

kód (C) je 1010

Pro D.

${ displaystyle { bar {F}} (D) = p (A) + p (B) + p (C) + { frac {1} {2}} p (D) = { frac {1} {3}} + { frac {1} {4}} + { frac {1} {6}} + { frac {1} {2}} cdot { frac {1} {4}} = 0,875}$

V binárním formátu Z (D) = 0.111

L (D) = ${ displaystyle left lceil log _ {2} { frac {1} { frac {1} {4}}} right rceil +1}$ = 3

kód (D) je 111

Analýza algoritmů

Předpona kód

Shannon – Fano – Eliasovo kódování vytváří binární soubor kód předpony, umožňující přímé dekódování.

Nechť bcode (x) je racionální číslo vytvořené přidáním desetinné čárky před binární kód. Například pokud kód (C) = 1010, pak bcode (C) = 0,1010. Pro všechna x, pokud žádné y neexistuje, takové

${ displaystyle bcode (x) leq bcode (y)$

pak všechny kódy tvoří kód předpony.

Porovnáním F s CDF z X může být tato vlastnost graficky demonstrována pro kódování Shannon – Fano – Elias.

Z definice L vyplývá, že

${ displaystyle 2 ^ {- L (x)} leq { frac {1} {2}} p (x)}$

A protože bity po L (y) jsou zkráceny z F (y) za účelem vytvoření kódu (y), vyplývá z toho

${ displaystyle { bar {F}} (y) -bcode (y) leq 2 ^ {- L (y)}}$

bcode (y) tedy nesmí být menší než CDF (x).

Výše uvedený graf tedy ukazuje, že ${ displaystyle bcode (y) -bcode (x)> p (x) geq 2 ^ {- L (x)}}$, proto vlastnost předpony platí.

Délka kódu

Průměrná délka kódu je ${ displaystyle LC (X) = součet _ {x epsilon X} p (x) L (x) = součet _ {x epsilon X} p (x) ( left lceil log _ {2} { frac {1} {p (x)}} vpravo rceil +1)}$.
Takže pro H (X) platí Entropie náhodné proměnné X,

${ displaystyle H (X) +1 leq LC (X)$

Shannon Fano Elias kóduje od 1 do 2 bitů navíc na symbol od X než entropie, takže kód se v praxi nepoužívá.

Reference