Введение

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

Введение

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

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

Символ обычно используется для обозначения интервала между образцами и называется периодом дискретизации или интервалом дискретизации. Образцы функции обычно обозначаются (в альтернативной нотации, используемой в более ранней литературе по обработке сигналов), для всех целых значений . Множитель является результатом перехода от непрерывного времени к дискретному времени (см. Дискретное преобразование Фурье#Связь с преобразованием Фурье) и сохраняет энергию сигнала при изменении . Математически идеальный способ интерполяции последовательности включает использование sinc-функций. Каждый образец в последовательности заменяется sinc-функцией, центрированной на оси времени в исходном положении образца, с амплитудой sinc-функции, масштабированной до значения образца. Затем sinc-функции суммируются для получения непрерывной функции. Математически эквивалентный метод использует гребень Дирака и заключается в свертке одной sinc-функции с серией дельта-функций Дирака, взвешенных значениями образцов. Ни один из этих методов не является численно практичным. Вместо этого используется некоторое приближение sinc-функций, ограниченных по длине. Несовершенства, связанные с приближением, известны как ошибка интерполяции. Практические цифро-аналоговые преобразователи не генерируют ни масштабированные и задержанные sinc-функции, ни идеальные дельта-импульсы Дирака. Вместо этого они генерируют кусочно-постоянную последовательность масштабированных и задержанных прямоугольных импульсов (удержание нулевого порядка), обычно за которой следует фильтр нижних частот (называемый "антиалиасинговым фильтром") для удаления ложных высокочастотных реплик (изображений) исходного сигнала базовой полосы.

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

Теорема выборки обычно формулируется для функций одной переменной. Следовательно, теорема непосредственно применима к сигналам, зависящим от времени, и обычно представляется в этом контексте. Однако теорему выборки можно прямолинейно расширить на функции любого числа переменных. Например, изображения в оттенках серого часто представляются как двумерные массивы (или матрицы) вещественных чисел, представляющие относительную интенсивность пикселей (элементов изображения), расположенных в точках пересечения строк и столбцов дискретизации. В результате для однозначного определения каждого пикселя изображения требуется две независимые переменные, или индекса – один для строки и один для столбца. Цветные изображения обычно состоят из комбинации трех отдельных изображений в оттенках серого, каждое из которых представляет один из трех основных цветов – красный, зеленый и синий, или, сокращенно, RGB. Другие цветовые пространства, использующие 3 вектора для представления цветов, включают HSV, CIELAB, XYZ и другие. Некоторые цветовые пространства, такие как голубой, пурпурный, желтый и черный (CMYK), могут представлять цвет четырьмя измерениями. Все они рассматриваются как векторно-значные функции на двумерной дискретизированной области. Подобно одномерным дискретным сигналам, изображения также могут страдать от алиасинга (псевдоизображения), если разрешение дискретизации, или плотность пикселей, недостаточно. Например, цифровая фотография полосатой рубашки с высокой частотой (то есть с малым расстоянием между полосами) может привести к алиасингу рубашки при дискретизации ее изображением с помощью сенсора камеры. Алиасинг проявляется в виде муара. "Решением" для повышения дискретизации в пространственной области в данном случае будет приблизиться к рубашке, использовать сенсор с более высоким разрешением или оптически размыть изображение перед захватом его сенсором с помощью оптического фильтра нижних частот. Другой пример показан на образцах кирпичной кладки. Верхнее изображение демонстрирует эффект, возникающий при невыполнении условия теоремы выборки. Когда программное обеспечение изменяет размер изображения (тот же процесс, который создает эскиз, показанный на нижнем изображении), оно фактически сначала пропускает изображение через фильтр нижних частот, а затем уменьшает его размер, в результате чего получается меньшее изображение, на котором не наблюдается эффект муара. Верхнее изображение показывает результат уменьшения размера изображения без применения фильтра нижних частот: возникает алиасинг. Теорема выборки применима к камерам, где сцена и объектив представляют собой аналоговый источник пространственного сигнала, а сенсор изображения – устройство пространственной дискретизации. Каждый из этих компонентов характеризуется функцией передачи модуляции (MTF), которая представляет точное разрешение (пространственную полосу пропускания), доступное в этом компоненте. Эффекты алиасинга или размытия могут возникать при несоответствии MTF объектива и MTF сенсора. Если оптическое изображение, дискретизируемое сенсором, содержит более высокие пространственные частоты, чем сенсор, то понижающая дискретизация действует как фильтр нижних частот, уменьшая или устраняя алиасинг. Если площадь точки дискретизации (размер сенсора пикселя) недостаточно велика для обеспечения достаточного пространственного антиалиасинга, в систему камеры может быть включен отдельный антиалиасинговый фильтр (оптический фильтр нижних частот) для уменьшения MTF оптического изображения. Вместо использования оптического фильтра графический процессор камер смартфонов выполняет цифровую обработку сигнала для удаления алиасинга с помощью цифрового фильтра. Цифровые фильтры также применяют повышение резкости для усиления контраста от объектива на высоких пространственных частотах, который в противном случае быстро снижается на дифракционном пределе. Теорема выборки также применима к постобработке цифровых изображений, например, к увеличению или уменьшению их размера. Эффекты алиасинга, размытия и повышения резкости можно регулировать с помощью цифровой фильтрации, реализованной в программном обеспечении, которое, по необходимости, следует теоретическим принципам.

Отбор проб сигналов вне базовой полосы

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

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

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

Исторический фон

Теорема выборки была предсказана работой Гарри Найквиста в 1928 году, в которой он показал, что до независимых импульсных отсчетов могут быть переданы через систему с полосой пропускания ; однако он явно не рассматривал проблему дискретизации и восстановления непрерывных сигналов. Примерно в то же время Карл Кюпфмюллер получил аналогичный результат и обсудил импульсную характеристику фильтра, ограничивающего полосу пропускания, – функцию sinc, через ее интеграл, синусный интеграл переходной характеристики; этот фильтр ограничения полосы и восстановления, имеющий центральное значение для теоремы выборки, иногда называют фильтром Кюпфмюллера (но редко так делают в англоязычной литературе). Теорема выборки, по сути, двойственная результату Найквиста, была доказана Клодом Э. Шенноном, Дж. М. Уиттакером в 1935 году и Габором в 1946 году ("Теория связи"). В 1948 и 1949 годах Клод Э. Шеннон опубликовал две революционные статьи, в которых заложил основы теории информации, а также Люке. Например, Люке отмечает, что Х. Раабе, ассистент Кюпфмюллера, доказал теорему в своей докторской диссертации 1939 года; термин "условие Раабе" стал ассоциироваться с критерием однозначного представления (частота дискретизации больше чем в два раза превышает полосу пропускания). Мейеринг упоминает нескольких других первооткрывателей и имена в абзаце и паре сносок:

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