Теорема выборки Найквиста – Шеннона

Не путать с теоремой Шеннона–Хартли .

Теорема выборки Найквиста -Шеннона является важным принципом цифровой обработки сигналов, связывающим диапазон частот сигнала и частоту дискретизации , необходимую для предотвращения типа искажения , называемого наложением спектров . Теорема утверждает, что частота дискретизации должна быть как минимум в два раза больше полосы пропускания сигнала, чтобы избежать наложения спектров. На практике он используется для выбора фильтров ограничения полосы , чтобы наложение спектров оставалось ниже приемлемого уровня при дискретизации аналогового сигнала или при изменении частоты дискретизации в функции цифровой обработки сигнала.

Пример величины преобразования Фурье функции с ограниченной полосой пропускания

Теорема выборки Найквиста-Шеннона — это теорема в области обработки сигналов , которая служит фундаментальным мостом между сигналами с непрерывным временем и сигналами с дискретным временем . Он устанавливает достаточное условие для частоты дискретизации , которая позволяет дискретной последовательности выборок захватывать всю информацию из непрерывного сигнала с конечной полосой пропускания .

Строго говоря, теорема применима только к классу математических функций , преобразование Фурье которых равно нулю вне конечной области частот. Интуитивно мы ожидаем, что когда кто-то сводит непрерывную функцию к дискретной последовательности и интерполирует обратно к непрерывной функции, точность результата зависит от плотности (или частоты дискретизации ) исходных выборок. Теорема о выборке вводит концепцию частоты дискретизации, достаточной для идеальной точности для класса функций, полоса которых ограничена заданной полосой пропускания, так что никакая фактическая информация не теряется в процессе выборки. Он выражает достаточную частоту дискретизации через полосу пропускания для класса функций. Теорема также приводит к формуле для идеального восстановления исходной функции непрерывного времени по выборкам.

Идеальная реконструкция все еще возможна, если критерий частоты дискретизации не удовлетворен, при условии, что известны другие ограничения на сигнал (см. § Выборка немодульных сигналов ниже и сжатое измерение ). В некоторых случаях (когда критерий частоты дискретизации не удовлетворяется) использование дополнительных ограничений позволяет провести приблизительную реконструкцию. Точность этих реконструкций можно проверить и количественно оценить с помощью теоремы Бохнера .

Название «Теорема выборки Найквиста-Шеннона» дано в честь Гарри Найквиста и Клода Шеннона , но эта теорема также была ранее открыта Э. Т. Уиттакером (опубликовано в 1915 году), и Шеннон цитировал статью Уиттекера в своей работе. Таким образом, теорема также известна под названиями: теорема выборки Уиттекера-Шеннона , Уиттакера-Шеннона и Уиттакера-Найквиста-Шеннона , и ее также можно назвать кардинальной теоремой интерполяции .

Введение

Выборка — это процесс преобразования сигнала (например, функции непрерывного времени или пространства) в последовательность значений (функцию дискретного времени или пространства). Шеннона гласит: Версия теоремы

Теорема . Если функция $x(t)$ не содержит частот выше B   герц , то ее можно полностью определить по ее ординатам в последовательности точек, отстоящих друг от друга менее $1/(2B)$ секунды с разницей.

Таким образом, достаточная частота дискретизации — это что-то большее, чем $2B$ выборок в секунду. Эквивалентно, для данной частоты дискретизации $f_{s}$, идеальная реконструкция гарантированно возможна для предела полосы пропускания $B<f_{s}/2$.

Когда предел полосы слишком высок (или предел полосы отсутствует), реконструкция демонстрирует недостатки, известные как наложение спектров . Современные формулировки теоремы иногда стараются явно заявить, что $x(t)$ не должно содержать синусоидальной составляющей точно на частоте $B,$ или что $B$ должно быть строго меньше половины частоты дискретизации. Порог $2B$ называется скоростью Найквиста и является атрибутом входных данных непрерывного времени. $x(t)$ быть отобранным. Частота выборки должна превышать частоту Найквиста, чтобы выборок было достаточно для представления $x(t).$ Порог $f_{s}/2$ называется частотой Найквиста и является атрибутом оборудования для отбора проб . Все значимые частотные компоненты правильно дискретизированного $x(t)$ существуют ниже частоты Найквиста. Условие, описываемое этими неравенствами, называется критерием Найквиста или иногда условием Раабе . Теорема также применима к функциям других областей, например пространства, в случае оцифрованного изображения. Единственное изменение в случае других областей — это единицы измерения, приписываемые $t,$ $f_{s},$ и $B.$

Нормализованная функция sinc : sin(π x ) / (π x ) ... показывающая центральный пик при x = 0 и переходы через нуль при других целочисленных значениях x .

Символ $T\triangleq 1/f_{s}$ обычно используется для обозначения интервала между выборками и называется периодом выборки или интервалом выборки . Образцы функций $x(t)$ обычно обозначаются $x[n]\triangleq T\cdot x(nT)$ (альтернативно $x_{n}$ в более старой литературе по обработке сигналов), для всех целочисленных значений $n.$ $T$ множитель является результатом перехода от непрерывного времени к дискретному времени (см. Discrete-time_Fourier_transform#Relation_to_Fourier_Transform ), и он сохраняет энергию сигнала как $T$ варьируется.

Математически идеальный способ интерполяции последовательности предполагает использование функций sinc . Каждая выборка в последовательности заменяется функцией sinc, центрированной на оси времени в исходном местоположении выборки. $nT,$ с амплитудой функции sinc, масштабированной до значения выборки, $x(nT).$ Впоследствии функции sinc суммируются в непрерывную функцию. Математически эквивалентный метод использует гребенку Дирака и осуществляется путем свертки одной функции sinc с серией дельта-импульсов Дирака , взвешенных по значениям выборки. Ни один из методов не является практичным с численной точки зрения. Вместо этого используется некоторый тип аппроксимации функций sinc конечной длины. Несовершенства, связанные с аппроксимацией, известны как ошибка интерполяции .

Практические цифро-аналоговые преобразователи не производят ни масштабируемых функций с задержкой синхроимпульсов , ни идеальных импульсов Дирака . Вместо этого они создают кусочно-постоянную последовательность масштабированных и задержанных прямоугольных импульсов ( удержание нулевого порядка ), за которыми обычно следует фильтр нижних частот (называемый «фильтром против изображения») для удаления ложных высокочастотных реплик (изображений) исходный основной сигнал.

Псевдонимы

Основная статья: Псевдонимы

Выборки двух синусоид могут быть идентичными, если хотя бы одна из них имеет частоту выше половины частоты дискретизации.

Когда $x(t)$ — функция с преобразованием Фурье $X(f)$:

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

Затем образцы, $x[n],$ из $x(t)$ достаточны для создания периодического суммирования $X(f).$ (см. Discrete-time_Fourier_transform#Relation_to_Fourier_Transform ) :

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

$X(f)$ (верхний синий) и $X_{A}(f)$ (внизу синий) — непрерывные преобразования Фурье двух разных функций, $x(t)$ и $x_{A}(t)$ (не показано). Когда функции выбираются со скоростью $f_{s}$, изображения (зеленые) добавляются к исходным преобразованиям (синие) при анализе преобразований Фурье в дискретном времени (DTFT) последовательностей. В этом гипотетическом примере DTFT идентичны, что означает, что выбранные последовательности идентичны , хотя исходные непрерывные предварительно выбранные функции не являются таковыми. Если бы это были звуковые сигналы, $x(t)$ и $x_{A}(t)$ может звучать не так. Но их образцы (взятые по курсу $f_{s}$) идентичны и приводят к идентичным воспроизводимым звукам; таким образом $x_{A}(t)$ это псевдоним $x(t)$ при этой частоте выборки.

которая является периодической функцией и ее эквивалентным представлением в виде ряда Фурье , коэффициенты которого равны $x[n]$. Эта функция также известна как преобразование Фурье дискретного времени (DTFT) последовательности выборок.

Как показано на рисунке, копии $X(f)$ сдвигаются на кратную частоту дискретизации $f_{s}=1/T$ и объединяются сложением. Для функции с ограниченным диапазоном частот $(X(f)=0,{\text{ for all }}|f|\geq B)$ и достаточно большой $f_{s},$ копии могут оставаться отличными друг от друга. Но если критерий Найквиста не выполняется, соседние копии перекрываются, и в общем случае невозможно выделить однозначную $X(f).$ Любая частотная составляющая выше $f_{s}/2$ неотличим от низкочастотной составляющей, называемой псевдонимом , связанной с одной из копий. В таких случаях обычные методы интерполяции создают псевдоним, а не исходный компонент. Когда частота дискретизации заранее определена другими соображениями (например, отраслевым стандартом), $x(t)$ перед дискретизацией обычно фильтруется, чтобы снизить высокие частоты до приемлемого уровня. Тип требуемого фильтра — фильтр нижних частот , и в данном приложении он называется фильтром сглаживания .

Спектр, $X_{s}(f)$, правильно дискретизированного сигнала с ограниченной полосой пропускания (синий) и соседних изображений DTFT (зеленый), которые не перекрываются. Фильтр с кирпичной стеной , нижних частот $H(f)$, удаляет изображения, оставляет исходный спектр, $X(f)$и восстанавливает исходный сигнал из его выборок.

На рисунке слева показана функция (серым/черным), которая подвергается выборке и восстановлению (золотом) при постоянно увеличивающейся плотности выборки, а на рисунке справа показан частотный спектр функции серого/черного цвета, который не меняется. . Самая высокая частота спектра составляет половину ширины всего спектра. Ширина постоянно увеличивающейся розовой заливки равна частоте дискретизации. Когда он охватывает весь частотный спектр, он в два раза больше самой высокой частоты, и тогда восстановленная форма сигнала соответствует дискретизированной.

Вывод как частный случай суммирования Пуассона

Когда нет перекрытия копий (также известных как «изображения») $X(f)$, $k=0$ член уравнения 1 может быть восстановлен произведением:

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

где:

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

Теорема выборки доказана, поскольку $X(f)$ однозначно определяет $x(t)$.

Остается только вывести формулу реконструкции. $H(f)$ нет необходимости точно определять регион $[B,\ f_{s}-B]$ потому что $X_{1/T}(f)$ в этой области равен нулю. Однако худший случай — это когда $B=f_{s}/2,$ частота Найквиста. Функция, достаточная для этого и во всех менее серьезных случаях :

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

где $\mathrm {rect}$ — прямоугольная функция . Поэтому:

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

$=\mathrm {rect} (Tf)\cdot \sum _{n=-\infty }^{\infty }T\cdot x(nT)\ e^{-i2\pi nTf}$ (из уравнения 1 выше).

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

Обратное преобразование обеих сторон дает интерполяционную формулу Уиттекера-Шеннона :

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

где показано, как образцы, $x(nT)$, можно объединить для реконструкции $x(t)$.

• Значения, превышающие необходимые значения $f_{s}$ (меньшие значения $T$), называемая передискретизацией , не влияет на результат реконструкции и оставляет место для полосы перехода , в которой $H(f)$ свободно принимать промежуточные значения. Недостаточная выборка , вызывающая псевдонимы, в целом не является обратимой операцией.
• Теоретически формулу интерполяции можно реализовать в виде фильтра нижних частот , импульсная характеристика которого равна $\mathrm {sinc} (t/T)$ и чей вход $\textstyle \sum _{n=-\infty }^{\infty }x(nT)\cdot \delta (t-nT),$ которая представляет собой гребенчатую функцию Дирака , модулированную выборками сигнала. Практические цифро-аналоговые преобразователи (ЦАП) реализуют такую ​​аппроксимацию, как удержание нулевого порядка . В этом случае передискретизация может уменьшить ошибку аппроксимации.

Оригинальное доказательство Шеннона

Пуассон показывает, что ряд Фурье в уравнении 1 дает периодическое суммирование $X(f)$, невзирая на $f_{s}$ и $B$. Шеннон, однако, выводит коэффициенты ряда только для случая $f_{s}=2B$. Практически цитируя оригинальную статью Шеннона:

Позволять $X(\omega )$ быть спектром $x(t).$ Затем

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

потому что $X(\omega )$ предполагается равным нулю вне диапазона $\left|{\tfrac {\omega }{2\pi }}\right|<B.$ Если мы позволим $t={\tfrac {n}{2B}},$ где $n$ любое положительное или отрицательное целое число, мы получаем:

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

Слева указаны значения $x(t)$ в точках отбора проб. Интеграл справа будем считать существенно тот $n^{th}$ коэффициент в разложении функции в ряд Фурье $X(\omega ),$ делая интервал $-B$ к $B$ как фундаментальный период. Это означает, что значения выборок $x(n/2B)$ определить коэффициенты Фурье в разложении в ряд $X(\omega ).$ Таким образом они определяют $X(\omega ),$ с $X(\omega )$ равен нулю для частот, превышающих $B,$ и для более низких частот $X(\omega )$ определяется, если определены его коэффициенты Фурье. Но $X(\omega )$ определяет исходную функцию $x(t)$ полностью, поскольку функция определена, если известен ее спектр. Поэтому исходные образцы определяют функцию $x(t)$ полностью.

На этом доказательство Шеннона теоремы завершено, но он продолжает обсуждать реконструкцию с помощью функций sinc , которые мы теперь называем интерполяционной формулой Уиттекера-Шеннона, как обсуждалось выше. Он не выводит и не доказывает свойства функции sinc, поскольку к тому времени была хорошо известна парная связь Фурье между функциями rect (прямоугольная функция) и sinc.

Позволять $x_{n}$ быть $n^{th}$ образец. Тогда функция $x(t)$ представлен:

$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. То есть все они являются псевдонимами друг друга, хотя их частота не превышает половины частоты дискретизации.

Критическая частота

Чтобы проиллюстрировать необходимость $f_{s}>2B,$ рассмотрим семейство синусоид, порожденных разными значениями $\theta$ в этой формуле:

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

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

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

независимо от стоимости $\theta .$ Такая двусмысленность является причиной строгого неравенства условия теоремы выборки.

Выборка сигналов, не являющихся основной полосой частот

Как обсуждал Шеннон:

Аналогичный результат верен, если полоса начинается не с нулевой частоты, а с некоторого более высокого значения, и может быть доказан путем линейного переноса (физически соответствующего однополосной модуляции ) в случае нулевой частоты. В этом случае элементарный импульс получается из $\sin(x)/x$ с помощью однополосной модуляции.

То есть достаточное условие отсутствия потерь для дискретизации сигналов , не имеющих компонентов основной полосы существует , которое включает в себя ширину ненулевого частотного интервала в отличие от его самой высокочастотной составляющей. См. выборку для получения более подробной информации и примеров.

Например, для выборки FM- радиосигналов в диапазоне частот 100–102 МГц не обязательно производить выборку на частоте 204 МГц (вдвое выше верхней частоты), а достаточно производить выборку на частоте 4 МГц (вдвое больше ширины полосы частот). частотного интервала).

Условие полосы пропускания заключается в том, что $X(f)=0,$ для всех неотрицательных $f$ вне открытой полосы частот:

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

для некоторого неотрицательного целого числа $N$. Эта формулировка включает в себя нормальное условие основной полосы частот в случае $N=0.$

Соответствующая интерполяционная функция представляет собой импульсную характеристику идеального полосового фильтра с кирпичной стеной (в отличие от использованного выше идеального с кирпичной стеной фильтра нижних частот ) с срезами на верхнем и нижнем краях заданной полосы, что и представляет собой разницу между парой импульсных характеристик нижних частот:

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

Возможны и другие обобщения, например, для сигналов, занимающих несколько несмежных полос. Даже самая обобщенная форма теоремы выборки не имеет доказуемо истинного обратного. То есть нельзя заключить, что информация обязательно теряется только потому, что не выполняются условия теоремы выборки; однако с инженерной точки зрения обычно можно с уверенностью предположить, что если теорема выборки не выполняется, то информация, скорее всего, будет потеряна.

Неравномерная выборка

Теорию выборки Шеннона можно обобщить на случай неравномерной выборки , то есть выборок, взятых не через равные промежутки времени. Теория выборки Шеннона для неравномерной выборки утверждает, что сигнал с ограниченной полосой частот может быть идеально восстановлен по его выборкам, если средняя частота дискретизации удовлетворяет условию Найквиста. Следовательно, хотя равномерно расположенные выборки могут привести к упрощению алгоритмов реконструкции, это не является необходимым условием идеальной реконструкции.

Общая теория немодулированных и неоднородных выборок была разработана в 1967 году Генри Ландау . Он доказал, что средняя частота дискретизации (равномерная или нет) должна быть в два раза больше занимаемой полосы пропускания сигнала, предполагая, что априори известно, какая часть спектра была занята.

В конце 1990-х годов эта работа была частично расширена и теперь охватывает сигналы, для которых величина занимаемой полосы частот известна, но фактическая занятая часть спектра неизвестна. В 2000-х годах была разработана полноценная теория(см. раздел «Выборка ниже частоты Найквиста при дополнительных ограничениях» ниже) с использованием сжатого измерения . В частности, теория с использованием языка обработки сигналов описана в статье Мишали и Эльдара 2009 года. Они показывают, среди прочего, что если частотные местоположения неизвестны, то необходимо проводить выборку, по крайней мере, в два раза превышающую критерии Найквиста; вы должны заплатить как минимум коэффициент 2 другими словами, за незнание местоположения спектра . Обратите внимание, что минимальные требования к выборке не обязательно гарантируют стабильность .

Выборка ниже уровня Найквиста при дополнительных ограничениях

Основная статья: Недостаточная выборка

Теорема выборки Найквиста-Шеннона обеспечивает достаточное условие для выборки и восстановления сигнала с ограниченной полосой пропускания. Когда реконструкция выполняется с помощью интерполяционной формулы Уиттекера-Шеннона , критерий Найквиста также является необходимым условием, позволяющим избежать наложения спектров, в том смысле, что если выборки отбираются с частотой, меньшей, чем в два раза превышает предел полосы, то есть некоторые сигналы, которые не будут быть правильно реконструированы. Однако если на сигнал наложены дополнительные ограничения, то критерий Найквиста может перестать быть необходимым условием .

Нетривиальный пример использования дополнительных предположений о сигнале представляет собой недавнюю область применения сжатого зондирования , которая позволяет выполнить полную реконструкцию с частотой дискретизации суб-Найквиста. В частности, это относится к сигналам, которые являются разреженными (или сжимаемыми) в некоторой области. Например, сжатое зондирование имеет дело с сигналами, которые могут иметь низкую общую полосу пропускания (скажем, эффективную полосу пропускания) . $EB$), но расположение частот неизвестно, а не все вместе в одной полосе, так что метод полосы пропускания не применяется. Другими словами, частотный спектр разрежен. Традиционно необходимая частота дискретизации равна $2B.$ Используя методы сжатого зондирования, сигнал может быть идеально восстановлен, если его дискретизировать с частотой немного меньшей, чем $2EB.$ При таком подходе реконструкция больше не задается формулой, а решением программы линейной оптимизации .

Другой пример, когда выборка суб-Найквиста является оптимальной, возникает при дополнительном ограничении, заключающемся в том, что выборки квантоваются оптимальным образом, как в комбинированной системе выборки и оптимального сжатия с потерями . Эта настройка актуальна в тех случаях, когда необходимо учитывать совместный эффект дискретизации и квантования , и может обеспечить нижнюю границу минимальной ошибки восстановления, которая может быть достигнута при дискретизации и квантовании случайного сигнала . Для стационарных гауссовских случайных сигналов эта нижняя граница обычно достигается при частоте дискретизации суб-Найквиста, что указывает на то, что выборка суб-Найквиста оптимальна для этой модели сигнала при оптимальном квантовании .

Историческая справка

Теорема выборки была высказана в работе Гарри Найквиста в 1928 году: в котором он показал это до $2B$ независимые выборки импульсов могут быть отправлены через систему полосы пропускания $B$; но он не рассматривал подробно проблему дискретизации и восстановления непрерывных сигналов. Примерно в то же время Карл Купфмюллер . аналогичный результат показал и обсудил импульсную характеристику функции sinc ограничительного фильтра через ее интеграл, синусоидальный интеграл переходной характеристики ; этот фильтр ограничения полосы пропускания и реконструкции, который играет центральную роль в теореме выборки, иногда называют фильтром Купфмюллера (но редко на английском языке).

Теорема выборки, по сути двойственная результату Найквиста, была доказана Клодом Э. Шенноном . Математик Э. Т. Уиттакер опубликовал аналогичные результаты в 1915 году. Дж. М. Уиттакер в 1935 году. и Габор в 1946 году («Теория коммуникации»).

В 1948 и 1949 годах Клод Э. Шеннон опубликовал две революционные статьи, в которых он основал теорию информации. В Шенноне в 1948 году теорема выборки была сформулирована как «Теорема 13»: Пусть $f(t)$ не содержат частот над W. Тогда

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

Лишь после публикации этих статей теорема, известная как «теорема выборки Шеннона», стала общим достоянием среди инженеров связи, хотя сам Шеннон пишет, что это общеизвестный факт в искусстве связи. Однако несколькими строками далее он добавляет: «Но, несмотря на свою очевидную важность, [оно], кажется, не появлялось явно в литературе по теории коммуникации». Несмотря на то, что его теорема выборки была опубликована в конце 1940-х годов, Шеннон вывел свою теорему выборки еще в 1940 году.

Другие первооткрыватели

Другие, которые независимо открыли теорему выборки или сыграли роль в ее разработке, обсуждались в нескольких исторических статьях, например, Джерри. и Люк. Например, Люке указывает, что Х. Раабе, помощник Купфмюллера, доказал эту теорему в своей докторской диссертации 1939 года. диссертация; термин «условие Раабе» стал ассоциироваться с критерием однозначного представления (частота дискретизации, более чем в два раза превышающая полосу пропускания). Мейеринг упоминает нескольких других первооткрывателей и имена в абзаце и паре сносок:

Как отметил Хиггинс, теорему выборки на самом деле следует рассматривать в двух частях, как это было сделано выше: первая констатирует тот факт, что функция с ограниченной полосой частот полностью определяется ее выборками, а вторая описывает, как восстановить функцию с использованием ее выборок. Обе части теоремы выборки были даны в несколько иной форме Дж. М. Уиттекером, а до него также Огурой. Вероятно, они не знали, что первая часть теоремы была сформулирована еще в 1897 году Борелем. Как мы видели, примерно в то же время Борель также использовал так называемый кардинальный ряд. Однако, похоже, он не сделал ссылку. В последующие годы стало известно, что теорема выборки была представлена ​​российскому коммуникационному сообществу еще до Шеннона Котельниковым . В более неявной, вербальной форме оно также было описано в немецкой литературе Раабе. Некоторые авторы отметили, что Сомея представил теорему в японской литературе параллельно с Шенноном. В английской литературе Уэстон представил его независимо от Шеннона примерно в то же время.

- Эрик Мейеринг, «Хронология интерполяции от древней астрономии до современной обработки сигналов и изображений» (цитаты опущены)

В русской литературе она известна как теорема Котельникова, названная в честь Владимира Котельникова , открывшего ее в 1933 году.

Почему Найквист?

Как, когда и почему Гарри Найквиста имя было связано с теоремой выборки, остается неясным. Термин «Теорема выборки Найквиста» (написанный с заглавной буквы) появился еще в 1959 году в книге его бывшего работодателя, Bell Labs . и снова появился в 1963 году, и не капитализировался в 1965 году. она была названа Теоремой выборки Шеннона . Еще в 1954 году но также и теорема выборки из нескольких других книг начала 1950-х годов.

В 1958 году Блэкман и Тьюки процитировали статью Найквиста 1928 года как ссылку на теорему выборки теории информации : даже несмотря на то, что в этой статье не рассматривается выборка и реконструкция непрерывных сигналов, как это делалось в других. Их глоссарий терминов включает следующие записи:

Теорема выборки (теории информации)

Результат Найквиста о том, что равноотстоящие данные с двумя или более точками на цикл самой высокой частоты позволяют восстанавливать функции с ограниченной полосой пропускания. (См. Кардинальную теорему .)

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

Точная формулировка условий, при которых значения, заданные в дважды бесконечном множестве равноотстоящих друг от друга точек, могут быть интерполированы для получения непрерывной функции с ограниченной полосой частот с помощью функции $${\frac {\sin(x-x_{i})}{x-x_{i}}}.$$

О каком «результате Найквиста» они имеют в виду, остается загадкой.

Когда Шеннон сформулировал и доказал теорему выборки в своей статье 1949 года, согласно Мейерингу, "он имел в виду критический интервал выборки $T={\frac {1}{2W}}$ как интервал Найквиста, соответствующий полосе $W,$ в знак признания открытия Найквистом фундаментальной важности этого интервала в связи с телеграфией». Это объясняет имя Найквиста на критическом интервале, но не на теореме.

Точно так же имя Найквиста было добавлено к ставке Найквиста в 1953 году Гарольдом С. Блэком :

Если основной диапазон частот ограничен $B$ циклов в секунду, $2B$ было дано Найквистом как максимальное количество элементов кода в секунду, которые можно однозначно разрешить, предполагая, что пиковая интерференция составляет менее половины квантового шага. Эту скорость обычно называют передачей сигналов со скоростью Найквиста . ${\frac {1}{2B}}$ был назван интервалом Найквиста .

— Гарольд Блэк, Теория модуляции (жирный шрифт выделен для выделения; курсив, как в оригинале)

Согласно Оксфордскому словарю английского языка , это может быть источником термина « ставка Найквиста» . В понимании Блэка это не частота дискретизации, а частота передачи сигналов.

См. также

• 44 100 Гц , обычная частота, используемая для выборки слышимых частот, основана на пределах человеческого слуха и теореме выборки.
• Теорема Балиана-Лоу , аналогичная теоретическая нижняя граница частоты дискретизации, но применимая к преобразованиям время-частота.
• Теорема Ченга-Маркса , которая определяет условия, при которых восстановление сигнала с помощью теоремы выборки может стать некорректным.
• Теорема Шеннона – Хартли
• Критерий Найквиста ISI
• Реконструкция по пересечениям нуля
• Удержание нулевого порядка
• Гребень Дирака

Дальнейшее чтение

• Хиггинс, младший (1985). «Пять рассказов о кардинальном сериале» . Вестник АМС . 12 (1): 45–89. дои : 10.1090/S0273-0979-1985-15293-0 .
• Купфмюллер, Карл (1931). «Переходные процессы в телеграфной и телефонной технике» . Технический журнал (9): 153–160. и (10): стр. 178–182
• Маркс, II, Р.Дж. (1991). Введение в теорию выборки и интерполяции Шеннона (PDF) . Тексты Springer по электротехнике. Спрингер. дои : 10.1007/978-1-4613-9708-3 . ISBN  978-1-4613-9708-3 . Архивировано (PDF) из оригинала 14 июля 2011 г.
• Маркс, II, Р.Дж., изд. (1993). Расширенные темы теории выборки и интерполяции Шеннона (PDF) . Тексты Springer по электротехнике. Спрингер. дои : 10.1007/978-1-4613-9757-1 . ISBN  978-1-4613-9757-1 . Архивировано (PDF) из оригинала 6 октября 2011 г.
• Маркс, II, Р.Дж. (2009). «Главы 5–8». Справочник по анализу Фурье и его приложениям . Издательство Оксфордского университета. ISBN  978-0-19-804430-7 .
• Пресс, WH; Теукольский, С.А.; Феттерлинг, WT; Фланнери, BP (2007), «§13.11. Численное использование теоремы выборки» , Численные рецепты: искусство научных вычислений (3-е изд.), Cambridge University Press, ISBN  978-0-521-88068-8 , заархивировано из оригинала 11 августа 2011 г. , получено 13 августа 2011 г.
• Унсер, Майкл (апрель 2000 г.). «Отбор проб через 50 лет после Шеннона» (PDF) . Учеб. ИИЭЭ . 88 (4): 569–587. дои : 10.1109/5.843002 . S2CID   11657280 . Архивировано (PDF) из оригинала 3 ноября 2022 г.

Внешние ссылки

• Обучение посредством моделирования Интерактивное моделирование последствий неадекватной выборки
• Интерактивная презентация выборки и реконструкции в веб-демо Института телекоммуникаций Штутгартского университета
• Недостаточная выборка и ее применение
• Теория дискретизации цифрового аудио
• Журнал, посвященный теории выборки
• Хуанг, Дж.; Падманабхан, К.; Коллинз, О.М. (июнь 2011 г.). «Теорема выборки с импульсами переменной ширины постоянной амплитуды». Транзакции IEEE в схемах и системах I: Регулярные статьи . 58 (6): 1178–90. дои : 10.1109/TCSI.2010.2094350 . S2CID   13590085 .
• Люке, Ганс Дитер (апрель 1999 г.). «Происхождение теоремы выборки» (PDF) . Журнал коммуникаций IEEE . 37 (4): 106–108. CiteSeerX   10.1.1.163.2887 . дои : 10.1109/35.755459 .