РГР_ИТ_ДМ_01

К а ф е д р а У п р а в л е н и я

А в то м а т и з и р о в а н н ы м и П р о и з в о д с т в а м и Л е с о п р о м ы ш л е н н о г о К о м п л е к с а

ИНФОРМАЦИОННЫЕ

ТЕХНОЛОГИИ

РАСЧЁТНО-ГРАФИЧЕСКАЯ РАБОТА

«Расчёт оптимального кода по методике Шеннона — Фано»

СПРАВОЧНЫЕ

МАТЕРИАЛЫ

Пример оформления титульного листа РГР

Министерство образования и науки РФ Московский Государственный Университет Леса

Кафедра Управления Автоматизированными Производствами Лесопромышленного Комплекса

Расчётно-графическая работа

по дисциплине Информационные технологии

«Расчёт оптимального кода по методике Шеннона – Фано»

Выполнил студент группы ДМ-__ Фамилия И.О. Принял Ст. преп. Лапин А. С.

Москва 20__

Исходные данные для выполнения расчёта

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

	Пример выполнения расчёта
	Содержание:
Оглавление
1	Аннотация..............................................................................................	5
2	Содержание задания ............................................................................	5
3	Теоретическая часть..............................................................................	7
	3.1 Количественная оценка информации.........................................	7

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

способности каналов связи..............................................................................

8

3.3Определение избыточности сообщений. Оптимальное

кодирование...................................................................................................		11
4 Практическая часть .............................................................................		14
4.1	Содержание задания .................................................................	14
4.2	Расчёт на основе исходных данных ..........................................	14
4.2.1 Определение количества информации, соответствующего
одному символу сообщения, составленного из данного алфавита ........		14

4.2.2Вычисление теоретической скорости передачи сообщений

15

4.2.3Вычисление избыточности сообщений, составленных из

данного алфавита .......................................................................................		15
	4.2.4 Построение оптимального кода сообщения........................	15
5	Заключение .........................................................................................	17
6	Библиографический список................................................................	18

1Аннотация

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

Также для данного алфавита выполняется построение оптимального двоичного кода на основе методик Шеннона – Фано и Хаффмана.

В процессе выполнения данной расчётно-графической работы происходит закрепление знаний, полученных при освоении дисциплины «Информационные технологии».

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

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

Для выполнения расчётов предполагается использование демонстрационной версии интегрированной среды выполнения инженерных расчётов PTC Mathcad или разработка прикладной программы средствами одного из современных языков программирования высокого уровня.

Число символов алфавита k = + 7.

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

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

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

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

Число символов алфавита равно k. Вероятности появления символов равны соответственно:

Длительности символов: 1 = 1 с; 2 = 2 с; k = k-1 + 1.

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

Сообщения составляются из алфавита с числом символов, равным k. Вероятность появления символов алфавита равна соответственно:

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

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

3.1Количественная оценка информации

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

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

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

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

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

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

Количество информации определяется исключительно характеристиками первичного алфавита, объём — характеристиками вторичного алфавита. Объём информации может быть вычислен следующим образом:

Где lср — средняя длина кодовых слов вторичного алфавита.

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

Где n — длина кода (число элементарных посылок в коде).

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

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

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

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

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

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

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

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

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

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

Где ai — передаваемый сигнал; bj — сигнал, соответствующий переданному ai сигналу. События A и B статистически жёстко связаны. При отсутствии помех, условная вероятность максимальна p(bj / ai) = 1, а условная энтропия:

так как log2p(bj / ai) = log21 = 0.

При высоком уровне помех любой из принятых сигналов bj может соответствовать любому переданному сигналу ai — статистическая связь между переданными и принятыми сигналами отсутствует. В этом случае вероятности p(ai) и p(bj) есть вероятности независимых событий и p(bj / ai) = p(bj); p(ai / bj) = p (ai).

Информационные характеристики реальных каналов лежат между этими двумя предельными случаями.

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

В случае для двоичного кода, выражение для расчёта пропускной способности примет вид:

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

или следующим образом:

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

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

Для симметричных бинарных каналов, в которых сигналы передаются при помощи двух качественных признаков и вероятность ложного приёма pЛ = p(1/0) = p(0/1), а вероятность правильного приёма pП = 1 - pЛ, потери учитываются при помощи условной энтропии вида:

Пропускная способность для таких каналов может быть определена следующим образом:

Таким образом, формула пропускной расчёта способности для симметричного бинарного канала будет иметь следующий вид:

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