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

Начнём с архипростого примера, а именно: представим себе синусоиду, задаваемую формулой

где $A$ — амплитуда, $f$ — частота, а независимая переменная $t$ пробегает отрезок $[0;\, 1]$. На графике такая синусоида выглядит ещё более тривиально.

Любую синусоиду, которая задаётся формулой (1), можно эффективно хранить в виде двух чисел — частоты и амплитуды, а значит, чтобы «сжать» синусоиду, надо по графику на одном периоде определить эти числа. Делается такое с помощью решения системы уравнений

Нюансы вырожденности тут, конечно, есть: если обе точки попали в нули синусоиды или встали симметрично относительно её максимума, уравнения становятся зависимыми и через эти две точки могут проходить сразу несколько синусоид. Но в целом всё просто, да и решать эту систему нам не принципиально. Принципиально другое: две точки на период однозначно определяют эту самую синусоиду.

Тут напрашивается возражение: а как вычислять частоту, если для этого нужны две точки внутри периода, а самого периода мы ещё не знаем? Вопрос резонный, но ответ простой: я меряю с той частотой, которую умеет прибор, — пусть это $f_s$ отсчётов в секунду, — беру два соседних отсчёта, решаю систему (2) и получаю $f$. Если вычисленная частота оказалась хотя бы вдвое меньше частоты измерения, то есть $f$​${} \le f_s / 2$, то шаг измерения и правда уложился внутрь периода дважды — значит, всё посчитано корректно.

Понятное дело, что одна синусоида никому не интересна, поэтому дальше речь пойдёт про линейную комбинацию синусоид — про спектр периодического или периодизированного сигнала. Периодичность здесь не ограничение: теорема на неё не опирается, а период нужен только затем, чтобы говорить о наборе гармоник. Скажем, мы наблюдаем сигнал в течение времени $T$ — вот это время и возьмём за период, а что сигнал делал до начала наблюдения и что будет делать после, нам всё равно.

Сначала немного слов о ряде Фурье: нас интересует переход из временной области в частотную и возврат обратно. Итак, пусть сигнал $y(t)$ периодичен с периодом $T$, а частоту $n$-й гармоники обозначим $f_n$​${} = n / T$. Соответствующая круговая частота — $\omega_n$​${} = 2 \pi f_n$. Переход в область частот — это два набора коэффициентов, и каждый считается своим интегралом

а обратно сигнал собирается суммированием всех этих гармоник

Свободный член $a_0 / 2$ — среднее значение сигнала. Частоты $\omega_n$ стоят на решётке с шагом $2 \pi / T$, так что спектр периодического сигнала — это просто список амплитуд $A_1, A_2, A_3, \ldots$.

Как можно видеть, чем больше гармоник — тем ближе сигнал к исходному (про явление Гиббса сознательно умолчим, так как это не тема нашей статьи). Получается, что при оцифровке сигнала всегда теряется некоторая часть его спектра. Иногда это даже хорошо — так убирают высокочастотный шум и сглаживают, — но я опять же не про это. Я про то, что сигнал с ограниченным спектром полностью определяется своими значениями, взятыми с круговой частотой дискретизации $\omega_s$​${} = 2 \pi f_s$​${} \ge 2 \omega_{\max}$, где $\omega_{\max}$ — верхняя граница его спектра. То, что я сформулировал выше, было давным-давно сформулировано В. А. Котельниковым аж в 1933 году. Независимо от него ту же теорему получили и другие: границу вдвое выше верхней частоты сигнала указал Гарри Найквист ещё в 1928 году, а Клод Шеннон в 1949 году опубликовал своё доказательство и встроил её в фундамент теории информации — поэтому в западной литературе теорему чаще называют теоремой Найквиста—Шеннона.

Для полного раскрытия вопроса надо бы рассмотреть, каким образом сигнал из спектра восстанавливается обратно. Но сперва чуть-чуть подстелем соломки — напишем всем известные тригонометрические формулы.

Дальше нам жизненно необходимо ядро Дирихле — замкнутая формула для суммы вида $\frac{1}{2}$​${} + \sum_{n=1}^{M} \cos(n x)$, поэтому выведем его сразу. Умножим эту сумму на $2 \sin(x/2)$ и раскроем каждое слагаемое первой формулой из (5) — в ней $\alpha$​${} = (n + 1/2) x$, $\beta$​${} = (n - 1/2) x$

сумма телескопическая: внутренние слагаемые попарно уничтожаются, крайние — сокращаются с $\sin(x/2)$ слева. Осталось поделить обе части на $2 \sin(x/2)$ — это и есть ядро Дирихле

Соломка постелена. Теперь рассмотрим произвольный сигнал и его оцифрованную версию: значения снимаются в моменты времени $k \Delta t$ с равным шагом $\Delta t$.

Измеренный сигнал — это просто набор чисел $y(k \Delta t)$, и записать его можно через функции Хевисайда $\theta(t)$ — ступеньки, равные нулю при $t$​${} < 0$ и единице при $t$​${} \ge 0$: каждый отсчёт держит своё значение до следующего, и вся лестница оказывается линейной комбинацией сдвинутых ступенек

Теперь перенесём нашу лестницу в спектральную область, для чего вычислим коэффициенты по формуле (3). Возьмём косинусный коэффициент; внутри периода лежат $N$​${} = T / \Delta t$ ступенек — нумеруем их с нуля, от $k$​${} = 0$ до $k$​${} = N$​${} - 1$, — и интеграл по периоду распадается на $N$ интегралов по шагам, в каждом из которых значение сигнала постоянно и выносится за знак интеграла

по аналогии для синусного коэффициента получаем

свернём разности в (8) и (9) первыми двумя формулами из (5): полусумма аргументов здесь — середина шага, а полуразность одна и та же для всех $k$; обозначим

Обратите внимание на $\Lambda_n$ — это плата за дискретизацию. По первому замечательному пределу, чем ниже частота сигнала или чем меньше интервал $\Delta t$, тем ближе $\Lambda_n$ к единице. Из (10) видно, что лестница даёт нужные нам суммы по отсчётам, умноженные на $\Lambda_n$, — значит, чтобы получить сами суммы, (10) надо на $\Lambda_n$ поделить. А теперь пора возвращаться из частотной области во временну́ю.

У сигнала с ограниченным спектром гармоник выше $\omega_{\max}$ нет, поэтому сумма (4) обрывается: последняя гармоника — та, у которой $\omega_n$​${} = \omega_{\max}$, то есть $n$​${} = M$​${} = \omega_{\max} T / (2 \pi)$

подставим сюда (10), поделённое на $\Lambda_n$, и поменяем порядок суммирования — сначала по отсчётам, потом по гармоникам

а эту сумму косинусов мы уже умеем складывать — это ядро Дирихле (6) при $x$​${} = 2 \pi u / T$, где $u$​${} = t$​${} - t_k$ — расстояние от точки $t$ до середины шага

осталось отпустить период в бесконечность — вместе с ним растут и число гармоник $M$, и число отсчётов $N$​${} = T / \Delta t$. В знаменателе $\sin(\pi u / T)$​${} \to \pi u / T$, в числителе $\pi (2M + 1) u / T$​${} \to 2 \pi M u / T$​${} = \omega_{\max} u$, а множитель $2 \Delta t / T$ против $2 \pi u / T$ даёт $\Delta t / (\pi u)$. При $\Delta t$​${} = \pi / \omega_{\max}$ — шаге дискретизации ровно на границе $\omega_s$​${} = 2 \omega_{\max}$ — всё сходится начисто

сумма по отсчётам одного периода в этом пределе становится суммой по всем целым $k$, а $u$​${} = t$​${} - t_k$ раскрывается как $t$​${} - \Delta t / 2$​${} - k \Delta t$

во всех слагаемых аргумент сдвинут на $\Delta t / 2$ — ровно на полшага. Отнесём отсчёт к началу его шага, то есть сдвинем время на $\Delta t / 2$ назад, и сдвиг исчезнет

Это и есть ряд Котельникова — вторая половина теоремы: мало знать, что отсчётов достаточно, нужен явный рецепт, как из отсчётов собрать сигнал в любой момент времени, в том числе между ними. Ряд (12) — такой рецепт и есть.

Присмотримся к $\sin u / u$. Она сдвинута в узел $k \Delta t$ и растянута так, что её нули попадают во все остальные узлы решётки: в своём узле она равна единице, во всех чужих — нулю (рис. 4). Отсюда видно, зачем ряд устроен именно так: в любом узле $t$​${} = m \Delta t$ все слагаемые, кроме одного, обращаются в ноль, а единственное выжившее — слагаемое с $k$​${} = m$ — даёт ровно $y(m \Delta t)$. Ряд гарантированно проходит через все отсчёты.

Вот как это выглядит на примере сигнала с рис. 3. Ползунок добавляет слагаемые ряда (12) по одному: каждый отсчёт приносит свою функцию $\sin u / u$, умноженную на значение отсчёта, и сумма этих слагаемых шаг за шагом собирается в исходный сигнал. Отсчётов у нас всего семь, а ряд бесконечный, поэтому у краёв отрезка восстановленная кривая от исходной отходит — это плата за обрыв ряда.