Кодирование и декодирование информации. Условие Фано

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

Учебная презентация по информатике

Автор: Звездина Вера Алексеевна,

учитель информатики

МБОУ «Образовательный центр №1»,

г.Ивантеевка Московской обл. 

НЕмного теории

Для передачи, обработки и хранения информации необходимо ее зафиксировать с помощью определенной знаковой системы ( алфавита) , т. е. закодировать.

Кодирование – это процесс представления информации в виде последовательности условных обозначений. Декодирование – это процесс, обратный кодированию.

НЕмного теории

Кодирование информации всегда происходит по определенным правилам. Правило кодирования называется кодом .

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

НЕмного теории

  Например, кодовое слово для буквы «O» в азбуке Морзе имеет длину равную трем и представляет последовательность из трех символов тире «— — —»).

Способы кодирования информации зависят от конкретной задачи. 

НЕмного теории

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

При этом перебора различных вариантов при декодировании не потребуется.   Это позволяет избежать ошибок и сэкономить время для решения задачи .

НЕмного теории

Прямое условие Фано гласит, что ни одно кодовое слово не может служить началом другого кодового слова.

Обратное условие Фано гласит, что ни одно кодовое слово не может служить концом другого кодового слова.

НЕмного теории

Например, в кодовых словах 

01, 011, 010, 110, 100 

нарушено  прямое условие Фано , так как кодовое слово 01 является началом кодового слова 011.  

Обратное условие не нарушено , поэтому задачу по раскодированию с такими кодовыми словами рекомендуется решать с конца сообщения , что обеспечит его однозначное декодирование

НЕмного теории

В кодовых словах

01, 001, 100, 101, 110

нарушено обратное условие Фано , так как кодовое слово 01 является концом кодовых слов 001 и 101.

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

НЕмного теории

В кодовых словах

01, 001, 010, 100, 110

нарушены оба условия Фано , так как кодовое слово 01 служит началом кодового слова 010 и концом кодового слова 001.

  Это значит, что при решении такой задачи однозначное декодирование невозможно, решать можно с любой стороны – все равно придется перебирать варианты.

НЕмного теории

Часто при решении задач по декодированию достаточно умения логически мыслить, быть внимательным и аккуратным – и все получится!

Следует учитывать, что результатом декодирования не обязательно должно быть осмысленное слово!

РЕШЕНИЕ ЗАДАЧ. Пример   1

На киностудии снимали фильм про шпионов и закодировали сообщение придуманным шифром. В сообщении присутствуют только буквы приведённого фрагмента кодовой таблицы:

Определите, какое сообщение закодировано в строчке:

                       01111111001

В ответе запишите последовательность букв без запятых и других знаков препинания.

Решение – на следующем слайде

РЕШЕНИЕ ЗАДАЧ. Пример   1

Решение.

В исходных кодовых словах данной задачи нарушено прямое условие Фано (кодовое слово 01 является началом кодовых слов 01 0 и 01 1), то для однозначного решения задачи будем декодировать сообщение с конца:

Ответ : РЕБИ

РЕШЕНИЕ ЗАДАЧ. Пример   2

На киностудии снимали фильм про шпионов и закодировали сообщение придуманным шифром. В сообщении присутствуют только буквы приведённого фрагмента кодовой таблицы:

Определите, какое сообщение закодировано в строчке:

                       11010001111

В ответе запишите последовательность букв без запятых и других знаков препинания.

Решение – на следующем слайде

РЕШЕНИЕ ЗАДАЧ. Пример   2

Решение.

В исходных кодовых словах данной задачи нарушено обратное условие Фано (кодовое слово 01 является концом кодового слова 101 ), то для однозначного решения задачи будем декодировать сообщение с начала:

Ответ : ТЕМА

РЕШЕНИЕ ЗАДАЧ. Пример   3

Агент 007, передавая важные сведения своему напарнику, закодировал сообщение придуманным шифром. В сообщении присутствуют только буквы из приведённого фрагмента кодовой таблицы:

Определите, какое сообщение закодировано в строчке:

? ? ? ? € ? €.

В ответе запишите последовательность букв без запятых и других знаков препинания.

Решение – на следующем слайде

РЕШЕНИЕ ЗАДАЧ. Пример   3

Решение.

Так как кодовое слово ? ? является началом кодового слова ? ? €, а кодовое слово € ? является концом кодового слова ? € ? , то однозначное декодирование в данной задаче выполнить невозможно. Тогда, перебирая варианты, получаем ответ БЫК .

Ответ : БЫК

РЕШЕНИЕ ЗАДАЧ. Пример   4

Кирилл шифрует английские слова, записывая вместо каждой буквы её номер в алфавите:

Некоторые шифровки можно расшифровать не одним способом. Например, 16118 может означать «AFAR», или - «РАR», или -«AFAAH». Даны четыре шифровки:

18205 81205 20158 20518

Найдите и расшифруйте ту из них, которая расшифровывается единственным способом. Запишите полученное в качестве ответа.

Решение – на следующем слайде

РЕШЕНИЕ ЗАДАЧ. Пример   4

Решение.

В данной таблице нарушены оба условия Фано, но есть своя закономерность: все кодовые слова лежат в диапазоне от 1 до 26, то есть кодового слова 0 здесь нет.

Тогда однозначно расшифровывается только вторая из заданных последовательностей, которая декодируется как НАTE.

Ответ : НАТЕ

РЕШЕНИЕ ЗАДАЧ. Пример   5

По каналу связи передаются сообщения, содержащие только буквы A, B, С, D . Для передачи используется двоичный код, допускающий однозначное декодирование.

Для букв A, B, C используются такие кодовые слова: A: 111, B: 0, C: 100 .

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

Решение – на следующем слайде

РЕШЕНИЕ ЗАДАЧ. Пример   5

Решение.

Решать задачу можно двумя способами – с помощью кодового дерева или без него, путем логических рассуждений.

Способ 1.

Построим дерево и найдем

в нем ответ. Возможными

вариантами для нового кода

могут быть свободные ветки

101 и 110 , но 101 – ветка с

наименьшим числовым

значением, что полностью

соответствует условию.

1

1

0

В

1

0

1

0

1

0

С

A

D

РЕШЕНИЕ ЗАДАЧ. Пример   5

Решение.

Способ 2.

Самое короткое кодовое слово здесь – В , которое является концом кодового слова С .

Это нарушает обратное условие Фано, и для получения однозначного декодирования ищем код, не нарушающий прямое условие. Началом кодового слова не могут быть 1, 10 и 11 , оно должно быть трехзначным. Варианты таких кодовых слов – 100 (занято), 101, 110, 111 (занято). Свободными остаются слова 101 и 110 , где меньшее числовое значение – у кодового слова 101 .

Ответ: 101