Решение задач на тему "Кодирование и декодирование информации"

Ко­ди­ро­ва­ние и де­ко­ди­ро­ва­ние информации

Задание №5

При выполнении данного задания необходимо знать условие Фано, Код Хаффмана

 В чем смысл прямого условия Фано?

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

Сформулировать данное условие можно следующим образом: «ни одно кодовое слово не может выступать в качестве начала любого другого кодового слова».

С математической точки зрения условие можно сформулировать следующим образом: «если код содержит слово B, то для любой непустой строки C слова BC не существует в коде».

В чем смысл обратного условия Фано?

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

С математической точки зрения обратное условие можно сформулировать следующим образом: «если код содержит слово B, то для любой непустой строки C слова CB не существует в коде».

Условие задачи: дана последовательность, которая состоит из букв «A», «B», «C», «D» и «E». Для кодирования приведенной последовательности применяется неравномерный двоичный код, при помощи которого можно осуществить однозначное декодирование.

Буква	A	B	C	D	E
Двоичный эквивалент	00	010	011	101	111

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

Номер варианта	1	2	3	4
Ответ	B – 01	Не представляется возможным	C – 01	D – 01

Решение: для того, чтобы сохранилась возможность декодирования, достаточным является соблюдение прямого или обратного условия Фано. Проведем последовательную проверку вариантов 1, 3 и 4. В случае если ни один из вариантов не подойдет, правильным ответом будет вариант 2 (не представляется возможным).

Вариант 1. Код: A - 00, B - 01, C - 011, D - 101, и E - 111. Прямое условие Фано не выполняется: код символа «B» совпадает с началом кода символа «C». Обратное правило Фано не выполняется: код символа «B» совпадает с окончанием кода символа «D». Вариант не является подходящим.

Вариант 3. Код: A - 00, B - 010, C - 01, D - 101, и E - 111. Прямое условие Фано не выполняется: код символа «C» совпадает с началом кода символа «B». Обратное условие также не выполняется: код символа «C» совпадает с окончанием кода символа «D». Вариант не является подходящим.

Вариант 4. Код: A - 00, B - 010, C - 011, D - 01, и E - 111. Прямое условие Фано не выполняется: код символа «D» совпадает с началом кода символов «B» и «C». Однако наблюдается выполнение обратного правила Фано: код символа «D» не совпадает с окончанием кода всех остальных символов. По этой причине, вариант является подходящим.

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

Ответ: 4

Код Хаффмана

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

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

1) 22162

2) 1020342

3) 2131453

4) 34017

По­яс­не­ние.

Сна­ча­ла сле­ду­ет пред­ста­вить дан­ные в усло­вии числа в дво­ич­ном коде:

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

Затем за­ко­ди­ро­вать по­сле­до­ва­тель­ность букв: ВО­ДО­ПАД — 010010001110010. Те­перь разобьём это пред­став­ле­ние на трой­ки спра­ва на­ле­во и пе­ре­ведём по­лу­чен­ный набор чисел в де­ся­тич­ный код, затем в вось­ме­рич­ный (вось­ме­рич­ное предств­ле­ние сов­па­да­ет с де­ся­тич­ным при раз­би­е­нии трой­ка­ми)

010 010 001 110 010 — 22162.

Пра­виль­ный ответ ука­зан под но­ме­ром 1.

 № 2. Для пе­ре­да­чи по ка­на­лу связи со­об­ще­ния, со­сто­я­ще­го толь­ко из сим­во­лов А, Б, В и Г, ис­поль­зу­ет­ся по­сим­воль­ное ко­ди­ро­ва­ние: А-00, Б-11, В-010, Г-011. Через канал связи пе­ре­да­ётся со­об­ще­ние: ВБ­ГА­ГВ. За­ко­ди­руй­те со­об­ще­ние дан­ным ко­дом. По­лу­чен­ное дво­ич­ное число пе­ре­ве­ди­те в шест­на­дца­те­рич­ный вид.

1) CBDADC

2) 511110

3) 5В1А

4) А1В5

По­яс­не­ние.

За­ко­ди­ру­ем по­сле­до­ва­тель­ность букв: ВБ­ГА­ГВ — 0101101100011010. Те­перь разобьём это пред­став­ле­ние на четвёрки спра­ва на­ле­во и пе­ре­ведём по­лу­чен­ный набор чисел сна­ча­ла в де­ся­тич­ный код, затем в шест­на­дца­те­рич­ный:

0101 1011 0001 1010 — 5 11 1 10 — 5В1А.

Пра­виль­ный ответ ука­зан под но­ме­ром 3

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

А	Б	В	Г
00	11	010	011

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

1) CDADBC

2) A7C4

3) 412710

4) 4С7А

По­яс­не­ние.

За­ко­ди­ру­ем по­сле­до­ва­тель­ность букв: ВГАГ­БВ — 0100110001111010. Те­перь разобьём это пред­став­ле­ние на четвёрки спра­ва на­ле­во и пе­ре­ведём по­лу­чен­ный набор чисел сна­ча­ла в де­ся­тич­ный код, затем в шест­на­дца­те­рич­ный:

0100 1100 0111 1010 — 4 12 7 10 — 4С7А.

Пра­виль­ный ответ ука­зан под но­ме­ром 4.

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

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

1) 57414

2) 53414

3) 53412

4) 53012

По­яс­не­ние.

Код пер­вой стро­ки: 10101.

Код вто­рой стро­ки: 11000.

Код тре­тьей стро­ки: 01010.

За­пи­шем коды по по­ряд­ку в одну стро­ку: 101011100001010. Те­перь разобьём это пред­став­ле­ние на трой­ки спра­ва на­ле­во и пе­ре­ведём по­лу­чен­ный набор чисел в де­ся­тич­ный код (вось­ме­рич­ное представ­ле­ние сов­па­да­ет с де­ся­тич­ным при раз­би­е­нии трой­ка­ми).

101 011 100 001 010 — 53412.

Пра­виль­ный ответ ука­зан под но­ме­ром 3.

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

a	b	c	d	e
000	110	01	001	10

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

1) baade

2) badde

3) bacde

4) bacdb

По­яс­не­ние.

Мы видим, что вы­пол­ня­ет­ся усло­вие Фано: ни­ка­кое ко­до­вое слово не яв­ля­ет­ся на­ча­лом дру­го­го ко­до­во­го слова, по­это­му од­но­знач­но можем рас­ко­ди­ро­вать со­об­ще­ние с на­ча­ла.

Разобьём код слева на­пра­во по дан­ным таб­ли­цы и пе­ре­ведём его в буквы:

110 000 01 001 10 — b a c d e.

Пра­виль­ный ответ ука­зан под но­ме­ром 3.

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

1) 6543

2) 62926

3) 62612

4) 3456

По­яс­не­ние.

Из при­ме­ра видно, что 2 знака ко­ди­ру­ют­ся 10 дво­ич­ны­ми раз­ря­да­ми (би­та­ми), на каж­дую цифру от­во­дит­ся 5 бит. В усло­вии ска­за­но, что каж­дая цифра за­пи­сы­ва­ет­ся кодом дли­ной 4 знака, зна­чит, пятую цифру можно от­ки­нуть.

Разобьём дво­ич­ную за­пись на груп­пы по 5 зна­ков: 01100 01010 01001 00110. От­бра­сы­ва­ем по­сле­юд­нюю цифру в каж­дой пятёрке и пе­ре­во­дим в де­ся­тич­ную за­пись:

0110 0101 0100 0011 — 6 5 4 3.

Пра­виль­ный ответ ука­зан под но­ме­ром 1.

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

П — 11111, О — 11000, Р — 00100, Т — 00011.

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

Это свой­ство важно для рас­шиф­ров­ки со­об­ще­ний при на­ли­чии помех (в пред­по­ло­же­нии, что пе­ре­да­ва­е­мые биты могут ис­ка­жать­ся, но не про­па­да­ют). За­ко­ди­ро­ван­ное со­об­ще­ние счи­та­ет­ся при­ня­тым кор­рект­но, если его длина крат­на 5 и каж­дая пятёрка от­ли­ча­ет­ся от не­ко­то­ро­го ко­до­во­го слова не более чем в одной по­зи­ции; при этом счи­та­ет­ся, что пятёрка ко­ди­ру­ет со­от­вет­ству­ю­щую букву. На­при­мер, если при­ня­та пя­тер­ка 00000, то счи­та­ет­ся, что пе­ре­да­ва­лась буква Р.

Среди при­ведённых ниже со­об­ще­ний най­ди­те то, ко­то­рое при­ня­то кор­рект­но, и ука­жи­те его рас­шиф­ров­ку (про­бе­лы не­су­ще­ствен­ны).

11011 11100 00011 11000 01110

00111 11100 11110 11000 00000

1) ПОТОП

2) РОТОР

3) ТОПОР

4) ни одно из со­об­ще­ний не при­ня­то кор­рект­но

По­яс­не­ние.

Длина обоих со­об­ще­ний крат­на пяти.

Ана­ли­зи­руя пер­вое со­об­ще­ние "11011 11100 00011 11000 01110", при­хо­дим к вы­во­ду, что оно при­ня­то не­кор­рект­но, по­сколь­ку нет та­ко­го слова, ко­то­рое бы от­ли­ча­лось от слова "01110" толь­ко в одной по­зи­ции.

Рас­смот­рим вто­рое со­об­ще­ние. Учи­ты­вая, что каж­дая пятёрка от­ли­ча­ет­ся от не­ко­то­ро­го ко­до­во­го слова не более чем в одной по­зи­ции, его воз­мож­но рас­шиф­ро­вать толь­ко как "ТОПОР".

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

А — 10010, Б — 11111, В — 00101.  

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

По­лу­че­но со­об­ще­ние 10000 10101 11001 10111. Де­ко­ди­руй­те это со­об­ще­ние — вы­бе­ри­те пра­виль­ный ва­ри­ант.

1) АВББ

2) хххх

3) АВхБ

4) АххБ

По­яс­не­ние.

Де­ко­ди­ру­ем каж­дое слово со­об­ще­ния. Пер­вое слово: 10000 от­ли­ча­ет­ся от буквы А толь­ко одной по­зи­ци­ей. Вто­рое слово: 10101 от­ли­ча­ет­ся от буквы В толь­ко одной по­зи­ци­ей. Тре­тье слово: 11001 от­ли­ча­ет­ся от любой буквы более чем в одной по­зи­ции. Четвёртое слово: 10111 от­ли­ча­ет­ся от буквы Б толь­ко одной по­зи­ци­ей.

Ответ: АВхБ.

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

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

1) 1

2) 0

3) 01

4) 10

По­яс­не­ние.

Для того, чтобы со­об­ще­ние, за­пи­сан­ное с по­мо­щью не­рав­но­мер­но­го по длине кода, од­но­знач­но рас­ко­ди­ро­ва­лось, тре­бу­ет­ся, чтобы ни­ка­кой код не был на­ча­лом дру­го­го (более длин­но­го) кода. Рас­смот­рим ва­ри­ан­ты для буквы Д, на­чи­ная с са­мо­го ко­рот­ко­го.

1) Д=1: код буквы Д яв­ля­ет­ся на­ча­лом всех пред­став­лен­ных кодов букв, по­это­му этот ва­ри­ант не под­хо­дит.

2) Д=0: код буквы Д не яв­ля­ет­ся на­ча­лом дру­го­го кода, по­это­му этот ва­ри­ант под­хо­дит.

3) Д=01: код буквы Д не яв­ля­ет­ся на­ча­лом дру­го­го кода, по­это­му этот ва­ри­ант под­хо­дит.

4) Д=10: код буквы Д яв­ля­ет­ся на­ча­лом кодов букв В и Г, сле­до­ва­тель­но, этот ва­ри­ант не под­хо­дит.

Таким об­ра­зом, под­хо­дят два ва­ри­ан­та: 0 и 01. 0 ко­ро­че, чем 01.

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

Е, Н, О, Т.

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

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

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

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

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

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

По­яс­не­ние.

Вы­бе­рем коды, для ко­то­рых вы­пол­не­но усло­вие Фано. Это коды 3 и 4.

Чтобы со­об­ще­ние было как можно ко­ро­че, не­об­хо­ди­мо, чтобы чем чаще встре­ча­лась буква, тем ко­ро­че был ее код.

Сле­до­ва­тель­но, ответ 4, по­сколь­ку буква О — самая часто встре­ча­ю­ща­я­ся буква и для ее ко­ди­ро­ва­ния в ва­ри­ан­те 4 ис­поль­зу­ет­ся один сим­вол.

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

1) 7

2) 8

3) 9

4) 10

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

По­яс­не­ние.

Найдём для остав­ших­ся двух сим­во­лов наи­бо­лее ко­рот­кое пред­став­ле­ние, удо­вле­тво­ря­ю­щее усло­вию Фано. Ко­до­вое слово 1 ис­поль­зо­вать нель­зя, так как тогда на­ру­шит­ся усло­вие Фано. Из дву­знач­ных ко­до­вых слов можно ис­поль­зо­вать слово 10, а слова 11 и 01 ис­поль­зо­вать нель­зя. При таком по­стро­е­нии кодов для четвёртого сим­во­ла не­воз­мож­но по­до­брать двух­знач­ное ко­до­вое слово. По­это­му ис­поль­зу­ем трёхзнач­ное слово, а имен­но — 111.

Таким об­ра­зом, наи­мень­шая воз­мож­ная сум­мар­ная длина всех четырёх ко­до­вых слов будет 1 + 3 + 2 + 3 = 9.

Пра­виль­ный ответ ука­зан под но­ме­ром 3.

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

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

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

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

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

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

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

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

По­яс­не­ние.

2 и 3 не под­хо­дят, так как в них встре­ча­ют­ся пары кодов, один из ко­то­рых яв­ля­ет­ся на­ча­лом дру­го­го.

Длина со­об­ще­ний при ис­поль­зо­ва­нии пер­во­го кода будет равна .

Длина со­об­ще­ний при ис­поль­зо­ва­нии четвёртого кода будет равна .

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