48742 (Расчет оптимального кода по методике Шеннона-Фано), страница 2
Описание файла
Документ из архива "Расчет оптимального кода по методике Шеннона-Фано", который расположен в категории "". Всё это находится в предмете "информатика" из 1 семестр, которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "курсовые/домашние работы", в предмете "информатика, программирование" в общих файлах.
Онлайн просмотр документа "48742"
Текст 2 страницы из документа "48742"
дв. симв.
Однако эту цифру необходимо округлить до ближайшего целого числа (в большую сторону), так как длина кода не может быть выражена дробным числом.
В общем случае, избыточность от округления:
где 
, k - округленное до ближайшего целого числа значение 
. Для нашего примера
Избыточность необходима для повышения помехоустойчивости кодов и ее вводят искусственно в виде добавочных 
символов. Если в коде всего n разрядов и 
из них несут информационную нагрузку, то 
характеризуют абсолютную корректирующую избыточность, а величина 
характеризует относительную корректирующую избыточность.
Для уменьшения избыточности используют оптимальные коды. При построении оптимальных кодов наибольшее распространение получили методики Шеннона-Фано и Хаффмена. Согласно методике Шеннона-Фано построение оптимального кода ансамбля из сообщений сводится к следующему:
1) множество из сообщений располагается в порядке убывания вероятностей;
2) первоначальный ансамбль кодируемых сигналов разбивается на две группы таким образом, чтобы суммарные вероятности сообщений обеих групп были по возможности равны.
Если равной вероятности в подгруппах нельзя достичь, то их делят так, чтобы в верхней части (верхней подгруппе) оставались символы, суммарная вероятность которых меньше суммарной вероятности символов в нижней части (нижней подгруппе);
3) первой группе присваивается символ 0, а второй группе - символ 1;
4) каждую из образованных подгрупп делят на две части таким образом, чтобы суммарные вероятности вновь образованных подгрупп были по возможности равны;
5) первым группам каждой из подгрупп вновь присваивается 0, а вторым - 1. Таким образом, мы получаем вторые цифры кода. Затем каждая из четырех групп вновь делится на равные (с точки зрения суммарной вероятности) части до тех пор, пока в каждой из подгрупп не останется по одной букве.
Построенный код называют оптимальным неравномерным кодом (ОНК).
ПРАКТИЧЕСКАЯ ЧАСТЬ
a) Расчеты
-
рассчитывается первоначальные вероятности для неравновероятных символов алфавита.
-
выполняет нормирование указанных вероятностей.
-
рассчитывается энтропия алфавита из равновероятных символов.
-
производится расчет энтропии алфавита с неравновероятными символами и недогруженность в этом случае.
-
с учетом заданных длительностей символов вычисляется скорость передачи и избыточность.
-
строится оптимальный код по методу Шеннона-Фано.
Расчет вероятностей.
| Промежуточные значения: k-1 ...pk = S pn /(m - k + 1). n-1 | Окончательный результат: рi = pi/( |
| p1 = 0,1500 p2 = 0,0065 p3 = 0,0071 p4 = 0,0078 p5 = 0,0086 p6 = 0,0095 p7 = 0,0105 p8 = 0,0118 p9 = 0,0132 p10 = 0,0150 p11 = 0,0171 p12 = 0,0198 p13 = 0,0231 p14 = 0,0273 p15 = 0,0327 p16 = 0,0400 p17 = 0,0500 p18 = 0,0643 p19 = 0,0857 p20 = 0,1200 p21 = 0,1800 p22 = 0,3000 p23 = 0,6000 p24 = 1,8000 | p1=0,0417 p2=0,0018 p3=0,0020 p4=0,0022 p5=0,0024 p6=0,0026 p7=0,0029 p8=0,0033 p9=0,0037 p10=0,0042 p11=0,0048 p12=0,0055 p13=0,0064 p14=0,0076 p15=0,0091 p16=0,0111 p17=0,0139 p18=0,0179 p19=0,0238 p20=0,0333 p21=0,0500 p22=0,0833 p23=0,1667 p24=0,5000 |
pi)
рi = 3,6Определение количества информации на символ сообщения, составленного из данного алфавита.
Количество информации на символ сообщения для символов данного алфавита, встречающихся с равными вероятностями:
Hmax = log2 24 = ln 24/ln 2 = 4,5850 бит/символ
Количество информации на символ сообщения для символов данного алфавита, встречающихся в сообщении с разными вероятностями:
H = – (0,0417*log20,0417 + 0,0018*log20,0018 + 0,020*log2 0,0020 + 0,0022*log20,0022 + 0,0024*log20,0024 + 0,0026*log20,0026 + 0,0029*log20,0029 + 0,0033*log20,0033 + 0,0037*log20,0037 + 0,0042*log20,0042 + 0,0048*log20,0048 + 0,0055*log20,0055 + 0,0064*log20,0064 + 0,0076*log20,0076 + 0,0091*log20,0091 + 0,0111*log20,0111 + 0,0139*log20,0139 + 0,0179*log20,0179 + 0,0238*log20,0238 + 0,0333*log20,0333 + 0,0500*log20,0500 + 0,0833*log20,0833 + 0,1667*log20,1667 + 0,5000*log20,5000) =
= 2,6409 бит/символ
Недогруженность символов в данном случае:
N = Нmax – Н = 4,5850 – 2,6409 = 1,9441 бит/символ
Вычисление скорости передачи информации.
С= – (0,0417*log20,0417 + 0,0018*log20,0018 + 0,020*log2 0,0020 + 0,0022*log20,0022 + 0,0024*log20,0024 + 0,0026*log20,0026 + 0,0029*log20,0029 + 0,0033*log20,0033 + 0,0037*log20,0037 + 0,0042*log20,0042 + 0,0048*log20,0048 + 0,0055*log20,0055 + 0,0064*log20,0064 + 0,0076*log20,0076 + 0,0091*log20,0091 + 0,0111*log20,0111 + 0,0139*log20,0139 + 0,0179*log20,0179 + 0,0238*log20,0238 + 0,0333*log20,0333 + 0,0500*log20,0500 + 0,0833*log20,0833 + 0,1667*log20,1667 + 0,5000*log20,5000) /
(1*0,0417 + 2*0,0018 + 3*0,020 + 4*0,0022 + 5*0,0024 + 6*0,0026 + 7*0,0029 + 8*0,0033 + 9*0,0037 + 10*0,0042 + 11*0,0048 + 12*0,0055 + 13*0,0064 + 14*0,0076 + 15*0,0091 + 16*0,0111 + 17*0,0139 + 18*0,0179 + 19*0,0238 + 20*0,0333 + 21*0,0500 + 22*0,0833 + 23*0,1667 + 24*0,5000) = 0,1244 бит/сек
Избыточность сообщений, составленных из данного алфавита.
D = 1 – (Н/Нmax) = 1 – (2,6409 / 4,5850) = 0,4240
Построение оптимального кода
| 1 | p24=0,5000 | 0,5 | 0 | 0 | ||||||||||||||||
| 2 | p23=0,1667 | 0,5 | 1 | 0,25 | 1 | 0,1666 | 1 | 111 | ||||||||||||
| 3 | p22=0,0833 | 1 | 1 | 0,0833 | 0 | 110 | ||||||||||||||
| 4 | p21=0,0500 | 1 | 0,25 | 0 | 0 | 0,05 | 1 0 | 1000 | ||||||||||||
| 5 | p1=0,0417 | 1 | 0 | 0 | 0,0690 | 1 | 0,0357 | 1 | 10011 | |||||||||||
| 6 | p20=0,0333 | 1 | 0 | 0,1190 | 0 | 1 | 0,0333 | 0 | 10010 | |||||||||||
| 7 | p19=0,0238 | 1 | 0 | 1 | 1 | 0,0428 | 1 | 0,0178 | 1 | 101111 | ||||||||||
| 8 | p18=0,0179 | 1 | 0 | 1 | 1 | 1 | 0,025 | 0 | 0,0138 | 0 | 1011100 | |||||||||
| 9 | p17=0,0139 | 1 | 0 | 1 | 1 | 0 | 0,025 | 1 | 101101 | |||||||||||
| 10 | p16=0,0111 | 1 | 0 | 1 | 0,0666 | 1 | 1 | 0 | 101110 | |||||||||||
| 11 | p15=0,0091 | 1 | 0 | 1 | 0,0642 | 0 | 0 | 1 | 0,0090 | 1 | 1010011 | |||||||||
| 12 | p14=0,0076 | 1 | 0 | 1 | 0 | 0 | 1 | 0,0102 | 0 | 0,0054 | 0 | 10100100 | ||||||||
| 13 | p13=0,0064 | 1 | 0 | 1 | 0 | 0 | 0,0166 | 0 | 0,0064 | 1 | 1010001 | |||||||||
| 14 | p12=0,0055 | 1 | 0 | 1 | 0 | 0 | 0,0166 | 1 | 0,0064 | 1 | 1010011 | |||||||||
| 15 | p11=0,0048 | 1 | 0 | 1 | 0 | 0,0333 | 1 | 1 | 1 | 0,0047 | 1 | 10101111 | ||||||||
| 16 | p10=0,0042 | 1 | 0 | 1 | 0 | 1 | 1 | 0,0088 | 1 | 0 | 0,0032 | 0 | 101011100 | |||||||
| 17 | p9=0,0037 | 1 | 0 | 1 | 0 | 1 | 1 | 0,0078 | 0 | 0,0036 | 1 | 10101101 | ||||||||
| 18 | p8=0,0033 | 1 | 0 | 1 | 0 | 1 | 1 | 0,0078 | 1 | 0,0036 | 0 | 10101110 | ||||||||
| 19 | p7=0,0029 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 10101010 | ||||||||||
| 20 | p6=0,0026 | 1 | 0 | 1 | 0 | 1 | 0,0167 | 0 | 1 | 0,0026 | 1 | 0,0026 | 1 | 101010111 | ||||||
| 21 | p5=0,0024 | 1 | 0 | 1 | 0 | 1 | 0,0147 | 0 | 1 | 1 | 0,0024 | 0 | 101010110 | |||||||
| 22 | p4=0,0022 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0,0022 | 0 | 10101000 | |||||||||
| 23 | p3=0,0020 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0,0038 | 1 | 0,0020 | 1 | 101010011 | |||||||
| 24 | p2=0,0018 | 1 | 0 | 1 | 0 | 1 | 0 | 0,0083 | 0 | 1 | 0,0018 | 0 | 101010010 |
| Буква | Вероятность появления буквы | Кодовые слова | Число знаков в кодовом слове | Pi· li |
| A[1] (p24) | 0,5000 | 0 | 1 | 0,5 |
| A[2] (p23) | 0,1667 | 111 | 3 | 0,50001 |
| A[3] (p22) | 0,0833 | 110 | 3 | 0,2500 |
| A[4] (p21) | 0,0500 | 1000 | 4 | 0,2000 |
| A[5] (p 1) | 0,0417 | 10011 | 5 | 0,2083 |
| A[6] (p20) | 0,0333 | 10010 | 5 | 0,1667 |
| A[7] (p19) | 0,0238 | 101111 | 6 | 0,1429 |
| A[8] (p18) | 0,0179 | 1011100 | 7 | 0,1250 |
| A[9] (p17) | 0,0139 | 101101 | 6 | 0,0833 |
| A[10] (p16) | 0,0111 | 101110 | 6 | 0,0667 |
| A[11] (p15) | 0,0091 | 1010011 | 7 | 0,0636 |
| A[12] (p14) | 0,0076 | 10100100 | 8 | 0,0606 |
| A[13] (p13) | 0,0064 | 1010001 | 7 | 0,0449 |
| A[14] (p12) | 0,0055 | 1010011 | 7 | 0,0385 |
| A[15] (p11) | 0,0048 | 10101111 | 8 | 0,0381 |
| A[16] (p10) | 0,0042 | 101011100 | 9 | 0,0375 |
| A[17] (p9) | 0,0037 | 10101101 | 8 | 0,0294 |
| A[18] (p8) | 0,0033 | 10101110 | 8 | 0,0261 |
| A[19] (p7) | 0,0029 | 10101010 | 8 | 0,0234 |
| A[20] (p6) | 0,0026 | 101010111 | 9 | 0,0237 |
| A[21] (p5) | 0,0024 | 101010110 | 9 | 0,0214 |
| A[22] (p4) | 0,0022 | 10101000 | 8 | 0,0173 |
| A[23] (p3) | 0,0020 | 101010011 | 9 | 0,0178 |
| A[24] (p2) | 0,0018 | 101010010 | 9 | 0,0163 |
Определение количества информации на символ сообщения. Построение оптимального кода.
