По каналу связи передаются сообщения, каждое из которых содержит 16 букв А, 8 букв Б, 4 буквы В и 4 буквы Г (других букв в сообщениях нет). Каждую букву кодируют двоичной последовательностью. При выборе кода учитывались два т...
По каналу связи передаются сообщения, каждое из которых содержит 16 букв А, 8 букв Б, 4 буквы В и 4 буквы Г (других букв в сообщениях нет).
Каждую букву кодируют двоичной последовательностью.
При выборе кода учитывались два требования:
а) ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование);
б) общая длина закодированного сообщения должна быть как можно меньше.
Какой код из приведённых ниже следует выбрать для кодирования букв А, Б, В и Г?
1) А:0, Б:10, В:110, Г:111
2) А:0, Б:10, В:01, Г:11
3) А:1, Б:01, В:011, Г:001
4) А:00, Б:01, В:10, Г:11
И объясните, почему, пожалуйста.
Гость
Ответ(ы) на вопрос:
Гость2) и 3) не подходят, так как нет однозначного декодирования.
Из 1) и 4) код короче в 1)ответе
1) 1*16+2*8+3*4+3*4=56
4)2*16+2*8+2*4+2*4=64
отв. 1
ГостьВ сообщении 16+8+4+4=32 символа. Вероятность появления символа А равна 16/32=1/2, символа Б 8/32=1/4, символов В и Г - 1/8.
Следовательно, для минимизации длины сообщения (условие "б") самым коротким должен быть символ А, несколько длиннее может быть символ Б и самые длинные - символы В и Г. По этой причине вариант 4) с равной длиной кодов не рассматриваем. Далее, достаточно компактными выглядят коды в варианте 2), но А=0 и В=01 нарушают условие "а" (код 0 является началом кода 01). Остаются варианты 1) и 3)
В варианте 1) нарушений условий нет. В варианте 3) код буквы Б 01 является началом кода буквы В 011 и это нарушает условие "а".
Ответ: 1)
Не нашли ответ?
Похожие вопросы