Основы сетевых технологии (90
..pdf
Федеральное агентство связи
Государственное федеральное образовательное учреждение высшего профессионального образования
ПОВОЛЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ И ИНФОРМАТИКИ
ЭЛЕКТРОННАЯ БИБЛИОТЕЧНАЯ СИСТЕМА
Самара
Федеральное агентство связи
Государственное образовательное учреждение высшего профессионального образования
«Поволжский государственный университет телекоммуникаций и информатики»
____________________________________________________________________
_______
Кафедра информационных систем и технологий
А.С.Овсянников
М.А.Бурова
ОСНОВЫ СЕТЕВЫХ ТЕХНОЛОГИЙ
Методические указания
САМАРА 2011
3
Лабораторная работа №1
“Исследование методов эффективного кодирования источников дискретных сообщений”
Цель работы
Изучить особенности и методы построения эффективных кодов и расчѐт их информационных характеристик.
Литература
1.Овсянников А.С. Теория информационных процессов и систем: В 2 ч. Ч.1. Теоретические основы информационных процессов: Допущено Уч.-метод. объедин. вузов по политехн. образов. в качестве учебного пособия для студентов спец. 071900-―Информационные системы и технологии‖ Самарск.гос.арх.-строит.ун-т. Самара,2005. -100 с.
2.Передача дискретных сообщений: Учебник для вузов / Под ред. В.П.Шувалова.- М.:Радио и связь,1990, стр.146-155.
Содержание работы
1.Запустить программу SourceCode.
2.При включении программы автоматически задаѐтся дискретный источник с восемью дискретными сообщениями, при этом каждое сообщение задаѐтся вероятностью его появления на выходе источника. Совокупность сообщений источника ранжирована по убыванию вероятностей сообщений.
3.Выполнение лабораторной работы осуществляется в три этапа:
a.равномерное кодирование;
b.кодирование по методу Шеннона-Фано;
c.кодирование по методу Хаффмена.
4.При выполнении каждого этапа необходимо рассчитать численные значения информационных характеристик исследуемых методов кодирования. Результаты расчѐтов вносятся в соответствующие окна интерфейса программы с точностью до второй значащей цифры с соблюдением правил округления.
5.При ошибках в вычислениях программа выдаст соответствующие сообщения. Выполнить исправления в расчѐтах и повторить ввод данных. При трѐхкратном вводе ошибочных данных программа возвращает выполнение работы в начало этапа.
6.При выполнении всех этапов работы программа выдаѐт сообщение об успешном выполнении лабораторной работы.
Отчѐт о выполненной работе
1.Сообщение программы об успешном выполнении лабораторной работы.
4
2.Расчѐтные формулы и рассчитанные численные значения информационных характеристик.
3.Выводы об особенностях, преимуществах и областях применения рассмотренных методов кодирования.
4.Правильный ответ на контрольный вопрос по заданию преподавателя.
Контрольные вопросы
1.В каких условиях целесообразно применять эффективное кодирование?
2.Преимущества и недостатки эффективных кодов.
3.До какого предела может быть уменьшена средняя длина кодовой комбинации эффективного кода?
4.Как определяется средняя длина кодовой комбинации эффективного кода?
5.Сущность кодирования по методике Шеннона-Фано.
6.Алгоритм кодирования по методу Хаффмена.
7.Какой эффективный код называется префиксным?
8.Дайте определение понятию избыточности кода (коэффициент статистического сжатия).
9.Что называется коэффициентом относительной эффективности?
10.Чему равна минимальная длина двоичных кодовых комбинаций для 32 буквенного алфавита, если буквы в тексте встречаются с равными вероятностями?
11.Алфавит источника содержит шесть сообщений,передаваемых независимо
друг от друга с вероятностями: Р1 = 0,4; Р2 = 0,3; Р3 = 0,1; Р4 = 0,08; Р5 = 0,07; Р6 = 0,05. До какого предела может быть уменьшена средняя длина кодовой комбинации эффективного кода?
12.Первичный алфавит состоит из четырѐх равновероятных символов.Рассчитать коэффициент относительной эффективности.
13.Какой код позволяет минимизировать среднюю длину передаваемой кодовой комбинации?
Краткая теория
Пусть задан дискретный стационарный источник без памяти вида
X= |
x1 ... |
x N |
. |
P(x1 ) ... |
P(x N ) |
Под кодированием сообщений источника Х будем понимать представление каждого сообщения источника Х в виде кодовой
последовательности (вектора) yj Y так, чтобы |
между i-м сообщением |
|
источника Х и j кодовой последовательностью |
|
Y существовало строго |
y j |
||
однозначное соответствие. При этом длина этой кодовой последовательности будет ni , причем мощность источника Y равна M<N.
Возможно кодирование двух типов:
5
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1)равномерное кодирование ni =n=const;
2)неравномерное кодирование ni =var. Рассмотрим эти типы кодирования. Пусть имеется источник вида
X |
x1 x2 x3 x 4 |
x5 |
x6 |
x 7 |
x8 |
. |
1 / 4 1 / 4 1 / 8 1 / 8 1 /16 1 /16 1 /16 1 /16 |
||||||
Здесь M=2 – объем (мощность) кодового множества (двоичный код). Определим эти типы кодирования следующими условиями:
1) n= k ближайшее целое снизу, для которого выполняется неравенство
2 k |
N ; |
|
|
|
|
|
|
2) |
ni I(xi ) . |
|
|
|
|
|
|
Реализация процессов кодирования сведена в табл. 1.1. |
|||||||
|
Таблица 1.1 Кодирование источника |
||||||
|
|
xi |
P(xi) |
I(xi) |
y(1) |
y(2) |
|
|
|
x1 |
1/4 |
2 |
000 |
00 |
|
|
|
x2 |
1/4 |
2 |
001 |
01 |
|
|
|
x3 |
1/8 |
3 |
010 |
100 |
|
|
|
x4 |
1/8 |
3 |
011 |
101 |
|
|
|
x5 |
1/16 |
4 |
100 |
1100 |
|
|
|
x6 |
1/16 |
4 |
101 |
1101 |
|
|
|
x7 |
1/16 |
4 |
110 |
1110 |
|
|
|
x8 |
1/16 |
4 |
111 |
1111 |
|
Средняя длина кодового слова для каждого типа кодирования равна:
1) |
n1 |
n |
|
3 ; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
8 |
|
|
|
1 |
|
1 |
|
1 |
|
1 |
|
1 |
|
1 |
|
1 |
|
1 |
|
|
2) |
n |
|
|
n P(x |
|
) 2 |
2 |
3 |
3 |
4 |
4 |
4 |
4 |
2.75. |
||||||||
|
|
i |
|
|
|
|
|
|
|
|
||||||||||||
|
1 |
|
|
i |
4 |
4 |
8 |
8 |
16 |
16 |
16 |
16 |
|
|||||||||
|
|
i |
1 |
|
|
|
||||||||||||||||
При кодировании источников сообщений существуют верхняя и нижняя границы эффективности кодирования сообщений дискретного источника, которые могут быть определены в виде следующей теоремы.
Теорема (о средней длине кодового слова)
При заданном ансамбле статистически независимых дискретных сообщений источника X, обладающего мощностью N и энтропией H(X), можно так закодировать его сообщения с помощью множества кодовых символов источника Y, мощностью M < N, что среднеe количество кодовых символов
ni , приходящихся на одно сообщение источника X, будет удовлетворять неравенствам:
6
|
H ( X ) |
|
|
|
|
H ( X ) |
1. |
||
|
ni |
||||||||
|
|
|
|
|
|
|
|||
|
log M |
|
|
log M |
|||||
|
|
|
|
|
|
||||
Определим избыточность кода (способа кодирования) в виде |
|||||||||
R y 1 |
H(Y) |
|
1 |
|
H(Y) |
. |
|
||
H0 (Y) |
|
|
|||||||
|
|
|
|
logM |
|
||||
С учетом уравнения информационного баланса имеет место равенство
H(X)= ni H(Y),
откуда информационная избыточность кода определяется в виде
Ry 1 |
|
|
|
H ( X ) |
. |
|
|
|
|
|
|
||
|
|
|
|
|||
|
|
ni log M |
||||
|
|
|
||||
Чем меньше |
ni или чем больше энтропия кодового символа, тем ниже |
|||||
избыточность кодового представления источника, а это достигается лишь в том случае, если распределение вероятности кодовых символов yki близко к равномерному.
Рассмотрим избыточность кодов в ранее приведенном примере. Избыточность источника
H (X )
R x 1 log N 10% .
Для равномерного кодирования
R yPA BH 1 |
H (X ) |
10% . |
|
|
|||
3log M |
|||
|
|
Для неравномерного кодирования
R yН ЕР A BH 1 |
H (X ) |
0% . |
|
|
|||
2.75log M |
|||
|
|
Из теоремы о средней длине кодового слова следует, что наименьшей избыточностью обладают коды, у которых символы в каждой кодовой позиции имеют распределение вероятностей, близкое к равномерному.
Рассмотрим два основных метода эффективного кодирования, которые известны под названиями методов Шеннона Фано и Хаффмена. Оба этих метода рассмотрим относительно случаев двоичного кодирования, т.е. M=2.
Метод кодирования источников Шеннона Фано
Реализация этого метода осуществляется посредством выполнения следующих итерактивных шагов:
7
1). Сообщения дискретного источника Х ранжируются в порядке убывания вероятностей.
2). Из множества порядочных сообщений выделяются два непересекающихся подмножества, модуль разности вероятностей которых минимален. Одно из них кодируется ―0‖, другое ―1‖.
3). Полученные подмножества разбиваются автономно по указанному в п.2 принципу до тех пор, пока каждое из подмножеств не будет состоять из одного сообщения.
Результатом таких процедур будет являться последовательность кодов переменной длины, соответствующих каждому из кодируемых сообщений. Пример кодирования по методу Шеннона Фано представлен в табл. 1.2.
Таблица 1.2 |
Кодирование по методу Шеннона Фано |
||||||||
|
Xi |
|
P(xi) |
yi1 |
yi2 |
yi3 |
yi4 |
yk |
|
|
x1 |
|
¼ |
0 |
0 |
- |
- |
00 |
|
|
x2 |
|
¼ |
0 |
1 |
- |
- |
01 |
|
|
x3 |
|
1/8 |
1 |
0 |
0 |
- |
100 |
|
|
x4 |
|
1/8 |
1 |
0 |
1 |
- |
101 |
|
|
x5 |
|
1/16 |
1 |
1 |
0 |
0 |
1100 |
|
|
x6 |
|
1/16 |
1 |
1 |
0 |
1 |
1101 |
|
|
x7 |
|
1/16 |
1 |
1 |
1 |
0 |
1110 |
|
|
x8 |
|
1/16 |
1 |
1 |
1 |
1 |
1111 |
|
Метод кодирования источников Хаффмена
1.Сообщения источника ранжируются в порядке убывания вероятностей. 2.Группируются два сообщения и вычисляется их суммарная вероятность. При этом два сообщения объединяются в одно.
3.(N-1) сообщения ранжируются в порядке убывания вероятностей и повторяется циклически п.2. Процесс продолжается до тех пор, пока суммарная вероятность не станет равна единице. Результатом указанных процедур является двоичное кодовое дерево, ветви которого кодируются нулем и единицей, а кодовая последовательность каждого сообщения образуется в результате движения от основания дерева к вершине .
Пример кодирования по методу Хаффмена представлен на рис. 1.1.
8
Рис.1.1 Кодирование по методу Хаффмена
9
Лабораторная работа №2 “Исследование циклических кодов”
Цель работы
Изучить особенности циклических кодов. Исследовать закономерности обнаружения и исправления ошибок.
Литература
1.Овсянников А.С. Теория информационных процессов и систем: В 2 ч. Ч.1. Теоретические основы информационных процессов: Допущено Уч.-метод. объедин. вузов по политехн. образов. в качестве учебного пособия для студентов спец. 071900-―Информационные системы и технологии‖ Самарск.гос.арх.-строит.ун-т. Самара,2005. -112 с.
2.Куликовский Л.Ф., Мотов В.В. Теоретические основы информационных процессов: Учебное пособие для вузов.-М.:Высш.шк.,1987.-248с.
3.Основы передачи дискретных сообщений: Учебник для вузов/ Ю.П. Куликов, В.М. Пушкин и др.; Под ред. В.М. Пушкина. - М.: Радио и Связь, 1992.
Содержание работы
1)Выполнить циклическое кодирование 4-х разрядных сообщений;
2)Выполнить циклическое кодирование 5-х разрядных сообщений;
3)Осуществить выбор образующего полинома при 2-х и 3-х кратных ошибках.
Порядок выполнения работы
Для изучения методов помехоустойчивого кодирования применяется исследовательский автоматизированный комплекс CyclicCode. Для того чтобы приступить к выполнению работы необходимо пройти тестовый опрос. При неудачном тестировании пользователь может воспользоваться обширной помощью по помехоустойчивому кодированию.
10
Только после прохождения тестового опроса пользователь может приступить к выполнению работы.
Первый шаг работы – «циклическое кодирование 4-х разрядных сообщений» состоит в выборе по заданию преподавателя одного из вариантов (n,k) кода, где n- число разрядов в кодовой комбинации помехоустойчивого кода, k - число информационных разрядов в кодовой комбинации. Вначале нужно выбрать информационную часть сообщения, которое и будет подвергаться кодированию и декодированию.
Пусть по заданию преподавателя задано сообщение (информационные разряды с k=4) 0100. Вводим это сообщение в поле «Информационная часть кодовой комбинации». Выбор образующего полинома осуществляется по методике, представленной в [1]
После этого необходимо получить кодовую комбинацию циклического кода. Для этого необходимо дописать к информационной части кодовой комбинации 0100 три нулевых разряда, таким образом, получим семи разрядный код 0100000. Полученную кодовую комбинацию разделим на образующий полином 1011:
11