Генератор нелинейных псевдослучайных последовательностей



Генератор нелинейных псевдослучайных последовательностей
Генератор нелинейных псевдослучайных последовательностей
Генератор нелинейных псевдослучайных последовательностей
Генератор нелинейных псевдослучайных последовательностей
Генератор нелинейных псевдослучайных последовательностей
Генератор нелинейных псевдослучайных последовательностей
Генератор нелинейных псевдослучайных последовательностей
Генератор нелинейных псевдослучайных последовательностей
Генератор нелинейных псевдослучайных последовательностей
Генератор нелинейных псевдослучайных последовательностей
Генератор нелинейных псевдослучайных последовательностей
Генератор нелинейных псевдослучайных последовательностей
Генератор нелинейных псевдослучайных последовательностей
Генератор нелинейных псевдослучайных последовательностей
Генератор нелинейных псевдослучайных последовательностей

 


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

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Казанский национальный исследовательский технический университет им. А.Н. Туполева-КАИ" (КНИТУ-КАИ) (RU)

Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных устройствах для формирования кодовых последовательностей. Технический результат заключается в расширении функциональных возможностей за счет расширения класса формируемых последовательностей путем добавления на h-разрядный выход устройства-прототипа модуля, содержащего h/3 нелинейных преобразователей, каждый из которых имеет три двоичных входа и двухбитовый вход, а также блока из h мультиплексоров с двумя входами данных каждый и с общим управляющим входом. Технический результат достигается за счет того, что в генератор нелинейных псевдослучайных последовательностей введены h/3 однотипных нелинейных преобразователя с тремя входами данных и двумя выходами, hmod3=0, и блок из h мультиплексоров с двумя входами данных каждый и с общим управляющим входом, каждый из нелинейных преобразователей содержит инвертор, четыре функциональных преобразователя и четыре конъюнктора на два входа и два дизъюнктора на два входа. 3 ил., 1 табл.

 

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

Известен генератор нелинейных последовательностей, приведенный в [1], содержащий регистр сдвига из последовательно соединенных триггеров, сумматор по модулю два, второй, третий и четвертый триггеры, сумматор по модулю два, с первого по девятый элементы «И», четыре сумматора по модулю два. Указанный генератор реализован на основе известной схемы генератора линейной М-последовательности [1, к. 1, с. 22-27].

Известен генератор псевдослучайных последовательностей, приведенный в книге [2] на с. 147, (генератор М-последовательностей), выбранный в качестве прототипа, содержащий генератор тактовых импульсов, регистр сдвига с синхровходом, с последовательным входом и с выходом на h разрядов, h умножителей и сумматор по модулю два на h входов.

Устройство-прототип имеет следующие функциональные связи.

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

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

При фиксированной разрядности h сдвигового регистра устройство позволяет формировать за счет применения h умножителей возможное количество (объем) различающихся М-последовательностей с периодом N=2h-1 (под различающимися М-последовательностями понимаются последовательности, каждую из которых нельзя было бы представить в виде циклического сдвига любой другой), определяемое по формуле вида [3, с. 33.]

,

где φ(N) - функция Эйлера (при h=10, Q1=60).

Известные свойства М-последовательностей показывают, что, несмотря на достаточно большой период и хорошие статистические качества, последовательности этого класса имеют простое аналитическое строение. Данный недостаток является следствием того, что М-последовательности формируются (в том числе и в устройстве - прототипе) на основе класса невырожденных двоичных матриц, связанных с классом примитивных полиномов над полем GF(2) и их схемная реализация сводится к применению одного типа линейных операций «сложение по модулю два».

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

На выходе модуля можно получать последовательности двоичных n-разрядных чисел, n=(2/3)·h, hmod3=0, с периодом N=2h-1 из класса нелинейных периодических последовательностей или последовательности двоичных h-разрядных чисел с периодом N=2h-1 из класса М-последовательностей.

Добавленный модуль, содержащий h/3 нелинейных преобразователей, функционально реализует нелинейную функцию аналитического усложнения поступающей на его вход М-последовательности.

На выходе модуля получаем двоичное псевдослучайное число, характер которого зависит от значения на общем управляющем входе блока из h мультиплексоров. Либо это h-разрядное число, формируемое генератором М-последовательности, либо n-разрядное число, снимаемое с генератора нелинейных псевдослучайных последовательностей, n=(2/3)·h, при условии, что hmod3=0.

Нелинейная функция усложнения описывается следующим образом. Рассмотрим преобразование, представляемое в виде отображения (1), где GF(2)n множество n-разрядных двоичных векторов над полем GF(2)={0, 1}.

Примем ограничение: отображение (1) является биективным преобразованием (биекцией), n - четное. Всего имеется 2n! различных биекций [4].

Определим линейное преобразование вектора Х в виде:

где А - двоичная невырожденная матрица размера n и равенство понимается по модулю 2. Число линейных невырожденных преобразований, выполняемых по формуле (2), определяется числом невырожденных матриц по соотношению [5]:

Далее будем рассматривать невырожденные преобразования и ограничимся рассмотрением преобразований над двумя переменными.

Разобьем вектор X на непересекающиеся пары переменных (x2i-1, x2i), i = 1, n / 2 ¯ . Линейному преобразованию над двумя переменными (x2i-1, x2i), выполняемому по формуле (2), поставим в соответствие линейный операционный преобразователь (ОПL) от двух переменных, имеющий двухбитовый выход.

Отображению (1) при n=2 соответствует 22!=24 биекции, что больше числа (определяемого по формуле (3)) линейных преобразований, представляемых невырожденными матрицами размера 2.

Рассмотрим аффинные преобразования, представляемые по формуле:

где вектор В∈GF(2)n, символ ⊕ - обозначение операции суммирования по модулю 2. Число аффинных преобразований определяется формулой:

Аффинному преобразованию над парой переменных (x2i-1, x2i), осуществляемому по формуле (4), ставим в соответствие операционный преобразователь (ОПaff). В этом случае, как следует из (5), число различных ОПaff равно 24. Множество всех этих ОПaff обозначим символом Пaff.

Операционные преобразователи ОПL и ОПaff будем называть эквивалентными, если для вектора (x2i-1, x2i), i = 1, n / 2 ¯ , биективные преобразования вектора (x2i-1, x2i) в вектор (z2i-1, z2i), i = 1, n / 2 ¯ , выполняемые в ОПL, и ОПaff, удовлетворяют условию ZL=Zaff.

Обозначим символом ПL={ОПLi}, i = 1,24 ¯ , множество ОПL, эквивалентных ОПaff∈Пaff. Введем в рассмотрение систему - транспонированный кортеж вида

где m=n/2, gi - некоторое линейное биективное преобразование над вектором (x2i-1, x2i), i = 1, n / 2 ¯ , выполняемое по формуле (2) соответствующим линейным операционным преобразователем ОПL.

Вследствие биективности преобразований gi, i = 1, n / 2 ¯ , система (6) описывает выполнение биективного преобразования вектора Х=(х1, х2, …, xn) в вектор Z=(z1, z2, …, zn). Систему (6) будем рассматривать как модель функции усложнения, реализующей отображение (1).

Обозначим символом ML={Ai}, множество невырожденных матриц Ai, размера 3 вида:

элементы а11, а12, b1, а21, а22 и b2 принимают значения 0 или 1. Введем следующее подмножество MB множества ML: MB={A14, А19, А7}, где (значения индекса i из интервала [1, 24] присвоены этим трем матрицам произвольно). Множество MB является базисом, порождающим множество ML.

Путем композиции (произведения) базисных матриц построим в соответствии с [6] все остальные матрицы множества ML. В таблице 1 дано представление множества матриц ML в базисе MB.

Матрицы, представленные в таблице 1, однозначно соответствуют 24-м аффинным преобразованиям вида:

т.е. реализуют все биективные преобразования от двух переменных и ОПLi∈ПL можно задать матрицей Ai∈ML, где в качестве входного вектора используем расширение вектора (x2i-1, x2i), представляемое вектором (x2i-1, x2i, 1).

Отсюда следует, что ОПLi∈ПL можно задать 1) матрицей Ai∈ML, где в качестве входного вектора используется расширение вектора (x2i-1, x2i), представляемое вектором (x2i-1, x2i, 1) или 2) по формуле (8), на основе значений а11, а12, b1, а21, а22 и b2, заданных по матрицам вида (7), представленным в таблице 1.

Представим нелинейную модель функции усложнения на основе системы ОПLi∈ПL.

Рассмотрим преобразование двоичной последовательности, представляемое в виде отображения

пространства GF(2)g h-мерных, h=n+m, nmod2=0, векторов V=(X, Y)=(x1, x2, …, xn, y1, y2, …, ym) в пространство GF(2)n и-мерных векторов Z=(z1, z2, …, zn) над полем GF(2). В преобразовании (9) вектор V рассматривается как конкатенация векторов Х=(х1, x2, …, xn) и Y=(y1, y2, …, ym), m=n/2, где вектор Х - преобразуемый, а вектор Y - управляющий.

Отображение (9) зависит от управляющего вектора Y. Известно [4], что при таком способе преобразования нелинейность последовательности векторов Z в (9) проявляется ввиду существования этой зависимости.

Пусть периодическая последовательность векторов V=(Х, Y)=(x1, x2, …, xn, y1, y2, …, ym) в (9) формируется генератором псевдослучайных М-последовательностей с периодом L=2h-1, основанном на линейном регистре сдвига, длина которого, h, отвечает условию (10)

где nmod2=0, m=n/2, hmod3=0.

Будем рассматривать эту М-последовательность как последовательность векторов Х=(х1, x2, …, xh) размера h. Разобьем вектор X на непересекающиеся триграммы переменных (x3i-2, x3i-1, x3i), где i=1, …, n/2. В каждой триграмме переменную x3i будем рассматривать как управляющую переменную yi из управляющего вектора Y=(y1, y2, …, ym), m=n/2. Период последовательности векторов Z=(z1, z2, …, zn) в этом случае равен L=2h-1.

Преобразование (9) при данных ограничениях является моделью рассматриваемой нелинейной функции усложнения. При фиксированном управляющем векторе Y отображение (9) выполняет биективное преобразование [4].

Структурное представление нелинейной векторной функции усложнения. Введем операционный преобразователь ОПн от 3-х переменных, имеющий 2-битовый выход. В качестве входного вектора элемента ОПн используем вектор (x3i-2, x3i-1, x3i), i=1, …, n/2. ОПн осуществляет нелинейное преобразование вектора (x3i-2, x3i-1, x3i) в вектор (z2i-1, z2i), где i=1, 2, …, n/2. В каждой триграмме (x3i-2, x3i-1, x3i), i=1, …, n/2 переменная x 3i является управляющей. ОПн представим как пару ОПLi∈ПL. В ОПн один ОПLi∈ПL выполняет преобразование над вектором (x3i-2, x3i-1, 1) при x 3i=0, а второй ОПLi∈ПL выполняет преобразование над вектором (x3i-2, x3i-1, 1) при x3i=1. Нелинейность преобразования в ОПн реализуется ввиду зависимости операции, выполняемой в ОПн, от управляющего бита. Объединение ОПн рассматривается как реализация отображения (9).

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

Предлагаемое устройство позволяет увеличить объем формируемых последовательностей с периодом N=2h-1 до величины Q=(n/2)!, n=(2/3)·h. Например, для h=48 Q=16!+20,9·1012.

Величину ансамбля Q при фиксированной входной М-последовательности можно менять следующим образом.

1) применяя в блоках ОПн различные сочетания блоков ОПLi∈ПL. Максимальное число сочетаний (и соответственно максимальное число различающихся ОПн) равно величине C 24 2 = 276 .

2) путем перестановки блоков ОПн (при этом можно учитывать, что максимальное число различающихся ОПн, равное величине 276, достигается при h=828, что следует из (10)).

В этом случае максимальная величина ансамбля Q, получаемая путем перестановки различных блоков ОПн (при h=828), определяется величиной Q=276!.

Технический результат в генераторе нелинейных псевдослучайных последовательностей, содержащем генератор тактовых импульсов, регистр сдвига на h разрядов с синхровходом и с последовательным входом, h умножителей, каждый из которых на два входа и один выход, и сумматор по модулю два на h входов, достигается тем, что в него введены h/3 однотипных нелинейных преобразователей с тремя входами данных и двумя выходами каждый, hmod3=0, и блок из h мультиплексоров с двумя входами данных каждый и с общим управляющим входом, каждый из нелинейных преобразователей содержит инвертор, четыре функциональных преобразователя и четыре конъюнктора на два входа каждый, из которых первый и второй входят в первую группу конъюнкторов, а третий и четвертый - во вторую группу конъюнкторов, и два дизъюнктора на два входа каждый, каждый функциональный преобразователь имеет три входа задания преобразования, вход инициализации, два входа данных и выход, содержит параллельный регистр на три разряда с входом инициализации, два двухвходовых сумматора по модулю два и трехвходовый сумматор по модулю два, причем генератор тактовых импульсов соединен с синхровходом регистра сдвига, каждый из выходов которого соединен с первым входом умножителя соответственно, второй вход которого является входом для подачи заданных констант, принимающих значения «0» или «1», выходы каждого из h умножителей соединены с входами сумматора по модулю два соответственно, выход которого соединен с последовательным входом регистра сдвига, выходы которого под номерами (3i-2), (3i-1) и 3i соединены с входами данных i-го нелинейного преобразователя соответственно, а также с первыми входами данных блока мультиплексоров под номерами (3i-2), (3i-1) и 3i, i = 1, h / 3 ¯ , соответственно, выходы данных каждого из n/2 нелинейных преобразователей соединены со вторыми входами данных блока мультиплексоров под номерами с 1 по n соответственно, на вторые входы данных блока мультиплексоров под номерами с (n+1) по h являются входами для подачи значений «0», n=2h/3 соответственно, общий управляющий вход блока мультиплексоров является входом конфигурации, а h выходов блока мультиплексоров являются выходами генератора; первый вход данных нелинейного преобразователя соединен с первым входом данных каждого из четырех функциональных преобразователей, второй вход данных нелинейного преобразователя соединен со вторым входом каждого из четырех функциональных преобразователей, третий вход данных нелинейного преобразователя соединен с входом первого конъюнктора на два входа первой группы, с входом четвертого конъюнктора на два входа второй группы и с входом инвертора, выход инвертора соединен с входом второго конъюнктора на два входа первой группы и с входом третьего конъюнктора на два входа второй группы; выходы конъюнкторов на два входа первой группы соединены с входами первого дизъюнктора на два входа соответственно, выход которого соединен с первым выходом нелинейного преобразователя, а выходы конъюнкторов на два входа второй группы соединены с входами второго дизъюнктора на два входа соответственно, выход которого соединен со вторым выходом нелинейного преобразователя; входы задания преобразования и вход инициализации функционального преобразователя соединены с входами данных и инициализации параллельного регистра на три разряда с входом инициализации соответственно, первый выход данных параллельного регистра на три разряда соединен с входом первого двухвходового сумматора по модулю два, второй выход данных параллельного регистра на три разряда соединен с входом второго двухвходового сумматора по модулю два, третий выход данных параллельного регистра на три разряда соединен с входом трехвходового сумматора по модулю два, два входа которого соединены с выходами сумматоров по модулю два соответственно, а выход трехвходового сумматора соединен с выходом функционального преобразователя; вход первого двухвходового сумматора по модулю два соединен с первым входом данных функционального преобразователя, а вход второго двухвходового сумматора по модулю два соединен со вторым входом данных функционального преобразователя.

Схема генератора нелинейных псевдослучайных последовательностей приведена на фиг. 1, блока нелинейного преобразователя приведена на фиг. 2, а схема блока функционального преобразователя - на фиг. 3.

Генератор нелинейных псевдослучайных последовательностей (фиг. 1) содержит генератор 1 тактовых импульсов, регистр 2 сдвига на h разрядов с синхровходом и с последовательным входом, умножители 3k, k = 1, h ¯ , каждый из которых на два входа и один выход, и сумматор 4 по модулю два на h входов, нелинейные преобразователи 5l с тремя входами данных и двумя выходами каждый, l = 1, ( n / 2 ) ¯ , n=(2/3)·h, блок 6 мультиплексоров с двумя входами данных каждый и с общим управляющим входом 7, выход блока 6 мультиплексоров является h-разрядным выходом 8 генератора нелинейных псевдослучайных последовательностей, причем генератор 1 тактовых импульсов соединен с синхровходом регистра 2 сдвига, k-й выход которого соединен с входом умножителя 3k, на второй вход каждого из которых - 27k, k = 1, h ¯ , подаются константы, «0» или «1», соответствующие коэффициентам примитивного неприводимого полинома [7], образующего М-последовательность для генератора, приведенного в книге [2] на с. 147, фиг. 4.2.3, выход каждого из умножителей 3k, k = 1, h ¯ , соединен с k-м входом сумматора 4 по модулю два, выход которого соединен с последовательным входом регистра 2 сдвига, выходы которого с (3i-2)-го по 3i-й соединены с входами данных под номерами 13, 14 и 15 соответственно нелинейного преобразователя 5i, i = 1, n / 2 ¯ , представленного на фиг. 2, и с первыми входами данных блока 6 мультиплексоров под номерами с (3i-2) по 3i, выходы данных каждого из нелинейных преобразователей 5i, i = 1, n / 2 ¯ , под номерами 16 и 17, представленные на фиг. 2, соединены со вторыми входами данных блока 6 мультиплексоров под номерами с 1 по n, вторые входы 28 данных блока 6 мультиплексоров под номерами с (n+1) по h являются входами для подачи значение «0», n=2h/3, управляющий вход 7 блока 6 мультиплексоров является входом конфигурации, а выход 8 блока 6 мультиплексоров является h-разрядным выходом генератора нелинейных псевдослучайных последовательностей.

На фиг. 2 представлен нелинейный преобразователь 5i, i = 1, n / 2 ¯ , n/2=h/3, который включает четыре функциональных преобразователя 91-94, четыре конъюнктора 101-104 на два входа, из которых 101 и 102 входят в первую группу, 103 и 104 - во вторую группу, инвертор 11, два дизъюнктора 121 и 122 на два входа, три входа данных - 13, 14 и 15, а также два выхода 16 и 17, при этом вход 13 нелинейного преобразователя является первым входом 24 каждого из функциональных преобразователей 91-94, представленных на фиг. 3, вход 14 нелинейного преобразователя является вторым входом 25 каждого из функциональных преобразователей 91-94 (см. фиг. 3), выход 26 каждого из функциональных преобразователей 9j (см. фиг. 3) соединен со входом конъюнктора 10j на два входа соответственно, j = 1,4 ¯ , вход 15 нелинейного преобразователя соединен с входами конъюнкторов 101 и 104 на два входа и входом инвертора 11 соответственно, выход инвертора 11 соединен с входами конъюнкторов 102 и 103 на два входа соответственно, выходы конъюнкторов 101 и 102 на два входа соединены с входами дизъюнктора 121 на два входа соответственно, выходы конъюнкторов 103 и 104 на два входа соединены с входами дизъюнктора 122 на два входа соответственно, выходы дизъюнкторов 121 и 122 являются выходами 16 и 17 нелинейного преобразователя соответственно.

На фиг. 3 представлен функциональный преобразователь 9j, j = 1,4 ¯ , который содержит параллельный регистр 18 на три разряда с входом инициализации, двухвходовые сумматоры 19 и 20 по модулю два, трехвходовый сумматор 21 по модулю два, вход 22 задания преобразования, вход 23 инициализации, входы 24 и 25 данных и выход 26, при этом вход задания преобразования 22 соединен с входом данных параллельного регистра 18 на три разряда с входом инициализации, вход 23 инициализации соединен с входом инициализации параллельного регистра 18 на три разряда с входом инициализации, первый выход параллельного регистра 18 на три разряда с входом инициализации соединен с входом двухвходового сумматора 19 по модулю два, второй выход параллельного регистра 18 на три разряда с входом инициализации соединен с входом двухвходового сумматора 20 по модулю два, третий выход параллельного регистра 18 на три разряда с входом инициализации соединен с входом трехвходового сумматора 21 по модулю два, входы которого соединены с выходами двухвходовых сумматоров 19 и 20 по модулю два, выход трехвходового сумматора 21 по модулю два является выходом 26 функционального преобразователя, входы данных 24 и 25 функционального преобразователя соединены с входами двухвходовых сумматоров 19 и 20 по модулю два соответственно.

Все блоки, приведенные на фиг. 1, фиг. 2 и фиг. 3, имеют стандартную и опубликованную в литературе реализацию, а также имеют входы электропитания, которые не изображены на фиг. 1, фиг. 2 и фиг. 3.

Рассмотрим генератор нелинейных псевдослучайных последовательностей в работе. В предлагаемом генераторе, как и в [1], вычисление элементов псевдослучайных последовательностей производится на основе генератора М-последовательности. По сравнению с прототипом ([2] на с. 147), в устройство введены: n/2=h/3 однотипных нелинейных преобразователя 5i, i = 1, n / 2 ¯ , с тремя входами данных и двумя выходами, n=(2/3)·h, hmod3=0, и блок 6 мультиплексоров с общим управляющим входом 7, выход 8 блока 6 является h-разрядным выходом генератора нелинейных псевдослучайных последовательностей; каждый из нелинейных преобразователей 5i, i = 1, n / 2 ¯ , включает по четыре функциональных преобразователя 91-94, четыре конъюнктора 101-104 на два входа, из которых 101 и 102 входят в первую группу, а 103 и 104 - во вторую группу, инвертор 11, два дизъюнктора 121 и 122 на два входа, каждый функциональный преобразователь 9j, j = 1,4 ¯ , включает параллельный регистр 18 на три разряда с входом инициализации, двухвходовые сумматоры 19 и 20 по модулю два, трехвходовый сумматор 21 по модулю два.

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

где z1 и z2 вычисляются согласно (8) на основе значений a11, а12, b1, а21, а22 и b2, заданных по матрицам (7) при инициализации функциональных преобразователей, а значения (x1=x 3i-2, x2=x 3i-1, yi=x3i), i = 1, ( n / 2 ) ¯ , поступают с выхода генератора М-последовательности (прототипа), приведенного в книге [2] на с. 147, фиг. 4.2.3.

Техническая реализация процедуры (11) в виде блока нелинейного преобразователя, позволяет увеличить объем формируемых последовательностей с периодом N=2h-1 до величины Q=(n/2)!, n=(2/3)·h, где возможная максимальная величина - Q, получаемая путем перестановки различных блоков ОПн, определяется как Q=276! при h=828 (n=552).

При этом блок нелинейного преобразователя позволяет получить последовательность с периодом N=2h-1 согласно формуле вида (11).

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

Значения элементов М-последовательности, h-разрядные числа X, формируемые по синхросигналу, подаваемому с генератора 1 тактовых импульсов на синхровход регистра 2 сдвига, поступают с выходов регистра 2 сдвига на входы данных нелинейных преобразователей 5i, i = 1, n / 2 ¯ . По синхросигналу, поступающему с генератора 1 тактовых импульсов, значения Х={{x2l-1, x2l, yl}}, поступают на входы 13, 14 и 15 данных каждого из нелинейных преобразователей 5l, с выходов 16 и 17 каждого из которых снимаются значения Z={(z2l-1, z2l)}, соответственно, l = 1, ( n / 2 ) ¯ (фиг. 2). Выходы 16 и 17 каждого из нелинейных преобразователей 5l, l = 1, ( n / 2 ) ¯ , общее количество которых равно n, соединены с вторыми входами данных блока 6 мультиплексоров под номерами с 1 по n, n=2h/3, на вторые входы 28 данных блока 6 мультиплексоров под номерами с (n+1) по h подано значение «0», с первыми входами данных блока 6 мультиплексоров соединены выходы данных регистра 2 сдвига, общий вход 7 блока 6 мультиплексоров является входом конфигурации, а выход 8 блока 6 мультиплексоров является выходом генератора нелинейных псевдослучайных последовательностей.

При подаче напряжения питания происходит инициализация генератора нелинейных псевдослучайных последовательностей.

На этапе инициализации на вход 23 (фиг. 2) инициализации параллельного регистра 18 на три разряда с входом инициализации поступает сигнал (значение «1»), согласно которому в регистр 18 на три разряда с входом инициализации заносится информация о выполняемом преобразовании согласно формуле (7): на вход 22 задания преобразования функциональных преобразователей 91 и 93 каждого из нелинейных преобразователей 5l, l = 1, ( n / 2 ) ¯ , поступают значения а11, а21 и b1 на первый, второй и третий разряды параллельного регистра 18 на три разряда с входом инициализации соответственно, а на вход 22 задания преобразования функциональных преобразователей 92 и 94 каждого из нелинейных преобразователей 5l, l = 1, ( n / 2 ) ¯ , поступают значения а21, а22 и b2 на первый, второй и третий разряды параллельного регистра 18 на три разряда с входом инициализации соответственно. При этом в каждый из нелинейных преобразователей 5l, l = 1, ( n / 2 ) ¯ , заносятся свои значения а11, а12, b1, а21, а22 и b2, задающие одно из аффинных преобразований (биекций) вида (7).

Если на выходе 8 генератора требуется получить значения М-последовательности, то на вход 7 конфигурации генератора псевдослучайных чисел требуется подать значение «0», если же на выходе 8 генератора требуется получить значения нелинейной последовательности, то на вход 7 конфигурации требуется подать значение «1».

На этапе функционирования, с генератора 1 тактовых импульсов поступает синхросигнал на синхровход регистра 2 сдвига. В данной связи в регистра 2 сдвига производится логический сдвиг двоичных значений его разрядов, а значение, формируемое на его последовательном входе при использовании умножителей 31, …, 3h и сумматора 4 по модулю два, заносится в младший разряд регистра 2 сдвига, n двоичных значений из регистра 2 сдвига поступают на входы нелинейных преобразователей 5l, n=(2/3)·h, hmod3=0, причем значения (x2l-1, x2l, yl) поступают на входы 13, 14 и 15 данных нелинейного преобразователя 5l, l = 1, ( n / 2 ) ¯ , внутри которого значения с входов 13 и 14 данных поступают на входы 24 и 25 данных каждого из функциональных преобразователей 91, …, 94 соответственно, а с входа данных 15 - на входы конъюнкторов 101 и 104 на два входа и инвертора 11, с выхода которого значения поступают на входы конъюнкторов 102 и 103 на два входа; внутри каждого из функциональных преобразователей 91, …, 94 значения, поступившие на входы 24 и 25 данных поступают на один из входов двухвходовых сумматоров 19 и 20 по модулю два, значения с выходов двухвходовых сумматоров 19 и 20 поступают на два входа трехвходового сумматора 21 по модулю два, значение с выхода которого поступает на выход 26 каждого из функциональных преобразователей 91, …, 94; значения с выходов функциональных преобразователей 91, …, 94 поступают на входы конъюнкторов 101, …, 104 соответственно, значения с выходов конъюнкторов 101 и 102 поступают на входы дизъюнктора 121 на два входа, а значения с выходов конъюнкторов 103 и 104 поступают на входы дизъюнктора 122 на два входа, с выходов дизъюнкторов 121 и 122 на два входа, которые являются выходами 16 и 17 нелинейного преобразователя 5l, снимаются значения (z2l-1, z2l), l = 1, ( n / 2 ) ¯ , поступающие на вторые входы данных блока 6 мультиплексоров под номерами с 1 по n, на вторые входы 28 данных блока 6 мультиплексоров под номерами с (n+1) по h подано значение «0», на первый вход блока 6 мультиплексоров поступают данные с h-разрядного регистра 2 сдвига, значение на общем управляющем входе 7 блока 6 мультиплексоров позволяет выбрать, какая из последовательностей, линейная или нелинейная, поступит на выход 8 блока 6 мультиплексоров. Выход 8 является h-разрядным выходом генератора нелинейных псевдослучайных последовательностей, на который поступают h значений из регистра 2 сдвига (М-последовательность) при подаче на управляющий вход 7 значения «0», тогда как при подаче на вход 7 значения «1», на n разрядов h-разрядного выхода 8 поступают значения, снимаемые с n/2 нелинейных преобразователей 5l, l = 1, ( n / 2 ) ¯ , n=2h/3.

Таким образом, введение в генератор нелинейных псевдослучайных последовательностей h/3 однотипных нелинейных преобразователей с тремя входами данных и двумя выходами каждый, а также блока из h мультиплексоров с двумя входами данных каждый и с общим управляющим входом, позволяет увеличить объем формируемых максимальных периодических последовательностей до величины Q=(n/2)!, n=(2/3)·h, hmod3=0, где h - количество двоичных разрядов чисел, снимаемых с выхода регистра сдвига, целое положительное число.

Источники информации

1. Пат. 1413616 SU, МПК4 G06F 1/02. Генератор нелинейных последовательностей / П.Г. Тараненко, Ю.И. Лютынский, А.В. Астанин и др. №4183715/24-24; заявл. 19.01.1987; опубл. 30.07.1988, Бюл. №28. 3 с.: ил.

2. Шумоподобные сигналы в системах передачи информации / В.Б. Пестряков, В.П. Афанасьев, В.Л. Гурвич и др. - М.: Сов. радио, 1973. - 424 с.

3. Свердлик М.Б. Оптимальные системы и сигналы. - М.: Сов. радио, 1975. - 200 с.

4. Молдовян Н.А., Молдовян А.А., Еремеев М. А. Криптография: от примитивов к синтезу алгоритмов. - СПб.: БХВ-Петербург, 2004. - 448 с.

5. Gunter, W. Linear transformations and exact minimization of BDDs / W. Gunter, R. Drechsler // IEEE Great Lakes Symposium on VLSI, Lafayette. - 1998. - P. 325-330.

6. Колпаков А.В. Методы и алгоритмы линейных и аффинных преобразований для модели бинарных диаграмм решений. Дисс. … канд. техн. наук: 05.13.18. - Казань, 2004.

7. Бухштаб А.А. Теория чисел / А.А. Бухштаб. - М.: Просвещение, 1966. - 384 с.

Генератор нелинейных псевдослучайных последовательностей, содержащий генератор тактовых импульсов, регистр сдвига на h разрядов с синхровходом и с последовательным входом, h умножителей, каждый из которых на два входа и один выход, и сумматор по модулю два на h входов, отличающийся тем, что в него введены h/3 однотипных нелинейных преобразователей с тремя входами данных и двумя выходами каждый, hmod3=0, и блок из h мультиплексоров с двумя входами данных каждый и с общим управляющим входом, каждый из нелинейных преобразователей содержит инвертор, четыре функциональных преобразователя и четыре конъюнктора на два входа каждый, из которых первый и второй входят в первую группу конъюнкторов, а третий и четвертый - во вторую группу конъюнкторов, и два дизъюнктора на два входа каждый, каждый функциональный преобразователь имеет три входа задания преобразования, вход инициализации, два входа данных и выход, содержит параллельный регистр на три разряда с входом инициализации, два двухвходовых сумматора по модулю два и трехвходовый сумматор по модулю два, причем генератор тактовых импульсов соединен с синхровходом регистра сдвига, каждый из выходов которого соединен с первым входом умножителя соответственно, второй вход которого является входом для подачи заданных констант, принимающих значения «0» или «1», выходы каждого из h умножителей соединены с входами сумматора по модулю два соответственно, выход которого соединен с последовательным входом регистра сдвига, выходы которого под номерами (3i-2), (3i-1) и 3i соединены с входами данных i-го нелинейного преобразователя соответственно, а также с первыми входами данных блока мультиплексоров под номерами (3i-2), (3i-1) и 3i, , соответственно, выходы данных каждого из n/2 нелинейных преобразователей соединены со вторыми входами данных блока мультиплексоров под номерами с 1 по n соответственно, на вторые входы данных блока мультиплексоров под номерами с (n+1) по h являются входами для подачи значений «0», n=2h/3 соответственно, общий управляющий вход блока мультиплексоров является входом конфигурации, a h выходов блока мультиплексоров являются выходами генератора; первый вход данных нелинейного преобразователя соединен с первым входом данных каждого из четырех функциональных преобразователей, второй вход данных нелинейного преобразователя соединен со вторым входом каждого из четырех функциональных преобразователей, третий вход данных нелинейного преобразователя соединен с входом первого конъюнктора на два входа первой группы, с входом четвертого конъюнктора на два входа второй группы и с входом инвертора, выход инвертора соединен с входом второго конъюнктора на два входа первой группы и с входом третьего конъюнктора на два входа второй группы; выходы конъюнкторов на два входа первой группы соединены с входами первого дизъюнктора на два входа соответственно, выход которого соединен с первым выходом нелинейного преобразователя, а выходы конъюнкторов на два входа второй группы соединены с входами второго дизъюнктора на два входа соответственно, выход которого соединен со вторым выходом нелинейного преобразователя; входы задания преобразования и вход инициализации функционального преобразователя соединены с входами данных и инициализации параллельного регистра на три разряда с входом инициализации соответственно, первый выход данных параллельного регистра на три разряда соединен с входом первого двухвходового сумматора по модулю два, второй выход данных параллельного регистра на три разряда соединен с входом второго двухвходового сумматора по модулю два, третий выход данных параллельного регистра на три разряда соединен с входом трехвходового сумматора по модулю два, два входа которого соединены с выходами сумматоров по модулю два соответственно, а выход трехвходового сумматора соединен с выходом функционального преобразователя; вход первого двухвходового сумматора по модулю два соединен с первым входом данных функционального преобразователя, а вход второго двухвходового сумматора по модулю два соединен со вторым входом данных функционального преобразователя.



 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Изобретение относится к области вычислительной техники и может быть использовано для генерации случайных чисел. Техническим результатом является повышение точности. Способ генерации равномерно распределенных и независимых случайных чисел с нечетным модулем d и множителем z, взаимно простым с d, начинает с произвольно заданного целого числа n, взаимно простого с d, и рекуррентно порождает последовательность целых чисел {r0, r1, r2, …} при помощи отношений конгруэнтности r0≡n mod(d), 0<r0<d, rk≡zrk-1 mod(d), 0<rk<d, k=1, 2, 3, …, и дает на выходе случайные числа {vk:=rk-1/d| k=1, 2, …}, при этом множитель z выбран таким образом, что удовлетворяет условию, что генератор (d,z′) при z′≡zj mod(d) для целого j по меньшей мере в диапазоне 1≤j≤6 проходит спектральный тест второй степени в пределах оценки 1,25, а именно, для любого целого j в диапазоне 1≤j≤6 генератор (d, z′) при z′≡zj mod(d) удовлетворяет условию, что вектор f дуальной решетки, заданный для (d, z′) посредством линейной комбинации f:=m1f1+m2f2 базисных векторов {f1, f2} дуальной решетки, f1:=(d,0), f2:=(-z′,1), с целочисленными коэффициентами {m1,m2} и длиной ||f||:={(dm1-z′m2)2+(m2)2}1/2>0, имеет наименьший ненулевой вектор fmin с длиной amin (2)(z′):=||fmin||>0, удовлетворяя условию ρd (2)(z′):=21/2d1/2/{31/4amin (2)(z′)}<l,25. 6 ил.

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

Изобретение относится к вычислительной технике и может быть использовано в устройствах, моделирующих случайные процессы. Техническим результатом является получение на компьютерах однородных и независимых случайных чисел. Способ проведения спектральных тестов мультипликативного конгруэнтного генератора (d,z,n) или (d,z), содержащего нечетное целое число d в качестве модуля, а также целое число z, взаимно-простое с d, в качестве множителя, и целое число n, взаимно-простое с d, в качестве начального случайного числа, генерирующего последовательность целых чисел {nk:≡nzk-1 mod(d)| 1≤nk≤d, k=1,2,...} последовательным образом и выдающего на выходе последовательность случайных чисел за счет реализации арифметики {vk:=nk/d| 0≤vk≤1, k=1,2,...}, основан на оценке геометрической формы решетки GL(d,z), в которой занимают свои места L последовательных целых чисел {Qk:=(nk,nk+1,…,nk+L-1)| k=1,2,...}, выданных генератором (d,z,n), посредством вычисления наибольшего расстояния λL(d,z) между параллельными и соседними гиперплоскостями решетки GL(d,z) и оценки ρL′(d,z):=λL(d,z)/ML(d) генератора (d,z) на основе новых контрольных значений ML(d):=L-1/2(L+1)(L-1)/(2L)d(L-1)/L, L≥3, а также принятия решения о прохождении теста (d,z), если условия 1<ρL′(d,z)<RL, 3≤L≤6 выполняются для заданных уровней {RL>1| 3≤L≤6}. 3 ил.

Изобретение относится к защите компьютерной информации. Технический результат - повышение криптостойкости и быстродействия нелинейного преобразования. Способ нелинейного трехмерного многораундового преобразования данных, в котором второй и третий раунды преобразования выполняются аналогично первому: при выполнении преобразований второго и третьего раунда осуществляется деление блока 1 данных S на четыре слоя 4х0, 4x1, 4х2, 4х3 (соответственно Lx0, Lx1, Lx2, Lx3) вдоль оси x; каждый слой Lxk, k=0, 1, 2, 3, представляется в виде квадратного массива байтов 4×4, после чего происходит двумерное стохастическое преобразование 5xk T_Layer каждого слоя Lxk и объединение слоев Lxk в преобразованный блок S; между первым и вторым раундами, а также между вторым и третьим раундами выполняется преобразование 6 перестановки байтов PermBytes; при выполнении преобразования 5xk T_Layer Lxk последовательно выполняются операции замены 9 байтов SubBytes, перемешивания 10 байтов состояния MixState и сложения 11 с раундовым подключом AddRoundSubKey; операция перемешивания 10 байтов состояния MixState выполняется следующим образом: - слой L разбивается на 16 байтов; - суть операции перемешивания байтов состояния - умножение строки байтов состояния на квадратную матрицу 16×16, при этом все операции умножения и сложения элементов строки и матрицы осуществляются в поле GF(28); перемешанные байты объединяются в преобразованный слой L. 5 ил.
Наверх