Теорема Котельникова

Теоре́ма Коте́льникова (теорема На́йквиста — Ше́ннона, теорема отсчётов) — фундаментальное утверждение в области цифровой обработки сигналов, связывающее непрерывные и дискретные сигналы. Теорема была предложена и доказана Владимиром Котельниковым в 1933 году. Теорема утверждает, что аналоговый сигнал с финитным спектром (т. е. со спектром, ограниченным некоторой частотой <math>f_m</math>) полностью определяется последовательностью своих дискретных значений (отсчётов), взятых через интервалы времени <math>\Delta t \le 1/(2f_m)</math>, то есть с частотой дискретизации <math>f_d \ge 2f_m</math><ref name="Мазор">Мазор Ю. Л. и др. Энциклопедия Радиотехника, 2002. — 513.</ref><ref>Васин В. А. и др. Радиосистемы передачи информации, 2005. — С. 27.</ref><ref name="Солонина">Солонина А. И. и др. Основы цифровой обработки сигналов: Курс лекций, 2005. — С. 195.</ref>. Другими словами, при выполнении этого условия аналоговый сигнал можно точно восстановить по его дискретным значениям<ref name="Нефедов">Нефедов В. И., Сигов А. С. Теория электросвязи. Учебник для СПО. — C. 374.</ref>. Эта теорема известна под названием теоремы отсчётовШаблон:Sfn.

Пояснение

График модуля спектра сигнала с ограниченной полосой частот. <math>B=f_m</math>.

Спектр сигнала после дискретизации <math>\delta</math>-функциями, имеющий период <math>f_s=f_d,</math> и передаточная характеристика идеального ФНЧ, выделяющего центральный парциальный спектр (верхний рисунок).
Спектр после прохождения дискретного сигнала через идеальный ФНЧ — совпадает со спектром исходного сигнала (нижний рисунок). Таким образом, исходный аналоговый сигнал выделяется из дискретного сигнала без ошибок.

Физически реализуемые сигналы (например, звуковая запись) ограничены во времени, поэтому их спектры не ограничены по частоте (нефинитны). Условие ограниченности спектра сигнала конечной верхней частотой предполагает, что сигнал не ограничен во времени (нефинитен), то есть начался бесконечно давно и никогда не закончится. Но даже спектр бесконечно длительного сигнала будет нефинитен, если сигнал содержит точки разрыва любого рода.

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

• Спектр аналогового сигнала должен быть ограничен некоторой верхней (максимальной) частотой <math>f_m</math> (финитен). Однако так как реальные сигналы имеют бесконечный (нефинитный) спектр, то в качестве максимальной частоты в спектре таких сигналов приходится выбирать некоторую частоту <math>f_m</math>, определяющую эффективную ширину спектра<ref>Мазор Ю. Л. и др. Энциклопедия Радиотехника, 2002. — C. 511.</ref>. Практически частоту дискретизации выбирают с некоторым запасом, например, <math>f_d > 3f_m</math><ref name="Мазор_2">Мазор Ю. Л. и др. Энциклопедия Радиотехника, 2002. — 512.</ref> или <math>f_d=2,5...5~f_m</math><ref name="Васин">Васин В. А. и др. Радиосистемы передачи информации, 2005. — С. 29.</ref>. Поэтому точное восстановление реального сигнала по дискретным значениям принципиально невозможно.

Спектр дискретного (дискретизированного) сигнала является периодическим с периодом, равным частоте дискретизации <math>f_d.</math> Поэтому, если спектр сигнала не ограничен конечной частотой <math>f_m</math>, то возникает эффект наложения парциальных (частичных) составляющих спектра (явление, называемое алиасинг), который может быть уменьшен сглаживанием исходного аналогового сигнала путём фильтрации самых верхних его частот. При этом такое сглаживание (англ. Шаблон:Lang-en2) должно быть выполнено до дискретизации<ref>Рафаэл Гонсалес, Ричард Вудс. Цифровая обработка изображений, 2012. — С. 266.</ref>. Фильтры, сглаживающие сигнал перед дискретизацией, называются антиалиасинговыми<ref>Нефедов В. И., Сигов А. С. Теория электросвязи. Учебник для СПО. — C. 382.</ref>. Например, при дискретизации стандартного телефонного сигнала исходный речевой аналоговый сигнал пропускается через полосовой антиалиасинговый фильтр с полосой пропускания 0,3…3,4 кГц. Тогда минимально допустимой частотой дискретизации будет <math>f_d=</math>6,8 кГц, а в качестве стандартной выбрана 8 кГц<ref name="Солонина"/>.

• Частота дискретизации должна в два или более раз превосходить верхнюю частоту в спектре сигнала<ref name="Мазор"/>. Это требование также следует из того, что спектр дискретного сигнала является периодическим с периодом равным частоте дискретизации. Таким образом, если условие <math>f_d \ge 2f_m</math> не выполняется, то возникает наложение спектров (алиасинг), поэтому будет невозможно восстановить аналоговый сигнал из дискретного представления без искажений. Также для точного восстановления аналогового сигнала из дискретного необходимо наличие физически нереализуемого идеального фильтра нижних частот с полосой пропускания <math>0...f_m</math>. Поэтому восстановление аналогового сигнала по дискретным значениям всегда сопровождается погрешностью<ref name="Мазор_2"/>.

Неравенство <math>f_d \ge 2f_m</math> в условии теоремы Котельникова предполагает, что спектр сигнала на частоте <math>f_m</math> равен нулю. Однако, например, для неограниченного по времени строго синусоидального сигнала с несущей частотой <math>f_0</math>, у которого в спектре содержатся лишь две спектральные линии с частотами <math>-f_0</math> и <math>f_0</math>, спектр равен нулю для <math>|f|</math> строго больших <math>f_0= f_m</math>. Поэтому в этом случае необходимо, чтобы частота дискретизации строго превышала удвоенную максимальную частоту в спектре сигнала, то есть <math>f_s > 2f_m</math>. В противном случае при выборе в соответствии с условием теоремы Котельникова <math>f_d = 2f_m</math> (ровно два отсчета за период) при дискретизации такого сигнала может оказаться так, что все дискретные отсчёты станут равными нулю. Очевидно, что в этом случае восстановление исходного сигнала из дискретного станет невозможным<ref>Рафаэл Гонсалес, Ричард Вудс. Цифровая обработка изображений, 2012. — С. 266—267.</ref>. Однако такое строгое неравенство требуется лишь в том случае, когда значение спектра сигнала на максимальной частоте не равно нулю. Если на максимальной частоте спектр сигнала равен нулю, то необходимость в строгом неравенстве отпадает.

Интерполяционная формула

Теорема Котельникова утверждает, что непрерывный сигнал <math>x(t)</math> можно представить в виде интерполяционного ряда Котельникова<ref name="Мазор"/>:

<math>\widehat{x}(t) = \sum_{k=-\infty}^\infty x(k\Delta t) \operatorname{sinc}\left[\frac{\pi}{\Delta t}(t - k\Delta t)\right],</math>

где <math>\operatorname{sinc}(z) = \sin(z)/z</math> — функция Шаблон:Math.

Интервал дискретизации удовлетворяет ограничениям <math>\Delta t \le \frac{1}{2f_m}</math> или <math>f_d \ge 2f_m</math>. Частоту, равную половине частоты дискретизации, называют частотой Найквиста: <math>f_N=f_d/2</math><ref>Дьяченко Ю. Н, Щепетов А. Г. Технические измерения. Преобразование измерительных сигналов. Учебник и практикум для СПО, 2024. — С. 76.</ref>. При выполнении условий теоремы Котельникова <math>\widehat{x}(t)=x(t)</math><ref>Васин В. А. и др. Радиосистемы передачи информации, 2005. — С. 28.</ref>.

Однако в этой сумме присутствует бесконечное число членов ряда, что практически неосуществимо. Поэтому реально число членов ряда <math>N</math> выбирают конечным, причём погрешность восстановления сигнала будет тем меньшей, чем больше <math>N</math><ref name="Мазор_2"/>.

Также ограничение спектра реального сигнала частотой <math>f_m</math> путём его предварительной фильтрации приводит к погрешности восстановления, относительный средний квадрат которой равен<ref name="Васин"/><ref>Васин В. А. и др. Радиосистемы передачи информации, 2005. — С. 17.</ref>:

<math>\delta_f^2 = \frac{P_\Delta}{P_x}=\frac{\int\limits_{f_m}^{\infty}|X(f)|^2 df}{\int\limits_{0}^{\infty} |X(f)|^2 df},</math>

где <math>P_\Delta = \frac{1}{T}\int\limits_{0}^{T} (\widehat{x}(t)-x(t))^2 dt</math> — мощность разностного сигнала,

<math>\widehat{x}(t)</math> — восстановленный аналоговый сигнал из дискретного,

<math>P_x=\frac{1}{T}\int\limits_{0}^{T} x^2(t) dt</math> — средняя мощность сигнала <math>x(t)</math>,

<math>T</math> — длительность сигнала,

<math>X(f)</math> — спектр сигнала <math>x(t)</math>.

Если спектр сигнала не ограничивать с помощью предварительной фильтрации, то относительный средний квадрат ошибки восстановления сигнала из-за алиасинга в два раза превышает <math>\delta_f^2.</math> Таким образом, предварительная фильтрация сигнала с помощью антиалиасингового фильтра является целесообразной<ref name="автоссылка1">Васин В. А. и др. Радиосистемы передачи информации, 2005. — С. 30.</ref>.

История

Хотя в западной литературе теорема часто называется теоремой Найквиста со ссылкой на работу «{{#if:en|{{#if:|{{{зачин}}} }}{{#if:||{{#switch:en |ab=абхазск. |abq=абазинск. |af=африкаанс |akk=аккадск. |akz=алабама |ale=алеутск. |als=тоскск. |am=амхарск. |an=арагонск. |ang=др.-англ. |ani=андийск. |ar=арабск. |arc=арамейск. |av=аварск. |ae|ave=авест. |awd=аравакск. |az=азерб. |eu=баскск. |ba=башк. |bar=бав. |be=белор. |ber=берберск. |bg=болг. |bn=бенг. |bo=тибетск. |br=брет. |bs=босн. |bua=бурятск. |ca=каталанск. |ce=чеченск. |cel=галльск. |cel-pro=пракельт. |ch=чам. |chm=мар. |cho=чокт. |chu-ru=русск.-церк.-слав. |chu-sr=сербск.-церк.-слав. |chu-bg=болг.-церк.-слав. |cjs=шорск. |ckt=чук. |co=корс. |crh=кр.-тат. |cs=чешск. |csb=кашубск. |cu=ст.-слав. |cv=чувашск. |cy=валл. |da=датск. |dar=дарг. |ddo=цезск. |de=нем. |dsb=н.-луж. |dty=дотели |dum=ср.-нидерл. |egy=егип. |el=греч. |en=англ. |enm=ср.-англ. |eo=эспер. |es=исп. |et=эст. |ett=этрусск. |fa=перс. |fi=финск. |fo=фарерск. |fr=франц. |frk=др.-франкск. |frm=ср.-франц. |fro=ст.-франц. |frr=сев.-фризск. |fry=зап.-фризск. |fur=фриульск. |fy=фризск. |ga=ирл. |gag=гагаузск. |gd=гэльск. |gdo=годобер. |gem=прагерм. |gez=древнеэфиопск. |gin=гинухск. |gkm=ср.-греч. |gl=галис. |gmh=ср.-в.-нем. |gml=ср.-н.-нем. |gmy=микен. |gn=гуарани |goh=др.-в.-нем. |got=готск. |grc=др.-греч. |grc-pro|grk-pro=протогреч. |gsw=алеманнск. |gu=гуджарати |ha=хауса |haw=гавайск. |hbo=др.-евр. |hbs=сербохорв. |he=ивр. |hi=хинд. |hit=хетт. |hr=хорв. |hsb=в.-луж. |ht=гаит. |hu=венг. |hy=армянск. |id=индон. |inh=ингушск. |is=исл. |it=итал. |itl=ительм. |iu=инукт. |ja=яп. |jv=яванск. |ka=груз. |kaa=каракалп. |kas=кашм. |kg=конго |kik=кикуйю |kjh=хакас. |kk=казахск. |kky=кууку-йимитирск. |kl=гренландск. |kn=канн. |ko=корейск. |kom=коми-зыр. |koi=коми-перм. |krc=карач.-балк. |krl=карельск. |kum=кумыкск. |ky=кирг. |la=лат. |lad=сефардск. |lb=люксемб. |lez=лезг. |liv=лив. |lmo=ломбардск. |lng=лангобардск. |lo=лаосск. |lt=лит. |ltg=латг. |lv=латышск. |mad=мадурск. |mdf=мокш. |mg=малаг. |mga=ср.-ирл. |mi=маори |mic=микмакск. |mk=макед. |mn=монг. |mnc=маньчжурск. |mns=мансийск. |mnw=монск. |ms=малайск. |mt=мальтийск. |myv=эрзянск. |myz=мандейск. |na=науру |nah=науатль |niv=нивх. |nds=нж.-нем. |ne=непали |nl=нидерл. |no=норв. |non=др.-сканд. |nuk=нутка |oc=прованс. |ojp=ст.-яп. |orv=др.-русск. |os=осет. |osp=ст.-исп. |osx=др.-сакс. |ota=османск. |otk=др.-тюрк. |pa=пендж. |pap=папьям. |pcd=пикардск. |pdc=пенсильв.-нем. |peo=др.-перс. |phn=финик. |pi=пали |pie=праиндоевр. |pl=польск. |pox=полабск. |ppol=праполинез. |pro=ст.-оксит. |prg=др.-прусск. |pt=порт. |pt-BR=браз.-порт. |qu=кечуа |rm=ретором. |ro=рум. |roa-nor=нормандск. |rom=цыганск. |ru=русск. |rw=киньяруанда |sa=санскр. |sah=якутск. |sc=сард. |scn=сицил. |sco=скотс. |se=северносаамск. |see=сенека |sga=др.-ирл. |sh=сербохорв. |shh=шошонск. |sjd=кильдин-саамск. |sjt=терско-саамск. |sk=словацк. |sl=словенск. |sla-pro=праслав. |smi-pro=прасаамск. |smn=инари-саамск. |sms=коллта-саамск. |sqi|sq=алб. |sr=сербск. |sux=шумерск. |sv=шведск. |sw=суах. |syc=сирийск. |syd=самодийск. |ta=там. |tab=табасаранск. |tg=тадж. |th=тайск. |tin=тинд. |tk=туркм. |tl=тагальск. |tn=тсвана |tnq=таино |tpn=тупи |tr=тур. |trk=тюрк. |tt=тат. |ttt=татск. |txb=тохар. B |ty=таитянск. |tyv=тувинск. |udm=удм. |ug=уйгурск. |uga=угаритск. |uk=укр. |ur=урду |urj-pro=прауральск. |uz=узб. |vec=венет. |vi=вьетн. |vot=водск. |vsn=др.-инд. |xas=камас. |xal=калм. |xcl=грабар |xh=коса |xil=иллир. |xld=лидийск. |xmf=мегр. |xno=англ.-норм. |xpr=парфянск. |xpu=пуническ. |xto=тохар. A |yi=идиш |yrk=ненецк. |zh=кит. |zu=зулусск. |en.}}}}}}{{#if:Certain topics in telegraph transmission theory|{{#if:en|{{#if:|| }}}}Шаблон:Aslinks{{#if:|}}}}{{#if:| }}{{#if:| «{{{3}}}{{#if:|, {{{4}}}}}{{#if:|, {{{5}}}}}»}}{{#if:| ({{{comment}}})}}{{#if:|}}{{#if:|Шаблон:Категория}}{{#if:|Шаблон:Категория}}{{#if:|Шаблон:Категория}}» 1928 года, в этой работе речь идёт лишь о требуемой полосе линии связи для передачи импульсного сигнала (частота следования должна быть меньше удвоенной полосы). Примерно в это же время Шаблон:Iw получил тот же результат<ref> 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).</ref>. О возможности полной реконструкции исходного сигнала по дискретным отсчётам в этих работах речь не идёт. Теорема была предложена и доказана Владимиром Котельниковым в 1933 году в работе «О пропускной способности эфира и проволоки в электросвязи», в которой, в частности, была сформулирована одна из теорем следующим образом<ref>Шаблон:Статья</ref><ref>Харкевич А. А. Спектры и анализ — 4-е изд. — Москва : URSS : ЛКИ, 2007. — С. 89.</ref>: «любую функцию Шаблон:S состоящую из частот Шаблон:S Шаблон:S можно непрерывно передавать с любой точностью при помощи чисел, следующих друг за другом через интервалы времени Шаблон:S». Независимо от него эту теорему в 1949 году доказал Клод Шеннон в работе «Связь при наличии шума»<ref name="Нефедов"/><ref>C. E. Shannon. Communication in the presence of noise. Proc. Institute of Radio Engineers. Vol. 37. No. 1. P. 10—21. Jan. 1949.</ref>, поэтому в западной литературе эту теорему часто называют теоремой Шеннона. Статья Шеннона была написана на основе работы Э. Т. Уиттекера «Функции, представленные распространением теории интерполяции» (1915 год),<ref name="Нефедов"/> также среди источников Шеннон упоминает статью Уильяма Ралфа Беннетта (1941 год), в свою очередь цитирующего диссертацию Шаблон:Iw (1939), которая содержала формулировку теоремы отсчётов<ref name=":0">Шаблон:Статья</ref>. Некоторые японские публикации упоминают «теорему Сомеи», при этом Шаблон:Iw опубликовал свою работу в 1949 году<ref name=":0" />.

В 1999 году Международный научный фонд Эдуарда Рейна (Германия) признал приоритет Котельникова, наградив его премией в номинации «за фундаментальные исследования» за впервые математически точно сформулированную и доказанную в аспекте коммуникационных технологий теорему отсчётов<ref>К 100-летию со дня рождения академика Котельникова Владимира Александровича. Шаблон:Wayback.</ref>. Исторические изыскания показывают, однако, что теорема отсчётов как в части утверждения возможности реконструкции аналогового сигнала по дискретным отсчётам, так и в части способа реконструкции рассматривалась в математическом плане многими учёными и ранее. В частности, первая часть была сформулирована ещё в 1897 году Эмилем Борелем<ref>Erik Meijering. A Chronology of Interpolation From Ancient Astronomy to Modern Signal and Image Processing, Proc. IEEE, 90, 2002.</ref>.

Вариации и обобщения

Впоследствии было предложено большое число различных способов аппроксимации сигналов с ограниченным спектром, обобщающих теорему отсчётов<ref>Джерри А. Дж. Теорема отсчётов Шеннона, её различные обобщения и приложения. Обзор. — ТИИЭР, т. 65, № 11, 1977, с. 53—89.</ref><ref>Хургин Я. И., Яковлев В. П. Прогресс в Советском Союзе в области теории финитных функций и её применений в физике и технике. — ТИИЭР, 1977, т. 65, № 7, с. 16—45.</ref>.

Так, вместо кардинального ряда по функциям Шаблон:Math, являющимся сдвинутыми копиями импульсной характеристики идеального фильтра нижних частот, можно использовать алгебраические полиномы. В частности, на практике применяются ступенчатая и линейная интерполяции<ref name="автоссылка1" />, ряды по конечно- или бесконечнократным свёрткам функций Шаблон:Math.

Относительный средний квадрат погрешности интерполяции зависит от спектра сигнала <math>x(t),</math> способа интерполяции и частоты дискретизации. При ступенчатой и линейной интерполяциях частота <math>f_d</math> должна существенно превышать частоту дискретизации по Котельникову (<math>2f_m</math>). Для сигналов с прямоугольной спектральной плотностью мощности, ограниченной частотой <math>f_m</math>, частота дискретизации для восстановления сигнала с относительным средним квадратом погрешности <math>\delta^2</math> равна<ref>Васин В. А. и др. Радиосистемы передачи информации, 2005. — С. 32.</ref>:

• для ступенчатой интерполяции <math>f_d = \frac{\pi}{6\delta} 2f_m</math>,
• для линейной интерполяции <math>f_d = \frac{\pi}{4{,}95\sqrt{\delta}} 2f_m</math>.

Например, при <math>\delta=0{,}1</math> для ступенчатой интерполяции <math>f_d = 5{,}23\cdot2f_m,</math> для линейной интерполяции <math>f_d = 2\cdot2f_m.</math>

Справедливо следующее обобщение ряда Котельникова непрерывной функции <math>x(t)</math> с финитным спектром с максимальной частотой <math>f_c</math> на основе преобразований Фурье атомарных функций<ref>Басараб М. А., Зелкин Е. Г., Кравченко В. Ф., Яковлев В. П. Цифровая обработка сигналов на основе теоремы Уиттекера-Котельникова-Шеннона. — М.: Радиотехника, 2004.</ref>:

<math>x(t) = \sum_{k=-\infty}^\infty x(k\Delta t) \prod_{n=1}^M \operatorname{sinc}\left[\frac{\pi}{a^{n-1} \Delta t} (t - k\Delta t)\right],</math>

параметры <math>a</math> и <math>M</math> удовлетворяют неравенству <math>a^{M-1} (a - 2) + 1 > 0,</math> а интервал дискретизации:

<math>0 < \Delta t \leqslant \frac{1}{2f_c} \left[1 + \frac{a^{M-1} + 1}{a^{M-1} (a - 1)}\right].</math>

См. также

• Экстраполятор нулевого порядка
• Экстраполятор первого порядка
• Квантование (обработка сигналов)
• Передискретизация
• Теорема отсчётов в частотной области

Литература

• 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