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

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

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

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

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

Идеальная реконструкция все еще может быть возможна, когда критерий частоты дискретизации не выполняется, при условии, что известны другие ограничения на сигнал (см. § Выборка сигналов, отличных от основной полосы частот, ниже и сжатое зондирование ). В некоторых случаях (когда критерий частоты дискретизации не выполняется) использование дополнительных ограничений позволяет проводить приблизительные реконструкции. Точность этих реконструкций можно проверить и количественно оценить, используя теорему Бохнера . ^[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 T\cdot x(nT)}$ ${\displaystyle x_{n}}$ ${\displaystyle n.}$ ${\displaystyle T}$ ${\displaystyle T}$

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

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

Алиасинг

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

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

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

Тогда выборок достаточно для создания периодического суммирования ( см. Дискретное_временное_преобразование_Фурье#Отношение_к_преобразованию_Фурье ) : ${\displaystyle x[n],}$ ${\displaystyle x(t)}$ ${\displaystyle X(f).}$

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

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

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

Спектр, , правильно выбранного сигнала с ограниченной полосой пропускания (синий) и смежные изображения 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_{1/T}(f),}$$

где:

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

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

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

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

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

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

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

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

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

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

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

• Большие, чем необходимо, значения (меньшие значения ), называемые избыточной выборкой , не оказывают влияния на результат реконструкции и имеют преимущество, оставляя место для переходной полосы , в которой свободно принимать промежуточные значения. Недостаточная выборка , которая вызывает наложение спектров, в общем случае не является обратимой операцией. ${\displaystyle f_{s}}$ ${\displaystyle T}$ ${\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] коэффициент в разложении ряда Фурье функции, принимающей интервал по в качестве основного периода. Это означает, что значения выборок определяют коэффициенты Фурье в разложении ряда   Таким образом, они определяют, поскольку равен нулю для частот, больших, чем и для более низких частот определяется, если определены его коэффициенты Фурье. Но полностью определяет исходную функцию , поскольку функция определяется, если известен ее спектр. Следовательно, исходные выборки полностью определяют функцию . ${\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] и рассмотрел импульсную характеристику sinc-функции фильтра, ограничивающего полосу пропускания, через ее интеграл, интеграл синуса ступенчатой ​​реакции ; этот фильтр, ограничивающий полосу пропускания и восстанавливающий полосу пропускания, который является столь центральным для теоремы о дискретизации, иногда называют фильтром Купфмюллера (но редко так в английском языке). ${\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] Однако несколькими строками дальше он добавляет: «но, несмотря на ее очевидную важность, [она], похоже, не появилась явно в литературе по теории связи». Несмотря на то, что его теорема выборки была опубликована в конце 1940-х годов, Шеннон вывел свою теорему выборки еще в 1940 году. ^[17]

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

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

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

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

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

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

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

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

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

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

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

Основная теорема (теории интерполяции)

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

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

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

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

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

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

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

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

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

Примечания

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

Ссылки

1. Немировски, Джонатан; Шимрон, Эфрат (2015). «Использование теоремы Бохнера для ограниченной оценки отсутствующих данных Фурье». arXiv : 1506.03300 [physics.med-ph].
2. Шеннон, Клод Э. (январь 1949). «Связь в присутствии шума». Труды Института радиоинженеров . 37 (1): 10–21. doi :10.1109/jrproc.1949.232969. S2CID  52873253.Перепечатано как классическая статья в: Proc. IEEE, Vol. 86, No. 2, (февраль 1998 г.) Архивировано 08.02.2010 на Wayback Machine
3. Ахмед, Н.; Рао, К. Р. (10 июля 1975 г.). Ортогональные преобразования для цифровой обработки сигналов (1-е изд.). Берлин-Гейдельберг-Нью-Йорк: Springer-Verlag. doi :10.1007/978-3-642-45450-9. ISBN 9783540065562.
4. Кэмпбелл, Джордж; Фостер, Рональд (1942). Интегралы Фурье для практических приложений . Нью-Йорк: Bell Telephone System Laboratories.
5. Марвасти, Ф., ред. (2000). Неравномерная выборка, теория и практика . Нью-Йорк: Kluwer Academic/Plenum Publishers.
6. Ландау, HJ (1967). «Необходимые условия плотности для выборки и интерполяции некоторых целых функций». Acta Mathematica . 117 (1): 37–52. doi : 10.1007/BF02395039 .
7. Например, Фэн, П. (1997). Универсальная минимальная частота дискретизации и спектрально-слепая реконструкция для многополосных сигналов (диссертация). Университет Иллинойса в Урбане-Шампейне.
8. Мишали, Моше; Эльдар, Йонина С. (март 2009 г.). «Слепая многополосная реконструкция сигнала: сжатое зондирование аналоговых сигналов». IEEE Trans. Signal Process . 57 (3): 993–1009. Bibcode : 2009ITSP...57..993M. CiteSeerX 10.1.1.154.4255 . doi : 10.1109/TSP.2009.2012791. S2CID  2529543. 
9. Кипнис, Алон; Голдсмит, Андреа Дж.; Элдар, Йонина К.; Вайсман, Цахи (январь 2016 г.). «Функция скорости искажения гауссовых источников с выборкой ниже Найквиста». Труды IEEE по теории информации . 62 : 401–429. arXiv : 1405.5329 . doi : 10.1109/tit.2015.2485271. S2CID  47085927.
10. Кипнис, Алон; Элдар, Йонина; Голдсмит, Андреа (26 апреля 2018 г.). «Аналогово-цифровое сжатие: новая парадигма преобразования сигналов в биты». Журнал обработки сигналов IEEE . 35 (3): 16–39. arXiv : 1801.06718 . Bibcode : 2018ISPM...35c..16K. doi : 10.1109/MSP.2017.2774249. S2CID  13693437.
11. Найквист, Гарри (апрель 1928 г.). «Некоторые темы в теории передачи телеграфа». Труды AIEE . 47 (2): 617–644. Bibcode : 1928TAIEE..47..617N. doi : 10.1109/t-aiee.1928.5055024.Перепечатано как классическая статья в: Proceedings of the IEEE , том 90, № 2, февраль 2002 г.
12. Купфмюллер, Карл (1928). «Über die Dynamik der selbsttätigen Verstärkungsregler». Elektrische Nachrichtentechnik (на немецком языке). 5 (11): 459–467.(Перевод на английский язык 2005 г.) Архивировано 21 мая 2019 г. на Wayback Machine .
13. Уиттекер, ET (1915). «О функциях, которые представлены расширениями теории интерполяции». Труды Королевского общества Эдинбурга . 35 : 181–194. doi :10.1017/s0370164600017806. ( «Теория кардинальных функций» ).
14. Уиттекер, Дж. М. (1935). Теория интерполяционных функций. Кембридж, Англия: Cambridge University Press.
15. Шеннон, Клод Э. (июль 1948 г.). «Математическая теория связи». Bell System Technical Journal . 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 Technical Journal . 27 (4): 623–666. doi :10.1002/j.1538-7305.1948.tb00917.x. hdl : 11858/00-001M-0000-002C-4314-2 .
17. Станкович, Раромир С.; Астола, Яакко Т.; Карповский, Марк Г. (сентябрь 2006 г.). Некоторые исторические замечания о теореме выборки (PDF) . Труды Международного семинара TICSP 2006 г. по спектральным методам и многоскоростной обработке сигналов.
18. Джерри, Абдул (ноябрь 1977 г.). «Теорема выборки Шеннона — ее различные расширения и приложения: обзор учебника». Труды IEEE . 65 (11): 1565–1596. Bibcode : 1977IEEEP..65.1565J. doi : 10.1109/proc.1977.10771. S2CID  37036141.См. также Джерри, Абдул (апрель 1979 г.). «Исправление к «Теореме выборки Шеннона — ее различные расширения и приложения: обзор учебника»". Труды IEEE . 67 (4): 695. doi :10.1109/proc.1979.11307.
19. Люке, Ханс Дитер (апрель 1999 г.). «Истоки теоремы выборки» (PDF) . Журнал IEEE Communications . 37 (4): 106–108. CiteSeerX 10.1.1.163.2887 . doi :10.1109/35.755459. 
20. Meijering, Erik (март 2002 г.). «Хронология интерполяции от древней астрономии до современной обработки сигналов и изображений» (PDF) . Труды IEEE . 90 (3): 319–342. doi :10.1109/5.993400.
21. Котельников ВА, О пропускной способности «эфира» и провода в электросвязи , (английский перевод, PDF) Архивировано 01.03.2021 в Wayback Machine , Изд. Ред. Упр. Связи РККА (1933), Переиздание в Modern Sampling Theory: Mathematics and Applications , Редакторы: JJ Benedetto и PJSG Ferreira, Birkhauser (Бостон) 2000, ISBN 0-8176-4023-1 . 
22. Члены технического персонала Bell Telephone Lababoratories (1959). Системы передачи для связи . Т. 2. AT&T. С. 26-4.
23. Гийемен, Эрнст Адольф (1963). Теория линейных физических систем. Wiley. ISBN 9780471330707.
24. Робертс, Ричард А.; Бартон, Бен Ф. (1965). Теория обнаруживаемости сигнала: составная теория отложенного принятия решений .
25. Грей, Трумэн С. (1954). «Прикладная электроника: первый курс по электронике, электронным лампам и связанным с ними схемам». Physics Today . 7 (11): 17. Bibcode : 1954PhT.....7k..17G. doi : 10.1063/1.3061438. hdl : 2027/mdp.39015002049487 .
26. Блэкман, Р. Б .; Тьюки, Дж. В. (1958). «Измерение спектров мощности с точки зрения техники связи. I». The Bell System Technical Journal . 37 : 185–282. doi :10.1002/j.1538-7305.1958.tb03874.x. MR  0102897.См. глоссарий, стр. 269–279. Кардинальная теорема находится на стр. 270, а теорема выборки — на стр. 277.
27. Блэк, Гарольд С. (1953). Теория модуляции .

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

• Хиггинс, Дж. Р. (1985). «Пять коротких рассказов о кардинальном ряду». Бюллетень AMS . 12 (1): 45–89. doi : 10.1090/S0273-0979-1985-15293-0 .
• Купфмюллер, Карл (1931). «Utjämningsförlopp inom Telegraf- och Telefontekniken» [Переходные процессы в телеграфной и телефонной технике]. Текниск Тидскрифт (9): 153–160.и (10): стр. 178–182
• Marks, II, RJ (1991). Введение в теорию выборки и интерполяции Шеннона (PDF) . Springer Texts in Electrical Engineering. Springer. doi :10.1007/978-1-4613-9708-3. ISBN 978-1-4613-9708-3. Архивировано (PDF) из оригинала 2011-07-14.
• Marks, II, RJ, ред. (1993). Advanced Topics in Shannon Sampling and Interpolation Theory (PDF) . Springer Texts in Electrical Engineering. Springer. doi :10.1007/978-1-4613-9757-1. ISBN 978-1-4613-9757-1. Архивировано (PDF) из оригинала 2011-10-06.
• Marks, II, RJ (2009). "Главы 5–8". Справочник по анализу Фурье и его приложениям. Oxford University Press. ISBN 978-0-19-804430-7.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "§13.11. Численное использование теоремы выборки", Numerical Recipes: The Art of Scientific Computing (3-е изд.), Cambridge University Press, ISBN 978-0-521-88068-8, архивировано из оригинала 2011-08-11 , извлечено 2011-08-13
• Ансер, Майкл (апрель 2000 г.). «Выборка — 50 лет после Шеннона» (PDF) . Proc. IEEE . 88 (4): 569–587. doi :10.1109/5.843002. S2CID  11657280. Архивировано (PDF) из оригинала 03.11.2022.

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

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

Sufficiency theorem for reconstructing signals from samples