Question

Срочно нужна помощь! По каналу связи передаются сообщения, каждое из которых содержит 10 букв А, 5 букв Б, 20 букв В и 5 букв Г (других букв в сообщениях нет). Каждую букву кодируют двоичной последовательностью. При выборе кода учитывались два требования: а) ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование); б) общая длина закодированного сообщения должна быть как можно меньше. Какой код из приведённых ниже следует выбрать для кодирования букв А, Б, В и Г? 1) А:1, Б:01, В:001, Г:111 2) А:00, Б:01, В:10, Г:11 3) А:0, Б:10, В:11, Г:111 4) А:10, Б:111, В:0, Г:110

Answer 1

Если нужно выбрать из вариантов, достаточно проверить, что код префиксный и найти общую длину сообщения в каждом случае.

1) ✔ префиксный
длина А: 1, длина Б: 2, длина В: 3, длина Г: 3
Длина сообщения: 10 * 1 + 5 * 2 + 20 * 3 + 5 * 3 = 10 + 10 + 60 + 15 = 95 бит

2) ✔ префиксный
длины кодовых слов: 2
Длина сообщения: (10 + 5 + 20 + 5) * 2 = 40 * 2 = 80 бит

3) ✘ не префиксный (11 - префикс 111)

4) ✔ префиксный
длина А: 2, длина Б: 3, длина В: 1, длина Г: 3
Длина сообщения: 10 * 2 + 5 * 3 + 20 * 1 + 5 * 3 = 20 + 15 + 20 + 15 = 70 бит

Наиболее оптимальный код 4).

Если бы нужно было бы найти какое-нибудь оптимальное префиксное кодирование, можно было бы построить код Хаффмана.
Выписываем частоты символов, а затем объединяем наименее часто встречающиеся символы, почлучая кодовое дерево.

А - 10, Б - 5, В - 20, Г - 5
А - 10, (БГ) - 10, В - 20
(А(БГ)) - 20, В - 20
(В(А(БГ)) - 40

Если в этой записи есть (XY), то к коду любой буквы из X приписываем слева 0, для любого символа из Y - 1. Начинаем с пустых кодов:
(БГ) -> Б: 0, Г: 1
(А(БГ)) -> А: 0, Б: 10, Г: 11
(В(А(БГ)) -> В: 0, А: 10, Б: 110, Г: 111.

Доказано, что такой код будет оптимальным.

Answer 2

Для выбора кода для кодирования букв А, Б, В и Г, мы должны учесть два требования: 1) Ни одно кодовое слово не должно быть началом другого кодового слова. Это необходимо для однозначного декодирования. 2) Общая длина закодированного сообщения должна быть как можно меньше.

Коды для выбора:

1) А:1, Б:01, В:001, Г:111 2) А:00, Б:01, В:10, Г:11 3) А:0, Б:10, В:11, Г:111 4) А:10, Б:111, В:0, Г:110

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

Вариант 1:

Коды: А:1, Б:01, В:001, Г:111

Проверка требования 1: Нет кодового слова, которое является началом другого кодового слова. Все коды уникальны и не пересекаются.

Проверка требования 2: Общая длина закодированного сообщения будет зависеть от количества каждой буквы в сообщении. Давайте посчитаем общую длину для данного варианта кода: 10 букв А * 1 = 10 5 букв Б * 2 = 10 20 букв В * 3 = 60 5 букв Г * 3 = 15

Общая длина = 10 + 10 + 60 + 15 = 95

Вариант 2:

Коды: А:00, Б:01, В:10, Г:11

Проверка требования 1: Нет кодового слова, которое является началом другого кодового слова. Все коды уникальны и не пересекаются.

Проверка требования 2: Общая длина закодированного сообщения будет зависеть от количества каждой буквы в сообщении. Давайте посчитаем общую длину для данного варианта кода: 10 букв А * 2 = 20 5 букв Б * 2 = 10 20 букв В * 2 = 40 5 букв Г *