Тема 4. Кодирование и декодирование – условие Фано

4.01 Кодирование буквенной последовательности

Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела кодирование и декодирование – условие фано
Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#5991

Для кодирования букв О, А, Б, Т, Ь решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Закодируйте последовательность букв БОТАТЬ таким способом и результат запишите восьмеричным кодом.

Показать ответ и решение

Для начала представим коды для букв в двоичном виде:

О — 00

А — 01

Б — 10

Т — 11

Ь — 100

Закодируем слово БОТАТЬ — 10001101111002   . Переведем в восьмеричную систему счисления: 1000110111100   =  1|000 |110 |111 |100 =  10674
               2                            8   .

Ответ: 10674

Ошибка.
Попробуйте повторить позже

Задача 2#5992

Для кодирования букв О, А, Б, Т, Ь решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Закодируйте последовательность букв БОТАТЬ таким способом и результат запишите шестнадцатеричным кодом.

Показать ответ и решение

Для начала представим коды для букв в двоичном виде:

О — 00

А — 01

Б — 10

Т — 11

Ь — 100

Закодируем слово БОТАТЬ — 10001101111002   . Переведем в шестнадцатеричную систему счисления: 1000110111100   =  1|0001 |1011|1100 = 11BC
               2                            16   .

Ответ: 11BC

Ошибка.
Попробуйте повторить позже

Задача 3#5993

Для кодирования букв А, К, Е, Т, Р решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Закодируйте последовательность букв РАКЕТА таким способом и результат запишите шестнадцатеричным кодом.

Показать ответ и решение

Для начала представим коды для букв в двоичном виде:

А — 00

К — 01

Е — 10

Т — 11

Р — 100

Закодируем слово РАКЕТА — 10000011011002   . Переведем в восьмеричную систему счисления: 1000001101100   =  1|0000 |0110|1100 = 106C
               2                           16   .

Ответ: 106C

Ошибка.
Попробуйте повторить позже

Задача 4#6444

Для 6 букв латинского алфавита заданы их двоичные коды (для некоторых букв — из двух бит, для некоторых — из трех). Эти коды представлены в таблице:

     |   |     |   |   |
  a  | b | c   |d  |e  | f
-----|---|-----|---|---|-----
 101 |01 |000  |00 |11 |100

Какой набор букв закодирован двоичной строкой 101000110100100? Буквы не могут повторяться.

Показать ответ и решение

Из таблицы видно, что в данной ситуации не выполнены условие Фано (кодовое слово любой буквы не является началом кодового слова другой) и обратное условие Фано (кодовое слово любой буквы не является концом кодового слова другой), поэтому код нельзя раскодировать однозначно.

Разбиваем двоичную строку на части (слева направо) с помощью данной в условии таблицы (получим 2 возможных случая):

(1) 101|000|11|01|00|100

(2) 101|00|01|101|00|100

Во (2) случае мы видим повторение кодовых слов 00 и 101. Значит, случай (2) не подходит (т.к. по условию буквы не могут повторяться).

Значит, наш ответ – (1) случай. Перепишем его, заменяя кодовые слова на буквы: 101|000|11|01|00|100 = acebdf.

Ответ: acebdf

Ошибка.
Попробуйте повторить позже

Задача 5#6693

Для кодирования букв Ш, К, О, Л, В решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (если двоичная запись числа занимает 1 символ, к нему слева дописывается 1 незначащий ноль). Закодируйте последовательность букв ШКОЛКОВО таким способом и результат запишите восьмеричным кодом (без незначащих нулей).

Показать ответ и решение

Для начала представим коды для букв в двоичном виде:

Ш — 00

К — 01

О — 10

Л — 11

В — 100

Закодируем слово ШКОЛКОВО — 000110110110100102   . Переведем в восьмеричную систему счисления: 00011011011010010    = 00|011|011|011|010|010 = 33322
                   2                                  8   .

Ответ: 33322

Ошибка.
Попробуйте повторить позже

Задача 6#6694

Для кодирования букв Ш, К, О, Л, В решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (если двоичная запись числа занимает 1 символ, к нему слева дописывается 1 незначащий ноль). Закодируйте последовательность букв ШКОЛКОВО таким способом и результат запишите шестнадцатеричным кодом (без незначащих нулей).

Показать ответ и решение

Для начала представим коды для букв в двоичном виде:

Ш — 00

К — 01

О — 10

Л — 11

В — 100

Закодируем слово ШКОЛКОВО — 000110110110100102   . Переведем в шестнадцатеричную систему счисления: 00011011011010010    = 0|0011|0110|1101|0010 =  36D2
                   2                                 16

Ответ: 36D2

Ошибка.
Попробуйте повторить позже

Задача 7#6695

Для кодирования букв О, Э, В, Р, Ж решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Закодируйте последовательность букв РОЖЭВЭ таким способом и результат запишите шестнадцатеричным кодом.

Показать ответ и решение

Для начала представим коды для букв в двоичном виде:

О — 00

Э — 01

В — 10

Р — 11

Ж — 100

Закодируем слово РОЖЭВЭ — 11001000110012   . Переведем в шестнадцатеричную систему счисления: 1100100011001   = 1 |1001 |0001 |1001  = 1919
               2                          16   .

Ответ: 1919

Ошибка.
Попробуйте повторить позже

Задача 8#6696

Для кодирования букв О, Э, В, Р, Ж решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Закодируйте последовательность букв РОЖЭВЭ таким способом и результат запишите восьмеричным кодом.

Показать ответ и решение

Для начала представим коды для букв в двоичном виде:

О — 00

Э — 01

В — 10

Р — 11

Ж — 100

Закодируем слово РОЖЭВЭ — 11001000110012   . Переведем в восьмеричную систему счисления: 1100100011001   =  1|100 |100 |011 |001 =  14431
               2                            8   .

Ответ: 14431

Ошибка.
Попробуйте повторить позже

Задача 9#6697

Для кодирования букв А, К, Е, Т, Р решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Закодируйте последовательность букв РАКЕТА таким способом и результат запишите восьмеричным кодом.

Показать ответ и решение

Для начала представим коды для букв в двоичном виде:

А — 00

К — 01

Е — 10

Т — 11

Р — 100

Закодируем слово РАКЕТА — 10000011011002   . Переведем в восьмеричную систему счисления: 1000001101100   =  1|000 |001 |101 |100 =  10154
               2                            8   .

Ответ: 10154

Ошибка.
Попробуйте повторить позже

Задача 10#25575

Все заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, в котором никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Известно, что слову КАША соответствует код 011011010. Какое наименьшее количество двоичных знаков может содержать сообщение, кодирующее слово ОСОКА?

Показать ответ и решение

Начнем с расшифровку кодового слова с конца. Букве А не может соответствовать код 0, так как в начале слова есть 0, а в начале должна стоять буква К. 10 подходящий код, но стоит проверить дальше. 010 не может соответствовать А, так как в слове больше нет 010, а буквы А две в слове, 1010 не может по тем же причинам. Далее проверять нет смысла, так как с кодами длиннее мы не уместим вторую букву А. Значит, А - 10. Если перебрать варианты, получается, что 01 10 110 10 единственный подходящий порядок. Выходит, К - 01, А - 10, Ш - 110. Если перерисовать это в дерево, получим, что веточка 00 не занята, буква О встречается два раза, поэтому за 00 подвесим О. Остается разветвить 111 и за 1110 подвесить С. Минимальная длина выходит 12.

Ответ: 12

Ошибка.
Попробуйте повторить позже

Задача 11#30054

Доктор Пескоедус кодирует фамилии пациентов неравномерным двоичным кодом, который удовлетворяет условию Фано. Для букв НОГЬ он использовал трехразрядное двоичное представление чисел 3, 4, 5, 6. Закодируйте слово ОГОНЬ таким образом и результат запишите в ответ.

Примечание. Прямое условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Показать ответ и решение

По условию, букве Н соответствует кодовое слово 011, О - 100, Г - 101, Ь - 110. Тогда несложно записать слово ОГОНЬ как 100101100011110  .

Ответ: 100101100011110

Ошибка.
Попробуйте повторить позже

Задача 12#30055

Машина дикая бешеная совсем взбесилась и закодировала заглавные буквы русского алфавита неравномерным двоичным кодом, удовлетворяющим условию Фано. Он вспомнил, что у всех кодовых слов длина больше 2  символов, но при том минимально возможная. Слову ОБМАН соответствует код 111101011000001  . Помогите машине дикой бешеной найти код для слова БОМБА.

Примечание. Прямое условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Показать ответ и решение

Так как длина каждого кодового слова не меньше 2  символов и минимальна, а букв 5  , то можно сделать вывод, что длина каждого кодового слова равна 3  . Разобьём код слова ОБМАН на тройки справа налево: 111 101 011 000 001  . Таким образом, букве О соответствует код 111  , Б — 101  , М — 011  , А — 000  , Н — 001  . Тогда нетрудно записать код слова БОМБА, используя полученные выше коды.

Получаем ответ: 101111011101000

Ответ: 101111011101000

Ошибка.
Попробуйте повторить позже

Задача 13#49354

Для кодирования букв Z  , X  , C  , G  используются трехразрядные последовательные двоичные числа, начинающиеся с 1 (от 100 до 111 соответственно). Закодируйте таким образом последовательность символов CGZX  и запишите результат в шестнадцатеричном коде.

Показать ответ и решение

Присвоим каждой букве свой код для кодирования: Z − 100,X − 101,C − 110,G − 111  .

Тогда последовательность CGZX  кодируется как: 1101111001012  .

Разобьем последовательность на четверки справа. Получим, что 01012 = 516,11102 = E16,11012 = D16  . Получаем ответ: DE5

Ответ: de5

Ошибка.
Попробуйте повторить позже

Задача 14#50669

Для кодирования букв А, Б, В, Г решили использовать двухразрядные последовательные двоичные числа (от 00 до 11, соответственно). Закодируйте таким образом последовательность символов ББГА и запишите полученное двоичное число в шестнадцатеричной системе счисления.

Показать ответ и решение

Закодируем двоичным кодом каждую букву:

А — 00

Б — 01

В — 10

Г — 11

Закодируем последовательность букв ББГА, используя кодировку букв:

Б  Б   Г   А

01 01 11 00

Получаем 010111002  ; после перевода в шестнадцатеричную сс получим 5C.

Ответ: 5C

Ошибка.
Попробуйте повторить позже

Задача 15#55054

Для кодирования букв A , B , C , D , E , F , G , H было решено использовать трехразрядные последовательные двоичные числа (от 000 до 111). Закодируйте последовательность символов EDFGBBAC и запишите полученное двоичное число в восьмеричной системе счисления. Систему счисления в ответе указывать не нужно.

Показать ответ и решение

Закодируем двоичным кодом каждую букву:

А – 000, B – 001, C – 010, D – 011, E – 100, F – 101, G – 110, H – 111

Закодируем последовательность символов EDFGBBAC, используя кодировку букв.

Получим 100011101110001001000010.

После перевода в восьмеричную систему счисления получим, что 1000111011100010010000102 = 435611028  .

Ответ: 43561102

Ошибка.
Попробуйте повторить позже

Задача 16#56433

Для кодирования букв А, Л, Р, И решили использовать двоичное представление чисел 0, 1, 2, 3 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Закодируйте последовательность букв ЛИРА таким способом и результат запишите десятичным кодом.

Показать ответ и решение

Представим числа из десятичной системы счисления в двоичную.

A Л Р И
0 1 2 3
00 01 10 11

Последовательности букв ЛИРА будет выглядеть следующим образом в 2сс: 01111000
       2  или же 120 в десятичной.

Ответ: 120

Ошибка.
Попробуйте повторить позже

Задача 17#56951

По каналу связи передаются сообщения, содержащие только восемь букв: А, В, Е, З, И, Н, О, Р. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 101, В — 010, И — 00. Какое наименьшее количество двоичных знаков потребуется для кодирования слова НЕВЕЗЕНИЕ?

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Показать ответ и решение

Буква Е повторяется в слове НЕВЕЗЕНИЕ чаще всего, поэтому закодируем её кодовым словом 11. Вторая самая встречаемая буква — это Н, поэтому её закодируем словом 011. З — 1000, буквы О и Р тоже необходимо закодировать несмотря на то, что в самом слове они не используются, поэтому им выделим слова 10011 и 10010 соответственно. Тогда количество двоичных знаков, которые потребуются для слова НЕВЕЗЕНИЕ равно 3 + 2+ 3+ 2+ 4 + 2+ 3+ 2 +2 = 23  .

Ответ: 23

Ошибка.
Попробуйте повторить позже

Задача 18#59327

Для кодирования букв Н, А, В, О, Р решили использовать двоичное представление чисел 0, 1, 2, 3, 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Закодируйте последовательность букв ВОРНАВАР таким способом и результат запишите шестнадцатеричным кодом.

Показать ответ и решение

Закодируем четверичным кодом каждую букву:

Н — 00

А — 01

В — 10

О — 11

Р — 100

Закодируем последовательность букв ВОРНАВАР, используя кодировку букв:

В  О  Р  Н  А  В  А  Р

10 11 100 00 01 10 01 100

Получаем 1011100000110011002  ; Переведем данное число в десятичную сс, а затем в 16-ную сс:

1011100000110011002 = 18862010 = 2E0CC16  .

Ответ: 2E0CC

Ошибка.
Попробуйте повторить позже

Задача 19#62477

Сёма кодирует слова. Для кодирования букв Д, Н, Й, А, Л, Е он решил использовать двоичное представление чисел 0, 1, 2, 3, 4, 5 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Сёма закодировал слово ДЕДЛАЙН и записал результат шестнадцатеричным кодом. Запишите, что получилось у Сёмы.

Показать ответ и решение

В двоичном представлении буквы равны: Д - 00, Н - 01, Й - 10, А, 11, Л - 100, Е - 101. Тогда, слово ДЕДЛАЙН кодируется как 0010100100111001. Теперь разобьем это представление на четверки: 0010− 1001− 0011− 10012 = 293916  .

Ответ: 2939
Рулетка
Вы можете получить скидку в рулетке!