Курсовая работа: Расчет оптимального кода по методике Шеннона Фано

Избыточность сообщений, составленных из данного алфавита.

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

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

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