Новости    Библиотека    Энциклопедия    Биографии    Карта сайта    Ссылки    О проекте




предыдущая главасодержаниеследующая глава

21. Задача об ожерельях, функция Мёбиуса и синхронизируемые коды

Некоторые вопросы теории кодирования связаны с известной комбинаторной задачей, называемой "задачей об ожерельях". Эту задачу можно сформулировать следующим образом.

Пусть ожерелье состоит из бусинок нескольких цветов. Спрашивается, сколько существует различных ожерелий, если задано число бусинок каждого цвета.


Расположим n бусинок по окружности, указав для каждой бусинки номер ее цвета. Если обойти эту окружность в определенном направлении, начав с некоторой бусинки, то ожерелью из n бусинок будет сопоставлено слово (a1 а2 ... аn), где аi есть номер цвета i-й бусинки. Но обход можно начать с любой бусинки, поэтому любому ожерелью соответствует n слов, получаемых одно из другого циклическими сдвигали. Например, для ожерелья, представленного на рисунке, получаем следующие слова:

12213, 31221, 13122, 21312, 22131.

Вообще говоря, среди n слов, сопоставленных ожерелью, могут быть и одинаковые. Нас, однако, будут интересовать не все ожерелья, а только такие, которые нельзя составить из двух или более одинаковых "кусков". Таким ожерельям отвечают слова, которые нельзя составить из нескольких одинаковых слов меньшей длины. Будем называть подобные слова основными. Например, слова 11, 100100100 не являются основными, а слово 1011 - основное. Ясно, что каждому "несоставному" ожерелью отвечает n различных основных слов.

Чтобы указать удобную формулу для числа основных слов, нам потребуется так называемая функция Мёбиуса *), определяемая следующим образом:


*) (Август Фердинанд Мёбиус (1790-1868) - немецкий математик и астроном, известный, главным образом, своими работами по проективной геометрии. Им были впервые систематически изучены свойства функции μ(n).)

Обозначим через Рn(m) общее число основных слов длины n алфавита из m символов. Тогда, как можно доказать,

Pn(m) = μ(d1)mn/d1 + μ(d2)mn/d2 + ... + μ(dk)mn/dk, (1)

где d1, d2, ..., dk - все различные делители числа n. Формула (1) позволяет найти число интересующих нас ожерелий, которое, очевидно, равно Рn(m)/n.

Выясним теперь, какое отношение имеет задача об ожерельях к проблемам кодирования. Дело в том, что при передаче закодированных сообщений должна соблюдаться определенная синхронность работы на передающей и приемной сторонах канала связи, которая обеспечивается дополнительными устройствами - тактовыми генераторами. При сбоях этих генераторов происходит нарушение синхронизации, и в качестве начального символа кодового слова воспринимается символ, который начальным не является. Отсюда актуальность задачи построения кодов, способных восстанавливать синхронизацию. Один из возможных путей ее решения (если отвлечься от исправления ошибок в символах) состоит в следующем. Будем рассматривать множество n-буквенных кодовых слов, удовлетворяющее такому ограничению: если (а1 а2 ... аn) и (b1 b2 ... bn) - кодовые слова (не обязательно различные), то никакое из "перекрытий" между ними

2а3 ... anb1), (а3 ...а1b1b2), ..., (anb1 ... bn-1)

не является кодовым словом. Коды с этим свойством называют синхронизируемыми, и они, как легко понять, отвечают поставленной цели.

Как и обычно, платой за усовершенствование кода является уменьшение числа кодовых слов и, как обычно, возникает вопрос, насколько велика эта плата. Для ответа на этот вопрос как раз и можно использовать решение задачи об ожерельях. В самом деле, если а = (а1 а2 а3 ... аn) - кодовое слово синхронизируемого кода, то кодовым словом не может быть никакой его циклический сдвиг, так как он является перекрытием для пары (а, а). Кроме того, по той же причине всякое кодовое слово должно быть основным.

Поэтому максимальное число n-буквенных слов синхронизируемого кода, использующего алфавит из m символов, не превосходит числа несоставных ожерелий с n бусинками m различных цветов. Обозначив это число через Wn(m), имеем, следовательно,

Wn(m) ≤ 1/n Pn(m).

Таким образом, пользуясь (1), получаем такую верхнюю границу для числа n-буквенных кодовых слов синхронизируемого кода:

Wn(m) ≤ 1/n (μ(d1)mn/d1 + ... + μ(dk)mn/dk); (2)

(здесь d1, ..., dk по-прежнему все различные делители n). Можно доказать (но это достаточно сложно), что при нечетных n граница (2) действительно достигается, и что это, вообще говоря, не так, если n четно. Относительно простые выкладки показывают, что при больших n сумма в скобках близка к mn, т. е. к общему числу слов длины n в m-буквенном алфавите, так что число допустимых слов синхронизируемого кода примерно в n раз меньше общего числа слов длины n.

предыдущая главасодержаниеследующая глава




ИНТЕРЕСНО:

Многомерный математический мир… в вашей голове

В школах Великобритании введут китайские учебники математики

Найдено самое длинное простое число Мерсенна, состоящее из 22 миллионов цифр

Как математик помог биологам совершить важное открытие

Математические модели помогут хирургам

Почему в математике чаще преуспевают юноши

Физики-практики откровенно не любят математику

В индийской рукописи нашли первое в истории упоминание ноля

Вавилонская глиняная табличка оказалась древнейшей «тригонометрической таблицей» в мире

Ученые рассказали о важной роли игр с пальцами в обучении детей математике
Пользовательского поиска

© Злыгостев Алексей Сергеевич, статьи, подборка материалов, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить ссылку на страницу источник:
http://mathemlib.ru/ 'MathemLib.ru: Математическая библиотека'
Рейтинг@Mail.ru