Xreferat.com » Рефераты по информатике и программированию » Расчет оптимального кода по методике Шеннона-Фано

Расчет оптимального кода по методике Шеннона-Фано

VALIGN=TOP>101010010 9 0,0163

Определение количества информации на символ сообщения. Построение оптимального кода.


С начало множество из сообщений расположим в порядке убывания вероятностей. Затем, разобьем данное множество на две группы таким образом, чтобы суммарные вероятности сообщений обеих групп были по возможности равны. Но поскольку равенство не достигается, то мы их делим так, чтобы в верхней части оставались символы, суммарная вероятность которых меньше суммарной вероятности символов в нижней части. Первой группе присваиваем символ 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:tp7tpu');

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.

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: