Расчет оптимального кода по методике Шеннона Фано (стр. 2 из 4)
,где
= μ - коэффициент сжатия (относительная энтропия). Н и Нмакс берутся относительно одного и того же алфавита.Кроме общего понятия избыточности существуют частные виды избыточности (избыточность, обусловленная неравновероятным распределением символов в сообщении, избыточность, вызванная статистической связью между символами сообщения).
Избыточность, которая заложена в природе данного кода, получается в результате неравномерного распределения в сообщениях качественных признаков этого кода и не может быть задана одной цифрой на основании статистических испытаний. Так при передаче десятичных цифр двоичным кодом максимально загруженными бывают только те символы вторичного алфавита, которые передают значения, являющиеся целочисленными степенями двойки. В остальных случаях тем же количеством символов может быть передано большее количество цифр (сообщений). Например, тремя двоичными разрядами мы можем передать и цифру 5, и цифру 8. Фактически для передачи сообщения достаточно иметь длину кодовой комбинации.
Фактически для передачи сообщения достаточно иметь длину кодовой комбинации
где N - общее количество передаваемых сообщений.
L можно представить и как
где
и 
- соответственно качественные признаки первичного и вторичного алфавитов. Поэтому для цифры 5 в двоичном коде можно записать 
дв. симв.Однако эту цифру необходимо округлить до ближайшего целого числа (в большую сторону), так как длина кода не может быть выражена дробным числом.
В общем случае, избыточность от округления:
где
, k - округленное до ближайшего целого числа значение 
. Для нашего примера 
Избыточность необходима для повышения помехоустойчивости кодов и ее вводят искусственно в виде добавочных
символов. Если в коде всего n разрядов и 
из них несут информационную нагрузку, то 
характеризуют абсолютную корректирующую избыточность, а величина 
характеризует относительную корректирующую избыточность.Для уменьшения избыточности используют оптимальные коды. При построении оптимальных кодов наибольшее распространение получили методики Шеннона-Фано и Хаффмена. Согласно методике Шеннона-Фано построение оптимального кода ансамбля из сообщений сводится к следующему:
1) множество из сообщений располагается в порядке убывания вероятностей;
2) первоначальный ансамбль кодируемых сигналов разбивается на две группы таким образом, чтобы суммарные вероятности сообщений обеих групп были по возможности равны.
Если равной вероятности в подгруппах нельзя достичь, то их делят так, чтобы в верхней части (верхней подгруппе) оставались символы, суммарная вероятность которых меньше суммарной вероятности символов в нижней части (нижней подгруппе);
3) первой группе присваивается символ 0, а второй группе - символ 1;
4) каждую из образованных подгрупп делят на две части таким образом, чтобы суммарные вероятности вновь образованных подгрупп были по возможности равны;
5) первым группам каждой из подгрупп вновь присваивается 0, а вторым - 1. Таким образом, мы получаем вторые цифры кода. Затем каждая из четырех групп вновь делится на равные (с точки зрения суммарной вероятности) части до тех пор, пока в каждой из подгрупп не останется по одной букве.
Построенный код называют оптимальным неравномерным кодом (ОНК).
ПРАКТИЧЕСКАЯ ЧАСТЬ
a) Расчеты
1) рассчитывается первоначальные вероятности для неравновероятных символов алфавита.
2) выполняет нормирование указанных вероятностей.
3) рассчитывается энтропия алфавита из равновероятных символов.
4) производится расчет энтропии алфавита с неравновероятными символами и недогруженность в этом случае.
5) с учетом заданных длительностей символов вычисляется скорость передачи и избыточность.
6) строится оптимальный код по методу Шеннона-Фано.
Расчет вероятностей.
| Промежуточные значения:k-1 ...pk = Spn/(m - k + 1).n-1 | Окончательный результат: рi= pi/(  pi) |
p1 = 0,1500p2 = 0,0065p3 = 0,0071p4 = 0,0078p5 = 0,0086p6 = 0,0095p7 = 0,0105p8 = 0,0118p9 = 0,0132p10 = 0,0150p11 = 0,0171p12 = 0,0198p13 = 0,0231p14 = 0,0273p15 = 0,0327p16 = 0,0400p17 = 0,0500p18 = 0,0643p19 = 0,0857p20 = 0,1200p21 = 0,1800p22 = 0,3000p23 = 0,6000p24 = 1,8000  рi = 3,6 | p1=0,0417p2=0,0018p3=0,0020p4=0,0022p5=0,0024p6=0,0026p7=0,0029p8=0,0033p9=0,0037p10=0,0042p11=0,0048p12=0,0055p13=0,0064p14=0,0076p15=0,0091p16=0,0111p17=0,0139p18=0,0179p19=0,0238p20=0,0333p21=0,0500p22=0,0833p23=0,1667p24=0,5000 рi = 1 |
Определение количества информации на символ сообщения, составленного из данного алфавита.
Количество информации на символ сообщения для символов данного алфавита, встречающихся с равными вероятностями:
Hmax = log2 24 = ln 24/ln 2 = 4,5850 бит/символ
Количество информации на символ сообщения для символов данного алфавита, встречающихся в сообщении с разными вероятностями:
H = – (0,0417*log20,0417 + 0,0018*log20,0018 + 0,020*log20,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*log20,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] (p1) | 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 |
Определение количества информации на символ сообщения. Построение оптимального кода.