Kódování (přenos informace)

Mějme informační zdroj ${\displaystyle \scriptstyle ({\mathcal {X}},p)}$. Pod pojmem kódování tohoto zdroje chápeme přiřazování určitých řetězců znaků konkrétním zprávám ${\displaystyle \scriptstyle x\in {\mathcal {X}}}$, jež vycházejí ze zdroje. Znaky v řetězcích přitom tvoří jistou abecedu ${\displaystyle \scriptstyle {\mathcal {D}}}$. Pokud mají všechny řetězce stejnou délku ${\displaystyle \scriptstyle n}$, pak za obor hodnot takového přiřazení stačí brát množinu ${\displaystyle \scriptstyle {\mathcal {D}}^{n}}$, pokud se ale délka řetězců pro různé zprávy může lišit, bude obor hodnot takového přiřazení podmnožina množiny

${\displaystyle {\mathcal {D}}^{\ast }=\bigcup _{n=1}^{\infty }{\mathcal {D}}^{n}.}$

Matematicky pak můžeme kód zdroje ${\displaystyle \scriptstyle ({\mathcal {X}},p)}$ definovat jako zobrazení

${\displaystyle C:{\mathcal {X}}\to {\mathcal {D}}^{\ast },}$

kde ${\displaystyle \scriptstyle {\mathcal {D}}}$ je jistá abeceda znaků. Obvykle se bere ${\displaystyle \scriptstyle {\mathcal {D}}=\{0,\ldots ,D-1\}}$ pro nějaké ${\displaystyle \scriptstyle D\geq 2}$. Mluvíme pak o kódu ${\displaystyle \scriptstyle {\boldsymbol {D}}}$-znakovém. Jestliže ${\displaystyle \scriptstyle D=2,3,\ldots }$, nazýváme daný kód binární, ternární, ...

Kód ${\displaystyle \scriptstyle C:{\mathcal {X}}\to {\mathcal {D}}^{\ast }}$ se nazývá nesingulární, jestliže je ${\displaystyle \scriptstyle C}$ prosté zobrazení.

Pod označením rozšířením kódu ${\displaystyle \scriptstyle C:{\mathcal {X}}\to {\mathcal {D}}^{\ast }}$ chápeme zobrazení

${\displaystyle C^{\ast }:{\mathcal {X}}^{\ast }\to {\mathcal {D}}^{\ast },\quad {\text{kde}}\quad {\mathcal {X}}^{\ast }=\bigcup _{i=1}^{\infty }{\mathcal {X}}^{i},}$

jež kóduje zdroj ${\displaystyle \scriptstyle ({\mathcal {X}}^{\ast },p^{\ast })}$ s libovolným rozdělením pravděpodobnosti ${\displaystyle \scriptstyle p^{\ast }}$.

Kód nazýváme jednoznačně dekódovatelný, jestliže jeho rozšíření je nesingulární kód.

Mějme zprávu ${\displaystyle \scriptstyle x\in {\mathcal {X}}}$, resp ${\displaystyle \scriptstyle x\in {\mathcal {X}}^{\ast }}$ a kód ${\displaystyle \scriptstyle C}$, resp. ${\displaystyle \scriptstyle C^{\ast }}$. Řetězce ${\displaystyle \scriptstyle C(x)}$, resp. ${\displaystyle \scriptstyle C^{\ast }(x)}$ (tj. obrazy zprávy ${\displaystyle \scriptstyle x}$ při zobrazení ${\displaystyle \scriptstyle C}$, resp. ${\displaystyle \scriptstyle C^{\ast }}$) se pak nazývají kódová slova.