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).

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

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

kde ${\displaystyle f_{\rm {vz}}}$ je frekvence vzorkování, ${\displaystyle 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.

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

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

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

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

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

${\displaystyle \delta (x)=0\Leftrightarrow x\neq 0,}$

${\displaystyle \delta (x)=?\Leftrightarrow x=0,}$

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

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

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

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

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

${\displaystyle 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á

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

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

platí, že

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

Fourierův obraz vzorkované funkce ${\displaystyle f\cdot s}$ je pak konvoluce Fourierova obrazu ${\displaystyle F}$ funkce ${\displaystyle f}$ s polem delta funkcí ${\displaystyle S}$. To znamená, že ${\displaystyle D(u,v)}$ je nekonečné pole Fourierových obrazů funkce ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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.

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

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