Однозначное декодирование

Содержание

Слайд 2

Задача 1

Пусть для кодирования фразы «Доброе утро» выбран такой код:

Задача 1 Пусть для кодирования фразы «Доброе утро» выбран такой код:

Слайд 3

Коды букв «сцепляются» в единую битовую строку и передаются, например, по сети:
Доброе

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

Слайд 4

11100000100001110101000
Раскодировать данное сообщение можно разными способами. В том числе предположим, что оно

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

Слайд 5

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

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

Слайд 6

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

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

Слайд 7

Задача 2

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

Задача 2 Равномерные коды. Для той же фразы используем равномерный код:

Слайд 8

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

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

Слайд 9

Задача 3

Чтобы сократить длину сообщения, можно попробовать применить неравномерный код, т.е. код,

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

Слайд 10

Используем следующий код:
0100101110000101011111101111010000
Эта битовая цепочка декодируется однозначно.

Используем следующий код: 0100101110000101011111101111010000 Эта битовая цепочка декодируется однозначно.

Слайд 11

Первая буква - Д (код 01), т.к. ни одно другое кодовое слово

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

Слайд 12

УСЛОВИЕ ФАНО

Никакое кодовое слово не совпадает с началом другого кодового слова.
Такие коды

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

Слайд 13

Задача 4

Рассмотрим ещё один код:
Он не является префиксным, т.к. код буквы Д

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

Слайд 14

Закодируем наше сообщение:
ДОБРОЕ УТРО→ 10 00 1011 001 00 0101 1111 1000

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

Слайд 15

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

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

Слайд 16

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

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

Слайд 17

Сделаем вывод:

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

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

Слайд 18

Условие Фано - это достаточное, но не необходимое условие однозначной декодируемости

Это значит,

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

Слайд 19

Задача 5

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г

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

Слайд 20

Можно ли сократить для одной из букв длину кодового слова так, чтобы

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

Слайд 21

РЕШЕНИЕ:

Исходный код – префиксный. Для него выполняется условие Фано – ни один

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

Слайд 22

Теперь проверим ответы.
Сократим Д до 11. Если полученный код нарушит прямое условие

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

Слайд 23

Вариант 2 сразу не рассматриваем – ответ у нас найден. Вариант 3

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