Введение в Алгебраическую теорию информации - Гоппа В.Д.
Скачать (прямая ссылка):
рефлексивное, симметричное и транзитивное бинарное отношение. Это
отношение порождает разбиение Q на непересе-кающиеся классы.
Множество классов эквивалентности называется фактормножеством и
обозначается Q/Пусть л: Q-*Q/" обозначает каноническое проектирование,
которое каждому элементу со G Q ставит в соответствие его класс
эквивалентности л(со). Информацию элемента со определим в виде
В предельном случае, когда существует только один класс эквивалентности,
информация каждого элемента одинакова и совпадает с информацией по
Хартли.
Предложение 1.1. Если N обозначает число классов эквивалентности:
Доказательство. Пусть W. обозначает г-й класс. Тогда
I(co) = log2 IQI.
I(co) = log21 л(со) I.
N= IQ/* I,
mo
cuEQ
N
N
i=l
i=l
5
1.3. Неравномерное кодирование слов
Пусть X-конечное множество (алфавит), IЛ = q, Хп-множество слов длины п в
алфавите X. Обозначим через В двоичный алфавит, так что В = {0, 1}, а
через В*-множество всех слов конечной длины в алфавите В. Неравномерным
кодом (сжимающим отображением) называют отображение
W: Хп -* В*,
определенное для любого п = 1, 2, ...
Код называется префиксным или дешифрируемым, если tp(x) не является
началом никакого другого кодового слова У'(х'), х' * х. Длину кодового
слова Ц>(х) обозначим через 1(х).
Слова префиксного кода можно записывать в одну цепочку, не используя
разделительных символов (запятых). Любую такую цепочку можно единственным
образом разложить на ее компоненты.
Предложение 1.2 (неравенство Крафта). Для существования префиксного кода
с длинами слов п^, nN необходимо и
достаточно, чтобы
N
2 2""' < 1.
/= 1
Доказательство. Если у префиксного кода существует слово длины у, то все
2n~J слов длины п (п > у), получающиеся добавлением п - j символов, не
могут входить в префиксный код. Если обозначить через S. число кодовых
слов длины у, то получаем
неравенство
S < 2" - S.-2n~l - S--2""2 - S .-2,
п 1 2 л-1
справедливое для любого п = 2, 3, ... Ясно, что это условие является
также и достаточным для построения префиксного кода с соответствующими
{S.}. Разделив на 2п, получаем
? Sy2~! < 1,
j=l
что и требовалось доказать, поскольку
i S/2-< = 2 2Л
/= 1 П<.п
6
Сопоставляя предложения 1 и 2, заключаем, что существует префиксный код с
длинами двоичных слов
1(со) = /(со) + log N, 1{со) = ]1{со) + log N[,
где ]а[ обозначает ближайшее целое, большее или равное а.
Ясно также, как осуществить кодирование: сначала нужно указать номер
класса W., содержащего со (для этого потребуется
префикс, содержащий JlogN[ двоичных символов), а затем указать номер
элемента со в классе W. (для этого потребуется еще
]log \W.\ [ символов). В дальнейшем основание логарифма предполагается
равным 2.
1.4. Действие группы на множестве
Рассмотрим наряду с множеством ?2 конечную группу G. Говорят, что G
действует на ?2, если задано отображение G х ?2 такое, что
(от)со = о(ты), есо = со
для всех <7, т G G и со S ?2; здесь та" обозначает образ пары (т, со) при
этом отображении, а е-единица группы G.
В этом случае ?2 называют G-множеством. Множество элементов те С, для
которых тсо = со есть, очевидно, подгруппа в G. Она называется
стационарной подгруппой элемента со и обозначается G. Подмножество в ?2,
состоящее из всех элементов
вида осо (где а Е G) обозначается Gw и называется орбитой элемента со.
Если а и т лежат в одном и том же (смежном) классе по Я = G' , то оси =
тсо, и обратно. Таким образом,
существует взаимно однозначное соответствие между левыми смежными
классами G/H и элементами орбиты Geo. Следовательно, порядок орбиты Geo
совпадает с индексом [G:G1 }. Заметим, что
G'¦ не является, вообще говоря, нормальной подгруппой в G.
Две орбиты группы G либо не пересекаются, либо совпадают. Таким ооразом,
на G-множестве существует каноническое разбиение
N
Я = 2 Оюс i=i
Поэтому на ?2 можно определить информацию разбиения /(со) = log IGbl =
log [G:GJ.
1.5. 0-информация слова
Пусть X-конечное множество (алфавит), Хп = ?2-множество всех слов
(последовательностей букв) длины п в алфавите X. На
7
Хп канонически действует симметрическая группа S^, переставляющая позиции
букв слова. Поэтому Хп является .^-множеством и можно ввести информацию
разбиения. Для произвольного слова со 6 Хп, со - (а|, а2, ..., а^) и
произвольной подстановки a G Sn действие Sn описывается как
о(со) = ("*,). V). •••.%,)).
Если буква a. S X входит в слово со е Хп ровно т. раз, i = 1, 2, ..., IЛ
= д, то разбиение п = т1 + ... + т определяет композицию (wij, ..., гПу)
слова со. Ясно, что все слова одной
и той же орбиты имеют одну и ту же композицию и обратно. Величину
/Q = log I Geo I,
где G = S , назовем 0-информацией слова со.
Стационарная подгруппа G' является в данном случае прямым произведением
симметрических групп
S х S х ... х 5 ,
т т т
1 2 q
поэтому
п\
/0(ш) = log
т. ImJ ... т !'
12 q
П р и м е р 1.1. Слово а>1 = (аааа) имеет композицию (4), поэтому Iq(oj
i) = 0. Слово со2 = (аЪаа) имеет композицию (3, 1), поэтому
