Форум » Кодирование и декодирование информации » А9 и граф Маркова » Ответить
А9 и граф Маркова
Luda: Константин Юрьевич, опрос создала нечаянно. А вопрос по задачи из книги Крылов, Ушаков 2013 вариант 2 А9 Нужно оптимизировать код (однозначно декодируемый) А — 00, Б — 01, В — 100, Г — 101, Д — 110, Е — 111 выбрав один из вариантов 1) невозможно 2) Е — 11 3) В — 10 4) Г — 10 Анализ исходного кода: префиксный-прямое условие Фано выполняется; обратное условие Фано не выполняется (А-В и Б-Г). Анализ предложенных вариантов: все варианты дают нарушение прямого условия Фано. Т. о. проверить однозначное декодирование предложенных вариантов можно только построением графа по Маркову для каждого варианта ответа?
Ответов - 2
Поляков: Luda пишет: Т. о. проверить однозначное декодирование предложенных вариантов можно только построением графа по Маркову для каждого варианта ответа? Строго говоря, да. Но есть второй вариант - найти цепочку, которая неоднозначно декодируется: 1) для варианта 2 это 110101 => ЕББ = ДГ и 110100 => ЕБА = ДВ 2) для варианта 3 это 10101 => ВГ = ГБ и 10110 => ВД = ГВ 3) для варианта 4 это 100100 => ГБА = ВВ Поэтому правильный вариант ответа - 1, оптимизировать код предложенными вариантами не удается.
Luda: Спасибо! у меня получилось найти цепочку только после того, как построила граф для варианта 2
полная версия страницы