КРИТЕРИЙ ВЫБОРА ДЛИНЫ ЛИНЕЙНОЙ ПСЕВДОСЛУЧАЙНОЙ КОДОВОЙ ШКАЛЫ
30 А. А. Ожиганов, Жуань Чжипэн
УДК 621.3.085
А. А. ОЖИГАНОВ, ЖУАНЬ ЧЖИПЭН
КРИТЕРИЙ ВЫБОРА ДЛИНЫ ЛИНЕЙНОЙ ПСЕВДОСЛУЧАЙНОЙ КОДОВОЙ ШКАЛЫ
Предложен критерий выбора минимального увеличения длины псевдослучайной кодовой шкалы с несколькими информационными кодовыми дорожками для преобразователей линейных перемещений. Приведен пример использования критерия.
Ключевые слова: критерий выбора, псевдослучайная кодовая шкала, М-последовательность, считывающие элементы.
В работе [1] были рассмотрены линейные псевдослучайные кодовые шкалы (ЛПСКШ)
для преобразователей перемещений. Основным достоинством таких шкал, по сравнению с
классическими [2], маска которых выполнена в обыкновенном двоичном коде или коде Грея,
является наличие одной информационной кодовой дорожки для преобразователя любой раз-
рядности. Однако использование в ЛПСКШ всего одной информационной дорожки влечет за
собой, при некоторых вариантах размещения вдоль нее считывающих элементов (СЭ), фак-
тически двукратное увеличение длины шкалы. Данная особенность однодорожечных
ЛПСКШ усложняет процесс их изготовления, в частности при разработке преобразователей
перемещения с такими шкалами, которые должны быть использованы для измерения значи-
тельных перемещений.
В работе [3] был предложен метод построения ЛПСКШ с несколькими информацион-
ными дорожками (2—4), позволяющий учесть указанную выше особенность, присущую од-
нодорожечным ЛПСКШ, и за счет использования дополнительных дорожек минимизировать
увеличение длины шкалы. Однако в этой работе не дано количественной оценки такого
уменьшения и конкретных рекомендаций для получения оптимального результата.
В настоящей работе предлагается критерий выбора минимального увеличения длины
ЛПСКШ с несколькими информационными дорожками. Для формализации критерия рас-
смотрим основные этапы синтеза таких шкал.
На первом этапе осуществляется построение модели однодорожечной ЛПСКШ. Кодо-
вая маска такой шкалы представляется в соответствии с символами псевдослучайной двоич-
ной последовательности максимальной длины (М-последовательности) {si }= s0s1...sM −1 .
Для генерации М-последовательности длиной М=2n–1 используется примитивный не-
приводимый полином h(x) степени п с коэффициентами поля Галуа GF(2), т.е.
n
∑h(x) = hi xi ,
i=0
где h0=hn=1, а hi=0,1 при 0 < i < n [4].
Символы М-последовательности sn+j удовлетворяют рекурсивному выражению
n−1
sn+
j
=
Ξ
i=0
si+
j hi
,
j = 0,1,...,
(1) (2)
где знак Ξ означает суммирование по модулю два, а индексы при символах М-последо-
вательности берутся по модулю M. Начальные значения символов М-последовательности
s0s1...sn−1 могут выбираться произвольно, за исключением нулевой комбинации.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 5
Критерий выбора длины линейной псевдослучайной кодовой шкалы
31
Известно, что М-последовательности относятся к классу циклических кодов и могут за-
даваться с помощью порождающего полинома g(x) = (xM +1) h(x) . Для каждой М-после-
довательности длиной M существует ровно M различных циклических сдвигов, которые мо-
гут быть получены путем умножения порождающего полинома g(x) на x j , где
j = 0,1,…, M −1.
Поскольку псевдослучайная кодовая шкала строится в соответствии с символами М-последовательности, можно путем циклических сдвигов определить порядок размещения на шкале n считывающих элементов, т.е. m-му СЭ ( m = 1, 2,..., n ) ставится в соответствие jm-й
циклический сдвиг x jm g ( x) М-последовательности.
Тогда полином, определяющий порядок размещения n СЭ на шкале, имеет вид
n
∑r(x) = x jm ,
(3)
m=1
где jm ∈{0,1,..., M −1}.
Положив j1 = 0 , согласно полиному (3), получим положения 2-го, 3-го, ..., n-го СЭ,
смещенные относительно положения первого СЭ на j2 , j3,..., jn позиций соответственно.
Используемый вариант размещения считывающих элементов, согласно (3), должен по-
зволять получить при полном перемещении шкалы М различных n-разрядных кодовых ком-
бинаций. В общем виде задача размещения СЭ на шкале была решена в [5].
( )Линейная шкала разомкнута, ее разрешающая способность δ = L / M = L / 2n −1 , где
L — длина кодируемого перемещения, а n — разрядность шкалы. Для обеспечения заданной разрешающей способности необходимо получить соответствующую последовательность
символов {Si } , i = 0, 1,…, пригодную для синтеза единственной информационной дорожки
ЛПСКШ. Очевидно, символы последовательности {Si } должны полностью включать в себя сим-
волы M-последовательности {si } , а также некоторые дополнительные символы этой же последовательности, число которых зависит от выбранного полинома размещения r(x) на шкале СЭ.
Общее число символов последовательности {Si } с учетом n задаваемых начальных зна-
чений может быть найдено из выражения
Q = M + jn .
(4)
Задача генерации последовательности {Si } в общем виде решается с использованием
рекурсивного выражения (2) в предположении, что размещение элементов на шкале
корректно и задается полиномом (3). Для определенности начальные значения символов
последовательности {Si } выбираются S0 = S1 =...= Sn−2 = 0 , Sn−1 =1. Таким образом,
последовательность {Si } , i = 0,1,…,Q−1, может быть получена на основе рекурсивного
выражения (2) с учетом (4).
На следующих этапах синтеза шкалы осуществляется построение моделей ЛПСКШ с
двумя, тремя и четырьмя информационными дорожками.
На последнем этапе выбирается ЛПСКШ минимальной длины. Для получения
оптимального результата этого этапа рассмотрим следующий критерий. Пусть t — число
дорожек ЛПСКШ, а e, g, k — параметры разбиения полинома r(x) размещения на шкале СЭ
на две, три и четыре части соответственно.
Тогда представим полином (3) в следующем виде:
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 5
32 А. А. Ожиганов, Жуань Чжипэн
n
∑r(x) = x jm = 1 + x + m=1
где 0 < e < g < k < n .
+ x je + x je+1 +
+ x jg + x jg+1 +
+ x jk + x jk+1 +
+ x jn ,
(5)
При t = 2 увеличение длины первой информационной дорожки шкалы может быть вычислено как lA = je − j1 , а второй — lB = jn − je+1 . Таким образом, результирующее увеличение длины двухдорожечной ЛПСКШ будет определяться выражением
l2д = max[lA, lB ] = max[ je − j1, jn − je+1] . Всего имеется n–1 вариантов разбиения полинома r(x) на две части. Эти варианты представляются множеством
{ }l2д = {max[ j1, jn − j2 ], ..., max[ je − j1, jn − je+1], ..., max[ jn−1, jn − jn ]} .
(6)
Для минимизации увеличения длины двухдорожечной ЛПСКШ необходимо осуществить выбор такого варианта разбиения полинома r(x) на две части, при котором
l2д = {max[ je − j1, jn − je+1]} → min ,
(7)
где e = 1, n −1.
При t = 3 увеличение длины первой, второй и третьей дорожек ЛПСКШ определяется соответственно из выражений lA = je − j1 , lB = jg − je+1 и lC = jn − jg+1 . Следовательно,
результирующее увеличение длины ЛПСКШ с тремя информационными дорожками может
быть получено из соотношения l3д = max[lA, lB , lC ] = max[ je − j1, jg − je+1, jn − jg+1] .
Всего имеется 1+ 2 +
+
(n
−
2)
=
(n
−
2)(n 2
−1)
вариантов разбиения полинома r(x) на три
части. Эти варианты представляются множеством
{ }l3д = {max[ j1, j2 − j2 , jn − j3 ], max[ j1, j3 − j2 , jn − j4 ], ...,
..., max[ je − j1, jg − je+1, jn − jg+1], ..., max[ jn−2 , jn−1 − jn−1, jn − jn ]} .
(8)
Для получения минимального увеличения длины трехдорожечной ЛПСКШ необходимо осуществить выбор такого варианта разбиения полинома r(x) на три части, при котором
{ }l3д = max[ je − j1, jg − je+1, jn − jg+1] → min ,
(9)
где e = 1, n − 2 , а g = e + 1, n −1.
При t = 4 увеличение длины дорожек ЛПСКШ определяется как lA = je − j1 ,
lB = jg − je+1 , lC = jk − jg+1 и lD = jn − jk+1 . Таким образом, результирующее увеличение
длины четырехдорожечной ЛПСКШ будет определяться выражением
l4д = max[lA, lB , lC , lD ] = max[ je − j1, jg − je+1, jk − jg+1, jn − jk+1] .
Всего
имеется
1⋅ 2 2
+
2⋅3 2
+
+
(n
−
3)(n 2
−
2)
=
(n
−
3) ( n
− 6
2)(n
− 1)
вариантов
разбиения
полинома r(x) на четыре части. Эти варианты представляются множеством
{ }l4д = {max[ j1, j2 − j2 , j3 − j3, jn − j4 ], max[ j1, j2 − j2 , j4 − j3 , jn − j5 ], ...,
..., max[ je − j1, jg − je+1, jk − jg+1, jn − jk+1],..., max[ jn−3 , jn−2 − jn−2 , jn−1 − jn−1, jn − jn ]} .(10)
Для минимизации увеличения длины ЛПСКШ с четырьмя дорожками необходимо
осуществить выбор такого варианта разбиения полинома r(x) на четыре части, при котором
{ }l4д = max[ je − j1, jg − je+1, jk − jg+1, jn − jk+1] → min ,
(11)
где e = 1, n − 3 , g = e + 1, n − 2 , а k = g + 1, n −1 .
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 5
Критерий выбора длины линейной псевдослучайной кодовой шкалы
33
Таким образом, критерий K выбора минимального увеличения длины ЛПСКШ с числом информационных дорожек 2—4 с учетом соотношений (5)—(11) может быть представлен в следующем виде:
{K
=
⎨⎧⎪⎪{mmaaxx[[
je je
− −
j1, j1,
{⎪
⎪⎩ max[ je − j1,
jn − je+1]} → min при t = 2,
}jg − je+1, jn − jg+1] → min при t = 3,
}jg − je+1, jk − jg+1, jn − jk+1] → min при
t = 4.
(12)
Для удобства применения критерия введем параметр, позволяющий оценить относи-
тельное увеличение длины ЛПСКШ. Определим этот параметр как
V
=
l M
,
(13)
где l — величина удлинения шкалы.
Поясним способ применения предложенного критерия на примере девятиразрядной
ЛПСКШ.
Для генерации M-последовательности {si } = a0a1 ...a510 = 000000001.......100010001 дли-
ной M = 29 −1 = 511 использован примитивный полином h ( x) = x9 + x4 + 1. Размещение де-
вяти СЭ вдоль кодовой дорожки шкалы задано в соответствии с полиномом
r ( x) = 1 + x48 + x96 + x144 + x192 + x240 + x288 + x336 + x384 .
(14)
Тогда длина последовательности S = {Si } = S0S1…S894 = 000000001......110000111,
необходимая для синтеза единственной информационной дорожки ЛПСКШ, будет
Q = M + jn = 511 + 384 = 895 , а абсолютное увеличение длины шкалы, необходимое для
обеспечения заданной разрешающей способности, l1д = jn = 384 . Таким образом, относи-
тельное
увеличение
длины
однодорожечной
ЛПСКШ
V1д
=
l1д M
=
384 511
=
0, 75 (75 %) .
Для построения модели двухдорожечной ЛПСКШ полином r ( x) разбивается со
e
стороны младших степеней на две части: rA ( x) = ∑ x jm m=1
определяется значение е.
∑и rB ( x) = 9−e x je+m . Далее m=1
В соответствии с (6) имеем исходные данные для восьми вариантов построения двухдо-
рожечной шкалы
{l2д} = {max[0, 336], max[48, 288], max[96, 240], max[144, 192], max[192, 144],
max[240,96], max[288, 48], max[336, 0]} ={336, 288, 240, 192, 192, 240, 288, 336} .
Из (7) определяется минимальное увеличение длины двухдорожечной ЛПСКШ
l2д = {max[ je − j1, jn − je+1]} → min = min{336, 288, 240, 192, 192, 240, 288, 336} = 192.
Для рассматриваемого случая je − j1 = 144 , а jn − je+1 = 192 . С учетом этих значений по выражению (14) рассчитывается значение коэффициента разбиения e = 4 . Тогда
rA ( x) = 1+ x48 + x96 + x144 и rB ( x) = x192 + x240 + x288 + x336 + x384 = x192 (1+ x48 + x96 + x144 + x192 ) .
Следовательно, относительное увеличение длины двухдорожечной ЛПСКШ
V2д
=
l2д M
=
192 511
=
0,
37
(37
%)
.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 5
34 А. А. Ожиганов, Жуань Чжипэн
Для построения модели трехдорожечной ЛПСКШ полином r ( x) разбивается со
e g−e
∑ ∑стороны младших степеней на три части: rA ( x) = x jm , rB ( x) = x je+m m=1 m=1
и
∑rC ( x) = 8−g x jg+m . Далее определяются значения е и g. m=1 В соответствии с (8) имеем исходные данные для построения трехдорожечной шкалы
{l3д} = {max[0, 0, 288], max[0, 48, 240], ..., max[96, 96, 96], ...,
..., max[240, 48, 0], max[288, 0, 0]} ={288, 240,..., 96, ..., 240, 288} .
Из (9) определяется минимальное увеличение длины трехдорожечной ЛПСКШ
{ }l3д = max[ je − j1, jg − je+1, jn − jg+1] → min = min{288, 240,...,96,..., 240, 288} = 96 .
Для данного случая je − j1 = 96 , jg − je+1 = 96 , а jn − jg+1 = 96 . С учетом этих
значений по выражению (14) рассчитываются значения коэффициентов разбиения e = 3 и
g = 6 . Тогда rA ( x) = 1 + x48 + x96 , rB ( x) = x144 + x192 + x240 = x144 (1 + x48 + x96 ) , а
rC ( x) = x288 + x336 + x384 = x288 (1 + x48 + x96 ) . Таким образом, относительное увеличение
длины
трехдорожечной
ЛПСКШ
V3д
=
l3д M
=
96 511
≈
0,19
(19
%)
.
Для построения модели четырехдорожечной ЛПСКШ полином r ( x) разбивается со
e g−e
∑ ∑стороны младших степеней на четыре части: rA ( x) = x jm , rB ( x) = x je+m , m=1 m=1
∑ ∑( )rC x = k−g x jg+m
и
rD
(x)
8−k
=
x jk+m .
Далее определяются
значения
e,
g
и k.
m=1 m=1
Согласно (10), имеем исходные данные для построения четырехдорожечной шкалы
{l4д} = {max[0, 0, 0, 240], max[0, 0, , 48 192], ... max[96, 96 48, 0], ...,
..., max[192, 48, 0, 0], max[0, 0, 0, 240]} ={240, 192, ..., 96, ..., 192, 240} .
Из (11) определяется минимальное увеличение длины четырехдорожечной ЛПСКШ
{ }l4д = max[ je − j1, jg − je+1, jk − jg+1, jn − jk+1] → min = min {240,192,...,96,...,192, 240} = 96 .
Для рассматриваемого случая je − j1 = 96 , jg − je+1 = 96 , jk − jg+1 = 48 , а jn − jk+1 = 0 .
С учетом этих значений по выражению (14) рассчитываются значения коэффициентов
разбиения e = 3 , g = 6 и k = 8 . Тогда rA ( x) = 1 + x48 + x96 , rB ( x) = x144 + x192 + x240 =
= x144 (1 + x48 + x96 ) , rC ( x) = x288 + x336 = x288 (1 + x48 ) и rD ( x) = x384 . Следовательно,
относительное
увеличение
длины
четырехдорожечной
ЛПСКШ
V4д
=
l4д M
=
96 511
≈
0,19 (19 %) .
Можно видеть, что V3д = V4д . Таким образом, трех- и четырехдорожечный варианты
построения ЛПСКШ оказались эквивалентными с точки зрения минимального увеличения
длины шкалы для заданного размещения на шкале СЭ. Очевидно, что для практической
реализации наиболее предпочтительным является трехдорожечный вариант выполнения
шкалы.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 5
Критерий выбора длины линейной псевдослучайной кодовой шкалы
35
На рисунке приведен пример девятиразрядной трехдорожечной ЛПСКШ с размещением
СЭ в соответствии с полиномами rA ( x) = 1 + x48 + x96 , rB ( x) = x144 + x192 + x240 =
= x144 (1 + x48 + x96 ) , rC ( x) = x288 + x336 + x384 = x288 (1 + x48 + x96 ) .
СЭ1 A0 A1
…
δ СЭ2 A48
СЭ3
… A96
… A607
0 0 0 0 … 0 0 0 0… 0 0 0 0… 0 0 0 0
В0 СЭ4 В1 00
… 0 0…
В48СЭ5
… В96СЭ6
… В607
0 0 0 0… 0 0 0 0… 0 0 0 0
СЭ7 С0
С1
…
С48СЭ8
СЭ9
… С96
… С607
0 0 0 0 … 0 0 0 0… 0 0 0 0 …0 0 0 0
Предложенный критерий выбора минимального увеличения длины псевдослучайной кодовой шкалы может быть положен в основу построения преобразователей линейных перемещений, работающих по методу считывания.
СПИСОК ЛИТЕРАТУРЫ
1. Ожиганов А. А. Псевдослучайные кодовые шкалы для преобразователей линейных перемещений // Изв. вузов. Приборостроение. 1995. Т. 38, № 11—12. С. 37—39.
2. Домрачев В. Г., Мейко Б. С. Цифровые преобразователи угла: принципы построения, теория точности, методы контроля. М.: Энергоатомиздат, 1984. 328 с.
3. Ожиганов А. А., Жуань Чжипэн. Использование псевдослучайных последовательностей при построении кодовых шкал для преобразователей линейных перемещений // Изв. вузов. Приборостроение. 2008. Т. 51, № 7. С. 28—33.
4. Макуильямс Ф. Д., Слоан Н. Д. Псевдослучайные последовательности и таблицы // ТИИЭР. 1976. Т. 64, № 12. С. 80—95.
5. Ожиганов А. А. Алгоритм размещения считывающих элементов на псевдослучайной кодовой шкале // Изв. вузов. Приборостроение. 1994. Т. 37, № 2. С. 22—27.
Сведения об авторах
Александр Аркадьевич Ожиганов — д-р техн. наук, профессор; Санкт-Петербургский государственный
университет информационных технологий, механики и оптики, ка-
федра вычислительной техники; E-mail: ojiganov@mail.ifmo.ru
Жуань Чжипэн
— аспирант; Санкт-Петербургский государственный университет ин-
формационных технологий, механики и оптики, кафедра вычисли-
тельной техники; E-mail: zhipeng_ruan@mail.ru
Рекомендована кафедрой вычислительной техники
Поступила в редакцию 16.12.09 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 5
УДК 621.3.085
А. А. ОЖИГАНОВ, ЖУАНЬ ЧЖИПЭН
КРИТЕРИЙ ВЫБОРА ДЛИНЫ ЛИНЕЙНОЙ ПСЕВДОСЛУЧАЙНОЙ КОДОВОЙ ШКАЛЫ
Предложен критерий выбора минимального увеличения длины псевдослучайной кодовой шкалы с несколькими информационными кодовыми дорожками для преобразователей линейных перемещений. Приведен пример использования критерия.
Ключевые слова: критерий выбора, псевдослучайная кодовая шкала, М-последовательность, считывающие элементы.
В работе [1] были рассмотрены линейные псевдослучайные кодовые шкалы (ЛПСКШ)
для преобразователей перемещений. Основным достоинством таких шкал, по сравнению с
классическими [2], маска которых выполнена в обыкновенном двоичном коде или коде Грея,
является наличие одной информационной кодовой дорожки для преобразователя любой раз-
рядности. Однако использование в ЛПСКШ всего одной информационной дорожки влечет за
собой, при некоторых вариантах размещения вдоль нее считывающих элементов (СЭ), фак-
тически двукратное увеличение длины шкалы. Данная особенность однодорожечных
ЛПСКШ усложняет процесс их изготовления, в частности при разработке преобразователей
перемещения с такими шкалами, которые должны быть использованы для измерения значи-
тельных перемещений.
В работе [3] был предложен метод построения ЛПСКШ с несколькими информацион-
ными дорожками (2—4), позволяющий учесть указанную выше особенность, присущую од-
нодорожечным ЛПСКШ, и за счет использования дополнительных дорожек минимизировать
увеличение длины шкалы. Однако в этой работе не дано количественной оценки такого
уменьшения и конкретных рекомендаций для получения оптимального результата.
В настоящей работе предлагается критерий выбора минимального увеличения длины
ЛПСКШ с несколькими информационными дорожками. Для формализации критерия рас-
смотрим основные этапы синтеза таких шкал.
На первом этапе осуществляется построение модели однодорожечной ЛПСКШ. Кодо-
вая маска такой шкалы представляется в соответствии с символами псевдослучайной двоич-
ной последовательности максимальной длины (М-последовательности) {si }= s0s1...sM −1 .
Для генерации М-последовательности длиной М=2n–1 используется примитивный не-
приводимый полином h(x) степени п с коэффициентами поля Галуа GF(2), т.е.
n
∑h(x) = hi xi ,
i=0
где h0=hn=1, а hi=0,1 при 0 < i < n [4].
Символы М-последовательности sn+j удовлетворяют рекурсивному выражению
n−1
sn+
j
=
Ξ
i=0
si+
j hi
,
j = 0,1,...,
(1) (2)
где знак Ξ означает суммирование по модулю два, а индексы при символах М-последо-
вательности берутся по модулю M. Начальные значения символов М-последовательности
s0s1...sn−1 могут выбираться произвольно, за исключением нулевой комбинации.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 5
Критерий выбора длины линейной псевдослучайной кодовой шкалы
31
Известно, что М-последовательности относятся к классу циклических кодов и могут за-
даваться с помощью порождающего полинома g(x) = (xM +1) h(x) . Для каждой М-после-
довательности длиной M существует ровно M различных циклических сдвигов, которые мо-
гут быть получены путем умножения порождающего полинома g(x) на x j , где
j = 0,1,…, M −1.
Поскольку псевдослучайная кодовая шкала строится в соответствии с символами М-последовательности, можно путем циклических сдвигов определить порядок размещения на шкале n считывающих элементов, т.е. m-му СЭ ( m = 1, 2,..., n ) ставится в соответствие jm-й
циклический сдвиг x jm g ( x) М-последовательности.
Тогда полином, определяющий порядок размещения n СЭ на шкале, имеет вид
n
∑r(x) = x jm ,
(3)
m=1
где jm ∈{0,1,..., M −1}.
Положив j1 = 0 , согласно полиному (3), получим положения 2-го, 3-го, ..., n-го СЭ,
смещенные относительно положения первого СЭ на j2 , j3,..., jn позиций соответственно.
Используемый вариант размещения считывающих элементов, согласно (3), должен по-
зволять получить при полном перемещении шкалы М различных n-разрядных кодовых ком-
бинаций. В общем виде задача размещения СЭ на шкале была решена в [5].
( )Линейная шкала разомкнута, ее разрешающая способность δ = L / M = L / 2n −1 , где
L — длина кодируемого перемещения, а n — разрядность шкалы. Для обеспечения заданной разрешающей способности необходимо получить соответствующую последовательность
символов {Si } , i = 0, 1,…, пригодную для синтеза единственной информационной дорожки
ЛПСКШ. Очевидно, символы последовательности {Si } должны полностью включать в себя сим-
волы M-последовательности {si } , а также некоторые дополнительные символы этой же последовательности, число которых зависит от выбранного полинома размещения r(x) на шкале СЭ.
Общее число символов последовательности {Si } с учетом n задаваемых начальных зна-
чений может быть найдено из выражения
Q = M + jn .
(4)
Задача генерации последовательности {Si } в общем виде решается с использованием
рекурсивного выражения (2) в предположении, что размещение элементов на шкале
корректно и задается полиномом (3). Для определенности начальные значения символов
последовательности {Si } выбираются S0 = S1 =...= Sn−2 = 0 , Sn−1 =1. Таким образом,
последовательность {Si } , i = 0,1,…,Q−1, может быть получена на основе рекурсивного
выражения (2) с учетом (4).
На следующих этапах синтеза шкалы осуществляется построение моделей ЛПСКШ с
двумя, тремя и четырьмя информационными дорожками.
На последнем этапе выбирается ЛПСКШ минимальной длины. Для получения
оптимального результата этого этапа рассмотрим следующий критерий. Пусть t — число
дорожек ЛПСКШ, а e, g, k — параметры разбиения полинома r(x) размещения на шкале СЭ
на две, три и четыре части соответственно.
Тогда представим полином (3) в следующем виде:
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 5
32 А. А. Ожиганов, Жуань Чжипэн
n
∑r(x) = x jm = 1 + x + m=1
где 0 < e < g < k < n .
+ x je + x je+1 +
+ x jg + x jg+1 +
+ x jk + x jk+1 +
+ x jn ,
(5)
При t = 2 увеличение длины первой информационной дорожки шкалы может быть вычислено как lA = je − j1 , а второй — lB = jn − je+1 . Таким образом, результирующее увеличение длины двухдорожечной ЛПСКШ будет определяться выражением
l2д = max[lA, lB ] = max[ je − j1, jn − je+1] . Всего имеется n–1 вариантов разбиения полинома r(x) на две части. Эти варианты представляются множеством
{ }l2д = {max[ j1, jn − j2 ], ..., max[ je − j1, jn − je+1], ..., max[ jn−1, jn − jn ]} .
(6)
Для минимизации увеличения длины двухдорожечной ЛПСКШ необходимо осуществить выбор такого варианта разбиения полинома r(x) на две части, при котором
l2д = {max[ je − j1, jn − je+1]} → min ,
(7)
где e = 1, n −1.
При t = 3 увеличение длины первой, второй и третьей дорожек ЛПСКШ определяется соответственно из выражений lA = je − j1 , lB = jg − je+1 и lC = jn − jg+1 . Следовательно,
результирующее увеличение длины ЛПСКШ с тремя информационными дорожками может
быть получено из соотношения l3д = max[lA, lB , lC ] = max[ je − j1, jg − je+1, jn − jg+1] .
Всего имеется 1+ 2 +
+
(n
−
2)
=
(n
−
2)(n 2
−1)
вариантов разбиения полинома r(x) на три
части. Эти варианты представляются множеством
{ }l3д = {max[ j1, j2 − j2 , jn − j3 ], max[ j1, j3 − j2 , jn − j4 ], ...,
..., max[ je − j1, jg − je+1, jn − jg+1], ..., max[ jn−2 , jn−1 − jn−1, jn − jn ]} .
(8)
Для получения минимального увеличения длины трехдорожечной ЛПСКШ необходимо осуществить выбор такого варианта разбиения полинома r(x) на три части, при котором
{ }l3д = max[ je − j1, jg − je+1, jn − jg+1] → min ,
(9)
где e = 1, n − 2 , а g = e + 1, n −1.
При t = 4 увеличение длины дорожек ЛПСКШ определяется как lA = je − j1 ,
lB = jg − je+1 , lC = jk − jg+1 и lD = jn − jk+1 . Таким образом, результирующее увеличение
длины четырехдорожечной ЛПСКШ будет определяться выражением
l4д = max[lA, lB , lC , lD ] = max[ je − j1, jg − je+1, jk − jg+1, jn − jk+1] .
Всего
имеется
1⋅ 2 2
+
2⋅3 2
+
+
(n
−
3)(n 2
−
2)
=
(n
−
3) ( n
− 6
2)(n
− 1)
вариантов
разбиения
полинома r(x) на четыре части. Эти варианты представляются множеством
{ }l4д = {max[ j1, j2 − j2 , j3 − j3, jn − j4 ], max[ j1, j2 − j2 , j4 − j3 , jn − j5 ], ...,
..., max[ je − j1, jg − je+1, jk − jg+1, jn − jk+1],..., max[ jn−3 , jn−2 − jn−2 , jn−1 − jn−1, jn − jn ]} .(10)
Для минимизации увеличения длины ЛПСКШ с четырьмя дорожками необходимо
осуществить выбор такого варианта разбиения полинома r(x) на четыре части, при котором
{ }l4д = max[ je − j1, jg − je+1, jk − jg+1, jn − jk+1] → min ,
(11)
где e = 1, n − 3 , g = e + 1, n − 2 , а k = g + 1, n −1 .
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 5
Критерий выбора длины линейной псевдослучайной кодовой шкалы
33
Таким образом, критерий K выбора минимального увеличения длины ЛПСКШ с числом информационных дорожек 2—4 с учетом соотношений (5)—(11) может быть представлен в следующем виде:
{K
=
⎨⎧⎪⎪{mmaaxx[[
je je
− −
j1, j1,
{⎪
⎪⎩ max[ je − j1,
jn − je+1]} → min при t = 2,
}jg − je+1, jn − jg+1] → min при t = 3,
}jg − je+1, jk − jg+1, jn − jk+1] → min при
t = 4.
(12)
Для удобства применения критерия введем параметр, позволяющий оценить относи-
тельное увеличение длины ЛПСКШ. Определим этот параметр как
V
=
l M
,
(13)
где l — величина удлинения шкалы.
Поясним способ применения предложенного критерия на примере девятиразрядной
ЛПСКШ.
Для генерации M-последовательности {si } = a0a1 ...a510 = 000000001.......100010001 дли-
ной M = 29 −1 = 511 использован примитивный полином h ( x) = x9 + x4 + 1. Размещение де-
вяти СЭ вдоль кодовой дорожки шкалы задано в соответствии с полиномом
r ( x) = 1 + x48 + x96 + x144 + x192 + x240 + x288 + x336 + x384 .
(14)
Тогда длина последовательности S = {Si } = S0S1…S894 = 000000001......110000111,
необходимая для синтеза единственной информационной дорожки ЛПСКШ, будет
Q = M + jn = 511 + 384 = 895 , а абсолютное увеличение длины шкалы, необходимое для
обеспечения заданной разрешающей способности, l1д = jn = 384 . Таким образом, относи-
тельное
увеличение
длины
однодорожечной
ЛПСКШ
V1д
=
l1д M
=
384 511
=
0, 75 (75 %) .
Для построения модели двухдорожечной ЛПСКШ полином r ( x) разбивается со
e
стороны младших степеней на две части: rA ( x) = ∑ x jm m=1
определяется значение е.
∑и rB ( x) = 9−e x je+m . Далее m=1
В соответствии с (6) имеем исходные данные для восьми вариантов построения двухдо-
рожечной шкалы
{l2д} = {max[0, 336], max[48, 288], max[96, 240], max[144, 192], max[192, 144],
max[240,96], max[288, 48], max[336, 0]} ={336, 288, 240, 192, 192, 240, 288, 336} .
Из (7) определяется минимальное увеличение длины двухдорожечной ЛПСКШ
l2д = {max[ je − j1, jn − je+1]} → min = min{336, 288, 240, 192, 192, 240, 288, 336} = 192.
Для рассматриваемого случая je − j1 = 144 , а jn − je+1 = 192 . С учетом этих значений по выражению (14) рассчитывается значение коэффициента разбиения e = 4 . Тогда
rA ( x) = 1+ x48 + x96 + x144 и rB ( x) = x192 + x240 + x288 + x336 + x384 = x192 (1+ x48 + x96 + x144 + x192 ) .
Следовательно, относительное увеличение длины двухдорожечной ЛПСКШ
V2д
=
l2д M
=
192 511
=
0,
37
(37
%)
.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 5
34 А. А. Ожиганов, Жуань Чжипэн
Для построения модели трехдорожечной ЛПСКШ полином r ( x) разбивается со
e g−e
∑ ∑стороны младших степеней на три части: rA ( x) = x jm , rB ( x) = x je+m m=1 m=1
и
∑rC ( x) = 8−g x jg+m . Далее определяются значения е и g. m=1 В соответствии с (8) имеем исходные данные для построения трехдорожечной шкалы
{l3д} = {max[0, 0, 288], max[0, 48, 240], ..., max[96, 96, 96], ...,
..., max[240, 48, 0], max[288, 0, 0]} ={288, 240,..., 96, ..., 240, 288} .
Из (9) определяется минимальное увеличение длины трехдорожечной ЛПСКШ
{ }l3д = max[ je − j1, jg − je+1, jn − jg+1] → min = min{288, 240,...,96,..., 240, 288} = 96 .
Для данного случая je − j1 = 96 , jg − je+1 = 96 , а jn − jg+1 = 96 . С учетом этих
значений по выражению (14) рассчитываются значения коэффициентов разбиения e = 3 и
g = 6 . Тогда rA ( x) = 1 + x48 + x96 , rB ( x) = x144 + x192 + x240 = x144 (1 + x48 + x96 ) , а
rC ( x) = x288 + x336 + x384 = x288 (1 + x48 + x96 ) . Таким образом, относительное увеличение
длины
трехдорожечной
ЛПСКШ
V3д
=
l3д M
=
96 511
≈
0,19
(19
%)
.
Для построения модели четырехдорожечной ЛПСКШ полином r ( x) разбивается со
e g−e
∑ ∑стороны младших степеней на четыре части: rA ( x) = x jm , rB ( x) = x je+m , m=1 m=1
∑ ∑( )rC x = k−g x jg+m
и
rD
(x)
8−k
=
x jk+m .
Далее определяются
значения
e,
g
и k.
m=1 m=1
Согласно (10), имеем исходные данные для построения четырехдорожечной шкалы
{l4д} = {max[0, 0, 0, 240], max[0, 0, , 48 192], ... max[96, 96 48, 0], ...,
..., max[192, 48, 0, 0], max[0, 0, 0, 240]} ={240, 192, ..., 96, ..., 192, 240} .
Из (11) определяется минимальное увеличение длины четырехдорожечной ЛПСКШ
{ }l4д = max[ je − j1, jg − je+1, jk − jg+1, jn − jk+1] → min = min {240,192,...,96,...,192, 240} = 96 .
Для рассматриваемого случая je − j1 = 96 , jg − je+1 = 96 , jk − jg+1 = 48 , а jn − jk+1 = 0 .
С учетом этих значений по выражению (14) рассчитываются значения коэффициентов
разбиения e = 3 , g = 6 и k = 8 . Тогда rA ( x) = 1 + x48 + x96 , rB ( x) = x144 + x192 + x240 =
= x144 (1 + x48 + x96 ) , rC ( x) = x288 + x336 = x288 (1 + x48 ) и rD ( x) = x384 . Следовательно,
относительное
увеличение
длины
четырехдорожечной
ЛПСКШ
V4д
=
l4д M
=
96 511
≈
0,19 (19 %) .
Можно видеть, что V3д = V4д . Таким образом, трех- и четырехдорожечный варианты
построения ЛПСКШ оказались эквивалентными с точки зрения минимального увеличения
длины шкалы для заданного размещения на шкале СЭ. Очевидно, что для практической
реализации наиболее предпочтительным является трехдорожечный вариант выполнения
шкалы.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 5
Критерий выбора длины линейной псевдослучайной кодовой шкалы
35
На рисунке приведен пример девятиразрядной трехдорожечной ЛПСКШ с размещением
СЭ в соответствии с полиномами rA ( x) = 1 + x48 + x96 , rB ( x) = x144 + x192 + x240 =
= x144 (1 + x48 + x96 ) , rC ( x) = x288 + x336 + x384 = x288 (1 + x48 + x96 ) .
СЭ1 A0 A1
…
δ СЭ2 A48
СЭ3
… A96
… A607
0 0 0 0 … 0 0 0 0… 0 0 0 0… 0 0 0 0
В0 СЭ4 В1 00
… 0 0…
В48СЭ5
… В96СЭ6
… В607
0 0 0 0… 0 0 0 0… 0 0 0 0
СЭ7 С0
С1
…
С48СЭ8
СЭ9
… С96
… С607
0 0 0 0 … 0 0 0 0… 0 0 0 0 …0 0 0 0
Предложенный критерий выбора минимального увеличения длины псевдослучайной кодовой шкалы может быть положен в основу построения преобразователей линейных перемещений, работающих по методу считывания.
СПИСОК ЛИТЕРАТУРЫ
1. Ожиганов А. А. Псевдослучайные кодовые шкалы для преобразователей линейных перемещений // Изв. вузов. Приборостроение. 1995. Т. 38, № 11—12. С. 37—39.
2. Домрачев В. Г., Мейко Б. С. Цифровые преобразователи угла: принципы построения, теория точности, методы контроля. М.: Энергоатомиздат, 1984. 328 с.
3. Ожиганов А. А., Жуань Чжипэн. Использование псевдослучайных последовательностей при построении кодовых шкал для преобразователей линейных перемещений // Изв. вузов. Приборостроение. 2008. Т. 51, № 7. С. 28—33.
4. Макуильямс Ф. Д., Слоан Н. Д. Псевдослучайные последовательности и таблицы // ТИИЭР. 1976. Т. 64, № 12. С. 80—95.
5. Ожиганов А. А. Алгоритм размещения считывающих элементов на псевдослучайной кодовой шкале // Изв. вузов. Приборостроение. 1994. Т. 37, № 2. С. 22—27.
Сведения об авторах
Александр Аркадьевич Ожиганов — д-р техн. наук, профессор; Санкт-Петербургский государственный
университет информационных технологий, механики и оптики, ка-
федра вычислительной техники; E-mail: ojiganov@mail.ifmo.ru
Жуань Чжипэн
— аспирант; Санкт-Петербургский государственный университет ин-
формационных технологий, механики и оптики, кафедра вычисли-
тельной техники; E-mail: zhipeng_ruan@mail.ru
Рекомендована кафедрой вычислительной техники
Поступила в редакцию 16.12.09 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 5