Министерство образования и науки РФ

Московский Государственный Университет Леса

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

Лесопромышленного Комплекса

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

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

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

Выполнил студент группы ДМ-11 Шкурин М.

Принял Ст. преп. Лапин А. С.

Москва 2014

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

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

переменной λ— младшая цифра, использованная при записи номера

зачётной книжки студента.

Содержание:

Оглавление

1 Аннотация…………………………………………………………………4

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

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

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

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

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

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

кодирование………………………………………………………………..11

4 Практическая часть……………………………………………………...15

4.1 Содержание задания…………………………………………………..15

4.2 Расчёт на основе исходных данных………………………………....15

4.2.1 Определение количества информации, соответствующего

одному символу сообщения, составленного из данного алфавита……16

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

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

данного алфавита…………………………………………………………17

4.2.4 Построение оптимального кода сообщения……………………...17

5 Заключение……………………………………………………………...18

6 Библиографический список……………………………………………20

Приложение……………………………………………………………….21

1Аннотация

В данной расчётно-графической работе рассматривается алфавит из

символов, появляющихся с определённой вероятностью, для которого

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

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

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

происходит закрепление знаний, полученных при освоении дисциплины

«Информационные технологии».

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

Исходные данные для выполнения расчётно-графической работы

индивидуальны и определяются на основе значения переменной λ,

указанного в задании на расчётно-графическую работу.

Для выполнения расчётов предполагается использование

демонстрационной версии интегрированной среды выполнения

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

средствами одного из современных языков программирования высокого

уровня.

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

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

одному символу сообщения, составленного из данного алфавита:

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

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

вероятностями:

p₁=;

p₂ =; p₃ =

p_n-1=; p_n=_.

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

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

Длительности символов: τ₁ = 1 с; τ₂ = 2 с; τ_k-1 = τ_k-1 + 1.

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

составленных из таких символов?

Cообщения составляются из алфавита с числом символов, равным k.

Вероятность появления символов алфавита равна соответственно:

p₂ =; p₃ =

p_n-1=; p_n=_.

Найти избыточность сообщений, составленных из данного алфавита.

Построить оптимальный код сообщения.

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

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

Общее количество неповторяющихся сообщений, которое может быть

составлено из алфавита m, путём комбинирования по n символов в

сообщении:

N = mⁿ (1)

Неопределённость, приходящаяся на символ первичного

(кодируемого) алфавита, составленного из равновероятностных и

взаимонезависимых символов:

H = log₂m (2)

Так как информация есть неопределённость, снимаемая при

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

I=kHбит (3)

Для случаев равновероятностных и взаимонезависимых символов

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

равно:

I= klog₂ mбит (4)

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

составляет:

H =log₂ =log₂ p_iбит/символ (5)

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

неравновероятностных символов:

I= klog₂ p_iбит (6)

Количество информации определяется исключительно

характеристиками первичного алфавита, объём — характеристиками

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

Q = klср(7)

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

Для равномерных кодов (когда все комбинации кода содержат

одинаковое количество разрядов), количество информации может быть

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

Q = kn(8)

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