Теорема выборки Найквиста – Шеннона - Nyquist–Shannon sampling theorem

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

Позволять ${displaystyle X (омега)}$ быть спектром ${displaystyle x (t).}$ потом

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

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

${displaystyle xleft ({frac {n} {2B}} ight) = {1 over 2pi} int _ {- 2pi B} ^ {2pi B} X (omega) e ^ {iomega {n over {2B}}}; {м {д}} омега.}$

(Уравнение 2)

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

Доказательство теоремы Шенноном на этом завершено, но он продолжает обсуждать восстановление через функции sinc, то, что мы сейчас называем Формула интерполяции Уиттекера – Шеннона как обсуждалось выше. Он не выводит и не доказывает свойства функции sinc, но это было бы^{[ласковые слова ]} знакомым инженерам, читавшим его работы в то время, так как парное соотношение Фурье между прямоугольник (прямоугольная функция) и sinc были хорошо известны.

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

${displaystyle 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 оптического изображения. Вместо оптического фильтра графический процессор из смартфон камеры выполняет цифровая обработка сигналов убрать алиасинг с помощью цифрового фильтра. Цифровые фильтры также применяют повышение резкости для усиления контраста объектива на высоких пространственных частотах, который в противном случае быстро падает на дифракционных пределах.

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

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

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

${displaystyle x (t) = {frac {cos (2pi Bt + heta)} {cos (heta)}} = cos (2pi Bt) -sin (2pi Bt) an (heta), quad -pi / 2$

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

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

${displaystyle x (nT) = cos (pi n) -underbrace {sin (pi n)} _ {0} an (heta) = (- 1) ^ {n}}$

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

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

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

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

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

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

Полосное условие - это Икс(ж) = 0 для всех неотрицательных ж вне открытой полосы частот:

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

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

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

${displaystyle (N + 1), имя оператора {sinc} left ({frac {(N + 1) t} {T}} ight) -N, имя оператора {sinc} left ({frac {Nt} {T}} ight) .}$

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

Неравномерный отбор проб

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

Общая теория для образцов без основной полосы частот и неоднородных образцов была разработана в 1967 г. Генри Ландау.^[4] Он доказал, что средняя частота дискретизации (однородная или нет) должна быть вдвое больше. занят ширина полосы сигнала, если предположить, что это априори Известно, какая часть спектра была занята. В конце 1990-х эта работа была частично расширена для охвата сигналов, когда была известна величина занимаемой полосы частот, но фактическая занятая часть спектра была неизвестна.^[5] В 2000-х годах была разработана полная теория (см. Раздел Выборка ниже ставки Найквиста при дополнительных ограничениях ниже) используя сжатое зондирование. В частности, теория, использующая язык обработки сигналов, описана в этой статье 2009 года.^[6] Они показывают, среди прочего, что если частотные местоположения неизвестны, то необходимо выполнить выборку, по крайней мере, в два раза больше критериев Найквиста; Другими словами, вы должны заплатить по крайней мере в 2 раза за незнание местонахождения спектр. Обратите внимание, что минимальные требования к отбору образцов не обязательно гарантируют стабильность.

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

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

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

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

Историческое прошлое

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

Теорема выборки, по сути двойной результата Найквиста было доказано Клод Э. Шеннон.^[2] Котельников В.А. опубликовал аналогичные результаты в 1933 г.,^[11] как и математикЭ. Т. Уиттакер в 1915 г.,^[12] Дж. М. Уиттакер в 1935 г.,^[13] и Габор в 1946 г. («Теория коммуникации»). В 1999 г. Фонд Эдуарда Рейна присудил Котельникову премию за фундаментальные исследования «за первую теоретически точную формулировку теоремы выборки».

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

${displaystyle f (t) = sum _ {n = -infty} ^ {infty} X_ {n} {frac {sin pi (2Wt-n)} {pi (2Wt-n)}},}$ куда ${displaystyle X_ {n} = fleft ({frac {n} {2W}} ight)}$.

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

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

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

Как указал Хиггинс [135], теорему о выборке действительно следует рассматривать в двух частях, как это было сделано выше: первая констатирует тот факт, что функция с ограниченной полосой пропускания полностью определяется ее выборками, вторая описывает, как восстановить функцию, используя ее образцы. Обе части теоремы выборки были даны в несколько иной форме Дж. М. Уиттакером [350, 351, 353], а до него также Огурой [241, 242]. Вероятно, они не знали о том, что первая часть теоремы была сформулирована еще в 1897 г. Борелем [25].²⁷ Как мы видели, Борель примерно в то время также использовал то, что стало известно как кардинальный ряд. Однако, похоже, он не сделал ссылку [135]. Позднее стало известно, что теорема выборки была представлена ​​еще до Шеннона российскому коммуникационному сообществу Котельниковым [173]. В более неявной, вербальной форме, это также было описано в немецкой литературе Раабе [257]. Некоторые авторы [33, 205] упоминали, что Someya [296] представил теорему в японской литературе параллельно с Шенноном. В английской литературе Вестон [347] ввел его независимо от Шеннона примерно в то же время.²⁸

²⁷ Некоторые авторы, вслед за Блэком [16], утверждали, что эта первая часть теоремы отсчетов была сформулирована еще раньше Коши в статье [41], опубликованной в 1841 году. Однако статья Коши не содержит такого утверждения, как был отмечен Хиггинсом [135].

²⁸ Как следствие открытия нескольких независимых введений теоремы выборки, люди начали ссылаться на теорему, включая имена вышеупомянутых авторов, в результате чего появились такие крылатые фразы, как «выборка Уиттекера – Котельникова – Шеннона (WKS)». теоремы »[155] или даже« теоремы выборки Уиттекера – Котельникова – Раабе – Шеннона – Сомейи »[33]. Во избежание путаницы, возможно, лучше всего называть ее теоремой выборки», а не пытаясь найти титул, который отдает должное всем заявителям »[136].

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

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

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

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

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

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

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

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

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

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

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

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

Согласно OED, это может быть происхождение термина Курс Найквиста. В использовании Блэка это не частота дискретизации, а частота передачи сигналов.

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

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

Примечания

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

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

• Хиггинс, Дж. Р.: Пять рассказов о кардинальном сериале, Бюллетень AMS 12 (1985)
• Кюпфмюллер, Карл, "Utjämningsförlopp inom Telegraf- och Telefontekniken", ("Переходные процессы в телеграфной и телефонной технике"), Текниск Тидскрифт, нет. 9 с. 153–160 и 10 с. 178–182, 1931. [1] [2]
• Маркс, Р.Дж. (II): Введение в теорию выборки и интерполяции Шеннона, Springer-Verlag, 1991.
• Маркс, Р.Дж. (II), редактор: Продвинутые темы в теории выборки и интерполяции Шеннона, Springer-Verlag, 1993.
• Маркс, Р.Дж. (II), Справочник по анализу Фурье и его приложениям, Oxford University Press, (2009), главы 5–8. Книги Google
• Нажмите, WH; Теукольский С.А.; Феттерлинг, штат Вашингтон; Фланнери, BP (2007), «Раздел 13.11. Численное использование теоремы выборки», Числовые рецепты: искусство научных вычислений (3-е изд.), Нью-Йорк: Издательство Кембриджского университета, ISBN  978-0-521-88068-8
• Унсер, Майкл: Выборка - 50 лет после Шеннона, Proc. IEEE, т. 88, нет. 4. С. 569–587, апрель 2000 г.

внешняя ссылка

• Обучение с помощью моделирования Интерактивное моделирование последствий неадекватной выборки
• Интерактивное представление выборки и реконструкции в веб-демонстрации Институт телекоммуникаций, Штутгартский университет
• Недостаточная выборка и ее применение
• Теория сэмплирования для цифрового звука
• Журнал, посвященный теории выборки
• Теорема дискретизации с постоянной амплитудой импульса переменной ширины
• Люке, Ханс Дитер (апрель 1999 г.). «Истоки теоремы об отсчетах» (PDF). Журнал IEEE Communications. 37 (4): 106–108. CiteSeerX  10.1.1.163.2887. Дои:10.1109/35.755459.