Основы построения телекоммуникационных сетей и систем
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
?меют соответственно вероятности их появления p1,p2,p3…pk.
Тогда алгоритм кодирования Хаффмана состоит в следующем:
. Сообщения располагаются в столбец в порядке убывания вероятности их появления.
. Два самых маловероятных сообщения объединяем в одно сообщение b, которое имеет вероятность, равную сумме вероятностей сообщений ak-1, ak т. е. pk-1+pk. В результате получим сообщения a1,a2,a3…ak-1,b, вероятности которых p1, p2, p3…pk-2, pk-1+ pk.
. Повторяем шаги 1 и 2 до тех пор, пока не получим единственное сообщение, вероятность которого равна 1.
. Проводя линии, объединяющие сообщения и образующие последовательные подмножества, получаем дерево, в котором отдельные сообщения являются концевыми узлами. Соответствующие им кодовые слова можно определить, приписывая правым ветвям объединения символ 1, а левым - 0. Впрочем, понятия правые и левые ветви в данном случае относительны (Рис. 3.2.2).
Рис. 3.2.2 Алгоритм Хаффмана
На основании полученной таблицы можно построить кодовое дерево рисунок 3.2.3:
Рис. 3.2.3 Кодовое дерево
Так как в процессе кодирования сообщениям сопоставляются только концевые узлы, полученный код является префиксным, и всегда однозначно декодируем.
При равномерных кодах одиночная ошибка в кодовой комбинации приводит к неправильному декодированию только этой комбинации. Одним из серьёзных недостатков префиксных кодов является появление трека ошибок, т.е. одиночная ошибка в кодовой комбинации, при определенных обстоятельствах, способна привести к неправильному декодированию не только данной, но и нескольких последующих кодовых комбинаций.
Арифметическое кодирование
Еще одним методом кодирования является арифметическое кодирование.
Арифметическое кодирование является методом, позволяющим упаковывать символы входного алфавита без потерь при условии, что известно распределение частот этих символов и является наиболее оптимальным, т.к. достигается теоретическая граница степени сжатия. Предполагаемая требуемая последовательность символов, при сжатии методом арифметического кодирования рассматривается как некоторая двоичная дробь из интервала [0,1). Результат сжатия представляется как последовательность двоичных цифр из записи этой дроби. Идея метода состоит в следующем: исходный текст рассматривается как запись этой дроби, где каждый входной символ является "цифрой" с весом, пропорциональным вероятности его появления. Этим объясняется интервал, соответствующий минимальной и максимальной вероятностям появления символа в потоке. Поясним работу метода на примере.
Математически процесс описывается следующим образом:
Кодирование:
. Границы рабочего интервала d0 и u0 изначально равны 0 и 1 соответственно. Длина рабочего интервала ?0=1.
. Определяем нижнюю границу рабочего интервала (т.е. границы первого закодированного сообщения):
i= di-1+ Qi?i-1
И верхнюю границу:
ui= di-1+ Qi ?i-
где Qi - граница кодируемого сообщения на начальном интервале. А так же определяем длину нового рабочего интервала
?i= ui - di.
Далее кодируем все последующие сообщения подобным образом.
Определяем середину конечного рабочего интервала
где An - число архив, un, dn - верхняя и нижняя границы конечного рабочего интервала соответственно.
Декодирование:
. Первое закодированное сообщение лежит на интервале, в который входит число архив.
. Последующие числа архивы определяются как:
где Aj - новое число архив, Aj-1 - предыдущее число архив, Qj-1 - нижняя граница декодированного сообщения, P(ai) - вероятность этого сообщения.
Графически метод арифметического кодирования представлен на рисунке 3.2.4.
Рис. 3.2.4. Арифметическое кодирование
.3 Циклические коды
Циклическая перестановка элементов разрешенных кодовых комбинаций приводит к появлению разрешенной кодовой комбинации. если а1а2…аn - разрешенная КК, то а2…аn а1 тоже разрешенная КК.
Всякая n-разрядная комбинация может быть представлена полиномом степени (n-1)
= =х5+х3+х2+1
В общем виде:
А(n)=an-1xn-1+an-2xn-2+………+a1x+a0
Свойство разрешенных КК:
Все разрешенные кодовые комбинации делятся на образующий полином без остатка.
Q(x) - полином, соответствующий исходной информационной комбинации
Pr(x) - образующий полином степени r, r- число проверочных разрядов.
\
R(x) - остаток от деления,
G(x) имеет ту же размерность, что и Q(x).
Два способа формирования циклического кода:
способ приводит к получению неразделимого кода.
способ позволяет получить разделимый код, в котором исходная кодовая комбинация является частью разрешенной.
шаг. Исходный полином умножаем на хr
шаг. Получаем остаток R(x)
шаг. Прибавляем остаток к Q(x)* хr
Недостатком первого способа является то, что в результате мы получаем неразделимый код (невозможно отделить проверочные элементы от информационных). Поэтому на практике чаще всего применяется второй способ формирования кодовых комбинаций.
Для обнаружения ошибок в принятой кодовой комбинации достаточно поделить ее на производящий полином. Если принятая кодовая комбинация разрешенная, то остаток от деления будет нулевым. Ненулевой остаток свидетельствует о том, что принятая кодовая комбинация содержит ошибки. По виду остатка (синдрома) можно в некоторых случаях та?/p>