Способ формирования псевдослучайной двоичной последовательности для однокоординатных датчиков перемещений

Изобретение относится к областям информатики и вычислительной техники и может быть использовано для генерации псевдослучайной двоичной последовательности (ПСДП) с различным кодовым циклом.

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

Наибольшее распространение получили линейные ПСП: М-последовательности, последовательности Голда, Касами, а также нелинейные ПСП: последовательности (циклы) де Брёйна, и т.п.

В приборостроении, в частности при разработке шкал однокоординатных датчиков перемещений (линейных, угловых), наибольший интерес представляют собой следующие свойства псевдослучайных последовательностей чисел:

- свойство «окна»: если окно заданной ширины перемещается вдоль последовательности, то каждый набор чисел будет видим только один раз, т.е. каждый видимый набор уникален в исходной последовательности,

- свойство «цикличности»: последовательность является периодической и циклически замкнутой, т.е. циклически бесконечной.

В настоящее время существует несколько основных методов формирования последовательностей чисел де Брёйна.

- методы основанные на исследовании и поиске решений циклического графа де Брёйна [1] фиг. 1;

- методы, основанные на использовании сдвиговых регистров с нелинейной обратной связью для генерации последовательностей, или на исследовании полиномиальных зависимостей, лежащих в их основе [2] фиг. 2.

Существует способ, основанный на исследовании и поиске решений циклического графа де Брёйна [1]. В общем случае число N_DB последовательностей де Брёйна определяется выражением

где k - мощность множества символов исходного алфавита A_k={a₁, а₂, …, a_k};

n - заданная мощность подмножества символов слова, состоящего из символов исходного алфавита.

В таблице 1. приведены значения числа N_DB последовательностей де Брёйна для некоторых величин k и n.

Как недостаток можно отметить и это видно из таблицы, что уже при относительно небольших значениях параметров k и n число последовательностей де Брёйна резко возрастает.

Известен способ, описанный в брошюре [1] - Б.И. Крыжановский «Электронное колесо», М.: «Знание», «Радиоэлектроника и связь», №5, 1991 г., рис. 6, стр. 18-20], - принятый нами за прототип, характеризующийся применением комбинаторного устройства, базирующегося на n-разрядном электронном колесе - двоичном генераторе, охваченных управляемой обратной связью, обеспечивающем генерацию при различных вариантах обратной связи (ВОС) и одновременно при сдвигах информации влево или вправо и при четном или нечетном суммировании - в соответствующих различных режимах, для каждого из которых генерируют свою, отличную от других режимов, пакет кодов, причем для получения генерации, состоящей из нескольких пакетов, по завершении генерации каждой цепочки переключают режим работы генератора.

Недостатком известного способа является то, что момент переключения режимов (из текущего в очередной) определяют путем отсчета числа синхротактов генерации, равного 2ⁿ и соответствующего самой длинной цепочке кодов (один цикл или один пакет) для не вырождающейся генерации. Между тем, для многих режимов имеет место вырождающаяся генерация с более короткой цепочкой кодов, в результате чего на последних синхротактах начнется повтор начальной части цепочки кодов, что снижает качество генерируемой ПСДП в целом. Качественная ПСДП (в том числе и составная) должна иметь как можно более длинную цепочку кодов одного цикла и без их макроповторов, т.е. когда для любой части кодов больше n внутри одного цикла ее первая половина не равна второй.

Другим недостатком прототипа является то, что в нем ставилась задача получения многопакетной генерации для тестовых наборов технической диагностики или команд управления и т.п. (при этом увеличение длины генерации является отрицательным критерием), но не ставилась задача получения ПСДП максимальной длины на данном n-разрядном генераторе без макроповторов, что важно для использования в задачах со случайными процессами, игровых и т.п.

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

Указанная цель достигается использованием Способа формирования псевдослучайной двоичной последовательности для однокоординатных датчиков перемещений, включающего в себя генерацию двоичных кодов при формировании Т-последовательности, дополнительно включает использование ориентированного дерева формирования Т-последовательности, выполнение анализа данных при построении и обходе ациклического направленного графа, динамический анализ графа путем одновременного построения и обхода графа по предварительно сформулированным правилам в отношении структуры и направления обхода с учетом заданных начальных условий:

а) структуру, порядок построения и приоритет направления обхода ориентированного дерева определяют алфавитом, т.е. порядком элементов алфавита a₁, a₂, …, a_k; символ алфавита a₁ является корнем; все узлы имеют одинаковый состав потомков a₁, a₂, …, a_k;

б) в процессе обхода контролируют список сформированных слов на уникальность; при обходе вводят запреты 1 рода - запрет слова с возвратом к предку из-за не уникальности слова; запреты 2 рода - запрет слова с возвратом к предку из-за отсутствия возможных приоритетных вариантов движения вниз;

в) критерием завершения построения и обхода дерева назначают момент формирования множества (списка) W_{(k, n)} с количеством слов N_{T(k, n)} равным

N_{T(k, n)}=kⁿ.

Иллюстраций три: На фиг. 1 представлен циклический графа де Брёйна, на фиг. 2 представлена схема использовании сдвиговых регистров с нелинейной обратной связью, а на фиг. 3 представлено ориентированное дерево формирования Т-последовательности.

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

Метод основан на выполнении анализа данных при построении и обходе ациклического направленного графа, т.е. на анализе ориентированного дерева. Отсюда название частного случая - Т-последовательность (от англ. Tree- дерево). В результате анализа данных формируется последовательность чисел с заданными свойствами «окна» и «цикличности».

Перед рассмотрением предлагаемого метода введем понятие динамического анализа графа: динамическим анализом графа называется процесс одновременного построения и обхода графа по предварительно сформулированным правилам в отношении структуры и направления обхода с учетом заданных начальных условий.

Сформулируем основные положения метода.

Пусть заданы элементы структуры и начальные условия в виде алфавита символов

A_k={а₁, а₂, …, a_k},

где k - мощность множества символов алфавита,

а также задана n - мощность подмножества символов слова (длина слова).

Тогда для формирования Т-последовательности необходимо выполнение следующих правил:

а) структура, порядок построения и приоритет направления обхода ориентированного дерева определяется алфавитом, т.е. порядком элементов алфавита а₁, а₂, …, a_k, символ алфавита а₁ является корнем; все узлы имеют одинаковый состав потомков a₁, а₂, …, a_k;

б) в процессе обхода контролируется список сформированных слов на уникальность; при обходе существуют запреты: 1 рода - запрет слова с возвратом к предку из-за не уникальности слова; 2 рода - запрет слова с возвратом к предку из-за отсутствия возможных приоритетных вариантов движения вниз;

в) критерием завершения построения и обхода дерева является формирование множества (списка) W_{(k, n)} с количеством слов N_{T(k, n)} равным

Отметим, что мощность множества элементов искомой Т-последовательности также определяется выражением (1).

В качестве примера, реализующего предлагаемый метод, рассмотрим случай формирования числовой бинарной последовательности, состоящей из символов алфавита А₂={0, 1}, т.е. мощность множества символов алфавита k=2, и мощность подмножества символов слова n=2.

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

На основании (1) при динамическом анализе необходимо получить множество из N_T(2,2) уникальных слов для формирования Т-последовательности мощностью:

Для заданных условий в соответствии с принятыми правилами имеем динамически построенное ориентированное дерево (фиг. 3).

Заметим, что в процессе построения и обхода в узлах с номерами 3, 7 и 8 возникали запреты 1 рода, а в узле номер 5 - запрет 2 рода; узлы 2, 10 не обходятся.

В результате динамического анализа дерева имеем подмножество слов требуемой мощности (2)

W_(2,2)={00,01,11,10}.

Для удобства представим полученное множество W_(2,2) в виде таблицы W размерностью n×N_T(2,2), в которой каждый столбец соответствует слову из подмножества

В данной таблице первая строка и является искомой Т-последовательностью

Нетрудно заметить, что и вторая строка таблицы W представляет собой ту же Т-последовательность, но сдвинутую циклически на 1 такт.

В соответствии с таблицей 1 для случая k=n=2 должно существовать единственное решение для цикла де Брёйна.

Для доказательства этого факта необходимо применить предложенный метод с новыми начальными условиями: заменим исходный алфавит на единственно возможный альтернативный вариант А₂={1, 0}, т.е. поменяем местами символы алфавита при k=2, и длине слов n=2.

Получим ориентированное дерево, аналогичное представленному на рисунке 1, но с инверсными значениями в узлах. Как следствие, имеем альтернативную Т_А-последовательность

Т_А(2,2)={1100}.

Сравнивая полученную альтернативную Т_А-последовательность с последовательностью (3), видим, что это одна и та же последовательность с циклическим сдвигом в 2 такта, или инверсия первоначально полученной последовательности.

Полученный результат подтверждает, что решение в виде Т-последовательности является единственным при заданных начальных условиях и неизменяемых в процессе построения и обхода правилах.

В таблице 2 приведены полученные в результате применения предложенного метода Т-последовательности для бинарного числового алфавита А₂={0, 1} при различной длине слова n.

Таким образом, предложенный способ позволяет формировать псевдослучайные последовательности в виде Т-последовательности, имеющей свойства «окна» и «цикличности» из любых символов с относительно малыми трудозатратами. Способ может быть использован при решении инженерно-технических задач, не связанных с необходимостью поиска всех возможных вариантов циклов де Брёйна, в частности для формирования шкалы однокоординатных цифровых датчиков линейных и угловых перемещений в приборостроении.

Литература

1. Ожиганов А.А., Захаров И.Д. Применение последовательностей де Брёйна для построения псевдорегулярных кодовых шкал // Научно-технический вестник информационных технологий, механики и оптики, 2012. №2 (78), с. 69-74.

2. Хачатрян Л.Г. Методы построения последовательностей де Брёйна // Дискретная математика, 1992, том 3, выпуск 4, с. 62-78.

3. Ричард Сох, Бернард Коул // Наука и техника, 2007, №7(14).