Для кодирования сообщения используется таблица1 Вариант 1:
А Б В Г Д
10 11 001 010 01
Сообщение: 0101110010110 (ответы: ГБАДДА, ДДБВДА)
1) Используя средства текстового процессора, изобразите 6двоичное дерево, соответствующее этому коду.
2. Выполняется ли для этой кодовой таблицы условие Фано? Обратное условие Фано? По-чему?
ответ:
3) Найдите все декодирования сообщение, записанное под таблицей:
ответ:
Проверьте свой ответ с программы decode.
4. Замените код одного символа так, чтобы выполнилось условие Фано (или обратное условие Фано). Выделите зеленым фоном ячейку таблицы с измененным кодом символа.
5. Сократите код одного символа в таблице, полученной в п. 4 так, чтобы условие Фано (или обратное условие Фано) по-прежнему выполнялось. Выделите фиолетовым фоном ячейку таблицы с измененным кодом символа.
ПОСТАВЛЮ ЛУЧШУЮЮ ОТМЕТКУ
```
А (10)
/ \
Г (010) В (001)
/ \ / \
Д (01) А (01) Д (01) А (01)
```
2) Для проверки выполнения условия Фано необходимо проверить, что ни один код символа не является началом другого кода символа. Аналогично, для проверки обратного условия Фано необходимо проверить, что ни один код символа не является подстрокой другого кода символа.
Для данной таблицы кодирования, условие Фано выполняется. Ни один код символа не является началом или подстрокой другого кода символа. Например, код Г (010) не является началом кода Д (01) и не является подстрокой кода В (001). Таким образом, наша таблица удовлетворяет условию Фано.
3) Чтобы найти все декодирования данного сообщения (0101110010110), необходимо последовательно разбить его на непересекающиеся фрагменты, соответствующие кодам символов в таблице.
В данном случае возможны два декодирования:
- ГБАДДА (010 11 1001 0 110 1 0)
- ДДБВДА (01 0111 0010 11 0)
4) Чтобы заменить код одного символа так, чтобы выполнилось условие Фано, нужно выбрать код, который является началом или подстрокой другого кода символа. В данной таблице все коды удовлетворяют условию Фано, поэтому необходимость в замене отсутствует.
5) Чтобы сократить код одного символа так, чтобы выполнилось условие Фано, нужно найти код символа, который является подстрокой другого кода символа, и удалить его. В данной таблице такого символа нет, поэтому сократить код не получится.