Файл: Теория информации.pdf

32
5
Лабораторная
работа
№
5.
Информационные
характеристики каналов связи
5.1 Цель работы
Вычисление скорости передачи информации и пропускной способности каналов связи
5.2 Теоретические сведения
Основными характеристиками информационных систем являются такие по- нятия, как энтропия, скорость передачи информации, избыточность, пропускная способность канала связи. Для организации передачи информации по канала связи надо учитывать не только количество информации, но и обеспечение пере- дачи его в более короткий срок, не только хранение определенного количества, но и хранение с помощью минимального объема аппаратуры и т.д.
Предположим, что по каналу связи передали за время Т количество ин- формации, которое равно
Можно вычислить скорость передачи данных
Скорость передачи данных представляет собой количество информации, приходящееся на одно сообщение. Если количество сообщений равно n, то ско- рость передачи n сообщений в секунду будет определяться
В этом случае максимальная пропускная способность данного канала пред- ставляет собой с

33
Различают техническую скорость передачи и информационную скорость передачи информации.
Технической скоростью передачи информации по каналу связи называется число символов, передаваемых в единицу времени
Информационной скоростью передачи информации по каналу связи назы- вается среднее количество информации, которое передается в единицу времени
Если сообщения являются равновероятными, составленные из равноверо- ятных взаимно независимых символов, то их информационная скорость равна
Если символы в сообщении не равновероятны, то скорость определяется
В случае, если символы имеют разную длительность
Пропускная способность канала передачи информации характеризуется максимальной энтропией
Для двоичного кода
1 Теорема Шеннона.
Пусть есть источник информации с энтропией H(X ) и канал связи с пропу- скной способностью с, то если c > H(X), то всегда можно закодировать достаточ-

34 но длинное сообщение таким образом, что оно будет передано без задержек. Если c < H(X), то передача информации без задержек невозможна.
Для всех практических каналов характерно наличие помех. На есть случаи, когда помехи малы, то вероятность искажения передаваемого сообщения равна нулю и можно считать, что все сигналы передаются верно. В этом случае среднее количество информации, переносимое одним символом
Следовательно, пропускная способность канала без помех за единицу времени
Реальные каналы характеризуются тем, что в них всегда есть помехи. Пропускная способность дискретного канала с помехами вычисляется
2 Теорема Шеннона.
Для дан источник информации Х, энтропия равна H(X ), и пропускная способность равна с. Если H(X) > c , то справедливо, что при любом методе ко- дировании передача сообщений без задержек и искажений невозможна. Если
H(X) < c , то любое достаточно длинное сообщение можно всегда закодировать так, что оно будет предано без задержек и искажений с вероятностью сколь угод- но близкой к единице.
Пример 1. Дандискретный симметричный канал без памяти, на вход кото- рого поступают двоичные символы x1= 0; x2 = 1 c априорными вероятностями
P(x1) = 0,85; P(x2) = 0,15. Переходные вероятности задаются соотношением где Р = 0,05 – это вероятность ошибки. Определить апостериорные вероятности.
Решение. Ситуация в канале характеризуется схемой

35
Так как вероятность ошибки Р= 0,05, то вероятность правильного приема q = 1 - 0,05 = 0,95.
В таком канале каждый кодовый символ может быть принят с ошибочной вероятностью
Правильно переданная информация описывается
5.3 Задание
Задача 1. Заданканал передачи информации без шума, по которому переда- ется сообщение из ансамбля:

36
Средняя длительность передачи одного элемента сообщения в канале
Найти: пропускную способность канала; скорость передачи информации в канале без шума.
Задача 2. Задан источник с вероятностями появления символов источника алфавита p(x1) = 0,5; p(x2) =0,25; p(x3) = 0,125; p(x4) = 0,125. Между соседни- ми символами имеются корреляционные связи, заданные матрицей вероятностей
Определить избыточность источника при статистической независимости символов и избыточность при зависимости символов.
Задача 3. Задан канал передачи информации, алфавит передаваемых сооб- щений содержит три символа с вероятностями p1 = 0,2; p2 = 0,7; p3 = 0,1. Чтобы передать информации по каналу без помех был применен равномерный двоич- ный код. Задана частота тактовых импульсов генератора 500 Гц. Найти пропуск- ную способность канала и скорость передачи информации.
Задача 4. Заданканал связи, по которому передается три символа
Матрица безусловных вероятностей источника сигналов

37
Канал связи характеризуется при p1 = 0,01; p2 = 0,02; p3 = 0,97 матрицей условных вероятностей
Определить пропускную способность канала. Сравнить производительность источника и пропускную способность канала.
Задача 5. По двоичному симметричному каналу связи с помехами переда- ются два символа с вероятностями p(x1) = 0,75 и p(x2) = 0,25. Из-за наличия по- мех вероятность правильного приема каждого из сигналов уменьшается до 0,875.
Необходимо определить: производительность и избыточность источника; скорость передачи информации и пропускную способность канала связи.
Задача 6. Определить скорость передачи информации для сообщений анг- лийского алфавита, при этом известно, что буквы e, t, o, n передаются за 10 мс каждая, а остальные за 20 мс каждая. При решении применить данные о распре- делении вероятностей букв в английском тексте.
5.4 Контрольные вопросы
1 Дать определения и пояснения технической и информационной скоро- сти передачи. Назвать единицы измерения и области применения этих понятий.
2 Дать определение информационной скорости для равновероятных со- общений. В чем заключается отличие от случая неравновероятных сообщений?
3 Дать определение пропускной способности канала без помех и с поме- хами, назвать единицы измерения, привести области применения этого понятия.
4 Сформулируйте и поясните первую и вторую теоремы Шеннона. В ка- ких задачах нашли применение эти теоремы?

38
6 Лабораторная работа № 6. Избыточность и оптимальное
кодирование информации
6.1 Цель работы
− Вычисление избыточности кодов.
− Освоение приемов кодирования на основе кода Шеннона-Фано.
6.2 Теоретические сведения
Преобразование информации из одной формы представления (знаковой системы) в другую называется кодированием. Все виды информации в вычислительных системах кодируются на машинном языке в виде последовательностей логических нуля и единицы.
Двоичный код можно представить как два равновероятных состояния: «0» и
«1». Количество информации любого двоичного символа равно одному биту.
Два символа двоичного кода несут информацию в 2 бита, три цифры – в 3 бита и т.д. Количество информации в битах равно количеству цифр двоичного машинного кода. Восемь последовательных бит равно одному байту. В одном байте можно закодировать значение одного символа из 256 возможных.
Используют умножительные приставки:
Кодирование - это процесс преобразования информации в форму, удобную для передачи по определённому каналу связи. Декодирование – восстановление принятого сообщения из кодированного вида в вид доступный для потребителя.
Одно и тоже сообщение можно закодировать различными способами.

39
Одной из основных проблем кодирования при передаче информации по ка- налам связи является оптимальный способкодирования, когда на передачу со- общения уходит минимальное время.
Предположим, что на передачу каждого элементарного символа (0 или 1) затрачивается одно и тоже время, то оптимальным будет такой код, при котором на передачу сообщения заданной длины будет затрачено минимальное количество символов.
Например, пусть имеются буквы русского алфавита а, б, в, г,…+ промежу- ток между словами (-). Если не различать ь и ъ (как принято в телеграфии), то по- лучим 32 буквы. Требуется закодировать двоичным кодом буквы так, чтобы каж- дой букве соответствовала определенная комбинация символов 0 и 1 и, чтобы среднее число этих символов на букву текста было минимальным.
1 вариант. Не меняя порядка букв, пронумеровав их от 0 до 31 и перевести их в двоичную систему счисления, получим следующий код:
В этом коде на каждую букву тратится ровно пять элементарных символов.
Является ли этот код оптимальным? Модно ли составить другой код, при котором на одну букву в среднем приходится меньше элементарных символов?
2 вариант. Так как одни буквы встречаются часто (а, о, е), а другие (щ, э, ф) редко, то часто встречающиеся буквы целесообразно закодировать меньшим чис- лом символов, а реже встречающиеся – большим. Чтобы составить такой код нужно знать частоты букв русского алфавита (таблица 5.1) . Пользуясь такой таб- лицей, можно составить наиболее экономичный код на основе соображений, свя- занных с количеством информации. Код будет самым экономичным, когда каж- дый символ будет передавать максимальную информацию.

40
Рассмотрим элементарный символ, т.е. изображающий его сигнал, как физическую систему с двумя возможными состояниями 0 и 1. Информация, которую дает этот символ, равна энтропии системы и максимальна в случае, когда оба состояния равновероятны.
Таблица 5.1 - Статистические данные русского алфавита
Метод Шеннона-Фано.
Метод Шеннона-Фано является методом оптимального кодирования. Алго- ритм построения кода Шеннона-Фано состоит в том, что кодируемые символы
(буквы) разделяются на две равновероятные подгруппы: для символов 1-й под- группы на втором месте ставится 0, а для 2-й подгруппы – 1 и т.д. Возможен дру- гой вариант, когда первая подгруппа соответствует «1», а вторая - «0». Главное, определить правило изначально и следовать ему на протяжении всего процесса кодирования.
Необходимо взять первые шесть букв (от – до т). Сумма их вероятностей равна 0,498, на все остальные (от н до ф) приходится 0,502. Первые шесть букв будут иметь на первом месте 0, остальные 1. Далее снова первая группа делится на две приблизительные равновероятные подгруппы: (от – до щ) и (от е до т) и т.д.

41
Для всех букв первой подгруппы на втором месте ставится 0, а второй под- группы – 1. Процесс продолжается до тех пор, пока в каждой группе не останется ровно одна буква, которая и будет закодирована определенным двоичным кодом.
Пример. Имеется алфавит символов и их вероятности, с которыми они встречаются в тексте. Построить таблицу кодов символов методом Шеннона-
Фано. Закодировать сообщение «вилка» и раскодировать заданную последова- тельность кодов.
Решение. Составим таблицу кодов для символов алфавита
Сообщению «вилка» соответствует выходная последовательность кодов
01101100111100. Выходной последовательности кодов 100101111000 соответст- вует сообщение «лиса».
Избыточность и оптимальное кодирование.
Если энтропия источника сообщений не равна максимальной энтропии для алфавита с заданным количеством качественных признаков, то это означает, что сообщения данного источника могли нести большее количество информации. Аб- солютная недогруженность на символ такого источника
Для определения количества «лишней» информации, которая заложена в структуре алфавита либо в природе кода, вводится понятие

избыточности. Ин-

42
формационная избыточность показывает относительную недогруженность на символ алфавита и является безразмерной величиной
Кроме общего понятия избыточности есть частные виды избыточности. Из- быточность, обусловленная неравновероятным распределением символов в сооб- щении (6.3)
Избыточность, вызванная статистической связью между символами сооб- щения (6.4)
Полная информационная избыточность
D = Ds + Dp – DsDp (6.5)
Для данного способа кодирования характерна избыточность. Это объясня- ется тем, что в результате неравномерного распределения качественных призна- ков этого кода не может быть задана одной цифрой на основании статистических испытаний. При передаче десятичных цифр двоичным кодом максимально загру- женными бывают только те символы вторичного алфавита, которые передают значения, являющиеся целочисленными степенями двойки. В остальных случаях тем же количеством символов может быть передано большее количество цифр
(сообщений). Фактически для передачи сообщения достаточно иметь длину кодо- вой комбинации (6.6)

43 где N – общее количество передаваемых сообщений. L можно представить как где m1 и m2 – соответственно качественные признаки первичного и вторичного алфавитов. Поэтому для цифры 5 в двоичном коде L > log5/log2 = 2,32 дв. симво- ла. Однако эту цифру надо округлить в большую сторону до ближайшего целого числа, так как длина кода не может быть выражена дробным числом. В общем случае избыточность от округления
Для нашего примера D0 = (3-2,32)/3 = 0,227.
Таким образом, избыточность может быть заложена как в первичном алфа- вите, так и в природе кода, составленного во вторичном алфавите.
Избыточность – не всегда нежелательное явление. Для повышения помехо- устойчивости кодов избыточность необходима и ее вводят искусственно в виде добавочных символов. (6.9)
Наиболее эффективным способом уменьшения избыточности является по- строение оптимальных кодов. Оптимальными называются коды, которые
имеют практически нулевую избыточностью. Оптимальные коды имеют ми- нимальную среднюю длину кодовых слов - L. Верхняя и нижняя границы L оп- ределяются из неравенства

44 где Н – энтропия первичного алфавита, m – число качественных признаков вто- ричного алфавита.
Под термином «оптимальный код» понимают коды с практически нулевой избыточностью, так как сравнивают длину кодовой комбинации с энтропией ис- точника сообщений, не учитывая взаимозависимость символов. С учетом взаимо- зависимости символов эффективность кодирования никогда не будет 100%, т.е.
При построении оптимальных кодов наибольшее распространение получи- ли методы Шеннона-Фано и Хаффмана.
6.3 Задание
Задача 1. Сообщения составляются из алфавита a, b, c, d. Вероятность появ- ления букв в текстах равна соответственно: pa = 0,2; pb = 0,3; pc = 0,4; pd = 0,1.
Найти избыточность сообщений, составленных из данного алфавита.
Залача 2. Чему равна минимальная длина кодовых слов для передачи 16,
128, 57, 10, 432 сообщений в восьмиричном и в двоичном кодах.
Задача 3. Пусть алфавит источника содержит шесть элементов {А, Б, В, Г,
Д, Е}, появляющихся с вероятностями Р(А)=0,15, Р(В)=0,1, Р(Б)=0,25, Р(Г)=0,13,
Р(Д)=0,25, Р(Е)=0,12. Найти энтропию такого источника, среднее число символов на одну букву при кодировании методом Ш-Ф.
Задача 4. Закодировать методом Шеннона-Фано блоки «мы все учились по- немногу чему-нибудь и как-нибудь». Каково среднее число символов на знак?
Задача 5. Сообщение состоит из последовательности букв А, B и С, вероят- ности которых не зависят от предыдущего сочетания букв и равны Р(А)=0,7,
Р(В)=0,2, Р(С)=0,1. Провести кодирование по алгоритму Шеннона-Фано отдель-