3.2. Эффективное кодирование  (код Хаффмена)

  Эффективное кодирование – это процедуры  направленные на устранение избыточности.

  Основная  задача эффективного кодирования –  обеспечить, в среднем, минимальное число двоичных элементов на передачу сообщения источника. В этом случае, при заданной скорости модуляции обеспечивается передача максимального числа сообщений, а значит максимальная скорости передачи информации.

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

  Пусть сообщения  входного алфавита имеют соответственно вероятности их появления .

  Тогда алгоритм кодирования Хаффмена состоит в следующем:

  1. Сообщения  располагаются в столбец в  порядке убывания вероятности  их появления.

  2. Два  самых маловероятных сообщения  объединяем в одно сообщение  , которое имеет вероятность, равную сумме вероятностей сообщений , т. е. . В результате получим сообщения , вероятности которых .

  3. Повторяем  шаги 1 и 2 до тех пор, пока  не получим единственное сообщение,  вероятность которого равна 1.

  4. Проводя  линии, объединяющие сообщения  и образующие последовательные подмножества, получаем дерево, в котором отдельные сообщения являются концевыми узлами. Соответствующие им кодовые слова можно определить, приписывая правым ветвям объединения символ “1”, а левым - “0”. Впрочем, понятия “правые” и “левые” ветви в данном случае относительны.

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

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

3.3. Циклические коды (теория)

   Широкое распространение получил класс  линейных кодов которые называются циклическими. Название этих кодов  происходит от их основного свойства: если кодовая комбинация a₁, а₂,......, a_n-1, a_n принадлежит циклическому коду, то комбинации a_n, a₁, а₂,........, a_n-1; a_n-1, a_n, a₁, а₂,......., а_n-2 и т.д., полученные циклической перестановкой элементов, также принадлежат этому коду.

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

   Поскольку любое число в произвольной системе  счисления можно записать в виде a_n-1×х^n-1+a_n-2×x^n-2+...+ а₀×х⁰, где х-основание системы счисления, a_n-1,...,a₀ – цифры этой системы, то переход от двоичного числа к записи в виде многочлена осуществляется следующим образом:

   11011® 1×x⁴ + 1×х³ +0×х²+1×x¹ +1×x⁰=x⁴+x³+x+1

   KK ЦК описываются полиномами обладающими  определенными свойствами. Последние определяются свойствами и операциями той алгебраической системы, к которой принадлежит множество полиномов. Например, в алгебраической системе, которая носит название поля Галуа (GF(x)), действие над коэффициентами полиномов (сложение, вычитание) производится по модулю два. Умножение полиномов должно производиться по модулю некоторого полинома Р_r(х). Эти два условия определяют замкнутость указанных операций: их применение не приводит к кодовым комбинациям, длинна которых больше длинны заданного кода n.

   В циклических кодах разрешенными KK являются те, которые делятся на образующий полином без остатка, из всех возможных полиномов степени n (2ⁿ) только 2^K полиномов (к=n-r) имеют нулевой остаток при делении. Они и образуют множество различных КК ЦК.

   ЦК  являются блочными, равномерными и  линейными. Линейность кодов вытекает из того, что если кодовые слова  принадлежат ЦК, то их линейная комбинация будет также принадлежать ЦК, т.е. обязательно делится без остатка  на производящий полином. Это свойство существенно упрощает аппаратурную реализацию кода. 

3.4. Построение кодера  и декодера циклического  кода. Формирование  кодовой комбинации  циклического кода. 
 

3.5. Задачи 

Задача  № 1. Осуществить кодирование каждого алфавита, используя двоичный код Хаффмена. Определить значения Н_max(x), H(x) и . Рассчитать значения К_сс и К_оэ.

 
 
 
 
 
 

Таблица 1. 
 
 

Построение  кода Хаффмена для восьми сообщений, появляющихся с вероятностями данными в таблице 1. 
 
 
 

 
 
 
 
 
 
 
 
 
 
 

     Рисунок 7.

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Рисунок 8. Кодовое дерево

                              Таблица 2. 
 

    Из  таблицы 2 видно, что полученный код  является неравномерным, причем сообщению с максимальной вероятностью появления соответствует минимальная длительность кодовой комбинации ( ), а сообщению с минимальной вероятностью – максимальная ( ).

    Энтропия:  
 
 

Среднее число  двоичных символов на одно сообщение алфавита объемом K, для неравномерных двоичных кодов, определяется выражением:

.

Эффективность неравномерных кодов оценивается  следующими параметрами:

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

,

где - средняя длина кодовой комбинации при равномерном кодировании,

• коэффициентом относительной эффективности, который показывает степень близости средней длины кодовой комбинации к теоретически возможному пределу H(A).

.

Задача  №2. Записать кодовую комбинацию циклического кода для случая, когда производящий полином имеет вид Р(х)=x⁴+x³+x+1. Кодовая комбинация, поступающая от источника сообщений имеет К=4 элементов и записывается в двоичном виде как число, соответствующее N+3.

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

     Для N=11+3=14₍₁₀₎=>1110₍₂₎, т.к. К должно быть равно 4, получим исходный многочлен А(х)=1000₍₂₎=x³

     Решение:

Решение будем производить по алгоритму:

     1) Умножим полином Q(x) на x^r, где r – число проверочных элементов:

Q(x)=1110₍₂₎=x³+x²+x - исходный полином

(x³+x²+x)x⁴=x⁷+x⁶+x⁵

2. Разделим  полученный полином на производящий P(x):

    
 
 
 
 
 
 
 

3. Прибавим  остаток к  и получим кодовую комбинацию на выходе кодера:

 

Нарисуем  кодирующее устройство с обнаружением ошибок:

Производящий  полином: Р(х)=x⁴+x³+x+1 

1. Число ячеек памяти = 4
2. Число сумматоров = 3

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Рисунок ??? Схема кодирующего устройства. 

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

Составим таблицу: 
 
 
 
 
 
 
 

       При считывании проверочных элементов необходимо разорвать цепь обратной связи. Это делается с помощью ключа К. 
 

 

4.Системы  ПДС с ОС.

     4.1 .Классификация  систем с ОС.

 

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

     В зависимости от назначения ОС различают  системы: