Глава 5. Другие полезные коды

5.1. Введение

Сушествует много кодов, используемых в различных практических ситуациях. Обсудим лишь некоторые, наиболее важные из них.

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

Далее рассмотрим весьма общий метод кодирования с предсказанием, позволяющий использовать любую структуру, которая может помочь точно предсказать следующий символ. Чем лучше предсказывается следующий символ, тем короче сообщение, которое нужно использовать. При этом о методе предсказания ничего не говорится; предполагается лишь, что написана программа, включающая в себя все используемые сведения о структуре сообщения. Этот метод является весьма общим для сжатие данных. Таким образом, как было обещано ранее, переходим к весьма общим методам и пропускаем много частных кодов, (применяемых в определенных случаях. Можно надеяться, что, встретившись с конкретной ситуацией и зная приведенные здесь коды, читатель сможет предложить свой собственный метод подходящего кодирования сообщений.

Далее обсуждается замечательная идея случайного кодирования, которая, с одной стороны, имеет практическое применение, а с другой — используется при доказательстве основных результатов теории информации. Приводимый здесь частный случай, называемый кодированием с перемешиванием, широко используется при составлении программ для ЭВМ, а также в других ситуациях.

Наконец, рассматриваются коды Грея, используемые для надежного перехода от аналогового представления данных к цифровому и обратно. Такой переход настолько часто встречается на практике (поскольку природа, в основном, снабжает нас аналоговыми сигналами), что эти коды входят в обязательную программу обучения инженеров по вычислительной технике и всех тех, кто имеет дело с реальными сигналами.

Подробности, относящиеся к этому материалу, можно найти в работе [9].