По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У; для передачи используется неравномерный двоичный код. Для девяти букв используются…
- 1
Проверяем кодовые слова меньшей длины. Код длины 1 невозможен, так как 0 и 1 являются началами существующих кодов.
- 2
Коды длины 2 также невозможны: 00 уже занято, 01 является началом кодов 010 и 011, 10 — началом кодов 1000, 1001 и 101, а 11 — началом кодов 1100, 1101 и 1110.
Ещё 2 шага — в полном решении
Световое табло состоит из лампочек, каждая из которых может находиться в двух состояниях («включено» или «выключено»). Какое наименьшее количество лампочек должно находиться на табло, чтобы с его…
- 1
Каждая лампочка имеет два состояния, поэтому $n$ лампочек могут образовать $2^n$ различных комбинаций.$$N = 2^n$$
- 2
Найдём минимальное $n$, при котором число комбинаций не меньше 50: $2^5 = 32 < 50$, а $2^6 = 64 \geq 50$.$$n = 6$$
По каналу связи передаются шифрованные сообщения, содержащие только 10 букв: А, Б, Е, И, К, Л, Р, С, Т, У; для передачи используется неравномерный двоичный код. Для девяти букв используются кодовые…
- 1
Кодовое слово для буквы С не может быть длины 1: слова $0$ и $1$ были бы началами других кодовых слов.
- 2
Слова длины 2 также не подходят: $00$ уже занято, а $01$, $10$ и $11$ являются началами известных кодовых слов.
Ещё 2 шага — в полном решении
По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У; для передачи используется неравномерный двоичный код. Для девяти букв используются…
- 1
Кодовое слово для буквы К не может быть началом уже заданного кодового слова. Поэтому слова $0$ и $1$ невозможны, так как являются началами других кодов.
- 2
Двухбитные варианты также невозможны: $00$, $01$, $10$ и $11$ либо уже заняты, либо являются началами существующих кодовых слов.
Ещё 2 шага — в полном решении
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г использовали…
- 1
Кодовые слова 00 и 01 занимают всю ветвь, начинающуюся с 0, а слова 100 и 101 — две ветви после 10.
- 2
Код 11 длины 2 использовать для буквы Д нельзя: после него не останется отдельной ветви для кодового слова буквы Е, не нарушающего условие Фано.
Ещё 2 шага — в полном решении
По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв…
- 1
Построим двоичное дерево кодов. Кодовые слова 00 и 01 полностью занимают ветви, начинающиеся с 0.
- 2
В ветви, начинающейся с 1, слова 1000 и 1001 занимают подветвь 100, а слова 110 и 111 — подветви 11. Единственная свободная ветвь — 101.
Ещё 2 шага — в полном решении
Для кодирования некоторой последовательности, состоящей из букв $A$, $B$, $C$, $D$, $E$, $F$, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы $A$ использовали…
- 1
Кодовые слова $0$ и $10$ являются листьями дерева кодирования, поэтому продолжать их нельзя. Для букв $C$, $D$, $E$, $F$ остаётся ветвь, начинающаяся с $11$.
- 2
Четыре кодовых слова можно разместить на минимальной одинаковой глубине: $1100$, $1101$, $1110$, $1111$. Все они удовлетворяют условию Фано.$$|1100|=|1101|=|1110|=|1111|=4$$
Ещё 1 шаг — в полном решении
По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Какое наименьшее количество…
- 1
Рассмотрим свободные ветви двоичного дерева. Кодовое слово 101 уже занято, поэтому в ветви 10 можно использовать слово 100 длины 3.
- 2
Ветвь 11 свободна полностью, поэтому для второй буквы можно взять кодовое слово 11 длины 2. Эти слова не являются началами друг друга и не нарушают условие Фано.$$l_1 + l_2 = 3 + 2 = 5$$
Ещё 1 шаг — в полном решении
По каналу связи передаются шифрованные сообщения, содержащие только 10 букв: А, Б, Е, И, К, Л, Р, С, Т, У. Для передачи используется неравномерный двоичный код. Для девяти букв уже заданы кодовые…
- 1
Кодовое слово для буквы Т не должно начинаться с 00, 010, 011, 1000, 1001, 1010, 1011, 110 или 1110, поскольку тогда одно из существующих слов было бы началом нового.
- 2
Слова длины 1 и 2 невозможны: 0 и 1 являются началами существующих слов, а все варианты длины 2 заняты или имеют заданные продолжения.
Ещё 2 шага — в полном решении
По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У; для передачи используется неравномерный двоичный код. Для девяти букв используются…
- 1
Слова $0$ и $1$ не подходят, поскольку являются началами нескольких заданных кодовых слов.
- 2
Слова длины 2 и 3 также не подходят: $00$, $01$, $10$ и $11$ либо уже заняты, либо являются началами существующих кодовых слов; их продолжения тоже нельзя использовать.
Ещё 2 шага — в полном решении
Для кодирования растрового рисунка, напечатанного с использованием шести красок, применили неравномерный двоичный код. Укажите кратчайшее кодовое слово для кодирования красного цвета, при котором…
- 1
Кодовое слово 0 уже используется, поэтому любое слово, начинающееся с 0, нарушит условие Фано.
- 2
Кодовое слово 10 уже используется, поэтому слова 100 и 101 не подходят: слово 10 было бы их началом.
Ещё 2 шага — в полном решении
По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Какое наименьшее количество…
- 1
Размещаем известные кодовые слова в двоичном дереве: $10$, $011$, $110$ и $1110$. Ни одно новое слово не может иметь уже использованное слово своим началом и само не может быть началом другого слова.
- 2
Наиболее короткий набор из четырёх свободных листьев можно выбрать как $000$, $001$, $010$ и $1111$. Все эти слова удовлетворяют условию Фано.
Ещё 1 шаг — в полном решении
По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г; для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв Б, В, Г используются такие кодовые…
- 1
Кодовое слово для буквы А не может начинаться с 0, поскольку 0 уже является кодовым словом для буквы Г.
- 2
Слова 10 и 11 также не подходят: 10 является началом кодового слова 101, а 11 — началом кодового слова 110.
Ещё 1 шаг — в полном решении
По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв…
- 1
По условию Фано ни одно кодовое слово не может быть началом другого. Кодовые слова 10 и 11 занимают обе ветви после первого знака 1.
- 2
Кодовые слова 010 и 011 занимают обе ветви после префикса 01. Поэтому четыре оставшихся кодовых слова должны располагаться в поддереве с префиксом 00.
Ещё 2 шага — в полном решении
Для кодирования последовательности из букв К, Л, М, Н, П, Р используют неравномерный двоичный код, удовлетворяющий условию Фано. Для букв К, Л, М, Н соответственно использованы кодовые слова 000…
- 1
Кодовое слово длины 1 не подходит: 0 является началом слов 000, 001 и 010, а 1 является началом слова 11.
- 2
Проверим слова длины 2. Слова 00 и 01 являются началами уже заданных кодовых слов, а слово 11 совпадает с уже использованным кодовым словом.
Ещё 2 шага — в полном решении
По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв…
- 1
Проверим двузначные кодовые слова. Код 00 уже занят, 01 является началом кодов 010 и 011, 10 является началом кодов 1000 и 1001, а 11 является началом кода 111.
- 2
На следующем уровне свободными являются ветви 101 и 110. Они не являются началами известных кодов и не являются началами друг друга, поэтому их можно назначить буквам Ж и З.
Ещё 1 шаг — в полном решении
По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У; для передачи используется неравномерный двоичный код. Для девяти букв используются…
- 1
Проверим кодовые слова длины 1. Коды 0 и 1 недопустимы, поскольку являются началами уже заданных кодовых слов.
- 2
Проверим коды длины 2: 00 уже занято, 01 является началом кодов 010 и 011, 10 является началом кодов 1000, 1001 и 1011, 11 является началом кодов 1101 и 111.
Ещё 2 шага — в полном решении
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г использовали…
- 1
Кодовые слова 000 и 001 занимают две ветви, начинающиеся с 00, а слова 10 и 11 — обе ветви, начинающиеся с 1.
- 2
Единственная свободная ветвь минимальной длины — 01. Однако если присвоить 01 букве Д, то любое кодовое слово для Е, начинающееся с 01, будет иметь 01 своим началом, что нарушит условие Фано.
Ещё 1 шаг — в полном решении
По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У. Для передачи используется неравномерный двоичный код. Для девяти букв используются…
- 1
Проверим кодовые слова малой длины. Код длины 1 невозможен, так как $0$ и $1$ являются началами существующих слов.
- 2
Коды длины 2 также невозможны: $00$ уже занято, а $01$, $10$ и $11$ являются началами существующих кодовых слов.
Ещё 2 шага — в полном решении
Для кодирования растрового рисунка, напечатанного с использованием шести красок, применили неравномерный двоичный код. Для кодирования цветов используются кодовые слова. Укажите кратчайшее кодовое…
- 1
Код синего цвета не может начинаться с $0$, так как код $0$ уже является кодовым словом белого цвета.
- 2
Код $1$ невозможен, поскольку он был бы началом кодов $10$, $1110$, $11110$ и $11111$.
Ещё 2 шага — в полном решении