litceysel.ru 1


М
ИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ



ФГБОУ ВПО

«Воронежский государственный УНИВЕРСИТЕТ

ИНЖЕНЕРНЫХ ТЕХНОЛОГИЙ»


КАФЕДРА ИНФОРМАЦИОННЫХ ТЕХНЛОГИЙ МОДЕЛИРОВАНИЯ И УПРАВЛЕНИЯ


Методические указания и задания

по выполнению контрольной работы

по курсу “ТЕОРЕТИЧЕСКИЕ АСПЕКТЫ ИНФОРМАЦИОННЫХ ПРОЦЕССОВ”

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

230400 заочной формы обучения




ВОРОНЕЖ

2011


Цель работы - изучение основ и принципов кодирования и декодирования информации при ее передачи от источника к приемнику на примере построения кода Шеннона - Фэно.


1. ОПИСАНИЕ ПРИНЦИПОВ ПОСТРОЕНИЯ КОДОВ


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

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

Наиболее простым случаем кодирования является случай, когда обе системы X и Y (отображаемая и отображающая) имеют конечное число возможных сообщений. Так обстоит дело при передаче записанных буквами сообщений, например при телеграфировании. Ограничимся рассмотрением этого простейшего случая кодирования.

Пусть имеется некоторая система X, которая может случайным образом принять одно из состояний x1,x2,...,xn. Необходимо закодировать ее с помощью другой системы Y, возможные состояния которой y1,y2,...,ym. Если m < n (число состояний системы Y меньше числа состояний системы Х), то нельзя каждое состояние системы X закодировать с помощью одного-единственного состояния системы Y. В таких случаях одно состояние системы X приходится отображать с помощью определенной комбинации (последовательности) состояний системы Y. Так, в азбуке Морзе буквы отображаются различными комбинациями элементарных символов (точка, тире). Выбор таких комбинаций и установление соответствия между передаваемым сообщением и этими комбинациями и называется "кодированием" в узком смысле слова


Коды различаются по числу элементарных символов (сигналов), из которых формируются комбинации, т.е. по числу возможных состояний системы Y. В азбуке Морзе элементарных символов четыре – точка, тире, короткая пауза, длительная пауза. Передача символов может осуществляться в различной форме: световые вспышки, посылки электрического тока различной длительности, звуковые сигналы и т.п. Широко распространены коды с двумя элементарными символами (0 и 1), такие коды называются двоичными [2]. Двоичные коды используются, например, при вводе, обработке и выводе информации в ЭВМ.

Одно и то же сообщение можно закодировать различными способами. Поэтому необходимо найти оптимальный способ кодирования, при котором на передачу сообщений тратится минимальное время. Если на передачу каждого элементарного символа (например 0 или 1) тратится одно и то же время, то оптимальным будет такой код, при котором на передачу сообщения заданной длины будет затрачено минимальное количество элементарных символов.

Рассмотрим следующую задачу: закодировать двоичным кодом буквы так, чтобы каждой букве соответствовала определенная комбинация символов 0 и 1 и чтобы среднее число этих символов на букву текста было минимальным.

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

Первый вариант: не меняя порядка букв, пронумеровать их от 0 до 31 и перевести в двоичную систему счисления. Тогда получим следующий код:


а ~ 00000

б ~ 00001

в ~ 00010

г ~ 00011

.........

я ~ 11110

- ~ 11111

В этом коде на каждую букву тратится ровно 5 элементарных символов. Возникает вопрос, является ли этот код оптимальным и нельзя ли составить другой код, в котором на одну букву будет в среднем приходиться меньше элементарных символов?.


В связи с этим рассмотрим другой способ кодирования [1]. Так как одни буквы (а, е, о) встречаются часто, а другие (щ, э, ф) редко, то часто встречающиеся буквы целесообразно закодировать меньшим числом символов, а реже встречающиеся - большим. Чтобы составить такой код, нужно знать частоты букв в русском тексте. Они известны и приведены в табл. 1.

Т а б л и ц а 1





буква

частота

буква

частота

буква

частота

буква

частота

-

0.145

р

0.041

я

0.019

х

0.009

о

0.095

в

0.039

ы

0.016

ж

0.008

е

0.074

л

0.036

з

0.015

ю

0.007

а

0.064

к

0.029

ъ,ь


0.015

ш

0.006

и

0.064

м

0.026

б

0.015

ц

0.004

т

0.056

д

0.026

г

0.014

щ

0.003

н

0.056

п

0.024

ч

0.013

э

0.003

с

0.047

у

0.021

й

0.01

ф

0.002

Пользуясь такой таблицей, можно составить наиболее экономичный код на основе соображений, связанных с количеством информации. Код будет самым экономичным, когда каждый элементарный символ будет передавать максимальную информацию. Рассмотрим элементарный символ т.е. изображающий его сигнал, как физическую систему с двумя возможными состояниями 0 и 1. Информация, которую дает этот символ, равна энтропии системы и максимальна в случае, когда оба состояния равновероятны. В этом случае элементарный символ передает информацию, равную одной 1 двоичной единице. Поэтому основой оптимального кодирования будет требование, чтобы элементарные символы в закодированном тексте встречались в среднем одинаково часто.



2. ОПИСАНИЕ АЛГОРИТМА ПОСТРОЕНИЯ КОДА ШЕННОНА - ФЭНО


Принцип построения кода Шеннона - Фэно позволяет говорить об оптимальности кода, так как соответствует поставленным выше требованиям. Способ построения кода проиллюстрирован в табл. 2.

Он удовлетворяет тому условию, для которого символы в закодированном тексте встречаются в среднем одинаково часто. Идея построения кода Шеннона - Фэно состоит в том, что кодируемые символы (у нас буквы) разделяются на две приблизительно равновероятные группы: для первой группы символов на первом месте комбинации символов становится 0, для второй группы - 1. Далее каждая группа снова делится на две приблизительно равновероятные подгруппы: для символов первой подгруппы на втором месте ставится 0; для второй подгруппы - 1 и т.д.

В нашей задаче возьмем первые шесть букв ( от - до Т), сумма их вероятностей = 0.498; на все остальные буквы (от Н до Ф) придется вероятность 0.502. Первые шесть букв будут иметь на первом месте 0, остальные - 1.

Далее снова разделим первую группу на две приблизительно равновероятные подгруппы : (от - до о ) и (от е до т) и т. д. Для всех букв первой подгруппы на втором месте поставим нуль, а второй подгруппы - единицу. Процесс будем продолжать пор, пока в каждом подразделении не окажется ровно одна буква, которая и будет закодирована определенным двоичным числом. Механизм построения кода показан на табл. 2, а сам код приведен в табл. 3


Т а б л и ц а 2


буквы

1-й

2-й

3-й

4-й

5-й

6-й

7-й


8-й

9-й

-



0


0

0



















о

1




е


1



0

0

а

1

и


1

0

т

1

н



1



0


0

0

с

1

р



1


0

0

в

1

л


1

0

к


1

м



1



0


0

0

д


1

0

п

1

у


1

0




я


1

0

ы

1

з



1




0


0

0

ъ,ь

1

б


1

0

г

1

ч



1



0

0

й


1

0

х

1

ж



1




0

0

ю

1

ш



1



0

0

ц

1

щ


1

0

э


1

0

ф

1

Т а б л и ц а 3





буква

дв. код

буква

дв.код

буква

дв.код

-

000

к

10111

ч

111100

о

001

м

11000

й

1111010

е

0100

д

110010

х

1111011


а

0101

п

110011

ж

1111100

и

0110

у

11010

ю

1111101

т

0111

я

110110

ш

11111100

н

1000

ы

110111

у

11111101

с

1001

з

111000

щ

11111110

р

10100

ь, ъ

111001

э

111111110

в

10101

б

111010

ф

111111111

л

10110

г

111011








3. ПРИМЕР КОДИРОВАНИЯ И ДЕКОДИРОВАНИЯ СООБЩЕНИЙ МЕТОДОМ ШЕННОНА - ФЭНО



С помощью табл. 2 можно закодировать и декодировать любое сообщение. В виде примера запишем двоичным кодом фразу: "Теория информаций"


0 111 010000 11 01 000 11 011 11 0000

01101000111111 111 00110 100

11 0000 10111111 10101100110


Отметим, что здесь нет необходимости отделять буквы друг от друга специальным знаком, т.к. и без этого декодирование выполняется однозначно. Убедимся в этом, декодируя с помощью табл. 2 следующую фразу:


10011100110011001001111010000

1011100111001001101010000110101

010110000110110110


Результат декодирования - фраза "способ кодирования". При таком кодировании любая ошибка (случайное перепутывание знаков 0 и 1) губительна, т.к. декодирование всего следующего за ошибкой текста становится невозможным. Поэтому данный принцип кодирования используется тогда, когда ошибки при кодировании и передаче сообщения исключены.


4. АНАЛИЗ ОПТИМАЛЬНОСТИ КОДА ШЕННОНА - ФЭНО


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


,


где pi - вероятность того, что буква примет определенное состояние (-, о, е, а,..., ф).

Из табл. 1 определяем


Н(б) = - (0.145 log 0.145 + 0.095 log 0.095 + ... + 0.002 log 0.002),

Н(б)  4.42 (двоичных единиц на одну букву текста).


По табл. 2 определяется среднее число элементарных символов на букву

nср = 30.145 + 30.095 + ... + 90.002 = 4.45.



Деля энтропию Н(б) на nср, вычисляется информация на один элементарный символ


Iср = 4.42 / 4.45  0.994 (дв. ед.).


Таким образом, информация на один символ очень близка к своему верхнему пределу - 1. Следовательно построенный код в целом отвечает принципу оптимальности. Оставаясь в пределах задачи кодирования по буквам, ничего лучшего получить нельзя

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


Iср = 4.42 / 5.00= 0.884 (дв. ед.),


т. е. заметно меньше, чем при кодировании методом Шеннона - Фэно.

Однако следует обратить внимание, что кодирование “по буквам” вообще не является экономичным. Дело в том, что между соседними буквами любого осмысленного текста всегда имеется зависимость. Например, после гласной буквы в русском языке не может стоять “ъ” или ”ь”; после шипящих не могут стоять “я” или ”ю”; после нескольких согласных подряд увеличивается вероятность гласной и т.д.

Известно, что при объединении зависимых систем суммарная энтропия меньше суммы энтропий отдельных систем. Следовательно, информация, передаваемая отрезком связного текста, всегда меньше, чем информация на один символ, умноженная на число символов. С учетом этого обстоятельства более экономичный код можно построить, если кодировать не каждую букву в отдельности, а целые “блоки” из букв. Например, в русском тексте имеет смысл кодировать целиком некоторые часто встречающиеся комбинации букв, как “тся”, “ает”, “ние” и т. п. Кодируемые блоки располагаются в порядке убывания частот, как буквы в табл. 1, а двоичное кодирование осуществляется по тому же принципу.

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


“поздравляю новым годом желаю здоровья успехов работе”.


5. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ


  1. получить вариант задания у преподавателя;

  2. реализовать алгоритм построения кода методом Шеннона-Фэно в виде программного модуля;

  3. выполнить вычисления на ЭВМ;

  4. проанализировать результаты вычислений;

  5. оформить отчет о работе.


6. КОНТРОЛЬНЫЙ ПРИМЕР


Алфавит состоит из семи символов с вероятностями:


а

в

л

и

е

с

к

0.3

0.2

0.15

0.1

0.1

0.08

0.07


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

а – 00

в – 01

л – 100

и – 101

е – 110

с – 1110

к – 1111

Пусть входное сообщение: "вилка". Выходная последовательность кодов: 01101100111100. Если входная последовательность кодов: 1000101111000. Сообщение на вы ходе: "лиса".


7. ТРЕБОВАНИЯ К ОТЧЕТУ


Отчет должен содержать:

  1. название работы;

  2. задание - номер варианта и вариант;

  3. схему алгоритма;

  4. программу;

  5. результаты счета.

8. КОНТРОЛЬНЫЕ ВОПРОСЫ.



1. На каких принципах основывается кодирование сообщений при передаче информации?

2. Что такое двоичное кодирование?

3. Дайте характеристику оптимального кодирования?

4. Чем отличается обычное кодирование двоичным кодом букв русского алфавита от оптимального кодирования по методу Шеннона - Фэно?

5. Является ли кодирование по буквам экономичным?

9. БИБЛИОГРАФИЧЕСКИЙ СПИСОК



1. Вентцель Е.С. Теория вероятностей. М. : Гос. издат. физ. - мат. литературы, 1962. - 564 с.

2. Дмитриев В.И. Прикладная теория информации. М. : Высш. шк., 1989. - 320 c.

3. Рози А.М. Теория информации в связи. М. : Энергия, 1971. - 184 с.

10. ПРИЛОЖЕНИЕ


ЗАДАНИЕ. Имеется алфавит символов и их частоты, с которыми они встречаются в тексте. Требуется построить таблицу кодов символов. Закодировать данное сообщение и раскодировать полученную последовательность кодов. Для этого написать программу на одном из языков программирования. Оформить отчет.


11. ВАРИАНТЫ ЗАДАНИЙ





  1. Алфавит: а б в г д е ж з и к л

Частоты: 0.05 0.08 0.07 0.04 0.1 0.09 0.12 0.09 0.11 0.15 0.1

Сообщение: гдежилабелка


  1. Алфавит: а b c d e f i h g k l

Частоты: 0.04 0.07 0.08 0.03 0.1 0.08 0.13 0.09 0.11 0.14 0.11

Сообщение: hgfebalkg



  1. Алфавит: * @ ( % + $ ! # | ? ~

Частоты: 0.05 0.09 0.06 0.07 0.1 0.06 0.13 0.08 0.13 0.12 0.1

Сообщение: (?%$|~?%#@*



  1. Алфавит: а & l г 8 # v ? и x q

Частоты: 0.03 0.1 0.05 0.06 0.12 0.07 0.1 0.11 0.13 0.15 0.08

Сообщение: гаl&qx#v?



  1. Алфавит: j б * f д @ 7 ^ i ! л

Частоты: 0.07 0.06 0.09 0.02 0.12 0.07 0.14 0.07 0.13 0.16 0.07


Сообщение: *jл@f^дд!i



  1. Алфавит: 0 ч s & д е # з g ь +

Частоты: 0.08 0.05 0.1 0.01 0.13 0.06 0.15 0.06 0.13 0.15 0.07

Сообщение: ч0д#gsь++з



  1. Алфавит: З Д О Е Ь Р В А Я М !

Частоты: 0.01 0.12 0.03 0.08 0.1 0.05 0.16 0.05 0.15 0.11 0.14

Сообщение: ЗДОРОВЬЯВАМ!


  1. Алфавит: < D J % N ! V T > Z Y

Частоты: 0.09 0.04 0.11 0.01 0.1 0.08 0.14 0.05 0.15 0.11 0.12

Сообщение: V>NYY


  1. Алфавит: и б ? u e п $ j и # h

Частоты: 0.07 0.08 0.05 0.06 0.1 0.07 0.12 0.11 0.09 0.13 0.12

Сообщение: u$jие?hhбп#



  1. Алфавит: A б J г P k Ж , н Г >

Частоты: 0.05 0.1 0.07 0.02 0.1 0.11 0.12 0.07 0.11 0.17 0.08

Сообщение: AkГ,PнбJгг>



  1. Алфавит: O H ! P A L W Y K U G

Частоты: 0.04 0.08 0.07 0.06 0.1 0.11 0.12 0.09 0.08 0.11 0.14

Сообщение: HAPPYYOU!!!



  1. Алфавит: Н Й В С Щ О М Г Ы ! Л

Частоты: 0.02 0.08 0.09 0.04 0.1 0.13 0.12 0.07 0.11 0.17 0.1

Сообщение: СНОВЫМГОДОМ