Кодирование в отсутствии шумов

С помощью введенных понятий можно рассмотреть многие информационные процессы. Начнем с дискретных систем без шумов. Здесь главное внимание привлекает проблема эффективности. Важно, чтобы данная информация заняла в запоминающем устройстве как можно меньше ячеек, при передаче желательно занимать канал связи на максимально короткий срок. В такой постановке задачи легко распознается проблема устранения всякой избыточности и эта проблема далеко не тривиальна.

Пусть алфавит системы состоит из m символов. Средствами этого алфавита требуется представить любой из М возможных сигналов {u_k}, k = 1...m, вероятности которых {p(u_k)} заданы. Обычно каждый из сигналов, подлежащих передаче, невозможно обозначить только одним символом и приходится ставить им в соответствие некоторые последовательности символов, которые называют «кодовыми словами». Так как возможна последовательная передачи разных кодовых слов, то они не только должны различаться для разных u_k, но и не должны быть продолжением других, более коротких. Пусть сигналу u_k cоответствует кодовое слово длиной l_k символов. При стационарной передаче сигналов с вероятностями {p(u_k)} средняя длина кодового слова равна cумме всех l_k⋅p(u_k). Возникает вопрос о том, как выбрать L и {l_k}. Вопрос не имеет смысла, пока не задан критерий выбора этих величин. Определим этот критерий так: L и {l_k} должны быть минимальными величинами, такими, при которых еще не происходит потери информации. Напомним, что в отсутствие шумов среднее количество информации на один элемент u_k ансамбля {u_k} равно энтропии этого ансамбля, т.е.

H(U) = -∑p(u_k)⋅log(p(u_k))

а индивилуальное количество информации есть

i(u_k) = -log(u_k).

С другой стороны, на один символ придется максимальное количество i информации, если символы равновероятны и независимы; при этом i = log(m). Поскольку кодирование должно вестись без потерь информации, сразу получаем

Так из общих соображений находим нижние границы для L и l_k. В теории информации доказываются теоремы об условиях достижимости этих границ. Мы не будем приводить эти теоремы. Укажем лишь, что речь идет не только о принципиальной возможности: разработаны процедуры построения кодов, обеспечивающих безизбыточное кодирование (либо сколь угодно близкое к нему).