Nikvist-Šenonova teorema odabiranja

U oblasti digitalne obrade signala, teorema uzorkovanja je osnovni most između signala kontinualnog vremena i signala diskretnog vremena . Ona uspostavlja dovoljan uslov za brzinu uzorkovanja koja dozvoljava diskretni niz uzoraka da prikupi sve informacije iz neprekidnog signala konačne propusnosti .

Primer veličine Furijeove transformacije opsežne funkcije

Strogo govoreći, teorema se odnosi samo na klasu matematičkih funkcija koja imaju Furijeovu transformaciju koja je nula izvan konačnog područja frekvencija. Intuitivno očekujemo da kada neko smanji kontinuiranu funkciju na diskretnu sekvencu i interpolira natrag na kontinuiranu funkciju, vernost rezultata zavisi od gustine (ili brzine uzorka ) originalnih uzoraka. Teorema uzorkovanja uvodi koncept brzine uzorkovanja koja je dovoljna za savršenu vernost klase funkcija koje su ograničene na datu širinu pojasa, tako da se u procesu uzorkovanja ne gube stvarne informacije. Izražava dovoljnu brzinu uzorka u smislu propusnosti za klasu funkcija. Teorema takođe vodi formuli za savršeno rekonstrukciju originalne funkcije neprekidnog vremena iz uzoraka.

Savršena rekonstrukcija i dalje može biti moguća kada kriterij brzine uzorkovanja nije zadovoljen, pod uslovom da su poznata druga ograničenja signala. (Vidi § Sampling of non-baseband signals i kompresovanog senzora. ) U nekim slučajevima (kada kriterijum brzine uzorka nije zadovoljen), korišćenje dodatnih ograničenja omogućava približne rekonstrukcije. Vernost ovih rekonstrukcija može se proveriti i kvantifikovati koristeći Bohnerovu teoremu .

Ime Nikvist-Šenonova teorema uzorkovanja odaje počast Hariju Nikvistu i Klodu Šenon-u, iako je činjenica da ju je Vladimir Kotelnikov već otkrio 1933. godine. Teoremu su takođe samostalno otkrili E.T. Vitaker i drugi. Tako je poznata i po imenima Nikvist-Šenon–Kotelnikova, Vitaker-Šenon-Kotelnikova, Vitaker-Nikvist-Kotelnikov-Šenonov- a i kardinalna teorema interpolacije .

Uvod

Uzorkovanje je proces pretvaranja signala (na primer, funkcije neprekidnog vremena i / ili prostora) u niz vrednosti (funkcija diskretnog vremena i / ili prostora). Šenonova verzija teoreme glasi:

Ako funkcija $x(t)$ ne sadrži frekvencije veće od B herca, on se u potpunosti određuje tako što će dati svoje ordinate u nizu razmaknutih tačaka $1/(2B)$ sekundi razmaka.

Dovoljna stopa uzorkovanja je, dakle, veća od $2B$ uzoraka u sekundi. Ekvivalentno za datu stopu uzorka $f_{s}$, zagarantovana je savršena rekonstrukcija $B<f_{s}/2$ .

Kada je ograničenje pojave previsoko (ili ne postoji ograničenje pojasa), rekonstrukcija pokazuje nesavršenosti poznate kao aliasing . Moderne izjave teoreme ponekad pažljivo izriču da to $x(t)$ ne sme sadržavati nikakve sinusoidne komponente frekvencije tačno B, ili da B mora biti strogo manja od ½ uzorka. Prag $2B$ zove se Nikvistova stopa i atribut je kontinuiranog unosa $x(t)$ koji će biti uzorkovan. Brzina uzorkovanja mora biti veća od Nikvistove stope da bi uzorci bili dovoljni da predstavljaju x(t). Prag f_s / 2 naziva se Nikvistovom frekvencijom i atribut je opreme za uzorkovanje . Sve značajne frekvencijske komponente pravilno uzorkovanih x(t) postoje ispod Nikvistove frekvencije. Uslov opisan ovim nejednakostima naziva se Nikvistov kriterijum, ili ponekad Raabeov uslov . Teorema je takođe primenljiva na funkcije drugih domena, poput prostora, u slučaju digitalizovane slike. Jedina promena, u slučaju drugih domena, su mere koje se primenjuju na t, f_s i B.

Normalizovana sinc funkcija : sin(πx) / (πx) ... prikazuje centralni vrh na x = 0, a nula-prelaz na ostalim celobrojnim vrednostima k .

symbol T = 1/f_s se obično koristi da predstavlja interval između uzoraka i naziva se period uzorka ili interval uzorkovanja . I uzorci funkcije x(t) su obično označeni sa x[n] = x(nT) (alternativno "x_n" u starijoj literaturi za obradu signala), za sve celobrojne vrednosti n . Matematički idealan način interpoliranja niza uključuje upotrebu sink funkcija . Svaki uzorak u nizu zamenjuje se sink funkcijom, centriranom na vremensku osu na originalnom mestu uzorka, nT, sa amplitudom sink funkcije prilagođenom vrednosti vrednosti uzorka, x[n]. Nakon toga, sink funkcije se sumiraju u kontinuiranu funkciju. Matematički ekvivalentna metoda je objedinjavanje jedne sink funkcije sa nizom Dirakovih delta impulsa, ponderisanih vrednostima uzorka. Nijedna metoda nije brojčano praktična. Umesto toga, koristi se neka vrsta aproksimacije sink funkcija, ograničene dužine. Savršenstva koja se mogu pripisati aproksimaciji poznata su kao greška interpolacije .

Praktični digitalno-analogni pretvarači ne proizvode ni umanjene ni zakasnele sink funkcije, niti idealne Dirakove impulse . Umesto toga, oni proizvode komadno-konstantni niz umanjenih i odloženih pravouglih impulsa ( zadržavanje nula reda ), obično praćen filtrom niske propusnosti (koji se naziva " filter za oslikavanje slike" ) za uklanjanje lažnih visokofrekventnih replika (slika) originalnog osnovnog signala.

Aliasing

Uzorci dva sinusna talasa mogu biti identični kada je barem jedan od njih frekvencije veće od polovine uzorka.

Kada $x(t)$ je funkcija sa Furijeovom transformacijom $X(f)$ :

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

Puasonova formula sumiranja ukazuje da su uzorci, $x(nT)$, od $x(t)$ dovoljni za pravljenje periodičnog sažetka $X(f)$ . Rezultat je :

$X_{s}(f)\ \triangleq \sum _{k=-\infty }^{\infty }X\left(f-kf_{s}\right)=\sum _{n=-\infty }^{\infty }T\cdot x(nT)\ e^{-i2\pi nTf},$ (Eq.1)

X(f) (u gornjem delu slike označeno plavom bojom) i X_A (f) (u donjem delu slike označeno plavom bojom) su kontinuirane Furijeove transformacije dveju različitih funkcija, $x(t)$ i $x_{A}(t)$ (nije prikazano). Kada se funkcije uzorkuju brzinom $f_{s}$, slike (označeno zelenom bojom) se dodaju originalnim transformacijama (označeno plavom bojom) kada se ispituju diskretne vremenske Furijeove transformacije (DTFT) sekvenci. U ovom hipotetičkom primeru, DTFT-ovi su identični, što znači da su uzorkovani singali identični, iako originalne kontinuirane prethodno uzorkovane funkcije nisu. Ako su to zvučni signali, $x(t)$ i $x_{A}(t)$ možda ne zvuči isto. Ali njihovi uzorci (uzeti brzinom f_s ) su identični i doveli bi do identičnih reprodukovanih zvukova; prema tome, x_A (t) je alias od x(t) pri ovoj brzini uzorka.

koja je periodična funkcija i njen ekvivalentni prikaz kao Furijeov niz, čiji su koeficijenti $T\cdot x(nT).$ Ova funkcija je poznata i kao diskretna Furijeova transformacija (DTFT) uzorka sekvence.

Kao što je prikazano, kopije $X(f)$ pomerane su umnošcima od $f_{s}$ i kombinovano dodavanjem. Za ograničeni opseg  $(X(f)=0,{\text{ for all }}|f|\geq B)$  i dovoljno velika $f_{s},$ moguće je da kopije ostanu različite. Ali ako Nikvistov kriterijum nije zadovoljen, susedne kopije se preklapaju i uopšte nije moguće razabrati nedvosmisleno. $X(f).$ Bilo koja komponenta frekvencije gore $f_{s}/2$ ne razlikuje se od komponente niže frekvencije, zvane alias, povezane sa jednom od kopija. U takvim slučajevima uobičajene tehnike interpolacije proizvode alias, a ne originalnu komponentu. Kada je stopa uzorkovanja unapred određena drugim razmatranjima (kao što je industrijski standard), $x(t)$ obično se filtrira tako da se njegove visoke frekvencije smanje na prihvatljive nivoe pre nego što se uzorkuje. Potrebna vrsta filtera je filter sa niskim propustom i u ovim se uslovima naziva anti-aliasing filter .

Spektar, X_s(f), pravilno uzorkovanog opsega signala (označeno plavom bojom) i susednih DTFT slika (označeno zelenom bojom) koje se ne preklapaju. Filtrirani niskopropusni filter od opeke, H(f), uklanja slike, ostavlja izvorni spektar, X(f) i vraća originalni signal iz svojih uzoraka.

Derivacija kao poseban slučaj sažimanja Puasona

Kada se ne preklapaju kopije (poznate i kao "slike") $X(f)$, $k=0$ značenje izraza 1 može se povratiti proizvodom :

$X(f)=H(f)\cdot X_{s}(f),$      where:

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

Teorema uzorkovanja je dokazana od kada $X(f)$ jedinstveno određuje $x(t).$

Sve što preostaje je da se dobije formula za rekonstrukciju. $H(f)$ ne moraju biti tačno definisane u regionu $[B,\ f_{s}-B]$ jer $X_{s}(f)$ je nula u tom regionu. Međutim, najgori je slučaj kada $B=f_{s}/2,$ Nikvistova frekvencija. Funkcija koja je dovoljna za to i za sve manje teške slučajeve je :

$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}}$

gde je rect (•) pravougaona funkcija..Stoga :

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

$=\mathrm {rect} (Tf)\cdot \sum _{n=-\infty }^{\infty }T\cdot x(nT)\ e^{-i2\pi nTf}$    (od   Eq.1, gore).

$=\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\}}.$   

Inverzna transformacija obe strane proizvodi Vitaker-Šenonovu interpolacijsku formulu :

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

koji pokazuje kako uzorci, $x(nT),$ može se kombinovati za rekonstrukciju $x(t).$

• Vrednosti f_s (manje vrednosti T ), koje se nazivaju preterano uzorkovanje, nemaju uicaja na ishod rekonstrukcije i imaju prednost da ostavljaju prostor za prelazni pojas u kojem je H(f) slobodan uzeti intermedijarne vrednosti. Prekomandiranje, koje uzrokuje alias, generalno nije reverzibilna operacija.
• Teoretski, interpolaciona formula se može primeniti kao filter niskog protoka, čiji je impulsni odziv sink (t/T) i čiji je ulaz $\textstyle \sum _{n=-\infty }^{\infty }x(nT)\cdot \delta (t-nT),$ što je funkcija Dirakova povorka impulsa modulirana uzorcima signala. Praktični digitalno-analogni pretvarači (DAC) implementiraju aproksimaciju kao što je nulti red . U tom slučaju, preterano uzorkovanje može umanjiti pogrešku aproksimacije.

Šenonov originalni dokaz

Puason pokazuje da Furijeov niz u izrazu 1 proizvodi periodično $X(f)$, bez obzira na $f_{s}$ i $B$ . Šenon, međutim, izvodi samo koeficijente serije za slučaj $f_{s}=2B$ . Gotovo citirajući Šenonov originalni rad :

Dozvoliti $X(\omega )$ da bude spektar $x(t).$  Onda

$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 ,$

jer $X(\omega )$ pretpostavlja se da je nula izvan opsega $\left|{\tfrac {\omega }{2\pi }}\right|<B.$  Ako dozvolimo $t={\tfrac {n}{2B}},$ gde $n$ bilo koji pozitivni ili negativni celi broj, dobijamo:

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

(Izraz 2)

Na levoj strani su vrednosti od $x(t)$ na tačkama uzorkovanja. Integral s desne strane biće prepoznat se kao suštinski n-ti koeficijent u širenju funkcije Fourier-ove serije $X(\omega ),$ uzimajući interval $-B$ do $B$ kao temeljni period. To znači da su vrednosti uzoraka $x(n/2B)$ odrediti Furijeove koeficijente u serijskom širenju $X(\omega ).$  Tako oni određuju $X(\omega ),$ Od $X(\omega )$ je nula za frekvencije veće od B, a za niže frekvencije $X(\omega )$ određuje se ako su utvrđeni njegovi Furijeovi koeficijenti. Ali $X(\omega )$ određuje originalnu funkciju $x(t)$ u potpunosti, jer se funkcija određuje ako je poznat njen spektar. Zbog toga originalni uzorci određuju funkciju $x(t)$ u potpunosti.

Šenonov dokaz teoreme je dovršen u tom trenutku, ali on nastavlja da razmatra rekonstrukciju preko sink funkcija, što sada nazivamo Vitaker-Šenonovom interpolacionom formulom kao što je gore diskutovano. On ne izvodi ili ne dokazuje svojstva sink funkcije, ali to bi bilo poznato inženjerima koji su u to vreme čitali njegova dela, budući da je odnos Furijeovog para između rect (pravougla funkcija) i sink bio dobro poznat.

Dozvoliti $x_{n}$ da bude n-ti uzorak. Tada funkcija $x(t)$ predstavlja:

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

Kao i u drugom dokazu, pretpostavlja se postojanje Furijeove transformacije izvornog signala, tako da dokaz ne kaže da li se teorema uzorkovanja proširuje na ograničene stacionarne slučajne procese.

Primena na multivarijabilne signale i slike

Podvrsta slike koja prikazuje Moarov uzorak

Pravilno uzorkovana slika

Teorema uzorkovanja se obično formuliše za funkcije jedne promenljive. Shodno tome, teorema je direktno primenljiva na signale koji zavise od vremena i normalno je formulisana u tom kontekstu. Međutim, teorema uzorkovanja može se direktno proširiti na funkcije proizvoljno mnogih promenljivih. Slike u sivim tonovima, na primer, često su predstavljene kao dvodimenzionalni nizovi (ili matrice) stvarnih brojeva koji predstavljaju relativni intenzitet piksela (elemenata slike) smeštenih na presecima mesta uzoraka reda i stupaca. Kao rezultat, slike zahtevaju dve nezavisne promenljive ili indekse da jedinstveno odrede svaki piksel - jedan za red i jedan za kolonu.

Slike u boji se obično sastoje od kompozicije od tri odvojene slike u sivim tonovima, od kojih jedna predstavlja svaku od tri osnovne boje - crvenu, zelenu i plavu ili RGB(Red, Green, Blue) ukratko. Ostali prostori u boji koji koriste 3 vektora za boje uključuju HSV(Hue, Saturation, Value), CIELAB, XYZ itd. Neki prostori boja poput cijan, magenta, žuta i crna (CMYK) mogu predstavljati boju u četiri dimenzije. Sve ovo se tretira kao funkcije vektorske vrednosti preko dvodimenzionalnog uzorkovanog domena.

Slično kao jednodimenzionalni diskretni vremenski signali, slike takođe mogu da trpe aliasing ako je rezolucija uzorkovanja ili gustina piksela neadekvatna. Na primer, digitalna fotografija prugaste košulje sa visokim frekvencijama (drugim rečima, udaljenost između pruga je mala) može prouzrokovati otuđenje košulje kada je uzorkuje senzor slike kamere. Aliasing se pojavljuje kao moarov uzorak . "Rešenje" većeg uzorkovanja u prostornom domenu u ovom slučaju bi bilo da se približi košulji, koristi senzor veće rezolucije ili optički zamagli sliku pre nego što je dobije sa senzorom.

Drugi primer je prikazan desno u uzorcima od opeke. Gornja slika prikazuje efekte kada nije zadovoljeno stanje teoreme uzorkovanja. Kada softver ponovo podešava veličinu slike (isti postupak koji stvara sličicu prikazanu na donjoj slici), ona, u stvari, prvo pokrene sliku kroz filter niskih propusnica, a zatim izvrši primer slike kako bi se dobila manja slika koja ne pokazuje moarovu teksturu . Gornja slika je ono što se događa kada slika nije prikazana u uzorku bez filtriranja sa malim prolazima: aliasing rezultata.

Teorema uzorkovanja se primenjuje na sisteme kamera, gde scena i sočivo predstavljaju analogni izvor prostornog signala, a senzor slike je uređaj za prostorno uzorkovanje. Svaku od ovih komponenti karakteriše funkcija prenosa modulacije (MTF), koja predstavlja preciznu rezoluciju (prostorna širina pojasa) koja je dostupna u toj komponenti. Efekti ublažavanja ili zamagljivanja mogu se pojaviti kada se MTF sočiva i MTF senzori ne poklapaju. Kada optička slika koju uzorkuje senzorski uređaj sadrži veće prostorne frekvencije od senzora, pod uzorkovanjem deluje kao filter niskih prolaza da bi se smanjio ili eliminisao otuđenje. Kada površina mesta uzorkovanja (veličina senzora piksela) nije dovoljno velika da obezbedi dovoljno prostornog anti-aliasing-a, u sistem kamere može biti uključen odvojeni filter za ublažavanje (optički filter sa malim prolazom) kako bi se smanjio MTF optičke slike. Umesto da zahteva optički filter, jedinica za grafičku obradu fotoaparata na pametnom telefonu vrši digitalnu obradu signala radi uklanjanja aliasa sa digitalnim filterom. Digitalni filteri takođe primenjuju oštrenje kako bi pojačali kontrast objektiva na visokim prostornim frekvencijama, koji inače brzo pada na difrakcijskim granicama.

Teorema uzorkovanja se takođe primenjuje na digitalne slike posle obrade, poput uzorkovanja nagore ili nadole. Efekti otuđivanja, zamagljivanja i oštrenja mogu se prilagoditi digitalnim filtriranjem implementiranim u softveru, koje nužno slijedi teorijske principe.

Kritična frekvencija

Da bi ilustrovali neophodnost $f_{s}>2B$, razmotrimo porodicu sinusoida generisanih različitim vrednostima $\theta$ u ovoj formuli :

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

Porodica sinusoida na kritičnoj frekvenciji, a svi imaju iste sekvence uzoraka naizmeničnih +1 i –1. To jest, svi su oni međusobno aliasi, iako njihova učestalost nije veća od polovine uzorka.

Sa $f_{s}=2B$ ili slično $T=1/2B$, uzorke daju :

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

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

Uzorkovanje signala koji izvan opsega

Šenonova rasprava glasi:

Sličan rezultat je tačan ako opseg ne počinje na nultoj frekvenciji, ali na nekoj višoj vrednosti, a može se dokazati linearnim prevodom (fizički odgovara modulaciji sa jednostrukom pojavom ) slučaja nulte frekvencije. U ovom slučaju, elementarni impuls se dobija od sin (x) /x jednosmernom modulacijom.

To jest, dovoljan uslov bez gubitka za uzorkovanje signala koji nemaju komponenete signala osnovog pojasa jeste da uključuje širinu frekvencijskog intervala nenultom nasuprot njene najviše komponente frekvencije. Pogledajte Uzorkovanje (obrada signala) za više detalja i primera.

Na primer, u uzorkovanju FM radio signala u frekvencijskom opsegu 100–102   MHz, nije potrebno uzorkovanje na 204 MHz (dvostruko veća od frekvencije), ali je dovoljno da se uzorkuje na 4   MHz (dvostruka širina intervala frekvencije).

Uslov opsega je da je X(f) = 0, za sve nenegativne f izvan otvorenog opsega frekvencija:

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

za neki negativni celi broj N. Ova formulacija uključuje normalno stanje osnovnog opsega kao slučaj N=0.

Odgovarajuća interpolaciona funkcija je impulsni odziv idealnog opružnog filtra od zidova od opeke (za razliku od prethodno upotrebljenog idealnog filtera za zid od opeke) sa presecima na gornjim i donjim ivicama navedenog opsega, što je razlika između para niskopropusnih impulsa:

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

Moguće su i druge generalizacije, na primer na signale koji zauzimaju više neprekinutih opsega. Čak ni najopšteniji oblik teoreme uzorkovanja nema dokazano istinitu suprotnost. Odnosno, ne može se zaključiti da se informacije nužno gube samo zato što nisu ispunjeni uslovi teoreme uzorkovanja; iz inženjerske perspektive, međutim, generalno je sigurno pretpostaviti da ako teorema uzorkovanja nije zadovoljena, informacije će najverovatnije biti izgubljene.

Neujednačeno uzorkovanje

Teorija uzorkovanja Šenona može se generalizovati za slučaj neujednačenog uzorkovanja, odnosno uzoraka koji nisu uzeti jednako raspoređeni u vremenu. Šenonova teorija uzorkovanja za nejednako uzorkovanje kaže da se signal ograničen u opsegu može savršeno rekonstruisati iz njegovih uzoraka ako prosečna brzina uzorkovanja zadovoljava uslov Nikvista. Stoga, iako jednoliko raspoređeni uzorci mogu rezultirati lakšim algoritmima obnove, to nije neophodan uslov za savršenu rekonstrukciju.

Opštu teoriju za neuobičajene uzorke i neujednačene uzorke razvio je 1967. godine Henri Landau . Dokazao je da prosečna stopa uzorkovanja (jednolična ili na neki drugi način) mora biti dvostruko zauzeta širina opsega signala, pretpostavljajući da je a priori poznato koliki deo spektra je zauzet. Krajem 1990-ih, ovaj rad je delimično proširen kako bi se pokrili signali kada je bila poznata količina zauzetog opsega, ali stvarni zauzeti deo spektra nije bio poznat. Tokom 2000-ih razvijena je kompletna teorija (vidi odeljak Uzorkovanje ispod Nikvistove stope pod dodatnim ograničenjima u daljem tekstu) koristeći komprimovano otkrivanje . Konkretno, teorija je koristeći jezik obrade signala opisana u ovom radu za 2009. godinu. Oni pokazuju, između ostalog, da ako su lokacije frekvencije nepoznate, potrebno je uzorkovati najmanje dva puta nikvističke kriterijume; drugim rečima, morate da snosite posledice bar faktora 2 zbog neznanja lokacije spektra . Imajte na umu da minimalni zahtevi za uzorkovanje ne garantuju nužno stabilnost .

Uzorkovanje ispod stope Nikvista pod dodatnim ograničenjima

Teorema uzorkovanja Nikvist-Šenon daje dovoljan uslov za uzorkovanje i rekonstrukciju signala ograničenog opsega. Kada se rekonstrukcija vrši putem interpolacione formule Vitaker-Šenon, Nikvistov kriterijum je takođe neophodan uslov da se izbegne vanzemaljac, u smislu da ako se uzorci uzimaju sporije od dvostruke granice opsega, postoje neki signali koji neće biti ispravno rekonstruisani. Međutim, ako se u signalu nametnu dodatna ograničenja, onda Nikvistov kriterijum više ne može biti neophodan uslov .

Netrivijalni primer iskorišćavanja dodatnih pretpostavki o signalu dat je u nedavnom polju kompresovanog senzora, koji omogućava potpunu rekonstrukciju sa podNikvistovim uzorkovanjem. To se posebno odnosi na signale koji su retki (ili kompresibilni) u nekom domenu. Kao primer, komprimovano detektovanje bavi se signalima koji mogu imati mali protok preko čitavog opsega (recimo, efektivna širina opsega EB ), ali lokacije frekvencija su nepoznate, pre nego sve zajedno u jednom opsegu, tako da se tehnika propusnog opsega ne primenjuje. Drugim rečima, frekvencijski spektar je mali. Tradicionalno, potrebna stopa uzorkovanja je, dakle, 2B. Korišćenjem tehnika komprimovanog otkrivanja, signal se može savršeno rekonstruisati ako se uzorkuje brzinom manjom od 2 EB . Kod ovog pristupa rekonstrukcija se više ne daje formulom, već rešenjem programa linearne optimizacije .

Drugi primer gde je podNikvistovo uzorkovanje optimalno nastaje pod dodatnim ograničenjem da se uzorci kvantiziraju na optimalan način, kao u kombinovanom sistemu uzorkovanja i optimalnoj kompresiji gubitaka . Ovo podešavanje je relevantno u slučajevima kada treba uzeti u obzir zajednički efekt uzorkovanja i kvantizacije i može pružiti donju granicu za minimalnu grešku rekonstrukcije koja se može postići uzorkovanjem i kvantiziranjem slučajnog signala . Za stacionarne Gausove slučajne signale, ta se donja granica obično postiže brzinom podNikvističkog uzorkovanja, što ukazuje da je podNikvističko uzorkovanje optimalno za ovaj model signala pod optimalnom kvantizacijom .

Istorijska pozadina

Teorema uzorkovanja podrazumevala je rad Harija Nikvista iz 1928. godine, u kojem je pokazao da se do 2B nezavisni impulsni uzorci mogu poslati putem sistema propusne širine B; ali nije izričito razmotrio problem uzorkovanja i rekonstrukcije kontinuiranih signala. Otprilike u isto vreme, Karl Kupfmuler pokazao je sličan rezultat i raspravljao o sink funkciji na impulsni odziv filtera za ograničavanje opsega, preko njegovog integrisanog, sinusnog integrala koraka-odziva; ovaj filtar za ograničavanje i rekonstrukciju, koji je toliko bitan za teoremu uzorkovanja, ponekad se naziva i Kupfmuler filter.

Teorema uzorkovanja, u osnovi dvostruki rezultat Nikuvista, dokazao je Klod E. Šenon . V.A Kotelnikov je objavio slične rezultate 1933, kao i matematičar E.T. Vitaker 1915, J.M. Vitaker 1935, i Gabor 1946 („Teorija komunikacije“). Fondacija Eduard Rajn je 1999. godine Kotelnikovu dodelila nagradu za osnovno istraživanje „za prvu teorijski tačnu formulaciju teoreme o uzorkovanju“.

1948. i 1949. godine, Klod E. Šenon, objavio je - 16 godina posle Vladimira Kotelnikova - dva revolucionarna članka u kojima je osnovao teoriju informacija. Kod Šenona teorema uzorkovanja iz 1948. formulisana je kao „Teorema 13“: Neka f (t) ne sadrži frekvencije preko V. Zatim

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

Tek što su objavljeni ovi članci, teorema poznata kao „Šenonova teorema uzorkovanja“ postala je zajedničko svojstvo među inženjerima komunikacija, mada sam Šenon piše da je to činjenica koja je opšte poznata u komunikacijskoj umetnosti. Ipak, nekoliko redova dalje, on dodaje: „ali uprkos očiglednoj važnosti, izgleda da se on nije eksplicitno pojavio u literaturi teorije komunikacije“.

Ostali pronalazači

O drugim koji su samostalno otkrili ili imali uloge u razvoju teoreme uzorkovanja raspravljali su, na primer, u nekoliko istorijskih članaka, Jeri i Luk. Na primer, Luk ističe da je H. Raabe, asistent Kupfmuler-a, teoremu dokazao u svojoj doktorskoj disertaciji iz 1939. godine; termin Raabe uslovio je da se povezuje sa kriterijumom za nedvosmislenu reprezentaciju (brzina uzorkovanja veća od dvostruke opsega). Mejring u paragrafu i paru fusnota pominje nekoliko drugih pronalazača i imena:

Kao što je ukazao Higins [135], teoremu uzorkovanja zaista treba razmotriti u dva dela, kao što je gore učinjeno: prvi navodi činjenicu da je opsežna funkcija potpuno određena njenim uzorcima, a drugi opisuje kako rekonstruisati funkciju pomoću njenih uzoraka. Oba dela teoreme uzorkovanja dao je u nešto drugačijem obliku J.M. Vitaker [350, 351, 353], a pre njega i Ogura [241, 242]. Oni verovatno nisu bili svesni činjenice da je prvi deo teoreme izjavio Borel još 1897. godine [25]. ²⁷ Kao što smo videli, Borel je u to vreme koristio i ono što je postalo poznato kao kardinalna serija. Međutim, čini se da nije uspostavio vezu [135]. U kasnijim godinama postalo je poznato da je Kotelnikov ruskoj komunikacijskoj zajednici pre Šenona predstavio teoremu o uzorkovanju [173]. U implicitnijem, verbalnom obliku, Raabe je to takođe opisao u nemačkoj literaturi [257]. Nekoliko autora [33, 205] pomenulo je da je Someia [296] uveo teoremu u japansku literaturu paralelno sa Šenonom. U engleskoj literaturi, Veston [347] ga je uveo nezavisno od Šenona otprilike u isto vreme. ²⁸

²⁷ Nekoliko autora, prateći Bleka [16], tvrdi da je ovaj prvi deo teoreme uzorkovanja izjavio Koši još ranije, u radu [41] objavljenom 1841. Međutim, rad Košija ne sadrži takvu izjavu, kako je ukazao Higins [135].

²⁸ Kao posledica otkrića nekoliko nezavisnih uvoda teoreme uzorkovanja, ljudi su počeli da se pozivaju na teoremu uključivanjem imena gore pomenutih autora, što je rezultiralo takvim rečenicama kao "Vitaker-Kotelnikov-Šenonova (VKŠ) teorema uzorkovanja" [155] ili čak „teorema o uzorkovanju Vitaker – Kotelnikov–Raabe– Šenon – Someia“ [33]. Da biste izbegli zabunu, možda je najbolje da se to odnosi na teoremu uzorkovanja, „umesto da se pokušava naći naslov koji bi pravdao svim podnosiocima zahteva“ [136].

Zašto Nikvist?

Tačno kako, kada ili zašto je Hari Nikvist svoje ime prikačio uz teoremu uzorkovanja ostaje nejasno. Izraz Nikvist-Šenonova Teorema (tako velikim slovom) pojavio se već 1959. godine u knjizi njegovog bivšeg poslodavca, Bela Labs, a ponovo se pojavio 1963. godine, i nije upotrebljen velikim slovom 1965. godine. Teoremom Šenonovog uzorkovanja nazvana je već 1954. ali i samo teorema o uzorkovanju u nekoliko drugih knjiga početkom 1950-ih.

Godine 1958, Blekman i Tuki naveli su Nikvistov članak iz 1928. kao referencu za teoremu uzorkovanja teorije informacija , iako taj članak ne tretira uzorkovanje i rekonstrukciju neprekidnih signala kao što su to činili drugi. Njihov glosar pojmova uključuje ove unose:

Teorema uzorkovanja (teorije informacija)

Rezultat Nikvista da izjednačeni podaci, sa dve ili više tačaka po ciklusu najviše frekvencije, omogućavaju rekonstrukciju funkcija ograničenih opsega. (Vidi kardinal teorema. )

Kardinal teorema (o teoriji interpolacije)

Precizna izjava uslova pod kojima se vrednosti date u dvostruko beskonačnom skupu jednako raspoređenih tačaka mogu interpolirati tako da se dobije kontinuirana funkcija ograničena u opsegu uz pomoć funkcije

${\frac {\sin(x-x_{i})}{x-x_{i}}}.$

Tačno ono što nazivaju „Nikvistov rezultat“ ostaje tajanstveno.

Kada je Šenon izjavio i dokazao teoremu uzorkovanja u svom članku iz 1949. godine, prema Mejringu, "on se osvrnuo na kritični interval uzorkovanja $T={\frac {1}{2W}}$ kao interval Nikvista koji odgovara pojasu V, u znak priznanja Nikvistovog otkrića suštinske važnosti ovog intervala u vezi sa telegrafijom ". Ovo objašnjava Nikvistovo ime na kritičnom intervalu, ali ne i na teoremi.

Slično tome, Nikvist-ovo ime je Harold S. Blek pripisao stopi Nikvista 1953. godine:

"Ako je esencijalni frekvencijski opseg ograničen na 'B' 'cikluse u sekundi, Nikvist je dao 2B kao maksimalni broj kodnih elemenata u sekundi koji se mogu nedvosmisleno razrešiti, pretpostavljajući da je vršna interferencija manja od pola kvantni korak. Ova brzina se generalno naziva "signaliziranje na Nikvistovoj stopi" "", a ${\frac {1}{2B}}$ nazvan je "nikvističkim intervalom" "." (podebljano za isticanje; kurziv kao u originalu)"

Prema OED, ovo može biti izvor termina Nikvistove stope . U Blekovoj upotrebi nije brzina uzorkovanja, već brzina signalizacije.

Vidi još

• 44,100 Hz, uobičajena brzina koja se koristi za uzorkovanje zvučnih frekvencija zasniva se na granicama ljudskog sluha i teoremi uzorkovanja
• Balian-Lou teorema, slična teorijska donja granica za brzine uzorkovanja, ali koja se odnosi na vremenske frekvencije transformacija
• Čung–Marksova teorema koja određuje uslove u kojima obnavljanje signala iz teoreme uzorkovanja može postati loše postavljeno
• Hartlijev zakon
• Nikvistov ISI kriterijum
• Rekonstrukcija sa nula prelaza
• Zadržavanje nula

Dodatna literatura

• 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, br. 9 str. 153–160 i 10 str. 178–182, 1931. [1] [2]
• Marks, R.J.(II): Introduction to Shannon Sampling and Interpolation Theory, Springer-Verlag, 1991.
• Marks, R.J.(II), Editor: 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), poglavlja 5-8. Google books
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), „Section 13.11. Numerical Use of the Sampling Theorem”, Numerical Recipes: The Art of Scientific Computing (3rd izd.), New York: Cambridge University Press, ISBN 978-0-521-88068-8, Arhivirano iz originala 11. 08. 2011. g., Pristupljeno 12. 12. 2019 
• Unser, Michael: Sampling-50 Years after Shannon Arhivirano na sajtu Wayback Machine (9. jul 2006), Proc. IEEE, vol. 88, br. 4, str. 569–587, april 2000

Spoljašnje veze

• Učenje pomoću simulacija Interaktivna simulacija efekata neadekvatnog uzorkovanja
• Interaktivna prezentacija uzorkovanja i rekonstrukcije na veb-demo Institutu za telekomunikacije Univerziteta u Štutgartu
• Podvlačenje i njegova primena
• Teorija uzorkovanja za digitalni audio
• Časopis posvećen teoriji uzorkovanja
• Teorema uzorkovanja sa stalnim impulsom promenljive širine impulsa
• Lüke, Hans Dieter (april 1999). „The Origins of the Sampling Theorem” (PDF). IEEE Communications Magazine. 37 (4): 106—108. CiteSeerX 10.1.1.163.2887 . doi:10.1109/35.755459.