Теоре́ма Коте́льникова (теорема На́йквиста — Ше́ннона, теорема отсчётов) — фундаментальное утверждение в области цифровой обработки сигналов, связывающее непрерывные и дискретные сигналы. Теорема была предложена и доказана Владимиром Котельниковым в 1933 году. Теорема утверждает, что аналоговый сигнал с финитным спектром (т. е. со спектром, ограниченным некоторой частотой ) полностью определяется последовательностью своих дискретных значений (отсчётов), взятых через интервалы времени , то есть с частотой дискретизации Мазор Ю. Л. и др. Энциклопедия Радиотехника, 2002. — 513.Васин В. А. и др. Радиосистемы передачи информации, 2005. — С. 27.. Другими словами, при выполнении этого условия аналоговый сигнал можно точно восстановить по его дискретным значениям. Эта теорема известна под названием теоремы отсчётов.
Пояснение
Физически реализуемые сигналы (например, звуковая запись) ограничены во времени, поэтому их спектры не ограничены по частоте (нефинитны). Условие ограниченности спектра сигнала конечной верхней частотой предполагает, что сигнал не ограничен во времени (нефинитен), то есть начался бесконечно давно и никогда не закончится. Но даже спектр бесконечно длительного сигнала будет нефинитен, если сигнал содержит точки разрыва любого рода.
Теорема Котельникова определяет условия, при которых аналоговый сигнал может быть точно восстановлен по своим дискретным значениям:
Спектр аналогового сигнала должен быть ограничен некоторой верхней (максимальной) частотой (финитен). Однако так как реальные сигналы имеют бесконечный (нефинитный) спектр, то в качестве максимальной частоты в спектре таких сигналов приходится выбирать некоторую частоту , определяющую эффективную ширину спектраМазор Ю. Л. и др. Энциклопедия Радиотехника, 2002. — C. 511.. Практически частоту дискретизации выбирают с некоторым запасом, например, Мазор Ю. Л. и др. Энциклопедия Радиотехника, 2002. — 512. или Васин В. А. и др. Радиосистемы передачи информации, 2005. — С. 29.. Поэтому точное восстановление реального сигнала по дискретным значениям принципиально невозможно. Спектр дискретного (дискретизированного) сигнала является периодическим с периодом, равным частоте дискретизации Поэтому, если спектр сигнала не ограничен конечной частотой , то возникает эффект наложения парциальных (частичных) составляющих спектра (явление, называемое алиасинг), который может быть уменьшен сглаживанием исходного аналогового сигнала путём фильтрации самых верхних его частот. При этом такое сглаживание () должно быть выполнено до дискретизацииРафаэл Гонсалес, Ричард Вудс. Цифровая обработка изображений, 2012. — С. 266.. Фильтры, сглаживающие сигнал перед дискретизацией, называются антиалиасинговыми. Например, при дискретизации стандартного телефонного сигнала исходный речевой аналоговый сигнал пропускается через полосовой антиалиасинговый фильтр с полосой пропускания 0,3…3,4 кГц. Тогда минимально допустимой частотой дискретизации будет 6,8 кГц, а в качестве стандартной выбрана 8 кГц. Частота дискретизации должна в два или более раз превосходить верхнюю частоту в спектре сигнала. Это требование также следует из того, что спектр дискретного сигнала является периодическим с периодом равным частоте дискретизации. Таким образом, если условие не выполняется, то возникает наложение спектров (алиасинг), поэтому будет невозможно восстановить аналоговый сигнал из дискретного представления без искажений. Также для точного восстановления аналогового сигнала из дискретного необходимо наличие физически нереализуемого идеального фильтра нижних частот с полосой пропускания . Поэтому восстановление аналогового сигнала по дискретным значениям всегда сопровождается погрешностью.
Неравенство в условии теоремы Котельникова предполагает, что спектр сигнала на частоте равен нулю. Однако, например, для неограниченного по времени строго синусоидального сигнала с несущей частотой , у которого в спектре содержатся лишь две спектральные линии с частотами и , спектр равен нулю для строго больших . Поэтому в этом случае необходимо, чтобы частота дискретизации строго превышала удвоенную максимальную частоту в спектре сигнала, то есть . В противном случае при выборе в соответствии с условием теоремы Котельникова (ровно два отсчета за период) при дискретизации такого сигнала может оказаться так, что все дискретные отсчёты станут равными нулю. Очевидно, что в этом случае восстановление исходного сигнала из дискретного станет невозможнымРафаэл Гонсалес, Ричард Вудс. Цифровая обработка изображений, 2012. — С. 266—267.. Однако такое строгое неравенство требуется лишь в том случае, когда значение спектра сигнала на максимальной частоте не равно нулю. Если на максимальной частоте спектр сигнала равен нулю, то необходимость в строгом неравенстве отпадает.
Интерполяционная формула Теорема Котельникова утверждает, что непрерывный сигнал можно представить в виде интерполяционного ряда Котельникова:
где — функция .
Интервал дискретизации удовлетворяет ограничениям или . Частоту, равную половине частоты дискретизации, называют частотой Найквиста: . При выполнении условий теоремы Котельникова Васин В. А. и др. Радиосистемы передачи информации, 2005. — С. 28..
Однако в этой сумме присутствует бесконечное число членов ряда, что практически неосуществимо. Поэтому реально число членов ряда выбирают конечным, причём погрешность восстановления сигнала будет тем меньшей, чем больше .
Также ограничение спектра реального сигнала частотой путём его предварительной фильтрации приводит к погрешности восстановления, относительный средний квадрат которой равенВасин В. А. и др. Радиосистемы передачи информации, 2005. — С. 17.:
где — мощность разностного сигнала, — восстановленный аналоговый сигнал из дискретного, — средняя мощность сигнала , — длительность сигнала, — спектр сигнала .
Если спектр сигнала не ограничивать с помощью предварительной фильтрации, то относительный средний квадрат ошибки восстановления сигнала из-за алиасинга в два раза превышает Таким образом, предварительная фильтрация сигнала с помощью антиалиасингового фильтра является целесообразнойВасин В. А. и др. Радиосистемы передачи информации, 2005. — С. 30..
История Хотя в западной литературе теорема часто называется теоремой Найквиста со ссылкой на работу «» 1928 года, в этой работе речь идёт лишь о требуемой полосе линии связи для передачи импульсного сигнала (частота следования должна быть меньше удвоенной полосы). Примерно в это же время получил тот же результат Küpfmüller K. Über die Dynamik der selbsttätigen Verstärkungsregler. Elektrische Nachrichtentechnik, vol. 5, no. 11, pp. 459—467, 1928. (German); K. Küpfmüller, On the dynamics of automatic gain controllers, Elektrische Nachrichtentechnik, vol. 5, no. 11, pp. 459—467. (English translation).. О возможности полной реконструкции исходного сигнала по дискретным отсчётам в этих работах речь не идёт. Теорема была предложена и доказана Владимиром Котельниковым в 1933 году в работе «О пропускной способности эфира и проволоки в электросвязи», в которой, в частности, была сформулирована одна из теорем следующим образомХаркевич А. А. Спектры и анализ — 4-е изд. — Москва : URSS : ЛКИ, 2007. — С. 89.: «любую функцию состоящую из частот можно непрерывно передавать с любой точностью при помощи чисел, следующих друг за другом через интервалы времени ». Независимо от него эту теорему в 1949 году доказал Клод Шеннон в работе «Связь при наличии шума»C. E. Shannon. Communication in the presence of noise. Proc. Institute of Radio Engineers. Vol. 37. No. 1. P. 10—21. Jan. 1949., поэтому в западной литературе эту теорему часто называют теоремой Шеннона. Статья Шеннона была написана на основе работы Э. Т. Уиттекера «Функции, представленные распространением теории интерполяции» (1915 год), также среди источников Шеннон упоминает статью Уильяма Ралфа Беннетта (1941 год), в свою очередь цитирующего диссертацию (1939), которая содержала формулировку теоремы отсчётов. Некоторые японские публикации упоминают «теорему Сомеи», при этом опубликовал свою работу в 1949 году.
В 1999 году Международный научный фонд Эдуарда Рейна (Германия) признал приоритет Котельникова, наградив его премией в номинации «за фундаментальные исследования» за впервые математически точно сформулированную и доказанную в аспекте коммуникационных технологий теорему отсчётовК 100-летию со дня рождения академика Котельникова Владимира Александровича. .. Исторические изыскания показывают, однако, что теорема отсчётов как в части утверждения возможности реконструкции аналогового сигнала по дискретным отсчётам, так и в части способа реконструкции рассматривалась в математическом плане многими учёными и ранее. В частности, первая часть была сформулирована ещё в 1897 году Эмилем БорелемErik Meijering. A Chronology of Interpolation From Ancient Astronomy to Modern Signal and Image Processing, Proc. IEEE, 90, 2002. ..
Вариации и обобщения Впоследствии было предложено большое число различных способов аппроксимации сигналов с ограниченным спектром, обобщающих теорему отсчётовДжерри А. Дж. Теорема отсчётов Шеннона, её различные обобщения и приложения. Обзор. — ТИИЭР, т. 65, № 11, 1977, с. 53—89.Хургин Я. И., Яковлев В. П. Прогресс в Советском Союзе в области теории финитных функций и её применений в физике и технике. — ТИИЭР, 1977, т. 65, № 7. — С. 16—45..
Так, вместо кардинального ряда по функциям , являющимся сдвинутыми копиями импульсной характеристики идеального фильтра нижних частот, можно использовать алгебраические полиномы. В частности, на практике применяются ступенчатая и линейная интерполяции, ряды по конечно- или бесконечнократным свёрткам функций .
Относительный средний квадрат погрешности интерполяции зависит от спектра сигнала способа интерполяции и частоты дискретизации. При ступенчатой и линейной интерполяциях частота должна существенно превышать частоту дискретизации по Котельникову (). Для сигналов с прямоугольной спектральной плотностью мощности, ограниченной частотой , частота дискретизации для восстановления сигнала с относительным средним квадратом погрешности равнаВасин В. А. и др. Радиосистемы передачи информации, 2005. — С. 32.: для ступенчатой интерполяции , для линейной интерполяции .
Например, при для ступенчатой интерполяции для линейной интерполяции
Справедливо следующее обобщение ряда Котельникова непрерывной функции с финитным спектром с максимальной частотой на основе преобразований Фурье атомарных функцийБасараб М. А., Зелкин Е. Г., Кравченко В. Ф., Яковлев В. П. Цифровая обработка сигналов на основе теоремы Уиттекера-Котельникова-Шеннона. — М.: Радиотехника, 2004.:
параметры и удовлетворяют неравенству а интервал дискретизации:
См. также Экстраполятор нулевого порядка Экстраполятор первого порядка Квантование (обработка сигналов) Передискретизация Теорема отсчётов в частотной области
Примечания
Литература H. Nyquist. Certain topics in telegraph transmission theory. Trans. AIEE, vol. 47, pp. 617—644, Apr. 1928. Котельников В. А. О пропускной способности эфира и проволоки в электросвязи — Всесоюзный энергетический комитет. // Материалы к I Всесоюзному съезду по вопросам технической реконструкции дела связи и развития слаботочной промышленности, 1933. Репринт статьи в журнале УФН, 176:7 (2006), 762—770.
Ссылки Теорема Котельникова на dsplib.org Sampling of analog signals Интерактивная презентация дискретизации по времени. Institute of Telecommunications, University of Stuttgart
Котельникова Категория:Цифровая обработка сигналов Котельников Котельникова