4.1 Кодирование

 

Вопросы кодирования играют существенную роль в математике. Кодирование позволяет изучение одних объектов сводить к изучению других. Хорошо известно, какую роль сыграло изображение чисел в десятичной системе счисления. Весьма важным в развитии математики было появление метода координат, который позволил кодировать геометрические объекты при помощи аналитических выражений. Однако, здесь средства кодирования являлись вспомогательным аппаратом и не были предметом изучения. Совсем другое значение получили коды в связи с изучением управляющих систем. Появилась необходимость систематического исследования в области теории кодирования. Основной круг задач может быть прослежен на примере из области связи, который характеризуется схемой, представленной на рис. 1.

 


 

Рис.1

 

Пусть задан алфавит , состоящий из конечного числа букв. Конечную последовательность букв из

будем называть словом в алфавите , а число n – длиной слова А. Длину  слова А будем обозначать через .

Пусть  – множество всех непустых слов в алфавите , и  – некоторое подмножество множества S. Объект, порождающий слова из , называется источником сообщений, а слова из  – сообщениями. Источником сообщений может быть автомат, человек и т.п. Обычно при рассмотрении задач теории кодирования используется дополнительная информация об источнике сообщений в виде некоторого его описания. Существует ряд способов описаний источников сообщений:

1) теоретико-множественное описание осуществляется путем фиксации мощностных характеристик , например,  – множество всех слов заданной длины m;

              

2) статистическое описание осуществляется заданием вероятностных характеристик , например, , и заданы вероятности  появления букв   ;

3) логическое описание – это описание множества  как некоторого «языка». Оно характеризует способы построения множества .

Пусть задан алфавит , где

.

Через В обозначим слово в алфавите  и через  – множество всех непустых слов в алфавите.

Пусть задано отображение F, которое каждому слову А, , ставит в соответствие слово

B=F(A),  .

Слово В будем называть кодом сообщения А, а переход от слова А к его коду – кодированием.

В теории кодирования отображение F задается некоторым алгоритмом.