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



Способ формирования псевдослучайной двоичной последовательности для однокоординатных датчиков перемещений
Способ формирования псевдослучайной двоичной последовательности для однокоординатных датчиков перемещений
Способ формирования псевдослучайной двоичной последовательности для однокоординатных датчиков перемещений
Способ формирования псевдослучайной двоичной последовательности для однокоординатных датчиков перемещений
Способ формирования псевдослучайной двоичной последовательности для однокоординатных датчиков перемещений
Способ формирования псевдослучайной двоичной последовательности для однокоординатных датчиков перемещений
Способ формирования псевдослучайной двоичной последовательности для однокоординатных датчиков перемещений
H03K3/64 - Импульсная техника (измерение импульсных характеристик G01R; механические счетчики с электрическим входом G06M; устройства для накопления /хранения/ информации вообще G11; устройства хранения и выборки информации в электрических аналоговых запоминающих устройствах G11C 27/02; конструкция переключателей для генерации импульсов путем замыкания и размыкания контактов, например с использованием подвижных магнитов, H01H; статическое преобразование электрической энергии H02M;генерирование колебаний с помощью схем, содержащих активные элементы, работающие в некоммутационном режиме, H03B; импульсная модуляция колебаний синусоидальной формы H03C;H04L ; схемы дискриминаторов с подсчетом импульсов H03D;

Владельцы патента RU 2712827:

Акционерное общество Московский научно-производственный комплекс "Авионика" имени О.В. Успенского (АО МНПК "Авионика") (RU)

Изобретение относится к областям информатики и вычислительной техники и может быть использовано для генерации псевдослучайной двоичной последовательности. Техническим результатом является повышение эффективности составления двоичного кода псевдослучайной кодовой шкалы. Генерируют двоичные коды при формировании Т-последовательности. Используют ориентированное дерево формирования Т-последовательности. Выполняют анализ данных при построении и обходе ациклического направленного графа и динамический анализ графа путем одновременного построения и обхода графа по предварительно сформулированным правилам в отношении структуры и направления обхода с учетом заданных начальных условий. Структуру, порядок построения и приоритет направления обхода ориентированного дерева определяют алфавитом, т.е. порядком элементов алфавита a1, а2, …, ak. Символ алфавита а1 является корнем. Все узлы имеют одинаковый состав потомков а1, а2, …, ak. В процессе обхода контролируют список сформированных слов на уникальность. При обходе вводят запреты 1 рода - запрет слова с возвратом к предку из-за неуникальности слова; запреты 2 рода - запрет слова с возвратом к предку из-за отсутствия возможных приоритетных вариантов движения вниз. 3 ил., 2 табл.

 

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

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

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

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

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

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

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

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

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

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

где k - мощность множества символов исходного алфавита Ak={a1, а2, …, ak};

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

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

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

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

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

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

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

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

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

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

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

NT(k, n)=kn.

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

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

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

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

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

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

Ak={а1, а2, …, ak},

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

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

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

а) структура, порядок построения и приоритет направления обхода ориентированного дерева определяется алфавитом, т.е. порядком элементов алфавита а1, а2, …, ak, символ алфавита а1 является корнем; все узлы имеют одинаковый состав потомков a1, а2, …, ak;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

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

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

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

Способ формирования псевдослучайной двоичной последовательности для однокоординатных датчиков перемещений, включающий в себя генерацию двоичных кодов при формировании Т-последовательности, отличающийся тем, что дополнительно включает использование ориентированного дерева формирования Т-последовательности, выполнение анализа данных при построении и обходе ациклического направленного графа, динамический анализ графа путем одновременного построения и обхода графа по предварительно сформулированным правилам в отношении структуры и направления обхода с учетом заданных начальных условий, при этом структуру, порядок построения и приоритет направления обхода ориентированного дерева определяют алфавитом, т.е. порядком элементов алфавита а1, а2, …, ak, символ алфавита a1 является корнем, все узлы имеют одинаковый состав потомков a1, а2, …, ak, в процессе обхода контролируют список сформированных слов на уникальность; при обходе вводят запреты 1 рода - запрет слова с возвратом к предку из-за неуникальности слова, запреты 2 рода - запрет слова с возвратом к предку из-за отсутствия возможных приоритетных вариантов движения вниз, критерием завершения построения и обхода дерева назначают момент формирования множества (списка) W(k, n) с количеством слов NT(k, n), равным NT(k, n)=kn.



 

Похожие патенты:

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

Группа изобретений относится к области радиосвязи и может быть использована в системах связи со сложными сигналами. Техническим результатом является повышение структурной скрытности шумоподобных сигналов на базе нелинейных рекуррентных последовательностей в виде кодов квадратичных вычетов, существующих в простых полях Галуа GF(p).

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

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

Группа изобретений относится к области кодирования и может быть использована для кодирования коэффициентов преобразования. Техническим результатом является снижение сложности и повышение эффективности кодирования.

Изобретение относится к области вычислительной техники. Технический результат заключается в обеспечении достоверной оценки радиационной обстановки.

Изобретение относится к области вычислительной техники. Техническим результатом является снижение пространства памяти, занимаемого XML-файлом, в контейнере печатающего материала, выполненном для установки в принтер.

Заявленное изобретение относится к области передачи телеметрической информации. Технический результат заключается в увеличении потока информации от датчиков с возросшей динамикой.

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

Изобретение относится к импульсной электронике. Технический результат: преобразование входного сигнала в частоту следования импульсов или во временной интервал выходного импульсного напряжения, а также выполнение операции деления входных сигналов.

Группа изобретений относится к области кодирования. Техническим результатом является повышение эффективности кодирования и декодирования данных.

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

Изобретение относится к области кодирования и декодирования изображений. Техническим результатом является способ декодирования изображения, который способен уменьшать объем обработки при одновременном подавлении ухудшения эффективности кодирования.

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

Изобретение относится к аналоговой микроэлектронике. Технический результат заключается в создании радиационно-стойкого и низкотемпературного схемотехнического решения буферного усилителя (БУ) на комплементарных полевых транзисторах, обеспечивающего малые значения напряжения смещения нуля.

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

Изобретение относится к цифровой схемотехнике, автоматике и промышленной электронике. Оно, в частности, может быть использовано в блоках вычислительной техники, построенных на логических элементах.

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

Изобретение относится к аналоговой микроэлектронике. Технический результат заключается в создании условий, которые позволяют повысить быстродействие выходного каскада за счет форсирования процесса перезаряда одного из его паразитных конденсаторов и исключения влияния второго паразитного конденсатора.

Изобретение относится к областям информатики и вычислительной техники и может быть использовано для генерации псевдослучайной двоичной последовательности. Техническим результатом является повышение эффективности составления двоичного кода псевдослучайной кодовой шкалы. Генерируют двоичные коды при формировании Т-последовательности. Используют ориентированное дерево формирования Т-последовательности. Выполняют анализ данных при построении и обходе ациклического направленного графа и динамический анализ графа путем одновременного построения и обхода графа по предварительно сформулированным правилам в отношении структуры и направления обхода с учетом заданных начальных условий. Структуру, порядок построения и приоритет направления обхода ориентированного дерева определяют алфавитом, т.е. порядком элементов алфавита a1, а2, …, ak. Символ алфавита а1 является корнем. Все узлы имеют одинаковый состав потомков а1, а2, …, ak. В процессе обхода контролируют список сформированных слов на уникальность. При обходе вводят запреты 1 рода - запрет слова с возвратом к предку из-за неуникальности слова; запреты 2 рода - запрет слова с возвратом к предку из-за отсутствия возможных приоритетных вариантов движения вниз. 3 ил., 2 табл.

Наверх