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),