По каналу связи передается сообщение каждое из которых содержит 32 буквы а 16 букв б

Обновлено: 29.06.2024

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

Что нужно знать:

· кодирование – это перевод информации с одного языка на другой (запись в другой системе символов, в другом алфавите)

· кодирование может быть равномерное и неравномерное;
при равномерном кодировании все символы кодируются кодами равной длины;
при неравномерном кодировании разные символы могут кодироваться кодами разной длины, это затрудняет декодирование

· условие Фано – это достаточное, но не необходимое условие однозначного декодирования.

Пример задания

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

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

1) А:0, Б:10, В:110, Г:111

2) А:0, Б:10, В:01, Г:11

3) А:1, Б:01, В:011, Г:001

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

Решение:

1) сначала выберем коды, в которых ни одно кодовое слово не совпадет с началом другого (такие коды называю префиксными)

4) для кодов 1 и 4 условие выполняется, их рассматриваем дальше

16∙1 + 8·2 + 4∙3 + 4∙3 = 56 битов

16∙2 + 8·2 + 4∙2 + 4∙2 = 64 бита

Пример задания

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

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

Решение (способ 1, исключение вариантов):

1) условие Фано означает, что ни одно кодовое слово не совпадает с началом другого кодового слова

2) поскольку уже есть кодовое слово 0, ни одно другое кодовое слово не может начинаться с 0

3) поскольку есть код 110, запрещены кодовые слова 1, 11; кроме того, ни одно другое кодовое слово не может начинаться с 110

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

5) есть одно допустимое кодовое слово из двух символов: 10

6) если выбрать кодовое слово 10 для буквы В, то остаётся одно допустимое трёхсимвольное кодовое слово – 111, которое можно выбрать для буквы Г

7) таким образом, выбрав кодовые слова А – 0, Б – 110, В – 10, Г – 111, получаем суммарную длину кодовых слов 9 символов

8) если же не выбрать В – 10, то есть три допустимых трёхсимвольных кодовых слова: 100, 101 и 110; при выборе любых двух их них для букв В и Г получаем суммарную длину кодовых слов 10, что больше 9; поэтому выбираем вариант 3 (9 символов)

Решение (способ 2, построение дерева):

1) условие Фано означает, что ни одно кодовое слово не совпадает с началом другого кодового слова; при этом в дереве кода все кодовые слова должны располагаться в листьях дерева, то есть в узлах, которые не имеют потомков;

2) построим дерево для заданных кодовых слов А – 0 и Б – 110:

4) таким образом, выбрав кодовые слова А – 0, Б – 110, В – 10, Г – 111, получаем суммарную длину кодовых слов 9 символов

Базовый уровень, время – 2 мин)

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

Что нужно знать:

· условие Фано – это достаточное, но не необходимое условие однозначного декодирования.

Пример задания

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

1) А:0, Б:10, В:110, Г:111

2) А:0, Б:10, В:01, Г:11

3) А:1, Б:01, В:011, Г:001

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

Решение:

4) для кодов 1 и 4 условие выполняется, их рассматриваем дальше

16∙1 + 8·2 + 4∙3 + 4∙3 = 56 битов

16∙2 + 8·2 + 4∙2 + 4∙2 = 64 бита

Пример задания

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

Решение (способ 1, исключение вариантов):

1) условие Фано означает, что ни одно кодовое слово не совпадает с началом другого кодового слова

2) поскольку уже есть кодовое слово 0, ни одно другое кодовое слово не может начинаться с 0

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

5) есть одно допустимое кодовое слово из двух символов: 10

Решение (способ 2, построение дерева):

2) построим дерево для заданных кодовых слов А – 0 и Б – 110:

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

1) А:0, Б:10, В:110, Г:111
2) А:0, Б:10, В:01, Г:11
3) А:1, Б:01, В:011, Г:001
4) А:00, Б:01, В:10, Г:11

И объясните, почему, пожалуйста.

Ира Яронкина
Информатика
2019-05-17 18:25:27
0
2

2) и 3) не подходят, так как нет конкретного декодирования.
Из 1) и 4) код кратче в 1)ответе
1) 1*16+2*8+3*4+3*4=56
4)2*16+2*8+2*4+2*4=64
отв. 1

Каждую букву кодируют двоичной последовательностью.

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

В а) записано условие Фано.

Будем использовать известный алгоритм Шеннона - Фано для построения кода.

Не вижу смысла тут описывать этот алгоритм : он хорошо известен и может быть быстро найден в учебниках или в Интернет.

Этапы построения кода даны во вложении.

Вероятности появления символов :

Z(a) = 8 / 64 = 1 / 8 ; Z(б) = Z(a) = 1 / 8 ; Z(в) = 16 / 64 = 1 / 4 ; Z(г) = 32 / 64 = 1 / 2.

В построенном коде символы выглядят так :

Суммарная длина кодовых слов составляет 1 + 2 + 3 + 3 = 9 бит.

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

Для букв Т О М используются такие кодовые слова Т : 100, О : 00, М : 11.

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

Если таких кодов несколько, укажите тот, у которого меньше длина.

Каждую букву кодируют двоичной последовательностью.

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

1) А : 0, Б : 10, В : 110, Г : 111 2) А : 0, Б : 10, В : 01, Г : 11 3) А : 1, Б : 01, В : 011, Г : 001 4) А : 00, Б : 01, В : 10, Г : 11 И объясните, почему, пожалуйста.

Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано?

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

Для буквы Н использовали кодовое слово 0, для буквы К – кодовое слово 10.

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

Для кодирования некоторой последовательности, состоящей из букв И, К, Л, М, Н, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано?

Для кодирования некоторой последовательности, состоящей из букв И, К, Л, М, Н, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано.

Для буквы Н использовали кодовое слово 0, для буквы К – кодовое слово 10.

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

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

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

Для букв А, Б, В используются такие кодовые слова : А - 000, Б - 1, В - 011.

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

Если таких кодов несколько, укажите код с наименьшим числовым значением.

СРОЧНО?

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

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

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

Если таких кодов несколько, укажите код с наименьшим числовым значением.

Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано ; для букв А, Б, В используются такие кодовые слова : А - 0, Б - 101, В - 110.

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

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

Коды, удовлетворяющие условию Фано, допускают однозначное декодирование.

Причем используются только буквы Б, У и М.

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

Для букв К, А, Н используются такие кодовые слова : К : 00, А : 1, Н : 010.

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

Если таких кодов несколько, укажите код с наименьшим числовым значением.

Картины. Рисунки. Фотографии. Сижу и рисую картину. Просматриваю старые фотографии. Смотрю детске рисунки.

236 Кбайт = 236 * 1024 * 8 = 1933312 бит 1933312 бит / 128000бит / с = 15, 104 секунды.

Дано : N = 16 I = 1 / 16Mb найти : К решение 1)16 = 2 в степени i , значит i = 4 формула N = 2i 2) I = K * i K = I / i I = 1 / 16Mb = 1024Kb : 16 = 64 KB K = 64 KB : 4 = 26 символов Ответ 26.

Первое - 6000 Второе ~185096282 раз.

Const a = 12 ; b = 19 ; var i : integer ; z : real ; begin for i : = a to b do z : = z + exp(sin(i)) ; writeln('Z = ', z) ; end. Const a = - 10 ; b = 19 ; var i : integer ; x : real ; begin for i : = a to b do begin x : = i ; if i>a then writeln('F3..

Var a : real ; begin readln(a) ; Writeln(a, ' км = ', 8 / 5 * a, ' миль') ; end.

Program abc ; Var X, y, c : Integer ; Begin C : = 0 ; Readln(x) ; Read(y) ; If y>60 then c : = (x * 25) + ((x + (x / 4)) * y - 60) ; Else c : = x * y ; Writeln(c) ; End. Примерно так. Y - это количество газет.

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

За это задание ты можешь получить 1 балл. На решение дается около 3 минут. Уровень сложности: базовый.
Средний процент выполнения: 84.4%
Ответом к заданию 4 по информатике может быть цифра (число) или слово.

Задачи для практики

Задача 1

Решение

Задача 2

Решение

Задача 3

Решение

Задача 4

Решение

Для решения данной задачи рассмотрим дерево, у которого из корня и любой вершины выходят по две ветви. Сопоставим каждой левой ветви 0, а каждой правой — 1. Тогда, проходя от вершины к каждому из листьев (узлов, из которых не выходят ветви) и выписывая последовательность нулей и единиц, соответствующих обходу дерева, получим набор кодовых слов, образующих префиксный код (код, в котором ни одно кодовое слово не является началом другого). Префиксный код является однозначно декодируемым.

На основе дерева получим кодовые слова 0, 01, 110 и 111.

Задача 5

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, в котором ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование). Известно, что для двух букв были использованы кодовые слова 10 и 110. Определите наименьшую возможную суммарную длину всех шести кодовых слов.

Решение

Задача 6

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, решили использовать неравномерный двоичный код, в котором ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование). Известно, что для двух букв были использованы кодовые слова 10 и 111.

Определите наименьшую возможную суммарную длину всех пяти кодовых слов.

Решение

Задача 7

Определите наименьшую возможную суммарную длину всех пяти кодовых слов.

Решение

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

Однако построенное дерево соответствует коду, содержащему только 4 кодовых слова. По условию задачи требуется пять кодовых слов. Для этого следует продолжить построение дерева для одного из узлов: 00 или 011.

Продолжив построение из узла 00, мы получим кодовые слова 000, 001, 010, 011, 1. Суммарная длина всех кодовых слов равна 3 + 3 + 3 + 3 + 1 = 13.

Продолжив построение из узла 0110, мы получим кодовые слова 00, 010, 0011, 0111, 1. Суммарная длина всех кодовых слов равна 2 + 3 + 4 + 4 + 1 = 14.

Следовательно, наименьшая возможная длина всех кодовых слов равна 13.

Задача 8

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А − 01, Б − 11, В − 001, Г − 0001, Д − 0000.

Определите букву, для которой можно сократить длину кодового слова так, чтобы код по-прежнему можно было однозначно декодировать. Коды остальных букв меняться не должны. В ответе укажите букву и её сокращенное кодовое слово без пробелов и запятых. Например, А0.

Решение

Условие однозначного декодирования (условие Фано) заключается в том, что однозначное декодирование возможно, только если ни одно кодовое слово не является началом другого кодового слова. В данной задаче нужно просмотреть кодовые слова для каждой из букв и проверить будет ли выполняться условие Фано, если мы каким-нибудь образом сократим данное кодовое слово. Например, рассмотрим букву А – 01. Если заменить её код на 1, то он будет являться началом кода буквы Б. Если заменить код на 0, то он будет являться началом кодов букв В, Г и Д. Таким образом, при любом сокращении кода буквы А условие Фано нарушается. Проверив подобным образом все буквы, приходим к выводу, что можно сократить букву Б, закодировав её словом 1. В таком случае нарушения условия Фано не произойдёт.

Задача 9

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код:А − 01, Б − 10, В − 110, Г − 001, Д − 000.

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

В ответе укажите букву и её сокращенное кодовое слово без пробелов и запятых. Например, А0.

Решение

Условие однозначного декодирования (условие Фано) заключается в том, что однозначное декодирование возможно, только если ни одно кодовое слово не является началом другого кодового слова. В данной задаче нужно просмотреть кодовые слова для каждой из букв и проверить будет ли выполняться условие Фано, если мы каким-нибудь образом сократим данное кодовое слово. Например, рассмотрим букву А – 01. Если заменить её код на 1, то он будет являться началом кодов букв Б и В. Если заменить код на 0, то он будет являться началом кодов букв Г и Д. Таким образом, при любом сокращении кода буквы А условие Фано нарушается. Проверив подобным образом все буквы, приходим к выводу, что можно сократить букву В, закодировав её словом 11. В таком случае нарушения условия Фано не произойдёт.

Задача 10

Решение

Условие однозначного декодирования (условие Фано) заключается в том, что однозначное декодирование возможно, только если ни одно кодовое слово не является началом другого кодового слова. В данной задаче нужно просмотреть кодовые слова для каждой из букв и проверить будет ли выполняться условие Фано, если мы каким-нибудь образом сократим данное кодовое слово. Например, рассмотрим букву А – 01. Если заменить её код на 1, то он будет являться началом кодов букв Б, Г и Д. Если заменить код на 0, то он будет являться началом кода буквы В. Таким образом, при любом сокращении кода буквы А условие Фано нарушается. Проверив подобным образом все буквы, приходим к выводу, что можно сократить букву В, закодировав её словом 00. В таком случае нарушения условия Фано не произойдёт.

Задача 11

Решение

Для решения данной задачи построим дерево, у которого из корня и любой вершины выходят по две ветви. Сопоставим каждой левой ветви 0, а каждой правой — 1. Тогда, проходя от вершины к каждому из листьев (узлов, из которых не выходят ветви) и выписывая последовательность нулей и единиц, соответствующих обходу дерева, получим набор кодовых слов, образующих префиксный код (код, в котором ни одно кодовое слово не является началом другого). Префиксный код является однозначно декодируемым. На рисунке представлено дерево, соответствующее заданному коду.

При сокращении кодового слова в дереве нужно заменить один из полученных листьев узлом более высокого уровня. Такая возможность есть только для кодового слова буквы Г. Вместо листа 100 можно взять узел более высокого уровня 10.

В этом случае полученный код: А — 00, Б — 01, В — 110, Г — 10, Д — 111 — будет префиксным и однозначно декодируемым.

Задача 12

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, допускающий однозначное декодирование. Для букв А, Б, В и Г используются следующие кодовые слова: А − 10, Б − 11, В − 000, Г − 001. Укажите, каким кодовым словом может быть закодирована буква Д, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Решение

Условие однозначного декодирования (условие Фано) заключается в том, что однозначное декодирование возможно, только если ни одно кодовое слово не является началом другого кодового слова. Известны кодовые слова 10, 11, 000, 001, следовательно, для других кодовых слов мы можем использовать только коды, начинающиеся с 01. Слово 01 можно использовать в качестве кодового, т.к. условие Фано для него выполняется. Это кодовое слово является минимальным, т.к. любой код меньший длины в данном случае не будет удовлетворять условию Фано.

Задача 13

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, допускающий однозначное декодирование. Для букв А, Б, В и Г используются следующие кодовые слова: А − 00, Б − 011, В − 010, Г − 10. Укажите, каким кодовым словом может быть закодирована буква Д, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Решение

Условие однозначного декодирования (условие Фано) заключается в том, что однозначное декодирование возможно, только если ни одно кодовое слово не является началом другого кодового слова. Известны кодовые слова 00, 011, 010, 10, следовательно, для других кодовых слов мы можем использовать только коды, начинающиеся с 11. Слово 11 можно использовать в качестве кодового, т.к. условие Фано для него выполняется. Это кодовое слово является минимальным, т.к. любой код меньший длины в данном случае не будет удовлетворять условию Фано.

Задача 14

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, допускающий однозначное декодирование. Для букв А, Б, В и Г используются следующие кодовые слова: А − 000, Б − 001, В − 010, Г − 011. Укажите, каким кодовым словом может быть закодирована буква Д, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Решение

Условие однозначного декодирования (условие Фано) заключается в том, что однозначное декодирование возможно, только если ни одно кодовое слово не является началом другого кодового слова. Известны кодовые слова 000, 001, 010, 011, следовательно, для других кодовых слов мы можем использовать только коды, начинающиеся с 1. Слово 1 можно использовать в качестве кодового, т.к. условие Фано для него выполняется.

Задача 15

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

Решение

Задача 16

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

Решение

Задача 17

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

Решение

Необходимо зарегистрироваться

Для доступа к решениям необходимо включить уведомления от группы Турбо в вк — это займет буквально 10 секунд. Никакого спама, только самое важное и полезное для тебя. Ты всегда можешь запретить уведомления.

Читайте также: