ИСПОЛЬЗОВАНИЕ ПОРОЖДАЮЩИХ ПОЛИНОМОВ M-ПОСЛЕДОВАТЕЛЬНОСТЕЙ ПРИ ПОСТРОЕНИИ ПСЕВДОСЛУЧАЙНЫХ КОДОВЫХ ШКАЛ
Использование порождающих полиномов M-последовательностей
49
УДК 621.3.085
И. Д. ЗАХАРОВ, А. А. ОЖИГАНОВ
ИСПОЛЬЗОВАНИЕ ПОРОЖДАЮЩИХ ПОЛИНОМОВ M-ПОСЛЕДОВАТЕЛЬНОСТЕЙ
ПРИ ПОСТРОЕНИИ ПСЕВДОСЛУЧАЙНЫХ КОДОВЫХ ШКАЛ
Рассмотрен метод построения порождающих полиномов М-последовательностей с одинаковым периодом на основе одного заданного полинома. В основу метода положено использование свойств децимации М-последовательности и алгоритма Берлекемпа — Мэсси. Предложенный метод пояснен примером.
Ключевые слова: порождающий полином, М-последовательность, децимация, псевдослучайная кодовая шкала.
Введение. Среди приборов, используемых в устройствах вычислительной техники и
систем управления, особое место занимают преобразователи угловых и линейных перемеще-
ний (ПП), построенные по методу параллельного считывания. Основным элементом таких
преобразователей является кодовая шкала (КШ). Классический подход к построению ПП ба-
зируется на использовании КШ с числом информационных кодовых дорожек, равным, как
правило, разрядности преобразователей.
В работах [1—3] предложен новый тип более простых в реализации однодорожечных
псевдослучайных кодовых шкал (ПСКШ). Для формирования структуры информационной
кодовой дорожки таких шкал используются псевдослучайные двоичные последовательности
максимального периода (М-последовательности), причем для построения n-разрядной ПСКШ
могут быть использованы различные М-последовательности с одинаковым периодом. Таким
образом, n-разрядная ПСКШ может иметь множество реализаций. В свою очередь, в основу
построения М-последовательностей положены порождающие полиномы, в качестве которых
выступают примитивные полиномы с коэффициентами поля Галуа GF(2). Число таких поли-
номов зависит от их степени и вычисляется на основе функции Эйлера.
В настоящее время при разработке преобразователей перемещения на основе ПСКШ
применяются системы автоматизированного проектирования (САПР ПСКШ) [4], что позво-
ляет с использованием эффективного алгоритма вычислять необходимые порождающие по-
линомы во избежание сохранения в памяти ЭВМ всей базы данных о полиномах.
В настоящей работе приводятся необходимые для понимания сути статьи базовые по-
ложения теории М-последовательностей, основные сведения о принципах построения ПСКШ
для преобразователей перемещений, а также рассматривается метод синтеза порождающих
полиномов М-последовательностей с заданным периодом, предназначенный для использова-
ния в САПР ПСКШ.
Теоретические основы построения псевдослучайных кодовых шкал. ПСКШ имеют
всего одну информационную кодовую дорожку, выполненную в соответствии с символами
{aj}=а0, а1, ..., аM–1 М-последовательности, и n считывающих элементов (СЭ), размещенных вдоль дорожки. Наличие считывающих элементов позволяет получить при полном перемещении шкалы М=2n–1 различных n-разрядных кодовых комбинаций.
Для генерации М-последовательности с периодом М=2n–1 используется примитивный
полином h(x) степени п с коэффициентами GF(2), т. е.
n
∑h(x) = hi xi , i=0
(1)
где h0=hn=1, а hi ={0,1} при 0 < i < n.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 6
50 И. Д. Захаров, А. А. Ожиганов
Примитивные полиномы существуют для всех n > 1. В табл. 1 приведены полиномы h(x)
для n =1…16, которые имеют минимальное число ненулевых коэффициентов hi и могут быть использованы для генерации соответствующих М-последовательностей [5].
n h(x) 1 x +1
2 x2 + x +1 3 x3 + x +1 4 x4 + x +1 5 x5 + x2 +1 6 x6 + x +1 7 x7 + x3 +1 8 x8 + x4 + x3 + x2 +1
М=2n–1
n
Таблица 1 h(x) М=2n–1
1 9 x9 + x4 +1
511
3 10 x10 + x3 + 1
1023
7 11 x11 + x2 + 1
2047
15
12 x12 + x6 + x4 + x + 1
4095
31
13 x13 + x4 + x3 + x +1
8191
63
14 x14 + x10 + x6 + x + 1
16383
127 15 x15 + x +1
32787
255
16 x16 + x12 + x3 + x +1
65535
Известно [6], что для конкретного значения n существует точно
( )Φ М = 2n −1
N= n
(2)
различных полиномов h(x), являющихся примитивными. Функция Ф(М), называемая функци-
ей Эйлера, представляет собой количество положительных целых чисел, меньших или рав-
ных М и взаимно простых с М. Так как функция Ф(М) с увеличением n очень быстро растет,
то число полиномов степени n, порождающих последовательности с максимальным перио-
дом, с ростом n также быстро увеличивается. В табл. 2 приведены расчетные значения N для
n =2…16.
Таблица 2
nNn
N
2 1 10 60
3
2 11
176
4
2 12
144
5
6 13
630
6
6 14
756
7 18 15 1800
8 16 16 2048
9 48
Так, для n=10 число примитивных полиномов равно 60, а для n=16 — уже 2048. Следо-
вательно, на основе порождающих полиномов 10-й степени можно получить 60 различных
М-последовательностей, а при использовании порождающих полиномов 16-й степени —
2048.
Символы аn+j М-последовательности удовлетворяют рекуррентному выражению
n−1
an+ j
=
⊕
i=0
ai
+
j
hi
,
j
= 0, 1, ... ,
(3)
где знак ⊕ — суммирование по модулю два, а индексы при символах М-последовательности
берутся по модулю M; начальные значения символов а0, а1, ..., аn–1 М-последовательности мо-
гут выбираться произвольно, за исключением нулевой комбинации.
Известно, что М-последовательности относятся к классу циклических кодов и могут
задаваться с помощью полинома g(x) = (xM + 1) h(x) . Для каждой М-последовательности с
периодом M существует ровно M различных циклических сдвигов, которые могут быть полу-
чены путем умножения полинома g ( x) на x j , где j = 0, 1, ..., M −1.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 6
Использование порождающих полиномов M-последовательностей
51
Поскольку ПСКШ строятся в соответствии с символами М-последовательности, можно путем циклических сдвигов определить порядок размещения на шкале n считывающих эле-
ментов, т.е. m-му СЭ, m = 1, 2, ..., n , ставится в соответствие jm-й циклический сдвиг x jm g ( x)
М-последовательности. Тогда полином, определяющий порядок размещения n СЭ на шкале, имеет вид
n
∑r(x) = x jm , jm ∈{0, 1, ..., M −1} . m=1
(4)
Приняв j1 = 0 , согласно полиному (4) получим положения 2-го, 3-го, ..., n-го СЭ, сме-
щенные относительно 1-го СЭ на j2 , j3, ..., jn позиций соответственно. Размещение считывающих элементов в соответствии с полиномом (4) должно обеспечи-
вать получение при полном перемещении шкалы М различных n-разрядных кодовых комбинаций. В общем виде задача размещения СЭ на ПСКШ решена в работе [7].
Метод синтеза порождающих полиномов М-последовательностей. В основу метода положено использование свойств децимации М-последовательности и алгоритма Берлекемпа — Мэсси.
{ }Согласно работе [8] децимацией М-последовательности a j по индексу qs ,
s = 2, 2n − 2, называется выборка qs-х элементов данной М-последовательности. Если период M = 2n–1 исходной М-последовательности и индекс децимации qs взаимно просты, т.е. НОД(M, qs)=1, децимация называется собственной или нормальной. В дальнейшем под децимацией будем подразумевать только собственную (или нормальную) децимацию, в результате которой получается М-последовательность с тем же периодом, что и исходная М-последо-
{ }вательность. Децимацию {aj} по индексу qs обозначим как a j qs , а полученную в результате
децимации М-последовательность — как {bj}. Таким образом, можно записать
{bj } = {a j}qs .
(5)
Алгоритм генерации примитивных полиномов заданной степени в общих чертах рассмотрен в работе [9]. Однако данный алгоритм оставляет открытым вопрос о нахождении всего множества порождающих полиномов М-последовательностей с заданным периодом и не оптимизирован для использования в САПР ПСКШ.
Рассмотрим метод синтеза порождающих полиномов М-последовательностей, свободный от указанного недостатка. Реализация метода предусматривает выполнение следующих шагов.
1. Из табл. 1 выбирается примитивный полином вида (1) определенной степени n. 2. На основе полинома (1) строится рекуррентное выражение (3). 3. Посредством рекуррентного выражения (3) генерируются символы {aj} М- последовательности с периодом М = 2n – 1. 4. В соответствии с выражением (2) определяется число примитивных полиномов h(x) степени n.
5. Осуществляется поиск значений индексов децимации ql , l = 1, N −1 , {ql } ⊂ {qs},
позволяющих сформировать все нормальные децимации М-последовательности {a j } , на
основе которых могут быть получены N–1 различных М-последовательностей {bj } с
периодом М.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 6
52 И. Д. Захаров, А. А. Ожиганов
6. Производится нормальная децимация М-последовательности {aj} по индексу ql. Результатом такой децимации является Мl-последовательность (5) с периодом М.
7. Далее, с использованием алгоритма Берлекемпа — Мэсси и предварительной выборки 2n символов из полученной Мl -последовательности определяется полином hl(x), который также будет примитивным.
8. Шаги 6 и 7 повторяются для всех нормальных децимаций, найденных на шаге 5. Результатом применения метода являются N–1 порождающих полиномов степени n. Эффективность разработанного метода в основном определяется результатом выполнения шага 5. Для оптимизации поиска значений индексов децимации рассмотрим алгоритм, в
котором: {qs} — множество всех значений индексов децимации; {qk } ⊂ {qs } — множество
нечетных значений индексов децимации; REG[n] — n-разрядный двоичный циклический регистр сдвига; REGz, z = 0,..., n −1, — значение z-го разряда регистра; SHIFT[p] — p-разрядный
двоичный счетчик числа сдвигов, где p=[lb n]; Ck — флаг децимации с индексом qk, причем
Сk
=
⎧0, ⎪ ⎨
если децимация с индексом qk не позволяет получить необходимую М-последовательность;
⎩⎪1, в противном случае.
Алгоритм содержит следующие шаги:
1. qk := 1; Ck := 1 , k = 2e +1, e = 1, 2n−1 −1 . 2. qk := qk + 2 . 3. Если qk ≥ 2n −1, переход к шагу 13. 4. Если Ck = 0 , переход к шагу 2. 5. Запись qk в REG[n]; обнуление счетчика SHIFT [p]. 6. Если SHIFT [p]≥n–1, переход к шагу 10. 7. Циклический сдвиг регистра REG[n] на один разряд влево. SHIFT [p]:= SHIFT [p]+1. 8. Если REG0=1, k := REG[n], Ck := 0. 9. Возврат к шагу 6.
( )10. Если НОД qk , 2n −1 =1, переход к шагу 12.
11. Ck := 0 , переход к шагу 2. 12. Сохранение полученного значения qk в массив результатов. Переход к шагу 2. 13. Вывод массива результатов. Таким образом, используя рассмотренный алгоритм, можно найти все значения индексов, позволяющие сформировать нормальные децимации М-последовательности {a j }ql , l = 1, N − 1, на основе которых могут быть получены N–1 различных М-последо-
вательностей {bj} с периодом М.
Пример. Рассмотрим метод синтеза порождающих полиномов М-последовательности на примере, ограничившись получением всех полиномов 5-й степени.
1. Из табл. 1 выбирается примитивный полином h ( x) = x5 + x2 + 1.
2. На основе выбранного полинома строится рекуррентное выражение a5+ j = a2+ j ⊕ a j . 3. Посредством полученного рекуррентного выражения генерируются символы
{ }a j = (0, 0, 0, 0,1, 0, 0,1,0,1,1, 0, 0,1,1,1,1,1, 0, 0, 0,1,1, 0,1,1,1, 0,1, 0,1) М-последовательности с
периодом М = 25 – 1=31.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 6
Использование порождающих полиномов M-последовательностей
53
4. В соответствии с выражением (2) вычисляется количество примитивных полиномов h(x) степени 5, т.е.
( ) ( )Φ
N=
М = 2n −1 n
Φ =
М = 25 −1 5
=
Φ
(31)
5
=
30 5
=
6.
5. Осуществляется поиск значений индексов децимации ql, позволяющих сформировать нормальные децимации М-последовательности {a j }ql ,l = 1,5 . В соответствии с приведенным
)выше алгоритмом используются только нечетные значения индекса qk ∈ ⎣⎢⎡3, 25 −1 . Каждое
значение qk заносится в регистр REG[5] и вычисляются все возможные значения, получаемые при его циклическом сдвиге влево. Например, при занесении в REG[5] значения q1=3 получается следующий результат:
REG[5] ← 3 ⇒ REG[5] : 0 0 0 11;
cдвиг 1: REG[5]: 0 0 11 0 (6);
cдвиг 2 : REG[5] : 0 11 0 0 (12);
cдвиг 3 : REG[5] :11 0 0 0 (24);
cдвиг 4 : REG[5] :1 0 0 0 1 (17).
{ } { }С учетом того [8], что a j 2d qs = a j (2d qs )mod M , полученные значения индексов деци-
мации q1(0)=3, q1(1)=6, q1(2)=12, q1(3)=24 и q1(4)=17 (где значение (*) определяет число сдвигов содержимого регистра) позволяют сформировать одинаковые (с точностью до циклического сдвига) M-последовательности. Следовательно, для синтеза необходимой M-последовательности достаточно использовать один из пяти индексов децимации, например q1(0)=3.
Аналогичным образом вычисляем:
q2 (0) = 5 ⇒ q2 (1) = 10, q2 (2) = 20, q2 (3) = 9, q2 (4) = 18;
q3 (0) = 7 ⇒ q3 (1) = 14, q3 (2) = 28, q3 (3) = 25, q3 (4) = 19;
q4 (0) = 11 ⇒ q4 (1) = 22, q4 (2) = 21, q4 (3) = 13, q4 (4) = 26;
q5 (0) = 15 ⇒ q5 (1) = 30, q5 (2) = 29, q5 (3) = 27, q5 (4) = 23.
Далее осуществляется проверка, являются ли полученные децимации ql , l =1, ..., 5, нормальными. Для этого определяется наибольший общий делитель значения каждого из полученных индексов ql и периода М М-последовательности, т.е.
НОД(3, 31)=1; НОД(5, 31)=1; НОД(7, 31)=1; НОД(11, 31)=1; НОД(15, 31)=1.
Данный результат свидетельствует о нахождении пяти индексов децимации,
использование которых дает возможность получения пяти различных М-
последовательностей.
6. Производятся нормальные децимации полученной на шаге 3 М-последовательности
{aj} по индексам ql , l =1, ..., 5 . Например, первые 2n=10 символов М1-последовательности,
{ }полученные в результате децимации по индексу 3, равны
aj
3 10
= (0,0,0,0,1,1,0,0,1,0) .
7. Далее, составляется система линейных алгебраических уравнений, решаемая с
использованием алгоритма Берлекемпа — Мэсси, т.е.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 6
54 И. Д. Захаров, А. А. Ожиганов
a5 = a4h4 ⊕ a3h3 ⊕ a2h2 ⊕ a1h1 ⊕ a0h0 ; ⎫ ⎧1 = 1⋅ h4 ⊕ 0 ⋅ h3 ⊕ 0 ⋅ h2 ⊕ 0 ⋅ h1 ⊕ 0 ⋅ h0 ;
a6 a7
= =
a5 h4 a6 h4
⊕ a4h3 ⊕ a5h3
⊕ a3h2 ⊕ a4h2
⊕ a2h1 ⊕ a3h1
⊕ ⊕
aa12hh00;;⎪⎬⎪⎪
=
⎪⎪⎪⎨00
= 1⋅ h4 ⊕1⋅ h3 ⊕ 0 ⋅ h2 = 0 ⋅ h4 ⊕1⋅ h3 ⊕1⋅ h2
⊕ 0 ⋅ h1 ⊕ 0 ⋅ h1
⊕ 0 ⋅ h0 ; ⊕ 0 ⋅ h0 ; .
a8
=
a7 h4
⊕ a6h3
⊕
a5h2
⊕
a4 h1
⊕
a3h0
;
⎪ ⎪
⎪⎪1 = 0 ⋅ h4 ⊕ 0 ⋅ h3 ⊕1⋅ h2 ⊕1⋅ h1 ⊕ 0 ⋅ h0 ;
a9 = a8h4 ⊕ a7h3 ⊕ a6h2 ⊕ a5h1 ⊕ a4h0 ⎭⎪ ⎪⎩0 = 1⋅ h4 ⊕ 0 ⋅ h3 ⊕ 0 ⋅ h2 ⊕1⋅ h1 ⊕1⋅ h0 .
В результате получаем значения h0 = 1; h1 = 0; h2 = 1; h3 = 1; h4 = 1; h5 = 1 , по которым
находим искомый порождающий полином h1(x) = h5 x5 + h4 x4 + h3x3 + h2 x2 + h1x1 + h0 = 1⋅ x5 + 1⋅ x4 + 1⋅ x3 + 1⋅ x2 + 0 ⋅ x1 + 1⋅ x0 =
= x5 + x4 + x3 + x2 + 1.
8. Шаги 6 и 7 повторяются для остальных нормальных децимаций, найденных на
шаге 5; в результате получаем еще четыре порождающих полинома 5-й степени.
Все порождающие полиномы 5-й степени, соответствующие М-последовательности и
значения индексов децимации приведены в табл. 3.
Таблица 3
Индекс децимации q Порождающий полином h(x)
M-последовательность
0
h ( x) = x5 + x2 +1
0000100101100111110001101110101
3
h1 ( x) = x5 + x4 + x3 + x2 +1
0000110010011111011100010101101
5
h2 ( x) = x5 + x4 + x2 + x +1
0000111001101111101000100101011
7
h3 ( x) = x5 + x3 + x2 + x +1
0000101101010001110111110010011
11
h4 ( x) = x5 + x4 + x3 + x +1
0000110101001000101111101100111
15
h5 ( x) = x5 + x3 +1
0000101011101100011111001101001
Отметим, что любая из приведенных в табл. 3 М-последовательностей пригодна для построения 5-разрядной ПСКШ. Например, линейная развертка круговой ПСКШ, выполненной с использованием М-последовательности, полученной на основе порождающего полинома
h3 ( x) = x5 + x3 + x2 + x + 1 , приведена на рисунке. Размещение на шкале пяти считывающих
элементов задано в соответствии с полиномом r(x) = 1 + x2 + x4 + x6 + x8 .
Последовательно с использованием считывающих элементов фиксируя кодовую комби-
нацию при перемещении шкалы на один квант, например справа налево, получаем 31 различ-
ную 5-разрядную кодовую комбинацию. Эти кодовые комбинации, соответствующие 31 раз-
личному угловому положению ПСКШ, приведены в табл. 4.
Таблица 4
Кодовая комбинация
Кодовая комбинация
Номер сдвига ПСКШ
Двоичный псевдослучай-
ный код
Десятичный эквивалент
Номер сдвига ПСКШ
Двоичный псевдослучай-
ный код
Десятичный эквивалент
0 00110
6
16 10110
22
1 00011
3
17 11110
30
2 01100 12
18 01101
13
3 00111
7
19 11100
28
4 11000 24
20 11010
26
5 01110 14
21 11001
25
6 10000 16
22 10101
21
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 6
Использование порождающих полиномов M-последовательностей
55
Продолжение табл. 4
Кодовая комбинация
Кодовая комбинация
Номер сдвига ПСКШ
Двоичный псевдослучай-
ный код
Десятичный эквивалент
Номер сдвига ПСКШ
Двоичный псевдослучай-
ный код
Десятичный эквивалент
7 11101 29
23 10010
18
8 00001
1
24 01010
10
9 11011 27
25 00100
4
10 00010
2
26 10100
20
11 10111
23
27 01001
9
12 00101
5
28 01000
8
13 01111
15
29 10011
19
14 01011
11
30 10001
17
15 11111
31
Заключение. Предложенный в настоящей статье метод построения порождающих по-
линомов М-последовательностей наиболее целесообразно использовать в системах автомати-
зированного проектирования псевдослучайных кодовых шкал для преобразователей переме-
щений.
СПИСОК ЛИТЕРАТУРЫ
1. Ожиганов А. А. Псевдослучайные кодовые шкалы // Изв. вузов СССР. Пpибоpостроение. 1987. Т. 30, № 2. С. 40—43.
2. Ожиганов А. А. Псевдослучайные кодовые шкалы для преобразователей линейных перемещений // Изв. вузов. Приборостроение. 1995. Т. 38, № 11—12. С. 37—39.
3. Ожиганов А. А., Чжипэн Жуань. Использование псевдослучайных последовательностей при построении кодовых шкал для преобразователей линейных перемещений // Там же. 2008. Т. 51, № 7. С. 28—33.
4. Ожиганов А. А., Коробейников А. Г., Климанов В. А. Структура системы автоматизированного проектирования рекурсивных кодовых шкал // Науч.-техн. вестн. СПбГУ ИТМО. 2006. Вып. 32. C. 237—245.
5. Макуильямс Ф. Д., Слоан Н. Д. Псевдослучайные последовательности и таблицы // ТИИЭР. 1976. Т. 64, № 12. С. 80—95.
6. Муттер В. М. Основы помехоустойчивой телепередачи информации. Л.: Энергоатомиздат, 1990. 288 с.
7. Ожиганов А. А. Алгоритм размещения считывающих элементов на псевдослучайной кодовой шкале // Изв. вузов. Приборостроение. 1994. Т. 37, № 2. С. 22—27.
8. Сарвате Д. В., Персли М. Б. Взаимно-корреляционные свойства псевдослучайных и родственных последовательностей // ТИИЭР. 1980. Т. 68, № 5. С. 59—95.
9. Борисенко Н. П., Гусаров А. В., Кривонос А. П. О возможности генерации примитивных полиномов заданной степени и быстрого вычисления сдвига выходной последовательности РСЛОС на заданное число тактов // Сб. трудов XII Междунар. науч. конф. „Информатизация и информационная безопасность правоохранительных систем“. М., 2003. С. 334—339.
Сведения об авторах
Илья Дмитриевич Захаров
— аспирант; Санкт-Петербургский государственный университет ин-
формационных технологий, механики и оптики, кафедра вычисли-
тельной техники; E-mail: zakharov_ilya@hotmail.com
Александр Аркадьевич Ожиганов — д-р техн. наук, профессор; Санкт-Петербургский государственный
университет информационных технологий, механики и оптики, ка-
федра вычислительной техники; E-mail: ojiganov@mail.ifmo.ru
Рекомендована кафедрой вычислительной техники
Поступила в редакцию 18.01.11 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 6
49
УДК 621.3.085
И. Д. ЗАХАРОВ, А. А. ОЖИГАНОВ
ИСПОЛЬЗОВАНИЕ ПОРОЖДАЮЩИХ ПОЛИНОМОВ M-ПОСЛЕДОВАТЕЛЬНОСТЕЙ
ПРИ ПОСТРОЕНИИ ПСЕВДОСЛУЧАЙНЫХ КОДОВЫХ ШКАЛ
Рассмотрен метод построения порождающих полиномов М-последовательностей с одинаковым периодом на основе одного заданного полинома. В основу метода положено использование свойств децимации М-последовательности и алгоритма Берлекемпа — Мэсси. Предложенный метод пояснен примером.
Ключевые слова: порождающий полином, М-последовательность, децимация, псевдослучайная кодовая шкала.
Введение. Среди приборов, используемых в устройствах вычислительной техники и
систем управления, особое место занимают преобразователи угловых и линейных перемеще-
ний (ПП), построенные по методу параллельного считывания. Основным элементом таких
преобразователей является кодовая шкала (КШ). Классический подход к построению ПП ба-
зируется на использовании КШ с числом информационных кодовых дорожек, равным, как
правило, разрядности преобразователей.
В работах [1—3] предложен новый тип более простых в реализации однодорожечных
псевдослучайных кодовых шкал (ПСКШ). Для формирования структуры информационной
кодовой дорожки таких шкал используются псевдослучайные двоичные последовательности
максимального периода (М-последовательности), причем для построения n-разрядной ПСКШ
могут быть использованы различные М-последовательности с одинаковым периодом. Таким
образом, n-разрядная ПСКШ может иметь множество реализаций. В свою очередь, в основу
построения М-последовательностей положены порождающие полиномы, в качестве которых
выступают примитивные полиномы с коэффициентами поля Галуа GF(2). Число таких поли-
номов зависит от их степени и вычисляется на основе функции Эйлера.
В настоящее время при разработке преобразователей перемещения на основе ПСКШ
применяются системы автоматизированного проектирования (САПР ПСКШ) [4], что позво-
ляет с использованием эффективного алгоритма вычислять необходимые порождающие по-
линомы во избежание сохранения в памяти ЭВМ всей базы данных о полиномах.
В настоящей работе приводятся необходимые для понимания сути статьи базовые по-
ложения теории М-последовательностей, основные сведения о принципах построения ПСКШ
для преобразователей перемещений, а также рассматривается метод синтеза порождающих
полиномов М-последовательностей с заданным периодом, предназначенный для использова-
ния в САПР ПСКШ.
Теоретические основы построения псевдослучайных кодовых шкал. ПСКШ имеют
всего одну информационную кодовую дорожку, выполненную в соответствии с символами
{aj}=а0, а1, ..., аM–1 М-последовательности, и n считывающих элементов (СЭ), размещенных вдоль дорожки. Наличие считывающих элементов позволяет получить при полном перемещении шкалы М=2n–1 различных n-разрядных кодовых комбинаций.
Для генерации М-последовательности с периодом М=2n–1 используется примитивный
полином h(x) степени п с коэффициентами GF(2), т. е.
n
∑h(x) = hi xi , i=0
(1)
где h0=hn=1, а hi ={0,1} при 0 < i < n.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 6
50 И. Д. Захаров, А. А. Ожиганов
Примитивные полиномы существуют для всех n > 1. В табл. 1 приведены полиномы h(x)
для n =1…16, которые имеют минимальное число ненулевых коэффициентов hi и могут быть использованы для генерации соответствующих М-последовательностей [5].
n h(x) 1 x +1
2 x2 + x +1 3 x3 + x +1 4 x4 + x +1 5 x5 + x2 +1 6 x6 + x +1 7 x7 + x3 +1 8 x8 + x4 + x3 + x2 +1
М=2n–1
n
Таблица 1 h(x) М=2n–1
1 9 x9 + x4 +1
511
3 10 x10 + x3 + 1
1023
7 11 x11 + x2 + 1
2047
15
12 x12 + x6 + x4 + x + 1
4095
31
13 x13 + x4 + x3 + x +1
8191
63
14 x14 + x10 + x6 + x + 1
16383
127 15 x15 + x +1
32787
255
16 x16 + x12 + x3 + x +1
65535
Известно [6], что для конкретного значения n существует точно
( )Φ М = 2n −1
N= n
(2)
различных полиномов h(x), являющихся примитивными. Функция Ф(М), называемая функци-
ей Эйлера, представляет собой количество положительных целых чисел, меньших или рав-
ных М и взаимно простых с М. Так как функция Ф(М) с увеличением n очень быстро растет,
то число полиномов степени n, порождающих последовательности с максимальным перио-
дом, с ростом n также быстро увеличивается. В табл. 2 приведены расчетные значения N для
n =2…16.
Таблица 2
nNn
N
2 1 10 60
3
2 11
176
4
2 12
144
5
6 13
630
6
6 14
756
7 18 15 1800
8 16 16 2048
9 48
Так, для n=10 число примитивных полиномов равно 60, а для n=16 — уже 2048. Следо-
вательно, на основе порождающих полиномов 10-й степени можно получить 60 различных
М-последовательностей, а при использовании порождающих полиномов 16-й степени —
2048.
Символы аn+j М-последовательности удовлетворяют рекуррентному выражению
n−1
an+ j
=
⊕
i=0
ai
+
j
hi
,
j
= 0, 1, ... ,
(3)
где знак ⊕ — суммирование по модулю два, а индексы при символах М-последовательности
берутся по модулю M; начальные значения символов а0, а1, ..., аn–1 М-последовательности мо-
гут выбираться произвольно, за исключением нулевой комбинации.
Известно, что М-последовательности относятся к классу циклических кодов и могут
задаваться с помощью полинома g(x) = (xM + 1) h(x) . Для каждой М-последовательности с
периодом M существует ровно M различных циклических сдвигов, которые могут быть полу-
чены путем умножения полинома g ( x) на x j , где j = 0, 1, ..., M −1.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 6
Использование порождающих полиномов M-последовательностей
51
Поскольку ПСКШ строятся в соответствии с символами М-последовательности, можно путем циклических сдвигов определить порядок размещения на шкале n считывающих эле-
ментов, т.е. m-му СЭ, m = 1, 2, ..., n , ставится в соответствие jm-й циклический сдвиг x jm g ( x)
М-последовательности. Тогда полином, определяющий порядок размещения n СЭ на шкале, имеет вид
n
∑r(x) = x jm , jm ∈{0, 1, ..., M −1} . m=1
(4)
Приняв j1 = 0 , согласно полиному (4) получим положения 2-го, 3-го, ..., n-го СЭ, сме-
щенные относительно 1-го СЭ на j2 , j3, ..., jn позиций соответственно. Размещение считывающих элементов в соответствии с полиномом (4) должно обеспечи-
вать получение при полном перемещении шкалы М различных n-разрядных кодовых комбинаций. В общем виде задача размещения СЭ на ПСКШ решена в работе [7].
Метод синтеза порождающих полиномов М-последовательностей. В основу метода положено использование свойств децимации М-последовательности и алгоритма Берлекемпа — Мэсси.
{ }Согласно работе [8] децимацией М-последовательности a j по индексу qs ,
s = 2, 2n − 2, называется выборка qs-х элементов данной М-последовательности. Если период M = 2n–1 исходной М-последовательности и индекс децимации qs взаимно просты, т.е. НОД(M, qs)=1, децимация называется собственной или нормальной. В дальнейшем под децимацией будем подразумевать только собственную (или нормальную) децимацию, в результате которой получается М-последовательность с тем же периодом, что и исходная М-последо-
{ }вательность. Децимацию {aj} по индексу qs обозначим как a j qs , а полученную в результате
децимации М-последовательность — как {bj}. Таким образом, можно записать
{bj } = {a j}qs .
(5)
Алгоритм генерации примитивных полиномов заданной степени в общих чертах рассмотрен в работе [9]. Однако данный алгоритм оставляет открытым вопрос о нахождении всего множества порождающих полиномов М-последовательностей с заданным периодом и не оптимизирован для использования в САПР ПСКШ.
Рассмотрим метод синтеза порождающих полиномов М-последовательностей, свободный от указанного недостатка. Реализация метода предусматривает выполнение следующих шагов.
1. Из табл. 1 выбирается примитивный полином вида (1) определенной степени n. 2. На основе полинома (1) строится рекуррентное выражение (3). 3. Посредством рекуррентного выражения (3) генерируются символы {aj} М- последовательности с периодом М = 2n – 1. 4. В соответствии с выражением (2) определяется число примитивных полиномов h(x) степени n.
5. Осуществляется поиск значений индексов децимации ql , l = 1, N −1 , {ql } ⊂ {qs},
позволяющих сформировать все нормальные децимации М-последовательности {a j } , на
основе которых могут быть получены N–1 различных М-последовательностей {bj } с
периодом М.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 6
52 И. Д. Захаров, А. А. Ожиганов
6. Производится нормальная децимация М-последовательности {aj} по индексу ql. Результатом такой децимации является Мl-последовательность (5) с периодом М.
7. Далее, с использованием алгоритма Берлекемпа — Мэсси и предварительной выборки 2n символов из полученной Мl -последовательности определяется полином hl(x), который также будет примитивным.
8. Шаги 6 и 7 повторяются для всех нормальных децимаций, найденных на шаге 5. Результатом применения метода являются N–1 порождающих полиномов степени n. Эффективность разработанного метода в основном определяется результатом выполнения шага 5. Для оптимизации поиска значений индексов децимации рассмотрим алгоритм, в
котором: {qs} — множество всех значений индексов децимации; {qk } ⊂ {qs } — множество
нечетных значений индексов децимации; REG[n] — n-разрядный двоичный циклический регистр сдвига; REGz, z = 0,..., n −1, — значение z-го разряда регистра; SHIFT[p] — p-разрядный
двоичный счетчик числа сдвигов, где p=[lb n]; Ck — флаг децимации с индексом qk, причем
Сk
=
⎧0, ⎪ ⎨
если децимация с индексом qk не позволяет получить необходимую М-последовательность;
⎩⎪1, в противном случае.
Алгоритм содержит следующие шаги:
1. qk := 1; Ck := 1 , k = 2e +1, e = 1, 2n−1 −1 . 2. qk := qk + 2 . 3. Если qk ≥ 2n −1, переход к шагу 13. 4. Если Ck = 0 , переход к шагу 2. 5. Запись qk в REG[n]; обнуление счетчика SHIFT [p]. 6. Если SHIFT [p]≥n–1, переход к шагу 10. 7. Циклический сдвиг регистра REG[n] на один разряд влево. SHIFT [p]:= SHIFT [p]+1. 8. Если REG0=1, k := REG[n], Ck := 0. 9. Возврат к шагу 6.
( )10. Если НОД qk , 2n −1 =1, переход к шагу 12.
11. Ck := 0 , переход к шагу 2. 12. Сохранение полученного значения qk в массив результатов. Переход к шагу 2. 13. Вывод массива результатов. Таким образом, используя рассмотренный алгоритм, можно найти все значения индексов, позволяющие сформировать нормальные децимации М-последовательности {a j }ql , l = 1, N − 1, на основе которых могут быть получены N–1 различных М-последо-
вательностей {bj} с периодом М.
Пример. Рассмотрим метод синтеза порождающих полиномов М-последовательности на примере, ограничившись получением всех полиномов 5-й степени.
1. Из табл. 1 выбирается примитивный полином h ( x) = x5 + x2 + 1.
2. На основе выбранного полинома строится рекуррентное выражение a5+ j = a2+ j ⊕ a j . 3. Посредством полученного рекуррентного выражения генерируются символы
{ }a j = (0, 0, 0, 0,1, 0, 0,1,0,1,1, 0, 0,1,1,1,1,1, 0, 0, 0,1,1, 0,1,1,1, 0,1, 0,1) М-последовательности с
периодом М = 25 – 1=31.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 6
Использование порождающих полиномов M-последовательностей
53
4. В соответствии с выражением (2) вычисляется количество примитивных полиномов h(x) степени 5, т.е.
( ) ( )Φ
N=
М = 2n −1 n
Φ =
М = 25 −1 5
=
Φ
(31)
5
=
30 5
=
6.
5. Осуществляется поиск значений индексов децимации ql, позволяющих сформировать нормальные децимации М-последовательности {a j }ql ,l = 1,5 . В соответствии с приведенным
)выше алгоритмом используются только нечетные значения индекса qk ∈ ⎣⎢⎡3, 25 −1 . Каждое
значение qk заносится в регистр REG[5] и вычисляются все возможные значения, получаемые при его циклическом сдвиге влево. Например, при занесении в REG[5] значения q1=3 получается следующий результат:
REG[5] ← 3 ⇒ REG[5] : 0 0 0 11;
cдвиг 1: REG[5]: 0 0 11 0 (6);
cдвиг 2 : REG[5] : 0 11 0 0 (12);
cдвиг 3 : REG[5] :11 0 0 0 (24);
cдвиг 4 : REG[5] :1 0 0 0 1 (17).
{ } { }С учетом того [8], что a j 2d qs = a j (2d qs )mod M , полученные значения индексов деци-
мации q1(0)=3, q1(1)=6, q1(2)=12, q1(3)=24 и q1(4)=17 (где значение (*) определяет число сдвигов содержимого регистра) позволяют сформировать одинаковые (с точностью до циклического сдвига) M-последовательности. Следовательно, для синтеза необходимой M-последовательности достаточно использовать один из пяти индексов децимации, например q1(0)=3.
Аналогичным образом вычисляем:
q2 (0) = 5 ⇒ q2 (1) = 10, q2 (2) = 20, q2 (3) = 9, q2 (4) = 18;
q3 (0) = 7 ⇒ q3 (1) = 14, q3 (2) = 28, q3 (3) = 25, q3 (4) = 19;
q4 (0) = 11 ⇒ q4 (1) = 22, q4 (2) = 21, q4 (3) = 13, q4 (4) = 26;
q5 (0) = 15 ⇒ q5 (1) = 30, q5 (2) = 29, q5 (3) = 27, q5 (4) = 23.
Далее осуществляется проверка, являются ли полученные децимации ql , l =1, ..., 5, нормальными. Для этого определяется наибольший общий делитель значения каждого из полученных индексов ql и периода М М-последовательности, т.е.
НОД(3, 31)=1; НОД(5, 31)=1; НОД(7, 31)=1; НОД(11, 31)=1; НОД(15, 31)=1.
Данный результат свидетельствует о нахождении пяти индексов децимации,
использование которых дает возможность получения пяти различных М-
последовательностей.
6. Производятся нормальные децимации полученной на шаге 3 М-последовательности
{aj} по индексам ql , l =1, ..., 5 . Например, первые 2n=10 символов М1-последовательности,
{ }полученные в результате децимации по индексу 3, равны
aj
3 10
= (0,0,0,0,1,1,0,0,1,0) .
7. Далее, составляется система линейных алгебраических уравнений, решаемая с
использованием алгоритма Берлекемпа — Мэсси, т.е.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 6
54 И. Д. Захаров, А. А. Ожиганов
a5 = a4h4 ⊕ a3h3 ⊕ a2h2 ⊕ a1h1 ⊕ a0h0 ; ⎫ ⎧1 = 1⋅ h4 ⊕ 0 ⋅ h3 ⊕ 0 ⋅ h2 ⊕ 0 ⋅ h1 ⊕ 0 ⋅ h0 ;
a6 a7
= =
a5 h4 a6 h4
⊕ a4h3 ⊕ a5h3
⊕ a3h2 ⊕ a4h2
⊕ a2h1 ⊕ a3h1
⊕ ⊕
aa12hh00;;⎪⎬⎪⎪
=
⎪⎪⎪⎨00
= 1⋅ h4 ⊕1⋅ h3 ⊕ 0 ⋅ h2 = 0 ⋅ h4 ⊕1⋅ h3 ⊕1⋅ h2
⊕ 0 ⋅ h1 ⊕ 0 ⋅ h1
⊕ 0 ⋅ h0 ; ⊕ 0 ⋅ h0 ; .
a8
=
a7 h4
⊕ a6h3
⊕
a5h2
⊕
a4 h1
⊕
a3h0
;
⎪ ⎪
⎪⎪1 = 0 ⋅ h4 ⊕ 0 ⋅ h3 ⊕1⋅ h2 ⊕1⋅ h1 ⊕ 0 ⋅ h0 ;
a9 = a8h4 ⊕ a7h3 ⊕ a6h2 ⊕ a5h1 ⊕ a4h0 ⎭⎪ ⎪⎩0 = 1⋅ h4 ⊕ 0 ⋅ h3 ⊕ 0 ⋅ h2 ⊕1⋅ h1 ⊕1⋅ h0 .
В результате получаем значения h0 = 1; h1 = 0; h2 = 1; h3 = 1; h4 = 1; h5 = 1 , по которым
находим искомый порождающий полином h1(x) = h5 x5 + h4 x4 + h3x3 + h2 x2 + h1x1 + h0 = 1⋅ x5 + 1⋅ x4 + 1⋅ x3 + 1⋅ x2 + 0 ⋅ x1 + 1⋅ x0 =
= x5 + x4 + x3 + x2 + 1.
8. Шаги 6 и 7 повторяются для остальных нормальных децимаций, найденных на
шаге 5; в результате получаем еще четыре порождающих полинома 5-й степени.
Все порождающие полиномы 5-й степени, соответствующие М-последовательности и
значения индексов децимации приведены в табл. 3.
Таблица 3
Индекс децимации q Порождающий полином h(x)
M-последовательность
0
h ( x) = x5 + x2 +1
0000100101100111110001101110101
3
h1 ( x) = x5 + x4 + x3 + x2 +1
0000110010011111011100010101101
5
h2 ( x) = x5 + x4 + x2 + x +1
0000111001101111101000100101011
7
h3 ( x) = x5 + x3 + x2 + x +1
0000101101010001110111110010011
11
h4 ( x) = x5 + x4 + x3 + x +1
0000110101001000101111101100111
15
h5 ( x) = x5 + x3 +1
0000101011101100011111001101001
Отметим, что любая из приведенных в табл. 3 М-последовательностей пригодна для построения 5-разрядной ПСКШ. Например, линейная развертка круговой ПСКШ, выполненной с использованием М-последовательности, полученной на основе порождающего полинома
h3 ( x) = x5 + x3 + x2 + x + 1 , приведена на рисунке. Размещение на шкале пяти считывающих
элементов задано в соответствии с полиномом r(x) = 1 + x2 + x4 + x6 + x8 .
Последовательно с использованием считывающих элементов фиксируя кодовую комби-
нацию при перемещении шкалы на один квант, например справа налево, получаем 31 различ-
ную 5-разрядную кодовую комбинацию. Эти кодовые комбинации, соответствующие 31 раз-
личному угловому положению ПСКШ, приведены в табл. 4.
Таблица 4
Кодовая комбинация
Кодовая комбинация
Номер сдвига ПСКШ
Двоичный псевдослучай-
ный код
Десятичный эквивалент
Номер сдвига ПСКШ
Двоичный псевдослучай-
ный код
Десятичный эквивалент
0 00110
6
16 10110
22
1 00011
3
17 11110
30
2 01100 12
18 01101
13
3 00111
7
19 11100
28
4 11000 24
20 11010
26
5 01110 14
21 11001
25
6 10000 16
22 10101
21
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 6
Использование порождающих полиномов M-последовательностей
55
Продолжение табл. 4
Кодовая комбинация
Кодовая комбинация
Номер сдвига ПСКШ
Двоичный псевдослучай-
ный код
Десятичный эквивалент
Номер сдвига ПСКШ
Двоичный псевдослучай-
ный код
Десятичный эквивалент
7 11101 29
23 10010
18
8 00001
1
24 01010
10
9 11011 27
25 00100
4
10 00010
2
26 10100
20
11 10111
23
27 01001
9
12 00101
5
28 01000
8
13 01111
15
29 10011
19
14 01011
11
30 10001
17
15 11111
31
Заключение. Предложенный в настоящей статье метод построения порождающих по-
линомов М-последовательностей наиболее целесообразно использовать в системах автомати-
зированного проектирования псевдослучайных кодовых шкал для преобразователей переме-
щений.
СПИСОК ЛИТЕРАТУРЫ
1. Ожиганов А. А. Псевдослучайные кодовые шкалы // Изв. вузов СССР. Пpибоpостроение. 1987. Т. 30, № 2. С. 40—43.
2. Ожиганов А. А. Псевдослучайные кодовые шкалы для преобразователей линейных перемещений // Изв. вузов. Приборостроение. 1995. Т. 38, № 11—12. С. 37—39.
3. Ожиганов А. А., Чжипэн Жуань. Использование псевдослучайных последовательностей при построении кодовых шкал для преобразователей линейных перемещений // Там же. 2008. Т. 51, № 7. С. 28—33.
4. Ожиганов А. А., Коробейников А. Г., Климанов В. А. Структура системы автоматизированного проектирования рекурсивных кодовых шкал // Науч.-техн. вестн. СПбГУ ИТМО. 2006. Вып. 32. C. 237—245.
5. Макуильямс Ф. Д., Слоан Н. Д. Псевдослучайные последовательности и таблицы // ТИИЭР. 1976. Т. 64, № 12. С. 80—95.
6. Муттер В. М. Основы помехоустойчивой телепередачи информации. Л.: Энергоатомиздат, 1990. 288 с.
7. Ожиганов А. А. Алгоритм размещения считывающих элементов на псевдослучайной кодовой шкале // Изв. вузов. Приборостроение. 1994. Т. 37, № 2. С. 22—27.
8. Сарвате Д. В., Персли М. Б. Взаимно-корреляционные свойства псевдослучайных и родственных последовательностей // ТИИЭР. 1980. Т. 68, № 5. С. 59—95.
9. Борисенко Н. П., Гусаров А. В., Кривонос А. П. О возможности генерации примитивных полиномов заданной степени и быстрого вычисления сдвига выходной последовательности РСЛОС на заданное число тактов // Сб. трудов XII Междунар. науч. конф. „Информатизация и информационная безопасность правоохранительных систем“. М., 2003. С. 334—339.
Сведения об авторах
Илья Дмитриевич Захаров
— аспирант; Санкт-Петербургский государственный университет ин-
формационных технологий, механики и оптики, кафедра вычисли-
тельной техники; E-mail: zakharov_ilya@hotmail.com
Александр Аркадьевич Ожиганов — д-р техн. наук, профессор; Санкт-Петербургский государственный
университет информационных технологий, механики и оптики, ка-
федра вычислительной техники; E-mail: ojiganov@mail.ifmo.ru
Рекомендована кафедрой вычислительной техники
Поступила в редакцию 18.01.11 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 6