Лекции, разбитые по вопросам экзамена (2008) / 10

Основная теорема кодирования сообщений заданного множества.

Теорема. Основная теорема кодирования.

Пусть - число символов алфавита кодировки и задано множество сообщений тогда сообщение может быть так закодировано последовательностью символов алфавита кодировки, что для среднего числа символов, приходящихся на 1 сообщение, будут справедливы неравенства:

Средняя длина кодового слова будет отличаться от нижней границы не более, чем на 1 символ.

Доказательство.

1. 

равенство когда .

2. 

Будем достигать нижней границы если.

Предположим, что длины кодовых слов могут быть нецелыми: .