Отправлено: 06.04.15 19:12. Заголовок: Для кодирования неко..

Для кодирования некоторой последовательности, состоящей из букв А, Б, В,
Г и Д, используется неравномерный двоичный код, позволяющий однозначно
декодировать полученную двоичную последовательность. Вот этот код:
А – 00; Б – 101; В – 011; Г – 111; Д – 110. Требуется сократить для одной из
букв длину кодового слова так, чтобы код по-прежнему можно было
декодировать однозначно. Коды остальных букв меняться не должны.
Каким из указанных способов это можно сделать?
1) это невозможно
2) для буквы Б – 01
3) для буквы В – 01
4) для буквы Г – 11

Задание 1 вариант 2 от 01. 04.
В этом задании не понятно какой признак Фано работает: прямой или обратный, так ни оно число не является ни началом, ни концом другого слова. Можно предположить, что одновременно работают оба условия Тогда новое число Б=01 совпадает с началом числа В. Это нам не подходит. Новое число В=01 будет являться окончанием числа Б. Тоже не подходит. Новое Г=11 является началом Д и, одновременно, окончанием В. Значит, ответ: это не возможно.
При проверке ответ правильный 3), т.е. имеется в виду прямое условие Фано. Но как это можно определить по предоставленным данным?
В чем я не права? Пожалуйста, подскажите!

 Отправлено: 06.04.15 19:43. Заголовок: Давайте посмотрим на..

Давайте посмотрим на исходный код:

цитата:

А – 00; Б – 101; В – 011; Г – 111; Д – 110.

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

Вот еще важная мысль:

цитата:

Для однозначной декодируемости сообщений достаточно выполнения ОДНОГО из двух условий Фано.

Это значит, что если, допустим, сохранить прямое условие Фано, то можно спокойно нарушить обратное, однозначная декодируемость не пострадает.

Теперь смотрим на варианты упрощения кода. Вариант 2, Б - 01. При этом нарушится прямое условие Фано (код буквы В начинается с 01), но сохранится обратное - ни одно другое кодовое слово не заканчивается на 01. Поэтому код однозначно декодируется, вариант подходит.

Вариант 3, В - 01. При этом нарушится обратное условие Фано (код буквы Б заканчивается на 01), но сохранится прямое - ни одно другое кодовое слово не начинается с 01. Поэтому код однозначно декодируется, вариант подходит.

Вариант 4, Г - 11. При этом нарушится и прямое условие Фано (код буквы Д начинается с 11), и обратное (код буквы В заканчивается на 11), вариант НЕ подходит.

Таким образом, здесь два правильных ответа, 2 и 3.

 Отправлено: 06.04.15 21:34. Заголовок: Спасибо большое. А ..

Спасибо большое. А все таки можно ли считать ответ 3)Это невозможно, подразумевая, что речь может идти как раз о том, что должны сработать оба условия. помнится, мне где-то попадались такие задания.

 Отправлено: 06.04.15 21:40. Заголовок: ИЮГ пишет: подразум..

ИЮГ пишет:

цитата:

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

Я еще раз подчеркну, что для обеспечения однозначной декодируемости НЕ НУЖНО обеспечивать оба условия Фано, достаточно одного из двух, любого. Поэтому ответ "невозможно" - неверный. Однозначно.

 Отправлено: 06.04.15 22:16. Заголовок: Еще раз спасибо. ..

Еще раз спасибо.

 Отправлено: 21.04.15 12:35. Заголовок: В сообщении встреча..

В сообщении встречается 7 разных букв. При его передаче использован неравномерный двоичный код, удовлетворяющий условию Фано. Известны коды трёх букв: 1, 01, 001. Коды остальных четырёх букв имеют одинаковую длину. Какова минимальная суммарная длина всех 7-ми кодовых слов?
Скажите, пожалуйста, эту задачу нужно решать построением дерева, и, понимая, что т.к. длина оставшихся четырех букв больше 3, то подбирать по дереву 5 уровень? тогда 5*4+6=26. Есть более общий способ? Заранее благодарна за любой ответ.

 Отправлено: 21.04.15 12:43. Заголовок: ELENA1991 пишет: Ест..

ELENA1991 пишет:

цитата:

Есть более общий способ?

Думаю, что нет.

 Отправлено: 21.04.15 13:39. Заголовок: Спасибо...

Спасибо.