Для кодирования используется таблица найдите все способы декодирования сообщения 1111001001100

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

Практические работы

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

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

Вариант 2:

Сообщение: 01011100101101 (Ответы: ААВААД, ААВГБА)

Корень

0 1

1

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

1. Выполняется ли для этой кодовой таблицы условие Фано? Обратное условие Фано? Почему?

Ответ:

Условие фано не выполняется, потому что код «А» является началом для кода «Г»
обратное условие фано не выполняетсяя, потому что код «А» является концом для кода «Д»

1. Найдите все способы декодирования сообщение, записанное под таблицей:

Ответ:

Источник

Урок 4
Кодирование и декодирование
§5. Язык и алфавит. §6. Кодирование

Содержание урока

§5. Язык и алфавит

§6. Кодирование

Задачи

§6. Кодирование

Задачи

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

.

2. Покажите с помощью дерева, что кодовая таблица из примера 2 удовлетворяет «обратному» условию Фано.

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

Найдите все способы декодирования сообщения 1111001011.

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

Найдите все способы декодирования сообщения 1111001001100.

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

Найдите все способы декодирования сообщения 1111001010.

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

Найдите все способы декодирования сообщения 01110011.

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

Декодируйте сообщение 0110100011000.

8. Для кодирования сообщения, состоящего только из букв А, В, С, D и Е, используется неравномерный двоичный код:

Какие из сообщений были переданы без ошибок:

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

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

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

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

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

Следующая страница §5. Язык и алфавит

Cкачать материалы урока

Источник

Уроки 7 — 8
Кодирование и декодирование
§5. Язык и алфавит. §6. Кодирование

Содержание урока

§5. Язык и алфавит

§6. Кодирование

Задачи

§6. Кодирование

Задачи

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

.

2. Покажите с помощью дерева, что кодовая таблица из примера 2 удовлетворяет «обратному» условию Фано.

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

Найдите все способы декодирования сообщения 1111001011.

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

Найдите все способы декодирования сообщения 1111001001100.

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

Найдите все способы декодирования сообщения 1111001010.

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

Найдите все способы декодирования сообщения 01110011.

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

Декодируйте сообщение 0110100011000.

8. Для кодирования сообщения, состоящего только из букв А, В, С, D и Е, используется неравномерный двоичный код:

Какие из сообщений были переданы без ошибок:

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

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

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

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

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

Следующая страница §5. Язык и алфавит

Cкачать материалы урока

Источник

Для кодирования используется таблица найдите все способы декодирования сообщения 1111001001100

Задания:

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

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

Из условия соответственно:
А — 00
Б — 01
В — 10
Г — 11
ГБАВ = 11010010 — переведем данную двоичную запись в шестнадцатеричную систему и получим D2
Ответ: 2

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

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

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

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

3) Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв — из двух бит, для некоторых — из трех). Эти коды представлены в таблице:
a b c d e
000 110 01 001 10
Определите, какой набор букв закодирован двоичной строкой 1100000100110
1) baade 2) badde 3) bacde 4) bacdb

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

Первая буква — b, так как стоит двоичный код 110
Вторая буква — a, так как стоит двоичный код 000
Третья буква — с, так как стоит двоичный код 01
Четвертая буква — d, так как стоит двоичный код 001
Пятая буква — e, так как стоит двоичный код 10
Итог: bacde, что соответствует варианту под номером 3.
Ответ: 3

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

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

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

Ответ: 2

5)

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

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

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

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

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

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

1000101010011011 2 = 105233 8

Ответ: 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 16 2) 4CB8 16 3) F15D 16 4) В9СА 16

Решение и ответ: соответственно..
A — 1001
B — 1010
C — 1011
D — 1100
Значит: CADB = 1011100111001010, переведем 1011100111001010 из двоичной в шестнадцатеричную:
1011 1001 1100 1010 2 = B9CA 16 , что соответствует четвертому варианту.
Ответ: 4

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

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

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

Ответ: 4

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

Решение и ответ:
ГАВБВГ = 0110001011010011 2 — Переведем в шестнадцатеричную систему:
0110 0010 1101 0011 2 = 62D3 16

Ответ: 1

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

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

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

Решение и ответ:
ГБВАВГ = 0111101000010011 2 — переведем в шестнадцатеричную.
0111 1010 0001 0011 2 = 7A13 16
Ответ: 4

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

ГАВБГВ = 0110001011011010 2 , переведем в шестнадцатеричную:
0110 0010 1101 1010 2 = 62DA 16
Ответ: 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 2 , переведем в шестнадцатеричную систему:
0100 0011 1101 1010 2 = 43DA 16
Ответ: 2

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

1, 3 и 4 варианты не подходят, являются началом других кодов.
2 вариант — не является началом других кодов.
Ответ: 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 2 , переведем данный код в восьмеричную:
101 011 100 001 010 2 = 53412 8

Ответ: 3

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

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

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

Пример 6 . Рассмотрим код

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

Следуя методу Ал.А. Маркова, построим граф следующим образом:

1. Определяем все последовательности (строки), которые
   а) совпадают с началом какого-то кодового слова и одновременно с концом какого-то кодового слова и
   б) сами не являются кодовыми словами.
   В данном случае это две последовательности:
   0 (начало кода буквы А и конец кода буквы Б) и
   1 (начало кода буквы Г и конец кода буквы Д);
   10 (начало кода буквы Д и конец кода буквы Б);
   последовательности 01 и 11 не учитываем, потому что они совпадают с кодами букв А и Г;
2. Добавляем к этому множеству <0, 1, 10>пустую строку, которую обычно обозначают греческой буквой Λ; элементы полученного множества <Λ, 0, 1, 10>будут вершинами графа:

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

Иначе говоря,

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

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

В нашем графе есть, по крайней мере, четыре таких цикла:

1. цикл «Λ0Λ», соответствующий сообщению ΛА0ГΛ = 01011; это сообщение может быть расшифровано как АВ и как БГ;
2. цикл «Λ1Λ», соответствующий сообщению ΛА1АΛ = 01101; это сообщение может быть расшифровано как АД и как ВА;
3. цикл «Λ01Λ», соответствующий сообщению ΛА01АΛ = 010101; это сообщение может быть расшифровано как ААА и как БД;
4. цикл «Λ0101Λ», соответствующий сообщению ΛА0101АΛ = 01010101; это сообщение может быть расшифровано как АБД и как БДА;

Кроме того, у вершины «1» есть петля, которая даёт более длинные циклы «из Λ в Λ». Действительно, проходя по стрелкам из вершины Λ, мы приходим в вершину 1, там «вертимся» какое-то количество раз, и возвращаемся обратно в вершину Λ, замыкая цикл. Поэтому неоднозначно декодируется любая последовательность вида 01…101, где многоточие обозначает любое количество единиц. Например, сообщение 0111101 может быть декодировано как АГД или ВГА.

Таким образом, код (6) не обладает свойством однозначной декодируемости.

Проверим таким же способом код (5), который, как мы уже выяснили, не является ни префиксным, ни постфиксным. Множество последовательностей, которые совпадают с началом и концом кодовых слов, состоит из пустой строки и единицы: <Λ, 1>. Граф, построенный с помощью приведённого выше алгоритма, содержит два узла и одну петлю:

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

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

Ещё примеры

Пример . Рассмотрим задачу А9 из демо-варианта КИМ ЕГЭ-2013 [1], которая сформулирована в начале статьи. Нужно оптимизировать код
выбрав один из вариантов
Решение . Сначала давайте посмотрим на исходный код, приведённый в условии. Можно заметить, что он префиксный — для него выполняется условие Фано: ни один из трехбитных кодов не начинается ни с 00 (код А), ни с 01 (код Б). Поэтому сообщения, закодированные с помощью такого кода, декодируются однозначно.

Заметим, что «обратное» условие Фано не выполняется: код буквы А (00) совпадает с окончанием кода буквы В (100), а код буквы Б (01) совпадает с окончанием кода буквы Г (101).

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

Остается убедиться, что варианты 3 и 4 не подходят. Если мы сократим код буквы Г до 10 (вариант 3), условие Фано оказывается нарушенным, так как теперь код буквы Г (10) совпал с началом кода буквы В (100). Одновременно нарушено и «обратное» условие Фано: код буквы А (00) совпадает с окончанием кода буквы В (100). Но, как мы знаем, при этом код может всё-таки быть однозначно декодируемым.

Конечно, можно построить граф, как было сделано выше, и проверить, есть ли в нём циклы, включающие вершину Λ. В данном случае граф выглядит так:

Здесь два цикла, проходящих через вершину Λ (не считая петли у вершины 0):

1. цикл, соответствующий сообщению ΛГ0Λ1АΛ = 100100; это сообщение может быть расшифровано как ГБА или как ВВ;
2. цикл, соответствующий сообщению ΛГ0Λ1ГΛ = 100110; это сообщение может быть расшифровано как ГБГ или как ВД.

Таким образом, вариант 3 не обеспечивает однозначную декодируемость сообщений.

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

Наконец, нужно убедиться, что вариант 4 не удовлетворяет условию. Если мы сократим код буквы Д до 10, условие Фано оказывается нарушенным, так как теперь код буквы Д (10) совпал с началом кода буквы В (100). Как и раньше, нарушено «обратное» условие Фано: код буквы А (00) совпадает с окончанием кода буквы В (100) и код буквы Б (01) совпадает с окончанием кода буквы Г (101).

Построим граф по методу Ал.А. Маркова:

Здесь два цикла, проходящих через вершину Λ (не считая петли у вершины 0):

1. цикл, соответствующий сообщению ΛД0Λ1АΛ = 100100; это сообщение может быть расшифровано как ДБА или как ВВ;
2. цикл, соответствующий сообщению ΛД0Λ1БΛ = 100101; это сообщение может быть расшифровано как ДББ или как ВГ.

Таким образом, вариант 4 также не соответствует условию. Поэтому правильный ответ — 1.

Пример . Оптимизируйте код
сохранив свойство однозначной декодируемости сообщений. Выберите один из вариантов:
Решение . Определим, за счёт чего обеспечивается однозначная декодируемость исходного кода. Легко видеть, что код префиксный — для него выполняется условие Фано: ни одно из трёхбитовых кодовых слов не начинается ни с 11 (код А), ни с 10 (код Б). В то же время, обратное условие Фано не выполняется, потому что код буквы А (11) совпадает с окончанием кода буквы В (011).

Проверим вариант 1 — сократим код буквы Г до 00. При этом нарушилось условие Фано, которое обеспечивало однозначную декодируемость исходного варианта: теперь код буквы Г (00) совпадает с началом кода буквы Д (001). Но и обратное условие Фано тоже не выполняется для пары букв А-В. Поэтому можно предположить, что такой код не обладает свойством однозначной декодируемости. И действительно, легко находится цепочка 001011, которую можно раскодировать как ГБА (00 10 11) или ДВ (001 011).

Рассмотрим вариант 3 — сократим код буквы В до 01. При этом условие Фано выполняется, поскольку ни одно из кодовых слов не начинается с 01, то есть код является префиксным и однозначно раскодируется. Это и есть правильный ответ.

На всякий случай проверяем вариант 4 — сокращает код буквы Б до 1. При этом код перестает быть префиксным, и обратное условие Фано также не выполнено (код буквы Б совпадает с началом и концом кода буквы А). Сразу понятно, что последовательность 11 можно раскодировать как А или как ББ, поэтому этот вариант неверный.

Источник

Вам также может понравиться

Ясень семена способ распространения

Ясень обыкновенный Fraxinus excelsior – так в ботанической

Ярлыки способы создания ярлыков ос windows

Создаем ярлыки на рабочем столе Windows Создаем ярлыки

Японское удобрение фуджима способ применения

Удобрения Фуджима Знаете потрясающее удобрение, палочка

Японский чай способ заварки

Технология заваривания японского чая Известно, что