ГНОМОН. От фараонов до фракталов - Газале М.
ISBN 5-93972-171-0
Скачать (прямая ссылка):
Вышеописанное упражнение можно продолжать до бесконечности — для современных компьютеров сложные переплетения межвершинных связей вряд ли составят сколько-нибудь серьезную проблему — однако представить эти переплетения визуально становится при дальнейшем увеличении размерности весьма и весьма затруднительно. Очевидно, что коэффициенты в приведенных тождествах являются не чем иным, как биномиальными коэффициентами, которые можно легко получить, следуя правилу построения знаменитого треугольника Паскаля (см. рис. 1.5Ь):
Отметим, что сумма чисел, расположенных на любой линии х, равна 2х, т. е. количеству вершин ж-мерного диадического гиперкуба, тогда как сумма чисел, расположенных на диагонали х = j, равна числу Фибоначчи F\^x.
Диадический гамильтонов путь
Приблизительно в середине XIX в. известный ирландский математик Уильям Роуан Гамильтон придумал игру, суть которой заключалась в прохо-
Ш-АДИЧЕСКИЕ ЧИСЛА
37
ждении ребер правильного многогранника таким образом, чтобы посетить каждую из его вершин один и только один раз и вернуться в исходную точку Особое внимание он уделял додекаэдрам (12 граней) и икосаэдрам (20 граней). В честь последнего многогранника была даже названа сама игра («икосианская игра»), которую, как ни удивительно, Гамильтон даже умудрился продать за двадцать пять фунтов стерлингов! В эту игру можно сыграть и на трехмерном диадическом кубе, центральная проекция которого изображена на цветной вклейке 16; красной линией показано искомое прохождение, называемое гамильтоновым путем. Читателю, возможно, будет интересно отыскать все возможные для такой фигуры гамильтоновы пути. Задача несколько усложняется, если заменить трехмерный диадический куб четырехмерным гиперкубом (см. вклейку 14).
Один из возможных гамильтоновых путей для четырехмерного гиперкуба показан на вклейке 17. Не стоит и пытаться тут же выяснить, сколько существует таких путей, — если, конечно, у вас нет под рукой мощного компьютера4. Двигаясь по ребру гиперкуба на вклейке 17 из вершины 0000 в вершину 0001, можно счесть, что число 0000 есть кодированное представление целого числа 0, число 0001 — целого числа 1, число 0011 — целого числа 3 и т. д. При этом мы получаем безусловно допустимый четырехразрядный (или четырехбитный) двоичный код для шестнадцати целых чисел от 0 до 15. Соответствие между этим кодом (который называют также двоичным рефлексивным кодом или кодом Грея5) и его десятичным и классическим двоичным (или диадическим) эквивалентами представлено в таблице 1.4. Отметим, что двоичные представления чисел — например,
7 и 8 — различаются во всех четырех знаках, двоичные коды некоторых других пар последовательных чисел различаются более чем одним знаком. С другой стороны, любые два последовательных кода Грея различаются в одном и только в одном знаке; более того, даже если последовательность из шестнадцати чисел замкнуть в петлю таким образом, чтобы 0 следовал за 15, коды, соответствующие этим двум целым числам, также будут различаться лишь одним знаком.
Построим мысленно следующий прибор: из какого-нибудь прозрачного материала сделаем кодирующий диск (аналогичный тем, что изображены на цветной вклейке 18), на визире разместим четыре миниатюрных источника света, по одному на каждое кольцо. С другой стороны диска аналогичным образом установим четыре фотоэлемента, по одному на каждый источник света. Получившаяся у нас конструкция может с успехом функционировать как осевой ротационный кодировщик с разрешением 2тг/16 радиан.
4См. «Gray codes and Paths on the гг-cube», Bell Systems Technical Journal 37, No. 1 (May 1958), pp. 815-826
5Фрэнк Грей, научный сотрудник «Bell Labs», патент №2632058 от 17 марта 1953 года на кодирующую вакуумную трубку Грея.
38 Глава I
Таблица 1.4. Десятичный код, код Грея и двоичный (диадический) код
Десятичный код Код Грея Двоичный код
0 0000 0000
1 0001 0001
2 0011 0010
3 0010 0011
4 0110 0100
5 0111 0101
6 0101 0110
7 0100 0111
8 1100 1000
9 1101 1001
10 1111 1010
11 1110 1011
12 1010 1100
13 1011 1101
14 1001 1110
15 1000 1111
В случае кодирующего диска Грея переход от какого-либо кодового значения к следующему по порядку требует изменения всего лишь одного бита, тогда как двоичный диск может при этом сгенерировать большое количество паразитных промежуточных кодов, поскольку идеального совмещения источников и детекторов света добиться практически невозможно. Работы по конструированию цифровых механических датчиков смещения — таких, например, как осевые измерители угловой скорости, — а также разработка первых телеграфных аппаратов, систем импульсно-кодовой модуляции и т. п. привели к необходимости создания кодов, при применении которых при переходе между соседними значениями сигнала не генерируется никаких промежуточных значений. Французский инженер Эмиль Бодо разработал так называемый циклический перестановочный код, который считается предшественником кода Грея. Этот код, в сущности, и является основной
