Введение в Алгебраическую теорию информации - Гоппа В.Д.
Скачать (прямая ссылка):
соответствует интервалу квантования (0.16; оо). В результате получаем
слово
х = (00 10 11).
1.9. Нахождение числа орбит
Каждая орбита однозначно определяется композицией (wij, ..., т^), где ^
т. = п. Таким образом, число различных
орбит совпадает с числом всевозможных представлений числа п в виде суммы
целых слагаемых (при этом допускается т. = 0
для некоторых г). Приходим к классической комбинаторной задаче: сколькими
способами можно разделить п одинаковых шаров (позиций слова) по q
различным урнам (буквам)?
15
Пусть, например, п = 4, q = 3. Возможны следующие варианты:
4 0 0 2 2 0
0 4 0 2 0 2
0 0 4 2 2 0
3 1 0 2 1 1
3 0 1 1 2 1
1 3 0 1 1 2
0 3 1
1 0 3
0 1 3
Упорядочим три буквы а, Ь, с следующим образом: а = 1, b = 2, с - 3.
Тогда варианту распределения (4 0 0) соответствует слово (а а а а) = (1 1
1 1), варианту (0 4 0)-слово (b b b Ь ) = = (2 2 2 2), а варианту (2 1
1)-слово (а а b с) = (112 3). При этом ?това (1 1 2 3) и (1 2 3 1)
отождествляются, поскольку лежат в одной и той же орбите. Отсортируем
каждое слово и прибавим (0 1 2 ...):
(112 3)
+ =>(1 2 4 6).
(0 12 3)
Получается взаимно однозначное отображение всех /г-слов q-ичного алфавита
на множество всех /г-слов в (п + q - 1)-ичном алфавите, причем в словах-
образах нет повторяющихся символов. Отсюда получаем формулу для числа
орбит:
(-^7 ¦).
В предыдущем, примере имеем
"-(4 + <~') = (') = 15-Если рассматривать слова с точностью до
переименования букв, то останутся лишь четыре варианта орбит:
(4), (3 1), (2 2), (2 1 1). ,
Всевозможные разбиения а, /?, ... числа п принято упорядочивать
лексикографически (как в словаре), так что
а = (т1 + т2 + ...) > /? = (п{ + п2 + ...)
тогда и только тоща, когда первая неисчезающая разность т{ - п.
положительна. Например, при п =7 имеем
(7) > (6, 1) > (5, 2) > (5, 1, 1) > (4, 2, 1) > (4, 1, 1, 1) >
> (3,3,1) > (3,2, 2) > (3,2, 1,1) > (3,1, 1,1,1) >
> (2, 2, 2, 1) > (2, 2, 1, 1, 1) > (2, 1, 1, 1,1, 1) > (1, 1, 1, 1, 1; 1,
1). Для числа таких разбиений не существует точной формулы.
1б
Пусть слово х имеет композицию (тj, /п?). Каждое
каноническое подслосо длины т. слова х порождает условное
разбиение, совпадающее с безусловным, поэтому на позициях,
соответствующих этому подслову, число орбит равно
'т. + д - 1\ i
v Я ~ 1
Так как все подслова действуют независимо, то общее число условных орбит
под действием слова х равно
JL (т. + 9-1'\
к, - П 1 '
/=1
Q ~ 1
П р и м е р 1.5.
л = (1 00 1 1), Y = X = {0, 1},
т
1 = 3, т2 = 2.
Число безусловных орбит равно
5 + 2-1 1
N =
= 6
(каждая орбита однозначно определяется числом единиц двоичного слова).
Число условных орбит при условии х равно
", = (3+П'(2+П = 12-
Ниже показаны все безусловные орбиты и их расщепление на условные:
I 00000 IV I) 10011
11 1) 00001 2) 11010
10000 11001
00010 01011
2) 01000 10110
00100 10101
111 1) 10001 00111
00011 3) 01101
2) 01100 01110
3) 11000 V 1) 11110
01001 11101
01010 01111
10100 2) 11011
00101 10111
00110 VI 11111
17
Число N совпадает в данном случае с числом всевозможных матриц 2x2 вида
1 0
1 т11 т12 3
0 т21 т22 2
Здесь т..-целые числа, такие, что
т11 + т12 = 3'
т21 + т22
= 2.
1.10. Сжатие по Фитингофу
Перейдем к описанию эффективного метода кодирования слов. Рассмотрим
сначала случай двоичного алфавита {q = 2). Каждая орбита здесь полностью
определяется числом единиц (весом Хэмминга) слова:
d = 0, 1, ..., п.
Это число будем считать номером орбиты и записывать его в виде префикса
постоянной длины ]log(n + 1) [. Для эффективной нумерации всех слов одной
и той же i-орбиты расположим их в лексикографическом порядке, считая, что
1 > 0:
1 1 1 1 0 *0 0
1 1 1 0 1 0 0
1 1 1 0 0 1 0
1 1 1 0 0 0 1
1 1 0 1 1 0 0
0 0 0 1 1 1 1
Пусть в слове х единицы занимают места п1 < п2 < ... <
считая справа. Например, для слова (110 110 0) = 3,
п2 = 4, "3 = 6, "4 = 7. Подсчитаем, сколько слов лежит ниже
слова х. Во-первых, нужно учесть все слова, у которых левые отрезки
совпадают вплоть до самой первой единицы (исключая ее). Тогда на п[ месте
в этих словах должен стоять 0, а последняя
единица может занимать любые из (/ij - 1) мест. Таким образом, всего
существует
1
таких слов.
Учтем, далее, все слова, которые совпадают с х левее п2-й позиции. Если у
этих слов на месте п2 также стоит 1, то приходим к предыдущему случаю.
Если же на месте п2 стоит 0, то остальные 18
две единицы могут занимать любое из
(V)
возможных мест.
Продолжая эти рассуждения, приходим к выводу, что число слов, лежащих
ниже слова х в лексикографическом упорядочении, равно
П2 ~ 1
nd~ 1
Это число и будем считать номером слова в <1-й орбите.
Пример 1.6. Для слова 1111000 га1=4, п2 = 5,
"3 = 6, = 7, поэтому его номер равен
i) + (г) + (з) +
= 34.
Слово же 0 0 0 11 1 1 имеет 0-й номер, поскольку = 1,
1 (
'6\
п2 = 2, га3 = 3, = 4. Номер слова 110 110 0 равен
l) + fl) + ft) +
= 30.
log
двоичных
Для записи номера слова d-к орбиты требуется
