Введение в Алгебраическую теорию информации - Гоппа В.Д.
Скачать (прямая ссылка):
Поскольку мы .рассматриваем слова с точностью до эквивалентности, то
каждое слово однозначно определяется своей композицией и перечислением
номеров позиций, занятых одной и той же буквой.
11
П р и м е р 1.3. Слово х = (abaacbca) можно задать в виде
х =
1
2
5
3
6
7
Зная такую таблицу, можно однозначно восстановить слово х с точностью до
переименования букв: на позициях 1, 3, 4 и 8 устанавливаем некоторую
букву d:
d d d d
1 2 3 4 5 6 7 8
Далее, на позициях 2 и 6 помещаем некоторую другую букву а
d a d d a d
1 2 3 4 5 6 7 8
Наконец, оставшиеся позиции занимаем третьей буквой, например Ь:
d a d d b a b d
1 2 3 4 5 6 7 8
В результате получаем слово з>, полученное из первоначального слова х
переименованием букв: a-* d, b -* а, с -* Ь (в криптографии такой прием
называется шифром Цезаря).
Таким образом, каждое слово разбивается на несколько канонических подслое
нулевой 0-информации. Например, слово х "склеивается" из следующих
подслов:
a a a a
1 2 3 4 5 6 7 8
Стационарная подгруппа G состоит из всех перестановок,
оставляющих неподвижной каждую строку в таблице Юнга, или, что то же
самое, каждое каноническое подслово. Поскольку
G = S х S х ... х 5
х т т т
1 2 ч
и каждая из этих симметрических групп действует независимо на своем
множестве позиций, орбита слова под действием Gx
оказывается произведением орбит под действием канонических подслов слова
х. Но условная орбита под действием канонического подслова совпадает с
безусловной орбитой. . Тем самым вычисление
условной информации сводится к вычислению безусловной информации.
Пусть х и у имеют композиции (п{, ..., п^)
соответственно. Составляем матрицу переходов букв слова х в буквы слова
у.
mll + m!2 + . .. + s" II s"
m21 + m22 + .. .. + m2k = mV
m . "1 + m -ql + .. . + m , = m . qk q
Тогда
IQ(y/x) = log
m.l
т.
I
1Г
Пример 1.4.
т
+ log
тТ
\к'
m
21'
... m
+
+ log
m !
_2_
2JC
m , ! ... m ,!'
g\ qk
x = (a b a a с b с a), у = (1 2 2 1 3 2 1 3),
1 2 3
a 2 1 1 4
b 2 2
с 1 1 2
3 3 2 8
Матрица переходов составлена следующим образом: замечаем, что буква а
переходит в символ 1 два раза, и по одному разу в символы 2 и 3 слова у.
Тем самым получаем первую строку матрицы и подсчитываем сумму элементов
этой строки. В конце определяем также сумму элементов каждого столбца.
Тем самым в матрице присутствуют композиции слов х и у.
х = (4, 2, 2), у = (3, 3, 2), а также общая длина слова:
п - 4 + 2 + 2 = 3 + 3 + 2 = 8.
i°g 2ГГПТ + log fr+ i°g ТПТ= log 12 + log 2 = log 24'
Производя такие же вычисления по столбцам, получаем IQ{x/y): IQ{x/y) =
log 2TjT + ,ог 2ПТ + log ШТ = 2 ,°g 3 + log 2 = log 18.
13
Для безусловной информации находим значения
У*) = l°g '41 2! 2! = log 420, I0(y) = log з; gj 2, = log 560.
Вычисляем взаимную информацию:
J0(x--y) = 10(х) ~ 10(х/у) = log = log Y =
= 10(у) - 10{у1х) = log ^ = log у.
Далее, слово х <8> у имеет композицию (2, 2, 1, 1, 1, 1,), поэтому
8' У* (r) У) = l°g 2121'
1.8. Группировка наблюдений (квантование)
Выясним теперь, как меняется , информация слова при отождествлении
некоторых букв алфавита. При переходе к алфавиту X' = Х/*& некоторые
канонические подслова склеиваются. Пусть в примере 1.3 буквы b и с
отождествляются. Тогда получаем вместо исходного слова х новое слово х':
х' = (a b a a b b b а),
х = (а b а а с b с а).
Имрет место функциональная зависимость х -* х', вызванная тем, что с -*
Ь. Поэтому
IQ(x:x') = 10(х') - I0(x'/x) = IQ(x').
С другой стороны,
У**') = у*) - у*/*')-
При вычислении IQ(x/x') можно ограничиться лишь буквами b и
с, которые отождествляются между собой:
Ь с______
b 2 2 4
У*/*') = lo&2Vv. = log6,
N
420 '
у*') = у*)-у*/*') = log-f - log 70.
Вычисляя непосредственно IQ(x'), получаем
У*') = log70,
14
Резюмируем сказанное.
Пре дложение 1.8. Информация слова уменьшается в результате
отождествления некоторых букв алфавита (группировки наблюдений). Если х и
х' обозначают соответственно исходное и новое слово, то
Vх') = 70w ~ 70(х/х') = Vx:x')-
Пусть в результате наблюдений получено слово (последовательность данных)
х = (0.16, 0.1, 0.7, 0.1, 0.18, 1.5).
Требуется превратить это слово в двоичное слово, выбрав соответствующие
два интервала квантования. Естественное требование заключается в том,
чтобы новое слово х' содержало как можно больше информации об исходном
слове, т. е. чтобы как можно меньше информации было бы утеряно при
квантовании. Таким образом, величина IQ(x:x') должна быть максимальной.
Но
эта величина совпадает, согласно предложению 1.8, с величиной /0(х').
Последняя величина примет наибольшее значение, когда 1
и 0 будут распределены поровну в слове х'. Приходим к квантованию по
принципу "вариационного ряда": нужно упорядочить все данные по
возрастанию, т. е.
0.16 0.1 0.7 0.1 0.18 1.5
3 1 5 2 4 6
Первые три значения относим к первому классу, что соответствует интервалу
(-°°; 0.16], а остальные три значения относим ко второму классу, что
