Изворни код странице Никвист-Шенонова теорема одабирања

[[Датотека:Bandlimited.svg|мини|250x250пиксел| Пример величине Фуријеове трансформације опсежне функције]]
У области [[Digitalna obrada signala|дигиталне обраде сигнала]], '''теорема узорковања''' је основни мост између [[Сигнал непрекидног времена|сигнала континуалног времена]]  и сигнала дискретног времена . Она успоставља довољан услов за брзину узорковања која дозвољава дискретни низ ''узорака'' да прикупи све информације из непрекидног сигнала коначне [[Ширина фреквентног опсега|пропусности]] .

Строго говорећи, теорема се односи само на класу [[Функција (математика)|математичких функција]] која имају [[Фуријеова трансформација|Фуријеову трансформацију]] која је нула изван коначног подручја фреквенција. Интуитивно очекујемо да када неко смањи континуирану функцију на дискретну секвенцу и [[Интерполација|интерполира]] натраг на континуирану функцију, верност резултата зависи од густине (или брзине узорка ) оригиналних узорака. Теорема узорковања уводи концепт брзине узорковања која је довољна за савршену верност класе функција које су ограничене на дату ширину појаса, тако да се у процесу узорковања не губе стварне информације. Изражава довољну брзину узорка у смислу пропусности за класу функција. Теорема такође води формули за савршено реконструкцију оригиналне функције непрекидног времена из узорака.

Савршена реконструкција и даље може бити могућа када критериј брзине узорковања није задовољен, под условом да су позната друга ограничења сигнала. (Види {{Section link||Sampling of non-baseband signals}} и [[Компримовано очитавање|компресованог сензора]]. ) У неким случајевима (када критеријум брзине узорка није задовољен), коришћење додатних ограничења омогућава приближне реконструкције. Верност ових реконструкција може се проверити и квантификовати користећи [[Боцхнерова теорема|Бохнерову теорему]] .<ref>{{Cite arXiv|arxiv=1506.03300|class=physics.med-ph|first=Jonathan|last=Nemirovsky|first2=Efrat|last2=Shimron|title=Utilizing Bochners Theorem for Constrained Evaluation of Missing Fourier Data|date=2015}}</ref>

Име ''Никвист-Шенонова теорема узорковања'' одаје почаст [[Хари Никвист|Харију Никвисту]] и [[Klod Elvud Šenon|Клоду Шенон-у,]] иако је чињеница да ју је [[Владимир Котелников]] већ открио 1933. године. Теорему су такође самостално открили Е.Т. Витакер и други. Тако је позната и по именима ''Никвист-Шенон–Котелникова'', ''Витакер-Шенон-Котелникова'', ''Витакер-Никвист-Котелников-Шенонов-'' а и ''кардинална теорема интерполације'' .

== Увод ==
Узорковање је процес претварања сигнала (на пример, функције непрекидног времена и / или простора) у низ вредности (функција дискретног времена и / или простора). [[Klod Elvud Šenon|Шенонова]] верзија теореме гласи:<ref name="Shannon49"/> <blockquote> Ако функција <math>x(t)</math> не садржи фреквенције веће од ''B''  [[херц]]а, он се у потпуности одређује тако што ће дати своје ординате у низу размакнутих тачака <math>1/(2B)</math> секунди размака. </blockquote> Довољна стопа узорковања је, дакле, већа од <math>2B</math> узорака у секунди. Еквивалентно за дату стопу узорка <math>f_s</math>, загарантована је савршена реконструкција <math>B < f_s/2</math> .

Када је ограничење појаве превисоко (или не постоји ограничење појаса), реконструкција показује несавршености познате као [[Алијасинг|алиасинг]] . Модерне изјаве теореме понекад пажљиво изричу да то <math>x(t)</math> не сме садржавати никакве [[Синусоида|синусоидне]] компоненте  фреквенције тачно ''B'', или да ''B'' мора бити строго мања од ½ узорка. Праг <math>2B</math> зове се '''Никвистова стопа''' и атрибут је континуираног уноса <math>x(t)</math> који ће бити узоркован. Брзина узорковања мора бити већа од Никвистове стопе да би узорци били довољни да представљају ''x''(''t''). Праг ''f''<sub>с</sub> / 2 назива се '''Никвистовом фреквенцијом''' и атрибут је опреме за [[Analogno digitalni konvertor|узорковање]] . Све значајне фреквенцијске компоненте правилно узоркованих ''x''(''t'') постоје испод Никвистове фреквенције. Услов описан овим неједнакостима назива се '''Никвистов критеријум''', или понекад ''Раабеов услов'' . Теорема је такође применљива на функције других домена, попут ''простора,'' у случају дигитализоване слике. Једина промена, у случају других домена, су мере које се примењују на ''t'', ''f''<sub>с</sub> и ''B.'' 
[[Датотека:Sinc_function_(normalized).svg|десно|мини|250x250пиксел| Нормализована [[Синц функција|sinc функција]] : {{Nowrap|sin(π''x'') / (π''x'')}} ... приказује централни врх на {{Nowrap|1=''x'' = 0}}, а нула-прелаз на осталим целобројним вредностима ''к'' . ]]
{{Nowrap|1=symbol ''T'' = 1/''f''<sub>s</sub>}} се обично користи да представља интервал између узорака и назива се '''период узорка''' или '''интервал узорковања''' . И узорци функције ''x''(''t'') су обично означени са {{Nowrap|1=''x''[''n''] = ''x''(''nT'')}} (алтернативно "''x<sub>n</sub>''" у старијој литератури за обраду сигнала), за све целобројне вредности ''н'' . Математички идеалан начин интерполирања низа укључује употребу синк функција . Сваки узорак у низу замењује се синк функцијом, центрираном на временску осу на оригиналном месту узорка, ''nТ'', са амплитудом синк функције прилагођеном вредности вредности узорка, x[n]. Након тога, синk функције се сумирају у континуирану функцију. Математички еквивалентна метода је обједињавање једне синк функције са низом [[Dirakova delta funkcija|Диракових делта]] импулса, пондерисаних вредностима узорка. Ниједна метода није бројчано практична. Уместо тога, користи се нека врста апроксимације синк функција, ограничене дужине. Савршенства која се могу приписати апроксимацији позната су као ''грешка интерполације'' .

Практични дигитално-аналогни претварачи не производе ни умањене ни закаснеле синк функције, нити идеалне [[Dirakova delta funkcija|Диракове импулсе]] . Уместо тога, они производе комадно-константни низ умањених и одложених правоуглих импулса ( задржавање нула реда ), обично праћен филтром ниске пропусности (који се назива ''"'' филтер за осликавање ''слике"'' ) за уклањање лажних високофреквентних реплика (слика) оригиналног основног сигнала.

== Алиасинг ==
[[Датотека:CPT-sound-nyquist-thereom-1.5percycle.svg|мини|250x250пиксел| Узорци два синусна таласа могу бити идентични када је барем један од њих фреквенције веће од половине узорка.]]
Када <math>x(t)</math> је функција са [[Фуријеова трансформација|Фуријеовом трансформацијом]] <math>X(f)</math> ''':'''

: <math>X(f)\ \triangleq\ \int_{-\infty}^{\infty} x(t) \ e^{- i 2 \pi f t} \ {\rm d}t,</math>

Пуасонова формула сумирања указује да су узорци, <math>x(nT)</math>, од <math>x(t)</math> довољни за прављење периодичног сажетка <math>X(f)</math> . Резултат је ''':''' {{Equation box 1|border|indent=|title=|equation={{NumBlk|:|<math>X_s(f)\ \triangleq \sum_{k=-\infty}^{\infty} X\left(f - k f_s\right) = \sum_{n=-\infty}^{\infty} T\cdot x(nT)\ e^{-i 2\pi n T f},</math>|{{EquationRef|Eq.1}}}}|cellpadding=6|border colour=#0073CF|background colour=#F5FFFA}}
[[Датотека:AliasedSpectrum.png|десно|мини|400x400пиксел| ''X''(''f'') (у горњем делу слике означено плавом бојом) и ''X''<sub>А</sub> (''f'') (у доњем делу слике означено плавом бојом) су континуиране Фуријеове трансформације двеју различитих функција, <math>x(t)</math> и <math>x_A(t)</math> (није приказано). Када се функције узоркују брзином <math>f_s</math>, слике (означено зеленом бојом) се додају оригиналним трансформацијама (означено плавом бојом) када се испитују дискретне временске Фуријеове трансформације (ДТФТ) секвенци. У овом хипотетичком примеру, ДТФТ-ови су идентични, што значи да су узорковани сингали идентични, иако оригиналне континуиране претходно узорковане функције нису. Ако су то звучни сигнали, <math>x(t)</math> и <math>x_A(t)</math> можда не звучи исто. Али њихови узорци (узети брзином ''f''<sub>с</sub> ) су идентични и довели би до идентичних репродукованих звукова; према томе, ''x<sub>А</sub>'' (t) је алиас од ''x(t)'' при овој брзини узорка.]]
која је периодична функција и њен еквивалентни приказ као [[Фуријеов ред|Фуријеов низ]], чији су коефицијенти <math>T\cdot x(nT).</math> Ова функција је позната и као дискретна Фуријеова трансформација (ДТФТ) узорка секвенце.

Као што је приказано, копије <math>X(f)</math> померане су умношцима од <math>f_s</math> и комбиновано додавањем. За ограничени опсег &nbsp;<math>(X(f) = 0, \text{ for all } |f| \ge B)</math>&nbsp; и довољно велика <math>f_s,</math> могуће је да копије остану различите. Али ако Никвистов критеријум није задовољен, суседне копије се преклапају и уопште није могуће разабрати недвосмислено. <math>X(f).</math> Било која компонента фреквенције горе <math>f_s/2</math> не разликује се од компоненте ниже фреквенције, зване ''алиас'', повезане са једном од копија. У таквим случајевима уобичајене технике интерполације производе алиас, а не оригиналну компоненту. Када је стопа узорковања унапред одређена другим разматрањима (као што је индустријски стандард), <math>x(t)</math> обично се филтрира тако да се његове високе фреквенције смање на прихватљиве нивое пре него што се узоркује. Потребна врста филтера је филтер са ниским пропустом и у овим се условима назива анти-алиасинг филтер . 
[[Датотека:ReconstructFilter.svg|десно|мини|400x400пиксел| Спектар, ''X<sub>с</sub>''(''f''), правилно узоркованог опсега сигнала (oзначено плавом бојом) и суседних ДТФТ слика (oзначено зеленом бојом) које се не преклапају. ''Филтрирани'' нископропусни филтер ''од опеке'', ''H''(''f''), уклања слике, оставља изворни спектар, ''X''(''f'') и враћа оригинални сигнал из својих узорака.]]

== Деривација као посебан случај сажимања Пуасона ==
Када се не преклапају копије (познате и као "слике") <math>X(f)</math>,  <math>k=0</math> значење израза 1 може се повратити производом ''':'''

: <math>X(f) = H(f) \cdot X_s(f),</math>&nbsp; &nbsp; &nbsp; where''':'''

: <math>H(f)\ \triangleq\ \begin{cases}1 & |f| < B \\ 0 & |f| > f_s - B. \end{cases}</math>

Теорема узорковања је доказана од када <math>X(f)</math> јединствено одређује <math>x(t).</math>

Све што преостаје је да се добије формула за реконструкцију. <math>H(f)</math> не морају бити тачно дефинисане у региону <math>[B,\ f_s-B]</math> јер <math>X_s(f)</math> је нула у том региону. Међутим, најгори је случај када <math>B=f_s/2,</math> Никвистова фреквенција. Функција која је довољна за то и за све мање тешке случајеве је ''':'''

: <math>H(f) = \mathrm{rect} \left(\frac{f}{f_s} \right) = \begin{cases}1 & |f| < \frac{f_s}{2} \\ 0 & |f| > \frac{f_s}{2}, \end{cases}</math>

где је rect (•) правоугаона функција..Стога ''':'''

: <math>X(f) = \mathrm{rect} \left(\frac{f}{f_s} \right) \cdot X_s(f)</math> 
::: <math> = \mathrm{rect}(Tf)\cdot \sum_{n=-\infty}^{\infty} T\cdot x(nT)\ e^{-i 2\pi n T f}</math>&nbsp;&nbsp;&nbsp; (од &nbsp; Eq.1, горе). 
::: <math> = \sum_{n=-\infty}^{\infty} x(nT)\cdot \underbrace{T\cdot \mathrm{rect} (Tf) \cdot e^{-i 2\pi n T f}}_{
\mathcal{F}\left \{
 \mathrm{sinc} \left( \frac{t - nT}{T} \right)
\right \}}.</math>&nbsp;&nbsp;&nbsp; {{Efn-ua|The sinc function follows from rows 202 and 102 of the [[Table of Fourier transforms|transform tables]]}}

Инверзна трансформација обе стране производи Витакер-Шенонову интерполацијску формулу ''':''' {{Equation box 1|border|indent=|title=|equation=:<math>x(t) = \sum_{n=-\infty}^{\infty} x(nT)\cdot \mathrm{sinc} \left( \frac{t - nT}{T}\right),</math>|cellpadding=6|border colour=#0073CF|background colour=#F5FFFA}} који показује како узорци, <math>x(nT),</math> може се комбиновати за реконструкцију <math>x(t).</math>

* Вредности ''f<sub>s</sub>'' (мање вредности ''Т'' ), које се називају ''претерано узорковање'', немају уицаја на исход реконструкције и имају предност да остављају простор за ''прелазни појас'' у којем је ''H''(''f'') слободан узети интермедијарне вредности. Прекомандирање, које узрокује алиас, генерално није реверзибилна операција. 
* Теоретски, интерполациона формула се може применити као филтер ниског протока, чији је импулсни одзив синк (''t''/''Т'') и чији је улаз <math>\textstyle\sum_{n=-\infty}^{\infty} x(nT)\cdot \delta(t - nT),</math> што је функција [[Поворка импулса|Диракова поворка импулса]] модулирана узорцима сигнала. Практични дигитално-аналогни претварачи (ДАЦ) имплементирају апроксимацију као што је нулти ред . У том случају, претерано узорковање може умањити погрешку апроксимације.

== Шенонов оригинални доказ ==
Пуасон показује да Фуријеов низ у изразу 1 производи периодично <math>X(f)</math>, без обзира на <math>f_s</math> и <math>B</math> . Шенон, међутим, изводи само коефицијенте серије за случај <math>f_s=2B</math> . Готово цитирајући Шенонов оригинални рад ''':'''

: Дозволити <math>X(\omega)</math> да буде спектар <math>x(t).</math>&nbsp; Онда

:: <math>x(t) = {1 \over 2\pi} \int_{-\infty}^{\infty} X(\omega) e^{i\omega t}\;{\rm d}\omega = {1 \over 2\pi} \int_{-2\pi B}^{2\pi B} X(\omega) e^{i\omega t}\;{\rm d}\omega,</math>

: јер <math>X(\omega)</math> претпоставља се да је нула изван опсега <math>\left|\tfrac{\omega}{2\pi}\right| < B.</math>&nbsp; Ако дозволимо <math>t = \tfrac{n}{2B},</math> где <math>n</math> било који позитивни или негативни цели број, добијамо: 
{{NumBlk|::|<math>x \left(\tfrac{n}{2B} \right) = {1 \over 2\pi} \int_{-2\pi B}^{2\pi B} X(\omega) e^{i\omega {n \over {2B}}}\;{\rm d}\omega.</math>|{{EquationRef|Израз 2}}}}

: На левој страни су вредности од <math>x(t)</math> на тачкама узорковања. Интеграл с десне стране биће препознат се као суштински {{Efn|Multiplying both sides of {{EquationNote|Eq.2}} by <math>T = 1/2B</math> produces, on the left, the scaled sample values <math>(T\cdot x(nT))</math> in Poisson's formula ({{EquationNote|Eq.1}}), and, on the right, the actual formula for Fourier expansion coefficients.|group=proof}} ''n-''ти коефицијент у ширењу функције Фоуриер-ове серије <math>X(\omega),</math> узимајући интервал <math>-B</math> до <math>B</math> као темељни период. То значи да су вредности узорака <math>x(n/2B)</math> одредити Фуријеове коефицијенте у серијском ширењу <math>X(\omega).</math>&nbsp; Тако они одређују <math>X(\omega),</math> Од <math>X(\omega)</math> је нула за фреквенције веће од ''B'', а за ниже фреквенције <math>X(\omega)</math> одређује се ако су утврђени његови Фуријеови коефицијенти. Али <math>X(\omega)</math> одређује оригиналну функцију <math>x(t)</math> у потпуности, јер се функција одређује ако је познат њен спектар. Због тога оригинални узорци одређују функцију <math>x(t)</math> у потпуности.

Шенонов доказ теореме је довршен у том тренутку, али он наставља да разматра реконструкцију преко синк функција, што сада називамо Витакер-Шеноновом интерполационом формулом као што је горе дискутовано. Он не изводи или не доказује својства синк функције, али то би било {{Weasel inline|date=јун 2017}}   познато инжењерима који су у то време читали његова дела, будући да је однос Фуријеовог пара између rect (правоугла функција) и синк био добро познат.

: Дозволити <math>x_n</math> да буде ''н-''ти  узорак. Тада функција <math>x(t)</math> представља:

:: <math>x(t) = \sum_{n=-\infty}^{\infty}x_n{\sin \pi(2Bt-n) \over \pi(2Bt-n)}.</math>

Као и у другом доказу, претпоставља се постојање Фуријеове трансформације изворног сигнала, тако да доказ не каже да ли се теорема узорковања проширује на ограничене стационарне случајне процесе.

=== Напомене ===
{{Notelist|group=proof}}

== Примена на мултиваријабилне сигнале и слике ==
[[Датотека:Moire_pattern_of_bricks_small.jpg|десно|мини|250x250пиксел| Подврста слике која приказује [[Моире паттерн|Моаров узорак]] ]]
[[Датотека:Moire_pattern_of_bricks.jpg|десно|мини|249x249пиксел| Правилно узоркована слика]]
Теорема узорковања се обично формулише за функције једне променљиве. Сходно томе, теорема је директно применљива на сигнале који зависе од времена и нормално је формулисана у том контексту. Међутим, теорема узорковања може се директно проширити на функције произвољно многих променљивих. Слике у сивим тоновима, на пример, често су представљене као дводимензионални низови (или матрице) стварних бројева који представљају релативни интензитет [[п]]а (елемената слике) смештених на пресецима места узорака реда и ступаца. Као резултат, слике захтевају две независне променљиве или индексе да јединствено одреде сваки пиксел - један за ред и један за колону.

Слике у боји се обично састоје од композиције од три одвојене слике у сивим тоновима, од којих једна представља сваку од три основне боје - црвену, зелену и плаву или ''[https://sr.wikipedia.org/sr-ec/RGB RGB](Red, Green, Blue)'' укратко. Остали простори у боји који користе 3 вектора за боје укључују HSV(''Hue, Saturation, Value)'', CIELAB, XYZ итд. Неки простори боја попут цијан, магента, жута и црна ([https://sr.wikipedia.org/sr-ec/CMYK CMYK]) могу представљати боју у четири димензије. Све ово се третира као функције векторске вредности преко дводимензионалног узоркованог домена.

Слично као једнодимензионални дискретни временски сигнали, слике такође могу да трпе алиасинг ако је резолуција узорковања или густина пиксела неадекватна. На пример, дигитална фотографија пругасте кошуље са високим фреквенцијама (другим речима, удаљеност између пруга је мала) може проузроковати отуђење кошуље када је узоркује сензор слике камере. Алиасинг се појављује као моаров узорак . "Решење" већег узорковања у просторном домену у овом случају би било да се приближи кошуљи, користи сензор веће резолуције или оптички замагли слику пре него што је добије са сензором.

Други пример је приказан десно у узорцима од опеке. Горња слика приказује ефекте када није задовољено стање теореме узорковања. Када софтвер поново подешава величину слике (исти поступак који ствара сличицу приказану на доњој слици), она, у ствари, прво покрене слику кроз филтер ниских пропусница, а затим изврши пример слике како би се добила мања слика која не показује [[Моире паттерн|моарову текстуру]] . Горња слика је оно што се догађа када слика није приказана у узорку без филтрирања са малим пролазима: алиасинг резултата.

Теорема узорковања се примењује на системе камера, где сцена и сочиво представљају аналогни извор просторног сигнала, а сензор слике је уређај за просторно узорковање. Сваку од ових компоненти карактерише [[Функција оптичког преноса|функција преноса модулације]] (МТФ), која представља прецизну резолуцију (просторна ширина појаса) која је доступна у тој компоненти. Ефекти ублажавања или замагљивања могу се појавити када се МТФ сочива и МТФ сензори не поклапају. Када оптичка слика коју узоркује сензорски уређај садржи веће просторне фреквенције од сензора, под узорковањем делује као филтер ниских пролаза да би се смањио или елиминисао отуђење. Када површина места узорковања (величина сензора пиксела) није довољно велика да обезбеди довољно просторног анти-алиасинг-а, у систем камере може бити укључен одвојени филтер за ублажавање (оптички филтер са малим пролазом) како би се смањио МТФ оптичке слике. Уместо да захтева оптички филтер, [[Grafički procesor|јединица]] за [[Grafički procesor|графичку обраду]] фотоапарата на [[Паметни телефон|паметном телефону]] врши [[Digitalna obrada signala|дигиталну обраду сигнала]] ради уклањања алиаса са дигиталним филтером. Дигитални филтери такође примењују оштрење како би појачали контраст објектива на високим просторним фреквенцијама, који иначе брзо пада на дифракцијским границама.

Теорема узорковања се такође примењује на дигиталне слике после обраде, попут узорковања нагоре или надоле. Ефекти отуђивања, замагљивања и оштрења могу се прилагодити дигиталним филтрирањем имплементираним у софтверу, које нужно слиједи теоријске принципе.

== Критична фреквенција ==
Да би илустровали неопходност <math>f_s>2B</math>, размотримо породицу синусоида генерисаних различитим вредностима <math>\theta</math> у овој формули ''':'''

: <math>x(t) = \frac{\cos(2 \pi B t + \theta )}{\cos(\theta )}\ = \ \cos(2 \pi B t) - \sin(2 \pi B t)\tan(\theta ), \quad -\pi/2 < \theta < \pi/2.</math>

[[Датотека:CriticalFrequencyAliasing.svg|десно|мини| Породица синусоида на критичној фреквенцији, а сви имају исте секвенце узорака наизменичних +1 и –1. То јест, сви су они међусобно алиаси, иако њихова учесталост није већа од половине узорка.]]
Са <math>f_s=2B</math> или слично <math>T=1/2B</math>, узорке дају ''':'''

: <math>x(nT) = \cos(\pi n) - \underbrace{\sin(\pi n)}_{0}\tan(\theta ) = (-1)^n</math>

 {{Em|без обзира на вредност <math>\theta</math>}} . Оваква двосмисленост разлог је ''строге'' неједнакости услова теореме узорковања.

== Узорковање сигнала који изван опсега ==
Шенонова расправа гласи:<ref name="Shannon49"/>

: <blockquote> Сличан резултат је тачан ако опсег не почиње на нултој фреквенцији, али на некој вишој вредности, а може се доказати линеарним преводом (физички одговара модулацији са једноструком појавом ) случаја нулте фреквенције. У овом случају, елементарни импулс се добија од sin (''x'') /''x''  једносмерном модулацијом. </blockquote>

То јест, довољан услов без губитка за узорковање [[Сигнал (електротехника)|сигнала]] који немају компоненете сигнала основог појаса јесте да укључује ''ширину'' фреквенцијског интервала ненултом насупрот њене највише компоненте фреквенције. Погледајте ''Узорковање (обрада сигнала)'' за више детаља и примера.

На пример, у узорковању ФМ радио сигнала у фреквенцијском опсегу 100–102 &nbsp; [[Херц|MHz]], није потребно узорковање на 204 MHz (двоструко већа од фреквенције), али је довољно да се узоркује на 4 &nbsp; MHz (двострука ширина интервала фреквенције).

Услов опсега је да је ''X''(''f'') = 0, за све ненегативне ''f'' изван отвореног опсега фреквенција:

:: <math> \left(\frac{N}2f_\mathrm{s},\frac{N+1}2f_\mathrm{s}\right), </math>

за неки негативни цели број ''N.'' Ова формулација укључује нормално стање основног опсега као случај ''N''=0.

Одговарајућа интерполациона функција је импулсни одзив идеалног опружног филтра од зидова од опеке (за разлику од претходно употребљеног идеалног филтера за зид од опеке) са пресецима на горњим и доњим ивицама наведеног опсега, што је разлика између пара нископропусних импулса:

:: <math>(N+1)\,\operatorname{sinc} \left(\frac{(N+1)t}T\right) - N\,\operatorname{sinc}\left( \frac{Nt}T \right).</math>

Могуће су и друге генерализације, на пример на сигнале који заузимају више непрекинутих опсега. Чак ни најопштенији облик теореме узорковања нема доказано истиниту супротност. Односно, не може се закључити да се информације нужно губе само зато што нису испуњени услови теореме узорковања; из инжењерске перспективе, међутим, генерално је сигурно претпоставити да ако теорема узорковања није задовољена, информације ће највероватније бити изгубљене.

== Неуједначено узорковање ==
Теорија узорковања Шенона може се генерализовати за случај неуједначеног узорковања, односно узорака који нису узети једнако распоређени у времену. Шенонова теорија узорковања за неједнако узорковање каже да се сигнал ограничен у опсегу може савршено реконструисати из његових узорака ако просечна брзина узорковања задовољава услов Никвиста.<ref>{{Cite book|title=Nonuniform Sampling, Theory and Practice|last=Marvasti (ed)|first=F.|date=2000|publisher=Kluwer Academic/Plenum Publishers|location=New York}}</ref> Стога, иако једнолико распоређени узорци могу резултирати лакшим алгоритмима обнове, то није неопходан услов за савршену реконструкцију.

Општу теорију за неуобичајене узорке и неуједначене узорке развио је 1967. године Хенри Ландау .<ref>{{Cite journal|last=Landau|first=H. J.|year=1967|title=Necessary density conditions for sampling and interpolation of certain entire functions|journal=Acta Math.|volume=117|issue=1|pages=37–52|doi=10.1007/BF02395039}}</ref> Доказао је да просечна стопа узорковања (једнолична или на неки други начин) мора бити двоструко ''заузета'' ширина опсега сигнала, претпостављајући да је ''[https://sr.wikipedia.org/sr-ec/Априори а приори]'' познато колики део спектра је заузет. Крајем 1990-их, овај рад је делимично проширен како би се покрили сигнали када је била позната количина заузетог опсега, али стварни заузети део спектра није био познат.<ref>see, e.g., {{Cite book|title=Universal minimum-rate sampling and spectrum-blind reconstruction for multiband signals|last=Feng|first=P.|publisher=Ph.D. dissertation, University of Illinois at Urbana-Champaign|year=1997}}</ref> Током 2000-их развијена је комплетна теорија (види одељак Узорковање испод Никвистове стопе под додатним ограничењима у даљем тексту) користећи компримовано откривање . Конкретно, теорија је користећи језик обраде сигнала описана у овом раду за 2009. годину.<ref>{{Cite journal|last=Mishali|first=Moshe|last2=Eldar|first2=Yonina C.|date=март 2009|title=Blind Multiband Signal Reconstruction: Compressed Sensing for Analog Signals|journal=IEEE Trans. Signal Process.|volume=57|issue=3|citeseerx=10.1.1.154.4255}}</ref> Они показују, између осталог, да ако су локације фреквенције непознате, потребно је узорковати најмање два пута никвистичке критеријуме; другим речима, морате да сносите последице бар фактора 2 због незнања локације [[Спектар зрачења|спектра]] . Имајте на уму да минимални захтеви за узорковање не гарантују нужно стабилност .

== Узорковање испод стопе Никвиста под додатним ограничењима ==
Теорема узорковања Никвист-Шенон даје довољан услов за узорковање и реконструкцију сигнала ограниченог опсега. Када се реконструкција врши путем интерполационе формуле Витакер-Шенон, Никвистов критеријум је такође неопходан услов да се избегне ванземаљац, у смислу да ако се узорци узимају спорије од двоструке границе опсега, постоје неки сигнали који неће бити исправно реконструисани. Међутим, ако се у сигналу наметну додатна ограничења, онда Никвистов критеријум више не може бити неопходан услов .

Нетривијални пример искоришћавања додатних претпоставки о сигналу дат је у недавном пољу компресованог сензора, који омогућава потпуну реконструкцију са подНиквистовим узорковањем. То се посебно односи на сигнале који су ретки (или компресибилни) у неком домену. Као пример, компримовано детектовање бави се сигналима који могу имати мали проток преко читавог опсега (рецимо, ''ефективна'' ширина опсега ''ЕB'' ), али локације фреквенција су непознате, пре него све заједно у једном опсегу, тако да се техника пропусног опсега не примењује. Другим речима, фреквенцијски спектар је мали. Традиционално, потребна стопа узорковања је, дакле, 2''B.'' Коришћењем техника компримованог откривања, сигнал се може савршено реконструисати ако се узоркује брзином мањом од 2 ''ЕB'' . Код овог приступа реконструкција се више не даје формулом, већ решењем програма [[Линеарно програмирање|линеарне оптимизације]] .

Други пример где је подНиквистово узорковање оптимално настаје под додатним ограничењем да се узорци квантизирају на оптималан начин, као у комбинованом систему узорковања и оптималној [[Компресија са губитком|компресији губитака]] .<ref>{{Cite journal|last=Kipnis|first=Alon|last2=Goldsmith|first2=Andrea J.|last3=Eldar|first3=Yonina C.|last4=Weissman|first4=Tsachy|date=јануар 2016|title=Distortion rate function of sub-Nyquist sampled Gaussian sources|journal=IEEE Transactions on Information Theory|volume=62|pages=401–429|arxiv=1405.5329|doi=10.1109/tit.2015.2485271}}</ref> Ово подешавање је релевантно у случајевима када треба узети у обзир заједнички ефект узорковања и [[Квантизација (обрада сигнала)|квантизације]] и може пружити доњу границу за минималну грешку реконструкције која се може постићи узорковањем и квантизирањем [[Stohastički proces|случајног сигнала]] . За стационарне Гаусове случајне сигнале, та се доња граница обично постиже брзином подНиквистичког узорковања, што указује да је подНиквистичко узорковање оптимално за овај модел сигнала под оптималном [[Квантизација (обрада сигнала)|квантизацијом]] .<ref>{{Cite journal|last=Kipnis|first=Alon|last2=Eldar|first2=Yonina|last3=Goldsmith|first3=Andrea|date=26. 4. 2018|title=Analog-to-Digital Compression: A New Paradigm for Converting Signals to Bits|journal=IEEE Signal Processing Magazine|volume=35|issue=3|pages=16–39|arxiv=1801.06718|bibcode=2018ISPM...35...16K|doi=10.1109/MSP.2017.2774249}}</ref>

== Историјска позадина ==
Теорема узорковања подразумевала је рад [[Хари Никвист|Харија Никвиста]] из 1928. године,<ref>{{Cite journal|last=Nyquist, Harry|author-link=Harry Nyquist|date=април 1928|title=Certain topics in telegraph transmission theory|journal=Trans. AIEE|volume=47|issue=2|pages=617–644|bibcode=1928TAIEE..47..617N|doi=10.1109/t-aiee.1928.5055024}} [http://www.ieee.org/publications_standards/publications/proceedings/nyquist.pdf Reprint as classic paper in: ''Proc. IEEE'', Vol. 90, No. 2, Feb 2002] {{Webarchive|url=https://web.archive.org/web/20130926031230/http://www.ieee.org/publications_standards/publications/proceedings/nyquist.pdf|date=26. 9. 2013}}</ref> у којем је показао да се до 2''B'' независни импулсни узорци могу послати путем система пропусне ширине ''B''; али није изричито размотрио проблем узорковања и реконструкције континуираних сигнала. Отприлике у исто време, Карл Купфмулер показао је сличан резултат <ref>{{Cite journal|last=Küpfmüller|first=Karl|year=1928|title=Über die Dynamik der selbsttätigen Verstärkungsregler|journal=Elektrische Nachrichtentechnik|language=de|volume=5|issue=11|pages=459–467}} [http://ict.open.ac.uk/classics/2.pdf (English translation 2005)] {{Wayback|url=http://ict.open.ac.uk/classics/2.pdf |date=20190521021624 }}.</ref> и расправљао о синк функцији на импулсни одзив филтера за ограничавање опсега, преко његовог интегрисаног, синусног интеграла корака-одзива; овај филтар за ограничавање и реконструкцију, који је толико битан за теорему узорковања, понекад се назива и ''Купфмулер филтер.''

Теорема узорковања, у основи двоструки резултат Никувиста, доказао је [[Klod Elvud Šenon|Клод Е. Шенон]] .<ref name="Shannon49">{{Cite journal|last=Shannon, Claude E.|author-link=Claude Shannon|date=јануар 1949|title=Communication in the presence of noise|journal=Proceedings of the Institute of Radio Engineers|volume=37|issue=1|pages=10–21|doi=10.1109/jrproc.1949.232969|ref=refShannon49}} [http://www.stanford.edu/class/ee104/shannonpaper.pdf Reprint as classic paper in: ''Proc. IEEE'', Vol. 86, No. 2, (Feb 1998)] {{Webarchive|url=https://web.archive.org/web/20100208112344/http://www.stanford.edu/class/ee104/shannonpaper.pdf|date=8. 2. 2010}}
</ref> В.А Котелников је објавио сличне резултате 1933,<ref>{{Cite journal|last=Kotelnikov, V. A.|author-link=V. A. Kotelnikov|date=1933|title=On the carrying capacity of the ether and wire in telecommunications|journal=Material for the First All-Union Conference on Questions of Communication, Izd. Red. Upr. Svyazi RKKA|language=Russian}} [http://ict.open.ac.uk/classics/1.pdf (English translation, PDF)] {{Wayback|url=http://ict.open.ac.uk/classics/1.pdf |date=20210301042517 }}.</ref> као и математичар Е.Т. Витакер 1915,<ref>{{Cite journal|last=Whittaker, E. T.|author-link=E. T. Whittaker|date=1915|title=On the Functions Which are Represented by the Expansions of the Interpolation Theory|url=https://zenodo.org/record/1428702|journal=Proc. Royal Soc. Edinburgh|volume=35|pages=181–194|doi=10.1017/s0370164600017806}} ("Theorie der Kardinalfunktionen").</ref> Ј.М. Витакер 1935,<ref>{{Cite book|url=https://archive.org/details/in.ernet.dli.2015.219870|title=Interpolatory Function Theory|last=Whittaker, J. M.|date=1935|publisher=Cambridge Univ. Press|location=Cambridge, England|author-link=J. M. Whittaker}}.</ref> и [[Денис Габор|Габор]] 1946 („Теорија комуникације“). Фондација Едуард Рајн је 1999. године Котелникову доделила награду за основно истраживање „за прву теоријски тачну формулацију теореме о узорковању“.

1948. и 1949. године, Клод Е. Шенон, објавио је - 16 година после Владимира Котелникова - два револуционарна чланка у којима је основао теорију информација.<ref name="Shannon49"/><ref>{{Cite journal|last=Shannon, Claude E.|author-link=Claude Shannon|date=јул 1948|title=A Mathematical Theory of Communication|journal=Bell System Technical Journal|volume=27|issue=3|pages=379–423|doi=10.1002/j.1538-7305.1948.tb01338.x|ref=refShannon48}}.</ref><ref>{{Cite journal|last=Shannon, Claude E.|author-link=Claude Shannon|date=октобар 1948|title=A Mathematical Theory of Communication|journal=Bell System Technical Journal|volume=27|issue=4|pages=623–666|doi=10.1002/j.1538-7305.1948.tb00917.x|ref=refShannon48oct}}</ref> Код Шенона теорема узорковања из 1948. формулисана је као „Теорема 13“: Нека ''f'' (''t'') не садржи фреквенције преко В. Затим

: <math>f(t) = \sum_{n=-\infty}^\infty X_n \frac{\sin \pi(2Wt - n)}{\pi(2Wt - n)},</math> где <math>X_n = f\left(\frac n {2W} \right)</math> .

Тек што су објављени ови чланци, теорема позната као „Шенонова теорема узорковања“ постала је заједничко својство међу инжењерима комуникација, мада сам Шенон пише да је то чињеница која је опште позната у комуникацијској уметности. {{Efn-ua|[[#refShannon49|Shannon 1949]], p. 448.}} Ипак, неколико редoва даље, он додаје: „али упркос очигледној важности, изгледа да се он није експлицитно појавио у литератури теорије комуникације“.

=== Остали проналазачи ===
О другим који су самостално открили или имали улоге у развоју теореме узорковања расправљали су, на пример, у неколико историјских чланака, Јери <ref>{{Cite journal|last=Jerri|first=Abdul|author-link=Abdul Jerri|date=новембар 1977|title=The Shannon Sampling Theorem—Its Various Extensions and Applications: A Tutorial Review|journal=Proceedings of the IEEE|volume=65|issue=11|pages=1565–1596|doi=10.1109/proc.1977.10771}} See also {{Cite journal|last=Jerri|first=Abdul|date=април 1979|title=Correction to "The Shannon sampling theorem—Its various extensions and applications: A tutorial review"|journal=Proceedings of the IEEE|volume=67|issue=4|page=695|doi=10.1109/proc.1979.11307}}</ref> и Лук.<ref>{{Cite journal|last=Lüke|first=Hans Dieter|date=април 1999|title=The Origins of the Sampling Theorem|url=http://www.hit.bme.hu/people/papay/edu/Conv/pdf/origins.pdf|journal=IEEE Communications Magazine|volume=37|issue=4|pages=106–108|citeseerx=10.1.1.163.2887|doi=10.1109/35.755459}}</ref> На пример, Лук истиче да је Х. Раабе, асистент Купфмулер-а, теорему доказао у својој докторској дисертацији из 1939. године; термин ''Раабе условио'' је да се повезује са критеријумом за недвосмислену репрезентацију (брзина узорковања већа од двоструке опсега). Мејринг <ref name="EM">{{Cite journal|last=Meijering|first=Erik|date=март 2002|title=A Chronology of Interpolation From Ancient Astronomy to Modern Signal and Image Processing|url=http://bigwww.epfl.ch/publications/meijering0201.pdf|journal=Proc. IEEE|volume=90|issue=3|pages=319–342|doi=10.1109/5.993400}}</ref> у параграфу и пару фуснота помиње неколико других проналазача и имена: <blockquote> Као што је указао Хигинс{{чињеница|date=07. 2024.}}, теорему узорковања заиста треба размотрити у два дела, као што је горе учињено: први наводи чињеницу да је опсежна функција потпуно одређена њеним узорцима, а други описује како реконструисати функцију помоћу њених узорака. Оба дела теореме узорковања дао је у нешто другачијем облику Ј.М. Витакер [350, 351, 353], а пре њега и Огура [241, 242]. Они вероватно нису били свесни чињенице да је први део теореме изјавио Борел још 1897. године.{{чињеница|date=07. 2024.}} <sup>27</sup> Као што смо видели, Борел је у то време користио и оно што је постало познато као кардинална серија. Међутим, чини се да није успоставио везу.{{чињеница|date=07. 2024.}} У каснијим годинама постало је познато да је Котелников руској комуникацијској заједници пре Шенона представио теорему о узорковању.{{чињеница|date=07. 2024.}} У имплицитнијем, вербалном облику, Раабе је то такође описао у немачкој литератури.{{чињеница|date=07. 2024.}} Неколико аутора [33, 205] поменуло је да је Сомеиа{{чињеница|date=07. 2024.}} увео теорему у јапанску литературу паралелно са Шеноном. У енглеској литератури, Вестон{{чињеница|date=07. 2024.}} га је увео независно од Шенона отприлике у исто време. <sup>28</sup>

  <sup>27</sup> Неколико аутора, пратећи Блека{{чињеница|date=07. 2024.}}, тврди да је овај први део теореме узорковања изјавио Коши још раније, у раду{{чињеница|date=07. 2024.}} објављеном 1841. Међутим, рад Кошија не садржи такву изјаву, како је указао Хигинс.{{чињеница|date=07. 2024.}}

 <sup>28</sup> Као последица открића неколико независних увода теореме узорковања, људи су почели да се позивају на теорему укључивањем имена горе поменутих аутора, што је резултирало таквим реченицама као "Витакер-Котелников-Шенонова (ВКШ) теорема узорковања"{{чињеница|date=07. 2024.}} или чак „теорема о узорковању Витакер – Котелников–Раабе– Шенон – Сомеиа“.{{чињеница|date=07. 2024.}} Да бисте избегли забуну, можда је најбоље да се то односи на теорему узорковања, „уместо да се покушава наћи наслов који би правдао свим подносиоцима захтева“.{{чињеница|date=07. 2024.}} </blockquote>

=== Зашто Никвист? ===
Тачно како, када или зашто је [[Хари Никвист]] своје име прикачио уз теорему узорковања остаје нејасно. Израз ''Никвист-Шенонова Теорема'' (тако великим словом) појавио се већ 1959. године у књизи његовог бившег послодавца, [[Белове лабораторије|Бела Лабс]],<ref>{{Cite book|title=Transmission Systems for Communications|last=Members of the Technical Staff of Bell Telephone Lababoratories|publisher=AT&T|year=1959|pages=26–4 (Vol.2)}}</ref> а поново се појавио 1963. године,<ref>{{Cite book|url=https://books.google.com/books?id=jtI-AAAAIAAJ|title=Theory of Linear Physical Systems|last=Guillemin|first=Ernst Adolph|publisher=Wiley|year=1963}}</ref> и није употребљен великим словом 1965. године.<ref>{{Cite book|title=Theory of Signal Detectability: Composite Deferred Decision Theory|last=Roberts|first=Richard A.|last2=Barton|first2=Ben F.|year=1965}}</ref> ''Теоремом Шеноновог узорковања'' названа је већ 1954.<ref>{{Cite book|title=Applied Electronics: A First Course in Electronics, Electron Tubes, and Associated Circuits|last=Gray|first=Truman S.|year=1954}}</ref> али и само ''теорема о узорковању'' у неколико других књига почетком 1950-их.

Године 1958, Блекман и Туки навели су Никвистов чланак из 1928. као референцу за ''теорему узорковања теорије информација'' <ref>{{Cite book|url=http://alcatel-lucent.com/bstj/vol37-1958/articles/bstj37-1-185.pdf|title=The Measurement of Power Spectra : From the Point of View of Communications Engineering|last=Blackman|first=R. B.|last2=Tukey|first2=J. W.|publisher=Dover|year=1958|location=New York|access-date=12. 12. 2019|archive-date=09. 10. 2022|archive-url=https://ghostarchive.org/archive/20221009/http://alcatel-lucent.com/bstj/vol37-1958/articles/bstj37-1-185.pdf|url-status=}}</ref>, иако тај чланак не третира узорковање и реконструкцију непрекидних сигнала као што су то чинили други. Њихов глосар појмова укључује ове уносе:

; Теорема узорковања (теорије информација) 
: Резултат Никвиста да изједначени подаци, са две или више тачака по циклусу највише фреквенције, омогућавају реконструкцију функција ограничених опсега. (Види ''кардинал теорема.'' ) 
; Кардинал теорема (о теорији интерполације) 
: Прецизна изјава услова под којима се вредности дате у двоструко бесконачном скупу једнако распоређених тачака могу интерполирати тако да се добије континуирана функција ограничена у опсегу уз помоћ функције 
:: <math>\frac{\sin (x - x_i)}{x - x_i}.</math>

Тачно оно што називају „Никвистов резултат“ остаје тајанствено.

Када је Шенон изјавио и доказао теорему узорковања у свом чланку из 1949. године, према Мејрингу,<ref name="EM"/> "он се осврнуо на критични интервал узорковања <math>T = \frac 1 {2W}</math> као ''интервал Никвиста који'' одговара појасу ''В'', у знак признања Никвистовог открића суштинске важности овог интервала у вези са телеграфијом ". Ово објашњава Никвистово име на критичном интервалу, али не и на теореми.

Слично томе, Никвист-ово име је Харолд С. Блек приписао ''стопи Никвиста'' 1953. године: {{Quote|"Ако је есенцијални фреквенцијски опсег ограничен на 'B' 'циклусе у секунди, Никвист је дао 2''B као максимални број кодних елемената у секунди који се могу недвосмислено разрешити, претпостављајући да је вршна интерференција мања од пола квантни корак. Ова брзина се генерално назива "сигнализирање на Никвистовој стопи" "", а <math>\frac 1 {2B} </math> назван је "никвистичким интервалом" "." <ref>{{citе књига | прва = Харолд С. | последња = Црна | наслов = Теорија модулације | година = 1953}}</ref> (подебљано за истицање; курзив као у оригиналу)"|sign=|source=}} Према [[Oksfordski engleski rečnik|ОЕД]], ово може бити извор термина ''Никвистове стопе'' . У Блековој употреби није брзина узорковања, већ брзина сигнализације.

== Види још ==

* [[44,100 Hz]], уобичајена брзина која се користи за узорковање звучних фреквенција заснива се на границама људског слуха и теореми узорковања 
* Балиан-Лоу теорема, слична теоријска доња граница за брзине узорковања, али која се односи на временске фреквенције трансформација 
* Чунг–Марксова теорема која одређује услове у којима обнављање сигнала из теореме узорковања може постати лоше постављено 
* Хартлијев закон 
* Никвистов ИСИ критеријум 
* Реконструкција са нула прелаза 
* Задржавање нула

== Напомене ==
{{Notelist-ua}}

== Референце ==
{{Извори}}

== Додатна литература ==

* Higgins, J.R.: ''Five short stories about the cardinal series'', Bulletin of the AMS 12(1985)
* Küpfmüller, Karl, "Utjämningsförlopp inom Telegraf- och Telefontekniken", ("Transients in telegraph and telephone engineering"), Teknisk Tidskrift, бр. 9 стр.&nbsp;153–160 и 10 стр.&nbsp;178–182, 1931. [http://runeberg.org/tektid/1931e/0157.html] [http://runeberg.org/tektid/1931e/0182.html]
* Marks, R.J.(II): ''[http://marksmannet.com/RobertMarks/REPRINTS/1999_IntroductionToShannonSamplingAndInterpolationTheory.pdf Introduction to Shannon Sampling and Interpolation Theory]'', Springer-Verlag, 1991.
* Marks, R.J.(II), Editor: [http://marksmannet.com/RobertMarks/REPRINTS/1993_AdvancedTopicsOnShannon.pdf Advanced Topics in Shannon Sampling and Interpolation Theory], Springer-Verlag, 1993.
* Marks, R.J.(II), ''Handbook of Fourier Analysis and Its Applications,'' Oxford University Press, (2009), поглавља 5-8. [https://books.google.com/books?id=Sp7O4bocjPAC Google books]
* {{Citation|last=Press|first=WH|last2=Teukolsky|first2=SA|last3=Vetterling|first3=WT|last4=Flannery|first4=BP|year=2007|title=Numerical Recipes: The Art of Scientific Computing|edition=3rd|publisher=Cambridge University Press|place=New York|isbn=978-0-521-88068-8|chapter=Section 13.11. Numerical Use of the Sampling Theorem|chapter-url=http://apps.nrbook.com/empanel/index.html#pg=717|accessdate=12. 12. 2019|archive-date=11. 08. 2011|archive-url=https://web.archive.org/web/20110811154417/http://apps.nrbook.com/empanel/index.html#pg=717|url-status=}}
* Unser, Michael: ''[http://bigwww.epfl.ch/publications/unser0001.html Sampling-50 Years after Shannon] {{Wayback|url=http://bigwww.epfl.ch/publications/unser0001.html |date=20060709190155 }}'', Proc. IEEE, vol. 88, бр. 4, стр.&nbsp;569–587, април 2000

== Спољашње везе ==

* [http://www.vias.org/simulations/simusoft_nykvist.html Учење помоћу симулација] Интерактивна симулација ефеката неадекватног узорковања 
* [http://webdemo.inue.uni-stuttgart.de/webdemos/02_lectures/uebertragungstechnik_1/sampling_theorem/ Интерактивна презентација узорковања и реконструкције на веб-демо] Институту за телекомуникације Универзитета у Штутгарту 
* [http://spazioscuola.altervista.org/UndersamplingAR/UndersamplingARnv.htm Подвлачење и његова примена] 
* [https://web.archive.org/web/20060614125302/http://www.lavryengineering.com/documents/Sampling_Theory.pdf Теорија узорковања за дигитални аудио] 
* [http://www.stsip.org/ Часопис посвећен теорији узорковања] 
* [http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=5699377&url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D5699377 Теорема узорковања са сталним импулсом променљиве ширине импулса] 
* {{Cite journal|last=Lüke|first=Hans Dieter|date=април 1999|title=The Origins of the Sampling Theorem|url=http://www.hit.bme.hu/people/papay/edu/Conv/pdf/origins.pdf|journal=IEEE Communications Magazine|volume=37|issue=4|pages=106–108|citeseerx=10.1.1.163.2887|doi=10.1109/35.755459}}

{{нормативна контрола}}

[[Категорија:Телекомуникациона теорија]]
[[Категорија:Теорија информације]]
[[Категорија:Дигитална обрада сигнала]]