Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Министерство науки и образования Российской Федерации
КАЗАНСКИЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ имени А.Н. Туполева
Отчет
по лабораторной работе №2 по дисциплине
«Теория информации»
Тема: «Оптимальное кодирование»
Выполнил студент
группы 4112
Мухаметшин Инсаф Рафилович
Проверила:
Ляшева Стелла Альбертовна
Казань 2013
9 вариант
Сообщение:
aacabaaaacdbbacbddccbbaccbbddadadbba
Задание 1
|
Вероятности состояний сообщения |
|||||
|
Состояние |
a |
b |
c |
d |
всего |
|
Число наблюдений для сообщения |
12 |
10 |
7 |
7 |
36 |
|
Вероятность для сообщения |
0,333333333 |
0,277777778 |
0,194444 |
0,194444 |
1 |
Задание 2
Энтропии сообщения:
1,960431
Задание 3
|
Код Шеннона-Фано для сообщения |
|||||
|
Состояние |
Количество |
Pi |
Номер шага(ni) |
Код |
|
|
1 |
2 |
||||
|
a |
12 |
12/36 |
0 |
0 |
00 |
|
b |
10 |
10/36 |
1 |
01 |
|
|
c |
7 |
7/36 |
1 |
0 |
10 |
|
d |
7 |
7/36 |
1 |
11 |
Код: 000010000100000000101101010010011111101001010010100101111100110011010100
Средняя длина кода:
бит
Избыточность:
.
Код Хаффмана для сообщения:
, X = {a,b,c,d};
, X1 = {x1,a,b};
, X2 = {x2, x1};
, X3 = {x3};
Таким образом, получены следующие коды исходных символов:
a = 00, b = 01, c = 10, d = 11.
Код: 000010000100000000101101010010011111101001010010100101111100110011010100
Средняя длина кода будет равна
бит.
Избыточность:
.
Aa ca ba aa ac db ba cb dd cc bb ac cb bd da da db ba
|
Код Шеннона-Фано для сообщения |
|||||||
|
состояния |
P |
Шаг 1 |
Шаг 2 |
Шаг 3 |
Шаг 4 |
Шаг 5 |
Код |
|
aa |
0,111111111 |
0 |
0 |
0 |
000 |
||
|
ab |
0,092592593 |
1 |
0 |
0010 |
|||
|
ba |
0,092592593 |
1 |
0011 |
||||
|
bb |
0,077160494 |
1 |
0 |
010 |
|||
|
ac |
0,064814815 |
1 |
0 |
0110 |
|||
|
ad |
0,064814815 |
1 |
0111 |
||||
|
ca |
0,064814815 |
1 |
0 |
0 |
0 |
1000 |
|
|
da |
0,064814815 |
1 |
1011 |
||||
|
bc |
0,054012346 |
1 |
0 |
1010 |
|||
|
bd |
0,054012346 |
1 |
1011 |
||||
|
cb |
0,054012346 |
1 |
0 |
0 |
1100 |
||
|
db |
0,054012346 |
1 |
0 |
11010 |
|||
|
cc |
0,037808642 |
1 |
11011 |
||||
|
cd |
0,037808642 |
1 |
0 |
1110 |
|||
|
dc |
0,037808642 |
1 |
0 |
11110 |
|||
|
dd |
0,037808642 |
1 |
11111 |
Средняя длина кода будет равна
бит.
Избыточность:
Код Хаффмана для сообщения:
X ={aa,ab,ba,bb,ac,ad,ca,da,bc,bd,cb,db,cc,cd,dc,dd};
x1=(dc,dd)
X1 ={aa,ab,ba,bb,x1,ac,ad,ca,da,bc,bd,cb,db,cc,cd,};
x2=(cc,cd)
X2 = { aa,ab,ba,bb,x2,x1,ac,ad,ca,da,bc,bd,cb,db};
x3=(cb,db), x4=(bc,bd)
X4 = { aa,x4,x3,ab,ba,bb,x2,x1,ac,ad,ca,da };
x5=(ca,da), x6=(ac,ad)
X6 = {x6,x5,aa,x4,x3,ab,ba,bb,x2,x1};
x7=(x2,x1)
X7 = { x7,x6,x5,aa,x4,x3,ab,ba,bb };
x8=(ba,bb)
X8 = {x8,x7,x6,x5,aa,x4,x3,ab };
x9=(x3,ab)
X9 = {x9,x8,x7,x6,x5,aa,x4};
x10=(aa,x4)
108 = {x10,x9,x8,x7,x6,x5};
x11=(x6,x5)
X11 = {x11,x10,x9,x8,x7};
x12=(x8,x7)
X12 = {x12,x11,x10,x9};
x13=(x10,x9)
X13 = {x13,x12,x11};
x14=(x12,x11)
X14 = {x14,x13};
x15=(x14,x13)
X15 = {x15};
aa=100, ac=0100, cb=1100, da=0111, db=111, ba=0000, bb=0001, bd=1011, ca=0110, cc=00100, dd=00111, ad=0101, ab=111, bc=1010, cd=00101, dc=00110;
Средняя длина кода будет равна
бит.
Избыточность:
|
Код Шеннона-Фано для сообщения |
|||||||
|
состояния |
количество |
P |
Шаг 1 |
Шаг 2 |
Шаг 3 |
Шаг 4 |
Код |
|
bac |
2 |
0,166667 |
0 |
0 |
0 |
000 |
|
|
aac |
1 |
0,083333 |
1 |
001 |
|||
|
aba |
1 |
0,083333 |
1 |
0 |
010 |
||
|
aaa |
1 |
0,083333 |
1 |
0 |
0110 |
||
|
cdb |
1 |
0,083333 |
1 |
0111 |
|||
|
bdd |
1 |
0,083333 |
1 |
0 |
0 |
100 |
|
|
ccb |
1 |
0,083333 |
1 |
0 |
1010 |
||
|
cbb |
1 |
0,083333 |
1 |
1011 |
|||
|
dda |
1 |
0,083333 |
1 |
0 |
110 |
||
|
dad |
1 |
0,083333 |
1 |
0 |
1110 |
||
|
bba |
1 |
0,083333 |
1 |
1111 |
Средняя длина кода будет равна
бит.
Избыточность:
Код Хаффмана для сообщения:
X0 ={bac,aac,aba,aaa,cdb,bdd,ccb,cbb,dda,dad,bba}
x1=(dad,bba), x2=(cbb,dda), x3=(bdd,ccb), x4=(aaa,cdb), x5=(aac,aba)
X5 ={x5,x4,x3,x2,x1,bac}
x6=( x1,bac), x7=(x3,x2), x8=(x4,x5)
X8 ={x8,x7,x6}
x9=(x7,x6)
X9 ={x9,x8}
x10=(x9,x8)
X10 ={x10}
bac=011, bdd=0000, ccb=0001, cbb=0010, dda=0011, dad=0100, bba=0101, aac=100, aba=101, aaa=110, cdb=111;
Средняя длина кода будет равна
бит.
Избыточность: