Theorem codio ffynhonnell Shannon

Mewn damcaniaeth gwybodaeth, mae theorem codio ffynhonnell Shannon (neu theorem codio di-sŵn) yn dangos fod cyfyngiadau ar gywasgiad data dichonadwy. Mae'n un o ddehongliadau entropi gwybodaeth.

Theorem codio ffynhonnell

Yn anffurfiol, mae'r theorem hon (Shannon, 1948) yn dweud fod:

"Gellir cywasgu N hapnewidyn annibynnol unfath, pob un gydag entropi H(X), i fwy nag NH(X) did gyda cholled gwybodaeth yn ddibwys o annhebygol; ond os y'i cywesgir yn lai nag NH(X) did, mae mwy neu lai yn sicr y bydd colled gwybodaeth." (MacKay 2003).

Ar gyfel codau symbol

Gadewch i X fod yn hapnewidyn sy'n cymryd gwerthoedd mewn gwyddor feidraidd ${\displaystyle \Sigma _{1}}$, a gadewch i f fod yn god dehongladwy o ${\displaystyle \Sigma _{1}}$ i ${\displaystyle \Sigma _{2}}$ a ellid ei ddehongli, lle mae ${\displaystyle |\Sigma _{2}^{*}|=a}$. Dynodwn hyd y geiriau yn f(X) gydag S.

Os mai f yw'r gorau posib, yn y ffaith fod ganddo'r hyd geiriau disgwyliedig lleiaf posib ar gyfer X, yna mae

${\displaystyle {\frac {H(X)}{\log _{2}a}}\leq \mathbb {E} S<{\frac {H(X)}{\log _{2}a}}+1}$

(Shannon 1948)