5.5.4. Прямая теорема кодирования.

Теорема 5.5.1. Пусть источник порождает независимые гауссовские с. в. с нулевыми математическими ожиданиями и дисперсиями Пусть эпсилон-энтропия этого источника относительно квадратического критерия качества

Тогда при достаточно больших существует -код такой, что при любом положительном 6

и

Доказательство. Для доказательства теоремы будет указан некоторый метод построения аппроксимирующего множества кода число элементов которого удовлетворяет условию (5.5.35), а средняя ошибка — условию (5.5.36). Чтобы построить такое множество по лемме 5.5.2, достаточно указать аппроксимирующее множество для векторов -мерной сферы Для построения аппроксимирующего множества для по лемме 5.5.1 достаточно указать аппроксимирующее множество для подмножества векторов этой сферы, состоящего из векторов.

Пусть гппроксимируклцее множество для фигурирующее в лемме .5.2. Будем строить это множество методом случайного кодирования, при котором векторы выбираются случайно и независимо из множества множества точек -мерной сферы радиуса Распределение вероятностей, в соответствии с которым происходит случайный выбор, будем считать равномерным на сфере т. е. для любой области на этой сфере положим

где площади области и сферы соответственно.

Предположим, что - некоторый вектор из множества лежащий на сфере Рассмотрим -мерные сферы с центром в точке у и с центром в начале координат:

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

случайном выборе множества вектор у будет аппроксимироваться с ошибкой, превышающей . В силу независимости выбора и условия (5.5.37) эта вероятность определяется соотношением

Так как вероятность не зависит от выбора вектора у, то вероятность того, что хотя бы один вектор множества будет аппроксимироваться с ошибкой, превышающей в — 60, удовлетворяет неравенству

Рис. 5.5.2. доказательству теоремы 5.5.1.

Число при этом является вероятностью выбора «плохого» аппроксимирующего множества, а следовательно, и вероятностью выбора «плохого» кода, который хотя бы один вектор множества аппроксимирует с ошибкой, превышающей

Если мы покажем, что при некоторых эта вероятность меньше единицы, то это будет означать, что в множестве всех кодов, обеспечивающих кодирование источника с ошибкой найдется хотя бы один код со скоростью который обеспечивает кодирование с той же ошибкой. Другими словами, в множестве всех кодов, получающихся при случайном выборе множества не все коды являются «плохими». Поэтому теперь мы покажем, что

Для оценки правой части неравенства (5.5.40) воспользуемся тем, что площадь поверхности -мерной сферы радиуса пропорциональна

где коэффициент пропорциональности зависит от но не зависит от радиусз. Оценим площадь Для этого рассмотрим рис. 5.5.2. Отрезки равны

Можно легко показать (см. задачу 5.5.3), что

где объем -мерного шара радиуса Так как объем -мерного шара пропорционален причем коэффициент пропорциональности равен (см. задачу 5.5.1), то

Простые геометрические расчеты, использующие рис. 5.5.2 и формулы (5.5.42), дают

Таким образом,

Так как при

где использованы результаты задач 5.5.1-5.5.3, то при достаточно больших будет выполняться следующее неравенство:

Положим тогда будет выполняться соотношение (5.5.35), и воспользуемся неравенством Так как при эпсилон-энтропия гауссовского источника без памяти равна

и, следовательно,

то вычисляя натуральный логарифм левой и правой частей неравенства (5.5.48), а также используя указанную оценку для выражение (5.5.50) и неравенство получим

Если теперь задаться некоторым положительным числом и положить

то

и поэтому

Правая часть неравенства (5.5.54) становится отрицательной при достаточно больших значениях Следовательно, при и при достаточно больших вероятность выбрать «плохой» код меньше единицы. При тривиальный код, аппроксимирующее множество которого состоит из одного нулевого вектора, удовлетворяет условиями теоремы. Теорема доказана.