Контрольная работа по "Эконометрике". 27

Государственное образовательное  учреждение высшего профессионального  образования

"Балтийский институт экономики  и финансов (БИЭФ)"

 

 

 

Кафедра прикладной информатики

 

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

По дисциплине ОСНОВЫ ТЕОРИИ ИНФОРМАЦИИ

 

 

                                                                                                        Шиндяпин Сергей Викторович

                                                                                        Группа/курс  2918/4

                                                                   Вариант 6

                                                                                                          Дата сдачи _______________

                                                                                                          Дата проверки ____________                                                                                     

                                                                                             Профессор Карлов А.М.

 

 

 

 

 

 

 

 

г. Калининград

2011 г.

 

План

 

1. Задача №1………………………………………………………………………………………………………………стр.3
2. Задача №2………………………………………………………………………………………………………………стр.6
3. Задача №3………………………………………………………………………………………………………………стр.9
4. Задача №4………………………………………………………………………………………………………………стр.13
5. Задача №5………………………………………………………………………………………………………………стр.17
6. Задача №6………………………………………………………………………………………………………………стр.22

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задача 1. Энтропия некоррелированного источника дискретных сообщений.

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

Таблица 1

Nвар	xi	x1	x2	x3	x4	x5	x6	x7	x8	x9
6	Pi	0,05	0,149	0,174	0,192	0,16	0,1	0,052	0,033	0,09

 

Решение

Xi	X1	X2	X3	X4	X5	X6	X7	X8	X9
pi	0,05	0,149	0,174	0,192	0,16	0,1	0,052	0,033	0,09
I(xi)	-log20.05	…	…	…	…	…	…	…	-log20.09

 

X_i– элемент источника дискретных сообщений

I(x_i) – количество информации

H(x) – энтропия источника дискретных сообщений

P(x_i) – вероятность появления элемента в сообщении

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

 

Энтропия  источника дискретных сообщений  можно определить по формуле:

 

Где:

L – число элементов источника дискретных сообщений

Получим:

H(x) = (-0.05×log₂0.05) + (-0.149×log₂0.149) + (-0.174×log₂0.174) + (-0.192×log₂0.192) + (-0.16×log₂0.16) + (-0.1×log₂0.1) + (-0.052×log₂0.052) + (-0.033×log₂0.033) + (-0.09×log₂0.09)

Используя свойство логарифмов с×log_аb = log_аb^с запишем:

H(x) = log₂0.05^-0.05 + log₂0.149^-0.149 + log₂0.174^-0.174 + log₂0.192^-0.192 + log₂0.16^-0.16 + log₂0.1^-0.1 + log₂0.052^-0.052 + log₂0.033^-0.033 + log₂0.09^-0.09

H(x) = log₂1.1616 + log₂1.3280 + log₂1.3556 + log₂1.3728 + log₂1.3407 + log₂1.2589 + log₂1.1662 + log₂1.1192 + log₂1.2420

Используя свойство логарифмов log_аb + log_ac = log_a(b×c) запишем:

H(x) = log₂(1.1616 × 1.3280 × 1.3556 × 1.3728 × 1.3407 × 1.2589 × 1.1662 × 1.1192 × 1.2420)

H(x) = log₂7.8545 = 2,974

Для того, чтобы  определить коэффициент избыточности источника сообщения R_изб, определим максимальное значение энтропии по формуле:

H_max = log₂L

H_max = log₂9

H_max = 3.17

Для характеристики алфавита источника сообщений представляет интерес сравнения энтропии H(x) с максимальной при данном алфавите энтропии H_max. По результатам этого сравнения определим коэффициент избыточности источника сообщения R_изб по формуле:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задача 2. Оптимальное  статистическое кодирование.

По  заданному закону распределения  вероятностей дискретного источника  информационных сообщений (табл. 1) провести оптимальное статистическое кодирование  источника сообщений по методу Хаффмена.

Определить  коэффициент избыточности закодированного  источника дискретных информационных сообщений и скорость передачи информации при использовании полученного  кода. При расчете скорости передачи информации длительность элементарной посылки принять равной 5 мксек.

 

Решение

Исходя из своего варианта, будем решать задачу по методу Хаффмена:

Для этого  воспользуемся таблицей 1 задачи №1

Используя код  Хаффмена построим таблицу элементов источника x_i в порядке убывания их вероятностей p_i.

 

 

xi	pi	xi↓	pi↓
X1	0.05	X4	0.192
X2	0.149	X3	0.174
X3	0.174	X5	0.16
X4	0.192	X2	0.149
X5	0.16	X6	0.1
X6	0.1	X9	0.09
X7	0.052	X7	0.052
X8	0.033	X1	0.05
X9	0.09	X8	0.033

 

 

 

 

 

xi↓	pi↓	Код	ni
X4	0.192	11	2
X3	0.174	011	3
X5	0.16	010	3
X2	0.149	001	3
X6	0.1	101	3
X9	0.09	100	3
X7	0.052	0001	4
X1	0.05	00001	5
X8	0.033	00000	5

 

Элементы  алфавита X_i располагаем в порядке убывания их вероятностей. Граф кода Хоффмена начинаем строить с 2-х элементов алфавита, имеющих наименьшие вероятности. Одному из этих элементов алфавита, а именно верхнему, присваиваем «единичный» символ кодовой комбинации, а нижнему – «нулевой» символ. Далее эти два символа объединяем в промежуточный элемент с вероятностью, равной сумме вероятностей исходных элементов. Затем в ансамбле оставшихся элементов алфавита вместе с промежуточными вновь находим два элемента с наименьшими вероятностями и проделываем предыдущую процедуру. Эту процедуру проделываем до тех пор, пока не исчерпаем весь алфавит источника,, то есть, получим промежуточный символ с вероятностью равной единице. Считывание кодовой комбинации осуществляем с конца графа Хоффмена по стрелкам.

Рассчитаем  среднюю длительность кодовой комбинации:

 

 

 

 

 

Найдем коэффициент  избыточности закодированного источника  дискретных информационных сообщений  по формуле:

 

Для расчета  возьмем энтропию дискретных сообщений  H(x) из предыдущей задачи (задача №1):

 

Рассчитаем  скорость передачи информации по формуле:

 

Где:

 

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

По условию задачи нам известна длительность элементарной посылки , значит получим:

Тогда:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задача 3. Инверсное  кодирование.

А) Информационная посылка Хинф в десятичном исчислении совпадает с номером вашего варианта Хинф = Nвар.

1) Записать информационную посылку  Λинф. пятиэлементным двоичным кодом.

2) Записать кодовую комбинацию  инверсного кода Λ, соответствующую Вашей информационной посылке.

В) На приемной стороне принята кодовая  комбинация Λ^* инверсного кода (табл. 2).

1) Проверить, есть ли ошибка в  принятой кодовой комбинации.

2) Если ошибка есть, то исправить  ее и записать Λ^*испр. – исправленную кодовую комбинацию инверсного кода.

3) Записать принятую информационную  посылку Λ^*испр. Сравнить ее с информационной посылкой, полученной в пункте 1 задачи, и сделать выводы.

Таблица 2

Nвар.	λ*1	λ*2	λ*3	λ*4	λ*5	е*1	е*2	е*3	е*4	е*5
6	0	0	1	0	0	0	0	1	1	0

 

Решение

Запишем информационную посылку x_инф в десятичном исчислении в соответствии с вариантом:

Х_инф = 6

Переведем информационную посылку x_инф в двоичный код Λ_инф:

Λ_инф = 0 0 1 1 0

                 λ_i

Запишем принятую кодовую комбинацию:

Λ^* = 0 0 1 0 0   0 0 1 1 0

              λ^*_i              e^*_j

Вычислим значения проверочных символов по следующему алгоритму:

т.к. количество единиц в принятых информационных символах (λ^*_i) нечетное

 

то проверочные символы получаются из информационных путём их инвертирования.

 

Исходя из выше сделанного вывода запишем вторую группу проверочных символов:

e_j^** = 1 1 0 1 1

 

 

Произведем суммирование по модулю два вычисленных e_j^** и принятых e_j^* проверочных символов:

e_j^*     0 0 1 1 0

e_j^**    1 1 0 1 1

         1 1 1 0 1

Получаем  синдром ошибок равный Х = 1 1 1 0 1

т.к. синдром  ошибок Х ≠ 0, то ошибки присутствуют в полученных информационных символах

Для нахождения ошибки в информационной посылке  воспользуемся таблицей 5.4 (УП Основы теории информации, А.М. Карлов, Е.Н. Авдеев, стр. 132)

 

Таблица 5.4

λi	λ1	λ 2	λ 3	λ 4	λ 5
X	0 1 1 1 1	1 0 1 1 1	1 1 0 1 1	1 1 1 0 1	1 1 1 1 0
ej	e1	e 2	e 3	e 4	e 5
X	1 0 0 0 0	0 1 0 0 0	0 0 1 0 0	0 0 0 1 0	0 0 0 0 1

 

Исходя из таблицы 5.4 находим полученный синдром  ошибок Х = 1 1 1 0 1  , следовательно ошибка находится в первом информационном символе информационной посылки (λ₄).

Запишем исправленную кодовую комбинацию инверсного кода:

Λ^*_испр = 0 0 1 1 0     0 0 1 1 0

Запишем принятую информационную посылку и информационную посылку полученную в 1 пункте:

Λ^*_инф = 0 0 1 0 0

Λ_инФ =  0 0 1 1 0

λ^*_испр = 0 0 1 1 0

Вывод: в этом задании использовался инверсный код. По его алгоритму была найдена ошибка, которая в последствии была исправлена. Этот код позволяет исправлять все однократные ошибки, другие ошибки инверсным кодом обнаруживаются. Для этого кода не обнаруживаются только ошибки четной кратности. Из приведенной задачи видно, принятая информационная посылка не соответствует начальной информационной посылки. Но в ходе проверки мы выяснили, где находится ошибка и это видно, если посмотреть исправленную информационную посылку.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задача 4. Код  Хемминга.

А) Информационная посылка Хинф в десятичном исчислении совпадает с номером Вашего варианта Хинф = Nвар.

1) Записать информационную посылку  Λинф. четырехэлементным двоичным кодом.

2) Записать кодовую комбинацию  кода Хемминга Λ, соответствующую Вашей информационной посылке.

В) На приемной стороне принята кодовая  комбинация кода Хемминга Λ^* (табл. 3).

1) Проверить, есть ли ошибка в  принятой кодовой комбинации.

2) Если ошибка есть, то исправить  ее и записать Λ^*испр. – исправленную кодовую комбинацию кода Хемминга.

3) Записать принятую информационную  посылку Λ^*инф. Сравнить ее с информационной посылкой, полученной в п. 1 задачи. Сделать выводы.

Таблица 3

Nвар.	λ*1	λ*2	λ*3	λ*4	е*1	е*2	е*3
6	0	1	1	0	1	1	1

 

Решение

 

Исходя из своего варианта запишем информационную посылку:

Х_инф = 6

 

Далее запишем  информационную посылку четырехэлементным  двоичным кодом:

Λ_инф = 0 1 1 0

Запишем кодовую  комбинацию кода Хемминга, соответствующую  информационной посылке. Для этого  необходимо найти проверочные символы информационной посылки используя формулу

 

 

и таблицу 5.5 (УП Основы теории информации, А.М. Карлов, Е.Н. Авдеев, стр. 134)

Таблица 5.5

λi ej	1	2	3	4
1	0	1	1	1
2	1	0	1	1
3	1	1	0	1

 

 

 

 

Λ =  0 1 1 0     0 1 1

                                                                                        λ_инф          е_j

Запишем полученную принятую комбинацию:

Λ^* = 0 1 1 0     1 1 1

           λ^*_инф        е^*_j

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

 

Получаем:

 

 

 

Произведем  суммирование по модулю для вычисленных  e_j^** и принятых e_j^* проверочных символов:

e_j^*     1 1 1

e_j^**     0 1 1

         1 0 0

Получаем  синдром ошибок Х = 1 0 0.

т.к. синдром  ошибок не равен 0, то делаем вывод, что  в принятой кодовой комбинации присутствуют ошибки.

Для того, чтобы  найти ошибку на приемной стороне  воспользуемся таблицей 5.6 (УП Основы теории информации, А.М. Карлов, Е.Н. Авдеев, стр. 135)

Искаженный символ	λ 1	λ 2	λ 3	λ 4	e1	e2	e3
Значение синдрома Х	0 1 1	1 0 1	1 1 0	1 1 1	1 0 0	0 1 0	0 0 1

 

По значению синдрома Х = 1 0 0, находим ошибку расположенную  в первом проверочном символе  принятой кодовой комбинации.

Запишем исправленную кодовую комбинацию:

Λ^*_испр = 0 1 1 0     0 1 1

Запишем принятую информационную посылку и информационную посылку полученную в 1 пункте:

Λ^*_инф = 0 1 1 0     1 1 1

Λ =       0 1 1 0     0 1 1

Вывод: коды Хэмминга позволяют исправлять, как  минимум, все однократные ошибки. По выше приведенным решением мы нашли  одну ошибка, которые в  последствии  исправили и получили правильную кодовую комбинацию

 

 

 

 

 

 

 

 

 

 

 

 

Задача 5. Неразделимые циклические коды.

А) 1) По информационной посылке Хинф = Nвар. записать информационную посылку четырехэлементным двоичным кодом Λинф.

2) Записать полином Λ(z) неразделимого циклического кода при образующем полиноме

 

3) Записать кодовую комбинацию  полученного семиэлементного неразделимого  циклического кода.

В) На приемной стороне принята кодовая  комбинация Λ^* неразделимого циклического кода (табл. 4).

1) Проверить, есть ли ошибка в  принятой кодовой комбинации.

2) Если ошибка есть, то исправить  ее и записать Λ^*испр. исправленную кодовую комбинацию неразделимого циклического кода.

3) Записать принятую информационную  посылку Λ^*инф. Сравнить ее с информационной посылкой, полученной в пункте А1 задачи. Сделать выводы.

Таблица 4

Nвар.	λ*7	λ*6	λ*5	λ*4	λ*3	λ*2	λ*1
6	0	1	1	1	0	0	0

 

 

Решение

Исходя из своего варианта запишем информационную посылку:

Х_инф = 6

и запишем  ее четырехэлементным двоичным кодом:

Λ_инф = 0 1 1 0

Запишем полином  Λ(z) неразделимого циклического кода при образующем полиноме

G(z) = z³ + z + 1

Для того, чтобы  записать полином неразделимого  циклического кода кодовой комбинации Λ_инф, воспользуемся формулой

 

получим:

 

тогда для  полинома кодовой комбинации неразделимого  циклического кода можно записать:

 

где G(z) – это образующий полином

 

следовательно

Запишем кодовую  комбинацию неразделимого циклического кода:

Λ = 0 1 1 1 0 1 0

Запишем принятую комбинацию:

Λ^* = 0 1 1 1 0 0 0

Для нахождения ошибок для начала запишем принятую комбинацию в виде полинома:

Λ^*(z) = (0 × z⁶) + (1 × z⁵) + (1 × z⁴) + (1 × z³) + (0 × z²) + (0 × z) + (0 × z⁰) = z⁵ + z⁴ + z³

Далее разделим полученный полином на образующий полином, для того, чтобы определить присутствует ли остаток R(z). Если остаток будет, значит произошла ошибка в принятой кодовой комбинации.

 

 

 

  Z⁵ + z⁴ + z³            z³ + z + 1

  Z⁵ + z³ + z²            z² +z

         Z⁴ + z² 

         Z⁴ + z² + z

                z

 

В итоге получили:

R(z) =  z

следовательно произошла ошибка.

Переведем остаток R(z) в двоичную систему:

R = 0 1 0

Для того, чтобы найти ошибку в нужном элементе воспользуемся таблицей ошибок для образующего полинома G(z) = z³ + z + 1

№ искаженного символа i	1	2	3	4	5	6	7
R(z)	1	z	z2	z2 + 1	z2 + z + 1	z + 1	z2 + z
Код остатка	0 0 1	0 1 0	1 0 0	1 0 1	1 1 1	0 1 1	1 1 0

Исходя  из таблицы видно, что ошибка произошла во втором символе.

Запишем исправленную кодовую комбинацию неразделимого  циклического кода:

Λ^*_испр = 0 1 1 1 0 1 0

Проверим  данный результат:

Λ(z) = G(z) × Λ_инф(z)

Λ^*_испр(z) = G(z) × Λ^*_инф(z)

 

  =       z⁵+ z⁴ + z³ + z    z³ + z + 1

                         Z⁵ + z³ + z²          z² + z             

                          z⁴ + z² + z           

                          z⁴ + z² + z                                      

                          0

 

т.к. остался остаток R(z) = 0, то значит исправленная кодовая комбинация верна

Запишем принятую информационную посылку и  информационную посылку полученную в 1 пункте:

Λ^* = 0 1 1 1 0 0 0

Λ_инф = 0 1 1 0

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