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

4.03 Общая длина кода

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела кодирование и декодирование – условие фано

Решаем задачи

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

Задача 1#30050

Мистер Крабс решил закодировать рецепт Крабсбургера двоичным кодом, удовлетворяющим условию Фано. Известно, что в рецепте содержится 136 букв и все кодовые слова имеют одинаковую длину. Определите длину кодового слова.

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

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

Чтобы закодировать 2 буквы двоичным кодом с минимальным количеством символов, нам потребуется всего 2 цифры - 1 и 0. Чтобы закодировать 3 или 4 буквы - уже нужно будет 4 кода: 00, 01, 10, 11, при условии, что их длина должна быть одинаковой. Аналогично для большего числа букв.

Таким образом, получаем формулу $n−1 n 2 < I ≤ 2$ , где $I$ - количество символов, которые надо закодировать, а $n$ - длина одного кодового слова.

Подставляем значения из задачи $2n−1 < 136 ≤ 2n ⇒ n = 8$ .

Ответ: 8

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

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

Задача 2#50668

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

Какова минимальная общая длина кодовых слов для всех пяти букв?

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

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

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

Не важно каким образом мы расставим буквы на свободные позиции, так как от этого сумма длин кодов не изменится: $1 + 2+ 3+ 4 + 4 = 14$ .

Ответ: 14

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

Задача 3#54917

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

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

Построим дерево Фано и увидим, что есть три свободные ветки – 11, 100 и 011. Нам нужно найти кодовые слова для четырёх букв - Ф, А, Р, У. Причём буква А встречается в слове ФАРТУНА дважды. Продлим ветвь 11 и любую из ветвей 100 или 011. Букве А присвоим код длины 3, букве Ф – длины 3, букве Р – длины 4 и букве У – длины 3.

Общая длина последовательности ФАРТУНА: $3+ 3+ 4 + 3+ 3+ 2+ 3 = 21$ .

Ответ: 21

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

Задача 4#55056

По каналу связи передаются сообщения, содержащие только буквы слова М А Н Г. Для передачи используется двоичный код, удовлетворяющий условию Фано. Для буквы М используется кодовое слово 00; для буквы Н используется кодовое слово 1.

Какое наименьшее количество двоичных знаков потребуется для кодирования слова МАНГА?

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

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

Построим дерево Фано, из которого очевидно, что свободное место только одно – 01. Но нам нужно закодировать ещё две буквы, А и Г, поэтому пустим ветки из этого места. Теперь имеется 2 свободных позиции, нам не важно каким образом мы расставим буквы на свободные позиции, так как от этого сумма длин кодов не изменится: 2+3+1+3+3 = 12.

Ответ: 12

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

Задача 5#56305

Для передачи слова АМБИДЕКСТР решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Известно, что у букв А, Р кодовые слова соответственно равны $010$ , $11$ . Коды остальных букв имеют одинаковую длину. Какова минимальная суммарная длина всех кодовых слов у букв передаваемого слова?

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

$PIC$

Тогда $3+ 4 +4 + 4+ 4+ 4 + 4+ 4+ 4 +2$ = $37$

Ответ: 37

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

Задача 6#56952

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

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

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

Найдём кодовые слова для букв D, E, F. Мы не можем брать слова, начинающиеся с нуля, так как это кодовое слово занято буквой С, поэтому рассмотрим слова, начинающиеся с единицы. Нам нужно добавить разряд в свободное кодовое слово — 100. Добавляем и получаем два свободных кодовых слова — 1000 и 1001. Так как нам нужно закодировать три буквы, то необходимо увеличить количество разрядов в одном из чисел. Соответственно, для буквы D возьмём кодовое слово 1000, для E — 10010, а для F — 10011.

Складываем длины имеющихся слов и получаем ответ: $2 + 3+ 1+ 4 + 5+ 5 = 20$ .

Ответ: 20

Курсы

Всё необходимое для достижения цели

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

Задача 7#56953

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

Какова минимальная общая длина кодовых слов для всех пяти букв?

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

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

Так как нужно закодировать три оставшиеся буквы, нам необходимо подобрать три кодовых слова. Для буквы Ш мы можем взять кодовое слово 110, для К – 1110, а для Л – 1111.

Складываем длины имеющихся слов и получаем ответ: 1+2+3+4+4 = 14

Ответ: 14

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

Задача 8#56954

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

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

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

Нам уже известны длины букв А, Б и В, теперь необходимо подобрать кодовые слова для Г, Д, Е. У нас имеется два свободных кодовых слова — 100 и 111. Так как нужно закодировать три буквы, нужно три свободных кодовых слова. Для этого добавляем разряд в любое из них и получаем два кодовых слова с длиной 4. Таким образом, для Г мы можем взять кодовое слово 100, для Д — 1110, а для Е — 1111. Складываем длины имеющихся слов и получаем ответ: $1 + 4+ 4+ 3+ 3 + 3 = 18$

Ответ: 18

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

Задача 9#57270

По каналу связи передаются сообщения, содержашие только шесть букв: М, О, Щ, Н, Ы, Й. Для передачи используется двоичный код, удовлетворяющий условию Фано. Для буквы Й используется кодововое слово 01; для буквы О используется кодовое слово 10.

Какова минимальная общая длина кодовых слов для всех шести букв?

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

Построим деревья для значений 0 и 1. Как мы знаем, Й это 01, а О это 10. Построим продолжения для значений 00 и 11.

Мы получили значения 000,001,110,111. Каждой оставшейся букве присвоим одно из кодовых слов.

Минимальная длина для всех шести букв будет равна: $4∗ 3+ 2∗ 2 = 16$ . Ответ: 16.

Ответ: 16

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

Задача 10#59323

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

Какова минимальная общая длина кодовых слов для всех пяти букв?

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

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

Не важно каким образом мы расставим буквы на свободные позиции, так как от этого сумма длин кодов не изменится: 1+2+3+4+4 = 14.

Ответ: 14

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

Задача 11#61620

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

Известно что слово ABCBD закодировано последовательностью 00111101111100. Какая наименьшая возможная по длине кодировка слова DBAEC?

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

Последовательность 00111101111100 раскодируется:

A – 00

B – 111

C – 101

D – 100

Минимальная длина кодового слова для буквы Е, удовлетворяющее условию Фано, равна 2 (то есть, 01). Получаем длину слова DBAEC:

3 + 3+ 2+ 2 +3 = 13

Ответ: 13

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

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

Задача 12#62475

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

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

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

Найдём коды, подходящие для букв Т, В и А. Так как кодовое слово 0 уже есть, то продолжать ветвь в дереве Фано из 0 мы не можем. Получается, что три кода с минимальной длиной, подходящие под условие Фано, равны 111, 100 и 110. Длина каждого из них равна 3. Тогда итоговая длина двоичного кода будет равна: $3 + 3+ 3+ 3+ 1 = 13$ .

Ответ: 13

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

Задача 13#62480

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

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

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

После построения дерева Фано можно заметить, что свободными остаются ветви 111, 10 и 001. Однако, у нас остались незакодированными 4 буквы - В, Д, Е, Н, т.е. четыре буквы. Так как буква Е встречается в слове 3 раза, то присвоим ей код длины 2. Буква В встречается в слове 2 раза - ей присвоим код длины 3. Продолжим ветвь 001 до 0010 и 0011. Тогда буквы Д и Н будут закодированы кодами длиной 4. Тогда итоговая длина всех семи кодовых слов равна: $3 + 3+ 2+ 4+ 2 + 4+ 2+ 3 = 23$

Ответ: 23

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

Задача 14#63236

По каналу связи передаются сообщения, содержащие только буквы Е, Ж, К, Й, О, Ф. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для букв известны: К: 00; Ж: 111; О: 100; Ф: 101.

Укажите наименьшую возможную длину закодированной последовательности для слова ЖОКЕЙ.

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

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

После построения дерева Фано можно заметить, что минимальными кодами, при которых не нарушится условие Фано, являются 01 и 110. Так как все буквы в слове ЖОКЕЙ повторяются одинаковое количество раз, то нам неважно, какой букве присваивать код. Пусть буква Е имеет код 01, буква Й - 110.

Тогда, длина последовательности равна $3+ 3 +2 + 2+ 3 = 13$

Ответ: 13

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

Задача 15#63823

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

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

После составления дерева Фано остается 2 свободных листа: 00 и 11, а букв которые нужно закодировать остается 5. Можно пойти по 2 путям:

1) оба листа раздвоить, получим 4 свободных позиции и один из них еще раздвоить, получим 5 свободных позиций;

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

При первой схеме длина всех кодовых слов равна $2 ⋅2+ 3⋅3 + 2⋅4 = 21$ .

При второй длина всех кодовых слов равна $3⋅2 + 4⋅4 = 22$ .

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

Ответ: 21

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

Задача 16#63911

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

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

Нарисуем дерево Фано. Свободными кодами окажутся: 00, 010 и 100. Так как нам нужно закодировать еще 4 буквы, а кодов всего 3, то необходимо одну из ветвей раздвоить. Перед этим поймем какие буквы нам осталось закодировать и как часто они встречаются в требуемой последовательности.

Б - не встречается, К - встречается дважды, Т - встречается один раз, Р - не встречается.

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

Тогда получаем $2+ 3+ 3 + 2+ 2 = 12$ .

Ответ: 12

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

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

Задача 17#87469

По каналу связи передаются сообщения, содержащие только десять букв: А, Б, В, Г, Д, Е, Ж, З, И, К. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 001, Б — 010, В — 1000, Г — 1001, Д — 11, Е — 0110.

Какое наименьшее количество двоичных знаков потребуется для кодирования четырёх оставшихся букв? В ответе запишите суммарную длину кодовых слов для букв: Ж, З, И, К.

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

Построим дерево Фано для известных букв. У нас остается 3 свободных ветви: 101, 0111 и 000. Но оставшихся букв четыре: Ж, З, И, К. Значит, продлим ветвь минимальной длины, например, код 000 представим в виде 0000 и 0001. Теперь все буквы заполнены кодами. Итоговая длина кодов оставшихся четырех букв равна: $4 + 4+ 4+ 3 = 15$ .

Ответ: 15

Предыдущий раздел

Следующий раздел