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 Скорость передачи информации:');
textcolor(10); writeln(' C =',C:7:4,' бит/сек');
textcolor(11); writeln;
Writeln('1.3 Избыточность сообщений:');
textcolor(10); writeln(' D =',D:7:4);
writeln;
TextColor(11);
write(' Нажмите любую клавишу для вывода таблицы резултатов построения.');
readkey;
clrScr;
vivod;
readkey;
end.
Заключение:
В моей курсовой работе я использовал теоретический материал и разработанную на языке (высокого уровня) Turbo Pascal программу. Мною было рассчитано количество информации на символ сообщения, составленного из алфавита, состоящего из 24 символа, для двух случаев:
1] если символы алфавита встречаются с равными вероятностями;
2] если вероятности не равны.
Также я определил количество недогрузки символов во втором случае, вычислил количество информации на символ сообщения и скорость передачи сообщений, составленных из таких символов, нашел избыточность сообщений, составленных из данного алфавита. Построил оптимальный код сообщения, применяя методику Шеннона-Фано: при помощи последовательного деления множества вероятностей на группы по принципу равенства сумм вероятностей я составил в соответствие каждому символу наиболее оптимальную двоичную комбинацию. Таким образом, был получен оптимальный двоичный код для алфавита из 31 символа.
В результате выполнения работы были получены следующие результаты:
-
количество информации на символ для равновероятного алфавита – 4,585 бит/сим;
-
количество информации на символ для неравновероятного алфавита - 2,6409 бит/сим;
-
недогруженность символов – 1,9441 бит/сим;
-
скорость передачи информации – 0,1244 бит/сек;
-
избыточность сообщения – 0,4240;
-
построен следующий оптимальный код:
Символ | Вероятность появления | Код | Число знаков | |
p[ 1] | 0.0417 | 0 | | |
p[ 2] | 0.0018 | 111 | | |
p[ 3] | 0.0020 | 110 | | |
p[ 4] | 0.0022 | 1000 | | |
p[ 5] | 0.0024 | 10011 | | |
p[ 6] | 0.0026 | 10010 | | |
p[ 7] | 0.0029 | 101111 | | |
p[ 8] | 0.0033 | 1011100 | | |
p[ 9] | 0.0037 | 101101 | | |
p[10] | 0.0042 | 101101 | | |
p[11] | 0.0048 | 1010011 | | |
p[12] | 0.0055 | 10100100 | | |
p[13] | 0.0064 | 1010001 | | |
p[14] | 0.0076 | 1010001 | | |
p[15] | 0.0091 | 10101111 | | |
p[16] | 0.0111 | 101011100 | | |
p[17] | 0,0139 | 10101101 | | |
p[18] | 0,0179 | 10101101 | | |
p[19] | 0,0238 | 10101010 | | |
p[20] | 0,0333 | 101010111 | | |
p[21] | 0,0500 | 101010110 | | |
p[22] | 0,0833 | 10101000 | | |
p[23] | 0,1667 | 101010011 | | |
p[24] | 0,5000 | 101010010 | | |
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ:
1. Бауэр Ф. Информатика, М. 1992.
2. Колесник В.Д. Курс теории информации, М. 1982.
3. Фаронов В. В. Turbo Pascal 7.0. Учебное пособие, М. 2000.
4. Цымбаль В.П. Задачник по теории информации и кодированию, Киев. 1976.
5. Марченко А.И. Программирование в среде Turbo Pascal 7.0.