АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Р Е Ш Е Н И Е

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

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 б

 

r q p1, p2, …p12
    0,34; 0,18; 0,15; 0,05;… 0,05; 0,04; 0,04

 

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

 

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

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

(4)

k = 10/3 = 1; q0 = 4.

 

2 Упорядоченный по убыванию список вероятностей p1, p2, …pr заменяют новым упорядоченным списком вида: p1, p2,.. pj, p,…prqo, где p = prqo+1+ …+ pr (т.е. суммируют последние 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 концевых вершин и каждой из которых приписана вероятность pj. Выписав цепи из нулевой вершины к концевым (перечень ребер), получим схему кодирования с минимальной избыточностью.

 

 

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

= 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

 

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |

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



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