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

О теореме Котельникова и квантовании сигнала

«... на свете есть вещи поважнее самых прекрасных
открытий - это знание метода, которым они сделаны.»

(немецкий философ и математик Г.В. Лейбниц)

В.А.Котельников (1908 - 2005 гг.) в 1926 г. поступил на Электротехнический факультет Московского высшего технического училища имени Н. Э. Баумана (МВТУ), но стал выпускником Московского энергетического института (МЭИ), который выделился из МВТУ как самостоятельный институт. Как одного из лучших выпускников, его оставили в аспирантуре МЭИ. До начала занятий в аспирантуре (1931-1933 гг.) он работал в НИИ Связи Красной Армии (ЦНИИИС). После окончания аспирантуры в 1933 году В.А.Котельников, оставаясь преподавать в МЭИ, поступил на работу в Центральный научно-исследовательский институт (ЦНИИ) Наркомата связи. Пытаясь найти ответ на принципиальный вопрос, какова же минимальная полоса частот, необходимая для передачи по каналу связи сообщения, спектр которого строго ограничен, В.А.Котельников доказал «теорему отсчётов». В 1941 сформулировал положение о том, каким требованиям должна удовлетворять математически недешифруемая система и дал доказательство невозможности её дешифровки. В 1944 г. Котельников занял должность профессора, декана радиотехнического факультета МЭИ, где проработал до 1980 г. В 1953 г. стал академиком. С 1968 по 1990 гг. Котельников - профессор, зав. кафедрой МИФИ.

Доклад В.А. Котельникова "О пропускной способности "эфира" и проволоки" был опубликован в 1933 г. в книге"Материалы по радиосвязи к 1-му Всесоюзному съезду по вопросам технической реконструкции связи", изданной малым тиражом Всесоюзным энергетическим комитетом. Попытка В.А. Котельникова опубликовать статью на эту тему в общесоюзном журнале "Электричество" Энергетического института АН СССР окончилась неудачно. Статья была отклонена, поскольку, как было указано в рецензии, она не представляет интереса для широкого круга инженеров.

Согласно теоремы отсчетов любая функция со спектром, ограниченным частотой F, представима своими отсчетами, взятыми через интервалы времени 1/2F. Независимо теорема отсчетов была установлена в 1949 г. выдающимся американским ученым К. Шенноном - создателем важного раздела теории связи - теории информации. Следует отметить, что как один из частных математических результатов теории интерполяции функции эта теорема была открыта еще в начале XX в. английскими математиками Е.Т. Уитекером и Дж.М.Уитекером. Кроме того, ранние работы Найквиста по определению ширины частотного диапазона, требуемого для передачи информации, заложили основы для последующих успехов К.Шеннона в разработке теории информации.

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

Сегодня общепризнанно, что теорема УКШ - один из фундаментальных результатов теории связи. Эта теорема имеет для техники связи исключительное значение. Однако понимание специалистами фундаментальности сделанного В.А. Котельниковым открытия пришло не сразу.

Из теоремы Котельникова следует, что при дискретизации сигнала полезную информацию будут нести только частоты ниже частоты Найквиста. Частоты выше частоты Найквиста являются зеркальным отображением нижних частот. Если аналоговый сигнал x(t) имеет ограниченный спектр, т.е. не имеет составляющих выше частоты Найквиста, то он может быть восстановлен однозначно и без потерь по своим дискретным отсчётам, взятым с частотой более, чем удвоенная максимальной частоты спектра Fmax. Другими словами: для дискретизации аналогового сигнала без потери информации частота отсчетов должна быть в два раза выше верхней граничной частоты спектра сигнала.

Такая трактовка рассматривает идеальный случай, когда сигнал начался бесконечно давно и никогда не закончится, а также не имеет во временной характеристике точек разрыва. Именно это подразумевает понятие «спектр, ограниченный частотой Fmax». Разумеется, реальные сигналы (например, звук на цифровом носителе) не обладают такими свойствами, так как они конечны по времени и, обычно, имеют во временной характеристике разрывы. Соответственно, их спектр бесконечен. В таком случае полное восстановление сигнала невозможно и из теоремы Котельникова вытекает два следствия:
- любой аналоговый сигнал может быть восстановлен с какой угодно точностью по своим дискретным отсчётам, взятым с частой Fmax (максимальная частота, которой был ограничен спектр реального сигнала);
- если максимальная частота в сигнале превышает половину частоты прерывания, то способа восстановить сигнал из дискретного в аналоговый без искажений не существует.

К примеру, в аудио компакт-дисках используется частота дискретизации 44 100 герц. Частота Найквиста для них - 22 050 герц, она ограничивает верхнюю полосу частот, до которой звук может быть воспроизведён без искажений. Но это - теоретический предел. На практике есть некоторые нюансы. При оцифровке аналогового сигнала с широким спектром необходимо обеспечить срез спектра аналогового сигнала на частоте Найквиста при помощи фильтра очень высокого порядка, чтобы избежать зеркального отражения спектра для частот, лежащих выше частоты Найквиста. Практическая реализация такого фильтра весьма сложна, так как амплитудно-частотные характеристики фильтров имеют не прямоугольную, а колоколообразную форму и образуется некоторая полоса "затухания". Поэтому максимальную частоту спектра дискретизуемого сигнала принимают несколько ниже частоты Найквиста, чтобы обеспечить надёжное подавление фильтром спектра дискретизуемого сигнала.

Термины "аналоговый" и "дискретный" принято относить к радиотехнике: если сигнал порожден физическим процессом, который можно описать непрерывной функцией, то его называют аналоговым, имея в виду его соответствие реальному процессу. Дискретный сигнал, как правило, является последовательностью импульсов, применяемых для кодирования чисел. Чаще всего речь идет о двоичном представлении чисел [4]. В этом случае единица представлена высоким, а нуль - низким потенциалом напряжения (рис.1).

Двоичное представление чисел

Рис. 1. Двоичное представление чисел

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

Представьте себе [2], что необходимо оцифровать аналоговый сигнал, амплитуда которого задана непрерывной функцией времени u(t) (рис. 2а). Несмотря на то, что категория непрерывности в математике имеет определенный смысл, в данном случае представления на уровне здравого смысла будет достаточно. Известно, что измерения реальных физических величин неизбежно сводятся к упрощению, "прореживанию" реальности: выборка осуществляется в отдельные моменты времени и результат отображается с помощью ограниченного набора значений, т.е. "упрощение реальности" идет и по оси t (выборка есть счетное множество), и по оси u (ограничения, накладываемые разрядностью чисел, используемых для записи результатов) (рис. 2б).

форма аналогового сигнала 

Рис. 2. Форма аналогового сигнала

Переход от аналогового (непрерывного) сигнала к множеству выборок его значений в определенные моменты времени (t0, t1, t2 ,...) называется дискретизацией (или семплированием), а представление амплитуды в соответствии с заданной разрядностью - квантованием[3, 4]. Дискретизацию можно сравнить с киносъемкой, где непрерывное движение фиксируется конечным числом кадров в единицу времени.

Отбрасывая на время вопрос о квантовании, можно предположить, что выборки соответствуют точным значениям u(tn). Тогда решение задачи будет заключаться в определении, насколько часто требуется производить выборки, т. е., какова должна быть частота дискретизации, если впоследствии по отсчетам надо будет восстановить исходный сигнал. На рисунках 3 и 4 показаны попытки дискретизации синусоидального сигнала, красные точки соответствуют дискретным значениям - отсчетам (семплам).

Частота исходного сигнала на рис. 3 составляет 0,09 от частоты дискретизации. Результат восстановления аналогового сигнала можно считать приемлемым, так как, после соединения соседних точек, получится кривая, близкая к форме исходного сигнала. А вот рис. 4 показывает иной случай. Здесь частота сигнала близка к частоте дискретизации (0,95), и в результате отсчеты выстраивают синусоиду, только совсем другую, с частотой раз в двадцать меньше. Подобную картину можно иногда наблюдать в кино, когда колеса у кареты вдруг начинают крутиться в обратную сторону.

Феномен изменения частоты синусоиды в результате дискретизации называется aliasing (alias по-английски - псевдоним). О восстановлении формы исходного сигнала говорить уже не приходится.

Частота исходного сигнала

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

Обычно ее формулируют так: "Произвольный сигнал u(t), спектр которого ограничен некоторой частотой FB, может быть полностью восстановлен по последовательности своих отсчетов, следующих с интервалом времени t = 1/(2 FB)", т. е., частота дискретизации должна как минимум вдвое превышать максимальную частоту, присутствующую в спектре сигнала, и тогда проблема будет снята. Сам факт существования такой теоремы и такого критерия может, конечно, служить причиной для эйфории, однако настораживают слова "может быть полностью восстановлен". О том, каким образом сигнал будет восстанавливаться, многие источники скромно умалчивают. Ведь через набор точек на плоскости, соответствующих отсчетам, можно провести бесчисленное множество кривых! (рис. 4). Или имеется в виду эта кошмарная "лестница" (рис. 9)? Конечно же, нет.

Великая формула Котельникова в аналитическом виде выглядит так:

Точки отсчета

 

(1),

 

где k - номер отсчета;
произведение kΔt - момент времени, соответствующий k-му отсчету;
u(kΔt) - само значение k отсчета,
и &#969B = 2&#960FB = &#960/Δt - максимальная (верхняя) частота спектра, только выраженная в радианах. Часто величину Δt называют шагом (интервалом) дискретизации, а FB - частотой Найквиста.

В некоторых источниках частотой Найквиста называют величину, равную 2FB, то есть частоту дискретизации! Это, вообще говоря, непринципиально, но, во избежание путаницы, еще раз подчеркнем: здесь под частотой Найквиста FB подразумевается половина частоты дискретизации.

Частота дискретизации

Таким образом, достаточно располагать частой выборкой значений u(kΔt), и исходная функция (форма сигнала) восстанавливается полностью, ибо равенство в формуле не приближенное, а строгое. Однако, если быть абсолютно точными, равенство справедливо в случае, когда, оцифровывается, например музыкальное произведение, длящееся с Начала Времен (тут мы уже опоздали), и которое никогда не кончится. Если же рассматривать ограниченный отрезок времени, то бесконечной сумма может стать, если t будет бесконечно малой величиной (
Δt --> 0
). Тогда в этом случае, если подступ к бесконечности (непрерывности) осуществляется с ограниченными выборками, то придется забыть о строгих равенствах.

Однако, тем не менее, переходя к практике, можно убедиться, что и теорема, и формула действительно работают. Как это все происходит? Во-первых, выражение на которое умножается значение отсчета в формуле (1), является функцией вида sin x/x, сжатой вдоль горизонтальной оси в B раз (рис. 5).

Спектр функции

Рис. 5. Cпектр функции sin x/x

 

Это так называемая функция Котельникова (базисная функция, функция отсчетов). То, что x здесь равно не B*t, а B*(t - kΔt), приводит к тому, что график сдвигается влево на kΔ t(рис. 6).

Функции Котельникова

Рис. 6. "Частокол из функций Котельникова"

 

В итоге получается "частокол" из функций с вершинами в точках, соответствующих значению отсчетов u(kΔt), так как максимум любого сомножителя (2) есть единица.

На рис. 7 представлены результаты небольшой лабораторной работы на эту тему.

Восстановление аналогового сигнала

Рис. 7. Восстановление аналогового сигнала

 

В качестве шага дискретизации было выбрано число 1 (следовательно, B = &#960), и всего три отсчета: u(0) = 1,2 (коричневая кривая на рисунке), u(1) = 1,4 (зеленая) и u(2) = 1,6 (синяя). Таким образом, слагаемых было не бесконечное число, а всего три, и, тем не менее, результат получился довольно убедительный: суммирующая кривая красного цвета проходит через все три точки, плавно соединяя их, и быстро сходит на нет справа и слева (рис. 7 и рис. 8).

Восстановление аналогового сигнала

Рис. 8. Результат восстановления аналогового сигнала

 

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

После дискретизации аналогового сигнала следующим ключевым моментом является цифровое представление значений отсчетов ("прореживание" вертикальной оси u) - квантование. Реальные значения должны быть представлены в виде N-разрядного двоичного числа. Такое число может принимать 2N различных значений. Например, для 16-битных чисел N=16, а 2N = 65536. Отсюда следует на столько долей надо разбить вертикальную ось, а после решать, в какой отрезок попадает то или иное значение отсчета. Совершенно очевидно, что чем больше разрядов в числе, тем более точной и полной будет кодируемая информация.

Выше дискретизация сигнала сравнивалась с киносъемкой, когда непрерывное движение представляется в виде череды кадров, и частота дискретизации аналогична частоте смены кадров. Если продолжить эту аналогию, то разрядность числа при квантовании можно соотнести с размером кадра. Ширина киноленты может варьироваться от 8 до 70 мм. Ясно, что кадр большего размера способен нести больше информации. Для иллюстрации можно привести еще такой пример. Представьте, что нужно измерить высоту дерева, но в наличии имеется шест лишь с метровыми отметками. Тогда придется считать, что высота дерева равна, скажем, 3 или 4 метрам, а то, что в действительности его длина составляет 3 м 75 см, знать нам будет не дано.

При добавлении двоичному числу нового разряда, увеличивается диапазон принимаемых им значений вдвое. Для амплитуды звукового сигнала, каковой и является функция u(t), это равносильно расширению динамического диапазона на 6 дБ. Таким образом, динамический диапазон цифрового звука прямо пропорционален разрядности числового (двоичного) представления отсчетов. Для 16-битных систем это будет величиной порядка 96 дБ, а для 24-битных - 144 дБ.

Рассмотренное здесь квантование относится к линейному типу, т.е. весь диапазон изменения амплитуды сигнала делится на равные промежутки величиной 1/2N (шаг квантования на рис. 9).

Линейное квантование

Рис. 9. Линейное квантование

 

Кроме линейного квантования используются и другие типы моделей, когда разрядность переменна и зависит от амплитуды. Иногда, чтобы внести в сигнал минимальные искажения, квантование проводят так, что интервалы Δх = хn - хn-1 становятся неравными (нелинейное квантование). Например, часто интервал Δх делают маленьким при малом значении сигнала, чтобы относительная погрешность (шум квантования/сигнал) не становилась очень большой при малых значениях х. Часто принимают Δх = εх, где ε - маленькое число (так называемое логарифмическое квантование). Нелинейное квантование позволяет получить при приемлемой точности хранения сигнала большой динамический диапазон (отношение максимального значения сигнала к минимальному или к величине кванта).

Квантование сигнала

Рис. 10. Квантование сигнала: а — по времени; б — по уровню;
x0(t) — исходный сигнал; x(t) — квантованный сигнал;
Δt — интервал квантования; Δх — уровень квантования.

 

В силу вышесказанного оцифрованный сигнал будет иметь вид лесенки (рис. 9а и рис. 10). Математически это означает, что приходится иметь дело с суммой двух сигналов - исходного и некоего дополнительного зигзагообразного (рис. 9б). Последний называется шумом квантования, и служит источником искажений.

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

Добавочный белый шум называется по-английски dither (дрожь). Сам процесс называется dithering. Из рисунков видно, что амплитуда шума квантования по абсолютной величине не превосходит Δ .

Величина = 1/2N соответствует младшему разряду N-битного числа, поэтому нужно обеспечить появление в этом разряде случайной величины, которая разрушит устойчивую форму шума квантования. Это и достигают, применяя dithering.

Dithering считается "неизбежным злом" в цифровой связи. Увеличивая общий уровень шума, он, тем не менее, обязательно присутствует практически в любом современном аналого-цифровом преобразователе (АЦП). Там, где белый шум отсутствует, это заметно по неудовлетворительному качеству звучания. Кроме АЦП, dithering зачастую применяется в других цифровых процессорах - эквалайзерах, компрессорах и пр.

Другой серьезной проблемой является aliasing, о котором уже упоминалось ранее. Это явление возникает при попытке оцифровать сигнал, частота которого превышает частоту Найквиста. Специалисты из Apogee Electronics Corporation Хулио Альварес (Julio Alvarez) и Ричард Элин (Richard Elen), которые и предложили аналогию с киносъемкой, так объясняют этот феномен. Допустим, снимается на ленту периодически вспыхивающая лампа, частота вспышек которой постепенно увеличивается. В какой-то момент частота вспышек будет равна половине частоты смены кадров. В этот период на ленте будут чередоваться кадры со светом и темнотой, что нормально. Если же частота вспышек сравняется с частотой кадров, то на ленте везде будет свет, или везде - темнота, в зависимости от того, в какую фазу попадает вспышка лампы. Съемка, таким образом, становится бессмысленной.

Если выбирается частота дискретизации равной, скажем, 44,1 кГц, то считается, что она должна обеспечить предел слышимых частот, равный 20 кГц, а что дальше - не имеет значения. А вот и имеет! Если в сигнале, который, в соответствии с теоремой отсчетов Котельникова, оцифровывается с частотой 2FB, то обнаруживается составляющая, имеющая частоту FH > FB. После оцифровки эта составляющая будет иметь другую частоту: FHD = 2FB - FH, которая попадает в область слышимых частот (рис. 11)!

Паразитная составляющая сигнала

Рис. 11. Паразитная составляющая сигнала

 

Ясно, что оцифрованный сигнал будет иметь недопустимые помехи, а запись его на компакт-диск будет непоправимо испорчена. На графике амплитудно-частотной характеристики (АЧХ) вертикальная линия, соответствующая FB, выполняет роль зеркала, отражая при оцифровке высокочастотные составляющие в левую, по отношению к себе< область графика. А такие высокочастотные паразитные составляющие в исходном сигнале обязательно будут присутствовать. Поэтому перед аналого-цифровым преобразованием сигнал необходимо пропустить через фильтр низких частот (ФНЧ).

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

Спектр прямоугольных импульсов

Рис. 12. Спектр последовательности прямоугольных импульсов

 

А если к тому же эта последовательность несет в двоичном виде информацию об исходном аналоговом сигнале u(t), который также имеет спектр определенного вида (рис. 12б), то не должно быть неожиданностью то, что окончательный спектр дискретного сигнала, как результата аналого-цифрового преобразования, представляет из себя столь пышный "букет" (рис. 12в) периодической структуры. Проблема в том, что нужно выделить только центральный "лепесток", отбросив остальные. Как и в предыдущем случае, это можно сделать с помощью ФНЧ. Но здесь начинаются настоящие трудности. Фильтр и в том, и в другом случае должен иметь высокий порядок, не ниже 12-го. Создание таких фильтров вызывает значительные технические сложности, а, кроме того, фильтры высокого порядка вносят заметные фазовые искажения. (См. "Звукорежиссер" №5/2000, статья М. Чернецкого). Возможно, именно из-за неудач в этой области у многих надолго закрепилось отрицательное отношение к цифровому аудио.

Один из путей решения проблемы состоит в увеличении частоты дискретизации в несколько раз. Этот метод носит название oversampling или передискретизации. При аналого-цифровом преобразовании применяется аналоговая передискретизация, то есть выборка отсчетов делается на повышенной частоте. Другая разновидность - цифровая передискретизация, используется при цифро-аналоговом преобразовании. Это искусственное увеличение частоты дискретизации. Между соседними отсчетами вставляются несколько "фиктивных" нулевых отсчетов, и результат затем обрабатывается специальным цифровым фильтром, что позволяет "восстановить" (интерполировать) эти новые значения так, как если бы они были реальными. Применимы и более традиционные методы, когда для интерполяции используются различные вычислительные алгоритмы. В результате частота дискретизации увеличивается в несколько раз, что качественным образом меняет картину: становится допустимым применение аналоговых ФНЧ рядовых характеристик, что существенно упрощает технические решения АЦП и ЦАП.


ИСПОЛЬЗОВАННАЯ ЛИТЕРАТУРА

1. "Форматы звуковых файлов". Журнал "Звукорежиссер", 1999, №№ 8,9,10.

2. "Аналого-цифровые и цифро-аналоговые преобразователи". Журнал "Звукорежиссер", 2000, № 8.

3. Харкевич А. А.. Борьба с помехами, 2 изд., М., 1965.

4. Маркюс Ж. Дискретизация и квантование, пер. с франц., М., 1969.