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

СОДЕРЖАНИЕ

Содержание

Аннотация

Введение

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

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

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

а)расчеты

б)программа

Заключение

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

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

Литература


АННОТАЦИЯ

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

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

SUMMARY

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


ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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


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

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

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

Определить,насколько недогружены символы во втором слу­чае.

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.

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

Определитьколичество информации на символ сообщения, составленного из этого алфавита:

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

Определить,насколько недогружены символы во втором случае.

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*log2pi бит/символ

i=1 i=1

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

m

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

i=1

ВЫЧИСЛЕНИЕСКОРОСТИ ПЕРЕДАЧИ ИНФОРМАЦИИ И ПРОПУСКНОЙ СПОСОБНОСТИ КАНАЛОВ СВЯЗИ

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

C = n*H,

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

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

/> бит/сек,

где тау — время передачиодного двоичного символа.

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


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

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

m

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

i=1

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

/>

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

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

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

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

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

/> бит/сек (15)

или

/> бит/сек

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

/>

/> бит/сек (16)

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

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

/> бит/сек (17)

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

/> бит/сек (18)

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

/>

/> бит/сек (19)

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

/> бит/сек (20)

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

 

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

∆D=(Нмакс-Н)бит/символ

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

/>/>,

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

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

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

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

/>


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

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

/>

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

/> дв. симв.

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

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

/>

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

/>


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

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

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

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

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

3) первой группеприсваивается символ 0, а второй группе — символ 1;

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

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

Построенный код называютоптимальным неравномерным кодом (ОНК).


ПРАКТИЧЕСКАЯЧАСТЬ

 

a)Расчеты

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

2)    выполняет нормирование указанныхвероятностей.

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

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

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

6)    строится оптимальный код по методуШеннона-Фано.

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

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

 k-1

 ...pk = S pn /(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*log20,0417+ 0,0018*log20,0018 + 0,020*log2 0,0020 + 0,0022*log20,0022+ 0,0024*log20,0024 + 0,0026*log20,0026 + 0,0029*log20,0029+ 0,0033*log20,0033 + 0,0037*log20,0037 + 0,0042*log20,0042+ 0,0048*log20,0048 + 0,0055*log20,0055 + 0,0064*log20,0064+ 0,0076*log20,0076 + 0,0091*log20,0091 + 0,0111*log20,0111+ 0,0139*log20,0139 + 0,0179*log20,0179 + 0,0238*log20,0238+ 0,0333*log20,0333 + 0,0500*log20,0500 + 0,0833*log20,0833+ 0,1667*log20,1667 + 0,5000*log20,5000) =

= 2,6409 бит/символ


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

N = Нmax – Н = 4,5850 – 2,6409 = 1,9441 бит/символ

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

С= – (0,0417*log20,0417+ 0,0018*log20,0018 + 0,020*log2 0,0020 + 0,0022*log20,0022+ 0,0024*log20,0024 + 0,0026*log20,0026 + 0,0029*log20,0029+ 0,0033*log20,0033 + 0,0037*log20,0037 + 0,0042*log20,0042+ 0,0048*log20,0048 + 0,0055*log20,0055 + 0,0064*log20,0064+ 0,0076*log20,0076 + 0,0091*log20,0091 + 0,0111*log20,0111+ 0,0139*log20,0139 + 0,0179*log20,0179 + 0,0238*log20,0238+ 0,0333*log20,0333 + 0,0500*log20,0500 + 0,0833*log20,0833+ 0,1667*log20,1667 + 0,5000*log20,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

еще рефераты
Еще работы по информатике, программированию