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

A9 Умение кодировать и декодировать информацию

http://kpolyakov.blogspot.ru/2012/10/blog-post.html

Кодирование – это перевод информ с одного языка на др (запись в др с-ме символов, в др алфав).

Код наз однозначно декодируемым, если любое кодов сообщ м расшифр единств спо (однозн).

Закодиров сообщ м однозн декодир с начала, если вып усл Фано: никакое код слово не явл нач др кодового слова. закодир сообщ м однозн декодир с конца, если вып обрат усл Фано: никакое код слово не явл оконч др кодового слова  Усл Фано – это дос, но не необх усл однозн декодир 

б исп двоичные коды, т е посл-ти 0 и 1.

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

Обр усл Фано: никакое код слово не совп с оконч др кодового слова. Коды, для кот вып обр условие Фано, наз постфиксными В этом сл тоже обеспеч однозн декодирование.

 Пусть исх алф вкл 9 симво: А,Л,М,О, П, Р,У,Ы, -.  Кодовый алф – двоичный. Кодовые слова:

А: 00 М: 01-: 100 Л: 101 У: 1100 Ы: 1101 Р: 1110 О: 11110 П: 11111

Кодовые слова вып в алф порядке. Видно, что ни одно из них не явл нач дру. ри

бинарное дерево. , каждому узлу соотв слово в двоичн алфа. Если слово X явл нач (префикс) сл Y, то узел, соотв X, нах на пути из корня в узел, соотв Y. Наши кодовые слова нахо в листьях дерева. Поэтому ни одно из них не явл нач другого.
Пр 1.для кодир фразы «МАМА МЫЛА ЛАМУ» выбран код:

МАМА МЫЛА ЛАМУ → 0010011100010111010010 неоднозн

раскодир такое сообщ м самыми разными спос. Напр, оно сост только из букв А (код 1) и Л (код 0). Тогда получаем ЛЛАЛЛАААЛЛЛАЛАААЛАЛЛАЛ

. Закодируем фразу из примера 1, используя равномерный код:

Получаем закодированное сообщение

МАМА МЫЛА ЛАМУ → 000001000001101000010011001101011001000100

Длина этого сообщ — 42 бита вместо 22 в пред вар, зато его легко разбить на отд код слова и раскодир («_» обозначает пробел):

000 001 000 001 101 000 010 011 001 101 011 001 000 100

М А М А _ М Ы Л А _ Л А М У

Равномерные коды

7) Для кодир букв А, Б, В, Г решили исп 2-разр послед двоичн числа (от 00 до 11 соотв). Если таким спос закодир Посл-ть симв ГБАВ и записать результат в16-ичн системе

счисления, то получится:

8) Для кодир букв А, Б, В, Г решили исп 2-разр послед двоичные числа (от 00 до 11 соотв). Если таким спос закодир Посл-ть симв ГБВА и записать рез-т 16ичн кодом, то получим

10) Для кодиров букв А, Б, В, Г исп 4-разр последов двоич числа от 1000 до 1011 соотв. Если таким спос закодировать посл-ть симв БГАВ и записать рез-т в 8-ичн коде, то получ:

1) 175423 2) 115612 3) 62577 4) 12376

11) Для кодир букв А, В, С, D исп 3-разр послед двоичн числа, нач с 1 (от 100 до 111 соотв). Если таким способ закодир Посл-ть символов CDAB и запис резт в 16ичн коде, то получится

12) Для кодир букв К, L, М, N исп 4разр послед двоичн числа от 1000 до 1011 соотв. Если таким способ закодир посл-ть символов KMLN и запи результат в 8ич коде, то получится

Полный ответ на вопр об однозн декодируем получил в нач1960-х матем Ал.А. Марков, предл реш с помощью графов [2]. Рассм код

Следуя методу Ал.А. Маркова, построим граф следующим образом:

1. Определяем все последовательности (строки), которые
      а) совп с нач какого-то код слова и одновр с концом какого-то код слова и
      б) сами не явл кодовыми словами.

2. В данном сл это две посл-ти:    0 (нач кода буквы А и конец кода буквы Б) и
      1 (начало кода буквы Г и конец кода буквы Д);
   посл-ти 01 и 11 не учиты, потому что они совпадают с кодами букв А и Г;

3. Доб к этому мн-ву {0,1} пустую строку, кот обозн греч бук Λ; эл получ мнва {Λ, 0, 1}б верш графа

1. Соед верш дугами (напр ребрами) по такому п-лу: две верш X и Y соед дугой, если послед запись кода вер X, кода нек буквы (или неск букв) и кода верш Y дает код ещё 1 буквы:

Надпись «W→Z» на дуге, ведущей из X в Y, озна, что если меж словами X и Y встав посл-ть букв W (она м сост из неск симв), то получ цепочка кодов совп с кодом буквы Z. Напр, послед запись пустой строки (Λ), кода А (01) и цепоч 0 дает цеп 010 (код Б); поэтому рисуем дугу из верш «Λ» в верш «0» и у этой дуги пишем «А→Б», и т.д. Поск код буквы Г м запис как 11 = 1Λ1, у вершины «1» появляется петля «Λ→Г».

Рез Ал.А. Маркова в след: Код явл однозн декодир тогда и только тогда, когда в постр так графе нет ориент циклов, вкл вершину Λ. Иначе г,

1. если есть сообщ, кот декодир неоднозн, то в графе есть цикл, прох через вершину Λ;

2. если в графе есть цикл, прох через верш Λ, то м постр сообщ, кот декодир неоднозначно; для этого н, проходя по циклу, послед выписыв коды всех встречающ вершин и дуг;

В нашем графе есть, по крайней мере, три таких цикла:

1. цикл «Λ0Λ», соотв сообщ ΛА0ГΛ = 01011; это сообщ м б расшифр как АВ и как БГ;

2. цикл «Λ1Λ», соотв сообщ ΛА1АΛ = 01101; это сообщ м б расшифр как АД и как ВА;

3. цикл «Λ01Λ», соотв сообщ ΛА01АΛ = 010101; это сооб м б расшифр как ААА и как БД.

Кр того, у верш «1» есть петля, кот даёт б длин циклы «из Λ в Λ». Действ, прох по стрелкам из верш Λ, мы прих в верш 1, там «вертимся» какое-то кол раз, и возвр обр в верш Λ, замыкая цикл. Поэтому неоднозн декодир любая посл-ть вида 01…101, где многот обозн любое кол 1. Напр, сообщ 0111101 м б декодир как АГД или ВГА.Т е, код (6) не обл св-вом однозн декодируем.

Пр1:Для кодир нек посл-ти, сост из букв А, Б, В, Г и Д, исп неравном двоичн код, позв однозн декодир двоич посл-ть, появл на приём стор канала связи.: А–1, Б–000, В–001, Г–011. Укаж, каким код словом м б закодир буква Д. Код д удовл свву однозн декодир.1)00  2)01 3)11 4) 010

Реш:1) 00 - наруш усл Фано, так как кодовая цепочка совп с нач Б = 000 и В = 001.   Невозм однозн раскодир цепочку 000000: это м б ДДД или ББ, поэтому 1 вариант не подходит

2) 01 - нарушает усл Фано, т к кодовая цепочка совп с началом Г = 011. Невоз однозн раскоди цепочку 011: это м б ДА или Г, поэтому 2й вариант тоже не подходит

3) 11 - наруш усл Фано, т к код цепочка совп с нач А = 1. Невозм одноз раскодир цепочку 111: это м б ДА или ААА; 3й вариант не подходит

4) 010 - условие Фано не нарушено. Ответ:  4) 010

Оптимизация неравномерного кода

Пр. А9 Н оптимизир код А — 00, Б — 01, В — 100, Г — 101, Д — 110 выбрав один из вар

1) для буквы Д — 11 2) это невозм 3) для буквы Г — 10 4) для буквы Д — 10

Реш посм на исх код, привед в усл он префиксн — для него вып усл Фано: ни один из 3-бит кодов не нач ни с 00 (код А), ни с 01 (код Б). Поэтому сообщ, закодир с пом такого кода, декодир однозн. Заметим, что «обрез» усл Фано не вып: код буквы А (00) совп с оконч кода буквы В (100), а код буквы Б (01) совпадает с оконч кода буквы Г (101).\
Теперь пров, что получ, если сокр код буквы Д до 11 (вар 1). Св-во однозн декодир м б потеряно только тогда, когда в рез такого сокращ наруш усл Фано, т е код буквы Д совп с нач какого-то др код слова. Видим, что этого не произош — нет др кодовых слов, кот на с 11, поэтому вар1 — это и есть верное реш.Ост убед, что вар 3 и 4 не подходят. Если мы сокр код буквы Г до 10 (вар3), усл Фано оказ наруш, так как теперь код буквы Г (10) совпал с нач кода буквы В (100). Одновр наруш и «обр» усл Фано: код буквы А (00) совп с оконч кода буквы В (100). Но, как мы знаем, при этом код м всё-таки быть одноз декодир. Конечно, м постр граф, как б сдел выше, и пров, есть ли в нём циклы, вкл вершину Λ. В данном сл граф выглядит так:

Здесь два цикла, проходящих через вершину Λ (не считая петли у вершины 0):

1. цикл, соотв сообщ ΛГ0Λ1АΛ = 100100; это сообщ м б расшифр как ГБА или как ВВ;

2. цикл, соотв сообщ ΛГ0Λ1ГΛ = 100110; это сообщ м б расшифр как ГБГ или как ВД.

Таким образом, вариант 3 не обесп однозн декодируем сообщений.
Постр и анализ графа -легче просто подобрать посл-ть, кот м б декодир 2 разн спо.
Наконец, н убед, что вар 4 не удовл усл. Если сокр код буквы Д до 10, усл Фано оказ наруш, т к теперь код буквы Д (10) совпал с нач кода буквы В (100). Как и раньше, наруш обр усл Фано: код буквы А (00) совп с оконч кода буквы В (100) и код буквы Б (01) совп с оконч кода буквы Г (101).
Построим граф по методу Ал.А. Маркова:

Здесь два цикла, проходящих через вершину Λ (не считая петли у вершины 0):

1. цикл, соотв сообщ ΛД0Λ1АΛ = 100100; это сообщ м б расшифр как ДБА или как ВВ;

2. цикл, соотв сообщению ΛД0Λ1БΛ = 100101; это сообщ м б расшифр как ДББ или как ВГ.

Таким образом, вариант 4 также не соответствует условию. Поэтому правильный ответ — 1.
Пр 8. Оптимизир код А — 11, Б — 10, В — 011, Г — 000, Д — 001, сохр свво однозн декодир сообщ. Выб один из вар: 1) для буквы Г 00 2) это невоз 3) для буквы В 01 4) для буквы Б 1

Реш. Опр, за счёт чего обесп однозн декодируем исх кода. Легко видеть, что код префикс — для него вып усл Фано: ни одно из 3бит код слов не нач ни с 11 (код А), ни с 10 (код Б). В то же вр, обр усл Фано не вып, потому что код буквы А (11) совп с оконч кода буквы В (011).
Пров вар1 — сокр код буквы Г до 00. При этом наруш услФано, кот обесп однозн декодир исх вари: теперь код буквы Г (00) совп с нач кода буквы Д (001). Но и обр усл Фано тоже не вып для пары букв А-В. Поэтому м предп, что такой код не обл сввом однозн декодир. И действ, легко нах цепочка 001011, кот м раскодир как ГБА (00 10 11) или ДВ (001 011).
Рассм вар 3 — сокр код буквы В до 01. При этом усл Фано вып, поск ни одно из код слов не нач с 01, то есть код явл префиксным и однозн раскодир. Это и есть прав ответ.
На всякий сл пров вар4 — сокр код буквы Б до 1. При этом код перест б префикс, и обр условие Фано также не вып (код буквы Б совп с нач и концом кода буквы А). понятно, что посл-ть 11 можно раскодир как А или как ББ, поэтому этот вариант неверный.

Пр2: Для кодир нек посл-ти, сост из букв А, Б, В, Г и Д, исп неравном двоичн код, позв однозн декодир получ двоичн посл-ть. А–00, Б–010, В–011, Г–101, Д–111. М ли сокр для одной из букв длину код слова так, чтобы код по-прежн м б декодир однозн? Коды ост букв меняться не должны. Выб правильный вариант ответа.

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

Решение (1 способ, проверка условий Фано):

для однозн декодир дост, чтобы вып усл Фано или обр условие Фано;

пров последоват вар 1, 3 и 4; пров вар 1: А–00, Б–01, В–011, Г–101, Д–111.

прямое усл Фано не вып (код буквы Б совп с нач кода буквы В);обр усл Фано не вып (код буквы Б совпадает с оконч кода буквы Г); поэтому этот вариант не подходит;

пров вар3: А–00, Б–010, В–01, Г–101, Д–111.прям услФано не вып (код В совп с нач кода буквы Б);обр усл Фано не вып (код буквы В совп с оконч кода Г); поэтому этот вар не подходит;

пров вар 4: А–00, Б–010, В–011, Г–01, Д–111.прямое усл Фано не вып (код буквы Г совп с нач кодов букв Б и В); нообр усл Фано вып (код буквы Г не совп с оконч кодов ост буквы); поэтому этот вар подходит;прав ответ – 4.

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

1. пост двоичное дерево, в кот от кажд узла отходит 2 ветки, соотв выб след цифры кода – 0 или 1; размест на этом дереве буквы А, Б, В, Г и Д так, чтобы их код получ как посл-ть чисел на рёбрах, сост путь от корня до дан буквы (красн цветом выд код букв В – 011):

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

2. пров вар отв: предл перен одну из букв, Б, В или Г, в узел с код 01, выдел синим видим, что при переносе любой из этих букв наруш усл Фано; напр, при переносе Б в син узел она оказ на пути от корня до В, и т.д.; это зн, что предл вар не позв вып прямое усл Фано

3. хочется уже выб вар 2 («это невоз»), но у есть еще обр усл Фано, для кот тоже м постр анал дерево, в кот движ от корня к букве дает её код с конца (красным цвет вы код буквы В – 011, записанный с конца):

видно, что обр усл Фано также вып, потому что на пути от корня к любой букве нет др букв

1. в зад вар отв предл перемес букву Б, В или Г в синий узел; понят, что Б или В туда перем нельзя – перемещ буква отказ на пути от корня к букве Г; а вот букву Г перемест м, при этом обр усл Фано сохр правильный ответ – 4.

Решение:

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

2)если Д = 00, такая кодо цепочка совп нач Б = 000 и В = 001, невозм однозн раскодир цепочку 000000: это м б ДДД или ББ; поэтому 1й вариант не подходит

3)если Д = 01, такая кодовая цепочка совп с началом Г = 011, невозм однозн раскодир цепочку 011: это может быть ДА или Г; поэтому второй вариант тоже не подходит

4)если Д = 11, усл Фано тоже наруш: код слово А = 1 совп с нач кода буквы Д, невозм однозн раскодир цепочку 111: это м б ДА или ААА; 3 ва не подходит

5)для 4 вар, Д = 010, усл Фано не нарушено;правильный ответ – 4.

1)  Для передачи по каналу связи сообщ, сост только из букв А, Б, В, Г, решили исп неравном по длине код: A=00, Б=11, В=100. Как н закодир букву Г, чтобы длина кода б миним и доп однозн разбиение кодир сообщения на буквы? 1) 010 2) 10 3) 01 4) 011

2)      А, Б, В, Г, неравном по длине код: A=1, Б=000, В=001. Как н закодир букву Г, чтобы длина кода была миним и доп однозн разб кодир сообщ на буквы? 1) 00 2) 01 3) 11 4) 010

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

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

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

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

5 А, Б, В, Г и Д неравном двоич код, А–10, Б–001, В–0001, Г–110, Д–111. М ли сокр для одной из букв длину код слова чтобы код по-прежн м б декодир однозн? Коды ост букв менять не должны

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

Декодирование неравномерного кода (Расшифровка сообщ)

Для 5 букв лат алф зад их двоич коды (для нек букв – из 2 бит, для нек – из 3). Эти коды п в табл:

Опр, какой набор букв закодир двоичной строк 0110100011000

1) EBCEA 2) BDDEA 3) BDCEA 4) EBAEA

1) пусть первая буква – E с кодом 011, тогда ост цепочка 0100011000

для кода 0100011000 1й букв м б B с код 01, тогда ост 00011000 ( нач исх цепоч – EB?)

для кода 00011000 1й букв м б только A с кодом 000, тогда ост 11000, а эта цеп не м б разл на зад коды букв поэтому предп о том, что 1я буква – E, неверно

2)пусть 1я буква – B с кодом 01, тогда ост цепочка 10100011000 для кода 10100011000 1й букв м б только D с кодом 10, тогда ост 100011000 (м полаг, что начало исх цепочки – BD?)

для кода 100011000 1й букв м б только С с кодом 100, тогда ост 011000 (нач исх цепоч – BDC?)

для кода 011000 на 1 месте м б B (код 01) или E (011); в 1 сл «хвост» 1000 нельзя разб на зад коды букв, а во 2м – ост код 000 (буква А), поэтому исх цеп м б декодир как BDCEA прав ответ – 3

2 вар –декодир с конца

6) Для 5 букв латин алф заданы их двоичн коды (для нек букв – из 2 бит, для нек – из 3х).

, какой набор букв закодир двоичн строкой 0110100011000 1)EBCEA 2) BDDEA 3) BDCEA 4) EBAEA прав отв – 3

Указ. Несм на то, что среди отв есть единств цепочка, кот нач с BDC, здесь нельзя остан, потому что «хвост» цепочки м не сойтись вар 1, декодир с начала): вар 2, декодир с конца

7)Какой набор букв за­ко­ди­р дво­ич­ стро 1000110110110? Все буквы в по­сле-ти — раз­ные.

подск. усл Фано и об­р усл Фано не вы­п зн код м рас­ко­ди­р не­од­н. Б про­б раз­н ва­р, от­бр те, в ко­т по­лу­ч по­вт буквы:

1) 100 011 01 10 110 1я бук опр од­но­зн, её код 100: a. Пусть 2я бук — с, тогда сле­д бук  d, потом — e и b. Такой ва­р удо­вл усло­вию, зн, окон­ч по­лу­ч ответ: acdeb.

9) Для 5 букв латин алфавита заданы их двоичные коды (для некот букв - из 2 бит, для

некот - из 3х). Эти коды представл в табл:

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

1. baade 2) badde 3) bacde 4) bacdb

13) Для 5 букв лат алф заданы их двоичн коды (для некот букв – из 2 бит, для нек – из 3х). Эти коды в табл: Опр, какой набор букв закодир двоичн строкой 1000110110110, если изв, что все буквы в посл-ти – разные:

1) cbade 2) acdeb 3) acbed 4) bacde

1)Для кодирования сообщения исп табл

1)

Сообщение: 0101110010110 (Отв: ГБАДДА, ДДБВДА)

2)

Сообщ: 01011100101101 (Ответы: ААВААД, ААВГБА)

3)

Сообщение: 0010001001001 Ответы: БВГББ, ВДГББ)

4)

Сообщение: 0100001101000010(Ответы: БАДГАБ, ГАВГАБ)

5)

Сообщ: 1010000011011000 (Ответы: ААГВВГ, АБГДВГ)

изобр двоичное дерево, соотв этому коду.

Вып ли для этой код таблицы условие Фано? Обр условие Фано? Почему?

Найдите все способы декодир сообщ, записанное под таблицей:

Замените код 1 симв так, чтобы вып усл Фано. Выд зел фоном яч табл с изме кодом символа.

Сокр код одного символа в таблице, получ в п. 4 так, чтобы усл Фано по-пр вып. Выделите фиолетовым фоном ячейку таблицы с измененным кодом символа.

Кодовое расстояние

1а)По каналу связи перед сообщ, содер только 4 буквы: Е, Н, О, Т. Для кодир букв Е, Н, О исп 5-бит код слова: Е - 00000, Н - 00111, О - 11011. Для этого наб код слов вып такое св-во: любые 2 слова из набора отлич не менее чем в 3 поз. Это свво важно для расшифр сообщ при налич помех. Какое из перечисл ниже код слов м исп для буквы Т, чтобы указ свво вып для всех 4 код слов?

1) 11111 2) 11100 3) 00011 4) не подходит ни одно из указ выше слов

Реш: 1)код, рассм в усл зад, отн к помехоуст кодам, кот позв обнар и испр опред кол ош, вызв помехами при перед данных;ко поз, в кот отлич 2 кодо слова одинак длины, наз расст Хэмминга

3)код, в кот расст Хэмминга меж каждой парой код слов = d, позв обнар до d-1 ош; для испр r ошибок треб вып усл d ≥ 2r + 1 поэтому код с d = 3 позв обнар 1 или 2 ош, и испр 1 ошибку.

4)легко пров, что для зад кода (Е - 00000, Н - 00111, О - 11011) расст Хэмминга= 3; в табл выделены отлич биты, их по три в парах Е-Н и Н-О и четыре в паре Е-О:

Е – 00000 Е – 00000 Н – 00111

Н – 00111 О – 11011 О – 11011

теперь пров расст между изв кодами и вар ответа; для 1 отв 11111 получаем мин расст 1 (в паре О-Т), этот вар не подхт:

Е – 00000 Н – 00111 О – 11011

Т - 11111 Т - 11111 Т - 11111

для 2 ответа 11100 получаем ми расст 3 (в парах Е-Т и О-Т):

Е – 00000 Н – 00111 О – 11011

Т - 11100 Т - 11100 Т - 11100

для 3 ответа 00011 получ мин расст 1 (в паре Н-Т) , этот вар не подходит:

Е – 00000 Н – 00111 О – 11011

Т - 00011 Т - 00011 Т - 00011

таким обр, расст Хэмминга, равное 3, сохр только для ответа 2 Ответ: 2.

1б) По каналу связи перед сообщ, содерж только 4 буквы: А, Б, В, Г. Для кодир букв А, Б, В исп 5-бит код слова: А - 01101, Б - 00110, В - 10001. Для этого набора код слов вып свойство: любые два слова из набора отли не менее чем в 3 поз.. Какое из перечис ниже код слов м исп для буквы Г, чтобы указ свойство вып для всех четырёх кодовых слов?

1) 11111 2) 11010 3) 01000 4) не подходит ни одно из указ выше слов

1в)  сооб 4 буквы — П, О, Р, Т. Для кодир букв исп 5-бит кодовые слова:

П — 11111, О — 11000, Р — 00100, Т — 00011. Отл не менее чем в 3 позициях.

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

11011 11100 00011 11000 01110