Однозначное декодирование егэ по информатике

Всего: 34    1–20 | 21–34

Добавить в вариант

Для кодирования растрового рисунка, напечатанного с использованием шести красок, применили неравномерный двоичный код. Для кодирования цветов используются кодовые слова.

Белый  — 0, Зелёный  — 11111, Фиолетовый  — 11110, Красный  — 1110, Чёрный  — 10. Укажите кратчайшее кодовое слово для кодирования синего цвета, при котором код будет допускать однозначное декодирование.

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

Источник: ЕГЭ по информатике 13.06.2019. Основная волна. Юг-Центр.

По каналу связи передаются сообщения, содержащие только 4 буквы: С, Л, О, Н; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв С, О, Н используются такие кодовые слова: С: 011, О: 00, Н: 11. Укажите такое кодовое слово для буквы Л, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите тот, у которого меньшая длина.

1)  1

2)  10

3)  010

4)  0

По каналу связи передаются сообщения, содержащие только 4 буквы: А, Т, О, М; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв Т, О, М используются такие кодовые слова: Т: 100, О: 00, М: 11. Укажите такое кодовое слово для буквы А, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите тот, у которого меньшая длина.

1)  1

2)  0

3)  01

4)  101

По каналу связи передаются сообщения, содержащие только 4 буквы К, О, Р, А; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв Р, А, К используются такие кодовые слова:

Р: 000, А: 10, К: 01.

Укажите такое кодовое слово для буквы О, при котором код будет допускать однозначное декодирование. Если таких кодовых слов несколько, укажите то, у которого меньшая длина.

1)  1

2)  0

3)  11

4)  001

По каналу связи передаются сообщения, содержащие только 4 буквы П, О, С, Т; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв Т, О, П используются такие кодовые слова:

Т: 111, О: 10, П: 01.

Укажите такое кодовое слово для буквы С, при котором код будет допускать однозначное декодирование. Если таких кодовых слов несколько, укажите тот, у которого меньшая длина.

1)  1

2)  0

3)  00

4)  110

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В и Г использовали такие кодовые слова: А–111, Б–110, В–100, Г–101.

Укажите, каким кодовым словом может быть закодирована буква Д. Код должен удовлетворять свойству однозначного декодирования. Если можно использовать более одного кодового слова, укажите кратчайшее из них.

1)  0

2)  01

3)  00

4)  000

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В и Г использовали такие кодовые слова: А — 100, Б — 101, В — 111, Г — 110.

Укажите, каким кодовым словом из перечисленных ниже может быть закодирована буква Д. Код должен удовлетворять свойству однозначного декодирования. Если можно использовать более одного кодового слова, укажите кратчайшее из них.

1)  10

2)  11

3)  000

4)  1111

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В и Г использовали такие кодовые слова: А  — 001, Б  — 010, В— 000, Г  — 011.

Укажите, каким кодовым словом из перечисленных ниже может быть закодирована буква Д.

Код должен удовлетворять свойству однозначного декодирования. Если можно использовать более одного кодового слова, укажите кратчайшее из них.

1)  00

2)  01

3)  101

4)  0000

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В и Г использовали такие кодовые слова: А  — 111, Б  — 110, В  — 101, Г  — 100.

Укажите, каким кодовым словом из перечисленных ниже может быть закодирована буква Д. Код должен удовлетворять свойству однозначного декодирования. Если можно использовать более одного кодового слова, укажите кратчайшее из них.

1)  1

2)  0

3)  01

4)  10

По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г; для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В используются такие кодовые слова: А  — 0; Б  — 110; В  — 100.

Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Источник: ЕГЭ по информатике 23.03.2016. Досрочная волна

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г использовали соответственно кодовые слова 000, 001, 10, 11. Укажите кратчайшее возможное кодовое слово для буквы Д, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением. Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Источник: Тренировочная работа по ИНФОРМАТИКЕ 11 класс 29 ноября 2016 года Вариант ИН10203

По каналу связи передаются сообщения, содержащие только шесть букв: А, B, C, D, E, F. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано. Для букв A, B, C используются такие кодовые слова: А  — 11, B  — 101, C  — 0. Укажите кодовое слово наименьшей возможной длины, которое можно использовать для буквы F. Если таких слов несколько, укажите то из них, которое соответствует наименьшему возможному двоичному числу. Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. Коды, удовлетворяющие условию Фано, допускают однозначное декодирование

Источник: Тренировочная работа по ИНФОРМАТИКЕ 11 класс 30 сентября 2016 года Вариант ИН10103

По каналу связи передаются сообщения, содержащие только четыре буквы: П, О, С, Т; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв Т, О, П используются такие кодовые слова: Т: 111, О: 0, П: 100.

Укажите кратчайшее кодовое слово для буквы С, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Источник: Демонстрационная версия ЕГЭ—2016 по информатике.

По каналу связи передаются сообщения, содержащие только пять букв: A, B, С, D, E. Для передачи используется двоичный код, допускающий однозначное декодирование. Для букв A, B, C используются такие кодовые слова:

A – 111, B – 0, C – 100.

Укажите кратчайшее кодовое слово для буквы D, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

По каналу связи передаются сообщения, содержащие только пять букв: A, B, С, D, E. Для передачи используется двоичный код, допускающий однозначное декодирование. Для букв A, B, C используются такие кодовые слова: A  — 1, B  — 010, C  — 000.

Укажите кратчайшее кодовое слово для буквы E, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Для кодирования некоторой последовательности, состоящей из букв А, Б, В и Г, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В используются такие кодовые слова: А  — 000, Б  — 1, В  — 011.

Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Для кодирования некоторой последовательности, состоящей из букв А, Б, В и Г, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В используются такие кодовые слова: А  — 010, Б  — 1, В  — 011.

Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г; для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В используются такие кодовые слова: А  — 0; Б  — 110; В  — 101.

Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наибольшим числовым значением.

Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Источник: ЕГЭ — 2018. Досрочная волна. Вариант 2., ЕГЭ — 2018. Досрочная волна. Вариант 1.

По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г; для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв Б, В, Г используются такие кодовые слова: Б  — 101; В  — 110; Г  — 0.

Укажите кратчайшее кодовое слово для буквы А, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наибольшим числовым значением.

Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Источник: ЕГЭ по информатике 2020. Досрочная волна. Вариант 1

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г использовали кодовые слова 100, 101, 00, 01 соответственно. Для двух оставшихся букв  — Д и Е  — коды неизвестны.

Укажите кратчайшее кодовое слово для буквы Д, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Источник: ЕГЭ по информатике 2020. Досрочная волна. Вариант 2

Всего: 34    1–20 | 21–34

Источник

Урок посвящен тому, как решать 4 задание ЕГЭ по информатике

Содержание:

  • Кодирование информации
    • Кодирование и расшифровка сообщений
  • Решение 4 заданий ЕГЭ

Кодирование информации

4-е задание: «Кодирование и декодирование информации»

Уровень сложности

— базовый,

Требуется использование специализированного программного обеспечения

— нет,

Максимальный балл

— 1,

Примерное время выполнения

— 2 минуты.

  
Проверяемые элементы содержания: Умение кодировать и декодировать информацию

До ЕГЭ 2021 года — это было задание № 5 ЕГЭ

Типичные ошибки и рекомендации по их предотвращению:

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

Кроме того, если в задании указано, что несколько букв остались без кодовых слов (как, например, в задании демоварианта), то кодовое слово для указанной буквы должно быть подобрано таким образом, чтобы осталась возможность найти кодовые слова, удовлетворяющие условию Фано, и для других букв. Так, например, если мы букву А закодируем нулём, а букву Б единицей, то букву В мы уже никак не сможем закодировать с соблюдением условия Фано, поэтому длину кодового слова для А или Б следует увеличить»

ФГБНУ «Федеральный институт педагогических измерений»

  • Кодирование — это представление информации в форме, удобной для её хранения, передачи и обработки. Правило преобразования информации к такому представлению называется кодом.
  • Кодирование бывает равномерным и неравномерным:
  • при равномерном кодировании всем символам соответствуют коды одинаковой длины;
  • при неравномерном кодировании разным символам соответствуют коды разной длины, это затрудняет декодирование.

Пример: Зашифруем буквы А, Б, В, Г при помощи двоичного кодирования равномерным кодом и посчитаем количество возможных сообщений:
двоичное кодирование

Таким образом, мы получили равномерный код, т.к. длина каждого кодового слова одинакова для всех кодов (2).

Кодирование и расшифровка сообщений

Декодирование (расшифровка) — это восстановление сообщения из последовательности кодов.

Для решения задач с декодированием, необходимо знать условие Фано:

Условие Фано: ни одно кодовое слово не должно являться началом другого кодового слова (что обеспечивает однозначное декодирование сообщений с начала)

Префиксный код — это код, в котором ни одно кодовое слово не совпадает с началом другого кодового слова. Сообщения при использовании такого кода декодируются однозначно.

  • если сообщение декодируется с конца, то его можно однозначно декодировать, если выполняется обратное условие Фано:

    • Обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова

    Постфиксный код — это код, в котором ни одно кодовое слово не совпадает с концом другого кодового слова. Сообщения при использовании такого кода декодируются однозначно и только с конца.

    постфиксный код

  • условие Фано – это достаточное, но не необходимое условие однозначного декодирования.

Однозначное декодирование обеспечивается:

Однозначное декодирование

Однозначное декодирование

Декодирование

Декодирование

Егифка ©:

решение 4 задания ЕГЭ

Задание демонстрационного варианта 2022 года ФИПИ
Плейлист видеоразборов задания на YouTube:

ЕГЭ 4.1: Для кодирования букв О, В, Д, П, А решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления).

Закодируйте последовательность букв ВОДОПАД таким способом и результат запишите восьмеричным кодом.

✍ Решение:

  • Переведем числа в двоичные коды и поставим их в соответствие нашим буквам:
    • О -> 0 -> 00
В -> 1 -> 01
Д -> 2 -> 10
П -> 3 -> 11
А -> 4 -> 100
  • Теперь закодируем последовательность букв из слова ВОДОПАД:
    • 010010001110010
  • Разобьем результат на группы из трех символов справа налево, чтобы перевести их в восьмеричную систему счисления:
    • 010 010 001 110 010
 ↓   ↓   ↓   ↓   ↓
 2   2   1   6   2

Результат: 22162

Теоретическое решение ЕГЭ данного задания по информатике, видео:
📹 YouTube здесь
📹 Видеорешение на RuTube здесь

Рассмотрим еще разбор 4 задания ЕГЭ:

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

a b c d e
000 110 01 001 10

Какой набор букв закодирован двоичной строкой 1100000100110?

✍ Решение:

  • Во-первых, проверяем условие Фано: никакое кодовое слово не является началом другого кодового слова. Условие верно.

    •  
    ✎ 1 вариант решения:

  • Код разбиваем слева направо согласно данным, представленным в таблице. Затем переведём его в буквы:
    • 110 000 01 001 10
 ↓   ↓   ↓  ↓  ↓
 b   a  c   d  e

Результат: b a c d e.

✎ 2 вариант решения:

    Этот вариант решения 4 задания ЕГЭ более сложен, но тоже верен.

  • Сделаем дерево, согласно кодам в таблице:

    • 1

  • Сопоставим закодированное сообщение с кодами в дереве:
    • 110 000 01 001 10

Результат: b a c d e.

Кроме того, вы можете посмотреть видеорешение этого задания ЕГЭ по информатике (теоретическое решение):

📹 YouTube здесь
📹 Видеорешение на RuTube здесь

Решим следующее 4 задание:

ЕГЭ 4.3:
Для передачи чисел по каналу с помехами используется код проверки четности. Каждая его цифра записывается в двоичном представлении, с добавлением ведущих нулей до длины 4, и к получившейся последовательности дописывается сумма её элементов по модулю 2 (например, если передаём 23, то получим последовательность 0010100110).

Определите, какое число пе­ре­да­ва­лось по ка­на­лу в виде 01100010100100100110.

✍ Решение:

  • Рассмотрим пример из условия задачи:
    • Было 2310
Стало 00101001102
  • Где сами цифры исходного числа (выделим их красным цветом):
    •  0010100110  (0010 - 2, 0011 - 3)
  • Первая добавленная цифра 1 после двоичной двойки — это проверка четности (1 единица в 0010 — значит нечетное), 0 после двоичной тройки — это также проверка нечетности (2 единицы в 0011, значит — четное).
  • Исходя из разбора примера решаем нашу задачу так: поскольку «нужные» нам цифры образуются из групп по 4 числа в каждой плюс одно число на проверку четности, то разобьем закодированное сообщение на группы по 5, и отбросим из каждой группы последний символ:
  • разбиваем по 5:
    • 01100 01010 01001 00110
  • отбрасываем из каждой группы последний символ:
    • 0110 0101 0100 0011
  • Результат переводим в десятичную систему: 
    • 0110 0101 0100 0011
 ↓    ↓     ↓    ↓
 6    5     4    3

Ответ: 6 5 4 3

Вы можете посмотреть видеорешение этого задания ЕГЭ по информатике, теоретическое решение:

📹 YouTube здесь
📹 Видеорешение на RuTube здесь

ЕГЭ 4.4:

Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово 0, для буквы К — кодовое слово 10.

Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?

Подобные задания для тренировки

✍ Решение:

✎

1 вариант решения

основан на логических умозаключениях:

  • Найдём самые короткие возможные кодовые слова для всех букв.
  • Кодовые слова 01 и 00 использовать нельзя, так как тогда нарушается условие Фано (начинаются с 0, а 0 — это Н).
  • Начнем с двухразрядных кодовых слов. Возьмем для буквы Л кодовое слово 11. Тогда для четвёртой буквы нельзя подобрать кодовое слово, не нарушая условие Фано (если потом взять 110 или 111, то они начинаются с 11).
  • Значит, надо использовать трёхзначные кодовые слова. Закодируем буквы Л и М кодовыми словами 110 и 111. Условие Фано соблюдается.
  • Суммарная длина всех четырёх кодовых слов равна:
    • (Н)1 + (К)2 + (Л)3 + (М)3 = 9

✎ 2 вариант решения:

  • Будем использовать дерево. Влево откладываем 0, вправо — 1:

    • разбор задания 4 егэ по информатике

  • Теперь выпишем соответствие каждой буквы ее кодового слова согласно дереву:
    • (Н) -> 0   -> 1 символ
(К) -> 10  -> 2 символа
(Л) -> 110 -> 3 символа
(М) -> 111 -> 3 символа
  • Суммарная длина всех четырёх кодовых слов равна:
    • (Н)1 + (К)2 + (Л)3 + (М)3 = 9

Ответ: 9

4.5:

По каналу связи передаются сообщения, содержащие только 4 буквы: А, Б, В, Г; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв А, Б, В используются такие кодовые слова: 

А: 101010, 
Б: 011011, 
В: 01000

Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Подобные задания для тренировки

✍ Решение:

  • Наименьшие коды могли бы выглядеть, как 0 и 1 (одноразрядные). Но это не удовлетворяло бы условию Фано (А начинается с единицы — 101010, Б начинается с нуля — 011011).
  • Следующим наименьшим кодом было бы двухбуквенное слово 00. Так как оно не является префиксом ни одного из представленных кодовых слов, то Г = 00.

Результат: 00

4.6:

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приемной стороне канала связи. Использовали код: 

А - 01 
Б - 00
В - 11
Г - 100

Укажите, каким кодовым словом должна быть закодирована буква Д. Длина этого кодового слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного декодирования. Если таких кодов несколько, укажите код с наименьшим числовым значением.

✍ Решение:

  • Так как необходимо найти кодовое слово наименьшей длины, воспользуемся деревом. Влево будем откладывать нули, а вправо — единицы:

    • ЕГЭ по информатике 2017 задание ФИПИ вариант 16 решение

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

    • ЕГЭ по информатике 2017 задание ФИПИ вариант 16

  • Перепишем сверху вниз получившееся кодовое слово для Д: 101

Результат: 101

Подробней разбор урока можно посмотреть на видео ЕГЭ по информатике 2017:

📹 YouTube здесь
📹 Видеорешение на RuTube здесь

4.7: Демоверсия ЕГЭ 2018 информатика (ФИПИ):

По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У. Для передачи используется неравномерный двоичный код. Для девяти букв используются кодовые слова.
задание 4 егэ информатика 2018

Укажите кратчайшее кодовое слово для буквы Б, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Подобные задания для тренировки

✍ Решение:

  • Для решения будем использовать дерево. Ветви, соответствующие нулю, будем откладывать влево, единице — вправо.

    • задание 4 егэ по информатике решение

  • При рассмотрении дерева видим, что все ветви «закрыты» листьями, кроме одной ветви — 1100:

    • разбор 4 задания егэ демоверсия 2018

Результат: 1100

Подробное теоретическое решение данного 4 (раньше №5) задания из демоверсии ЕГЭ 2018 года смотрите на видео:

📹 Видеорешение на RuTube здесь

4.8:

По каналу связи передаются шифрованные сообщения, содержащие только четыре букв: А, Б, В, Г; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв А, Б, В используются кодовые слова: 

А: 00011 
Б: 111 
В: 1010

Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

✍ Решение:

  • Для решения будем использовать дерево. Ветви, соответствующие нулю, будем откладывать влево, единице — вправо.
  • Поскольку в задании явно не указано о том, что код должен удовлетворять условию Фано, то дерево нужно построить как с начала (по условию Фано), так и с конца (обратное условие Фано).

    • Дерево по условию Фано (однозначно декодируется с начала):
    0

  • Получившееся числовое значение кодового слова для буквы Г — 01.

    • Дерево по обратному условию Фано (однозначно декодируется с конца):
    0

  • Получившееся числовое значение кодового слова для буквы Г — 00.
  • После сравнения двух кодовых слов (01 и 00), код с наименьшим числовым значением — это 00.

Результат: 00

4.9:

По каналу связи передаются сообщения, содержащие только буквы: А, Е, Д, К, М, Р; для передачи используется двоичный код, удовлетворяющий условию Фано. Известно, что используются следующие коды:

Е – 000
Д – 10
К – 111

Укажите наименьшую возможную длину закодированного сообщения ДЕДМАКАР.
В ответе напишите число – количество бит.

Подобные задания для тренировки

✍ Решение:

  • С помощью дерева отобразим известные коды для букв:

    • Тренировочный вариант №3 решение

  • В результирующем слове — ДЕДМАКАР — вде буквы А. Значит, для получения наименьшей длины необходимо для буквы А выбрать наименьший код в дереве. Учтем это и достроим дерево для остальных трех букв А, М и Р:

    • 00

  • Расположим буквы в порядке их следования в слове и подставим их кодовые слова:
    • Д   Е   Д   М   А   К   А   Р
10 000 10  001 01  111 01  110
  • Посчитаем количество цифр в итоговом коде и получим 20.

Результат: 20

Смотрите виде решения задания:

📹 YouTube здесь
📹 Видеорешение на RuTube здесь

Источник

Привет! Сегодня узнаем, как решать 4 задание из ЕГЭ по информатике нового формата 2021.

Четвёртое задание из ЕГЭ по информатике раскрывает тему кодирование информации. Одним из центральных приёмов при решении задач подобного типа является построение дерева Фано. Рассмотрим на примерах этот метод.

Задача (стандартная)

По каналу связи передаются сообщения, содержащие только шесть букв: А, B, C, D, E, F. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано. Для букв A, B, C используются такие кодовые слова: А — 11, B — 101, C — 0. Укажите кодовое слово наименьшей возможной длины, которое можно использовать для буквы F. Если таких слов несколько, укажите то из них, которое соответствует наименьшему возможному двоичному числу.

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

Решение:

Т.к. код букв должен удовлетворять условию Фано (т.е. однозначно декодироваться), то
расположим буквы, которые уже имеют код (A, B, C), на Дереве Фано.

Дерево Фано для двоичного кодирования начинается с двух направлений, которые означают 0(ноль) и 1(единицу) (цифры двоичного кодирования).

От каждого направления можно также рисовать только два направления: 0(ноль) и 1(единицу) и т.д. Для удобства будем рисовать 1(единицу) только вправо, а 0(ноль) только влево.

Получается структура похожая на дерево!

В конце каждой ветки можно располагать букву, которую мы хотим закодировать, но если мы расположили букву, от этой ветки больше нельзя делать новых ответвлений.

Такой подход позволяет однозначно декодировать сообщение, состоящее из этих букв.

ЕГЭ по информатике - задание 4 (Дерево Фано)

Буква C заблокировала левую ветку, поэтому будем работать с правой частью нашего дерева.

Если мы расположим какую-нибудь букву на оставшуюся ветку (100), то эта ветка заблокируется, и нам некуда будет писать остальные 2 буквы. Поэтому продолжаем ветку (100) дальше.

ЕГЭ по информатике - задание 4 (Дерево Фано решение)

Теперь свободно уже две ветки, а нам нужно закодировать ещё три буквы. Поэтому должны ещё раз продолжить дерево от какой-нибудь ветки.

Но уже видно, что букве F будет правильно присвоить код 1000, т.к. нам в условии сказано, что код буквы F должен соответствовать наименьшему возможному двоичному числу. Как расположить буквы D и E в данной задаче не принципиально.

ЕГЭ по информатике - задание 4 (Дерево Фано окончательное решение)

Ответ: 1000.

Ещё один важный тип задания 4 из ЕГЭ по информатике нового формата 2021.

Задача (стандартная)

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, И, К, Л, С, Ц. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Б — 00, К — 010, Л — 111. Какое наименьшее количество двоичных знаков потребуется для кодирования слова АБСЦИССА?

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

Решение:

Коды букв должны удовлетворять условию Фано. Некоторые буквы уже имеют заданные коды (Б, К, Л). Нам нужно, чтобы слово АБСЦИССА имело как можно меньше двоичных знаков. Заметим, что буква C встречается три раза, а буква A два раза, значит, этим буквам стараемся присвоить как можно меньшую длину!

Отметим на дереве Фано уже известные буквы (Б, К, Л).

ЕГЭ по информатике - задание 4 (стандартная задача Дерево Фано)

У нас осталось 4 (четыре) буквы, а свободных веток 3(три), поэтому мы должны продолжить дерево. но какую ветку продолжить ?

1 вариант

Если продолжить линию 1-0, то получится такая картина :

ЕГЭ по информатике - задание 4 (тренировочная задача Дерево Фано)

Теперь получились 4(четыре) свободные ветки равной длины (3(трём) двоичным символам). Т.к. ветки равной длины, то не важно на какую ветку какую букву расположим.

Посчитаем общую длину слова АБСЦИССА.

ЕГЭ по информатике - задание 4 (тренировочная задача подсчёт длины)

3 + 2 + 3 + 3 + 3 + 3 + 3 + 3 = 23.

2 вариант

Продлим линию 1-1-0 (можно и 0-1-1, не принципиально, т.к. эти ветки имеют одинаковую длину.), то получится:

ЕГЭ по информатике - задание 4 (тренировочная задача дерево фано 2)

С мы присваиваем 1-0, т.к. это буква повторяется в сообщении самое большое количество раз, значит, ей присваиваем самый маленький код, чтобы всё сообщение имело наименьшую длину.

Из этих же соображений букве А присваиваем код из трёх двоичных символов 0-1-1.

Подсчитаем общее количество символов в сообщении.

ЕГЭ по информатике - задание 4 (тренировочная задача подсчёт длины 2)

3 + 2 + 2 + 4 + 4 + 2 + 2 + 3 = 22

Длина получилась меньше, чем в первом варианте. Других вариантов нет, поэтому ответ будет 22.

Ответ: 22.

Задача (не сложная)

Для передачи по каналу связи сообщения, состоящего только из символов А, Б, В и Г, используется неравномерный (по длине) код: А-10, Б-11, В-110, Г-0. Через канал связи передаётся сообщение: ВАГБААГВ. Закодируйте сообщение данным кодом. Полученное двоичное число переведите в восьмеричный вид.

Решение:

В этой задаче ничего не сказано про условие Фано. Здесь уже все буквы закодированы, осталось написать сам код.

Задача сводится к переводу из двоичной системы в восьмеричную систему. На эту тему был урок на моём сайте.

ЕГЭ по информатике - задание 4 (кодирование сообщения)

Ответ: 151646.

На этом всё! Увидимся на следующих занятиях по подготовке к ЕГЭ по информатике.

Этого не знаю. Это просто примерные задачи, которые наиболее часто попадаются в книжках и на сайтах по подготовке к ЕГЭ по информатике.

Здравствуйте, а вот такое задание ПО КАНАЛУ СВЯЗИ ПЕРЕДАЮТСЯ СООБЩЕНИЯ, СОДЕРЖАЩИЕ ТОЛЬКО 4 БУКВЫ : А, Б, В, Г; ДЛЯ ПЕРЕДАЧИ ИСП. ДВОИЧНЫЙ КОД, ДОПУСКАЮЩИЙ ОДНОЗНАЧНОЕ ДЕКОДИРОВАНИЕ. ДЛЯ БУКВ А, Б, В ИСПОЛЬЗУЮТСЯ ТАКИЕ КОДОВЫЕ СЛОВА: А:00011, Б:1001, В: 01100.
УКАЖИТЕ КРАТЧАЙШЕЕ КОДОВОЕ СЛОВО ДЛЯ БУКВЫ Г, ПРИ КОТОРОМ КОД БУДЕТ ДОПУСКАТЬ ОДНОЗНАЧНОЕ ДЕКОДИРОВАНИЕ. ЕСЛИ ТАКИХ КОДОВ НЕСКОЛЬКО, УКАЖИТЕ КОД С НАИМЕНЬШИМ ЧИСЛОВЫМ ЗНАЧЕНИЕМ. В ответе указано число 10. Не могу понять почему. У меня 11.

Здравствуйте, а вот такое задание ПО КАНАЛУ СВЯЗИ ПЕРЕДАЮТСЯ СООБЩЕНИЯ, СОДЕРЖАЩИЕ ТОЛЬКО 4 БУКВЫ : А, Б, В, Г; ДЛЯ ПЕРЕДАЧИ ИСП. ДВОИЧНЫЙ КОД, ДОПУСКАЮЩИЙ ОДНОЗНАЧНОЕ ДЕКОДИРОВАНИЕ. ДЛЯ БУКВ А, Б, В ИСПОЛЬЗУЮТСЯ ТАКИЕ КОДОВЫЕ СЛОВА: А:00011, Б:1001, В: 01100.
УКАЖИТЕ КРАТЧАЙШЕЕ КОДОВОЕ СЛОВО ДЛЯ БУКВЫ Г, ПРИ КОТОРОМ КОД БУДЕТ ДОПУСКАТЬ ОДНОЗНАЧНОЕ ДЕКОДИРОВАНИЕ. ЕСЛИ ТАКИХ КОДОВ НЕСКОЛЬКО, УКАЖИТЕ КОД С НАИМЕНЬШИМ ЧИСЛОВЫМ ЗНАЧЕНИЕМ. В ответе указано число 10. Не могу понять почему. У меня 11.

Ольга Владимировна Сорокина, как я понимаю, суть задания в том, что здесь действует либо прямое, либо обратное условие Фано. (Примечание. Условие Фано означает, что соблюдается одно из двух условий.
Либо никакое кодовое слово не является началом другого кодового слова,
либо никакое кодовое слово не является окончанием другого кодового слова.
Это обеспечивает возможность однозначной расшифровки закодированных
сообщений.)
Поэтому 10 является ответом, так как ни один код для букв не оканчивается на 10 (срабатывает обратное условие Фано)

Источник

Кодирование – это перевод информации, представленной символами первичного алфавита, в последовательность кодов.
Декодирование (операция, обратная кодированию) – перевод кодов в набор символов первичного алфавита.
Кодирование может быть равномерное и неравномерное. При равномерном кодировании каждый символ исходного алфавита заменяется кодом одинаковой длины. При неравномерном кодировании разные символы исходного алфавита могут заменяться кодами разной длины.

Задача 1

Для кодирования букв О, В, Д, П, А решили использовать двоичное представление
чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Если закодировать последовательность букв ВОДОПАД таким способом и результат записать восьмеричным кодом, то получится
1) 22162
2) 1020342
3) 2131453
4) 34017

Решение:
Представим коды указанных букв в дво­ич­ном коде, добавив незначащий нуль для одноразрядных чисел:

О В Д П А
0 1 2 3 4
00 01 10 11 100

Закодируем по­сле­до­ва­тель­ность букв: ВО­ДО­ПАД — 010010001110010.
Разобьём это пред­став­ле­ние на трой­ки спра­ва на­ле­во и пе­ре­ведём каждую тройку в восьмеричное число.
010 010 001 110 010 — 22162.
Пра­виль­ный ответ ука­зан под но­ме­ром 1.
Ответ: 1

Задача 2

Для пе­ре­да­чи по ка­на­лу связи со­об­ще­ния, со­сто­я­ще­го толь­ко из сим­во­лов А, Б, В и Г, ис­поль­зу­ет­ся по­сим­воль­ное ко­ди­ро­ва­ние: А-10, Б-11, В-110, Г-0. Через канал связи пе­ре­даётся со­об­ще­ние: ВАГ­БА­А­ГВ. За­ко­ди­руй­те со­об­ще­ние дан­ным кодом. По­лу­чен­ное дво­ич­ное число пе­ре­ве­ди­те в шест­на­дца­те­рич­ный вид.
1) D3A6
2) 62032206
3) 6A3D
4) CADBAADC

Решение:
За­ко­ди­ру­ем по­сле­до­ва­тель­ность букв: ВАГ­БА­А­ГВ — 1101001110100110. Разобьем это пред­став­ле­ние на четвёрки спра­ва на­ле­во и пе­ре­ведём каждую четверку в шестнадцатеричное число:
1101 0011 1010 01102 = D3A616
Пра­виль­ный ответ ука­зан под но­ме­ром 1.
Ответ: 1

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

a b c d e
100 110 011 01 10

Опре­де­ли­те, какой набор букв за­ко­ди­ро­ван дво­ич­ной стро­кой 1000110110110, если из­вест­но, что все буквы в по­сле­до­ва­тель­но­сти – раз­ные:
1) cbade
2) acdeb
3) acbed
4) bacde

Решение:
Мы видим, что усло­вия Фано и об­рат­ное усло­вие Фано не вы­пол­ня­ют­ся, зна­чит код можно рас­ко­ди­ро­вать не­од­но­знач­но.
Значит, будем перебирать варианты, пока не получим подходящее слово :
1) 100 011 01 10 110
Пер­вая буква опре­де­ля­ет­ся од­но­знач­но, её код 100: a.
Пусть вто­рая буква — с, тогда сле­ду­ю­щая буква — d, потом — e и b.
Такой ва­ри­ант удо­вле­тво­ряет усло­вию, зна­чит, окон­ча­тель­но по­лу­чи­ли ответ: acdeb.
Ответ: 2

Задача 4

Для передачи чисел по каналу с помехами используется код проверки четности. Каждая его цифра записывается в двоичном представлении, с добавлением ведущих нулей до длины 4, и к получившейся последовательности дописывается сумма её элементов по модулю 2 (например, если передаём 23, то получим последовательность 0010100110). Определите, какое число передавалось по каналу в виде 01010100100111100011?
1) 59143 2) 5971 3) 102153 4) 10273

Решение:
При кодировании под саму цифру отводится 4 разряда, и еще один под код проверки четности (т.е. всего под цифру отводится 5 разрядов).
Разобьем заданную последовательность на группы по 5 бит в каждой:
01010, 10010, 01111, 00011.
отбросим пятый (последний) бит в каждой группе:
0101, 1001, 0111, 0001.
это и есть двоичные коды передаваемых чисел:
01012 = 5, 10012 = 9, 01112 = 7, 00012 = 1.
таким образом, были переданы числа 5, 9, 7, 1 или число 5971.
Ответ: 2

Задача 5

По ка­на­лу связи пе­ре­да­ют­ся со­об­ще­ния, со­дер­жа­щие толь­ко 4 буквы — П, О, Р, Т. Для ко­ди­ро­ва­ния букв ис­поль­зу­ют­ся 5-би­то­вые ко­до­вые слова:
П — 11111, О — 11000, Р — 00100, Т — 00011.
Для этого на­бо­ра ко­до­вых слов вы­пол­не­но такое свой­ство: любые два слова из на­бо­ра от­ли­ча­ют­ся не менее чем в трёх по­зи­ци­ях.
Это свой­ство важно для рас­шиф­ров­ки со­об­ще­ний при на­ли­чии помех (в пред­по­ло­же­нии, что пе­ре­да­ва­е­мые биты могут ис­ка­жать­ся, но не про­па­да­ют). За­ко­ди­ро­ван­ное со­об­ще­ние счи­та­ет­ся при­ня­тым кор­рект­но, если его длина крат­на 5 и каж­дая пятёрка от­ли­ча­ет­ся от не­ко­то­ро­го ко­до­во­го слова не более чем в одной по­зи­ции; при этом счи­та­ет­ся, что пятёрка ко­ди­ру­ет со­от­вет­ству­ю­щую букву. На­при­мер, если при­ня­та пя­тер­ка 00000, то счи­та­ет­ся, что пе­ре­да­ва­лась буква Р.

Среди при­ведённых ниже со­об­ще­ний най­ди­те то, ко­то­рое при­ня­то кор­рект­но, и ука­жи­те его рас­шиф­ров­ку (про­бе­лы не­су­ще­ствен­ны).
11011 11100 00011 11000 01110
00111 11100 11110 11000 00000

1) ПОТОП
2) РОТОР
3) ТОПОР
4) ни одно из со­об­ще­ний не при­ня­то кор­рект­но

Решение:
Длина обоих со­об­ще­ний крат­на пяти.
Ана­ли­зи­руя пер­вое со­об­ще­ние «11011 11100 00011 11000 01110», при­хо­дим к вы­во­ду, что оно при­ня­то не­кор­рект­но, по­сколь­ку нет та­ко­го слова, ко­то­рое бы от­ли­ча­лось от слова «01110» толь­ко в одной по­зи­ции.
Рас­смот­рим вто­рое со­об­ще­ние. Учи­ты­вая, что каж­дая пятёрка от­ли­ча­ет­ся от не­ко­то­ро­го ко­до­во­го слова не более чем в одной по­зи­ции, его воз­мож­но рас­шиф­ро­вать толь­ко как «ТОПОР».
Ответ: 3

Задача 6

Для пе­ре­да­чи дан­ных по ка­на­лу связи ис­поль­зу­ет­ся 5-би­то­вый код. Со­об­ще­ние со­дер­жит толь­ко буквы А, Б и В, ко­то­рые ко­ди­ру­ют­ся сле­ду­ю­щи­ми ко­до­вы­ми сло­ва­ми: А — 11010, Б — 10111, В — 01101.
При пе­ре­да­че воз­мож­ны по­ме­хи. Од­на­ко не­ко­то­рые ошиб­ки можно по­пы­тать­ся ис­пра­вить. Любые два из этих трёх ко­до­вых слов от­ли­ча­ют­ся друг от друга не менее чем в трёх по­зи­ци­ях. По­это­му если при пе­ре­да­че слова про­изо­шла ошиб­ка не более чем в одной по­зи­ции, то можно сде­лать обос­но­ван­ное пред­по­ло­же­ние о том, какая буква пе­ре­да­ва­лась. (Го­во­рят, что «код ис­прав­ля­ет одну ошиб­ку».) На­при­мер, если по­лу­че­но ко­до­вое слово 10110, счи­та­ет­ся, что пе­ре­да­ва­лась буква Б. (От­ли­чие от ко­до­во­го слова для Б толь­ко в одной по­зи­ции, для осталь­ных ко­до­вых слов от­ли­чий боль­ше.) Если при­ня­тое ко­до­вое слово от­ли­ча­ет­ся от ко­до­вых слов для букв А, Б, В более чем в одной по­зи­ции, то счи­та­ет­ся, что про­изо­шла ошиб­ка (она обо­зна­ча­ет­ся ‘х’).

По­лу­че­но со­об­ще­ние 11000 11101 10001 11111. Де­ко­ди­руй­те это со­об­ще­ние — вы­бе­ри­те пра­виль­ный ва­ри­ант.

1) АххБ
2) АВхБ
3) хххх
4) АВББ

Решение:
Де­ко­ди­ру­ем каж­дое слово со­об­ще­ния. Пер­вое слово: 11000 от­ли­ча­ет­ся от буквы А толь­ко одной по­зи­ци­ей. Вто­рое слово: 11101 от­ли­ча­ет­ся от буквы В толь­ко одной по­зи­ци­ей. Тре­тье слово: 10001 от­ли­ча­ет­ся от любой буквы более чем одной по­зи­ци­ей. Четвёртое слово: 11111 от­ли­ча­ет­ся от буквы Б толь­ко одной по­зи­ци­ей.
Таким об­ра­зом, ответ: АВхБ.
Ответ: 2

Однозначное декодирование. Условие Фано

Код называется однозначно декодируемым, если любое сообщение, составленное из кодовых слов, можно декодировать единственным способом.
Равномерное кодирование всегда однозначно декодируемо.
Для неравномерных кодов существует следующее достаточное (но не необходимое) условие однозначного декодирования:
Сообщение однозначно декодируемо с начала, если выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова.
Сообщение однозначно декодируемо с конца, если выполняется обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова.

Задача 7

Для пе­ре­да­чи по ка­на­лу связи со­об­ще­ния, со­сто­я­ще­го толь­ко из букв А, Б, В, Г, ре­ши­ли ис­поль­зо­вать не­рав­но­мер­ный по длине код: A=1, Б=01, В=001. Как нужно за­ко­ди­ро­вать букву Г, чтобы длина кода была ми­ни­маль­ной и до­пус­ка­лось од­но­знач­ное раз­би­е­ние ко­ди­ро­ван­но­го со­об­ще­ния на буквы?
1) 0001
2) 000
3) 11
4) 101

Решение:
Для анализа соблюдения условия однозначного декодирования (условия Фано) изобразим коды в виде дерева. Тогда однозначность выполняется, если каждая буква является листом дерева:


Видим, что ближайший от корня дерева свободный лист (т.е. код с минимальной длиной) имеет код 000.
Ответ: 2

Задача 8

Для ко­ди­ро­ва­ния не­ко­то­рой по­сле­до­ва­тель­но­сти, со­сто­я­щей из букв У, Ч, Е, Н, И и К, ис­поль­зу­ет­ся не­рав­но­мер­ный дво­ич­ный пре­фикс­ный код. Вот этот код: У — 000, Ч — 001, Е — 010, Н — 100, И — 011, К — 11. Можно ли со­кра­тить для одной из букв длину ко­до­во­го слова так, чтобы код по-преж­не­му остал­ся пре­фикс­ным? Коды осталь­ных букв ме­нять­ся не долж­ны.
Вы­бе­ри­те пра­виль­ный ва­ри­ант от­ве­та.
При­ме­ча­ние. Пре­фикс­ный код — это код, в ко­то­ром ни одно ко­до­вое слово не яв­ля­ет­ся на­ча­лом дру­го­го; такие коды поз­во­ля­ют од­но­знач­но де­ко­ди­ро­вать по­лу­чен­ную дво­ич­ную по­сле­до­ва­тель­ность.
1) ко­до­вое слово для буквы Е можно со­кра­тить до 01
2) ко­до­вое слово для буквы К можно со­кра­тить до 1
3) ко­до­вое слово для буквы Н можно со­кра­тить до 10
4) это не­воз­мож­но

Решение:
Для анализа соблюдения условия однозначного декодирования (условия Фано) изобразим коды в виде дерева. Тогда однозначность выполняется, если каждая буква является листом дерева:

Легко заметить, что если букву Н перенести в вершину 10, она останется листом. Т.е. ко­до­вое слово для буквы Н можно со­кра­тить до 10.
Пра­виль­ный ответ ука­зан под но­ме­ром 3.
Ответ: 3

Задача 9

Для ко­ди­ро­ва­ния не­ко­то­рой по­сле­до­ва­тель­но­сти, со­сто­я­щей из букв К, Л, М, Н, ре­ши­ли ис­поль­зо­вать не­рав­но­мер­ный дво­ич­ный код, удо­вле­тво­ря­ю­щий усло­вию Фано. Для буквы Н ис­поль­зо­ва­ли ко­до­вое слово 0, для буквы К — ко­до­вое слово 110. Ка­ко­ва наи­мень­шая воз­мож­ная сум­мар­ная длина всех четырёх ко­до­вых слов?
1) 7
2) 8
3) 9
4) 10
При­ме­ча­ние. Усло­вие Фано озна­ча­ет, что ни­ка­кое ко­до­вое слово не яв­ля­ет­ся на­ча­лом дру­го­го ко­до­во­го слова. Это обес­пе­чи­ва­ет воз­мож­ность од­но­знач­ной рас­шиф­ров­ки за­ко­ди­ро­ван­ных со­об­ще­ний.

Решение:
Для анализа соблюдения условия однозначного декодирования (условия Фано) изобразим коды в виде дерева. Тогда однозначность выполняется, если каждая буква является листом дерева:

Легко заметить, что ближайшие от корня свободные листы (т.е. свободные коды с наименьшей длиной) – это 10 и 111. Таким об­ра­зом, наи­мень­шая воз­мож­ная сум­мар­ная длина всех четырёх ко­до­вых слов будет 1 + 3 + 2 + 3 = 9.
Пра­виль­ный ответ ука­зан под но­ме­ром 3.
Ответ: 3

Задача 10

По ка­на­лу связи пе­ре­да­ют­ся со­об­ще­ния, со­дер­жа­щие толь­ко че­ты­ре буквы: П, О, С, Т; для пе­ре­да­чи ис­поль­зу­ет­ся дво­ич­ный код, до­пус­ка­ю­щий од­но­знач­ное де­ко­ди­ро­ва­ние. Для букв Т, О, П ис­поль­зу­ют­ся такие ко­до­вые слова: Т: 111, О: 0, П: 100.
Ука­жи­те крат­чай­шее ко­до­вое слово для буквы С, при ко­то­ром код будет до­пус­кать од­но­знач­ное де­ко­ди­ро­ва­ние. Если таких кодов не­сколь­ко, ука­жи­те код с наи­мень­шим чис­ло­вым зна­че­ни­ем.

Решение:
Для анализа соблюдения условия однозначного декодирования (условия Фано) изобразим коды в виде дерева. Тогда однозначность выполняется, если каждая буква является листом дерева:

Легко заметить, что ближайшие от корня свободные листы (т.е. свободные коды с наименьшей длиной) – это 101 и 110. Наименьшее числовое значение имеет код 101.
Ответ: 101

Благодарим за то, что пользуйтесь нашими материалами.
Информация на странице «6. Задание 4. Кодирование и декодирование информации» подготовлена нашими редакторами специально, чтобы помочь вам в освоении предмета и подготовке к экзаменам.
Чтобы успешно сдать необходимые и поступить в высшее учебное заведение или колледж нужно использовать все инструменты: учеба, контрольные, олимпиады, онлайн-лекции, видеоуроки, сборники заданий.
Также вы можете воспользоваться другими статьями из данного раздела.

Публикация обновлена:
07.03.2023

Источник

За это задание ты можешь получить 1 балл. На решение дается около 3 минут. Уровень сложности: базовый.
Средний процент выполнения: 84.4%
Ответом к заданию 4 по информатике может быть цифра (число) или слово.

Разбор сложных заданий в тг-канале

Задачи для практики

Задача 1

По каналу связи передаются сообщения, каждое из которых содержит 15 букв А, 10 букв Б, 7 букв В и 5 букв Г (других букв в сообщениях нет). Каждую букву кодируют двоичной последовательностью.При выборе кода учитывались два требования: а) ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование); б) общая длина закодированного сообщения должна быть как можно меньше.

Определите, чему равна длина кодового сообщения для кода, удовлетворяющего перечисленным условиям.

Решение

Условие однозначного декодирования (условие Фано) заключается в том, что однозначное декодирование возможно, только если ни одно кодовое слово не является началом другого кодового слова. В данной задаче требуется получить минимальную длину закодированного сообщения, поэтому кодовые слова следует подбирать так, чтобы самая часто встречающаяся буква кодировалась самым коротким кодовым словом. Исходя из этого, можно построить код следующего вида: А – 00, Б – 01, В – 10, Г – 11. Этот код удовлетворяет условию Фано, и длина всего сообщения, закодированного этим кодом, будет равна 15$·$2+10$·$2+7$·$2+5$·$2=74. Для проверки имеет смысл составить ещё один код, удовлетворяющий условию Фано, который мог бы быть оптимальным для некоторых сообщений. Например, рассмотрим такой код: А – 0, Б – 10, В – 110, Г – 111. Тогда длина закодированного сообщения будет 15$·$1+10$·$2+7$·$3+5$·$3=71. Следовательно, такой вариант нас устраивает, данный код является более выгодным, и длина сообщения, закодированного этими кодовыми словами, рана 71.

Ответ: 71

Задача 2

По каналу связи передаются сообщения, каждое из которых содержит 15 букв А, 14 букв Б, 12 букв В и 4 буквы Г (других букв в сообщениях нет). Каждую букву кодируют двоичной последовательностью.При выборе кода учитывались два требования: а) ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование); б) общая длина закодированного сообщения должна быть как можно меньше.

Определите, чему равна длина кодового сообщения для кода, удовлетворяющего перечисленным условиям.

Решение

Условие однозначного декодирования (условие Фано) заключается в том, что однозначное декодирование возможно, только если ни одно кодовое слово не является началом другого кодового слова. В данной задаче требуется получить минимальную длину закодированного сообщения, поэтому кодовые слова следует подбирать так, чтобы самая часто встречающаяся буква кодировалась самым коротким кодовым словом. Исходя из этого, можно построить код следующего вида: А – 00, Б – 01, В – 10, Г – 11. Этот код удовлетворяет условию Фано, и длина всего сообщения, закодированного этим кодом, будет равна 15$·$2+14$·$2+12$·$2+4$·$2=90. Для проверки имеет смысл составить ещё один код, удовлетворяющий условию Фано, который мог бы быть оптимальным для некоторых сообщений. Например, рассмотрим такой код: А – 0, Б – 10, В – 110, Г – 111. Тогда длина закодированного сообщения будет 15$·$1+14$·$2+12$·$3+4$·$3=91. Следовательно, такой вариант нас не устраивает, первый код является более выгодным, и длина сообщения, закодированного этими кодовыми словами, рана 90.

Ответ: 90

Задача 3

По каналу связи передаются сообщения, каждое из которых содержит 20 букв Е, 18 букв И, 16 букв К и 10 букв П (других букв в сообщениях нет). Каждую букву кодируют двоичной последовательностью. При выборе кода учитывались два требования: а) ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование); б) общая длина закодированного сообщения должна быть как можно меньше.

Определите, чему равна длина кодового сообщения для кода, удовлетворяющего перечисленным условиям.

Решение

Условие однозначного декодирования (условие Фано) заключается в том, что однозначное декодирование возможно, только если ни одно кодовое слово не является началом другого кодового слова. В данной задаче требуется получить минимальную длину закодированного сообщения, поэтому кодовые слова следует подбирать так, чтобы самая часто встречающаяся буква кодировалась самым коротким кодовым словом. Исходя из этого, можно построить код следующего вида: Е – 00, И – 01, К – 10, П – 11. Этот код удовлетворяет условию Фано, и длина всего сообщения, закодированного этим кодом, будет равна 20$·$2+18$·$2+16$·$2+10$·$2=128. Для проверки имеет смысл составить ещё один код, удовлетворяющий условию Фано, который мог бы быть оптимальным для некоторых сообщений. Например, рассмотрим такой код: Е – 0, И – 10, К – 110, П – 111. Тогда длина закодированного сообщения будет 20$·$1+18$·$2+16$·$3+10$·$3=134. Следовательно, такой вариант нас не устраивает, первый код является более выгодным, и длина сообщения, закодированного этими кодовыми словами, рана 128.

Ответ: 128

Задача 4

По каналу связи передаются сообщения, каждое из которых содержит 18 букв Е, 10 букв И, 8 букв К и 6 букв П (других букв в сообщениях нет). Каждую букву кодируют двоичной последовательностью.При выборе кода учитывались два требования: а) ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование); б) общая длина закодированного сообщения должна быть как можно меньше.

Определите, чему равна длина кодового сообщения для кода, удовлетворяющего перечисленным условиям.

Решение

Для решения данной задачи рассмотрим дерево, у которого из корня и любой вершины выходят по две ветви. Сопоставим каждой левой ветви 0, а каждой правой — 1. Тогда, проходя от вершины к каждому из листьев (узлов, из которых не выходят ветви) и выписывая последовательность нулей и единиц, соответствующих обходу дерева, получим набор кодовых слов, образующих префиксный код (код, в котором ни одно кодовое слово не является началом другого). Префиксный код является однозначно декодируемым.

По условию задачи в сообщении используются только 4 различные буквы. Следовательно, для построения кодовых слов возможно использование одного из двух деревьев. При использовании других кодовых деревьев длины кодовых слов будут или совпадать с длинами кодовых слов дерева (в этом случае общая длина кодового сообщения так же будет совпадать), или будут больше, и, следовательно, не будут удовлетворять условию наименьшей длины кодового сообщения.

На основе дерева получим кодовые слова 00, 01, 10 и 11. Все слова имеют длину 2. Учитывая количество вхождений каждой из букв в сообщение, получим, что в этом случае длина закодированного сообщения равна 2 · (18 + 10 + 8 + 6) = 84.

На основе дерева получим кодовые слова 0, 01, 110 и 111.

Чтобы общая длина кодового сообщения была наименьшей, следует назначить букве, встречающейся наибольшее число раз, кодовое слово наименьшей длины. Например, Е — 0, И — 01, К — 110 и П — 111.

В этом коде длины кодовых слов для букв Е, И, К и П равны 1, 2, 3 и 3 соответственно. Учитывая количество вхождений каждой из букв в сообщение, получим, что в этом длина закодированного сообщения равна 1 · 18 + 2 · 10 + 3 · 8 + 3 · 6 = 80.

Следовательно, наименьшая длина кодового сообщения, для кода удовлетворяющего условиям задачи, равна 80.

Ответ: 80

Задача 5

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, в котором ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование). Известно, что для двух букв были использованы кодовые слова 10 и 110. Определите наименьшую возможную суммарную длину всех шести кодовых слов.

Решение

Условие однозначного декодирования (условие Фано) заключается в том, что однозначное декодирование возможно, только если ни одно кодовое слово не является началом другого кодового слова. Известны кодовые слова 10 и 110, следовательно, для других кодовых слов мы можем использовать только коды, начинающиеся с 0 или 111. Взять в качестве кодового слова 0 нельзя, т.к. в таком случае невозможно будет найти другие кодовые слова, удовлетворяющие условию Фано для оставшихся сообщений. Таким образом, можем использовать 00, 010, 011, 111. Суммарная длина всех кодовых слов – 16.

Ответ: 16

Задача 6

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, решили использовать неравномерный двоичный код, в котором ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование). Известно, что для двух букв были использованы кодовые слова 10 и 111.

Определите наименьшую возможную суммарную длину всех пяти кодовых слов.

Решение

Условие однозначного декодирования (условие Фано) заключается в том, что однозначное декодирование возможно, только если ни одно кодовое слово не является началом другого кодового слова. Известны кодовые слова 10 и 111, следовательно, для других кодовых слов мы можем использовать только коды, начинающиеся с 0 или 110. Взять в качестве кодового слова 0 нельзя, т.к. в таком случае невозможно будет найти другие кодовые слова, удовлетворяющие условию Фано для оставшихся сообщений. Таким образом, можем использовать 00, 01, 110. Суммарная длина всех кодовых слов – 12.

Ответ: 12

Задача 7

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, решили использовать неравномерный двоичный код, в котором ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование). Известно, что для двух букв были использованы кодовые слова 1 и 010.

Определите наименьшую возможную суммарную длину всех пяти кодовых слов.

Решение

Для решения данной задачи рассмотрим дерево, у которого из корня и любой вершины выходят по две ветви. Сопоставим каждой левой ветви 0, а каждой правой — 1. Тогда, проходя от вершины к каждому из листьев (узлов, из которых не выходят ветви) и выписывая последовательность нулей и единиц, соответствующих обходу дерева, получим набор кодовых слов, образующих префиксный код (код, в котором ни одно кодовое слово не является началом другого).

Согласно условию задачи, искомый код должен содержать кодовые слова 1 и 010. Значит, узлы, соответствующие эти кодовым словам, должны быть листьями. На основе этих данных построим дерево.

Однако построенное дерево соответствует коду, содержащему только 4 кодовых слова. По условию задачи требуется пять кодовых слов. Для этого следует продолжить построение дерева для одного из узлов: 00 или 011.

Продолжив построение из узла 00, мы получим кодовые слова 000, 001, 010, 011, 1. Суммарная длина всех кодовых слов равна 3 + 3 + 3 + 3 + 1 = 13.

Продолжив построение из узла 0110, мы получим кодовые слова 00, 010, 0011, 0111, 1. Суммарная длина всех кодовых слов равна 2 + 3 + 4 + 4 + 1 = 14.

Следовательно, наименьшая возможная длина всех кодовых слов равна 13.

Ответ: 13

Задача 8

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А − 01, Б − 11, В − 001, Г − 0001, Д − 0000.

Определите букву, для которой можно сократить длину кодового слова так, чтобы код по-прежнему можно было однозначно декодировать. Коды остальных букв меняться не должны. В ответе укажите букву и её сокращенное кодовое слово без пробелов и запятых. Например, А0.

Решение

Условие однозначного декодирования (условие Фано) заключается в том, что однозначное декодирование возможно, только если ни одно кодовое слово не является началом другого кодового слова. В данной задаче нужно просмотреть кодовые слова для каждой из букв и проверить будет ли выполняться условие Фано, если мы каким-нибудь образом сократим данное кодовое слово. Например, рассмотрим букву А – 01. Если заменить её код на 1, то он будет являться началом кода буквы Б. Если заменить код на 0, то он будет являться началом кодов букв В, Г и Д. Таким образом, при любом сокращении кода буквы А условие Фано нарушается. Проверив подобным образом все буквы, приходим к выводу, что можно сократить букву Б, закодировав её словом 1. В таком случае нарушения условия Фано не произойдёт.

Ответ: б1

Задача 9

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код:А − 01, Б − 10, В − 110, Г − 001, Д − 000.

Определите букву, для которой можно сократить длину кодового слова так, чтобы код по-прежнему можно было однозначно декодировать. Коды остальных букв меняться не должны.

В ответе укажите букву и её сокращенное кодовое слово без пробелов и запятых. Например, А0.

Решение

Условие однозначного декодирования (условие Фано) заключается в том, что однозначное декодирование возможно, только если ни одно кодовое слово не является началом другого кодового слова. В данной задаче нужно просмотреть кодовые слова для каждой из букв и проверить будет ли выполняться условие Фано, если мы каким-нибудь образом сократим данное кодовое слово. Например, рассмотрим букву А – 01. Если заменить её код на 1, то он будет являться началом кодов букв Б и В. Если заменить код на 0, то он будет являться началом кодов букв Г и Д. Таким образом, при любом сокращении кода буквы А условие Фано нарушается. Проверив подобным образом все буквы, приходим к выводу, что можно сократить букву В, закодировав её словом 11. В таком случае нарушения условия Фано не произойдёт.

Ответ: в11

Задача 10

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А − 01, Б − 11, В − 001, Г − 101, Д − 100.

Определите букву, для которой можно сократить длину кодового слова так, чтобы код по-прежнему можно было однозначно декодировать. Коды остальных букв меняться не должны. В ответе укажите букву и её сокращенное кодовое слово без пробелов и запятых. Например, А0.

Решение

Условие однозначного декодирования (условие Фано) заключается в том, что однозначное декодирование возможно, только если ни одно кодовое слово не является началом другого кодового слова. В данной задаче нужно просмотреть кодовые слова для каждой из букв и проверить будет ли выполняться условие Фано, если мы каким-нибудь образом сократим данное кодовое слово. Например, рассмотрим букву А – 01. Если заменить её код на 1, то он будет являться началом кодов букв Б, Г и Д. Если заменить код на 0, то он будет являться началом кода буквы В. Таким образом, при любом сокращении кода буквы А условие Фано нарушается. Проверив подобным образом все буквы, приходим к выводу, что можно сократить букву В, закодировав её словом 00. В таком случае нарушения условия Фано не произойдёт.

Ответ: в00

Задача 11

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А − 00, Б − 01, В − 110, Г − 101, Д − 111.

Определите букву, для которой можно сократить длину кодового слова так, чтобы код по-прежнему можно было однозначно декодировать. Коды остальных букв меняться не должны. В ответе укажите букву и её сокращенное кодовое слово без пробелов и запятых. Например, А0.

Решение

Для решения данной задачи построим дерево, у которого из корня и любой вершины выходят по две ветви. Сопоставим каждой левой ветви 0, а каждой правой — 1. Тогда, проходя от вершины к каждому из листьев (узлов, из которых не выходят ветви) и выписывая последовательность нулей и единиц, соответствующих обходу дерева, получим набор кодовых слов, образующих префиксный код (код, в котором ни одно кодовое слово не является началом другого). Префиксный код является однозначно декодируемым. На рисунке представлено дерево, соответствующее заданному коду.

При сокращении кодового слова в дереве нужно заменить один из полученных листьев узлом более высокого уровня. Такая возможность есть только для кодового слова буквы Г. Вместо листа 100 можно взять узел более высокого уровня 10.

В этом случае полученный код: А — 00, Б — 01, В — 110, Г — 10, Д — 111 — будет префиксным и однозначно декодируемым.

Ответ: г10

Задача 12

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, допускающий однозначное декодирование. Для букв А, Б, В и Г используются следующие кодовые слова: А − 10, Б − 11, В − 000, Г − 001. Укажите, каким кодовым словом может быть закодирована буква Д, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Решение

Условие однозначного декодирования (условие Фано) заключается в том, что однозначное декодирование возможно, только если ни одно кодовое слово не является началом другого кодового слова. Известны кодовые слова 10, 11, 000, 001, следовательно, для других кодовых слов мы можем использовать только коды, начинающиеся с 01. Слово 01 можно использовать в качестве кодового, т.к. условие Фано для него выполняется. Это кодовое слово является минимальным, т.к. любой код меньший длины в данном случае не будет удовлетворять условию Фано.

Ответ: 01

Задача 13

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, допускающий однозначное декодирование. Для букв А, Б, В и Г используются следующие кодовые слова: А − 00, Б − 011, В − 010, Г − 10. Укажите, каким кодовым словом может быть закодирована буква Д, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Решение

Условие однозначного декодирования (условие Фано) заключается в том, что однозначное декодирование возможно, только если ни одно кодовое слово не является началом другого кодового слова. Известны кодовые слова 00, 011, 010, 10, следовательно, для других кодовых слов мы можем использовать только коды, начинающиеся с 11. Слово 11 можно использовать в качестве кодового, т.к. условие Фано для него выполняется. Это кодовое слово является минимальным, т.к. любой код меньший длины в данном случае не будет удовлетворять условию Фано.

Ответ: 11

Задача 14

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, допускающий однозначное декодирование. Для букв А, Б, В и Г используются следующие кодовые слова: А − 000, Б − 001, В − 010, Г − 011. Укажите, каким кодовым словом может быть закодирована буква Д, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Решение

Условие однозначного декодирования (условие Фано) заключается в том, что однозначное декодирование возможно, только если ни одно кодовое слово не является началом другого кодового слова. Известны кодовые слова 000, 001, 010, 011, следовательно, для других кодовых слов мы можем использовать только коды, начинающиеся с 1. Слово 1 можно использовать в качестве кодового, т.к. условие Фано для него выполняется.

Ответ: 1

Задача 15

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Известно, что для двух букв были использованы кодовые слова 00 и 10. Определите наименьшую возможную суммарную длину всех кодовых слов.

Задача 16

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 1, для буквы Б — кодовое слово 01. Какова наименьшая возможная сумма длин всех шести кодовых слов?

Примечание: Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки кодированных сообщений.

Задача 17

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 100, для буквы Б — кодовое слово 01. Укажите наименьшую сумму длин кодовых слов для букв В, Г, Д и Е, при котором код будет допускать однозначное декодирование.

Примечание: Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки кодированных сообщений.

Рекомендуемые курсы подготовки

Источник

На этой странице вы узнаете

  • Как закодировать сообщение “КУРЛЫК” правильно?
  • Что такое равномерное кодирование?
  • Так как кодировать сообщения максимально эффективно?

Понятие однозначного декодирования

Вы любите шпионов? А готовы почувствовать себя в их шкуре?

Нам нужно передать секретное сообщение на базу, а раз оно секретное, никто не должен понять, что мы передаем. Для этого надо представить наше сообщение в каком-то новом виде, который на первый взгляд будет бессмысленным, но мы будем знать, как его расшифровать.

Главное — чтобы расшифровать было возможно.

Мы уже знаем, что для компьютера информацию надо представить в двоичномкоде — подробнее об этом рассказано в статье «Основные понятия об информации». Но сам процесс кодирования информации — не такая простая вещь. Есть несколько факторов, которые нужно соблюсти, чтобы кодирование прошло хорошо.

Но чтобы научиться делать что-то правильно, сначала надо разобраться, как сделать неправильно. Давайте попробуем произвольным образом закодировать буквы К, У, Р, Л, Ы, чтобы составлять из них сообщения.

Каждой букве в табличке сопоставлено несколько символов, в нашем случае цифр. Эти символы — кодовое слово буквы, позволяющее отличить ее от других букв в закодированном сообщении.

С помощью кодовых слов каждой отдельной буквы закодируем сообщение КУРЛЫК, для этого на место каждой буквы будем подставлять соответствующее ей кодовое слово:

С проблемой мы столкнемся при попытке расшифровать сообщение. Чтобы это сделать, надо выделить в коде сообщения отдельные кодовые слова и подставить на их место соответствующие буквы. Но при расшифровке этого кода можно получить другой вариант:

Как закодировать сообщение КУРЛЫК правильно?

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

Равномерное кодирование

Но как можно соблюдать это условие? Или еще круче — как строить кодовые слова, которые заранее будут этому условию удовлетворять?

Что такое равномерное кодирование?

Это первый вариант подхода к однозначному декодированию.Он подразумевает кодирование отдельных элементов кодами, имеющими одинаковую длину.

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

Кодируем сообщение КУРЛЫК:

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

Такой метод действительно прост и в освоении, и при составлении кодовых слов, и при расшифровке. Но есть один минус — он не всегда эффективен.

Выбирая длину одного кодового слова, мы можем заранее определить количество возможных кодов: так как на каждой позиции может быть либо 0, либо 1, количество возможных кодов N длины i будет равно

(N = 2^i).

Выбрав длину 3 для наших кодовых слов, мы имеем 8 различных кодов, хотя кодируем всего 5 букв.

В других ситуациях потери могут быть плачевнее: для кодирования, например, 33 букв русского алфавита длина кодового слова должна быть не меньше 6 (если выберем 5, получим максимум 25 = 32 кодового слова, но тогда 1 буква останется незакодированной).

Но имея 26 = 64 кодовых слова для 33-х букв алфавита, мы явно взяли кодов больше, чем нужно.

Почему это плохо? Рассмотрим следующую ситуацию.
Вася собирает вещи для переезда и ему надо упаковать какой-то набор вещей в коробку. Если в ней много свободного места — это плохо, потому что Вася может взять коробку поменьше и ему будет легче нести маленькую коробку. Также и здесь, если в нашей кодировке много неиспользованных кодов — это плохо, потому что можно оптимальнее перекодировать необходимый набор символов, и зашифрованные сообщения станут занимать меньше места на компьютере или быстрее передаваться по интернету.

Естественно, равномерное кодирование — все еще возможный вариант, при котором код будет однозначно декодируемым, но нет ли более рационального подхода?

Условие Фано и дерево вариантов

Так как кодировать сообщения максимально эффективно?

Хороший вариант — составление кодовых слов, которые удовлетворяют условию Фано.

Условие Фано гласит: «ни одно кодовое слово не должно быть началом другого кодового слова».

В составленных нами в самом начале статьи кодовых словах это условие нарушалось — код буквы К (010) начинался с кода буквы У (01), а код Ы (001) — с кода Р (00). Из-за этого мы не могли быть точно уверены, где закончилось кодовое слово, а где оно продолжается.

Очень просто строить код, который будет удовлетворять условию Фано, с помощью дерева вариантов — структуры, в нашем случае помогающей получить кодовые слова максимально просто и понятно. Принцип работы дерева состоит в том, что в его узлах будут находиться кодовые слова, а из узла могут выходить два ребра, соответствующие добавлению в конец кодового слова 0 и 1, таким образом заменяя одно кодовое слово на два новых, которые длиннее на один символ.

Алгоритм построения дерева вариантов

1. Начальный узел — пустой.
2. К любому узлу могут быть добавлены ребра, создающие два новых узла, в каждом из которых находится новое кодовое слово на 1 символ длиннее предыдущего (с добавленным в конец символом 0 и 1, соответственно).
3. Шаг 2 выполняется до тех пор, пока не будет получено необходимое количество конечных узлов (самых последних, из которых не выходит ни одного ребра).

Давайте попробуем таким образом получить ровно 5 кодовых слов, чтобы закодировать наши буквы К, У, Р, Л, Ы.

  1. Первые два кодовых слова, которые мы можем получить из ничего — 0 и 1.
    Чтобы продолжить построение дерева, выбираем любой из конечных узлов и также добавляем ему 0 и 1 в конец.
  1. Допустим, мы добавим 0 и 1 к кодовому слову 1, и вместо него теперь получим два новых — 10 и 11. Теперь кодовых слов у нас уже три — 0, 10 и 11.
    Все еще мало, продолжаем построение дерева.
  1. Мы проделали ту же операцию с кодовым словом 0, заменив его на 2 новых — 00 и 01.
    Кодовых слов стало 4, этого все еще мало, нужно продолжить построение дерева.
  1.  Из конечных узлов можно выбрать любой для продолжения построения, например — 01, продолжив это кодовое слово, получаем два новых — 010 и 011.

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

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

Так, код 010110010011010 мы можем однозначно декодировать, читая его слева направо:

Существует также обратное условие Фано.

Его формулировка немного отличается: «ни одно кодовое слово не должно быть окончанием другого». Такая формулировка уже допустит сосуществование кодовых слов 011 и 01, но не допустит 110 и 10, так как второе совпадает с окончанием первого. 

Здесь построение дерева вариантов и чтение кодов происходит в точности до наоборот — при построении мы добавляем символы не в конец, а в начало предыдущего кодового слова и читаем код справа налево.

И код 010110001110010 будет читаться уже в другую сторону – из конца в начало:

Практика

В жизни чаще всего используются равномерные кодировки в силу многих причин, таких как:

  1. Большая устойчивость. 

Представим, что мы передаем слово КУРЛЫК разными вариантами, но при передаче допускаем ошибку в четвертом бите (в четвертом символе нашего кода). Посмотрим, что получится в итоге.

Выводы: 

  • В первом случае из-за одного неправильного бита сломалась половина символов текста, и даже поменялось количество этих символов.
  • Во втором случае текст отличается от первоначального только тем символом, на который влиял сломанный бит.

Таким образом, мы видим большую устойчивость равномерного кодирования.

2. Простота расширения. 

Мы обсуждали, что проблема равномерного кодирования — в большом количестве «пустых мест». Но эти пустые места могут быть полезны. Например, захочет разработчик добавить в код несколько новых эмодзи. У него как раз есть незанятые коды для этих символов. Согласитесь, это удобнее, чем переписывать всю кодировку целиком. 

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

Также применение неравномерной кодировки есть в 4 задаче ЕГЭ и во 2 задаче ОГЭ.

Разберем задачу №4 ЕГЭ:

По каналу связи передаются закодированные сообщения о состоянии системы, состоящие из пяти символов: A, B, C, D, E. При передаче сообщений используется двоичный код, при этом он допускает однозначное декодирование. Для символов A, B, C используются эти кодовые слова: 1, 010 и 001 (соответственно).

В ответе нужно указать наименьшее по длине кодовое слово для буквы D. Если таких кодов несколько, то в ответе укажите наименьший по значению.

Решение.

Шаг 1. Построим дерево вариантов кодовых слов и отметим на нем уже известные коды букв:

Шаг 2. Заметим, что раз для символа A кодовое слово 1, то в дальнейшем нам не подойдут любые коды, начинающиеся с 1, так как для них и символа A не будет выполняться условие однозначного декодирования.

Шаг 3. Начнем разбирать по возрастанию кодовые слова, начинающиеся с 0:

  • 0 — не подойдет, будет началом для кодовых слов 001 и 010.
  • 00 — не подойдет, будет началом слова 001.
  • 01 — не подойдет, будет началом слова 010.
  • 000 — подойдет.
  • 001 — не подойдет, буква C.
  • 010 — не подойдет, буква B.
  • 011 — подойдет.

Шаг 4. Получаем два недостающих кодовых слова равной длины: 000 и 011. Значит, можем использовать их для букв Е и D, при этом сохранив однозначное декодирование. Для D нужно слово, меньшее по значению, тогда верным ответом будет 000.

Ответ: 000
В этой статье мы познакомились с условием Фано и научились правильно кодировать и декодировать сообщения. Но различные виды информации требуют собственных уникальных подходов. Приглашаем вас продолжить изучение темы в статьях «Кодирование изображения» и «Кодирование звука».

Фактчек

  • Условие однозначного декодирования необходимо для того, чтобы у закодированного сообщения был ровно один вариант расшифровки — исходный.
  • Однозначное декодирование может давать равномерное кодирование, при котором все кодовые слова имеют одинаковую длину, или кодовые слова, составленные по условию Фано, которое гласит: «ни одно кодовое слово не должно совпадать с началом другого кодового слова».
  • Существует другая вариация этого условия — обратное условие Фано, оно гласит: «ни одно кодовое слово не должно совпадать с окончанием другого кодового слова».
  • Для составления кодовых слов, удовлетворяющих условию Фано, используется дерево вариантов.

Проверь себя

Задание 1.
Для чего необходимо условие однозначного декодирования?

  1. Для более удобной шифровки сообщений.
  2. Для построения минимально возможных кодовых слов.
  3. Для сохранения возможности абсолютно точно получить исходное сообщение из закодированного.
  4. Для красоты.

Задание 2.
Выберите верные утверждения:

  1. При равномерном кодировании все кодовые слова имеют одну длину.
  2. При равномерном кодировании кодовые слова не могут начинаться на один и тот же символ.
  3. Для соблюдения условия Фано необходимо, чтобы ни одно кодовое слово не совпадало с окончанием другого кодового слова.
  4. Обратное условие Фано не гарантирует однозначное декодирование.
  5. Для составления кодовых слов, удовлетворяющих обратному условию Фано, используется дерево вариантов.

Задание 3.
Выберите наборы кодовых слов, которые удовлетворяют условию однозначного декодирования по любому из критериев, описанных в статье:

  1. 1, 11, 111, 1111, 11111, 0.
  2. 01, 001, 0001, 00001, 1
  3. 000, 111, 100, 001
  4. 10, 11, 00, 1001
  5. 10, 100, 1000, 10000

Задание 4.
Для передачи сообщений используются буквы А, Б, В, Г, Д. Известны некоторые кодовые слова: А = 01, Б = 111, В = 00, Г = 110. Какое кодовое слово может соответствовать кодовому слову для буквы Д, чтобы весь код удовлетворял условию Фано?

  1. 0
  2. 11
  3. 101
  4. 1100

Ответы: 1. — 3; 2. — 1, 5; 3. — 2, 3, 4, 5; 4. — 3.

Источник

Кодирование. Правило Фано. Передача данных с ошибками

Типы только для начальной подготовки (не нужно тренировать для экзамена):

  • Правило Фано ( 16 )
    Подобрать код для новой буквы, чтобы допускалось однозначное декодирование.

  • Правило Фано и длительность сообщения ( 18 )

Актуальные типы:

  • Правило Фано 2 ( 35 )
    С ограничениями

Устаревшие типы (нажмите, чтобы раскрыть)

  • Буквы — двоичный код ( 6 )
    Буквам ставится в соответствие двоичный код. Последовательность букв кодируется, результат нужно перевести в восьмеричную или шестнадцатеричную систему.

  • Буквы — двоичный (неравномерный) код ( 4 )
    Аналогично «Буквы — двоичный код», но код неравномерный. Особое внимание на добавление нулей в случае одноразрядного представления

  • Декодирование строки ( 7 )
    Декодирование с начала, с конца или кодирование ответов

  • Правило Фано (с частотой букв) ( 5 )
    Тоже, что и задачи на правило Фано, но нужно учитывать частоту появления букв и подбирать длину кода.

  • Передача с ошибками ( 12 )
    Подобрать новый код, чтобы отличался от имеющихся не менее, чем в трех позициях.

  • Другие задачи ( 4 )
    Длина кода с четным количеством единиц в коде; Задачи с битом четности (сумма … по модулю 2), изображения и т.д.

Правило Фано ( 16 )

Подобрать код для новой буквы, чтобы допускалось однозначное декодирование.

14 ege4 Правило Фано

Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=1, Б=01, В=001. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?

1) 0001
2) 000
3) 11
4) 101

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

15 ege4 Правило Фано

Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=0, Б=100, В=101. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?

1) 1
2) 11
3) 01
4) 010

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

16 ege4 Правило Фано

Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=01, Б=1, В=001. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?

1) 0001
2) 000
3) 11
4) 101

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

17 ege4 Правило Фано

Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=0, Б=100, В=110. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?

1) 101
2) 10
3) 11
4) 01

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

18 ege4 Правило Фано

Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=00, Б=11, В=100. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?

1) 010
2) 0
3) 01
4) 011

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

19 ege4 Правило Фано

Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=1, Б=000, В=001. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?

1) 00
2) 01
3) 11
4) 010

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

20 ege4 Правило Фано

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А–10, Б–11, В–000, Г–001, Д–011. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.

1) это невозможно
2) для буквы Б – 1
3) для буквы Г – 00
4) для буквы Д – 01

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

21 ege4 Правило Фано

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А–11, Б–10, В–011, Г–000, Д–001. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.

1) для буквы Г – 00
2) это невозможно
3) для буквы В – 01
4) для буквы Б – 1

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

22 ege4 Правило Фано

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д и Е, используется неравномерный двоичный префиксный код. Даны кодовые слова для четырёх букв: А – 011, Б – 010, В – 001, Г – 000. Какие кодовые слова из приведённых ниже вариантов подходят для букв Д и Е? Если подходит более одного варианта, укажите тот, для которого сумма длин кодовых слов меньше.

Примечание. Префиксный код – это код, в котором ни одно кодовое слово не является началом другого; такие коды позволяют однозначно декодировать полученную двоичную последовательность.

1) Д – 100, Е – 110
2) Д – 100, Е – 11
3) Д – 10, Е – 11
4) Д – 10, Е – 1

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

23 ege4 Правило Фано

Для кодирования некоторой последовательности, состоящей из букв У, Ч, Е, Н, И и К, используется неравномерный двоичный префиксный код. Вот этот код: У – 000, Ч – 001, Е – 010, Н – 100, И – 011, К – 11. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему остался префиксным? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.

Примечание. Префиксный код – это код, в котором ни одно кодовое слово не является началом другого; такие коды позволяют однозначно декодировать полученную двоичную последовательность.

1) кодовое слово для буквы Е можно сократить до 01
2) кодовое слово для буквы К можно сократить до 1
3) кодовое слово для буквы Н можно сократить до 10
4) это невозможно

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

26 ege4 Правило Фано

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В и Г использовали такие кодовые слова: А — 000, Б — 001, В — 010, Г — 011.
Укажите, каким кодовым словом из перечисленных ниже может быть закодирована буква Д.
Код должен удовлетворять свойству однозначного декодирования. Если можно использовать более одного кодового слова, укажите кратчайшее из них.

1) 1
2) 0
3) 01
4) 10

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

27 ege4 Правило Фано

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А – 00, Б – 01, В – 100, Г – 101, Д – 110. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны.
Выберите правильный вариант ответа.

1) это невозможно
2) для буквы Г – 10
3) для буквы Д – 11
4) для буквы Д – 10

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

28 ege4 Правило Фано

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В и Г использовали такие кодовые слова: А — 111, Б — 110, В — 101, Г — 100.
Укажите, каким кодовым словом из перечисленных ниже может быть закодирована буква Д.
Код должен удовлетворять свойству однозначного декодирования. Если можно использовать более одного кодового слова, укажите кратчайшее из них.

1) 1
2) 0
3) 01
4) 10

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

29 ege4 Правило Фано

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный троичный код, позволяющий однозначно декодировать полученную троичную последовательность. Вот этот код: А–0, Б–11, В–20, Г–21, Д–22. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.

1) для буквы Б – 1
2) это невозможно
3) для буквы В – 2
4) для буквы Д – 2

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

48 ege4 Правило Фано

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Использовали код:
А–111, Б–110, В–100, Г–0. Укажите, каким кодовым словом может быть закодирована буква Д.
Код должен удовлетворять свойству однозначного декодирования. Если можно использовать более одного кодового слова, укажите кратчайшее из них.

1) 001
2) 00
3) 101
4) 10

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

3683 ege4 Правило Фано

Для кодирования растрового рисунка, напечатанного с использованием шести красок, применили неравномерный двоичный код. Для кодирования цветов используются кодовые слова.
Белый – 0, Зелёный – 11111, Фиолетовый – 11110, Красный – 1110, Чёрный – 10.
Укажите кратчайшее кодовое слово для кодирования синего цвета, при котором код будет допускать однозначное декодирование.

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

Правило Фано и длительность сообщения ( 18 )


1021 ege4 Правило Фано и длительность сообщения

Для кодирования некоторой последовательности, состоящей из букв И, К, Л, М, Н, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово 0, для буквы К – кодовое слово 10. Какова наименьшая возможная суммарная длина всех пяти кодовых слов?

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп


1022 ege4 Правило Фано и длительность сообщения

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 1, для буквы Б – кодовое слово 001. Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп


1023 ege4 Правило Фано и длительность сообщения

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 01, для буквы Б – кодовое слово 10. Какова наименьшая возможная суммарная длина всех пяти кодовых слов?

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп


1024 ege4 Правило Фано и длительность сообщения

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 0, для буквы Б – кодовое слово 101. Какова наименьшая возможная суммарная длина всех пяти кодовых слов?

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп


1025 ege4 Правило Фано и длительность сообщения

В сообщении встречается 7 разных букв. При его передаче использован неравномерный двоичный код, удовлетворяющий условию Фано. Известны коды трёх букв: 1, 01, 001. Коды остальных четырёх букв имеют одинаковую длину. Какова минимальная суммарная длина всех 7-ми кодовых слов?

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп


1026 ege4 Правило Фано и длительность сообщения

В сообщении встречается 10 разных букв. При его передаче использован неравномерный двоичный префиксный код. Известны коды трех букв: 11, 100, 101. Коды остальных семи букв имеют одинаковую длину. Какова минимальная суммарная длина всех 10-ти кодовых слов?

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп


1027 ege4 Правило Фано и длительность сообщения

В сообщении встречается 7 разных букв. При его передаче использован неравномерный двоичный префиксный код. Известны коды двух букв: 10, 111. Коды остальных пяти букв имеют одинаковую длину. Какова минимальная суммарная длина всех 7-ми кодовых слов?

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп


1028 ege4 Правило Фано и длительность сообщения

В сообщении встречается 50 букв А, 30 букв Б, 20 букв В и 5 букв Г. При его передаче использован неравномерный двоичный префиксный код, который позволил получить минимальную длину закодированного сообщения. Какова она в битах?

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

3693 ege4 Правило Фано и длительность сообщения

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, К, О, Т, Р, Я . Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А – 101, О – 11, Я – 011. Какое наименьшее количество двоичных знаков потребуется для кодирования слова КАТОК?

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

3685 ege4 Правило Фано и длительность сообщения

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, В, Г, Д, Е и Ж. Для передачи используется двоичный код, удовлетворяющий условию Фано. Для буквы А используется кодовое слово 1; для буквы Б используется кодовое слово 01. Какова минимальная общая длина кодовых слов для всех семи букв?

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

4593 ege4 Правило Фано и длительность сообщения

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Й, Л, М, Т, Ю . Для передачи используется двоичный к од, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Л – 010, Б – 011, Ю – 10. Какое наименьшее количество двоичных знаков потребуется для кодирования слова АЛТАЙ?

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

3686 ege4 Правило Фано и длительность сообщения

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, В, Г, Д, Е и Ж. Для передачи используется двоичный код, удовлетворяющий условию Фано. Для буквы А используется кодовое слово 1; для буквы Б используется кодовое слово 011. Какова минимальная общая длина кодовых слов для всех семи букв?

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

3687 ege4 Правило Фано и длительность сообщения

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, В, Г, Д, Е и Ж. Для передачи используется двоичный код, удовлетворяющий условию Фано. Для буквы А используется кодовое слово 10; для буквы Б используется кодовое слово 011. Какова минимальная общая длина кодовых слов для всех семи букв?

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

3688 ege4 Правило Фано и длительность сообщения

По каналу связи передаются сообщения, содержащие только пять букв: Р, А, Н, Е, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Для буквы А используется кодовое слово 0; для буквы Е используется кодовое слово 10. Какова минимальная общая длина кодовых слов для всех пяти букв?

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

3689 ege4 Правило Фано и длительность сообщения

(А.Г. Гильдин, г. Уфа) Для кодирования букв А, Б, В, Г, Д, Е, Ж, З, И, использован неравномерный троичный код, удовлетворяющий условию Фано. Для буквы А используется кодовое слово 0; для буквы Б используется кодовое слово 10; для буквы В используется кодовое слово 11; для буквы Г используется кодовое слово 21; для буквы Д используется кодовое слово 22. Какова минимальная общая длина кодовых слов для букв Е, Ж, З, И?

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

3690 ege4 Правило Фано и длительность сообщения

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, М, Р, Я . Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А – 010, Б – 011, И – 10. Какое наименьшее количество двоичных знаков потребуется для кодирования слова ГРАММ?

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

3691 ege4 Правило Фано и длительность сообщения

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, М, Р, Я . Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А – 11, Б – 101, Я – 010. Какое наименьшее количество двоичных знаков потребуется для кодирования слова ГРАММ?

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

3692 ege4 Правило Фано и длительность сообщения

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, К, О, Н, Р, Я . Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А – 010, Р – 011, Я – 10. Какое наименьшее количество двоичных знаков потребуется для кодирования слова КОРАН?

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

Правило Фано 2 ( 35 )

С ограничениями


3694 ege4 Правило Фано 2

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, допускающий однозначное декодирование. Для букв А, Б, В, Г использовали соответственно кодовые слова 00, 01, 110, 111. Укажите кратчайшее возможное кодовое слово для буквы Д, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

3695 ege4 Правило Фано 2

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, Ж решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г использовали соответственно кодовые слова 010, 011, 10, 11. Укажите кратчайшее возможное кодовое слово для буквы Д, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

3696 ege4 Правило Фано 2

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, Ж решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г использовали соответственно кодовые слова 00, 01, 100, 101. Укажите кратчайшее возможное кодовое слово для буквы Д, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

3697 ege4 Правило Фано 2

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, Ж решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г использовали соответственно кодовые слова 00, 010, 011, 11. Укажите кратчайшее возможное кодовое слово для буквы Д, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

3698 ege4 Правило Фано 2

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, Ж решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г использовали соответственно кодовые слова 0, 100, 101, 111. Укажите кратчайшее возможное кодовое слово для буквы Д, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

3699 ege4 Правило Фано 2

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, Ж решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г использовали соответственно кодовые слова 000, 1, 010, 011. Укажите кратчайшее возможное кодовое слово для буквы Д, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

3700 ege4 Правило Фано 2

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, Ж, З, И, Й. решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г, Д, Е, Ж, З, И использовали соответственно кодовые слова 00, 111, 1000, 1001, 1010, 1100, 1101, 010, 011. Укажите кратчайшее возможное кодовое слово для буквы Й, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

3701 ege4 Правило Фано 2

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, Ж, З, И, Й. решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г, Д, Е, Ж, З, И использовали соответственно кодовые слова 0011, 1011, 1111, 0110, 0001, 1100, 0010, 0111, 0000. Укажите кратчайшее возможное кодовое слово для буквы Й, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

3702 ege4 Правило Фано 2

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, Ж, З, И, Й. решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г, Д, Е, Ж, З, И использовали соответственно кодовые слова 0100, 0101, 1000, 11, 000, 101, 0010, 0011, 1001. Укажите кратчайшее возможное кодовое слово для буквы Й, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

3703 ege4 Правило Фано 2

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, Ж, З, И, Й. решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г, Д, Е, Ж, З, И использовали соответственно кодовые слова 1110, 011, 1001, 1111, 0001, 0000, 110, 0011, 0100. Укажите кратчайшее возможное кодовое слово для буквы Й, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

3704 ege4 Правило Фано 2

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, Ж, З, И, Й. решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г, Д, Е, Ж, З, И использовали соответственно кодовые слова 111, 0100, 1100, 0010, 0001, 0011, 0110, 1001, 1010. Укажите кратчайшее возможное кодовое слово для буквы Й, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

3705 ege4 Правило Фано 2

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, Ж, З, И, Й. решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г, Д, Е, Ж, З, И использовали соответственно кодовые слова 110, 00, 1011, 010, 0110, 1001, 1110, 1111, 0111. Укажите кратчайшее возможное кодовое слово для буквы Й, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

3706 ege4 Правило Фано 2

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, Ж, З, И, Й. решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г, Д, Е, Ж, З, И использовали соответственно кодовые слова 1101, 111, 0101, 0110, 1001, 1011, 0100, 1010, 1000. Укажите кратчайшее возможное кодовое слово для буквы Й, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

3707 ege4 Правило Фано 2

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, Ж, З, И, Й. решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г, Д, Е, Ж, З, И использовали соответственно кодовые слова 010, 0011, 0111, 0000, 0010, 1110, 110, 1111, 0110. Укажите кратчайшее возможное кодовое слово для буквы Й, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

3709 ege4 Правило Фано 2

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, Ж, З, И, Й. решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г, Д, Е, Ж, З, И использовали соответственно кодовые слова 1010, 1101, 010, 00, 1000, 1110, 1001, 0111, 1011. Укажите кратчайшее возможное кодовое слово для буквы Й, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

3708 ege4 Правило Фано 2

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, Ж, З, И, Й. решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г, Д, Е, Ж, З, И использовали соответственно кодовые слова 1100, 0010, 1010, 0000, 0111, 1101, 0101, 100, 0001. Укажите кратчайшее возможное кодовое слово для буквы Й, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп


3713 ege4 Правило Фано 2

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, Ж, З, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г, Д, Е использовали соответственно кодовые слова 11, 0010, 100, 0011, 01, 000. Укажите кратчайшее возможное кодовое слово для буквы Ж, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп


3712 ege4 Правило Фано 2

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, Ж, З, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г, Д, Е использовали соответственно кодовые слова 0101, 101, 011, 00, 0100, 11. Укажите кратчайшее возможное кодовое слово для буквы Ж, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп


3711 ege4 Правило Фано 2

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, Ж, З, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г, Д, Е использовали соответственно кодовые слова 10, 110, 010, 0110, 111, 0111. Укажите кратчайшее возможное кодовое слово для буквы Ж, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп


3716 ege4 Правило Фано 2

По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г; для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В используются такие кодовые слова: А – 0; Б – 110; В – 101. Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наибольшим числовым значением.

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп


3718 ege4 Правило Фано 2

По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г; для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв А и Б используются такие кодовые слова: А – 1; Б – 011. Укажите сумму длин кратчайших кодовых слов для букв В и Г, при котором код будет допускать однозначное декодирование.

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп


3717 ege4 Правило Фано 2

По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г; для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв А и Б используются такие кодовые слова: А – 0; Б – 1011. Укажите сумму длин кратчайших кодовых слов для букв В и Г, при котором код будет допускать однозначное декодирование.

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп


3720 ege4 Правило Фано 2

По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г; для передачи используется двоичный код, удовлетворяющий условию Фано. Для буквы А используется кодовое слово: А – 10. Укажите сумму длин кратчайших кодовых слов для букв Б, В и Г, при котором код будет допускать однозначное декодирование.

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп


3719 ege4 Правило Фано 2

По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г; для передачи используется двоичный код, удовлетворяющий условию Фано. Для буквы А используется кодовое слово: А – 1. Укажите сумму длин кратчайших кодовых слов для букв Б, В и Г, при котором код будет допускать однозначное декодирование.

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

4594 ege4 Правило Фано 2

По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г; для передачи используется двоичный код, удовлетворяющий условию Фано. Для буквы А используется кодовое слово: А – 101. Укажите сумму длин кратчайших кодовых слов для букв Б, В и Г, при котором код будет допускать однозначное декодирование.

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

4595 ege4 Правило Фано 2

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, И, Л, О, С, Ц. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Б – 00, O – 010, Л – 111. Какое наименьшее количество двоичных знаков потребуется для кодирования слова АБСЦИССА?

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

4597 ege4 Правило Фано 2

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, З, К, Р, У, Ф. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А – 00, Б – 01, Ф – 111. Какое наименьшее количество двоичных знаков потребуется для кодирования слова КУКУРУЗА?

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

4596 ege4 Правило Фано 2

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, В, Д, Е, И, Н. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А – 110, Б – 01, И – 000. Какое наименьшее количество двоичных знаков потребуется для кодирования слова ВВЕДЕНИЕ?

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

4598 ege4 Правило Фано 2

По каналу связи передаются сообщения, содержащие только семь букв: А, В, К, Л, О, Т, Ц. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: К – 00, Л – 01, О – 1000. Какое наименьшее количество двоичных знаков потребуется для кодирования слова АВТОЛАВКА?

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

4599 ege4 Правило Фано 2

По каналу связи передаются сообщения, содержащие только семь букв: А, И, К, Л, Р, Ц, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А – 01, Я – 11. Какое наименьшее количество двоичных знаков потребуется для кодирования слова КИРИЛЛИЦА?

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп


4601 ege4 Правило Фано 2

По каналу связи передаются сообщения, содержащие только шесть букв: А, Б, В, Д, О, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Б – 010, В – 011. Какое наименьшее количество двоичных знаков потребуется для кодирования слова ВОДООТВОД?

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

4600 ege4 Правило Фано 2

По каналу связи передаются сообщения, содержащие только семь букв: А, Г, Д, Е, П, Р, Ф. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Г – 100, Д – 11, Е – 0. Какое наименьшее количество двоичных знаков потребуется для кодирования слова ПАРАГРАФ?

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп


3715 ege4 Правило Фано 2

(А.Н. Носкин) Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, Ж, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г, Д, Е использовали соответственно кодовые слова 11, 10, 010, 0011, 0010, 0000. Укажите возможное кодовое слово для буквы Ж, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп


3714 ege4 Правило Фано 2

(А.Н. Носкин) Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г использовали соответственно кодовые слова 011, 010, 001, 0001. Укажите возможное кодовое слово для буквы Д, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп


3710 ege4 Правило Фано 2

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, Ж, З, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г, Д, Е, Ж использовали соответственно кодовые слова 11, 0010, 1011, 01, 0011, 000, 1010. Укажите кратчайшее возможное кодовое слово для буквы З, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

Буквы — двоичный код ( 6 )

Буквам ставится в соответствие двоичный код. Последовательность букв кодируется, результат нужно перевести в восьмеричную или шестнадцатеричную систему.


2 ege4 Буквы — двоичный код

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

1) 132
2) D2
3) 3102
4) 2D

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп


4 ege4 Буквы — двоичный код

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

1) 138
2) DBCA
3) D8
4) 3120

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп


5 ege4 Буквы — двоичный код

Для кодирования букв А, Б, В, Г используются четырехразрядные последовательные двоичные числа от 1000 до 1011 соответственно. Если таким способом закодировать последовательность символов БГАВ и записать результат в восьмеричном коде, то получится:

1) 175423
2) 115612
3) 62577
4) 12376

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп


6 ege4 Буквы — двоичный код

Для кодирования букв А, В, С, D используются трехразрядные последовательные двоичные числа, начинающиеся с 1 (от 100 до 111 соответственно). Если таким способом закодировать последовательность символов CDAB и записать результат в шестнадцатеричном коде, то получится:

1) А52
2) 4С8
3) 15D
4) DE5

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

7 ege4 Буквы — двоичный код

Для кодирования букв К, L, М, N используются четырехразрядные последовательные двоичные числа от 1000 до 1011 соответственно. Если таким способом закодировать последовательность символов KMLN и записать результат в восьмеричном коде, то получится:

1) 84613
2) 105233
3) 12345
4) 776325

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

13 ege4 Буквы — двоичный код

Для кодирования букв А, В, С, D используются четырехразрядные последовательные двоичные числа, начинающиеся с 1 (от 1001 до 1100 соответственно). Если таким способом закодировать последовательность символов CADB и записать результат в шестнадцатеричном коде, то получится:

1) AF52
2) 4CB8
3) F15D
4) В9СА

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

Буквы — двоичный (неравномерный) код ( 4 )

Аналогично «Буквы — двоичный код», но код неравномерный. Особое внимание на добавление нулей в случае одноразрядного представления


43 ege4 Буквы — двоичный (неравномерный) код

Для кодирования букв Е,П, Н, Ч, Ь используются двоичные коды чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Если таким способом закодировать последовательность символов ПЕЧЕНЬЕ и записать результат в восьмеричном коде, то получится:

1) 1030240
2) 12017
3) 2141351
4) 23120

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп


44 ege4 Буквы — двоичный (неравномерный) код

Для кодирования букв И, Д, Т, О, Х используются двоичные коды чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Если таким способом закодировать последовательность символов ТИХОХОД и записать результат в шестнадцатеричном коде, то получится:

1) CD89
2) 89CD
3) 3154542
4) 2043431

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп


45 ege4 Буквы — двоичный (неравномерный) код

Для кодирования букв Х, Е, Л, О, Д используются двоичные коды чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Если таким способом закодировать последовательность символов ЛЕДОХОД и записать результат в шестнадцатеричном коде, то получится:

1) 999C
2) 3254145
3) 123F
4) 2143034

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп


46 ege4 Буквы — двоичный (неравномерный) код

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

1) 5434215
2) 9DA4
3) ABCD
4) 4323104

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

Декодирование строки ( 7 )

Декодирование с начала, с конца или кодирование ответов


8 ege4 Декодирование строки

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

  a   b   c    d   e
 000 110  01  001  10

Определите, какой набор букв закодирован двоичной строкой 1100000100110

1) baade
2) badde
3) bacde
4) bacdb

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

9 ege4 Декодирование строки

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

 а    b    с   d   е
100  110  011  01  10

Определите, какой набор букв закодирован двоичной строкой 1000110110110, если известно, что все буквы в последовательности – разные:

1) cbade
2) acdeb
3) acbed
4) bacde

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

10 ege4 Декодирование строки

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

А    В   С    D   Е   F
00  100  10  011  11 101

Определите, какая последовательность из 6 букв закодирована двоичной строкой 011111000101100.

1) DEFBAC
2) ABDEFC
3) DECAFB
4) EFCABD

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

11 ege4 Декодирование строки

Для кодирования сообщения, состоящего только из букв A, B, C, D и E, используется неравномерный по длине двоичный код: 

 A   B   C    D   E
000  11  01  001  10

Какое (только одно!) из четырех полученных сообщений было передано без ошибок и может быть раскодировано:

1) 110000010011110
2) 110000011011110
3) 110001001001110
4) 110000001011110

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

12 ege4 Декодирование строки

Для кодирования сообщения, состоящего только из букв О, К, Л, М и Б, используется неравномерный по длине двоичный код: 

  О  К   Л    М    Б
 00  01  11  010  0110

Какое (только одно!) из четырех полученных сообщений было передано без ошибок и может быть раскодировано:

1) 110001001001110
2) 10000011000111010
3) 110001001101001
4) 1000110001100010

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

35 ege4 Декодирование строки

По каналу связи передаются сообщения, содержащие только 5 букв А, И, К, О, Т. Для кодирования букв используется неравномерный двоичный код с такими кодовыми словами:
А-0, И-00, К-10, О-110, Т-111.
Среди приведённых ниже слов укажите такое, код которого можно декодировать только одним способом. Если таких слов несколько, укажите первое по алфавиту.

1) КАА
2) ИКОТА
3) КОТ
4) ни одно из сообщений не подходит

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

47 ege4 Декодирование строки

Для кодирования сообщения, состоящего только из букв A, M, N, E и O, используется неравномерный по длине двоичный код: 

 A   M   N    E   O
000  11  01  001  10

Какое (только одно!) из четырех полученных сообщений было передано без ошибок и может быть раскодировано:

1) 01100010001100
2) 01100100011001
3) 01100100011101
4) 01100100011100

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

Правило Фано (с частотой букв) ( 5 )

Тоже, что и задачи на правило Фано, но нужно учитывать частоту появления букв и подбирать длину кода.

24 ege4 Правило Фано (с частотой букв)

По каналу связи передаются сообщения, содержащие только 4 буквы Э, Ю, Я, Ы. Для передачи сообщений нужно использовать неравномерный двоичный код, допускающий однозначное декодирование. В любом сообщении больше всего букв Я, следующая по частоте буква — Ю, затем — Э. Буква Ы встречается реже, чем любая другая. Какой из перечисленных ниже кодов нужно использовать, чтобы передаваемые закодированные сообщения были как можно более короткими?

1) Э — 0, Ю — 1, Я — 00, Ы – 11
2) Я — 1, Ю – 0, Э — 01, Ы — 10
3) Э — 1, Ю — 01, Я — 001, Ы — 000
4) Я — 0, Ю — 11, Э — 101, Ы — 100

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

1019 ege4 Правило Фано (с частотой букв)

По каналу связи передаются сообщения, каждое из которых содержит 15 букв А, 10 букв Б, 6 букв В и 4 буквы Г (других букв в сообщениях нет). Каждую букву кодируют двоичной последовательностью. При выборе кода учитывались два требования:
а) ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование);
б) общая длина закодированного сообщения должна быть как можно меньше.
Какой код из приведённых ниже следует выбрать для кодирования букв А, Б, В и Г?

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

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

1020 ege4 Правило Фано (с частотой букв)

По каналу связи передаются сообщения, каждое из которых содержит 15 букв А, 10 букв Б, 6 букв В и 4 буквы Г (других букв в сообщениях нет). Каждую букву кодируют двоичной последовательностью. При выборе кода учитывались два требования:
а) ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование);
б) общая длина закодированного сообщения должна быть как можно меньше.
Какой код из приведённых ниже следует выбрать для кодирования букв А, Б, В и Г?

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

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

25 ege4 Правило Фано (с частотой букв)

По каналу связи передаются сообщения, содержащие только 4 буквы: E, Н, О, Т. В любом сообщении больше всего букв О, следующая по частоте буква – Е, затем – Н. Буква Т встречается реже, чем любая другая. Для передачи сообщений нужно использовать неравномерный двоичный код, допускающий однозначное декодирование; при этом сообщения должны быть как можно короче. Шифровальщик может использовать один из перечисленных ниже кодов. Какой код ему следует выбрать?

1) Е – 0, Н – 1, О – 00, Т – 11
2) О – 1, Н – 0, Е – 01, Т – 10
3) Е – 1, Н – 01, О – 001, Т – 000
4) О – 0, Н – 10, Е – 111, Т – 110

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

3684 ege4 Правило Фано (с частотой букв)

(Д.В. Богданов) По каналу связи передаются сообщения, состоящие из букв Г, Т, К, Х, У. Известны вероятности появления каждой буквы:
Г – 0,5; Т – 0,25; К – 0,12; Х – 0,12; У – 0,01.
Для букв Г и У используются кодовые слова: Г – 0, У – 10. Укажите кратчайшее кодовое слово для буквы К, при котором код будет иметь минимальную длину и допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

Передача с ошибками ( 12 )

Подобрать новый код, чтобы отличался от имеющихся не менее, чем в трех позициях.

30 ege4 Передача с ошибками

По каналу связи передаются сообщения, содержащие только 4 буквы: А, Б, В, Г. Для кодирования букв А, Б, В используются 5-битовые кодовые слова: А — 11111, Б — 11000, В — 00100. Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех. Какое из перечисленных ниже кодовых слов можно использовать для буквы Г, чтобы указанное свойство выполнялось для всех четырёх кодовых слов?

1) 00000
2) 00011
3) 11100
4) не подходит ни одно из указанных выше слов

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

31 ege4 Передача с ошибками

По каналу связи передаются сообщения, содержащие только 4 буквы: А, Б, В, Г. Для кодирования букв А, Б, В используются 5-битовые кодовые слова: А — 00110, Б — 11000, В — 10011. Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех. Какое из перечисленных ниже кодовых слов можно использовать для буквы Г, чтобы указанное свойство выполнялось для всех четырёх кодовых слов?

1) 01101
2) 01001
3) 00011
4) не подходит ни одно из указанных выше слов

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

32 ege4 Передача с ошибками

По каналу связи передаются сообщения, содержащие только 4 буквы: А, Б, В, Г. Для кодирования букв А, Б, В используются 5-битовые кодовые слова: А — 10110, Б — 11000, В — 00101. Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех. Какое из перечисленных ниже кодовых слов можно использовать для буквы Г, чтобы указанное свойство выполнялось для всех четырёх кодовых слов?

1) 01011
2) 01110
3) 10001
4) не подходит ни одно из указанных выше слов

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

33 ege4 Передача с ошибками

По каналу связи передаются сообщения, содержащие только 4 буквы: А, Б, В, Г. Для кодирования букв А, Б, В используются 5-битовые кодовые слова: А — 10000, Б — 00101, В — 01010. Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех. Какое из перечисленных ниже кодовых слов можно использовать для буквы Г, чтобы указанное свойство выполнялось для всех четырёх кодовых слов?

1) 01111
2) 11011
3) 10110
4) не подходит ни одно из указанных выше слов

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

36 ege4 Передача с ошибками

По каналу связи передаются сообщения, содержащие только 4 буквы – П, О, Р, Т. Для кодирования букв используются 5-битовые кодовые слова: П – 00000, О – 00111, Р – 11011, Т – 11100. Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех (в предположении, что передаваемые биты могут искажаться, но не пропадают). Закодированное сообщение считается принятым корректно, если его длина кратна 5 и каждая пятёрка отличается от некоторого кодового слова не более чем в одной позиции; при этом считается, что пятёрка кодирует соответствующую букву. Например, если принята пятерка 11111, то считается, что передавалась буква Р. Среди приведённых ниже сообщений найдите то, которое принято корректно, и укажите его расшифровку (пробелы несущественны).
11011 10111 11101 00111 10001
10000 10111 11101 00111 00001

1) ПОТОП
2) РОТОР
3) ТОПОР
4) ни одно из сообщений не принято корректно

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

37 ege4 Передача с ошибками

По каналу связи передаются сообщения, содержащие только 4 буквы – П, О, Р, Т. Для кодирования букв используются 5-битовые кодовые слова: П – 11111, О – 11000, Р – 00100, Т – 00011. Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех (в предположении, что передаваемые биты могут искажаться, но не пропадают). Закодированное сообщение считается принятым корректно, если его длина кратна 5 и каждая пятёрка отличается от некоторого кодового слова не более чем в одной позиции; при этом считается, что пятёрка кодирует соответствующую букву. Например, если принята пятерка 00000, то считается, что передавалась буква Р. Среди приведённых ниже сообщений найдите то, которое принято корректно и укажите его расшифровку (пробелы несущественны).
11011 11100 00011 11000 01110
00111 11100 11110 11000 00000

1) ПОТОП
2) РОТОР
3) ТОПОР
4) ни одно из сообщений не принято корректно

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

38 ege4 Передача с ошибками

Для передачи данных по каналу связи используется 5-битовый код. Сообщение содержит только буквы А, Б и В, которые кодируются следующими кодовыми словами:
А — 10111, Б — 00000, В — 11010.
При передаче возможны помехи. Однако некоторые ошибки можно попытаться исправить. Любые два из этих трёх кодовых слов отличаются друг от друга не менее чем в трёх позициях. Поэтому если при передаче слова произошла ошибка не более чем в одной позиции, то можно сделать обоснованное предположение о том, какая буква передавалась. (Говорят, что «код исправляет одну ошибку».) Например, если получено кодовое слово 00100, считается, что передавалась буква Б. (Отличие от кодового слова для Б только в одной позиции, для остальных кодовых слов отличий больше.) Если принятое кодовое слово отличается от кодовых слов для букв А, Б, В более чем в одной позиции, то считается, что произошла ошибка (она обозначается ‘х’).

Получено сообщение 10101 10000 11110 10010. Декодируйте это сообщение – выберите правильный вариант.

1) АБВВ
2) хххх
3) АБхх
4) АБхВ

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

39 ege4 Передача с ошибками

Для передачи данных по каналу связи используется 5-битовый код. Сообщение содержит только буквы А, Б и В, которые кодируются следующими кодовыми словами:
А — 10001, Б — 01101, В — 10110.
При передаче возможны помехи. Однако некоторые ошибки можно попытаться исправить. Любые два из этих трёх кодовых слов отличаются друг от друга не менее чем в трёх позициях. Поэтому если при передаче слова произошла ошибка не более чем в одной позиции, то можно сделать обоснованное предположение о том, какая буква передавалась. (Говорят, что «код исправляет одну ошибку».) Например, если получено кодовое слово 01111, считается, что передавалась буква Б. (Отличие от кодового слова для Б только в одной позиции, для остальных кодовых слов отличий больше.) Если принятое кодовое слово отличается от кодовых слов для букв А, Б, В более чем в одной позиции, то считается, что произошла ошибка (она обозначается ‘х’).

Получено сообщение 00110 11101 11000 11001. Декодируйте это сообщение – выберите правильный вариант.

1) ВБхх
2) ВБВА
3) хххх
4) ВБхА

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

40 ege4 Передача с ошибками

Для передачи данных по каналу связи используется 5-битовый код. Сообщение содержит только буквы А, Б и В, которые кодируются следующими кодовыми словами:
А — 11000, Б — 00010, В — 10101.
При передаче возможны помехи. Однако некоторые ошибки можно попытаться исправить. Любые два из этих трёх кодовых слов отличаются друг от друга не менее чем в трёх позициях. Поэтому если при передаче слова произошла ошибка не более чем в одной позиции, то можно сделать обоснованное предположение о том, какая буква передавалась. (Говорят, что «код исправляет одну ошибку».) Например, если получено кодовое слово 01010, считается, что передавалась буква Б. (Отличие от кодового слова для Б только в одной позиции, для остальных кодовых слов отличий больше.) Если принятое кодовое слово отличается от кодовых слов для букв А, Б, В более чем в одной позиции, то считается, что произошла ошибка (она обозначается ‘х’).

Получено сообщение 11110 10111 10010 10000. Декодируйте это сообщение – выберите правильный вариант.

1) хххх
2) АВБА
3) ххБА
4) хВБА

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

41 ege4 Передача с ошибками

По каналу связи передаются сообщения, содержащие только 4 буквы: И, Г, Л, А. Для кодирования букв И, Г, Л используются 6-битовые кодовые слова:
И – 000000, Г – 001110, Л – 110110.
Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее, чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех. Нужно подобрать кодовое слово для буквы А так, чтобы указанное свойство выполнялось для всех четырёх кодовых слов.

1) 111110
2) 111000
3) 000110
4) не подходит ни одно из указанных выше слов

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

3682 ege4 Передача с ошибками

По каналу связи с помощью равномерного двоичного кода передаются сообщения, содержащие только 4 буквы А, Б, В, Г. Каждой букве соответствует своё кодовое слово, при этом для набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех. Для кодирования букв Б, В, Г используются 5-битовые кодовые слова: Б: 00001, В: 01111, Г: 10110. 5-битовый код для буквы А начинается с 1 и заканчивается на 0. Определите кодовое слово для буквы А.

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

3681 ege4 Передача с ошибками

По каналу связи с помощью равномерного двоичного кода передаются сообщения, содержащие только 4 буквы П, Р, С, Т. Каждой букве соответствует своё кодовое слово, при этом для набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех. Для кодирования букв П, Р, С используются 5-битовые кодовые слова: П: 01111, Р: 00001, С: 11000. 5-битовый код для буквы Т начинается с 1 и заканчивается на 0. Определите кодовое слово для буквы Т.

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

Другие задачи ( 4 )

Длина кода с четным количеством единиц в коде; Задачи с битом четности (сумма … по модулю 2), изображения и т.д.


34 ege4 Другие задачи

Для передачи помехоустойчивых сообщений в алфавите, который содержит 16 различных символов, используется равномерный двоичный код. Этот код удовлетворяет следующему свойству: в любом кодовом слове содержится четное количество единиц (возможно, ни одной). Какую наименьшую длину может иметь кодовое слово?

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп


49 ege4 Другие задачи

Для передачи данных по каналу связи используется 5-битовый код. Сообщение содержит только русские буквы А, Б и В, которые кодируются следующими кодовыми словами: А — 11010, Б — 00110, В — 10101.

При передаче возможны помехи. Однако некоторые ошибки можно попытаться исправить. Любые два из этих трёх кодовых слов отличаются друг от друга не менее чем в трёх позициях. Поэтому если при передаче слова произошла ошибка не более чем в одной позиции, то можно сделать обоснованное предположение о том, какая буква передавалась. (Говорят, что «код исправляет одну ошибку».) Например, если получено кодовое слово 10110, считается, что передавалась буква Б. (Отличие от кодового слова для Б только в одной позиции, для остальных кодовых слов отличий больше.) Если принятое кодовое слово отличается от кодовых слов для букв А, Б, В более чем в одной позиции, то считается, что произошла ошибка (она обозначается ‘х’).
Получено сообщение 00111 11110 11000 10111. Декодируйте это сообщение.

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп


50 ege4 Другие задачи

Черно-белое растровое изображение кодируется построчно, начиная с левого верхнего угла и заканчивая в правом нижнем углу. При кодировании 1 обозначает темный цвет, а 0 – светлый.

Для компактности результат записали в восьмеричной системе счисления. Декодируйте сообщение

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп


42 ege4 Другие задачи

Для передачи чисел по каналу с помехами используется код проверки четности. Каждая его цифра записывается в двоичном представлении, с добавлением ведущих нулей до длины 4, и к получившейся последовательности дописывается сумма её элементов по модулю 2 (например, если передаём 23, то получим последовательность 0010100110). Определите, какое число передавалось по каналу в виде 01100010100100100110?

1) 6543
2) 62926
3) 62612
4) 3456

Обязательно укажите способ с вами: страница ВК, электронная почта, скайп

Источник

Понравилась статья? Поделить с друзьями:
  • Одного выдающегося геронтолога спросили то что положено у него спросить сочинение егэ
  • Одновременно ударение в слове егэ
  • Одноатомные спирты подготовка к егэ
  • Одноатомные спирты задания егэ
  • Одноатомные спирты егэ тест