ПРОГРАММИРОВАНИЕ, 2011, No 2, с. 61-70
КОМПЬЮТЕРНАЯ АЛГЕБРА -
УДК 681.3.06
ПОСТРОЕНИЕ ВЕСОВОГО МНОГОЧЛЕНА АВТОКОРРЕЛЯЦИИ Q-АРНЫХ СЛОВ
© 2011 г. Н. Гогин, А. Мюлляри Университет г. Турку, Финляндия 20014 Turun yliopisto, Finland
E-mail: alemio@utu.fi Поступила в редакцию 10.10.2010 г.
В статье получена явная формула для весового многочлена автокорреляции q-арных слов, позволяющая легко вычислять ее весовые коэффициенты стандартными алгоритмическими средствами компьютерной алгебры.
1. ВВЕДЕНИЕ
Основной целью настоящей работы, как сказано в ее названии, является получение компактной и удобной для программирования формулы для весового многочлена автокорреляции q-арных слов, при развертывании которой по степеням неизвестных, набор коэффициентов при этих неизвестных совпадает с весовым спектром указанной автокорреляции. Задача изучения такой автокорреляции возникает при исследовании перекрытия строк (см., например, [1]), а в качестве примера ее практического применения можно привести задачу о времени ожидания появления данного слова в игре Penney Ante (по-русски также называемой "Орлянка"), описание которой можно найти, например, в [2, 3]. Хотя игра выглядит простой, результаты ее изучения (после соответствующих видоизменений) находят применения в реальных ситуациях, например, при игре на бирже, где прежде чем сделать "ход" (купить, продать акции) игроки ждут появления некой последовательности скачков цен интересующих их акций [4]).
Современые системы компьютерной алгебры, такие, как Mathematica или Maple, предоставляют хорошие возможности для символьных и численных вычислений, а также хорошие графические возможности для иллюстраций их результатов. Применение этих систем позволяет также достаточно быстро проверять гипотезы, появляющиеся в ходе ис-
следования. В данной работе мы использовали МаЬНвтаЫса 7.
2. ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ
В данной работе мы рассматриваем слова и = £0^1 •••£п-1 длины п, п > 2 над алфавитом, являющимся кольцом вычетов Zq = {0,1, • • •, д — 1} по модулю д > 2, которые мы будем отождествлять с элементами абелевой группы Уп = Zq ф ■ ■ ■ ф Zq (п слагаемых) и поэтому использовать для них также и векторную запись и = (е0,е1, • • • , £п-1), £к € Zq• Кроме того, каждому такому вектору ставится во взаимно-однозначное соответствие натуральное число, обозначаемое нами также через и (совпадение обозначений не приводит здесь к путанице) по формуле:
п- 1
и = 1] £к дп-1-к = (£о£1 • • • £п-1),, (2.1) к=0
где £к € Zq рассматриваются здесь как разряды д-ичного разложения числа и, и, таким образом, ясно, что 0 < и < дп — 1 Например, при этих соглашениях для д = 6, п = 7, и = (0, 0,1, 0, 2, 3, 4) справедливы равенства:
и = (0, 0,1, 0, 2, 3, 4) = (10234)б = 0 ■ 66 + 0 ■ 65 + +1 ■ 64 + 0 ■ 63 + 2 ■ 62 + 3 ■ 61 + 4 ■ 60 = 1390^
Далее, следуя [1], мы будем говорить, что вектор (слово) и = (е0, £1, • • •, £п-1) перекрывает
вектор v = (по, Пъ • • •, Пп-i) со сдвигом к, 0 < к < n—1 (или кратко: "u к-перекрывает v"), если (£к ,£fc+i, ...,en-i) = (по, П1, • • • ,nn-k-i) и будем записывать это отношение в виде u =к = v^ Ясно, что u =о= v означает обычное равенство u = v^ Снова следуя [1], мы называем строковой корреляцией (string correlation) пары векторов (слов) u и v число
n-1
c (u,v) = ^ qn-1-k||u =к = v||, k=о
где ||u =к = v|| равно 1 (соотв. 0), если отношение u =к = v истинно (соотв. ложно).
В дальнейшем нас будет интересовать только автокорреляция c(u, u) (в той же статье [1] показано, что c(u, u) пропорционально так называемому "времени ожидания" появления слова u в игре Penney Ante с q-гранной костью), которую мы будем обозначать для краткости т(u) :
n-1
т(u) = c(u,u) = J^ 5п-1-к||u =к = u|| (2.2) к=о
n-1
„п-1 I \ ^ „n-1-кц,,, „,11
= q +2q ||u =к = u| к= 1
Таким образом, т (u) представляет собой положительную целозначную функцию на Vn, для которой выполняются очевидные соотношения т(0) = и qn-1 < т(u) < ^ •
Однако, следует сразу же отметить, что в целом поведение функции т (u), 0 < u < qn — 1 весьма нерегулярно (см. рис. 1 для q = 2, n = 8), поэтому все вопросы, связанные с конкретными деталями ее поведения оказываются как правило весьма сложными. (См. по этому поводу, например, статью [5].)
Таким образом, в силу указанной нерегулярности возникает естественная идея рассматривать подходящие усреднения значений этой функции с целью найти некоторые "стабильные" характеристики ее поведения. Настоящая работа посвящена одной из возможных реализаций такого усреднения, а именно, вычислению коэффициентов весового спектра Хэмминга значений этой функции.
Здесь необходимо отметить, что аналогичная двумерная задача о вычислении весового спектра функции c(u, v) оказывается алгоритмически проще: в этом случае, как показано нами
в статьях [9] и [10], построение матриц весовых коэффициентов может быть осуществлено с помощью простого рекурсивного алгоритма по размерности матрицы.
Но для функции т(и) (т.е. в "одномерном случае") явные выражения ее весовых коэффициентов оказываются весьма сложными (см. Предложение 1, формула (3.7)) и неудобными для программирования, поскольку вряд ли для них возможна какая-либо простая рекурсия. Поэтому в разделе 4 настоящей работы, мы как это обычно делается в алгебраической теории кодирования, находим в явном виде производящий многочлен (называемый также "весовым многочленом", см. [6]) для этих коэффициентов, что, как было сказано выше, и составляет основную цель настоящей статьи. Этот результат, представленный в Предложении 4, насколько нам известно, является новым, и как видно из полученной нами формулы (5.9), нахождение коэффициентов этого многочлена представляет собой весьма простую алгоритмическую задачу в любой системе программирования, содержащей стандартные функции компьютерной полиномиальной алгебры.
Основным инструментом наших исследований служит аппарат, стандартно применяемый в алгебраической теории кодирования, а именно, преобразование Фурье на конечных абелевых группах, которое используется нами в разделе 3, и формула Мак-Вильямс для весовых многочленов взаимно дуальных кодов, используемая нами в разделе 4.
3. УСРЕДНЕНИЕ ПО ВЕСУ ХЭММИНГА
Вес Хэмминга -ш£(и) вектора и = (во, £ъ ..., еп_1) € Уп определяется здесь обычным образом (см. [6]):
■ш£(и) = количество ненулевых компонент в и. Ясно, что 0 < -ш£(и) < п для любого и € Уп и что
количество векторов веса m в Vn = (q — 1)r
n
шу (3.1)
Как обычно, весовой спектр функции т определяется нами
Ат(т) = т(и), 0 < т < п (3.2)
Рис. 1. График функции т(и) для д =1, п =
(см. [6]) и нашей ближайшей целью будет сейчас явное их выражение через д, п и т- Ясно, что А0(т) = т(0) = ||-~11, поэтому далее мы полагаем т = 0^
Прежде всего здесь следует указать на следующий легко доказываемый факт (см. [5], стр. 21):
Лемма 1. 1. ||и =к = и|| = 1 для некоторого 1 < к < п — 1 т. и т.т., когда слово и имеет следующий вид:
и = (а|а|а| • • • |а|г(а)),
(3.3)
#{и € Уп, ||и =к = и|| = 1} = дп
(3.4)
Доказательство.
1. Достаточность условия (3.3) очевидна. Необходимость этого условия также очевидна для случая к > п — к, а для случая к < п — к надо просто заметить, что здесь обязательно и = (а|и) = (и1|ад1) для некоторых а, € Ук, и1 € Уп-к и доказательство получается итерацией этого процесса.
2. Формула (3.4) очевидно следует из первой части леммы.
Переходя от векторов (слов) и € Уп и а € Ук к кодирующим их целым числам (см. выше, ф. (2.1)), мы сразу же получаем из (3.3)
Следствие 1. ||и =к = и|| = 1 для некоторого 1 < к < п — 1 т. и т.т., когда
и=
-1
д
гк-п
(3.5)
где 0 < а < дк — 1 и г = |~п~| есть верхняя целая
где а € Ук, и ¿(а) есть некоторый начальный отрезок (префикс) слова а (в статье [5] всякое слово а, для которого выполняется (3.3), называется периодом слова и^ 2.
часть числа ^ •
Замечание 1. Алгоритм, вычисляющий т(и) непосредственно по формуле (2.2) с использованием формулы (3.5) реализован авторами статьи в Mathematica 7 в виде программы ConwayAutocorrfrm2zwzd[g_, п_]^ Результат ее работы при д = 2, п = 8 иллюстрируется на рис. 1.
Если теперь положить в формуле (3.3) а = ¿(а) и а = ав, то ее можно переписать так:
и = (а в а в • • • а в а),
(3.6)
где а = (а в) € Ук, а € Уто<(п,к), в € Ук-то<1(п,к) = УmЫ(n,k), причем а входит в запись (3.6) г = [к] раз, а в входит в нее г = |_п] раз. (Здесь то^(п, к) означает остаток от деления п на к, а то^(п, к) = к — то^(п, к) - дополнение этого остатка до к^)
Теперь мы можем перейти к нахождению явного вида коэффициентов весового спектра Ат(т) для 1 < т < п :
|
а
Предложение 1.
Ат(т)= ^^ - 1)
п
т
+
(3.7)
+
п_ 1
Е
Г=1
то^(п,Г)=0
9
,п_1_Г
Е «
*=г ? 1
- 1)* X
/той(п, к)\ /той(п, кУ \ т — 2Г / — т
+
Е
«п-1_ 5|
х ?
— 1) Т
¿>1
( п/й \т/й
1 < т < п.
Доказательство. Согласно (2.2) и (3.2) имеем:
Ат(т) = £ т (и) = 9^(9 — 1)т( т)
ш4(и)=т
п_ 1
+ Е Е9П-1_' Ни =т = и»
ш4(и)=т Г=1
= 9п-1(9 — 1)г
п
т
+
п_ 1
+ £ *п_1_Г Е
|и =Г = и|
Г=1
ш4(и)=т
Внутреннюю сумму во втором из равенств в (3.8) (при фиксированном к > 1) ищем, используя представление (3.6):
Е
ш4(и)=т
|и =Г = и||
Е
1, (3.8)
а, в
ж,у,гж + гу = т
должно быть целым числом, и поэтому в этом случае (3.8) упрощается следующим образом:
Е
ш4(и)=т
|и =Г = и|| =
Е
1 = (3.9)
веУкМв)=2
тк / к
— 1) п тГ
(Напомним, что если тт не является целым числом, то (?к) =0 по определению.)
п
Записывая теперь п = йк, й > 1, тт = т и подставляя это в (3.9), получаем
Е
ш4(и)=т
1и =т=ин=(9—1) м т^т
т
= ( 9 — 1) 1
1) ? п/^ ^ = п> 1
\т/й/' к '
поэтому формулу (3.8) можно теперь записать так:
Ат(т) = 9п-1(9 — 1)т( п ) +(3.10)
т
+ Е
й|дсй(п, т) й > 1
+ Е 9
1 < к < п — 1 той(п, к) = 0
9п-1_П(
—1)т (т/й)+
,п_ 1_Г
£ Ни =г = и|
ш4(и)=т
Переходим к случаю (В): той(п,к) = 0. В этом случае г = г +1 и равенство (3.8) принимает вид:
£ Ни =г = и||
ш4(и)=т
где а € , в € УГ_той(п,Г) = УтОЙ^,^
х = -ш£(а), у = -ш£(в), т.е. эта сумма равна числу таких векторов а и в, веса ж и у которых являются решениями диофантова уравнения т = жг + уг, где г = |~п~| , Г = |_п1 , т
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.