Кодирование. Декодирование.pptx

Количество информации, которое мы получаем, достигает максимального значения, если события равновероятны. Отношение количества вариантов (или чисел) N к количеству информации которую несет в себе один из вариантов I: N=2I. Полный информационный объем сообщения V равен количеству символов в сообщении K умноженное на количество информации на каждый символ I: V=K*I
Формула Шеннона для равновероятных событий: I=log2N
если алфавит имеет мощность ( количество символов в этом алфавите) М, то количество всех возможных «слов» (символьных цепочек) длиной N (без учета смысла) равно K=MN; для двоичного кодирования (мощность алфавита M –2 символа) получаем известную формулу: K=2N

Кодирование информации в ПК заключается в том, что каждому символу ставится в соответствие уникальный двоичный код.
 КОИ-8: 1 символ - 1 байт = 8 бит
 UNICODE: 1 символ - 2 байта = 16 бит

Задание 1. 
В алфавите формального языка два знака («0» и «1») и каждое слово этого языка состоит из восьми букв.Определить максимальное количество слов в языке.

Решение.
Существует формула, определяющая максимально возможное количество комбинаций (слов) фиксированной длины определенного алфавита: N = mk
m – это количество символов в алфавите. У нас их два – 0 и 1. Значит m = 2.k – это длина слова, т.е. количество знакомест, отводимых под каждое из них. По условию задачи k = 7.N – максимально возможное количество различных комбинаций из m знаков при длине слова в k знакомест.
В данном случае  N = 28 = 256

Ответ. Максимальное количество слов (комбинаций), состоящих из 8-ми букв (знакомест), в алфавите из 2-х знаков равно 256.

Задание 2. 

Определить количество различных последовательностей, которые можно закодировать с помощью двоичных слов, состоящих из шести символов (знакомест).

Решение.
Используется та же формула: N = mk
В данном случае m = 2, k = 6, следовательно,
N = 26 = 64.

Ответ. Максимальное количество последовательностей, которые можно закодировать с помощью двоичных слов, состоящих из восьми букв, равно 64.

Задание 3. 
Определить количество различных последовательностей из символов “a”, “b”, “c”, “%”, “&”  длиной в четыре символа.

Решение.
Используется формула: N = mk
Количество букв (символов) алфавита равно 5, т.е. m = 5. Длина слова – k = 4.
Получаем  N = 54 = 625

Ответ. Количество последовательностей из пяти любых символов длиной в три символа равно 625.

Что нужно знать для решения задач:
Кодирование – это перевод информации с одного языка на другой (запись в другой системе символов, в другом алфавите).
При этом обычно кодированием называют перевод информации с «человеческого» языка на формальный, например, в двоичный код, а декодированием– обратный переход.Существует равномерное и неравномерное кодирование. При равномерном кодировании сообщение декодируется однозначно.При неравномерном кодировании для однозначного декодирования сообщения нужно, чтобы выполнялось прямое и обратное условие Фано (прямое: никакой код не должен быть началом другого кода, обратное: никакой код не должен быть концом другого кода)
Понимать, что мы можем закодировать сообщение, даже если условие Фано не выполняется, но возможно не сможем его однозначно декодировать.
Однозначно декодировать – получить один единственный точный вариант.  

Задание 4.
Для шифрования каждой буквы используются двузначные числа. Известно, что буква «е» закодирована числом 20. Среди слов «елка», «полка», «поле», «пока», «кол» есть слова, кодируемые последовательностями цифр 11321220, 20121022.

Выясните код слова «колокол».

Решение.
Данные последовательности цифр (11321220, 20121022) состоят из восьми символов.
По условию задачи каждая буква кодируется двумя символами. Значит, эти последовательности кодируют слова, состоящие из четырех букв.
Число 20 кодирует букву «е». В последовательности 11321220 есть число 20 в конце. Из представленного перечня слов подходит только «поле».
Отсюда следует, что код «п» - 11, «о» – 32, «л» – 12.
В последовательности 20121022 есть число 20 в начале. С буквы «е» начинается только слово «елка».
Следовательно, код «л» - 12 (мы это уже знаем), «к» - 10, «а» - 22.
Запишем код слова «колокол» - 10|32|12|32|10|32|12.

Ответ. Кодом слова «колокол» является комбинация следующих цифр - 10321232103212.

Задание 5
Для пяти букв алфавита заданы их двоичные коды (для некоторых букв – из двух бит, для некоторых – из трех). Эти коды представлены в таблице:
a b c d e
000 110 01 001 10

Определите, какой набор букв закодирован двоичной строкой
1100000100110.

Решение
1. Ни одна последовательность из двух символов не начинается с 11, значит первый код 110. Он соответствует букве «b». Будем отбрасывать известную часть кода, оставляя неизвестную - 0000100110.
2. Ни одна последовательность из двух символов не начинается с 00, значит следующий код 000. Это соответствует букве «a». Остается 0100110.
3. Следующие два символа – 01. Если рассматривать три символа, то 010, однако такая комбинация ничего не кодирует. Следовательно, мы имеем дело с буквой «c». Остаток – 00110.
4. 001 – это «d».
5. 10 – это «e».
6. Запишем буквы по порядку: bacde.

Ответ. Двоичной строкой 1100000100110 закодирован следующий набор букв - bacde.

Задача 6.
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Использовали код: А–1, Б–000, В–001, Г–011. Укажите, каким кодовым словом должна быть закодирована буква Д. Длина этого кодового слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного декодирования.

1) 00 2) 01 3)11 4) 010

Решение:
Заметим, что для известной части кода выполняется условие Фано – никакое кодовое слово не является началом другого кодового слова
если Д = 00, такая кодовая цепочка совпадает с началом Б = 000 и В = 001, невозможно однозначно раскодировать цепочку 000000: это может быть ДДД или ББ; поэтому первый вариант не подходит
если Д = 01, такая кодовая цепочка совпадает с началом Г = 011, невозможно однозначно раскодировать цепочку 011: это может быть ДА или Г; поэтому второй вариант тоже не подходит
если Д = 11, условие Фано тоже нарушено: кодовое слово А = 1 совпадает с началом кода буквы Д, невозможно однозначно раскодировать цепочку 111: это может быть ДА или ААА; третий вариант не подходит
для четвертого варианта, Д = 010, условие Фано не нарушено;
правильный ответ – 010