Автор | Сообщение |
|
Отправлено: 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), т.е. имеется в виду прямое условие Фано. Но как это можно определить по предоставленным данным? В чем я не права? Пожалуйста, подскажите!
|
|
|
Ответов - 7
[только новые]
|
|
|
| Администратор
|
Сообщение: 785
|
|
Отправлено: 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)Это невозможно, подразумевая, что речь может идти как раз о том, что должны сработать оба условия. помнится, мне где-то попадались такие задания.
|
|
|
|
| Администратор
|
Сообщение: 786
|
|
Отправлено: 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. Есть более общий способ? Заранее благодарна за любой ответ.
|
|
|
|
| Администратор
|
Сообщение: 796
|
|
Отправлено: 21.04.15 12:43. Заголовок: ELENA1991 пишет: Ест..
ELENA1991 пишет: Думаю, что нет.
|
|
|
|
Отправлено: 21.04.15 13:39. Заголовок: Спасибо...
Спасибо.
|
|
|
|