Shannons satser för en allmän källa

Shannons teorem för en allmän källa beskriver möjligheterna att koda en allmän källa med hjälp av separerbara koder. Med andra ord beskrivs de maximalt uppnåbara förlustfria kodningsmöjligheterna.

Direktsats

Såsom den tillämpas på bokstav för bokstav-kodning kan den direkta satsen formuleras enligt följande:

Det finns ett prefix , det vill säga en separerbar kod , för vilken den genomsnittliga meddelandelängden inte skiljer sig från den normaliserade entropin med mer än en :

E_{U}w\left(U\right)<{\frac {H\left(U\right)}{\log _{2}D))+1

var:

$U$ - någon källa till meddelanden, såväl som uppsättningen av alla dess meddelanden ${\displaystyle u_{1},u_{2},...,u_{K))$
${\displaystyle w_{1},w_{2},...,w_{K))$ är längden på källmeddelanden efter kodning
$E_{U}w\left(U\right)$ — genomsnittlig meddelandelängd
$H\left(U\right)$ är källentropin _
$D$ — antalet bokstäver i kodningsalfabetet (till exempel 2 för det binära alfabetet, 33 för kodning med stora ryska bokstäver, etc.)

Som ett bevis på satsen undersöks egenskaperna hos Shannon-Fano-koden . Denna kod uppfyller villkoren för satsen och den har de angivna egenskaperna.

Omvänd sats

Den omvända satsen begränsar det maximala kompressionsförhållandet som kan uppnås med förlustfri kodning. Såsom den tillämpas på kodning bokstav för bokstav, beskriver den en begränsning av den genomsnittliga kodordslängden för varje separerbar kod.

För varje separerbar kod med längder är den genomsnittliga meddelandelängden större än eller lika med källentropin , normaliserat till den binära logaritmen för antalet bokstäver i kodarens alfabet: ${\displaystyle w_{1},w_{2},...,w_{K))$ $U$ $D$

{\frac {H\left(U\right)}{\log _{2}D}}\leq E_{U}w\left(U\right)

Litteratur

Gabidulin E. M. , Pilipchuk N. I. §3.4 Shannons satser för källan // Lectures on information theory - MIPT , 2007. - P. 49-52. — 214 sid. — ISBN 978-5-7417-0197-3