ПРИМЕНЕНИЕ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ДЕ БРЕЙНА ДЛЯ ПОСТРОЕНИЯ ПСЕВДОРЕГУЛЯРНЫХ КОДОВЫХ ШКАЛ
А.А. Ожиганов, И.Д. Захаров
УДК 621.3.085
ПРИМЕНЕНИЕ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ДЕ БРЕЙНА ДЛЯ ПОСТРОЕНИЯ ПСЕВДОРЕГУЛЯРНЫХ КОДОВЫХ ШКАЛ
А.А. Ожиганов, И.Д. Захаров
Предложен алгоритм получения последовательностей де Брейна заданной степени на основе одноименных графов. Приведены примеры построения кодирующих масок псевдорегулярных кодовых шкал с использованием полученных последовательностей. Ключевые слова: последовательность де Брейна, граф де Брейна, кодовая шкала, кодовая дорожка, рекурсивная кодовая шкала, псевдослучайная кодовая шкала, нелинейная кодовая шкала, псевдорегулярная кодовая шкала.
Введение
Цифровые преобразователи угла (ЦПУ), построенные по методу параллельного считывания, являются важной частью многих современных вычислительных устройств. Основным элементом таких преобразователей является кодовая шкала (КШ). Классические КШ имеют кодирующую маску, выполненную в обыкновенном двоичном коде или в коде Грея, где каждому разряду шкалы соответствует своя кодовая дорожка (КД) [1].
В работах [2–12] рассмотрены рекурсивные кодовые шкалы (РКШ), разновидностями которых являются псевдослучайные (ПСКШ), композиционные (ККШ), нелинейные (НКШ) и псевдорегулярные кодовые шкалы (ПРКШ). Отличительной особенностью всех РКШ является то, что все они строятся с использованием линейных или нелинейных рекуррентных двоичных последовательностей (РП) и имеют одну или две информационные КД. В качестве РП, используемых для построения кодирующих масок РКШ, применяются псевдослучайные двоичные последовательности максимального периода (М-последовательности) или их комбинации. Число М-последовательностей NM (L) / n , где (L) –
Научно-технический вестник информационных технологий, механики и оптики, 2012, № 2 (78)
69
ПРИМЕНЕНИЕ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ДЕ БРЕЙНА ДЛЯ ПОСТРОЕНИЯ …
функция Эйлера, L 2n 1 , а n – степень примитивного полинома, положенного в основу построения М-последовательности и одновременно разрядность РКШ.
В свою очередь, число М-последовательностей определяет множество разнообразных кодирующих масок РКШ.
Наиболее перспективными из РКШ, нашедшими практическое применение в выпускаемых в ОАО «Авангард» фотоэлектрических ЦПУ, являются ПРКШ. Однако число кодирующих масок ПРКШ для заданной степени n определяется величиной NM .
Известны двоичные последовательности де Брейна [13], число которых для заданного n, NDB 22n1n . В таблице приведено число М-последовательностей и последовательностей де Брейна для различных значений n.
n NM NDB 211
322
4 2 16
5 6 2048
… 10 60 2503
Таблица. Число М-последовательностей и последовательностей де Брейна для различных значений n
Анализ таблицы показывает, что последовательностей де Брейна несоизмеримо больше по сравнению с М-последовательностями. Например, для n=5 существует 2048 последовательностей де Брейна и всего 6 М-последовательностей. Следовательно, при использовании последовательностей де Брейна для построения кодирующих масок ПРКШ их можно получить 2048, тогда как использование Мпоследовательностей позволит реализовать всего 6 различных кодирующих масок. Большее число последовательностей де Брейна по сравнению с М-последовательностями для одного и того же n дает дополнительные возможности при проектировании высокоразрядных малогабаритных ЦПУ с учетом различных конструкторско-технологических ограничений.
Из литературных источников [14, 15] известны алгебраические алгоритмы нахождения последовательностей де Брейна определенной степени. Однако эти алгоритмы либо не дают их полного множества, либо малоэффективны и ресурсоемки.
В настоящей работе предлагается алгоритм, лишенный указанных выше недостатков и позволяющий последовательно генерировать все двоичные последовательности де Брейна заданной степени.
Алгоритм получения последовательностей де Брейна
Алгоритм состоит из двух этапов. На первом этапе формируется матрица смежности соответствующего графа де Брейна, а на втором этапе по полученной матрице смежности находятся собственно последовательности.
Одним из представлений последовательностей де Брейна являются одноименные графы. Это направленные графы, в вершинах которых находятся все возможные слова длины n, составленные из заданного алфавита (для двоичного алфавита – всего 2n вершин). Между двумя вершинами x=(x0, …, xn–1) и y=(y0, …, yn–1) есть направленная связь x→y тогда и только тогда, когда xi=yi+1, i=0, …, n–2 . Пример графа де Брейна для n=3 приведен на рис. 1.
Визуальная интерпретация графа де Брейна весьма наглядна для восприятия ее человеком, однако на практике в алгоритмах чаще всего используется матрица смежности. Квадратная матрица A размерности 2n×2n называется матрицей смежности графа де Брейна Gn тогда, когда каждый ее элемент отражает наличие связи между соответствующими вершинами. Так, например, если элемент aij матрицы A равен единице, значит, существует ребро от вершины vi к вершине vj. Иначе направленной связи между вершинами нет. Так, например, в графе де Брейна для n=3 (рис. 1) существуют направленные связи от вершин v2 = (010) и v6 = (110) к вершине v5 = (101), а именно v2 → v5 и v6 → v5.
Схема алгоритма формирования матрицы смежности приведена на рис. 2. Сначала, в соответствии с заданной степенью n, формируется двоичная маска индекса для каждой вершины, т.е. mask=2n–1. Это достигается побитовым сдвигом изначально нулевой переменной mask с последующим инкрементом на единицу. После формирования маски начинается построчное заполнение матрицы смежности A. Для каждой из 2n строк матрицы элементам с индексами (2i) & mask и (2i) & mask +1 (здесь i – индекс текущей строки) присваиваются значения 1. Таким образом, устанавливается наличие всех направленных связей от вершины i.
70 Научно-технический вестник информационных технологий, механики и оптики,
2012, № 2 (78)
А.А. Ожиганов, И.Д. Захаров
v4 100
000 v0
v2 010
v1 001
v6 110
101 v5
v3 011
v7 111
Рис. 1. Граф де Брейна для n = 3
.
НАЧАЛО
mask := 0
Для всех i от 0 до n-1
mask := 2×mask + 1
Для всех i от 0 до 2n-1.
A [ i, (2i) & mask ] = 1 A [ i, (2i) & mask + 1 ] = 1
A [0, 0] = 0 A [n-1, n-1] = 0
КОНЕЦ
Рис. 2. Схема алгоритма формирования матрицы смежности
Рассмотрим вершины с индексами 0 и n–1. Так как (2×0) & mask=0 и (2(n–1)) & mask+1=n–1, полученная в результате матрица смежности будет содержать две кольцевые связи. Для приведения матрицы к корректному виду их необходимо удалить. Так, для n=3 в матрице A обнуляются элементы, соответствующие кольцевым связям вершин с индексами 0 и 7. Пример окончательно сформированной матрицы смежности для n=3 приведен ниже.
Научно-технический вестник информационных технологий, механики и оптики, 2012, № 2 (78)
71
ПРИМЕНЕНИЕ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ДЕ БРЕЙНА ДЛЯ ПОСТРОЕНИЯ …
0 1 0 0 0 0 0 0
0 0 1 1 0 0 0 0
0 0 0 0 1 1 0 0
A3
0 1
0 1
0 0
0 0
0 0
0 0
1 0
1 0
0 0 1 1 0 0 0 0
0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0
Второй этап алгоритма представляет собой рекурсивную процедуру над строкой i матрицы смеж-
ности A, полученной ранее. Схема алгоритма рекурсивной процедуры получения последовательностей
показана на рис. 3. В качестве параметров в процедуру передается индекс текущей строки i (изначально
i=0) и текущее состояние выходной последовательности. Затем осуществляется проход по строке с ин-
дексом i матрицы смежности A в поисках элемента aij =1, где j – индекс текущего столбца. Если находится элемент aij =1 (есть ребро из вершины i в вершину j), следует добавить индекс i в
выходную последовательность. Затем обнуляется вся строка i (далее нас не интересуют ребра графа из
вершины i) и столбцы i и j (далее не будут рассматриваться ребра в вершинах i и j). Данная процедура
вызывается с индексом строки j в качестве параметра.
2n–1
– –
Рис. 3. Схема алгоритма рекурсивной процедуры поиска последовательностей де Брейна на основе матрицы смежности
Если в текущей строке не осталось единичных элементов, выходная последовательность при условии, что ее длина равна 2n, сохраняется, а сама процедура завершается, возвращая управление на предыдущий уровень рекурсии.
Результатом выполнения рассмотренного алгоритма для n=3 являются следующие последовательности десятичных чисел, представляющие собой индексы вершин графа де Брейна: result1={1, 2, 5, 3, 7, 6, 4, 0}, result2={1, 3, 7, 6, 5, 2, 4, 0}. Осуществив деление по модулю 2 десятичных чисел для всех полученных результатов, найдем искомые двоичные последовательности де Брейна. Для n=3, это будут последовательности result1={1, 2, 5, 3, 7, 6, 4, 0}=10111000 и result2={1, 3, 7, 6, 5, 2, 4, 0}=11101000.
Ниже приводится пример использования последовательностей де Брейна для построения ПРКШ.
Пример псевдорегулярной кодовой шкалы
На рис. 4 приведена линейная развертка шестиразрядной ПРКШ с двумя информационными КД. В примере старшая КД 1 шкалы построена в соответствии с символами последовательности де Брейна 00010111 длиной L=2n=23=8, причем на КД 1 шкалы наносится только один период последовательности. Последовательность длиной L=2n определяет число квантов КД 1 шкалы, которое в нашем случае равно 8.
72 Научно-технический вестник информационных технологий, механики и оптики,
2012, № 2 (78)
А.А. Ожиганов, И.Д. Захаров
Отсюда величина кванта δ=360º/L=360º/8=45º. В примере размещение считывающих элементов (СЭ) 3, 4 и 5 вдоль КД 1 осуществляется с шагом, равным величине одного кванта δ КД по ходу часовой стрелки.
6 7 8 2
2
345
1
Рис. 4. Двухдорожечная псевдорегулярная кодовая шкала
Младшая КД 2 шкалы построена в соответствии с символами той же последовательности де Брейна, что и старшая КД. Причем на КД 2 шкалы наносятся 8 периодов последовательности, определяющих число квантов младшей КД шкалы, которое в данном примере равно 64. Отсюда величина кванта КД 2 δ2=360º/L2=360º/64=5,625º. В примере размещение СЭ 6, 7 и 8 вдоль младшей КД 2 осуществляется с шагом, равным величине (δ + δ2)=45º +5,625º =50,625º по ходу часовой стрелки.
В нашем примере суммарная разрядность, обеспечиваемая двумя КД при рассмотренном выше размещении СЭ, будет равна 6.
Фиксируя считывающими элементами 3–8 последовательно кодовую комбинацию при перемещении ПРКШ циклически на один элементарный участок (квант) младшей КД δ2, например, против хода часовой стрелки, получаем 64 различных шестиразрядных кодовых комбинаций, которые соответствуют 64 угловым положениям шкалы.
В рассматриваемом примере для построения старшей и младшей КД использована одна и та же двоичная последовательность де Брейна. Однако в общем случае допускается использование как одинаковых, так и различных последовательностей, причем с увеличением разрядности двухдорожечной ПРКШ число вариантов ее построения также возрастает.
Заключение
В работе представлен алгоритм генерации всех двоичных последовательностей де Брейна заданной степени. Показано, что использование таких последовательностей дает дополнительные возможности для выбора наиболее технологичного варианта построения псевдорегулярной кодовой шкалы (и, как следствие, цифровых преобразователей угла на ее основе), что связано с возможностью многовариантного размещения на шкале считывающих элементов и большим разнообразием кодирующих масок.
Литература
1. Домрачев В.Г., Мейко Б.С. Цифровые преобразователи угла: Принципы построения, теория точности, методы контроля. – М.: Энергоатомиздат, 1984. – 328 с.
2. Азов А.К., Ожиганов А.А., Тарасюк М.В. Рекурсивные кодовые шкалы // Информационные технологии. – 1998. – № 6. – С. 39–43.
3. Ожиганов А.А. Псевдослучайные кодовые шкалы // Изв. вузов. Приборостроение. – 1987. – Т. 30. – № 2. – С. 40–43.
4. Ожиганов А.А. Корректирующие возможности псевдослучайных кодовых шкал // Изв. вузов. Приборостроение. – 1988. – Т. 31. – № 7. – С. 26–30.
5. Ожиганов А.А., Тарасюк М.В. Композиционные кодовые шкалы // Изв. вузов. Приборостроение. – 1994. – Т. 37. – № 5, 6. – С. 26–29.
6. Ожиганов А.А. Алгоритм размещения корректирующих считывающих элементов на псевдослучайной кодовой шкале // Изв. вузов. Приборостроение. – 1995. – Т. 38. – № 7, 8. – С. 33–36.
7. Ожиганов А.А. Анализ кодовых шкал преобразователей угла // Изв. вузов. Приборостроение. – 1996. – Т. 39. – № 4. – С. 32–35.
8. Ожиганов А.А., Тарасюк М.В. Преобразование присоединенных псевдослучайных кодов в обыкновенный двоичный код // Изв. вузов. Приборостроение. – 1997. – Т. 40. – № 5. – С. 47–52.
9. Азов А.К., Ожиганов А.А. Устранение неоднозначности считывания в преобразователях перемещения с рекурсивными кодовыми шкалами // Информационные технологии. – 2001. – № 6. – С. 39–42.
10. Азов А.К., Ожиганов А.А., Тарасюк М.В. Преобразование композиционных кодов в обыкновенный двоичный код // Информационные технологии. – 2003. – № 1. – С. 47–51.
11. Ожиганов А.А., Прибыткин П.А. Псевдорегулярные кодовые шкалы для цифровых преобразователей угла // Научно-технический вестник СПбГУ ИТМО. – 2011. – № 1 (71) – С. 67–72.
12. Ожиганов А.А., Захаров И.Д. Использование порождающих полиномов M-последовательностей при построении псевдослучайных кодовых шкал // Изв. вузов. Приборостроение. – 2011. – Т. 54. – № 6. – С. 49–56.
13. De Bruijn N.G. A combinatorial problem // Koninklijke Nederlandse Akademie v. Wetenschappen. – 1946. – V. 49. – P. 758–764.
Научно-технический вестник информационных технологий, механики и оптики, 2012, № 2 (78)
73
ЗАДАЧИ РАЗВИТИЯ IT-ИНФРАСТРУКТУРЫ ПРЕДПРИЯТИЯ
14. Abraham Lempel. On a Homomorphism of the de Bruijn Graph and Its Applications to the Design of Feedback Shift Registers // IEEE Transactions on Computers. – 1970. – V. C-19. – № 12. – P. 1204–1209.
15. Abbas M.Alhakim. A simple combinatorial algorithm for de Bruijn sequences // The American Mathematical Monthly. – 2010. – V. 117. – № 8. – P. 728–732.
Ожиганов Александр Аркадьевич Захаров Илья Дмитриевич
– Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, доктор технических наук, профессор, ojiganov@mail.ifmo.ru
– Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, аспирант, zakharov_ilya@hotmail.com
74 Научно-технический вестник информационных технологий, механики и оптики,
2012, № 2 (78)
УДК 621.3.085
ПРИМЕНЕНИЕ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ДЕ БРЕЙНА ДЛЯ ПОСТРОЕНИЯ ПСЕВДОРЕГУЛЯРНЫХ КОДОВЫХ ШКАЛ
А.А. Ожиганов, И.Д. Захаров
Предложен алгоритм получения последовательностей де Брейна заданной степени на основе одноименных графов. Приведены примеры построения кодирующих масок псевдорегулярных кодовых шкал с использованием полученных последовательностей. Ключевые слова: последовательность де Брейна, граф де Брейна, кодовая шкала, кодовая дорожка, рекурсивная кодовая шкала, псевдослучайная кодовая шкала, нелинейная кодовая шкала, псевдорегулярная кодовая шкала.
Введение
Цифровые преобразователи угла (ЦПУ), построенные по методу параллельного считывания, являются важной частью многих современных вычислительных устройств. Основным элементом таких преобразователей является кодовая шкала (КШ). Классические КШ имеют кодирующую маску, выполненную в обыкновенном двоичном коде или в коде Грея, где каждому разряду шкалы соответствует своя кодовая дорожка (КД) [1].
В работах [2–12] рассмотрены рекурсивные кодовые шкалы (РКШ), разновидностями которых являются псевдослучайные (ПСКШ), композиционные (ККШ), нелинейные (НКШ) и псевдорегулярные кодовые шкалы (ПРКШ). Отличительной особенностью всех РКШ является то, что все они строятся с использованием линейных или нелинейных рекуррентных двоичных последовательностей (РП) и имеют одну или две информационные КД. В качестве РП, используемых для построения кодирующих масок РКШ, применяются псевдослучайные двоичные последовательности максимального периода (М-последовательности) или их комбинации. Число М-последовательностей NM (L) / n , где (L) –
Научно-технический вестник информационных технологий, механики и оптики, 2012, № 2 (78)
69
ПРИМЕНЕНИЕ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ДЕ БРЕЙНА ДЛЯ ПОСТРОЕНИЯ …
функция Эйлера, L 2n 1 , а n – степень примитивного полинома, положенного в основу построения М-последовательности и одновременно разрядность РКШ.
В свою очередь, число М-последовательностей определяет множество разнообразных кодирующих масок РКШ.
Наиболее перспективными из РКШ, нашедшими практическое применение в выпускаемых в ОАО «Авангард» фотоэлектрических ЦПУ, являются ПРКШ. Однако число кодирующих масок ПРКШ для заданной степени n определяется величиной NM .
Известны двоичные последовательности де Брейна [13], число которых для заданного n, NDB 22n1n . В таблице приведено число М-последовательностей и последовательностей де Брейна для различных значений n.
n NM NDB 211
322
4 2 16
5 6 2048
… 10 60 2503
Таблица. Число М-последовательностей и последовательностей де Брейна для различных значений n
Анализ таблицы показывает, что последовательностей де Брейна несоизмеримо больше по сравнению с М-последовательностями. Например, для n=5 существует 2048 последовательностей де Брейна и всего 6 М-последовательностей. Следовательно, при использовании последовательностей де Брейна для построения кодирующих масок ПРКШ их можно получить 2048, тогда как использование Мпоследовательностей позволит реализовать всего 6 различных кодирующих масок. Большее число последовательностей де Брейна по сравнению с М-последовательностями для одного и того же n дает дополнительные возможности при проектировании высокоразрядных малогабаритных ЦПУ с учетом различных конструкторско-технологических ограничений.
Из литературных источников [14, 15] известны алгебраические алгоритмы нахождения последовательностей де Брейна определенной степени. Однако эти алгоритмы либо не дают их полного множества, либо малоэффективны и ресурсоемки.
В настоящей работе предлагается алгоритм, лишенный указанных выше недостатков и позволяющий последовательно генерировать все двоичные последовательности де Брейна заданной степени.
Алгоритм получения последовательностей де Брейна
Алгоритм состоит из двух этапов. На первом этапе формируется матрица смежности соответствующего графа де Брейна, а на втором этапе по полученной матрице смежности находятся собственно последовательности.
Одним из представлений последовательностей де Брейна являются одноименные графы. Это направленные графы, в вершинах которых находятся все возможные слова длины n, составленные из заданного алфавита (для двоичного алфавита – всего 2n вершин). Между двумя вершинами x=(x0, …, xn–1) и y=(y0, …, yn–1) есть направленная связь x→y тогда и только тогда, когда xi=yi+1, i=0, …, n–2 . Пример графа де Брейна для n=3 приведен на рис. 1.
Визуальная интерпретация графа де Брейна весьма наглядна для восприятия ее человеком, однако на практике в алгоритмах чаще всего используется матрица смежности. Квадратная матрица A размерности 2n×2n называется матрицей смежности графа де Брейна Gn тогда, когда каждый ее элемент отражает наличие связи между соответствующими вершинами. Так, например, если элемент aij матрицы A равен единице, значит, существует ребро от вершины vi к вершине vj. Иначе направленной связи между вершинами нет. Так, например, в графе де Брейна для n=3 (рис. 1) существуют направленные связи от вершин v2 = (010) и v6 = (110) к вершине v5 = (101), а именно v2 → v5 и v6 → v5.
Схема алгоритма формирования матрицы смежности приведена на рис. 2. Сначала, в соответствии с заданной степенью n, формируется двоичная маска индекса для каждой вершины, т.е. mask=2n–1. Это достигается побитовым сдвигом изначально нулевой переменной mask с последующим инкрементом на единицу. После формирования маски начинается построчное заполнение матрицы смежности A. Для каждой из 2n строк матрицы элементам с индексами (2i) & mask и (2i) & mask +1 (здесь i – индекс текущей строки) присваиваются значения 1. Таким образом, устанавливается наличие всех направленных связей от вершины i.
70 Научно-технический вестник информационных технологий, механики и оптики,
2012, № 2 (78)
А.А. Ожиганов, И.Д. Захаров
v4 100
000 v0
v2 010
v1 001
v6 110
101 v5
v3 011
v7 111
Рис. 1. Граф де Брейна для n = 3
.
НАЧАЛО
mask := 0
Для всех i от 0 до n-1
mask := 2×mask + 1
Для всех i от 0 до 2n-1.
A [ i, (2i) & mask ] = 1 A [ i, (2i) & mask + 1 ] = 1
A [0, 0] = 0 A [n-1, n-1] = 0
КОНЕЦ
Рис. 2. Схема алгоритма формирования матрицы смежности
Рассмотрим вершины с индексами 0 и n–1. Так как (2×0) & mask=0 и (2(n–1)) & mask+1=n–1, полученная в результате матрица смежности будет содержать две кольцевые связи. Для приведения матрицы к корректному виду их необходимо удалить. Так, для n=3 в матрице A обнуляются элементы, соответствующие кольцевым связям вершин с индексами 0 и 7. Пример окончательно сформированной матрицы смежности для n=3 приведен ниже.
Научно-технический вестник информационных технологий, механики и оптики, 2012, № 2 (78)
71
ПРИМЕНЕНИЕ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ДЕ БРЕЙНА ДЛЯ ПОСТРОЕНИЯ …
0 1 0 0 0 0 0 0
0 0 1 1 0 0 0 0
0 0 0 0 1 1 0 0
A3
0 1
0 1
0 0
0 0
0 0
0 0
1 0
1 0
0 0 1 1 0 0 0 0
0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0
Второй этап алгоритма представляет собой рекурсивную процедуру над строкой i матрицы смеж-
ности A, полученной ранее. Схема алгоритма рекурсивной процедуры получения последовательностей
показана на рис. 3. В качестве параметров в процедуру передается индекс текущей строки i (изначально
i=0) и текущее состояние выходной последовательности. Затем осуществляется проход по строке с ин-
дексом i матрицы смежности A в поисках элемента aij =1, где j – индекс текущего столбца. Если находится элемент aij =1 (есть ребро из вершины i в вершину j), следует добавить индекс i в
выходную последовательность. Затем обнуляется вся строка i (далее нас не интересуют ребра графа из
вершины i) и столбцы i и j (далее не будут рассматриваться ребра в вершинах i и j). Данная процедура
вызывается с индексом строки j в качестве параметра.
2n–1
– –
Рис. 3. Схема алгоритма рекурсивной процедуры поиска последовательностей де Брейна на основе матрицы смежности
Если в текущей строке не осталось единичных элементов, выходная последовательность при условии, что ее длина равна 2n, сохраняется, а сама процедура завершается, возвращая управление на предыдущий уровень рекурсии.
Результатом выполнения рассмотренного алгоритма для n=3 являются следующие последовательности десятичных чисел, представляющие собой индексы вершин графа де Брейна: result1={1, 2, 5, 3, 7, 6, 4, 0}, result2={1, 3, 7, 6, 5, 2, 4, 0}. Осуществив деление по модулю 2 десятичных чисел для всех полученных результатов, найдем искомые двоичные последовательности де Брейна. Для n=3, это будут последовательности result1={1, 2, 5, 3, 7, 6, 4, 0}=10111000 и result2={1, 3, 7, 6, 5, 2, 4, 0}=11101000.
Ниже приводится пример использования последовательностей де Брейна для построения ПРКШ.
Пример псевдорегулярной кодовой шкалы
На рис. 4 приведена линейная развертка шестиразрядной ПРКШ с двумя информационными КД. В примере старшая КД 1 шкалы построена в соответствии с символами последовательности де Брейна 00010111 длиной L=2n=23=8, причем на КД 1 шкалы наносится только один период последовательности. Последовательность длиной L=2n определяет число квантов КД 1 шкалы, которое в нашем случае равно 8.
72 Научно-технический вестник информационных технологий, механики и оптики,
2012, № 2 (78)
А.А. Ожиганов, И.Д. Захаров
Отсюда величина кванта δ=360º/L=360º/8=45º. В примере размещение считывающих элементов (СЭ) 3, 4 и 5 вдоль КД 1 осуществляется с шагом, равным величине одного кванта δ КД по ходу часовой стрелки.
6 7 8 2
2
345
1
Рис. 4. Двухдорожечная псевдорегулярная кодовая шкала
Младшая КД 2 шкалы построена в соответствии с символами той же последовательности де Брейна, что и старшая КД. Причем на КД 2 шкалы наносятся 8 периодов последовательности, определяющих число квантов младшей КД шкалы, которое в данном примере равно 64. Отсюда величина кванта КД 2 δ2=360º/L2=360º/64=5,625º. В примере размещение СЭ 6, 7 и 8 вдоль младшей КД 2 осуществляется с шагом, равным величине (δ + δ2)=45º +5,625º =50,625º по ходу часовой стрелки.
В нашем примере суммарная разрядность, обеспечиваемая двумя КД при рассмотренном выше размещении СЭ, будет равна 6.
Фиксируя считывающими элементами 3–8 последовательно кодовую комбинацию при перемещении ПРКШ циклически на один элементарный участок (квант) младшей КД δ2, например, против хода часовой стрелки, получаем 64 различных шестиразрядных кодовых комбинаций, которые соответствуют 64 угловым положениям шкалы.
В рассматриваемом примере для построения старшей и младшей КД использована одна и та же двоичная последовательность де Брейна. Однако в общем случае допускается использование как одинаковых, так и различных последовательностей, причем с увеличением разрядности двухдорожечной ПРКШ число вариантов ее построения также возрастает.
Заключение
В работе представлен алгоритм генерации всех двоичных последовательностей де Брейна заданной степени. Показано, что использование таких последовательностей дает дополнительные возможности для выбора наиболее технологичного варианта построения псевдорегулярной кодовой шкалы (и, как следствие, цифровых преобразователей угла на ее основе), что связано с возможностью многовариантного размещения на шкале считывающих элементов и большим разнообразием кодирующих масок.
Литература
1. Домрачев В.Г., Мейко Б.С. Цифровые преобразователи угла: Принципы построения, теория точности, методы контроля. – М.: Энергоатомиздат, 1984. – 328 с.
2. Азов А.К., Ожиганов А.А., Тарасюк М.В. Рекурсивные кодовые шкалы // Информационные технологии. – 1998. – № 6. – С. 39–43.
3. Ожиганов А.А. Псевдослучайные кодовые шкалы // Изв. вузов. Приборостроение. – 1987. – Т. 30. – № 2. – С. 40–43.
4. Ожиганов А.А. Корректирующие возможности псевдослучайных кодовых шкал // Изв. вузов. Приборостроение. – 1988. – Т. 31. – № 7. – С. 26–30.
5. Ожиганов А.А., Тарасюк М.В. Композиционные кодовые шкалы // Изв. вузов. Приборостроение. – 1994. – Т. 37. – № 5, 6. – С. 26–29.
6. Ожиганов А.А. Алгоритм размещения корректирующих считывающих элементов на псевдослучайной кодовой шкале // Изв. вузов. Приборостроение. – 1995. – Т. 38. – № 7, 8. – С. 33–36.
7. Ожиганов А.А. Анализ кодовых шкал преобразователей угла // Изв. вузов. Приборостроение. – 1996. – Т. 39. – № 4. – С. 32–35.
8. Ожиганов А.А., Тарасюк М.В. Преобразование присоединенных псевдослучайных кодов в обыкновенный двоичный код // Изв. вузов. Приборостроение. – 1997. – Т. 40. – № 5. – С. 47–52.
9. Азов А.К., Ожиганов А.А. Устранение неоднозначности считывания в преобразователях перемещения с рекурсивными кодовыми шкалами // Информационные технологии. – 2001. – № 6. – С. 39–42.
10. Азов А.К., Ожиганов А.А., Тарасюк М.В. Преобразование композиционных кодов в обыкновенный двоичный код // Информационные технологии. – 2003. – № 1. – С. 47–51.
11. Ожиганов А.А., Прибыткин П.А. Псевдорегулярные кодовые шкалы для цифровых преобразователей угла // Научно-технический вестник СПбГУ ИТМО. – 2011. – № 1 (71) – С. 67–72.
12. Ожиганов А.А., Захаров И.Д. Использование порождающих полиномов M-последовательностей при построении псевдослучайных кодовых шкал // Изв. вузов. Приборостроение. – 2011. – Т. 54. – № 6. – С. 49–56.
13. De Bruijn N.G. A combinatorial problem // Koninklijke Nederlandse Akademie v. Wetenschappen. – 1946. – V. 49. – P. 758–764.
Научно-технический вестник информационных технологий, механики и оптики, 2012, № 2 (78)
73
ЗАДАЧИ РАЗВИТИЯ IT-ИНФРАСТРУКТУРЫ ПРЕДПРИЯТИЯ
14. Abraham Lempel. On a Homomorphism of the de Bruijn Graph and Its Applications to the Design of Feedback Shift Registers // IEEE Transactions on Computers. – 1970. – V. C-19. – № 12. – P. 1204–1209.
15. Abbas M.Alhakim. A simple combinatorial algorithm for de Bruijn sequences // The American Mathematical Monthly. – 2010. – V. 117. – № 8. – P. 728–732.
Ожиганов Александр Аркадьевич Захаров Илья Дмитриевич
– Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, доктор технических наук, профессор, ojiganov@mail.ifmo.ru
– Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, аспирант, zakharov_ilya@hotmail.com
74 Научно-технический вестник информационных технологий, механики и оптики,
2012, № 2 (78)