для букв латинского алфавита заданы их двоичные коды для некоторых букв

infoegehelp.ru

Разбор задачи A13 (демо ЕГЭ 2005)

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

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

На графе розовым цветом выделены коды искомых букв.

На рисунке видно, что декодирование цепочки символов будет неоднозначным, т.к. идет дублирование (повторение) части кода другого символа. Например, в коде буквы E ( 01 1) дублируется код буквы B ( 01 ), а в коде буквы C ( 10 0) дублируется код буквы D ( 10 ).

При раскодировании последовательности будем стараться использовать буквы, код которых длиннее, чтобы быстрее рассмотреть всю последовательность. Например, если встретится последовательность 011, то сначала ее раскодируем как E. И если идущий дальше код раскодироваь нельзя, то вернемся обратно и выберем вместо E букву B. Также поступим с буквами C и D.

Анализ строки 0110100011000 происходит так:

1) берем первый символ. Он равен «0», поэтому смотрим граф с вершиной, равной «0»:

Видно, что в этом графе есть коды: 01, 000, 011.

2) берем второй символ. Он равен «1», поэтому идем по правой ветке: 0→01 (на рисунке розовая стрелка). Получаем код «01». Им закодирован символ «B».

Если взять следующий 3-й символ (он равен «1»), то пойдем по ветке 0→01→011 (на рисунке синие стрелки). Получится код «011». Им закодирована буква E.

Далее анализ снова начинаем с вершины графа

3)берем четвертый символ. Он равен «0», поэтому смотрим граф с вершиной, равной «0».

Видно, что в этом графе есть коды: 01, 000, 011.

4)берем пятый символ. Он равен «1», поэтому идем по правой ветке: 0→01 (на рисунке розовая стрелка). Получаем код «01». Им закодирован символ «B».

Надо проверить, даст ли следующий (шестой) символ букву E. Он равен «0», поэтому пойдем по ветке 0→01→010. Получится код 010. Следовательно, E не получим. Остановимся на букве B.

Далее анализ снова начинаем с вершины графа

5)снова берем шестой символ. Он равен «0», поэтому смотрим граф с вершиной, равной «0».

В таблицах ниже описан анализ всей строки:

Двоичная строка	011 01 000 110 00
Путь в графе до кода буквы	0→01→011	0→01	0→00→000	1
Двоичная строка, разбитая на коды букв	011	01	000	—
Буква	E	B	A	—

Т.к. строку раскодировать не удалось, то возвращаемся к букве E. Берем вместо » E «, букву » B «:

Двоичная строка	01 10 100 011 000
Путь в графе до кода буквы	0→01	1→10	1→10→100	0→01→011	0→00→000
Двоичная строка, разбитая на коды букв	01	10	100	011	000
Буква	B	D	C	E	A

Используем метод подстановки. Для этого приведенные варианты заменим двоичными кодами:

Источник

Для букв латинского алфавита заданы их двоичные коды для некоторых букв

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

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

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

Разобьём код слева направо по данным таблицы и переведём его в буквы:

110 000 01 001 10 — b a c d e.

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

Какой набор букв закодирован двоичной строкой 1000110110110? Все буквы в последовательности — разные.

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

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

1) 100 011 01 10 110

Первая буква определяется однозначно, её код 100: a.

Пусть вторая буква — с, тогда следующая буква — d, потом — e и b.

Такой вариант удовлетворет условию, значит, окончательно получили ответ: acdeb.

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

001001001111101

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

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

Будем пробовать различные варианты:

1) 011 11 100 0101100

Первая буква определяется однозначно, её код 011: D.

Вторая буква также определится однозначно — E.

Пусть третья буква B, тогда следующая начинается с кода 010, но таких букв в таблице нет, значит, предположение не верно.

2) 011 11 10 00 101 100

Третья буква — С, потом — A. Мы хотим получить ещё две буквы, чтобы в сумме их было 6, тогда следующая буква — F, и последняя — B.

Окончательно получили ответ: DECAFB.

Примечание. DECACEA не подходит, так как 7 букв.

так же подходит decacea

011 11 10 00 10 11 00

В задании спрашивается о последовательности из шести букв.

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

Из примера видно, что 2 знака кодируются 10 двоичными разрядами (битами), на каждую цифру отводится 5 бит. В условии сказано, что каждая цифра записывается кодом длиной 4 знака, значит, пятую цифру можно отбросить.

Разобьём двоичную запись на группы по 5 знаков: 01100 01010 01001 00110. Отбрасываем последнюю цифру в каждой пятёрке и переводим в десятичную запись:

0110 0101 0100 0011 — 6 5 4 3.

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

Для однозначного декодирования получившееся в результате сокращения кодовое слово не должно быть началом никакого другого. Второй вариант ответа не подходит, поскольку код буквы А является началом кода буквы В. Третий вариант не подходит, поскольку код буквы В является началом кода буквы Г. Четвёртый вариант ответа подходит.

Источник

Для букв латинского алфавита заданы их двоичные коды для некоторых букв

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

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

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

Разобьём код слева направо по данным таблицы и переведём его в буквы:

110 000 01 001 10 — b a c d e.

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

Какой набор букв закодирован двоичной строкой 1000110110110? Все буквы в последовательности — разные.

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

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

1) 100 011 01 10 110

Первая буква определяется однозначно, её код 100: a.

Пусть вторая буква — с, тогда следующая буква — d, потом — e и b.

Такой вариант удовлетворет условию, значит, окончательно получили ответ: acdeb.

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

001001001111101

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

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

Будем пробовать различные варианты:

1) 011 11 100 0101100

Первая буква определяется однозначно, её код 011: D.

Вторая буква также определится однозначно — E.

Пусть третья буква B, тогда следующая начинается с кода 010, но таких букв в таблице нет, значит, предположение не верно.

2) 011 11 10 00 101 100

Третья буква — С, потом — A. Мы хотим получить ещё две буквы, чтобы в сумме их было 6, тогда следующая буква — F, и последняя — B.

Окончательно получили ответ: DECAFB.

Примечание. DECACEA не подходит, так как 7 букв.

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

Из примера видно, что 2 знака кодируются 10 двоичными разрядами (битами), на каждую цифру отводится 5 бит. В условии сказано, что каждая цифра записывается кодом длиной 4 знака, значит, пятую цифру можно отбросить.

Разобьём двоичную запись на группы по 5 знаков: 01100 01010 01001 00110. Отбрасываем последнюю цифру в каждой пятёрке и переводим в десятичную запись:

0110 0101 0100 0011 — 6 5 4 3.

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

Для однозначного декодирования получившееся в результате сокращения кодовое слово не должно быть началом никакого другого. Второй вариант ответа не подходит, поскольку код буквы А является началом кода буквы В. Третий вариант не подходит, поскольку код буквы В является началом кода буквы Г. Четвёртый вариант ответа подходит.

Источник

Кодирование и декодирование информации. ЕГЭ

Задание:

1) Для кодирования букв А, Б, В, Г решили использовать двухразрядные последовательные двоичные числа (от 00 до 11 соответственно). Если таким способом закодировать последовательность символов ГБАВ и записать результат в шестнадцатеричной системе счисления, то получится:
1) 132 ₁₆ 2) D2 ₁₆ 3) 3102 ₁₆ 4) 2D ₁₆

Решение и ответ:

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

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

Решение и ответ:

По условию:
А = 00
Б = 01
В = 10
Г = 11
Значит:
ГБВА = 11011000 в двоичной системе. Переведем в шестнадцатеричную и получим D8
Ответ: 3

Решение и ответ:

4) Для кодирования букв А, Б, В, Г используются четырехразрядные последовательные двоичные числа от 1000 до 1011 соответственно. Если таким способом закодировать последовательность символов БГАВ и записать результат в восьмеричном коде, то получится:
1) 175423 2) 115612 3) 62577 4) 12376

Решение и ответ:

По условию:
А = 1000
Б = 1001
В = 1010
Г = 1011
БГАВ = 1001101110001010, теперь слудует перевести данное число из двоичной в восьмеричную, и получить ответ.
1001101110001010₂ = 115612₈

Ответ: 2

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

Решение и ответ:

По условию: Соответственно
A = 100
B = 101
C = 110
D = 111
СDAB = 110111100101, переведем двоичное число в шестнадцатеричную:
110111100101₂ = DE5₁₆
Ответ: 4

6) Для кодирования букв К, L, М, N используются четырехразрядные последовательные двоичные числа от 1000 до 1011 соответственно. Если таким способом закодировать последовательность символов KMLN и записать результат в восьмеричном коде, то получится:
1) 84613₈ 2) 105233₈ 3) 12345₈ 4) 776325₈

Решение и ответ:

По условию: соответственно
K = 1000
L = 1001
M = 1010
N = 1011
KMLN = 1000101010011011, переведем в восьмеричное число:

Ответ: 2

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

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

Решение и ответ:

Запишем двоичный код в виде битов: Методом перебора возможных вариантов, чтобы не повторялись буквы.
Получается: 100 011 01 10 110
Следовательно: acdeb
Ответ: 2

8) Для 6 букв латинского алфавита заданы их двоичные коды (для некоторых букв из двух бит, для некоторых – из трех). Эти коды представлены в таблице:
А В С D Е F
00 100 10 011 11 101
Определите, какая последовательность из 6 букв закодирована двоичной строкой 011111000101100.
1) DEFBAC 2) ABDEFC 3) DECAFB 4) EFCABD

Решение и ответ:

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

Получаем:
011 11 10 00 101 100
Соответственно: DECAFB
Ответ: 3

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

10) Для кодирования сообщения, состоящего только из букв А, Б, В и Г, используется неравномерный по длине двоичный код:
А Б В Г
00 11 010 011
Если таким способом закодировать последовательность символов ВГАГБВ и записать результат в шестнадцатеричном коде, то получится:
1) CDADBC₁₆ 2) A7C4₁₆ 3) 412710₁₆ 4) 4С7А₁₆

Решение и ответ:

ВГАГБВ = 0100110001111010, переведем в шестнадцатеричную:
0100 1100 0111 1010₂ = 4C7A₁₆

Ответ: 4

11) Для кодирования сообщения, состоящего только из букв А, Б, В и Г, используется неравномерный по длине двоичный код:
А Б В Г
00 11 010 011
Если таким способом закодировать последовательность символов ГАВБВГ и записать результат в шестнадцатеричном коде, то получится:
1) 62D3₁₆ 2) 3D26₁₆ 3) 31326₁₆ 4) 62133₁₆

Ответ: 1

12) Для кодирования сообщения, состоящего только из букв А, Б, В и Г, используется неравномерный по длине

двоичный код:
А Б В Г
00 11 010 011
Если таким способом закодировать последовательность символов ГБВАВГ и записать результат в шестнадцатеричном

коде, то получится:
1) 71013₁₆ 2) DBCACD₁₆ 3) 31A7₁₆ 4) 7A13₁₆

13) Для кодирования сообщения, состоящего только из букв А, Б, В и Г, используется неравномерный по длине двоичный код:
А Б В Г
00 11 010 011
Если таким способом закодировать последовательность символов ГАВБГВ и записать результат в шестнадцатеричном коде, то получится:
1) DACBDC₁₆ 2) AD26₁₆ 3) 621310₁₆ 4) 62DA₁₆
Решение и ответ: соответственно..

ГАВБГВ = 0110001011011010₂, переведем в шестнадцатеричную:
0110 0010 1101 1010₂ = 62DA₁₆
Ответ: 4

14) Для кодирования сообщения, состоящего только из букв A, B, C, D и E, используется неравномерный по длине двоичный код:
A B C D E
000 11 01 001 10
Какое (только одно!) из четырех полученных сообщений было передано без ошибок и может быть раскодировано:
1) 110000010011110
2) 110000011011110
3) 110001001001110
4) 110000001011110

Решение и ответ:

Возьмем первый код:
11 000 001 001 11 10 = BADDBE
Второй код:
11 000 001 10 11 110 = с ошибкой в конце.
Третий код:
11 000 10 01 001 110 = с ошибкой в конце.
Четвертый код:
11 000 000 10 11 110 = с ошибкой в конце.
Ответ: 1

15) Для передачи по каналу связи сообщения, состоящего только из символов А, Б, В и Г используется посимвольное

кодирование: А-00, Б-11, В-010, Г-011. Через канал связи передается сообщение: ВАГБГВ. Закодируйте сообщение

данным кодом. Полученную двоичную последовательность переведите в шестнадцатеричный вид.
1) AD34 2) 43DA 3) 101334 4) CADBCD
Решение и ответ:

ВАГБГВ = 0100001111011010₂, переведем в шестнадцатеричную систему:
0100 0011 1101 1010₂ = 43DA₁₆
Ответ: 2

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

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

Аналогично заданию номер 16.

Ответ: 2

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

Для компактности результат записали в восьмеричной системе счисления. Выберите правильную запись кода.
1) 57414 2) 53414 3) 53412 4) 53012

Решение и ответ:
После кодирования мы получаем данный код:

101011100001010₂, переведем данный код в восьмеричную:
101 011 100 001 010₂ = 53412₈

Ответ: 3

19) Для передачи по каналу связи сообщения, состоящего только из символов А, Б, В и Г используется посимвольное

кодирование: А-0, Б-11, В-100, Г-011. Через канал связи передается сообщение: ГБАВАВГ. Закодируйте сообщение

данным кодом. Полученную двоичную последовательность переведите в восьмеричный код.
1) DBACACD 2) 75043 3) 7A23 4) 3304043
Решение и ответ: Соответственно:
ГБАВАВГ = 0111101000100011₂, переведем в восьмеричную систему.
0 111 101 000 100 011₂ = 75043₈, первый нолик не значащий.
Ответ: 2

20) Для передачи данных по каналу связи используется 5-битовый код. Сообщение содержит только

буквы А, Б и В, которые кодируются следующими кодовыми словами:

A — 11010, Б — 00110, В — 10101.

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

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

1) БААx
2) БААВ
3) xxxx
4) xAAx

Решение:
1) 00111 = Б, так как 1 ошибка в последней цифре.
2) 11110 = A, так как 1 ошибка в третьей цифре.
3) 11000 = А, так как 1 ошибка в четвертой цифре.
4) 10111 = В, так как 1 ошибка в четвертой цифре

00111 11110 11000 10111 = БААВ.
Ответ: 2

Источник

Декодирование двоичных кодов в буквенные сообщения

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

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

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

Разбиваем двоичную строку на части (слева направо) с помощью данной в условии таблицы и переписываем ее, заменяя кодовые слова на буквы: 011|00|010|10|11 = debac.

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

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

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

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

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

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

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

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

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

Разбиваем двоичную строку на части (справа налево) с помощью данной в условии таблицы и переписываем, заменяя кодовые слова на буквы: 001|00|010|110|11|101 = cdebaf.

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

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

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

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

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

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

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

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

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

Чтобы выяснить двоичный код буквы e, построим граф. Так как обратное условие Фано должно выполняться, кодовое слово любой буквы не должно являться концом кодового слова другой. Значит, строим граф ”с конца” кодового слова (то есть читаем значения задом наперед: a: 01 \(\rightarrow\) 10, b: 110 \(\rightarrow\) 011, c: 00 \(\rightarrow\) 00, d: 010 \(\rightarrow\) 010).

Из графа видно, что кодовое слово минимальной длины, удовлетворяющее обратному условию Фано, – 11. Значит, кодовое слово буквы e – 11.

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

Разбиваем двоичную строку на части (справа налево) с помощью данной в условии таблицы и переписываем, заменяя кодовые слова на буквы: 00|010|01|11|110 = cdaeb.

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

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

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

Чтобы выяснить двоичный код буквы f, построим граф. Так как условие Фано должно выполняться, кодовое слово любой буквы не должно являться началом кодового слова другой. Значит, строим граф ”с начала” кодового слова.

Из графа видно, что кодовое слово минимальной длины, удовлетворяющее условию Фано, – 000. Значит, кодовое слово буквы f – 000.

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

Разбиваем двоичную строку на части (слева направо) с помощью данной в условии таблицы и переписываем строку, заменяя кодовые слова на буквы: 100|000|001|01|101|11 = cfebad.

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

Кодовое буквы d такое, что оно должно быть минимально возможной длины и кодовое слово буквы b должно являться началом этого кодового слова.

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

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

Из графа видно, что кодовое слово минимальной длины, началом которого является кодовое слово буквы b, – 01. Значит, кодовое слово буквы d – 01.

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

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

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

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

Источник