Что такое однозначное кодирование

Что такое однозначное кодирование

лабораторные работы и задачи по программированию и информатике, егэ по информатике

Кодирование информации

  • Кодирование — это представление информации в форме, удобной для её хранения, передачи и обработки. Правило преобразования информации к такому представлению называется кодом.
  • Кодирование бывает равномерным и неравномерным:
  • при равномерном кодировании всем символам соответствуют коды одинаковой длины;
  • при неравномерном кодировании разным символам соответствуют коды разной длины, это затрудняет декодирование.

Таким образом, мы получили равномерный код, т.к. длина каждого кодового слова одинакова для всех кодов (2).

Кодирование и расшифровка сообщений

Для решения задач с декодированием, необходимо знать условие Фано:

    если сообщение декодируется с конца, то его можно однозначно декодировать, если выполняется обратное условие Фано:

  • условие Фано – это достаточное, но не необходимое условие однозначного декодирования.
  • Однозначное декодирование обеспечивается:

    Решение 5 заданий ЕГЭ

    Закодируйте последовательность букв ВОДОПАД таким способом и результат запишите восьмеричным кодом.

    • Переведем числа в двоичные коды и поставим их в соответствие нашим буквам:
    • Теперь закодируем последовательность букв из слова ВОДОПАД :
    • Разобьем результат на группы из трех символов справа налево, чтобы перевести их в восьмеричную систему счисления:

    Результат: 22162

    Решение ЕГЭ данного задания по информатике, видео:

    Рассмотрим еще разбор 5 задания ЕГЭ:

    a b c d e
    000 110 01 001 10

    Какой набор букв закодирован двоичной строкой 1100000100110 ?

    • Во-первых, проверяем условие Фано: никакое кодовое слово не является началом другого кодового слова. Условие верно.
  • Код разбиваем слева направо согласно данным, представленным в таблице. Затем переведём его в буквы:
  • Результат: b a c d e.

    ✎ 2 вариант решения:

      Этот вариант решения 5 задания ЕГЭ более сложен, но тоже верен.

    Сделаем дерево, согласно кодам в таблице:

  • Сопоставим закодированное сообщение с кодами в дереве:
  • Результат: b a c d e.

    Кроме того, вы можете посмотреть видео решения этого задания ЕГЭ по информатике:

    Решим следующее 5 задание:

    Определите, какое число пе­ре­да­ва­лось по ка­на­лу в виде 01100010100100100110 .

    • Рассмотрим пример из условия задачи:
    • Где сами цифры исходного числа (выделим их красным цветом):

    Ответ: 6 5 4 3

    Вы можете посмотреть видео решения этого задания ЕГЭ по информатике:

    Для кодирования некоторой последовательности, состоящей из букв К , Л , М , Н решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово 0 , для буквы К — кодовое слово 10 .

    Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?

    • Найдём самые короткие возможные кодовые слова для всех букв.
    • Кодовые слова 01 и 00 использовать нельзя, так как тогда нарушается условие Фано (начинаются с 0, а 0 — это Н).
    • Начнем с двухразрядных кодовых слов. Возьмем для буквы Л кодовое слово 11. Тогда для четвёртой буквы нельзя подобрать кодовое слово, не нарушая условие Фано (если потом взять 110 или 111, то они начинаются с 11).
    • Значит, надо использовать трёхзначные кодовые слова. Закодируем буквы Л и М кодовыми словами 110 и 111. Условие Фано соблюдается.
    • Суммарная длина всех четырёх кодовых слов равна:

    2 вариант решения:

      Будем использовать дерево. Влево откладываем 0, вправо — 1:

  • Теперь выпишем соответствие каждой буквы ее кодового слова согласно дереву:
  • Суммарная длина всех четырёх кодовых слов равна:
  • Ответ: 9

    По каналу связи передаются сообщения, содержащие только 4 буквы: А , Б , В , Г ; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв А, Б, В используются такие кодовые слова:

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

    • Наименьшие коды могли бы выглядеть, как 0 и 1 (одноразрядные). Но это не удовлетворяло бы условию Фано (А начинается с единицы — 101010, Б начинается с нуля — 011011).
    • Следующим наименьшим кодом было бы двухбуквенное слово 00. Так как оно не является префиксом ни одного из представленных кодовых слов, то Г = 00.

    Результат: 00

    Для кодирования некоторой последовательности, состоящей из букв А , Б , В , Г и Д , решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приемной стороне канала связи. Использовали код:

    Укажите, каким кодовым словом должна быть закодирована буква Д . Длина этого кодового слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного декодирования. Если таких кодов несколько, укажите код с наименьшим числовым значением.

    • Так как необходимо найти кодовое слово наименьшей длины, воспользуемся деревом. Влево будем откладывать нули, а вправо — единицы:

    Поскольку у нас все ветви завершены листьями, т.е. буквами, кроме одной ветви, то остается единственный вариант, куда можно поставить букву Д:

  • Перепишем сверху вниз получившееся кодовое слово для Д: 101
  • Результат: 101

    Подробней разбор урока можно посмотреть на видео ЕГЭ по информатике 2017:

    По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А , Б , Е , И , К , Л , Р , С , Т , У . Для передачи используется неравномерный двоичный код. Для девяти букв используются кодовые слова.

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

    • Для решения будем использовать дерево. Ветви, соответствующие нулю, будем откладывать влево, единице — вправо.

    При рассмотрении дерева видим, что все ветви «закрыты» листьями, кроме одной ветви — 1100 :

    Результат: 1100

    Подробное решение данного 5 задания из демоверсии ЕГЭ 2018 года смотрите на видео:

    По каналу связи передаются шифрованные сообщения, содержащие только четыре букв: А , Б , В , Г ; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв А, Б, В используются кодовые слова:

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

    • Для решения будем использовать дерево. Ветви, соответствующие нулю, будем откладывать влево, единице — вправо.
    • Поскольку в задании явно не указано о том, что код должен удовлетворять условию Фано, то дерево нужно построить как с начала (по условию Фано), так и с конца (обратное условие Фано).

    Дерево по условию Фано (однозначно декодируется с начала):

    Получившееся числовое значение кодового слова для буквы Г01.

    Дерево по обратному условию Фано (однозначно декодируется с конца):

  • Получившееся числовое значение кодового слова для буквы Г00.
  • После сравнения двух кодовых слов (01 и 00), код с наименьшим числовым значением — это 00 .
  • Результат: 00

    По каналу связи передаются сообщения, содержащие только буквы: А, Е, Д, К, М, Р; для передачи используется двоичный код, удовлетворяющий условию Фано. Известно, что используются следующие коды:

    Укажите наименьшую возможную длину закодированного сообщения ДЕДМАКАР.
    В ответе напишите число – количество бит.

    • С помощью дерева отобразим известные коды для букв:

    В результирующем слове — ДЕДМАКАР — вде буквы А. Значит, для получения наименьшей длины необходимо для буквы А выбрать наименьший код в дереве. Учтем это и достроим дерево для остальных трех букв А, М и Р:

  • Расположим буквы в порядке их следования в слове и подставим их кодовые слова:
  • Посчитаем количество цифр в итоговом коде и получим 20 .
  • Результат: 20

    Смотрите виде решения задания:

    Разбор экзаменационных задач по декодированию информации. Прямое и обратное условие Фано.

    Скачать:

    Вложение Размер
    odnoznachnoe_dekodirovanie.pptx 102.09 КБ

    Предварительный просмотр:

    Подписи к слайдам:

    Однозначное декодирование Прямое и обратное условие Фано Учитель информатики и ИКТ МБОУ СОШ № 7 г. Оха Сахалинской области Сергиенко Татьяна Геннадьевна

    Задача 1 Пусть для кодирования фразы «Доброе утро» выбран такой код: Д О Б Р Е У Т Пробел 111 000 00 1 01 0 10 11

    Коды букв «сцепляются» в единую битовую строку и передаются, например, по сети: Доброе утро→ 11100000100001110101000 В пункте назначения возникает проблема – как восстановить исходное сообщение, и возможно ли это.

    11100000100001110101000 Раскодировать данное сообщение можно разными способами. В том числе предположим, что оно состоит только из букв Р – 1 и У – 0. Тогда получим РРРУУУУУРУУУУРРРУРУРУУУ, т.е. бессмысленный набор букв .

    Код называется однозначно декодируемым , если любое кодовое сообщение можно расшифровать единственным способом (однозначно ).

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

    Задача 2 Равномерные коды. Для той же фразы используем равномерный код: Д О Б Р Е У Т Пробел 111 000 001 101 011 010 100 110

    Равномерные коды неэкономичны – гораздо длиннее неравномерных. Это приводит к усложнению кодирования, но при этом они раскодируются однозначно, что, естественно, облегчает задачу.

    Задача 3 Чтобы сократить длину сообщения, можно попробовать применить неравномерный код, т.е. код, в котором кодовые слова, соответствующие разным символам исходного алфавита, могут иметь разную длину, от одного до нескольких символов.

    Используем следующий код: 0100101110000101011111101111010000 Эта битовая цепочка декодируется однозначно. Д О Б Р Е У Т Пробел 01 00 1011 100 1010 1101 1110 1111

    Первая буква — Д (код 01), т.к. ни одно другое кодовое слово не начинается с 01. Вторая буква – О (код 00). Никакое другое слово не начинается с 00. Это же свойство, которое называется условием Фано , выполняется и для кодовых слов других букв.

    УСЛОВИЕ ФАНО Никакое кодовое слово не совпадает с началом другого кодового слова. Такие коды называются префиксными (раскодируются с начала сообщения) и декодируются однозначно.

    Задача 4 Рассмотрим ещё один код: Он не является префиксным, т.к. код буквы Д (10 ) совпадает с началом кода буквы Б (1011), У(1000) и код буквы О(00) совпадает с началом кода буквы Р (001 ). Д О Б Р Е У Т Пробел 10 00 1011 001 0101 1000 0111 1111

    Закодируем наше сообщение: ДОБРОЕ УТРО→ 10 00 1011 001 00 0101 1111 1000 0111 001 00 Начнём раскодировать с начала. Первая – Д, или У, а дальше идут вообще разные варианты : Р или Б… Т.е. надо «заглядывать» вперёд, что очень неудобно.

    Попробуем раскодировать сообщение с конца – оно однозначно декодируется! Выполняется обратное условие Фано : никакое кодовое слово не совпадает с окончанием другого кодового слова.

    Коды , для которых выполняется обратное условие Фано , называются постфиксными.

    Сделаем вывод: Сообщение декодируется однозначно, если для используемого кода выполняется прямое или обратное условие Фано .

    Условие Фано — это достаточное, но не необходимое условие однозначной декодируемости Это значит, что: — для однозначной декодируемости достаточно выполнения хотя бы одного из двух условий — прямого или обратного. — могут существовать коды, для которых не выполняется ни прямое, ни обратное условие Фано , но тем не менее обеспечивается однозначное декодирование, т.к. иначе теряется смысл выражения.

    Задача 5 Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А – 00, Б – 01, В – 100, Г – 101, Д – 110.

    Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа: 1) для буквы Д -11 2) это невозможно 3) для буквы Г — 10 4) для буквы Д -10

    РЕШЕНИЕ: Исходный код – префиксный. Для него выполняется условие Фано – ни один из трёхбитных кодов не начинается ни с 00 (А), ни с 01 (Б). (При этом обратное условие Фано не выполняется – код А (00) совпадает с окончанием В (100), а код Б (01) совпадает с окончанием Г (101 ).)

    Теперь проверим ответы. Сократим Д до 11. Если полученный код нарушит прямое условие Фано , то свойство однозначного декодирования будет нарушено. Но этого не произошло, нет других кодов, начинающихся с 11. Это и есть верное решение. Проверим остальные варианты.

    Вариант 2 сразу не рассматриваем – ответ у нас найден. Вариант 3 нарушает прямое условие Фано – с 10 начинается код буквы В (101). Вариант 4 – так же нарушает прямое условие Фано . Т.е. ответ однозначный, других вариантов нет.

    Спасибо за внимание!

    По теме: методические разработки, презентации и конспекты

    «Человек – культура – социум » в методике преподавания иностранных языков выразилось в разработке личностно-ориентированного подхода . Обучение речевому общению стало основной задач.

    Успешное обучение в школе предполагает понимание обращённой к ребёнку речи, умения связно излагать свои мысли и суждения. В сотрудничестве, под руководством, с чьей-то помощью ребёнок всегда мож.

    Урок информатики в 9 классе.

    Данный урок проводитсяя в 5 классе по программе, изучается в разделе "Лексика".

    Индивидуальный план работы на межаттестационный период по повышению профессионального уровня учителя русского языка и литературы.

    Самостоятельная работа 5 вариантов.

    Самообразование учителя есть необходимое условие профессиональной деятельности педагога. Общество всегда предъявляло, и будет предъявлять к учителю самые высокие требования. Для того, чтобы учить друг.

    Однозначность декодирования можно обеспечить, не вводя разделительного символа, если строить код так, чтобы он удовлетворял условию, известному под названием "свойство префикса". Оно заключается в том, что ни одна комбинация более кратного кода не должна совпадать с началом ("префиксом") другого кодового слова. Коды, удовлетворяющие этому условию, называют префиксными кодами. Эти коды обеспечивают однозначное декодирование принятых кодовых слов без введения дополнительной информации для их разделения, т. е. всякая последовательность кодовых символов должна быть единственным образом разделена на кодовые слова. Коды, в которых это требование выполнимо, называются однозначно декодируемыми, или кодами без запятой.

    Если код префиксный, то, читая принятую последовательность подряд с начала до конца, можно установить, где кончается одно кодовое слово и начинается следующее. Например, если код префиксный и в последовательности встретился код 110, то, очевидно, в коде не должно содержаться слов (1), (11). Закодировано префиксным кодом с а1 = (00), а2 = (01), а3 = (101), а4 = (100). На рис. 1 представлен граф (кодовое дерево) префиксного кода с сообщением а1 = (0), а2 = (1), а3 = (11), а4 = (111). Из рис. 1 следует, что если свойство префикса не выполняется, то некоторые промежуточные вершины дерева могут соответствовать кодовым словам.

    Не нашли то, что искали? Воспользуйтесь поиском:

    Лучшие изречения: Для студента самое главное не сдать экзамен, а вовремя вспомнить про него. 10677 — | 7830 — или читать все.

    Ссылка на основную публикацию
    Что такое asus vibe
    Файл asusvibe2.0.exe из ASUSTeK Computer Inc является частью AsusVibe2 0. asusvibe2.0.exe, расположенный в c:program files (x86)asusasusvibeasusvibe2.0.exe с размером файла 924336...
    Что делать если виснет браузер
    Автор Юрий Белоусов · 18.03.2019 Пользователи могут столкнуться с неприятной ситуацией, когда браузер Опера зависает, виснет, подвисает, тормозит, лагает, глючит....
    Что делать если винда 10 не запускается
    В нашей сегодняшней статье будет рассмотрен ряд случаев, связанных с отказом запуска операционной системы Windows 10 на компьютере или ноутбуке....
    Что такое elm agent на андроид
    Практически каждый пользователь мобильных устройств, рано или поздно, пытается разобраться в настройках, просматривать установленные приложения и сервисы. При просмотре списка...
    Adblock detector