Тема 5: Элементы теории кодирования

Лекция 1. Теория кодирования. Общие положения

1) Общие положения теории кодирования [1,2,3]

Пусть — алфавит. Конечная последовательность символов из U называется словом в алфавите U. Через S(U) обозначим множество всех слов в алфавите U.

Пусть U и B — два алфавита. Однозначное отображение F произвольного подмножества на подмножества называется кодированием. При этом слова из M называются сообщениями, а их образы — кодами сообщений. Множество С называется кодом множества сообщений М. Алфавит U называется алфавитом сообщений, а алфавит В — кодирующим алфавитом. Кодирование F называется взаимно однозначным, если каждый код сообщения является кодом ровно одного сообщения.

Пусть задано отображение букв алфавита U в множество S (B) вида

Кодирование , удовлетворяющее свойствам:

где под произведением слов АВ понимается приписывание слова В справа к слову А, называется алфавитным кодированием, задаваемым схемой .

2) Свойство префикса. Критерий однозначности декодирования [1,2,3]

Если то называется префиксом, а — суффиксом слова В. Префикс (суффикс) слова В называется собственным, если он отличен от пустого слова (обозначаемого через ) и от самого слова В. Длиной слова называется число букв в нем. Схема обладает свойством префикса, если для любых слов и () из С() слово не является префиксом слова .

Теорема. Алфавитный код С() является однозначно декодируемым тогда и только тогда, когда в графе отсутствуют контуры и петли, проходящие через вершину .