Форум » Кодирование и декодирование информации » [A9] Условие Фано » Ответить
[A9] Условие Фано
PavelG: Здравсвуйте, Константин. В первом разоранном примере из задания А9 проверятся как прямое, так и обратное условие Фано. Во втором же, мне показалось, что проверяется только прямое. Можно ли как-то поподробное разъянить, когда исп. прямое условие Фано,а когда и обратное тоже (впервые познакомился с ним в ваших материалах). Спасибо.
Ion: Вы, меня, наверное, не совсем поняли. tavabar пишет: Он (10) неверен, т. к. является началом кода буквы В (100) Из этого следует только то, что не выполняется условие Фано. А оно не является необходимым для однозначного декодирования. В задаче ведь спрашивают про второе ("чтобы ... допускалось однозначное разбиение кодированного сообщения на буквы"), а не про то, выполняется ли тут условие Фано. Я о том и говорю. Условие Фано НЕ выполняется, я это прекрасно вижу. Но придумать такие примеры, которые бы допускали неоднозначности, я никак не смог. А Вы можете? :)
Поляков: Ion пишет: Я о том и говорю. Условие Фано НЕ выполняется, я это прекрасно вижу. Но придумать такие примеры, которые бы допускали неоднозначности, я никак не смог. А Вы можете? :) Уточним код: А = 00, Б = 11, В = 100, Г = 10 Для него невозможно придумать цепочку, которая неоднозначно раскодируется. Это можно доказать с помощью графов. А можно "по-простому": 1) Две единицы рядом могут появиться только от буквы Б, поэтому удаляем все комбинации 11. 2) Далее, если в начале цепочки стоят нули, их обязательно должно быть четное количество, это буквы А. 3) В конце цепочки обязательно стоят нули, если их четное число, то это буква В и за ней (возможно) буквы А. Если в конце цепочки нечетное число нулей, то это буква Г и за ней (возможно) буквы А. Таким образом дальше просто раскодировать, хоть с начала, хоть с конца. Причём однозначно. Итак, в условии задачи неточность. Сейчас на сайте исправлено. Спасибо! Успеха на экзамене! Вы должны сдать очень хорошо. :-)
oval: Поляков пишет: Это можно доказать с помощью графов. А у Вас не осталось решение с помощью графов? Ссылочка Евич Людмила решение задачи A9: (.pdf) http://dl.dropbox.com/u/17135806/Sol_%D0%909_LN.pdf не работает
Поляков: oval пишет: А у Вас не осталось решение с помощью графов? К сожалению, не смог найти файл, присланный Л. Евич. В моем изложении это выглядит так: decode_graph.doc.
oval: спасибо
Поляков: oval пишет: А у Вас не осталось решение с помощью графов? Вот и оригинал, который присылала Л. Евич.
Поляков: Поскольку поток вопросов по задаче А9 не прекращается, я сделал подробный анализ со всеми ньюансами, даже выходящими за рамки самого ЕГЭ: kpolyakov.blogspot.com/2012/10/blog-post.html.
Ion: Да-да, Константин Юрьевич, я примерно это и имел в виду, когда говорил про "чётность-нечётность". Просто времени сейчас в обрез, так что детально разбираться с этим заданием - трата времени для меня сейчас.
Ion: Поляков пишет: Успеха на экзамене! Вы должны сдать очень хорошо. :-) Спасибо за добрые слова поддержки, Константин Юрьевич! Но увы - от меня здесь зависит далеко не всё. Ну, я уже немало писал Вам насчёт всего этого. Надеюсь на лучшее, но морально готовлюсь и к самому худшему тоже...
ДубинкинаТ: Спасибо за ссылку "мысли вслух" - помогло разобраться с заданием А6 КЕГЭ
Власова: Здравствуйте, Константин Юрьевич! С данной задачей я так и не разобралась. Помогите, пожалуйста, я прочитала всю теорию у Вас на сайте, такого примера нет. Для передачи помехоустойчивых сообщений в алфавите, который содержит 16 различных символов, используется равномерный двоичный код. Этот код удовлетворяет следующему свойству: в любом кодовом слове содержится четное количество единиц (возможно, ни одной). Какую наименьшую длину может иметь кодовое слово?
Поляков: Власова пишет: Для передачи помехоустойчивых сообщений в алфавите, который содержит 16 различных символов, используется равномерный двоичный код. Этот код удовлетворяет следующему свойству: в любом кодовом слове содержится четное количество единиц (возможно, ни одной). Какую наименьшую длину может иметь кодовое слово? Посмотрите пояснения к ответу, который есть на Яндексе. Там 4 рабочих бита (24 = 16) и 5-ый - бит четности, который и обеспечивает четное число единиц.
полная версия страницы