48742 (Расчет оптимального кода по методике Шеннона-Фано), страница 3
Описание файла
Документ из архива "Расчет оптимального кода по методике Шеннона-Фано", который расположен в категории "". Всё это находится в предмете "информатика" из 1 семестр, которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "курсовые/домашние работы", в предмете "информатика, программирование" в общих файлах.
Онлайн просмотр документа "48742"
Текст 3 страницы из документа "48742"
С начало множество из сообщений расположим в порядке убывания вероятностей. Затем, разобьем данное множество на две группы таким образом, чтобы суммарные вероятности сообщений обеих групп были по возможности равны. Но поскольку равенство не достигается, то мы их делим так, чтобы в верхней части оставались символы, суммарная вероятность которых меньше суммарной вероятности символов в нижней части. Первой группе присваиваем символ 0, а второй группе = символ 1. каждую из образованных подгрупп делим на две части таким образом, чтобы суммарные вероятности вновь образованных подгрупп были по возможности равны. Первым группам каждой из подгрупп вновь присваиваем 0, а вторым 1. таким образам мы получаем мы получаем вторые цифры кода. Затем каждую из четырех групп вновь делим на равные части до тех пор, пока в каждой из подгрупп не останется по одной букве.
Оптимальный код (получившийся результат):
Буква | Вероятность появления буквы | Кодовое слово | Число знаков в кодовом слове | pi∙ li |
P1 | 0,055 | 000 | 3 | 0,165 |
P2 | 0,053 | 0010 | 4 | 0,212 |
P3 | 0,051 | 00110 | 5 | 0,255 |
P4 | 0,050 | 00111 | 5 | 0,250 |
P5 | 0,048 | 0100 | 4 | 0,192 |
P6 | 0,046 | 0101 | 4 | 0,176 |
P7 | 0,044 | 0110 | 4 | 0,114 |
P8 | 0,043 | 01110 | 5 | 0,215 |
P9 | 0,041 | 011110 | 6 | 0,246 |
P10 | 0,040 | 011111 | 6 | 0,240 |
P11 | 0,039 | 1000 | 4 | 0,156 |
P12 | 0,038 | 10010 | 5 | 0,190 |
P13 | 0,036 | 10011 | 5 | 0,180 |
P14 | 0,035 | 1010 | 4 | 0,140 |
P15 | 0,033 | 10110 | 5 | 0,165 |
P16 | 0,032 | 101110 | 6 | 0,192 |
P17 | 0,030 | 101111 | 6 | 0,180 |
P18 | 0,029 | 11000 | 5 | 0,145 |
P19 | 0,027 | 11001 | 5 | 0,135 |
P20 | 0,026 | 11010 | 5 | 0,130 |
P21 | 0,025 | 110110 | 6 | 0,150 |
P22 | 0,023 | 110111 | 6 | 0,138 |
P23 | 0,022 | 11100 | 5 | 0,110 |
P24 | 0,020 | 111010 | 6 | 0,120 |
P25 | 0,019 | 111011 | 6 | 0,114 |
P26 | 0,018 | 111100 | 6 | 0,108 |
P27 | 0,017 | 111101 | 6 | 0,102 |
P28 | 0,016 | 111110 | 6 | 0,096 |
P29 | 0,013 | 1111110 | 7 | 0,091 |
P30 | 0,012 | 11111110 | 8 | 0,096 |
P31 | 0,010 | 11111111 | 8 | 0,080 |
Ручное построение ОНК по методике Шеннона-Фано:
P1 | 0,010 | 11111111 | 0,520 | 0,277 | 0,147 | 0,086 | 0,051 | 0,035 | 0,022 | 0,010 |
P2 | 0,012 | 11111110 | 0,012 | |||||||
P3 | 0,013 | 1111110 | 0,013 | |||||||
P4 | 0,016 | 111110 | 0,016 | |||||||
P5 | 0,017 | 111101 | 0,035 | 0,017 | ||||||
P6 | 0,018 | 111100 | 0,018 | |||||||
P7 | 0,019 | 111011 | 0,061 | 0,039 | 0,019 | |||||
P8 | 0,020 | 111010 | 0,020 | |||||||
P9 | 0,022 | 11100 | 0,022 | |||||||
P10 | 0,023 | 110111 | 0,130 | 0,074 | 0,048 | 0,023 | ||||
P11 | 0,025 | 110110 | 0,025 | |||||||
P12 | 0,026 | 11010 | 0,026 | |||||||
P13 | 0,027 | 11001 | 0,056 | 0,027 | ||||||
P14 | 0,029 | 11000 | 0,029 | |||||||
P15 | 0,030 | 101111 | 0,243 | 0,130 | 0,095 | 0,062 | 0,030 | |||
P16 | 0,032 | 101110 | 0,032 | |||||||
P17 | 0,033 | 10110 | 0,033 | |||||||
P18 | 0,035 | 1010 | 0,035 | |||||||
P19 | 0,036 | 10011 | 0,113 | 0,074 | 0,036 | |||||
P20 | 0,038 | 10010 | 0,038 | |||||||
P21 | 0,039 | 1000 | 0,039 | |||||||
P22 | 0,040 | 011111 | 0,471 | 0,262 | 0,168 | 0,124 | 0,081 | 0,040 | ||
P23 | 0,041 | 011110 | 0,041 | |||||||
P24 | 0,043 | 01110 | 0,043 | |||||||
P25 | 0,044 | 0110 | 0,044 | |||||||
P26 | 0,046 | 0101 | 0,094 | 0,046 | ||||||
P27 | 0,048 | 0100 | 0,048 | |||||||
P28 | 0,050 | 00111 | 0,209 | 0,154 | 0,101 | 0,050 | ||||
P29 | 0,051 | 00110 | 0,051 | |||||||
P30 | 0,053 | 0010 | 0,053 | |||||||
P31 | 0,055 | 000 | 0,055 |
ТЕКСТ ПРОГРАММЫ:
uses Crt,Graph;
const k=24;
type
mass=array [1..k] of real;
var