Алфавитное кодирование. Префиксные коды

Пусть B = { b 1, b 2,..., bn } - алфавит. Любая конечная последовательность

символов из B называется словом в алфавите B. Длина слова – количество

символов в нѐм. Через |α | будем обозначать длину слова α.

Пустое слово – слово, не содержащее ни одного символа. Будем

обозначать его через ƛ. Длина пустого слова равна 0.

B+ − множество всех непустых слов в алфавите B.

B* − множество, содержащее все слова в алфавите B, включая пустое

слово.

Пусть L B* - язык сообщений, A ={0,1,..., q -1}, где q 2, - алфавит

канала связи. Алфавитное кодирование задается схемой fv:

где vi A+ - элементарный код, соответствующий букве

Тогда каждому слову языка ставится в соответствие кодовое слово,

определяемое по правилу:

Схема алфавитного кодирования задает код ,

представляющий собой упорядоченное множество элементарных кодовых слов

.

Упорядоченный вектор -

длина элементарного кода vi, называется спектром длин кода V.

К основным требованиям, предъявляемым к алфавитному кодированию,

относится прежде всего взаимная однозначность кодирующего отображения fv. Код V называется взаимно однозначным или однозначно декодируемым,

если различным сообщениям языка соответствуют различные кодовые слова.

Если слово имеет вид , тогда подслово называется префиксом,

а − суффиксом слова .

Префикс (суффикс) слова называется собственным, если он отличен

от пустого слова и от самого слова .

Схема алфавитного кодирования обладает свойством префикса, если

для любых i и j слово vi не является префиксом слова v j.

Алфавитное кодирование, схема которого обладает свойством префикса,

называется префиксным.

Префиксные коды, т. е. коды, у которых никакой из элементарных кодов

не является началом другого элементарного кода, составляют важный класс

однозначно декодируемых кодов переменной длины.

Префиксность кода является достаточным условием его взаимной

однозначности.