Двоичное кодирование

Кодирование

Задача 1

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

-..---…-..

И приложил, к некоторым использованным в тексте буквам, кодовую таблицу:

1 Раскодируйте текст

2 Придумайте такую кодовую таблицу, чтобы можно было однозначно декодировать этот текст.

А

.

Б

Е

-

Н

..

О

-.

.-

пробел

--

Решение п. 1.

• Сложность задачи заключается в том, что код нельзя однозначно декодировать

• Например:
• [-.][.-][--][..][.][-.][.]
• Н О Е А Н А
• Или:
• [-.][.-][--][.][..][-][..]
• Н О А Е Б Е
• И т. д.

А

Б

.

-

Е

..

Н

-.

О

пробел

.-

--

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

[-.][.][--][-.][..][-][..]

Н А Н Е Б Е

Решение п.2

Для однозначного декодирования кода должно соблюдаться условие Фано:

Ни одно кодовое слово (набор из «–» и «.» для буквы) не должно быть началом другого

Такой код называется Пре́фиксный

В таблице Феди это условие не соблюдается!

Роберт Фано – итальяно-американский ученый

Например, код А [.], является началом кода Е [..] и т .д.

Чтобы создать кодовую таблицу, в которой соблюдается условие Фано, построим двоичное дерево

Наша новая таблица:

А

…

Б

Е

..-

Н

.-

О

--

-..

пробел

-.-

--…-.---.-..-.-

Навый код:

Задание 2

Закодируйте свое имя с помощью символов 1 и 0 так, чтобы при декодировании соблюдалось условие Фано

Этапы выполнения задания:

• Изобразите двоичное дерево
• Заполните по нему кодовую таблицу
• Закодируйте имя, используя эти коды

Двоичное дерево для 10 разных букв

1

0

Замените буквы А на свои.

Буквы не должны повторяться.

0

1

1

0

0

1

0

0

1

1

1

0

А

А

А

А

А

А

1

0

0

1

А

А

А

А

Кодовая таблица

А

А

А

А

А

А

А

А

А

А

Замените буквы на свои (Буквы не должны повторяться).

Лишние буквы просто игнорируйте

Под буквами напишите кодовые слова из 1 и 0

• Ваше имя:
• Закодированное имя:

Задача 3

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

Вот этот код: А – 0; Б – 100; В – 1010; Г – 111; Д – 110. Требуется сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно. Коды остальных букв меняться не должны.

Напишите эту букву и её новый код

А – 0; Б – 100; В – 1010; Г – 111; Д – 110.

Г

В 101

Задача 4

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

При этом используются следующие коды: А-1110, Б-0, В-10, Г-110.

Каким кодовым словом может быть закодирована буква Д?

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

Задача 5

Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=1, Б=01, В=001. Как нужно закодировать букву Г, чтобы длина кода была минимальной и соблюдалось условие Фано

A=1, Б=01, В=001

1

0

0

А

1

0

Б

1

Г

В

Г = 000

А

А

Задача 6

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, М, Р, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 010, Б — 011, Г — 100. Какое  наименьшее  количество двоичных знаков потребуется для кодирования слова МАГИЯ?

110 010 100 111 000 = 15 вариант1 1 0 0 1 1 0 0 1 0 0 1 1 0 Г Я А Р М Б И " width="640"

А — 010, Б — 011, Г — 100.

МАГИЯ из А, Б, Г, И, М, Р, Я

М -? И-? Я-?

МАГИЯ =110 010 100 111 000 = 15

вариант1

1

0

0

1

1

0

0

1

0

0

1

1

0

Г

Я

А

Р

М

Б

И

11 010 100 000 001 = 14 вариант2 1 0 0 1 1 0 0 1 0 М 0 1 Г И Р Я А Б Р " width="640"

А — 010, Б — 011, Г — 100.

МАГИЯ из А, Б, Г, И, М, Р, Я

М -? И-? Я-?

МАГИЯ =11 010 100 000 001 = 14

вариант2

1

0

0

1

1

0

0

1

0

М

0

1

Г

И

Р

Я

А

Б

Р