Основные понятия и определения теории кодирования

Оптимальным статистическим (экономным) кодированием называется кодирование, при котором обеспечивается распределение времени на передачу отдельных символов алфавита в зависимости от априорных вероятностей их появления:

; (1)

где C_п - пропускная способность канала; p_i - априорная вероятность i –й кодовой комбинации; t_i -длительность i-й кодовой комбинации.

Оптимальными неравномерными кодами (ОНК) - называются коды, в которых символы алфавита кодируются кодовыми словами минимальной средней длины.

Принципы построения оптимальных кодов:

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

2. Символам первичного алфавита, имеющим наибольшую вероятность появления в сообщении, присваиваются более короткие кодовые слова, при этом, средняя длина кодовых комбинаций имеет минимально-возможную длину.

При таком кодировании избыточность кода, которая вызвана неравной вероятностью символов алфавита, сводится к минимуму (практически к нулю). Оптимальные коды являются неравномерными блочными кодами, при их построении необходимо обеспечить однозначность декодирования. Префиксным (неприводимым)- называется код, в котором ни одна кодовая комбинация не является началом другой. Для обеспечения этого свойства кодовые комбинации должны записываться от корня кодового дерева.

Возможность однозначного декодирования неравномерного кода обеспечивается выполнением требования разделимости (префиксности) кодовых комбинаций.

При неравномерном кодировании производится сжатие данных. Сжатие данных используется как при хранении данных в памяти, так и при их передаче. Оптимальное кодирование можно использовать только в каналах без помех или в случае низкой требовательности к достоверности передаваемой информации.

Существует много методов оптимального, статистического кодирования. Наиболее часто используют оптимальное кодирование по методу Шеннона - Фано и Хаффмена.

Алфавитное кодирование

В общем случае задачу кодирования можно представить следующим образом. Пусть заданы два алфавита А и В, состоящие из конечного числа символов:

  и   .

 Элементы алфавита называются буквами. Упорядоченный набор в алфавите А назовем словом

 

,где  , число п показывает количество букв в слове и называется длиной слова  ,  обозначается п =l( )=| |.

Пустое слово обозначается:

Для слова

 

буква a1, называется началом, или префиксом, слова  , а буква an — окончанием, или постфиксом, слова  .

    Слова можно соединять. Для этого префикс второго слова должен следовать сразу за постфиксом первого, при этом в новом слове они, естественно, утрачивают свой статус, если только одно из слов не было пустым.

    Соединение слов   и   обозначается  , соединение п одинаковых слов   обозначается  , причем  .

    Множество всех непустых слов алфавита А обозначим А*:

 

    Множество А называют алфавитом сообщений, а множество В — кодирующим алфавитом. Множество слов, составленных в алфавите В,обозначим В*.

Обозначим через F отображение слов алфавита А в алфавит В. Тогда слово     назовем кодом слова  .

    Кодированием называют универсальный способ отображения информации при ее хранении, передаче и обработке в виде системы соответствий между элементами сообщений и сигналами, при помощи которых эти элементы можно зафиксировать. Таким образом, код — правило однозначного преобразования (т.е. функция) сообщения из одной символической формы представления (исходного алфавита А) в другую (объектный алфавит В), обычно без каких-либо потерь информации. Процесс преобразования F: А*→В* слов исходного алфавита А в алфавит Вназывается кодированием информации.

    Процесс обратного преобразования слова   в слово   называется декодированием. Таким образом, декодирование — функция, обратная F, т.е. F-1.

    Так как для любого кодирования должна выполняться операция декодирования, то отображение должно быть обратимым (биекция).

    Если |B|= m, то F называется m-ичным кодированием, наиболее распространенный случай В = {0, 1}- двоичное кодирование. Именно этот случай и рассматривается в дальнейшем.

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

    Алфавитное (или побуквенное), кодирование можно задать таблицей кодов. Кодом или кодирующей функцией, будет служить некоторая подстановка  . Тогда

 

, где  ,   .

    Такое побуквенное кодирование обозначается  . Множество кодов букв   называется множеством элементарных кодов. Алфавитное ко­дирование можно использовать для любого множества сообщений. Таким образом, алфавитное кодирование является самым простым, и его всегда можно ввести на непустых алфавитах.

Пример:

Пусть заданы алфавиты

 А = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

 В = {0, 1}.

Тогда таблица кодирования может быть подстановкой:

  .

    Это двоично-десятичное кодирование, оно является взаимнооднозначным и потому допускает декодирование.

Однако схема

 

 не является взаимно-однозначной. Например, набор из шести единиц 111111 может соответствовать как слову 333, так и 77,  а также 111111, 137, 3311 или 7111 плюс любая перестановка.

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

    Схема алфавитного кодирования  называется разделимой, если любое слово, составлен­ное из элементарных кодов, разлагается на элементарные коды единственным образом.

    Алфавитное кодирование с разделимой схемой допускает де­кодирование. Можно доказать, что префиксная схема является разделимой.

    Для того чтобы схема алфавитного кодирования была разделимой, необходимо, чтобы длины элементарных кодов удовлетворяли соотношению, известному как неравенство Макмиллана.