Контрольная Теория информации, задачи, номер: 170375

"Тема: Модель передачи информации по каналу связи
1)Рассмотрим информационные процессы на примере передачи информации в системе связи.
2) Понятие вероятностной схемы.

Тема: Меры информации
Задача №1:
1. Составить число сочетаний из 10 элементов по 1,2,3,4,…9?
2. Сколько вариантов дает перестановка десяти элементов без повторений?
3. Сколько размещений 10 элементов по 9-ти позициям можно составить?

Задача №2:
План застройки улицы 10 домами, среди которых 3 дома одного типа, 5 другого и 2 третьего, в каком количестве вариантов может быть представлен?

Задача №3:
Определить количество информации, которое содержится в телевизионном сигнале, соответствующем одному кадру развертки. Пусть в кадре 625 строк, а сигнал, соответствующий одной строке, представляет собой последовательность из 600 случайных по амплитуде импульсов, причем амплитуда импульса может принимать любое из 8 значений с шагом 1 В.

Задача №4:
1. Определить минимальное число взвешиваний, которое необходимо произвести на равноплечих весах, что бы среди 27 внешне не отличимых может найти одну фальшивую, более легкую.
1) 13+13+1;
2) 6+6+1;
3) 3+3;
4) 1+1+1;

Задача №5:
Алфавит состоит из букв A,B,C,D, вероятность появления которых равна ; ; ; Определить число знаков другого алфавита, у которого знаки равновероятны, а энтропия такая же как у заданного алфавита.

Задача №6.
Заданы вероятностные схемы двух сообщений:
и . Сравнить их энтропии.

Задача №7:
Задана вероятностная схема сообщения . Найти абсолютную и относительную избыточность такого источника.

Задача №8:
Определить избыточность источника, если он задан вероятностной схемой букв русского алфавита


Задача №9.
Изобразить и пояснить график зависимости энтропии двоичного источника от вероятности проявления событий.

Задача №10.
Найти значение энтропии при нормальной плотности распределения вероятности случайной величины х:
р(х) = - нормальный закон плотности распределения вероятности.


Задача№11.
Найти значение энтропии для равномерного закона плотности распределения вероятности на интервале а?x?b:



Задача №12.
При организации мешающего воздействия при передаче информации можно использовать источник шума с нормальным распределением плотности и источник, имеющий в некотором интервале равномерную плотность распределения. Определить какой источник шума применять экономичнее и каков при этом выигрыш в мощности.

Задача №13.
Определить энтропию непрерывной случайной величины, распределенной по экспоненциальному закону с плотностью вероятности:



Задача№14.
Найдите энтропию случайной величины, распределенной по закону с плотностью вероятности
р(х) =

Задача №15.
Для устранения статистических связей символов источника (их декорреляции) с целью повышения эффективности связей иногда прибегают к перекодировке, которая сводится к сопоставлению блока из n>1 символов первичного алфавита новому символу укрупненного алфавита. Показать, что этот способ устранения связей символов не изменяет избыточность сообщения.

Тема: Источники сообщений и их энтропия.
Задача №1.
Закон распределения вероятностей системы, объединяющий зависимые источники информации Х и Y задан с помощью таблицы

Х Y y1 y2 y3
x1 0,4 0,1 0
x2 0 0,2 0,1
x3 0 0 0,2
p(xi,yj) – совместная вероятность.
Определить энтропии Н(X), Н(Y), H(X/Y), H(Y/X), H(X,Y), I(X;Y).

Задача№2.
Известны энтропии двух зависимых источников Н(Х) = 5 бит; H(Y) = 10 бит. Определить в каких пределах будет изменяться условная энтропия H(Y/X) в максимально возможных пределах.

Задача№3.
Определить Н(Х) и Н(Y/X), если p(x1, y1) = 0,3; p(x1, y2) = 0,2; p(x3, y2) = 0,25; p(x3, y3) = 0,1.

Задача№4.
Определить H(X), H(Y), H(X,Y), I(X,Y), если p(x1,y1) = 0,2; p(x2,y1) = 0,4; p(x2,y2) = 0,25; p(x2,y3) = 0,15. Проверить полученные результаты через соотношения энтропий.

Задача№5.
Определить I(X;Y), если p(x1,y1)= 0,3; p(x1,y2) = 0,2; p(x2,y3) = 0,1; p(x3,y2) = 0,1; p(x3,y3) = 0,3. Проверить результаты через соотношения энтропий и взаимной информации.

Марковские источники
Задача №1.
Дана Марковская цепь с тремя равновероятными состояниями.
1) Построить матрицу переходных вероятностей через графовое представление цепи.
2) Показать, что она стационарна.
3) Показать, что она регулярна.
4) Построить предельную матрицу переходных вероятностей.


Задача№2.
Задан марковский источник А={a1, a2}, в котором буквы принимают значения 0 и 1 равновероятно. Граф состояний такого источника задан.
1) Определить матрицу вероятностей перехода.
2) Проверить источник на стационарность и регулярность.

Задача№3.
Задан граф марковской цепи. Определить матрицу переходных вероятностей, если р0 = (1 0 0) и проанализировать свойства цепи и найти вер.состояний на 2-ом шаге.

Задача№4.
Дана матрица вероятностей перехода:
П = и р0 = (0 1 0).

1) Построить граф.
2) Найти р3 при n = 3.
3) Проверить свойства.

Тема: Оптимальное, эффективное кодирование источников. Сжатие данных. Алгоритмы сжатия данных без потерь.
Задача №1.
Построить код Шеннона-Фано, если известны вероятности: р(x1) = 0,5; p(x2) = 0,25; p(x3) = 0,125; p(x4) = 0,125. Оценить эффективность кодирования.

Задача №2.
Построить код Хаффмена для алфавита источника, заданного вероятностями символов в таблице:
xi pi
X1 0,22
X2 0,2
X3 0,16
X4 0,16
X5 0,1
X6 0,1
X7 0,04
X8 0,02

Задача №3.
Провести декодирование кода Хаффмена для задачи №2.

Задача №4.
Проанализировать эффективное кодирование сообщений, образованных алфавитом, состоящим из двух знаков (букв) x1 и x2 с вероятностями р(х1) = 0,9 и р(х2) = 0,1.


Задача №5

Закодировать универсальным алгоритмом фразу - КАРЛ_У_КЛАРЫ_УКРАЛ_КОРАЛЛЫ
словарь: 26, буфер: 8

Задача №6
Составить арифметический код для сообщения ВААВС, полученного из алфавита Х = {А, В, С}, при р(А) = ?, р(В) = ?, р(С) = ?.
(1) ВААВС, р(А) = ?, p(B) = ?, p(C) = ?.
шаг сообщение интервал
0 нет [0,1]
1 В [1/4; 3/4]
2 BA [1/4; 3/8]
3 BAA [1/4; 9/32]
4 BAAB [33/128; 35/128]
5 BAABC [69/256; 35/128]

Задача №7
Составить коды Хаффмена, блочный код Хаффмена (для блоков длины 2 и 3) и арифметический код для сообщения АВАААВ (с относительными частотами повторений из заданного сообщения), вычислить их длины.
ABAAAB, p(A) = 4/6 = 2/3, p(B) = 2/6 = 1/3.
шаг сообщение интервал
0 нет [0;1]
1 A [0;2/3]
2 AB [4/9; 2/3]
3 ABA [4/9; 16/27]
4 ABAA [4/9; 44/81]
5 ABAAA [4/9; 124/243]
6 ABAAAB [356/729; 124/243]

Задача № 8:
Закодировать кодом LZ77 фразу: «Корабли лавировали, лавировали, да не вылавировали», вычислить длину кода.

Задача № 9:
Распаковать сообщение и рассчитать длину кода сжатого сообщения, при словаре – 12 байт; буфере - 4 байта:
< 0,0,A > < 0,0,F > < 0,0,X > < 9,2,F > < 8,1,F > < 6,2,X > < 4,3,A >.

"Промежуточный контроль:
№1. Укажите последовательность шагов при построении префиксного кода методом Хаффмена:
4) Проводим ребра, соединяющие буквы в алфавитах, получаем граф-дерево, помечаем ребра метками из алфавита В = {0, 1}. Прослеживаем метки от корня к концевой вершине и получаем кодовое слово.
2) Две наименее вероятные буквы склеиваем в одну букву редуцированного источника и приписываем этой букве суммарную вероятность склеенных букв.
3) Переходим к первому шагу, если алфавит редуцированного источника состоит из двух или более букв. В противном случае переходим к последнему шагу алгоритма.
1) Буквы источника располагаем в порядке убывания вероятностей.

№2. Выберите правильный ответ
Необходимым и достаточным условием того, чтобы дерево префиксного кода с длинами кодовых слов l1,l2….ln в алфавите мощностью D было полным является:
+:
-:
-:
-:

№3. Выберите правильный ответ
Величина H(k) = / называется
-: энтропией источника на один знак;
+: шаговой энтропией марковского источника порядка k;
-: энтропией эргодического источника.

№4. Расположите двоичные источники без памяти с вероятностью появления 0 Р(0) и вероятностью появления 1 Р(1) в порядке возрастания энтропии, начиная с наименьшей
(2) Р(1) = 0,9; Р(0) = 0,1;
(3) Р(1) = 0,5; Р(0) = 0,5;
(1) Р(1) = 1; Р(0) = 0 ;
№5.Выберите правильный ответ
Величина, вычисляемая по формуле l = , где li – длина кодового слова , называется …
-: коэффициентом сжатия кода;
-: длиной кодового слова;
+: средней длиной кодового слова;
-: кодовым расстоянием.


№6. Впишите цифру:
Источник без памяти можно назвать марковским источником глубины m = …
+: 0
№7. Соответствие типа кода его определению

1)код, в котором длины всех кодовых слов одинаковы - … (1) избыточный код
2) код, в котором ни одно кодовое слово не совпадает с началом другого кодового слова - … (2) префиксный код
3) однозначно декодируемый код, обладающий минимально возможной средней длиной во множестве всех кодов, построенных для каждого источника - … () блоковый код
4) код, в котором длины кодовых слов могут быть различны - … (4) неравномерный код
(3) оптимальный код
№8. Впишите ответ в виде числа с двумя знаками после запятой
Средняя длина кодового двоичного префиксного кода, заданного таблицей
a P(ai) код
a1 0,36 00
a2 0,18 01
a3 0,18 100
a4 0,12 101
a5 0,09 110
a6 0,07 111
составляет … +: 2,46
№9. Впишите фамилию ученого
Фамилия ученого, доказавшего, что последовательности, порожденные марковским источником порядка m, обладают информационной устойчивостью - …
+: Шеннон
№10. Выберите правильный ответ
Величина H(k) = / называется
-: энтропией источника на один знак;
+: шаговой энтропией марковского источника порядка k;
-: энтропией эргодического источника.
№11. Выберите правильный ответ
Кодовая комбинация, соответствующая букве а6 двоичного префиксного кода, заданного кодовым деревом, …
-: 10101
-: 11111
-: 11100
+: 11110
№12. Относительное увеличение длины кодового слова за счет введения в него контрольных символов называется …
-: детерминированностью кода;
-: помехоустойчивостью кода;
-: значностью кода;
+: избыточностью кода.
№13.Выберите правильный ответ
Согласно теорем Шеннона, распределение вероятностей реализаций последовательностей, порождаемых источником без памяти, обладает свойством …
+: информационной устойчивости;
-: информационной безопасности;
-: информационной достоверности.
№14. Расположите вероятности появления нулей Р(0) в выходной последовательности двоичного источника без памяти в порядке возрастания числа высоковероятных последовательностей, начиная с наименьшего
(1)Р(0) = 1/2
(3) Р(0) = 1
(2)0<P(0)<1/2
№15.Выберите верные ответы
Верными являются следующие выражения: …
+: информационная емкость сообщения увеличивается при повышении энтропии источника;
-: энтропия ансамбля равновероятных и взаимонезависимых сообщений равна нулю;
+:бросок игральной кости имеет энтропию больше, чем бросок монеты;
+: энтропия нескольких независимых источников равна сумме энтропий этих источников.
№16. Расположите источники с энтропией Н и нижней границей сжатия q в порядке убывания мощности алфавита кодера, начиная с наибольшей
(1) Н = 8,4 бит, q = 4,2;
(3) Н = 8,4 бит, q = 2,1;
(2) Н = 6,3 бит, q = 2,1.

Тема: Помехоустойчивое кодирование. Циклические коды. Коды БЧХ. Сверточные коды.
Задача №1:
Для линейного кода, имеющего n = 10 символов в кодовой комбинации и , найти:
1) Число проверочных и информационных символов, при условии, что он близок к оптимальному?
2) Составить порождающую и проверочную матрицы, на основе правила формирования проверочных символов.

Тестовые задания:
1) Число искаженных символов в принятой кодовой комбинации называется:
А) избыточностью кода;
+Б) кратностью ошибки;
В) синдромом;
Г) кодовым расстоянием;
2) Соответствие (n - k) кода числу информационных символов:
А)(15;11) a) 11
Б) (15;7) б) 7
В) (7;6) в) 6
3) Выберите правильный ответ:
Кодовое расстояние для пары кодовых комбинаций 1111011110 и 1011000111 равно…
А) 10;
Б) 8;
+В) 4;
Г) 6;
4) Соответствие пар кодовых комбинации кодовому расстоянию между ними:
А)10100011 и 10001110 a) d = 4;
Б) 101000010 и 110101111 б) d = 6;
В) 1000100011 и 0101110010 в) d = 5;
г) d = 3;
5) Соответствие (n - k) кода числу информационных символов:
А)(15;8) a) 8;
Б) (7;4) б) 4;
В) (15;7) в) 7;
г) 3;
6) Соответствие (n - k) кода числу проверочных символов:
А) 5 a) (15;11);
Б) 2 б) (7;2);
В) 5 в) (7;5);
г) (7;4);
7) Соответствие (n - k) кода числу проверочных символов:
А) (7;4); а) 3;
Б) (15;10); б) 5;
В) (15;11); в) 4;
г) 7;

8) Соответствие (n - k) кода числу проверочных символов:
А) (15;8); а) 7;
Б) (7;5); б) 2;
В) (7;3); в) 4;
г) 3;
9) Число информационных символов кода (15;7) равно:
А) 17;
Б) 15;
В) 10;
+Г) 7;
10) Впишите слово.
Мощность двоичного кода (10;8) равна…
Ответ: (256 бит);
11) Соответствие мощности кода М мощности алфавита В, если число информационных символов k = 5:
А) М = 1024; а) В = 4;
Б) М = 243; б) В = 3;
В) М = 32; в) В = 2;
г) В = 5;
12) Соответствие пар кодовых комбинаций кодовому расстоянию между ними…
А)10100010 и 11010111 a) d = 4;
Б) 10101011 и 10101110 б) d = 3;
В) 1010100011и 1101110010 в) d = 5;
г) d = 2;
13) Соответствие кодового расстояния d кратности обнаруживаемых ошибок g:
А) d = 6; а) g ? 3;
Б) d = 7; б) g ? 5;
В) d = 4; в) g ? 6;
Г) d = 5; г) g ? 4;
Д) d = 3;
14) Соответствие (n - k) кода числу проверочных символов:
А) (15;9); а) 6;
Б) (15;11); б) 4;
В) (15;10); в) 5;
Г) (7;4); г) 3;
д) 11;
15) Соответствие (n - k) кода числу проверочных символов:
А) (15;8); а) 7;
Б) (7;3); б) 4;
В) (7;5); в) 2;
г) 5;
"16) Мощность двоичного кода (10;8) равна:
А) 1024;
Б) 64;
+В) 256;
Г) 4;
17) Расположите кодовые комбинации в порядке убывания их веса Хемминга начиная с наибольшего…
1. 1100110011;
2. 0101010101;
3. 0011011000;
18) Расположите ситуации при декодировании систематического кода (7;4) в порядке убывания веса синдрома, начиная с наибольшего:
1. Одиночная ошибка содержится в информационных символах;
2. Одиночная ошибка содержится в проверочных символах;
3. Отсутствие ошибок;
19) Мощность двоичного кода (11;5) равна…
Ответ: 32.
20) Соответствие термина его определению:
А) Вес кода; а) число единиц, содержащихся в сумме кодовых комбинаций по модулю два;
Б) Мощность кода; б)мощность алфавита, возведенная в степень, равную числу информационных символов;
В) Кодовое расстояние; в) число ненулевых символов двоичной кодовой комбинации;
Г) Основание кода;


Тема: Моделирование дискретного канала передачи информации. Характеристики дискретного канала передачи информации.
Задание №1:
Изобразить и пояснить модель двоичного симметричного канала и пояснить формализованные обозначения и ее физический смысл.

Задание №2:
Изобразить схему информационных потоков в канале передачи данных. Пояснить физический смысл формализованных обозначений в схеме.
Записать соотношения энтропий в схеме, выражение для определения количества взаимной информации.

Задание №3:
Записать соотношения между величинами технической, информационной скоростей и пропускной способности канала передачи данных. Пояснить физический смыл этих соотношений.

Задание №4:
Сформулировать Теорему Шеннона для канала без помех. Пояснить физический смысл применения ее на практике.

Задание №5:
Сформулировать Теорему Шеннона для канала с помехами (прямую и обратную). Пояснить физический смысл ее применения на практике.

Задание №6:
Дать определение понятий помехоустойчивости и эффективности канала передачи данных. Пояснить физический смысл соотношений этих понятий и применение их на практике.

Задание №7:
Сформулировать (синтезировать) задачу по анализу пропускной способности и скоростей передачи данных для реальных каналов используемых в домашних условия студента.


"