Введение в Алгебраическую теорию информации - Гоппа В.Д.
Скачать (прямая ссылка):
символов. Таким образом, каждое кодовое слово состоит в данном случае из
постоянной части (префикса длины ]log(n+l)[) и
'°* G)
переменной части длины
Общий случай недвоичного алфавита сводится к двоичному с помощью
последовательного отождествления букв. Пусть слово имеет композицию (т^
..., т^). Выделим букву а1, а остальные
буквы отождествим. Получим двоичное слово, в которое входит т1 единиц.
Это слово закодируем описанным выше способом, а
затем применим те же рассуждения к каноническому подслову длины п - wij,
записанному в старом алфавите. В результате
получим кодовое слово длины
l(x) = ]log (п + 1)[ +
log
т,
+ ] log (п - т1 + 1)[ +
log
п - т
т
.. + ]log (п - т1 - ... - т _2 + 1)1 +
log
2
in - т
- т
9-2
т
д-1
19
Величина
п - тЛ (п - т, - ... - т 1 д-2 II ¦
т2 \ / 3 1 т,!т2!.. . т ! я
Кроме того,
(п + 1)(л - т{ + 1) ... (л - т{ - ... - тд_2 + 1) - (п + I)9 *-
Последняя оценка имеет простое объяснение: для того, чтобы указать номер
орбиты, достаточно выделить д - 1 упорядоченных ящиков, в каждый из
которых записывать числа ..., mQ_l-
Поскольку каждое из этих чисел может принимать значения от
О до п, имеется ровно (п + l)^-1 возможностей. Эта оценка является
достаточно точной для числа орбит при больших п и фиксированном д.
Описанный метод сжатия требует вычисления
биномиальных коэффициентов . Известное тождество
позволяет находить эти коэффиценты с помощью треугольника Паскаля:
1 2 3 4 5 6 7
8 7 21 35 35 21 7 1
7 6 15 20 15 6 1 0
6 5 10 10 5 1 0
5 4 6 4 1 0
4 3 3 1 0
3 2 -> *- 1 0
2 1 -> *- 0
1 0
Треугольник строится снизу вверх и слева направо сложением соседних
элементов. На пересечении г'-й строки и /-го столбца
стоит элемент ^j. Допустим, требуется вычислить номер слова
1 10 10 0. Здесь Atj = 3, п2 = 4, rt3 = 6, = 7. Находим в первом
столбце треугольника элемент 3-й строки: он равен 2, затем во втором
столбце ищем элемент 4-й строки, он равен 3 и т.д. Складывая эти числа,
получаем искомый номер слова. Следовательно, если хранить треугольник в
памяти компьютера, то процесс сжатия происходит практически мгновенно.
Конечно, при больших п приходится для построения треугольника Паскаля
работать с числами большой разрядности, реализуя соответствующую
арифметику программным путем.
20
Рассмотрим теперь, как происходит процесс декодирования. Требуется по
номеру
N*
восстановить числа п^, п2, ..., п^. Для этого воспользуемся следующим
свойством треугольника Паскаля:
Это простое следствие основного тождества для биномиальных коэффициентов
можно интерпретировать так: если просуммировать d элементов главной
диагонали, отличной от нулевой, слева направо, то получится число, на
единицу меньше того числа, которое стоит выше последнего диагонального
элемента в d-м столбце. Например, 1 + 1 + 1 + 1=5 - 1,
2+3+4+5=
= 15-1, 3 + 6 + 1 0 + 1 5 = 35 - 1.
Получаем следующий способ декодирования. Пусть Nx = 30 (предполагается,
что п и d фиксированы, п = 7, d = 4). Находим в 4-м столбце наибольший
элемент, не превосходящий 30. Им оказывается число 15 в 7-й строке.
Это число обязательно
входит в разложение Nx. Действительно, если бы нужным
элементом оказалось бы число 5 из 6-й строки, то, поскольку
п1 < п2< < nd' ^ не превосходило бы суммы чисел диагонали,
содержащей число 5, т. е. величины 5 + 4 + 3 + 2, которая меньше 15.
Таким образом заключаем, что п4 = 7. Вычитаем 15
из 30 и находим в 3-м столбце максимальный элемент, не превосходящий 15.
Им оказывается число 10 в 6-й строке. Заключаем, что п3 = 6. Точно так же
находим номера п2 = 4 и
Подытожим сказанное
Т еорема 1.1. Существует префиксный код полиномиальной трудоемкости, у
которого длина кодового слова асимптотически равна его 0-информации:
1(х) = /0(х) + О(п), где 10(п) I < (q - 1) log (n + 1) + 2(q - 1).
1.11. Независимость
Величины /Q(у/х) и IQ(x:y) характеризуют степень зависимости
слов. Один предельный случай, когда IQ(y/x) = 0, был уже
рассмотрен в этой главе. Он соответствует самой сильной зависимости-
функциональной зависимости х -* у. В этом случае взаимная информация
IQ(x:y) принимает максимальное значение,
+ ... +
+ 1.
21
равное /0(.у). Для эквивалентных слов расстояние р(х, у) = 0, а
*0(х'-У) = У*) = /0(у).
Рассмотрим теперь другой крайний случай, когда IQ(x:y) = 0.
Предложение 1.9. Следующие определения эквивалентны'.
1) Слова х и у независимы; 2) IQ(x:y) = 0,
3) /0(х/у) = /0(дс), 4) I0(y/x) = IQ(y).
Таким образом, если х и у независимы, то в слове х не содержится никакой
информации относительно слова у.
Примером независимых слов являются слова
х = (1 1 1 1), у - (а Ъ Ъ а).
Информацию слова мы будем вычислять с точностью до О(п), так что
независимыми оказываются также слова
х = (1 1 1 1 000 0), >> = (01010101).
По определению IQ(y/дс) = log [G^:(G^ П G^)\. Когда слово
х фиксировано, то IQ(y/x) принимает наибольшее значение, если
G П G = е. При этом х у
I0(y/x) = log I GxI, /0(х/у) = log IG^I, I0(x(r)y) = log IGI.
