Beispiel für die Größe der Fourier-Transformation einer bandbegrenzten Funktion
Das Nyquist-Shannon-Abtasttheorem ist ein Theorem auf dem Gebiet der Signalverarbeitung, das als grundlegende Brücke zwischen zeitkontinuierlichen Signalen und zeitdiskreten Signalen dient. Es schafft eine ausreichende Bedingung für eine Abtastrate, die eine diskrete Folge von erlaubt Proben um alle Informationen aus einem zeitkontinuierlichen Signal endlicher Bandbreite zu erfassen.
Genau genommen gilt der Satz nur für eine Klasse mathematischer Funktionen mit einer Fourier-Transformation, die außerhalb eines endlichen Frequenzbereichs Null ist. Intuitiv erwarten wir, dass die Genauigkeit des Ergebnisses von der Dichte (oder Abtastrate) der ursprünglichen Abtastwerte abhängt, wenn man eine stetige Funktion auf eine diskrete Sequenz reduziert und auf eine stetige Funktion zurückinterpoliert. Das Abtasttheorem führt das Konzept einer Abtastrate ein, die für eine perfekte Wiedergabetreue für die Klasse von Funktionen ausreicht, die auf eine bestimmte Bandbreite bandbegrenzt sind, so dass beim Abtastprozess keine tatsächlichen Informationen verloren gehen. Es drückt die ausreichende Abtastrate in Bezug auf die Bandbreite für die Funktionsklasse aus. Der Satz führt auch zu einer Formel zur perfekten Rekonstruktion der ursprünglichen zeitkontinuierlichen Funktion aus den Proben.
Eine perfekte Rekonstruktion ist möglicherweise immer noch möglich, wenn das Abtastratenkriterium nicht erfüllt ist, sofern andere Einschränkungen des Signals bekannt sind (siehe § Abtastung von Nicht-Basisbandsignalen unten und komprimierte Erfassung). In einigen Fällen (wenn das Abtastratenkriterium nicht erfüllt ist) ermöglicht die Verwendung zusätzlicher Einschränkungen ungefähre Rekonstruktionen. Die Genauigkeit dieser Rekonstruktionen kann unter Verwendung des Bochner-Theorems verifiziert und quantifiziert werden.[1]
Der Name Nyquist-Shannon-Abtasttheorem ehrt Harry Nyquist und Claude Shannon, aber der Satz wurde auch zuvor von ET Whittaker (veröffentlicht 1915) entdeckt und Shannon zitierte Whittakers Artikel in seiner Arbeit. Es wurde auch 1933 von Vladimir Kotelnikov entdeckt. Der Satz ist also auch unter den Namen bekannt Whittaker-Shannon-Stichprobensatz, Nyquist-Shannon-Kotelnikov, Whittaker-Shannon-Kotelnikov, und Whittaker-Nyquist-Kotelnikov-Shannonund kann auch als bezeichnet werden Kardinalsatz der Interpolation.
Table of Contents
Einführung[edit]
Bei der Abtastung wird ein Signal (z. B. eine Funktion der kontinuierlichen Zeit oder des kontinuierlichen Raums) in eine Folge von Werten (eine Funktion der diskreten Zeit oder des diskreten Raums) umgewandelt. Shannons Version des Satzes besagt:[2]
Wenn eine Funktion
Das Symbol T. = 1 /fs wird üblicherweise verwendet, um das Intervall zwischen Abtastwerten darzustellen, und wird als bezeichnet Probezeit oder Abtastintervall. Die Funktionsbeispiele x((t) werden üblicherweise mit bezeichnet x[n] = x((nT) (Alternative “xn” in älterer Signalverarbeitungsliteratur) für alle ganzzahligen Werte von n. Ein mathematisch idealer Weg, um die Sequenz zu interpolieren, beinhaltet die Verwendung von sinc-Funktionen. Jede Probe in der Sequenz wird durch eine sinc-Funktion ersetzt, die auf der Zeitachse am ursprünglichen Ort der Probe zentriert ist. nTmit der Amplitude der sinc-Funktion, die auf den Abtastwert skaliert ist, x[n]. Anschließend werden die sinc-Funktionen zu einer stetigen Funktion summiert. Eine mathematisch äquivalente Methode besteht darin, eine Sinc-Funktion mit einer Reihe von Dirac-Delta-Impulsen zu falten, die mit den Abtastwerten gewichtet sind. Keine der beiden Methoden ist numerisch praktikabel. Stattdessen wird eine Art von Approximation der Sinc-Funktionen mit endlicher Länge verwendet. Die der Annäherung zuzuschreibenden Unvollkommenheiten sind bekannt als Interpolationsfehler.
Praktische Digital-Analog-Wandler erzeugen weder skalierte und verzögerte Sinc-Funktionen noch ideale Dirac-Impulse. Stattdessen erzeugen sie eine stückweise konstante Folge von skalierten und verzögerten Rechteckimpulsen (das Halten nullter Ordnung), gefolgt von einem Tiefpassfilter (genannt als “Anti-Imaging-Filter”) um störende Hochfrequenzrepliken (Bilder) des ursprünglichen Basisbandsignals zu entfernen.
Aliasing[edit]
Die Abtastwerte von zwei Sinuswellen können identisch sein, wenn mindestens eine von ihnen eine Frequenz über der Hälfte der Abtastrate aufweist.
Wann
X.s((f)≜∑k=– –∞∞X.((f– –kfs)=∑n=– –∞∞T.⋅x((nT.)e– –ich2πnT.f,{ displaystyle 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},}
((Gl.1)
Dies ist eine periodische Funktion und ihre äquivalente Darstellung als Fourier-Reihe, deren Koeffizienten sind
T.⋅x((nT.).{ displaystyle T cdot x (nT).}
Diese Funktion wird auch als zeitdiskrete Fourier-Transformation (DTFT) der Abtastsequenz bezeichnet.
Wie abgebildet, Kopien von
X.((f){ displaystyle X (f)}
werden um ein Vielfaches von verschoben
fs{ displaystyle f_ {s}}
und durch Zugabe kombiniert. Für eine bandbegrenzte Funktion
((X.((f)=0, für alle |f|≥B.){ displaystyle (X (f) = 0, { text {für alle}} | f | geq B)}
und ausreichend groß
fs,{ displaystyle f_ {s},}
Es ist möglich, dass die Kopien voneinander verschieden bleiben. Wenn das Nyquist-Kriterium jedoch nicht erfüllt ist, überlappen sich benachbarte Kopien, und es ist im Allgemeinen nicht möglich, eine eindeutige zu erkennen
X.((f).{ displaystyle X (f).}
Beliebige Frequenzkomponente oben
fs/.2{ displaystyle f_ {s} / 2}
ist nicht von einer niederfrequenten Komponente zu unterscheiden, die als bezeichnet wird alias, verbunden mit einer der Kopien. In solchen Fällen erzeugen die üblichen Interpolationstechniken eher den Alias als die ursprüngliche Komponente. Wenn die Abtastrate durch andere Überlegungen (z. B. einen Industriestandard) vorbestimmt ist,
Spektrum, X.s((f) eines ordnungsgemäß abgetasteten bandbegrenzten Signals (blau) und der benachbarten DTFT-Bilder (grün), die sich nicht überlappen. EIN Ziegelwand Tiefpassfilter, H.((f), entfernt die Bilder, verlässt das ursprüngliche Spektrum, X.((f) und stellt das ursprüngliche Signal aus seinen Abtastwerten wieder her.
Die Abbildung links zeigt eine Funktion (in Grau / Schwarz), die mit stetig ansteigenden Probendichten abgetastet und rekonstruiert wird (in Gold), während die Abbildung rechts das Frequenzspektrum der Grau / Schwarz-Funktion zeigt, das sich nicht ändert . Die höchste Frequenz im Spektrum ist ½ der Breite des gesamten Spektrums. Die Breite der stetig zunehmenden rosa Schattierung entspricht der Abtastrate. Wenn es das gesamte Frequenzspektrum umfasst, ist es doppelt so groß wie die höchste Frequenz, und dann stimmt die rekonstruierte Wellenform mit der abgetasteten überein.
Ableitung als Sonderfall der Poisson-Summation[edit]
Wenn es keine Überlappung der Kopien gibt (auch bekannt als “Bilder”) von
X.((f){ displaystyle X (f)}
, das
k=0{ displaystyle k = 0}
Laufzeit von Gl.1 kann durch das Produkt zurückgewonnen werden::
X.((f)=H.((f)⋅X.s((f),{ displaystyle X (f) = H (f) cdot X_ {s} (f),} wo::
H.((f)≜{1|f|<B.0|f|>fs– –B..{ displaystyle H (f) triangleq { begin {case} 1 & | f |f_ {s} -B. end {Fälle}}}X.((f){ displaystyle X (f)} bestimmt eindeutig H.((f){ displaystyle H (f)} müssen in der Region nicht genau definiert werden [B,fs−B]{ displaystyle [B, f_{s}-B]}} weil X.s((f){ displaystyle X_ {s} (f)} ist in dieser Region Null. Der schlimmste Fall ist jedoch, wenn B.=fs/.2,{ displaystyle B = f_ {s} / 2,} die Nyquist-Frequenz. Eine Funktion, die dafür und für alle weniger schweren Fälle ausreicht, ist::
H.((f)=rect((ffs)={1|f|<fs20|f|>fs2,{ displaystyle H (f) = mathrm {rect} left ({ frac {f} {f_ {s}}} right) = { begin {case} 1 & | f |<{frac {f_{s}}{2}}\0&|f|>{ frac {f_ {s}} {2}}, end {Fälle}}}X.((f)=rect((ffs)⋅X.s((f){ displaystyle X (f) = mathrm {rect} left ({ frac {f} {f_ {s}}} right) cdot X_ {s} (f)}
=rect((T.f)⋅∑n=– –∞∞T.⋅x((nT.)e– –ich2πnT.f{ displaystyle = mathrm {rect} (Tf) cdot sum _ {n = – infty} ^ { infty} T cdot x (nT) e ^ {- i2 pi nTf}} (von Gl.1, über).
=∑n=– –∞∞x((nT.)⋅T.⋅rect((T.f)⋅e– –ich2πnT.f⏟F.{sichnc((t– –nT.T.)}}.{ 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 }}.}[A]
Die inverse Transformation beider Seiten ergibt die Whittaker-Shannon-Interpolationsformel::
x((nT.),{ displaystyle x (nT),} kann kombiniert werden, um zu rekonstruieren ∑n=– –∞∞x((nT.)⋅δ((t– –nT.),{ displaystyle textstyle sum _ {n = – infty} ^ { infty} x (nT) cdot delta (t-nT),} Dies ist eine Dirac-Kammfunktion, die durch die Signalabtastungen moduliert wird. Praktische Digital-Analog-Wandler (DAC) implementieren eine Näherung wie das Halten nullter Ordnung. In diesem Fall kann eine Überabtastung den Approximationsfehler verringern.
Shannons Originalbeweis[edit]
Poisson zeigt, dass die Fourier-Reihe in Gl.1 erzeugt die periodische Summation von
X.((f){ displaystyle X (f)}, Egal ob fs{ displaystyle f_ {s}} und B.{ displaystyle B}. Shannon leitet jedoch nur die Serienkoeffizienten für den Fall ab fs=2B.{ displaystyle f_ {s} = 2B}. Shannons Originalarbeit virtuell zitieren:
Lassen X.((ω){ displaystyle X ( omega)} sei das Spektrum von
x((n2B.)=12π∫– –2πB.2πB.X.((ω)eichωn2B.dω.{ 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.}
((Gl.2)
Links sind Werte von xn{ displaystyle x_ {n}} sei der nth Stichprobe. Dann die Funktion Anmerkungen[edit]
^Multiplizieren Sie beide Seiten von Gl.2 durch T.=1/.2B.{ displaystyle T = 1 / 2B} erzeugt links die skalierten Abtastwerte ((T.⋅x((nT.)){ displaystyle (T cdot x (nT))} in Poissons Formel (Gl.1) und rechts die tatsächliche Formel für Fourier-Expansionskoeffizienten.
Anwendung auf multivariable Signale und Bilder[edit]
Der Abtastsatz wird normalerweise für Funktionen einer einzelnen Variablen formuliert. Folglich ist der Satz direkt auf zeitabhängige Signale anwendbar und wird normalerweise in diesem Zusammenhang formuliert. Der Abtastsatz kann jedoch auf einfache Weise auf Funktionen beliebig vieler Variablen erweitert werden. Graustufenbilder werden beispielsweise häufig als zweidimensionale Anordnungen (oder Matrizen) von reellen Zahlen dargestellt, die die relativen Intensitäten von Pixeln (Bildelementen) darstellen, die sich an den Schnittpunkten von Zeilen- und Spaltenprobenpositionen befinden. Daher benötigen Bilder zwei unabhängige Variablen oder Indizes, um jedes Pixel eindeutig anzugeben – eine für die Zeile und eine für die Spalte.
Farbbilder bestehen normalerweise aus drei separaten Graustufenbildern, von denen eines jede der drei Grundfarben Rot, Grün und Blau oder darstellt RGB kurz gesagt. Andere Farbräume, die 3-Vektoren für Farben verwenden, umfassen HSV, CIELAB, XYZ usw. Einige Farbräume wie Cyan, Magenta, Gelb und Schwarz (CMYK) können Farbe in vier Dimensionen darstellen. Alle diese Funktionen werden als vektorwertige Funktionen über eine zweidimensional abgetastete Domäne behandelt.
Ähnlich wie eindimensionale zeitdiskrete Signale können Bilder auch unter Aliasing leiden, wenn die Abtastauflösung oder Pixeldichte unzureichend ist. Beispielsweise kann ein digitales Foto eines gestreiften Hemdes mit hohen Frequenzen (mit anderen Worten, der Abstand zwischen den Streifen ist gering) ein Aliasing des Hemdes verursachen, wenn es vom Bildsensor der Kamera abgetastet wird. Das Aliasing erscheint als Moiré-Muster. Das “Lösung” Eine höhere Abtastung im räumlichen Bereich würde in diesem Fall bedeuten, näher an das Hemd heranzukommen, einen Sensor mit höherer Auflösung zu verwenden oder das Bild optisch zu verwischen, bevor es mit dem Sensor unter Verwendung eines optischen Tiefpassfilters aufgenommen wird.
Ein weiteres Beispiel ist rechts in den Ziegelmustern dargestellt. Das obere Bild zeigt die Auswirkungen, wenn die Bedingung des Abtasttheorems nicht erfüllt ist. Wenn die Software ein Bild neu skaliert (der gleiche Vorgang, bei dem das im unteren Bild gezeigte Miniaturbild erstellt wird), führt es das Bild tatsächlich zuerst durch einen Tiefpassfilter und tastet das Bild dann herunter, um ein kleineres Bild zu erhalten, das das Bild nicht aufweist Moiré-Muster. Das obere Bild ist das, was passiert, wenn das Bild ohne Tiefpassfilterung heruntergesampelt wird: Aliasing-Ergebnisse.
Das Abtasttheorem gilt für Kamerasysteme, bei denen die Szene und das Objektiv eine analoge räumliche Signalquelle darstellen und der Bildsensor eine räumliche Abtastvorrichtung ist. Jede dieser Komponenten ist durch eine Modulationsübertragungsfunktion (MTF) gekennzeichnet, die die genaue Auflösung (räumliche Bandbreite) darstellt, die in dieser Komponente verfügbar ist. Aliasing- oder Unschärfeeffekte können auftreten, wenn die Linsen-MTF und die Sensor-MTF nicht übereinstimmen. Wenn das optische Bild, das von der Sensorvorrichtung abgetastet wird, höhere Ortsfrequenzen als der Sensor enthält, wirkt die Unterabtastung als Tiefpassfilter, um Aliasing zu reduzieren oder zu beseitigen. Wenn der Bereich des Abtastpunkts (die Größe des Pixelsensors) nicht groß genug ist, um ein ausreichendes räumliches Anti-Aliasing bereitzustellen, kann ein separates Anti-Aliasing-Filter (optisches Tiefpassfilter) in einem Kamerasystem enthalten sein, um das zu reduzieren MTF des optischen Bildes. Anstatt einen optischen Filter zu benötigen, führt die Grafikverarbeitungseinheit von Smartphone-Kameras eine digitale Signalverarbeitung durch, um Aliasing mit einem digitalen Filter zu entfernen. Digitale Filter wenden auch eine Schärfung an, um den Kontrast von der Linse bei hohen Ortsfrequenzen zu verstärken, der ansonsten bei Beugungsgrenzen schnell abfällt.
Das Abtasttheorem gilt auch für die Nachbearbeitung digitaler Bilder, beispielsweise für die Aufwärts- oder Abwärtsabtastung. Die Auswirkungen von Aliasing, Unschärfe und Schärfen können durch in Software implementierte digitale Filterung angepasst werden, die notwendigerweise den theoretischen Prinzipien folgt.
Kritische Häufigkeit[edit]
Um die Notwendigkeit von zu veranschaulichen
fs>2B.{ displaystyle f_ {s}> 2B}θ{ displaystyle theta} in dieser Formel::
fs=2B.{ displaystyle f_ {s} = 2B} oder gleichwertig T.=1/.2B.{ displaystyle T = 1 / 2B}sind die Proben gegeben durch::
x((nT.)=cos((πn)– –Sünde((πn)⏟0bräunen((θ)=((– –1)n{ displaystyle x (nT) = cos ( pi n) – underbrace { sin ( pi n)} _ {0} tan ( theta) = (- 1) ^ {n}}
unabhängig vom Wert von
θ{ displaystyle theta}. Diese Art von Mehrdeutigkeit ist der Grund für die streng Ungleichung der Bedingung des Abtasttheorems.
Abtastung von Nicht-Basisbandsignalen[edit]
Wie von Shannon besprochen:[2]
Ein ähnliches Ergebnis ist wahr, wenn das Band nicht bei einer Frequenz von Null beginnt, sondern bei einem höheren Wert, und kann durch eine lineare Translation (die physikalisch einer Einseitenbandmodulation entspricht) des Nullfrequenzfalls bewiesen werden. In diesem Fall wird der Elementarimpuls aus sin erhalten (x) /x durch einseitige Bandmodulation.
Das heißt, es besteht eine ausreichende verlustfreie Bedingung zum Abtasten von Signalen, die keine Basisbandkomponenten aufweisen, an denen das beteiligt ist Breite des Frequenzintervalls ungleich Null im Gegensatz zu seiner höchsten Frequenzkomponente. Sehen Abtastung (Signalverarbeitung) Weitere Details und Beispiele.
Um beispielsweise die FM-Radiosignale im Frequenzbereich von 100–102 MHz abzutasten, ist es nicht erforderlich, mit 204 MHz (der doppelten oberen Frequenz) abzutasten, sondern es ist ausreichend, mit 4 MHz (der doppelten Frequenz) abzutasten Breite des Frequenzintervalls).
Eine Bandpassbedingung ist das X.((f) = 0 für alle nichtnegativen f außerhalb des offenen Frequenzbandes:
((N.2fs,N.+12fs),{ displaystyle left ({ frac {N} {2}} f _ { mathrm {s}}, { frac {N + 1} {2}} f _ { mathrm {s}} right),}
für eine nichtnegative ganze Zahl N.. Diese Formulierung enthält den normalen Basisbandzustand N.= 0.
Die entsprechende Interpolationsfunktion ist die Impulsantwort eines idealen Brick-Wall-Bandpassfilters (im Gegensatz zu dem oben verwendeten idealen Brick-Wall-Tiefpassfilter) mit Cutoffs am oberen und unteren Rand des angegebenen Bandes, was die Differenz zwischen einem Paar darstellt von Tiefpass-Impulsantworten:
Andere Verallgemeinerungen, beispielsweise auf Signale, die mehrere nicht zusammenhängende Bänder belegen, sind ebenfalls möglich. Selbst die allgemeinste Form des Stichprobensatzes hat keine nachweislich wahre Umkehrung. Das heißt, man kann nicht schließen, dass Informationen notwendigerweise verloren gehen, nur weil die Bedingungen des Abtasttheorems nicht erfüllt sind; Aus technischer Sicht ist jedoch im Allgemeinen davon auszugehen, dass Informationen höchstwahrscheinlich verloren gehen, wenn der Stichprobensatz nicht erfüllt ist.
Ungleichmäßige Probenahme[edit]
Die Stichprobentheorie von Shannon kann für den Fall einer ungleichmäßigen Stichprobe verallgemeinert werden, d. H. Stichproben, die nicht zeitlich gleich verteilt entnommen wurden. Die Shannon-Abtasttheorie für ungleichmäßige Abtastung besagt, dass ein bandbegrenztes Signal aus seinen Abtastwerten perfekt rekonstruiert werden kann, wenn die durchschnittliche Abtastrate die Nyquist-Bedingung erfüllt.[3] Obwohl gleichmäßig beabstandete Proben zu einfacheren Rekonstruktionsalgorithmen führen können, ist dies daher keine notwendige Bedingung für eine perfekte Rekonstruktion.
Die allgemeine Theorie für nicht-basische und ungleichmäßige Proben wurde 1967 von Henry Landau entwickelt.[4] Er bewies, dass die durchschnittliche Abtastrate (einheitlich oder anderweitig) doppelt so hoch sein muss belegt Bandbreite des Signals, vorausgesetzt es ist a priori bekannt, welcher Teil des Spektrums besetzt war. In den späten 1990er Jahren wurde diese Arbeit teilweise erweitert, um Signale abzudecken, wann die Menge der belegten Bandbreite bekannt war, aber der tatsächlich belegte Teil des Spektrums war unbekannt.[5] In den 2000er Jahren wurde eine vollständige Theorie (siehe Abschnitt Probenahme unterhalb der Nyquist-Rate unter zusätzlichen Einschränkungen unten) unter Verwendung der komprimierten Abtastung entwickelt. Insbesondere wird die Theorie unter Verwendung der Signalverarbeitungssprache in diesem Artikel von 2009 beschrieben.[6] Sie zeigen unter anderem, dass bei unbekannten Frequenzorten mindestens das Doppelte der Nyquist-Kriterien abgetastet werden muss; Mit anderen Worten, Sie müssen mindestens den Faktor 2 bezahlen, wenn Sie den Ort des Spektrums nicht kennen. Beachten Sie, dass Mindestanforderungen an die Probenahme nicht unbedingt die Stabilität garantieren.
Probenahme unterhalb der Nyquist-Rate unter zusätzlichen Einschränkungen[edit]
Das Nyquist-Shannon-Abtasttheorem bietet eine ausreichende Bedingung für die Abtastung und Rekonstruktion eines bandbegrenzten Signals. Wenn die Rekonstruktion über die Whittaker-Shannon-Interpolationsformel erfolgt, ist das Nyquist-Kriterium auch eine notwendige Bedingung, um ein Aliasing zu vermeiden richtig rekonstruiert werden. Wenn dem Signal jedoch weitere Einschränkungen auferlegt werden, ist das Nyquist-Kriterium möglicherweise keine notwendige Bedingung mehr.
Ein nicht triviales Beispiel für die Ausnutzung zusätzlicher Annahmen über das Signal ist das neuere Feld der komprimierten Abtastung, das eine vollständige Rekonstruktion mit einer Sub-Nyquist-Abtastrate ermöglicht. Dies gilt insbesondere für Signale, die in einem bestimmten Bereich spärlich (oder komprimierbar) sind. Beispielsweise befasst sich die komprimierte Abtastung mit Signalen, die eine geringe Gesamtbandbreite aufweisen können (z Wirksam Bandbreite EB), aber die Frequenzorte sind unbekannt und nicht alle zusammen in einem einzigen Band, so dass die Durchlassbandtechnik nicht angewendet wird. Mit anderen Worten ist das Frequenzspektrum spärlich. Traditionell beträgt die erforderliche Abtastrate somit 2B.. Unter Verwendung komprimierter Sensortechniken könnte das Signal perfekt rekonstruiert werden, wenn es mit einer Rate abgetastet wird, die etwas niedriger als 2 istEB. Bei diesem Ansatz wird die Rekonstruktion nicht mehr durch eine Formel gegeben, sondern durch die Lösung eines linearen Optimierungsprogramms.
Ein weiteres Beispiel, bei dem die Sub-Nyquist-Abtastung optimal ist, ergibt sich unter der zusätzlichen Einschränkung, dass die Abtastungen optimal quantisiert werden, wie in einem kombinierten System aus Abtastung und optimaler verlustbehafteter Komprimierung.[7] Diese Einstellung ist in Fällen relevant, in denen der gemeinsame Effekt von Abtastung und Quantisierung berücksichtigt werden soll, und kann eine Untergrenze für den minimalen Rekonstruktionsfehler liefern, der beim Abtasten und Quantisieren eines Zufallssignals erreicht werden kann. Für stationäre Gaußsche Zufallssignale wird diese Untergrenze normalerweise mit einer Sub-Nyquist-Abtastrate erreicht, was darauf hinweist, dass die Sub-Nyquist-Abtastung für dieses Signalmodell bei optimaler Quantisierung optimal ist.[8]
Historischer Hintergrund[edit]
Der Stichprobensatz wurde durch die Arbeit von Harry Nyquist im Jahr 1928 impliziert,[9] in dem er das bis zu 2 zeigteB. Unabhängige Impulsproben könnten durch ein Bandbreitensystem gesendet werden B.;; Das Problem der Abtastung und Rekonstruktion kontinuierlicher Signale wurde jedoch nicht explizit berücksichtigt. Etwa zur gleichen Zeit zeigte Karl Küpfmüller ein ähnliches Ergebnis[10] und diskutierte die Impulsantwort der Sinc-Funktion eines bandbegrenzenden Filters über sein Integral, das Sinusintegral mit Sprungantwort; Dieses Bandlimitierungs- und Rekonstruktionsfilter, das für den Abtastsatz so zentral ist, wird manchmal als bezeichnet Küpfmüller Filter (aber selten so auf Englisch).
Der Stichprobensatz, im Wesentlichen ein Dual von Nyquists Ergebnis, wurde von Claude E. Shannon bewiesen.[2]VA Kotelnikov veröffentlichte ähnliche Ergebnisse im Jahr 1933,[11] ebenso wie der Mathematiker ET Whittaker im Jahr 1915,[12] JM Whittaker im Jahr 1935,[13] und Gabor im Jahr 1946 (“Theorie der Kommunikation”). 1999 verlieh die Eduard-Rhein-Stiftung Kotelnikov den Preis für Grundlagenforschung “für die erste theoretisch genaue Formulierung des Stichprobensatzes”.
In den Jahren 1948 und 1949 veröffentlichte Claude E. Shannon – 16 Jahre nach Vladimir Kotelnikov – die beiden revolutionären Artikel, in denen er die Informationstheorie begründete.[14][15][2] In Shannon 1948 wird der Stichprobensatz als „Satz 13“ formuliert: Let f((t) enthalten keine Frequenzen über W. Dann
Andere Entdecker[edit]
Andere, die unabhängig voneinander eine Rolle bei der Entwicklung des Stichprobensatzes entdeckt oder gespielt haben, wurden in mehreren historischen Artikeln diskutiert, beispielsweise von Jerri[16] und von Lüke.[17] Zum Beispiel weist Lüke darauf hin, dass H. Raabe, ein Assistent von Küpfmüller, den Satz in seiner Doktorarbeit von 1939 bewiesen hat. Dissertation; der Begriff Raabe Zustand wurde mit dem Kriterium der eindeutigen Darstellung in Verbindung gebracht (Abtastrate größer als die doppelte Bandbreite). Meijering[18] erwähnt mehrere andere Entdecker und Namen in einem Absatz und zwei Fußnoten:
Wie von Higgins hervorgehoben [135]Das Abtasttheorem sollte wirklich in zwei Teilen betrachtet werden, wie oben ausgeführt: Der erste besagt, dass eine bandbegrenzte Funktion vollständig durch ihre Abtastwerte bestimmt wird, der zweite beschreibt, wie die Funktion unter Verwendung ihrer Abtastwerte rekonstruiert wird. Beide Teile des Stichprobensatzes wurden von JM Whittaker in etwas anderer Form angegeben [350, 351, 353] und vor ihm auch von Ogura [241, 242]. Sie waren sich wahrscheinlich nicht bewusst, dass der erste Teil des Satzes bereits 1897 von Borel angegeben worden war [25].27 Wie wir gesehen haben, verwendete Borel zu dieser Zeit auch die sogenannte Kardinalserie. Er scheint den Link jedoch nicht hergestellt zu haben [135]. In späteren Jahren wurde bekannt, dass Kotel’nikov der russischen Kommunikationsgemeinschaft den Stichprobensatz vor Shannon vorgestellt hatte [173]. In impliziterer, verbaler Form war es auch in der deutschen Literatur von Raabe beschrieben worden [257]. Mehrere Autoren [33, 205] habe erwähnt, dass Someya [296] führte den Satz in der japanischen Literatur parallel zu Shannon ein. In der englischen Literatur Weston [347] führte es ungefähr zur gleichen Zeit unabhängig von Shannon ein.28
27 Mehrere Autoren folgen Black [16]haben behauptet, dass dieser erste Teil des Stichprobensatzes noch früher von Cauchy in einem Artikel angegeben wurde [41] veröffentlicht im Jahr 1841. Das Papier von Cauchy enthält jedoch keine solche Aussage, wie von Higgins hervorgehoben wurde [135].
28 Infolge der Entdeckung der verschiedenen unabhängigen Einführungen des Stichprobensatzes begannen die Menschen, sich auf den Satz zu beziehen, indem sie die Namen der oben genannten Autoren einfügten, was zu Schlagworten wie „Whittaker-Kotel’nikov-Shannon (WKS) -Stichprobe“ führte Satz” [155] oder auch “der Whittaker-Kotel’nikov-Raabe-Shannon-Someya-Stichprobensatz” [33]. Um Verwirrung zu vermeiden, ist es vielleicht das Beste, sie als Stichprobensatz zu bezeichnen. “anstatt zu versuchen, einen Titel zu finden, der allen Antragstellern gerecht wird” [136].
Warum Nyquist?[edit]
Wie, wann oder warum Harry Nyquist seinen Namen an den Stichprobensatz angehängt hat, bleibt unklar. Der Begriff Nyquist Sampling Theorem (so groß geschrieben) erschien bereits 1959 in einem Buch seines früheren Arbeitgebers Bell Labs,[19] und erschien 1963 erneut,[20] und 1965 nicht aktiviert.[21] Es war das genannt worden Shannon Sampling Theorem bereits 1954,[22] aber auch nur der Abtastsatz von mehreren anderen Büchern in den frühen 1950er Jahren.
1958 zitierten Blackman und Tukey Nyquists Artikel von 1928 als Referenz für der Stichprobensatz der Informationstheorie,[23] obwohl dieser Artikel die Abtastung und Rekonstruktion kontinuierlicher Signale nicht wie andere behandelt. Ihr Glossar enthält folgende Einträge:
Stichprobensatz (der Informationstheorie)
Nyquists Ergebnis, dass Daten mit gleichem Abstand und zwei oder mehr Punkten pro Zyklus mit der höchsten Frequenz die Rekonstruktion bandbegrenzter Funktionen ermöglichen. (Sehen Kardinalsatz.)
Kardinalsatz (der Interpolationstheorie)
Eine genaue Angabe der Bedingungen, unter denen Werte, die an einem doppelt unendlichen Satz von Punkten mit gleichem Abstand angegeben sind, interpoliert werden können, um mit Hilfe der Funktion eine kontinuierliche bandbegrenzte Funktion zu erhalten
Genau was “Nyquists Ergebnis” sie beziehen sich auf bleibt mysteriös.
Als Shannon laut Meijering den Stichprobensatz in seinem Artikel von 1949 feststellte und bewies,[18] “er bezog sich auf das kritische Abtastintervall
T.=12W.{ displaystyle T = { frac {1} {2W}}} als die Nyquist-Intervall entsprechend der Band W.in Anerkennung von Nyquists Entdeckung der grundlegenden Bedeutung dieses Intervalls im Zusammenhang mit der Telegraphie”. Dies erklärt Nyquists Namen im kritischen Intervall, aber nicht im Theorem.
Ebenso wurde Nyquists Name angehängt Nyquist Rate 1953 von Harold S. Black:
“Wenn der wesentliche Frequenzbereich auf begrenzt ist B. Zyklen pro Sekunde, 2B. wurde von Nyquist als die maximale Anzahl von Codeelementen pro Sekunde angegeben, die eindeutig aufgelöst werden konnten, vorausgesetzt, die Spitzeninterferenz beträgt weniger als einen halben Quantenschritt. Diese Rate wird allgemein als bezeichnet Signalisierung mit der Nyquist-Rate und
12B.{ displaystyle { frac {1} {2B}}}
wurde als a bezeichnet Nyquist-Intervall.”[24] (zur Hervorhebung fett gedruckt; kursiv wie im Original)
Laut OED kann dies der Ursprung des Begriffs sein Nyquist Rate. Bei der Verwendung von Black handelt es sich nicht um eine Abtastrate, sondern um eine Signalisierungsrate.
Siehe auch[edit]
Verweise[edit]
^Nemirovsky, Jonathan; Shimron, Efrat (2015). “Verwendung des Bochners-Theorems zur eingeschränkten Auswertung fehlender Fourier-Daten”. arXiv:1506.03300 [physics.med-ph].
^siehe zB Feng, P. (1997). Universelle Abtastung mit minimaler Rate und spektrumblinde Rekonstruktion für Multiband-Signale. Ph.D. Dissertation, Universität von Illinois in Urbana-Champaign.
^Kipnis, Alon; Goldsmith, Andrea J.; Eldar, Yonina C.; Weissman, Tsachy (Januar 2016). “Verzerrungsratenfunktion von Sub-Nyquist-abgetasteten Gaußschen Quellen”. IEEE-Transaktionen zur Informationstheorie. 62: 401–429. arXiv:1405.5329. doi:10.1109 / tit.2015.2485271.
^Kipnis, Alon; Eldar, Yonina; Goldschmied, Andrea (26. April 2018). “Analog-Digital-Komprimierung: Ein neues Paradigma für die Umwandlung von Signalen in Bits”. IEEE Signal Processing Magazine. 35 (3): 16–39. arXiv:1801.06718. Bibcode:2018ISPM … 35 … 16K. doi:10.1109 / MSP.2017.2774249. S2CID 13693437.
^Küpfmüller, Karl (1928). “Über die Dynamik der selbsttätigen Beförderungsregler”. Elektrische Nachrichtentechnik (auf Deutsch). 5 (11): 459–467. (Englische Übersetzung 2005).
^Kotelnikov, VA (1933). “Über die Tragfähigkeit von Äther und Draht in der Telekommunikation”. Material für die erste All-Union-Konferenz zu Kommunikationsfragen, Izd. Rot. Upr. Svyazi RKKA (auf Russisch). (Englische Übersetzung, PDF).
^Jerri, Abdul (November 1977). “Das Shannon-Sampling-Theorem – seine verschiedenen Erweiterungen und Anwendungen: Ein Tutorial Review”. Verfahren des IEEE. 65 (11): 1565–1596. doi:10.1109 / proc.1977.10771. S2CID 37036141. Siehe auch Jerri, Abdul (April 1979). “Korrektur zu “Das Shannon-Sampling-Theorem – Seine verschiedenen Erweiterungen und Anwendungen: Ein Tutorial-Review““. Verfahren des IEEE. 67 (4): 695. doi:10.1109 / proc.1979.11307.
Higgins, JR: Fünf Kurzgeschichten über die Kardinalserie, Bulletin des AMS 12 (1985)
Küpfmüller, Karl, “Utjämningsförlopp inom Telegrafoch Telefontekniken”, (“Transienten in der Telegraphen- und Telefontechnik”), Teknisk Tidskrift, Nr. 9 S. 153–160 und 10 S. 178–182, 1931. [1][2]
Marks, RJ (II), Handbuch der Fourier-Analyse und ihrer Anwendungen, Oxford University Press, (2009), Kapitel 5–8. Google Bücher
Drücken Sie, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), “Abschnitt 13.11. Numerische Verwendung des Abtastsatzes”, Numerische Rezepte: Die Kunst des wissenschaftlichen Rechnens (3. Aufl.), New York: Cambridge University Press, ISBN 978-0-521-88068-8
Recent Comments