Коды и математика (рассказы о кодировании) - Аршинов М.Н.
Скачать (прямая ссылка):
Обозначим через Рп(т) общее число основных слов длины п алфавита из т символов. Тогда, как можно доказать,
P„(m)=m(d1)mn/d* + \i(dt)mald' + ... + ц(йк)тп,\ (1)
где dlt d2,. . ., dk— все различные делители числа п.
Формула (1) позволяет найти число интересующих нас ожерелий, которое, очевидно, равно Рп(т)/п.
Выясним теперь, какое отношение имеет задача об ожерельях к проблемам кодирования. Дело в том, что при передаче закодированных сообщений должна соблюдаться определенная синхронность работы на передающей и приемной сторонах канала связи, которая обеспечивается дополнительными устройствами — тактовыми генераторами. При сбоях этих генераторов происходит нарушение синхронизации, и в качестве начального символа кодового слова воспринимается символ, который начальным не является. Отсюда актуальность задачи построения кодов, способных восстанавливать синхронизацию. Один из возможных путей ее решения (если отвлечься от исправления ошибок в символах) состоит в следующем. Будем рассматривать множество л-буквенных кодовых слов, удовлетворяющее такому ограничению: если (Ct1 а2, . .ап) и (bx b2. . .Ьп) — кодовые слова (не обязательно различные), то никакое из «перекрытий» между ними
(а2а3. . MJj1), (а3. . .о„6Л).....(aA- • -^-i)
не является кодовым словом. Коды с этим свойством называют синхронизируемыми, и они, как легко понять, отвечают поставленной цели.
Как и обычно, платой за усовершенствование кода является уменьшение числа кодовых слов и, как обычно, возникает вопрос, насколько велика эта плата. Для ответа на этот вопрос как раз и можно использовать решение задачи об ожерельях. В самом деле, если O=Ia1 а2 а3. . .ап) — кодовое слово синхронизируемого кода, то кодовым словом не может быть никакой его циклический сдвиг, так как он является перекрытием для пары (а, а). Кроме того, по той же причине всякое кодовое слово должно быть основным.
і М. її. АршищоБ, Л. Е. Садовский
из Поэтому максимальное число «-буквенных слов синхронизируемого кода, использующего алфавит из т символов, не превосходит числа несоставных ожерелий с п бусинками т различных цветов. Обозначив это число через Wn(m), имеем, следовательно,
Таким образом, пользуясь (1), получаем такую верхнюю границу для числа /г-буквенных кодовых слов синхронизируемого кода:
Wn (т) < (М- +...+V- (dk) тЫ*ь)\ (2)
(здесь di,. . .,dk по-прежнему все различные делители п).
Можно доказать (но это достаточно сложно), что при нечетных п граница (2) действительно достигается, и что это, вообще говоря, не так, если п четно. Относительно простые выкладки показывают, что при больших п сумма в скобках близка к т", т. е. к общему числу слов длины п в /«-буквенном алфавите, так что число допустимых слов синхронизируемого кода примерно в п раз меньше общего числа слов длины п.
Задачи и дополнения
1. Доказать следующее свойство функции Мёбиуса: |А (шп)=|х (п)ц (т) для любых взаимно простых пит.
2. Функция / называется сумматорной функцией для g, если
/ (") = 2g(d) а\п
(запись d\ti означает, что суммирование распространяется на все различные делители числа п).
Показать, что сумматорная функция для функции Мёбиуса равна нулю при п>1 и единице при п=1.
3. Пусть / — сумматорная функция для g (см. задачу 2). Верна следующая замечательная формула обращения Мёбиуса, лежащая в основе всех приложений функции (.1 (п):
g(n) = hn(n/d) I (d). (3)
dl п
Действительно,
2 ц (n/d) / (d) = 2 Ц (n/d) 2 в (k) = 2 2 jx (nid) g (k). (4)
d\n d\n h\d d\n k\d
В получившейся двойной сумме изменим порядок суммирования. Заметим для этого, что аргумент k функции g (k) при двойном суммирова-
,114 нии пробегает всевозможные делители числа п, и если k фиксировано, то d пробегает все делители п, которые в свою очередь делятся на k. Поэтому двойную сумму (4) можно переписать в виде:
2 2 Ё(Щ | i (nld) = ^Eig(K) E |i (n/d), (5)
k\n k\d\n k\n k\d\n
при этом запись k\d\n обозначает, что d пробегает все делители л, делящиеся на k. Введем обозначения m=n!d и t=n!k, тогда т пробегает всевозможные делители t ив силу утверждения задачи 2
если ;='•
k\d\n m\t \ 0, если t > 1.
Следовательно,
S |i(n/rf) = i еСЛИ к = п- (А —делитель п). u\d\n ( 0, если k < п
Обращаясь теперь к выражению (5), мы видны, что в сумме по k имеется лишь одно ненулевое слагаемое, отвечающее значению k=n, и потому
SgW Л, n(n/d)=g(n),
kin Н'Л'ї
что равносильно (3).
4. Назовем числос! периодом слоьа а, если а получается сочленением одинаковых слов длины d и не является сочленением одинаковых слов меньшей длины. Пусть Pd (т) означает общее число слов длины п в алфавите из т символов, имеющих период d. Убедиться, что
л ^Ра(т)=т",
d\n
и, пользуясь формулой обращения (3), получить оценку (2), ЗАКЛЮЧЕНИЕ
Наши рассказы о кодировании подошли к концу. Мы познакомились, конечно, далеко не со всеми задачами этой теории, но в той или иной мере затронули три ее основных направления — кодирование с целью засекречивания сообщений, кодирование с целью сжатия информации, наконец, кодирование с целью исправления и обнаружения ошибок. Нам хотелось дать представление читателю, сколь широки и многообразны связи этой теории с разными разделами математики, и как порой самые абстрактные математические теории могут с успехом применяться для решения практических задач.
