3. Умножение вероятностей независимых совместных событий

4. Нахождение среднего для значений случайных независимых величин

5. Понятие условной вероятности

6. Общая формула для вероятности произведения событий

7. Общая формула для вероятности суммы событий

Лекция 3. Понятие энтропии

1. Энтропия как мера неопределенности

2. Свойства энтропии

3. Условная энтропия

Лекция 4. Энтропия и информация

1. Объемный подход к измерению количества информации

2. Энтропийный подход к измерению количества информации

Лекция 5. Информация и алфавит

Лекция 6. Постановка задачи кодирования. Первая теорема Шеннона.

Лекция 7. Способы построения двоичных кодов. Алфавитное неравномерное двоичное кодирование сигналами равной длительности. Префиксные коды.

1. Постановка задачи оптимизации неравномерного кодирования

2. Неравномерный код с разделителем

3. Коды без разделителя. Условие Фано

4. Префиксный код Шеннона–Фано

5. Префиксный код Хаффмана

Лекция 8. Способы построения двоичных кодов. Другие варианты

1. Равномерное алфавитное двоичное кодирование. Байтовый код

2. Международные системы байтового кодирования текстовых данных. Универсальная система кодирования текстовых данных

3. Алфавитное кодирование с неравной длительностью элементарных сигналов. Код Морзе

4. Блочное двоичное кодирование

5. Кодирование графических данных

6. Кодирование звуковой информации

Лекция 9. Системы счисления. Представление чисел в различных системах счисления. Часть 1

1. Системы счисления

2. Десятичная система счисления

3. Двоичная система счисления

4. 8- И 16-ричная системы счисления

5. Смешанные системы счисления

6. Понятие экономичности системы счисления

Лекция 10. Системы счисления. Представление чисел в различных системах счисления. Часть 2.

1. Задача перевода числа из одной системы счисления в другую

2. Перевод q  p целых чисел

3. Перевод p  q целых чисел

4. Перевод p  q дробных чисел

6. Перевод чисел между 2-ичной, 8-ричной и 16-ричной системами счисления

Лекция 11. Кодирование чисел в компьютере и действия над ними

1. Нормализованные числа

2. Преобразование числа из естественной формы в нормализованную

3. Преобразование нормализованных чисел

4. Кодирование и обработка целых чисел без знака

5. Кодирование и обработка целых чисел со знаком

6. Кодирование и обработка вещественных чисел

Лекция 12. Передача информации в линии связи

1. Общая схема передачи информации в линии связи

2. Характеристики канала связи

3. Влияние шумов на пропускную способность канала

Лекция 13. Обеспечение надежности передачи информации.

1. Постановка задачи обеспечения надежности передачи

2. Коды, обнаруживающие одиночную ошибку

3. Коды, исправляющие одиночную ошибку

Лекция 14. Способы передачи информации в компьютерных линиях связи

1. Параллельная передача данных

2. Последовательная передача данных

3. Связь компьютеров по телефонным линиям

Лекция 15. Классификация данных. Представление данных в памяти компьютера

1. Классификация данных

2. Представление элементарных данных в озу

Лекция 16. Классификация структур данных

1. Классификация и примеры структур данных

2. Понятие логической записи

Лекция 17. Организация структур данных в оперативной памяти и на внешних носителях

1. Организация структур данных в озу

2. Иерархия структур данных на внешних носителях

3. Особенности устройств хранения информации

Контрольные вопросы

Список литературы

3. Коды без разделителя. Условие Фано

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

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

Наиболее простыми и употребимыми кодами без разделителя являются так называемые префиксные коды , которые удовлетворяют следующему условию –условию Фано :Сообщение, закодированное с использованием неравномерного кода может быть однозначно декодировано, если никакой из кодов в данном сообщении не совпадает с префиксом * (началом) какого-либо иного более длинного кода.

Например, если имеется код 110, то уже не могут использоваться коды 1, 11, 1101, 110101 и пр.

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

Пример 1 . Являются ли коды, представленные втабл. 4,префиксными? Коды, представленные в табл. 4, не являются префиксными. См., например, коды букв «О» и «Е», «А» и «Н», «С» и «М», «Д» и «Ч».

Пример 2 . Имеется таблица префиксных кодов (табл. 6). Требуется декодировать следующее сообщение, закодированное с использованием этой приведенной кодовой таблицы:

00100010000111010101110000110

Табл. 6. Таблица префиксных кодов

Декодирование производится циклическим повторением следующих действий:

«Отрезать» от текущего сообщения крайний слева символ, присоединить его справа к рабочему (текущему) кодовому слову;

сравнить текущее кодовое слово с кодовой таблицей; если совпадения нет, вернуться к пункту 1.

С помощью кодовой таблицы текущему кодовому слову поставить в соответствие символ первичного алфавита;

Проверить, имеются ли еще знаки в закодированном сообщении; если да, то перейти к пункту 1.

Применение данного алгоритма к предложенному выше закодированному сообщению дает:

00100010000111010101110000110

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

Таким образом, использование префиксного кодирования позволяет делать сообщение более коротким, поскольку нет необходимости передавать разделители знаков.

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

4. Префиксный код Шеннона–Фано

Рассмотрим вариант кодирования, который был предложен в 1948 – 1949 гг. независимо К. Шенноном и Р. Фано.

Рассмотрим схему кодирования (как она строится) Шеннона–Фано на следующем примере .

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

Разделим знаки на две группы так, чтобы суммы вероятностей в каждой из этих двух групп были бы приблизительно равными. При этом в 1-ю группу попадут и, а остальные – во 2-ю группу. Знакампервой группы присвоим первый слева разряд их кодов «0», а первым слева разрядом кодов символов второй группы пусть будет «1».

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

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

Табл. 7. Построение кода Шеннона-Фано

Знак		Разряды кода

Видно, что построенные коды знаков удовлетворяют условию Фано, следовательно, такое кодирование является префиксным.

Найдем среднюю длину полученного кода по формуле

,

где – число разрядов (символов) в коде, соответсвующем символу.

Из таблицы видно, что
,
,
.

Таким образом, получаем:

Таким образом, для кодирования одного символа первичного алфавитапотребовалось в среднем 2.45 символов вторичного (двоичного) алфавита.

Определим среднее количество информации, приходящееся на знак первичного алфавита в первом приближении (с учетом различной вероятности появления этих знаков в сообщениях). Применим формулу Шеннона:

.

Найдем избыточность полученного двоичного кода:

,

то есть избыточность – около 2.5.

Выясним, является ли полученный код оптимальным. Нулей в полученных кодах – 6 штук, а единиц – 11 штук. Таким образом, вероятности появления 0 и 1 далеко не одинаковы. Следовательно, полученный код нельзя считать оптимальным.

Урок посвящен тому, как решать 5 задание ЕГЭ по информатике

5-я тема характеризуется, как задания базового уровня сложности, время выполнения – примерно 2 минуты, максимальный балл — 1

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

Пример: Зашифруем буквы А, Б, В, Г при помощи двоичного кодирования равномерным кодом и посчитаем количество возможных сообщений:

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

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

Декодирование (расшифровка) - это восстановление сообщения из последовательности кодов.

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

Условие Фано: ни одно кодовое слово не должно являться началом другого кодового слова (что обеспечивает однозначное декодирование сообщений с начала)

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

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

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

ЕГЭ 5.1: Для кодирования букв О, В, Д, П, А решили использовать двоичное представление чисел 0 , 1 , 2 , 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления).

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

✍ Решение:

• Переведем числа в двоичные коды и поставим их в соответствие нашим буквам:

О -> 0 -> 00 В -> 1 -> 01 Д -> 2 -> 10 П -> 3 -> 11 А -> 4 -> 100

Теперь закодируем последовательность букв из слова ВОДОПАД:

010010001110010

Разобьем результат на группы из трех символов справа налево, чтобы перевести их в восьмеричную систему счисления:

010 010 001 110 010 ↓ ↓ ↓ ↓ ↓ 2 2 1 6 2

Результат: 22162

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

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

ЕГЭ 5.2: Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв - из двух бит, для некоторых - из трех). Эти коды представлены в таблице:

a	b	c	d	e
000	110	01	001	10

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

✍ Решение:

• Во-первых, проверяем условие Фано: никакое кодовое слово не является началом другого кодового слова. Условие верно.

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

• Код разбиваем слева направо согласно данным, представленным в таблице. Затем переведём его в буквы:

110 000 01 001 10 ↓ ↓ ↓ ↓ ↓ b a c d e

Результат: b a c d e.

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

110 000 01 001 10

Результат: b a c d e.

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

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

ЕГЭ 5.3:
Для передачи чисел по каналу с помехами используется код проверки четности. Каждая его цифра записывается в двоичном представлении, с добавлением ведущих нулей до длины 4 , и к получившейся последовательности дописывается сумма её элементов по модулю 2 (например, если передаём 23 , то получим последовательность 0010100110).

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

✍ Решение:

• Рассмотрим пример из условия задачи:

Было 23 10 Стало 0010100110 2

Где сами цифры исходного числа (выделим их красным цветом):

0010 10011 0 (0010 - 2, 0011 - 3)

Первая добавленная цифра 1 после двоичной двойки — это проверка четности (1 единица в 0010 — значит нечетное), 0 после двоичной тройки — это также проверка нечетности (2 единицы в 0011 , значит — четное).

Исходя из разбора примера решаем нашу задачу так: поскольку «нужные» нам цифры образуются из групп по 4 числа в каждой плюс одно число на проверку четности, то разобьем закодированное сообщение на группы по 5, и отбросим из каждой группы последний символ:

разбиваем по 5:

01100 01010 01001 00110

отбрасываем из каждой группы последний символ:

0110 0101 0100 0011

Результат переводим в десятичную систему:

0110 0101 0100 0011 ↓ ↓ ↓ ↓ 6 5 4 3

Ответ: 6 5 4 3

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

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

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

✍ Решение:

✎ 1 вариант решения основан на логических умозаключениях:

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

(Н)1 + (К)2 + (Л)3 + (М)3 = 9

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

(Н) -> 0 -> 1 символ (К) -> 10 -> 2 символа (Л) -> 110 -> 3 символа (М) -> 111 -> 3 символа

Суммарная длина всех четырёх кодовых слов равна:

(Н)1 + (К)2 + (Л)3 + (М)3 = 9

Ответ: 9

ЕГЭ по информатике 5 задание 2017 ФИПИ вариант 2 (под редакцией Крылова С.С., Чуркиной Т.Е.):

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

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

✍ Решение:

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

Результат: 00

ЕГЭ по информатике 5 задание 2017 ФИПИ вариант 16 (под редакцией Крылова С.С., Чуркиной Т.Е.):

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

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

✍ Решение:

Результат: 101

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

ЕГЭ по информатике 5 задание 2017 ФИПИ вариант 17 (Крылов С.С., Чуркина Т.Е.):

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

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

✍ Решение:

1 - не подходит (все буквы кроме А начинаются с 1) 10 - не подходит (соответствует коду Д) 11 - не подходит (начало кодов Б, В и Г) 100 - не подходит (код Д - 10 - является началом данного кода) 101 - не подходит (код Д - 10 - является началом данного кода) 110 - не подходит (начало кода В и Г) 111 - не подходит (соответствует коду Б) 1000 - не подходит (код Д - 10 - является началом данного кода) 1001 - не подходит (код Д - 10 - является началом данного кода) 1010 - не подходит (код Д - 10 - является началом данного кода) 1011 - не подходит (код Д - 10 - является началом данного кода) 1100 - не подходит (начало кода В и Г) 1101 - подходит

Результат: 1101

Более подробное решение данного задания представлено в видеоуроке:

5 задание. Демоверсия ЕГЭ 2018 информатика (ФИПИ):

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

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

✍ Решение:

Результат: 1100

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

Задание 5_9. Типовые экзаменационные варианты 2017. Вариант 4 (Крылов С.С., Чуркина Т.Е.):

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

А: 00011 Б: 111 В: 1010

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

✍ Решение:

Результат: 00

Задание 5_10. Тренировочный вариант №3 от 01.10.2018 (ФИПИ):

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

Е – 000 Д – 10 К – 111

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

✍ Решение:

Д Е Д М А К А Р 10 000 10 001 01 111 01 110

Посчитаем количество цифр в итоговом коде и получим 20 .

Результат: 20

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

Демонстрационный вариант ЕГЭ 2019 г. – задание №5

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 0; для буквы Б – кодовое слово 10. Какова наименьшая возможная сумма длин кодовых слов для букв В, Г, Д, Е?

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

Решение:

Ответ:

Демонстрационный вариант ЕГЭ 2018 г. – задание №5

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

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

Решение:

Ответ: 1100

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 0; для буквы Б – кодовое слово 10. Какова наименьшая возможная сумма длин всех шести кодовых слов?
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Демонстрационный вариант ЕГЭ 2017 г. – задание №5

Решение:

Для на­хож­де­ния ко­до­вых слов будем ис­поль­зо­вать данную таблицу.

Если коды остальных букв будет начинаться на 0, код буквы А=0 будет яв­ля­ть­ся на­ча­лом их кодов, по­это­му этот ва­ри­ант не под­хо­дит. Если код Б=10, коды букв В, Г, Д, Е начинаются на11. Чтобы получить 4 разных кода, нужно использовать коды, состоящие из 4-х символов (1111, 1110, 1101, 1100) .

0	1
	1
	1		0
	1	0	1	0

А - 0 (1 символ)
Б - 10 (2 символа)
В - 1100 (4 символа)
Г - 1101 (4 символа)
Д - 1110 (4 символа)
Е - 1111 (4 символа)

1+2+4+4+4+4 = 19

Ответ: 19

Демонстрационный вариант ЕГЭ 2016 г. – задание №5

По каналу связи передаются сообщения, содержащие только четыре буквы: П, О, С, Т; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв Т, О, П используются такие кодовые слова: Т: 111, О: 0, П: 100.

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

Решение:

Для на­хож­де­ния ко­до­вых слов будем ис­поль­зо­вать данную схему.

Если коды остальных букв будет начинаться на 0 , код буквы О =0 будет яв­ля­ть­ся на­ча­лом их кодов, по­это­му этот ва­ри­ант не под­хо­дит. Так как код буквы П =100 , а код буквы Т =111 , то буква С не может начинаться и заканчиваться этими цифрами.

Ответ: 101

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

Если таким способом закодировать последовательность символов ГАВБГВ и записать результат в шестнадцатеричном коде, то получится:

1) DACBDC 1 6 2) AD26 16 3) 621310 16 4) 62DA 16

Решение:

ГАВБГВ = 0110001011011010

0110	0010	1101	1010
6	2	D	A

Ответ: 4

Черно-белое растровое изображение кодируется построчно, начиная с левого верхнего угла и заканчивая в правом нижнем углу. При кодировании 1 обозначает черный цвет, а 0 – белый.

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

1) 57414 2) 53414 3) 53412 4) 53012

Решение:

1	0	1	0	1
1	1	0	0	0
0	1	0	1	0

101	011	100	001	010
5	3	4	1	2

Ответ: 3

Для передачи чисел по каналу с помехами используется код проверки четности. Каждая его цифра записывается в двоичном представлении, с добавлением ведущих нулей до длины 4, и к получившейся последовательности дописывается сумма её элементов по модулю 2 (например, если передаём 23, то получим последовательность 0010100110). Определите, какое число передавалось по каналу в виде 01100010100100100110?

1) 6543 2) 62926 3) 62612 4) 3456

Решение:

01100010100100100110

01100	01010	01001	00110
6	5	4	3

Ответ: 1

Для кодирования букв О, Л, А, З, К используются двоичные коды чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Если таким способом закодировать последовательность символов ЗАКОЛКА и записать результат в шестнадцатеричном коде, то получится:

1) 4531253 2) 9876 3) E832 4) 238E

Решение:

О	Л	А	З	К
0=00	1=01	2=10	3=11	4=100

ЗАКОЛКА = 1110100000110010

1110	1000	0011	0010
E	8	3	2

Ответ: 3

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

1) 010 2) 0 3) 01 4) 011

Решение:

A=00, Б=11, В=100, Г=?

Ответ: 3

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

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

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

1) 1 2) 0 3) 01 4) 10

Решение:

А — 111, Б — 110, В — 101, Г — 100, Д — ?

Ответ: 2

По каналу связи передаются сообщения, содержащие только 4 буквы: А, Б, В, Г. Для кодирования букв А, Б, В используются 5-битовые кодовые слова: А — 10110, Б — 11000, В — 00101. Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех. Какое из перечисленных ниже кодовых слов можно использовать для буквы Г, чтобы указанное свойство выполнялось для всех четырёх кодовых слов?

1) 01110 2) 01011 3) 10001 4) не подходит ни одно из указанных выше слов

Решение:

1) 01 110: А — 10 110 — не отличаются не менее чем в трёх позициях

2) 01011: А — 101 10 , Б — 1 1000 , В — 0010 1 — отличаются не менее чем в трёх позициях

Ответ: 2

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

А — 10001, Б — 01101, В — 10110.

При передаче возможны помехи. Однако некоторые ошибки можно попытаться исправить. Любые два из этих трёх кодовых слов отличаются друг от друга не менее чем в трёх позициях. Поэтому если при передаче слова произошла ошибка не более чем в одной позиции, то можно сделать обоснованное предположение о том, какая буква передавалась. (Говорят, что «код исправляет одну ошибку».) Например, если получено кодовое слово 01111, считается, что передавалась буква Б. (Отличие от кодового слова для Б только в одной позиции, для остальных кодовых слов отличий больше.) Если принятое кодовое слово отличается от кодовых слов для букв А, Б, В более чем в одной позиции, то считается, что произошла ошибка (она обозначается ‘х’).

Получено сообщение 00110 11101 11000 11001. Декодируйте это сообщение – выберите правильный вариант.

1) ВБхх 2) ВБВА 3) хххх 4) ВБхА

Решение:

00110	11101	11000	11001
В=1 0110	Б=0 1101	x	А=10 001

Ответ: 4

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А – 1; Б – 0100; В – 000; Г – 011; Д – 0101. Требуется сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно. Коды остальных букв меняться не должны. Каким из указанных способов это можно сделать?

1) для буквы Г – 11 2) для буквы В – 00 3) для буквы Г – 01 4) это невозможно

Решение:

Ответ: 2

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 1, для буквы Б – кодовое слово 011. Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?

1) 7 2) 8 3) 9 4) 10

Решение:

А-1, Б-011, В-00, Г-010

Ответ: 9

По каналу связи передаются сообщения, каждое из которых содержит 15 букв А, 10 букв Б, 6 букв В и 4 буквы Г (других букв в сообщениях нет). Каждую букву кодируют двоичной последовательностью. При выборе кода учитывались два требования:

а) ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование);

б) общая длина закодированного сообщения должна быть как можно меньше.

Какой код из приведённых ниже следует выбрать для кодирования букв А, Б, В и Г?

1) А:1, Б:01, В:001, Г:111

2) А:1, Б:01, В:10, Г:111

3) А:00, Б:01, В:10, Г:11

4) А:100, Б:101, В:11, Г:0

Решение:

Ни одно кодовое слово не является началом другого: А является началом Г в 1-й и 2-й вариантах.

Общая длина закодированного сообщения должна быть как можно меньше.

3) А:00 (15), Б:01 (10), В:10 (6), Г:11 (4)

2.15+2.10+2.6+2.4 = 70

4) А:100 (15), Б:101 (10), В:11 (6), Г:0 (4)

3.15+3.10+2.6_1.4 = 61

Ответ: 3

По каналу связи с помощью равномерного двоичного кода передаются сообщения, содержащие только 4 буквы П, Р, С, Т. Каждой букве соответствует своё кодовое слово, при этом для набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех. Для кодирования букв П, Р, С используются 5-битовые кодовые слова: П: 01111, Р: 00001, С: 11000. 5-битовый код для буквы Т начинается с 1 и заканчивается на 0. Определите кодовое слово для буквы Т.

Решение:

С: 1 1000

Т: 1 0110 (Т начинается с 1 и заканчивается на 0)

С и Т: 2 буквы одинаковы, то это означает, что остальные 3 буквы должны быть разными.

Ответ: 1 0110