Контрольная работа - Теория информации. 2 - файл n1.doc

Контрольная работа - Теория информации. 2
скачать (124 kb.)
Доступные файлы (1):
n1.doc124kb.01.06.2012 07:49скачать

n1.doc

Факультет дистанционного образования

Томский государственный университет систем управления и радиоэлектроники (ТУСУР)


Кафедра автоматизации обработки информации (АОИ)

Контрольная работа №2

По дисциплине «Теория информации»
Учебное пособие Ю.П. Акулиничева, В.И. Дроздовой «Теория информации»

Задача 3.

Сколько вопросов в среднем надо задать, чтобы отгадать заданное собеседником целое положительное число, не превосходящее А, если спрашиваемый на все вопросы отвечает лишь «да» или «нет»?

Указание: воспользоваться кодом Шэннона-Фэно. Число А равно номеру варианта плюс 7.

Решение:

A=11+7=18. Имеем алфавит из 18 букв. В результате кодирования методом Шеннона-Фэно получаем:

Буква

Разряды кода

Код

1

2

3

4

5

1

0

0

0

0




0000

2

0

0

0

1




0001

3

0

0

1

0




0010

4

0

0

1

1




0011

5

0

1

0

0




0100

6

0

1

0

1




0101

7

0

1

1

0

0

01100

8

0

1

1

0

1

01101

9

0

1

1

1




0111

10

1

0

0

0




1000

11

1

0

0

1

0

10010

12

1

0

0

1

1

10011

13

1

0

1

0




1010

14

1

0

1

1




1011

15

1

1

0

0




1100

16

1

1

0

1




1101

17

1

1

1

0




1110

18

1

1

1

1




1111

Среднее количество вопросов равно средней длине кодового слова:

, где lkдлина кодового слова, p(uk) – вероятность буквы (в данном случае p(uk) = 1/18=0.05556, т.к. каждая буква равновероятна).

Таким образом, средняя длина кодового слова:

.

Ответ: 4.223.
Задача 4.

Сообщение источника составляется из статистически независимых букв а1, а2, а3 с вероятностями, заданными таблицей 3.

Произвести двоичное кодирование по методу Хафмана отдельных букв и двухбуквенных блоков. Сравнить коды по их эффективности.



Решение:

1) Кодирование отдельных букв:



Энтропия источника сообщений:



бит/симв.

Средняя длина кодового слова:

симв./букву.

Коэффициент эффективности:

.

Избыточность:



2) Кодирование двухбуквенных блоков:

Строим вспомогательный алфавит из N=32 блоков: (a1a1, a1a2, a1a3, a2a1, a2a2, a2a3, a3a1, a3a2, a3a3).

Вероятности блоков находим по формуле , считая буквы исходного алфавита независимыми. Располагаем блоки в порядке убывания вероятностей и осуществляем кодирование методом Хаффмана.

Всю процедуру построения представим в виде таблицы:


Исходный алфавит

Промежуточные алфавиты

A1

A2

A3

A4

A5

A6

A7

a3a3


0.1225

110

0.195

111

0.21

00

0.2275

01

0.245

10

0.3175

11

0.4375

0

0.5625

1

a3a2


0.1225

101

0.1225

110

0.195

111

0.21

00

0.2275

01

0.245

10

0.3175

11

0.4375

0

a2a3


0.1225

100

0.1225

101

0.1225

110

0.195

111

0.21

00

0.2275

01

0.245

10







a2a2


0.1225

011

0.1225

100

0.1225

101

0.1225

110

0.195

111

0.21

00













a3a1


0.105

010

0.1225

011

0.1225

100

0.1225

101

0.1225

110



















a2a1


0.105

001

0.105

010

0.1225

011

0.1225

100

























a1a3


0.105

000

0.105

001

0.105

010































a1a2


0.105

1111

0.105

000





































a1a1


0.09

1110










































Энтропия источника сообщений:

бит/симв.

Средняя длина кодового слова:



симв./букву.

Коэффициент эффективности:

.

Избыточность:

.

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

Томский государственный университет систем управления и радиоэлектроники (ТУСУР)
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации