21. ЗАДАЧА ОБ ОЖЕРЕЛЬЯХ, ФУНКЦИЯ МЁБИУСА И СИНХРОНИЗИРУЕМЫЕ КОДЫ
Некоторые вопросы теории кодирования связаны с известной комбинаторной задачей, называемой «задачей об ожерельях». Эту задачу можно сформулировать следующим образом.
Пусть ожерелье состоит из бусинок нескольких цветов (Доставка цветов). Спрашивается, сколько существует различных ожерелий, если задано число бусинок каждого цвета.
Расположим п бусинок по окружности, указав для каждой бусинки номер ее цвета. Если обойти эту окружность в определенном направлении, начав с некоторой бусинки, то ожерелью из п бусинок будет сопоставлено слово («х сц. . ,й„), где а{ есть номер цвета 1-й бусинки. Но обход можно начать с любой бусинки, поэтому любому ожерелью соответствует п слов, получаемых одно из другого циклическими сдвигами. Например, для ожерелья, представленного на рисунке, получаем следующие слова: 12213, 31221, 13122, 21312, 22131.
Вообще говоря, среди п слов, сопоставленных ожерелью, могут быть и одинаковые. Нас, однако, будут интересовать не все ожерелья, а только такие, которые нельзя составить из двух или более одинаковых «кусков». Таким ожерельям отвечают слова, которые нельзя составить из нескольких одинаковых слов меньшей длины. Будем называть подобные слова основными. Например, слова 11, 100100100 не являются основными, а слово 1011 — основное. Ясно, что каждому «несоставному» ожерелью отвечает п различных основных слов.
Чтобы указать удобную формулу для числа основных слов, нам потребуется так называемая Функция Мёбиуса ).
определяемая следующим образом:
Обозначим через Р„(т) общее число основных слов длины п алфавита из т символов. Тогда, как можно доказать,
где йи й2,. . ., <4— все различные делители числа п.
Формула (1) позволяет найти число интересующих нас ожерелий, которое, очевидно, равно Рп(т)/п.
Выясним теперь, какое отношение имеет задача об ожерельях к проблемам кодирования. Дело в том, что при передаче закодированных сообщений должна соблюдаться определенная синхронность работы на передающей и приемной сторонах канала связи, которая обеспечивается дополнительными устройствами — тактовыми генераторами. При сбоях этих генераторов происходит нарушение синхронизации, и в качестве начального символа кодового слова воспринимается символ, который начальным не является. Отсюда актуальность задачи построения кодов, способных восстанавливать синхронизацию. Один из возможных путей ее решения (если отвлечься от исправления ошибок в символах) состоит в следующем. Будем рассматривать множество п-буквенных кодовых слов, удовлетворяющее такому ограничению: если (ах а2. . .ап) и (Ь1 Ь2■ . ■Ьп) — кодовые слова (не обязательно различные), то никакое из «перекрытий» между ними не является кодовым словом. Коды с этим свойством называют синхронизируемыми, и они, как легко понять, отвечают поставленной цели.
Как и обычно, платой за усовершенствование кода является уменьшение числа кодовых слов и, как обычно, возникает вопрос, насколько велика эта плата. Для ответа на этот вопрос как раз и можно использовать решение задачи об ожерельях. В самом деле, если а=(а1 а2 а3. . ,ап) — кодовое слово синхронизируемого кода, то кодовым словом не может быть никакой его циклический сдвиг, так как он является перекрытием для пары (а, а). Кроме того, по той же причине всякое кодовое слово должно быть основным.
Поэтому максимальное число и-буквенных слов синхронизируемого кода, использующего алфавит из т символов, не превосходит числа несоставных ожерелий с п бусинками т различных цветов. Обозначив это число через \У'п(т), имеем, следовательно.
Таким образом, пользуясь (1), получаем такую верхнюю границу для числа п-буквенных кодовых слов синхронизируемого кода:
(здесь . .,йк по-прежнему все различные делители я).
I. Доказать следующее свойство функции Мёбиуса: ц («т)=(я («)|х (т) для любых взаимно простых пит.
2. Функция / называется сумматорной функцией для р, если (запись й\п означает, что суммирование распространяется на все различные делители числа п).
Показать, что сумматорная функция для функции Мёбиуса равна нулю при и>1 и единице при п= 1.
3. Пусть / — сумматориая функция для {> (см. задачу 2). Верна следующая замечательная формула обращения Мёбиуса, лежащая в основе всех приложений функции и(и1:
Действительно,
В получившейся двойной сумме изменим порядок суммирования. Заметим для этого, что аргумент к функции ц(к) при двойном суммирова-
Можно доказать (но это достаточно сложно), что при нечетных п граница (2) действительно достигается, и что это, вообще говоря, не так, если я четно. Относительно простые выкладки показывают, что при больших п сумма в скобках близка к т", т. е. к общему числу слов длины п в т-буквен- ном алфавите, так что число допустимых слов синхронизируемого кода примерно в я раз меньше общего числа слов длины п.
Задачи и дополнениянии пробегает всевозможные делители числа п, и если к фиксировано, то Л пробегает все делители п, которые в свою очередь делятся на к. Поэтому двойную сумму (4) можно переписать в виде:
при этом запись к\Л\п обозначает, что й пробегает все делители п, делящиеся на к. Введем обозначения т=п/с1 и 1=п1к, тогда т пробегает всевозможные делители /ив силу утверждения задачи 2
Обращаясь теперь к выражению (5), мы си/м , что в сумме по к имеется лишь одно ненулевое слагаемое, отвечающее значению к=п, я потому что равносильно (3).
4. Назовем число й периодом слаьа и, если а получается сочленением одинаковых слов длины Л и не является сочленением одинаковых слов меньшей длины. Пусть Ра (т) означает общее число слов длины п в алфавите из т символов, имеющих период Л.
Следовательно,
и, пользуясь формулой обращения (3), получить оценку (2),