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

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

Ответ: 19 ___________________________.

Решение:
1) Кодируем:
А 0
Б 10
В 110
Г 1110
Д 1111
Е 10000
итого:19 Ответ: 19

1. Еще одна задача

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

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

1) 00; 2) 001; 3) 10; 4) 101

Решение. Набор кодовых слов для букв А, Б, В, Г является префиксным (ни одно из них не является началом другого). Посмотрим, нет ли среди предложенных вариантов такого, после добавления которого код останется префиксным. Однако, в отличие от задачи из демо-варианта, здесь по условию более одного варианта может приводить к тому, что получится код, допускающий однозначное декодирование. Поэтому нужно перебирать варианты от более коротких к более длинных и, если вариант не приводит к префиксному коду, убеждаться, что этот вариант действительно дает код, не допускающий однозначного декодирования.

1) Код для Д: 00 – не допускает однозначного декодирования (00 допускает две расшифровки: ГГ и Д).

2) Код для Д: 10 – не допускает однозначного декодирования (100 допускает две расшифровки: В и ДГ).

3) Код для Д: 001 – не допускает однозначного декодирования (00100 допускает две расшифровки: ГГВ и ДГГ).

4) Код для Д: 101 – вместе с кодами для А, Б, В, Г образует префиксный код.

Правильный ответ : 4

Еще одна Задача 2 .

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

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

Решение . Набор кодовых слов для букв А, Б, В, Г является префиксным (ни одно из них не является началом другого). Посмотрим, нет ли среди предложенных вариантов такого, после добавления которого код останется префиксным.

1) 00 – не подходит (является началом кодового слова 000 для буквы Б);

2) 01 – не подходит (является началом кодового слова 011 для буквы Г);

3) 11– не подходит (является продолжением(!) кодового слова 1 для буквы А);

4) 010 – подходит! (не является ничьим началом и никто не является его началом).

Ответ : 4.

Замечание 1. Условие Фано является достаточным условием того, что код допускает однозначное декодирование, но не является необходимым. То есть код может допускать однозначное декодирование, но не удовлетворять условию Фано. Простейший пример таких кодов – т.н. постфиксные коды. Это такие коды, в которых никакое кодовое слово не является концом другого кодового слова. Для этих кодов расшифровка производится так же, как и для префиксных кодов, но двигаясь справа налево.

Замечание 2. В рассмотренной задаче А достаточно найти один вариант, удовлетворяющий требованиям задачи. НЕ ТРЕБУЕТСЯ доказывать, что при остальных вариантах код не будет допускать однозначного декодирования. Однако, в данном случае это сделать несложно. А именно.

Каталог заданий. Передача информации. Выбор кода

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

Ответ:

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

Ответ:

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

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

1) это невозможно

2) для буквы В – 000

3) для буквы Б – 0

4) для буквы Г – 11

Ответ:

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

1) это невозможно

2) для буквы А – 01

3) для буквы Б – 00

4) для буквы Г – 00

Ответ:

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

1) для буквы Д – 11

2) это невозможно

3) для буквы Г – 10

4) для буквы Д – 10

Ответ:

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

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

Ответ:

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

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

Ответ:

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

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

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

Ответ:

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

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

Ответ:

По ка­на­лу связи пе­ре­да­ют­ся сообщения, со­дер­жа­щие только 4 буквы: E, H, O, T. Для ко­ди­ро­ва­ния букв E, H, O ис­поль­зу­ют­ся 5-битовые ко­до­вые слова: E — 00000, H — 00111, O — 11011.

.

4) не под­ходит ни одно из ука­зан­ных выше слов

Ответ:

По ка­на­лу связи пе­ре­да­ют­ся сообщения, со­дер­жа­щие только 4 буквы: П, О, Р, T. Для ко­ди­ро­ва­ния букв П, О, Р ис­поль­зу­ют­ся 5-битовые ко­до­вые слова: П — 11111, О — 11000, Р — 00100.

Для этого на­бо­ра кодовых слов вы­пол­не­но такое свойство: любые два слова из на­бо­ра отличаются не менее чем в трех позициях .

Это свой­ство важно для рас­шиф­ров­ки сообщений при на­ли­чии помех. Какое из пе­ре­чис­лен­ных ниже ко­до­вых слов можно ис­поль­зо­вать для буквы T, чтобы ука­зан­ное свойство вы­пол­ня­лось для всех четырёх ко­до­вых слов?

4) не под­хо­дит ни одно из ука­зан­ных слов

Ответ:

По каналу связи передаются сообщения, содержащие только 4 буквы: Е, Н, О, Т.

В любом сообщении больше всего букв О, следующая по частоте буква − Е, затем − Н. Буква Т встречается реже, чем любая другая.

Для передачи сообщений нужно использовать неравномерный двоичный код, допускающий однозначное декодирование; при этом сообщения должны быть как можно короче. Шифровальщик может использовать один из перечисленных ниже кодов. Какой код ему следует выбрать?

1) Е−0, Н−1, O−00, Т−11

2) O−1, Н−0, Е−01,Т−10

3) Е−1, Н−01, O−001, Т−000

4) О−0, Н−11, Е−101, Т−100

Ответ:

По ка­на­лу связи пе­ре­да­ют­ся сообщения, со­дер­жа­щие только 4 буквы: А, И, С, Т.

В любом со­об­ще­нии больше всего букв А, сле­ду­ю­щая по ча­сто­те буква — С, затем — И. Буква Т встре­ча­ет­ся реже, чем любая другая.

Для пе­ре­да­чи сообщений нужно ис­поль­зо­вать неравномерный дво­ич­ный код, до­пус­ка­ю­щий однозначное декодирование; при этом со­об­ще­ния должны быть как можно короче. Шиф­ро­валь­щик может ис­поль­зо­вать один из пе­ре­чис­лен­ных ниже кодов. Какой код ему сле­ду­ет выбрать?

1) А−0, И−1, С−00, Т−11

2) С−1, И−0, А−01, Т−10

3) А−1, И−01, С−001, Т−000

4) С−0, И−11, А−101, Т−100

Ответ:

По ка­на­лу связи пе­ре­да­ют­ся сообщения, со­дер­жа­щие толь­ко 4 буквы: И, Г, Л, А. Для ко­ди­ро­ва­ния букв И, Г, Л ис­поль­зу­ют­ся 6-битовые ко­до­вые слова:

И - 000000, Г - 001110, Л - 110110.

Для этого на­бо­ра ко­до­вых слов вы­пол­не­но такое свойство: любые два слова из на­бо­ра от­ли­ча­ют­ся не менее, чем в трёх позициях. Это свой­ство важно для рас­шиф­ров­ки со­об­ще­ний при на­ли­чии помех. Нужно по­до­брать ко­до­вое слово для буквы А так, чтобы ука­зан­ное свой­ство вы­пол­ня­лось для всех четырёх ко­до­вых слов.

Можно ли ис­поль­зо­вать одно из таких слов: 111110, 111000, 000110?

Ответ:

По ка­на­лу связи пе­ре­да­ют­ся сообщения, со­дер­жа­щие толь­ко 4 буквы: П, А, Р, К. Для ко­ди­ро­ва­ния букв П, А, Р ис­поль­зу­ют­ся 6-битовые ко­до­вые слова:

П - 111111, А - 110001, Р - 001001.

Для этого на­бо­ра ко­до­вых слов вы­пол­не­но такое свойство: любые два слова из на­бо­ра от­ли­ча­ют­ся не менее, чем в трёх позициях. Это свой­ство важно для рас­шиф­ров­ки со­об­ще­ний при на­ли­чии помех. Нужно по­до­брать ко­до­вое слово для буквы К так, чтобы ука­зан­ное свой­ство вы­пол­ня­лось для всех четырёх ко­до­вых слов.

Можно ли ис­поль­зо­вать одно из таких слов: 000001, 111001, 000111?

4) нет, не под­хо­дит ни одно из ука­зан­ных выше слов

Ответ:

По ка­на­лу связи пе­ре­да­ют­ся сообщения, со­дер­жа­щие толь­ко 4 буквы: С, Л, О, Н; для пе­ре­да­чи ис­поль­зу­ет­ся дво­ич­ный код, до­пус­ка­ю­щий од­но­знач­ное декодирование. Для букв С, О, Н ис­поль­зу­ют­ся такие ко­до­вые слова: С: 011, О: 00, Н: 11. Ука­жи­те такое ко­до­вое слово для буквы Л, при ко­то­ром код будет до­пус­кать од­но­знач­ное декодирование. Если таких кодов несколько, ука­жи­те тот, у ко­то­ро­го мень­шая длина.

Ответ:

По ка­на­лу связи пе­ре­да­ют­ся сообщения, со­дер­жа­щие толь­ко 4 буквы: А, Т, О, М; для пе­ре­да­чи ис­поль­зу­ет­ся дво­ич­ный код, до­пус­ка­ю­щий од­но­знач­ное декодирование. Для букв Т, О, М ис­поль­зу­ют­ся такие ко­до­вые слова: Т: 100, О: 00, М: 11. Ука­жи­те такое ко­до­вое слово для буквы А, при ко­то­ром код будет до­пус­кать од­но­знач­ное декодирование. Если таких кодов несколько, ука­жи­те тот, у ко­то­ро­го мень­шая длина.

Ответ:

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

Р: 000, А: 10, К: 01.

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

Ответ:

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

Т: 111, О: 10, П: 01.

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

Ответ:

Для ко­ди­ро­ва­ния не­ко­то­рой последовательности, со­сто­я­щей из букв У, Ч, Е, Н, И и К, ис­поль­зу­ет­ся не­рав­но­мер­ный дво­ич­ный пре­фикс­ный код. Вот этот код: У - 000, Ч - 001, Е - 010, Н - 100, И - 011, К - 11. Можно ли со­кра­тить для одной из букв длину ко­до­во­го слова так, чтобы код по-прежнему остал­ся префиксным? Коды осталь­ных букв ме­нять­ся не должны.

1) ко­до­вое слово для буквы Е можно со­кра­тить до 01

2) ко­до­вое слово для буквы К можно со­кра­тить до 1

3) ко­до­вое слово для буквы Н можно со­кра­тить до 10

4) это невозможно

Ответ:

Для ко­ди­ро­ва­ния не­ко­то­рой последовательности, со­сто­я­щей из букв У, Ч, Е, Н, И и К, ис­поль­зу­ет­ся не­рав­но­мер­ный дво­ич­ный пре­фикс­ный код. Вот этот код: У - 000, Ч - 001, Е - 010, Н - 100, И - 101, К - 11. Можно ли со­кра­тить для одной из букв длину ко­до­во­го слова так, чтобы код по-прежнему остал­ся префиксным? Коды осталь­ных букв ме­нять­ся не должны.

Выберите пра­виль­ный ва­ри­ант ответа.

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

1) кодовое слово для буквы Е можно со­кра­тить до 01

2) кодовое слово для буквы К можно со­кра­тить до 1

3) кодовое слово для буквы Н можно со­кра­тить до 10

4) это невозможно

Ответ:

Для пе­ре­да­чи по ка­на­лу связи сообщения, со­сто­я­ще­го толь­ко из сим­во­лов А, Б, В и Г, ис­поль­зу­ет­ся не­рав­но­мер­ный (по длине) код: А – 0; Б – 100; В – 101. Каким ко­до­вым сло­вом нужно ко­ди­ро­вать сим­вол Г, чтобы длина его была минимальной, а код при этом до­пус­кал од­но­знач­ное раз­би­е­ние ко­ди­ро­ван­но­го со­об­ще­ния на символы?

Ответ:

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

Даны ко­до­вые слова для четырёх букв: А - 011, Б - 010, В - 001, Г - 000. Какие ко­до­вые слова из приведённых ниже ва­ри­ан­тов под­хо­дят для букв Д и Е? Если под­хо­дит более од­но­го варианта, ука­жи­те тот, для ко­то­ро­го сумма длин ко­до­вых слов меньше.

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

1) Д - 100, Е - 110

2) Д - 100, Е - 11

3) Д - 10, Е - 11

4) Д - 10, Е - 1

Ответ:

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

Даны ко­до­вые слова для четырёх букв: А - 111, Б - 110, В - 101, Г - 100. Какие ко­до­вые слова из приведённых ниже ва­ри­ан­тов подходят для букв Д и Е? Если под­хо­дит более од­но­го варианта, ука­жи­те тот, в ко­то­ром сумма длин ко­до­вых слов меньше.

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

1) Д - 001, Е - 011

2) Д - 001, Е - 01

3) Д - 00, Е - 01

4) Д - 0, Е - 01

Ответ:

Для пе­ре­да­чи по ка­на­лу связи сообщения, со­сто­я­ще­го только из сим­во­лов А, Б, В и Г, ис­поль­зу­ет­ся неравномерный (по длине) код: А - 0; Б - 10; В - 110. Каким ко­до­вым словом нужно ко­ди­ро­вать символ Г, чтобы длина его была минимальной, а код при этом до­пус­кал однозначное раз­би­е­ние кодированного со­об­ще­ния на символы?

Ответ:

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

Примечание.

Ответ:

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

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

Ответ:

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

Задание № 5 в ЕГЭ 2017

(в ЕГЭ 2014г - задание А9,

в ЕГЭ 2015г - задание 1)

Спецификация контрольных измерительных материалов единого государственного экзамена 2016 года по информатике и ИКТ

Практика

1. Разберем примеры заданий из ЕГЭ прошлых лет

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

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

При решении этого задания можно попробовать подобрать такую цепочку из кодов букв, которая бы однозначно была декодирована или, наоборот, не однозначно была бы декодирована, и проанализировать варианты. Но можно быстрее решить это задание, воспользовавшись условием Фано (смотри в теории). Проверим, можно ли сократить код буквы Г до 10. В этом случае нарушается условие Фано, т.е. код буквы Г станет началом кода буквы В, однозначное декодирование невозможно. То же самое мы видим, если сократим код буквы Д до 10. Не подходит и этот вариант. А если код буквы Д сократить до 11, то этот код не является ни началом, ни концом какого-либо кода. Это и есть ответ.

Ответ: 1

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

A - 11010, Б - 00110, В - 10101.
При передаче возможны помехи. Однако некоторые ошибки можно попытаться исправить. Любые два из этих трёх кодовых слов отличаются друг от друга не менее чем в трёх позициях. Поэтому если при передаче слова произошла ошибка не более чем в одной позиции, то можно сделать обоснованное предположение о том, какая буква передавалась. (Говорят, что «код исправляет одну ошибку».) Например, если получено кодовое слово 10110, считается, что передавалась буква Б. (Отличие от кодового слова для Б - только в одной позиции, для остальных кодовых слов отличий больше.)
Если принятое кодовое слово отличается от кодовых слов для букв А, Б, В более чем в одной позиции, то считается, что произошла ошибка (она обозначается ‘x’).
Получено сообщение 00111 11110 11000 10111. Декодируйте это сообщение - выберите правильный вариант.
1) БААВ
2) БААx
3) xxxx
4) xААx

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

Я выделила красным цветом те цифры, которые отличаются в кодах слов, причем у тех букв, где не более одного отличия. Таким образом, полученное сообщение можно декодировать как БААВ.

Ответ: 1

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

А - 0; Б - 100; В - 1010; Г - 111; Д - 110. Требуется сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно. Коды остальных букв меняться не должны.
Каким из указанных способов это можно сделать?
1) для буквы В - 101
2) это невозможно
3) для буквы В - 010
4) для буквы Б - 10

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

2. Очень хорошо разобраны решения заданий ЕГЭ на сайте К.Полякова ( )

3. И, в заключение, рекомендую пройти онлайн-тест по заданию №1 (А1) на сайте К.Полякова (выбрать ) или на сайте ege.yandex.ru (

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

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

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

Правильный ответ : 101

Решение: Так как код А – это 0, то код для Г не может начинаться с 0 (нарушается условие Фано для букв А и Г). Поэтому код для Г должен начинаться с 1. Оба слова длины 2, которые начинаются с 1, использовать нельзя: 10 – начало кода буквы Б, а 11 – начало кода буквы В. Из начинающихся с 1 слов длины 3 для использования в качестве кода для Г доступны слова 101 и 111. В обоих случаях условие Фано выполняется. Из них наименьшее кодовое значение имеет слово 101 (см. рис.1).

Замечание. Условие Фано также будет выполнено, если в качестве кода для Г использовать любое слово, которое начинается с 101 или 111. Условие Фано НЕ будет выполнено, если в качестве кода для Г использовать любое слово, которое начинается со слов 100 и 110 – кодов для Б и В. Вместе со сказанным выше это означает, что в качестве кода для Г использовать любое слово, которое начинается с 101 или 111 и ТОЛЬКО такое слово.

Рис.5-1. Все двоичные слова длины не более 3; каждый узел дерева соответствует одному такому слову. Красным обозначены узлы, соответствующие началам кодовых слов; оранжевым – узлы, соответствующие продолжениям кодовых слов; зеленым – слова, которые могут быть кодовыми словами для Г при соблюдении условия Фано.

2. Еще одна задача

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

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

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

Правильный ответ : 18

Решение: В соответствии с замечанием после решения задачи 5-1, каждое из кодовых слов для букв Г, Д, Е является продолжением одного из слов 100 и 111 (коды для буквы Б в условиях задач 5-1 и 5-2 – разные). Таким образом, среди слов, которые можно использовать, есть только два слова длины 3 – сами слова 100 и 111. Но если использовать оба эти слова в качестве кодовых слов, скажем, для букв Г и Д, то для буквы Е кодовых слов не останется – любое из возможных для Е слов – продолжение слов, уже выбранных для Г и Д. Поэтому в коде (скажем, для буквы Г) можно использовать только одно из трехбуквенных слов 100 и 111. Для оставшихся двух букв придется использовать 4-буквенные слова. Пример такого кода, удовлетворяющего условию Фано: А: 0, Б: 101, В: 110, Г: 100, Д: 1110, Е: 1111. Суммарная длина кодовых слов: 1+3+3+3+4+4 = 18.

3. И еще одна задача

По каналу связи с помощью равномерного двоичного кода передаются сообщения, содержащие только 4 буквы С, О, Ф, Т. Для кодирования букв С, О, Ф используются 5-битовые кодовые слова: С – 01111, О – 00001, Ф – 11000.

Для этого набора кодовых слов выполнено такое свойство:

любые два слова из набора отличаются не менее, чем в трех позициях .

Это свойство важно для расшифровки сообщений при наличии помех.

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

Правильный ответ : 10110

Решение:

Искомое число не может начинаться с 11. Действительно, единственное такое число, которое отличается от кода буквы Ф не менее, чем в 3 разрядах. – это число 11111. Но это число не подходит, т.к. оно отличается от кода буквы С только в одной позиции. Поэтому наибольшее из возможных кодовых слов (если оно начинается с 1) должно начинаться с 10. Из сравнения с кодом буквы С получаем, что хотя бы одна из трех оставшихся цифр – это 0. Наибольшее из таких чисел – это число 10110. Проверкой убеждаемся, что оно подходит.

Еще задачи на кодирование на

Главная » Английский алфавит » Для кодирования некоторой