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

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

СОДЕРЖАНИЕ

Содержание

Инструкция

Введение

Содержание задания

Теоретическая часть

Практическая часть

а) расчеты

б) программка

Заключение

а) результаты работы программки

б) блок-схема

Литература

АННОТАЦИЯ

В данной работе по данному числу знаков в алфавите рассчитываются их вероятности, количество инфы, если знаки встречаются с равными вероятностями и с различными вероятностями, недогруженность знаков, скорость передачи сообщений и избыточность сообщений. Не считая того, в данной работе строится лучший двоичный код по методике Шеннона – Фано. Выполнение данной курсовой работы закрепляет наши познания по дисциплине «Теория инфы».

К работе прилагается программка, написанная на языке программирования высочайшего уровня (Turbo Pascal).

SUMMARY

In this work on the given numbeof symbols in the alphabet their probabilities, amount of the information if symbols meet equal probabilities and with different probabilities, speed of Message transfer and redundancy of messages pay off. Besides in the given work the optimum binary code by technique of Shennon and Fano is under construction. Performance of this course work fixes our knowledge on discipline «The Theory of the Information».

ВВЕДЕНИЕ

Информатика и вычислительная техника – это область науки и техники, которая включает совокупа средств, методов и способов людской деятель, направленных на создание и применение устройств связи, систем сбора, хранения и обработки инфы.

В почти всех вариантах хранимая и передаваемая информация может представлять энтузиазм для лиц, желающих употреблять ее в алчных целях.

Одним из способов защиты является кодирование.

Кодирование – это отображение сообщений кодом по определенному правилу присвоения знаков.

Код – это правило, описывающее отображение 1-го набора символов в иной набор символов (либо слов). Кодом также именуют и огромное количество образов при всем этом отображении.

Лучший код – это более действенный вариант кодировки с нулевой избыточностью. При устранении избыточности значительно понижается количество знаков, требуемых для шифруемых сообщений. Вследствие этого миниатюризируется время передачи, понижается требуемый размер памяти.

Таковым образом, познание способов обработки инфы является базисным для инженеров, работа которых связана с вычислительными системами и сетями. Избыточность — доп средства, вводимые в систему для увеличения ее надежности и защищенности.

Таковым образом, информатика занимается исследованием обработки и передачи инфы.

В работе отражается применение базисных понятий информатики.

СОДЕРЖАНИЕ ЗАДАНИЯ

Для проведения расчетов создать программку на языке ПАСКАЛЬ.

1.1. Число знаков алфавита k = m (номер варианта задания) + 10. Найти количество инфы на знак сообщения, составленного из этого алфавита:

а) если знаки алфавита встречаются с равными вероятностями;

б) если знаки алфавита встречаются в сообщении с вероятностями:

р1
= 0,15; p2
= p1
/(k-1); p3
= (p1
+ p2
)/(k-2) …

k-1

pk
= ∑ pn
/(k – k + 1).

n=1

Сумма всех вероятностей обязана быть равой единице, потому:

pi

рi
= ——

k

∑ pj

j=1

Найти, как недогружены знаки во 2-м слу­чае.

1.2. Число знаков алфавита = m (номер варианта задания). Вероятности возникновения знаков равны соответственно

р1
= 0,15; p2
= p1
/(k-1); p3
= (p1
+ p2
)/(k-2) …

k-1

pk
= ∑ pn
/(k – k + 1).

n=1

Продолжительности знаков τ1
= 1 сек; τ2
= 2 сек;

τk
= τk
-1
+ 1.

Чему равна скорость передачи сообщений, составленных из таковых знаков?

Найти количество инфы на знак сообщения, составленного из этого алфавита:

а) если знаки алфавита встречаются с равными вероятностями;

Найти, как недогружены знаки во 2-м случае.

1.3. Сообщения составляются из алфавита с числом знаков = m. Возможность возникновения знаков алфавита равна соответственно:

р1
= 0,15; p2
= p1
/(k-1); p3
= (p1
+ p2
)/(k-2) …

k-1

pk
= ∑ pn
/(k – k + 1).

n=1

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

Выстроить лучший код сообщения.

ТЕОРЕТИЧЕСКАЯ часть

КОЛИЧЕСТВЕННАЯ ОЦЕНКА ИНФОРМАЦИИ

Общее число неповторяющихся сообщений, которое быть может составлено из алфавита m методом комбинирования по n знаков в сообщении,

N = mn

Неопределенность, приходящаяся на знак первичного (кодируемого) алфавита, составленного из равновероятных и невзаимосвязанных знаков,

H = log2
m

Потому что информация есть неопределенность, снимаемая при получении сообщения, то количество инфы быть может представлено как произведение общего числа сообщений k на среднюю энтропию H, приходящуюся на одно сообщение:

I = k*H бит

Для случаев равновероятных и невзаимосвязанных знаков первичного алфавита количество инфы в k сообщениях алфавита m равно:

I = k*log2
m бит

Для неравновероятных алфавитов энтропия на знак алфавита:

m m

H =∑ pi
*log2
(1/2pi
)=-∑pi
*log2
pi
бит/знак

i=1 i=1

А количество инфы в сообщении, составленном из k неравновероятных знаков,

m

I = -k*∑ pi
*log2
pi
бит

i=1

ВЫЧИСЛЕНИЕ СКОРОСТИ ПЕРЕДАЧИ ИНФОРМАЦИИ И ПРОПУСКНОЙ возможности КАНАЛОВ СВЯЗИ

В критериях отсутствия помех скорость передачи инфы определяется количеством инфы, переносимым эмблемой сообщения в единицу времени, и равна

C = n*H,

где n — количество знаков, вырабатываемых источником сообщений за единицу времени; H — энтропия (неопределенность), снимаемая при получении 1-го знака сообщений, вырабатываемых данным источником.

Скорость передачи инфы также быть может представлена как

бит/сек,

где тау — время передачи 1-го двоичного знака.

Для сообщений, составленных из равновероятных невзаимосвязанных знаков равной продолжительности, скорость передачи инфы:

C=(1/τ)*log2
m бит/сек

В случае неравновероятных знаков равной продолжительности:

m

C =(1/τ)*∑pi
*log2
pi
бит/сек

i=1

В случае неравновероятных и невзаимосвязанных знаков разной продолжительности:

Пропускная способность (либо емкость канала связи) – есть наибольшая скорость передачи инфы по данному каналу связи. Под каналом связи предполагается совокупа средств, созданных для передачи инфы от данного источника сообщений к адресату. Выражение для пропускной возможности различается тем, что пропускную способность охарактеризовывает наибольшая энтропия:

Смакс
= бит/сек

Для двоичного кода:

Смакс
бит/сек

При наличии помех пропускная способность канала связи рассчитывается как произведение количества принятых в секунду символов n на разность энтропии источника сообщений и условной энтропии источника сообщений относительно принятого сигнала:

бит/сек (15)

либо

бит/сек

В общем случае

бит/сек (16)

Если знаки источника сообщений неравновероятны и взаи­мозависимы, то энтропия источника считается по формуле общей условной энтропии.

Для симметричных бинарных каналов, в каких сигналы передаются с помощью 2-ух высококачественных признаков и возможность неверного приема , а возможность правильного приема , утраты учитываются при помо­щи условной энтропии вида

бит/сек (17)

пропускная способность таковых каналов

бит/сек (18)

Для симметричного бинарного канала

бит/сек (19)

Для симметричных дискретных каналов связи с числом качест­венных признаков m > 2 пропускная способность

бит/сек (20)

ОПРЕДЕЛЕНИЕ ИЗБЫТОЧНОСТИ СООБЩЕНИЙ. ОПТИМАЛЬНОЕ КОДИРОВАНИЕ

Если энтропия источника сообщений не равна наибольшей энтропии для алфавита с данным количеством высококачественных признаков (имеются в виду высококачественные признаки алфавита, с помощью которых составляются сообщения), то это, до этого всего, значит, что сообщения данного источника могли бы нести большее количество инфы. Абсолютная недогруженность на знак сообщений такового источника:

∆D=(Нмакс
-Н) бит/знак

Для определения количества «излишней» инфы, которая заложена в структуре алфавита или в природе кода, вводится понятие избыточности. Избыточность, с которой мы имеем дело в теории инфы, не зависит от содержания сообщения и обычно заблаговременно известна из статистических данных. Информационная избыточность указывает относительную недогруженность на знак алфавита и является безразмерной величиной:

,

где = μ — коэффициент сжатия (относительная энтропия). Н и Нмакс
берутся относительно 1-го и такого же алфавита.

Не считая общего понятия избыточности есть личные виды избыточности (избыточность, обусловленная неравновероятным распределением знаков в сообщении, избыточность, вызванная статистической связью меж знаками сообщения).

Избыточность, которая заложена в природе данного кода, выходит в итоге неравномерного распределения в сообщениях высококачественных признаков этого кода и не быть может задана одной цифрой на основании статистических испытаний. Так при передаче десятичных цифр двоичным кодом очень загруженными бывают лишь те знаки вторичного алфавита, которые передают значения, являющиеся целочисленными степенями двойки. В других вариантах этим же количеством знаков быть может передано большее количество цифр (сообщений). К примеру, 3-мя двоичными разрядами мы можем передать и цифру 5, и цифру 8. Практически для передачи сообщения довольно иметь длину кодовой композиции.

Практически для передачи сообщения довольно иметь длину кодовой композиции

где N — общее количество передаваемых сообщений.

L можно представить и как

где и — соответственно высококачественные признаки первичного и вторичного алфавитов. Потому для числа 5 в двоичном коде можно записать

дв. симв.

Но эту цифру нужно округлить до наиблежайшего целого числа (в огромную сторону), потому что длина кода не быть может выражена дробным числом.

В общем случае, избыточность от округления:

где , k — округлое до наиблежайшего целого числа . Для нашего примера

Избыточность нужна для увеличения помехоустойчивости кодов и ее вводят искусственно в виде дополнительных знаков. Если в коде всего n разрядов и из их несут информационную нагрузку, то охарактеризовывают абсолютную корректирующую избыточность, а величина охарактеризовывает относительную корректирующую избыточность.

Для уменьшения избыточности употребляют рациональные коды. При построении хороших кодов наибольшее распространение получили методики Шеннона-Фано и Хаффмена. Согласно методике Шеннона-Фано построение рационального кода ансамбля из сообщений сводится к последующему:

1) огромное количество из сообщений размещается в порядке убывания вероятностей;

2) начальный ансамбль шифруемых сигналов разбивается на две группы таковым образом, чтоб суммарные вероятности сообщений обеих групп были по способности равны.

Если равной вероятности в подгруппах недозволено достигнуть, то их делят так, чтоб в верхней части (верхней подгруппе) оставались знаки, суммарная возможность которых меньше суммарной вероятности знаков в нижней части (нижней подгруппе);

3) первой группе присваивается знак 0, а 2-ой группе — знак 1;

4) каждую из образованных подгрупп делят на две части таковым образом, чтоб суммарные вероятности вновь образованных подгрупп были по способности равны;

5) первым группам каждой из подгрупп вновь присваивается 0, а вторым — 1. Таковым образом, мы получаем 2-ые числа кода. Потом любая из 4 групп вновь делится на равные (исходя из убеждений суммарной вероятности) части до того времени, пока в каждой из подгрупп не остается по одной буковке.

Построенный код именуют хорошим неравномерным кодом (ОНК).

ПРАКТИЧЕСКАЯ часть

a)
Расчеты

1) рассчитывается начальные вероятности для неравновероятных знаков алфавита.

2) делает нормирование обозначенных вероятностей.

3) рассчитывается энтропия алфавита из равновероятных знаков.

4) делается расчет энтропии алфавита с неравновероятными знаками и недогруженность в этом случае.

5) с учетом данных длительностей знаков рассчитывается скорость передачи и избыточность.

6) строится лучший код по способу Шеннона-Фано.

Расчет вероятностей.

Промежные значения:

k-1

…pk
= Spn
/(m — k + 1).

n-1

Окончательный итог:

рi
= pi
/(pi
)

p1
= 0,1500

p2
= 0,0065

p3
= 0,0071

p4
= 0,0078

p5
= 0,0086

p6
= 0,0095

p7
= 0,0105

p8
= 0,0118

p9
= 0,0132

p10
= 0,0150

p11
= 0,0171

p12
= 0,0198

p13
= 0,0231

p14
= 0,0273

p15
= 0,0327

p16
= 0,0400

p17
= 0,0500

p18
= 0,0643

p19
= 0,0857

p20
= 0,1200

p21
= 0,1800

p22
= 0,3000

p23
= 0,6000

p24
= 1,8000

рi
= 3,6

p1
=0,0417

p2
=0,0018

p3
=0,0020

p4
=0,0022

p5
=0,0024

p6
=0,0026

p7
=0,0029

p8
=0,0033

p9
=0,0037

p10
=0,0042

p11
=0,0048

p12
=0,0055

p13
=0,0064

p14
=0,0076

p15
=0,0091

p16
=0,0111

p17
=0,0139

p18
=0,0179

p19
=0,0238

p20
=0,0333

p21
=0,0500

p22
=0,0833

p23
=0,1667

p24
=0,5000

рi
= 1

Определение количества инфы на знак сообщения, составленного из данного алфавита.

количество инфы на знак сообщения для знаков данного алфавита, встречающихся с равными вероятностями:

Hmax
= log2
24 = ln 24/ln 2 = 4,5850 бит/знак

Количество инфы на знак сообщения для знаков данного алфавита, встречающихся в сообщении с различными вероятностями:

H = – (0,0417*log2
0,0417 + 0,0018*log2
0,0018 + 0,020*log2
0,0020 + 0,0022*log2
0,0022 + 0,0024*log2
0,0024 + 0,0026*log2
0,0026 + 0,0029*log2
0,0029 + 0,0033*log2
0,0033 + 0,0037*log2
0,0037 + 0,0042*log2
0,0042 + 0,0048*log2
0,0048 + 0,0055*log2
0,0055 + 0,0064*log2
0,0064 + 0,0076*log2
0,0076 + 0,0091*log2
0,0091 + 0,0111*log2
0,0111 + 0,0139*log2
0,0139 + 0,0179*log2
0,0179 + 0,0238*log2
0,0238 + 0,0333*log2
0,0333 + 0,0500*log2
0,0500 + 0,0833*log2
0,0833 + 0,1667*log2
0,1667 + 0,5000*log2
0,5000) =

= 2,6409 бит/знак

Недогруженность знаков в этом случае:

N = Нmax
– Н = 4,5850 – 2,6409 = 1,9441 бит/знак

Вычисление скорости передачи инфы.

С= – (0,0417*log2
0,0417 + 0,0018*log2
0,0018 + 0,020*log2
0,0020 + 0,0022*log2
0,0022 + 0,0024*log2
0,0024 + 0,0026*log2
0,0026 + 0,0029*log2
0,0029 + 0,0033*log2
0,0033 + 0,0037*log2
0,0037 + 0,0042*log2
0,0042 + 0,0048*log2
0,0048 + 0,0055*log2
0,0055 + 0,0064*log2
0,0064 + 0,0076*log2
0,0076 + 0,0091*log2
0,0091 + 0,0111*log2
0,0111 + 0,0139*log2
0,0139 + 0,0179*log2
0,0179 + 0,0238*log2
0,0238 + 0,0333*log2
0,0333 + 0,0500*log2
0,0500 + 0,0833*log2
0,0833 + 0,1667*log2
0,1667 + 0,5000*log2
0,5000) /

(1*0,0417 + 2*0,0018 + 3*0,020 + 4*0,0022 + 5*0,0024 + 6*0,0026 + 7*0,0029 + 8*0,0033 + 9*0,0037 + 10*0,0042 + 11*0,0048 + 12*0,0055 + 13*0,0064 + 14*0,0076 + 15*0,0091 + 16*0,0111 + 17*0,0139 + 18*0,0179 + 19*0,0238 + 20*0,0333 + 21*0,0500 + 22*0,0833 + 23*0,1667 + 24*0,5000) = 0,1244 бит/сек

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

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, а 2-ой группе = знак 1. каждую из образованных подгрупп делим на две части таковым образом, чтоб суммарные вероятности вновь образованных подгрупп были по способности равны. Первым группам каждой из подгрупп вновь присваиваем 0, а вторым 1. таковым образам мы получаем мы получаем 2-ые числа кода. Потом каждую из 4 групп вновь делим на равные части до того времени, пока в каждой из подгрупп не остается по одной буковке.

Лучший код (получившийся итог):

Буковка

Возможность

возникновения буковкы

Кодовое слово
Число символов в кодовом слове
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 абс(s/2-s1)<абс(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 знака, для 2-ух случаев:

1] если знаки алфавита встречаются с равными вероятностями;

2] если вероятности не равны.

Также я обусловил количество недогрузки знаков во 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. Марченко А.И. Программирование в среде TurboPascal 7.0.

]]>