СОДЕРЖАНИЕ
Содержание
Аннотация
Введение
Содержаниезадания
Теоретическаячасть
Практическаячасть
а)расчеты
б)программа
Заключение
а)результаты работы программы
б)блок-схема
Литература
АННОТАЦИЯ
В этой работе по данномучислу символов в алфавите рассчитываются их вероятности, количество информации,если символы встречаются с равными вероятностями и с разными вероятностями,недогруженность символов, скорость передачи сообщений и избыточность сообщений.Кроме того, в данной работе строится оптимальный двоичный код по методике Шеннона– Фано. Выполнение этой курсовой работы закрепляет наши знания по дисциплине«Теория информации».
К работе прилагаетсяпрограмма, написанная на языке программирования высокого уровня (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