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


Рис.1
Пусть задан
алфавит
, состоящий из конечного числа букв. Конечную
последовательность букв из ![]()
![]()
будем
называть словом в алфавите
, а число n – длиной слова А.
Длину слова А будем обозначать через
.
Пусть
– множество всех
непустых слов в алфавите
, и
– некоторое
подмножество множества S. Объект,
порождающий слова из
, называется источником
сообщений, а слова из
– сообщениями. Источником сообщений может быть автомат, человек и
т.п. Обычно при рассмотрении задач теории кодирования используется дополнительная
информация об источнике сообщений в виде некоторого его описания. Существует
ряд способов описаний источников сообщений:
1) теоретико-множественное описание осуществляется
путем фиксации мощностных характеристик
, например,
– множество всех слов
заданной длины m;
2) статистическое описание осуществляется
заданием вероятностных характеристик
, например,
, и заданы вероятности
появления букв
;
3) логическое описание – это описание
множества
как некоторого
«языка». Оно характеризует способы построения множества
.
Пусть задан
алфавит
, где
.
Через В обозначим слово в алфавите
и через
– множество всех непустых слов в алфавите
.
Пусть задано
отображение F, которое каждому слову А,
, ставит в соответствие слово
B=F(A),
.
Слово В будем называть кодом сообщения А, а переход от слова А к его коду – кодированием.
В теории
кодирования отображение F задается
некоторым алгоритмом.