Форум » Кодирование и декодирование информации » Для кодирования неко.. » Ответить
Для кодирования неко..
ИЮГ: Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А – 00; Б – 101; В – 011; Г – 111; Д – 110. Требуется сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно. Коды остальных букв меняться не должны. Каким из указанных способов это можно сделать? 1) это невозможно 2) для буквы Б – 01 3) для буквы В – 01 4) для буквы Г – 11 Задание 1 вариант 2 от 01. 04. В этом задании не понятно какой признак Фано работает: прямой или обратный, так ни оно число не является ни началом, ни концом другого слова. Можно предположить, что одновременно работают оба условия Тогда новое число Б=01 совпадает с началом числа В. Это нам не подходит. Новое число В=01 будет являться окончанием числа Б. Тоже не подходит. Новое Г=11 является началом Д и, одновременно, окончанием В. Значит, ответ: это не возможно. При проверке ответ правильный 3), т.е. имеется в виду прямое условие Фано. Но как это можно определить по предоставленным данным? В чем я не права? Пожалуйста, подскажите!
Ответов - 7
Поляков: Давайте посмотрим на исходный код: А – 00; Б – 101; В – 011; Г – 111; Д – 110. Легко проверить, что для него выполняются оба условия Фано, и прямое (ни одно кодовое слово не совпадает с началом другого кодового слова), и обратное (ни одно кодовое слово не совпадает с окончанием другого кодового слова). Поэтому закодированные этим кодом сообщения могут быть однозначно декодированы как с начала, так и с конца. Вот еще важная мысль: Для однозначной декодируемости сообщений достаточно выполнения ОДНОГО из двух условий Фано. Это значит, что если, допустим, сохранить прямое условие Фано, то можно спокойно нарушить обратное, однозначная декодируемость не пострадает. Теперь смотрим на варианты упрощения кода. Вариант 2, Б - 01. При этом нарушится прямое условие Фано (код буквы В начинается с 01), но сохранится обратное - ни одно другое кодовое слово не заканчивается на 01. Поэтому код однозначно декодируется, вариант подходит. Вариант 3, В - 01. При этом нарушится обратное условие Фано (код буквы Б заканчивается на 01), но сохранится прямое - ни одно другое кодовое слово не начинается с 01. Поэтому код однозначно декодируется, вариант подходит. Вариант 4, Г - 11. При этом нарушится и прямое условие Фано (код буквы Д начинается с 11), и обратное (код буквы В заканчивается на 11), вариант НЕ подходит. Таким образом, здесь два правильных ответа, 2 и 3.
ИЮГ: Спасибо большое. А все таки можно ли считать ответ 3)Это невозможно, подразумевая, что речь может идти как раз о том, что должны сработать оба условия. помнится, мне где-то попадались такие задания.
Поляков: ИЮГ пишет: подразумевая, что речь может идти как раз о том, что должны сработать оба условия. Я еще раз подчеркну, что для обеспечения однозначной декодируемости НЕ НУЖНО обеспечивать оба условия Фано, достаточно одного из двух, любого. Поэтому ответ "невозможно" - неверный. Однозначно.
ИЮГ: Еще раз спасибо.
ELENA1991: В сообщении встречается 7 разных букв. При его передаче использован неравномерный двоичный код, удовлетворяющий условию Фано. Известны коды трёх букв: 1, 01, 001. Коды остальных четырёх букв имеют одинаковую длину. Какова минимальная суммарная длина всех 7-ми кодовых слов? Скажите, пожалуйста, эту задачу нужно решать построением дерева, и, понимая, что т.к. длина оставшихся четырех букв больше 3, то подбирать по дереву 5 уровень? тогда 5*4+6=26. Есть более общий способ? Заранее благодарна за любой ответ.
Поляков: ELENA1991 пишет: Есть более общий способ? Думаю, что нет.
ELENA1991: Спасибо.
полная версия страницы