Файл: Выясните, какие из представленных ниже кодов, является префиксными.docx

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 01.12.2023

Просмотров: 52

Скачиваний: 1

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

  1. Выясните, какие из представленных ниже кодов, является префиксными:
{01, 101, 110, 1, 10}{11, 001, 101, 1001, 110}{ 10, 01, 110, 111}{01, 101, 110, 111}{11, 01, 011, 111}{01, 110, 001, 111}Ответ: префиксными кодами являются:{01, 101, 110, 1, 10}{10, 01, 110, 111}{01, 101, 110, 111}{01, 110, 001, 111}

  1. Дискретная случайная величина X, задана распределением:

Х
1
2
3
4
5
6
7
8

Р
0,15
0,2
0,1
0,15
0,1
0,05
0,2
0,05
Найти энтропию. Ответ:H(X) = - (0,15 * log2(0,15) + 0,2 * log2(0,2) + 0,1 * log2(0,1) + 0,15 * log2(0,15) + 0,1 * log2(0,1) + 0,05 * log2(0,05) + 0,2 * log2(0,2) + 0,05 * log2(0,05))H(X) ≈ - (0,15 * (-3,16993) + 0,2 * (-2,32193) + 0,1 * (-3,32193) + 0,15 * (-3,16993) + 0,1 * (-3,32193) + 0,05 * (-4,32193) + 0,2 * (-2,32193) + 0,05 * (-4,32193))H(X) ≈ 0,55354 + 0,46439 + 0,33219 + 0,47549 + 0,33219 + 0,21610 + 0,46439 + 0,21610H(X) ≈ 2,25449Энтропия дискретной случайной величины X составляет примерно 2,25449.

  1. Определить энтропию, приходящуюся в среднем на одну букву и на одно двухбуквенное сочетание, количество информации, которое несёт в себе сообщение о получении первой буквы относительно второй. В качестве сообщения использовать Ваше ФИО с пробелами, например: «Иванов Иван Иванович».
Ответ:Сообщение: Лихобабин Василий Васильевич

Буква
Количество
Вероятность

Л

1

1/21

и

3

3/21

х

1

1/21

о

2

2/21

б

2

2/21

а

2

2/21

н

1

1/21

пробел
1

1/21

В

2

2/21

с

2

2/21

л

2

2/21

й

1

1/21

в

1

1/21

е

1

1/21

ч

1

1/21
Расчёт энтропии на основе вероятностей:H(буква) = - ((1/21) * log2(1/21) + (3/21) * log2(3/21) + (1/21) * log2(1/21) + (2/21) * log2(2/21) + (2/21) * log2(2/21) + (2/21) * log2(2/21) + (1/21) * log2(1/21) + (1/21) * log2(1/21) + (2/21) * log2(2/21) + (2/21) * log2(2/21) + (2/21) * log2(2/21) + (1/21) * log2(1/21) + (1/21) * log2(1/21) + (1/21) * log2(1/21) + (1/21) * log2(1/21))H(буква) = - ((1/21) * (-4.39) + (3/21) * (-1.585) + (1/21) * (-4.39) + (2/21) * (-2.585) + (2/21) * (-2.585) + (2/21) * (-2.585) + (1/21) * (-4.39) + (1/21) * (-4.39) + (2/21) * (-2.585) + (2/21) * (-2.585) + (2/21) * (-2.585) + (1/21) * (-4.39) + (1/21) * (-4.39) + (1/21) * (-4.39) + (1/21) * (-4.39)))H(буква) = 0.202 + 0.227 + 0.202 + 0.393 + 0.393 + 0.393 + 0.202 + 0.202 + 0.393 + 0.393 + 0.393 + 0.202 + 0.202 + 0.202 + 0.202H(буква) = 4.629"Лихобабин Василий Васильевич" энтропия, приходящаяся в среднем на одну букву в сообщении составляет примерно 4.629 бит.

Буквы

Количество

Вероятность

Л и х

1

1/21

и х

1

1/21

х о

1

1/21

о б

2

2/21

б а

1

1/21

а б

1

1/21

б и

1

1/21

и н

1

1/21

н

1

1/21

В а

1

1/21

а с

1

1/21

с и

1

1/21

и л

1

1/21

л и

1

1/21

и й

1

1/21

й

1

1/21

В а

1

1/21

а с

1

1/21

с и

1

1/21

и л

1

1/21

л ь

1
1/21
H(пара) = - ((1/21) * log2(1/21) + (1/21) * log2(1/21) + (1/21) * log2(1/21) + (2/21) * log2(2/21) + (1/21) * log2(1/21) + (1/21) * log2(1/21) + (1/21) * log2(1/21) + (1/21) * log2(1/21) + (1/21) * log2(1/21) + (1/21) * log2(1/21) + (1/21) * log2(1/21) + (1/21) * log2(1/21) + (1/21) * log2(1/21) + (1/21) * log2(1/21) + (1/21) * log2(1/21) + (1/21) * log2(1/21) + (1/21) * log2(1/21) + (1/21) * log2(1/21) + (1/21) * log2(1/21) + (1/21) * log2(1/21))
H(пара) = - ((1/21) * (-4.39) + (1/21) * (-4.39) + (1/21) * (-4.39) + (2/21) * (-2.585) + (1/21) * (-4.39) + (1/21) * (-4.39) + (1/21) * (-4.39) + (1/21) * (-4.39) + (1/21) * (-4.39) + (1/21) * (-4.39) + (1/21) * (-4.39) + (1/21) * (-4.39) + (1/21) * (-4.39) + (1/21) * (-4.39) + (1/21) * (-4.39) + (1/21) * (-4.39) + (1/21) * (-4.39) + (1/21) * (-4.39) + (1/21) * (-4.39) + (1/21) * (-4.39)))H(пара) = 0.202 + 0.202 + 0.202 + 0.393 + 0.202 + 0.202 + 0.202 + 0.202 + 0.202 + 0.202 + 0.202 + 0.202 + 0.202 + 0.202 + 0.202 + 0.202 + 0.202 + 0.202 + 0.202 + 0.202H(пара) = 4.058Энтропия, приходящаяся в среднем на одно двухбуквенное сочетание в сообщении "Лихобабин Василий Васильевич" составляет примерно 4.058 битОтвет:

  1. Вероятности появления символов источника заданы таблицей:

Х
1
2
3
4
5
∑

n
5
4
4
3
3
19

w
5/19
4/19
4/19
3/19
3/19
1
Найти длину кода и информационную избыточность при равномерном кодировании.Ответ:Длина кода для каждого символа:L(1) = log2(1/(5/19))L(2) = log2(1/(4/19))L(3) = log2(1/(4/19))L(4) = log2(1/(3/19))L(5) = log2(1/(3/19))L(1) = log2(19/5)L(2) = log2(19/4)L(3) = log2(19/4)L(4) = log2(19/3)L(5) = log2(19/3)I = (5/19) * L(1) + (4/19) * L(2) + (4/19) * L(3) + (3/19) * L(4) + (3/19) * L(5)I = (5/19) * log2(19/5) + (4/19) * log2(19/4) + (4/19) * log2(19/4) + (3/19) * log2(19/3) + (3/19) * log2(19/3)Длина кодов и информационная избыточность:L(1) ≈ 1.080L(2) ≈ 1.292L(3) ≈ 1.292L(4) ≈ 1.585L(5) ≈ 1.585I ≈ 0.378 Таким образом, длины кодов при равномерном кодировании составляют около 1.080, 1.292, 1.292, 1.585 и 1.585 соответственно, а информационная избыточность составляет примерно 0.378.

  1. Используя частотные таблицы, полученные в задаче №3 и алгоритм Хаффмена, построить кодовые последовательности для букв русского алфавита. Каждый этап алгоритма необходимо подробно расписать.

  1. Используя частотные таблицы, полученные в задаче №3 и алгоритм Шеннона-Фано, построить кодовые последовательности для букв русского алфавита. Каждый этап алгоритма необходимо подробно расписать.

  1. Рассчитать среднюю длину кода для кодов, полученных в задачах №5 и №6. Определить, какой код наиболее эффективен.

  1. Методом взвешенных кодов закодировать и раскодировать сообщение «TEXT 123». TEXT заменить своим именем, 123 – количество букв в Вашем ФИО. Например для Иванов Иван Иванович получим: «IVAN 10» Используемый алфавит:

  • Латинские буквы (A B C D E F G H I J K L M N O P Q R S T U V W X Y Z);

  • цифры (1 2 3 4 5 6 7 8 9 0);

  • знак пробела.
Ответ:Присвоим каждому символу следующие веса:A = 10, B = 11, C = 12, D = 13, E = 14, F = 15, G = 16, H = 17, I = 18, J = 19, K = 20, L = 21, M = 22, N = 23, O = 24, P = 25, Q = 26, R = 27, S = 28, T = 29, U = 30, V = 31, W = 32, X = 33, Y = 34, Z = 35, пробел = 36, 1 = 1, 2 = 2, 3 = 3, 4 = 4, 5 = 5, 6 = 6, 7 = 7, 8 = 8, 9 = 9, 0 = 0.Теперь закодируем сообщение "VASILIY 20" с помощью взвешенных кодов:V = 31 (вес = 6)A = 10 (вес = 5)S = 28 (вес = 4)I = 18 (вес = 3)L = 21 (вес = 2)I = 18 (вес = 1)Y = 34 (вес = 0)(пробел) = 36 (вес = 0)2 = 2 (вес = 0)0 = 0 (вес = 0)Вычисление суммы взвешенных значений символов:316 + 105 + 284 + 183 + 212 + 181 + 340 + 360 + 20 + 00 = 186Контрольный символ (КС):КС = (37 - (186 % 37)) % 37КС = (37 - 22) % 37КС = 15Закодированное сообщение "VASILIY 20" будет выглядеть как "V6A5S4I3L2I1Y0P".Раскодирование сообщенияV = 31 (вес = 6)6 = 6 (вес = 5)A = 10 (вес = 4)5 = 5 (вес = 3)S = 28 (вес = 2)4 = 4 (вес = 1)I = 18 (вес = 0)3 = 3 (вес = 0)L = 21 (вес = 0)2 = 2 (вес = 0)I = 18 (вес = 0)1 = 1 (вес = 0)Y = 34 (вес = 0)0 = 0 (вес = 0)P = 25 (вес = 0)Вычислим сумму взвешенных значений символов:316 + 65 + 104 + 53 + 282 + 41 + 180 + 30 + 210 + 20 + 180 + 10 + 340 + 00 + 25*0 = 666Проверим остаток от деления суммы на 37:666 % 37 = 15

  1. Методом Хемминга была закодировано некоторая комбинация α. После передачи по каналу связи было получено сообщение, содержащее комбинацию β =1100010. Необходимо проверить, есть ли ошибка в полученном сообщении и, при необходимости, исправить ее. Для решения использовать проверочную матрицу H и порождающую матрицу G:
, Ответ:β = 1100010H^T = (1 1 1)(0 1 0)(1 0 1)(0 1 1)(1 0 0)(0 1 0)(0 0 1)Выполним операцию умножения по модулю 2:синдром = β * H^T = (1 1 1 0 1 0 0) * (1 1 1) = (0 0 0)Полученный синдром ошибки равен нулевому вектору (синдром = 000), что означает, что ошибки в полученном сообщении β нет.Исправление ошибки (если была бы обнаружена):В случае, если синдром ошибки не равен нулевому вектору, мы могли бы определить позицию ошибки, сравнивая синдром ошибки со столбцами проверочной матрицы H. Затем мы могли бы инвертировать бит в этой позиции в полученном сообщении β для исправления ошибки. Однако, поскольку синдром равен нулю, исправление ошибки не требуется.
Таким образом, в полученном сообщении β = 1100010 ошибок нет и оно может быть рассматриваться как корректное.

  1. Методом Хемминга закодировать комбинацию α=0110, построить порождающую проверочную матрицу. Внести ошибку в один из разрядов кодового вектора, найти синдром, найти и исправить ошибку.
, α = 0110G = (1 0 0 0 1 1 1)(0 1 0 0 1 1 0)(0 0 1 0 1 0 1)(0 0 0 1 0 1 1)β = α * G = (0 1 1 0 0 0 0)Таким образом, полученный кодовый вектор β равен 0110000.Внесение ошибки:Изменяем один из разрядов кодового вектора, чтобы создать ошибку.Допустим, мы внесли ошибку, инвертируя третий разряд кодового вектора β. Тогда новый кодовый вектор β' будет:β' = 0100000Нахождение синдрома:Умножаем полученный кодовый вектор β' на проверочную матрицу H, используя операцию умножения по модулю 2 (XOR), для вычисления синдрома ошибки.Синдром ошибки вычисляется следующим образом: синдром = β' * H^T, где H^T - транспонированная матрица H.Выполним необходимые вычисления:H^T = (1 1 1)(0 1 0)(1 0 1)(0 1 1)(1 0 0)(0 1 0)(0 0 1)синдром = β' * H^T = (0 1 0 0 0 0 0) * (1 1 1) = (1 1 1)Полученный синдром ошибки равен (1 1 1).Исправление ошибки:Сравниваем синдром ошибки со столбцами проверочной матрицы H, чтобы определить позицию ошибки.Инвертируем бит в позиции ошибки в кодовом векторе β' для исправления ошибки.В данном случае, синдром ошибки (1 1 1) указывает на третью позицию ошибки в проверочной матрице H. Мы инвертируем бит в третьей позиции кодового вектора β':Исправленный кодовый вектор β'' будет:β'' = 0110000Таким образом, исправленный кодовый вектор β'' равен 0110000.Кодовый вектор β'' снова стал исходной комбинацией α=0110, что указывает на успешное исправление ошибки.

Смотрите также файлы