Nyquistův–Shannonův vzorkovací teorém

Nyquistův–Shannonův vzorkovací teorém (také Shannonův teorém, Nyquistův teorém, Kotělnikovův teorém, Nyquistův–Shannonův teorém, Shannonův–Nyquistův–Kotělnikovův teorém apod.) je fyzikální tvrzení o tom, že „přesná rekonstrukce spojitého, frekvenčně omezeného signálu z jeho vzorků je možná tehdy, pokud byla vzorkovací frekvence vyšší než dvojnásobek nejvyšší harmonické složky vzorkovaného signálu.“

Teorém je pojmenovaný po fyzicích Harrym Nyquistovi (1889–1976), Claudovi Shannonovi (1916–2001) a Vladimiru Kotělnikovovi (1908–2005).

Shannonův teorém a vzorkovací frekvence v praxi

V praxi se tedy vzorkovací frekvence volí dvakrát větší plus ještě malá rezerva, než je maximální požadovaná přenášená frekvence. V telekomunikacích je to např. 8 kHz, neboť je třeba přenášet pouze signály ve standardním telefonním pásmu (od 0,3 do 3,4 kHz – zaokrouhleno směrem nahoru 4 kHz). Například u záznamu na CD je to 44,1 kHz, neboť průměrné zdravé lidské ucho slyší maximálně cca do 20 kHz, a tudíž vzorkovací frekvence 44,1 kHz byla zvolena s určitou rezervou.

Shannonův teorém lze vyjádřit vztahem

$f_{\rm {vz}}>2f_{\max }[s^{-1}],$

kde $f_{\rm {vz}}$ je frekvence vzorkování, $f_{\max }$ je maximální frekvence, která se vyskytuje v signálu.

Při použití nižší vzorkovací frekvence může dojít k tzv. aliasingu – rekonstruovaný signál je výrazně odlišný od původního vzorkovaného signálu.

Shannonův teorém pro vzorkování obrazu

Nechť $f(x,y)$ je spojitá funkce obrazu. Vzorkováním funkce $f(x,y)$ rozumíme reprezentaci této funkce pomocí matice (označme ji $d(x,y)$).

Dále definujme konvoluci dvou funkcí $f(x),g(x)\in L^{1}$ jako

$f(x)*g(x)=\int _{-\infty }^{\infty }f(t)g(x-t)\,{\rm {d}}t.$

Označme $F(u,v)$ jako Fourierovu transformaci funkce $f(x,y)$.

Definujme ještě tzv. delta funkci $\delta$, pro kterou platí:

$\delta (x)=0\Leftrightarrow x\neq 0,$

$\delta (x)=?\Leftrightarrow x=0,$

$\int _{-\infty }^{\infty }\delta (x)\,{\rm {d}}x=1.$

Pak vzorkování s krokem $\Delta x,\Delta y$ je pouze násobení funkce obrazu nekonečným polem delta funkcí $s(x,y)$ definovaným jako

$s(x,y)=\sum _{i=-\infty }^{\infty }\sum _{j=-\infty }^{\infty }\delta \left(x-i\Delta x,y-j\Delta y\right).$

Tedy $d(x,y)=f(x,y)\,\,s(x,y)$.

Platí, že Fourieova transformace funkce $s(x,y)$ má tvar

$S(u,v)={\frac {1}{\Delta x\Delta y}}\sum _{i=-\infty }^{\infty }\sum _{j=-\infty }^{\infty }\delta \left(u-{\frac {i}{\Delta x}},v-{\frac {j}{\Delta y}}\right).$

Díky konvolučnímu teorému, který říká

${\mathcal {F}}\{f(x)\ast g(x)\}={\mathcal {F}}\{f(x)\}\cdot {\mathcal {F}}\{g(x)\}\,=F(u)\cdot G(u),\,$

${\mathcal {F}}\{f(x)\cdot g(x)\}={\mathcal {F}}\{f(x)\}\ast {\mathcal {F}}\{g(x)\}\,=F(u)\ast G(u),\,$

platí, že

$D(u,v)=F(u,v)*S(u,v).\,$

Fourierův obraz vzorkované funkce $f\cdot s$ je pak konvoluce Fourierova obrazu $F$ funkce $f$ s polem delta funkcí $S$. To znamená, že $D(u,v)$ je nekonečné pole Fourierových obrazů funkce $f$. Při vzorkování s menším krokem se tyto obrazy od sebe vzdalují a naopak při vzorkování s delším krokem se k sobě přibližují. Pokud vzorkujeme příliš řídce, mohou se tyto obrazy protnout a vzniká efekt zvaný aliasing. Pokud je funkce frekvenčně omezená, je možné ji navzorkovat beze ztráty informace (tzn. že je možné ze vzorků opět získat funkci $f$ v původní podobě).

Dle Shannonova teorému je pak ideální frekvence pro vzorkování rovna dvojnásobku maximální frekvence vyskytující se ve funkci $f$. Při vzorkování s krokem menším, než je polovina maximální frekvence, vzorkuji zbytečně moc. Při kroku větším než polovina maximální frekvence se Fourierovy obrazy protnou a vzniká aliasing.

Odkazy

Související články

• Aliasing
• Generační ztráta
• Harmonická analýza
• Vzorkovací frekvence
• Vzorkování

Externí odkazy

• Obrázky, zvuky či videa k tématu Shannonův teorém na Wikimedia Commons

Portály: Matematika