укажите каким кодовым словом должна быть закодирована буква д
infoegehelp.ru
Разбор задачи A9 (демо ЕГЭ 2012)
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Использовали код: А–1, Б–000, В–001, Г–011. Укажите, каким кодовым словом должна быть закодирована буква Д. Длина этого кодового слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного декодирования.
При однозначном декодировании в коде одного символа не должно быть дублирования(повторения) части кода другого символа. Т.к. длина кода должна быть наименьшей, то начнем с длины кода =1.
Возможные коды: 0, 1.
«0»-не подходит, т.к. он является частью кода букв: Б,В,Г
«1»-не подходит,т.к. таким кодом закодирована буква А
Возьмем длину кода =2.
Возможные коды: 00,01,10,11
«00»- не подходит, т.к. он является частью кода букв: Б,В
«01»- не подходит, т.к. он является частью кода буквы Г
«10» и «11»- не подходят, т.к. он начинается с «1», а этим кодом закодирована буква А
Возьмем длину кода =3.
Возможные коды: 000,001,010,011,100,101,110,111.
Сразу отбросим коды,которые начинаются с «1»,т.к. этим кодом закодирована буква А.
«000»- не подходит, т.к. таким кодом закодирована буква Б
«001»- не подходит, т.к. таким кодом закодирована буква В
» 010 «- подходит, т.к. таким кодом ничего не закодировано
Укажите каким кодовым словом должна быть закодирована буква д
Тема: Кодирование и декодирование информации.
· кодирование – это перевод информации с одного языка на другой (запись в другой системе символов, в другом алфавите)
· обычно кодированием называют перевод информации с «человеческого» языка на формальный, например, в двоичный код, а декодированием – обратный переход
· один символ исходного сообщения может заменяться одним символом нового кода или несколькими символами, а может быть и наоборот – несколько символов исходного сообщения заменяются одним символом в новом коде (китайские иероглифы обозначают целые слова и понятия)
· кодирование может быть равномерное и неравномерное;
при равномерном кодировании все символы кодируются кодами равной длины;
при неравномерном кодировании разные символы могут кодироваться кодами разной длины, это затрудняет декодирование
· закодированное сообщение можно однозначно декодировать с начала, если выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова;
· закодированное сообщение можно однозначно декодировать с конца, если выполняется обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова;
· условие Фано – это достаточное, но не необходимое условие однозначного декодирования.
Пример задания:
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А–00, Б–010, В–011, Г–101, Д–111. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.
1) для буквы Б – 01 2) это невозможно
3) для буквы В – 01 4) для буквы Г – 01
Решение (1 способ, проверка условий Фано):
1) для однозначного декодирования достаточно, чтобы выполнялось условие Фано или обратное условие Фано;
2) проверяем последовательно варианты 1, 3 и 4; если ни один из них не подойдет, придется выбрать вариант 2 («это невозможно»);
«прямое» условие Фано не выполняется (код буквы Б совпадает с началом кода буквы В);
«обратное» условие Фано не выполняется (код буквы Б совпадает с окончанием кода буквы Г); поэтому этот вариант не подходит ;
«прямое» условие Фано не выполняется (код буквы В совпадает с началом кода буквы Б);
«обратное» условие Фано не выполняется (код буквы В совпадает с окончанием кода буквы Г); поэтому этот вариант не подходит ;
«прямое» условие Фано не выполняется (код буквы Г совпадает с началом кодов букв Б и В); но «обратное» условие Фано выполняется (код буквы Г не совпадает с окончанием кодов остальных буквы); поэтому этот вариант подходит ;
Решение (2 способ, дерево):
1) построим двоичное дерево, в котором от каждого узла отходит две ветки, соответствующие выбору следующей цифры кода – 0 или 1; разместим на этом дереве буквы А, Б, В, Г и Д так, чтобы их код получался как последовательность чисел на рёбрах, составляющих путь от корня до данной буквы (красным цветом выделен код буквы В – 011):
2) здесь однозначность декодирования получается за счёт того, что при движении от корня к любой букве в середине пути не встречается других букв (выполняется условие Фано);
3) теперь проверим варианты ответа: предлагается перенести одну из букв, Б, В или Г, в узел с кодом 01, выделенный синим цветом
4) видим, что при переносе любой из этих букв нарушится условие Фано; например, при переносе буквы Б в синий узел она оказывается на пути от корня до В, и т.д.; это значит, что предлагаемые варианты не позволяют выполнить прямое условие Фано
5) хочется уже выбрать вариант 2 («это невозможно»), но у нас есть еще обратное условие Фано, для которого тоже можно построить аналогичное дерево, в котором движение от корня к букве дает её код с конца (красным цветом выделен код буквы В – 011, записанный с конца):
видно, что обратное условие Фано также выполняется, потому что на пути от корня к любой букве нет других букв
6) в заданных вариантах ответа предлагается переместить букву Б, В или Г в синий узел; понятно, что Б или В туда перемещать нельзя – перемещённая буква отказывается на пути от корня к букве Г; а вот букву Г переместить можно, при этом обратное условие Фано сохранится
Ещё пример задания:
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Использовали код:
А–1, Б–000, В–001, Г–011. Укажите, каким кодовым словом должна быть закодирована буква Д. Длина этого кодового слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного декодирования.
1) 00 2) 01 3)11 4) 010
8) заметим, что для известной части кода выполняется условие Фано – никакое кодовое слово не является началом другого кодового слова
9) если Д = 00, такая кодовая цепочка совпадает с началом Б = 000 и В = 001, невозможно однозначно раскодировать цепочку 000000: это может быть ДДД или ББ; поэтому первый вариант не подходит
10) если Д = 01, такая кодовая цепочка совпадает с началом Г = 011, невозможно однозначно раскодировать цепочку 011: это может быть ДА или Г; поэтому второй вариант тоже не подходит
11) если Д = 11, условие Фано тоже нарушено: кодовое слово А = 1 совпадает с началом кода буквы Д, невозможно однозначно раскодировать цепочку 111: это может быть ДА или ААА; третий вариант не подходит
12) для четвертого варианта, Д = 010, условие Фано не нарушено;
· условие Фано – это достаточное, но не необходимое условие однозначного декодирования, поэтому для уверенности полезно найти для всех «неправильных» вариантов контрпримеры: цепочки, для которых однозначное декодирование невозможно
Еще пример задания:
Для кодирования букв А, Б, В, Г решили использовать двухразрядные последовательные двоичные числа (от 00 до 11, соответственно). Если таким способом закодировать последовательность символов БАВГ и записать результат шестнадцатеричным кодом, то получится
14) из условия коды букв такие: A – 00, Б –01, В – 10 и Г – 11, код равномерный
15) последовательность БАВГ кодируется так: 01 00 10 11 = 1001011
16) разобьем такую запись на тетрады справа налево и каждую тетраду переведем в шестнадцатеричную систему (то есть, сначала в десятичную, а потом заменим все числа от 10 до 15 на буквы A, B, C, D, E, F); получаем
1001011 = 0100 10112 = 4B 16
17) правильный ответ – 1.
· расчет на то, что при переводе тетрад в шестнадцатеричную систему можно забыть заменить большие числа (10–15) на буквы (10112 = 11, получаем неверный ответ 41116)
· может быть дан неверный ответ, в котором нужные цифры поменяли местами (расчет на невнимательность), например, B 416
· в ответах дана последовательность, напоминающая исходную (неверный ответ BACD 16), чтобы сбить случайное угадывание
Еще пример задания:
Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв – из двух бит, для некоторых – из трех). Эти коды представлены в таблице:
Укажите каким кодовым словом должна быть закодирована буква д
Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=1, Б=01, В=001. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?
Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=0, Б=100, В=101. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А–10, Б–001, В–0001, Г–110, Д–111.
Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.
2) для буквы В – 000
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А–011, Б–000, В–11, Г–001, Д–10. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А – 00, Б – 01, В – 100, Г – 101, Д – 110. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В и Г использовали такие кодовые слова: А–111, Б–110, В–100, Г–101.
Укажите, каким кодовым словом может быть закодирована буква Д. Код должен удовлетворять свойству однозначного декодирования. Если можно использовать более одного кодового слова, укажите кратчайшее из них.
Укажите, каким кодовым словом из перечисленных ниже может быть закодирована буква Д. Код должен удовлетворять свойству однозначного декодирования. Если можно использовать более одного кодового слова, укажите кратчайшее из них.
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В и Г использовали такие кодовые слова: А — 001, Б — 010, В— 000, Г — 011.
Укажите, каким кодовым словом из перечисленных ниже может быть закодирована буква Д.
Код должен удовлетворять свойству однозначного декодирования. Если можно использовать более одного кодового слова, укажите кратчайшее из них.
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В и Г использовали такие кодовые слова: А — 111, Б — 110, В — 101, Г — 100.
Укажите, каким кодовым словом из перечисленных ниже может быть закодирована буква Д. Код должен удовлетворять свойству однозначного декодирования. Если можно использовать более одного кодового слова, укажите кратчайшее из них.
По каналу связи передаются сообщения, содержащие только 4 буквы: E, H, O, T. Для кодирования букв E, H, O используются 5-битовые кодовые слова: E — 00000, H — 00111, O — 11011.
Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трех позициях.
Это свойство важно для расшифровки сообщений при наличии помех. Какое из перечисленных ниже кодовых слов можно использовать для буквы T, чтобы указанное свойство выполнялось для всех четырёх кодовых слов?
4) не подходит ни одно из указанных выше слов
По каналу связи передаются сообщения, содержащие только 4 буквы: П, О, Р, T. Для кодирования букв П, О, Р используются 5-битовые кодовые слова: П — 11111, О — 11000, Р — 00100.
Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трех позициях.
Это свойство важно для расшифровки сообщений при наличии помех. Какое из перечисленных ниже кодовых слов можно использовать для буквы T, чтобы указанное свойство выполнялось для всех четырёх кодовых слов?
4) не подходит ни одно из указанных слов
По каналу связи передаются сообщения, содержащие только 4 буквы:
В любом сообщении больше всего букв О, следующая по частоте буква − Е, затем − Н. Буква Т встречается реже, чем любая другая.
Для передачи сообщений нужно использовать неравномерный двоичный код, допускающий однозначное декодирование; при этом сообщения должны быть как можно короче. Шифровальщик может использовать один из перечисленных ниже кодов. Какой код ему следует выбрать?
3) Е−1, Н−01, O−001, Т−000
4) О−0, Н−11, Е−101, Т−100
По каналу связи передаются сообщения, содержащие только 4 буквы:
В любом сообщении больше всего букв А, следующая по частоте буква — С, затем — И. Буква Т встречается реже, чем любая другая.
Для передачи сообщений нужно использовать неравномерный двоичный код, допускающий однозначное декодирование; при этом сообщения должны быть как можно короче. Шифровальщик может использовать один из перечисленных ниже кодов. Какой код ему следует выбрать?
3) А−1, И−01, С−001, Т−000
4) С−0, И−11, А−101, Т−100
По каналу связи передаются сообщения, содержащие только 4 буквы: И, Г, Л, А. Для кодирования букв И, Г, Л используются 6-битовые кодовые слова:
И — 000000, Г — 001110, Л — 110110.
Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее, чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех. Нужно подобрать кодовое слово для буквы А так, чтобы указанное свойство выполнялось для всех четырёх кодовых слов.
Можно ли использовать одно из таких слов: 111110, 111000, 000110?
4) нет, не подходит ни одно из указанных выше слов
По каналу связи передаются сообщения, содержащие только 4 буквы: П, А, Р, К. Для кодирования букв П, А, Р используются 6-битовые кодовые слова:
П — 111111, А — 110001, Р — 001001.
Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее, чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех. Нужно подобрать кодовое слово для буквы К так, чтобы указанное свойство выполнялось для всех четырёх кодовых слов.
Можно ли использовать одно из таких слов: 000001, 111001, 000111?
4) нет, не подходит ни одно из указанных выше слов
По каналу связи передаются сообщения, содержащие только 4 буквы: С, Л, О, Н; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв С, О, Н используются такие кодовые слова: С: 011, О: 00, Н: 11. Укажите такое кодовое слово для буквы Л, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите тот, у которого меньшая длина.
По каналу связи передаются сообщения, содержащие только 4 буквы: А, Т, О, М; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв Т, О, М используются такие кодовые слова: Т: 100, О: 00, М: 11. Укажите такое кодовое слово для буквы А, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите тот, у которого меньшая длина.
По каналу связи передаются сообщения, содержащие только 4 буквы К, О, Р, А; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв Р, А, К используются такие кодовые слова:
Укажите такое кодовое слово для буквы О, при котором код будет допускать однозначное декодирование. Если таких кодовых слов несколько, укажите то, у которого меньшая длина.
По каналу связи передаются сообщения, содержащие только 4 буквы П, О, С, Т; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв Т, О, П используются такие кодовые слова:
Укажите такое кодовое слово для буквы С, при котором код будет допускать однозначное декодирование. Если таких кодовых слов несколько, укажите тот, у которого меньшая длина.
Для кодирования некоторой последовательности, состоящей из букв У, Ч, Е, Н, И и К, используется неравномерный двоичный префиксный код. Вот этот код: У — 000, Ч — 001, Е — 010, Н — 100, И — 011, К — 11. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему остался префиксным? Коды остальных букв меняться не должны.
Выберите правильный вариант ответа.
Примечание. Префиксный код — это код, в котором ни одно кодовое слово не является началом другого; такие коды позволяют однозначно декодировать полученную двоичную последовательность.
1) кодовое слово для буквы Е можно сократить до 01
2) кодовое слово для буквы К можно сократить до 1
3) кодовое слово для буквы Н можно сократить до 10
Для кодирования некоторой последовательности, состоящей из букв У, Ч, Е, Н, И и К, используется неравномерный двоичный префиксный код. Вот этот код: У — 000, Ч — 001, Е — 010, Н — 100, И — 101, К — 11. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему остался префиксным? Коды остальных букв меняться не должны.
Выберите правильный вариант ответа.
Примечание. Префиксный код — это код, в котором ни одно кодовое слово не является началом другого; такие коды позволяют однозначно декодировать полученную двоичную последовательность.
1) кодовое слово для буквы Е можно сократить до 01
2) кодовое слово для буквы К можно сократить до 1
3) кодовое слово для буквы Н можно сократить до 10
Для передачи по каналу связи сообщения, состоящего только из символов А, Б, В и Г, используется неравномерный (по длине) код: А – 0; Б – 100; В – 101. Каким кодовым словом нужно кодировать символ Г, чтобы длина его была минимальной, а код при этом допускал однозначное разбиение кодированного сообщения на символы?
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д и Е, используется неравномерный двоичный префиксный код.
Даны кодовые слова для четырёх букв: А — 011, Б — 010, В — 001, Г — 000. Какие кодовые слова из приведённых ниже вариантов подходят для букв Д и Е? Если подходит более одного варианта, укажите тот, для которого сумма длин кодовых слов меньше.
Примечание. Префиксный код — это код, в котором ни одно кодовое слово не является началом другого; такие коды позволяют однозначно декодировать полученную двоичную последовательность.
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д и Е, используется неравномерный двоичный префиксный код.
Даны кодовые слова для четырёх букв: А — 111, Б — 110, В — 101, Г — 100. Какие кодовые слова из приведённых ниже вариантов подходят для букв Д и Е? Если подходит более одного варианта, укажите тот, в котором сумма длин кодовых слов меньше.
Примечание. Префиксный код — это код, в котором ни одно кодовое слово не является началом другого; такие коды позволяют однозначно декодировать полученную двоичную последовательность.
Для передачи по каналу связи сообщения, состоящего только из символов А, Б, В и Г, используется неравномерный (по длине) код: А — 0; Б — 10; В — 110. Каким кодовым словом нужно кодировать символ Г, чтобы длина его была минимальной, а код при этом допускал однозначное разбиение кодированного сообщения на символы?
Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово 0, для буквы К — кодовое слово 110. Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Л использовали кодовое слово 1, для буквы М — кодовое слово 011. Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
По каналу связи передаются сообщения, каждое из которых содержит 16 букв А, 8 букв Б, 4 буквы В и 4 буквы Г (других букв в сообщениях нет). Каждую букву кодируют двоичной последовательностью. При выборе кода учитывались два требования:
а) ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование);
б) общая длина закодированного сообщения должна быть как можно меньше.
Какой код из приведённых ниже следует выбрать для кодирования букв А, Б, В и Г?
Укажите каким кодовым словом должна быть закодирована буква д
Для 6 букв латинского алфавита заданы их двоичные коды (для некоторых букв из двух бит, для некоторых – из трех). Эти коды представлены в таблице:
Какая последовательность из 6 букв закодирована двоичной строкой 011111000101100?
Мы видим, что условия Фано и обратное условие Фано не выполняются, значит, код можно раскодировать неоднозначно.
Будем пробовать различные варианты:
1) 011 11 100 0101100
Первая буква определяется однозначно, её код 011: D.
Вторая буква также определится однозначно — E.
Пусть третья буква B, тогда следующая начинается с кода 010, но таких букв в таблице нет, значит, предположение не верно.
2) 011 11 10 00 101 100
Третья буква — С, потом — A. Мы хотим получить ещё две буквы, чтобы в сумме их было 6, тогда следующая буква — F, и последняя — B.
Окончательно получили ответ: DECAFB.
Примечание. DECACEA не подходит, так как 7 букв.
так же подходит decacea
011 11 10 00 10 11 00
В задании спрашивается о последовательности из шести букв.
Укажите, каким кодовым словом из перечисленных ниже может быть закодирована буква Д. Код должен удовлетворять свойству однозначного декодирования. Если можно использовать более одного кодового слова, укажите кратчайшее из них.
Для того, чтобы сообщение, записанное с помощью неравномерного по длине кода, однозначно раскодировалось, требуется, чтобы никакой код не был началом другого (более длинного) кода.
Рассмотрим варианты для буквы Д, начиная с самого короткого.
1) Д=10: код буквы Д является началом кода буквы Б=101, поэтому этот вариант не подходит.
2) Д=11: код буквы Д является началом кода буквы В=111, Д=110, поэтому этот вариант не подходит.
3) Д=000: код буквы Д не является началом другого кода, следовательно, это правильный ответ.
4) Д=1111: код буквы Д является началом кода буквы В=111, поэтому этот вариант не подходит.
Правильный ответ указан под номером 3.
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В и Г использовали такие кодовые слова: А — 001, Б — 010, В— 000, Г — 011.
Укажите, каким кодовым словом из перечисленных ниже может быть закодирована буква Д.
Код должен удовлетворять свойству однозначного декодирования. Если можно использовать более одного кодового слова, укажите кратчайшее из них.
Для того, чтобы сообщение, записанное с помощью неравномерного по длине кода, однозначно раскодировалось, требуется, чтобы никакой код не был началом другого (более длинного) кода.
Рассмотрим варианты для буквы Д, начиная с самого короткого.
1) Д=00: код буквы Д является началом кода буквы В=000, поэтому этот вариант не подходит.
2) Д=01: код буквы Д является началом кода буквы Б=010, Г=011, поэтому этот вариант не подходит.
3) Д=101: код буквы Д не является началом другого кода, следовательно, это правильный ответ.
Правильный ответ указан под номером 3.
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В и Г использовали такие кодовые слова: А — 111, Б — 110, В — 101, Г — 100.
Укажите, каким кодовым словом из перечисленных ниже может быть закодирована буква Д. Код должен удовлетворять свойству однозначного декодирования. Если можно использовать более одного кодового слова, укажите кратчайшее из них.
Для того, чтобы сообщение, записанное с помощью неравномерного по длине кода, однозначно раскодировалось, требуется, чтобы никакой код не был началом другого (более длинного) кода. Рассмотрим варианты для буквы Д, начиная с самого короткого.
1) Д=1: код буквы Д является началом всех представленных кодов букв, поэтому этот вариант не подходит.
2) Д=0: код буквы Д не является началом другого кода, поэтому этот вариант подходит.
3) Д=01: код буквы Д не является началом другого кода, поэтому этот вариант подходит.
4) Д=10: код буквы Д является началом кодов букв В и Г, следовательно, этот вариант не подходит.
Таким образом, подходят два варианта: 0 и 01. 0 короче, чем 01.
Правильный ответ указан под номером 2.
Для кодирования некоторой последовательности, состоящей из букв У, Ч, Е, Н, И и К, используется неравномерный двоичный префиксный код. Вот этот код: У — 000, Ч — 001, Е — 010, Н — 100, И — 011, К — 11. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему остался префиксным? Коды остальных букв меняться не должны.
Выберите правильный вариант ответа.
Примечание. Префиксный код — это код, в котором ни одно кодовое слово не является началом другого; такие коды позволяют однозначно декодировать полученную двоичную последовательность.
1) кодовое слово для буквы Е можно сократить до 01
2) кодовое слово для буквы К можно сократить до 1
3) кодовое слово для буквы Н можно сократить до 10
Проверим каждый из вариантов.
Первый вариант. Если использовать для буквы E код 01, то этот код совпадёт с началом кода для буквы И. Этот вариант нам не подходит.
Второй вариант. Если использовать для буквы К код 1, то этот код совпадёт с началом кода для буквы Н. Этот вариант нам не подходит.
Третий вариант. Если использовать для буквы Н код 10, то этот код не совпадёт с началом кода ни для одной из других букв. Этот вариант нам подходит.