Logo GenDocs.ru

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

Загрузка...

Контрольная работа - Расчет вероятностей. Коды Хаффмена и Шеннона-Фено. Расчет энтропии источника - файл AA.doc


Контрольная работа - Расчет вероятностей. Коды Хаффмена и Шеннона-Фено. Расчет энтропии источника
скачать (66.6 kb.)

Доступные файлы (1):

AA.doc195kb.15.05.2007 23:49скачать

Загрузка...

AA.doc

Реклама MarketGid:
Загрузка...
Министерство образования и науки Украины

Национальный горный университет

ИЗДО

Кафедра автоматизации компьютерных систем

Контрольная работа

по теории информации
вариант №**
Выполнил: ст. гр. Б-ЗИ-05

**********************


Преподаватель: доц.Кожевников

Антон Вячеславович

Днепропетровск

2007

Задание 3.

1. Создать текстовый файл, содержащий по пять символов с последовательно идущими кодами, начинающимися с кодов 30+№ и 130+№, где № - порядковый номер студента по списку. Для генерации символа с заданным кодом можно воспользоваться комбинацией клавиш Alt+код (Num Lock).

2. С использованием текстового редактора, имеющего режим отображения шестнадцатеричных кодов, посмотреть символы, содержащиеся в файлах в кодировках Windows (CP-1251) и MS-DOS (CP-866). Для указанных целей могут быть использованы встроенные текстовые редакторы файловых менеджеров OC DOS FAR, Norton (Volkov) Commander. Для включения режима просмотра содержимого файла используется горячая клавиша F3. В режиме просмотра переключение кодовой таблицы для отображения символов осуществляется клавишей F4, а переключение отображения содержимого в виде символов или их кодов – клавишей F8. Зафиксировать и представить в виде таблиц значения:

a. шестнадцатеричных и десятичных кодов символов;

b. символов в кодировках Windows (CP-1251) и MS-DOS (CP-866).

1. Создаем в текстовом редакторе Блокнот текстовый файл, содержащий по пять символов с последовательно идущими кодами с 33 по 37 и с 133 по 137 включительно. Этим кодам соответствуют следующие символы:

33 - ! 133 - Е

34 – « 134 - Ж

35 - # 135 - З

36 - $ 136 - И

37 - % 137 – Й
Сам текстовый файл имеет вид:

!»#$%ЕЖЗИЙ


2. С помощью текстового редактора, встроенного в файловый менеджер, в режиме отображения шестнадцатеричных кодов просматриваем символы, содержащиеся в файле в кодировках Windows (CP-1251) и MS-DOS (CP-866)
Десятеричные коды: 33 34 35 36 37 133 134 135 136 137
Шестнадцатеричные коды: 21 22 23 24 25 с5 с6 с7 с8 с9
Кодировка Windows (CP-1251):


Кодировка MS-DOS (CP-866):



Задание 4.
1. В соответствии с номером варианта рассчитать значения вероятностей появления N=10 сообщений, генерируемых источником. Соотношения для расчета вероятностей:

pi=P(1-P)i-1/1-(1-P)N i=1,…,N P=1/(№div5+2)

2. Построить коды сообщений согласно алгоритмам Хаффмена и Шеннона-Фено.

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

1. Рассчитываем значения вероятностей появления 10 сообщений, генерируемых источником:














2. Построим коды сообщений согласно алгоритму Хаффмена. Для этого расположим все элементы исходной последовательности по уменьшению вероятностей их появления. Далее две наименьшие вероятности объединим как ветки бинарного дерева, одной из которых присвоим кодовый символ 0, а другой 1. Вероятности сложим и результат сложения запишем в промежутке между двумя ближайшими вероятностями. Процесс объединения элементов продолжим, пока суммарная вероятность двух объединяемых веток не станет равной единице. Код для каждого элемента исходной последовательности строится путем обратного спуска по дереву и состоит из кодовых символов веток, которые ведут к указанному элементу.
x1=0.5------------------------------------------------------------------------------------------------------0-1

x2=0.25---------------------------------------------------------------------------------------------0-0.5-1-

x3=0.125-----------------------------------------------------------------------------------0-0.25-1--

x4=0.063-------------------------------------------------------------------------0-0.125-1--

x5=0.031--------------------------------------------------------------0-0.062-1--

x6=0.016----------------------------------------------------0-0.031-1--

x7=7.82*10-3-------------------------------------0-0.015-1--

x8=3.91*10-3--------------------0-6.843*10-3-1--

x9=1.955*10-3--0-2.933*10-3-1--

x10=9.775*10-4-1--

Таким образом, коды элементов первичной последовательности составят:
x10=111111111; x9=111111110; x8=11111110; x7=1111110;

x6=111110; x5= 11110; x4=1110; x3=110; x2=10; x1=0.


Для построения кода Шеннона-Фено элементы исходной последовательности разбиваем на две примерно равновероятные подгруппы. Сообщениям одной из подгрупп присваивается кодовый символ 0, а другим 1. Аналогичное деление на подгруппы продолжаем до тех пор, пока каждая подгруппа не будет образована единственным сообщением. Например, следующим образом:


x1=0.5---1




x2 x2=0.25---1

x3

x4 x3 x3=0.125---1

x5 x4

x6 0 x5 x4 x4=0.063---1

x7 x6 0 x5

x8 x7 x6 0 x5 x5=0.031---1

x9 x8 x7 x6

x10 x9 x8 x7 0 x6 x6=0.016---1

x10 x9 x8 x7

0.5 x10 x9 x8 0 x7 x7=0.00782---1

0.25 x10 x9 x8

0.125 x10 x9 0 x8 x8=0.00391---1

0.062 x10 x9 0

0.031 x10 x9 0 x9---1

0.015 x10

0.006843 x10---0

0.002933

Таким образом, коды элементов первичной последовательности составят:
x10=000000000; x9=000000001; x8=00000001; x7=0000001;

x6=000001; x5= 00001; x4=0001; x3=001; x2=01; x1=1.
3. Определим математическое ожидание длин кодовых слов при использовании оптимальных алгоритмов.



где Pi – вероятность появления i-го сообщения;

L(xi) – длина кодового слова.
Тогда для алгоритма Хаффмена:
M[L]=0.5*1+0.25*2+0.125*3+0.063*4+0.031*5+0.016*6+0.00782*7+0.00391*8+

+0.001955*9+0.0009775*9=1.989

Для алгоритма Феннона-Шено:
M[L]=0.5*1+0.25*2+0.125*3+0.063*4+0.031*5+0.016*6+0.00782*7+0.00391*8+

+0.001955*9+0.0009775*9=1.989
Определим длину кодового слова при использовании нормального двоичного кода. Алфавит кода представляет собой символы 0 и 1 и имеет основание m=2. Код является равномерным, длина кодового слова составляет:



log2n если log2n - целое

k=
[log2n]+1 иначе
Для данного условия:

log210=3.322;
Таким образом, длина кодового слова при использовании нормального двоичного кода равна:
k=[3.322]+1=3+1=4;
Определим нижний предел математического ожидания длины кодового слова по теореме Шеннона. Согласно этой теореме, при кодировании сообщений источника с энтропией H(X) и использованием алфавита из m символов нижний предел математического ожидания длины кодового слова M[L]min составляет:



При использовании двоичного алфавита m=2 указанный предел численно равен величине энтропии источника, выраженной в битах.

Для случая, когда сообщения взаимнонезависимые, но неравновероятные Шеннон получил следующее выражение для энтропии:



где n – количество сообщений, каждое из которых имеет свою вероятность.

Таким образом, для данных условий:


Подставим значения и вычислим нижний предел :
M[L]min=-(0.5*log0.5+0.25*log0.25+0.125*log0.125+0.063*log0.063+

+0.031*log0.031+0.016*log0.016+0.00782*log0.00782+0.00391*log0.00391+

+0.001955*log0.001955+0.0009775*log0.0009775)=1.989
Эффективность кода определяем как отношение нижнего предела математического ожидания длин кодовых слов M[L]min к соответствующей величине для данного кода:




Для алгоритма Хаффмена эффективность кода:

χ = 1.989/1.989=1;
Для алгоритма Шеннона-Фено:

χ = 1.989/1.989=1;

Математическое ожидание числа нулей в кодовых словах, построенных с помощью алгоритмов оптимального кодирования:



Вероятность появления нулей и единиц в кодированной последовательности:





Коэффициент сжатия или энтропия кодированного источника двоичных сообщений:



Избыточность кода:



Вычислим эти величины для алгоритма Хаффмена, подставив числовые значения.
M[n0]= 0.5*1+0.25*1+0.125*1+0.063*1+0.031*1+0.016*1+0.00782*1+0.00391*1+

+0.001955*1+0.0009775*0=0.999;
P(0)=0.999/1.989=0.502;
P(1)=1-0.502=0.498;
μ=-(0.502*log0.502+0.498*log0.498)=0.99999;
R=1-0.99999=1.039*10-5;
Для алгоритма Шеннона-Фено:
M[n0]= 0.5*0+0.25*1+0.125*2+0.063*3+0.031*4+0.016*5+0.00782*6+0.00391*7+

+0.001955*8+0.0009775*9=0.99;
P(0)=0.99/1.989=0.498;
P(1)=1-0.498=0.502;
μ=-(0.502*log0.502+0.498*log0.498)=0.99999;
R=1-0.99999=1.039*10-5;
Задание 5.
1. В соответствии с номером варианта рассчитать:

- энтропию источника и порождаемый им поток информации;

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

- первичного (L=8),

- нормального двоичного




log2n если log2n - целое

k=
[log2n]+1 иначе

- оптимального (Ľ=H);

-пропускную способность канала при наличии помех;

- коэффициенты загрузки канала по информации и по коду для всех вариантов кодирования;


Источник

Канал

n

p1

p2

p3

p4

p5

C0

vc

P

5

0.02

0.02

0.02

0.02

0.02

160

1500

0.06


2. Построить семейство графиков зависимостей (при значениях параметров в соответствии с вариантом) максимальной скорости генерации сообщений источником от:

- вероятности трансформации двоичного символа в канале 0<P<1 для всех рассмотренных вариантов кодирования vs=vs(P;Ľ – var; Ňo, H - const);

- средней длины кодового слова H≤Ľ≤8 для вероятностей трансформации двоичного символа P, 0.5P, 2P vs=vs(Ľ; P – var; Ňo, H - const)

- скорости передачи двоичных символов в канале 0≤vň≤C0 для всех рассмотренных вариантов кодирования vs=vs(vс;Ľ– var; P, H - const);

- скорости передачи двоичных символов в канале 0≤vň≤C0 для вероятностей трансформации символа P, 0.5P, 2P vs=vs(vс;P– var; Ľ, H - const).

1. Рассчитаем энтропию источника по формуле:

;

H=-5*0.02*log0.02=0,564;

Поток, порождаемый источником, определяем как произведение энтропии источника на скорость генерации сообщений:

S=H·vc;

S=0.564*1500=846,578;
Определим скорость генерации двоичных символов кодером для трех вариантов кодирования, а также пропускную способность канала при наличии помех и коэффициенты загрузки канала по информации и по коду для всех вариантов кодирования.


Первичное(L=8).

Скорость генерации двоичных символов:

vk=L·vc
vk=8*1500=12000;
Пропускная способность канала:

C= vc·(1+P·log2(P)+(1-P)·log2(1-P));

C=1500*(1+0.06*log0.06+(1-0.06)*log(1-0.06))=1009;
Коэффициент загрузки канала по информации:
ki=S/C

ki=846.578/1009=0.839;
Коэффициент загрузки канала по коду:
kk= vk/ vc

kk=12000/1500=8;

Нормальное двоичное.

log25=2.322;

L=[2.322]+1=3;

Скорость генерации:

vk=L·vc;

vk=3*1500=4500;
Пропускная способность канала:

C= vc·(1+P·log2(P)+(1-P)·log2(1-P));

C=1500*(1+0.06*log0.06+(1-0.06)*log(1-0.06))=1009;
Коэффициент загрузки канала по информации:

ki=S/C

ki=846.578/1009=0.839;
Коэффициент загрузки канала по коду:
kk= vk/ vc

kk=4500/1500=3;
Оптимальное (Ľ =H).
Скорость генерации:

vk=L·vc;

vk=0.564*1500=846.578;

Пропускная способность канала:

C= vc·(1+P·log2(P)+(1-P)·log2(1-P));

C=1500*(1+0.06*log0.06+(1-0.06)*log(1-0.06))=1009;

Коэффициент загрузки канала по информации:
ki=S/C

ki=846.578/1009=0.839;
Коэффициент загрузки канала по коду:
kk= vk/ vc

kk=846.578/1500=0.564;


2. Построим семейство графиков зависимости максимальной скорости генерации сообщений источником от вероятности трансформации двоичного символа в канале 0<P<1 для всех рассмотренных вариантов кодирования vs=vs(P;Ľ – var; Ňo, H - const);








Первичное








Нормальное двоичное









Оптимальное














Построим семейство графиков зависимости максимальной скорости генерации сообщений источником от средней длины кодового слова H≤Ľ≤8 для вероятностей трансформации двоичного символа P, 0.5P, 2P vs=vs(Ľ; P – var; Ňo, H - const);


Для P=p0












Для P=p0*0.5













Для P=p0*2














Построим семейство графиков зависимости максимальной скорости генерации сообщений источником от скорости передачи двоичных символов в канале 0≤vň≤C0 для всех рассмотренных вариантов кодирования vs=vs(vс;Ľ– var; P, H - const);
Первичное















Нормальное двоичное










Оптимальное












Построим семейство графиков зависимости максимальной скорости генерации сообщений источником от скорости передачи двоичных символов в канале 0≤vň≤C0 для вероятностей трансформации символа P, 0.5P, 2P vs=vs(vс;P– var; Ľ, H - const);
Для P=p0















Для P=p0*0.5















Для P=p0*2














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

Вид неприводимого многочлена:

x6+x5+x3+x2+x+1

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

000011

































Скачать файл (66.6 kb.)

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

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации