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

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

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

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

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

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

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

Введение

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

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

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

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

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

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

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

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

Псевдонимы

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

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

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

Формула суммирования Пуассона указывает, что выборок достаточно для периодического суммирования . Результат : ${\displaystyle x(nT),}$ ${\displaystyle x(t)}$ ${\displaystyle X(f).}$

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

которая является периодической функцией и ее эквивалентным представлением в виде ряда Фурье , коэффициенты которого равны . Эта функция также известна как преобразование Фурье дискретного времени (DTFT) последовательности выборок. ${\displaystyle T\cdot x(nT)}$

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

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

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

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

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

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

где:

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

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

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

$${\displaystyle H(f)=\mathrm {rect} \left({\frac {f}{f_{s}}}\right)={\begin{cases}1&|f|<{\frac {f_{s}}{2}}\\0&|f|>{\frac {f_{s}}{2}},\end{cases}}}$$

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

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

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

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

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

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

который показывает, как выборки , могут быть объединены для восстановления . ${\displaystyle x(nT)}$ ${\displaystyle x(t)}$

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

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

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

Пусть – спектр   Тогда ${\displaystyle X(\omega )}$ ${\displaystyle x(t).}$

${\displaystyle x(t)={1 \over 2\pi }\int _{-\infty }^{\infty }X(\omega )e^{i\omega t}\;{\rm {d}}\omega ={1 \over 2\pi }\int _{-2\pi B}^{2\pi B}X(\omega )e^{i\omega t}\;{\rm {d}}\omega ,}$

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

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

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

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

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

Как и в другом доказательстве, предполагается существование преобразования Фурье исходного сигнала, поэтому в доказательстве не говорится, распространяется ли теорема выборки на стационарные случайные процессы с ограниченной полосой пропускания.

Примечания

1. Умножение обеих частей уравнения 2 на дает слева масштабированные выборочные значения в формуле Пуассона ( уравнение 1 ), а справа - фактическую формулу для коэффициентов разложения Фурье. ${\displaystyle T=1/2B}$ ${\displaystyle (T\cdot x(nT))}$

Приложение к многопараметрическим сигналам и изображениям

Изображение с субдискретизацией, показывающее муаровый узор

Правильно выбранное изображение

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

Цветные изображения обычно состоят из трех отдельных изображений в оттенках серого, по одному для каждого из трех основных цветов — красного, зеленого и синего или сокращенно RGB . Другие цветовые пространства, использующие 3-векторы для цветов, включают HSV, CIELAB, XYZ и т. д. Некоторые цветовые пространства, такие как голубой, пурпурный, желтый и черный (CMYK), могут представлять цвет в четырех измерениях. Все они рассматриваются как векторные функции в двумерной выборочной области.

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

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

Теорема выборки применима к системам камер, где сцена и объектив представляют собой источник аналогового пространственного сигнала, а датчик изображения является устройством пространственной выборки. Каждый из этих компонентов характеризуется функцией передачи модуляции (MTF), представляющей точное разрешение (пространственную полосу пропускания), доступную в этом компоненте. Эффекты сглаживания или размытия могут возникнуть, если MTF объектива и MTF сенсора не совпадают. Когда оптическое изображение, снимаемое сенсорным устройством, содержит более высокие пространственные частоты, чем сенсор, недостаточная дискретизация действует как фильтр нижних частот для уменьшения или устранения наложения спектров. Когда площадь пятна выборки (размер пиксельного датчика) недостаточно велика для обеспечения достаточного пространственного сглаживания , в систему камеры может быть включен отдельный сглаживающий фильтр (оптический фильтр нижних частот), чтобы уменьшить MTF оптического изображения. Вместо оптического фильтра графический процессор камер смартфонов выполняет цифровую обработку сигнала для устранения наложения с помощью цифрового фильтра. Цифровые фильтры также повышают резкость для усиления контраста объектива на высоких пространственных частотах, который в противном случае быстро падает в пределах дифракции.

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

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

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

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

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

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

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

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

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

Как обсуждал Шеннон: ^[2]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Теорема выборки была высказана в работе Гарри Найквиста в 1928 году ^[11] , в которой он показал, что через систему полосы пропускания можно отправлять до независимых выборок импульсов ; но он не рассматривал подробно проблему дискретизации и восстановления непрерывных сигналов. Примерно в то же время Карл Купфмюллер показал аналогичный результат ^[12] и обсудил импульсную характеристику синх-функции полосового фильтра через ее интеграл, синусоидальный интеграл переходной характеристики ; этот фильтр ограничения полосы пропускания и реконструкции, который играет центральную роль в теореме выборки, иногда называют фильтром Купфмюллера (но редко на английском языке). ${\displaystyle 2B}$ ${\displaystyle B}$

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

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

$${\displaystyle f(t)=\sum _{n=-\infty }^{\infty }X_{n}{\frac {\sin \pi (2Wt-n)}{\pi (2Wt-n)}},}$$

${\displaystyle X_{n}=f\left({\frac {n}{2W}}\right).}$

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

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

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

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

1. Некоторые авторы, вслед за Блэком, утверждали, что эта первая часть теоремы выборки была сформулирована еще раньше Коши в статье, опубликованной в 1841 году. Однако статья Коши не содержит такого утверждения, как было указано Коши. Хиггинс.
2. В результате открытия нескольких независимых введений теоремы выборки люди начали ссылаться на теорему, включая имена вышеупомянутых авторов, что привело к появлению таких крылатых фраз, как «Уиттакер – Котельников – Шеннон (WKS)». теорема выборки» или даже «теорема выборки Уиттекера-Котельникова-Раабе-Шеннона-Сомеи». Чтобы избежать путаницы, возможно, лучше всего называть ее теоремой выборки, «вместо того, чтобы пытаться найти название, которое справедливо для всех заявителей».

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Смотрите также

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

Примечания

1. Функция sinc следует из строк 202 и 102 таблиц преобразований.
2. Шеннон 1949, с. 448.

Рекомендации

1. Немировский, Джонатан; Шимрон, Эфрат (2015). «Использование теоремы Бохнера для ограниченной оценки недостающих данных Фурье». arXiv : 1506.03300 [Physics.med-ph].
2. Шеннон, Клод Э. (январь 1949 г.). «Связь в условиях шума». Труды Института радиоинженеров . 37 (1): 10–21. дои : 10.1109/jrproc.1949.232969. S2CID  52873253.Перепечатка как классическая статья в: Учеб. IEEE, Том. 86, № 2, (февраль 1998 г.). Архивировано 8 февраля 2010 г. в Wayback Machine.
3. Ахмед, Н.; Рао, КР (10 июля 1975 г.). Ортогональные преобразования для цифровой обработки сигналов (1-е изд.). Берлин Гейдельберг Нью-Йорк: Springer-Verlag. дои : 10.1007/978-3-642-45450-9. ISBN 9783540065562.
4. Кэмпбелл, Джордж; Фостер, Рональд (1942). Интегралы Фурье для практических приложений . Нью-Йорк: Лаборатории телефонной системы Bell.
5. Марвасти, Ф., изд. (2000). Неравномерная выборка, теория и практика . Нью-Йорк: Издательство Kluwer Academic/Plenum.
6. Ландау, HJ (1967). «Необходимые условия плотности для выборки и интерполяции некоторых целых функций». Акта Математика . 117 (1): 37–52. дои : 10.1007/BF02395039 .
7. Например, Фэн, П. (1997). Универсальная дискретизация с минимальной частотой и слепая по спектру реконструкция многополосных сигналов (кандидатская диссертация). Университет Иллинойса в Урбана-Шампейн.
8. Мишали, Моше; Эльдар, Йонина К. (март 2009 г.). «Слепая реконструкция многополосного сигнала: сжатое измерение аналоговых сигналов». IEEE Транс. Сигнальный процесс . 57 (3): 993–1009. Бибкод : 2009ИТСП...57..993М. CiteSeerX 10.1.1.154.4255 . дои :10.1109/TSP.2009.2012791. S2CID  2529543. 
9. Кипнис, Алон; Голдсмит, Андреа Дж.; Эльдар, Йонина С.; Вайсман, Цахи (январь 2016 г.). «Функция скорости искажения гауссовских источников с выборкой суб-Найквиста». Транзакции IEEE по теории информации . 62 : 401–429. arXiv : 1405.5329 . дои : 10.1109/tit.2015.2485271. S2CID  47085927.
10. Кипнис, Алон; Эльдар, Йонина; Голдсмит, Андреа (26 апреля 2018 г.). «Аналогово-цифровое сжатие: новая парадигма преобразования сигналов в биты». Журнал обработки сигналов IEEE . 35 (3): 16–39. arXiv : 1801.06718 . Бибкод : 2018ISPM...35c..16K. дои : 10.1109/MSP.2017.2774249. S2CID  13693437.
11. Найквист, Гарри (апрель 1928 г.). «Некоторые вопросы теории телеграфной передачи». Сделки AIEE . 47 (2): 617–644. Бибкод : 1928TAIEE..47..617N. дои : 10.1109/t-aiee.1928.5055024.Перепечатка как классическая статья в: Proceedings of the IEEE , Vol. 90, № 2, февраль 2002 г. Архивировано 26 сентября 2013 г. в Wayback Machine.
12. Купфмюллер, Карл (1928). «Über die Dynamik der selbsttätigen Verstärkungsregler». Elektrische Nachrichtentechnik (на немецком языке). 5 (11): 459–467.(Английский перевод, 2005 г.).
13. Уиттакер, ET (1915). «О функциях, представляемых разложениями теории интерполяции». Труды Королевского общества Эдинбурга . 35 : 181–194. дои : 10.1017/s0370164600017806. ( «Теория кардинальных функций» ).
14. Уиттакер, Дж. М. (1935). Интерполяционная теория функций. Кембридж, Англия: Издательство Кембриджского университета.
15. Шеннон, Клод Э. (июль 1948 г.). «Математическая теория связи». Технический журнал Bell System . 27 (3): 379–423. doi :10.1002/j.1538-7305.1948.tb01338.x. hdl : 11858/00-001M-0000-002C-4317-B .
16. Шеннон, Клод Э. (октябрь 1948 г.). «Математическая теория связи». Технический журнал Bell System . 27 (4): 623–666. doi :10.1002/j.1538-7305.1948.tb00917.x. hdl : 11858/00-001M-0000-002C-4314-2 .
17. Джерри, Абдул (ноябрь 1977 г.). «Теорема Шеннона о выборке - ее различные расширения и приложения: обзор учебного пособия». Труды IEEE . 65 (11): 1565–1596. Бибкод : 1977IEEP..65.1565J. дои : 10.1109/proc.1977.10771. S2CID  37036141.См. также Джерри, Абдул (апрель 1979 г.). «Поправка к «Теореме выборки Шеннона - ее различные расширения и приложения: обзор учебного пособия»". Proceedings of IEEE . 67 (4): 695. doi :10.1109/proc.1979.11307.
18. Люке, Ганс Дитер (апрель 1999 г.). «Происхождение теоремы выборки» (PDF) . Журнал коммуникаций IEEE . 37 (4): 106–108. CiteSeerX 10.1.1.163.2887 . дои : 10.1109/35.755459. 
19. Мейеринг, Эрик (март 2002 г.). «Хронология интерполяции от древней астрономии до современной обработки сигналов и изображений» (PDF) . Труды IEEE . 90 (3): 319–342. дои : 10.1109/5.993400.
20. Котельников В. А., О пропускной способности «эфира» и проводов в электросвязи , (английский перевод, PDF), Изд. Красный. Упр. Svyazzi RKKA (1933), Переиздание в «Современной теории выборки: математика и приложения» , редакторы: JJ Benedetto и PJSG Ferreira, Birkhauser (Бостон) 2000, ISBN 0-8176-4023-1 . 
21. Члены технического персонала телефонных лабораторий Bell (1959). Системы передачи для связи . Том. 2. АТ&Т. стр. 26–4.
22. Гиймен, Эрнст Адольф (1963). Теория линейных физических систем. Уайли. ISBN 9780471330707.
23. Робертс, Ричард А.; Бартон, Бен Ф. (1965). Теория обнаруживаемости сигналов: теория составного отложенного решения .
24. Грей, Трумэн С. (1954). «Прикладная электроника: первый курс электроники, электронных трубок и связанных с ними схем». Физика сегодня . 7 (11): 17. Бибкод :1954ФТ.....7к..17Г. дои : 10.1063/1.3061438. hdl : 2027/mdp.39015002049487 .
25. Блэкман, РБ; Тьюки, JW (1958). Измерение спектров мощности: с точки зрения техники связи (PDF) . Нью-Йорк: Дувр. Архивировано (PDF) из оригинала 9 октября 2022 г.^{[ постоянная мертвая ссылка ]}
26. Блэк, Гарольд С. (1953). Теория модуляции .

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

• Хиггинс, младший (1985). «Пять рассказов кардинального ряда». Вестник АМС . 12 (1): 45–89. дои : 10.1090/S0273-0979-1985-15293-0 .
• Купфмюллер, Карл (1931). «Utjämningsförlopp inom Telegraf- och Telefontekniken» [Переходные процессы в телеграфной и телефонной технике]. Текниск Тидскрифт (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) из оригинала 03 ноября 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.

Sufficiency theorem for reconstructing signals from samples