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

Будем называть исходным алфавитом, а кодовым алфавитом (выходным).

Определение. Кодирование будем называть функцию , отображение алфавита в множество слов , причем различным буквам в алфавите должны соответствовать различные слова из множества слов в алфавите .

Определение. Пусть некоторое исходное слово в алфавите . Тогда кодирующим словом, согласно кодированию , называют слово , полученное соединением соответствующих кодовых слов (побуквенное кодирование исходного слова):

Пример. Исходный алфавит , выходной алфавит . Функция . Т.к. образы различны, то имеем по определению кодирование. Слова и , соответствующие отдельным буквам, будем называть кодовыми. Ну и для примера, закодируем слово: .

Определение. Кодирование называют корректным (правильным), если различным исходным словам будут соответствовать различные кодирующие слова, согласно кодированию .

Приведенный пример является корректным кодированием, т.к. кодовые слова имеют одну и ту же длину. Действительно, по образу в данной кодировке можно определить исходное слово, считывая образ слева направо и сворачивая кодовые слова в исходные буквы:

Пр имер. Исходный алфавит , кодовый алфавит . Функция . Данное кодирование будет некорректно, т.к. слово 01001 можно раскодировать по-разному:

Определение. Суффиксным кодированием называют кодирование, при котором никакое кодовое слово не начинается ни на какое другое кодовое слово.

Утверждение. Каждое суффиксное кодирование является корректным.

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

Аналогично можно ввести понятие постфиксного кодирования.

Определение. Постфиксным кодированием называют кодирование, при котором ни одно из кодовых слов не является концом никакого другого кодового слова.

Утверждение. Постфиксное кодирование корректно.

Доказательство аналогично предыдущему утверждению.

Дата добавления: 2017-01-13