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

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

Пример магнитуде Фуријеове трансформације функције са ограниченим опсегом

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

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

Савршена реконструкција може и даље бити могућа када критеријум брзине одабирања није задовољен, под условом да су позната друга ограничења сигнала (погледајте одељак Одабирање сигнала ван основног опсега испод и компресовано очитавање). У неким случајевима (када критеријум брзине одабирања није задовољен), коришћење додатних ограничења омогућава приближне реконструкције. Верност ових реконструкција може се проверити и квантификовати коришћењем Бохнерове теореме.^[1]

Назив Никвист-Шенонова теорема одабирања одаје почаст Харију Никвисту и Клоду Шенону, али теорему је такође претходно открио Е. Т. Витакер (објављено 1915), а Шенон је цитирао Витакеров рад у свом делу. Теорема је стога позната и под називима Витакер-Шенонова теорема одабирања, Витакер-Шенонова, и Витакер-Никвист-Шенонова, а може се називати и кардинална теорема интерполације.

Увод

Одабирање је процес претварања сигнала (на пример, функције континуалног времена или простора) у низ вредности (функцију дискретног времена или простора). Шенонова верзија теореме гласи:^[2]

Theorem—Ако функција ${\displaystyle x(t)}$ не садржи фреквенције веће од B херца, онда се она може у потпуности одредити из њених ордината у низу тачака размакнутих на мање од ${\displaystyle 1/(2B)}$ секунди.

Довољна брзина одабирања је, дакле, било која вредност већа од ${\displaystyle 2B}$ узорака у секунди. Еквивалентно, за дату брзину одабирања ${\displaystyle f_{s}}$, савршена реконструкција је гарантовано могућа за ограничење опсега ${\displaystyle B<f_{s}/2}$. Када је ограничење опсега превисоко (или не постоји), реконструкција показује несавршености познате као алијасинг. Модерне формулације теореме понекад пажљиво експлицитно наводе да ${\displaystyle x(t)}$ не сме садржати синусоидну компоненту на тачно фреквенцији ${\displaystyle B,}$ или да ${\displaystyle B}$ мора бити стриктно мање од половине брзине одабирања. Праг ${\displaystyle 2B}$ се назива Никвистова брзина и представља атрибут континуалног улазног сигнала ${\displaystyle x(t)}$ који се узоркује. Брзина одабирања мора премашити Никвистову брзину да би узорци били довољни за представљање ${\displaystyle x(t).}$ Праг ${\displaystyle f_{s}/2}$ се назива Никвистова фреквенција и атрибут је опреме за одабирање. Све значајне фреквенцијске компоненте правилно узоркованог ${\displaystyle x(t)}$ постоје испод Никвистове фреквенције. Услов описан овим неједнакостима назива се Никвистов критеријум, или понекад Рабеов услов. Теорема је такође применљива на функције других домена, као што је простор, у случају дигитализоване слике. Једина промена, у случају других домена, су јединице мере које се приписују ${\displaystyle t,}$ ${\displaystyle f_{s},}$ и ${\displaystyle B.}$

Нормализована синк-функција: sin(πx) / (πx) ... приказује централни врх на x = 0, и пресеке са нулом на осталим целобројним вредностима x.

Симбол ${\displaystyle T\triangleq 1/f_{s}}$ се уобичајено користи за представљање интервала између суседних узорака и назива се период одабирања или интервал одабирања. Узорци функције ${\displaystyle x(t)}$ се обично означавају са ${\displaystyle x[n]\triangleq T\cdot x(nT)}$^[3] (алтернативно ${\displaystyle x_{n}}$ у старијој литератури о обради сигнала), за све целобројне вредности ${\displaystyle n.}$ Множилац ${\displaystyle T}$ је резултат преласка са континуалног на дискретно време (погледајте Однос са Фуријеовом трансформацијом), и потребан је да би се очувала енергија сигнала како се ${\displaystyle T}$ мења.

Математички идеалан начин за интерполацију низа укључује употребу синк-функција. Сваки узорак у низу замењује се синк-функцијом, центрираном на временској оси на оригиналној локацији узорка ${\displaystyle nT,}$ са амплитудом синк-функције скалираном на вредност узорка, ${\displaystyle x(nT).}$ Након тога, синк-функције се сабирају у континуалну функцију. Математички еквивалентна метода користи Дираков чешаљ и наставља конволуцијом једне синк-функције са низом Диракових делта импулса, пондерисаних вредностима узорака. Ниједна од ових метода није нумерички практична. Уместо тога, користи се неки тип апроксимације синк-функција, коначне дужине. Несавршености које се приписују апроксимацији познате су као грешка интерполације.

Практични дигитално-аналогни претварачи не производе ни скалиране и закаснеле синк-функције, нити идеалне Диракове импулсе. Уместо тога, они производе по деловима константан низ скалираних и закаснелих правоугаоних импулса (задржавање нултог реда), обично праћен нископропусним филтром (који се назива „филтер против сликања”) да би се уклониле лажне високофреквентне реплике (слике) оригиналног сигнала из основног опсега.

Алијасинг

Главни чланак: Алијасинг

Узорци два синусна таласа могу бити идентични када је бар један од њих на фреквенцији изнад половине брзине одабирања.

Када је ${\displaystyle x(t)}$ функција са Фуријеовом трансформацијом ${\displaystyle X(f)}$:

${\displaystyle X(f)\ \triangleq \ \int _{-\infty }^{\infty }x(t)\ e^{-i2\pi ft}\ {\rm {d}}t,}$

тада су узорци ${\displaystyle x[n]}$ од ${\displaystyle x(t)}$ довољни да се креира периодична сумација од ${\displaystyle X(f).}$ (погледајте Однос са Фуријеовом трансформацијом):

${\displaystyle X_{1/T}(f)\ \triangleq \sum _{k=-\infty }^{\infty }X\left(f-k/T\right)=\sum _{n=-\infty }^{\infty }x[n]\ e^{-i2\pi fnT},}$     (Једн. 1)

${\displaystyle X(f)}$ (горња плава) и ${\displaystyle X_{A}(f)}$ (доња плава) су континуалне Фуријеове трансформације две различите функције, ${\displaystyle x(t)}$ и ${\displaystyle x_{A}(t)}$ (нису приказане). Када се функције узоркују брзином ${\displaystyle f_{s}}$, слике (зелене) се додају оригиналним трансформацијама (плаве) када се посматрају дискретне временске Фуријеове трансформације (ДТФТ) низова. У овом хипотетичком примеру, ДТФТ-ови су идентични, што значи да су узорковани низови идентични, иако оригиналне континуалне функције пре узорковања нису. Да су ово аудио сигнали, ${\displaystyle x(t)}$ и ${\displaystyle x_{A}(t)}$ можда не би звучали исто. Али њихови узорци (узети брзином ${\displaystyle f_{s}}$) су идентични и довели би до идентично репродукованих звукова; стога је ${\displaystyle x_{A}(t)}$ алијас од ${\displaystyle x(t)}$ при овој брзини одабирања.

што је периодична функција и њена еквивалентна репрезентација као Фуријеов ред, чији су коефицијенти ${\displaystyle x[n]}$. Ова функција је такође позната као Фуријеова трансформација дискретног времена (ДТФТ) низа узорака.

Као што је приказано, копије ${\displaystyle X(f)}$ се померају за умношке брзине одабирања ${\displaystyle f_{s}=1/T}$ и комбинују сабирањем. За функцију са ограниченим опсегом ${\displaystyle (X(f)=0,{\text{ for all }}|f|\geq B)}$ и довољно великом ${\displaystyle f_{s},}$ могуће је да копије остану међусобно различите. Али ако Никвистов критеријум није задовољен, суседне копије се преклапају, и у општем случају није могуће разазнати недвосмислен ${\displaystyle X(f).}$ Било која фреквенцијска компонента изнад ${\displaystyle f_{s}/2}$ је неразлучива од компоненте ниже фреквенције, назване алијас, повезане са једном од копија. У таквим случајевима, уобичајене технике интерполације производе алијас, а не оригиналну компоненту. Када је брзина одабирања унапред одређена другим разматрањима (као што је индустријски стандард), ${\displaystyle x(t)}$ се обично филтрира да би се његове високе фреквенције смањиле на прихватљиве нивое пре него што се узоркује. Тип филтра који је потребан је нископропусни филтер, а у овој примени се назива филтар за спречавање алијасинга.

Спектар, ${\displaystyle X_{s}(f)}$, правилно узоркованог сигнала са ограниченим опсегом (плаво) и суседне ДТФТ слике (зелено) које се не преклапају. Brick-wall нископропусни филтер, ${\displaystyle H(f)}$, уклања слике, оставља оригинални спектар, ${\displaystyle X(f)}$, и опоравља оригинални сигнал из његових узорака.

Слика лево приказује функцију (сиво/црно) која се узоркује и реконструише (златно) при стално растућим густинама одабирања, док слика десно приказује фреквенцијски спектар сиво/црне функције, који се не мења. Највиша фреквенција у спектру је половина ширине целог спектра. Ширина стално растућег ружичастог сенчења једнака је брзини одабирања. Када обухвати цео фреквенцијски спектар, она је двоструко већа од највише фреквенције, и тада се реконструисани таласни облик поклапа са узоркованим.

Извођење као посебан случај Поасонове сумације

Када нема преклапања копија (такође познатих као „слике”) од ${\displaystyle X(f)}$, члан ${\displaystyle k=0}$ из Једн. 1 може се повратити производом:

$${\displaystyle X(f)=H(f)\cdot X_{1/T}(f),}$$

где је:

$${\displaystyle H(f)\ \triangleq \ {\begin{cases}1&|f|<B\\0&|f|>f_{s}-B.\end{cases}}}$$

Теорема одабирања је доказана пошто ${\displaystyle X(f)}$ јединствено одређује ${\displaystyle x(t)}$.

Све што преостаје је да се изведе формула за реконструкцију. ${\displaystyle H(f)}$ не мора бити прецизно дефинисано у региону ${\displaystyle [B,\ f_{s}-B]}$ јер је ${\displaystyle X_{1/T}(f)}$ нула у том региону. Међутим, најгори случај је када је ${\displaystyle B=f_{s}/2,}$ Никвистова фреквенција. Функција која је довољна за тај и све мање озбиљне случајеве је:

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

где је ${\displaystyle \mathrm {rect} }$ правоугаона функција. Стога:

${\displaystyle X(f)=\mathrm {rect} \left({\frac {f}{f_{s}}}\right)\cdot X_{1/T}(f)}$

${\displaystyle =\mathrm {rect} (Tf)\cdot \sum _{n=-\infty }^{\infty }T\cdot x(nT)\ e^{-i2\pi nTf}}$      (из  Једн. 1, горе).

${\displaystyle =\sum _{n=-\infty }^{\infty }x(nT)\cdot \underbrace {T\cdot \mathrm {rect} (Tf)\cdot e^{-i2\pi nTf}} _{{\mathcal {F}}\left\{\mathrm {sinc} \left({\frac {t-nT}{T}}\right)\right\}}.}$     ^[а]

Инверзна трансформација обе стране производи Витакер-Шенонову формулу за интерполацију:

${\displaystyle x(t)=\sum _{n=-\infty }^{\infty }x(nT)\cdot \mathrm {sinc} \left({\frac {t-nT}{T}}\right),}$

што показује како се узорци, ${\displaystyle x(nT)}$, могу комбиновати да би се реконструисало ${\displaystyle x(t)}$.

• Веће вредности ${\displaystyle f_{s}}$ од потребних (мање вредности ${\displaystyle T}$), назване прекомерно одабирање (енгл. oversampling), немају утицаја на исход реконструкције и имају предност што остављају простор за прелазни опсег у којем ${\displaystyle H(f)}$ може слободно узимати међувредности. Пододабирање, које узрокује алијасинг, у општем случају није реверзибилна операција.
• Теоретски, формула за интерполацију може се имплементирати као нископропусни филтер, чији је импулсни одзив ${\displaystyle \mathrm {sinc} (t/T)}$ и чији је улаз ${\displaystyle \textstyle \sum _{n=-\infty }^{\infty }x(nT)\cdot \delta (t-nT),}$ што је Дираков чешаљ функција модулисана узорцима сигнала. Практични дигитално-аналогни претварачи (DAC) имплементирају апроксимацију попут задржавања нултог реда. У том случају, прекомерно одабирање може смањити грешку апроксимације.

Шенонов оригинални доказ

Поасон показује да Фуријеов ред у Једн. 1 производи периодичну сумацију ${\displaystyle X(f)}$, без обзира на ${\displaystyle f_{s}}$ и ${\displaystyle B}$. Шенон, међутим, изводи коефицијенте реда само за случај ${\displaystyle f_{s}=2B}$. Практично цитирајући Шенонов оригинални рад:

Нека је ${\displaystyle X(\omega )}$ спектар од ${\displaystyle x(t).}$  Тада

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

јер се претпоставља да је ${\displaystyle X(\omega )}$ нула изван опсега ${\displaystyle \left|{\tfrac {\omega }{2\pi }}\right|<B.}$  Ако ставимо да је ${\displaystyle t={\tfrac {n}{2B}},}$ где је ${\displaystyle n}$ било који позитиван или негативан цео број, добијамо:

${\displaystyle 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 .}$     (Једн. 2)

Са леве стране су вредности ${\displaystyle x(t)}$ у тачкама одабирања. Интеграл са десне стране ће бити препознат као суштински^[б] ${\displaystyle n}$-ти коефицијент у развоју функције ${\displaystyle X(\omega )}$ у Фуријеов ред, узимајући интервал од ${\displaystyle -B}$ до ${\displaystyle B}$ као основни период. То значи да вредности узорака ${\displaystyle x(n/2B)}$ одређују Фуријеове коефицијенте у развоју ${\displaystyle X(\omega )}$ у ред.  Дакле, оне одређују ${\displaystyle X(\omega ),}$ пошто је ${\displaystyle X(\omega )}$ нула за фреквенције веће од ${\displaystyle B,}$ а за ниже фреквенције ${\displaystyle X(\omega )}$ је одређено ако су одређени његови Фуријеови коефицијенти. Али ${\displaystyle X(\omega )}$ у потпуности одређује оригиналну функцију ${\displaystyle x(t)}$, пошто је функција одређена ако је њен спектар познат. Према томе, оригинални узорци у потпуности одређују функцију ${\displaystyle x(t)}$.

Шенонов доказ теореме је у том тренутку завршен, али он наставља да расправља о реконструкцији путем синк-функција, што данас називамо Витакер-Шенонова формула за интерполацију, као што је већ дискутовано. Он не изводи нити доказује својства синк-функције, пошто је однос Фуријеовог пара између рект функције (правоугаоне функције) и синк-функција био добро познат у то време.^[4]

Нека је ${\displaystyle x_{n}}$ ${\displaystyle n}$-ти узорак. Тада је функција ${\displaystyle x(t)}$ представљена са:

${\displaystyle x(t)=\sum _{n=-\infty }^{\infty }x_{n}{\sin(\pi (2Bt-n)) \over \pi (2Bt-n)}.}$

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

Примена на вишеваријабилне сигнале и слике

Главни чланак: Вишедимензионално одабирање

Подузоркована слика која приказује моаре ефекат

Правилно узоркована слика

Теорема одабирања се обично формулише за функције једне променљиве. Сходно томе, теорема је директно применљива на временски зависне сигнале и нормално се формулише у том контексту. Међутим, теорема одабирања може се на једноставан начин проширити на функције произвољног броја променљивих. Слике у сивим тоновима, на пример, често се представљају као дводимензионални низови (или матрице) реалних бројева који представљају релативне интензитете пиксела (елемената слике) који се налазе на пресецима локација узорака у редовима и колонама. Као резултат, слике захтевају две независне променљиве, или индексе, да би се јединствено одредио сваки пиксел — један за ред, и један за колону.

Слике у боји се обично састоје од композиције три одвојене слике у сивим тоновима, по једна за представљање сваке од три основне боје — црвене, зелене и плаве, или скраћено RGB. Други простори боја који користе 3-векторе за боје укључују HSV, CIELAB, XYZ, итд. Неки простори боја као што су цијан, магента, жута и црна (CMYK) могу представљати боју са четири димензије. Све ово се третира као векторски вредносне функције над дводимензионалним узоркованим доменом.

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

Још један пример је приказан овде на шарама цигли. Горња слика приказује ефекте када услов теореме одабирања није задовољен. Када софтвер рескалира слику (исти процес који креира умањену слику приказану на доњој слици), он, у ствари, прво пропушта слику кроз нископропусни филтер, а затим је подузоркује како би се добила мања слика која не показује моаре ефекат. Горња слика је оно што се дешава када се слика подузоркује без нископропусног филтрирања: долази до алијасинга.

Теорема одабирања се примењује на системе камера, где сцена и сочиво чине аналогни просторни извор сигнала, а сензор слике је уређај за просторно одабирање. Свака од ових компоненти се карактерише функцијом преноса модулације (MTF), која представља прецизну резолуцију (просторну ширину опсега) доступну у тој компоненти. Ефекти алијасинга или замућења могу се јавити када су MTF сочива и MTF сензора неусклађени. Када оптичка слика коју узоркује сензорски уређај садржи веће просторне фреквенције од сензора, пододабирање делује као нископропусни филтер да би се смањио или елиминисао алијасинг. Када површина тачке одабирања (величина пикселског сензора) није довољно велика да обезбеди довољно просторног анти-алијасинга, у систем камере се може укључити посебан анти-алијасинг филтер (оптички нископропусни филтер) да би се смањио MTF оптичке слике. Уместо да захтева оптички филтер, графички процесор камера на паметним телефонима врши дигиталну обраду сигнала да би уклонио алијасинг помоћу дигиталног филтра. Дигитални филтри такође примењују изоштравање како би појачали контраст са сочива на високим просторним фреквенцијама, који иначе нагло опада на границама дифракције.

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

Породица синусоида на критичној фреквенцији, које све имају исте низове узорака наизменично +1 и –1. То јест, све су оне алијаси једна друге, иако њихова фреквенција није изнад половине брзине одабирања.

Критична фреквенција

Да би се илустровала неопходност ${\displaystyle f_{s}>2B,}$ размотримо породицу синусоида генерисаних различитим вредностима ${\displaystyle \theta }$ у овој формули:

${\displaystyle x(t)={\frac {\cos(2\pi Bt+\theta )}{\cos(\theta )}}\ =\ \cos(2\pi Bt)-\sin(2\pi Bt)\tan(\theta ),\quad -\pi /2<\theta <\pi /2.}$

Са ${\displaystyle f_{s}=2B}$ или еквивалентно ${\displaystyle T=1/2B,}$ узорци су дати са:

${\displaystyle x(nT)=\cos(\pi n)-\underbrace {\sin(\pi n)} _{0}\tan(\theta )=(-1)^{n}}$

без обзира на вредност ${\displaystyle \theta .}$ Оваква врста двосмислености је разлог за стриктну неједнакост у услову теореме одабирања.

Одабирање сигнала ван основног опсега

Као што је дискутовао Шенон:^[2]

Сличан резултат важи ако опсег не почиње од нулте фреквенције већ од неке више вредности, и може се доказати линеарном транслацијом (која физички одговара модулацији са једним бочним опсегом) случаја са нултом фреквенцијом. У овом случају, елементарни импулс се добија из ${\displaystyle \sin(x)/x}$ модулацијом са једним бочним опсегом.

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

На пример, да би се узорковали ФМ радио сигнали у фреквенцијском опсегу од 100–102 MHz, није неопходно узорковати на 204 MHz (двоструко више од горње фреквенције), већ је довољно узорковати на 4 MHz (двоструко више од ширине фреквенцијског интервала). (Реконструкција обично није циљ код узоркованих IF или RF сигнала. Уместо тога, низ узорака се може третирати као обични узорци сигнала фреквенцијски помереног близу основног опсега, и дигитална демодулација се може наставити на тој основи.)

Користећи услов пропусног опсега, где је ${\displaystyle X(f)=0}$ за све ${\displaystyle |f|}$ изван отвореног опсега фреквенција

${\displaystyle \left({\frac {N}{2}}f_{\mathrm {s} },{\frac {N+1}{2}}f_{\mathrm {s} }\right),}$

за неки ненегативни цео број ${\displaystyle N}$ и неку фреквенцију одабирања ${\displaystyle f_{\mathrm {s} }}$, могуће је пронаћи интерполацију која репродукује сигнал. Имајте на уму да може постојати више комбинација ${\displaystyle N}$ и ${\displaystyle f_{\mathrm {s} }}$ које функционишу, укључујући нормалан услов основног опсега као случај ${\displaystyle N=0.}$ Одговарајући интерполациони филтер који треба конволуирати са узорком је импулсни одзив идеалног „brick-wall” филтра пропусника опсега (за разлику од идеалног brick-wall нископропусног филтра који је коришћен горе) са пресечним фреквенцијама на горњој и доњој ивици наведеног опсега, што је разлика између пара импулсних одзива нископропусних филтара:

$${\displaystyle (N+1)\,\operatorname {sinc} \left({\frac {(N+1)t}{T}}\right)-N\,\operatorname {sinc} \left({\frac {Nt}{T}}\right).}$$

Ова функција је 1 на ${\displaystyle t=0}$ и нула на било ком другом умношку од ${\displaystyle T}$ (као и у другим временима ако је ${\displaystyle N>0}$).

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

Неуниформно одабирање

Шенонова теорија одабирања може се генерализовати за случај неуниформног одабирања, то јест, узорака који нису узети у једнаким временским интервалима. Шенонова теорија одабирања за неуниформно одабирање наводи да се сигнал са ограниченим опсегом може савршено реконструисати из својих узорака ако просечна брзина одабирања задовољава Никвистов услов.^[5] Дакле, иако равномерно распоређени узорци могу резултирати лакшим алгоритмима за реконструкцију, то није неопходан услов за савршену реконструкцију.

Општу теорију за сигнале ван основног опсега и неуниформне узорке развио је 1967. године Хенри Ландау.^[6] Он је доказао да просечна брзина одабирања (униформна или не) мора бити двоструко већа од заузете ширине опсега сигнала, под претпоставком да је a priori познато који део спектра је заузет.

Крајем 1990-их, овај рад је делимично проширен да покрије сигнале за које је количина заузетог пропусног опсега позната, али стварни заузети део спектра није познат.^[7] Двехиљадитих година развијена је комплетна теорија (погледајте одељак Одабирање испод Никвистове брзине под додатним ограничењима испод) користећи компресовано очитавање. Конкретно, теорија, користећи језик обраде сигнала, описана је у раду Мишалија и Елдара из 2009. године.^[8] Они показују, између осталог, да ако су локације фреквенција непознате, онда је неопходно узорковати најмање двоструко више од Никвистових критеријума; другим речима, морате платити барем фактор 2 за непознавање локације спектра. Имајте на уму да минимални захтеви за одабирање не гарантују нужно стабилност.

Одабирање испод Никвистове брзине под додатним ограничењима

Главни чланак: Пододабирање

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

Нетривијалан пример искоришћавања додатних претпоставки о сигналу даје недавна област компресованог очитавања, која омогућава потпуну реконструкцију са брзином одабирања испод Никвистове. Конкретно, ово се односи на сигнале који су ретки (или компресибилни) у неком домену. Као пример, компресовано очитавање се бави сигналима који могу имати ниску укупну ширину опсега (рецимо, ефективну ширину опсега ${\displaystyle EB}$), али су локације фреквенција непознате, уместо да су све заједно у једном опсегу, тако да се техника пропусног опсега не примењује. Другим речима, фреквенцијски спектар је редак. Традиционално, неопходна брзина одабирања је стога ${\displaystyle 2B.}$ Користећи технике компресованог очитавања, сигнал би се могао савршено реконструисати ако се узоркује брзином нешто нижом од ${\displaystyle 2EB.}$ Са овим приступом, реконструкција више није дата формулом, већ решењем програма линеарне оптимизације. Други пример где је одабирање испод Никвистове брзине оптимално јавља се под додатним ограничењем да су узорци квантизовани на оптималан начин, као у комбинованом систему одабирања и оптималне компресије са губицима.^[9] Ова поставка је релевантна у случајевима где се разматра заједнички ефекат одабирања и квантизације, и може пружити доњу границу за минималну грешку реконструкције која се може постићи приликом одабирања и квантизације случајног сигнала. За стационарне Гаусове случајне сигнале, ова доња граница се обично постиже при брзини одабирања испод Никвистове, што указује да је одабирање испод Никвистове брзине оптимално за овај модел сигнала под оптималном квантизацијом.^[10]

Историјска позадина

Теорему одабирања имплицирао је рад Харија Никвиста из 1928. године,^[11] у којем је показао да се до ${\displaystyle 2B}$ независних импулсних узорака може послати кроз систем ширине опсега ${\displaystyle B}$; али он није експлицитно разматрао проблем одабирања и реконструкције континуалних сигнала. Отприлике у исто време, Карл Кипфмилер је показао сличан резултат^[12] и расправљао о импулсном одзиву синк-функције филтра за ограничавање опсега, путем његовог интеграла, одзива на јединични скок синусног интеграла; овај филтар за ограничавање опсега и реконструкцију који је толико централан за теорему одабирања понекад се назива Кипфмилеров филтар (али ретко на енглеском).

Теорему одабирања, у суштини дуал Никвистовог резултата, доказао је Клод Е. Шенон.^[2] Едмунд Тејлор Витакер је објавио сличне резултате 1915. године,^[13] као и његов син Џон Макнатен Витакер 1935. године,^[14] и Денис Габор 1946. године („Теорија комуникације”).

Године 1948. и 1949, Клод Е. Шенон је објавио два револуционарна чланка у којима је утемељио теорију информација.^[15][16][2] У Шеноновом делу „Математичка теорија комуникације”, теорема одабирања је формулисана као „Теорема 13”: Нека ${\displaystyle f(t)}$ не садржи фреквенције преко W. Тада

$${\displaystyle f(t)=\sum _{n=-\infty }^{\infty }X_{n}{\frac {\sin \pi (2Wt-n)}{\pi (2Wt-n)}},}$$ где је ${\displaystyle X_{n}=f\left({\frac {n}{2W}}\right).}$

Тек након објављивања ових чланака, теорема позната као „Шенонова теорема одабирања” постала је опште позната међу инжењерима комуникација, иако сам Шенон пише да је то чињеница која је опште позната у комуникационој уметности.^[в] Неколико редова даље, међутим, додаје: „али упркос њеној очигледној важности, чини се да се није експлицитно појавила у литератури теорије комуникације”. Упркос томе што је његова теорема одабирања објављена крајем 1940-их, Шенон је своју теорему извео још 1940. године.^[17]

Други проналазачи

Други који су независно открили или одиграли улогу у развоју теореме одабирања расправљани су у неколико историјских чланака, на пример, од стране Џерија^[18] и Ликеа.^[19] На пример, Лике истиче да је Херберт Рабе, Кипфмилеров асистент, доказао теорему у својој докторској дисертацији из 1939. године; термин Рабеов услов почео је да се повезује са критеријумом за недвосмислену репрезентацију (брзина одабирања већа од двоструке ширине опсега). Мејеринг^[20] помиње неколико других откривача и имена у једном пасусу и пар фуснота:

Како је истакао Хигинс, теорему одабирања би заиста требало разматрати у два дела, као што је горе урађено: први наводи чињеницу да је функција са ограниченим опсегом потпуно одређена својим узорцима, док други описује како реконструисати функцију користећи њене узорке. Оба дела теореме одабирања дао је у нешто другачијем облику Џ. М. Витакер, а пре њега и Огура. Вероватно нису били свесни чињенице да је први део теореме навео још 1897. године Борел.^[г] Као што смо видели, Борел је такође у то време користио оно што је постало познато као кардинални ред. Међутим, изгледа да није направио везу. У каснијим годинама постало је познато да је теорему одабирања пре Шенона представио руској комуникационој заједници Котељников. У имплицитнијем, вербалном облику, такође је описана у немачкој литератури од стране Рабеа. Неколико аутора је поменуло да је Сомеја увео теорему у јапанску литературу паралелно са Шеноном. У енглеској литератури, Вестон ју је увео независно од Шенона отприлике у исто време.^[д]

— Ерик Мејеринг, „Хронологија интерполације од древне астрономије до модерне обраде сигнала и слике” (цитати изостављени)

У руској литератури позната је као Котељникова теорема, названа по Владимиру Котељникову, који ју је открио 1933. године.^[21]

Зашто Никвист?

Како, када или зашто је тачно Хари Никвист добио своје име везано за теорему одабирања остаје нејасно. Термин Никвистова теорема одабирања (тако капитализован) појавио се већ 1959. године у књизи његовог бившег послодавца, Белових лабораторија,^[22] а поново се појавио 1963. године,^[23] и не-капитализован 1965. године.^[24] Називана је Шенонова теорема одабирања још 1954. године,^[25] али и само теорема одабирања у неколико других књига раних 1950-их.

Године 1958, Блекман и Тјуки цитирали су Никвистов чланак из 1928. као референцу за теорему одабирања теорије информација,^[26] иако тај чланак не третира одабирање и реконструкцију континуалних сигнала као други. Њихов речник термина укључује ове ставке: Теорема одабирања (теорије информација)

Никвистов резултат да равномерно распоређени подаци, са две или више тачака по циклусу највише фреквенције, омогућавају реконструкцију функција са ограниченим опсегом. (Погледајте Кардинална теорема.)

Кардинална теорема (теорије интерполације)

Прецизна изјава услова под којима се вредности дате у двоструко бесконачном скупу једнако распоређених тачака могу интерполирати да би се добила континуална функција са ограниченим опсегом уз помоћ функције $${\displaystyle {\frac {\sin(x-x_{i})}{x-x_{i}}}.}$$

На који се тачно „Никвистов резултат” они позивају остаје мистериозно. Када је Шенон навео и доказао теорему одабирања у свом чланку из 1949. године, према Мејерингу,^[20] „он је критични интервал одабирања ${\displaystyle T={\frac {1}{2W}}}$ назвао Никвистов интервал који одговара опсегу ${\displaystyle W,}$ у знак признања Никвистовом открићу фундаменталне важности овог интервала у вези са телеграфијом”. Ово објашњава Никвистово име на критичном интервалу, али не и на теореми.

Слично томе, Никвистово име је везано за Никвистову брзину 1953. године од стране Харолда С. Блека:

Ако је суштински фреквенцијски опсег ограничен на ${\displaystyle B}$ циклуса у секунди, ${\displaystyle 2B}$ је Никвист дао као максималан број кодних елемената у секунди који се могу недвосмислено разрешити, под претпоставком да је вршна интерференција мања од пола квантног корака. Ова брзина се генерално назива сигнализација на Никвистовој брзини а ${\displaystyle {\frac {1}{2B}}}$ је назван Никвистов интервал.

— Харолд Блек, Теорија модулације^[27] (подебљано додато ради наглашавања; италик као у оригиналу)

Према Оксфордском енглеском речнику, ово може бити порекло термина Никвистова брзина. У Блековој употреби, то није брзина одабирања, већ брзина сигнализације.

Види још

• 44.100 Hz, уобичајена брзина која се користи за узорковање чујних фреквенција заснована на границама људског слуха и теореми одабирања
• Балијан-Лоуова теорема, слична теоријска доња граница брзина одабирања, али која се примењује на временско-фреквенцијске трансформације
• Ченг-Марксова теорема, која специфицира услове где обнова сигнала помоћу теореме одабирања може постати лоше постављен проблем
• Шенон-Хартлијева теорема
• Никвистов ИСИ критеријум
• Реконструкција из прелазака кроз нулу
• Задржавање нултог реда
• Дираков чешаљ

Напомене

1. Синк функција следи из редова 202 и 102 табела трансформација.
2. Множењем обе стране Једн. 2 са ${\displaystyle T=1/2B}$ добијају се, са леве стране, скалиране вредности узорака ${\displaystyle (T\cdot x(nT))}$ у Поасоновој формули (Једн. 1), а са десне, стварна формула за коефицијенте Фуријеовог реда.
3. Shannon 1949, стр. 448.
4. Неколико аутора, пратећи Блека, тврдило је да је овај први део теореме одабирања навео још раније Коши, у раду објављеном 1841. Међутим, Кошијев рад не садржи такву изјаву, како је истакао Хигинс.
5. Као последица открића неколико независних увођења теореме одабирања, људи су почели да се позивају на теорему укључујући имена поменутих аутора, што је резултирало фразама попут „Витакер-Котељников-Шенонова (ВКШ) теорема одабирања” или чак „Витакер-Котељников-Рабе-Шенон-Сомејина теорема одабирања”. Да би се избегла забуна, можда је најбоље да се на њу једноставно реферише као на теорему одабирања, „уместо да се покушава пронаћи наслов који одаје признање свим претендентима”.