С начало множество из сообщений расположим в порядке убывания вероятностей. Затем, разобьем данное множество на две группы таким образом, чтобы суммарные вероятности сообщений обеих групп были по возможности равны. Но поскольку равенство не достигается, то мы их делим так, чтобы в верхней части оставались символы, суммарная вероятность которых меньше суммарной вероятности символов в нижней части. Первой группе присваиваем символ 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
i,x: integer;
s,H,Hmax,deltaD,sum,C,sumTiPi,D: real;
p,a: mass;
code: array [1..k] of string[20];
{Процедура построения оптимального кода по методике Шеннона-Фано}
procedure shannona(b:mass);
procedure divide(var nS:integer; n1,n2:integer);
var
s,s1,s2: real;
begin
s:=0;
for i:=n1 to n2 do s:=s+a[i];
s1:=0; s2:=0;
i:=n1-1;
repeat
inc(i);
s1:=s1+a[i];
s2:=s1+a[i+1];
until abs(s/2-s1)<abs(s/2-s2);
nS:=i;
for x:=n1 to nS do
if (s/2-s1)>=0 then code[x]:=code[x]+'0'
else code[x]:=code[x]+'1';
for x:=nS+1 to n2 do
if (s/2-s1)<0 then code[x]:=code[x]+'0'
else code[x]:=code[x]+'1';
end;
var
tmp: real;
j,n1,n2,nS: integer;
begin
for i:=1 to k do code[i]:='';
for i:=1 to k do a[i]:=b[i];
for i:=1 to k do
for j:=k downto(i+1) do
if a[i]<a[j]
then
begin
tmp:=a[i];
a[i]:=a[j];
a[j]:=tmp;
end;
j:=1;
repeat
divide(nS,j,k);
n1:=nS;
while (nS-j)>0 do divide(nS,j,nS);
j:=nS+1;
n2:=n1;
while (n1-j)>0 do divide(n1,j,n1);
j:=n2+1;
until j>(k-1);
end;
procedure zastavka;
var dr,reg,err:integer;
begin
dr:=detect;reg:=detect;
initgraph(dr,reg,'d:\tp7\tpu\');
err:=graphresult;
if err<>grok then
begin
writeln('Ошибка инициализации графического модуля!');
halt;
end;
setcolor(19);
settextstyle(3,0,4);
outtextxy(150,40,'Расчетно-графическая работа');
outtextxy(240,65,'на тему');
setcolor(14);
settextstyle(4,0,4);
outtextxy(50,125,'''Построение оптимального кода методом Шеннона-Фано''');
settextstyle(6,0,2);
setcolor(19);
outtextxy(325,250,'Выполнил:');
settextstyle(6,0,2);
setcolor(10);
outtextxy(400,250,'Калинин С.А. ПС-11');
outtextxy(200,450,'Нажмите любую клавишу');
readln;
closegraph;
end;
procedure vivod;
begin
textcolor(lightgreen);
writeln('Оптимальный код: '); {вывод конечной таблицы}
writeln('Символ':7,'Вероятность':13,'Оптимальный код':20,'Число зн.':15,'Вероятн.*Числ.зн.':20);
for i:=1 to k do
begin
write(' p[',i:2,'] ');
write(p[i]:0:4,' ');
write(code[i]:20,' ');
write(length(code[i]):15,' ');
write((p[i]*length(code[i])):0:4);
if i<>k then writeln;
end;
end;
begin
zastavka;
clrscr;
{1.1 а) Кол-во информации на символ сообщения,
составленного из алфавита равновероятных символов}
Hmax:=ln(k)/ln(2);
{1.1 б) Расчет вероятностей для неравновероятных символов}
p[1]:=0.15;
sum:=p[1];
for i:=2 to k do
begin
p[i]:=sum/(k+1-i);
sum:=sum+p[i];
end;
clrscr;
textcolor(11);
writeln('Промежуточные значения вероятностей: ');
writeln;
textcolor(10);
for i:=1 to 14 do
writeln('Вероятность p[',i:2,'] = ',p[i]:4:4);
readkey;
clrscr;
textcolor(11);
writeln('Промежуточные значения вероятностей: ');
writeln;
textcolor(10);
for i:=15 to k do
writeln('Вероятность p[',i:2,'] = ',p[i]:4:4);
writeln;
textcolor(11);
for i:=1 to k do s:=s+p[i];
writeln('Сумма вероятностей = ',s:4:2);
readkey;
H:=0;
sumTiPi:=0;
for i:=1 to k do
begin
p[i]:=p[i]/sum;
{1.1 б) Расчет энтропии для алфавита неравновероятных символов}
H:=H+p[i]*(ln(1/p[i])/ln(2));
sumTiPi:=sumTiPi+i*p[i];
end;
clrscr;
textcolor(11);
writeln('Окончательные значения: ');
writeln;
textcolor(10);
for i:=1 to 14 do
writeln('Вероятность p[',i:2,'] = ',p[i]:4:4);
readkey;
clrscr;
textcolor(11);
writeln('Окончательные значения: ');
writeln;
textcolor(10);
for i:=15 to k do
writeln('Вероятность p[',i:2,'] = ',p[i]:4:4);
writeln;
textcolor(11);
s:=0;
for i:=1 to k do s:=s+p[i];
writeln('Сумма вероятностей = ',s:4:2);
readkey;
{1.1 б) Определение недогруженности символов}
deltaD:=Hmax-H;
{1.2 Расчет скорости передачи сообщения}
C:=H/SumTiPi;
{1.3 Расчет избыточности сообщений}
D:=1-H/Hmax;
{Вызов процедуры построения оптимального кода}
shannona(p);
{Вывод результатов}
clrscr;
textcolor(11);
{ writceln('Количество символов алфавита = ',k,'.');}
writeln('1.1 Количество информации на символ сообщения:');
writeln(' a) для алфавита равновероятных символов: ');
textcolor(10); writeln(' Hmax =',Hmax:7:4,' бит/символ');
textcolor(11); writeln(' b) для алфавита неравновероятных символов: ');
textcolor(10); writeln(' H =',H:7:4,' бит/символ');
textcolor(11); write(' Недогруженность:');
textcolor(10); writeln(' дельтаD =',deltaD:7:4,' бит/символ');
textcolor(11); writeln;
Writeln('1.2 Скорость передачи информации:');