Р Е Ш Е Н И Е

Решим задачу для случая (а):

q ^m < r < q ^m+1, (1)

(для конкретных значений q и r всегда можно подобрать з начение m, удовлетворяющее этому неравенству).

Обобщенный алгоритм поиска кода (схемы кодирования) с минимальной избыточностью:

§ для построения элементарных кодов использовать только m и m+1 ярусы кодового дерева;

§ переходить на m+1 ярус только после исчерпания всех возможностей m– го яруса.

Для реализации этого алгоритма необходимо представить r в виде уравнения:

r = (q ^m– n )+ q ×n – t, (2)

где n – количество неконцевых вершин яруса m (будут ветвиться в m+1 ярус);

t (t < q). – количество вершин m+1 яруса, которые не будут задействованы при построении кода (n, t –целые неотрицательные числа).

Формула для определения l_* будет иметь следующий вид:

l_* = [(q ^m– n) × m + (q ×n – t)(m+1)]/ r (3)

q =4; r = 9 в соответствии с формулой (1) m = 1. Для кодирования будет достаточно 1–го и 2–го ярусов обобщенного кодового дерева (см. рис. 1).

r = (q ^m – n )+ q ×n – t, 9= (4 –n)+ 4 n – t ( подбираем целые n и t)

Равенство выполняется для n = 2 и t= 1.

Определим l_* для полученной схемы по формуле (3)

l_* = [(q ^m– n) × m + (q ×n – t)(m+1)]/ r

l_* = ((4-2) х 1 + (4х2 – 1) (1+1)) / 9 = 16/9 = 1,78.

Решение задачи 4 б

Алгоритм решения задачи следующий:

1 Определить q_о по формуле (4).

k = r / (q –1) (остаток от деления)

(4)

k = 10/3 = 1; q₀ = 4.

2 Упорядоченный по убыванию список вероятностей p₁, p₂, …p_r заменяют новым упорядоченным списком вида: p₁, p₂,.. p_j, p,…p_r–qo, где p = p_r–qo+1+ …+ p_r (т.е. суммируют последние q_о штук элементов списка и создают новый упорядоченный список, в который входит полученная сумма); процесс суммирования и упорядочивания (но уже суммируют последние q штукэлементов) продолжается до тех пор, пока в списке вероятностей останется ровно q элементов.

Упорядоченный список 1 (10 чисел) 0,34; 0,18; 0,15; 0,05;… 0,05; 0,04; 0,04

Упорядоченный список 2 (7 чисел) 0,34; 0,18; 0,18; 0,15; 0,05; 0,05; 0,05

Упорядоченный список 3 (4 числа) 0,34; 0,3; 0,18; 0,18;

3 Для последнего свернутого в п.2 списка строится одноярусное кодовое дерево (из начальной вершины выходит q ребер, каждому из которых приписывается буква алфавита O, а каждой вершине 1–го яруса вероятности из последнего свернутого списка).

4 Построить 2–й, 3–й и другие ярусы кодового дерева, на которых развернуть просуммированные вероятности последнего, предпоследнего и т.д. списков(вершины, которым приписаны вероятности букв входного алфавита на любом ярусе, становятся концевыми); в результате таких действий получим кодовое дерево, в котором r концевых вершин и каждой из которых приписана вероятность p_j. Выписав цепи из нулевой вершины к концевым (перечень ребер), получим схему кодирования с минимальной избыточностью.

Величина среднего превышения длины закодированного сообщения над длиной самого сообщения определим по формуле:

= 0,34 + 0,18 + (0,3+0,18)х2 = 1,48.

ЛИТЕРАТУРА

1.Мао В. Современная криптография: теория и практика.: Пер. с англ. – М.: изд. дом «Вильямс», 2005. –768с.:ил.

2.Масленников М. Практическая криптография. –СПб.: БХВ-Петербург, 2003.—464с.:ил.

3 Нечаев В. Элементы криптографии. Основы теории защиты информации: Учеб. пособие для вузов / Под ред. В.А. Садовничего.– 2-е изд стер. – М.: Высш.шк., 2004. – 424с.

4 Яблонский С. Введение в дискретную математику: Учеб. пособие для вузов / Под ред. В.А. Садовничего.– 3-е изд стер. – М.: Высш.шк., 2002. –384с.

5.Андерсон Д. Дискретная математика и комбинаторика.: Пер. с англ. – М.: изд. дом «Вильямс», 2004. –960с.:ил.

Теория алгоритмов: Краткий курс лекций для студентов специальности 7,8.05010102 «Информационные технологи проектирования» / Сост. М.П.Богдан. – Краматорск: ДГМА, 2012. – 60 с.

Автор: Михаил Петрович Богдан,

Редактор саморедактирование

----------------------------------------------------------------------------------

ДДМА. 84313, Краматорськ, вул. Шкадінова, 72

Поиск по сайту: