С.В. Яблонский - Введение в дискретную математику (1060464), страница 38
Текст из файла (страница 38)
е. источник сообщений порождает множество всех слов в алфавите И. Очевидно, что алфавитное кодирование порождает отображевяе множества 8(И) в множество Я(6). Обозначим через Ва(6) обрав множества 8(И) в атом отображении. В случае, когда отображение Я(И) на Я~(6) взаимно одноэначно, возможно декодирование, т. е. воаможво по коду В одноаначно восстановить исходное сообщение Л, кодом которого является В.
В этом случае говорят также, что алфавитное кодирование является взаимно одноаначным. П р и м е р 2. Рассмотрим алфавитиое кодирование, для которого И = (а„ а,), 6 (Ь„ Ь,) и схема имеет вид а,— Ь» а, — Ь,Ь,. Пусть В' и В являются соответственно кодами слов А' и А".
Очевидно, что если А' ч" А", то В' чь В". Процесс декодирования происходит следующим образом. Произведем разбиение слова В, В ю Яа(6), на элементарные коды. Для этого ваметим, что перед каждым вхождением буквы Ь, в слове В непосредственно находится буква Ь,.
Это позволяет выделить все пары (Ь,Ь3). Оставшаяся часть слова В будет состоять из бука Ь,. Если те_#_ерь эаменить каждую пару (Ь,Ь,) на а„а каждую ив оставшихся букв Ь~ — на аь то получим слово А, являющееся прообраэом В. ч, 1ч. теОРпя кОдиРОВАния гч Пусть В Ь,Ь,Ь,Ь,Ь,Ь,Ь,Ь,Ь.. После выделения пар мы получим разбиение на элементарные коды В= Ь,(Ь,Ь,) (Ь,Ь,)Ь,Ь,(Ь,Ь,), из которого находим слово А = а,а,а,а,а,а,. Можно привести большое количество примеров, в которых алфавитное кодирование не будет обладать свойством взаимной однозначности.
В связи с этим возникает вопрос: воаможно ли по схеме Е алфавитного кодирования узнать, обладает алфавитное кодирование свойством взаимной однозначности или нет. Трудность решения аадачи состоит в том, что для непосредственной проверки вааимной однозначности необходимо просмотреть бесконечное число слов. Прежде чем приводить общий критерий взаимной однозначности алфавитного кодирования, рассмотрим весьма простой достаточный признак взаимной однозначности. Определение. Пусть слово В Имеет вид В = В'В". Гогда слово В' называется качалов или префиксоль слова В, а В" — концом слова В. Прн атом пустое слово Л и само слово В считаются началами и концами слова В.
Все начала н концы слова В, отличные от него самого, называются собственными. Определение. Схема Г обладает свойством префикса, если для любых ~ н ) (1 ~ <, ь" ~ г, ьч")) слово В< не'является префиксом слова В<. Теорема 1. Если схема л обладает свойством префикса, то алфавитное кодирование будет взаимно однозначным.
Д о к а з а т е л ь с т в о. Поскольку схема Е обладает свойством префикса, все элементарные коды в ней попарно рааличны, т. е. В,чьВ< при (чьь'. Предположим, что некоторое слово В из Я,(6) допускает две расшифровки, а значит и два разбиения на элементарные коды В=В,,...В„ В,, 262 ч. <ч. Ткогпл кодптовлппя Пусть В< — — В< ° ° ю В» В В ФВ' ком случае одно из слов В;„, В;„является префиксом другого. Теорема доказана.
Предыдущий пример показывает, что условие префикс- ности не является необходпмым: Х может не обладать свойством префикса, а алфавитное кодирование, определяемое лч будет взаимно однозначным. Пусть В=Ь<,... Ь,„слово из Я(6). Обозначим через  — слово, получающееся из В путем «обращения», т.
е. В=Ь, " Ьк я Обозна шм, далее, через Х схему вида а,-В„ а, — В,. Пример 3. Возьмем в качестве л'. схему из примера 2. Тогда Е имеет вид а,— Ь„ а, — Ь,Ь<. Здесь Й обладает свойством префикса, и в силу теоремы г алфавитное кодирование, задаваемое Й, будет взаимно однозначным. Замечание. Алфавитное кодирование, определяемое схемой Х, и алфавитное кодирование, определяемое схемой лч одновременно либо обладают свойством взаимной однозначности, либо нет. Данное замечание позволяет усилить теорему 1. Теорема 2. Если либо схема Е, либо схема Х обладает свойством префикса, то алфавитное кодирование, задаваемое Е(Е), будет взаимно однозначнь»м. Можно привести пример алфавитного кодирования со схемой Х так, что и л и Й не обладают свойством префикса, а алфавитное кодирование будет взаимно однозначным.
Для этого предыдущий пример уже не годится, но может быть легко усовершенствован. ч. гч, теогня кодпгоэлнпя 263 Пример 4. Пусть 6=(а„а„а<) и ч<=(Ь„Ь„Ь,). Рассмотрим схему Х: а,— Ь„ ໠— Ь,Ь„ а, — Ь<Ь,. (Х) — нетривиальное разлоя<ение элементарного кода Вь т.е. разложение, отличное от рааложепия В< = В< ()) ' = р" = Л)', причем р' и ()" отличны от элементарных кодов. Параметр в< может быть целым числом, большим или равным нулю. Соотношение (1) означает, что в элементарном коде В, мок<но отбросить некое начало р' и некий конец ()" так, что оставшаяся часть разбивается на элементарные коды (см. рис. 3). Очевидно, что для каждого В, число разложений вида (1) конечно. Обозначим через И' максимум чисел ш, взятый по всем разложениям В, и по всем <, т.
е. И' шах и<. Очевидно, Х и Х не обладают свойством префикса, в то же время алфавитное кодирование будет взаимно однозначным. В самом деле, если В<и Я,(с<), то зто слово однозначным образом разбивается на элементарные коды: слева от буквы Ь, непосредственно находится Ь,— выделяем пару (Ь,Ь,); справа от буквы Ь, непосредственно находится Ь,— выделяем пару (Ь,Ь,); после выделения всех пар (Ь,Ь,) и (Ь,Ь,) в слове останутся лишь символы Ь,. В дальнейшем предположим, что в Х элементарные коды попарно различны. Прежде чем идти дальше, введем ряд обозначений: 1(В) будет обозначать длину слова В, т.
е. количество букв в этом слове. В частности для длин элементарных кодов В, (<=1, ..., г) полагаем 1(В,)= 1ь Далее, через Ь обозначим величину ЦВ,...В,), т. е. «длину» схемы Х. Пусть ч. гч. твоккя нодшовлния Пример 5. Рассмотрим алфавитное кодирование с й( (а„а„а„а„а,), 6 (Ь„Ьг, Ь,) и схемой а,-Ь,Ь„ а, — Ь,Ь,Ь„ а| — Ь,Ь„ а, — Ъ|Ь,Ь,Ь,> а, — Ь,Ь,Ь,Ь,Ь, Так как 6>(|2|2, то ЬУ~З.
С другой стороны, В| ЬгЬ!ЬзЬ|Ьз Ь~В|В|, новтому Я' 2. Обовкачим, наконец, через Я" (6) множество всех не- пустых слов в алфавите Ж, имеююг щих длину, не превосходящую № Ясно, что о"(И) — конечное множество, его мощность равна Ф дг. дгг |;, А ~~,л $-1 Рис.
2 Сформулируем теперь критерий взаимной одноаначности алфавитного кодирования. Те о р е и а 3 (Марков Ал. А. [22, 23]). Для всякого ая4аеитного кодирования со схемой Е существует та- кое У„ у ) ()т'+)) (Ъ вЂ” |+2) 1 в<~ 2 что кроблема взвил|ной одноэначиости алу|авитного кодирования сводится к аналогичной лроблеме для лодироно валия конечного множества б (6). Докавательство.
Если в алфавитном коднровакки нарушена вгаимная однозначность, то найдется такое слово В, которое допускает по крайней мере две различные расшифровки А' и А ". Для доказательства теоремы достаточно установить, что можно найти также такое слово В, что для его расшифровок А' и А имеют место неравенства ((А ) )(А„) ~[ ()т+ |) (1 — |+ 2) 1 ч, 1т. Теогпя коднговлння 265 Слово В, допускающее не менее двух расшифровок, называется непрнводимьы если каждое слово В', получающееся нз В путем выбрасывания непустого куска, допускает не более одной расшифровки. Ясно, что с самого начала можно предполагать, что слово  — непрнводнмо.
Рассмотрим его две расшнфров- гг Рвс. 4 ки А' и А". Очевидно, что с ними свяваны два равбиения слова В на элементарные коды — верхнее Т, и нижнее Т, (см. рис. 4). Возьмем произведение Т этих раэбиений, т. е. разбиение, которое получается путем одновременного равбиения Т, и Т,. Слова этого нового разбиения Т раэделим на два класса: к первому классу отнесем слова, являющиеся элементарными кодами, ко второму — все остальные слова.
Ясно, что слова иэ первого класса входят каждое ровно в одно разбиение, а слова второго класса (на рис, 4 иэображены жирными отреэками) являются одновременно непустыми началами' и концами элементарных кодов из разных разбиений и отличны от элементарных кодов, так как слово В неприводимо. Покажем, что каждые два слова р' и р" из второго класса раэличны, т. е.))'~р". Положим противное: р' р р, Тогда В В'р'В" р" В™ В'рВ" рВ, Утверждается, гго слово В'р'В", получающееся иэ В путем выбрасывания куска В" р", допускает по крайней мере две расшифровки. Для расположения слов р' и )) воэможны 4 случая, которые изображены на рис. 5. Нетрудно видеть, что случай в) сводится к случаю а), случай г) — к случаю 6). Для этого в в) и е) нужно поменять ролями разбиения Т, и Та. В случае а) при выбрасывании куска В" р и сдвигании кусков В'р' и В" верхнее равбиение получается из склейки частей верхнего раабиения, нижнее — ив склейки частей нижнего разбиения.
2св Ч. 1Ч. ТЕОРИЯ КОДИРОВАНИЯ Рнс. 5 В атом куске все словаВ,, ..., В,впринадлежат одному и тому же разбиению сло- Ф Ф" йл ва В, например Т„а слово Ф ФВ! ...В!1+ -В! Рис. 6 принадлежит другому разбиению — Т,. При этом 1Р < !т'. Поэтому с каждым куском связаны !Р элементарных кодов одного разбиения и один элементарный код другого разбиения. Если взять теперь два соседних куска р!В ° ... В ° А+!В.... В ° (1!+1, !1 ' ' ' !в !1 ' ' ' !в то элементарные коды В О ..., В °, В;. (т'+!В.... В ° р!+1 !1 ! !1 !в" В случае б) верхнее разбиение получается из склейки части верхнего разбиения для куска В'р' и нижнего разбиения для В", нижнее разбиение — путем склейки нижнего разбиения для куска В'р' и верхнего — для куска В". Итак, для слова В'р'В"' во всех случаях мы получа- ем по крайней мере две рас- Ф л в в шифровки, что противоречит тому, что исходное слово не- Ю приводимо.
Число р слов второго Ж класса не превосходит числа непустых собственных начал элементарных кодов, т. е. р -..(((В,) — 1)+ +(((В,) — 1)+... ... +(1(В,) — 1)= Б — г. Слова из второго класса разбивают слово В не более чем на Б — г+ 1 кусков,'некоторые из них могут быть пустыми (см. рис. б). Пусть р' р'+! Л. Рассмотрим один из кусков, рас. положенный между словами р! и ф+! (! =О, ..., р): б'В1,... В!.б'", ч. 1ч. ТБОРкя кодкРОВАния 267 входят в одно разбиение, а В ° В °, Вк фВ ...
В ° ~'+' !щЮ 1~р — в другое разбиение (см. рис. 7). Следовательно, кускам разбиения Т между словами ~' и р'+' для одной и той же четности у соответствуют Уг з/+3 4'~ Рас. 7 злементарные коды В, исходного разбиения (иапри- мер Т,) и группы элементарных кодов В;,, ..., В~ тогоже разбиения для другой четности ), Отсюда легко получается оценка для максимального числа элементарных кодов, входящих в разбиение.
Оно яе превосходит 1Ь вЂ” +2] [ Ь вЂ” + 21 [ (И~+ $) (Б — + 2! 1 Мы получаем, что ) (А,) (( ~„) ~ [ (Ж+ Ц (Б — г+ 2) ~ Если теперь положить № шах(ЦА'), ЦА")), то очевидно, что взаимная однозначность кодирования уже нарушается на множестве Я '(а), так как А', А" ы ея 8 '(6). Теорема полностью доказана. Критерий однозначности декодирования дает простой алгоритм для установления по схеме Х, будет алфавитное кодирование обладать свойством взаимной однозкачкости или нет. Для этого достаточно рассмотреть мвожество слов в алфавите й, имеющих длину не более №, ~О т. е. Б (И), и выяснить, будет лп кодирование этого ко- гвв Ч.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
