3.13.2. Коды с фиксированной композицией.

Пусть X — конечное множество множество последовательностей длины с элементами из некоторая последовательность из Обозначим через количество элементов в последовательности х, которые равны данному Очевидно, для любой последовательности

Определение 3.13.1. Вероятностный вектор называется композицией последовательности х. Множество всех последовательностей из композиции которых совпадают и равны называется множеством последовательностей с фиксированной композицией Такое множество будет обозначаться символом X

Лемма 3.13.1. Пусть количество различных композиций для последовательностей Имеет место неравенство

где число элементов в множестве

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

принимать одно из значений, от 0 до Поэтому количество различных наборов чисел определяющих различные композиции, удовлетворяет неравенству (3.13.16). Знак неравенства в (3.13.16) имеет место вследствие того, что среди различных наборов чисел имеются и такие, что которые не определяют никакой композиции. Лемма доказана.

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

Лемма 3.13.2. Пусть для дискретного канала без памяти существует код со средней вероятностью ошибки Тогда существует композиция х и код со средней вероятностью ошибки X такой, что

где число элементов во входном алфавите канала.

Доказательство. Код можно рассматривать как объединение кодов с фиксированными композициями:

где

Из леммы 3.13.1 следует, что такое представление всегда возможно при некотором Среди кодов найдется по крайней мере один код, объем которого

и, следовательно, скорость которого удовлетворяет неравенствам (3.13.17). Обозначим скорость, вероятность ошибки и композицию этого кода через соответственно.

Пусть вероятность ошибки для кода тогда вероятность ошибки X для кода может быть представлена следующим образом:

что совпадает с неравенством (3.13.18). Лемма доказана.

Лемма 3.13.2 позволяет строить нижнюю оценку для вероятности ошибки декодирования произвольных кодов, исходя из нижней оценки вероятности ошибки для кодов с фиксированной композицией. В п. 3.13.3 мы построим нижнюю оценку вероятности ошибки для таких кодов.