принимать одно из
значений, от 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 мы построим нижнюю оценку вероятности ошибки для таких кодов.